Content：

8.1 Optimization Objection

8.2 Large margin intuition

8.3 Mathematics Behind Large Margin Classification

8.4 Kernels

8.5 Using a SVM

8.5.1 Multi-class Classification

8.5.2 Logistic Regression vs. SVMs

8.1 Optimization Objection

支持向量機(jī)(Support Vector Machine: SVM)是一種非常有用的監(jiān)督式機(jī)器學(xué)習(xí)算法。首先回顧一下Logistic回歸，根據(jù)log()函數(shù)以及Sigmoid函數(shù)的性質(zhì)，有：

同時(shí)，Logistic回歸的代價(jià)函數(shù)（未正則化）如下：

為得到SVM的代價(jià)函數(shù)，我們作如下修改：

因此，對(duì)比Logistic的優(yōu)化目標(biāo)

SVM的優(yōu)化目標(biāo)如下：

注1：事實(shí)上，上述公式中的Cost0與Cost1函數(shù)是一種稱為hinge損失的替代損失(surrogate loss)函數(shù)，其他常見的替代損失函數(shù)有指數(shù)損失和對(duì)率損失

注2：注意參數(shù)C和λ的對(duì)應(yīng)關(guān)系: C與(1 / λ)成正相關(guān)。

8.2 Large margin intuition

根據(jù)8.1中的代價(jià)函數(shù)，為使代價(jià)函數(shù)最小，有如下結(jié)論：

現(xiàn)假設(shè)C很大（如C=100000），為使代價(jià)函數(shù)最小，我們希望

所以代價(jià)函數(shù)就變?yōu)椋?/p>

所以問題就變成：

該問題最后的優(yōu)化結(jié)果是找到具有"最大間隔"(maximum margin)的劃分超平面，所以支持向量機(jī)又稱大間距分類器(large margin classifier)。那么什么是間隔? 為什么這樣優(yōu)化就可以找到最大間隔？首先，我們通過(guò)圖8-1所示的二維的0/1線性分類情況來(lái)直觀感受。

圖8-1 SVM Decision Boundary: Linearly separable case

直觀上，應(yīng)該去找位于兩類訓(xùn)練樣本"正中間"的劃分超平面，即圖8-1的黑色直線(二維)，因?yàn)樵搫澐殖矫鎸?duì)訓(xùn)練樣本局部擾動(dòng)的"容忍"性最好。例如，圖中的粉色和綠色直線，一旦輸入數(shù)據(jù)稍有變化，將會(huì)得到錯(cuò)誤的預(yù)測(cè)。換言之，這個(gè)劃分超平面所產(chǎn)生的分類結(jié)果是最魯棒的，對(duì)要預(yù)測(cè)數(shù)據(jù)集的泛化能力最強(qiáng)。而兩條藍(lán)色直線之間的距離就稱為間隔(margin)。下一節(jié)將從數(shù)學(xué)角度來(lái)解釋間隔與最大間隔的優(yōu)化原理。

8.3 Mathematics Behind Large Margin Classification

首先介紹一些數(shù)學(xué)知識(shí)。

2-范數(shù)(2-norm)： 也可稱長(zhǎng)度(length)，是二維或三維空間向量長(zhǎng)度的推廣，向量u記為||u||。例如，對(duì)于向量u = [ u1, u2, u3, u4]，||u|| = sqrt(u1^2 + u2^2 + u3^2 + u4^2)

向量?jī)?nèi)積(Vector Inner Product): 設(shè)向量a = [a1, a2, … , an]，向量b = [b1, b2, … , bn]，a和b的的內(nèi)積定義為：a · b = a1b1 + a2b2 + … + anbn 。向量?jī)?nèi)積是幾何向量數(shù)量積(點(diǎn)積)的推廣，可以理解為向量a在向量b上的投影長(zhǎng)度(范數(shù))和向量b的長(zhǎng)度的乘積。

所以有：

其中是在向量上的投影長(zhǎng)度。

所以，8.2節(jié)得到的優(yōu)化問題可以轉(zhuǎn)為如下形式:

分界線為，所以可知和分界線正交(垂直)，并且當(dāng)時(shí)，分界線過(guò)原點(diǎn)(歐式空間)。為使目標(biāo)最優(yōu)（取最小值）且滿足約束，應(yīng)該盡可能大，這樣就要求間距盡可能的大。直觀的如圖8-2所示，圖左為間距較小的情況，此時(shí)的較小，為滿足約束，導(dǎo)致目標(biāo)函數(shù)變大，圖右為最大間距的情況，此時(shí)的是最大的，所以目標(biāo)可以盡可能的小。

圖8-2 兩種不同間距的情況

8.4 Kernels

上述的討論都是基于線性可分的樣本，即存在一個(gè)劃分超平面可以將訓(xùn)練樣本正確分類，然而現(xiàn)實(shí)世界存在大量復(fù)雜的，非線性分類問題(如4.4.2節(jié)的異或/同或問題)。Logistic回歸處理非線性問題可以通過(guò)引入多項(xiàng)式特征量作為新的特征量；神經(jīng)網(wǎng)絡(luò)通過(guò)引入隱藏層，逐層進(jìn)化解決非線性分類問題；而SVM是通過(guò)引入核函數(shù)(kernel function)來(lái)解決非線性問題。具體做法如下：

對(duì)于給定輸出x, 規(guī)定一定數(shù)量的landmarks，記為；

將x,作為核函數(shù)的輸入，得到新的特征量，若將核函數(shù)記為similarity()，則有

，其中與為一一對(duì)應(yīng)；

將新的特征量替代原有特征量，得到假設(shè)函數(shù)如下：

現(xiàn)在有兩個(gè)問題，

如何選擇landmarks？

用什么樣的核函數(shù) ?

對(duì)于第一個(gè)問題，可以按照如下方式，即將訓(xùn)練集的輸入作為landmarks

所以特征量的個(gè)數(shù)與訓(xùn)練集的個(gè)數(shù)相等，即n = m，所以帶有核的SVM變?yōu)槿缦滦问剑?/p>

對(duì)于第二個(gè)問題，常用的核函數(shù)有線性核，高斯核，多項(xiàng)式核，Sigmoid核，拉普拉斯核等，現(xiàn)以常用的高斯核(Gaussian)為例。

高斯核具有如下性質(zhì)：

也就是說(shuō)，如果x和landmark接近，那么核函數(shù)的值也就是新的特征量將會(huì)接近1，而如果x和landmark距離很遠(yuǎn)，那么核函數(shù)的值將會(huì)接近0.

是高斯核的參數(shù)，它的大小會(huì)影響核函數(shù)值的變化快慢，具體的，圖8-3是一個(gè)二維情況下的特殊例子，但是所含有的性質(zhì)是可推廣的。即越大，核函數(shù)變化(下降)越緩慢，反之，越小，核函數(shù)變化越快。

圖8-3 參數(shù)對(duì)高斯核的影響舉例

如何選擇參數(shù)？

下面對(duì)SVM的參數(shù)對(duì)偏差和方差的影響做簡(jiǎn)要分析：

C: 由于C和(1 /λ)正相關(guān)，對(duì)λ的分析有：

8.5 Using a SVM

上文簡(jiǎn)單的介紹了SVM的優(yōu)化原理以及核函數(shù)的使用方式。在實(shí)際應(yīng)用SVM中，我們不需要自己去實(shí)現(xiàn)SVM的訓(xùn)練算法來(lái)得到參數(shù)，通常是使用現(xiàn)有的軟件包(如liblinear, libsvm)。

但是下面的工作是我們需要做的：

選擇參數(shù)C的值

選擇并實(shí)現(xiàn)核函數(shù)

如果核函數(shù)帶參數(shù)，需要選擇核函數(shù)的參數(shù)，例如高斯核需要選擇

如果無(wú)核(選擇線性核)，即給出線性分類器，適用于n大，m小的情況

選擇非線性核（如高斯核），適用于n小，m大的情況

下面是需要注意的地方：

在使用核函數(shù)之前要對(duì)特征量進(jìn)行規(guī)范化

并不是所有的函數(shù)是有效的核函數(shù)，它們必須滿足Mercer定理。

如果想要通過(guò)訓(xùn)練得到參數(shù)C或者核函數(shù)的參數(shù)，應(yīng)該是在訓(xùn)練集和交叉檢驗(yàn)集上進(jìn)行

8.5.1 Multi-class Classification

8.5.2 Logistic Regression vs. SVMs