svm支持向量机课件[共55页]

1、1前情提要前情提要l 支持向量机的创新之一在于将分类面的求支持向量机的创新之一在于将分类面的求解看作是一个解看作是一个二次规划二次规划问题问题l支持向量机的创新之二在于揭示了对分类支持向量机的创新之二在于揭示了对分类起关键作用的只是一部分训练样本，即起关键作用的只是一部分训练样本，即支持支持向量向量1.1.对对线性线性支持向量机的小结支持向量机的小结22.2.线性支持向量机的数学模型：线性支持向量机的数学模型：( ),iiii SVfxyx xb 其中其中i通过求解如下的优化问题得到：通过求解如下的优化问题得到：1min(, ),2w bw w(,)1iiyw xb 1,2,ilL. .s t

2、1,11max( ),2lliijijijii jWy yx x10liiiy. .s t前情提要前情提要( (续续1)1)3前情提要前情提要( (续续2)2)3.3.线性支持向量机的编程实现：线性支持向量机的编程实现：( ),iiii SVfxyx xb 1,11max( ),2lliijijijii jWy yx x10liiiy. .s tMatlab C svcoutput(trnx,trny,testx,linear,alpha,bias);nsv alpha bias=svc(trnx,trny,linear); svm_model * svm_train(svm_problem

3、*prob, svm_parameter *param)svm_predict(svm_model *model, svm_node *x)4SVM For Nonlinear Problems求解非线性问题的求解非线性问题的SVM4第四讲第四讲51.1.如何解决少量非线性可分样本？如何解决少量非线性可分样本？5内容提要内容提要2.2.如何解决大量非线性可分样本？如何解决大量非线性可分样本？3.3.核函数方法（核函数方法（Kernel Trick）4.4.SVM背后的统计学习理论背后的统计学习理论6基本思想：基本思想：通过训练误差通过训练误差和类间宽度之间的权衡，和类间宽度之间的权衡，得到一个

4、最优超平面。得到一个最优超平面。1. 线性线性SVM求解含少量非线性可分样本的思想求解含少量非线性可分样本的思想优化目标：优化目标：111min( , ;,),()2lliiw bw wC L,1iiiyw xb 约束条件：约束条件：0i1,2,ilL权衡因子松弛变量7l1类样本：位于分类间隔之外7类似的，通过类似的，通过Lagrange函数，转化为对偶问题函数，转化为对偶问题1 1类样本类样本2 2类样本类样本3 3类样本类样本1,11max( ),2lliijijijii jWy yx x 0iC1,2,ilL1. .0liiisty0i 0iC ( )1if x( )1if x( )1i

5、f xiC l2类样本：支持向量l3类样本：位于分类间隔之内8不同的权衡因子得到的不同的分类面C10C100092.2.非线性支持向量机非线性支持向量机 当线性支持向量机划分样本会产生过当线性支持向量机划分样本会产生过多训练误差时，需要考虑使用非线性分类多训练误差时，需要考虑使用非线性分类面对两类样本进行划分。面对两类样本进行划分。102.1 2.1 寻找非线性问题的三种思路寻找非线性问题的三种思路l思路思路1:1:原空间法原空间法 在原空间中直接求解非线性问题在原空间中直接求解非线性问题11 例例1：XOR问题问题l思路思路2 :2 :特征空间法特征空间法 将非线性问题的求解转换成另一个空间

6、将非线性问题的求解转换成另一个空间中的线性问题求解中的线性问题求解12( ,)xx x12221231 2( )( ( ),( ), ( )( , 2)xxxxx xxx(0,0,0)(1,1,2)(0,1,0)(1,0,0)(0,0)(1,1)(0,1)(1,0)12 例例2 2：物种分类问题：物种分类问题13寻找特征映射所面临的问题：1. 特征映射的确定往往需要相当高的技巧和相当专业的领域知识；3. 特征映射往往是一个低维向高维映射的过程，这个映射过程经常面临维数灾难。2. 特征映射的计算可能会相当复杂；14思路思路3. 核函数方法核函数方法1,11max( ),2lliijijijii

7、jWy yx x. .s t0i10liiiy优化问题：优化问题：判别函数：判别函数：*( )sgn(,)iiif xyx xb支持向量样本之间的内积结结 论：论： 构建支持向量机只需要知道任意两个样本之间的内积定义，无需知道样本点自身的特征表示构建到特征空间的隐式映射构建到特征空间的隐式映射152.2 2.2 线性线性SVMSVM通过核函数扩展为非线性通过核函数扩展为非线性SVMSVM( ),iiii SVfxyx xb 线性线性SVM:SVM:假设经过某种非线性特征映射后原来的非线性可分问题可以假设经过某种非线性特征映射后原来的非线性可分问题可以通过线性通过线性SVMSVM来解决，则在特征

8、空间中的判别函数可以表示为：来解决，则在特征空间中的判别函数可以表示为：( )( ), ()( ,)iiii SViiii SVfxyxxby k x xb 16其中其中i通过求解如下的优化问题得到：通过求解如下的优化问题得到：1,11,11max( )(), ()21( ,)2lliijijijii jlliijijijii jWy yxxy y k x x. .s t10liiiy 利用核函数将非线性问题转化为线性问题利用核函数将非线性问题转化为线性问题的手段和方法称之为的手段和方法称之为核函数方法核函数方法。17 例：例：XOR问题中我们构造了一个非线性映问题中我们构造了一个非线性映射实

9、现了特征的升维：射实现了特征的升维：122212312( )( ),( ),( )(,2)xxxxxxx x( )12(,)( )xxxx 样本点在新的特征空间中的内积为：样本点在新的特征空间中的内积为：l核函数核函数描述了样本点在经过某种特征变换后，描述了样本点在经过某种特征变换后，在新的特征空间中的内积。在新的特征空间中的内积。( , )k x y2(,)x y 112233( ),( )( )( )( )( )( )( )xyxyxyxy 181,11max( )(,)2lliijijijii jWy y k x x . .s t0i10liiiy优化问题：优化问题：判别函数：判别函数：

10、线性支持向量机线性支持向量机非线性支持向量机非线性支持向量机 利用支持向量机求解异或利用支持向量机求解异或问题的结果示意图问题的结果示意图核函数核函数*( )sgn( , )iiif xy k x xb支持向量193.1 3.1 核函数的定义核函数的定义定义定义 核函数是一个对称函数，对所有的核函数是一个对称函数，对所有的 满足：满足：特征空间中的内积运算的充分必要条件是，对于任意特征空间中的内积运算的充分必要条件是，对于任意的的，它是某个，它是某个这里这里是从是从X到内积特征空间到内积特征空间F 的映射。的映射。, x yX( )( , )( ), ( )k x yxyMercerMerce

11、r定理定理 对于任意的对称函数对于任意的对称函数且且有有( ,)K x x( )0 x2( )x dx ( ,) ( ) ( )0K x xxx dxdx 3 3 核函数方法核函数方法20推论推论 令令X是有限输入空间，是有限输入空间，K(x , z)是是X上的对称函数。上的对称函数。那么那么K(x , z)是核函数的充要条件是矩阵：是核函数的充要条件是矩阵：是半正定的。是半正定的。常用的核函数：常用的核函数：多项式核函数多项式核函数高斯核函数高斯核函数sigmoid核函数核函数,1( ,)niji jKK x x( ,)(1)dijijk x xx x22( ,)exp(/ 2)ijijk

12、x xxx( ,)tanh(,)ijik x xkx x 213.2 核函数的构造核函数的构造令令K1和和K2是是X*X上的核，上的核，f()是是X上的一个实值函数。上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数：是一个对称半正定矩阵。那么下面的函数是核函数：从核函数中构造从核函数中构造从特征中构造从特征中构造从相似性度量中构从相似性度量中构造造12( , )( , )( , )k x zK x zKx z1( , )( , )k x zK x z12( , )( , )( , )k x zK x zKx z( , )( )( )k x zf xf z( , )Tk x zx

13、 Bz223.3 核函数的可分性核函数的可分性定理定理2：样本点：样本点D在核函数在核函数k(x,y)导出的特征映射下线性导出的特征映射下线性可分的充要条件是，下列方程组可分的充要条件是，下列方程组不存在不存在非负解：非负解：1(1,1,1)THX 其中，其中，111,( ,)1ijijijijijn nHhhk x xy yy y 233.3 核函数的可分性核函数的可分性其中，其中，000,( ,)ijijijijijn nHhhk x xy yy y 推论推论1：当：当 时，样本点线性可分。时，样本点线性可分。01()()rank Hrank H推论推论2： 对任意给定的训练样本，如果选用

14、对任意给定的训练样本，如果选用RBF核函核函数数 ，则当宽度参数，则当宽度参数 充分小时，充分小时， 训练样本总是线性训练样本总是线性可分的。可分的。243.4 如何选择核函数如何选择核函数问题问题1： 何谓一个好的核函数？何谓一个好的核函数？好的核函数能够真实反映样本间的远近关系。好的核函数能够真实反映样本间的远近关系。问题问题2： 如何判断核函数是否真实的反映的样本间的如何判断核函数是否真实的反映的样本间的远近关系？远近关系？比较难！但是初步判断核函数是否真实反映了训比较难！但是初步判断核函数是否真实反映了训练样本之间的远近关系还是可能的。练样本之间的远近关系还是可能的。核函数的选择策略核

15、函数的选择策略： 选择能够真实反映训练样本远近选择能够真实反映训练样本远近关系的核函数。关系的核函数。25问题问题3：训练样本间的远近关系如何表达？训练样本间的远近关系如何表达？*1,0ijijijn nijyyKkkyy物理含义物理含义：两个属于同类的样本相似度为：两个属于同类的样本相似度为1，不同类的，不同类的样本相似度为样本相似度为0。问题问题4：核函数与训练样本间的远近关系的一致性评估核函数与训练样本间的远近关系的一致性评估利用利用矩阵的相似性度量矩阵的相似性度量：,( , ),A BS A BA AB B26 草案：通过求解下面的优化问题进行核函数参数的选择：*),(maxKKS问题

16、：如果K K()如下所示： 1111它是一个糟糕的Gram矩阵。因为它把所有的训练样本均看作是同一类样本 。而它会使目标函数取到比较大的值！例例1：核函数的选择核函数的选择27 最终方案：通过求解下面的优化问题进行核函数的选择：) ),(maxKKS其中，jijijiyyyyk11,nnijk)(K=物理意义：一个好的核函数能够使同类的样本更加接近，而使不同类的样本更加疏远。 例例1：核函数的选择核函数的选择28实验结果：采用RBF核函数，随着半径参数的变化， Thyroid数据分类正确率与相似度之间的关系 。00.511.522.533.50.20.30.40.50.60.70.80.91C

17、orrect RateSimilarity Measure例例1：用于用于RBF核函数半径参数的选择核函数半径参数的选择2912345600.10.20.30.40.50.60.70.80.91Correct RateSimilarityMeasure 实验结果： 采用不同的核函数，Tyroid疾病诊断数据的分类正确率与相似度之间的关系 1 ：线性核函数；2,3：RBF核函数，半径参数分别为2、1；4,5：eRBF核函数，半径参数分别为2、16： Sigmoid核函数例例1：用于核函类型的选择用于核函类型的选择303.4 关于核函数方法的评述关于核函数方法的评述l 功能：采用核映射技术，将非线

18、性问题转化为一个线性问题的非线性数据处理方法。核的使用使得将数据隐式表达为特征空间并越过本来需要的特征映射的计算成为可能。l适用条件：如果某个线性问题的求解过程只与样本间的点积相关，则可以采用核函数方法将该线性问题的求解过程推广到非线性问题。lKernel trick：将所有的计算转变为向量间的点积运算。313.5 核函数方法的应用示例：核函数方法的应用示例：PCAKPCAPCA的作用：发现数据的作用：发现数据分布的主要方向分布的主要方向 特征降维特征降维 数据压缩数据压缩 去除噪声去除噪声PCA的常用功能：的常用功能：一个一个PCA的例子的例子PCA的局限性：的局限性： 只能得到样本分布的线

19、性主方向只能得到样本分布的线性主方向32TCX XPCA求解步骤求解步骤Step 1：样本中心化，使得样本中心化，使得( )12( ,)( )xx xx Step 2：求解中心化后的样本的协方差矩阵：求解中心化后的样本的协方差矩阵Step 3：求解协方差矩阵的特征值和特征向量，：求解协方差矩阵的特征值和特征向量，其中最大特征值对应的特征向量即为主方向。其中最大特征值对应的特征向量即为主方向。(1, )iiivC vin1对应的特征向量对应的特征向量1v为主方向为主方向33()()TCXXKPCA：基于核函数的非线性主成分分析：基于核函数的非线性主成分分析Step 1：样本中心化，使得：样本中心

20、化，使得0iStep 2：求解中心化后的样本的协方差矩阵：求解中心化后的样本的协方差矩阵Step 3：求解协方差矩阵的特征值和特征向量：求解协方差矩阵的特征值和特征向量1( )niiivx 不妨设所求的特征向量为：不妨设所求的特征向量为：则根据特征向量的定义，有：则根据特征向量的定义，有：(),(),kkxvxCv341111(), ( )(),()(), ( ) )nnnikiikjjiiijxxxxxxn 根据核函数的定义，有：根据核函数的定义，有：展开后，得到：展开后，得到：2n KK 其中其中K K为核函数对应的的为核函数对应的的GramGram矩阵。考虑到其矩阵。考虑到其逆存在，故：

21、逆存在，故：nK解该方程得到解该方程得到即可得到特征空间中的主分量即可得到特征空间中的主分量1, ( )( ,)niiiVxk x x样本在主方向的投影可表示为：样本在主方向的投影可表示为：35-1.5-1-0.500.511.5-1.5-1-0.500.511.5利用利用PCAPCA得到的主分量重建结果得到的主分量重建结果利用利用KPCAKPCA得到的主分量重建结果得到的主分量重建结果-1-0.500.51-1.5-1-0.500.511.536KPCAKPCA与其它方法的对比与其它方法的对比37Patterns7291 train2007 testSize: 16 x 16Linear P

22、CAKernel PCA38lKernel Fisher Discriminant AnalysislKernel K-Means ClusteringlKernel Independent Component Analysisl3.6 核函数核函数方法在其它方面的应用39lParameters selection for Multi-KernellConstructing Special Kernel for Special ApplicationslData Driven Kernel Construction3.7 核函数核函数方面的研究40问题：问题：1.1.如果已知特征映射如果已知特

23、征映射( )xx则该特征映射则该特征映射对应的核函数是？对应的核函数是？2.2.给定两类样本：给定两类样本：(0,0),(1,1);(1,0),(0,1)(0,0),(1,1);(1,0),(0,1) 求在核函数求在核函数2( , ),k x yx y导出的特征空间中两类导出的特征空间中两类样本中心间的距离。样本中心间的距离。41SVM & Statistic Learning Theory支持向量机与统计学习理支持向量机与统计学习理论论41补补 充充42421.1.统计学习理论对分类问题的描述统计学习理论对分类问题的描述定义定义期望风险期望风险( , )F x y：输入输出样本对的联合分布：

24、输入输出样本对的联合分布( )( ,( , )( , )R wL y f x w dF x y学习目标：从一组函数集学习目标：从一组函数集 中求一个最优中求一个最优的函数的函数 ，使得期望风险最小，即：，使得期望风险最小，即：0 ( ,)f x w ( , )f x w0( ,)( ,( ,)1( ,)if yf x wL y f x wif yf x w其中：其中：0()inf()wR wR w43问题：问题：期望风险如何计算？期望风险如何计算？11( , )(,( , )lempiiiRw lL yf x wl令则( )lim( , )PemplR wRw linf( ) inf lim(

25、 , )PempwwlR wRw l11lim(,(,)lPiiliL yf x wl？( )( ,( , )( , )R wL y f x w dF x yERMERM原则一致性原则一致性44经验风险小不等于实际风险小的例子经验风险小不等于实际风险小的例子采用采用sin(w)函数集中的函数进行逼近函数集中的函数进行逼近4445统计学习理论的三个里程碑定理：统计学习理论的三个里程碑定理：1.遵循ERM原则的学习机满足什么条件就能使经验风险收敛到最小时实际风险也收敛到最小2. 遵循ERM原则的学习机满足什么条件就能快速收敛3. 遵循ERM原则的学习机满足什么条件就能快速收敛而且与要求解的问题无关

26、46OCCAM剃刀原则：剃刀原则： 对于一种现象，能够用简单模型解释的，对于一种现象，能够用简单模型解释的，绝不用更复杂的模型解释。绝不用更复杂的模型解释。优化目标优化目标：f(x,w)的复杂度尽可能小的复杂度尽可能小约束条件约束条件：4611( , )(,( ,)lempiiiRw lL yf x wlOCCAM剃刀原则剃刀原则结构复杂度最小化原则结构复杂度最小化原则如无必要，勿增实体如无必要，勿增实体47统计学习中对结构复杂度的定义：统计学习中对结构复杂度的定义：VC维维。 VC维维：如果存在：如果存在h个样本能够被函数集中的函个样本能够被函数集中的函数按所有可能的数按所有可能的 2h 种

27、形式分开，则称函数集种形式分开，则称函数集能够把能够把h个样本打散；函数集的个样本打散；函数集的VC维就是它维就是它能打散的最大样本数目能打散的最大样本数目h.问题：问题：如何评估函数集的结构复杂度？如何评估函数集的结构复杂度？48例：求解例：求解2维空间中超平面的维空间中超平面的VC维维解：解：a. 2维空间中超平面的维空间中超平面的VC维维3b. 2维空间中超平面的维空间中超平面的VC维维448引理：若两个样本点位于某线性引理：若两个样本点位于某线性分类平面的同侧，则连接这两个分类平面的同侧，则连接这两个点的线段上的所有点也在该线性点的线段上的所有点也在该线性分类面的同侧。分类面的同侧。4

28、9关于关于VC维的补充说明：维的补充说明：l VC维是从函数分类能力的角度，定量地描述维是从函数分类能力的角度，定量地描述了函数集的结构复杂性。函数集的了函数集的结构复杂性。函数集的VC维越大，维越大，表明函数集的结构越复杂表明函数集的结构越复杂l n维超平面的维超平面的VC维为维为n1，sin()函数集的函数集的VC维为无穷大维为无穷大l VC是是Vapnik和和Chervinenkis名字的首字母名字的首字母 49l 一般来说，给定函数集，计算该函数集的一般来说，给定函数集，计算该函数集的VC维是相当困难的维是相当困难的5050定理定理1 1：对于指示集中的所有函数，经验风险对于指示集中的所