A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition這篇文章的翻譯，自己辛苦翻譯的
All Right Reserved From: NZQ 我們注意到如果存在密度函數p(x,y),則P(x,y)可以寫成p(x,y)dxdy 這是一個計算期望風險很好的途徑,但是除非我們知道概率分布函數P(x,y)的 估計,否則這種方法沒有什么意義。 R(ω)的數值被稱為期望風險,或者直接說風險。此處我們稱其為真實風險, 以強調我們最終感興趣的是這個數值。我們定義訓練集(對應固定有限個樣本) 上的測量平均誤差為經驗風險Remp(a): R emp ∑-y-f(x;,) 注意到,上式沒有出現概率分布函數。對于一個選定的參數c和固定的訓練集 x;,y;,Rem()是一個固定的數值 數值y1-f(x,m)被稱為損失函數,在上述情況下,其取值只能是或者 現在選定一個數值η,其中0≤η≤1。損失函數如上所述取值或,則下式 所示的界以1-η的概率成立 R()≤Rmp()+ h(og(2h)+1)-g(/4 上式中是一個非負整數,稱為維( 維),是衡量上 述容量概念的一個標準。下文中我們將稱公式()的右邊第二項為“風險的界”。 我們從以前的術語開始探究 等作家()稱它為“保證風險”(原文是 ),這樣命名有一點不恰當,因為它只是風險的界而非風險;并且 它僅是提供一種確定的可能性,而非保證。對右端第二項的第二種命名方式是稱 之為“VC置信區間” 我們注意到關于這個界有三個關鍵點。第一,明顯地這個界與概率分布函數 P(x,y)無關。它僅假定訓練數據與測試數據服從同一未知概率分布P(x,y)。其 次,通常沒有辦法具體求岀上式左端項的數值。第三,如果我們知道了的值, 我們很容易可以計算上式右端項的數值。因此,對于給定的學習機器(“學習機 器”僅表示函數集f(x,α)),選定一個固定且足夠小的η,然后選擇使上式右端項 最小化的學習杋器,則這個學習機器可以使真實風險的上界最小。這個理論是結 構風險最小化(見章節)的基本思想,對于為給定任務選擇合理的學習機器 其提供了一個理論上的方法。給定一組學習機器,則至少有一個學習機器,相對 于其他機器來說,其界是緊的。即使對于任一學習機器來說,這個界也不是緊的, 上式右端項仍能為最小化經驗風險提供一些有用的信息。這個界可能對于所有的 數集都不是緊的,使得反對者可以借此批評這一理論。目前這種情況下,一切 都只能以實驗作為依據(貌似 已經證明這個界是緊的)。 維 維表征了函數集α(我們再次使用α作為一個一般的參數,確定了α也 就確定了特定的函數)的一種特性,其可以用各類函數關系進行定義。此處我 All Right Reserved From: NZQ 們僅考慮對應于兩類模式識別問題的函數,所以,f(x,a)∈{-11}vx,。如 果給定的長度為的樣木集可以被函數集a中的一個函數以2種方式分開,我 們則說該樣木可以被這個函數集打散。函數集a的維定義為其可以打亂的 樣本點最大的個數。請注意,如果喲數集的維為,則不少存在一組長度為 的樣本集可以被該函數集打散,但是這并不意味著該函數集可以把任意長度為 的樣本集打散。 R空間中定向超平面打散樣本點 假定樣本都是二維空間R2中的數據,函數集c是一個定向直線的集合,對 于一條給定直線,位于直線一側的是類,另一側的是類。直線的方向如圖 中箭頭所示,箭頭所指一側的樣本點標記為類。我們可以發現,這函數集可 以打散某一長度為的樣本集,卻無法打散任意長度為的樣本集,因此,二維 空間R2中定向直線的維是 圖 二維空間R2中三個樣本點被定向直線打散 現在讓我們考慮維空間R中的超平面。可能要利用下述定理: 定理 維空問R中的長度為的樣本集可以被相應定向超平面打散的允 要條件是,任選一個樣本點作為原點,其它樣本點的位置向量線性無關 推論: 維空間R中定向超平面的維是,因為我們總可以選出 個點,其中一個點作為原點,其余個點的位置向量線性無關,但是我們選不出 個點(因為維空間R中不會有個線性無關的向量)。 本推論的另一種證明方法見于 和 ()的著作,見于參考 文南3 維與參數數目 維使得函數集容量的概念得以具體化。人們直觀上容易認為,參數多的 函數集維會很高,而參數少的函數集的維會很低。然而 和 ,)提出」一個很明顯的反例:僅含一個參數的學習 機器可以有無窮大的維(對于分類器來說,有無窮大的維,意味著 無論有多大,它都可以打散長度為的樣本集)。定義階躍函數0(x)x∈R: All Right Reserved From: NZQ e(x)=1vx>0;6(x)=-1wx≤0。考慮如下定義的僅有一個參數的 數集 f(x,a)≡(sin(ax),x,a∈R 對于任意大的數字,可以找到按照如下方式選擇的長度為的樣本集, 其能被該函數集打散: X1=10 可以為指定任意標號 y1,y2 y1,y1∈{-1,1} 只需選擇如下式所示的α,f(x)就能按照上式中標號分開樣本集: =T(1+l19m1° () 因此,這個學習機器的維是無窮大的。 =0 圖 維無限大的函數集0(sin(ax)無法打散的個點 有意思的是,盡管上述函數集可以打散某個任意長度的樣本集,我們仍能找 出一個僅有個點的樣本集,使其無法打散。這個樣本點只是簡單地均勻分布, 其標號如圖所示。這種情況看作:樣木點x1位于相位φ1=2nm+6處,其標號 y1=1,其中0<8<π。x2的相位對2π取余為28,令y2=1→0<8< 簡單地點x3會使得6>T/3然后,在點x處,/3<8<2會使得f(x4,0)=-1, 與給定的標號相反。這四個點是空間R中有向超平面對于位于同一直線上三個點 按照公式()的一種類推。這兩種情況下,喲數集都無法打散這些點集。 通過最小化最小化界 圖說明了,在置信度為(n=0.05),樣本數量為的情況下,公 式右端第二項是如何隨變化的。對于任意的樣木數 置信區間都是 的單調增數。 因此,給定一些經驗風險為零的學習機器,我們應該選擇維小的函數集。 這樣才能有一個更小的誤差上界。總體而言,對于經驗誤差不為零的情況,我們 應該選擇使得公式右端項最小的學習機器。 注意到釆用這種策略時我們僅依據公式。公式(在給定概率下)可以給 出真實風險的上界。這并不意味著,一個具有同樣的繹驗風險然而維更高的 學習機器不可以有更好的泛化能力。事實上,下一節我們將給出一個例子,它有 無窮大的維然而其泛化能力同樣很好。從圖形中可以注意到,對于 (n=0.05且1=10000)的情況,置信區間超過了單位,所以對于吏高的 值,這個界不能保證是緊的。 All Right Reserved From: NZQ 14 12 o9cgE89> 0.8 0.6 0.4 0.2 0.10.20.30.40.50.60.7080.91 h/I= VC Dimension /Sample Size 圖 置信區間隨單調遞增 兩個案例 考慮近鄰分類器,。因為任意數目的樣本點和任意的標號組成的樣本 集都可以被該函數集正確的學習(假設不同類的樣木點不緊鄰),所以這個函數 集具有無窮大的維和零經驗風險。因此這個界一無所用。事實上,對于任何 具有無窮大的維的函數集來說,這個界都沒有任何意義。然而,即使不遵循 使這個界最小化的原則,近鄰分類器的泛化能力依然很好。因此,第一個案例警 示我們,無窮人的容量并不一定造成差的泛化能力 讓我們以一種試圖打破傳統知識以利用傳統知識的方式來理解這個理論,看 下我們是否能夠提出這樣一個分類器,其存在這個邊界然而違反這個邊界。(此 處作者的意思大概是讓公式的小于等于變成大于等于)我們使公式中左邊項 盡可能的大同時右邊項盡可能的小,以使我們得到這樣一個分類器:其真實風險 是最壞的 同時對于某些樣本其經驗風險為零而且其維很容易計算并遠 小于(這樣這個邊界就不成立了)。下面有一個這樣的案例,我們稱其為“筆記 型分類器”(原文是 )。這個分類器包含一個有足夠空間記 個訓練樣本類別的筆記,m≤1。對于后續所有的樣本點,該分類器簡單的認為 所冇樣本點同屬一類。假設樣本點是隨機選擇的,而且其正類與負類數目大抵相 同。這個筆記型分類器對于前個樣本點經驗風險為零;對后續樣本點錯分概 率為;同時其維。把上述數值帶入公式,可得 ≤m(21/m)+1-(/m)ln(/4 () 上式將滿足任意n如果下式成立 f()=( 2)exp(4-1 ,0≤z≤1 因為f(z)單調遞增而且f(z=1)=0236,所以上式成立 All Right Reserved From: NZQ 結構風險最小化 4(h3(h2 h1 h1<h2≤h3 圖 依照維嵌套的函數序列 我們現在能夠總結下結構風險最小化()原則( )。注意 到,公式中提到的置信區間依賴于所選擇函數集,相反地經驗風險與真實 風險依賴于訓練過程所選擇的某一特定函數。我們要從待選函數集中選擇一個最 小化風險邊界的子集。因為維是一個整數,所以明顯地我們不能夠得到平 滑變化的維。取而代之,我們介紹一種“結構”,其將整個函數集分成層層 嵌套的子集(如圖)。對于每個子集,我們要么可以算出維,要么可以直 接算出所決定的界。 原則就是找出可以最小化真實風險的界的子集。這 點可以通過簡單地訓練學習機器做到,對于每個子集,訓練的日標是找到最小 化經驗風險的那個函數。然后從序列中取得經驗風險與維置信區問最小的函 數 到此為止,我們已經為探索支持向量機之路鋪設了基礎 線性支持向量機 可分的情況 我們將以最簡單的情況開始:在線性可分數據中訓練線分類機(正如我們看 到的,對于更一般情況的分析一在線性不可分數據上訓練非線性分類機一最后都 會轉化為一個簡單的二次規劃問題)。再次標注訓練數據{xy},i=1,…,,J,y1∈ {-1,1,x1∈R。假定我們有一個超平面可以把正類與負類分開(分類超平面)。 超平面上的點滿足ox+b=0,其中o是超平面的法向量。B1o是超平面到 原點的垂育距離,其中‖是o的歐兒里得距離(范數)。用d+(d-)表小(負) 類到分類超平面的最短距離。定義d++d-為分類超平面的“裕度”(原文為 )。對于線性可分的情況,支持向量機算法就是尋找分類超平面的最大裕 度。可以具體闡述為:假定所有訓練數據滿足下述約束 X;·ω+b≥+1fory;=+1 X1·0+b≤-1fory1=-1 上述兩式可以合為下式 (X1·ω+b)-1≥0vi 現在考慮滿足公式()取等號的點(這樣的點在某種程度上決定了0和) 這些點在超平面H1上:x1:ω+b=1,其含有ω且到原點的垂直距離是 All Right Reserved From: NZQ o/同樣的,使得公式()取等號的點在超平面12上:x1:u+b=-1, 其含有0且到原點的垂直距離是 lo因此d+=d-=1o且裕度可 以簡單地表示為/1ol注意到H1與H2是平行的(有共同的法向量)且沒有樣本 點落在它們之間。因此我們能夠在滿足約束條件公式()的情況下,通過最小 化‖ω)‖2來得到裕度最大的超平面 Origin ⊥ argin 圖可分情況下的線性可分超平面。圈中樣本點代表支持向量 對于典型的二維情形,我們期望其解具有圖所示的情形。使得公式() 取等號的訓練點(超平面H1或者H2上的點)的移動可以改變訓練結果,稱其為 支持向量;在圖中通過圓圈標出了這些點 我們轉向這個問題的一個拉格朗日方程。這個轉化有兩個原因。首先是約束 ()會轉化成拉格朗日乘子的形式,以更好的處理。第二是通過這樣重構問題, 訓練數據(在訓練與測試中)將會僅出現向量點乘的形式。這是一個很重要的特 性,決定了我們可以得到解決非線性情況的方法(第章)。 因此,對每個不等式約東(),我們都引入一個正的拉格朗囗乘了 ax,i=1,…,l。回想對于形如c1>0的不等式約束條件,拉格朗日方程是從 標方程中減去約束方程乘以一個正的拉格朗日乘子。對于等式約束,拉格朗日乘 子沒有非負約束。拉格朗日方程如下: Lp=‖o2-2=1cy(x;:ω+b)+∑=1a 我們必須在滿足約束α1>0的情況下消去Lp中含有a1的中間變量(我們稱這 組特定的約束為C1),然后對于ω和來最小化L。因為目標函數本身是個凸函 數,且滿足該約束的點形成的是凸集(任一線性約束都定義了一個凸集,個線 性約束同時定義了這些凸集的交集,凸集的交集仍是凸集),所以這個問題是 個凸二次規劃問題。這意味著我們可以等效地求解下述“對偶”問題:在以下約束 條件下最大化Lp,L對ω和的梯度等于;c1>0(我們稱這組特定的約束為C2) 這種特定的對偶形式成為對偶( )。它有這樣一種特性:在 8 All Right Reserved From: NZQ 約束C2下最大化Lp與在約束C1下最小化L得到的ω,,a的值是相同的 Lp對ω與的梯度等于的約束給出了以下條件: ∑ i yixi ∑ 因為對偶問題中的約東條件與原問題相同,將其帶入公式()可得: aiajyiyjxi' xi 注意到我們給了拉格朗口方程不同的標弓(原問題用,對偶問題有)以 強調這兩個表達式的不同:L與L源自同一個目標函數,卻有不同的約束條件 分別通過最小化L或最大化L求解。也注意到,如果我們在的條件下構造 這個問題,等價于所有的超平面都包含原點,約束()就不再成立。這對于高 維空間是一個緩和約束(原文為 ),因為它等效于降低一個自度。 支持向量訓練(對于線性可分的情況)等價于在公式()和為正的約東 條件下,對α;最大化Lp,其解由公式()給出。注意到每個訓練點都對應于 個拉格朗日乘子c1。在解中,那些對應于α1>0的樣木點稱為“攴持冋量”,位于 超平面H1或者H2上。其余所有訓練點1=0,其要么位于H1或者H2上(使得公 式()等式成立),要么位于H1或者H2兩側使得公式()不等號成立。對于 這些學習機器,支持向量是訓練集的決定性元素。它們最鄰近決策邊界;如果其 他訓練點被移動(改變位置但沒穿過H1或者H2),即使重新訓練,也會得到同 個分類超平面 條件 在約東優化的理論與應用中, ()條件都有著至關 重要的作用。對于上述原問題, 條件可表述為( LP=ωy-∑yxw=0v=1,…,d ∑iαiyi1=0 y1(x1·(+b)-1≥0i=1,…,l a>o vi a1Gy1(x1·+b)-1)=0V 對于任何約東條件,假定可行域的下降方向與線性約束的下降方向交于一點, 則仼意帶約束最優化問題(無論是否凸規劃)的解都滿足條件(參見 )。這個相當技術規范的假定對于每個支持向量機都成 立,因為其約束都是線性的。而且, 問題是一個凸規劃(目標函數是凸函 數,可行域是凸集),對于凸規劃(如果上述規范條件成立),條件是ω,b和α 為解的充要條件 )。因此,求解問題相當于尋找滿足 條件的解。這導致有很多方法可以求解 問題(比如,第章中提到的原 對偶方法)。 作為一個直接的應用,我們注意到,盡管ω可以在訓練過程中直接求解,國 值卻只能隱含的求解。然而,通過KKT“補充條件”公式(),選擇使得α1≠0的 可以很容易的計算出(注意到對每個合適的計算出所有的取平均會更合理) All Right Reserved From: NZQ 注意到我們目前為止所做的就是把問題轉化為一個優化問趣,其約束比公式 (),()更易處理。求解現實中的問題往往需要數值解法。隨后我們會介紹 更多。然而,我們先求解一種相對少見的情況,其是非平凡的問題(維數任意, 解不明顯),但是其可以通過解析求解 最優超平面:一個案例 盡管夲節的主要目的是求解一個其支持向量可以被解析求解的非平凡模式 識別問題,此處得到的結果可用于后面的證明。對于所考慮問題,每個訓練點都 被證眀是一個支持向量,這也是我們能解析求解的一個原因。 考慮將個點對稱地放在半徑為的球休S"-1上:更確切地說,這些點形 成了維空間對稱的頂點。可以很容易地將這些點映射到維空間R+中的經 過原點的法向量為()維向量(,,)的超平面上(在這個變換中, 這些點略過維空間R,直接映射到維空間R+1)。可以確切地知道,向量 本身是用歲馬數字標示,而其下標使川希臘字封表示,其下標通過下式給出 R +δ; 其中張積量(原文是 )δ當的時候為,否則為。因此,單 位圓上的三個等距點的向量(參見圖)分別是 3′y6 V6 對稱的一個結果就是任意兩個向量之間的夾角都是相等的(等于 arccos (I/n)) lx‖2=R R 或者,更簡潔地 61-(1-61) 對每個樣本點任意指定一個類別標號C∈{+1,-1},我們希望找出以最大 裕度將兩類樣本點分開的超平面。因此,我們必須在滿足約束a;>0,與等式約 東公式()的條件下,最大化公式()中的L。我們的方法是假定不存在不 等式約東而簡單地求解問題。在滿足等式約束公式()的情況下,若得到的解 滿足約束條件α>0,ⅵi,我們就認為得到了一般的解,因為L的最大值落在可 行域內。為了利用等式約束,我們引入附加的拉格朗日乘子。因此我們尋求最大 化下式: