svm支持向量机课件

1,前情提要,支持向量机的创新之一在于将分类面的求解看作是一个二次规划问题,支持向量机的创新之二在于揭示了对分类起关键作用的只是一部分训练样本，即支持向量,1.对线性支持向量机的小结,2,2.线性支持向量机的数学模型：,前情提要(续1),3,前情提要(续2),3.线性支持向量机的编程实现：,Matlab,C,svcoutput(trnx,trny,testx,linear,alpha,bias);,nsvalphabias=svc(trnx,trny,linear);,svm_model*svm_train(svm_problem*prob,svm_parameter*param),svm_predict(svm_model*model,svm_node*x),4,SVMForNonlinearProblems,求解非线性问题的SVM,4,第四讲,5,1.如何解决少量非线性可分样本？,5,内容提要,2.如何解决大量非线性可分样本？,3.核函数方法（KernelTrick）,4.SVM背后的统计学习理论,6,基本思想：通过训练误差和类间宽度之间的权衡，得到一个最优超平面。,1.线性SVM求解含少量非线性可分样本的思想,优化目标：,约束条件：,权衡因子,松弛变量,7,1类样本：位于分类间隔之外,7,类似的，通过Lagrange函数，转化为对偶问题,1类样本,2类样本,3类样本,2类样本：支持向量,3类样本：位于分类间隔之内,8,不同的权衡因子得到的不同的分类面,C10,C1000,9,2.非线性支持向量机,当线性支持向量机划分样本会产生过多训练误差时，需要考虑使用非线性分类面对两类样本进行划分。,10,2.1寻找非线性问题的三种思路,思路1:原空间法在原空间中直接求解非线性问题,11,例1：XOR问题,思路2:特征空间法将非线性问题的求解转换成另一个空间中的线性问题求解,12,例2：物种分类问题,13,寻找特征映射所面临的问题：,1.特征映射的确定往往需要相当高的技巧和相当专业的领域知识；,3.特征映射往往是一个低维向高维映射的过程，这个映射过程经常面临维数灾难。,2.特征映射的计算可能会相当复杂；,14,思路3.核函数方法,优化问题：,判别函数：,样本之间的内积,构建到特征空间的隐式映射,15,2.2线性SVM通过核函数扩展为非线性SVM,线性SVM:,假设经过某种非线性特征映射后原来的非线性可分问题可以通过线性SVM来解决，则在特征空间中的判别函数可以表示为：,16,其中,通过求解如下的优化问题得到：,利用核函数将非线性问题转化为线性问题的手段和方法称之为核函数方法。,17,例：XOR问题中我们构造了一个非线性映射实现了特征的升维：,样本点在新的特征空间中的内积为：,核函数描述了样本点在经过某种特征变换后，在新的特征空间中的内积。,18,优化问题：,判别函数：,线性支持向量机,非线性支持向量机,利用支持向量机求解异或问题的结果示意图,核函数,19,3.1核函数的定义,定义核函数是一个对称函数，对所有的,满足：,特征空间中的内积运算的充分必要条件是，对于任意的,，它是某个,3核函数方法,20,推论令X是有限输入空间，K(x,z)是X上的对称函数。那么K(x,z)是核函数的充要条件是矩阵：,是半正定的。,常用的核函数：,多项式核函数,高斯核函数,sigmoid核函数,21,3.2核函数的构造,令K1和K2是X*X上的核，f()是X上的一个实值函数。B是一个对称半正定矩阵。那么下面的函数是核函数：,从核函数中构造,从特征中构造,从相似性度量中构造,22,3.3核函数的可分性,定理2：样本点D在核函数k(x,y)导出的特征映射下线性可分的充要条件是，下列方程组不存在非负解：,其中，,23,3.3核函数的可分性,其中，,推论1：当时，样本点线性可分。,推论2：对任意给定的训练样本，如果选用RBF核函数，则当宽度参数充分小时，训练样本总是线性可分的。,24,3.4如何选择核函数,问题1：何谓一个好的核函数？,好的核函数能够真实反映样本间的远近关系。,问题2：如何判断核函数是否真实的反映的样本间的远近关系？,比较难！但是初步判断核函数是否真实反映了训练样本之间的远近关系还是可能的。,核函数的选择策略：选择能够真实反映训练样本远近关系的核函数。,25,问题3：训练样本间的远近关系如何表达？,物理含义：两个属于同类的样本相似度为1，不同类的样本相似度为0。,问题4：核函数与训练样本间的远近关系的一致性评估,利用矩阵的相似性度量：,草案：通过求解下面的优化问题进行核函数参数的选择：,问题：如果K()如下所示：,它是一个糟糕的Gram矩阵。因为它把所有的训练样本均看作是同一类样本。而它会使目标函数取到比较大的值！,例1：核函数的选择,最终方案：通过求解下面的优化问题进行核函数的选择：,其中，,K=,物理意义：一个好的核函数能够使同类的样本更加接近，而使不同类的样本更加疏远。,例1：核函数的选择,实验结果：,采用RBF核函数，随着半径参数的变化，Thyroid数据分类正确率与相似度之间的关系。,例1：用于RBF核函数半径参数的选择,实验结果：采用不同的核函数，Tyroid疾病诊断数据的分类正确率与相似度之间的关系,1：线性核函数；2,3：RBF核函数，半径参数分别为2、1；4,5：eRBF核函数，半径参数分别为2、16：Sigmoid核函数,例1：用于核函类型的选择,30,3.4关于核函数方法的评述,功能：采用核映射技术，将非线性问题转化为一个线性问题的非线性数据处理方法。核的使用使得将数据隐式表达为特征空间并越过本来需要的特征映射的计算成为可能。,适用条件：如果某个线性问题的求解过程只与样本间的点积相关，则可以采用核函数方法将该线性问题的求解过程推广到非线性问题。,Kerneltrick：将所有的计算转变为向量间的点积运算。,31,3.5核函数方法的应用示例：PCA,KPCA,PCA的作用：发现数据分布的主要方向,特征降维数据压缩去除噪声,PCA的常用功能：,一个PCA的例子,PCA的局限性：只能得到样本分布的线性主方向,32,PCA求解步骤,Step1：样本中心化，使得,Step2：求解中心化后的样本的协方差矩阵,Step3：求解协方差矩阵的特征值和特征向量，其中最大特征值对应的特征向量即为主方向。,对应的特征向量,为主方向,33,KPCA：基于核函数的非线性主成分分析,Step1：样本中心化，使得,Step2：求解中心化后的样本的协方差矩阵,Step3：求解协方差矩阵的特征值和特征向量,不妨设所求的特征向量为：,则根据特征向量的定义，有：,34,根据核函数的定义，有：,展开后，得到：,其中K为核函数对应的的Gram矩阵。考虑到其逆存在，故：,解该方程得到,即可得到特征空间中的主分量,样本在主方向的投影可表示为：,35,利用PCA得到的主分量重建结果,利用KPCA得到的主分量重建结果,36,KPCA与其它方法的对比,37,KPCA的去噪功能（USPS）,Patterns7291train2007testSize:16x16,LinearPCA,KernelPCA,38,KernelFisherDiscriminantAnalysisKernelK-MeansClusteringKernelIndependentComponentAnalysis,3.6核函数方法在其它方面的应用,39,ParametersselectionforMulti-KernelConstructingSpecialKernelforSpecialApplicationsDataDrivenKernelConstruction,3.7核函数方面的研究,40,问题：,41,SVM&StatisticLearningTheory,支持向量机与统计学习理论,41,补充,42,42,1.统计学习理论对分类问题的描述,定义期望风险,：输入输出样本对的联合分布,学习目标：从一组函数集中求一个最优的函数，使得期望风险最小，即：,其中：,43,问题：期望风险如何计算？,？,ERM原则一致性,44,经验风险小不等于实际风险小的例子,采用sin(w)函数集中的函数进行逼近,44,45,统计学习理论的三个里程碑定理：,1.遵循ERM原则的学习机满足什么条件就能使经验风险收敛到最小时实际风险也收敛到最小,2.遵循ERM原则的学习机满足什么条件就能快速收敛,3.遵循ERM原则的学习机满足什么条件就能快速收敛而且与要求解的问题无关,46,OCCAM剃刀原则：,对于一种现象，能够用简单模型解释的，绝不用更复杂的模型解释。,优化目标：f(x,w)的复杂度尽可能小,约束条件：,46,OCCAM剃刀原则,结构复杂度最小化原则,如无必要，勿增实体,47,统计学习中对结构复杂度的定义：VC维。,VC维：如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开，则称函数集能够把h个样本打散；函数集的VC维就是它能打散的最大样本数目h.,问题：如何评估函数集的结构复杂度？,48,例：求解2维空间中超平面的VC维,解：a.2维空间中超平面的VC维3,b.2维空间中超平面的VC维4,48,引理：若两个样本点位于某线性分类平面的同侧，则连接这两个点的线段上的所有点也在该线性分类面的同侧。,49,关于VC维的补充说明：,VC维是从函数分类能力的角度，定量地描述了函数集的结构复杂性。函数集的VC维越大，表明函数集的结构越复杂,n维超平面的VC维为n1，sin()函数集的VC维为无穷大,VC是Vapnik和Chervinenkis名字的首字母,49,一般来说，给定函数集，计算该函数集的VC维是相当困难的,50,50,定理1：对于指示集中的所有函数，经验风险和实际风险至少以的概率满足：,为VC维为样本数,：结构风险,51,51,52,在维空间中，为覆盖样本向量的超球半径，则满足条件的分类超平面的VC维有下面的界：,定理2：,52,优化目标：,约束条件：,53,53,VC维与可证伪理论,问题：如何区分科学理论与非科学理论？,30年代，波普（K.Popper）提出了区分科学理论与非科学理论的准则：可证伪理论，即一种理论是科学的，其前提条件是：该理论存在着被证伪的可能性。,定义1：发现、积累