机器学习: SVM

为什么要有 SVM

SVM (Support Vector Machine）即支持向量机，主要用于解决数据的分类问题的。还记得线性分类的问题么？在那个问题只是说怎么去找分开数据的函数，但是没办法求这个函数怎样才能落在数据正中间，将两个数据分开。如下图

线性分类器只能分成左边的样子，SVM 则可以优化右右边图那样，函数正好落在正中间。

计算 Margin

找正中间位置的关键就是算这个直线到两边数据的距离，最好相等，那不就正中间了？所有我们将图画成这样

这里我们定义分割的函数 $f(x)$ ，红色则为 +1，蓝色为 -1。现在在这个函数加一个向量 $w$ 使其正交于 $f(x)$ 。

而且我们还得出 $w(x^\prime -x)=0$ 。现在我们加多一点变量来求 Margin M。

这里添加 $rw$ ，使得 $x^+=x^-+rw$ ，注意 $rw$ 是向量不是要求的 Margin M。将 $x^-$ 和 $x^+$ 代入 $f(x)$ 方程可以得到

$wx^-+b=-1 ; wx^++b=1$

可以推出 $r$ 的值。

也就能算出 Margin 的值了

Margin 最大化

为了能够刚好在正中间，Margin 应该越大越好所以要求
$\max_{w}\frac{2}{\sqrt{w^Tw}}$

也就是要求分子的最小值
$\min_w\sum_j{w_j}^2$

不过这里有个约束条件是

$y^{(j)}(wx^{(j)}+b) \geq + 1$

例子

下面举个简单例子来说明，假设下面有点

x	y
-3	-1
-1	-1
2	1

分割起来会是这样

要满足的条件如下

画在坐标轴上会相交出重叠的部分，阴影部分就是约束条件，在这部分可以随便选参数 $a$ 和 $b$ ，如 $a=1,b=0$ ，只不过 Margin 不是最好的。

此时我们想要 Margin 最大就要最小化 $||a||$ ，得到 $a=0.66,b=-0.33$

拉格朗日

其实上面已经是可以求到最优解了，不过每次都要搞一个约束条件太麻烦了，有没有像直接求某个函数最小值一步到位的方法呢？拉格朗日就开始教你做人了，使用拉格朗日乘子法构造一个新的目标函数就可以将约束条件包含在新目标函数里，相当于去掉了约束条件。

现在来看看我们要求的目标函数和约束条件

新构造出来的目标函数如下

可能现在暂时接受不了，一来一大串东西。先说说后面的 $\sum_i\alpha_ig_i(\theta)$ 是相当于将约束条件融入到新的目标函数里了。前面的 $\min_\theta\max_{\alpha\geq0}$ 是拉格朗日对偶搞出来的，因为不搞对偶单单求 $\min$ 是很难求的，所以新的目标函数就写上面这样了。