机器学习技法笔记(2)-Linear SVM

文章目录
  1. 引入SVM
  2. SVM求解
  3. SVM 与 VC 维

从这一节开始学习机器学习技法课程中的SVM, 这一节主要介绍标准形式的SVM: Linear SVM

引入SVM

首先回顾Percentron Learning Algrithm(感知器算法PLA)是如何分类的,如下图,找到一条线,将两类训练数据点分开即可:

PLA的最后的直线可能有很多条,那到底哪条好呢?好坏的标准则是其泛化性能,即在测试数据集上的正确率,如下,下面三条直线都能正确的分开训练数据,那到底哪个好呢?SVM就是解决这个问题的。

SVM求解

直觉告诉我们最右的要好一些,因为测试数据的分布应该与训练数据的分布类似,因此看起来它可以容忍更多的噪音,假设有一个数据在第一个红叉叉下方位置,也是属于叉类别,前两直线则容易把它分到圈圈的类别,而造成错误。因此理想的直线或者分类平面应该距离两类训练数据集越远越好:也就是下面的灰色区域越胖越好:

灰色区域的宽度是由直线与训练数据\(x_{1..N}\) 中到分类平面最近的距离决定的,这个距离称为margin,因此我们就可以将问题描述如下:

\[\begin{align} & \max\limits_{W,b}(margin(W,b)) \\ & s.t. y_n(W^TX_n+b) > 0 \end{align}\]

其中,分类平面由\(W,b\)决定,我们要找出最大\(margin\)的那条直线,这里的\(margin(W)=\min\limits_{n=1...N} distance(x_n,,W,b)\), 约束条件是这条直线已经将两类完全分开,即:\(y_n(X_n+b) >0\) 。下面我们看看点\((x_n)\)到平面\(W^TX+b = 0\)的距离,看下图:

\(W\) 为平面\(W^TX+b=0\)的法向量,\(x^{'}\)\(x^{''}\)为平面上的两个点,现在如果要求点\(X\)到平面的距离\(dist(X,W,b)\),即向量\(X-X^{'}\)投影(proj)到法向量\(W\):

\[distance(X,W,b)=\left | \frac{W^T}{\Arrowvert W\Arrowvert }(X-X^{'}) \right |= \frac{1}{\Arrowvert W\Arrowvert }|(W^TX +b) |\]

到此,再结合约束条件\(y_n(W^TX+b)>0, \ y_n \in \{-1, 1\}\), 点\(X\)到平面的距离可以通过去绝对值符号,转化为如下的式子:

\[distance(X,W,b)=\frac{1}{\Arrowvert W \Arrowvert }y_n(W^TX+b)\]

因此问题转化如下的优化问题:

\[\begin{align} & \max\limits_{W,b} \quad & margin(b,W) \\ & s.t. & every \ y_n(W^TX_n +b) > 0 \\ & & margin(b,W) = \min\limits_{n=1..N} \frac{1}{\Arrowvert W \Arrowvert}y_n(W^TX_n +b)\end{align}\]

另外,考虑到\(W^TX+b=0\)\(2W^TX+2b=0\)这两个平面是同一个平面,只是对\(W,b\)经过了放缩(scaling),因此在缩放的过程中,不管是\(W,b\),还是\(2W,2b\), 都是对应同一个平面,因此求距离进行优化的过程不会有影响,利用这个特点,同时为了方便计算,对于某个的超平面,作出如下的假设放缩:

\[\min\limits_{n=1...N}y_n(W^TX_n+b) = 1\]

因为对于一个固定的平面,通过放缩,肯定存在一组\(W,b\)使得上述的等式成立,同时也保证了条件\(y_n(W^TX_n+b) >0\),这样\(margin(W,b) = \frac{1}{\Arrowvert W \Arrowvert}\),因此我们的优化问题转化为如下:

\[\begin{align} & \max\limits_{W,b} \quad \frac{1}{\Arrowvert W\Arrowvert} \\ & s.t. \quad \min\limits_{n=1...N}(y_n(W^TX_n+b)) =1 \end{align}\]

上述的约束条件是最小值等于1,对于优化问题来说,一般是某个等式或者不等式,这样容易求解,因此将上述的约束条件转为:\[y_n(W^TX_n +b) \geq 1, \quad for \ all \ n\]

考虑上述转换的正确性: 反证法,假设对于所有的\(n\), 有\(y_n(W^TX_n+b) > 1\), 即不满足最小值为1的条件,不妨设为\(\min = K, K>1\),设此时得到的最优解为\(W,b\),那么\(\frac{W}{K},\frac{b}{K}\) 很显然比\(W,b\)更优,矛盾。因此下面两式等价:

\[\begin{align}& \min(y_n(W^TX_n + b)) =1 \\ & y_n(W^TX_n+B) \geq 1, \ for \ all \ n \end{align}\]

再结合将求max转为min, 求距离,转为求平方等转化,最后我们的优化问题如下:

\[\begin{align} & \min\limits_{W,b} \quad \frac{1}{2}W^TW \\ & s.t. \ y_n(W^TX_n +b) \geq 1, \ for \ all \ n \end{align}\]

这个问题的优化方程为二次方程,条件为一次线性约束,是一个典型的二次规划问题(Quadratic Programming),而QP问题有很多解法,我们只需要将上述优化问题,转化为QP问题解法的格式,然后直接代入QP Solver,即可,如下:

左侧是我们最后的优化问题,右侧是标准的QP问题的输入格式,一共有4个输入变量: \(Q,p,A,c\), 及一个最终的优化结果: \(u\) ,我们只需要表示出上述四个输入变量,就可以输入到某个QP Solver里面即可,通过对应关系,表示如下:

这样就可以得到最优的\(W,b\),进而求出\(g_{SVM} = sign(W^TX+b)\),进行后续预测。

上述的算法仅仅是最简单的线性SVM, 不过是其它类型SVM的基础,总结一下,流程很简单,如下:

这种算法同样也可以解决非线性分类问题,通过之前的非线性转化,到线性空间: \(z_n = \phi(x_n)\),理论上即可直接应用到非线性问题中。不过缺陷也很明显,要求数据点必须线性可分,由于这个特点,这种算法也叫做: Linear Hard-Margin SVM。

SVM 与 VC 维

这里需要提一下,SVM(Support Vector Machine)的含义,我们了解到,SVM就是要找到最胖的那个分类面,如下:

其中,在边界上的用黑框圈出来的三个点,我们就称为SV,Support Vector,因为它们才是求解过程中,真正起到作用的点,其余的点没有起到作用,后续的课程中也有进一步的介绍SV。

简单来说,SVM是基于PLA的一个算法,上面开始说了, 直觉告诉我们最胖的直线应该容错性好,其中的原理其实则是SVM相对于PLA,VC维降低了(注: 算法的VC维的定义不太明确,类比与\(\mathcal{H}\)的VC维定义即可, 这里只是定性的介绍),看下图:

以三个输入的数据为例,PLA可以shatter(能够将\(2^3\)种情况都分开),而无法将4个数据点shatter,因此VC(PLA)=3,我们从另外一个角度来考虑, 假设我们规定了Margin的值为\(\rho\) ,也就是胖瘦的程度,那么肯定会存在输入数据量为3,且无法shatter的情形,比如上图的后两种,在\(\rho\)下 无法shatter,因此大致看起来,\(d_{VC}(\rho) < 3\)的。其实有严格的数学证明,可以得到:

\[d_{VC}(\rho) \leq d+1 = d_{VC}(PLA)\]

VC维减少了,意味着复杂度降低,也就是说更不容易overfitting,泛化性能更好,这也是就是我们要找最胖的分类面的原因。