基于核函数的学习算法

引言

近几年，出现了一些基于核函数的机器学习方法，例如：SVM（可支持向量机）、KFD（基于核的Fisher判别分析）、KPCA（核主成分分析）等。这些方法在分类问题、回归问题以及无监督学习上都具有现实意义。这些核函数方法已经成功应用到模式识别的各个领域，比如目标识别、文本分类、时间序列预测等等理论基础监督学习:SVM、KFD无监督学习：KPCA模型选择理论基础机器学习VC维结构风险最小化原则SLT(StatisticalLearningTheory)上世纪90年代中才成熟的统计学习理论，是在基于经验风险的有关研究基础上发展起来的，专门针对小样本的统计理论。统计学习理论为研究有限样本情况下的模式识别、函数拟合和概率密度估计等三种类型的机器学习问题提供了理论框架，同时也为模式识别发展了一种新的分类方法——支持向量机。机器学习机器学习是现代智能技术中重要的一个方面，研究从观测样本出发去分析对象，去预测未来。机器学习的基本模型：输出y与x之间存在一种固定的、但形式未知的联合概率分布函数F(y,x)。学习机中有函数集{f(x,w)}，可估计输入与输出之间依赖关系，其中w为广义参数。风险最小化－机器学习问题表示

已知变量y与输入x之间存在一定的未知依赖关系，即联合概率分布F(x,y)机器学习就是根据独立同分布的n个观测样本：

(x1,y1),(x2,y2),···,(xn,yn)

在一组函数{f(x,w)}中求一个最优函数f(x,w0)，使预测的期望风险R(w)最小化。

L(y,{f(x,w)})为损失函数，由于对y进行预测而造成的损失；w为函数的广义参数，故{f(x,w)}可表示任何函数集；F(x,y)为联合分布函数。VC维Vanik和Chervonenkis(1968)提出了VC维的概念。VC维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把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，它们所对应的训练样本完全确定了这个超平面，因此称其为支持向量(supportvector)。(x1,y1),(x2,y2),···,(xn,yn)由此,式(5)的对偶形式可变为：典型的例子就是KPCA（核主成分分析）。VC维是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标,在此概念基础上发展出了一系列关于统计学习的一致性、收敛速度、泛化性能等的重要结论。ζi≥0，i=1，…，n.该线性分类函数的VC维即为3一般而言,VC维越大,学习能力就越强,但学习机器也越复杂。目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。结构风险最小化准则Vapnik和Chervonenkis(1974)提出了SRM。传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化准则(StructuralRiskMinimizationPrinciple)。核函数在处理线性分类问题时，数据以点积的形式(xi·xj)出现。而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：当在特征空间H中构造最优超平面时，训练算法仅使用空间中的点积，即存在一种核函数K,使得:核函数将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题。核方法分为核函数设计和算法设计两个部分,具体情况如图1所示。核方法的实施步骤,具体描述为:①收集和整理样本,并进行标准化;②选择或构造核函数;③用核函数将样本变换成为核矩阵;④在特征空间对核矩阵实施各种线性算法;⑤得到输入空间中的非线性模型。核函数主要的核函数有三类：多项式核函数径向基函数S形函数有监督学习(supervised

learning)监督学习，就是人们常说的分类，通过已有的训练样本（即已知数据以及其对应的输出）去训练得到一个最优模型（这个模型属于某个函数的集合，再利用这个模型将所有的输入映射为相应的输出，对输出进行简单的判断从而实现分类的目的，也就具有了对未知数据进行分类的能力。典型的例子就是SVM（可支持向量机）、KFD（基于核的Fisher判别分析）。SVM（Supportvectormachines)SVM是基于SLT的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广（泛化）能力。支持向量机方法建立在统计学习理论基础之上，专门针对小样本情况下的机器学习问题。对于分类问题，支持向量机方法根据区域中的样本计算该区域的分类曲面，由该曲面决定该区域中的样本类别。已知样本x为m维向量,在某个区域内存在n个样本:(x1,y1)，(x2,y2)，…，(xn,yn)其中，xi是训练元组，xi∈Rm，yi是类标号，yi∈{1,-1}。若存在超平面(hyperplane):ω·x+b=0(1)其中·表示向量的点积，如图1所示，超平面能将这n个样本分为两类,那么存在最优超平面不仅能将两类样本准确分开，而且能使两类样本到超平面的距离最大。式(1)中的ω和b乘以系数后仍能满足方程，进行归一化处理之后，对于所有样本xi，式|ω·xi+b|的最小值为1,则样本与此最优超平面的最小距离为|ω·xi+b|/‖ω‖=1/‖ω‖,那么最优超平面应满足条件:yi（ω·xi+b）≥1，i=1，…，n.(2)根据最优超平面的定义可知:ω和b的优化条件是使两类样本到超平面最小距离之和2/‖ω‖最大。此外，考虑到可能存在一些样本不能被超平面正确分类,因此引入松弛变量(slackvariable)：

ζi≥0，i=1，…，n.（3）这样上述二元分类问题转换为在式(2)和式(3)的约束下最小化：

（4）其中,非负常数C为惩罚因子，C值越大表示对错误分类的惩罚越大。这是一个具有线性约束的二次规划问题，利用拉格朗日乘子法可以将式(4)转化为其对偶形式:(5)约束条件:(6)其中ai为原问题中与约束条件式(2)对应的拉格朗日乘子。这是一个不等式约束下的二次函数寻优问题，存在高效的算法求解。可以证明，在此寻优问题的解中有一部分ai不为0，它们所对应的训练样本完全确定了这个超平面，因此称其为支持向量(supportvector)。对于类型未知的样本x,可以采用线性判决函数:来判断其所属类别,综合式(9)，可得分类判决函数:

根据核函数的相关知识，可以使用核函数K(xi·xj)替代线性分类问题中的点积形式，从而实现非线性变换后的线性分类。由此,式(5)的对偶形式可变为：

约束条件：

相应的分类判决函数转变为:KernelFisherdiscriminantanalysis（基于核的Fisher判别方法）

是由Mika等人于1999年提出的方法。核Fisher判别分析是一种很有用的机器学习方法，将一个非线性问题通过非线性变换转化为另一个空间中的线性问题进行求解.它不依赖于

模型，也不存在维数灾难。线性Fisher判别分析对于两类问题,设待分类的样本有n个:x1,x2,…,xn∈Rd。在进行Fisher判别分析时,目标是找到线性投影方向(投影轴),使得训练样本在这些轴上的投影结果类内散度最小,类间散度最大。设样本类内均值为mi,则设样本类间离散度矩阵为Sω,则设样本类间离散度矩阵为Sb,则最佳投影方向是通过最大化目标函数J(w)W为投影方向。考虑到J(w)的尺度不变性,令分母为非零常数,用Lagrange乘子法求解得到下面的特征值：W*就是J(w)中的极值解,也就是矩阵S-1ωSb的最大特征值对应的特征向量。测试样本在这个向量上的投影系数就是所提取的测试样本的特征值。则FDA的判别函数为b为偏移量,可以通过求解以下方程得到则对于一待测样本xi,求Fisher判别分析判别函数f(xi)=w*xi+b,通过f(xi)正负确定其归属。基于核的Fisher判别分析KFDA算法的思想是:引入核方法，通过一个非线性映射,将输入数据映射到一个高维的线性可分的特征空间中,然后在这个特征空间中进行线性Fisher判别分析,从而实现相对于输入空间的非线性判别分析。在进行KFDA时,首先通过非线性映射Ø将输入数据映射到一个高维特征空间中,即这时,输入训练样本由原来的x变为Ø(x),然后在这个特征空间F中进行线性FDA。问题转变为在F中最大化目标函数JF(w)式中,ω∈F,

是F中相应的矩阵,分别为由于F空间的维数通常很高甚至是无穷维,因JF(w)式直接求解很困难。借用非线性支持向量机的核方法,引入以下内积核函数来隐含地进行运算，,定义核矩阵K为式中,(Ki)pj=k(xp,xij),p=1,2,⋯,n,是n×ni

矩阵(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的内积核矩阵。此外，考虑到可能存在一些样本不能被超平面正确分类,因此引入松弛变量(slackvariable)：设样本类内均值为mi,则（4）核Fisher判别分析与支持向量机分类精度相差不大;但由于SVM需要求解二次优化问题,因此在训练样本较多的情况下需要的训练时间较长,而KFDA只计算矩阵的特征向量,计算量小，在消耗时间上具有明显的优势。而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：则对于一待测样本xi,求Fisher判别分析判别函数F(x,y)为联合分布函数。W为投影方向。在F空间中,求解Fisher线性判别函数:该判别函数隐式地对应原空间的一个非线性判别函数,因此,它是一种非线性方法。求解矩阵N-1M的最大特征值对应的特征向量就可求得上式的最优解。测试数据在特征向量wØ

上的投影为：在实际应用中为了防止N非正定,使解更稳定,通常引入一个正则化参数λ,令Nλ=N+λI,I是单位矩阵。则判别函数可以写为:b可以通过求解具有L1软边界的一维线性支持向量机(SVM)来确定。SVM和KFD的比较核Fisher判别分析与支持向量机分类精度相差不大;但由于SVM需要求解二次优化问题,因此在训练样本较多的情况下需要的训练时间较长,而KFDA只计算矩阵的特征向量,计算量小，在消耗时间上具有明显的优势。与SVM分类相似,KFDA的分类性能受核函数及参数影响很大,核函数参数在特定的范围内才能得到良好的分类精度。无监督学习(unsupervised

learning)

无监督学习是我们事先没有任何训练样本，而需要直接对数据进行建模。典型的例子就是KPCA（核主成分分析）。而在处理非线性分类问题时，需要采用非线性映射把输入空间映射到高维特征空间，记为：W为投影方向。其原理是将训练样本分成容量相同的k个子集,并对模型训练k次.该判别函数隐式地对应原空间的一个非线性判别函数,因此,它是一种非线性方法。在第i次(i=1,…k)训练时,要用除了第i个子集的所有子集训练模型,再用得到的模型对第i个子集计算误差.在第i次(i=1,…k)训练时,要用除了第i个子集的所有子集训练模型,再用得到的模型对第i个子集计算误差.测试数据在特征向量wØ上的投影为：由于F空间的维