机器学习技法---线性SVM
本文参考整理了Coursera上由NTU的林轩田讲授的《机器学习技法》课程的第一章的内容，主要介绍了支撑向量机SVM的基本概念，文中的图片都是截取自在线课程的讲义。
欢迎到我的博客跟踪最新的内容变化。
如果有任何错误或者建议，欢迎指出，感激不尽！
Large-Margin Separating Hyperplane
首先来看一个问题，如果要用一条线来进行二元分类，以下哪一条线最好呢？
大部分人可能感觉最右边的线最好，怎么解释？
因为最右边的线离最近点的距离更大，对点的noise更鲁棒、强壮。
假设noise服从高斯分布，则将来测试样本点x'≈x(可能x'就是x，只是因为测量误差等原因造成约等于)的话，那么分类结果应该一致。
三条线对测量误差的容忍度不同，容忍度越大则对过拟合overfitting更加robust(因为测量误差也是一种Noise，而Noise会引起Overfitting)。
用线距离最近点的距离来衡量这个属性。
换种描述，我们叫线有多“胖”，即线往两侧最大扩展多远才会碰到最近的点。
目标：找到最胖的分割线(超平面)。
问题描述为：
正式定义（Large-Margin Separating Hyperplane）：
胖是一种非正式的描述，正式名称为margin。
Standard Large-Margin Problem
如何计算点到直线的距离？
distance(Xn,W)
为了计算距离的方便，将W的表示形式进行缩短，去掉截距项W0，输入样本特征的X0=1也去掉。
h(x) = sign(W’X + b)
因此用distance(X,b,W)代表点X到平面W’X+b=0的距离。
注意：在本文中用大写英文字母表示矩阵或向量，如X、W，用W’表示矩阵的转置,用小写字母表示标量。
考虑平面上的两个点X和X`，则满足平面方程，有：
W'X = -b
W'X`= -b
则
W'(X`-X) = -b - (-b) = 0
而X`-X是平面上的一个向量，对于任意考虑的两个点X和X`，W与(X`-X)的内积都是0，所以W垂直于这个平面，W是法向量。
所以点到平面的距离等于点到平面上任意一点的距离投到法向量的投影长度。
所以距离公式为：
化简标准问题
我们只考虑可以完美分隔XX和OO的线，它有性质：
对于每一个n，yn*(W'Xn + b) > 0
因为|yn|=1，所以绝对值可以脱掉
现在的最佳化问题如下：
其实这个世界上可能没有那么多条线，比如
W`X + b = 0 和 3W'X + 3b = 0 表示的是同一条直线，也就是说法向量的长度不影响线的表示。
所以我们可以利用特别的放缩，使得
所以我们可以只考虑由特殊的(b,W)表达的分隔线，满足以上条件，则
则最优化问题可以简化为：
而min=1同时也意味着every>0，第一个条件可以删去而不影响结果。
但问题仍然不好解，主要因为条件有个min操作，是否可以把条件放松一点呢？
条件放松，需要证明最优解一样。
满足原始条件必然满足放松条件(必要条件)，而通过反证法可以证明满足放松条件的也一定满足原始条件，因此两个条件等价。
问题可以表述如下：
将讨厌的max改为min，将W的模方的开方根号去掉，补充一个便于后续计算的常数1/2，得到最终的问题表述。
该问题称为“标准问题”(Standard Problem).
Support Vector Machine
名称解释
最胖的那条线g(svm)就叫做支撑向量机(SVM)
用方框圈起的是离线最近的那些点，有趣的是，如果删去其他不是方框框住的点，所找出的最胖的线仍然不变，所以这些最近的点已经足够告诉我们最胖的线长什么样子，而其他的点不重要。
我们称这些方框圈住的最近的点，告诉我们最胖的线在哪的这些点，为支撑向量[候选者] (Support Vector[candidate])。
所以support vector machine（SVM）就是在support vectors的帮助下，学习找出最胖的分割超平面。
求解一般SVM问题
该最优化问题不适合梯度下降法，因为有约束，也不便于直接手动求解，但幸运的是，该问题属于一类已知的最优化类型。
它的最小化目标是一个二次函数（convex），它的所有约束条件都是W和b的一次式，有这样性质的最佳化问题，一般称为“二次规划”(Quadratic Programming)。
做数值最佳化的人发现这样的问题很容易解决，并已有多种求解QP问题的软件工具，因此我们需要将该问题表示成QP的标准形式，再输入到算法中，即可求解最优解。
二次规划的标准形式
目标是最小化向量U的二次函数，二次项的系数放在矩阵Q中，一次项的系数放在向量P中。
条件是U向量的线性约束，共有M个条件，每个条件的一次式的系数放在向量Am中，常数项放在常数cm中，把所有的向量Am集合起来到一个矩阵A中，把所有的常数cm放到一个向量C中。
我们的当前问题描述为：
将b和W集成一个向量U
系数表示如下
注意要阅读QP算法的相关手册说明。
所以求解一般SVM问题的步骤如下：
hard-margin（硬边界）：不允许任何点违反“胖分割线”。
linear：在X原始空间中直接使用Xn向量，没有经过任何特征转换，如果要使用非线性的分割线（即X空间的曲线），可以考虑使用Z=Φ(X)转换。
为什么要使用最大边界的分隔超平面？
最开始的理由：“胖”一点的分割线对测量误差的容忍度更好
与regularization的对比：
| 技术 | 最小化目标 | 约束条件 |
|---|---|---|
| regularization | Ein | W’W<=C |
| SVM | W’W | Ein=0 [and more] |
所以SVM其实就是一种regularization，只是它regularization的解释是边界Margin要尽可能大，以能够抵抗一些测量误差。
即也是一种“weight-decay regularization within Ein = 0”(保证Ein为0的权重衰减正则化方法)，因此SVM可以一定程度上防止overfitting。
从VC维度解释
从另一个角度解释，利用导入VC维度时引入的二划分(dichotomy)概念，考虑这样一种“large-margin”演算法A(ρ)：
如果存在一条线g满足margin(g)>=ρ时，返回g；否则如果不存在则返回0.
这样的演算法在某一种特定的资料上，到底能够产生多少种OO和XX的排列组合(即dichotomies)呢？
越少的dichotomies ==> 越小的'VC维度'(有效的VC维度) ==> 更好的泛化(generalization)性能
演算法的VC维度
之前所说的VC维度都是指假设空间（即一堆hypotheses）的VC维度，这里给出演算法的VC维度概念。
演算法的VC维度和资料相关(data-dependent)，比如上述的Aρ。
例如：
假设在2维平面上有一个单位圆，当数据从单位圆内取值时
- 当ρ=0时，等价于PLA，因此dVC=3
- 当ρ>√3/2时，并不能shatter任意的3个点，因此dVC<3 【因为任何3个点中总有两个点的距离小于√3，】
一般地，当数据点取值在一个半径为R的超球体内时，有：
Large-Margin Hyperplanes 的好处
| Large-margin hyperplanes | hyperplanes | hyperplanes + 特征转换Φ | |
|---|---|---|---|
| 数量# | 甚至更少 | 很少 | 很多 |
| 边界线 | 简单 | 简单 | 复杂 |
- 数量#少比较好，因为可以控制dVC，优化泛化性能
- 边界复杂比较好，可能会有更好的Ein
原来我们只能做好其中之一，但如果把large-margin和feature transform合起来考虑，就可能两者都做好。
即我们有了一种新的可能选择：非线性SVM
| large-margin hyperplanes + numerous feature transform Φ | |
|---|---|
| 数量# | 很少 |
| 边界线 | 复杂 |
Mind Map Summary
有关非线性SVM及更多机器学习算法相关的内容将在日后的几篇文章中分别给出，敬请关注！
