实例介绍
【实例简介】
特征融合，多核学习，核方法是机器学习的一种重要思想
8期 汪洪桥等:多核学习方法 1039 1.2容许核的构造 数据的基因功能分类问题,其中就讨论了前期、中期 利用核函数可以大大简化计算,但如何针对具和后期三种集成方式.早期集成是指数据的集成,后 体的问题设计出最适当的核函数却是一个难点实期集成是指分类器结果的集成,而中期集成就是核 际上,经常采用的方法是直接定义核函数,从而隐矩库的组合,它通过对多个基本核矩阵进行合成得 含地定义了特征空间. Mercer条件是检验核函数到,基于这种多核矩阵直接求和方式,可以实现异构 是否定义了一个特征空间的充分条件,我们称满足数据源的融合,用来训练分类器 此后,在蛋白质功能预测56与定位,蛋白质 容许楼满是一些闭包性质或条件6,这使得我分子间的交互预测2,蛋白质折叠识别和远端同源 们可以从些简单的核函数设计出复杂的核函数 性检测2等方向,由于涉及到多特征空间或有效属 性质1.容许核的正系数线性组合是容许核 性的集合( roups of attributes available)问题,来 性质2.容许核的乘积是容许核 自异构源的数据具有不同特性,如全局特性、局部特 性质3.函数乘积的积分是容许核. 性等,这就需要核矩阵在集成时可以评佔这些潜在 设s(x,)是一个定义在X×X上的函数,使的异构目标描述子各自的贡献.因此出现了一些加 得k(x,x)=/5x,x)(2,x)dx存在则ka,2)板图多核合成方法,这类多核方法都无追过多个核 是一个容许核 数的线性组合得到的,图1所示的就是其构成的 性质4.平移不变核是容许核的充要条件 示意图 个平移不变核k(x,2)=k(-x)是容许核,类别标号或预测值 结果输出) 且仅当其傅里叶变换F(u)-(2x)-号xk(x) i(ur)dx是非负的 分类或回归 (分类器或回归R效 性质5.内积型核是容诈核的必要条件. 合成核空闫 合成核 若一个内积型核k(x,2)=k(x·z)是容许核,则 它必满足v≥0.k(5)≥0.0k()≥0且k(5) Kernel s Kernel h 5k()>0 核空间(kemC 性质6.内积型核是容许核的充要条件. 一个内积型核k(x,z)=k(x·z)是容许核,当 征空间(C 且仅当其幂级数展开式k(t)=∑0ant中所有系 数an≥0.对于有限维的空间,条件可以稍微减弱 输入数据 图1多核函数线性组合合成示意图 当前已经仔在较多的满足 Mercer条件的核函rig. 1 Sketch map of composition using multiple kernel 数,常见核函数通常可分为两类:局部核和全局核6 ar 而局部核选择不同的核参数,又可分为大尺度核与 小尺度核.在一些复杂情形下.同时考虑核机器分 下面呆用公式的形式对上述线性组合合成核进 类、回归性能和泛化能力,将不同核组合使用,将是行描述.假定k(x,2)是已知核函数,k(x,2)是它的 更合理的选择 归一化形式,例如核函数k(x,z)可以采用如下方法 进行归一化:√k(x,x)k(z,x).采用以引入的符 2基本多核学习:合成核方法 号,可以定义以下几种合成核: 将不同特性的核函数进行组合,获得多类核函 a)直接求和核( Direct summation kernel) 数的优点,可以得到更优的映射性能.并且,典型的 学习问题经常涉及到多种或者异构的数据,多核方 k(,2)=∑k(x,2) 法可以提供更佳的灵活性.此外,它可以作为一种巧 妙的方法来解释学习结果、使得应用问题可以得到 b)加求和核( Weighted summation kernel) 更深入的理解.这就是多核学习的一类基本方法,即 合成核方法 k(x,2)=∑(,2,≥0,∑月=1(6) 2.1合成核的构造 1)多核线性组合合成方法 c)加权多项式扩展核( Weighted polynomial 多核学习最早从生物信息学领域得到应用和认 extended kernel 同.如 Pavlidis等20在2001年就研究了基于异构 k(x,z)=ak1(x,2)+(1-a)k2(x,2)(7) 1010 自动化学报 36卷 其中.k(x,2)是k(x,x)的多项式扩展 是,该合成核矩阵的大小为(s×n)×(s×n),而原 近来,这类合成核法又得到一些改进,在图始核矩阵的大小都是n×n,由于合成核矩阵是原始 像目标的识别领域得到广泛应用.如在金字塔框架核矩阵规模的§倍,因此样本特征必须被复制,使运 对日标形状进行多核表示阿,或釆用多核方法,算量成倍增加 自动获得基」决策的一种相应目标类别的稀疏依赖 3)其他改进合成核方法 图,实现了多类目标联合检测③2].提高了目标的识 近年来,针对多核学习中核函数的选取以及杖 别率.通过同时考虑多核线性组合的稀疏性和分类值系数的改进,又出现了一些新的多核合成方法, 器的强判别力,将多核学习问题转化为不同的优化如: 问题58.63,或通过多对象描述子、多特征空间的整 a)非平稳多核学习 合,并进行快速求解64.此外,合成核方法在特征提 前述的多核线性组合方法都是对核函数的平稳 取、处理及应用7、分类972-4、图像分割、组合,即对所有输入样本,不同的核对应的权值是 系统辨识等方面又得到了一些成功应用 不变的.无形中对样本进行了一种平均处理. Lewis 2)多核扩展合成方法 等吲提出了一种多核的非平稳组合方法,对每个输 述合成核方法都是试图通过一种求和“平均入样本配以不同的权值系数.如常规SVM判别函 化”的思想42来实现不同核矩阵融合.然而,这里数为 存在个丢失原始核矩阵信息的风险.比如,如果数 据集的局部分布是多变的.不同的核处理不同的区 f(c)=∑0r,m)+b(1 域会得到更好的结果,对不同核函数采用平均的方 法将丢失刻画这些局部分布的性能.为了实现核矩 引入不同的加权系数,典型的合成核SVM的 阵的组合而不丢失任何原始信息,可以考虑将多核判别函数可以改写为 矩阵进行扩展合成42],新的核矩阵由原核矩阵和其 他不同的核矩阵共同构成.在这个更大的核矩阵中 原核矩阵仍然存在.因此,原始核函数的性质得以保 ∫(x)-∑m∑k(x,x)+b(1 留.该合成核矩阵的形式为 而对于非平稳的合成核SVM,其判别函数改进 11K1,2 K 为 2.2 K ∑a:∑()k(c;,m) (12) K1 K 可以看出,原始核矩阵位于新矩阵的对角线上在最大熵判别( Maximum entropy discrimination, 其他所有元素是定义为(Kn)3=Fn(m,)的MED)框架下,通过使用一种大间隔隐变量生成 两个不同核矩阵的混合,可由如下公式求得(以两个 模型,使得隐参数估计问题可以通过变化边界和 高斯核为例) 一个内点优化过程来表示,并且相应的参数估计可 以通过快速的序列最小优化( Sequential minimal optimization,SMO)算法实现.通过多种数据集的 4:4 + (9)实验验证,非平稳的多核学习方法具有更好的通用 性. 很明显,当p=p时,Kp=kn b)局部多核学习 实验结果显示,当数据集具有变化的局部数据 此后,仍旧是针对多核学习在整个输入空间中 分布时,这种合成核方法将是更好的选择此外,通对某个核都是分配相同权值的问题,G6nen等0 常核组合方法在很大程度上依靠训练数据,并且必利用一种选通模型( Galing nodel)部地选择合 须道过学习获取一些权系数,以标识每个核的重要适核函数,提出了一种局部多核学习算法在SVM 性.而在护展合成核方法中,这些核函数的重要性可框架下,其判别函数形如 以直接从支持向量机的训练过程中导出.由此,分别 对应不同核的权系数可以通过一个单独的分类尜优 化过程整体得到.并且该优化过程不会像其他加权 ∑q∑(x)k1(x;xm/r)+b(13) 核方法那样,由于在优化权系数和训练分类器过程 中两次仗用训练数据而产生训练数据的过拟合.但其中,7z(x)是选通函数,其定义形式为 8期 汪洪桥等:多核学习方法 1011 7(c) exp((vm, )+Umo) (14)详细阐述了应用于合成核的列生成 Boosting方法 并成功推广到分类和回归问题 ∑ep(,x)+"l 2)二次约束型二次规划 从数学形式上看,二次约束型二次规划是一类 这里的tm和tm是选通模型参数,可以在多核学习 目标函数和约束同为二次函数的优化问题 过程中通过梯度下降法获得.将局部选通模型和基 于核的分类器相结合,优化问题可以用一种联合的 方式加以解决.局部多核学习方法获得了与多核学 习近似的精度,但只需要存储更少的支持向量.基于 st.Px+qx+r;≤0,i=1,2,…,m 此, Christoudias等又提出了一种基于 Bayesian Ar=b 的局部权值求取方法,以使学习过稈能适应人规模 (1 的数据集 这里,P,B1,…,Pn是n×n矩阵,优化变量x∈ c)非稀疏多核学习 R;如果P1,…,Pmn均为0矩阵,则约束变为线性 大部分合成核方法都有式(6)的形式,即对多核的,该问题实际变为一个二次规划问题 系数的约束是一种1范数的形式,以提高核组合的 Bach等针对多核矩阵和分类器系数锥组合 稀疏性.稀疏性的提高在一些情况下可以减少冗余,问题的联合优化,提出了Q(QP的-种新对偶肜 提高运算效率.但当某个问题多个特征编码间具有式,把它作为一个二阶锥规划,可以利用 Moreau- 正交性,稀性可能导致有用信息的丢失和泛化性 Yosida正则化来生成SMO方法的适用形式.实 能变弱.Klof等通过对系数引入一种l2范数约验结果显示这种基于SMO的算法比常用工具箱中 束,即‖2=1,提出了非稀疏的多核学习方法.虽应用的内点法更有效,广泛应用于支持向量回归问 然在此约束下,名核组合形式是非凸的,但通过使用题1 二范数‖|2=1边界上的值,可以得到一个紧致的 3)半定规划 凸近似,这就保证了核矩阵的严格正定性.通过在大 通过在一个核矩阵中综合考虑训练数据和测试 规模数据集下与C1范数和常用多核学习( Multiple数据, Lanckrict等田通过半定规划技术实现了核 kernel learning,MKT)方法进行对比实验,仿真实矩阵的学习问题,也为合成核模型提供了一种功能 验结果显示2-MKL在抗噪声和特征集冗余方面具强大的渐进直推式算法,该算法被成功应用并推广 有较强的鲁棒性.此后,Klo等刚又将O2范数约到蛋白质功能预测0.其考虑的核矩阵具有如下形 束推广到任意C范数,p>1,进步增强了核机器式 的通用性和鲁棒性 Ktr Ktrt 2,2合成核机器的学习方法 Kr Kt 为了求取合成核的参数,通常是将合戊核与支其中,K一(x)重(x;),1-1,…,mu,m+ 持向量机方法相结合,然后将目标函数转化成不同1,…,m1+nt:这里nt和m是有标号的训练样 的优化问题,如不同的正则化形式或对训练样本本个数和无标号的测试样本个数.我们的目标是 的一些约束,通过不同的优化方法进行求解.基于通过优化关于训练数据块Kt的损失函数,学习得 此,出现了多种合成核机器的学方法 到最优的混合数据块矩阵Kr和测试数据块矩阵 1) Boosting方法 K1即利用有标号的训练样本米预测测试样本的类 早期受集成思想和 Boosting方法的启发,别,也就是说,作者认为在训练的过程中同时考虑训 Bennett提出了一种多自适应国归核( Multiple练样本和测试样本,可以找出最佳的核矩阵.但这 additive regression kernels,MARK)算法.MARK样产生的问题是,求解核矩阵的搜索空间也相对变 定义了一种异构核模型,并考虑一个大规模核知阵大,为了避免过学丬( Overfilling), Lanckriet利用 库( Library),这个库由不同的核函数和其参数构成.限制核矩阵的迹为一常数米控制,于是有了约束式 通过使用一种梯度 Boosting列生成方法, MARK tr(K)=C 构建出异构核矩阵的每一列,然后将其添加到合成 半定规划是一种凸优化问题( Convex opti- 核中.算法的目标就是在这个核矩阵库的基础上,找 mization problem)∞o,它有一个线性的目标函数 到一种构建推广模型的方法.这种方法推广性强,不( Alline objectives lunction)、有限个线性矩阵不等 需要存储大量的数据米应对后续的预测,提高了预式约束( Linear matrix inequality constraints)以及 测的效率在此基础上,通过与SVM结合,Bi等17有限个线性矩阵等式约束( Affine matrix equality 1042 自动化学报 36卷 constraints),其标准形式如下 如回归问题、一类分类(奇异检测)问题等.实验结 果显示该算法可以有效增强模型的自动选择能力 min c u 并能提高学习结果的解释性.同时能有效应用于数 S.t.Fy()-Fd+uFi+,.+ugFg20 十万个样本和数百个核的大规模组合优化问题.这 7=1,…, 种半无限线性规划相比其他方法明显提高了学习速 度,适宜于解决大规模问题.特别是当SVMs与·些 Au= b 已出现的字符串核( String kernel)相结合, String (17) kernel也是一种有效的核方法,它根据两个字符串 其中向量t是最优化目标,F F是n×n的的所有公共子串计算它们的相似度,利用这些核对 对称矩阵.F(a)是一个半正定阵,上标j表示特征的稀疏映射,使得我们可以训练一种字符串核 可能有1全1个约束式:满足此约束式的所构成sVM,并应用于计算生物学中的千万级样本的数据 的集合是一个凸集合.A是一个行数与长度相同,片段24在此基础上,7iem等提出了一种应用于 列数与b长度相同的矩阵表示有限个等式约束式联含特征映射的多核学习方法,为多兴分类问题的 因此,半定规划是在对称且半正定矩阵的凸子集合多核学习提供了一种史方便和原理化的途径.通过 ( Convex subsct)卜:求解凸函数的最优化问题 针对多核支持向量分类问题,通过定义一种对一种凸Q(QP以及两种 SILPs在数据集上进行 比较,实验结果显示 SILPS比QCQP在速度上更 能指标( Performance iudex)u(K),基于原始一对有优势 终可以转化为一个标准的半定规划形式 5)超核( Hypcrkcrncls) 对基于核方法的支持向量机而言、如何选择一 个合适的核函数实现自动的机器学习是一个很大的 min t ,t,入,υ,6 挑战Ong等3通过定义一种核空间上的再生核 t.tr|∑F Hilbert空间,即超再生核 Hilbert空间,并引入超 核的概念及构造方法,在更广义的层面上实现了这 ,K;≥0 目标 定义1(超再生核 Hilbert空间, Hyper re producing kernel Hilbert space).改Ⅹ为非 3.tr e-tU 8+ xy 空集合,Ⅹ:ⅩxX是复合指标集,H为函数f:X →R的 Hilbert空间,该函数可表示为该空间中两 (e+-6+入y)1t-26Ce 个向量的内积,且其范数f=√f,f,则被 0>0 称为超雨生 Hilbert空间,如果存在一个超核k:x 6>0 X→R具有如下性质: (18 再生性:对所有∫∈丑,有(k,),/) 其中,t是引入的一个替代变量( Auxiliary vari-f(x),特殊地,(k(x),k(,x2)-k(xx ablc),v,6,A是引入的 Lagrangian乘子,至此,可 b)k张成整个空间H,即H 以通过标准的半定规划求解方法得到B及相应的span()(X Lagrangian乘子,半定规划具有很高的泛化能力 c)对仟一固定的(X,超核k是关于其第 线性规划( Linear programming,LP)以及QCQP二个输入的核函数,即对任一固定的x∈X,函数 问题都可以转换推广成半定规划门题然后可以很k(x,x)-kx,(x,x),x,x′∈是一个核函数 容易地使用内点法( Interior-point method)加以解 在超再生核 Hilbert空间上,可以用类似于止则 决 化品质函数的方法.得到一个从训练数据对核进行 4)半无限线性规划 学习的推理框架.对超核的学习,可以通过定义 Sonnenburg等B7在多核矩阵锥组合的基础上,个被称为品质函数( Quality functional)的量(类似 提出了一种通用而更有效的多核学习算法.该方法于风险函数)来实现,这个量可以衡量核函数“非良 将Bach等的QCQP对偶形式改写为一种半无限( Badness”的程度 线性规划(Semi- infinit ite linear program, SILP)形 定义2(正则化品质函数, Regularized qual- 式,新的规划形式可以在标准的SVM应用问题中, ity functionality).设X,Y分别是训练测试样本 利用成熟的线性规划方法进行求解.并且,通过将组合和样本标签,对X的一个半正定核矩阵K, 此形式进行推广,算法能有效解决更多类型的问题,其正则化的质函数定义为如下形式: 8期 汪洪桥等:多核学习方法 1013 g(,x,Y)=9mp(k,X,Y)+2‖(1 7)分组Laso Lasso回归是目前处理多重共线性的主要方法 这里,≥0是一个正则化常数,h表示空间之一,相刘于其他方法,更容易产生稀疏解:在参 H中的范数,Qm(k,X,Y)是一种经验品质函数,数估计的同时实现变量选择,因而可以用来解决检 它表示核函数k与某一特定数据集X,Y的匹配程验中的多重共线性问题,以提高检验的效率.Laso 度,该函数的值常用来调整k以使得gm最优(如:可以推广为分组Laso( Group lasso),从而使得 最优核目标度量) 模型的解可以保持组稀疏性和层次性.Bach26·关 引理1(再生核 Hilbert空间的表示定理,注于分块1范数正则化的最小二乘回归,即分组 Representer theorem for hyper-RKHS).设Las0o题,研究了其渐进模型一致性,推导出了分 X为非空集合,Qmp是任意经验品质函数,X,Y组Laso-致性在一些实际假设下的充要条件,如 分别是训练测试样木组合和样木标签,则每一个最模型误定.当线性预测器和欧氏范数(2范数)用函 小化正则化品质函数g(k,X,Y)的k∈Ⅱ具有数和再生核 Hilbert,范数代替,这就是常说的多核学 以下的一种表示形式 习问题.通过使用函数分析工具和特定的协方差算 ,将上述一致性结果推广到无限维情形,同时提出 k(x)=∑月12(m,m),(m,m1),,x∈x 种自适应方法来获得一致性模型的估计,即使 2,7 在非适应方法必要性条件不满足的情况下也能适用 (20)为多核学习间题提供了一条新的途径 对每一个1≤i,≤M,这里B;∈R 2.3其他合成核参数学习方法 根据超再牛核 Hilbert空间的表示理论可知,由 超核构造的决策函数不仅由某一个单核构成,而且 从最简单的多个核直接求和到上述的各种改进 还由多核之间的一个线性组合构成,因此具有更优合成核构造方法,多核学习经历了从经验性选择 的性能在分类、回归以及奇异检测等方面的实验证运用多和优化方法求解的过程但针对一些具体间 实了该方法的有效性B.8,拓展了多核模型选择与题,对核参数的选取,多核权系数的设定,目前还没 合成的研究途径 有形成一个合理统一的模式.常用的方法只能是凭 6)简单MKL 借经验、实验对比、大范围的搜索或通过交叉验证 从Bach等的多核学习框架36出发, Sonnen- 等进行寻优.在这种情况下,也出现了其他的些方 bug等提出了种通用而更有效的多核学习算法,实现了多核学习问题,典型的有 法37,该方法通过迭代使用现有的支持向量机代 1)基于智能优化方法的多核学习 码,从一个新的角度解决了人规模问题的多核学习 这类方法主要通过一些比较成熟的智能优化 然而,这种迭代算法在收敛到一个合理解之前,需要方法,建立目标函数,寻找该函数极值的过程就是 过多的迭代运算. Rakotomanonyy等27用一种自合成核参数寻优的过程如采用多项式核与径向 适应的C2范数正则化方法米考虑多核学习问题,每基核的合成核2作为支持向量机的核函数k 个核矩阵的权系数被包含在标准SVM的经验风险2-(1-p)km,将其用SVM进行预测过程中 最小化问题中,并采用(2约束以提高解的稀疏,的参数向量(d,o,,p)作为粒子,其中d为多项式 然后采用了一种基于分块1范数正则化的算法来解核参数,为径向基核尺度参数,y为SVM调整参 决这一问题,为多核问题提供了一个新的视角,并且数,p为合成核的权重参数,利用粒了群算法对该合 证明了该方法与Bach等的方法是等效的.从上运成核的参数进行优化,最终找到最优的预测结果 描述可以看出,除了学习合成核外,该与法解决的是 2)基于核目标度量的多核学习 个标准的SVM优化问题,这里核的定义形式为 核度量434是两个核函数之间或核函数与目 多个核的线性组合. Rakotomamonjyl称之为简标函数间的一个相似性度量,在多核矩阵信息融合 单多核学习( Simple MKL)在加权的2范数正则方面得到了应用,其概念最早由 Cristianini等提出 化形式下,同时对多核权系数进行一个额外的1范考虑一个两类分类数据集S={(x,1)}=1,其中非 数约束,为多核学习提供了一种基于混合范数正则∈{+1,-1},则在数据集S下,两个核矩阵之间的 化的新思路.简单多核学习可以从两类分类问题向核度量定义为 其他方向扩展,如回归、类、一类分类(奇异检测) A(S,K1,K2) (K1,K2) 以及多类分类问题,具有很强的通用性,并且与其他 (21 √k1,K1)F(K2,k2)F 多核学习算法相比,该算法收敛速度更快且效率更 这里,(K,Ka)F=>1-1Fn(x2:)(x,T)通 1044 自动化学报 36卷 过上式,对应于S的核矩阵K的性能可以通过A ;-2,t-0,1,2, 值米量度,如:A(5,K,G),这里的G是基于特定任 务的理想核G=y,其中y=m12…,.基 另一种典型多尺度核为小波核函数( Wavelet kernel function) 831 于对目标核的度量原珥,通过使用不同的核函数,或 定理1.令h(m)是一个小波母函数,a和c分 者调节不同的参数值,可以产生一组核矩阵.然后,别表示仲缩和转移因子,a,∈R如果x,z∈R 对该度量值的最大化执行半定规划或其他学习方法,则内积型小波核函数可表示为 以得到一个对不同核矩阵加权组合的最优核 3多个尺度的多核学习:多尺度核方法 k(2)=江4( 合成核方法虽然有了一些成功应用,但都是根 据简单核函数的线性组合,生成满足 Mercer条件的转移不变小波核函数为 新核函数;核函数参数的选择与组合没有依据可循, 对样木的不平坦分布仍无法圆满解决,限制了决策 k(a, z)= ( 函数的表示能力.在此情况下,山现了多核学习的 种特殊化情形,即将多个尺度的核进行融合.这种 定理2.考虑具有一般性的小波函数 方法更具灵活性,并且能比合成核方法提供更完备 的尺度选择.此外,随着小波理论、多尺度分析理论 h(x)=cos(1.75x) 25 2 间使其其有了很好的且论录这类方法目箭也如果x2(R",则小波核函数为 得到了很好的利用,烘型的如 Kingsbury等③2将多 个尺度大小的核进行分光heng等B到、 Yang k(a,2)=h(x二 等834提出了多尺度支持向量回归.分别用于非平坦 i=1 数的估计和时序列预测.此外,通过进一步将多 ∏1c015(n-2) C一之 尺度核与支持向量机结合.多尺度核方法在基于回 归的热点检测48和图像压缩49等方面均得到了应 (26 用.近来,结合多尺度分析方法,基于 Hilbert空间通过仲缩因子a的变化,即可得到不同尺度的小波 中的再生核进行函数重构得到了重视并进行了 相关的应用研究;此外,多尺度核方法又逐步推广到核函数 了高斯过程的健模与处里-27,这对基于核方法3.2多尺度核的学习方法 的机器学习又是一次大的扩展 1)多尺度核序列学习方法 3.1具有多尺度表示能力的核函数 对多尺度核的学习,很直观的思路就是进行多 尺度核的序列学习.多尺度核序列合成方法32简单 度表示能力的核函数.在被广泛使用的核函数中,高理解就是先用大尺度核拟合对应决策函数平滑区域 的样木,然后用小尺度核拟合决策函数变化相对剧 斯径向基核 烈区域的样本,后面的步骤利用前面步骤的结果,进 k(a, a )=cxp (22 行逐级优化,最终得到更优的分类结果 考虑一个两尺度核k1和k2合成的分类问题 是最受欢迎的,因为它们具有通用普遍的近似能力,我们要得到合成的决策函数 同时它也是一种典型的可多尺度化核.以此核为例 f(x)=f1(x)+f2(x) 将其多尺度化(假设其只有半移不变性): k(-22 这里 2 2a f()=∑ak1(xn,)b2 其中.σ1<…<Om可以看出,当σ较小时,SVC (28 可以对那些剧烈变化的样本进行分类;而当σ较大 f2(x)-∑k2x1x)+b2 时,可以用来对那些平缓变化的样木进行分类,能得 到更优的泛化能力.具体实现时,σ的取值可以借鉴 设想k1是一个大尺度的核函数(如σ较大的径 小波变换中尺度变化的规律,a可由下式定义: 向基函数),相关的核项系数αz选择那些决策函数 8期 汪洪桥等:多核学习方法 1015 f(x)光滑区域村应的支持向量;而k2是小尺度核函数f(v),其中,u是由2n个组合核参数构成的向量 数,核项系数β;选择那些决策函数∫(x)剧烈变化(a1,%,a2,,…,an,"n),我们的目标就是找到 区域对应的支持向量.具体方法是:首先通过人尺个合适的v.使得∫(v)最人.其核心就是通过对解 度的单核k1构造函数(x),这样,该函数可以很好向量进行组合、变异、选择,在设定的进化代数内不 地拟合光滑区域,但在其他地方存在显者误差,可以断求取并更新目标函数,最终得到∫(u)的最大值 使用相对较小的松弛因了来求取α;然后,在f1(x 基础上使用小尺度的核k2构造几2(m)使得联合函4从有限向无限核的扩展:无限核方法 数f1(m)J2(x)比∫(m)具有更好的拟合性能,这 前述的合成核与多尺度核方法都是在有限个核 种方法实际上是多次使用二次规划以实现参数的获函数线性组合前提下加以讨论的.但对一些人规模 取,运算复杂度较高,同时支持向量的数量大量增问题,基于有限个核的多核处理方法不一定有效,多 加 核融合的决策函数的表示能力也不能达到处处最优; 近来, Cortes等2关注于序列核函数学习问此外,在一个多尺度核函数族中,有限个核函数的选 题,提出了一种学习合理核函数的通用形式,并且证择并不唯一,并且其不能完备地表征这个核函数族 明这个大的合理核函数族可以通过结合支持向量机因此,将有限核向无限核的扩展也是一个重要的方 目标图数和核脊回归的一种简单二次规划加以解决,向 这种方法提高了先前出现的·些学习方法效率.如 早在2006年, Argyriou等同关注于监督学习 SDP、QCQP此外,对于核脊回归这种特定情形,中的核学习问题,提出了一种多核学习的新方法,该 给出了基于最优核矩阵封闭解的一个替代解,该方方法可以从由多个基本核函数的合法集合所构成的 法成功应用到了分类和回归问题. 个凸壳中找到某个核,使其能最小化凸正则化函 2)基」智能优化的多尺度核学习方法 数.与其他方法相比,这个方法有一个独有的特征, 与合成核类似,针对多尺度核学习问题,另一类即上述基木核的个数可以是无限多个,仅仅需要这 重要的方法仍是基于多核的整体智能优化.如:利些核是连续参数化的.例如:基本核可以是各向同 用EM算法训练多尺度支持向量回归( Multi-scal性、方差规定为一定间隔的高斯核,甚至可以是通过 support vector regression, MS-SVR.这种方法起对多个连续参数进行参数化的高斯核尽管这个优 源」非平坦图数的估计间题,它采用多种尺度的化问题是非凸的,但它属于更广范畴的凸函数差分 核函数,使得较小尺度的核可以拟合快达变化,而较(D) iference of convex functions)规划问题,因此 大尺度的核可以拟合平缓变化基于此,文献84可以应用最新的凸函数差分优化理论加以解决 提出了两种迭代的EM训练算法,它们分别以渐进 在此基础上, Geller等39更侧重于用半无限规 的方式实现了1范数和0范数:通过限制基函数的划解决来自通用核类型的核函数学习问题,并设计 数目从而限制了模型的复杂性,同时解的稀疏性大 种新的算法,称为无限核学习( Infinite kernel 大加快了训练过程,也节约了大量的测试时间并且 earring,IL).IKL算法既适用于无限也适用」有 MS-SVR的优化目标函数是全局的,可以直接求得限核情形,并且在大量核情形下,它比 Simple mKl 所有m个核项系数a;文献5]提出了一种多尺算法更快也更稳定.通过将IL和MKL应用于 度径向基核参数选择的进化策略,用于支持向量机sM对人量数据集进行实验发现:在一些数据集 的训练.该算法针对多尺度高斯核函数的组合形式 ,由于核函数族中核的大幅增加,IKL可以比 SVM/MKL大大提高分类正确率,在这些情况下 需,y )=∑ak(xy,7) (29)IKL能保持它的实用性,而交叉验证和MKL都是 不实用的 k(a, y r2)=exp(vills-y (30 此后,针对有限核的凸组合受限于选择的有限 性问题, Onogur- Akyiiz等又提出了一种基于无 这里有2个参数需要确定,分别是〃个权重参数限和半无限优化的无限核组合新方法,核的组合可 和n个径向基核的宽度a1Y,讠-1,……,n.这些以通过同伦参数( Homotopy parameter)或更特殊 参数值的确定会影响到组合核的性能,也最终会影的参数来实现.考察所有来自无限核集合中核的极 响分类精度.具体方法是将样本集中的总训练样本小良凸组合,可以发现:于组合,间隔最人化是在 分成数量相等的几份,如5份,任意选取其中的4份个紧指标集( Compact index set)下的无穷多个 作为训练样木,可以训练得到5个分类器,分别以约束和一个额外的整数约束条件下实现的.通过在 剩余的1份作为测试样本,可以得到5个分类结果.概率测度( Probability measures)空间的参数化,该 将这5个分类结果(正确率)的平均值作为目标函问题变成了一个半无限问题,可以通过半定规划方 1016 自动化学报 36卷 法加以解决 等3】近米提出的一种更广义的核理论,在核函数的 构造方面也是一种重大创新.必将成为这一领域 5总结与展望 个新的热点,其理论体系还有待进一步完善与扩展 核方法在模式回归、分类以及概率密度佔计等 3)多核学习方法逐步问人规模数据集的应用领 方面都有大量的理论分析和成功应用.针对单核函域扩展对于一些规模较小的数据集(虽然通常核 数的弊端,多核方法已经成为当前核机器学习的热机器学习向题考虑的就是小样本情形),多核方法采 点.特别是在解决一些复杂问题时,多核方法具有更用这些组合操作和学习方法并不会遇到太大障碍 优的性能.基于此,也出现了很多相关的多核机器学但对于一些大规模问题,由于涉及到多核矩阵的快 习方法,这些方法为多核紅阵的融合提供了多种更速求解,高维多核扩展矩阵的各种分解等处理,常 优性能的解决途径,同时一些方法还能有效解决大规的多核学习方法的学习效率会非常低下.利用支 规模问题.可以预见,多核方法必将在核 Fisher判持向量机以及各种改进方法,虽然当前L经出了 别分析、攴持向量机、相关向量机、奇异检测、核聚一些基于大规模问题的学习算法,如 Boosting方 类分析等方向得到不断推广,并在诸如时间序列(动法、QCQP、SDP或一些分级方法1等,但这些 态系统、财经等)预测、信号和图像的滤波、压缩和方法在学习速度方面仍然有待提高 超解析( Super-resolution)、故障预报、文本分类 4)多尺度核方法具有更优的研究基础和前景 图像处理、目标检测、视频跟踪、生物信息学(双螺随着尺度空间理论和小波理论的不断完善,多尺 旋、基因序列数据的分类、蛋白质功能预测等)等领度/多分辨分析方法得到了认同和推广.多尺度核由 域得到广泛应用 于具有较为统一的模型形式和丰富的尺度选择,使 多核学习方法已经得到了广泛认同和成功应用,得它在处理复杂问题时有很大的优势,特别是如高 必将成为今后的理论研究热点和有效的模式分析工斯核这种具有强映射能力的核函数(能将样本空间 具,以卜总结其进一步的儿个研究方向 映射到无穷维的特征空间).因此,多尺度核方法的 1)除了常规的回归、分类等应用领域,核方法 种有效解决方案是引入尺度空间,构成具有多分 的热点还包括核密度佔计、子空间分析、用于冋归辨分析能力的增广特征空问、获得决策函数的多分 或分类的特衎选择等.同样的,合成核与多尺度辨表示期望在这些特征空间所组成的一个增广空 核方法在这些领域也大有用武之地.如用于两类、间中,构造新的全局优化问题,找到一个融合了它 多类分类问题最优贝叶斯决策面的获取,改进的核们各自优势的史好的解.它的难点在于如何构建 主成分分析等.此外,在当前机器学习的些热门套完备的多分辨分析的核函数空间理论,并应用到 领域.如多示例学习閃η、半监督学习、非监督学习等支持向量机的快速实现.这里可以设想采用标准化 方向.多核方法也得到了一些研究和应用.典型的如尺度核函数的构造,期待多尺度特征增广空间解的 Kembhavi等8提出了一种多核方法的增量学习算快速求取,此外,多尺度核是有限个向无限个核函 法,并将其用于目栎识别.黎铭等应用多核理论,数扩展的基础对于如何解决多个尺度核分步执行 提出了基于多核集成的在线半监督学习方法 OMike带来的支持向量个数急剧增大的问题,可以考虑构 ( Online multi-kernel ensemble),能够有效利用大建新的基于多尺度合成核的全局优化问题,采用迭 量未标记数据提升在线学习性能Zhao等m研代的方法,获取基于非传统意义下的稀疏的支持向 究了基于最大间隔的多核聚类方法.牟少敏等2针量10.除此之外,还可以将不同多尺度核进行合 对实际应用中经常出现的昇类数据源和多核函数带成,研究多尺度合成核方法,如高斯核与小波核,进 来的计算量增加等问题,提出了一种利用协同聚类步增强决策凶数的多尺度分辨与表达性能 对多核支持向量机的训练数据进行简化的方法,大 5)当前的一些多核学习方法,还存在大量未解 人减少了支持向最的数目,从而减少了计算量,并且决的问题,阻碍了多核方法的进一步推.如根据简 还不会影响分类精度 单核函数的凸组合,生成满足 Mercer条件的新核函 2)核函数的构造一直是核机器学习的一个难数,它在核数的选择与组合上没有依据可循;如何 点.针对具体应用问题,如何选择或构造出最合适的处理好多个核之间的关系,采用多核学习方法确定 核函数,目前并没有完善的理论基础.多核方法通过系数时的效率问题,这些都有待进一步探索;此外, 多个或多种核函数的组合,从另一个角度解决了特通常合成核方法对样本的不平坦分布仍无法很好解 定核函数的构造问题,通过多个参数的学习与调节,次,限制了回归函数的拟合性能和分类决策函数的 使组合的核函数尽可能满足实际需求.因此,多核表示能力;多尺度核方法在尺度选取上没有完备有 方法是针对复杂问题,构造新的核函数与新的高效效的理论依据,并不是真正意义上的多尺度:用优 核机器3的一条实用途径此外,超核理论是Ong化方法进行参数选择和序列多人度方法,都会使学 【实例截图】
【核心代码】
特征融合，多核学习，核方法是机器学习的一种重要思想
8期 汪洪桥等:多核学习方法 1039 1.2容许核的构造 数据的基因功能分类问题,其中就讨论了前期、中期 利用核函数可以大大简化计算,但如何针对具和后期三种集成方式.早期集成是指数据的集成,后 体的问题设计出最适当的核函数却是一个难点实期集成是指分类器结果的集成,而中期集成就是核 际上,经常采用的方法是直接定义核函数,从而隐矩库的组合,它通过对多个基本核矩阵进行合成得 含地定义了特征空间. Mercer条件是检验核函数到,基于这种多核矩阵直接求和方式,可以实现异构 是否定义了一个特征空间的充分条件,我们称满足数据源的融合,用来训练分类器 此后,在蛋白质功能预测56与定位,蛋白质 容许楼满是一些闭包性质或条件6,这使得我分子间的交互预测2,蛋白质折叠识别和远端同源 们可以从些简单的核函数设计出复杂的核函数 性检测2等方向,由于涉及到多特征空间或有效属 性质1.容许核的正系数线性组合是容许核 性的集合( roups of attributes available)问题,来 性质2.容许核的乘积是容许核 自异构源的数据具有不同特性,如全局特性、局部特 性质3.函数乘积的积分是容许核. 性等,这就需要核矩阵在集成时可以评佔这些潜在 设s(x,)是一个定义在X×X上的函数,使的异构目标描述子各自的贡献.因此出现了一些加 得k(x,x)=/5x,x)(2,x)dx存在则ka,2)板图多核合成方法,这类多核方法都无追过多个核 是一个容许核 数的线性组合得到的,图1所示的就是其构成的 性质4.平移不变核是容许核的充要条件 示意图 个平移不变核k(x,2)=k(-x)是容许核,类别标号或预测值 结果输出) 且仅当其傅里叶变换F(u)-(2x)-号xk(x) i(ur)dx是非负的 分类或回归 (分类器或回归R效 性质5.内积型核是容诈核的必要条件. 合成核空闫 合成核 若一个内积型核k(x,2)=k(x·z)是容许核,则 它必满足v≥0.k(5)≥0.0k()≥0且k(5) Kernel s Kernel h 5k()>0 核空间(kemC 性质6.内积型核是容许核的充要条件. 一个内积型核k(x,z)=k(x·z)是容许核,当 征空间(C 且仅当其幂级数展开式k(t)=∑0ant中所有系 数an≥0.对于有限维的空间,条件可以稍微减弱 输入数据 图1多核函数线性组合合成示意图 当前已经仔在较多的满足 Mercer条件的核函rig. 1 Sketch map of composition using multiple kernel 数,常见核函数通常可分为两类:局部核和全局核6 ar 而局部核选择不同的核参数,又可分为大尺度核与 小尺度核.在一些复杂情形下.同时考虑核机器分 下面呆用公式的形式对上述线性组合合成核进 类、回归性能和泛化能力,将不同核组合使用,将是行描述.假定k(x,2)是已知核函数,k(x,2)是它的 更合理的选择 归一化形式,例如核函数k(x,z)可以采用如下方法 进行归一化:√k(x,x)k(z,x).采用以引入的符 2基本多核学习:合成核方法 号,可以定义以下几种合成核: 将不同特性的核函数进行组合,获得多类核函 a)直接求和核( Direct summation kernel) 数的优点,可以得到更优的映射性能.并且,典型的 学习问题经常涉及到多种或者异构的数据,多核方 k(,2)=∑k(x,2) 法可以提供更佳的灵活性.此外,它可以作为一种巧 妙的方法来解释学习结果、使得应用问题可以得到 b)加求和核( Weighted summation kernel) 更深入的理解.这就是多核学习的一类基本方法,即 合成核方法 k(x,2)=∑(,2,≥0,∑月=1(6) 2.1合成核的构造 1)多核线性组合合成方法 c)加权多项式扩展核( Weighted polynomial 多核学习最早从生物信息学领域得到应用和认 extended kernel 同.如 Pavlidis等20在2001年就研究了基于异构 k(x,z)=ak1(x,2)+(1-a)k2(x,2)(7) 1010 自动化学报 36卷 其中.k(x,2)是k(x,x)的多项式扩展 是,该合成核矩阵的大小为(s×n)×(s×n),而原 近来,这类合成核法又得到一些改进,在图始核矩阵的大小都是n×n,由于合成核矩阵是原始 像目标的识别领域得到广泛应用.如在金字塔框架核矩阵规模的§倍,因此样本特征必须被复制,使运 对日标形状进行多核表示阿,或釆用多核方法,算量成倍增加 自动获得基」决策的一种相应目标类别的稀疏依赖 3)其他改进合成核方法 图,实现了多类目标联合检测③2].提高了目标的识 近年来,针对多核学习中核函数的选取以及杖 别率.通过同时考虑多核线性组合的稀疏性和分类值系数的改进,又出现了一些新的多核合成方法, 器的强判别力,将多核学习问题转化为不同的优化如: 问题58.63,或通过多对象描述子、多特征空间的整 a)非平稳多核学习 合,并进行快速求解64.此外,合成核方法在特征提 前述的多核线性组合方法都是对核函数的平稳 取、处理及应用7、分类972-4、图像分割、组合,即对所有输入样本,不同的核对应的权值是 系统辨识等方面又得到了一些成功应用 不变的.无形中对样本进行了一种平均处理. Lewis 2)多核扩展合成方法 等吲提出了一种多核的非平稳组合方法,对每个输 述合成核方法都是试图通过一种求和“平均入样本配以不同的权值系数.如常规SVM判别函 化”的思想42来实现不同核矩阵融合.然而,这里数为 存在个丢失原始核矩阵信息的风险.比如,如果数 据集的局部分布是多变的.不同的核处理不同的区 f(c)=∑0r,m)+b(1 域会得到更好的结果,对不同核函数采用平均的方 法将丢失刻画这些局部分布的性能.为了实现核矩 引入不同的加权系数,典型的合成核SVM的 阵的组合而不丢失任何原始信息,可以考虑将多核判别函数可以改写为 矩阵进行扩展合成42],新的核矩阵由原核矩阵和其 他不同的核矩阵共同构成.在这个更大的核矩阵中 原核矩阵仍然存在.因此,原始核函数的性质得以保 ∫(x)-∑m∑k(x,x)+b(1 留.该合成核矩阵的形式为 而对于非平稳的合成核SVM,其判别函数改进 11K1,2 K 为 2.2 K ∑a:∑()k(c;,m) (12) K1 K 可以看出,原始核矩阵位于新矩阵的对角线上在最大熵判别( Maximum entropy discrimination, 其他所有元素是定义为(Kn)3=Fn(m,)的MED)框架下,通过使用一种大间隔隐变量生成 两个不同核矩阵的混合,可由如下公式求得(以两个 模型,使得隐参数估计问题可以通过变化边界和 高斯核为例) 一个内点优化过程来表示,并且相应的参数估计可 以通过快速的序列最小优化( Sequential minimal optimization,SMO)算法实现.通过多种数据集的 4:4 + (9)实验验证,非平稳的多核学习方法具有更好的通用 性. 很明显,当p=p时,Kp=kn b)局部多核学习 实验结果显示,当数据集具有变化的局部数据 此后,仍旧是针对多核学习在整个输入空间中 分布时,这种合成核方法将是更好的选择此外,通对某个核都是分配相同权值的问题,G6nen等0 常核组合方法在很大程度上依靠训练数据,并且必利用一种选通模型( Galing nodel)部地选择合 须道过学习获取一些权系数,以标识每个核的重要适核函数,提出了一种局部多核学习算法在SVM 性.而在护展合成核方法中,这些核函数的重要性可框架下,其判别函数形如 以直接从支持向量机的训练过程中导出.由此,分别 对应不同核的权系数可以通过一个单独的分类尜优 化过程整体得到.并且该优化过程不会像其他加权 ∑q∑(x)k1(x;xm/r)+b(13) 核方法那样,由于在优化权系数和训练分类器过程 中两次仗用训练数据而产生训练数据的过拟合.但其中,7z(x)是选通函数,其定义形式为 8期 汪洪桥等:多核学习方法 1011 7(c) exp((vm, )+Umo) (14)详细阐述了应用于合成核的列生成 Boosting方法 并成功推广到分类和回归问题 ∑ep(,x)+"l 2)二次约束型二次规划 从数学形式上看,二次约束型二次规划是一类 这里的tm和tm是选通模型参数,可以在多核学习 目标函数和约束同为二次函数的优化问题 过程中通过梯度下降法获得.将局部选通模型和基 于核的分类器相结合,优化问题可以用一种联合的 方式加以解决.局部多核学习方法获得了与多核学 习近似的精度,但只需要存储更少的支持向量.基于 st.Px+qx+r;≤0,i=1,2,…,m 此, Christoudias等又提出了一种基于 Bayesian Ar=b 的局部权值求取方法,以使学习过稈能适应人规模 (1 的数据集 这里,P,B1,…,Pn是n×n矩阵,优化变量x∈ c)非稀疏多核学习 R;如果P1,…,Pmn均为0矩阵,则约束变为线性 大部分合成核方法都有式(6)的形式,即对多核的,该问题实际变为一个二次规划问题 系数的约束是一种1范数的形式,以提高核组合的 Bach等针对多核矩阵和分类器系数锥组合 稀疏性.稀疏性的提高在一些情况下可以减少冗余,问题的联合优化,提出了Q(QP的-种新对偶肜 提高运算效率.但当某个问题多个特征编码间具有式,把它作为一个二阶锥规划,可以利用 Moreau- 正交性,稀性可能导致有用信息的丢失和泛化性 Yosida正则化来生成SMO方法的适用形式.实 能变弱.Klof等通过对系数引入一种l2范数约验结果显示这种基于SMO的算法比常用工具箱中 束,即‖2=1,提出了非稀疏的多核学习方法.虽应用的内点法更有效,广泛应用于支持向量回归问 然在此约束下,名核组合形式是非凸的,但通过使用题1 二范数‖|2=1边界上的值,可以得到一个紧致的 3)半定规划 凸近似,这就保证了核矩阵的严格正定性.通过在大 通过在一个核矩阵中综合考虑训练数据和测试 规模数据集下与C1范数和常用多核学习( Multiple数据, Lanckrict等田通过半定规划技术实现了核 kernel learning,MKT)方法进行对比实验,仿真实矩阵的学习问题,也为合成核模型提供了一种功能 验结果显示2-MKL在抗噪声和特征集冗余方面具强大的渐进直推式算法,该算法被成功应用并推广 有较强的鲁棒性.此后,Klo等刚又将O2范数约到蛋白质功能预测0.其考虑的核矩阵具有如下形 束推广到任意C范数,p>1,进步增强了核机器式 的通用性和鲁棒性 Ktr Ktrt 2,2合成核机器的学习方法 Kr Kt 为了求取合成核的参数,通常是将合戊核与支其中,K一(x)重(x;),1-1,…,mu,m+ 持向量机方法相结合,然后将目标函数转化成不同1,…,m1+nt:这里nt和m是有标号的训练样 的优化问题,如不同的正则化形式或对训练样本本个数和无标号的测试样本个数.我们的目标是 的一些约束,通过不同的优化方法进行求解.基于通过优化关于训练数据块Kt的损失函数,学习得 此,出现了多种合成核机器的学方法 到最优的混合数据块矩阵Kr和测试数据块矩阵 1) Boosting方法 K1即利用有标号的训练样本米预测测试样本的类 早期受集成思想和 Boosting方法的启发,别,也就是说,作者认为在训练的过程中同时考虑训 Bennett提出了一种多自适应国归核( Multiple练样本和测试样本,可以找出最佳的核矩阵.但这 additive regression kernels,MARK)算法.MARK样产生的问题是,求解核矩阵的搜索空间也相对变 定义了一种异构核模型,并考虑一个大规模核知阵大,为了避免过学丬( Overfilling), Lanckriet利用 库( Library),这个库由不同的核函数和其参数构成.限制核矩阵的迹为一常数米控制,于是有了约束式 通过使用一种梯度 Boosting列生成方法, MARK tr(K)=C 构建出异构核矩阵的每一列,然后将其添加到合成 半定规划是一种凸优化问题( Convex opti- 核中.算法的目标就是在这个核矩阵库的基础上,找 mization problem)∞o,它有一个线性的目标函数 到一种构建推广模型的方法.这种方法推广性强,不( Alline objectives lunction)、有限个线性矩阵不等 需要存储大量的数据米应对后续的预测,提高了预式约束( Linear matrix inequality constraints)以及 测的效率在此基础上,通过与SVM结合,Bi等17有限个线性矩阵等式约束( Affine matrix equality 1042 自动化学报 36卷 constraints),其标准形式如下 如回归问题、一类分类(奇异检测)问题等.实验结 果显示该算法可以有效增强模型的自动选择能力 min c u 并能提高学习结果的解释性.同时能有效应用于数 S.t.Fy()-Fd+uFi+,.+ugFg20 十万个样本和数百个核的大规模组合优化问题.这 7=1,…, 种半无限线性规划相比其他方法明显提高了学习速 度,适宜于解决大规模问题.特别是当SVMs与·些 Au= b 已出现的字符串核( String kernel)相结合, String (17) kernel也是一种有效的核方法,它根据两个字符串 其中向量t是最优化目标,F F是n×n的的所有公共子串计算它们的相似度,利用这些核对 对称矩阵.F(a)是一个半正定阵,上标j表示特征的稀疏映射,使得我们可以训练一种字符串核 可能有1全1个约束式:满足此约束式的所构成sVM,并应用于计算生物学中的千万级样本的数据 的集合是一个凸集合.A是一个行数与长度相同,片段24在此基础上,7iem等提出了一种应用于 列数与b长度相同的矩阵表示有限个等式约束式联含特征映射的多核学习方法,为多兴分类问题的 因此,半定规划是在对称且半正定矩阵的凸子集合多核学习提供了一种史方便和原理化的途径.通过 ( Convex subsct)卜:求解凸函数的最优化问题 针对多核支持向量分类问题,通过定义一种对一种凸Q(QP以及两种 SILPs在数据集上进行 比较,实验结果显示 SILPS比QCQP在速度上更 能指标( Performance iudex)u(K),基于原始一对有优势 终可以转化为一个标准的半定规划形式 5)超核( Hypcrkcrncls) 对基于核方法的支持向量机而言、如何选择一 个合适的核函数实现自动的机器学习是一个很大的 min t ,t,入,υ,6 挑战Ong等3通过定义一种核空间上的再生核 t.tr|∑F Hilbert空间,即超再生核 Hilbert空间,并引入超 核的概念及构造方法,在更广义的层面上实现了这 ,K;≥0 目标 定义1(超再生核 Hilbert空间, Hyper re producing kernel Hilbert space).改Ⅹ为非 3.tr e-tU 8+ xy 空集合,Ⅹ:ⅩxX是复合指标集,H为函数f:X →R的 Hilbert空间,该函数可表示为该空间中两 (e+-6+入y)1t-26Ce 个向量的内积,且其范数f=√f,f,则被 0>0 称为超雨生 Hilbert空间,如果存在一个超核k:x 6>0 X→R具有如下性质: (18 再生性:对所有∫∈丑,有(k,),/) 其中,t是引入的一个替代变量( Auxiliary vari-f(x),特殊地,(k(x),k(,x2)-k(xx ablc),v,6,A是引入的 Lagrangian乘子,至此,可 b)k张成整个空间H,即H 以通过标准的半定规划求解方法得到B及相应的span()(X Lagrangian乘子,半定规划具有很高的泛化能力 c)对仟一固定的(X,超核k是关于其第 线性规划( Linear programming,LP)以及QCQP二个输入的核函数,即对任一固定的x∈X,函数 问题都可以转换推广成半定规划门题然后可以很k(x,x)-kx,(x,x),x,x′∈是一个核函数 容易地使用内点法( Interior-point method)加以解 在超再生核 Hilbert空间上,可以用类似于止则 决 化品质函数的方法.得到一个从训练数据对核进行 4)半无限线性规划 学习的推理框架.对超核的学习,可以通过定义 Sonnenburg等B7在多核矩阵锥组合的基础上,个被称为品质函数( Quality functional)的量(类似 提出了一种通用而更有效的多核学习算法.该方法于风险函数)来实现,这个量可以衡量核函数“非良 将Bach等的QCQP对偶形式改写为一种半无限( Badness”的程度 线性规划(Semi- infinit ite linear program, SILP)形 定义2(正则化品质函数, Regularized qual- 式,新的规划形式可以在标准的SVM应用问题中, ity functionality).设X,Y分别是训练测试样本 利用成熟的线性规划方法进行求解.并且,通过将组合和样本标签,对X的一个半正定核矩阵K, 此形式进行推广,算法能有效解决更多类型的问题,其正则化的质函数定义为如下形式: 8期 汪洪桥等:多核学习方法 1013 g(,x,Y)=9mp(k,X,Y)+2‖(1 7)分组Laso Lasso回归是目前处理多重共线性的主要方法 这里,≥0是一个正则化常数,h表示空间之一,相刘于其他方法,更容易产生稀疏解:在参 H中的范数,Qm(k,X,Y)是一种经验品质函数,数估计的同时实现变量选择,因而可以用来解决检 它表示核函数k与某一特定数据集X,Y的匹配程验中的多重共线性问题,以提高检验的效率.Laso 度,该函数的值常用来调整k以使得gm最优(如:可以推广为分组Laso( Group lasso),从而使得 最优核目标度量) 模型的解可以保持组稀疏性和层次性.Bach26·关 引理1(再生核 Hilbert空间的表示定理,注于分块1范数正则化的最小二乘回归,即分组 Representer theorem for hyper-RKHS).设Las0o题,研究了其渐进模型一致性,推导出了分 X为非空集合,Qmp是任意经验品质函数,X,Y组Laso-致性在一些实际假设下的充要条件,如 分别是训练测试样木组合和样木标签,则每一个最模型误定.当线性预测器和欧氏范数(2范数)用函 小化正则化品质函数g(k,X,Y)的k∈Ⅱ具有数和再生核 Hilbert,范数代替,这就是常说的多核学 以下的一种表示形式 习问题.通过使用函数分析工具和特定的协方差算 ,将上述一致性结果推广到无限维情形,同时提出 k(x)=∑月12(m,m),(m,m1),,x∈x 种自适应方法来获得一致性模型的估计,即使 2,7 在非适应方法必要性条件不满足的情况下也能适用 (20)为多核学习间题提供了一条新的途径 对每一个1≤i,≤M,这里B;∈R 2.3其他合成核参数学习方法 根据超再牛核 Hilbert空间的表示理论可知,由 超核构造的决策函数不仅由某一个单核构成,而且 从最简单的多个核直接求和到上述的各种改进 还由多核之间的一个线性组合构成,因此具有更优合成核构造方法,多核学习经历了从经验性选择 的性能在分类、回归以及奇异检测等方面的实验证运用多和优化方法求解的过程但针对一些具体间 实了该方法的有效性B.8,拓展了多核模型选择与题,对核参数的选取,多核权系数的设定,目前还没 合成的研究途径 有形成一个合理统一的模式.常用的方法只能是凭 6)简单MKL 借经验、实验对比、大范围的搜索或通过交叉验证 从Bach等的多核学习框架36出发, Sonnen- 等进行寻优.在这种情况下,也出现了其他的些方 bug等提出了种通用而更有效的多核学习算法,实现了多核学习问题,典型的有 法37,该方法通过迭代使用现有的支持向量机代 1)基于智能优化方法的多核学习 码,从一个新的角度解决了人规模问题的多核学习 这类方法主要通过一些比较成熟的智能优化 然而,这种迭代算法在收敛到一个合理解之前,需要方法,建立目标函数,寻找该函数极值的过程就是 过多的迭代运算. Rakotomanonyy等27用一种自合成核参数寻优的过程如采用多项式核与径向 适应的C2范数正则化方法米考虑多核学习问题,每基核的合成核2作为支持向量机的核函数k 个核矩阵的权系数被包含在标准SVM的经验风险2-(1-p)km,将其用SVM进行预测过程中 最小化问题中,并采用(2约束以提高解的稀疏,的参数向量(d,o,,p)作为粒子,其中d为多项式 然后采用了一种基于分块1范数正则化的算法来解核参数,为径向基核尺度参数,y为SVM调整参 决这一问题,为多核问题提供了一个新的视角,并且数,p为合成核的权重参数,利用粒了群算法对该合 证明了该方法与Bach等的方法是等效的.从上运成核的参数进行优化,最终找到最优的预测结果 描述可以看出,除了学习合成核外,该与法解决的是 2)基于核目标度量的多核学习 个标准的SVM优化问题,这里核的定义形式为 核度量434是两个核函数之间或核函数与目 多个核的线性组合. Rakotomamonjyl称之为简标函数间的一个相似性度量,在多核矩阵信息融合 单多核学习( Simple MKL)在加权的2范数正则方面得到了应用,其概念最早由 Cristianini等提出 化形式下,同时对多核权系数进行一个额外的1范考虑一个两类分类数据集S={(x,1)}=1,其中非 数约束,为多核学习提供了一种基于混合范数正则∈{+1,-1},则在数据集S下,两个核矩阵之间的 化的新思路.简单多核学习可以从两类分类问题向核度量定义为 其他方向扩展,如回归、类、一类分类(奇异检测) A(S,K1,K2) (K1,K2) 以及多类分类问题,具有很强的通用性,并且与其他 (21 √k1,K1)F(K2,k2)F 多核学习算法相比,该算法收敛速度更快且效率更 这里,(K,Ka)F=>1-1Fn(x2:)(x,T)通 1044 自动化学报 36卷 过上式,对应于S的核矩阵K的性能可以通过A ;-2,t-0,1,2, 值米量度,如:A(5,K,G),这里的G是基于特定任 务的理想核G=y,其中y=m12…,.基 另一种典型多尺度核为小波核函数( Wavelet kernel function) 831 于对目标核的度量原珥,通过使用不同的核函数,或 定理1.令h(m)是一个小波母函数,a和c分 者调节不同的参数值,可以产生一组核矩阵.然后,别表示仲缩和转移因子,a,∈R如果x,z∈R 对该度量值的最大化执行半定规划或其他学习方法,则内积型小波核函数可表示为 以得到一个对不同核矩阵加权组合的最优核 3多个尺度的多核学习:多尺度核方法 k(2)=江4( 合成核方法虽然有了一些成功应用,但都是根 据简单核函数的线性组合,生成满足 Mercer条件的转移不变小波核函数为 新核函数;核函数参数的选择与组合没有依据可循, 对样木的不平坦分布仍无法圆满解决,限制了决策 k(a, z)= ( 函数的表示能力.在此情况下,山现了多核学习的 种特殊化情形,即将多个尺度的核进行融合.这种 定理2.考虑具有一般性的小波函数 方法更具灵活性,并且能比合成核方法提供更完备 的尺度选择.此外,随着小波理论、多尺度分析理论 h(x)=cos(1.75x) 25 2 间使其其有了很好的且论录这类方法目箭也如果x2(R",则小波核函数为 得到了很好的利用,烘型的如 Kingsbury等③2将多 个尺度大小的核进行分光heng等B到、 Yang k(a,2)=h(x二 等834提出了多尺度支持向量回归.分别用于非平坦 i=1 数的估计和时序列预测.此外,通过进一步将多 ∏1c015(n-2) C一之 尺度核与支持向量机结合.多尺度核方法在基于回 归的热点检测48和图像压缩49等方面均得到了应 (26 用.近来,结合多尺度分析方法,基于 Hilbert空间通过仲缩因子a的变化,即可得到不同尺度的小波 中的再生核进行函数重构得到了重视并进行了 相关的应用研究;此外,多尺度核方法又逐步推广到核函数 了高斯过程的健模与处里-27,这对基于核方法3.2多尺度核的学习方法 的机器学习又是一次大的扩展 1)多尺度核序列学习方法 3.1具有多尺度表示能力的核函数 对多尺度核的学习,很直观的思路就是进行多 尺度核的序列学习.多尺度核序列合成方法32简单 度表示能力的核函数.在被广泛使用的核函数中,高理解就是先用大尺度核拟合对应决策函数平滑区域 的样木,然后用小尺度核拟合决策函数变化相对剧 斯径向基核 烈区域的样本,后面的步骤利用前面步骤的结果,进 k(a, a )=cxp (22 行逐级优化,最终得到更优的分类结果 考虑一个两尺度核k1和k2合成的分类问题 是最受欢迎的,因为它们具有通用普遍的近似能力,我们要得到合成的决策函数 同时它也是一种典型的可多尺度化核.以此核为例 f(x)=f1(x)+f2(x) 将其多尺度化(假设其只有半移不变性): k(-22 这里 2 2a f()=∑ak1(xn,)b2 其中.σ1<…<Om可以看出,当σ较小时,SVC (28 可以对那些剧烈变化的样本进行分类;而当σ较大 f2(x)-∑k2x1x)+b2 时,可以用来对那些平缓变化的样木进行分类,能得 到更优的泛化能力.具体实现时,σ的取值可以借鉴 设想k1是一个大尺度的核函数(如σ较大的径 小波变换中尺度变化的规律,a可由下式定义: 向基函数),相关的核项系数αz选择那些决策函数 8期 汪洪桥等:多核学习方法 1015 f(x)光滑区域村应的支持向量;而k2是小尺度核函数f(v),其中,u是由2n个组合核参数构成的向量 数,核项系数β;选择那些决策函数∫(x)剧烈变化(a1,%,a2,,…,an,"n),我们的目标就是找到 区域对应的支持向量.具体方法是:首先通过人尺个合适的v.使得∫(v)最人.其核心就是通过对解 度的单核k1构造函数(x),这样,该函数可以很好向量进行组合、变异、选择,在设定的进化代数内不 地拟合光滑区域,但在其他地方存在显者误差,可以断求取并更新目标函数,最终得到∫(u)的最大值 使用相对较小的松弛因了来求取α;然后,在f1(x 基础上使用小尺度的核k2构造几2(m)使得联合函4从有限向无限核的扩展:无限核方法 数f1(m)J2(x)比∫(m)具有更好的拟合性能,这 前述的合成核与多尺度核方法都是在有限个核 种方法实际上是多次使用二次规划以实现参数的获函数线性组合前提下加以讨论的.但对一些人规模 取,运算复杂度较高,同时支持向量的数量大量增问题,基于有限个核的多核处理方法不一定有效,多 加 核融合的决策函数的表示能力也不能达到处处最优; 近来, Cortes等2关注于序列核函数学习问此外,在一个多尺度核函数族中,有限个核函数的选 题,提出了一种学习合理核函数的通用形式,并且证择并不唯一,并且其不能完备地表征这个核函数族 明这个大的合理核函数族可以通过结合支持向量机因此,将有限核向无限核的扩展也是一个重要的方 目标图数和核脊回归的一种简单二次规划加以解决,向 这种方法提高了先前出现的·些学习方法效率.如 早在2006年, Argyriou等同关注于监督学习 SDP、QCQP此外,对于核脊回归这种特定情形,中的核学习问题,提出了一种多核学习的新方法,该 给出了基于最优核矩阵封闭解的一个替代解,该方方法可以从由多个基本核函数的合法集合所构成的 法成功应用到了分类和回归问题. 个凸壳中找到某个核,使其能最小化凸正则化函 2)基」智能优化的多尺度核学习方法 数.与其他方法相比,这个方法有一个独有的特征, 与合成核类似,针对多尺度核学习问题,另一类即上述基木核的个数可以是无限多个,仅仅需要这 重要的方法仍是基于多核的整体智能优化.如:利些核是连续参数化的.例如:基本核可以是各向同 用EM算法训练多尺度支持向量回归( Multi-scal性、方差规定为一定间隔的高斯核,甚至可以是通过 support vector regression, MS-SVR.这种方法起对多个连续参数进行参数化的高斯核尽管这个优 源」非平坦图数的估计间题,它采用多种尺度的化问题是非凸的,但它属于更广范畴的凸函数差分 核函数,使得较小尺度的核可以拟合快达变化,而较(D) iference of convex functions)规划问题,因此 大尺度的核可以拟合平缓变化基于此,文献84可以应用最新的凸函数差分优化理论加以解决 提出了两种迭代的EM训练算法,它们分别以渐进 在此基础上, Geller等39更侧重于用半无限规 的方式实现了1范数和0范数:通过限制基函数的划解决来自通用核类型的核函数学习问题,并设计 数目从而限制了模型的复杂性,同时解的稀疏性大 种新的算法,称为无限核学习( Infinite kernel 大加快了训练过程,也节约了大量的测试时间并且 earring,IL).IKL算法既适用于无限也适用」有 MS-SVR的优化目标函数是全局的,可以直接求得限核情形,并且在大量核情形下,它比 Simple mKl 所有m个核项系数a;文献5]提出了一种多尺算法更快也更稳定.通过将IL和MKL应用于 度径向基核参数选择的进化策略,用于支持向量机sM对人量数据集进行实验发现:在一些数据集 的训练.该算法针对多尺度高斯核函数的组合形式 ,由于核函数族中核的大幅增加,IKL可以比 SVM/MKL大大提高分类正确率,在这些情况下 需,y )=∑ak(xy,7) (29)IKL能保持它的实用性,而交叉验证和MKL都是 不实用的 k(a, y r2)=exp(vills-y (30 此后,针对有限核的凸组合受限于选择的有限 性问题, Onogur- Akyiiz等又提出了一种基于无 这里有2个参数需要确定,分别是〃个权重参数限和半无限优化的无限核组合新方法,核的组合可 和n个径向基核的宽度a1Y,讠-1,……,n.这些以通过同伦参数( Homotopy parameter)或更特殊 参数值的确定会影响到组合核的性能,也最终会影的参数来实现.考察所有来自无限核集合中核的极 响分类精度.具体方法是将样本集中的总训练样本小良凸组合,可以发现:于组合,间隔最人化是在 分成数量相等的几份,如5份,任意选取其中的4份个紧指标集( Compact index set)下的无穷多个 作为训练样木,可以训练得到5个分类器,分别以约束和一个额外的整数约束条件下实现的.通过在 剩余的1份作为测试样本,可以得到5个分类结果.概率测度( Probability measures)空间的参数化,该 将这5个分类结果(正确率)的平均值作为目标函问题变成了一个半无限问题,可以通过半定规划方 1016 自动化学报 36卷 法加以解决 等3】近米提出的一种更广义的核理论,在核函数的 构造方面也是一种重大创新.必将成为这一领域 5总结与展望 个新的热点,其理论体系还有待进一步完善与扩展 核方法在模式回归、分类以及概率密度佔计等 3)多核学习方法逐步问人规模数据集的应用领 方面都有大量的理论分析和成功应用.针对单核函域扩展对于一些规模较小的数据集(虽然通常核 数的弊端,多核方法已经成为当前核机器学习的热机器学习向题考虑的就是小样本情形),多核方法采 点.特别是在解决一些复杂问题时,多核方法具有更用这些组合操作和学习方法并不会遇到太大障碍 优的性能.基于此,也出现了很多相关的多核机器学但对于一些大规模问题,由于涉及到多核矩阵的快 习方法,这些方法为多核紅阵的融合提供了多种更速求解,高维多核扩展矩阵的各种分解等处理,常 优性能的解决途径,同时一些方法还能有效解决大规的多核学习方法的学习效率会非常低下.利用支 规模问题.可以预见,多核方法必将在核 Fisher判持向量机以及各种改进方法,虽然当前L经出了 别分析、攴持向量机、相关向量机、奇异检测、核聚一些基于大规模问题的学习算法,如 Boosting方 类分析等方向得到不断推广,并在诸如时间序列(动法、QCQP、SDP或一些分级方法1等,但这些 态系统、财经等)预测、信号和图像的滤波、压缩和方法在学习速度方面仍然有待提高 超解析( Super-resolution)、故障预报、文本分类 4)多尺度核方法具有更优的研究基础和前景 图像处理、目标检测、视频跟踪、生物信息学(双螺随着尺度空间理论和小波理论的不断完善,多尺 旋、基因序列数据的分类、蛋白质功能预测等)等领度/多分辨分析方法得到了认同和推广.多尺度核由 域得到广泛应用 于具有较为统一的模型形式和丰富的尺度选择,使 多核学习方法已经得到了广泛认同和成功应用,得它在处理复杂问题时有很大的优势,特别是如高 必将成为今后的理论研究热点和有效的模式分析工斯核这种具有强映射能力的核函数(能将样本空间 具,以卜总结其进一步的儿个研究方向 映射到无穷维的特征空间).因此,多尺度核方法的 1)除了常规的回归、分类等应用领域,核方法 种有效解决方案是引入尺度空间,构成具有多分 的热点还包括核密度佔计、子空间分析、用于冋归辨分析能力的增广特征空问、获得决策函数的多分 或分类的特衎选择等.同样的,合成核与多尺度辨表示期望在这些特征空间所组成的一个增广空 核方法在这些领域也大有用武之地.如用于两类、间中,构造新的全局优化问题,找到一个融合了它 多类分类问题最优贝叶斯决策面的获取,改进的核们各自优势的史好的解.它的难点在于如何构建 主成分分析等.此外,在当前机器学习的些热门套完备的多分辨分析的核函数空间理论,并应用到 领域.如多示例学习閃η、半监督学习、非监督学习等支持向量机的快速实现.这里可以设想采用标准化 方向.多核方法也得到了一些研究和应用.典型的如尺度核函数的构造,期待多尺度特征增广空间解的 Kembhavi等8提出了一种多核方法的增量学习算快速求取,此外,多尺度核是有限个向无限个核函 法,并将其用于目栎识别.黎铭等应用多核理论,数扩展的基础对于如何解决多个尺度核分步执行 提出了基于多核集成的在线半监督学习方法 OMike带来的支持向量个数急剧增大的问题,可以考虑构 ( Online multi-kernel ensemble),能够有效利用大建新的基于多尺度合成核的全局优化问题,采用迭 量未标记数据提升在线学习性能Zhao等m研代的方法,获取基于非传统意义下的稀疏的支持向 究了基于最大间隔的多核聚类方法.牟少敏等2针量10.除此之外,还可以将不同多尺度核进行合 对实际应用中经常出现的昇类数据源和多核函数带成,研究多尺度合成核方法,如高斯核与小波核,进 来的计算量增加等问题,提出了一种利用协同聚类步增强决策凶数的多尺度分辨与表达性能 对多核支持向量机的训练数据进行简化的方法,大 5)当前的一些多核学习方法,还存在大量未解 人减少了支持向最的数目,从而减少了计算量,并且决的问题,阻碍了多核方法的进一步推.如根据简 还不会影响分类精度 单核函数的凸组合,生成满足 Mercer条件的新核函 2)核函数的构造一直是核机器学习的一个难数,它在核数的选择与组合上没有依据可循;如何 点.针对具体应用问题,如何选择或构造出最合适的处理好多个核之间的关系,采用多核学习方法确定 核函数,目前并没有完善的理论基础.多核方法通过系数时的效率问题,这些都有待进一步探索;此外, 多个或多种核函数的组合,从另一个角度解决了特通常合成核方法对样本的不平坦分布仍无法很好解 定核函数的构造问题,通过多个参数的学习与调节,次,限制了回归函数的拟合性能和分类决策函数的 使组合的核函数尽可能满足实际需求.因此,多核表示能力;多尺度核方法在尺度选取上没有完备有 方法是针对复杂问题,构造新的核函数与新的高效效的理论依据,并不是真正意义上的多尺度:用优 核机器3的一条实用途径此外,超核理论是Ong化方法进行参数选择和序列多人度方法,都会使学 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论