关于支持向量机的总结

支持向量机总结 2018/02/24 by Jenny

先看支持向量机的直观理解：

（1）https://www.zhihu.com/question/21094489/answer/86273196
只看第一个帖子，这个比喻形象贴切。
（2）https://v.qq.com/x/page/k05170ntgzc.html
核技巧的可视化。

基本知识点：

• SVM：“最大间隔”分类器。
  直观想法：对于线性可分的数据点，位于两类边界附近的数据点是最难分的，而离得远的那些点容易区分，因此SVM将处理重心放到“边界”附近的点上，使得它们能以最大的确信度分离，从而保证数据变动时，也尽可能分类正确。
  从几何上看，分类超平面仅由位于间隔面上的样本点（即支持向量）所决定，和其他远离间隔面的样本点无关。（后面对SVM的对偶模型的解的分析上，也明确体现了这一点。）

• （2）线性可分的SVM的优化模型是一个凸二次优化问题。
  凸优化：优化目标是凸函数（想成碗形曲面），约束点集是凸集。
  凸优化问题的局部最优解也是全局最优解。
  凸优化问题有现成的数值求解方法和软件可直接求最优解。

• （3）但是SVM的优化模型有其特殊性，可以转到其对偶模型上求解。
  理由：它的对偶模型也是凸二次优化问题，但约束条件比原始模型简单得多，这样不仅可以设计更高效的求解方法（后面的SMO算法），而且对偶模型的形式和它的解的表达形式有特殊性，在将线性可分的SVM推广至非线性情形的时候，方便使用核技巧，提高计算效率。
   

• （4）广义Lagrange函数和对偶问题。
  借助广义Lagrange函数，可以给出原始优化模型的对偶模型。
  对于最小化问题：原始模型等价于Lagrange函数的min-max形式；
  对偶模型是Lagrange函数的max-min形式。
  对于任何函数，总有： max-min <= min-max 。
  因此，对于最小化问题，总有：对偶模型的最优值 <= 原始模型的最优值，这称为弱对偶性；
  但是在一定的条件下，对偶模型的最优值 = 原始模型的最优值，这称为强对偶性；
  此时，如果对偶模型更容易求解，通常会将原始问题转为对偶问题进行求解，SVM即是如此。

• （5）KKT条件。
  KKT：Karush-Kuhn-Tucker，中文教材翻译为库恩-塔克条件。
  KKT条件原本是带有不等式约束的函数取极值的必要条件，就像带有等式约束的函数求极值的时候，我们采用Lagrange乘数法时，各偏导数为零是函数取极值的必要条件一样（这里大前提都要求：函数可微，否则极值点可能在不可导点上取得），KKT条件也是一组类似的表达式，包含偏导数为零、对偶互补、可行约束等条件。
  但在“一定的Regulation条件”下，原始模型的最优解和对偶模型的最优解之间的关系可以完全由KKT条件刻画，即：它们满足KKT条件里的各表达式，而且是这一刻画是充要的。

• （6）回到SVM中，“一定的Regulation条件”是满足的，因此SVM的原始最优解和对偶模型的最优解满足KKT条件，这样可以利用KKT中的对偶互补条件给出支持向量的刻画，从而解释为什么线性可分的SVM仅由支持向量决定，而与远离间隔面的样本点无关。（后面讲求解SVM的对偶模型的SMO算法时，KKT条件作为算法收敛的判别条件，这是由于KKT条件的充分性。）

【说明：这里KKT条件不是用来求解SVM的对偶模型的。在数学分析中，我们常用导数为零、偏导数为零得到极值点满足的方程或方程组，KKT条件也可以看成极值点满足的方程组（含不等式方程），理论上求解这些方程组可以得到得可能的极值点。但这些方程组一般很难求解，所以实际的极值问题通常转到牛顿法、梯度下降等数值方法上求极值（问题：带约束的极值问题的数值解法有哪些？）。因此，这些条件的作用多是体现在理论分析上，或者为数值求解提供理论保证，而不是用来计算求解。】

• 非线性的SVM与核技巧。
  对于线性不可分的数据集，可以通过特殊的映射（称为特征映射）将数据映到高维空间，使得数据在高维空间（称作特征空间，原数据空间称为输入空间）中线性可分，这样就得到了原数据空间里的分类超曲面，这是利用线性方法处理非线性分类问题的基本思想。
  观察线性的SVM的对偶模型，涉及都是原始数据的内积而不是原始数据本身，这样在处理非线性的SVM时，可以跨过特征映射的定义，利用核函数直接给出数据在特征空间的内积的简便计算方式，避免映射原始数据的计算和存储代价，也避免在高维空间中计算内积，从而提高效率。

• （8）正则化——软间隔SVM线性分类器。
  线性的SVM的缺点：一是只适用于线性可分的数据集，二是容易受特异数据的影响而造成过拟合。虽然利用核技巧可以解决线性不可分的数据集，但是通常很难确定合适的核函数。因此，在线性的SVM模型中，引入松弛变量，允许某些样本点“出错”，形成软间隔，从而减小过拟合的风险，也将适用范围扩大到处理线性不可分数据集。
  同样，对于软间隔的原始模型，也可以转化为对偶模型，并通过KKT条件给出支持向量的刻画。此时支持向量分为多种情形：落在间隔面上、落在间隔内、甚至有错误分类点。
  软间隔SVM线性分类器对应的是hinge损失函数：w模的部分，体现的是模型的复杂程度；惩罚项部分给出了出错样本点的累计误差，即经验风险项。

• （9）SVM的对偶模型的求解——SMO算法。
  SVM的对偶模型是一个多元的二次的目标函数求极值的问题，要求的极值点的分量满足一个等式约束。为简便求解起见，每次迭代时，选取两个分量，固定这两个分量之外的其他分量，求得目标函数关于这两个分量的极值，即一次只更新两个分量，使得目标函数不断增大，直到KKT条件基本满足时，迭代停止。
  两个分量求极值点时，由于目标函数是二次函数，约束形式也简单，所以对可以直接给出解析解，不需要数值解法，计算效率高。
  两个分量的选取方式：一个是违背KKT条件程度最大的，另一个是目标函数增长最快的。

【SMO：Sequential Minimal Optimization，中文书翻译为序列最小最优化，Pratt的论文摘要里解释得比较清楚：Training a support vector machine requires the solution of a very large quadratic programming (QP) optimization problem. SMO breaks this large QP problem into a series of smallest possible QP problems. These small QP problems are solved analytically, which avoids using a time-consuming numerical QP optimization as an inner loop. The amount of memory required for SMO is linear in the training set size, which allows SMO to handle very large training sets. （这里说了sequential的含义，原论文中讨论的优化模型是求最小，所以是minimal optimization）】