3.5.1 線(xiàn)性可分條件下的支持向量機最優(yōu)分界面
Vapnik等人在多年研究統計學(xué)習理論基礎上對線(xiàn)性分類(lèi)器提出了另一種設計最佳準則。其原理也從線(xiàn)性可分說(shuō)起，然后擴展到線(xiàn)性不可分的情況。甚至擴展到使用非線(xiàn)性函數中去，這種分類(lèi)器被稱(chēng)為支持向量機(Support Vector Machine,簡(jiǎn)稱(chēng)SVM)。支持向量機的提出有很深的理論背景。但我們只就支持向量機的最淺顯原理進(jìn)行討論。因此本章所說(shuō)的SVM設計的思路只是我們對它一種通俗化的理解。
支持向量機方法是在近年來(lái)提出的一種新方法。
在學(xué)習這種方法時(shí)，首先要弄清楚這種方法考慮問(wèn)題的特點(diǎn)，這就要從線(xiàn)性可分的最簡(jiǎn)單情況討論起，在沒(méi)有弄懂其原理之前，不要急于學(xué)習線(xiàn)性不可分等較復雜的情況，支持向量機在設計時(shí)，需要用到條件極值問(wèn)題的求解，因此需用拉格朗日乘子理論，但對多數人來(lái)說(shuō)，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿(mǎn)足的條件，此時(shí)我們只要了解拉格朗日理論的有關(guān)結論就行。
圖3.28
SVM的思路是這樣的，由于兩類(lèi)別訓練樣本線(xiàn)性可分，因此在兩個(gè)類(lèi)別的樣本集之間存在一個(gè)隔離帶。對一個(gè)二維空間的問(wèn)題我們用圖3.28表示。其中用圈和交叉符號分別表示第一類(lèi)和第二類(lèi)訓練樣本，H是將兩類(lèi)分開(kāi)的分界面，而H1與H2與H平行，H是其平分面，H1上的樣本是第一類(lèi)樣本到H最近距離的點(diǎn)，H2的點(diǎn)則是第二類(lèi)樣本距H的最近點(diǎn)，由于這兩種樣本點(diǎn)很特殊，處在隔離帶的邊緣上，因此用再附加一個(gè)圈表示。這些點(diǎn)稱(chēng)為支持向量，它們決定了這個(gè)隔離帶。
從圖上可以看出能把兩類(lèi)分開(kāi)的分界面并不止H這一個(gè)，如果略改變H的方向，則根據H1、H2與H平行這一條件，H1、 H2的方向也隨之改變，這樣一來(lái)，H1與H2之間的間隔(兩條平行線(xiàn)的垂直距離)會(huì )發(fā)生改變。顯然使H1與H2之間間隔最大的分界面H是最合理的選擇，因此最大間隔準則就是支持向量機的最佳準則。為了將這個(gè)準則具體化，需要用數學(xué)式子表達。為了方便，我們將訓練樣本集表示成{ xi,yi },i=1,…,N,其中xi為d維向量也就是我們常說(shuō)的特征向量，而yi∈{-1，+1},即用yi是+1或-1表示其類(lèi)別。對于分界面H表示成
(3-80)
并且令 (3-81)
對在H1與H2平面上的點(diǎn)，上兩式取等號。上兩式也可合并成
(3-82)
顯然H1平面到坐標原點(diǎn)的距離為 ，而H2則為 ，故H1到H2的間隔為 ，即與成反比。因此欲達到 Vapnik提出的使間隔最大的準則，則應使最小，而(3-82)則是它必須遵守的約束條件，可改寫(xiě)成大于零的不等式，
(3-83)
對于這樣一個(gè)帶約束條件為不等式的條件極值問(wèn)題，需要引用擴展的拉格朗日乘子理論，按這個(gè)理論構造拉格朗日函數的原則為：目標函數(在此為最小，為了方便用最小)減去用拉格朗日乘子(乘子值必須不小于0)與約束條件函數的乘積，在我們討論的問(wèn)題中可寫(xiě)成
(3-84)，
由于(3-84)中的目標函數是二次函數，而約束條件中為線(xiàn)性函數，按拉格朗日理論該問(wèn)題存在唯一解，根據研究擴展的拉格朗日理論的 Kuhn與Tucker等人的研究，表明以下是該唯一解的充分必要條件：
(3-85)
(3-86)
以及 (3-87)
(3-88)
(3-89)
(3-87)和(3-88)表明，只有滿(mǎn)足條件的點(diǎn),其拉格朗日乘子才可能不為零; 而對滿(mǎn)足的樣本數據來(lái)說(shuō)，其拉格朗日乘子必須為零，顯然只有部分(經(jīng)常是少量)的樣本數據的ai不為零，而線(xiàn)性分界面的權向量W則是這些ai不為零的樣本數據的線(xiàn)性組合，ai不為零的樣本數據也因而被稱(chēng)為支持向量。
到此為止，我們可再回顧一下線(xiàn)性可分條件下的支持向量機方法說(shuō)了些什么。
首先支持向量機的方法是明確提出一個(gè)隔離帶概念，并把使隔離帶最寬作為確定線(xiàn)性分界面的最佳原則。既然是隔離帶又有線(xiàn)性可分作條件，只需找到處在隔離帶邊緣上的點(diǎn)，以便確定最優(yōu)的隔離帶就行，而其它數據點(diǎn)的作用，只是要求所確定的隔離帶能保證把它們置在隔離帶外確定的一方就行。這樣一來(lái)，數據點(diǎn)就分成兩部分，一種對確定隔離帶參數(體現在權向量w的確定上式(3-90))很重要，而另一類(lèi)(一般說(shuō)占數據的大部分)對確定隔離帶的參數沒(méi)有直接的影響，在這個(gè)意義上說(shuō)它們對確定隔離帶參數無(wú)關(guān)緊要。它們相應的拉格朗日乘子ai是否為0,就表示了數據的這種重要性，對確定隔離帶參數主要的點(diǎn)應有 ，并稱(chēng)為支持向量，而其余的數據點(diǎn)，它的,這在式(3-88)中體現。一旦使式(3-91)達極大值的 確定下來(lái)(只有少量的>0，其余都為0)，則最佳的權向量w也就可以利用(3-90)式定下來(lái)，它們是這些支持向量數據的線(xiàn)性求和。
如圖3-29所示：
圖3.29
如果知道哪些數據是支持向量，哪些不是，則問(wèn)題就簡(jiǎn)單了。問(wèn)題在于哪些數據是支持向量事先并不能確定，因此這只有通過(guò)求(3-84)式的極大值來(lái)求解。
從(3-85)可以看出，只要最佳的ai求得(表示成)，則
(3-90)
為了求出最佳的ai，拉格朗日理論中引入一種對偶函數，與(3-84)式相對偶的函數的構造方法是：對L(W,a) 分別求它對W及w0的偏微分，并置為零，然后再代回到(3-84)式中，從而得到
(3-91)
拉格朗日理論證明：滿(mǎn)足上述條件(3-85)到(3-89)時(shí)，找(3-91)式極大值的解就是(3-84)式的條件極小值，因此由(3-91)可求得各個(gè)最佳值，代入(3-90)即可得到，在W確定之后w0值也可利用(3-88)對某個(gè)的數據求出。
對(3-91)式的來(lái)源不要求弄懂，只需知道，它的極大值解與(3-84)式的極小值解是一致的就行了。因為后面還要用(3-91)說(shuō)明一些問(wèn)題。
接觸支持向量機（SVM）也有一年多了，由于之前沒(méi)有學(xué)習過(guò)這方面的東西，學(xué)校也沒(méi)開(kāi)之類(lèi)課程，所以學(xué)習起來(lái)非常困難。之間經(jīng)歷了不少，有迷茫（能不能拿下），有無(wú)奈（看理論就像讀天書(shū)）、沒(méi)有人指點(diǎn)、沒(méi)有人幫助，一度時(shí)期都快要放棄，像瘋了一樣的尋找資料，很是著(zhù)急。不過(guò)幸運的是當初沒(méi)有真的放棄！
最近幾個(gè)月，一直忙于遙感方面的事，就把SVM放了一下，今天上網(wǎng)，在瀏覽一些論壇的時(shí)候，發(fā)現有許多SVM人正在經(jīng)受和我一樣的過(guò)去
！看著(zhù)那些求助的留言，心里沉沉為了讓大家少一點(diǎn)痛苦，我就把我的一點(diǎn)小小的看法也算一點(diǎn)建議吧寫(xiě)出來(lái)，希望能起一點(diǎn)作用！如果你要勇敢的走下去，就要做好準備，一個(gè)是要啃一下統計學(xué)習理論，二一個(gè)的要補習一下英文，三一個(gè)要學(xué)習C或MATLAB語(yǔ)言。
先介紹一下SVM：
支持矢量機（support vector machine 簡(jiǎn) SVM）其實(shí)是一種統計學(xué)習方用于模式識別、回歸估計及密度估計。它是在統計學(xué)習理論（Statistical Learning Theory, Vapink,1995）的基礎上發(fā)展起來(lái)的一種專(zhuān)門(mén)解決小樣本學(xué)習規律的學(xué)習方法。
與其他傳統的學(xué)習方法（如模式識別，神經(jīng)網(wǎng)絡(luò )等）相比它有
一、它基于結構風(fēng)險最小化原則，
這樣就避免了過(guò)學(xué)習問(wèn)題，泛化能力強。
二、它是一個(gè)凸優(yōu)化問(wèn)題，因此局部最優(yōu)解一定是全局最優(yōu)解的優(yōu)點(diǎn)。
因此，許多學(xué)者認為，SVM正在成為繼神經(jīng)網(wǎng)絡(luò )之后在人工智能界的又一個(gè)新的研究熱點(diǎn)。
其實(shí)大多數的應用在分類(lèi)，聚類(lèi)（classifaction），回歸(regressiong)兩個(gè)方面，也有做數據挖掘的！
我這里有一些關(guān)于統計學(xué)習理論的一些資料和SVM學(xué)習軟件（LS-SVM、SPIDER、C_SVM、LIBSVM、GINI-SVM等），及應用實(shí)例。
支持向量機，這個(gè)名字非常得怪異，直到我看了相關(guān)得文獻，才知道，原來(lái)這種工具將其中最重要的一些數據定義為了支持向量，然后就給其取名支持向量機。支持向量機誕生沒(méi)有多久，也就十幾歲吧，先在正茁壯地成長(cháng)著(zhù)。我學(xué)它，就是因為大家現在都很關(guān)心它。
下面來(lái)點(diǎn)專(zhuān)業(yè)的。
SVM解決了分類(lèi)問(wèn)題，線(xiàn)性可分自不必說(shuō)。在線(xiàn)性不可分情況下，利用一個(gè)余量。在非線(xiàn)性情況下，利用核函數，將低維非線(xiàn)性轉化為高位線(xiàn)性問(wèn)題。在解決SVM問(wèn)題時(shí)，就是要求出分類(lèi)函數。其實(shí)就是一些系數而已。
1. 支持向量機的關(guān)鍵技術(shù)是什么?
答: 支持向量機性能的優(yōu)劣主要取決于核函數的選取,所以對于一個(gè)實(shí)際問(wèn)題而言,如何根據實(shí)際的數據模型選擇合適的核函數從而構造SVM算法.目前比較成熟的核函數及其參數的選擇都是人為的,根據經(jīng)驗來(lái)選取的,帶有一定的隨意性.在不同的問(wèn)題領(lǐng)域,核函數應當具有不同的形式和參數,所以在選取時(shí)候應該將領(lǐng)域知識引入進(jìn)來(lái),但是目前還沒(méi)有好的方法來(lái)解決核函數的選取問(wèn)題.
2. 支持向量機的優(yōu)缺點(diǎn)?
答:優(yōu)點(diǎn):SVM理論提供了一種避開(kāi)高維空間的復雜性,直接用此空間的內積函數(既是核函數),再利用在線(xiàn)性可分的情況下的求解方法直接求解對應的高維空間的決策問(wèn)題.當核函數已知,可以簡(jiǎn)化高維空間問(wèn)題的求解難度.同時(shí)SVM是基于小樣本統計理論的基礎上的,這符合機器學(xué)習的目的.而且支持向量機比神經(jīng)網(wǎng)絡(luò )具有較好的泛化推廣能力.
缺點(diǎn):對于每個(gè)高維空間在此空間的映射F,如何確定F也就是核函數,現在還沒(méi)有合適的方法,所以對于一般的問(wèn)題,SVM只是把高維空間的復雜性的困難轉為了求核函數的困難.而且即使確定核函數以后,在求解問(wèn)題分類(lèi)時(shí),要求解函數的二次規劃,這就需要大量的存儲空間.這也是SVM的一個(gè)問(wèn)題.
3. 支持向量機的主要應用和研究的熱點(diǎn)?
答:目前支持向量機主要應用在模式識別領(lǐng)域中的文本識別,中文分類(lèi),人臉識別等;同時(shí)也應用到許多的工程技術(shù)和信息過(guò)濾等方面.
當前研究的熱點(diǎn)主要是對支持向量機中算法的優(yōu)化,包括解決SVM中二次規劃求解問(wèn)題,對大規模SVM的求解問(wèn)題,對SVM中QP問(wèn)題的求解問(wèn)題等.另外就是如何更好的構造基于SVM的多類(lèi)分類(lèi)器,如何提高SVM的歸納能力和分類(lèi)速度等.如何根據實(shí)際問(wèn)題確定核函數也是一個(gè)重要的研究熱點(diǎn).
