基于ＲＢＦ核的ＳＶＭ及ＲＶＭ模式分析性能比較

（1.西北工業大學 自動化學院 西安 710072;2.西安工業大學 經管學院 西安 710032）

摘 要：基于RBF核，利用Synthc、BC等標準數據集，采用五重交叉驗證，比較SVM(支持向量機)及RVM(關聯向量機)模式分析性能。實驗結果表明，與SVM相比，RVM時間復雜度、測試錯誤率較低，模式分析性能較優。

關鍵詞：關聯向量機；支持向量機；分類；徑向基函數核

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)05-1782-03

Comparison on pattern analysis performance of SVM and RVM based on RBF kernel

LI Gang1，2，XING Shubao1，XUE Huifeng1

(1.College of Automation Northwestern Polytechnical University Xi’an 710072 China；2.School of Economics Management Xi’an Technological University Xi’an 710032 China)

Abstract:Making use of standard dataset such as synth and BC，compared the pattren analysis performance of SVM and RVM using 5fold verification based on RBF kernel.Test result indicates that the mistake rate and time complication degree is lower than that of SVM.Research shows under the condition of this paper RVM’s pattern analysis performance is more excellent.

Key words:RVM; SVM; class; RBF kernel

統計學習理論（statistical learning theory，SLT）是一種專門研究小樣本情況下機器學習規律的理論。SLT針對小樣本統計問題建立了一套新的理論體系，在這種體系下的統計推理規則不僅考慮了對漸近性能的要求，而且追求在現有有限信息的條件下得到最優結果。模式分析研究的是如何自動檢測和辨識數據中潛在的關系，人們通常把這種方法稱為統計模式識別^[1]。隨著人們的注意力從線性關系轉移到非線性關系，20世紀80年代模式分析領域經歷了一場“非線性革命”，幾乎同時引入了后向傳播多層神經網絡算法和高效的決策樹學習算法^[2]。盡管這些方法用到了啟發式算法和不完全統計分析，它們使得檢測非線性模式成為可能。然而，這些非線性算法建立在梯度下降和貪心啟發式法的基礎上，受到局部最小化的限制。由于沒有很好地理解它們在統計上的行為，這些方法經常遇到過擬合的問題。20世紀90年代出現了新的被稱為基于核學習方法的模式分析方法，該方法可以高效地分析非線性關系，而這種高效率只有線性算法才能達到，而且避免了過擬合的危險。

20世紀90年代Vapnic在統計學習理論的 VC 維理論和結構風險最小原理基礎上提出SVM方法^[3]，根據有限的樣本信息在模型的復雜性(即對特定訓練樣本的學習精度)和學習能力(即無錯誤地識別任意樣本的能力)間尋求最佳折中，以期獲得最好的泛化能力。SVM的主要優點有： 

a)它是專門針對有限樣本情況的，其目標是得到現有信息下的最優解而不僅僅是樣本數趨于無窮大時的最優值。

b)算法最終將轉換成為一個二次型尋優問題。從理論上說，得到的將是全局最優，解決了在神經網絡方法中無法避免的局部極值問題。

c）算法將實際問題通過核函數非線性變換轉換到高維的特征空間，在高維空間中構造線性判別函數來實現原空間中的非線性判別函數，同時它巧妙地解決了維數問題，其算法復雜度與樣本維數無關。

SVM在實際應用中取得了成功，但也存在不足之處^[4]：

a）雖然支持向量數會明顯少于訓練樣本的個數，但依然會隨著訓練樣本的數量呈線性成長。一方面可能造成過度擬合的問題；另一方面則浪費計算時間。

b）SVM無法得到概率式的預測。一般人會偏好概率式的預測，因為概率式的預測能夠給出確定的程度，如氣象預報不會單純預測天氣為晴天或雨天，而會給出降雨概率。

c)SVM的使用者必須給定一個誤差參數C或ε，這個參數對結果有很大的影響。不幸的是，C及ε值設置的主觀性很強，使用者都必須猜測各種可能值才能找到最好的結果。

d)SVM的核函數必須符合Mercer條件。

模式分析的基本問題是二值分類問題，本文目的是將研究無須C值設定的RVM的二值模式分析性能：采用標準數據集及多重交叉驗證，在使用單一RBF核函數的情況下，通過比較需要設置主觀C值SVM的二值分類性能，考察RVM的優勢。

1 SVM及RVM基本算法

SVM與RVM的共同之處是：借助于核函數把低維空間線性不可分的問題轉換為高維空間中的線性劃分問題。SVM的基本思想是使分類間隔最大。CSVC（C支持向量分類機）引入近似線性劃分。對于基本的二值分類算法如下^[5]：

a）根據給定的訓練集：T={(x1，y1)，…，(xl，yl)}∈(X×Y)l。其中xi∈X=Rn，yi∈Y={1，-1}，i=1，2，…，l。

b）選取適當的核函數k(xi，xj)和適當的參數C構造并求解最優化問題

minα (1/2)li=1

li=1yiyjαiαjk(xi，xj)-li=1αi

s.t. li=1yiαi=0 0≤αi≤C，i=1，…，l

得到最優解α=(α1，…，αl)T。

c）選取α的一個正分量0＜αj＜C，并據此計算閾值b=yj-li=1yiαik(xi，xj)。

d）構造決策函數f(x)=sgn(li=1αiyik(xi，x)+b)。

RVM是Michael E.Tipping于2001年提出的一種建立在SVM上的稀疏概率模型，它的訓練是在貝葉斯框架下進行的，可以用它進行分類預測。與SVM相比，RVM具有以下優點：可以得到概率式的預測；避免主觀設置誤差參數C；訓練所用的相關向量少于SVM中的相關向量；核函數不用滿足Mercer條件，有更大的選擇范圍。RVM與SVM的最大不同之處是變硬性劃分為概率意義下的合理劃分，使得分類函數針對于訓練集似然函數值最大。基本理論如下：

設{xi}Ni=1是訓練中的特征值，t=[t1，t2，…，tn]T是目標值。 RVM認為ti服從以y為均值的正態分布：

p(ti)=N(ti|y(x)，σ2); y(x)=mj=1ωjk(x，xj)+ω0(1)

其中：k(x，xj)為非線性核函數;ωj為模型的權值。在定義了模型（式(1)）的基函數之后，可以在貝葉斯框架下用最大似然方法來訓練模型權值ωj，這樣可回避過學習問題，提高模型的泛化能力。因此，RVM為每個權值定義了先驗概率分布：

p(ωj|α)=[αj/2π]1/2exp[-2αjω2j/2]

其中：ωj是決定權值αj先驗分布的超參數。

訓練樣本集的似然函數為

p(t|ω，σ2)=(2πσ2)-N/2exp[（-1/2σ2）‖t-Φ ω‖2]

其中：t=(t1，…，tN)T；ω=(ω1，…，ωN)T;Φ為矩陣，其行包含所有核函數對輸入xi的響應(Φ)i=[1，1(xi)，…，n(xi)]。

根據先驗概率分布和似然分布，再用貝葉斯式計算權值的后驗概率分布，即

p(ω|t，α，σ2)=p(t|ω，σ2）p(ω|α)/p(t|α，σ2)

該權值的后驗分布屬于多變量高斯分布，即

p(ω|t，α，σ2)=N(μ，Σ)

其中：Σ=（σ-2ΦTΦ+A）-1為協方差，A是(α0，…，αn)的對角矩陣；μ=σ-2ΣΦTt為均值。

訓練目標值的似然分布通過對權值變量進行積分，即

p(ω|t，α，σ2)=∫p(t|ω，σ2)p(ω|α)dω

實現邊緣化，從而求得超參數的邊緣似然分布：

p(ωt|α，σ2)=N(0，C)

其中的協方差C=σ2I+ΦA-1ΦT。

RVM方法中的模型權值的估計值由后驗分布的均值給出，同時它也是權值的最大后驗(MAP)估計。權值的MAP估計取決于超參數α和噪聲方差σ2，其估計值和2可以通過最大化邊緣似然分布得到。后驗分布反映出的權值最優值的不確定性可以表示模型預測的不確定性。若給定輸入值x，相應輸出的概率分布為

p(t|x，，2)=∫p(t|x，ω，2)p(ω|t，，2)dω

服從高斯分布的形式，即

p(t|x，，2)=N(y，σ*2)

其中的預測均值和方差(不確定性)分別為

y=μTΦ(x)，σ*2=2+ΦT(x)Φ(x)

在最基本的二元分類的情況，目標值{ti}Ni=0只可能為0 或1。RVM使用把回歸算法應用到分類問題時常用的sigmoid函數：

p(ti=1|w)=σ[y(xi;w)]=1/（1+e-y(xi;w)）

在每次觀測皆為獨立事件的前提下，得到觀測結果為t的概率為P(t|W)=Ni=1σ[y(xi;w)]ti{1-σ[y(xi;w)]1-ti}。

RVM使用貝葉斯框架下的顯著度解決了模型的參數選取問題，具有較好的適用性。

2 模式分析測試

采用統計學習常用的二值分類標準測試數據Synth、PIMA^[6]、Wine、BC^[7]，為避免數據數值單位差異性對各維進行了歸一化處理。數據如表1所示。

表1 數據樣本個數及維度

數據集樣本個數樣本維度數據集樣本個數樣本維度

Synth1 2503Wine56931

BC68310PIMA5328

統計學習的性能隨核函數的不同性能各異。為簡單起見，實驗采用常用的RBF核：k（x，xj）=exp((-‖x-xj‖2/σ2)。由于數據已進行了歸一化處理，σ取為1。

a）實驗方法。五重交叉驗證，即將數據隨機等分成五份，依次取1~5作為訓練集，剩余四份作為測試集。這樣可充分利用數據，做到全面訓練及測試，獲得全面準確的性能測試數據。

b）算法實現。MATLAB實現SVM以Steve Gunn的SVM toolbox v 2.0為核心，RVM以Michael E.Tipping的SparseBayes程序為核心，測試計算機配置為：Intel Pentium 4 3.0 GHz，1 GB內存。

以Synth數據為例，該數據集為二維人工數據，Ripley于1996年用高斯分布產生，正類與負類數據各為750個，正類與負類數據相重疊約占8%。分別取C=inf（無窮大），1，0.8等觀察SVM的分類性能（五重檢驗的平均值），如表2所示。

從表4可以看出：a)RV比例（關聯向量占訓練樣本的比例）比SV比例（支持向量占訓練樣本的比例）低得多；b）RVM的測試錯誤率低于SVM的測試錯誤率；c）RVM的計算時間低于SVM的計算時間。

3 結束語

本文采用固定的σ值RBF核（SVM和RVM的模式分析性能受核函數種類影響較大）和歸一化的Synth、Wine、BC、PIME 數據，選取SVM分類性能最優的C值與RVM的分類性能比較，實驗結果表明在此條件下RVM的分類性能優于SVM。具體為：a）SVM算法較繁瑣，時間復雜度高于RVM；b)為使預測錯誤率較低，需嘗試不同C值，C值選取具有很強的主觀性；c)RV比例（關聯向量數占訓練樣本的比例）大大低于SV比例（支持向量數占訓練樣本的比例），從統計學習理論可知由此可以帶來更高的泛化性能。實際上，RVM的測試錯誤率低于SVM的測試錯誤率。

本研究的局限性在于僅選用了固定值的RBF核函數，實際上SVM和RVM的分類性能隨核函數種類的影響較大，這也是需要進一步研究的。

參考文獻：［1］

WEBB A R.統計模式識別[M].2版.北京：電子工業出版社，2004：1516.

[2]SHAWETAYLOR J，CRISTIANINI N.Kernel methods for pattern analysis[M].Cambridge:Cambridge University Press，2004.

[3]瓦普尼克.統計學習理論的本質[M].張學工，譯.北京：清華大學出版社，2004：2426.

[4]MICHAEL E T.Sparse Bayesian learning and the relevance vector machine[J].Journal of Machine Learning Research，2001，1:211244.

[5]鄧乃揚，田英杰.數據挖掘中的新方法：支持向量機[M].北京：科學出版社，2004:195196.

[6][EB/OL].http://stats.ox.ac.uk/pub/pmn.

[7][EB/OL].http://kdd.ics.edu/summary.data.type.html.