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