SMO算法详解：快速训练支持向量机

5星 · 超过95%的资源需积分: 16 75 浏览量更新于2024-07-23 收藏 88KB PDF 举报

"Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines" 支持向量机（Support Vector Machine，简称SVM）是一种强大的监督学习模型，广泛应用于分类和回归问题。SMO（Sequential Minimal Optimization）算法是由John Platt提出的，用于解决训练SVM时遇到的大规模二次规划（Quadratic Programming, QP）问题的有效方法。 SVM的核心在于寻找最大边距超平面，这个过程实际上是一个复杂的优化问题。传统的解决方法，如内点法，往往计算量大、效率低，尤其在处理大量数据时。而SMO算法则采取了一种创新的方式，将大型的QP问题分解为一系列最小规模的QP问题，这些小问题可以解析求解，避免了耗时的数值优化过程作为内循环。 SMO算法的内存需求与训练集大小呈线性关系，这意味着它可以处理非常大的训练集。在处理速度上，SMO的表现介于训练集大小的线性与二次之间，对于不同的测试问题，这比传统的分块SVM算法（它们的速度通常在线性和立方之间）更为高效。SMO的计算时间主要由支持向量的评估决定，因此，对于线性SVM和稀疏数据集，SMO表现出更快的速度。 SMO算法的工作流程主要包括以下几个步骤： 1. 选择一对违反KKT条件（Karush-Kuhn-Tucker条件）的样本点。 2. 保持其他样本点的拉格朗日乘子不变，调整这对样本点的乘子，以最小化目标函数。 3. 重复步骤1和2，直到所有样本点满足KKT条件或达到预设的终止条件。 4. 在迭代过程中，为了避免过多的迭代，会采用一些策略来选择下一对需要更新的样本点，例如，选择最优化的对或者使用启发式规则。 SMO算法的成功在于其高效性和可扩展性，它为大规模数据集的SVM训练提供了实际可行的解决方案，是机器学习领域中不可或缺的工具之一。尽管后来出现了其他更高效的SVM优化算法，如LibSVM和LIBLINEAR，但SMO算法仍然是理解和实现SVM的基本步骤，对于初学者和研究人员来说具有重要的学习价值。

the entire set of non-zero Lagrange multipliers has been identified, hence the last step solves the

large QP problem.

Chunking seriously reduces the size of the matrix from the number of training examples squared

to approximately the number of non-zero Lagrange multipliers squared. However, chunking still

cannot handle large-scale training problems, since even this reduced matrix cannot fit into

memory.

In 1997, Osuna, et al. [16] proved a theorem which suggests a whole new set of QP algorithms

for SVMs. The theorem proves that the large QP problem can be broken down into a series of

smaller QP sub-problems. As long as at least one example that violates the KKT conditions is

added to the examples for the previous sub-problem, each step will reduce the overall objective

function and maintain a feasible point that obeys all of the constraints. Therefore, a sequence of

QP sub-problems that always add at least one violator will be guaranteed to converge. Notice

that the chunking algorithm obeys the conditions of the theorem, and hence will converge.

Osuna, et al. suggests keeping a constant size matrix for every QP sub-problem, which implies

adding and deleting the same number of examples at every step [16] (see figure 2). Using a

constant-size matrix will allow the training on arbitrarily sized data sets. The algorithm given in

Osuna’s paper [16] suggests adding one example and subtracting one example every step.

Clearly this would be inefficient, because it would use an entire numerical QP optimization step

to cause one training example to obey the KKT conditions. In practice, researchers add and

subtract multiple examples according to unpublished heuristics [17]. In any event, a numerical

QP solver is required for all of these methods. Numerical QP is notoriously tricky to get right;

there are many numerical precision issues that need to be addressed.

Chunking

Osuna

SMO

Figure 2. Three alternative methods for training SVMs: Chunking, Osuna’s algorithm, and SMO. For

each method, three steps are illustrated. The horizontal thin line at every step represents the training

set, while the thick boxes represent the Lagrange multipliers being optimized at that step. For

chunking, a fixed number of examples are added every step, while the zero Lagrange multipliers are

discarded at every step. Thus, the number of examples trained per step tends to grow. For Osuna’s

algorithm, a fixed number of examples are optimized every step: the same number of examples is

added to and discarded from the problem at every step. For SMO, only two examples are analytically

optimized at every step, so that each step is very fast.

剩余20页未读，继续阅读

keaiwenwen

粉丝: 12

SMO算法详解：快速训练支持向量机

SMO算法高效训练：英文文献中的序列最小优化详解

掌握SVM必读经典资料合集

SVM与核方法综述：理论与应用详解

svm算法源码和文献说明 svm算法源码和文献说明 svm算法源码和文献说明

SVM及SMO重要外文文献书籍

smo最经典论文

SVM详解对应斯坦福大学教学视频

matlab SVM函数

支持向量机与核方法学习导论

vue.js v2.5.17

最新资源