SVM推导

参考链接。

问题分析：给定一个标注的数据集(x_{i},y_{i}), i=1,2,3,4……N，其中x_{i}\in R^{d}, y_{i}\in\{1,-1\}，我们希望找到一个分类器或者说分类平面f(x_{i})使得以下的判别成立：

f\left( x_{i}\right) \begin{cases}\geq 0,y_{i}=1\\ <0,y_{i}=-1\end{cases}

也就是对于正确分类的话应该有y_{i}f(x_{i})>0成立

正负样本

线性可分与线性不可分

线性可分与线性不可分

对于线性可分的情况，分类平面以f(x)=\omega^Tx+b表示，其中\omega^T是权重向量，b是偏差。在二维的坐标里面，分类平面就是一条直线。在三维空间就是一个分类平面。训练集是为了学习到\omega^T

二维分类平面 三维空间的SVM

最优的\omega

通过训练集可以更新\omega来得到最终的决策平面。有个问题是，满足划分正确的决策平面有无数多个，怎么样的\omega才是最优的？最好的决策平面应该是距离两种类别的点都是最远的，也就是间隔要最大化，这样在新的数据点进入的时候，才能有比较大的抗干扰能力。

什么是最优的omega

因为决策平面2(\omega^Tx+b)=0和\omega^Tx+b=0是一回事，因此我们总是能够调整调整权重值和偏差值，使得最终支持向量所在的间隔为下图的形式所示。

这个时候，我们求两个边界之间的间隔也就是：

\omega^Tx+b=1和\omega^Tx+b=-1之间的距离在\omega方向上面的投影。

margin=\frac{\omega}{\left\| w\right\|}(x_{+}-x_{-})=\frac{\omega^T}{\left\| w\right\|}(x_{+}-x_{-})=\frac{2}{\left\| w\right\|}，其中\frac{\omega}{\left\| w\right\|}是\omega方向上面的单位向量，

推导 最大化间隔的示意图

因此我们要最大化的间隔，也就是我们的目标函数是Margin=\frac{2}{\left\| w\right\|}, s.t.y_{i}(\omega^Tx_{i}+b)\geq1, i=1,2,3……N

也就是在满足线性约束条件y_{i}(\omega^Tx_{i}+b)\geq1, i=1,2,3……N的前提下，求Margin的最大值，等价于求argmin_{\omega}\frac{1}{2}{\left\| w\right\|}^2, s.t.y_{i}(\omega^Tx_{i}+b)\geq1, i=1,2,3……N

这是一个满足线性限制条件的二次优化问题，有唯一的最小值。

软间隔

最优的omega

在一些问题上我们需要对误差和间隔最大化做一些妥协和让步，比如上面两幅图当中，为了把很靠近红色正样本的那个蓝色点正确划分，极大地扭曲了决策平面。因此我们需要调整决策平面使得它能够容忍一定的误差。

引入一个弛豫变量\xi

弛豫变量

在这里弛豫变量\xi可以认为是偏离正确分类边界的y方向的距离（也可以认为是等式右边的偏差），比如以负样本的划分为例子，恰好在划分边界上面的点\xi=0，而再往上去一点，0<\xi<1，因为点还没有到中间的分类平面，中间的分类平面到下面的负样本的边界函数距离为1，在法向量方向上的投影为\frac{1}{\left\| \omega \right\|}，当负样本的点在决策平面以上之后，\xi>1，是错分点，其在法向量上面的投影\frac{\xi_{i}}{\left\| \omega \right\|}>\frac{1}{\left\| \omega \right\|}。

软间隔优化方法

在优化的目标函数里面引入误差项，变成了min_{\omega}\frac{1}{2}\left\|\omega\right\|+C\sum_{i=1}^{N}\xi_{i}, s.t. y_{i}(\omega^Tx+b)\geq1-\xi_{i},i=1,2,3……，目标函数变成了这个。

C就是正则化项，其值越大对误差的惩罚就越大。1-\xi_{i}相当于降低了标准，可以允许在间隔内。