趙劍

摘要：支持向量機是近年來比較流行的一種機器學習方法，以其出色的學習性能在模式識別等領域得到廣泛應用。核函數(shù)是支持向量機的核心部分，對其工作性能起到重要作用，其中核參數(shù)直接決定分類器識別率的高低?，F(xiàn)有的核參數(shù)選擇方法計算復雜度很高，因此本文介紹了一種新的跟蹤核參數(shù)路徑的算法，該方法從核參數(shù)的學習出發(fā)，為支持向量機解決模型選擇問題，記錄選用各個核參數(shù)得到的最優(yōu)解，而不是反復訓練多個支持向量機，在一定程度上降低了計算復雜度，提高了學習效率。

關鍵詞：支持向量機;核函數(shù);核路徑算法

1 引言

支持向量機（Support Vector Machine，SVM）是近年來在模式識別與機器學習領域中出現(xiàn)的新工具，SVM以統(tǒng)計學習理論為基礎，基于結構風險最小化原則之上，有效地避免了經(jīng)典學習方法中過學習、維數(shù)災難、局部極小等傳統(tǒng)學習存在的問題，在小樣本條件下仍然具有良好的泛化能力。目前支持向量機在文本分類、手寫體識別、圖像分類、生物信息學等領域獲得了較好的應用。

支持向量機的基本思想是：通過非線性映射將輸入空間變換到一個高維特征空間，在這個高維空間中尋找輸入變量和輸出變量之間的一種非線性關系（如圖1所示）。在訓練中該算法僅使用到高維空間中的內(nèi)積，通過引入核函數(shù)，高維空間的內(nèi)積運算就可用原空間中的函數(shù)來實現(xiàn)，甚至沒有必要知道的形式。通過采用適當?shù)暮撕瘮?shù)就可實現(xiàn)某一非線性變換后的線性分類，而計算復雜度卻沒有增加，從而在一定程度上避免了維數(shù)災難問題。

由以上可以看出，核函數(shù)是支持向量機的關鍵部分，它決定了支持向量機中非線性的原始數(shù)據(jù)空間到高維特征空間的映射關系。目前較為常用的核函數(shù)主要有以下三種：

核函數(shù)的形式和參數(shù)的變化會隱式地改變從輸入空間到特征空間的映射，進而對特征空間的性質(zhì)產(chǎn)生影響，最終改變各種核函數(shù)方法的性能。

從形式上核函數(shù)主要分為全局核函數(shù)和局部核函數(shù)兩種，其中全局核函數(shù)的典型代表是多項式核函數(shù)，而局部核函數(shù)以徑向基核函數(shù)最為常用。一般來說局部核函數(shù)的學習能力優(yōu)于全局核函數(shù)，而推廣能力卻不及全局核函數(shù)。

另外，在SVM 的實際應用中涉及到核函數(shù)參數(shù)確定的問題。核函數(shù)參數(shù)的確定直接關系到分類器識別率的高低，因此選擇合適的核函數(shù)參數(shù)非常重要，這也是本文討論的重點。目前解決這一問題最常用的方法為交叉驗證法，該方法的原理是選定的一組核參數(shù)，構成與此對應的SVM模型，將訓練樣本分成容量相同的k個子集，并對模型訓練k次，在第i（i=1，…，k）次訓練時，要用除第i個子集的所有子集訓練模型，再用得到的模型對第i個子集計算誤差，以k次誤差的平均數(shù)值作為模型推廣能力的近似值，這樣反復訓練最后選擇一組核參數(shù)使得模型推廣能力最好。另外還有基于網(wǎng)格搜索的支持向量機參數(shù)確定法^[5]、基于Gram矩陣的支持向量機參數(shù)確定法以及貝葉斯法等。雖然這些方法都能在一定程度上提高分類正確率，但都需要反復訓練多個支持向量機，造成了較大的計算復雜度，同時也不一定能找到最優(yōu)解。

針對此問題，本文介紹了一種跟蹤核參數(shù)路徑的算法，該方法從核參數(shù)的學習出發(fā)，為SVM解決模型選擇問題，記錄選用各個核參數(shù)得到的最優(yōu)解，而不是反復訓練多個SVM。該算法基本思想可以概括為：給定一組核參數(shù)訓練得到最優(yōu)解，那么該核參數(shù)鄰域的某一個取值所對應的最優(yōu)解就可以從前一組結果精確推導出。這種記錄最優(yōu)解的方法不可避免分段線性化以至非線性，因此實際迭代中存在斷點。在訓練過程中，應近似估計斷點從而繼續(xù)下一個范圍的迭代。

總結

本文介紹了一種新的跟蹤核參數(shù)路徑的算法，該方法從核參數(shù)的學習出發(fā)，為支持向量機解決模型選擇問題，記錄選用各個核參數(shù)得到的最優(yōu)解，而不是反復訓練多個支持向量機，在一定程度上降低了計算復雜度，提高了學習效率。

在支持向量機的訓練中，正則化參數(shù)的選擇也很關鍵，因為不僅關系模型的分類性能，而且決定著運算迭代的次數(shù)，影響核路徑的運算效率，在假設核參數(shù)固定的情況下，經(jīng)過適當參數(shù)代換，也可以采用本文介紹的方法確定。目前，有關專家提出了在二維平面內(nèi)同時跟蹤正則化參數(shù)和核參數(shù)以尋求最優(yōu)解的方法，它不同于基于網(wǎng)格的核參數(shù)確定方法，在運算效率和精度方面應優(yōu)于后者，成為解決核參數(shù)選擇問題的一個重要研究方向。

參考文獻：

[1]張學工.關于統(tǒng)計學習理論與支持向量機.自動化學報，2000，26（1）：32-33.

[2]楊斌，路游.基于統(tǒng)計學習理論的支持向量機分類方法.計算機技術與發(fā)展，2006，16（11）.

[3]Zhonghui Hu，Yunze Cai，Ye Li.Support Vector Machine Based Ensemble Classifier.2005 American Control Conference.June 8-10，2005.

[4]王華忠，俞金壽.核函數(shù)方法及其模型選擇.江南大學學報，2006，5（4）.

[5]王興玲，李占斌.基于網(wǎng)格搜索的支持向量機核函數(shù)參數(shù)的確定.中國海洋大學學報，2005，35（5）：859-862.

[6]李曉宇，張新峰.一種確定徑向基核函數(shù)參數(shù)的方法.電子學報，2005，33（12）.

[7]Gang Wang，Dit-Yan Yeung，F(xiàn)rederick H.Lochovsky.A Kernel Path Algorith for Support Vector Machine.Proceedings of the 24th International Conference on Machine Learning，Corvalis，OR，2007.