林轩田机器学习技法笔记1：Liner Support Vector Machine(SVM)

0. 前言

机器学习技法第一课，机器学习技法将会有16课。第一课将会介绍线性支持向量机。

1. Large-Margin Separating Hyperplane

我们之前使用PLA、Pocket、线性分类等方法时，会得到不同的直线，他们都能得到正确的分类，比如说：

三条直线都是正确的，但是最好的直线是哪个呢？直观的看是第三个，因为在第三幅图中，样本点离直线比较远，看起来比较”安全“，即使样本有些波动也不会分错。也就是说我们要找的直线需要满足两个条件：
1. 能容忍更多的噪声点。
2. 对于过拟合鲁棒性更好。
我们使用一个形象的概念来表述这一现象：Fat Hyperplane。也就是说，一条直线有多胖时，样本点仍然能正确分类。

第三天直线最胖，说明第三条直线最好。
用数学方式进行写就是：

2. Distance to Hyperplane: Preliminary

上一部分的数学公式中写到，我们需要计算每个样本到直线的距离。
这里我们需要对w$w$做一次变动，之前w$w$中存在w0$w_0$项表示常数项，现在我们将w0$w_0$分离出来并记为b$b$，这样w$w$中就不存在w0$w_0$了。分类器直线为：

那么如何计算距离呢，我们知道一个点到一个平面（分类器是一个超平面）的距离计算公式，该点与平面上任意一点在平面法向量上投影的长度。那么法向量是哪个呢？其实就是我们之前处理过的w$w$。

两个平面上的点x′$x^{\prime }$，x′′$x^{″}$之间的直线与w$w$垂直，这证明了w$w$与平面垂直。最后我们得到任意一点到平面的距离为：

我们之前说过支持向量机的目的是最大化正确分类点到直线的距离，所以满足

因此我们可以去掉绝对值得到：

此时我们的线性分类器为：

此时我们的目标仍然很复杂，我们做进一步的简化处理。我们对margin进行放缩，使得最小的样本时
此时我们的目标就变成1∥w∥$\frac{1}{\Vert w\Vert }$了。

通过一张图加深理解：

3. Support Vector Machine

支持向量机这个名字怎么来的呢？这是因为分类面仅仅由分类面的两边距离它最近的几个点决定的，其它点对分类面没有影响。决定分类面的几个点称之为支持向量（Support Vector），好比这些点“支撑”着分类面。而利用Support Vector得到最佳分类面的方法，称之为支持向量机（Support Vector Machine）。
求解支持向量机可以总结为：
这是一个典型的二次规划问题，，可以使用一些软件（例如Matlab）自带的二次规划的库函数来求解。下图给出SVM与标准二次规划问题的参数对应关系：

其实求解过程使用python的sklearn算法包就好了，一步到位。

4. Reasons behind Large-Margin Hyperplane

SVM的这种思想其实与我们之前介绍的机器学习非常重要的正则化regularization思想很类似。两种方法的最小化和约束条件分别是：

regularization与SVM的目标和限制条件分别对调了。其实，考虑的内容是类似的，效果也是相近的。SVM也可以说是一种weight-decay regularization，限制条件是Ein$E_{in}$=0。
支持向量机具有更小的VC维，其实支持向量机的VC维小于d+1，我们知道线性分类的VC维为d+1。

5. 总结

这节课主要讲了线性支持向量机几个部分。
- 介绍了Margin
- 什么是支持向量机
- 支持向量机怎么求解
- 支持向量机的VC维