支持向量机训练算法：Sequential Minimal Optimization（SMO）

需积分: 14 50 浏览量更新于2024-07-15 收藏 90KB PDF 举报

"Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines" 本文主要介绍了一种用于训练支持向量机（Support Vector Machines, SVM）的新算法——Sequential Minimal Optimization（SMO）。SMO是由John C. Platt在1998年提出的，旨在解决支持向量机训练中的大规模二次规划（Quadratic Programming, QP）优化问题，从而提高训练速度和模型的准确性。支持向量机是一种广泛应用于分类和回归任务的监督学习模型，其核心在于寻找一个超平面，使得不同类别的样本点距离这个超平面的距离最大化。在训练过程中，需要求解一个复杂的QP问题，这通常涉及到大量的计算和内存需求。SMO算法通过将大问题分解成一系列最小的QP子问题来解决这一难题。 SMO算法的独特之处在于它将大QP问题分解为两个变量的优化问题，然后通过解析解求解这些小问题，避免了使用数值优化方法作为内部循环，从而显著减少了计算时间。这种策略使得SMO对内存的需求线性依赖于训练集的大小，因此可以处理大规模的训练数据。在实际应用中，SMO的运行时间主要由支持向量的评估决定。对于线性SVM和稀疏数据集，SMO表现得尤为高效，因为这类问题中的支持向量评估更快。相比之下，标准的分块SVM算法的复杂度在训练集大小上介于线性和立方之间，对于大规模数据集来说，SMO的效率优势更为明显。此外，SMO的性能在不同的测试问题中表现出介于线性与二次之间的扩展性，而传统的SVM算法则在最坏情况下可能达到三次方的复杂度。这意味着，对于大规模数据，SMO在保持高效的同时，也能保证较高的精度，对于机器学习领域，尤其是需要处理大量数据的问题，SMO算法的提出是一个重要的进步。

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页未读，继续阅读

不仅自己可见

粉丝: 23

支持向量机训练算法：Sequential Minimal Optimization（SMO）

支持向量机训练算法：Sequential Minimal Optimization（SMO）

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

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

Sequential Minimal Optimization A Fast Algorithm for Training

论文Sequential Minimal Optimization for SVM（smo）--有smo程序

OPTIMASI_ALGORITMA_SUPPORT_VECTOR_MACHIN_paper_pdf_SVM_

Improvements to Platt’s SMO Algorithm for SVM Classifier Design

SMO Algorithm

SMO algorithm

SVM学习——Improvements to Platt’s SMO Algorithm

最新资源