本文只描述了支持向量机(SVM)算法的重要知识点，具体算法原理可通读作者之前的文章。

线性可分情形：最大间隔原理

原问题是一个典型的带线性约束的凸二次规划问题。模型的求解主要采用运筹学中的方法，这里就不仔细展开了。解决思路如下：

第一步是在原问题中引入拉格朗日乘子，将其转化为无约束问题(拉格朗日乘子法)；

第二步是根据优化后的一阶条件将原问题转化为对偶问题；

第三步，根据KKT条件，得到获得最优解需要满足的条件。

KKT条件是拉格朗日乘子法的推广。当存在等式约束时，采用拉格朗日乘数法；当存在不等式约束时，采用KKT条件。

转变为双重问题的原因：

1.双重问题往往更容易解决。

2.自然引入核函数，再将其推广到非线性分类问题。

支持向量：

在这两类样本中，最接近最优分类超平面且在与最优分类超平面平行的平面l _ 1上的训练样本称为支持向量。

00-1010湿区间应尽可能大，错分点数应尽可能少，并加入罚系数C调和二者关系。

近似线性可分情形

将低维空间中寻找非线性“最大超曲面”的问题转化为高维空间中求解线性“最大区间平面”的问题。也就是说，非线性可分离样本被映射到高维空间，使得样本是线性可分离的。

核k (xi，xj) k (xi，xj)=( (Xi)， (XJ))= (Xi) * (XJ)是特征空间中样本Xi和XJ的内积，称为输入空间x中的核函数。

1)对于非线性问题，可以通过非线性变换将其转化为高维空间中的线性问题，并在变换空间中得到最优分类面。这个转化可能比较复杂，所以这个思路一般不容易实现。

2)为了避免从低维空间到高维空间的维度灾难，避免高维内积操作。

总而言之，考虑引入内核函数：

1)用核函数代替非线性映射到高维空间，并且不需要知道映射函数。

2)在最优分类平面上使用合适的核函数可以实现一定非线性变换后的线性分类，但计算复杂度并没有增加。

3)通过计算K(xi，xj)的值，可以避免高维空间的内积运算。这种内积运算可以通过原空间定义的核函数来实现，甚至不需要知道变换形式。

00-1010序列最小优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题。这类凸二次规划问题具有全局最优解，但当训练样本量较大时，问题的求解将变得非常困难。目前，已经提出了许多快速实现算法，如SMO算法。

SMO算法是一种启发式算法。它的基本思想是，如果所有变量的解都满足这个优化问题的KKT条件，那么就得到这个优化问题的解。因为KKT条件是这个优化问题的充要条件。否则，选择两个变量，固定其他变量，为这两个变量构造一个二次规划问题。同一二次规划问题中这两个变量的解应该更接近原二次规划问题的解，因为这样会使原二次规划问题的目标函数值变小。此外，该问题可以用解析法解决，可以大大提高整个算法的计算速度。子问题有两个变量，一个是最严重违反KKT条件的变量，另一个由约束条自动确定。这样，SMO算法将原问题分解为子问题。