快速隨機多核學習分類算法

孫 濤，馮 婕

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

快速隨機多核學習分類算法

孫 濤，馮 婕

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

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

多核學習；極限學習；隨機核；經驗Rademacher復雜度

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

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

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

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

1 多核學習框架

在單核學習中，依據優化的最終目標不同，有支撐矢量機（Support Vector Machine，SVM）、核判別分析、核最近鄰等.當單核學習變為了多核學習的時候，按照最終的優化目標不同，分為了不同的算法.由于SVM分類不用考慮數據的分布特性，有著更廣泛的應用環境，所以，文中利用SVM給出多核學習對偶式的公式為

2 快速隨機多核學習

2.1構造隨機核

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

定理1 對于任意N個輸入樣本，給定一個在任意區間可以無窮可導的激活函數和L個隱藏層節點，對隱藏層節點的權重和偏差隨機賦值，ELM可以無誤差地逼近這N個獨立樣本.

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

其中，

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

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

2.2一般性誤差的理論分析

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

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

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

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

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

從文獻［10］的結論中，可以得到多核學習L1約束的經驗Rademacher復雜度為

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

假設L是一個關于ρ的損失函數，把式（6）代入式（5）中，可以得到

3 實驗結果分析

胃癌每年在全球影響著大約800 000的人.胃癌的術前分期對于胃癌的治療具有非常重要的意義.當前，腫瘤診斷系統是胃癌分期的一個標準系統.其中的淋巴結診斷又是腫瘤分期的一個重要組成部分.淋巴結診斷為手術治療提供了非常重要的參考.

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

在這里把生理指標的選擇問題轉變為一個優化選擇問題.多核學習被用來求解這個問題.每個指標對應著一個子核，那么優化選擇子核的過程就等價于選擇最優指標的過程.經過優化求解以后，可以得到多個指標的一個最佳加權組合，它就可以用來檢測淋巴結是否轉移.

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

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

對于隨機多核學習，每個指標被用來構造一個隨機核.激活函數，選擇RBF激活函數.影層的節點數是2 000，總共有18個候選子核.每次運行，隨機抽取［30%，50%，70%］的樣本作為訓練樣本，剩余的樣本作為測試.整個過程被重復50次.平衡因子C由10次交叉驗證來確定.

表1　淋巴結轉移分類結果比較

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

4 結束語

筆者提出了一種隨機多核學習分類算法，縮減了子核的規模，從而加快了多核學習的訓練時間，節省了內存存儲空間，并且提高了分類精度.在淋巴結檢測數據庫上的實驗，充分驗證了該算法的優良性能.

隨著當前信息量的爆炸式發展，要處理的分類問題規模將越來越大，借助語義先驗的方法，進一步減少算法的運算時間將是下一步工作的重點.

［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判別分析的目標識別［J］.西安電子科技大學學報，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，FENG 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 網絡出版時間：2015-04-14

國家973計劃資助項目（2013CB329402）；國家自然科學基金資助項目（61272282）；新世紀人才計劃資助項目（NCET-13-0948）

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

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.023.html