《svm算法简介解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《svm算法简介解析ppt课件.ppt（53页珍藏版）》请在三一办公上搜索。
1、svm(supported vector machine),概念： 支持向量机是Corinna Cortes和Vapnik等于1995年首先提出的，其基本原理是（以二维数据为例）：如果训练数据是分布在二维平面上的点，它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是，通过训练，找到这些分类之间的边界。对于多维数据（如N维），可以将它们视为N维空间中的点，而分类边界就是N维空间中的面，称为超面（超面比N维空间少一维）。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。数据：线性可分&线性不可分,线性可分线性不可分情况1：样本本质上是非线性可分的解决方法：核函数情况2：本质上线性
2、，非线性由噪音导致强制使用非线性函数，会导致过拟合 解决方法：软间隔,两种情况,线性可分,定义： 对于来自两类的一组模式 ,如果能用一个线性判别函数正确分类,则称他们是线性可分的。,线性不可分,线性可分情况,我们怎样才能取得一个最优的划分直线f(x)呢？,最大距离Maximum Marginal,从概率的角度上来说，就是使得置信度最小的点置信度最大从实践的角度来说，这样的效果非常好从误差的角度，误分次数 （其中， 是样本集合到分类面的间隔，R是空间中一个能完全包含样本数据的球的半径）误分次数一定程度上代表分类器的误差，间隔越大的解，它的误差上界越小。,函数间隔,定义函数间隔为：接着，我们定义超
3、平面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点（xi,yi）的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有,定义函数间隔的原因,一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面 确定的情况下， 能够相对的表示点X到超平面的远近，而 的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量 的正负性来判定或表示分类的正确性和确信度，于是引出函数间隔概念。,函数间隔的局限性,上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改
4、变为2w和2b，虽然此时超平面没有改变，但函数间隔的值却发生改变。我们可以对法向量w加些约束条件，使其表面看起来规范化，如此，我们引入了真正意义点到超平面的距离-几何间隔。,几何间隔,在函数间隔 的基础上，对w和b进行归一化，即为几何间隔：这时如果成比例的改变w和b，几何间隔的值不会发生改变。,因为wx+b=0，为了方便，我们可以按任意比例缩放w和b，而不会改变结果。我们可以添加这样的约束条件 ，这意味着可以先求出w和b的解，之后重新缩放这些参数，就可以轻易地满足这个条件。,最大间隔分类器的定义,由于函数间隔的缺陷，不适合用来最大化一个量，因为在超平面固定以后，我们可以等比例地缩放w好b的值，
5、这样可以使得 的值任意打，亦即函数间隔可以在超平面不变的情况下被取得任意大。而几何间隔则没有这个问题，因为除上 这个分母，所以缩放w和b的时候几何间隔不会随之改变，它只随超平面的变动而变动，因此更加适合用其来定义最大距离。,因此，我们的最大间隔分类的目标函数可以定义为： 事实证明这个约束是一个非凸性约束，我们需要避免，所以我们需要改变优化问题的表述方式。,添加约束条件， 这是一个隐含的缩放约束，因为假设你已经解出了w和b，并且发现最差情形的函数间隔是10或者其他值，这样，通过对w和b除以10或者其他值，我们可以将函数间隔变为1。,此时，优化问题的表达式为： 我们的优化问题转变成了一个凸优化问题
6、,目标函数是二次的，约束条件是线性的，所以这是一个凸二次规划问题，所以一定会存在全局的最优解，这个问题可以用现成的QP（quadratic programming）优化包或者二次程序软件进行求解。此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性变换到对偶变量的优化问题，即通过与原问题等价的对偶问题得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解，二者可以自然的引入核函数，进而推广到非线性分类问题。,最优问题的求解,拉格朗日乘数法的扩展形式,minf(w)s.t. gi(w)0 i=1,2,.,k hi(w)=0 i=1,2,.,
7、l （这里0指的是零向量） 定义：,当所有约束条件都满足时有,对偶问题,一般有 ，但是在某些特定条件下（KKT），这两个最优化问题会取相同的值。（经证明，我们求解的目标函数满足条件KKT条件）,1.首先固定，要让L关于w和b最小化，我们分别对w,b偏导并令其等于零，得到带回 得到：,凸二次规划问题求解,问题转换为：由凸二次规划的性质能保证这样最优的向量a是存在的,凸二次规划问题求解,2.求对的极大，即是关于对偶变量的优化问题 （SMO优化算法-序列最小最优化算法）然后根据可求出最优的w和b，即最优超平面。,一个简单的例子：,x1 =(0, 0), y1 = +1x2 =(1, 0), y2 =
8、 +1x3 =(2, 0), y3 = -1x4 =(0, 2), y4 = -1,可调用Matlab中的二次规划程序，求得1, 2, 3, 4的值，进而求得w和b的值。,线性不可分情况下,情况1：样本本质上是非线性可分的 解决方法：核函数,将分类函数变形得最终分类函数，为：,根据线性可分情况下的结论：,我们把横轴上断电a,b之间红色部分里的所有点定为正类，两边黑色部分定为负类，不能找到一个线性函数将两类正确分开。,问题引入：,但是能找到一条二次曲线将正负类分开，它的函数表达式可以写为：,问题只是它不是一个线性函数，但是，新建一个向量在z和a：,在任意维度的空间中，这种形式的函数都是一个线性函
9、数（只不过其中的a,z是多维向量），因此，自变量z的次数不大于1。经过映射，判别函数为：,原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的。因此，这也形成了我们最初想解决线性不可分问题的基本思路-向高维空间转化，使其变得线性可分。 而转化的关键的部分在于找到x到y的映射方法。遗憾的是，如何找到这个映射没有系统的方法，此外，在数据维度较大时，计算困难（我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 的计算带来了非常大的困难，而且如果遇到无穷维的情况
10、，就根本无从计算了）。,如果有一种方式可以在特征空间中直接计算内积(xi ） (x)，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法，于是，核函数便横空出世了。核函数：对所有x,z属于X，满足 这里 是从X到内积特征空间F的映射。,分类函数为：,优化问题的表达式：,常见核函数,多项式核线性核 高斯径向基函数核Sigmoid核,对于核函数的选择，现在还缺乏指导原则。各种实验的观察结果表明，某些问题用某些核函数效果很好，用另一些很差，但一般来讲，径向基核函数是不会出现太大偏差的一种，首选。 如果使用核函数向高维空间映射后，问题仍
11、然是线性不可分的，怎么办？,情况2：本质上线性，非线性由噪音导致 强制使用非线性函数，会导致过拟合 解决方法：软间隔,想象我们有另一个训练集，它是方形的（负类），这单独的一个样本使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）。叫做“近线性可分”问题。,我们会觉得，这个点可能是错误的，是噪声。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。 但这种对噪声的容错性是人的思维带来的，我们的程序没有，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表距离，是非负的，像这种情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为
12、他硬性的要求所有样本点都满足和分类平面间的距离大于某个值。 由上面的例子可以看出，硬间隔分类法其结果容易受少数点的控制。,解决方法,允许一些点到分类平面的距离不满足原先的要求。原先对样本点的要求是（意思是说离分类面最近的样本点函数间隔要比1大）： 如果引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许：,因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的间隔。,如何衡量损失,
13、把损失加入到目标函数里的时候，就需要一个惩罚因子C，原来的优化问题变为：,注意,并非所有的样本点都有一个松弛变量与其对应，实际上只有离群点才有。松弛变量的值实际上标示出了对应的点到底离群多远，值越大，点越远。惩罚因子决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这就退化成了硬间隔问题。,注意,惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值，指定这个值以后，解一下
14、，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值，再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身不是一回事，优化问题在求解的过程中，C一直是定值。尽管加入了松弛变量，但是优化问题的求解过程与硬间隔问题求解过程无异。,用之前的方法将限制条件加入到目标函数中，得到新的拉格朗日函数， 分析方法和前面一样，让L对w,b,最小化 将w带回目标函数并化简得到,不过，由于我们得到 而又有 （作为拉格朗日乘数法的条件），因此有 优化表达式变为,和之前的结果对比一下，可以看到唯一的区别就是多了一个上限C,而核函数化的非线性形式也是一样的，只
15、要把 换成k即可。,加入松弛变量的优化问题求解过程,先试着确定一下w，也就是确定图中的三条直线，看看间隔有多大，有多少离群点，算出目标函数。然后换一组三条直线，再把目标函数的值算一下，如此迭代，直到找到目标函数最小时的w.,特例-偏斜问题,样本的偏斜，也叫数据集偏斜，它是指参与分类的两个类别（也可以指多个类别）样本数量差异很大，比如说正类有10000个样本，而负类只有100个，如图,方形的点是负类，H,H1，H2是根据给的样本算出来的分类面，由于负类的样本很少很少，所以有一些本来是负类的样本没有提供，比如图中两个灰色的方形点，如果这两个点提供的话，那么算出来的分类面应该是H”，H2”,H1，实
16、际上负类给的样本点越多，越容易出现在灰色点附近的点，我们算出的结果也就越接近于真实的分类面，但现在由于出现偏斜的现象，使得数量多的正类可以把分类面向负类方向“推”，因而影响了结果的准确性。,解决方法,给样本量少的负类更大的惩罚因子，表示我们重视这部分样本（本来样本就少，所以抛弃的应该少），因此我们的目标函数中因松弛变量而损失的部分变成了,样本的偏斜不仅由于数量，还由样本分布的广度决定。说一个具体的例子，给政治类和体育类的文章做分类，政治类的文章多，而体育类只提供几篇关于篮球的文章，这时分类会明显偏向于政治类，如果要给体育类增加样本，但增加的样本仍然全都是篮球的，那即使体育类文章在数量上可以达到
17、与政治类一样多，但过于集中了，结果仍偏向政治类。,所以，给C+和C-确定比例更好的方法可以是衡量他们分布的程度。比如可以算算他们在空间中占据了多大的体积，例如给正负两类分别找一个超球面，它们分布包含正、负类所有样本，比较两个球的半径，就可以大致确定分布的情况。显然半径大的分布比较广，就给小一点的惩罚因子。,然而，存在一种情况，有的类别样本确实很集中，这不是提供样本数量多少的问题，而是这类别本身的特征（就是某些话题涉及的面很窄，例如计算机类的文章明显不如文化类的文章丰富），这时候即便超球面的半径相差很大，也不应该赋予两个类别不同的惩罚因子。 所以，完全的方法是没有的，需要根据需要，选择实现简单又合理的方法。,
