[置顶] 加州理工学院公开课：机器学习与数据挖掘_SVM（第十四课）

课程简介

这节课主要讲述了支持向量机的原理及其在线性可分数据集上的应用。最后讲到支持向量机在处理高维空间时显示出的优势。。在讲述支持向量机的原理的时候用到拉格朗日方程， KKT 及二次规划进行求解。理论部分比较深。

课程提纲：

1、Maximing the Margin

2、The Solution 

3、Nonlinear Transform

1、Maximing the Margin

首先什么是 Margin ？ 

定义：Margin 表示的是离分类器最接近的点到分类器的距离。

如下图黄色部分：

上面三幅图像中，分类器对于样本数据的分类效果是一样的，但是哪一种会具有更好的泛化能力呢？

直觉上认为第三幅图相对来说具有最好的分化能力。下面是一个不太严禁的证明：

假设数据集只有三个点，那么所有可能的分类最多为  8 种，如下图：

现在我们增加一点限制，要求所有可能的分类情况，分类器的 Margin 至少大于某个值。首先我们需要知道在每一种情况下最大的 Margin 是多少，然后只需要把该值跟我们设定的阀值进行比较，若小于则去掉相应的分类情况。

如下图所示，假设我们要求的阀值大于 0.5 则最靠右的两列分类情况不能存在。因此在该限制条件下，我们的 Growth Function 比原来没有限制的情况下小。即我们有较低的 VC 维。因而有利于进行机器学习。当然上面的分析是不严谨的，后面我们会给出一个严谨的推导，通过该推导我们将认识到，Margin 越大，泛化能力很大概率上越强。

现在的问题是如何才能找到最大的 Margin ？下节将会给出严谨的数学推导。

2、The Solution 

令 Xn 是距离 WX = 0 最小的点。为了方便起见，我们令数据集是线性可分的二分类，则存在函数：WX + b = 0，该函数能够正确地分类所有的点。我们的目标就是找到合适的 W 和 b 使得 Margin 最大化即找到合适的 W 和 b 使得 Xn 到该平面的距离 d 最大化。

有 |WXn + b | > 0 ( 因为 Xn 不在 WX + b = 0 上 )

为了方便计算，我们通过归一化 |WXn+b| > 0 使得 | WXn + b | = 1 （为什么可以这么做？不太理解。）

因此有：| WXn + b | = 1.

首先我们从 WX + b = 0 上任意取两个不同的点，x1，x2 

则有：

b1：WX1 + b = 0

b2：WX2 + b = 0

b1 - b2 : W(X1-X2) = 0. 

所以 W 垂直于WX+b = 0 平面。

如下图所示：

因此 Xn 到平面的距离 d = |(Xn-Xa)| * W / || W ||。 其中 Xa 是平面上的任意一点。

d = |W*Xn-W*Xa| / ||W||.

有：| WXn + b | = 1. WXa + b  = 0.

所以 d= |W*Xn + b - (W*Xa + b) | / ||W|| = |W*Xn + b - 0| / ||W|| =1/||W||.

因此我们的目标就是 最小化 ||W||.

限制条件是：

min<n = 1 to N>  |WXn + b| = 1.（由于之前的 Xn 是假定的，其值是通过该方程求解得到的。）

由于 |WXi + b | = h(Xi)(WXi+b),所以上面的限制条件变为：

min<n = 1 to N>  h(Xn)(WXn+b) = 1

再次，为了便于计算，我们可以转换上面的条件为：

最小化：1/2 W‘ W 第一个 W' 

h(Xi)(WXi+b)>= 1  for all points in the dataset.

Ok 到目前为止，一切顺利，最棘手的问题是如何求解？？？

下面通过拉格朗日 、 KKT 及二次规划方程进行求解（这个不懂的可以百度，我搞不懂也...）

下面的 yn 对应于 上面的 h(xn)

对于中间的等式，只有当 (yn(WXn+b)-1) != 0 时 αn 才等于 0。其它情况下 α 都不为 0 。

对于任何 αi 当 αi 大于 0 的时候对应的 Xi 为一个支持向量。

一般来说，因为存在噪声等问题，不同的支持向量求解得出的 b 会不一样，一般策略是通过求平均来得到最终的 b 。

3、Nonlinear Transform

如果当前问题是非线性的，我们可以把它转换到线性空间然后进行求解。通过上面的分析我们可以发现，在处理不同维度问题的时候，支持向量机的时间消耗主要跟数据集大小有关，维度的影响相对来说是非常小的，因此可以利用支持向量机处理高维度的问题。一个应该注意的问题就是，当我们把问题转换到高维空间进行求解，得出的支持向量并不适用于原来的输入空间。