人工智能：第8章 支持向量機

1、第八章 支持向量機 支持向量機SVM ( Support Vector Machines)是由Vanpik領(lǐng)導的AT&T Bell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術(shù)，SVM是一種基于統(tǒng)計學習理論的模式識別方法，主要應(yīng)用于模式識別領(lǐng)域。 發(fā)展：90年代，由于統(tǒng)計學習理論的實現(xiàn)和神經(jīng)網(wǎng)絡(luò)等較新興的機器學習方法的研究遇到一些重要的困難，如，如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學習與欠學習問題、局部極小點問題等，使得SVM迅速發(fā)展和完善。SVM優(yōu)勢：小樣本、非線性及高維模式識別問題，函數(shù)擬合等其他機器學習問題運用:模式識別、回歸分析、函數(shù)估計、時間序列預測等領(lǐng)域，文本識別、手寫字體識別

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

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

4、：找出最優(yōu)的分類超平面。8.2 統(tǒng)計學習理論統(tǒng)計學習理論誕生于20世紀6070年代，主要創(chuàng)立者: VladimirN.Vapnik，90年代中期發(fā)展比較成熟，受到世界機器學習界的廣泛重視。統(tǒng)計學習理論：一種專門研究小樣本情況下機器學習規(guī)律的理論。針對小樣本統(tǒng)計問題建立了一套新的理論體系，該體系下的統(tǒng)計推理規(guī)則不僅考慮了對漸近性能的要求，而且追求在現(xiàn)有有限信息的條件下得到最優(yōu)結(jié)果。8.2.1 學習問題的表示樣本學習的一般模型產(chǎn)生器(G)：產(chǎn)生隨機向量，它們是從固定但未知的概率分布函數(shù)F(x)中獨立抽取的。訓練器(S)：對每個輸入向量x返回一個輸出值y，產(chǎn)生輸出的根據(jù)是同樣固定但未知的條件分布函數(shù)

5、F(y|x)。學習機器(LM)：它能夠?qū)崿F(xiàn)一定的函數(shù)集，其中是參數(shù)集合。在學習過程中，學習機器LM觀察數(shù)據(jù)對(x,y)。在訓練之后，學習機器必須對任意輸入x，使之接近訓練器的響應(yīng)y。8.2.2 期望風險和經(jīng)驗風險給定輸入x下訓練器響應(yīng)y與學習機器給出的響應(yīng) 之間的損失記作 就是風險泛函，即預測的期望(實際)風險。 稱為經(jīng)驗風險。8.3 支持向量機（SVM）一種經(jīng)典的二分類模型，基本模型定義為特征空間中最大間隔的線性分類器，其學習的優(yōu)化目標便是間隔最大化，因此支持向量機本身可以轉(zhuǎn)化為一個凸二次規(guī)劃求解的問題。函數(shù)間隔與幾何間隔對于二分類學習，假設(shè)數(shù)據(jù)是線性可分的分類學習：找到一個合適的超平面，該

6、超平面能夠?qū)⒉煌悇e的樣本分開類似二維平面使用ax+by+c=0來表示，超平面實際上表示的就是高維的平面，如下圖所示：8.3.1 線性可分支持向量機劃分超平面：其中， 為法向量。樣本空間中任意點x到超平面(w,b)的距離寫為：8.3.1 線性可分支持向量機假設(shè)超平面能正確分類，則：兩個異類支持向量到超平面的距離之和為：8.3.1 線性可分支持向量機欲找最大間隔的劃分超平面，即找滿足約束的參數(shù)w,b使得 最大，即：8.3.1 線性可分支持向量機等價于：8.3.1 對偶問題支持向量機問題可以等價為求解下面的二次規(guī)劃問題： 最小化泛函： 約束條件為不等式類型 該問題的解是由下面的拉格朗日泛函的鞍點給

7、出的： 其中 為拉格朗日乘子。問題的對偶問題為： 最大化泛函約束條件為：這樣原問題的解為： 由拉格朗日可得到原問題的Karush-Kuhn-Tucker(KKT)條件：根據(jù)優(yōu)化理論， 是原問題的解當且僅當 滿足KKT條件。在對偶問題或KKT條件中，每個訓練數(shù)據(jù) 都對應(yīng)一個拉格朗日乘子 ，其中與 對應(yīng)的數(shù)據(jù)成為支持向量。 利用任一支持向量和KKT條件 ，可求出 一般情況下，為了準確，常求出多個b值，然后取平均值，或者 其中，用 表示屬于第一類的任一支持向量，用 表示屬于第二類的任一支持向量。 最后的最優(yōu)超平面方程： 最終完成學習過程。 8.3.2 線性不可分與軟間隔最大化首先我們引入松弛變量 來

8、表示經(jīng)驗風險，將原約束條件變?yōu)椋?這樣，樣本數(shù)據(jù)的經(jīng)驗風險在一定程度上可以表示為： 其中 參數(shù)，代表經(jīng)驗風險的某種度量方式。給定樣本數(shù)據(jù) 后，我們在容許結(jié)構(gòu)的某個子集下最小化經(jīng)驗風險，問題可以描述為： 最小化泛函： 約束條件為：這個問題可以等價為在約束條件下最小化泛函： 這里的C是一個給定的值。原問題的對偶形式為：只是約束條件變?yōu)椋?這樣原問題的解為： 8.4 核函數(shù)支持向量機的關(guān)鍵在于核函數(shù)。低維空間向量集通常難于劃分，解決的方法是將它們映射到高維空間，但這個辦法帶來的困難就是計算復雜度的增加，而核函數(shù)正好巧妙地解決了這個問題。只要選用適當?shù)暮撕瘮?shù)，我們就可以得到高維空間的分類函數(shù)。在SVM

9、理論中，采用不同的核函數(shù)將導致不同的SVM算法。8.4 核函數(shù)首先定義映射 ， 是輸入空間，H是高維內(nèi)積空間，稱為特征空間， 稱為特征映射，然后在H中構(gòu)造最優(yōu)超平面。 在特征空間中的學習過程同前面一樣，對偶問題為： 約束條件不變： 核函數(shù)的思想：在輸入空間的變量直接計算特征空間中的內(nèi)積，即 其中 ， 屬于輸入空間，函數(shù) 即為核函數(shù)。 這樣，只要定義了核函數(shù)，就不必真的進行非線性變換，更沒有必要知道采用的非線性變換的形式，所以我們只要構(gòu)造輸入空間的一個核函數(shù)即可。 核函數(shù)：定理 8.6 對于任意的對稱函數(shù) ，它是某個特征空間的內(nèi)積運算的充分必要條件是，對于任意的 且 ，有 事實上這一條件并不難滿

10、足。 這樣我們就可以得到輸入空間中的非線性決策函數(shù) 它等價于在高維特征空間中的線性決策函數(shù)。 8.4.2 核函數(shù)的分類多項式核函數(shù) 所得到的是階多項式分類器： 徑向基函數(shù) 經(jīng)典的徑向基函數(shù)的判別函數(shù)為： 最通常采用的核函數(shù)為高斯函數(shù)：多層感知機 SVM采用Sigmoid函數(shù)作為內(nèi)積，這時就實現(xiàn)了包含一個隱層的多層感知機，隱層節(jié)點數(shù)目由算法自動確定。滿足mercer條件的Sigmoid函數(shù)為： 8.5 SVM的算法及多類SVM目前SVM的訓練算法一般采用循環(huán)迭代解決對偶尋優(yōu)問題：將原問題分解成為若干子問題，按照某種迭代策略，通過反復求解子問題，最終使結(jié)果收斂到原問題的最優(yōu)解。根據(jù)子問題的劃分和迭

11、代策略的不同，大致可以分為：塊算法Chunking Algorithm： 考慮到去掉Lagrange乘子等于零的訓練樣本不會影響原問題的解，采用選擇一部分樣本構(gòu)成工作樣本集進行訓練，剔除其中的非支持向量，并用訓練結(jié)果對剩余樣本進行檢驗，將不符合KKT條件的樣本與此次結(jié)果的支持向量合并成為一個新的工作樣本集，然后重新訓練，如此重復下去直到獲得最優(yōu)結(jié)果。 Chunking算法將矩陣規(guī)模從訓練樣本數(shù)的平方減少到具有非零Lagrange乘數(shù)的樣本數(shù)的平方，在很大程度上降低了訓練過程對存儲容量的要求。Chunking算法能夠大大提高訓練速度，尤其是當支持向量的數(shù)目遠遠小于訓練樣本的數(shù)目時。然而，如果支持

12、向量個數(shù)比較多，隨著算法迭代次數(shù)的增多，所選的塊也會越來越大，算法的訓練速度依舊會變得十分緩慢。 (2)分解算法(Decomposition Algorithm) 分解算法最早由Osuna等人提出，是目前有效解決大規(guī)模問題的主要方法。分解算法將二次規(guī)劃問題分解成一系列規(guī)模較小的二次規(guī)劃子問題，進行迭代求解。在每次迭代中，選取拉格朗日乘子分量的一個子集做為工作集，利用傳統(tǒng)優(yōu)化算法求解一個二次規(guī)劃的子問題。該算法的關(guān)鍵在于選擇一種最優(yōu)的工作集選擇算法，但是Osuna在工作集的選取中采用了隨機的方法，因此限制了算法的收斂速度。 Joachims在Osuna分解算法的基礎(chǔ)上，關(guān)于工作集的選擇做了重要改

13、進。其主要思想是，如果存在不滿足KTT條件的樣本，利用最速下降法，在最速下降方向中存在 個樣本，然后以這 個樣本構(gòu)成工作集，在此工作集上解決QP問題，直到所有樣本滿足KTT條件。Joachims的改進大幅度提高了分解算法的收斂速度，并且他利用這些方法實現(xiàn)了SVMlight算法。 由John C.Platt提出的序列最小優(yōu)化（Sequential Minimal Optimization, SMO）算法可以說是Osuna分解算法的一個特例，工作集中只有2個樣本，其優(yōu)點是針對2個樣本的二次規(guī)劃問題可以有解析解的形式，從而避免了多樣本情況下的數(shù)值解不穩(wěn)定及耗時問題，同時也不需要大的矩陣存儲空間，特別

14、適合稀疏樣本。其工作集的選擇不是傳統(tǒng)的最陡下降法，而是啟發(fā)式。通過兩個嵌套的循環(huán)來尋找待優(yōu)化的樣本，然后在內(nèi)環(huán)中選擇另一個樣本，完成一次優(yōu)化，再循環(huán)，進行下一次優(yōu)化，直到全部樣本都滿足最優(yōu)條件。SMO算法主要耗時在最優(yōu)條件的判斷上，所以應(yīng)尋找最合理即計算代價最低的最優(yōu)條件判別式。(3)增量學習 增量學習是機器學習系統(tǒng)在處理新增樣本時，能夠只對原學習結(jié)果中與新樣本有關(guān)的部分進行增加修改或刪除操作，與之無關(guān)的部分則不被觸及。增量訓練算法的一個突出特點是支持向量機的學習不是一次離線進行的，而是一個數(shù)據(jù)逐一加入反復優(yōu)化的過程。新型SVM（1）粒度支持向量機GSVM GSVM由Tang Y C于2004

15、年提出的，主要思想：通過常用的粒度劃分方法構(gòu)建粒度空間獲得一系列信息粒，然后在每個信息粒上進行學習，最后通過聚合信息粒上的信息（或數(shù)據(jù)、規(guī)則知識、屬性等）獲得最終的支持向量機決策函數(shù)。 這一學習機制通過數(shù)據(jù)的粒化可以將一個線性不可分問題轉(zhuǎn)化為一系列線性可分問題，從而獲得多個決策函數(shù)；同時，這一學習機制也使得數(shù)據(jù)的泛化性能增強，即可在SVM的訓練中得到間隔更寬的超平面。（2）模糊支持向量機FSVM為了克服噪聲和野值點對支持向量機的影響，臺灣學者Chunfu Lin和Shengde Wang將模糊數(shù)學和支持向量機相結(jié)合，提出了模糊支持向量機，主要用來處理訓練樣本中的噪聲數(shù)據(jù)。主要思想：針對支持向量

16、機對訓練樣本內(nèi)的噪音和孤立點的敏感性，在訓練樣本集中增加一項：隸屬度，并賦予支持向量較高的隸屬度，而非支持向量及噪聲野值點賦予較小的隸屬度，從而降低了非支持向量、噪聲和野值點對最優(yōu)超平面的影響。（3）孿生支持向量機TSVMs2007年，Jayadeva 和Khemchandani R提出了一種二值數(shù)據(jù)的分類器孿生支持向量機(又稱雙分界面支持向量機)TWSVMs在形式上類似于傳統(tǒng)的支持向量機，具有傳統(tǒng)支持向量機的優(yōu)點，且對大規(guī)模數(shù)據(jù)具有更好的處理能力。TWSVMs為兩個類各自得到一個分類平面，屬于每個類的數(shù)據(jù)盡量圍繞在與之相對應(yīng)的分類平面周圍，然后TWSVMs通過優(yōu)化一對分類平面來構(gòu)建分類超平面

17、。即：TWSVMs解決一對QP問題，而SVM則是解決一個QP問題，但是在TWSVMs中，其中一個類的數(shù)據(jù)要作為另一個QP問題的約束條件，反之亦然。8.5.2 多類問題中的SVM 類模式識別問題是為 個樣本 構(gòu)成一個決策函數(shù)。由于SVM是解決兩類問題的有效方法，因此用SVM解多類問題的方法通常將問題轉(zhuǎn)化為兩類問題，然后對結(jié)果進行處理。一般常用的方法有以下幾種： One-against-the-rest方法：在第 類和其他 類之間構(gòu)建超平面。 One-against-one方法：為任意兩個類構(gòu)建超平面，共需 個 。 K-class SVM：同時為所有的類構(gòu)造一個分類超平面。8.6 SVM的應(yīng)用現(xiàn)狀

18、 人臉檢測、驗證和識別 Osuna最早將SVM應(yīng)用于人臉檢測，并取得了較好的效果。其方法是直接訓練非線性SVM分類器完成人臉與非人臉的分類。大量實驗結(jié)果表 明這種方法不僅具有較高的檢測率和較低的誤檢率，而且具有較快的速度。 說話人/語音識別 建立SVM和HMM（隱式馬爾可夫模型）的混合模型。HMM適合處理連續(xù)信號，而SVM適合于分類問題；HMM的結(jié)果反映了同類樣本的相似度，而SVM的輸出結(jié)果則體現(xiàn)了異類樣本間的差異。 8.6 SVM的應(yīng)用現(xiàn)狀 文字/手寫體識別 貝爾實驗室對美國郵政手寫數(shù)字庫進行的實驗，人工識別平均錯誤率為2.5%，專門針對該特定問題設(shè)計的5層神經(jīng)網(wǎng)絡(luò)錯誤率為5.1%（其中利用率大量先驗知識），而用3種SVM方法（采用3種核函數(shù)）得到的錯誤率分別為4.0%、4.1%和4.2%，且是直接采用1616的字符點陣作為輸入，表明了SVM的優(yōu)越性能。 8.6 SVM的應(yīng)用現(xiàn)狀 圖像處理： a 圖像過濾,支持向量機分類和最近鄰方法校驗的多層系圖像處理框架，達到85%以上的準確率。 b 視頻字幕提取,首先將原始圖像幀分割為NN的子塊，提取每個子塊的灰度特征；然后使用預先訓練好的SVM分類機進行字