支持向量机SMO算法：快速训练技术

需积分: 9 123 浏览量更新于2024-07-24 收藏 101KB PDF 举报

"Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines by John C. Platt, Microsoft Research. This technical report (MSR-TR-98-14) introduces a new method for training Support Vector Machines (SVMs), known as Sequential Minimal Optimization (SMO). The paper focuses on solving the large quadratic programming (QP) problem that arises during SVM training." 支持向量机（SVM）是一种强大的监督学习模型，广泛应用于分类和回归任务。然而，训练SVM通常涉及到解决一个大规模的二次规划问题，这在计算上是相当复杂的。约翰·普拉特提出的Sequential Minimal Optimization（SMO）算法解决了这一挑战。 SMO算法的核心思想是将大的QP问题分解成一系列最小规模的QP问题。这些小的QP问题可以解析求解，避免了使用耗时的数值优化方法作为内循环。这种方法显著减少了计算时间和所需的内存，其内存需求与训练集大小呈线性关系，因此能够处理大规模的训练数据集。对于不同的测试问题，SMO的运行时间在训练集规模上介于线性和二次之间，而传统的分块SVM算法的时间复杂度则介于线性和三次之间。这是因为SMO的主要计算开销在于支持向量的评估，所以对于线性SVM和稀疏数据集，SMO表现出更快的训练速度。 SMO的另一个优点是它避免了大量的矩阵运算，这使得它在处理大型数据集时能更有效地扩展。该算法的高效性使得SVM在实际应用中变得更加可行，特别是在处理高维数据和大数据集时。 SMO算法为SVM的训练提供了一个快速且内存效率高的解决方案，对于机器学习领域，特别是那些处理大规模数据的项目，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.

More documents and datum download website

Lu Zhenbo's Blog:

blog.sina.com.cn/luzhenbo2

Communication & Cooperation: luzhenbo@yahoo.com.cn

剩余20页未读，继续阅读

mingspy

粉丝: 15
资源: 15

支持向量机SMO算法：快速训练技术

SMO英文原文

SMO比较详细的论文

SMO算法视频文稿1

smo最经典论文

SMO_linnerTEST.zip_smo_smo 分类 matlab_smo分类_smo算法_smo算法matlab

smo.zip_smo matlab_smo-matlab_smo算法 MATLAB

SMO Algorithm

SMO algorithm

SMO.rar_smo算法_svm smo_svm smo_优化SVM

PMSM_SMO.zip_PMSM SMO_SMO 仿真_exactly92k_pmsm smo matlab_smo

最新资源