《統(tǒng)計學習方法》第 7 章“支持向量機”學習筆記

關鍵字：函數(shù)間隔火诸、幾何間隔、正則化的合頁損失函數(shù)荠察、凸二次規(guī)劃置蜀、核技巧（核函數(shù)）、輸入空間悉盆、特征空間盯荤、歐式空間、希爾伯特空間焕盟。

我這篇筆記主要是介紹李航的《統(tǒng)計學習方法》第 7 章內(nèi)容秋秤，以筆記的方式呈現(xiàn)。需要說明的是脚翘，為了使得本文盡量易懂灼卢，我把書上的一些標題或者專有名詞做了更改，只是為了幫助初學的朋友們的理解来农。

SVM 的思想鞋真，從感知機開始

1、研究基礎：感知機沃于，二分類問題涩咖，并且數(shù)據(jù)是線性可分的；

感知機的缺點：數(shù)據(jù)集必須線性可分繁莹。如果數(shù)據(jù)集不能線性可分檩互，（在不限制迭代次數(shù)的情況下），算法無法收斂蒋困。

2盾似、感知機的決策邊界是不唯一的，而 SVM 得到的決策邊界唯一；

3零院、感知機對數(shù)據(jù)不能線性可分的情況下溉跃，它的訓練不收斂，而 SVM 更多地考慮到了模型的泛化能力告抄，對于未知的數(shù)據(jù)撰茎， SVM 有更好的預測能力；

比較下面兩張圖打洼，我們認為數(shù)據(jù)點應該盡量遠離決策邊界龄糊，這是我們指定嚴格線性可分支持向量機的學習準則，即策略募疮，因為如果數(shù)據(jù)點距離決策邊界很近炫惩，決策邊界的一點點改動，都會造成一些數(shù)據(jù)點的預測類別改變阿浓，這是不穩(wěn)定的他嚷。

說明：這里“硬間隔”對應了我前面說的“嚴格線性可分”，是相對于后面敘述的“軟間隔”而言的芭毙，可以看到軟間隔的時候筋蓖，再來理解這一點。

4退敦、SVM 嘗試尋找一個最優(yōu)的決策邊界粘咖，這個決策邊界距離兩個類別“最近的樣本”足夠遠，并且考慮到模型的泛化能力侈百，允許不分點分錯（soft margin）瓮下；

5、一些重要的概念：支持向量（距離決策邊界最近的那些點）钝域；尋找到的決策邊界是分離超平面唱捣；margin = 2d。

研究思路

1网梢、最大化間隔（soft margin 其實就是正則化，參數(shù) C 控制松弛因子）赂毯；

2战虏、轉(zhuǎn)化成最優(yōu)化問題的標準格式（注意：此時是有約束的）；

3党涕、使用拉格朗日乘子法把約束去掉烦感；

4、轉(zhuǎn)向拉格朗日對偶問題膛堤；我們本來的目標是求 w 和 b手趣，但是我們轉(zhuǎn)向求 \alpha 了，通過求得的 \alpha，得到 w 和 b 的表達式绿渣。

5朝群、使用 SMO 解決這個問題，我們發(fā)現(xiàn)中符， w 和 b 只由部分支持向量決定姜胖，即拉格朗日引入的參數(shù)里，很多都是 0淀散；

6右莱、為了處理非線性問題，我們引入了核函數(shù)（相似性函數(shù)）：

低維度不能線性可分档插，高維度可以線性可分慢蜓，這是研究的基本思路；

升維以后郭膛，計算量巨大晨抡，為了解決這個問題，引入了核函數(shù)饲鄙，使得我們的計算不必放到高維空間去計算凄诞；

常用的核函數(shù)有：線性核函數(shù)、多項式核函數(shù)忍级、高斯核函數(shù)帆谍。

線性不可分有兩種策略：1、軟間隔：允許一些點分錯轴咱；2汛蝙、核函數(shù)。

可以取函數(shù)間隔等于 1 是為什么

我看到這一部分覺得比較難理解的是朴肺，怎么就把最后的目標函數(shù)窖剑，即兩條間隔邊界的距離變成

{\max_{w,b}} \quad \cfrac{1}{||w||}

書上怎么就莫名其妙取 \hat \gamma=1，然后得到線性可分的支持向量機的最優(yōu)化問題

\begin{aligned} {\rm \min_{w,b}} \quad & \cfrac{1}{2}||w||^2 \\ {\rm s.t.} \quad & y_i(w \cdot x_i+b) - 1\geq 0, \quad i = 1, 2, \cdots,N \end{aligned}

假設兩條平行直線分別是：

Wx+A=0,\tag{1}

與

Wx+B=0.\tag{2}

那么和這兩條直線平行戈稿，且位于中間的那條直線就可以表示成：
Wx + A + \frac{B-A}{2} = 0. \tag{3}

令 t=B-A西土，則有 B=t+A。將 t=B-A 代入（3）鞍盗，得到
Wx+A+\frac{t}{2}=0.\tag{4}

將 B=t+A 代入（2）需了，得到
Wx+t+A=0.\tag{5}

整理一下，這三條直線現(xiàn)在可以寫成
Wx+A=0,\tag{6}
Wx+t+A=0,\tag{7}
Wx+A+\frac{t}{2}=0.\tag{8}

下面給（6）左右都加上 \cfrac{t}{2}般甲，給（7）左右都減去 \cfrac{t}{2}肋乍，得到

Wx+A+\frac{t}{2}=\frac{t}{2},\tag{9}
與
Wx+A+\frac{t}{2}=-\frac{t}{2}.\tag{10}
接下來將等式（8）、（9）敷存、（10）的兩邊都乘以 \frac{2}{t}墓造，得
\cfrac{2}{t}Wx+\cfrac{2}{t}(A+\cfrac{t}{2})=0,\tag{11}

\cfrac{2}{t}Wx+\cfrac{2}{t}(A+\cfrac{t}{2})=1,\tag{12}

\cfrac{2}{t}Wx+\cfrac{2}{t}(A+\cfrac{t}{2})=-1.\tag{13}

令 w=\frac{2}{t}W，b=\frac{2}{t}(A+\frac{t}{2})，則等式（11）觅闽、等式（12）帝雇、等式（13）又可以寫成：

wx+b=0,\tag{14}

wx+b=1,\tag{15}

wx+b=-1.\tag{16}

化簡成這樣的主要原因是，間隔（margin）的表達式最簡單谱煤。

可以假設向量 x_1 在 wx+b=1 上摊求，向量 x_2 在 wx+b=-1 上，間隔（margin）的表達式為
margin = d = |x_1-x_2|\cdot \cos \theta.\tag{17}

其中 \theta 是向量 x_1-x_2 與平行直線的法向量 w 的夾角刘离。為了利用向量的工具室叉，我們可以在等式（17）兩邊都乘以 |w|，則有
d\cdot |w| = |x_1-x_2| \cdot |w| \cdot \cos \theta = |w(x1-x2)| .\tag{18}
又因為向量 x_1 在 wx+b=1 上硫惕，向量 x_2 在 wx+b=-1 上茧痕，則
wx_1+b=1,

wx_2+b=-1.

所以

|w(x1-x2)|=|wx_1-wx_2|=|1-b-(-1-b)|=2=d\cdot |w|.

所以
d = \frac{2}{|w|}.

手寫筆記如下：

學習“支持向量機”的步驟

“支持向量機”的內(nèi)容非常多，掌握“支持向量機”是要花費一定時間的恼除，經(jīng)匙倏酰看著看著，就不知道自己在看啥了豁辉。下面我簡單羅列一下關于“支持向量機”的研究順序令野，和各個知識點的地位和作用，希望能給看到我這篇筆記的朋友們一些幫助徽级。

"支持向量機"學習方法包含構建由簡單到復雜的模型气破。

—— 李航《統(tǒng)計學習方法》第 7 章“支持向量機”引言部分。

由簡單到復雜的模型依次就是下面 3 個模型餐抢，我從統(tǒng)計學習 3 要素的角度（模型现使、策略、方法旷痕，李航《統(tǒng)計學習方法》第 1 章就有介紹）對它們再做一層剖析碳锈。

第 1 階段：嚴格線性可分支持向量機

“嚴格線性可分支持向量機”即書上說的“線性可分支持向量機”。我這里強調(diào)“嚴格”是為了突出我們此時對模型的假設欺抗，這個假設和感知機模型是完全一致的售碳。

注：感知機模型是李航的《統(tǒng)計學習方法》介紹的第 1 個模型，麻雀雖小五臟俱全绞呈，我個人認為還是非常重要的团滥，雖然很簡單（那是在我了解他以后才覺得），在實際做分類的時候不會用它报强，但感知機模型從模型假設（線性可分）、到找到策略（損失函數(shù)最小化）拱燃、到使用方法（隨機梯度下降法）秉溉，比較完整清晰地體現(xiàn)了機器學習研究的基本步驟，并且感知機模型中提到的一些概念，例如線性可分召嘶、超平面父晶、超平面的法向量、點到超平面的距離公式弄跌，定義類標為 -1 和 1甲喝，使用類標乘以預測結(jié)果表示預測正確與否，這些思想和技巧在支持向量機都可以看到铛只，甚至感知機也有對偶問題的算法（對偶問題的算法提出就是為了方便計算埠胖，將參數(shù)的學習歸結(jié)為部分樣本數(shù)據(jù)特征和標簽的線性組合，二者在這點上也是非常一致的）局荚，這一點也是極其相似的氢妈，因此寝杖，在學習支持向量機的時候，感知機如果你忘了的話谋竖，可以趁機復習一下。

后一個模型“差一點線性可分的支持向量機”就可以通過引入一個容忍錯誤的度量承匣，和嚴格線性可分的情況使用相同的“策略”和“方法”完成分類任務蓖乘。

具體，我們在看第 2 部分“線性支持向量機”的時候韧骗，其實可以看到嘉抒，很多地方都是在摘抄第 1 部分的結(jié)論，在一些邊界條件和目標函數(shù)上稍有不同而已宽闲，第 1 部分搞懂了众眨，第 2 部分就非常快了容诬。

前面會跟你扯一些“代數(shù)間隔”娩梨、“幾何間隔”的概念，我個人覺得不太重要览徒，回過頭來看都不要緊狈定，介紹這兩個概念無非是要保證后續(xù)敘述的無比正確性，這是寫數(shù)學專著的要求习蓬；

策略：策略這部分是很重要的纽什，策略如果你忘了是什么，翻到書本第 1 章看看策略是什么躲叼，“硬間隔最大化”是核心思想芦缰，策略就是學習的準則，在“嚴格線性可分”的前提下枫慷，“硬間隔最大化”保證了模型有更好的泛化能力让蕾，即對未知數(shù)據(jù)的預測能力浪规。

image

“硬間隔最大化的支持向量機”問題最終轉(zhuǎn)換成了數(shù)學問題，我們解這個最優(yōu)化問題：

{\rm \min_{w,b}} \qquad \cfrac{1}{2}||w||^2 \\ {\rm s.t.} \qquad y_i(w \cdot x_i+b) - 1\geq 0, \quad i = 1, 2, \cdots,N
輸入是嚴格線性可分的數(shù)據(jù)對 (\vec x,y)探孝，輸出是這個問題的最優(yōu)解 w^* 和 b^*笋婿。然后最優(yōu)超平面就得到了：

w^* \cdot \vec x + b^* = 0

做預測的時候把 \vec x 代入 w^{*} \cdot \vec x + b^{*} 判斷符號，大于 0 的歸為一類顿颅，小于 0 的歸為另一類缸濒。

看到這里，其實我覺得可以先跳過書本的一些部分粱腻，直接到 7.2 節(jié)“線性支持向量機與軟間隔最大化”庇配。因為其實你已經(jīng)知道”支持向量機“在做什么了。最起碼它能解決嚴格線性可分的二分類數(shù)據(jù)問題栖疑。比起感知機而言讨永，它得到的決策邊界是唯一的，并且是對未知數(shù)據(jù)有很好的預測能力遇革。

在這個問題里卿闹，模型和感知機是一樣的，即二分類數(shù)據(jù)“嚴格”線性可分萝快，策略是“硬間隔最大化”锻霎，這一點用數(shù)學表達成能表示成如下形式：

{\rm \min_{w,b}} \qquad \cfrac{1}{2}||w||^2 \\ {\rm s.t.} \qquad y_i(w \cdot x_i+b) - 1\geq 0, \quad i = 1, 2, \cdots,N

看到這里，你可能會問：

1揪漩、感知機只要分類都正確算法就停止了旋恼，它得到的決策邊界是不唯一的；那么支持向量機得到的泛化性能比感知機好奄容，你說它決策邊界是唯一的冰更，有什么證據(jù)嗎？

答：當然有啦昂勒，就是書本上的定理 7.1蜀细，你可以回過頭來再看它；

2戈盈、上面的最優(yōu)化問題怎么解奠衔？

答：書本上 7.1.4 節(jié)”學習的對偶算法“就是在講這一部分。這屬于統(tǒng)計學習 3 要素的角度（模型塘娶、策略归斤、方法）中的方法。我們?yōu)榱丝辞濉敝С窒蛄繖C“的全貌刁岸，可以暫時略過脏里，這部分內(nèi)容不好消化，要結(jié)合附錄一起看虹曙，剛開始看的時候會漸漸忘了這個算法到底是在做什么膝宁，跑得原來越遠鸦难，拉不回來了，這是我剛開始看這部分內(nèi)容的狀態(tài)员淫，聰明的你應該比我好。

3击敌、只能解決嚴格線性可分的二分類問題介返，是不是太沒用了。遇到不能線性可分的是不是就沒轍了沃斤，多分類問題咋辦圣蝎？

答：之所以先討論嚴格的情況，是因為線性可分好做衡瓶。其它非線性可分的情況徘公，可以轉(zhuǎn)化成線性可分的情況來做。想一想從一元線性回歸到多元線性回歸哮针，通過構造多項式特征关面，最后也是用線性回歸的算法來做的，道理是一樣的十厢。至于使用二分類問題問題解決多分類問題等太，機器學習中使用的思想有 ”O(jiān)vO“ 與 ”O(jiān)vR“，很多書籍上都有介紹蛮放，在這里就不展開了缩抡。

寫到這里，有一些概念我是沒有提到包颁，因為絕大多數(shù)將支持向量機的書籍都有講瞻想，我羅列一下：支持向量、間隔娩嚼、間隔邊界蘑险、決策邊界（即分離超平面），當然這個時候待锈，你可以去看看函數(shù)間隔漠其、幾何間隔。這些概念其實都是見名知義的竿音，如果你還比較模糊和屎，不妨再翻翻書。

第 2 階段：差一點線性可分的支持向量機

有的時候春瞬，我們會遇到一些離群點柴信，如果要照顧到它們分類的正確性是得不償失的。我們不會”撿了芝麻丟了西瓜“宽气，就是這個道理随常。

理解松弛變量

那么潜沦，此時我們是怎么做的呢？對每一個數(shù)據(jù)引入一個松弛變量绪氛，這個變量對于分類正確且在間隔邊界之外的數(shù)據(jù)而言為 0 唆鸡，如果在間隔邊界之內(nèi)，即使分類正確枣察，也會有一個很小的值争占。

理解這個思想可以對比于邏輯回歸，對于邏輯回歸算法而言序目，不管你分類多正確臂痕，你的損失函數(shù)都會計入一個很小的概率。而此時支持向量機不是：

1猿涨、只要是分類正確的落在兩個間隔邊界之外的握童，認為是絕對安全的，因此不計損失叛赚；

2澡绩、即使分類正確，但是落在兩個間隔邊界之內(nèi)的红伦，我們認為此時的預測有一定風險英古，這個風險就量化為松弛變量的值；

3昙读、分類錯誤的話召调，松弛變量的值就會大于 1 ，錯得越離譜蛮浑，這個值越大唠叛。

Soft Margin 和 SVM 的正則化

1、為了考慮到模型的泛化能力沮稚，我們放棄一些離群點艺沼，于是就有了 soft margin。
2蕴掏、為什么要會引入 Soft Margin 呢障般？因為有可能“支撐向量”是離群點，這樣就會使得我們的 margin 變得非常窄盛杰，于是我們就有下面的數(shù)學表示：
{\rm s.t.}\quad y^{(i)}(w^Tx^{(i)}) \geq 1 - \zeta_i
其中 \zeta_i \geq 0挽荡，這里 \zeta_i 不是一個固定的數(shù)，并且我們不可能讓 \zeta_i 無限大即供，所以定拟，我們在目標函數(shù)上限制
{\rm min}\quad \frac{1}{2}||w||^2 + C\sum_{i=1}^{m} \zeta_{i}\\
C\sum_{i=1}^{m} \zeta_{i} 叫做正則化項，它是 L_1 正則化逗嫡，同樣青自，我們可以定義 L_2 正則株依。

什么是懲罰系數(shù) C

如何理解正則化：當 C 越來越大的時候，我們的目標函數(shù)是求最小值延窜，于是我們就逼迫正則化項應該越來越小恋腕，即容錯空間越來越小，即此時的 Margin 是越來越 hard 的逆瑞。

反之吗坚，當 C 越來越小的時候，正則化項就被忽略呆万，因此容錯空間就可以越來越大，margin 內(nèi)部的點就可以越來越多车份，即朝著 soft 的方向發(fā)展谋减。

scikit-learn 中的 C 就是在這個位置。引入 soft margin 的原因是扫沼，讓 SVM 模型對訓練數(shù)據(jù)集有一定的容錯能力出爹，這樣模型就不會對那些離群點敏感，于是泛化能力就更強了缎除。

C 其實我們并不陌生严就，我們在學習嶺回歸和 LASSO 回歸的時候，知道可以在損失函數(shù)的后面加上一個尾巴器罐，這個尾巴表示了模型的復雜程度梢为，這個尾巴前面有一個系數(shù)，用于平衡損失函數(shù)和模型的復雜度：

C 很大轰坊，說明模型復雜度占據(jù)了損失函數(shù)的主要部分铸董，因此真的”損失“那部分就會淡化了，因此模型會變得簡單肴沫，容易欠擬合粟害；

C 很小，極端情況那就跟沒有一樣颤芬，此時模型容易變得復雜悲幅，容易過擬合。

這個道理在李航《統(tǒng)計學習方法》第 1 章介紹“策略”的部分站蝠，“結(jié)構風險 = 經(jīng)驗風險 + 正則化項”汰具，正則化項又叫懲罰項，叫懲罰還好理解一點沉衣。

這里 C 的作用是一樣的郁副，為了權衡“最大間隔”和“對每一個數(shù)據(jù)引入的松弛變量”這兩件事。如果我們對那個越過邊界的點特別在意豌习，“寧可錯殺三千存谎，不能放過一個”拔疚，這個 C 就要設置得很大，讓這個離群點盡量不越界或者越界的距離短一點既荚。如果我們想要顧大局稚失，犧牲個體，就可以把 C 設置小一點恰聘。

從松弛變量的角度理解 SVM 自帶正則化

引入了松弛變量以后句各，此時“差一點線性可分的支持向量機”所表達的最優(yōu)化問題的數(shù)學表示式就跟“嚴格線性可分的支持向量機”差不多了，結(jié)構上一致晴叨，因此引入了松弛變量的線性支持向量機的問題就可以包括嚴格線性可分的支持向量機問題凿宾，因為其實只要引入的松弛變量都為 0，就是嚴格線性可分的支持向量機兼蕊，兩個問題合二為一了初厚。

還有一點好處，對于支持向量機而言孙技，我們從來不談“支持向量機”的正則化产禾，這其實是在這一節(jié)介紹的“差一點線性可分的支持向量機”自帶的效果。

我們來看此時得到的數(shù)學表達式：

{\rm \min_{w,b,\xi}} \qquad \cfrac{1}{2}||w||^2 + C\sum_{i=1}^N \xi_i\\ {\rm s.t.} \qquad y_i(w \cdot x_i+b) \geq 1 - \xi_i, \quad i = 1, 2, \cdots, N\\ \xi_i \ge0,\quad i = 1, 2, \cdots, N \quad\qquad

目標函數(shù)從形式上看牵啦，前面的 \cfrac{1}{2}||w||^2 就是我們學習過的嶺回歸的表示形式亚情，而后面的 \sum_{i=1}^N \xi_i 是針對所有樣本而言的，\xi_i 是針對每一個樣本在指定的一個距離間隔邊界（注意是間隔邊界哈雏，不是決策邊界）的距離楞件，可以看成是一種損失。目標函數(shù)的形式不就是”損失 + 正則化“的樣子嗎僧著？

這里的松弛變量的值書本上又叫它”合頁損失“履因。

這部分內(nèi)容雖然占據(jù)了一定篇幅，但是很多都是和第 1 階段相同盹愚，很多結(jié)論無非就是在限制條件那里多了個 C栅迄。

第 3 階段：線性不可分的支持向量機

終于到最后了〗耘拢”和線性可分差距太遠的時候“即這里對于”線性不可分的支持向量機“而言毅舆，我們的思路其實很簡單，上面我們也提過愈腾，就是從”一元線性回歸“到”多元線性回歸“的思路憋活，”通過構造特征升維“，”低維空間線性不可分虱黄，到高維空間就有可能線性可分“悦即，李航老師的書上也用例子介紹了這個思路。

直觀理解“低維空間線性不可分，到高維空間就有可能線性可分”

這一小節(jié)雖然一開始就在講核技巧辜梳，整個章節(jié)也幾乎都在介紹核技巧粱甫，但核技巧不是解決線性不可分的支持向量機問題的思想，它是一個具體的作瞄、可以操作的方法茶宵，核技巧是方法層面，不是思想層面宗挥，我們應該首先看到思想層面乌庶，因為它有時候更重要，而不應該被這個技巧契耿、方法層面的東西蒙蔽了雙眼瞒大。

這里舉一個可能不是很恰當?shù)睦樱阂粋€學校來了兩個老師，一個是普通二本師范院校剛剛畢業(yè)的學生 A搪桂，他是來工作的糠赦，一個是名牌大學的本科生 B，他來上課只是為了為考研賺一些生活費锅棕，他們的教學效果和受歡迎程度很可能是 A 更優(yōu)，原因很簡單：A 是來教書的淌山，他選擇了教育行業(yè)是熱愛教學裸燎，經(jīng)過 4 年的專業(yè)訓練和學習，在教學技能和教學態(tài)度上很可能遠遠超過 B泼疑，而 B 有可能根本不喜歡教書德绿，名牌大學畢業(yè)只是他的標簽，他來教書只是為了貼補生活費退渗，他的主要精力放在考研上移稳。所以我們看待問題不能只看到這個問題吸引人的部分，有時要先看看它是用來干什么的会油。

因此我們就可以在高維空間中个粱，使用第 1 階段和第 2 階段介紹的線性可分或者近似線性可分的策略和方法來解決在高維空間線性可分的問題，進而解決在原始低維空間中線性不可分的問題翻翩。核心思想就是構造特征都许，轉(zhuǎn)化。

其實到這里支持向量機的主要框架就介紹完了嫂冻，就這么簡單胶征。那么你要問我“核技巧”被你吃了嗎？不是的桨仿，核技巧只是我們?yōu)榱私鉀Q在高維空間中線性可分問題的時候使用的一個方法睛低，因為它有一定技巧性，還有一點點神奇、神秘的色彩钱雷，是一個可以讓我們偷懶的“捷徑”骂铁，所以我們叫它“核技巧”。

“核技巧”是技巧層面急波，而不是思想層面的東西

上面說了“線性不可分的支持向量機”首先是構造特征从铲，把空間映射到高維空間，那么具體怎么做呢澄暮？

首先“從低維空間到高維空間的映射”一定是非線性映射名段，才有可能把低維空間的超曲面“拉直”，問題來了泣懊，這個映射是什么伸辟？怎么找到這個映射？

其實這個映射找到以后馍刮，我們要在高維空間中做運算信夫，我們要意識到一點：在高維空間中做運算，其實是很消耗資源的卡啰。

單單第一件事情其實就很不好辦了静稻，這個非線性映射是什么，那么多非線性映射匈辱，你怎么找振湾。好在這件事情，偉大的數(shù)學家（計算機科學家）幫我們解決了亡脸。核技巧就幫我們一下子干了這兩件事押搪，核技巧給出了一個具體的樣子，它雖然沒有直接給出非線性映射的樣子浅碾，但其實我們并不關心大州，我們只關心那個在高維空間中進行運算的結(jié)果（具體可以等到理解了對偶問題的算法再來理解），核技巧把它們合二為一垂谢，具體化了厦画，我們剩下要做的只是調(diào)參，如果你的數(shù)據(jù)很干凈滥朱，噪聲很小苛白，你可以設置參數(shù)，使得算法預測非常準確焚虱，這樣即使過擬合购裙，影響也不大，如果你的數(shù)據(jù)噪聲很大鹃栽，就得設置另一套參數(shù)躏率，避免過擬合躯畴，這正是核技巧神奇、神秘的地方薇芝。

“核技巧”把一個抽象的問題具體化蓬抄，簡單化，并且可以且容易操作夯到。在這里還是強調(diào)一下嚷缭，“核技巧”是方法層面，而不是思想層面的東西耍贾。處理非線性可分的問題阅爽，SVM 處理的思路是構造特征，使用樣本在新的高維特征空間中線性可分荐开。

如果我們能夠有一種方法輕松地解決低維空間中的非線性可分問題付翁，或者我們輕松地找到了從低維空間到高維空間的非線性映射，并且在高維空間中進行計算毫不費事晃听，那可能核函數(shù)（核技巧）就不為我們所知了百侧。

這里做一個階段總結(jié)。

1能扒、SVM 是一個有約束的最優(yōu)化問題佣渴；

目標函數(shù)：
\min \frac{1}{2}||w||^2

使得：

\begin{cases} y_i(w\cdot x_i+b)\ge1,& \forall y_i=1\\ y_i(w\cdot x_i+b)\le-1,& \forall y_i=-1 \end{cases}

2、用到的數(shù)學技巧：在感知機模型中初斑，我們采用的是保留分子观话，固定分母；在 SVM 中越平，我們反過來，固定分子灵迫，保留分母秦叛。

3、SVM 涉及到距離問題瀑粥，所以要做特征歸一化挣跋；

4、為了解決非線性可分的問題狞换，我們要升維度（低維空間不能線性可分避咆，高維空間可以線性可分），但是升維度的時候帶來了一個很大的問題修噪，就是計算量大（維度災難）查库，核函數(shù)就幫我們解決了帶來的計算量大的問題，我們可以直接在低維度空間中計算得到升維以后等價的效果黄琼。核函數(shù)的本質(zhì)其實就是為了替換原來的 在高維空間中的計算樊销；

5、基本模型：定義在特征空間上的間隔最大的線性分類器，以獲得更好的泛化能力围苫。

6裤园、研究思路

  • 線性可分支持向量機（硬間隔最大化）；

  • 線性支持向量機（軟間隔最大化）：大概線性可分剂府，丟棄少數(shù)離群點（噪聲點）拧揽；

  • 非線性支持向量機；

  • SVM 是一個判別模型（區(qū)別于先求出聯(lián)合概率分布的生成模型）腺占，可以用于分類淤袜，也可以用于回歸；

  • 支持向量機的損失函數(shù)湾笛，叫合頁（hung）損失饮怯。

7、公式推導

類標記與邏輯回歸和感知機都不一樣：決策函數(shù) >= 0 的時候嚎研，預測類別為 1蓖墅；決策函數(shù) < 0 的時候，預測類別為 -1临扮。

SVM 的優(yōu)點

1论矾、解決小樣本下機器學習問題；

2杆勇、解決非線性問題贪壳；

3、無局部極小值問題（相對于神經(jīng)網(wǎng)絡等算法）蚜退；

4闰靴、可以很好的處理高維數(shù)據(jù)集；

5钻注、泛化能力比較強蚂且；

6、模型依賴的支持向量比較少幅恋，說明它們都是非常精致的模型杏死，消耗的內(nèi)存少；

7捆交、一旦模型訓練完成淑翼，預測階段的速度非常快品追；

8玄括、模型只受邊界線附近的點的影響，因此它們對于高維數(shù)據(jù)的學習效果非常好——即使訓練比樣本數(shù)量還要高的數(shù)據(jù)也沒有問題肉瓦，這是其他算法難以企及的惠豺；

9银还、核技巧能夠適用于不同類型的數(shù)據(jù)。

SVM 的缺點

1洁墙、對于核函數(shù)的高維映射解釋力不強蛹疯，尤其是徑向基函數(shù)；

2热监、對缺失數(shù)據(jù)敏感捺弦；

3、隨著樣本數(shù)量的增加孝扛，時間復雜度提升列吼，計算成本高；

4苦始、訓練的效果依賴于 C 的選擇寞钥，須要交叉驗證來搜索，數(shù)據(jù)集大的時候陌选，計算量也很大理郑；

5、進行概率解釋比較困難咨油，但 scikit-learn 支持計算概率您炉。

SVM 如何處理多分類問題

在機器學習的分類算法中，有些算法天生支持多分類問題役电，例如 k-近鄰算法赚爵、樸素貝葉斯問題、決策樹算法應用于分類法瑟。而有些分類算法最初是解決二分類問題的冀膝，要適用于多分類問題，需要一定的策略霎挟，其中窝剖，主要的策略有以下兩種：

OVR（one vs rest）

假設我們的 target 有三個類 A、B氓扛、C，我們拿到一個新樣本论笔，這個時候我們做的事情是：

1采郎、A 類數(shù)據(jù)原封不動，將 B 類和 C 類數(shù)據(jù)歸為一類狂魔，即非 A 類蒜埋，針對 A 類和非 A 類數(shù)據(jù)，訓練一個分類器最楷；

2整份、B 類數(shù)據(jù)原封不動待错，將 A 類和 C 類數(shù)據(jù)歸為一類，即非 B 類烈评，針對 B 類和非 B 類數(shù)據(jù)逞力，訓練一個分類器诉稍；

3、C 類數(shù)據(jù)原封不動，將 A 類和 B 類數(shù)據(jù)歸為一類蕊唐，即非 C 類，針對 C 類和非 C 類數(shù)據(jù)芹彬，訓練一個分類器掸读。

一共得到 3 個二分類器，將測試數(shù)據(jù)使用這 3 個二分類器進行分類投票否彩，票數(shù)最多的那個類就作為這個測試數(shù)據(jù)最終的分類疯攒。

可以看出，如果是 k 分類問題列荔，OVR 策略就會訓練出 k 個二分類器敬尺。

OVO（one vs one）

假設我們的 target 有三個類 A、B肌毅、C筷转，我們拿到一個新樣本，這個時候我們做的事情是：

1悬而、只拿出 A 類數(shù)據(jù)和 B 類數(shù)據(jù)呜舒，訓練一個分類器；

2笨奠、只拿出 A 類數(shù)據(jù)和 C 類數(shù)據(jù)袭蝗，訓練一個分類器；

3般婆、只拿出 B 類數(shù)據(jù)和 C 類數(shù)據(jù)到腥，訓練一個分類器。

一共得到 3 個二分類器蔚袍，將測試數(shù)據(jù)使用這 3 個二分類器進行分類投票乡范，票數(shù)最多的那個類就作為這個測試數(shù)據(jù)最終的分類。

可以看出啤咽，如果是 k 分類問題晋辆，OVR 策略就會訓練出 C_k^2 個二分類器，因此 OVO 策略的時間復雜度更高宇整，但是更準確瓶佳，因為，我們每次都是拿真實的兩個類去訓練鳞青，而不像 OVR 那樣將類別的意義做了一些修改霸饲。

參考資料

[1] 李航. 統(tǒng)計學習方法（第 2 版）第 7 章“支持向量機”. 北京：清華大學出版社为朋，2019.

[2] 周志華. 機器學習（第 6 章“支持向量機”）. 北京：清華大學出版社.

（本節(jié)完）

以下為草稿，我自己留著備用厚脉，讀者可以忽略习寸，歡迎大家批評指正。

后面還沒有介紹的內(nèi)容有：

  • 如何求解第 1 部分提到的數(shù)學化以后的帶約束的最優(yōu)化問題器仗；
  • 拉格朗日乘子法
  • 拉格朗日對偶問題
  • KKT 條件
  • 核函數(shù)

當然融涣，絕大部分介紹 SVM 的書籍在這些知識上已經(jīng)講解得很正確了，我只會談一些直觀理解和應用的部分精钮。

  • 僅僅使用一部分支持向量來做超平面的決策威鹿，無需依賴全部數(shù)據(jù)，效率高轨香；
  • SVM 模型的目標函數(shù)計算了距離忽你，距離是對特征縮放敏感的，這一點類似于在 k 近鄰算法中計算距離臂容。
  • SVM 用于回歸科雳；
  • SVM 如何用于異常檢測。
  • 軟間隔最大化：那些參數(shù)和是不是支持向量機的關系：利用對偶互補條件脓杉，介紹合頁損失
  • 落在軟間隔之內(nèi)的樣本也是支持向量

求解：拉格朗日乘子法

應用：最大熵模型糟秘，SVM，線性判別分析球散，主成分分析

參考資料

1尿赚、劉建平的文章

支持向量機原理(一) 線性支持向量機
https://www.cnblogs.com/pinard/p/6097604.html

scikit-learn 支持向量機算法庫使用小結(jié)
https://www.cnblogs.com/pinard/p/6117515.html

支持向量機高斯核調(diào)參小結(jié)
https://www.cnblogs.com/pinard/p/6126077.html

2、https://www.bookstack.cn/read/hands_on_Ml_with_Sklearn_and_TF/docs-5.%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA.md

3蕉堰、拉格朗日對偶性：
http://www.hankcs.com/ml/lagrange-duality.html

4凌净、Python3《機器學習實戰(zhàn)》學習筆記（八）：支持向量機原理篇之手撕線性SVM

5、SVM 核函數(shù)的理解：https://blog.csdn.net/u012328476/article/details/52382593

6屋讶、關于核函數(shù)的參考資料：https://www.jiqizhixin.com/articles/2017-10-08

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末冰寻，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子皿渗，更是在濱河造成了極大的恐慌斩芭，老刑警劉巖，帶你破解...
    沈念sama閱讀 218,682評論 6贊 507
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件乐疆，死亡現(xiàn)場離奇詭異划乖，居然都是意外死亡，警方通過查閱死者的電腦和手機诀拭，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,277評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門迁筛，熙熙樓的掌柜王于貴愁眉苦臉地迎上來煤蚌，“玉大人耕挨，你說我怎么就攤上這事细卧。” “怎么了筒占？”我有些...
    開封第一講書人閱讀 165,083評論 0贊 355
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵贪庙，是天一觀的道長。 經(jīng)常有香客問我翰苫，道長止邮，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,763評論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任奏窑，我火速辦了婚禮导披，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘埃唯。我一直安慰自己撩匕，他們只是感情好，可當我...
    茶點故事閱讀 67,785評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布墨叛。 她就那樣靜靜地躺著止毕，像睡著了一般。 火紅的嫁衣襯著肌膚如雪漠趁。 梳的紋絲不亂的頭發(fā)上扁凛，一...
    開封第一講書人閱讀 51,624評論 1贊 305
  • 城市分裂傳說
    那天，我揣著相機與錄音闯传，去河邊找鬼谨朝。 笑死，一個胖子當著我的面吹牛丸边，可吹牛的內(nèi)容都是我干的叠必。 我是一名探鬼主播，決...
    沈念sama閱讀 40,358評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼妹窖，長吁一口氣：“原來是場噩夢啊……” “哼纬朝！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起骄呼，我...
    開封第一講書人閱讀 39,261評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤共苛，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后蜓萄，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體隅茎，經(jīng)...
    沈念sama閱讀 45,722評論 1贊 315
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,900評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年嫉沽，在試婚紗的時候發(fā)現(xiàn)自己被綠了辟犀。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,030評論 1贊 350
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡绸硕，死狀恐怖堂竟，靈堂內(nèi)的尸體忽然破棺而出魂毁，到底是詐尸還是另有隱情，我是刑警寧澤出嘹，帶...
    沈念sama閱讀 35,737評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布席楚，位于F島的核電站，受9級特大地震影響税稼，放射性物質(zhì)發(fā)生泄漏烦秩。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,360評論 3贊 330
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一郎仆、第九天 我趴在偏房一處隱蔽的房頂上張望只祠。 院中可真熱鬧，春花似錦扰肌、人聲如沸铆农。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,941評論 0贊 22
  • 一樁弒父案狡耻，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽墩剖。三九已至，卻和暖如春夷狰，著一層夾襖步出監(jiān)牢的瞬間岭皂，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,057評論 1贊 270
  • 情欲美人皮
    我被黑心中介騙來泰國打工沼头， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留爷绘，地道東北人。 一個月前我還...
    沈念sama閱讀 48,237評論 3贊 371
  • 代替公主和親
    正文 我出身青樓进倍，卻偏偏與公主長得像土至，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子猾昆，可洞房花燭夜當晚...
    茶點故事閱讀 44,976評論 2贊 355

推薦閱讀更多精彩內(nèi)容