機(jī)器學(xué)習(xí)之理解支持向量機(jī)SVM

平時(shí)都是直接使用現(xiàn)成的libsvm，雖然對(duì)于SVM原理理解有一定的難度，但是仍然試著知其然，亦知其所以然。本文主要是SVM的概念性的分享。

基本概念

支持向量機(jī)（Support Vector Machine，SVM）是Corinna Cortes和Vapnik等于1995年首先提出的，它在解決小樣本、非線性及高維模式識(shí)別中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問(wèn)題中。

支持向量機(jī)，其含義是通過(guò)支持向量運(yùn)算的分類(lèi)器。其中“機(jī)”的意思是機(jī)器，可以理解為分類(lèi)器。

什么是支持向量呢？在求解的過(guò)程中，會(huì)發(fā)現(xiàn)只根據(jù)部分?jǐn)?shù)據(jù)就可以確定分類(lèi)器，這些數(shù)據(jù)稱(chēng)為支持向量。

見(jiàn)下圖，在一個(gè)二維環(huán)境中，其中點(diǎn)R，S，G點(diǎn)和其它靠近中間黑線的點(diǎn)可以看作為支持向量，它們可以決定分類(lèi)器，也就是黑線的具體參數(shù)。

支持向量機(jī)（Support vector machines，SVM）與神經(jīng)網(wǎng)絡(luò)類(lèi)似，都是學(xué)習(xí)型的機(jī)制，但與神經(jīng)網(wǎng)絡(luò)不同的是SVM使用的是數(shù)學(xué)方法和優(yōu)化技術(shù)。

為了更好的理解SVM，下面從logistic回歸出發(fā)，引出了SVM，既揭示了模型間的聯(lián)系，也讓人覺(jué)得過(guò)渡更自然。

重新審視logistic回歸

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

形式化表示就是

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

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

那么g（z）的圖像是

可以看到，將無(wú)窮映射到了（0，1）。

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

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

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

圖形化表示如下：

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

形式化表示

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

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

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

接下來(lái)定義幾何間隔，先看圖

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

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

這里用||w||=1規(guī)約w，使得是wTx+bi（因沒(méi)法輸入公式，寫(xiě)成這樣子了）幾何間隔。

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

由于||w||=1不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系，公式：

我們改寫(xiě)為：

這時(shí)候其實(shí)我們求的最大值仍然是幾何間隔，只不過(guò)此時(shí)的w不受||w||=1的約束了。然而這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒(méi)法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫(xiě)。前面說(shuō)到同時(shí)擴(kuò)大w和b對(duì)結(jié)果沒(méi)有影響，但我們最后要求的仍然是w和b的確定值，不是他們的一組倍數(shù)值。

這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問(wèn)題（目標(biāo)函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。到這里發(fā)現(xiàn)，雖然沒(méi)有先畫(huà)好圖，畫(huà)好分類(lèi)超平面，在圖上標(biāo)示出間隔那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來(lái)推導(dǎo)出目標(biāo)函數(shù)和約束。