基于核函数的学习算法.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,引言,近几年，出现了一些基于核函数的机器学习方法，例如：,SVM,（可支持向量机）、,KFD,（基于核的,Fisher,判别分析）、,KPCA,（核主成分分析）等。这些方法在分类问题、回归问题以及无监督学习上都具有现实意义。这些核函数方法已经成功应用到模式识别的各个领域，比如目标识别、文本分类、时间序列预测等等,理论基础,监督学习,:SVM,、,KFD,无监督学习：,KPCA,模型选择,理论基础,机器学习,VC,维,结构风险最小化原则,SLT(,Statistical Learning Theory,),上世纪,90,年代中才成熟的统计学习理论，是在基于经验风险的有关研究基础上发展起来的，专门针对小样本的统计理论。,统计学习理论为研究有限样本情况下的模式识别、函数拟合和概率密度估计等三种类型的机器学习问题提供了理论框架，同时也为模式识别发展了一种新的分类方法,支持向量机。,机器学习,机器学习是现代智能技术中重要的一个方面，研究从观测样本出发去分析对象，去预测未来。,机器学习的基本模型：,输出,y,与,x,之间存在一种固定的、但形式未知的联合概率分布函数,F,(,y,x,),。,学习机中有函数集,f,(,x,w,),，可估计输入与输出之间依赖关系，其中,w,为广义参数。,风险最小化机器学习问题表示,已知变量,y,与输入,x,之间存在一定的未知依赖关系，即联合概率分布,F(x,y),机器学习就是根据独立同分布的,n,个观测样本：,(x,1,y,1,),(x,2,y,2,),(x,n,y,n,),在一组函数,f(x,w),中求一个最优函数,f(x,w,0,),，使预测的期望风险,R(w),最小化。,L(y,f(x,w),为损失函数，由于对,y,进行预测而造成的损失；,w,为函数的广义参数，故,f(x,w),可表示任何函数集；,F(x,y),为联合分布函数。,VC,维,Vanik,和,Chervonenkis(1968),提出了,VC,维,的概念。,VC,维：对于一个指示函数（即只有,0,和,1,两种取值的函数）集，如果存在,h,个样本能够被函数集里的函数按照所有可能的,2,h,种形式分开，则称函数集能够把,h,个样本打散，函数集的,VC,维就是能够打散的最大样本数目。,VC,维是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论。,监督学习:SVM、KFD,（3）,测试样本在这个向量上的投影系数就是所提取的测试样本的特征值。,(x1,y1),(x2,y2),(xn,yn),W*就是J(w)中的极值解,也就是矩阵S-1 Sb的最大特征值对应的特征向量。,式(1)中的和b 乘以系数后仍能满足方程，进行归一化处理之后，对于所有样本xi，式|xi+b|的最小值为1,则样本与此最优超平面的最小距离为|xi+b|/=1/,那么最优超平面应满足条件:,相应的分类判决函数转变为:,在第 i次(i=1,k)训练时,要用除了第 i 个子集的所有子集训练模型,再用得到的模型对第 i个子集计算误差.,对于分类问题，支持向量机方法根据区域中的样本计算该区域的分类曲面，由该曲面决定该区域中的样本类别。,可以证明，在此寻优问题的解中有一部分ai不为0，它们所对应的训练样本完全确定了这个超平面，因此称其为支持向量(support vector)。,(x1,y1),(x2,y2),(xn,yn),由此,式(5)的对偶形式可变为：,典型的例子就是KPCA（核主成分分析）。,VC维是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论。,i0，i=1，n.,该线性分类函数的,VC,维即为,3,一般而言,VC,维越大,学习能力就越强,但学习机器也越复杂。,目前还没有通用的关于计算任意函数集的,VC,维的理论,只有对一些特殊函数集的,VC,维可以准确知道。,结构风险最小化准则,Vapnik,和,Chervonenkis(1974),提出了,SRM,。,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。,统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照,VC,维的大小排列,;,在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化准则,(,Structural Risk Minimization Principle),。,核函数,在处理线性分类问题时，数据以点积的形式,(x,i,x,j,),出现。而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：,当在特征空间,H,中构造最优超平面时，训练算法仅使用空间中的点积，即,存在一种核函数,K,使得,:,核函数将,m,维高维空间的内积运算转化为,n,维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题。,核方法分为核函数设计和算法设计两个部分,具体情况如图1所示。核方法的实施步骤,具体描述为:收集和整理样本,并进行标准化;选择或构造核函数;用核函数将样本变换成为核矩阵;在特征空间对核矩阵实施各种线性算法;得到输入空间中的非线性模型。,核函数,主要的核函数有三类：,多项式核函数,径向基函数,S,形函数,有监督学习,(supervisedlearning),监督学习，就是人们常说的分类，通过已有的训练样本（即已知数据以及其对应的输出）去训练得到一个最优模型（这个模型属于某个函数的集合，再利用这个模型将所有的输入映射为相应的输出，对输出进行简单的判断从而实现分类的目的，也就具有了对未知数据进行分类的能力。,典型的例子就是,SVM,（可支持向量机）、,KFD,（基于核的,Fisher,判别分析）。,SVM,（,Support vector machines),SVM,是基于,SLT,的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。,SVM,是建立在统计学习理论的,VC,维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广（泛化）能力。,支持向量机方法建立在统计学习理论基础之上，专门针对小样本情况下的机器学习问题。对于分类问题，支持向量机方法根据区域中的样本计算该区域的分类曲面，由该曲面决定该区域中的样本类别。,已知样本,x,为,m,维向量,在某个区域内存在,n,个样本,:,(x1,y1),，,(x2,y2),，,，,(xn,yn),其中，,xi,是训练元组，,xiRm,，,yi,是类标号，,yi1,-1,。,若存在超平面,(hyperplane):,x+b=0 (1),其中,表示向量的点积，如图,1,所示，超平面能将这,n,个样本分为两类,那么存在最优超平面不仅能将两类样本准确分开，而且能使两类样本到超平面的距离最大。式,(1),中的,和,b,乘以系数后仍能满足方程，进行归一化处理之后，对于所有样本,x,i,，式,|x,i,+b|,的最小值为,1,则样本与此最优超平面的最小距离为,|x,i,+b|/=1/,那么最优超平面应满足条件,:,y,i,（,x,i,+b,）,1,，,i=1,，,，,n.(2),根据最优超平面的定义可知,:,和,b,的优化条件是使两类样本到超平面最小距离之和,2/,最大。此外，考虑到可能存在一些样本不能被超平面正确分类,因此引入松弛变量,(slack variable),：,i0,，,i=1,，,，,n.,（,3,）,这样上述二元分类问题转换为在式,(2),和式,(3),的约束下最小化：,（,4,）,其中,非负常数,C,为惩罚因子，,C,值越大表示对错误分类的惩罚越大。这是一个具有线性约束的二次规划问题，利用拉格朗日乘子法可以将式,(4),转化为其对偶形式,:,(5),约束条件,:,(6),其中,a,i,为原问题中与约束条件式,(2),对应的拉格朗日乘子。这是一个不等式约束下的二次函数寻优问题，存在高效的算法求解。可以证明，在此寻优问题的解中有一部分,ai,不为,0,，它们所对应的训练样本完全确定了这个超平面，因此称其为支持向量,(support vector),。,对于类型未知的样本,x,可以采用线性判决函数,:,来判断其所属类别,综合式,(9),，可得分类判决函数,:,根据核函数的相关知识，可以使用核函数,K(x,i,x,j,),替代线性分类问题中的点积形式，从而实现非线性变换后的线性分类。由此,式,(5),的对偶形式可变为：,约束条件：,相应的分类判决函数转变为,:,Kernel Fisher discriminant analysis,（基于核的,Fisher,判别方法）,是由,Mika,等人于,1999,年提出的方法。,核,Fisher,判别分析是一种很有用的机器学习方法，将一个非线性问题通过非线性变换转化为,另一个空间中的线性问题进行求解,.,它不依赖于,模型，也不存在维数灾难。,线性Fisher判别分析,对于两类问题,设待分类的样本有,n,个,:x,1,x,2,x,n,Rd,。在进行,Fisher,判别分析时,目标是找到线性投影方向,(,投影轴,),使得训练样本在这些轴上的投影结果类内散度最小,类间散度最大。设样本类内均值为,m,i,则,设样本类间离散度矩阵为,S,则,设样本类间离散度矩阵为,S,b,则,最佳投影方向是通过最大化目标函数,J(w),W,为投影方向。,考虑到,J(w),的尺度不变性,令分母为非零常数,用,Lagrange,乘子法求解得到下面的特征值：,W*,就是,J(w),中的极值解,也就是矩阵,S,-1,S,b,的最大特征值对应的特征向量。测试样本在这个向量上的投影系数就是所提取的测试样本的特征值。,则,FDA,的判别函数为,b,为偏移量,可以通过求解以下方程得到,则对于一待测样本,x,i,求,Fisher,判别分析判别函数,f(x,i,)=w*x,i,+b,通过,f(x,i,),正负确定其归属。,基于核的Fisher判别分析,KFDA,算法的思想是,:,引入核方法，通过一个非线性映射,将输入数据映射到一个高维的线性可分的特征空间中,然后在这个特征空间中进行线性,Fisher,判别分析,从而实现相对于输入空间的非线性判别分析。,在进行,KFDA,时,首先通过非线性映射,将输入数据映射到一个高维特征空间中,即,这时,输入训练样本由原来的,x,变为,(x),然后在这个特征空间,F,中进行线性,FDA,。问题转变为在,F,中最大化目标函数,J,F,(w),式中,F,是,F,中相应的矩阵,分别为,由于,F,空间的维数通常很高甚至是无穷维,因,J,F,(w),式直接求解很困难。借用非线性支持向量机的核方法,引入以下内积核函数,来隐含地进行运算，,定义核矩阵,K,为,式中,(K,i,),pj,=k(x,p,x,ij,),p=1,2,n,是,n n,i,矩阵,(i=1,2),是全体样本分别与类,1,、类,2,的内积核矩阵。,由再生核理论可知,F,空间的任何解,w,都是,F,空间中的训练样 本的线性组合,即,:,是第,i,类各个样本与总体的内积核的均值。,由上述三式可得,模型，也不存在维数灾难。,基于核的Fisher判别分析,在第 i次(i=1,k)训练时,要用除了第 i 个子集的所有子集训练模型,再用得到的模型对第 i个子集计算误差.,式中,F,是F中相应的矩阵,分别为,机器学习是现代智能技术中重要的一个方面，研究从观测样本出发去分析对象，去预测未来。,KFDA算法的思想是:引入核方法，通过一个非线性映射,将输入数据映射到一个高维的线性可分的特征空间中,然后在这个特征空间中进行线性Fisher判别分析,从而实现相对于输入空间的非线性判别分析。,式中,(Ki)pj=k(xp,xij),p=1,2,n,是n ni 矩阵(i=1,2),是全体样本分别与类1、类2的内积核矩阵。,此外，考虑到可能存在一些样本不能被超平面正确分类,因此引入松弛变量(slack variable)：,设样本类内均值为mi,则,（4）,核Fisher判别分析与支持向量机分类精度相差不大;但由于SVM需要求解二次优化问题,因此在训练样本较多的情况下需要的训练时间较长,而KFDA只计算矩阵的特征向量,计算量小，在消耗时间上具有明显的优势。,而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：,则对于一待测样本xi,求Fisher判别分析判别函数,F(x,y)为联合分布函数。,W为投影方向。,在,F,空间中,求解,Fisher,线性判别函数,:,该判别函数隐式地对应原空间的一个非线性判别函数,因此,它是一种非线性方法。求解矩阵,N,-1,M,的最大特征值对应的特征向量就可求得上式的最优解。,测试数据在特征向量,w,上的投影为：,在实际应用中为了防止,N,非正定,使解更稳定,通常引入一个正 则化参数,令,N=N+I,I,是单位矩阵。则判别函数可以写为,:,b,可以通过求解具有,L1,软边界的一维线性支持向量机,(SVM),来确定。,SVM和KFD的比较,核Fisher判别分析与支持向量机分类精度相差不大;但由于SVM需要求解二次优化问题,因此在训练样本较多的情况下需要的训练时间较长,而KFDA只计算矩阵的特征向量,计算量小，在消耗时间上具有明显的优势。,与SVM分类相似,KFDA的分类性能受核函数及参数影响很大,核函数参数在特定的范围内才能得到良好的分类精度。,无监督学习,(unsupervisedlearning),无监督学习是我们事先没有任何训练样本，而需要直接对数据进行建模。,典型的例子就是,KPCA,（核主成分分析）。,而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：,W为投影方向。,其原理是将训练样本分成容量相同的 k 个子集,并对模型训练 k次.,该判别函数隐式地对应原空间的一个非线性判别函数,因此,它是一种非线性方法。,在第 i次(i=1,k)训练时,要用除了第 i 个子集的所有子集训练模型,再用得到的模型对第 i个子集计算误差.,在第 i次(i=1,k)训练时,要用除了第 i 个子集的所有子集训练模型,再用得到的模型对第 i个子集计算误差.,测试数据在特征向量w 上的投影为：,由于F空间的维数通常很高甚至是无穷维,因JF(w)式直接求解很困难。,KFDA算法的思想是:引入核方法，通过一个非线性映射,将输入数据映射到一个高维的线性可分的特征空间中,然后在这个特征空间中进行线性Fisher判别分析,从而实现相对于输入空间的非线性判别分析。,f(xi)=w*xi+b,通过f(xi)正负确定其归属。,支持向量机方法建立在统计学习理论基础之上，专门针对小样本情况下的机器学习问题。,式中,F,是F中相应的矩阵,分别为,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。,式中,F,是F中相应的矩阵,分别为,机器学习是现代智能技术中重要的一个方面，研究从观测样本出发去分析对象，去预测未来。,Kernel Principal Component Analysis,KPCA,方法借鉴,SVM,的核方法思想,将线性的,PCA,扩展到非线性情形。,其思想可描述为,:,通过一个非线性函数，将输入空间映射到更高维的特征空间中,然后在此高维空间中使用,PCA,方法提取数据特征。由图,1,可以看出,非线性可分的输入空间通过函数映射到特征空间后,变成了一个线性可分的问题。,Principal Component Analysis,主成分分析(Principal Component Analysis,简称PCA)是一种常用的基于变量协方差矩阵对信息进行处理、压缩和抽提的有效方法。,模型选择,核函数方法中模型选择十分重要,模型选择包括核函数的选择、构造以及参数调整,;,就,SVMs,而言,还包括容量控制参数,(,正则化参数,),、损失函数的确定等。,多数应用研究都采用高斯核函数,然后再确定其他参数,.,对于高斯核函数方法,要选择的参数就是核的宽度,和正则化参数等,目前常用方法有：,交叉检验法：,该方法是十分常用的模型验证方法,.,其原理是将训练样本分成容量相同的,k,个子集,并对模型训练,k,次,.,在第,i,次,(i=1,k),训练时,要用除了第,i,个子集的所有子集训练模型,再用得到的模型对第,i,个子集计算误差,.,以,k,次误差的平均数值作为模型推广能力的近似数值,.,