支持向量机原理课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,-,*,支持向量机,201,4,-,2,-,21,1,-,支持向量机2014-2-211-,本讲,主要内容,一.支持向量机,二.,最大间隔分类器,三.,核函数,四.软间隔优化,五.支持向量机总结,2,-,本讲主要内容一.支持向量机2-,一.,SVM warming up,1.1 SVM概念简介,1.2 超平面,1.3 logistic回归,1.4 形式化表示,1.5 函数间隔与几何间隔,3,-,一.SVM warming up 3-,1.1,SVM概念简介,支持向量机（SVM）是 90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。,通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。,4,-,1.1 SVM概念简介支持向量机（SVM）是 90 年代中期,1.2 超平面,超平面H是从n维空间到n-1维空间的一个映射子空间,。,设d是n维欧式空间R中的一个非零向量，,a是实数，则R中满足条件dX=a的点X所组成的集合称为R中的一张超平面。,5,-,1.2 超平面 超平面H是从n维空间到n-1维空间的一,1.3 logistic回归,Logistic 回归目的是从特征学习出一个 0/1 分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic 函数（或称作 sigmoid 函数）将自变量映射到(0,1)上，映射后的值被认为是属于 y=1 的概率。,6,-,1.3 logistic回归Logistic 回归目的是从特,1.3 logistic回归,形式化,表示：,假设函数为：,x 是 n 维特征向量，函数 g 就是 logistic 函数,。,其中,图像如图所示：,可以看到，将无穷映,射到了(0,1),7,-,1.3 logistic回归形式化表示：7-,1.4 形式化表示,结果标签是y=-1,y=1，替换logistic回归中的y=0和y=1。,同时将替换成w和b。以前的,，其中认为 。现在我们替换 为b，后面,替换为 （即 ）。,我们只需考虑 的正负问题，而不用关心g(z)，因此我们这里将g(z)做一个简化，将其简单映射到y=-1和y=1上。映射关系如下：,8,-,1.4 形式化表示结果标签是y=-1,y=1，替换logis,1.5 函数间隔与几何间隔,定义函数间隔为：,x是特征，y是结果标签。i表示第i个样本,。,（这是单个样本）,全局函数间隔：,在训练样本上分类正例和负例确信度最小那个函数间隔,9,-,1.5 函数间隔与几何间隔定义函数间隔为：9-,1.5 函数间隔与几何间隔,几何间隔：,全局几何间隔：,10,-,1.5 函数间隔与几何间隔几何间隔：10-,二.,最大间隔分类器,2.1 二次规划原问题建立,2.2 拉格朗日对偶,2.2.1 等式约束,2.2.1 不等式约束,2.3 最大间隔分类器,11,-,二.最大间隔分类器 2.1 二次规划原问题建立11-,2.1 二次规划原问题建立,形式1：,形式2：,形式3：,12,-,2.1 二次规划原问题建立形式1：12-,2.2拉格朗日对偶之等式约束,问题：,目标函数是f(w)，通常解法是引入拉格朗日算子，这里使用来表示,算子，得到拉格朗日公式为：,L是等式约束的个数。然后分别对w和,求偏导，使得偏导数等于0，然后解出w和,。,13,-,2.2拉格朗日对偶之等式约束问题：13-,2.2拉格朗日对偶之不等式约束,问题：,利用,拉格朗日公式,变换：,令,知,14,-,2.2拉格朗日对偶之不等式约束问题：14-,2.2拉格朗日对偶之不等式约束,原来要求的min f(w)可以转换成,求了。,利用对偶求解:,D的意思是对偶，,将问题转化为先求拉格朗日关于w的最小值，将,和,看作是固定值。之后在,求最大值的话：,15,-,2.2拉格朗日对偶之不等式约束原来要求的min f(w)可以,2.2拉格朗日对偶之不等式约束,下面解释在什么条件下两者会等价。假设f和g都是凸函数，h是仿射的。并且存在w使得对于所有的i，,。在这种假设下，一定存在,使得是,原问题的解，,是对偶问题的解。还有另外，,满足库恩-塔克条件（Karush-Kuhn-Tucker,KKT condition），该条件如下：,16,-,2.2拉格朗日对偶之不等式约束下面解释在什么条件下两者会等价,2.3 最大间隔分类器,重新回到SVM的优化问题：,我们将约束条件改写为：,17,-,2.3 最大间隔分类器重新回到SVM的优化问题：17-,2.3 最大间隔分类器,从KKT条件得知只有函数间隔是1（离超平面最近的点）的线性约束式前面的系数,，也就是说这些约束式,，对于其他的不在线上的点(,)，极值不会在他们所在的范围内取得，因此前面的系数,.注意每一个约束式实际就是一个训练样本,。,18,-,2.3 最大间隔分类器 从KKT条件得知只有函数间隔是1（,2.3 最大间隔分类器,实线是最大间隔超平面，假设号的是正例，圆圈的是负例。在虚线上的点就是函数间隔是1的点，那么他们前面的系数,，其他点都是,。这三个点称作支持向量。构造拉格朗日函数如下：,19,-,2.3 最大间隔分类器实线是最大间隔超平面，假设号的是正例,2.3 最大间隔分类器,下面我们按照对偶问题的求解步骤来一步步进行，,首先求解,的最小值，对于固定的,，,的最小值只与w和b有关。对w和b分别求偏导数。,20,-,2.3 最大间隔分类器下面我们按照对偶问题的求解步骤来一步步,2.3 最大间隔分类器,得到：,代入后，,结果如下,：,由于最后一项是0，因此简化为,21,-,2.3 最大间隔分类器得到：21-,2.3 最大间隔分类器,此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b。,接着是极大化的过程,22,-,2.3 最大间隔分类器此时的拉格朗日函数只包含了变量。然而我,2.3 最大间隔分类器,前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束都是凸函数，而且这里不存在等式约束h。存在w使得对于所有的i，,因此，一定存在,使得,是原问题的解，是对偶问题的解。在这里，求,就是,求了。,如果求出了，根据即可求出w（也是 ，原问题的解）。然后,即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。,23,-,2.3 最大间隔分类器 前面提到过对偶问题和原问题满足的几个,三.,核函数,3.1 核函数简介,3.2 核函数有效性判定,24,-,三.核函数 24-,3.1 核函数简介,建立一个R,2,R,3,的非线性映射,计算,R,3,中2个矢量的内积：,定义核函数：，则：,输入空间,特征空间,25,-,3.1 核函数简介 建立一个R2R3的非线性映射输入空,3.1 核函数简介,上个例子说明：特征空间中两个矢量之间的内积可以通过定义输入空间中的核函数直接计算得到。,这就启示我们可以不必定义非线性映射,而直接在输入空间中定义核函数,K,来完成非线性映射。,这样做的条件是：,定义的核函数,K,能够,对应于特征空间中的内积；,识别方法中不需要计算特征空间中的矢量本身，而只须计算特征空间中两个矢量的内积。,26,-,3.1 核函数简介上个例子说明：特征空间中两个矢量之间的内,3.1 核函数简介,SVM的求解，最后归结为如下目标函数的优化：,可以引入非线性映射,，则目标函数变为：,而权矢量为：,判别函数：,27,-,3.1 核函数简介SVM的求解，最后归结为如下目标函数的优,3.2 核函数有效性判定（Mercer定理）,作为核函数应满足如下条件：,是 下的对称函数，对任意 ，且,有：,成立，则 可以作为核函数。,或者,如果函数K是上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例，其相应的核函数矩阵是对称半正定的。,28,-,3.2 核函数有效性判定（Mercer定理）作为核函数应满,四.软间隔优化,4.1 规则化和不可分情况处理,4.2 坐标上升法,4.3 SMO优化算法,29,-,四.软间隔优化29-,4.1 规则化和不可分情况处理,问题：,拉格朗日变换：,30,-,4.1 规则化和不可分情况处理30-,4.1 规则化和不可分情况处理,看看KKT条件的变化：,31,-,4.1 规则化和不可分情况处理31-,4.2 坐标上升法,问题：,32,-,4.2 坐标上升法问题：32-,4.3 SMO优化算法,33,-,4.3 SMO优化算法33-,五.支持向量机总结,SVM重点是,拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。,对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一层sigmoid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。,34,-,五.支持向量机总结 SVM重点是拉格朗日对偶的,五.支持向量机总结,之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。,35,-,五.支持向量机总结 之后所有的推导都是去解决目标函,谢谢！,36,-,谢谢！36-,