Svm基本知识与原理.ppt

1、Svm的基本知识和原理、张新新、Svm入门(1)SVM的八股介绍支持向量机是Vapnik于1995年首次提出的，它在解决小样本、非线性和高维模式识别中有许多特有的优势并且可以推广应用的支持向量机方法基于集成校正学习理论的VC维理论和结构风险最小原理，基于有限样本信息在模型的复杂性(即特定训练样本的学习精度)与学习能力(即无错误地识别任何样本的能力)之间进行最佳折衷所谓VC次元是对于函数类的一种尺度，作为问题的复杂性可以简单理解，VC次元越高一个问题就越复杂。 构造上风险最小的听起来像是句缩，其实只不过如下。 机器学习本质上接近问题的实模型，但实模型一定不知道。 那么，我们不能知道我们选择的假设

2、和问题的真正解之间有多大的差别。 这个和问题的真正解的误差叫做风险。 我们选择假说后，虽然不知道真正的误差，但可以把握的量来近似。 最直观的想法是用分类器对样本数据进行分类的结果与实际结果(因为样本是已经标记的数据，因为它是准确的数据)之间的差来表达。 这种差别称为经验风险Remp(w )。 传统的机器学习方法以将经验风险降到最低为目标，但后来发现很多分类函数在样本集中很容易达到100%的正确率，在真正的分类中非常糟糕(所谓的普及能力差，泛化能力差)。 会选择足够复杂的分类函数来准确记住每个样本，但是非样本数据总是分类错误。 整合学习引入泛化误差界的概念，真正的风险应该用两个部分内容来描述，一

3、个是经验风险，表示有分类器的样本上的误差。 二是信任风险，说明了分类器在未知样本上分类的结果有多可靠。 显然，第二部分不能正确地进行校正，从而只能提供一个所估计的区间，只能校正整个误差，并不能校正正确的值。 信任风险与两个量有关。 一个是样本数，明显给出的样本数越多，我们的学习结果可能越正确，此时信任风险越小。 二是分类函数的VC维，明显VC维越大推进能力越差，信赖风险越大。 R(w)Remp(w) (h/n )统一修正学习的目标从经验风险最小化变为求经验风险和信赖风险的和最小，即结构风险最小。 SVM入门(2)线性分类器Part 1、C1和C2是区分的两个类，中间的直线是一个分类函数，能够完

4、全分离两个类的采样。 如果一个线性函数可以完全精确地分离样本，则这些数据称为线性可分离，否则称为非线性可分离。 什么是线性函数？ 一维空间中的一个点，二维空间中的一条直线，三维空间中的一个平面，可以这样想象。 如果不关注空间维数，则该线性函数具有统一的名称超平面(Hyper Plane )。 实际上，一个线性函数是一个实值函数，而我们的分类问题需要离散输出值，在这种情况下，可以简单地将阈值加到实值函数上，以根据在执行分类函数时所获得的值是大于还是小于该阈值来确定类别的归属。 例如，线性函数g(x)=wx b。 阈值为0时，需要判别样品xi时可以看到g(xi )的值。 如果是g(xi)0则判别为

5、类别C1，如果是g(xi)0则判别为类别C2。 此时，对函数g(x )附加编码函数sgn ()，即f(x)=sgn g(x )是等同于我们的真实判别函数。对于g(x)=wx b的表达式，需要注意到，“1”式中的x不是二维坐标系的横轴，而是样本的向量表达。 其次，该形式并不限定于二维的情况，在n维空间中也能够使用该式，但是，式中的w为n维向量的三，g(x )不是中间的直线的式，中间的直线的式是g(x)=0，即wx b=0，因此，也将该函数称为分类面。 实际上，中间的分界线不是唯一的，我们只要稍微旋转它，不弄错两种数据，就能达到上述效果。 可以稍微平移一下。 SVM入门(3)线性分类器Part 2

6、对于样本分类的不确定问题，需要测量解决方案的好坏的指标，分类间隔是比较好的指标。 我们定义从样本点到超平面的间隔： i=yi(wxi b )。 现在，将w和b标准化，用w/|w|和b/|w|分别替换原来的w和b，可以写出其间隔。 这个公式看起来有点面熟吗？ 是的。 这不是从解析几何中点xi到直线g(x)=0的距离式。 (展开时，超平面g(x)=0的距离。 |w|称为向量w的范数，范数是向量长度的尺度。 用规范化的w和b替换原始值后的间隔具有特殊的名称，称为几何间隔，该几何间隔表示从点到超平面的欧几里得距离，并且同样可以定义从点的集合(样本集合)到某个超平面的距离。 下图更直观地显示了几何间隔的

7、现实意义： h是分类面，H1和H2是平行于h、通过最接近h的两种样本的直线，H1和h、H2和h之间的距离是几何间隔。 误分次数在一定程度上表现了分类器的误差。 几何间隔和样品的误分割次数之间有关系：间隔与|w|成反比，间隔最大化与最小化|w|完全相同。 我们常用的方法不是固定|w|的大小来求最大几何间隔，而是固定间隔来寻找最小|w|的方法。 SVM入门(4)线性分类器的求解问题的记述和变换从上一节开始被我们的目标函数：另一个完全等价的目标函数替换，也就是说，如果直接求出该求最小值的问题，|w|=0时容易得到目标函数的最小值的图中反映的是， 当H1和H2这两条线之间的距离为无穷大时，所有样本点(

8、无论正样本还是负样本)行进在H1和H2之间，但我们原本打算拒绝H1右侧为正类、H2左侧为负类、两类中间的样本的分类。 这样就可以了。 所有的取样点都在无法分类的灰色区域。 造成这种结果的原因是，在说明问题时只考虑目标，不加制约条件，体现在我们的问题中，样本点必须是H1或H2中的一方(或者至少H1和H2上)，不能在两者之间行驶。 将间隔固定为1意味着在所有采样点中间隔最小的点的间隔为1，即，集合中的另一点的间隔不小于1，根据间隔的定义，满足这些条件对应于以下公式始终成立： yi (wxi ) b1(或l，l) (l是总样本数)我们的分类问题也被转换成受约束的最小值问题：在此问题中，称为自变量为w

9、、目标函数为w的二次函数、所有约束条件为w的线性函数的校正像素问题被称为有名的二次校正像素，更具体地说，因为其可执行区域是凸集合，所以我们喜欢凸二次校正像素的双曲馀弦值。 而想求出这样的线性函数g(x)=wx b的g(x )的过程是求出w和b两个残奥参数的过程。 求g(x )时，w是变量。那么w是谁决定的呢？ 显然是由你给的样品决定的。 给空间提供它们的样本、点和三条直线的位置，实际上是唯一确定的。 当确定了样本w并且以数学语言来描述时，可以将w表达为某个样本组合： w=11-22 nxn公式中的I是一个整数，因为xi是样本点，所以n是总样本点的数目。 严格地区分数字和向量的积和向量的积，用1

10、x1表示数字和向量的积，表示向量x1、x2的内积。 因此，g(x )表达式的精确格式应该与样本点的位置有关，而且与样本类别有关。 因此，w=1y1x1 2y2x2 nynxn中的yi是第I个样本的标签，其等于1或-1。 其实在上式的拉格朗日乘法中，只有少数部分不等于0，该部分不等于0的拉格朗日乘法之后所乘的样本点，其实落到H1和H2，即该部分的样本当然确定唯一分类函数，更严格地说，这些样本因此，原始的g(x )方程可部分地从内积符号取出，用于得到g(x )的方程是： SVM入门(5)为什么需要核函数，问题不是线性函数，但是将注意到以下几点，以创建新的向量y和a : 你知道精彩之处在哪里吗？ 原

11、本二维空间中的一个线性不可分问题，映射到四维空间后就变成了线性不可分，因此，我们将首先想要解决线性不可分问题的基本思想变换为高维空间，使之变成了线性不可分。 若有这个函数，若给定低维空间的输入x，则g(x)=K(w，x) b f(x)=b这两个函数的校正结果完全相同，我们只要将直接低维的输入放入g(x )中就可以(这次g )幸运了内核函数的基本作用是能够接收两个低维空间中的向量并通过一种变换来纠正高维空间中的向量内积值。 这是给出的问题是线性不可分的，但我们解为线性问题，在解的过程中求内积时用你选择的核函数进行修正。 这样求得的是，如果与你选择的核函数组合，就能得到分类器，SVM入门(6)缓和

12、变量，现在由于将本来不可线性分类的文本分类问题映射到高维空间，所以变得线性不可分。 圆形和方形的点各有几千个。 现在我们想象着还有一个训练集。 只有一个样本比原来的训练集多，如果映射到高维空间，则另一个样本点多。 然而，该样本的位置是图中的黄色点，它是方形的，它是负类样本，是这个单独的样本。这类相似的问题被称为“近似线性可分”问题。 实际上，这个样本点是完全错误的，是噪音，我认为提供训练集的人在人工分类时很可能放错了。 所以，我们简单地忽略了这个样本点，使用了原来的分类器，但其效果一点也没有影响。 但是，这种对噪音的耐受性是由人类的思考带来的，没有我们的程序。在我们原来的优化问题的表达式中，几

13、何间隔本身表示距离，非负，因为确实考虑了所有采样点，并且在此基础上寻找正负类之间的最大几何间隔，这种有噪声的情况不能解决整个问题。 此解决方案也称为硬空间分类法。 这是因为硬要求所有采样点与分类平面之间的距离必须大于一定值。 因此，从上面的例子可以看出，硬空间分类法的结果容易受少数点支配，很危险。 解决方法也很明显，就是仿照人的想法，允许从一部分到分类平面的距离不满足原来的要求。 由于每个点的间隔尺度因训练集而异，因此以间隔进行测量有助于我们表现形式的简洁化。 原本对样本点的要求意味着最接近分类表面的样本点函数间隔也大于1。 在引入容错性时，对1这一硬阈值加上松弛变量，即允许。 由于松弛变量不

14、是负的，所以最终所需的间隔可以小于1。 但是，在某一点上这个间隔小于1意味着放弃了这些点的正确分类，对我们的分类器来说是损失。 然而，丢弃这些点有不需要在这些点的方向上移动分类的表面并且可以获得更大的几何间隔的优点。 很明显，我们必须对这一损失和利益进行比较研究。 优点很明显，我们得到的分类间隔越大，优点就越多。 回顾一下对应于我们原始硬空间分类的优化问题，|w|2是我们的目标函数，希望越小越好，损失是可以增大的量。 那个怎么衡量损失，有两种常用的方式。 喜欢某个人，把损失列入目标函数时，需要处罚因子。 原来的优化问题如下所示。 注意1 :并非所有的样本点都有松弛变量。 实际上只有“离群点”。 未离群的所有点缓和变量等于02表示缓和变量的值实际对应的点离群多少，值越大表示点越远。 第三，你决定了多重视由离群点造成的损失，显然当离群点的缓和变量之和为一定时，暗示了你决定的c越大，对目标函数的损失也越大，这时，暗示了你不想放弃这些离群点，是最极端的