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\|}$ 。