SVM

SVM（Support Vector Machine）要解决的问题可以用一个经典的二分类问题加以描述。

背景&定义：

图1中的(b)和(c)分别给出了A、B两种不同的分类方案，其中黑色实线为分界线，术语称为“决策面”。每个决策面对应了一个线性分类器。虽然在目前的数据上看，这两个分类器的分类结果是一样的，但如果考虑潜在的其他数据，则两者的分类性能是有差别的。

为什么叫决策面，而不是决策线？在图1里，样本是二维空间中的点，1维的直线可以分开它们。但更加一般的情况下，样本点的维度是n，则将它们分开的决策面的维度就是n-1维的超平面，所以叫“决策面”更加具有普适性，直线只是决策面的一个特例

图1

两虚线间的垂直距离即为“分类间隔”。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。不同方向的最优决策面的分类间隔通常是不同的，那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为“支持向量”。对于图1中的数据，A决策面就是SVM寻找的最优解，而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量。

从表面上看，我们优化的对象似乎是这个决策面的方向和位置。但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后，你最终会发现，其实与线性决策面的方向和位置直接相关的参数都会被约减掉，最终结果只取决于样本点的选择结果。

约束条件：

1）并不是所有的方向都存在能够实现100%正确分类的决策面，我们如何判断一条直线是否能够将所有的样本点都正确分类？

2）即便找到了正确的决策面方向，还要注意决策面的位置应该在间隔区域的中轴线上，所以用来确定决策面位置的截距\gamma也不能自由的优化，而是受到决策面方向和样本点分布的约束。

3）即便取到了合适的方向和截距，公式(2.6)里面的x不是随随便便的一个样本点，而是支持向量对应的样本点。对于一个给定的决策面，我们该如何找到对应的支持向量？

类别标签

决策面方程对样本分类

决策面处于间隔区域的中轴线上，且相应的支持向量到决策面的距离为d

左右两边同除d

化简后，约束条件的基本描述

SVM优化问题基本描述：

当x_{i} 是支持向量时，有

由点到直线的距离公式，对于所有的支持向量样本点，

原来的任务是找到一组参数\omega,\gamma 使得分类间隔W=2d 最大化，根据上式就可以转变为||\omega|| 的最小化问题，也等效于1/2||\omega||^2 的最小化问题。我们之所以要在||\omega|| 上加上平方和1/2的系数，是为了以后进行最优化的过程中对目标函数求导时比较方便，但这绝不影响最优化问题最后的解。

上式描述的是一个典型的不等式约束条件下的二次型函数优化问题，同时也是支持向量机的基本数学模型。

拉格朗日乘子法：

尽管在3.1节我们已经想象出有约束优化问题的几何意象。可是如何利用代数方法找到这个被约束了的最优解呢？这就需要用到拉格朗日乘子法（即解决有约束的优化问题）。

首先定义原始目标函数f(x) ，拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数L(x,\lambda) 的一部分，从而使有约束优化问题变成我们习惯的无约束优化问题。

未完待续。