【轉(zhuǎn)載請(qǐng)注明出處】http://www.cnblogs.com/jerrylead

1 簡(jiǎn)介

支持向量機(jī)基本上是最好的有監(jiān)督學(xué)習(xí)算法了。最開始接觸SVM是去年暑假的時(shí)候，老師要求交《統(tǒng)計(jì)學(xué)習(xí)理論》的報(bào)告，那時(shí)去網(wǎng)上下了一份入門教程，里面講的很通俗，當(dāng)時(shí)只是大致了解了一些相關(guān)概念。這次斯坦福提供的學(xué)習(xí)材料，讓我重新學(xué)習(xí)了一些SVM知識(shí)。我看很多正統(tǒng)的講法都是從VC 維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小原理出發(fā)，然后引出SVM什么的，還有些資料上來就講分類超平面什么的。這份材料從前幾節(jié)講的logistic回歸出發(fā)，引出了SVM，既揭示了模型間的聯(lián)系，也讓人覺得過渡更自然。

2 重新審視logistic回歸

Logistic回歸目的是從特征學(xué)習(xí)出一個(gè)0/1分類模型，而這個(gè)模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無窮到正無窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。

形式化表示就是

假設(shè)函數(shù)

其中x是n維特征向量，函數(shù)g就是logistic函數(shù)。

的圖像是

可以看到，將無窮映射到了(0,1)。

而假設(shè)函數(shù)就是特征屬于y=1的概率。

當(dāng)我們要判別一個(gè)新來的特征屬于哪個(gè)類時(shí)，只需求，若大于0.5就是y=1的類，反之屬于y=0類。

再審視一下，發(fā)現(xiàn)只和有關(guān)，>0，那么，g(z)只不過是用來映射，真實(shí)的類別決定權(quán)還在。還有當(dāng)時(shí)，=1，反之=0。如果我們只從出發(fā)，希望模型達(dá)到的目標(biāo)無非就是讓訓(xùn)練數(shù)據(jù)中y=1的特征，而是y=0的特征。Logistic回歸就是要學(xué)習(xí)得到，使得正例的特征遠(yuǎn)大于0，負(fù)例的特征遠(yuǎn)小于0，強(qiáng)調(diào)在全部訓(xùn)練實(shí)例上達(dá)到這個(gè)目標(biāo)。

圖形化表示如下：

中間那條線是，logistic回顧強(qiáng)調(diào)所有點(diǎn)盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線?？紤]上面3個(gè)點(diǎn)A、B和C。從圖中我們可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。這樣我們可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點(diǎn)，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點(diǎn)上達(dá)到最優(yōu)。因?yàn)槟菢拥脑挘沟靡徊糠贮c(diǎn)靠近中間線來換取另外一部分點(diǎn)更加遠(yuǎn)離中間線。我想這就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)，一個(gè)考慮局部（不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn)），一個(gè)考慮全局（已經(jīng)遠(yuǎn)離的點(diǎn)可能通過調(diào)整中間線使其能夠更加遠(yuǎn)離）。這是我的個(gè)人直觀理解。

3 形式化表示

我們這次使用的結(jié)果標(biāo)簽是y=-1,y=1，替換在logistic回歸中使用的y=0和y=1。同時(shí)將替換成w和b。以前的，其中認(rèn)為。現(xiàn)在我們替換為b，后面替換為（即）。這樣，我們讓，進(jìn)一步。也就是說除了y由y=0變?yōu)閥=-1，只是標(biāo)記不同外，與logistic回歸的形式化表示沒區(qū)別。再明確下假設(shè)函數(shù)

上一節(jié)提到過我們只需考慮的正負(fù)問題，而不用關(guān)心g(z)，因此我們這里將g(z)做一個(gè)簡(jiǎn)化，將其簡(jiǎn)單映射到y(tǒng)=-1和y=1上。映射關(guān)系如下：

4 函數(shù)間隔（functional margin）和幾何間隔（geometric margin）

給定一個(gè)訓(xùn)練樣本，x是特征，y是結(jié)果標(biāo)簽。i表示第i個(gè)樣本。我們定義函數(shù)間隔如下：

可想而知，當(dāng)時(shí)，在我們的g(z)定義中，，的值實(shí)際上就是。反之亦然。為了使函數(shù)間隔最大（更大的信心確定該例是正例還是反例），當(dāng)時(shí)，應(yīng)該是個(gè)大正數(shù)，反之是個(gè)大負(fù)數(shù)。因此函數(shù)間隔代表了我們認(rèn)為特征是正例還是反例的確信度。

繼續(xù)考慮w和b，如果同時(shí)加大w和b，比如在前面乘個(gè)系數(shù)比如2，那么所有點(diǎn)的函數(shù)間隔都會(huì)增大二倍，這個(gè)對(duì)求解問題來說不應(yīng)該有影響，因?yàn)槲覀円蠼獾氖?a >，同時(shí)擴(kuò)大w和b對(duì)結(jié)果是無影響的。這樣，我們?yōu)榱讼拗苭和b，可能需要加入歸一化條件，畢竟求解的目標(biāo)是確定唯一一個(gè)w和b，而不是多組線性相關(guān)的向量。這個(gè)歸一化一會(huì)再考慮。

剛剛我們定義的函數(shù)間隔是針對(duì)某一個(gè)樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔

說白了就是在訓(xùn)練樣本上分類正例和負(fù)例確信度最小那個(gè)函數(shù)間隔。

接下來定義幾何間隔，先看圖

假設(shè)我們有了B點(diǎn)所在的分割面。任何其他一點(diǎn)，比如A到該面的距離以表示，假設(shè)B就是A在分割面上的投影。我們知道向量BA的方向是（分割面的梯度），單位向量是。A點(diǎn)是，所以B點(diǎn)是x=（利用初中的幾何知識(shí)），帶入得，

進(jìn)一步得到

實(shí)際上就是點(diǎn)到平面距離。

再換種更加優(yōu)雅的寫法：

當(dāng)時(shí)，不就是函數(shù)間隔嗎？是的，前面提到的函數(shù)間隔歸一化結(jié)果就是幾何間隔。他們?yōu)槭裁磿?huì)一樣呢？因?yàn)楹瘮?shù)間隔是我們定義的，在定義的時(shí)候就有幾何間隔的色彩。同樣，同時(shí)擴(kuò)大w和b，w擴(kuò)大幾倍，就擴(kuò)大幾倍，結(jié)果無影響。同樣定義全局的幾何間隔

5 最優(yōu)間隔分類器（optimal margin classifier）

回想前面我們提到我們的目標(biāo)是尋找一個(gè)超平面，使得離超平面比較近的點(diǎn)能有更大的間距。也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形象的說，我們將上面的圖看作是一張紙，我們要找一條折線，按照這條折線折疊后，離折線最近的點(diǎn)的間距比其他折線都要大。形式化表示為：

這里用=1規(guī)約w，使得是幾何間隔。

到此，我們已經(jīng)將模型定義出來了。如果求得了w和b，那么來一個(gè)特征x，我們就能夠分類了，稱為最優(yōu)間隔分類器。接下的問題就是如何求解w和b的問題了。

由于不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系，，我們改寫一下上面的式子：

這時(shí)候其實(shí)我們求的最大值仍然是幾何間隔，只不過此時(shí)的w不受的約束了。然而這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫。前面說到同時(shí)擴(kuò)大w和b對(duì)結(jié)果沒有影響，但我們最后要求的仍然是w和b的確定值，不是他們的一組倍數(shù)值，因此，我們需要對(duì)做一些限制，以保證我們解是唯一的。這里為了簡(jiǎn)便我們?nèi)?a >。這樣的意義是將全局的函數(shù)間隔定義為1，也即是將離超平面最近的點(diǎn)的距離定義為。由于求的最大值相當(dāng)于求的最小值，因此改寫后結(jié)果為：

這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問題（目標(biāo)函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。

到這里發(fā)現(xiàn)，這個(gè)講義雖然沒有像其他講義一樣先畫好圖，畫好分類超平面，在圖上標(biāo)示出間隔那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來推導(dǎo)出目標(biāo)函數(shù)和約束。

接下來介紹的是手工求解的方法了，一種更優(yōu)的求解方法。