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

时间:2023-02-01 01:00:07

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

引入SVM

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

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

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

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

SVM求解

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

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

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

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

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

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

(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 WArrowvert }(X-X^{'}) right |= frac{1}{Arrowvert WArrowvert }|(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} & maxlimits_{W,b} quad & margin(b,W) \ & s.t. & every y_n(W^TX_n +b) > 0 \ & & margin(b,W) = minlimits_{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), 都是对应同一个平面,因此求距离进行优化的过程不会有影响,利用这个特点,同时为了方便计算,对于某个的超平面,作出如下的假设放缩:

[minlimits_{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} & maxlimits_{W,b} quad frac{1}{Arrowvert WArrowvert} \ & s.t. qua 大专栏  机器学习技法笔记(2)-Linear SVMd minlimits_{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} & minlimits_{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,即可,如下:

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

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

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

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

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

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

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

SVM 与 VC 维

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

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

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

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

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

以三个输入的数据为例,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,泛化性能更好,这也是就是我们要找最胖的分类面的原因。