快速隨機(jī)多核學(xué)習(xí)分類算法

孫 濤，馮 婕

（西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710071）

快速隨機(jī)多核學(xué)習(xí)分類算法

孫 濤，馮 婕

（西安電子科技大學(xué)智能感知與圖像理解教育部重點(diǎn)實(shí)驗(yàn)室，陜西西安 710071）

多核學(xué)習(xí)是整合多個(gè)子核在一個(gè)優(yōu)化框架內(nèi)，從而尋求到多個(gè)子核之間的一個(gè)最佳線性組合，而且多核學(xué)習(xí)可以獲得比單核學(xué)習(xí)更好的分類性能.受極限學(xué)習(xí)思想的啟發(fā)，提出了快速隨機(jī)多核學(xué)習(xí)分類方法.當(dāng)滿足極限學(xué)習(xí)的理論框架時(shí)，可以在構(gòu)造核的過(guò)程中，對(duì)參數(shù)隨機(jī)賦值，構(gòu)造一種隨機(jī)核.可以縮減子核的規(guī)模，加快了多核學(xué)習(xí)的計(jì)算時(shí)間，并且節(jié)省了內(nèi)存空間，使得多核學(xué)習(xí)可以處理更大規(guī)模的問(wèn)題.另外，通過(guò)使用經(jīng)驗(yàn)Rademacher復(fù)雜度來(lái)分析多核學(xué)習(xí)的一般性誤差，從而獲得比原有多核學(xué)習(xí)更高的分類精度.結(jié)果表明，與經(jīng)典的快速多核學(xué)習(xí)算法相比，文中提供的算法計(jì)算更快，占用內(nèi)存空間更小，分類精度更高.

多核學(xué)習(xí)；極限學(xué)習(xí)；隨機(jī)核；經(jīng)驗(yàn)Rademacher復(fù)雜度

核學(xué)習(xí)是機(jī)器學(xué)習(xí)中的重要領(lǐng)域.在分類問(wèn)題中，如果不同種類的數(shù)據(jù)混雜在一起，在當(dāng)前維數(shù)空間內(nèi)，可能無(wú)法找到一個(gè)分類面對(duì)它們加以區(qū)分.此時(shí)，就需要把原始數(shù)據(jù)通過(guò)一個(gè)映射函數(shù)投影到髙維空間，在髙維空間內(nèi)把它們區(qū)分開(kāi).這種方式稱為核學(xué)習(xí)，又稱為核技巧［1］.核學(xué)習(xí)因?yàn)槠湓诮鉀Q線性不可分問(wèn)題上的卓越性能，被廣泛應(yīng)用于分類算法［2-4］.多核學(xué)習(xí)（Multiple Kernel Learning，MKL）［5］是核學(xué)習(xí)新的研究熱點(diǎn).當(dāng)對(duì)一個(gè)目標(biāo)樣本進(jìn)行分類時(shí)，該目標(biāo)可能呈現(xiàn)出多種特征，需要從中選取出最適合分類的特征.多核學(xué)習(xí)可以把每一種特征都構(gòu)成一個(gè)單獨(dú)的子核，然后把多個(gè)子核放到一個(gè)統(tǒng)一框架內(nèi)，從而選擇出最合適的子核組合，即選出最合適的特征來(lái)進(jìn)行分類.與其他特征選擇算法相比，多核學(xué)習(xí)可以把特征選擇問(wèn)題轉(zhuǎn)變成一個(gè)凸優(yōu)化問(wèn)題，從而采用經(jīng)典優(yōu)化得到最優(yōu)解.

多核學(xué)習(xí)往往可以取得比單核學(xué)習(xí)更好的結(jié)果，但是相對(duì)應(yīng)的是時(shí)間復(fù)雜度和空間復(fù)雜度的增加.自從多核學(xué)習(xí)算法提出以來(lái)，研究者們就熱衷于如何提高多核學(xué)習(xí)的計(jì)算速度.早期，Bach等［6］把多核學(xué)習(xí)問(wèn)題轉(zhuǎn)變成二次錐形規(guī)劃問(wèn)題來(lái)求解，在算法復(fù)雜度上得到一定的降低，但依然不是很理想.后來(lái)，Sonnenburg等［7］使用最小最大化模型來(lái)描述多核學(xué)習(xí)問(wèn)題，用交替優(yōu)化的方法來(lái)求解，大大加快了算法的計(jì)算時(shí)間.在這個(gè)模型的基礎(chǔ)上，研究者們?yōu)榱诉M(jìn)一步加快優(yōu)化速度，相繼提出了梯度下降的方法［8］、基于Lasso的方法［9］和解析優(yōu)化的方法［10］.

上述多核學(xué)習(xí)的加速算法，都是著重于如何建立更快的優(yōu)化模型，從而加快優(yōu)化速度.筆者則考慮通過(guò)縮減子核的規(guī)模來(lái)達(dá)到加速的目的，并從極限學(xué)習(xí)機(jī)（Extreme Learning Machine，ELM）［11-12］得到了啟發(fā). ELM以單隱層前饋神經(jīng)網(wǎng)絡(luò)為平臺(tái)，提供了一種無(wú)需參數(shù)調(diào)節(jié)的分類方法.按照ELM理論的描述，如果隱層節(jié)點(diǎn)的數(shù)目足夠多，在隱藏節(jié)點(diǎn)的權(quán)重隨機(jī)賦值的情況下，給定一個(gè)在任意區(qū)間無(wú)限可導(dǎo)的激活函數(shù)，SLFN就可以無(wú)限逼近擬合輸入樣本集.如果減少了子核的規(guī)模，不僅加快了優(yōu)化的速度，而且節(jié)省了內(nèi)存空間，使得筆者的方法可以處理更大規(guī)模的問(wèn)題.

另外，通過(guò)使用經(jīng)驗(yàn)Rademacher復(fù)雜度［13］來(lái)分析多核學(xué)習(xí)的一般性誤差，發(fā)現(xiàn)多核學(xué)習(xí)一般性誤差的上確界受到子核數(shù)目的影響.如果子核數(shù)目過(guò)多，誤差的上確界增高，從而導(dǎo)致分類精度的下降.隨機(jī)多核學(xué)習(xí)在保持訓(xùn)練誤差不變的同時(shí)，通過(guò)降低子核的數(shù)目降低了多核學(xué)習(xí)一般性誤差的上確界，從而理論上保證了文中方法可以獲得比原有多核學(xué)習(xí)更好的分類結(jié)果.

1 多核學(xué)習(xí)框架

在單核學(xué)習(xí)中，依據(jù)優(yōu)化的最終目標(biāo)不同，有支撐矢量機(jī)（Support Vector Machine，SVM）、核判別分析、核最近鄰等.當(dāng)單核學(xué)習(xí)變?yōu)榱硕嗪藢W(xué)習(xí)的時(shí)候，按照最終的優(yōu)化目標(biāo)不同，分為了不同的算法.由于SVM分類不用考慮數(shù)據(jù)的分布特性，有著更廣泛的應(yīng)用環(huán)境，所以，文中利用SVM給出多核學(xué)習(xí)對(duì)偶式的公式為

2 快速隨機(jī)多核學(xué)習(xí)

2.1構(gòu)造隨機(jī)核

在上節(jié)介紹了子核的參數(shù)設(shè)置對(duì)多核學(xué)習(xí)的時(shí)間和空間復(fù)雜度的巨大影響.如果有一種無(wú)需參數(shù)調(diào)節(jié)的核，就可以減少子核的規(guī)模，降低多核學(xué)習(xí)的計(jì)算時(shí)間和內(nèi)存存儲(chǔ).Huang等［11］提出了一種無(wú)需參數(shù)調(diào)節(jié)的分類方式:ELM算法.先回顧ELM的逼近擬合理論.

定理1 對(duì)于任意N個(gè)輸入樣本，給定一個(gè)在任意區(qū)間可以無(wú)窮可導(dǎo)的激活函數(shù)和L個(gè)隱藏層節(jié)點(diǎn)，對(duì)隱藏層節(jié)點(diǎn)的權(quán)重和偏差隨機(jī)賦值，ELM可以無(wú)誤差地逼近這N個(gè)獨(dú)立樣本.

給定一個(gè)含有L個(gè)隱藏層節(jié)點(diǎn)和M個(gè)輸出節(jié)點(diǎn)的單隱層前饋神經(jīng)網(wǎng)絡(luò).訓(xùn)練集x=（x1，x2，…，xN），含有N個(gè)樣本，每個(gè)樣本的維數(shù)是d，輸出結(jié)果是f（x）.G（ai，bi，xi）是滿足ELM理論的激活函數(shù)，其中，a，b都是隨機(jī)賦值的.βi是隱藏層的輸出權(quán)重，它滿足如下的公式:

其中，

H稱作隱層輸出矩陣，第i列表示輸入樣本在激活函數(shù)G（ai，bi，x）映射下的第i個(gè)隱層節(jié)點(diǎn)的輸出，T=［tT1，…，tTN］T，是訓(xùn)練樣本的類標(biāo).

由上文的介紹可知，當(dāng)輸入樣本被激活函數(shù)映射到一個(gè)L維空間后，通過(guò)一定的操作可以無(wú)誤差的逼近任何一個(gè)輸入樣本的類標(biāo).這意味著不同種類的樣本在這個(gè)L維空間內(nèi)是完全可分的.按照線性不可分問(wèn)題的解決思路:尋找一個(gè)髙維映射函數(shù)，把原始數(shù)據(jù)映射到一個(gè)足夠髙維的空間，把原來(lái)不可分的數(shù)據(jù)完全可分，而核矩陣就等價(jià)于髙維映射函數(shù)與它的轉(zhuǎn)置做內(nèi)積.在ELM中，如果把激活函數(shù)看作髙維映射函數(shù)，L維空間就是那個(gè)足夠髙維的空間，可以直接把激活函數(shù)和它的轉(zhuǎn)置做內(nèi)積K=H·HT來(lái)構(gòu)成核矩陣.由于在構(gòu)造核過(guò)程中的參數(shù)可以隨機(jī)賦值，不需要調(diào)節(jié)參數(shù)，所以稱之為隨機(jī)核.

2.2一般性誤差的理論分析

雖然隨機(jī)核的構(gòu)造加快了多核學(xué)習(xí)的計(jì)算速度，但是否會(huì)影響分類的精度依然未知.這里，通過(guò)對(duì)多核學(xué)習(xí)的一般性誤差分析，來(lái)判斷隨機(jī)核對(duì)分類精度的影響.

首先，回顧一下模式識(shí)別的一個(gè)重要理論.

定理2 F是一個(gè)定義在集合X上輸出為｛±1｝的函數(shù).P是在集合X上的概率分布.假設(shè)（X1，Y1），…，（Xn，Yn）與（X，Y）相對(duì)于P獨(dú)立同分布的，則F中的每個(gè)子函數(shù)f以概率至少1-δ滿足

其中，σ1，…，σN∈｛-1，+1｝，是獨(dú)立均勻分布的隨機(jī)變量.E代表著期望操作.利用McDiarmid不等式，F(xiàn)中的每個(gè)子函數(shù)f以概率至少1-δ滿足

其中，M是子核的數(shù)目.L代表?yè)p失函數(shù)（例如最小平方損失和hinge loss損失）.當(dāng)δ固定時(shí) （，ln（2/δ）/ （2N））1/2是一個(gè)常數(shù).

從文獻(xiàn)［10］的結(jié)論中，可以得到多核學(xué)習(xí)L1約束的經(jīng)驗(yàn)Rademacher復(fù)雜度為

其中，η0=23/22.R是一個(gè)滿足Km（x，x）≤R2的常數(shù).

假設(shè)L是一個(gè)關(guān)于ρ的損失函數(shù)，把式（6）代入式（5）中，可以得到

3 實(shí)驗(yàn)結(jié)果分析

胃癌每年在全球影響著大約800 000的人.胃癌的術(shù)前分期對(duì)于胃癌的治療具有非常重要的意義.當(dāng)前，腫瘤診斷系統(tǒng)是胃癌分期的一個(gè)標(biāo)準(zhǔn)系統(tǒng).其中的淋巴結(jié)診斷又是腫瘤分期的一個(gè)重要組成部分.淋巴結(jié)診斷為手術(shù)治療提供了非常重要的參考.

傳統(tǒng)上，淋巴結(jié)尺寸被用來(lái)作為淋巴結(jié)診斷的參考指標(biāo).后來(lái)，臨床醫(yī)學(xué)發(fā)現(xiàn)僅僅使用淋巴結(jié)尺寸是不足夠的.因?yàn)榇蟮牧馨徒Y(jié)可能是由發(fā)炎引起的.而那些不被關(guān)注的小淋巴結(jié)有可能是真正的轉(zhuǎn)移淋巴結(jié).所以，僅僅依賴淋巴結(jié)的尺寸，有可能形成誤判.多項(xiàng)生理指標(biāo)的組合使用就成為了淋巴結(jié)診斷的必然選擇.但是人的生理指標(biāo)有很多，哪些生理指標(biāo)是跟淋巴結(jié)診斷相關(guān)的，在臨床上還暫未定論.

在這里把生理指標(biāo)的選擇問(wèn)題轉(zhuǎn)變?yōu)橐粋€(gè)優(yōu)化選擇問(wèn)題.多核學(xué)習(xí)被用來(lái)求解這個(gè)問(wèn)題.每個(gè)指標(biāo)對(duì)應(yīng)著一個(gè)子核，那么優(yōu)化選擇子核的過(guò)程就等價(jià)于選擇最優(yōu)指標(biāo)的過(guò)程.經(jīng)過(guò)優(yōu)化求解以后，可以得到多個(gè)指標(biāo)的一個(gè)最佳加權(quán)組合，它就可以用來(lái)檢測(cè)淋巴結(jié)是否轉(zhuǎn)移.

該實(shí)驗(yàn)的實(shí)驗(yàn)數(shù)據(jù)來(lái)自北京大學(xué)醫(yī)學(xué)院癌癥研究中心.該數(shù)據(jù)包含1000個(gè)病例，每位病人擁有18個(gè)生理指標(biāo).它們分別是性別、年齡、腫瘤位置、腫瘤最大半徑、腫瘤厚度、腫瘤模式、腫瘤模式、漿膜入侵、入侵深度、博爾曼（Borrmann）類型、加強(qiáng)模式、淋巴結(jié)個(gè)數(shù)、最大淋巴結(jié)尺寸、淋巴結(jié)數(shù)目、最大淋巴結(jié)尺寸、淋巴結(jié)station、淋巴結(jié)的CT衰減、淋巴結(jié)的短徑與長(zhǎng)徑比、淋巴結(jié)分布、病理類型和血清癌培抗原（CEA of serum）.

對(duì)比實(shí)驗(yàn)包括簡(jiǎn)單多核學(xué)習(xí)［8］，基于Lasso的多核學(xué)習(xí)［9］和Lp范數(shù)多核學(xué)習(xí)［10］.使用RBF核，其中的核參數(shù)，提供了10個(gè)候選值［2-3，2-2，…，26］.因此，每個(gè)指標(biāo)對(duì)應(yīng)于有著不同核參數(shù)的10個(gè)子核.總共擁有18×10=180個(gè)子核.

對(duì)于隨機(jī)多核學(xué)習(xí)，每個(gè)指標(biāo)被用來(lái)構(gòu)造一個(gè)隨機(jī)核.激活函數(shù)，選擇RBF激活函數(shù).影層的節(jié)點(diǎn)數(shù)是2 000，總共有18個(gè)候選子核.每次運(yùn)行，隨機(jī)抽取［30%，50%，70%］的樣本作為訓(xùn)練樣本，剩余的樣本作為測(cè)試.整個(gè)過(guò)程被重復(fù)50次.平衡因子C由10次交叉驗(yàn)證來(lái)確定.

表1　淋巴結(jié)轉(zhuǎn)移分類結(jié)果比較

如表1所示，隨機(jī)多核學(xué)習(xí)在所有3種不同比例的訓(xùn)練樣本集上，分類精度都要優(yōu)于其他3種多核學(xué)習(xí)算法.由于減少了子核的規(guī)模，隨機(jī)多核學(xué)習(xí)使用了最少的訓(xùn)練時(shí)間.而且隨機(jī)多核學(xué)習(xí)需要更少的子核數(shù)目，它一定程度上對(duì)應(yīng)著需要的特征數(shù)目.這在臨床醫(yī)學(xué)上是非常重要的.因?yàn)樗梢员苊獠』甲鲆恍┎槐匾模蛘哂酗L(fēng)險(xiǎn)的醫(yī)療檢查.

4 結(jié)束語(yǔ)

筆者提出了一種隨機(jī)多核學(xué)習(xí)分類算法，縮減了子核的規(guī)模，從而加快了多核學(xué)習(xí)的訓(xùn)練時(shí)間，節(jié)省了內(nèi)存存儲(chǔ)空間，并且提高了分類精度.在淋巴結(jié)檢測(cè)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)，充分驗(yàn)證了該算法的優(yōu)良性能.

隨著當(dāng)前信息量的爆炸式發(fā)展，要處理的分類問(wèn)題規(guī)模將越來(lái)越大，借助語(yǔ)義先驗(yàn)的方法，進(jìn)一步減少算法的運(yùn)算時(shí)間將是下一步工作的重點(diǎn).

［1］KWAK N.Nonlinear Projection Trick in Kernel Methods:an Alternative to the Kernel Trick［J］.IEEE Transactions on Neural Networks and Learning Systems，2013，24（12）:2113-2119.

［2］SHAO Z F，ZHANG L，ZHOU X R，et al.A Novel Hierarchical Semisupervised SVM for Classification of Hyperspectral Images［J］.IEEE Geoscience and Remote Sensing Letters，2014，11（9）:92-97.

［3］WON K，SAUNDERS C，PRüGEL-BENNETT A.Evolving Fisher Kernels for Biological Sequence Classification［J］. Evolutionary Computation，2013，21（1）:81-105.

［4］李映，焦李成.基于核Fisher判別分析的目標(biāo)識(shí)別［J］.西安電子科技大學(xué)學(xué)報(bào)，2003，30（2）:179-182. LI Ying，JIAO Licheng.Target Recognition Based on Kernel Fisher Discriminant［J］.Journal of Xidian University，2003，30（2）:179-182.

［5］SUN T，JIAO L C，LIU F，et al.Selective Multiple Kernel Learning for Classification with Ensemble Strategy［J］. Pattern Recognition，2013，46（11）:3081-3090.

［6］BACH F，LANCKRIET G，JORDAN M.Multiple Kernel Learning，Conic Duality，and the SMO Algorithm［C］// Proceedings of 21th International Conference on Machine Learning.New York:ACM，2004:41-48.

［7］SONNENBURG S，RATSCH G，SCHAFER C，et al.Large Scale Multiple Kernel Learning［J］.Journal of Machine Learning Research，2006，7（1）:1531-1565.

［8］BACH F，RAKOTOMAMONJY A，CANU S，et al.Simple MKL［J］.Journal of Machine Learning Research，2008，9:2491-2521.

［9］XU Z L，JIN R，YANG H Q，et al.Simple and Efficient Multiple Kernel Learning by Group Lasso［C］//Proceedings of the International Conference on Machine Learning.London:Elsevier Limited，2010:1175-1182.

［10］KLOFT M，BREFELD U，SONNENBURG S，et al.Lp-Norm Multiple Kernel Learning［J］.Journal of Machine Learning Research，2011，12:953-997.

［11］HUANG G B，WANG D H，LAN Y.Extreme Learning Machines:a Survey［J］.International Journal of Machine Learning and Cybernetics，2011，2（2）:107-122.

［12］CHEN J Y，ZHENG G Z，CHEN H J.ELM-Map Reduce:MapReduce Accelerated Extreme Learning Machine for Big Spatial Data Analysis［C］//IEEE International Conference on Control and Automation.Washington:IEEE Computer Society，2013:400-405.

［13］CORTES C，MOHRI M，ROSTAMIZADEH A.Generalization Bounds for Learning Kernels［C］//Proceedings of the 27th International Conference on Machine Learning.London:Elsevier Limited，2010:247-254.

（編輯:王 瑞）

Fast randommultiple kernel learning for classification

SUN Tao，F(xiàn)ENG Jie
（Ministry of Education Key Lab.of Intelligent Perception and Image Understanding，Xidian Univ.，Xi’an 710071，China）

Multiple kernel learning（MKL）combines multiple kernels in a convex optimization framework and seeks the best line combination of them.Generally，MKL can get better results than single kernel learning，but heavy computational burden makes MKL impractical.Inspired by the extreme learning machine（ELM），a novel fast MKL method based on the random kernel is proposed.When the framework of ELM is satisfied，the kernel parameters can be given randomly，which produces the random kernel. Thus，the sub-kernel scale is reduced largely，which accelerates the training time and saves the memory. Furthermore，the reduced kernel scale can reduce the error bound of MKL by analyzing the empirical Rademacher complexity of MKL.It gives a theoretical guarantee that the proposed method gets a higher classification accuracy than traditional MKL methods.Experiments indicate that the proposed method uses a faster speed，more small memory and gets better results than several classical fast MKL methods.

multiple kernel learning；extreme learning machine；random kernel；empirical rademacher complexity

TP775

A

1001-2400（2016）01-0036-05

10.3969/j.issn.1001-2400.2016.01.007

2014-08-31 網(wǎng)絡(luò)出版時(shí)間：2015-04-14

國(guó)家973計(jì)劃資助項(xiàng)目（2013CB329402）；國(guó)家自然科學(xué)基金資助項(xiàng)目（61272282）；新世紀(jì)人才計(jì)劃資助項(xiàng)目（NCET-13-0948）

孫 濤（1984-），男，西安電子科技大學(xué)博士研究生，E-mail:taosun@mail.xidian.edu.cn.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.023.html