【学习笔记】斯坦福大学公开课（机器学习） 之支持向量机

支持向量机SVM (Support Vector Machines)

在之前的算法中，我们是根据样本来预测出数据的标记（即结果）的概率，那么SVM算法是通过找到数据中的区分边际从而实现数据分类。

边际（Margins）

从margins来认识SVM，首先我们想想之前的算法，比如logistic regression算法，它得到的是样本对应各个标记的概率，概率越大，说明该样本有更多可能分类成该标记。如 果我们需要把这个概率提升，即在根据模型进行分类后就明确指示出是哪一类呢？比如当θTx>>0时（注意是”远大于”，即离边际的距离很远），y=1而不是得到结果p(y=1)=69%之类的概率，此时就可以明确的看到根据特征值预测出的分类结果。那么这里的边际就是所说的θTx=0。
我们再从图像上来认识下边际：

比如上图中，x和o是两种不同的数据分类。我们会找到分割两种数据的线（边际），A,B,C三个数据都在边际的一侧，所以都属于“x”类，但是A与边际的距离远远大于B和C,那么A属于”x”类的概率就更高。

标记（Notation）

为了更方便的讨论SVM，需要换一种方式来表示标记，我们使用y∈{−1,1}来做标记，并且把参数的向量形式，写成w,b参数形式：

其中，g(z)=1  if z≥0，否则就是g(z)=−1。
注意到函数g，我们的分类器直接预测出标记是1还是-1，而不会去预测样本为各类标记的概率（如logistic regression）。

函数间隔和几何间隔(Functional and geometric margins)

已知一个训练样本(x(i),y(i))，我们可以定义一个关于(w,b)的函数间隔：

当y(i)=1时，会让函数间隔比较大，所以就会需要让wT+b成为一个很大的正数。相反的y(i)=−1时，我们需要wT+b成为一个很大的负数。函数间隔越大，那么就可以得到一个更正确，更可信的预测结果。
对于一个关于g(z)的线性分类器来说，有一个关于函数间隔很不好的性质：当我们用2w来代替w，2b来代替b时，就会有g(wTx+b)=g(2wT+2b)，这并不会改变我们预测出的hw,b(x)，因为hw,b(x)的值只取决于g(wTx+b)的符合，而不与它的大小无关。这样看来，我们把函数间隔改成任意大，都不会对我们的实际效果造成影响，这样看来我们需要做出一些改变，比如做一些归一化||w||2=1。
已知训练样本S={(x(i),y(i));i=1,2,3⋯m}，我们定义这个训练样本S的函数距离是样本空间中各个样本到判断边界距离中最短的距离。符号记为:

下面来看下几何间隔：

看上图，已经把关于(w,b)的，沿着向量w判定边界划出来了。注意到，w的方向与判定边界是成垂直状态。点A，一个被标记为1的训练样本，它到判定边界的距离是线段AB，我们用符号γ(i)来表示。
我们如何求出γ(i)？我们知道，w/||w||表示一个单位向量，A点用x(i)表示，而点B就可以通过向量运算得到x(i)−γ(i)∗w/||w||，而这点又在判断边界的直线上，即是满足判断边界的方程wT+b=0，所以就有下面的方程：

那么，每个点到判断边界的距离就是：

上面就是把判断边界正数一侧的样本的几何距离，更一般的，给定样本及标记(x(i),y(i))，我们得到几何距离：

我们注意到，当||w||=1的时候，几何距离与函数距离是相同的。
与函数距离类似，我们也把各个样本的几何距离中，最短的距离写成：

最优边界分类器（The optimal margin classifier）

从上面的论述来看，现在我们需要一个分类器，若要把训练样本分类，则需要分类器，一条线（几何距离），把样本很好的分割成不同类别的标记。
这个问题可以转化为找到一个超平面，使得样本空间中的样本到该平面的距离最大，即：

这里就是说我们需要最大化γ∧||w||，在叙述函数距离的时候，我们发现，w,b的等比变化并不会影响超平面的位置，那么就可以让γ∧=1。
所以原来的式子就变为1||w||，我们要将这个式子最大化，等同于我们需要将||w||2最小化即：

这个就是在线性约束条件下的，二次优化问题。