第4章支持向量機及其學(xué)習(xí)算法

支持向量機及其學(xué)習(xí)算法

合肥工業(yè)大學(xué)圖像信息處理研究室

協(xié)同形成結(jié)構(gòu)競爭促進發(fā)展主要內(nèi)容一、

歷史背景二、統(tǒng)計學(xué)習(xí)理論三、支持向量機四、支持向量機的分類學(xué)習(xí)算法五、用于函數(shù)擬合的支持向量機六、支持向量機算法的研究與應(yīng)用七、仿真實例傳統(tǒng)統(tǒng)計學(xué)是一種漸進理論，研究的是樣本數(shù)目趨于無窮大時的極限特性?，F(xiàn)有的學(xué)習(xí)方法多基于傳統(tǒng)統(tǒng)計學(xué)理論，但在實際應(yīng)用中，樣本往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法在實際中的表現(xiàn)卻不盡人意，存在著一些難以克服的問題，比如說如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)問題、局部極小值問題等，從本質(zhì)上來說就是因為理論上需要無窮樣本與實際中樣本有限的矛盾造成的。

與傳統(tǒng)統(tǒng)計學(xué)的方向不同，Vapnik等人提出了一個較完善的基于有限樣本的理論體系－－統(tǒng)計學(xué)習(xí)理論。統(tǒng)計學(xué)習(xí)理論是一種專門研究小樣本情況下機器學(xué)習(xí)規(guī)律的理論，它從更本質(zhì)上研究機器學(xué)習(xí)問題，為解決有限樣本學(xué)習(xí)問題提供了一個統(tǒng)一的框架。支持向量機方法是在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的通用學(xué)習(xí)方法，它具有全局優(yōu)化、適應(yīng)性強、理論完備、泛化性能好等優(yōu)點。Return統(tǒng)計學(xué)習(xí)理論

（StatisticalLearningTheory，SLT）機器學(xué)習(xí)的基本問題統(tǒng)計學(xué)習(xí)理論機器學(xué)習(xí)問題的表示基于數(shù)據(jù)的機器學(xué)習(xí)是現(xiàn)有智能技術(shù)中的重要方面，其研究的實質(zhì)是根據(jù)給定的訓(xùn)練樣本求出對系統(tǒng)輸入輸出之間依賴關(guān)系的估計，使它能對未知樣本的輸出做出盡可能準確的預(yù)測。

定義期望風(fēng)險：

－－預(yù)測函數(shù)集－－廣義參數(shù)

－－損失函數(shù)

－－聯(lián)合概率分布

經(jīng)驗風(fēng)險最小化

（EmpiricalRiskMinimization

，ERM）

實際應(yīng)用中，一般根據(jù)概率論中的大數(shù)定理，即采用下式的算術(shù)平均來逼近期望風(fēng)險。

用對參數(shù)求經(jīng)驗風(fēng)險的最小值代替求期望風(fēng)險的最小值。

事實上，從期望風(fēng)險最小化到經(jīng)驗風(fēng)險最小化并沒有可靠的理論依據(jù)，只是直觀上合理的想當然做法。經(jīng)驗風(fēng)險最小化原則不成功的一個例子就是神經(jīng)網(wǎng)絡(luò)的過學(xué)習(xí)問題:訓(xùn)練誤差（經(jīng)驗風(fēng)險）過小反而會導(dǎo)致推廣能力的下降，即真實誤差（期望風(fēng)險）的增加。出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因主要是由于學(xué)習(xí)樣本不充分和學(xué)習(xí)機器設(shè)計不合理。

當試圖用一個復(fù)雜的模型去擬合有限的樣本，必然會喪失推廣能力。由此可見，有限樣本下學(xué)習(xí)機器的復(fù)雜性與推廣性之間存在矛盾。機器的復(fù)雜度高，必然會導(dǎo)致其推廣性差；反之，一個推廣性好的學(xué)習(xí)機器，其分類能力必然不夠強。設(shè)計一個好的學(xué)習(xí)機器的目標就變成如何在學(xué)習(xí)能力和推廣性之間取得一個平衡，使得在滿足給定學(xué)習(xí)能力的前提下，提高其推廣性。

Return統(tǒng)計學(xué)習(xí)理論（SLT）

統(tǒng)計學(xué)習(xí)理論被認為是目前針對小樣本統(tǒng)計估計和預(yù)測學(xué)習(xí)的最佳理論。它從理論上較為系統(tǒng)的研究了經(jīng)驗風(fēng)險最小化原則成立的條件、有限樣本下經(jīng)驗風(fēng)險與期望風(fēng)險的關(guān)系以及如何利用這些理論找到新的學(xué)習(xí)原則和方法等問題。其中，最有指導(dǎo)性的理論結(jié)果是推廣性的界的結(jié)論，和與此相關(guān)的一個核心概念是函數(shù)集的VC維。

函數(shù)集的VC維

（VapnikChervonenkisDimension

）模式識別方法中VC維的直觀定義是：對于一個指標函數(shù)集，如果存在n個樣本能夠被函數(shù)集中的函數(shù)按所有可能的種形式分開，則稱函數(shù)集能夠把n個樣本打散；函數(shù)集的VC維就是它能打散的最大樣本數(shù)目h。有界實函數(shù)的VC維可以通過用一定的閾值將其轉(zhuǎn)化為指示函數(shù)來定義。VC維反映了函數(shù)集的學(xué)習(xí)能力，VC維越大則學(xué)習(xí)機器越復(fù)雜（學(xué)習(xí)能力越強）。推廣性的界

統(tǒng)計學(xué)習(xí)理論系統(tǒng)地研究了各種類型函數(shù)集的經(jīng)驗風(fēng)險（即訓(xùn)練誤差）和實際風(fēng)險（即期望風(fēng)險）之間的關(guān)系，即推廣性的界。關(guān)于兩類分類問題有如下結(jié)論：對指示函數(shù)集中的所有函數(shù)，經(jīng)驗風(fēng)險和實際風(fēng)險之間至少以概率滿足如下關(guān)系：

其中h是函數(shù)集的VC維，l是樣本數(shù)。

置信范圍實際風(fēng)險學(xué)習(xí)機器的實際風(fēng)險由兩部分組成：經(jīng)驗風(fēng)險，即訓(xùn)練誤差；置信范圍（ConfidenceInterval）

可以簡單的表示為：它表明在有限樣本訓(xùn)練下，學(xué)習(xí)機VC維越高（機器的復(fù)雜性越高），則置信范圍越大，導(dǎo)致真實風(fēng)險與經(jīng)驗風(fēng)險之間可能的差別越大。這就是為什么出現(xiàn)過學(xué)習(xí)現(xiàn)象的原因。結(jié)構(gòu)風(fēng)險最小化

（StructuralRiskMinimization，SRM）

經(jīng)驗風(fēng)險最小化原則在樣本有限（即較大）時是不合理的，此時一個小的經(jīng)驗風(fēng)險值并不能保證小的實際風(fēng)險值。為解決此問題，就需要在保證分類精度（即減小經(jīng)驗風(fēng)險）的同時，降低學(xué)習(xí)機器的VC維，從而使得學(xué)習(xí)機器在整個樣本集上的期望風(fēng)險得到控制，這就是結(jié)構(gòu)風(fēng)險最小化（SRM）原則的基本思想。結(jié)構(gòu)風(fēng)險最小化為我們提供了一種不同于經(jīng)驗風(fēng)險最小化的更科學(xué)的學(xué)習(xí)機器設(shè)計原則，顯然，利用結(jié)構(gòu)風(fēng)險最小化原則的思想，就可以完美解決神經(jīng)網(wǎng)絡(luò)中的過學(xué)習(xí)問題。支持向量機方法實際上就是這種思想的具體實現(xiàn)。

函數(shù)集子集：

VC維：

結(jié)構(gòu)風(fēng)險最小化示意圖

支持向量機

（SupportVectorMachine，SVM）90年代中期，在統(tǒng)計學(xué)習(xí)理論的基礎(chǔ)上發(fā)展出了一種通用的學(xué)習(xí)方法－－支持向量機。它根據(jù)有限的樣本信息在模型的復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折衷，以獲得最好的泛化能力。支持向量機在很多機器學(xué)習(xí)問題的應(yīng)用中已初步表現(xiàn)出很多優(yōu)于已有方法的性能。支持向量機的理論最初來自于對數(shù)據(jù)分類問題的處理。對于線性可分數(shù)據(jù)的二值分類，如果采用多層前向網(wǎng)絡(luò)來實現(xiàn)，其機理可以簡單描述為：系統(tǒng)隨機的產(chǎn)生一個超平面并移動它，直到訓(xùn)練集合中屬于不同類別的點正好位于該超平面的不同側(cè)面，就完成了對網(wǎng)絡(luò)的設(shè)計要求。但是這種機理決定了不能保證最終所獲得的分割平面位于兩個類別的中心，這對于分類問題的容錯性是不利的。

保證最終所獲得的分割平面位于兩個類別的中心對于分類問題的實際應(yīng)用是很重要的。支持向量機方法很巧妙地解決了這一問題。該方法的機理可以簡單描述為：尋找一個滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度的同時，能夠使超平面兩側(cè)的空白區(qū)域最大化；從理論上來說，支持向量機能夠?qū)崿F(xiàn)對線性可分數(shù)據(jù)的最優(yōu)分類。為了進一步解決非線性問題，Vapnik等人通過引入核映射方法轉(zhuǎn)化為高維空間的線性可分問題來解決。最優(yōu)分類超平面

（OptimalHyperplane

）對于兩類線性可分的情形，可以直接構(gòu)造最優(yōu)超平面，使得樣本集中的所有樣本滿足如下條件：（1）能被某一超平面正確劃分；（2）距該超平面最近的異類向量與超平面之間的距離最大，即分類間隔（margin）最大；以上兩個條件體現(xiàn)了結(jié)構(gòu)風(fēng)險最小化（SRM）的原則。保證經(jīng)驗風(fēng)險最小保證置信范圍最小設(shè)訓(xùn)練樣本輸入為，，對應(yīng)的期望輸出為

如果訓(xùn)練集中的所有向量均能被某超平面正確劃分，并且距離平面最近的異類向量之間的距離最大（即邊緣margin最大化），則該超平面為最優(yōu)超平面（OptimalHyperplane

）。最優(yōu)分類面示意圖

支持向量SupportVector其中距離超平面最近的異類向量被稱為支持向量（SupportVector），一組支持向量可以唯一確定一個超平面。SVM是從線性可分情況下的最優(yōu)分類面發(fā)展而來，其超平面記為：為使分類面對所有樣本正確分類并且具備分類間隔，就要求它滿足如下約束：可以計算出分類間隔為，因此構(gòu)造最優(yōu)超平面的問題就轉(zhuǎn)化為在約束式下求：

為了解決這個約束最優(yōu)化問題，引入下式所示的Lagrange函數(shù)：

其中為Lagrange乘數(shù)。約束最優(yōu)化問題的解由Lagrange函數(shù)的鞍點決定。

利用Lagrange優(yōu)化方法可以將上述二次規(guī)劃問題轉(zhuǎn)化為其對偶問題，即在約束條件：

下對求解下列函數(shù)的最大值：如果為最優(yōu)解，那么：以上是在不等式約束下求二次函數(shù)極值問題，是一個二次規(guī)劃問題（QuadraticProgramming，QP），存在唯一解。根據(jù)最優(yōu)性條件－－Karush-Kühn-Tucker條件（KKT條件），這個優(yōu)化問題的解必須滿足：對多數(shù)樣本將為零，取值不為零的所對應(yīng)的樣本即為支持向量，它們通常只是全體樣本中很少的一部分。

求解上述問題后得到的最優(yōu)分類函數(shù)是：在通過訓(xùn)練得到最優(yōu)超平面后,對于給定的未知樣本x，只需計算f(x)即可判斷x所屬的分類。

若訓(xùn)練樣本集是線性不可分的，或事先不知道它是否線性可分，將允許存在一些誤分類的點，此時引入一個非負松弛變量，約束條件變?yōu)?目標函數(shù)改為在以上約束條件下求：即折衷考慮最小錯分樣本和最大分類間隔。其中，C＞0為懲罰因子，控制對錯分樣本的懲罰程度。線性不可分情況和線性可分情況的差別就在于可分模式中的約束條件中的在不可分模式中換為了更嚴格的條件。除了這一修正，線性不可分情況的約束最優(yōu)化問題中權(quán)值和閾值的最優(yōu)值的計算都和線性可分情況中的過程是相同的。支持向量機

（SupportVectorMachine，SVM）在現(xiàn)實世界中，很多分類問題都是線性不可分的，即在原來的樣本空間中無法找到一個最優(yōu)的線性分類函數(shù)，這就使得支持向量機的應(yīng)用具有很大的局限性。但是可以設(shè)法通過非線性變換將原樣本空間的非線性問題轉(zhuǎn)化為另一個空間中的線性問題。SVM就是基于這一思想的。首先將輸入向量通過非線性映射變換到一個高維的特征向量空間，在該特征空間中構(gòu)造最優(yōu)分類超平面。

由于在上面的二次規(guī)劃（QP）問題中，無論是目標函數(shù)還是分類函數(shù)都只涉及內(nèi)積運算，如果采用核函數(shù)(KernelFunction)就可以避免在高維空間進行復(fù)雜運算，而通過原空間的函數(shù)來實現(xiàn)內(nèi)積運算。因此，選擇合適的內(nèi)積核函數(shù)

就可以實現(xiàn)某一非線性變換后的線性分類，而計算復(fù)雜度卻沒有增加多少，從而巧妙地解決了高維空間中計算帶來的“維數(shù)災(zāi)難”問題。

此時，相應(yīng)的決策函數(shù)化為：支持向量機求得的決策函數(shù)形式上類似于一個神經(jīng)網(wǎng)絡(luò)，其輸出是若干中間層節(jié)點的線性組合，而每一個中間層節(jié)點對應(yīng)于輸入樣本與一個支持向量的內(nèi)積，因此也被稱作是支持向量網(wǎng)絡(luò)。

支持向量機示意圖

選擇不同的核函數(shù)可以生成不同的支持向量機，常有以下幾種：（1）線性核函數(shù)：（2）多項式核函數(shù)：（3）Gauss核函數(shù)：（4）Sigmoid核函數(shù)：

一個具體核函數(shù)的例子假設(shè)數(shù)據(jù)是位于中的向量，選擇：

然后尋找滿足下述條件的空間H：使映射從映射到H且滿足：

可以選擇H=R3以及：用圖來表示該變換：SVM用于二維樣本分類支持向量機與多層前向網(wǎng)絡(luò)的比較

與徑向基函數(shù)網(wǎng)絡(luò)和多層感知器相比，支持向量機避免了在前者的設(shè)計中經(jīng)常使用的啟發(fā)式結(jié)構(gòu)，它不依賴于設(shè)計者的經(jīng)驗知識；而且支持向量機的理論基礎(chǔ)決定了它最終求得的是全局最優(yōu)值而不是局部極小值，也保證了它對于未知樣本的良好泛化能力而不會出現(xiàn)過學(xué)習(xí)現(xiàn)象。

支持向量機的分類學(xué)習(xí)算法

對于分類問題，用支持向量機方法進行求解的學(xué)習(xí)算法過程為：第一步

給定一組輸入樣本，

及其對應(yīng)的期望輸出；第二步選擇合適的核函數(shù)及相關(guān)參數(shù)；第三步在約束條件和下求解

得到最優(yōu)權(quán)值；第四步計算：；第五步對于待分類向量x

，計算：

為＋1或－1，決定x屬于哪一類。用于函數(shù)擬合的支持向量機

假定數(shù)據(jù)集。首先考慮用線性回歸函數(shù)擬合數(shù)據(jù)集X的問題。所有訓(xùn)練數(shù)據(jù)在精度下無誤差地用線性函數(shù)擬合，即：考慮到允許擬合誤差存在的情況：優(yōu)化目標函數(shù)為：對偶問題為：在約束條件下求下式的最大值?；貧w函數(shù)為：

支持向量機算法的研究與應(yīng)用支持向量機算法改進核函數(shù)的改進錯誤懲罰參數(shù)的選擇不敏感參數(shù)的選擇支持向量機解決多類劃分問題

支持向量機的應(yīng)用支持向量機算法改進傳統(tǒng)的利用標準二次型優(yōu)化技術(shù)解決對偶問題的方法可能是訓(xùn)練算法慢的主要原因。首先，SVM方法需要計算和存儲核函數(shù)矩陣，當樣本點數(shù)目較大時，需要很大的內(nèi)存，例如，當樣本點數(shù)目超過4000時，存儲核函數(shù)矩陣需要多達128MB內(nèi)存；其次，SVM在二次型尋優(yōu)過程中要進行大量的矩陣運算，多數(shù)情況下，尋優(yōu)算法是占用算法時間的主要部分。

近年來人們針對方法本身的特點提出了許多算法來解決對偶尋優(yōu)問題。這些算法的一個共同的思想就是采用分而治之的原則將原始QP問題分解為規(guī)模較小的子問題，通過循環(huán)解決一系列子問題來求得原問題的解。現(xiàn)有的訓(xùn)練算法分為三類：

“塊算法”（chunkingalgorithm）“Osuna

分解算法”

“SMO算法”

核函數(shù)的改進核函數(shù)的形式及其參數(shù)決定了分類器的類型和復(fù)雜程度。在不同的問題領(lǐng)域，核函數(shù)應(yīng)當具有不同的形式和參數(shù)，應(yīng)將領(lǐng)域知識引入進來，從數(shù)據(jù)依賴的角度選擇核函數(shù)。初步嘗試的方法有：

Amari－－利用黎曼幾何結(jié)構(gòu)方法來修改核函數(shù)；

Barzilay－－通過改進鄰近核來改進核函數(shù)；

Brailovsky－－局部核函數(shù)方法；

G.F.Smits－－多個核函數(shù)組合起來使用；

錯誤懲罰參數(shù)的選擇

錯分樣本懲罰參數(shù)C實現(xiàn)在錯分樣本的比例和算法復(fù)雜度之間的折衷。C值的確定一般是用戶根據(jù)經(jīng)驗給定的，隨意性很大，也很難知道所取C值的好壞性。如何消除C值選取的隨意性，而采用某種方法自動地選擇一個最佳的C值，這個問題目前尚未解決。

不敏感參數(shù)的選擇SVM通過參數(shù)控制回歸估計的精度，但取多少才能達到所期望的估計精度是不明確的，為此出現(xiàn)了許多新的SVM方法。

Sch?lkoph和Smola－－

-SVM方法

LinC-F

－－加權(quán)支持向量機，通過對每個樣本數(shù)據(jù)點采用不同的，來獲得更準確的回歸估計。支持向量機解決多類劃分問題

“多類支持向量機”（Multi-categorySupportVectorMachines，M-SVMs）。它們可以大致分為兩大類：（1）通過某種方式構(gòu)造一系列的兩類分類器并將它們組合在一起來實現(xiàn)多類分類；（2）直接在目標函數(shù)上進行改進，建立K分類支持向量機。一對多方法

(l-against-rest，1-a-r)

此算法是對于K類問題構(gòu)造K個兩類分類器。第i個SVM用第i類中的訓(xùn)練樣本作為正的訓(xùn)練樣本，而將其它的樣本作為負的訓(xùn)練樣本，即每個SVM分別將某一類的數(shù)據(jù)從其他類別中分離出來。測試時將未知樣本劃分到具有最大分類函數(shù)值的那類。缺點：泛化能力較差，且訓(xùn)練樣本數(shù)目大，訓(xùn)練困難。此外，該方法還有可能存在測試樣本同時屬于多類或不屬于任何一類的情況。

一對一方法

(l-against-1，1-a-1)該算法在K類訓(xùn)練樣本中構(gòu)造所有可能的兩類分類器，每類僅僅在K類中的兩類訓(xùn)練樣本之間訓(xùn)練，結(jié)果共構(gòu)造K(K-1)/2個分類器。組合這些兩類分類器很自然地用到了投票法，得票最多（MaxWins）的類為新點所屬的類。缺點：推廣誤差無界，分類器的數(shù)目K(K-1)/2隨類數(shù)K的增加急劇增加，導(dǎo)致在決策時速度很慢。此外，還可能存在一個樣本同時屬于多個類的情況。決策導(dǎo)向非循環(huán)圖SVM方法

（DecisionDirectedAcyclicGraph，DDAG）

在訓(xùn)練階段，其與1-a-1方法相同，對于K類問題，DDAG含有K(K-1)/2個兩類分類器。然而在決策階段，使用從根節(jié)點開始的導(dǎo)向非循環(huán)圖（DAG），具有K(K-1)/2個內(nèi)部節(jié)點以及K個葉子節(jié)點，每個內(nèi)部節(jié)點都是一個兩類分類器，葉子