核函数的选择研究综述.pdf
- 文档编号:3435437
- 上传时间:2023-05-05
- 格式:PDF
- 页数:6
- 大小:2.45MB
核函数的选择研究综述.pdf
《核函数的选择研究综述.pdf》由会员分享,可在线阅读,更多相关《核函数的选择研究综述.pdf(6页珍藏版)》请在冰点文库上搜索。
年月第卷第期计算机工程与设计核函数的选择研究综述汪廷华,陈峻婷(赣南师范学院数学与计算机科学学院,江西赣州;赣南师范学院现代教育技术中心,江西赣州)摘要:
核方法是解决非线性模式分析问题的一种有效方法,是当前机器学习领域的一个研究热点。
核函数是影响核方法性能的关键因素,以支持向量机作为核函数的载体,从核函数的构造、核函数中参数的选择、多核学习个角度对核函数的选择的研究现状及其进展情况进行了系统地概述,并指出根据特定应用领域选择核函数、设计有效的核函数度量标准和拓宽核函数选择的研究范围是其中个值得进一步研究的方向。
关键词:
核函数;支持向量机;核方法;模型选择;多核学习中图法分类号:
文献标识号:
文章编号:
()收稿日期:
;修订日期:
基金项目:
江西省自然科学基金项目()作者简介:
汪廷华(),男,江西玉山人,博士,讲师,研究方向为数据挖掘与模式识别;陈峻婷(),女,福建安溪人,实验员,研究方向为智能信息处理。
:
,(,;,):
(),(),:
;();()引言支持向量机(,)由及其合作者在年的计算学习理论会议上介绍进机器学习领域,之后的十几年中受到了广泛的关注并得到了全面深入的发展,现已成为机器学习和数据挖掘领域的标准工具。
支持向量机是若干机器学习标准技术的集大成者,它集成了最大间隔超平面、核、凸二次优化、稀疏解和松弛变量等多项技术,主要用于模式分类和回归估计。
支持向量机是结构风险最小化(,)原则的具体体现,它根据有限的样本信息在机器的学习能力和复杂性之间寻求最佳折衷。
与传统的神经网络学习算法相比,支持向量机克服了局部极小和维数灾难等问题,泛化能力明显提高。
用于模式分类的支持向量机工作的原理是:
在非线性可分的情况下,使用一个非线性变换,把输入空间映射到一个高维特征空间,然后在特征空间中使用线性分类算法进行分类。
非线性变换通过所谓的核函数(,)隐式定义,它能在特征空间中高效地计算内积,即(,)()()。
通常()比()更为复杂,因此核函数的引入可以大大降低非线性变换的计算量。
通过核映射将原空间线性不可分的问题转化成某高维特征空间线性可分问题,而且不增加计算的复杂度,这就是所谓的核技巧。
可以这么说,在支持向量机所获得计算机工程与设计年的巨大成功中,核技巧扮演了非常重要的角色。
进一步地,通过把核函数引入到一些传统的学习算法,可以方便地把线性算法转换为非线性算法,例如:
核判别分析()、核主成分分析()、核独立成分分析()、核聚类分析、核等距映射()等等,这些算法和支持向量机一起即是所谓的基于核的学习方法,简称核方法。
核方法为我们提供了一种解决非线性问题的非常巧妙的方法;简单地说,我们可以把核方法推广至任何包含内积运算的算法中。
各种核方法的共同策略是:
把数据嵌入到一个可以发现线性关系的空间。
从模块化的角度来看,核方法由两个组件构成:
初始映射和模式分析算法,前者由所谓的核函数隐式定义,它依赖于具体的数据类型和关于模式的领域知识,该组件由输入数据构造一个核矩阵(矩阵);后者是从核矩阵中检测具体的模式函数。
这一观测表明模式分析算法能够收集到的关于训练数据和选定的特征空间的所有信息,都包含在由核函数构造的核矩阵中。
从这个意义上说,可以把核函数(核矩阵)看作核方法的信息瓶颈;核函数的选择是核方法取得成功的一个关键问题,同时也是一个难点问题。
本文以支持向量机作为核函数的载体系统综述了核函数的构造与学习方法,在总结该领域研究现状与应用的基础上,凝练了其进一步研究的方向。
支持向量机学习算法支持向量机方法是从线性可分情况下的最优分类面发展而来的。
对于一组训练样本集(,),如果分类面能将训练样本正确地分为两类,那么应使得两类样本到最优分类面最小距离之和最大。
通过求解下面的优化问题可以到得最优分类面(),()式中:
惩罚系数(目的是在模型复杂性与学习能力之间进行折),误差项。
采用拉格朗日乘子法求解上述具有线性约束的二次规划问题,可以得到对偶问题(),()式中:
拉格朗日乘子。
显然,这是一个具有线性约束的凸二次优化问题,具有唯一解。
解中所对应的样本称为支持向量,也就是对最优分类面有贡献的样本。
解上述优化问题可以得到决策函数()()()对非线性问题,设有一个非线性映射:
将输入空间的样本映射到一个高维(可能是无穷维)的特征空间中,在中实现线性分类。
引入核函数(,)()(),对偶问题()变为(,),()相应的决策函数也变为()(,)()()在实际应用中,常用的核函数有线性核、多项式核、核、核等。
核函数的构造核函数的理论最早可以追溯到世纪初期。
年,发现在积分方程的所有连续核中,核可以表征为正定积分算子的一个二元函数,并从数学上给出了有关正定核函数存在和判定的充分必要条件,这就是著名的定理。
另一方面,在世纪年代发展了再生核空间的理论。
在该理论中,通过核函数的再生性质对核函数的定义进行了统一,从而使得很多复杂的证明被大大简化。
而运用定理把核解释成一个空间中的内积这一思想,则首先是在年由,和在势函数方法的研究工作中引入机器学习领域的;但是它的应用潜力直到,和在介绍支持向量机时才首次得到充分理解。
根据定理,确认一个新的对称函数是否是一个核的关键是要检查该函数在任意有限点集上定义的矩阵是否是半正定的。
确切地说,只要我们能保证一个或多个核上的运算结果总是一个半正定对称矩阵,就认为该运算结果是一个核,并称核函数在这些运算下是封闭的。
由此,我们可以得到一种简单的核函数构造方法,即利用简单的核函数构造复杂的核函数。
在核方法研究的早期,人们只考虑这种封闭形式的核函数,它们的处理数据一般定义在向量空间。
例如任双桥等人根据特征空间完全可分的条件,提出了一种自适应的多项式核函数和样条核函数的构造方法,其本质上也是利用了核函数运算的封闭性质。
核的引入给出了第一个根据递归关系定义的核,可以利用动态规划高效地求出这个核。
同时人们也认识到,核并不一定必须定义在向量型的输入上。
年,根据递归关系定义的串核开始出现。
这些开创性的工作极大地扩展了核的应用,显示了输入空间可以是向量、字符串、生物序列、文本、图像等结构化数据。
定义在结构第卷第期汪廷华,陈峻婷:
核函数的选择研究综述化数据上的核,如卷积核、字符串核、树核、图核等,被称为结构化数据核函数。
这些核一般通过直接定义特征空间的内积构造,无需检查半正定性,这就是所谓的从特征中构造核函数的方法。
在结构化数据核函数中,从输入空间到特征空间的映射较为复杂,直接通过这种映射去计算核函数不太现实,因为计算量太大,无法在实际的应用中使用。
因此,在提出这些核函数的同时,研究者们都会提出一些快速实现算法,以便将这些结构化数据核函数应用于实际问题中,。
对于结构化数据,另一个有趣的构造核的方法是从数据的生成信息中求得核,和最早研究了这个主题。
这种方法要求首先按照数据生成的方式建立一个被称为生成模型的模型,该模型可以是确定的或者是概率的,也可以是简单函数或者复杂的图结构,例如有限状态自动机或者隐模型;然后利用这些模型为嵌入函数提供特征并设计可以高效计算的核。
另外,在核方法中参与实际运算的是核矩阵,因而可以不需要知道核函数的具体形式,直接推断出核矩阵就足够了。
基于这种考虑,一些研究人员研究了直接核矩阵学习与构造的方法,例如等人利用半正定规划(,)技术进行最优核矩阵的学习;吴涛等人提出利用散乱数据插值的办法确定特征空间中感兴趣点的内积值以代替传统核函数的一般表达式所起的作用。
这种方法的本质是直接从数据中构造核矩阵,为研究人员提供了一种新的有潜力的思路。
最后,等人通过定义在一种核空间上的再生核空间,即超再生核空间,引入了超核的概念。
超核的构造与学习可以通过定义一个“品质函数()”的量来实现。
超核是一种更广义的核理论,在核函数的构造方面是一种新的尝试。
核函数中参数的选择核函数的构造对于核方法固然重要,但当核函数构造完毕(核函数的类型固定)后,如何确定核函数中待定参数(简称核参数)的最优值同样重要。
研究表明,针对同一个核函数,选择不同的核参数,核方法的性能可能会相差很大。
这主要是因为不同的参数所对应的特征空间的结构具有差异性,而特征空间的性质直接决定着核方法的性能。
从模型选择的角度来看,一般地,判断算法中的参数值是否最优,本质上就是选取适当的参数值以使得算法相应的错误率最小。
目前关于核函数中参数选择问题的解决思路主要有种:
交叉验证技术;最小化学习算法错误率的上界;优化核函数(核矩阵)度量标准。
交叉验证技术的基本思想通过测试非训练样本在某固定参数值上的分类错误率,然后不断地修正参数,以便使测试错误率最小。
该方法本质上是参数空间穷尽搜索法,即用参数空间中每一组可能的参数组合去训练和测试,找出效果最好的参数组合。
经典方法有折交叉验证()和留一法(,)。
以泛化误差估计定理为理论基础的留一法在理论上已被证明是关于真实错误率的无偏估计;折交叉验证法是留一法的推广,计算精度较高而且计算量相对留一法来说减少很多。
交叉验证技术的明显缺陷是不仅需要极大的计算量,并且当参数超过两个时,将难于实现。
为了解决交叉验证技术在大样本、多参数计算上的困难,许多学者提出了最小化留一法误差上界的方法,这些误差界包括、()等。
其中界是较常用的一种误差界,等人指出该界是连续且容易计算的一种风险上界,但只适用于硬间隔和二范数软间隔。
为了使界适用于一范数软间隔,等人对该界进行了推广,得到了一个新的界,并利用这个新的界去选择核的宽度参数,取得了很好的效果。
常群等人则利用这个新的界把核参数的选择从单个推广到多个。
另外,考虑到上述这些界只适用于二分类的缺陷,等人将界推广到了多分类的情形。
基于界的方法通常采用基于梯度的优化算法去求得较优的参数值。
和交叉验证技术相比,这种最小化学习算法风险上界的方法大大减少了计算量,从而适合于多参数的选择问题;但该方法有一个明显的缺陷,即每一次迭代均需训练和求解一个额外的二次规划问题去得到特征空间中包含所有训练样本的最小超球半径,这无疑是一个可观的计算开销。
核参数选择的第三种思路是优化相关的核度量标准,其主要出发点是如何衡量核函数和学习任务(分类)的一致性。
核度量是两个核函数之间或核函数与目标函数间的一个相似性度量,其概念最早由等人提出。
等人提出的核度量标准称为核排列(,),它已经广泛地应用于核函数的选择之中。
提出的核极化()标准可以看作是未归一化的核排列,实验表明采用核极化标准和采用交叉验证技术选择核的宽度参数,获得了相似的分类性能。
等人则进一步研究了核极化的几何意义,指出高的核极化值意味着同类的数据点相互靠近而异类的数据点则相互远离,并提出了一种基于优化核极化的广义核的参数选择算法。
和两人则分析了核排列标准的一些严重缺陷,指出拥有较大的核排列值是一个好核函数的充分而非必要条件(即使值很小的核函数完全有可能获得很好的性能),并提出了一个替代标准,即基于特征空间的核矩阵度量标准(,)。
从特征空间中数据点的分布趋势来看,核排列(包计算机工程与设计年括核极化)与基于特征空间的核矩阵度量标准的目标是基本一致的,即尽量使得同类数据点尽量靠近,而异类数据点尽量远离。
然而,不同的地方在于,对于同类数据,前者是在所有的方向上考虑数据的偏差,而后者只是在正负类中心所确定的方向上考虑数据的偏差;换句话说,数据沿着平行于分类超平面的方向移动并不影响分类的性能。
等人对上述种核度量标准进行了深入的分析,指出它们只考虑了异类样本数据之间的分离性,而没有考虑同类样本数据的局部结构信息的保持性;这种“全局性”的度量标准有可能会限制增强数据可分性的自由度。
针对这个缺陷,提出了一个局部化的核度量标准,即局部核极化(,)。
局部核极化通过引入亲和系数()在一定程度上保持了同类样本数据的局部结构信息,从而进一步增强了异类样本数据之间的可分性。
最近,考虑到数据点在特征空间中的位置不当(例如数据点的凸包远离坐标原点)会导致核排列标准的失效,等人提出了一种基于中心化核的排列标准,并给出了该标准的理论结果及在核优化中的应用。
和最小化学习算法错误率(风险)上界的方法相比,优化核函数(核矩阵)度量标准的方法的优点是不需要多遍训练和计算特征空间中包含所有训练样本的最小超球半径;另外,优化核函数(核矩阵)度量标准的方法可以独立于具体的核学习算法。
核参数选择的其它方法包括核路径算法、基于计算特征空间中簇间距的算法、基于核相似性差异最大化的高斯核参数选择算法等。
另外,从所采用的优化方法的角度看,除了常用的基于梯度的迭代算法之外,许多学者也采用了随机算法来选择核函数中的参数。
多核学习现实世界中往往存在大量的来自多个数据源或异构的数据集,例如基因组数据库就往往由多种类型的数据构成:
变长度的氨基酸串、实值的基因表达数据以及蛋白质之间的交感作用图等。
基于采用单个核函数的形式处理类似数据的效果不是很理想的事实,年和等人,提出了一种新的学习框架,即多核学习(,)。
多核学习采用了多个基核()的组合形式,其中每个基核可以使用描述样例的所有特征,也可以只使用来自某个特定数据源(或观察样例的某个特定视角)的特征。
由于采用多核学习的具有一系列单核所不具备的优点,例如决策函数的可解释性、核函数的自动选择、预测性能的提升等,多核学习一经提出就得到了广泛的关注,是近年来核方法研究的一个非常热点的问题,。
多核学习能够自动评估各个基核对于目标问题的重要性,从而为我们提供了一条选择最优核函数的较佳途径。
目前,多核学习的研究主要集中在如何提高学习的效率()和准确率()两个方面。
从学习的效率方面来看,等人首先指出以的结构风险为优化目标函数的多核学习等价于求解一个半正定规划(,)问题,或更特殊地是一个二次约束的二次规划(,)问题,为多核模型提供了一种功能强大的渐近直推式算法。
与属于凸规划问题,理论上可以保证得到全局最优解,但只适合于求解小规模(基核数目与数据规模均较小)的问题。
随后等人又提出了的一种新的对偶形式,即二阶锥规划(,),并将其写成算法适用的形式,可以求解中等规模的问题。
为了适用于大规模问题,近年来许多研究者提出了交替优化的方法,如基于半无限线性规划(,)的方法、简单多核学习()方法、基于分组的方法等。
这类方法在基核的权系数优化与训练之间交替进行直至算法收敛,即算法的每一次循均包含两个步骤:
给定当前步的权系数值,求解一个经典的问题;采用某种特定的过程更新权系数。
这类方法的优点是可以利用成熟的工具包进行快速求解,不同的地方主要在于更新权系数方法的不同。
从分类的准确率方面来看,主要考虑的是什么样的基核组合形式能够获得更高的分类准确率。
多核模型最简单也是最常见的一种构造形式就是多个基核的凸组合。
凸组合形式中权系数的范数也称为单纯形约束,采用这种组合形式的多核学习称为。
的优点是它会得到稀疏的解,即只有一部分权系数不为零。
稀疏性的提高在某些情况下可以减少冗余,提高运算效率;但当问题的特征编码之间具有正交性的时候,稀疏性可能导致有用信息的丢失和泛化能力的减弱,基于这种情况,等人提出了非稀疏多核学习方法,即。
在特征集冗余和抗噪声方面具有较强的鲁棒性。
随后等人又将范数推广到任意的()范数,即,进一步增强了算法的鲁棒性和通用性。
此外,考虑到基核集中可能存在主成分结构,一些研究者也提出了基于权系数的混合范数()的组合形式,为多核学习提供了一种基于混合范数正则化的新思路。
与上述多核模型基于基核的线性组合形式不同,一些研究人员讨论了基核的非线性组合的可行性。
虽然非线性组合扩大了问题的解空间,但高昂的计算开销和结果的难以解释性等问题是不容忽视的。
最后,许多研究者也根据具体应用问题的实际,对多核学习的框架进行了相应的扩展(或修正),例如提出了多分类多核学习、多标签多核学习、局部多核学习、基于间第卷第期汪廷华,陈峻婷:
核函数的选择研究综述隔和半径的多核学习等模型及其求解算法。
结束语核函数的选择是核方法研究中的一个关键问题,同时也是一个难点问题。
本文从以作为核函数的载体,从核函数的构造、核函数中参数的选择、多核学习个方面对核函数的选择作了比较全面的评述。
从目前的情况看,作者认为该领域的以下一些问题值得进一步研究:
()根据特定的应用领域选择核函数。
是一种在特征空间实施线性判决的学习算法,其中特征空间由核函数隐式定义。
事实上,尽管在理论上核函数有很大的选择余地,但在现实世界中如何根据特定的应用领域选择使用特定的核函数是却是一个公开的难题。
一般而言,使用一些通用的核函数(例如核函数)可以解决一部分问题;然而,众多的研究已经表明核函数的选择与数据的性质(领域)有着密切的关系。
多核学习通过多个基核的组合,从另一个角度解决了特定核函数的选择问题,通过多个权系数的调节与优化,使组合的核函数尽可能满足实际的需求。
由于多核学习需要对多个基核的权系数及其它参数进行优化,因而研究高效的学习算法是必需的。
另外,根据具体问题的不同,对多核学习的框架进行相应的扩展(或修正)也是一个需要进行深入研究的课题。
()设计有效的核函数度量标准。
为了选择恰当的核函数,一个好的核度量标准是必要的。
和两人在提出基于特征空间的核矩阵度量标准的时候曾经指出,当数据集中存在局部结构信息的时候,简单地减小同类内的数据偏差是没有什么意义的,但是他们并没有给出在设计核度量标准的时候如何消除这种影响的方法。
等人提出的局部核极化应该是一种有益的尝试和可行的选择。
然而,这个工作还是略显粗糙,还有诸如如何针对具体问题确定亲和系数、如何将局部核极化推广到一般的核函数等问题需要进一步的研究和探讨。
通过采用与等人相同的分析方法,我们很容易发现核排列和基于特征空间的核矩阵度量标准也没有考虑数据集中的局部结构信息对算法性能的影响,因而也是一种“全局性”的核度量标准。
虽然如此,但要提出它们的“局部化”版本却比局部核极化复杂得多。
这显然是未来研究的一个令人感兴趣的方向。
此外,设计核度量标准的目的是为了通过优化该标准来增强异类样本数据之间的可分性,这和机器学习中的其它标准非常类似,如最小最大概率机器(,)中的最差误分概率、距离度量学习()中的有关优化准则、类别可分离性标准等。
深入研究这些标准之间的关系,可以使我们从这些标准中得到启发,进而设计出更有效的核度量标准。
()拓宽核函数选择的研究范围。
目前,核函数的选择研究主要集中在模式分类领域,在回归、聚类、时间序列分析等领域的研究则较少,在这些方面的研究对于拓宽核函数选择研究的范围,开辟核方法应用的新领域具有十分重要的意义。
参考文献:
,:
,:
,:
,():
()任双桥,魏玺章,黎湘,等基于特征可分性的核函数自适应构造计算机学报,():
,():
,():
()尹传环,田盛丰,牟少敏一种面向间隙核函数的快速算法电子学报,():
,():
,:
,():
()吴涛,贺汉计算机工程与设计年根,贺明科基于插值的核函数构造计算机学报,():
,:
,:
,():
,():
,():
()常群,王晓龙,林沂蒙,等支持向量分类和多宽度高斯核电子学报,():
,:
,():
,:
,():
,():
,():
,:
,:
,():
,:
,:
,:
,:
,():
,():
()唐耀华,郭为民,高静怀基于核相似性差异最大化的支持向量机参数选择算法模式识别与人工智能,():
,():
,:
,:
,():
,:
,:
,:
,:
,:
,:
,:
,():
()牟少敏,田盛丰,尹传环基于协同聚类的多核学习北京交通大学学报,():
,():
()汪洪桥,孙富春,蔡艳宁,等多核学习方法自动化学报,():
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 函数 选择 研究 综述
![提示](https://static.bingdoc.com/images/bang_tan.gif)