線性SVM分類器通過簡(jiǎn)單地計(jì)算決策函數(shù)

背后機(jī)制

這個(gè)章節(jié)從線性 SVM 分類器開始，將解釋 SVM 是如何做預(yù)測(cè)的并且算法是如何工作的。如果你是剛接觸機(jī)器學(xué)習(xí)，你可以跳過這個(gè)章節(jié)，直接進(jìn)入本章末尾的練習(xí)。等到你想深入了解 SVM，再回頭研究這部分內(nèi)容。

首先，關(guān)于符號(hào)的約定：在第 4 章，我們將所有模型參數(shù)放在一個(gè)矢量θ里，包括偏置項(xiàng)θ0，θ1到θn的輸入特征權(quán)重，和增加一個(gè)偏差輸入x0 = 1到所有樣本。在本章中，我們將使用一個(gè)不同的符號(hào)約定，在處理 SVM 上，這更方便，也更常見：偏置項(xiàng)被命名為b，特征權(quán)重向量被稱為w，在輸入特征向量中不再添加偏置特征。

決策函數(shù)和預(yù)測(cè)

線性 SVM 分類器通過簡(jiǎn)單地計(jì)算決策函數(shù)

來預(yù)測(cè)新樣本的類別：如果結(jié)果是正的，預(yù)測(cè)類別?是正類，為 1，否則他就是負(fù)類，為 0。見公式 5-2

圖 5-12 顯示了和圖 5-4 右邊圖模型相對(duì)應(yīng)的決策函數(shù)：因?yàn)檫@個(gè)數(shù)據(jù)集有兩個(gè)特征（花瓣的寬度和花瓣的長度），所以是個(gè)二維的平面。決策邊界是決策函數(shù)等于 0 的點(diǎn)的集合，圖中兩個(gè)平面的交叉處，即一條直線（圖中的實(shí)線）

虛線表示的是那些決策函數(shù)等于 1 或 -1 的點(diǎn)：它們平行，且到?jīng)Q策邊界的距離相等，形成一個(gè)間隔。訓(xùn)練線性 SVM 分類器意味著找到w值和b值使得這一個(gè)間隔盡可能大，同時(shí)避免間隔違規(guī)（硬間隔）或限制它們（軟間隔）

訓(xùn)練目標(biāo)

看下決策函數(shù)的斜率：它等于權(quán)重向量的范數(shù)。如果我們把這個(gè)斜率除于 2，決策函數(shù)等于 ±1 的點(diǎn)將會(huì)離決策邊界原來的兩倍大。換句話，即斜率除于 2，那么間隔將增加兩倍。在圖 5-13 中，2D 形式比較容易可視化。權(quán)重向量w越小，間隔越大。

所以我們的目標(biāo)是最小化，從而獲得大的間隔。然而，如果我們想要避免間隔違規(guī)（硬間隔），對(duì)于正的訓(xùn)練樣本，我們需要決策函數(shù)大于 1，對(duì)于負(fù)訓(xùn)練樣本，小于 -1。若我們對(duì)負(fù)樣本（即）定義，對(duì)正樣本（即）定義，那么我們可以對(duì)所有的樣本表示為

因此，我們可以將硬間隔線性 SVM 分類器表示為公式 5-3 中的約束優(yōu)化問題

注

為了獲得軟間隔的目標(biāo)，我們需要對(duì)每個(gè)樣本應(yīng)用一個(gè)松弛變量（slack variable） 表示了第i個(gè)樣本允許違規(guī)間隔的程度。我們現(xiàn)在有兩個(gè)不一致的目標(biāo)：一個(gè)是使松弛變量盡可能的小，從而減小間隔違規(guī)，另一個(gè)是使1/2 w·w盡量小，從而增大間隔。這時(shí)C超參數(shù)發(fā)揮作用：它允許我們?cè)趦蓚€(gè)目標(biāo)之間權(quán)衡。我們得到了公式 5-4 的約束優(yōu)化問題。

二次規(guī)劃

硬間隔和軟間隔都是線性約束的凸二次規(guī)劃優(yōu)化問題。這些問題被稱之為二次規(guī)劃（QP）問題?，F(xiàn)在有許多解決方案可以使用各種技術(shù)來處理 QP 問題，但這超出了本書的范圍。一般問題的公式在公式 5-5 給出。

對(duì)偶問題

給出一個(gè)約束優(yōu)化問題，即原始問題（primal problem），它可能表示不同但是和另一個(gè)問題緊密相連，稱為對(duì)偶問題（Dual Problem）。對(duì)偶問題的解通常是對(duì)原始問題的解給出一個(gè)下界約束，但在某些條件下，它們可以獲得相同解。幸運(yùn)的是，SVM 問題恰好滿足這些條件，所以你可以選擇解決原始問題或者對(duì)偶問題，兩者將會(huì)有相同解。公式 5-6 表示了線性 SVM 的對(duì)偶形式（如果你對(duì)怎么從原始問題獲得對(duì)偶問題感興趣，可以看下附錄 C）

一旦你找到最小化公式的向量α（使用 QP 解決方案），你可以通過使用公式 5-7 的方法計(jì)算w和b，從而使原始問題最小化。

當(dāng)訓(xùn)練樣本的數(shù)量比特征數(shù)量小的時(shí)候，對(duì)偶問題比原始問題要快得多。更重要的是，它讓核技巧成為可能，而原始問題則不然。那么這個(gè)核技巧是怎么樣的呢？

核化支持向量機(jī)

假設(shè)你想把一個(gè) 2 次多項(xiàng)式變換應(yīng)用到二維空間的訓(xùn)練集（例如衛(wèi)星數(shù)據(jù)集），然后在變換后的訓(xùn)練集上訓(xùn)練一個(gè)線性SVM分類器。公式 5-8 顯示了你想應(yīng)用的 2 次多項(xiàng)式映射函數(shù)?。

注意到轉(zhuǎn)換后的向量是 3 維的而不是 2 維。如果我們應(yīng)用這個(gè) 2 次多項(xiàng)式映射，然后計(jì)算轉(zhuǎn)換后向量的點(diǎn)積（見公式 5-9），讓我們看下兩個(gè) 2 維向量a和b會(huì)發(fā)生什么。

轉(zhuǎn)換后向量的點(diǎn)積等于原始向量點(diǎn)積的平方：

Mercer 定理

根據(jù) Mercer 定理，如果函數(shù)K(a, b)滿足一些 Mercer 條件的數(shù)學(xué)條件(K函數(shù)在參數(shù)內(nèi)必須是連續(xù)，對(duì)稱，即K(a, b)=K(b, a)，等)，那么存在函數(shù)?，將a和b映射到另一個(gè)空間（可能有更高的維度），有。所以你可以用K作為核函數(shù)，即使你不知道?是什么。使用高斯核（Gaussian RBF kernel）情況下，它實(shí)際是將每個(gè)訓(xùn)練樣本映射到無限維空間，所以你不需要知道是怎么執(zhí)行映射的也是一件好事。

注意一些常用核函數(shù)（例如 Sigmoid 核函數(shù)）并不滿足所有的 Mercer 條件，然而在實(shí)踐中通常表現(xiàn)得很好。

我們還有一個(gè)問題要解決。公式 5-7 展示了線性 SVM 分類器如何從對(duì)偶解到原始解，如果你應(yīng)用了核技巧那么得到的公式會(huì)包含。事實(shí)上，w必須和有同樣的維度，可能是巨大的維度或者無限的維度，所以你很難計(jì)算它。但怎么在不知道w的情況下做出預(yù)測(cè)？好消息是你可以將公式 5-7 的w代入到新的樣本的決策函數(shù)中，你會(huì)得到一個(gè)在輸入向量之間只有點(diǎn)積的方程式。這時(shí)，核技巧將派上用場(chǎng)，見公式 5-11

注意到支持向量才滿足α(i)≠0，做出預(yù)測(cè)只涉及計(jì)算為支持向量部分的輸入樣本的點(diǎn)積，而不是全部的訓(xùn)練樣本。當(dāng)然，你同樣也需要使用同樣的技巧來計(jì)算偏置項(xiàng)b，見公式 5-12

如果你開始感到頭痛，這很正常：因?yàn)檫@是核技巧一個(gè)不幸的副作用

在線支持向量機(jī)

在結(jié)束這一章之前，我們快速地了解一下在線 SVM 分類器（回想一下，在線學(xué)習(xí)意味著增量地學(xué)習(xí)，不斷有新實(shí)例）。對(duì)于線性SVM分類器，一種方式是使用梯度下降（例如使用SGDClassifire）最小化代價(jià)函數(shù)，如從原始問題推導(dǎo)出的公式 5-13。不幸的是，它比基于 QP 方式收斂慢得多。

代價(jià)函數(shù)第一個(gè)和會(huì)使模型有一個(gè)小的權(quán)重向量w，從而獲得一個(gè)更大的間隔。第二個(gè)和計(jì)算所有間隔違規(guī)的總數(shù)。如果樣本位于“街道”上和正確的一邊，或它與“街道”正確一邊的距離成比例，則間隔違規(guī)等于 0。最小化保證了模型的間隔違規(guī)盡可能小并且少。

Hinge 損失

函數(shù)max(0, 1–t)被稱為 Hinge 損失函數(shù)（如下）。當(dāng)t≥1時(shí)，Hinge 值為 0。如果t<1,它的導(dǎo)數(shù)（斜率）為 -1，若t>1，則等于0。在t=1處，它是不可微的，但就像套索回歸（Lasso Regression）（參見 130 頁套索回歸）一樣，你仍然可以在t=0時(shí)使用梯度下降法（即 -1 到 0 之間任何值）

我們也可以實(shí)現(xiàn)在線核化的 SVM。例如使用“增量和遞減 SVM 學(xué)習(xí)”或者“在線和主動(dòng)的快速核分類器”。但是，這些都是用 Matlab 和 C++ 實(shí)現(xiàn)的。對(duì)于大規(guī)模的非線性問題，你可能需要考慮使用神經(jīng)網(wǎng)絡(luò)（見第二部分）