【機器學習】SVM理解及推導

05-10

前言
最近發現自己的基礎知識不夠紮實，面對別人的問題總是「知其然不知其所以然」。出現這個問題的朋友周圍有很多，大多數人都是「拿來主義」，想著「有了開源庫，有了函數包，只要會用就行，在遇到具體問題的時候再去尋找相應的解決辦法」，這種「非系統」的學習思想其實殆害無窮，在自己想要踏實做一個工程時，會出現眼界窄，能力不足的問題，有時候為解決一個問題千方百計地找到了一個非常好用的函數，而這個函數自己根本沒聽過。如果自己深入專研這方面的話，第一反應就是使用最便捷的方法了，這便是「紮實」的基本功帶來的好處。
在簡書、知乎、CSDN上有許多前輩已經總結了好的學習資料，自己也從中獲益良多，但每次不論文章寫得多好，過段時間還是忘了，反思了一下還是沒有將其「私有化」，因此現在用自己的話總結一些基礎知識，如果在學習記錄的同時，可以給大家理解枯燥的理論知識帶來一點點幫助，不勝榮幸。

1.面試中考察SVM的必要性

其一：面試官便於了解面試者的基礎知識，數學基本功，學習態度，可以通過一些基礎模型來看出這個面試者是否能夠勝任該崗位。

其二：由於機器學習範疇大，流派多，面試官懂的可能你不懂，你懂的可能面試官沒有提前準備，索性來個大家都應該懂的——SVM、LR等。

因此，面試前準備一些基礎知識的理解和推導是對本次面試最起碼的態度（面試官把最基本的題都告訴你了，如果連這些你都答不上來，那不好意思了）。

2.基本介紹

SVM最初是為解決二元分類問題而設計的，假設我們在桌面（二維平面下）上有兩種顏色的球，我們需要用一條直線把它們分成兩類。如果在平面上我們沒法用一條直線把它們分成兩類，我們就採取猛拍桌子（核技巧）的方法，把球振到空中（多維空間下），迅速扔出一張紙，將兩個顏色的球在空間中分隔開。我們把這些球叫做「data」（數據源），把直線叫做「classifier」（分類器）, 拍桌子叫做「kernelling」（建立核函數）, 那張紙叫做「hyperplane」（超平面）。

來自wiki

3.SVM的推導（線性可分的情況）

給定樣本集

$D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}$ （式0）

其中 $x$ 為 $1*m$ 維的向量（有m個屬性的一條訓練數據）。

目的：尋找一個最優（泛化能力最強）的超平面，將不同類別的樣本分開。

超平面可用

$w^T+b=0$ （式1）

描述，其中w為法向量，b為位移項。w和b其實就是模型的參數。

任意點x到超平面(w,b)的距離為

$gamma=frac{|w^T+b|}{||w||}$ （式2）

如果超平面將樣本成功分類，則下式成立

$left{egin{array}{l} w^Tx_i+bgeqslant+1, y_i=+1 \ w^Tx_i+bgeqslant-1, y_i=-1 end{array} ight.$ （式3）

使等號成立的幾個樣本點稱為「支持向量」，兩個異類支持向量到超平面的距離之和為

$gamma=frac{2}{||w||}$ （式4）

其被稱為「間隔」。我們要找到具有「最大間隔」的超平面，即

$egin{aligned} &max_{w,b} frac{2}{||w||} \ &s.t. y_i(w^Tx_i+b)geqslant1,i=1,2,...,m. end{aligned}$ （式5）

可以知道，最大化 ${||w||}^{-1}$ ，等價於最小化 ${||w||}^2$ 。

（PS：使用平方L2範數的原因是 ${||w||}^2=w^Tw$ ）

將式5重寫為

$egin{aligned} &max_{w,b} frac{1}{2}{||w||}^2 \ &s.t. y_i(w^Tx_i+b)geqslant1,i=1,2,...,m. end{aligned}$ （式6）

式6為SVM的「基本型」。求解式6來得到模型

$f(x)=w^T+b$ （式7）

對式6中的每條約束加上拉格朗日乘子 $alpha_igeq0$ ，得到

$L(w,b,alpha)=frac{1}{2}{||w||}^2+sum_{i=1}^{m}alpha_i(1-y_i(w^Tx_i+b))$ （式8）

令L分別對w和b的偏導為0，得

$w=sum_{i=1}^{m}alpha_iy_ix_i$ （式9）

$0=sum_{i=1}^{m}alpha_iy_i$ （式10）

代入式8中，得到式6的對偶問題（線性規劃有一個有趣的特性，就是任何一個求極大的問題都有一個與其匹配的求極小的線性規劃問題。）

$egin{aligned} &max_{alpha }sum_{i=1}^{m}alpha_i-frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}alpha _ialpha _jy_iy_j{x_i}^Tx_j \ &s.t.sum_{i=1}^{m}alpha_iy_i=0, \ &alpha_igeqslant0,i=1,2,...,m. end{aligned}$ （式11）

求w（即求α）和b，得模型

$egin{aligned} f(x)&=w^Tx+b \ &=sum_{i=1}^{m}alpha _iy_i{x_i}^T+b end{aligned}$ （式12）

上述過程需滿足KKT條件。

使用SMO演算法來求取 $alpha$ ，使支持向量的性質來求 $b$ 。

這裡應該指出，每一個理論的每一個介紹者給出的介紹都可能不盡符合你，或多或少會出現不好理解的情況，原因在於每個人（包括介紹者和學習者）的思維習慣、知識基礎、問題背景都不盡相同。自己在學習時總結的經驗就是「集成學習」（即取各家之所長），多看幾個優秀介紹者的介紹。比如SVM的就充分借鑒了《機器學習》（周志華）等人的介紹。

參考

1.《機器學習》（周志華）

2. 支持向量機(SVM)是什麼意思？

3. 機器學習面試之有必要手推SVM嗎？

機器學習面試之有必要手推SVM嗎(2)?

4. 支持向量機SVM推導及求解過程

轉載請註明如下內容：

本文作者： @Forfreedom
簡書號：For_freedom - 簡書
簡書原文鏈接：【機器學習】SVM理解及推導