本文參考整理了Coursera上由NTU的林軒田講授的《機(jī)器學(xué)習(xí)技法》課程的第一章的內(nèi)容，主要介紹了支撐向量機(jī)SVM的基本概念，文中的圖片都是截取自在線課程的講義。
歡迎到我的博客跟蹤最新的內(nèi)容變化。
如果有任何錯誤或者建議，歡迎指出，感激不盡！

Large-Margin Separating Hyperplane

首先來看一個問題，如果要用一條線來進(jìn)行二元分類，以下哪一條線最好呢？

大部分人可能感覺最右邊的線最好，怎么解釋？
因為最右邊的線離最近點的距離更大，對點的noise更魯棒、強(qiáng)壯。

假設(shè)noise服從高斯分布，則將來測試樣本點x'≈x(可能x'就是x，只是因為測量誤差等原因造成約等于)的話，那么分類結(jié)果應(yīng)該一致。

三條線對測量誤差的容忍度不同，容忍度越大則對過擬合overfitting更加robust(因為測量誤差也是一種Noise，而Noise會引起Overfitting)。

用線距離最近點的距離來衡量這個屬性。

換種描述，我們叫線有多“胖”，即線往兩側(cè)最大擴(kuò)展多遠(yuǎn)才會碰到最近的點。

目標(biāo)：找到最胖的分割線(超平面)。

問題描述為：

正式定義（Large-Margin Separating Hyperplane）：

胖是一種非正式的描述，正式名稱為margin。

Standard Large-Margin Problem

如何計算點到直線的距離？

distance(Xn,W)

為了計算距離的方便，將W的表示形式進(jìn)行縮短，去掉截距項W0，輸入樣本特征的X0=1也去掉。

h(x) = sign(W’X + b)

因此用distance(X,b,W)代表點X到平面W’X+b=0的距離。

注意：在本文中用大寫英文字母表示矩陣或向量，如X、W，用W’表示矩陣的轉(zhuǎn)置,用小寫字母表示標(biāo)量。

考慮平面上的兩個點X和X`，則滿足平面方程，有：

W'X = -b
W'X`= -b

則

W'(X`-X) = -b - (-b) = 0

而X`-X是平面上的一個向量，對于任意考慮的兩個點X和X`，W與(X`-X)的內(nèi)積都是0，所以W垂直于這個平面，W是法向量。

所以點到平面的距離等于點到平面上任意一點的距離投到法向量的投影長度。

所以距離公式為：

化簡標(biāo)準(zhǔn)問題

我們只考慮可以完美分隔XX和OO的線，它有性質(zhì)：

對于每一個n，yn*(W'Xn + b) > 0

因為|yn|=1，所以絕對值可以脫掉

現(xiàn)在的最佳化問題如下：

其實這個世界上可能沒有那么多條線，比如
W`X + b = 0 和 3W'X + 3b = 0 表示的是同一條直線，也就是說法向量的長度不影響線的表示。

所以我們可以利用特別的放縮，使得

所以我們可以只考慮由特殊的(b,W)表達(dá)的分隔線，滿足以上條件，則

則最優(yōu)化問題可以簡化為：

而min=1同時也意味著every>0，第一個條件可以刪去而不影響結(jié)果。

但問題仍然不好解，主要因為條件有個min操作，是否可以把條件放松一點呢？

條件放松，需要證明最優(yōu)解一樣。

滿足原始條件必然滿足放松條件(必要條件)，而通過反證法可以證明滿足放松條件的也一定滿足原始條件，因此兩個條件等價。

問題可以表述如下：

將討厭的max改為min，將W的模方的開方根號去掉，補(bǔ)充一個便于后續(xù)計算的常數(shù)1/2，得到最終的問題表述。

該問題稱為“標(biāo)準(zhǔn)問題”(Standard Problem).

Support Vector Machine

名稱解釋

最胖的那條線g(svm)就叫做支撐向量機(jī)(SVM)

用方框圈起的是離線最近的那些點，有趣的是，如果刪去其他不是方框框住的點，所找出的最胖的線仍然不變，所以這些最近的點已經(jīng)足夠告訴我們最胖的線長什么樣子，而其他的點不重要。

我們稱這些方框圈住的最近的點，告訴我們最胖的線在哪的這些點，為支撐向量[候選者] (Support Vector[candidate])。

所以support vector machine（SVM）就是在support vectors的幫助下，學(xué)習(xí)找出最胖的分割超平面。

求解一般SVM問題

該最優(yōu)化問題不適合梯度下降法，因為有約束，也不便于直接手動求解，但幸運的是，該問題屬于一類已知的最優(yōu)化類型。

它的最小化目標(biāo)是一個二次函數(shù)（convex），它的所有約束條件都是W和b的一次式，有這樣性質(zhì)的最佳化問題，一般稱為“二次規(guī)劃”(Quadratic Programming)。

做數(shù)值最佳化的人發(fā)現(xiàn)這樣的問題很容易解決，并已有多種求解QP問題的軟件工具，因此我們需要將該問題表示成QP的標(biāo)準(zhǔn)形式，再輸入到算法中，即可求解最優(yōu)解。

二次規(guī)劃的標(biāo)準(zhǔn)形式

目標(biāo)是最小化向量U的二次函數(shù)，二次項的系數(shù)放在矩陣Q中，一次項的系數(shù)放在向量P中。

條件是U向量的線性約束，共有M個條件，每個條件的一次式的系數(shù)放在向量Am中，常數(shù)項放在常數(shù)cm中，把所有的向量Am集合起來到一個矩陣A中，把所有的常數(shù)cm放到一個向量C中。

我們的當(dāng)前問題描述為：

將b和W集成一個向量U

系數(shù)表示如下

注意要閱讀QP算法的相關(guān)手冊說明。

所以求解一般SVM問題的步驟如下：

hard-margin（硬邊界）：不允許任何點違反“胖分割線”。

linear：在X原始空間中直接使用Xn向量，沒有經(jīng)過任何特征轉(zhuǎn)換，如果要使用非線性的分割線（即X空間的曲線），可以考慮使用Z=Φ(X)轉(zhuǎn)換。

為什么要使用最大邊界的分隔超平面？

最開始的理由：“胖”一點的分割線對測量誤差的容忍度更好

與regularization的對比：

所以SVM其實就是一種regularization，只是它regularization的解釋是邊界Margin要盡可能大，以能夠抵抗一些測量誤差。
即也是一種“weight-decay regularization within Ein = 0”(保證Ein為0的權(quán)重衰減正則化方法)，因此SVM可以一定程度上防止overfitting。

從VC維度解釋
從另一個角度解釋，利用導(dǎo)入VC維度時引入的二劃分(dichotomy)概念，考慮這樣一種“l(fā)arge-margin”演算法A(ρ)：

如果存在一條線g滿足margin(g)>=ρ時，返回g；否則如果不存在則返回0.

這樣的演算法在某一種特定的資料上，到底能夠產(chǎn)生多少種OO和XX的排列組合(即dichotomies)呢？

越少的dichotomies ==> 越小的'VC維度'(有效的VC維度) ==> 更好的泛化(generalization)性能

演算法的VC維度

之前所說的VC維度都是指假設(shè)空間（即一堆hypotheses）的VC維度，這里給出演算法的VC維度概念。

演算法的VC維度和資料相關(guān)(data-dependent)，比如上述的Aρ。

例如：

假設(shè)在2維平面上有一個單位圓，當(dāng)數(shù)據(jù)從單位圓內(nèi)取值時

• 當(dāng)ρ=0時，等價于PLA，因此dVC=3
• 當(dāng)ρ>√3/2時，并不能shatter任意的3個點，因此dVC<3 【因為任何3個點中總有兩個點的距離小于√3，】

一般地，當(dāng)數(shù)據(jù)點取值在一個半徑為R的超球體內(nèi)時，有：

Large-Margin Hyperplanes 的好處

• 數(shù)量#少比較好，因為可以控制dVC，優(yōu)化泛化性能
• 邊界復(fù)雜比較好，可能會有更好的Ein

原來我們只能做好其中之一，但如果把large-margin和feature transform合起來考慮，就可能兩者都做好。

即我們有了一種新的可能選擇：非線性SVM

Mind Map Summary

有關(guān)非線性SVM及更多機(jī)器學(xué)習(xí)算法相關(guān)的內(nèi)容將在日后的幾篇文章中分別給出，敬請關(guān)注！