Svm基本知识与原理 张立新.

Presentation on theme: "Svm基本知识与原理 张立新."— Presentation transcript:

1 Svm基本知识与原理 张立新

2 SVM入门（一）SVM的八股简介 支持向量机(Support Vector Machine)是Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力 。 所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。结构风险最小听上去文绉绉，其实说的也无非是下面这回事。

3 机器学习本质上就是一种对问题真实模型的逼近，但毫无疑问，真实模型一定是不知道的。那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。这个与问题真实解之间的误差，就叫做风险。我们选择了一个假设后，真实误差无从得知， 但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。

4 R(w)≤Remp(w)+Ф(h/n)统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。
此时的情况便是选择了一个足够复杂的分类函数，能够精确的记住每一个样本，但对样本之外的数据一律分类错误。 统计学习引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上可以信任分类器在未知样本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值。 置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。 R(w)≤Remp(w)+Ф(h/n)统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。

5 SVM入门（二）线性分类器Part 1 C1和C2是要区分的两个类别，中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。 什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称——超平面（Hyper Plane）！ 实际上，一个线性函数是一个实值函数，而我们的分类问题需要离散的输出值，这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。

6 例如我们有一个线性函数 g(x)=wx+b
我们可以取阈值为0，这样当有一个样本xi需要判别的时候，我们就看g(xi)的值。若g(xi)>0，就判别为类别C1，若g(xi)<0，则判别为类别C2。此时也等价于给函数g(x)附加一个符号函数sgn()，即f(x)=sgn [g(x)]是我们真正的判别函数。 关于g(x)=wx+b这个表达式要注意三点：一，式中的x不是二维坐标系中的横轴，而是样本的向量表示。二，这个形式并不局限于二维的情况，在n维空间中仍然可以使用这个表达式，只是式中的w成为了n维向量；三，g(x)不是中间那条直线的表达式，中间那条直线的表达式是g(x)=0，即wx+b=0，我们也把这个函数叫做分类面。 实际上很容易看出来，中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以。

7 SVM入门（三）线性分类器Part 2 对于样本分类的不适定问题，需要有一个指标来衡量解决方案的好坏，而分类间隔是一个比较好的指标。我们定义一个样本点到超平面的间隔：δi=yi(wxi+b)。现在把w和b进行归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间隔就可以写成 这个公式是不是看上去有点眼熟？没错，这不就是解析几何中点xi到直线g(x)=0的距离公式嘛！（推广一下，是到超平面g(x)=0的距离) 。||w||叫做向量w的范数，范数是对向量长度的一种度量。当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更加直观的展示出了几何间隔的现实含义：

8 H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。误分次数一定程度上代表分类器的误差。几何间隔与样本的误分次数间存在关系：
注意到间隔与||w||是成反比的，因此最大化间隔与最小化||w||完全是一回事。而我们常用的方法并不是固定||w||的大小而寻求最大几何间隔，而是固定间隔，寻找最小的||w||。

9 SVM入门（四）线性分类器的求解——问题的描述与转化
由上节可知 我们的目标函数： 用另一个完全等价的目标函数来代替，那就是： 如果直接来解这个求最小值问题，很容易看出当||w||=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，这个时候，所有的样本点（无论正样本还是负样本）都跑到了H1和H2中间，而我们原本的意图是，H1右侧的 被分为正类，H2 左侧的被分为负类，位于两类中间的样本则拒绝分类。这下可好，所有样本点都进 入了无法分类的灰色地带。造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件， 体现在我们的问题中就是样本点必须在H1或H2的某一侧（或者至少在H1和H2上），而不能跑到两者中间。

10 我们把间隔固定为1，这是指把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，按照间隔的定义，满足这些条件就相当于让下面的式子总是成立：
yi[(w·xi)+b]≥1 (i=1,2,…,l) （l是总的样本数） 经常用变换过的形式： yi[(w·xi)+b]-1≥0 (i=1,2,…,l) （l是总的样本数） 我们分类问题也被转化成一个带约束的最小值的问题： 在这个问题中，自变量就是w，而目标函数是w的二次函数，所有的约束条件都是w的线性函数这种规划问题有个很有名气的称呼——二次规划，而且可以更进一步的说，由于它的可行域是一个凸集，因此它是一个凸二次规划。凸二次规划让人喜欢的地方就在于，它有解，而且可以找到。

11 完整重复。 我们想求得这样一个线性函数g(x)=wx+b 求这样的g(x)的过程就是求w和b两个参数的过程。求g(x)的时候，w才是变量。那么w是谁决定的？显然是你给的样本决定的，一旦你在空间中给出了那些个样本 点，三条直线的位置实际上就唯一确定了。样本确定了w，用数学的语言描述，就是w可以表示为样本的某种组合： w=α1x1+α2x2+…+αnxn 式子中的αi是一个一个的数，而xi是样本点，因而是向量，n就是总样本点的个数。严格区别数字与向量的乘积和向量间的乘积，用α1x1表示数字和向量的乘积，而用<x1,x2>表示向量x1,x2的内积。

12 因此g(x)的表达式严格的形式应该是：g(x)=<w,x>+b w不仅跟样本点的位置有关，还跟样本的类别有关。因此用下面这个式子表示才算完整：
w=α1y1x1+α2y2x2+…+αnynxn （式1） 其中的yi就是第i个样本的标签，它等于1或者-1。 其实以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于 0，这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在H1和H2上，也正是这部分样本唯一的确定了分类函数，当然，更严格的说，这些样本的一部分就可以确定，因为例如确定一条直线，只需要两个点就可以，即便有三五个都落在上面，我们也不是全都需 要。这部分我们真正需要的样本点，就叫做支持（撑）向量。 因此原来的g(x)表达式可以写为：

13 部分可以从内积符号中拿出来，得到g(x)的式子为：

14 SVM入门（五）为何需要核函数 问题只是它不是一个线性函数，但是，下面要注意看了，新建一个向量y和a： g(x)=f(y)=ay
看出妙在哪了么？原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的！因此这也形成了我们最初想解决线性不可分问题的基本思路——向高维空间转化，使其变得线性可分。

15 如果有这样的函数，那么当给了一个低维空间的输入x以后
g(x)=K(w,x)+b f(x’)=<w’,x’>+b 这两个函数的计算结果就完全一样，我们直接拿低维的输入往g(x)里面代就可以了（这回的g(x)就不是线性函数啦，因为你不能保证K(w,x)这个表达式里的x次数不高于1）。万幸的是，这样的K(w,x)确实存在，它被称作核函数，而且还不止一个，事实上，只要是满足了Mercer条件的函数，都可以作为核函数。核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。 这就是说，尽管给的问题是线性不可分的，但是我们就硬当它是线性问题来求解，只不过求解过程中，凡是要求内积的时候就用你选定的核函数来算。 这样求出来的α再和你选定的核函数组合，就得到分类器啦！

16 SVM入门（六）松弛变量 现在我们已经把一个本来线性不可分的文本分类问题，通过映射到高维空间而变成了线性可分的。圆形和方形的点各有成千上万个现在想象我们有另一个训练集，只比原先这个训练集多了一个样本，映射到高维空间以后，也就多了一个样本点，但是这个样本的位置是这样的： 就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题叫做“近似线性可分”的问题。

17 其实我们会觉得，更有可能的是，这个样本点压根就是错误，是噪声，是提供训练集的人在人工分类时错放进去的。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。
但这种对噪声的容错性是人的思维带来的，我们的程序可没有。由于我们原本的优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。 这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。因此由上面的例子中也可以看出，硬间隔的分类法其结果容易受少数点的控制，这是很危险的。解决方法也很明显，就是仿照人的思路，允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔来衡量有利于我们表达形式的简洁。我们原先对样本点的要求是：

18 意思是说离分类面最近的样本点函数间隔也要比1大。如果要引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许
因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时，意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔。显然我们必须权衡这种损失和好处。好处很明显，我们得到的分类间隔越大，好处就越多。回顾我们原始的硬间隔分类对应的优化问题

19 ||w||2就是我们的目标函数，希望它越小越好，因而损失就是一个能使之变大的量。那如何来衡量损失，有两种常用的方式，有人喜欢用
把损失加入到目标函数里的时候，就需要一个惩罚因子，原来的优化问题就变成了下面这样： 注意 一：并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有。

20 所有没离群的点松弛变量都等于0 二是松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。 三是惩罚因子C决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这就退化成了硬间隔问题。 四是惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值，再解一次优化问 题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身决不是一回事，优化问题在解的过程中，C一直是定值，要记住。

21 五是尽管加了松弛变量这么一说，但这个优化问题仍然是一个优化问题，解它的过程比起原始的硬间隔问题来说，没有任何更加特殊的地方。
从大的方面说优化问题解的过程，就是先试着确定一下w，也就是确定了前面图中的三条直线，这时看看间隔有多大，又有多少点离群，把目标函数的值算一算，再换一组三条直线，再把目标函数的值算一 算，如此往复（迭代），直到最终找到目标函数最小时的w。

22 谢谢!