支持向量機課件

第八章支持向量機支持向量機SVM(SupportVectorMachines)是由Vanpik領導的AT&TBell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術，SVM是一種基于統(tǒng)計學習理論的模式識別方法，主要應用于模式識別領域。

第八章支持向量機支持向量機SVM(SupportV

發(fā)展：90年代，由于統(tǒng)計學習理論的實現(xiàn)和神經(jīng)網(wǎng)絡等較新興的機器學習方法的研究遇到一些重要的困難，如，如何確定網(wǎng)絡結構的問題、過學習與欠學習問題、局部極小點問題等，使得SVM迅速發(fā)展和完善。SVM優(yōu)勢：小樣本、非線性及高維模式識別問題，函數(shù)擬合等其他機器學習問題運用:模式識別、回歸分析、函數(shù)估計、時間序列預測等領域，文本識別、手寫字體識別、人臉圖像識別、基因分類、時間序列預測等。發(fā)展：90年代，由于統(tǒng)計學習理論的實現(xiàn)和神經(jīng)網(wǎng)絡等較新興的第八章支持向量機8.1概述8.2統(tǒng)計學習理論

8.3支持向量機（SVM）8.4核函數(shù)8.5SVM的算法及多類SVM8.6SVM的應用現(xiàn)狀8.7小結第八章支持向量機8.1概述8.1概述基于數(shù)據(jù)的機器學習：從觀測數(shù)據(jù)(樣本)出發(fā)尋找數(shù)據(jù)中的模式和數(shù)據(jù)中的函數(shù)依賴規(guī)律，利用這些模式和函數(shù)依賴對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行分類、識別和預測。分為三種：一、經(jīng)典的(參數(shù))統(tǒng)計估計算法----參數(shù)的相關形式是已知的，訓練樣本用來估計參數(shù)的值。局限性:1.需要已知樣本分布形式，2.假設樣本數(shù)目趨于無窮大，但在實際問題中，樣本數(shù)往往是有限的。8.1概述基于數(shù)據(jù)的機器學習：從觀測數(shù)據(jù)(樣本)出發(fā)尋找數(shù)

二、人工神經(jīng)網(wǎng)絡(ANN)----利用已知樣本建立非線性模型，克服了傳統(tǒng)參數(shù)估計方法的困難。應用廣泛，但是現(xiàn)在的神經(jīng)網(wǎng)絡技術研究理論基石不足，有較大的經(jīng)驗成分，在技術上仍存在一些不易解決的問題。三、支持向量機(SVM)，——統(tǒng)計學習理論。SVM是統(tǒng)計學習理論中最年輕的內(nèi)容，也是最實用的部分，已經(jīng)成為神經(jīng)網(wǎng)絡和機器學習的研究熱點之一。二、人工神經(jīng)網(wǎng)絡(ANN)----利用已知樣本建立非線性模支持向量機的基本思想訓練數(shù)據(jù)集非線性地映射到一個高維特征空間目的：把在輸入空間中的線性不可分數(shù)據(jù)集映射到高維特征空間后變?yōu)槭蔷€性可分的數(shù)據(jù)集在特征空間建立一個具有最大隔離距離的最優(yōu)分隔超平面支持向量機的基本思想訓練數(shù)據(jù)集非線性地映射到一個高維特征空間

存在多個分類超平面可以把兩個類分離開來，但是只有一個是最優(yōu)分類超平面，它與兩個類之間最近向量的距離最大。支持向量機的目的：找出最優(yōu)的分類超平面。

8.2統(tǒng)計學習理論統(tǒng)計學習理論誕生于20世紀60～70年代，主要創(chuàng)立者:Vladimir

N.

Vapnik，90年代中期發(fā)展比較成熟，受到世界機器學習界的廣泛重視。統(tǒng)計學習理論：一種專門研究小樣本情況下機器學習規(guī)律的理論。針對小樣本統(tǒng)計問題建立了一套新的理論體系，該體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結果。8.2統(tǒng)計學習理論統(tǒng)計學習理論誕生于20世紀60～70年代8.2.1學習問題的表示樣本學習的一般模型產(chǎn)生器(G)：產(chǎn)生隨機向量，它們是從固定但未知的概率分布函數(shù)F(x)中獨立抽取的。訓練器(S)：對每個輸入向量x返回一個輸出值y，產(chǎn)生輸出的根據(jù)是同樣固定但未知的條件分布函數(shù)F(y|x)。學習機器(LM)：它能夠實現(xiàn)一定的函數(shù)集，其中∧是參數(shù)集合。在學習過程中，學習機器LM觀察數(shù)據(jù)對(x,y)。在訓練之后，學習機器必須對任意輸入x，使之接近訓練器的響應y。8.2.1學習問題的表示樣本學習的一般模型8.2.2期望風險和經(jīng)驗風險給定輸入x下訓練器響應y與學習機器給出的響應之間的損失記作就是風險泛函，即預測的期望(實際)風險。稱為經(jīng)驗風險。8.2.2期望風險和經(jīng)驗風險給定輸入x下訓練器響應y與學習8.3支持向量機（SVM）一種經(jīng)典的二分類模型，基本模型定義為特征空間中最大間隔的線性分類器，其學習的優(yōu)化目標便是間隔最大化，因此支持向量機本身可以轉化為一個凸二次規(guī)劃求解的問題。8.3支持向量機（SVM）一種經(jīng)典的二分類模型，基本模型定函數(shù)間隔與幾何間隔對于二分類學習，假設數(shù)據(jù)是線性可分的分類學習：找到一個合適的超平面，該超平面能夠將不同類別的樣本分開類似二維平面使用ax+by+c=0來表示，超平面實際上表示的就是高維的平面，如下圖所示：函數(shù)間隔與幾何間隔對于二分類學習，假設數(shù)據(jù)是線性可分的8.3.1線性可分支持向量機劃分超平面：其中，為法向量。樣本空間中任意點x到超平面(w,b)的距離寫為：8.3.1線性可分支持向量機劃分超平面：8.3.1線性可分支持向量機假設超平面能正確分類，則：兩個異類支持向量到超平面的距離之和為：8.3.1線性可分支持向量機假設超平面能正確分類，則：8.3.1線性可分支持向量機欲找最大間隔的劃分超平面，即找滿足約束的參數(shù)w,b使得最大，即：8.3.1線性可分支持向量機欲找最大間隔的劃分超平面，即找8.3.1線性可分支持向量機等價于：8.3.1線性可分支持向量機等價于：8.3.1對偶問題8.3.1對偶問題支持向量機問題可以等價為求解下面的二次規(guī)劃問題：最小化泛函：約束條件為不等式類型該問題的解是由下面的拉格朗日泛函的鞍點給出的：其中為拉格朗日乘子。 問題的對偶問題為：最大化泛函 約束條件為： 這樣原問題的解為：

支持向量機問題可以等價為求解下面的二次規(guī)劃問題：由拉格朗日可得到原問題的Karush-Kuhn-Tucker(KKT)條件：根據(jù)優(yōu)化理論，是原問題的解當且僅當滿足KKT條件。在對偶問題或KKT條件中，每個訓練數(shù)據(jù)都對應一個拉格朗日乘子，其中與對應的數(shù)據(jù)成為支持向量。

由拉格朗日可得到原問題的Karush-Kuhn-Tucker利用任一支持向量和KKT條件，可求出

一般情況下，為了準確，常求出多個b值，然后取平均值，或者

其中，用表示屬于第一類的任一支持向量，用表示屬于第二類的任一支持向量。最后的最優(yōu)超平面方程：

最終完成學習過程。

利用任一支持向量和KKT條件8.3.2線性不可分與軟間隔最大化首先我們引入松弛變量來表示經(jīng)驗風險，將原約束條件變?yōu)椋?/p>

這樣，樣本數(shù)據(jù)的經(jīng)驗風險在一定程度上可以表示為：

其中參數(shù)，代表經(jīng)驗風險的某種度量方式。給定樣本數(shù)據(jù)后，我們在容許結構的某個子集下最小化經(jīng)驗風險，問題可以描述為：最小化泛函：約束條件為：8.3.2線性不可分與軟間隔最大化首先我們引入松弛變量這個問題可以等價為在約束條件下最小化泛函：這里的C是一個給定的值。原問題的對偶形式為：只是約束條件變?yōu)椋?/p>

這樣原問題的解為：

這個問題可以等價為在約束條件下最小化泛函：8.4核函數(shù)支持向量機的關鍵在于核函數(shù)。低維空間向量集通常難于劃分，解決的方法是將它們映射到高維空間，但這個辦法帶來的困難就是計算復雜度的增加，而核函數(shù)正好巧妙地解決了這個問題。只要選用適當?shù)暮撕瘮?shù)，我們就可以得到高維空間的分類函數(shù)。在SVM理論中，采用不同的核函數(shù)將導致不同的SVM算法。8.4核函數(shù)支持向量機的關鍵在于核函數(shù)。8.4核函數(shù)首先定義映射，是輸入空間，H是高維內(nèi)積空間，稱為特征空間，稱為特征映射，然后在H中構造最優(yōu)超平面。在特征空間中的學習過程同前面一樣，對偶問題為：約束條件不變：8.4核函數(shù)首先定義映射，核函數(shù)的思想：在輸入空間的變量直接計算特征空間中的內(nèi)積，即其中，屬于輸入空間，函數(shù)即為核函數(shù)。這樣，只要定義了核函數(shù)，就不必真的進行非線性變換，更沒有必要知道采用的非線性變換的形式，所以我們只要構造輸入空間的一個核函數(shù)即可。

核函數(shù)：核函數(shù)的思想：在輸入空間的變量直接計算特征空間中的定理8.6對于任意的對稱函數(shù)，它是某個特征空間的內(nèi)積運算的充分必要條件是，對于任意的且，有

事實上這一條件并不難滿足。這樣我們就可以得到輸入空間中的非線性決策函數(shù)

它等價于在高維特征空間中的線性決策函數(shù)。

定理8.6對于任意的對稱函數(shù)8.4.2核函數(shù)的分類⑴多項式核函數(shù)

所得到的是ｄ階多項式分類器：

⑵徑向基函數(shù) 經(jīng)典的徑向基函數(shù)的判別函數(shù)為：

最通常采用的核函數(shù)為高斯函數(shù)：8.4.2核函數(shù)的分類⑴多項式核函數(shù)⑶多層感知機SVM采用Sigmoid函數(shù)作為內(nèi)積，這時就實現(xiàn)了包含一個隱層的多層感知機，隱層節(jié)點數(shù)目由算法自動確定。滿足mercer條件的Sigmoid函數(shù)為：

⑶多層感知機8.5SVM的算法及多類SVM目前SVM的訓練算法一般采用循環(huán)迭代解決對偶尋優(yōu)問題：將原問題分解成為若干子問題，按照某種迭代策略，通過反復求解子問題，最終使結果收斂到原問題的最優(yōu)解。根據(jù)子問題的劃分和迭代策略的不同，大致可以分為：⑴塊算法ChunkingAlgorithm：考慮到去掉Lagrange乘子等于零的訓練樣本不會影響原問題的解，采用選擇一部分樣本構成工作樣本集進行訓練，剔除其中的非支持向量，并用訓練結果對剩余樣本進行檢驗，將不符合KKT條件的樣本與此次結果的支持向量合并成為一個新的工作樣本集，然后重新訓練，如此重復下去直到獲得最優(yōu)結果。8.5SVM的算法及多類SVM目前SVM的訓練算法一般采用

Chunking算法將矩陣規(guī)模從訓練樣本數(shù)的平方減少到具有非零Lagrange乘數(shù)的樣本數(shù)的平方，在很大程度上降低了訓練過程對存儲容量的要求。Chunking算法能夠大大提高訓練速度，尤其是當支持向量的數(shù)目遠遠小于訓練樣本的數(shù)目時。然而，如果支持向量個數(shù)比較多，隨著算法迭代次數(shù)的增多，所選的塊也會越來越大，算法的訓練速度依舊會變得十分緩慢。Chunking算法將矩陣規(guī)模從訓練樣本數(shù)的平方減少到具有

(2)分解算法(DecompositionAlgorithm)分解算法最早由Osuna等人提出，是目前有效解決大規(guī)模問題的主要方法。分解算法將二次規(guī)劃問題分解成一系列規(guī)模較小的二次規(guī)劃子問題，進行迭代求解。在每次迭代中，選取拉格朗日乘子分量的一個子集做為工作集，利用傳統(tǒng)優(yōu)化算法求解一個二次規(guī)劃的子問題。該算法的關鍵在于選擇一種最優(yōu)的工作集選擇算法，但是Osuna在工作集的選取中采用了隨機的方法，因此限制了算法的收斂速度。Joachims在Osuna分解算法的基礎上，關于工作集的選擇做了重要改進。其主要思想是，如果存在不滿足KTT條件的樣本，利用最速下降法，在最速下降方向中存在個樣本，然后以這個樣本構成工作集，在此工作集上解決QP問題，直到所有樣本滿足KTT條件。Joachims的改進大幅度提高了分解算法的收斂速度，并且他利用這些方法實現(xiàn)了SVMlight算法。(2)分解算法(DecompositionAlgorit

由JohnC.Platt提出的序列最小優(yōu)化（SequentialMinimalOptimization,SMO）算法可以說是Osuna分解算法的一個特例，工作集中只有2個樣本，其優(yōu)點是針對2個樣本的二次規(guī)劃問題可以有解析解的形式，從而避免了多樣本情況下的數(shù)值解不穩(wěn)定及耗時問題，同時也不需要大的矩陣存儲空間，特別適合稀疏樣本。其工作集的選擇不是傳統(tǒng)的最陡下降法，而是啟發(fā)式。通過兩個嵌套的循環(huán)來尋找待優(yōu)化的樣本，然后在內(nèi)環(huán)中選擇另一個樣本，完成一次優(yōu)化，再循環(huán)，進行下一次優(yōu)化，直到全部樣本都滿足最優(yōu)條件。SMO算法主要耗時在最優(yōu)條件的判斷上，所以應尋找最合理即計算代價最低的最優(yōu)條件判別式。由JohnC.Platt提出的序列最小優(yōu)化（(3)增量學習增量學習是機器學習系統(tǒng)在處理新增樣本時，能夠只對原學習結果中與新樣本有關的部分進行增加修改或刪除操作，與之無關的部分則不被觸及。增量訓練算法的一個突出特點是支持向量機的學習不是一次離線進行的，而是一個數(shù)據(jù)逐一加入反復優(yōu)化的過程。(3)增量學習新型SVM（1）粒度支持向量機GSVMGSVM由TangYC于2004年提出的，主要思想：通過常用的粒度劃分方法構建粒度空間獲得一系列信息粒，然后在每個信息粒上進行學習，最后通過聚合信息粒上的信息（或數(shù)據(jù)、規(guī)則知識、屬性等）獲得最終的支持向量機決策函數(shù)。

這一學習機制通過數(shù)據(jù)的粒化可以將一個線性不可分問題轉化為一系列線性可分問題，從而獲得多個決策函數(shù)；同時，這一學習機制也使得數(shù)據(jù)的泛化性能增強，即可在SVM的訓練中得到間隔更寬的超平面。新型SVM（1）粒度支持向量機GSVM（2）模糊支持向量機FSVM為了克服噪聲和野值點對支持向量機的影響，臺灣學者ChunfuLin和ShengdeWang將模糊數(shù)學和支持向量機相結合，提出了模糊支持向量機，主要用來處理訓練樣本中的噪聲數(shù)據(jù)。主要思想：針對支持向量機對訓練樣本內(nèi)的噪音和孤立點的敏感性，在訓練樣本集中增加一項：隸屬度，并賦予支持向量較高的隸屬度，而非支持向量及噪聲野值點賦予較小的隸屬度，從而降低了非支持向量、噪聲和野值點對最優(yōu)超平面的影響。（2）模糊支持向量機FSVM為了克服噪聲和野值點對支持向量機（3）孿生支持向量機TSVMs2007年，Jayadeva和KhemchandaniR提出了一種二值數(shù)據(jù)的分類器——孿生支持向量機(又稱雙分界面支持向量機)TWSVMs在形式上類似于傳統(tǒng)的支持向量機，具有傳統(tǒng)支持向量機的優(yōu)點，且對大規(guī)模數(shù)據(jù)具有更好的處理能力。TWSVMs為兩個類各自得到一個分類平面，屬于每個類的數(shù)據(jù)盡量圍繞在與之相對應的分類平面周圍，然后TWSVMs通過優(yōu)化一對分類平面來構建分類超平面。即：TWSVMs解決一對QP問題，而SVM則是解決一個QP問題，但是在TWSVMs中，其中一個類的數(shù)據(jù)要作為另一個QP問題的約束條件，反之亦然。（3）孿生支持向量機TSVMs2007年，Jayadeva8.5.2多類問題中的SVM類模式識別問題是為個樣本構成一個決策函數(shù)。由于SVM是解決兩類問題的有效方法，因此用SVM解多類問題的方法通常將問題轉化為兩類問題，然后對結果進行處理。一般常用的方法有以下幾種：⑴One-against-the-rest方法：在第類和其他類之間構建超平面。⑵One-against-one方法：為任意兩個類構建超平面，共需個。⑶K-classSVM：同時為所有的類構造一個分類超平面。8.5.2多類問題中的SVM類模式識別問題是為8.6SVM的應用現(xiàn)狀⑴人臉檢測、驗證和識別Osuna最早將SVM應用于人臉檢測，并取得了較好的效果。其方法是直接訓練非線性SVM分類器完成人臉與非人臉的分類。大量實驗結果表明這種方法不僅具有較高的檢測率和較低的誤檢率，而且具有較快的速度。⑵說話人/語音識別

建立SVM和HMM（隱式馬爾可夫模型）的混合模型。HMM適合處理連續(xù)信號，而SVM適合于分類問題；HMM的結果反映了同類樣本的相似度，而SVM的輸出結果則體現(xiàn)了異類樣本間的差異。

8.6SVM的應用現(xiàn)狀⑴人臉檢測、驗證8.6SVM的應用現(xiàn)狀⑶文字/手寫體識別貝爾實驗室對美國郵政手寫數(shù)字庫進行的實驗，人工識別平均錯誤率為2.5%，專門針對該特定問題設計的5層神經(jīng)網(wǎng)絡錯誤率為5.1%（其中利用率大量先驗知識），而用3種SVM方法（采用3種核函數(shù)）得到的錯誤率分別為4.0%、4.1%和4.2%，且是直接采用16×16的字符點陣作為輸入，表明了SVM的優(yōu)越性能。

8.6SVM的應用現(xiàn)狀⑶文字/手寫體識別8.6SVM的應用現(xiàn)狀

⑷圖像處理：a圖像過濾,支持向量機分類和最近鄰方法校驗的多層系圖像處理框架，達到85%以上的準確率。b視頻字幕提取,首先將原始圖像幀分割為N×N的子塊，提取每個子塊的灰度特征；然后使用預先訓練好的SVM分類機進行字幕子塊和非字幕子塊的分類；最后結合金字塔模型和后期處理過程，實現(xiàn)視頻圖像字幕區(qū)域的自動定位提取。

c圖像分類和檢索,以SVM為分類器，在每次反饋中對用戶標記的正例和反例樣本進行學習，并根據(jù)學習所得的模型進行檢索，使用由9918幅圖像組成的圖像庫進行實驗，結果表明，在有限訓練樣本情況下具有良好的泛化能力。8.6SVM的應用現(xiàn)狀⑷圖像處理：8.6SVM的應用現(xiàn)狀

目前，國際上關于SVM理論的討論和深入地研究逐漸廣泛，我國國內(nèi)在此領域的研究尚處在萌芽狀態(tài)。我們需要及時學習掌握有關的理論知識，開展有效的研究工作，使我們在這個具有重要意義的領域中盡快趕上國際水平，跟上國際發(fā)展步伐。8.6SVM的應用現(xiàn)狀目前，國際上關于SVM8.7小結SVM是基于統(tǒng)計學習理論中的經(jīng)驗風險最小化原則的一種機器學習，解決了對非線性函數(shù)求解超平面的問題。SVM可以有效地解決小樣本、非線性及高維模式識別問題。SVM用于模式分類的觀點可以簡單地闡述為：首先，無論問題是否為線性的，選擇相應的核函數(shù)，均可將輸入向量映射到一個高維空間；其次，用最優(yōu)化理論方法尋求最優(yōu)超平面將二類分開?，F(xiàn)在，統(tǒng)計學習理論和SVM方法尚處在發(fā)展階段，很多方面還不完善，許多理論在算法中尚未實現(xiàn)；SVM算法的某些理論解釋并非完美，SVM的應用目前僅是在有限的實驗中觀察到的現(xiàn)象，期待著理論證明。8.7小結SVM是基于統(tǒng)計學習理論中的經(jīng)驗風險最小化原則的習題1.比較經(jīng)驗風險最小化和結構風險最小化的原理。2.描述支持向量機的基本思想和數(shù)學模型。3.簡述支持向量機解決非線性可分問題的基本思想。4.描述支持向量機的核函數(shù)構造方法。習題1.比較經(jīng)驗風險最小化和結構風險最小化的原理。第八章支持向量機支持向量機SVM(SupportVectorMachines)是由Vanpik領導的AT&TBell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術，SVM是一種基于統(tǒng)計學習理論的模式識別方法，主要應用于模式識別領域。

第八章支持向量機支持向量機SVM(SupportV

發(fā)展：90年代，由于統(tǒng)計學習理論的實現(xiàn)和神經(jīng)網(wǎng)絡等較新興的機器學習方法的研究遇到一些重要的困難，如，如何確定網(wǎng)絡結構的問題、過學習與欠學習問題、局部極小點問題等，使得SVM迅速發(fā)展和完善。SVM優(yōu)勢：小樣本、非線性及高維模式識別問題，函數(shù)擬合等其他機器學習問題運用:模式識別、回歸分析、函數(shù)估計、時間序列預測等領域，文本識別、手寫字體識別、人臉圖像識別、基因分類、時間序列預測等。發(fā)展：90年代，由于統(tǒng)計學習理論的實現(xiàn)和神經(jīng)網(wǎng)絡等較新興的第八章支持向量機8.1概述8.2統(tǒng)計學習理論

8.3支持向量機（SVM）8.4核函數(shù)8.5SVM的算法及多類SVM8.6SVM的應用現(xiàn)狀8.7小結第八章支持向量機8.1概述8.1概述基于數(shù)據(jù)的機器學習：從觀測數(shù)據(jù)(樣本)出發(fā)尋找數(shù)據(jù)中的模式和數(shù)據(jù)中的函數(shù)依賴規(guī)律，利用這些模式和函數(shù)依賴對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行分類、識別和預測。分為三種：一、經(jīng)典的(參數(shù))統(tǒng)計估計算法----參數(shù)的相關形式是已知的，訓練樣本用來估計參數(shù)的值。局限性:1.需要已知樣本分布形式，2.假設樣本數(shù)目趨于無窮大，但在實際問題中，樣本數(shù)往往是有限的。8.1概述基于數(shù)據(jù)的機器學習：從觀測數(shù)據(jù)(樣本)出發(fā)尋找數(shù)

二、人工神經(jīng)網(wǎng)絡(ANN)----利用已知樣本建立非線性模型，克服了傳統(tǒng)參數(shù)估計方法的困難。應用廣泛，但是現(xiàn)在的神經(jīng)網(wǎng)絡技術研究理論基石不足，有較大的經(jīng)驗成分，在技術上仍存在一些不易解決的問題。三、支持向量機(SVM)，——統(tǒng)計學習理論。SVM是統(tǒng)計學習理論中最年輕的內(nèi)容，也是最實用的部分，已經(jīng)成為神經(jīng)網(wǎng)絡和機器學習的研究熱點之一。二、人工神經(jīng)網(wǎng)絡(ANN)----利用已知樣本建立非線性模支持向量機的基本思想訓練數(shù)據(jù)集非線性地映射到一個高維特征空間目的：把在輸入空間中的線性不可分數(shù)據(jù)集映射到高維特征空間后變?yōu)槭蔷€性可分的數(shù)據(jù)集在特征空間建立一個具有最大隔離距離的最優(yōu)分隔超平面支持向量機的基本思想訓練數(shù)據(jù)集非線性地映射到一個高維特征空間

存在多個分類超平面可以把兩個類分離開來，但是只有一個是最優(yōu)分類超平面，它與兩個類之間最近向量的距離最大。支持向量機的目的：找出最優(yōu)的分類超平面。

8.2統(tǒng)計學習理論統(tǒng)計學習理論誕生于20世紀60～70年代，主要創(chuàng)立者:Vladimir

N.

Vapnik，90年代中期發(fā)展比較成熟，受到世界機器學習界的廣泛重視。統(tǒng)計學習理論：一種專門研究小樣本情況下機器學習規(guī)律的理論。針對小樣本統(tǒng)計問題建立了一套新的理論體系，該體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結果。8.2統(tǒng)計學習理論統(tǒng)計學習理論誕生于20世紀60～70年代8.2.1學習問題的表示樣本學習的一般模型產(chǎn)生器(G)：產(chǎn)生隨機向量，它們是從固定但未知的概率分布函數(shù)F(x)中獨立抽取的。訓練器(S)：對每個輸入向量x返回一個輸出值y，產(chǎn)生輸出的根據(jù)是同樣固定但未知的條件分布函數(shù)F(y|x)。學習機器(LM)：它能夠實現(xiàn)一定的函數(shù)集，其中∧是參數(shù)集合。在學習過程中，學習機器LM觀察數(shù)據(jù)對(x,y)。在訓練之后，學習機器必須對任意輸入x，使之接近訓練器的響應y。8.2.1學習問題的表示樣本學習的一般模型8.2.2期望風險和經(jīng)驗風險給定輸入x下訓練器響應y與學習機器給出的響應之間的損失記作就是風險泛函，即預測的期望(實際)風險。稱為經(jīng)驗風險。8.2.2期望風險和經(jīng)驗風險給定輸入x下訓練器響應y與學習8.3支持向量機（SVM）一種經(jīng)典的二分類模型，基本模型定義為特征空間中最大間隔的線性分類器，其學習的優(yōu)化目標便是間隔最大化，因此支持向量機本身可以轉化為一個凸二次規(guī)劃求解的問題。8.3支持向量機（SVM）一種經(jīng)典的二分類模型，基本模型定函數(shù)間隔與幾何間隔對于二分類學習，假設數(shù)據(jù)是線性可分的分類學習：找到一個合適的超平面，該超平面能夠將不同類別的樣本分開類似二維平面使用ax+by+c=0來表示，超平面實際上表示的就是高維的平面，如下圖所示：函數(shù)間隔與幾何間隔對于二分類學習，假設數(shù)據(jù)是線性可分的8.3.1線性可分支持向量機劃分超平面：其中，為法向量。樣本空間中任意點x到超平面(w,b)的距離寫為：8.3.1線性可分支持向量機劃分超平面：8.3.1線性可分支持向量機假設超平面能正確分類，則：兩個異類支持向量到超平面的距離之和為：8.3.1線性可分支持向量機假設超平面能正確分類，則：8.3.1線性可分支持向量機欲找最大間隔的劃分超平面，即找滿足約束的參數(shù)w,b使得最大，即：8.3.1線性可分支持向量機欲找最大間隔的劃分超平面，即找8.3.1線性可分支持向量機等價于：8.3.1線性可分支持向量機等價于：8.3.1對偶問題8.3.1對偶問題支持向量機問題可以等價為求解下面的二次規(guī)劃問題：最小化泛函：約束條件為不等式類型該問題的解是由下面的拉格朗日泛函的鞍點給出的：其中為拉格朗日乘子。 問題的對偶問題為：最大化泛函 約束條件為： 這樣原問題的解為：

支持向量機問題可以等價為求解下面的二次規(guī)劃問題：由拉格朗日可得到原問題的Karush-Kuhn-Tucker(KKT)條件：根據(jù)優(yōu)化理論，是原問題的解當且僅當滿足KKT條件。在對偶問題或KKT條件中，每個訓練數(shù)據(jù)都對應一個拉格朗日乘子，其中與對應的數(shù)據(jù)成為支持向量。

由拉格朗日可得到原問題的Karush-Kuhn-Tucker利用任一支持向量和KKT條件，可求出

一般情況下，為了準確，常求出多個b值，然后取平均值，或者

其中，用表示屬于第一類的任一支持向量，用表示屬于第二類的任一支持向量。最后的最優(yōu)超平面方程：

最終完成學習過程。

利用任一支持向量和KKT條件8.3.2線性不可分與軟間隔最大化首先我們引入松弛變量來表示經(jīng)驗風險，將原約束條件變?yōu)椋?/p>

這樣，樣本數(shù)據(jù)的經(jīng)驗風險在一定程度上可以表示為：

其中參數(shù)，代表經(jīng)驗風險的某種度量方式。給定樣本數(shù)據(jù)后，我們在容許結構的某個子集下最小化經(jīng)驗風險，問題可以描述為：最小化泛函：約束條件為：8.3.2線性不可分與軟間隔最大化首先我們引入松弛變量這個問題可以等價為在約束條件下最小化泛函：這里的C是一個給定的值。原問題的對偶形式為：只是約束條件變?yōu)椋?/p>

這樣原問題的解為：

這個問題可以等價為在約束條件下最小化泛函：8.4核函數(shù)支持向量機的關鍵在于核函數(shù)。低維空間向量集通常難于劃分，解決的方法是將它們映射到高維空間，但這個辦法帶來的困難就是計算復雜度的增加，而核函數(shù)正好巧妙地解決了這個問題。只要選用適當?shù)暮撕瘮?shù)，我們就可以得到高維空間的分類函數(shù)。在SVM理論中，采用不同的核函數(shù)將導致不同的SVM算法。8.4核函數(shù)支持向量機的關鍵在于核函數(shù)。8.4核函數(shù)首先定義映射，是輸入空間，H是高維內(nèi)積空間，稱為特征空間，稱為特征映射，然后在H中構造最優(yōu)超平面。在特征空間中的學習過程同前面一樣，對偶問題為：約束條件不變：8.4核函數(shù)首先定義映射，核函數(shù)的思想：在輸入空間的變量直接計算特征空間中的內(nèi)積，即其中，屬于輸入空間，函數(shù)即為核函數(shù)。這樣，只要定義了核函數(shù)，就不必真的進行非線性變換，更沒有必要知道采用的非線性變換的形式，所以我們只要構造輸入空間的一個核函數(shù)即可。

核函數(shù)：核函數(shù)的思想：在輸入空間的變量直接計算特征空間中的定理8.6對于任意的對稱函數(shù)，它是某個特征空間的內(nèi)積運算的充分必要條件是，對于任意的且，有

事實上這一條件并不難滿足。這樣我們就可以得到輸入空間中的非線性決策函數(shù)

它等價于在高維特征空間中的線性決策函數(shù)。

定理8.6對于任意的對稱函數(shù)8.4.2核函數(shù)的分類⑴多項式核函數(shù)

所得到的是ｄ階多項式分類器：

⑵徑向基函數(shù) 經(jīng)典的徑向基函數(shù)的判別函數(shù)為：

最通常采用的核函數(shù)為高斯函數(shù)：8.4.2核函數(shù)的分類⑴多項式核函數(shù)⑶多層感知機SVM采用Sigmoid函數(shù)作為內(nèi)積，這時就實現(xiàn)了包含一個隱層的多層感知機，隱層節(jié)點數(shù)目由算法自動確定。滿足mercer條件的Sigmoid函數(shù)為：

⑶多層感知機8.5SVM的算法及多類SVM目前SVM的訓練算法一般采用循環(huán)迭代解決對偶尋優(yōu)問題：將原問題分解成為若干子問題，按照某種迭代策略，通過反復求解子問題，最終使結果收斂到原問題的最優(yōu)解。根據(jù)子問題的劃分和迭代策略的不同，大致可以分為：⑴塊算法ChunkingAlgorithm：考慮到去掉Lagrange乘子等于零的訓練樣本不會影響原問題的解，采用選擇一部分樣本構成工作樣本集進行訓練，剔除其中的非支持向量，并用訓練結果對剩余樣本進行檢驗，將不符合KKT條件的樣本與此次結果的支持向量合并成為一個新的工作樣本集，然后重新訓練，如此重復下去直到獲得最優(yōu)結果。8.5SVM的算法及多類SVM目前SVM的訓練算法一般采用

Chunking算法將矩陣規(guī)模從訓練樣本數(shù)的平方減少到具有非零Lagrange乘數(shù)的樣本數(shù)的平方，在很大程度上降低了訓練過程對存儲容量的要求。Chunking算法能夠大大提高訓練速度，尤其是當支持向量的數(shù)目遠遠小于訓練樣本的數(shù)目時。然而，如果支持向量個數(shù)比較多，隨著算法迭代次數(shù)的增多，所選的塊也會越來越大，算法的訓練速度依舊會變得十分緩慢。Chunking算法將矩陣規(guī)模從訓練樣本數(shù)的平方減少到具有

(2)分解算法(DecompositionAlgorithm)分解算法最早由Osuna等人提出，是目前有效解決大規(guī)模問題的主要方法。分解算法將二次規(guī)劃問題分解成一系列規(guī)模較小的二次規(guī)劃子問題，進行迭代求解。在每次迭代中，選取拉格朗日乘子分量的一個子集做為工作集，利用傳統(tǒng)優(yōu)化算法求解一個二次規(guī)劃的子問題。該算法的關鍵在于選擇一種最優(yōu)的工作集選擇算法，但是Osuna在工作集的選取中采用了隨機的方法，因此限制了算法的收斂速度。Joachims在Osuna分解算法的基礎上，關于工作集的選擇做了重要改進。其主要思想是，如果存在不滿足KTT條件的樣本，利用最速下降法，在最速下降方向中存在個樣本，然后以這個樣本構成工作集，在此工作集上解決QP問題，直到所有樣本滿足KTT條件。Joachims的改進大幅度提高了分解算法的收斂速度，并且他利用這些方法實現(xiàn)了SVMlight算法。(2)分解算法(DecompositionAlgorit

由JohnC.Platt提出的序列最小優(yōu)化（SequentialMinimalOptimization,SMO）算法可以說是Osuna分解算法的一個特例，工作集中只有2個樣本，其優(yōu)點是針對2個樣本的二次規(guī)劃問題可以有解析解的形式，從而避免了多樣本情況下的數(shù)值解不穩(wěn)定及耗時問題，同時也不需要大的矩陣存儲空間，特別適合稀疏樣本。其工作集的選擇不是傳統(tǒng)的最陡下降法，而是啟發(fā)式。通過兩個嵌套的循環(huán)來尋找待優(yōu)化的樣本，然后在內(nèi)環(huán)中選擇另一個樣本，完成一次優(yōu)化，再循環(huán)，進行下一次優(yōu)化，直到全部樣本都滿足最優(yōu)條件。SMO算法主要耗時在最優(yōu)條件的判斷上，所以應尋找最合理即計算代價最低的最優(yōu)條件判別式。由JohnC.Platt提出的序列最小優(yōu)化（(3)增量學習增量學習是機器學習系統(tǒng)在處理新增樣本時，能夠只對原學習結果中與新樣本有關的部分進行增加修改或刪除操作，與之無關的部分則不被觸及。增量訓練算法的一個突出特點是支持向量機的學習不是一次離線進行的，而是一個數(shù)據(jù)逐一加入反復優(yōu)化的過程。(3)增量學習新型SVM（1）粒度支持向量機GSVMGSVM由TangYC于2004年提出的，主要思想：通過常用的粒度劃分方法構建粒度空間獲得一系列信息粒，然后在每個信息粒上進行學習，最后通過聚合信息粒上的信息（或數(shù)據(jù)、規(guī)則知識、屬性等）獲得最終的支持向量機決策函數(shù)。

這一學習機制通過數(shù)據(jù)的?；梢詫⒁粋€線性不可分問題轉化為一系列線性可分問題，從而獲得多個決策函數(shù)；同時，這一學習機制也使得數(shù)據(jù)的泛化性能增強，即可在SVM的訓練中得到間隔更寬的超平面。新型SVM（1）粒度支持向量機GSVM（2）模糊支持向量機FSVM為了克服噪聲和野值點對支持向量機的影響，臺灣學者ChunfuLin和ShengdeWang將模糊數(shù)學和支持向量機相結合，提出了模糊支持向量機，主要用來處理訓練樣本中的噪聲數(shù)據(jù)。主要思想：針對支持向量機對訓練樣本內(nèi)的噪音和孤立點的敏感性，在訓練樣本集中增加一項：隸屬度，并賦予支持向量較高的隸屬度，而非支持向量及噪聲野值點賦予較小的隸屬度，從而降低了非支持向量、噪聲和野值點對最優(yōu)超平面的影響。（2）模糊支持向量機FSVM為了克服噪聲和野值點對支持向量機（3）孿生支持向量機TSVMs2007年，Jayadeva和KhemchandaniR提出了一種二值數(shù)據(jù)的分類器——孿生支持向量機(又稱雙分界面支持向量機)TWSVMs在形式上類似于傳統(tǒng)的支持向量機，具有傳統(tǒng)支持向量機的優(yōu)點，且對大規(guī)模數(shù)據(jù)具有更好的處理能力。TWSVMs為兩個類各自得到一個分類平面，屬于每個類的數(shù)據(jù)盡量圍繞在與之相對應的分類平面周圍，然后TWSVMs通過優(yōu)化一對分類平面來構建分類超平面。即：TWSVMs解決一對QP問題，而SVM則是解決一個QP問題，但是在TWSVMs中，其中一個類的數(shù)據(jù)要作為另一個QP問題的約束條件，反之亦然。（3）孿生支持向量機TSVMs2007年，Jayadeva8.5.2多類問題中的SVM類模式識別問題是為個樣本構成一個決策函數(shù)。由于SVM是解決兩類問題的有效方