Machine Learning Techniques Lecture 1: Linear Support Vector Machine | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 1: Linear Support Vector Machine


 
 

这里讲的是 linear support vector machine

 
 

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 


 
 

课程基本信息。

 
 

Coursera 前8周是基石课程,后面8周是技法课程。

华语授课,投影片授课。

 
 


 
 

与机器学习基石的课程的异同点:

一样的是:哲学的讨论,理论分析,算法和实现,笑话。

不一样的是:把基石课程提到的基本理论工具延伸成为实用的学习模型,围绕在一个主要的点就是特征转换上面:

  1. 有大量的特征转换怎么运用,如何控制复杂度 – SVM
  2. 找出一些比较具有预测性质的特征以及混合应用 – AdaBoost
  3. 学习资料的一些隐藏特征 – Deep Learning

 
 

通过往这三个方向的学习来使得你能够专业的使用相关工具。

 
 


 
 

练习。

 
 


 
 

第一讲:线性支持向量机

 
 


 
 

先来看看之前讲过的 linear classification,他做的事情就是如图所示,通过画一条直线来区分圈圈叉叉。数学上的意义就是资料拿过来算一个分数,看分数的值是正的还是负的来决定其是圈圈还是叉叉。

 
 


 
 

PLA 是以前课程讲过的算法,在确定存在线的时候,此方法可以帮助我们找出这条线。

 
 

但是如上图所示,如果资料给定,有可能不会只存在一条线可以区分这些资料。问题是,从上面三幅图,哪一条线来区分圈圈叉叉比较好?

 
 

PLA 算法会选择的是随机一条线。

VC Bound 理论上看,上面三条线是一样好的。

而你是不是会选择最右边的线是比较好的吧,为什么?

 
 


 
 

简单的解释:

假设我们已经得到原始资料xn,未来我们用到的资料是和原始资料相近的一些资料,因为存在误差不可能是完全一样的,那么上面的三条线对相近的容错能力就是在能区分的情况下每个原始资料对的点所能画的圆圈的最大半径,就如上图所示,第三张图的线对于圆圈的容错能力最好,所以的三条线比较好。

 
 

也就是说每一个点离得线越远,那么能容忍的测量误差越大,反过来说就是找出一条线,离每一个点越远越好。

More robust:离最近的训练资料的距离来判断。

 
 

 
 


 
 

从线的角度看就是如下面三图:看线能长的多胖,越胖的线越robust。

 
 


 
 

也就是原来的问题可以变为一个最佳化的问题:找出一条最胖的线满足可以很好的分开所有的圈圈叉叉。

胖的定义:算一下线到每一个点的距离,取两边最小的。

 
 

下面要做的事情就是把这个最佳化问题变成可以数学求解的最佳化问题。

 
 


 
 

margin:线的边界,就是学术上线有多胖的说词。

 
 


 
 

练习

 
 


 
 

上面的最佳化问题里面有一个重要问题:找出的这条线你需要去看一下他和每一个点的距离是多远,取最小的距离。

 
 

探讨距离的运算:

 
 

分开w0和其他的wi,w0单独处理,w0取名为b,就是截距的意思。

所以公示里面的部分包括了 W^T*X + b

 
 


 
 

所以我们要算的是:一个用b,w表示的平面到一个点x的距离

 
 

假设我们已经有一个平面在手上,考虑平面上的两个点:x’和x”

因为都在平面上,所以有:w * x’ +b = 0, w * x” + b = 0

所以有上面的标号1的结论,然后两个相减,就得到标号2的结果。

x” – x’ 表示的是平面上的向量,w 与平面上任意的 (x” – x’) 向量都等于0,也就是说 w 垂直于平面,也就是说 w 是平面的法向量。

有了法向量任意一点x到平面的距离就比较好求解了。也就是说标号3所示:将(x-x’)向量投影到垂直于平面的方向w。

所以结果就是黄色所示公式:线性代数里面的投影距离公式。

然后做一下化简你会发现:就是 绝对值(W^t * x + b) / 绝对值 w 【这里只是除以w的长度,所以上面要把b分出来的原因】

 
 


 
 

因此有了点到一条线的距离,但是我们需要的是点到分隔线的距离。

 
 

分隔线的性质:我们要的分数(W^T * Xn + b)和结果(yn)是同号的。因此上面的距离公式的绝对值可以化简掉。

 
 


 
 

至此得到的新的式子,但还是不会解。

 
 

世界上其实没有那么多条线,也就是说同一条线能用不同的方程式来表示,例如蓝色框框的第一点所述,也就是说线的系数可以放缩。

所以我们可以用特殊放缩使得式子更简单。

蓝色框框第二点所述,那部分最小的话刚好等于1,则margin就可以表示为 1/w长度。

所以可以把 margin 换掉为 1/||w||,但是要求yxb相关部分要取最小值1.这个条件就包含了原来的要求yxb相关部分要大于0。

 
 


 
 

所以得到了上面的黄色狂所述的简洁的表示,还是不会解,因为最大化的问题里面还包含一个最小化的问题。

 
 

所以考虑放松一下条件,看能不能化简求解。但是我们首先要证明的是,就算我们把条件放松,最后的到的解还是落在原来的区域。

 
 

条件放松为 大于等于1,而不是等于1.

反证法:如果放松后最佳解落在外面(min yxb 部分最小的大于1),例如大于1.126,那么bw都除以1.126的结果比bw更好,这就矛盾了,所以可以证明:即使条件放宽到大于等一1,也会有不落在外面的结果。

 
 

所以原来的公式可以放松得到第二个黄色框所示,大大的简化了原来的问题。

这里还做了两个变化:最大化变成了最小化,求导,去掉根号部分,加上1/2。

 
 


 
 

练习

 
 


 
 

因此接下来我们要求解的是黄色框所示公式。

 
 

先举例一个特殊的例子,蓝色框所示,四个点就有四个条件,目标是最小化 W^t * W。

1式和3式 得到 W1 >= 1

2式和3式 得到 W2<=-1

所以就有了 W^T * W >= 1

所以就得到最终解了。

 
 

SVM 就冒出来了。

 
 


 
 

最胖的线就一定会有几个点离他最近。

如果我们去掉除这些最近点以外的点,在去找分隔线,会得到一样的结果。

也就是说这条分隔线就是由这些最近点决定的,其他点都不重要。

 
 

也就是说原来的资料可以看作两种:

一部分资料:告诉我们分隔线在哪 – support vector

另一部分资料:不需要

 
 

Support vector machine:可以看作一种找出最胖平面的方法,就是考虑分隔线最边边的点,就是上面的图示所标识的方法。

 
 


 
 

上面是解特例,那么通用解怎么解。

 
 

坏消息:不容易

好消息:目标最小化的是二次函数,条件是b,w的一次式,也就是二次规划(quadratic programming)的问题【线性规划进阶版】。数学上是可以求解的。

 
 

所以下一步:把问题变成二次规划的一般形式,然后使用已有的数学工具求解。

 
 


 
 

左边是目前的公式形式。

右边是二次规划的标准型。最小化u向量的二次函数,二次项系数Q,一次项系数P,条件是U向量的一次式,条件有M个,一次项系数A,常数项c。

 
 

因此我们要把这些系数向量提出来,如红色部分。Q里面与w有关的系数用I矩阵表示,其他都为0。P就是0向量。

 
 

直接使用matlab解QP问题。

 
 


 
 

因此这里就得到了一个新的演算法(linear hard-margin svm altorithm):

  1. 算系数
  2. 二次规划求解
  3. 得到的就是最胖的分隔线

 
 

Hard-margin:坚持圈圈叉叉一定是要完全分开的,不能有犯错误。

linear:使用直线分

 
 

如果你要非线性的,那就是把x做一个转换,基石里面有类似的方法来说明从直线到曲线的变化转换,此处类似。

 
 


 
 

练习

 
 


 
 

此处黄色公式用z代替x表示的就是非线性,在z空间做SVM。

 
 

此处我们再从理论上来解释为什么SVm可以得到好的结果。

 
 

与 regularization 比较,有趣的是条件和优化对调了:

Regularization:Ein 越小越好,条件是 W^T * W <= C 为的是不 overfit

SVM: W^T * W 越小越好,条件是 Ein = 0,就是上面那句话反着说

 
 

因此:SVM可以看作是一种 weight-decay 的 regularization。

 
 


 
 

另外一种解释:

 
 

Dvc:解决的是我想要知道我的线到底能产生多少种圈圈叉叉的排列组合。

 
 

现在考虑:

如果我今天喜欢的是胖的线,定一个胖的标准,如果资料拿来能找到达标的胖的线就是好的结果,找不到足够胖的线就没有结果

那么同样考虑在一组特定的资料上,到底能够找出多少足够胖的区分圈圈叉叉的组合

 
 

举例:

不计较胖瘦,绿色图示,三个点八种情况,都能分开。

计较胖瘦,红色图示,线的粗度要超过1.126,那么三个点,八种情况下都不一定能分开(具体和数据点相关)。

 
 

Dvc 有你能够做出几种情况来决定,情况越少复杂度越低。因此线越粗,有效的Dvc就可能越低,就是越好的分类。

 
 


 
 

我们考虑线的胖度来算演算法的Dvc,就看其最多最多能shatter多少个点。

(演算法的Dvc是没有绝对定义的,其结果与实际拿到的资料有关)

 
 

shatter的意思就是所有圈圈叉叉的排列组合。

 
 

如图平面上有三个点,在一个单位圆的边上。

如果不在乎分隔线的胖瘦,区分这三个点的所有排列组合都能做出来,Dvc就是3。

如果线要有 (根号3)/2 那么胖,那么圆上任意三点你做不到所有情况都产生出来(存在两个差异点之间的距离小于根号3就不能产生出区分情况),所以 Dvc 小于3。

 
 

数学上证明结论如上面公式,其Dvc与两个事情相关:资料的空间大小R,你容许的胖的程度p。

就是说:透过设定胖瘦条件,真的可以降低Dvc,所以理论上SVM就是一种控制复杂度的方式。

 
 


 
 

一开始我们喜欢 hyperplanes 的原因是它的有效数量不是很多,Dvc比较小,可以有效控制复杂度,但是呢太简单的平面不一定能把事情做好。 – not many

反过来我们考虑更复杂的平面,通过feature transform来实现,虽然可以处理很复杂的情况了,但是数量就变多了,Dvc就变得很大。- sophisticated(复杂)

原来只能二选一。

 
 

这里我们讲了一个新的概念 large-margin ,就是要胖的 hyperplanes,作用是控制数量,Dvc变比较小。

 
 

Large-margin hyperplanes + feature transform

可以做到的是,降低Dvc,但同时还能透过transform得到复杂的boundary。- not many & sophisticated

 
 

SVM 的好处:有了一种新的控制复杂度的方法,这样就可以尽情的采用各式各样不同的 feature transform。

 
 


 
 

练习

 
 


 
 

总结:

这里讲的是 linear support vector machine

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 

下一讲

我们开始讲将SVM的复杂度控制配合非线性的转换,看可以做到什么事情。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags