孫 濤，馮 婕

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

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

孫 濤，馮 婕

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

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

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

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

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

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

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

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

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

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

2.1構(gòu)造隨機核

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

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

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

其中，

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

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

2.2一般性誤差的理論分析

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

首先，回顧一下模式識別的一個重要理論.

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

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

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

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

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

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

3 實驗結(jié)果分析

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

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

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

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

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

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

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

如表1所示，隨機多核學(xué)習(xí)在所有3種不同比例的訓(xùn)練樣本集上，分類精度都要優(yōu)于其他3種多核學(xué)習(xí)算法.由于減少了子核的規(guī)模，隨機多核學(xué)習(xí)使用了最少的訓(xùn)練時間.而且隨機多核學(xué)習(xí)需要更少的子核數(shù)目，它一定程度上對應(yīng)著需要的特征數(shù)目.這在臨床醫(yī)學(xué)上是非常重要的.因為它可以避免病患做一些不必要的，或者有風(fēng)險的醫(yī)療檢查.

4 結(jié)束語

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

隨著當(dāng)前信息量的爆炸式發(fā)展，要處理的分類問題規(guī)模將越來越大，借助語義先驗的方法，進(jì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)識別［J］.西安電子科技大學(xué)學(xué)報，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ò)出版時間：2015-04-14

國家973計劃資助項目（2013CB329402）；國家自然科學(xué)基金資助項目（61272282）；新世紀(jì)人才計劃資助項目（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