通俗易懂的解釋支持向量機(jī)

A Brief Introduction To Support Vector Machine

作者：?Wang Shuyang
?????a bachelor's degree candidate.

導(dǎo) 語：相信有很多剛?cè)肟訖C(jī)器學(xué)習(xí)的小伙伴會(huì)和我一樣糯累，感覺SVM是一道勸退的坎兒枉氮，而消除恐懼的最好辦法就是微笑著面對(duì)它，本篇文章中我會(huì)用樸實(shí)的“人話”幫助大家邁過這道坎！

本文成文思路如下：
1.SVM原始模型構(gòu)建
2.對(duì)偶形式的推導(dǎo)
3.求解的方法
4.軟間隔SVM及核方法
5.SVM優(yōu)缺點(diǎn)及應(yīng)用

本文旨在幫助新手理解算法狰闪，為了便于理解部分表述可能不夠準(zhǔn)確辛润，懇請(qǐng)批評(píng)指正。

首先崎场，讓我們來對(duì)SVM產(chǎn)生一個(gè)直觀的認(rèn)識(shí)：支持向量機(jī)(Support Vector Machine,SVM)佩耳，二類分類器，它最終能告訴你一個(gè)東西是屬于A還是屬于B谭跨。在由樣本點(diǎn)構(gòu)成的向量空間內(nèi)干厚，SVM通過找到一個(gè)可以將兩類數(shù)據(jù)正確分隔在兩側(cè)的劃分超平面，達(dá)到對(duì)數(shù)據(jù)分類及預(yù)測(cè)的效果螃宙。而這個(gè)超平面是通過支持向量確定的蛮瞄，機(jī)的意思呢就是算法，故支持向量機(jī)就是通過支持向量確定劃分超平面谆扎，從而做到分類及預(yù)測(cè)的算法挂捅。

支持向量機(jī)

-什么是超平面？
-超平面是指 n 維線性空間中維度為 n-1 的子空間堂湖。它可以把線性空間分割成不相交的兩部分闲先。比如二維空間中，一條直線是一維的无蜂，它把平面分成了兩塊伺糠；三維空間中，一個(gè)平面是二維的酱讶，它把空間分成了兩塊退盯。
在樣本空間中，劃分超平面可通過線性方程 $w^Tx+b=0$ 來描述，其中 $w=(w_1,w_2,...,w_d)$ 為法向量渊迁，決定超平面的方向慰照； $b$ 為位移項(xiàng)，決定超平面與原點(diǎn)之間的距離琉朽。一個(gè)劃分超平面就由法向量 $w$ 和位移 $b$ 確定毒租。

-那什么又是支持向量？
-且聽我慢慢道來箱叁。

一墅垮、SVM原始模型構(gòu)建

1.1 線性SVM模型

1.1.1 線性可分

SVM由線性分類開始，所以我們首先來了解一下什么是線性可分耕漱。簡單來說算色，在二維空間上，兩類點(diǎn)能夠被一條直線完全分開則叫做線性可分螟够。如下圖左邊是線性不可分的灾梦，而右邊即為線性可分。

圖1 線性可分

數(shù)學(xué)上我們可以表述為：對(duì)于 n 維歐氏空間中的兩個(gè)點(diǎn)集 $D_0$ 和 $D_1$ 妓笙，若存在 n 維向量 $w$ 和實(shí)數(shù) $b$ 若河，使得： $\forall x_i\in D_0$ 滿足 $w^Tx_i+b>0$ ，而 $\forall x_j\in D_1$ 滿足 $w^Tx_j+b<0$ 寞宫，則稱 $D_0$ 和 $D_1$ 線性可分萧福。

1.1.2 支持向量與最大化間隔

給定線性可分的訓(xùn)練樣本集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}$ , $y_i\in\{-1,1 \}$ ，線性分類器將基于訓(xùn)練樣本 $T$ 在二維空間中找到一個(gè)超平面來正確劃分兩類樣本辈赋。顯然鲫忍，滿足條件的超平面有很多，而我們旨在找到魯棒性最好的炭庙。

“魯棒”是“Robust”的音譯饲窿，也就是健壯的意思。由于訓(xùn)練樣本集的局限性或噪聲因素焕蹄，訓(xùn)練集之外的樣本可能會(huì)更接近兩個(gè)類的分隔界，這將導(dǎo)致很多劃分超平面出現(xiàn)錯(cuò)誤阀溶。所以我們想要找到與兩類數(shù)據(jù)間隔最大的超平面腻脏，使之對(duì)訓(xùn)練集之外的數(shù)據(jù)或噪聲有最大的“容忍”能力。

首先银锻，我們要明確該模型中“距離”的概念永品。由于劃分超平面并不確定，所以我們需要比較同一個(gè)點(diǎn)到不同超平面的距離击纬，為了使之具有可比性鼎姐，我們使用歐式幾何距離。

相信大家不陌生的是，一個(gè)二維空間點(diǎn) $p=(x_p,y_p)$ 到直線 $Ax+By+C=0$ 的距離公式為： $r=\frac{|Ax_p+By_p+C|}{\sqrt[]{{A^2+B^2}}}$

而擴(kuò)展到 n 維空間后炕桨，點(diǎn) $x=(x_1,x_2,...,x_n)$ 到超平面 $w^Tx+b=0$ 的距離公式為： $r=\frac{|w^Tx+b|}{||w||}$ ,其中 $||w||=\sqrt[]{w_1^2+w_2^2+...+w_n^2}$

既然我們要找出與兩類數(shù)據(jù)間隔最大的劃分超平面饭尝，很直觀地就會(huì)考慮從兩類數(shù)據(jù)最靠近的地方下手，因?yàn)樗鼈兏髯宰钸吘壩恢玫狞c(diǎn)才有可能成為最靠近劃分超平面的那幾個(gè)點(diǎn)献宫，而其他點(diǎn)對(duì)確定超平面的最終位置是起不了作用的钥平，所以我們認(rèn)為是這些邊緣點(diǎn)支持了超平面的確立。而在數(shù)學(xué)里點(diǎn)又可以叫向量姊途，比如二維點(diǎn) (x, y) 就可以看成是一個(gè)二維向量涉瘾，同理 n 維點(diǎn)就是一個(gè) n 維向量，所以我們將這些有用的邊緣點(diǎn)稱為“支持向量”(support vector)捷兰。

圖2 支持向量

如圖2所示立叛，標(biāo)紅的點(diǎn)就是支持向量，它們確定出了兩條虛線贡茅，我們稱之為“支撐超平面”秘蛇，并將它們之間的距離稱為“間隔”(margin)，用希臘字母 $\gamma$ 表示友扰，而它們“正中間”的位置就是我們要找的最優(yōu)劃分超平面的位置彤叉。顯然，間隔越大我們的劃分超平面魯棒性就越好村怪。所以在開始推導(dǎo)SVM的原始公式之前秽浇，請(qǐng)?jiān)谀X海里跟我默念三遍SVM的核心思想 —— “?最大化間隔！”

1.2 SVM原始公式導(dǎo)出

假設(shè)超平面 $(w,b)$ 能將訓(xùn)練樣本 $T$ 正確分類甚负，那么任一數(shù)據(jù)點(diǎn) $(x_i,y_i)$ 到該超平面的距離為： $r_i=\frac{|w^T{x_i}+b|}{||w||}$ 顯然 $||w||>0$ 柬焕，否則超平面變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=b%3D0" alt="b=0" mathimg="1">，失去意義梭域。

考慮到此式中含有絕對(duì)值會(huì)對(duì)后續(xù)數(shù)學(xué)計(jì)算帶來不便斑举，所以我們利用數(shù)據(jù)點(diǎn)自帶的標(biāo)簽 $y_i$ 去絕對(duì)值。結(jié)合1.1.1中講過的線性可分的數(shù)學(xué)定義可知：
$\begin{cases}{w^Tx_i+b>0病涨，\ \ \mathrm{if}\ \; y_i>0}\\{w^Tx_i+b<0富玷，\ \ \mathrm{if}\ \; y_i<0} \end{cases}$

所以任一數(shù)據(jù)點(diǎn)到超平面的距離可表示為： $r_i=\frac{y_i(w^T{x_i}+b)}{||w||}>0$ 則最接近超平面的距離為： $d=\min \limits_i\frac{y_i(w^Tx_i+b)}{||w||}$ 調(diào)整平面位置，找到最大距離： $d^*=\max\limits_{w,b}\min\limits_i \frac{y_i(w^Tx_i+b)}{||w||}$ 則最大間隔為： $\gamma=2d^*=2\max\limits_{w,b}\min\limits_i \frac{y_i(w^Tx_i+b)}{||w||}$ 至此既穆，我們已經(jīng)將問題用數(shù)學(xué)語言表述出來了赎懦，即要找到一組使得 $\gamma$ 最大的 $(w^*,b^*)$ 確立最優(yōu)劃分超平面，但形式上任較為復(fù)雜幻工。

我們知道励两，對(duì)于二維空間中的一條直線 $Ax+By+C=0$ ，等比例地放縮 $A囊颅、B当悔、C$ 是不影響它的位置的傅瞻，比如 $kAx+kBy+kC=0$ 仍代表同一條直線。

擴(kuò)展到 n 維空間中盲憎，等比例地放縮 $w嗅骄、b$ 也是不影響解平面 $w^Tx+b=0$ 位置的。又已知 $y_i(w^Tx_i+b)>0$ （超平面外一點(diǎn)與之距離大于 $0$ 得出）焙畔，所以我們不妨令 $\gamma$ 表達(dá)式中的 $\min\limits_iy_i(w^Tx_i+b)=1$ 掸读，則問題簡化為，求： $\max\limits_{w,b}{\frac{2}{||w||}}$ $\mathrm{s.t.}\quad y_i(w^Tx_i+b)\ge1,\ i=1,2,...,m$ 顯然宏多，最大化 $\frac{1}{||w||}$ 等價(jià)于最小化 ${||w||}^2$ 儿惫，為了便于求導(dǎo)，我們繼續(xù)將問題轉(zhuǎn)化為伸但，求： $\min\limits_{w,b}\frac{1}{2} {{||w||}^2}$ $\mathrm{s.t.}\quad y_i(w^Tx_i+b)\ge1,\ i=1,2,...,m$ 至此肾请，我們便得到了SVM的基本型。

1.3 算法小結(jié)

介紹了這么多更胖，但構(gòu)建出來的模型到底能不能用呢铛铁？接下來，我們就從理論上驗(yàn)證它的可行性却妨。

1.3.1 SVM最大間隔劃分超平面的存在唯一性

定理：若訓(xùn)練數(shù)據(jù)集 $T$ 線性可分饵逐，則可將 $T$ 中的樣本點(diǎn)完全正確分開的最大間隔劃分超平面存在且唯一。

證明：
(1)存在性
由于訓(xùn)練數(shù)據(jù)集線性可分彪标，又目標(biāo)函數(shù)存在下界倍权，所以必存在最優(yōu)解，由此得知最大間隔劃分超平面的存在性捞烟。
(2)唯一性
首先證明最優(yōu)解中 $w^*$ 的唯一性薄声。假設(shè)存在兩個(gè)最優(yōu)解 $(w_1^*,b_1^*)$ 和 $(w_2^*,b_2^*)$ ，由目標(biāo)函數(shù)的形式可知必有 $||w_1^*||=||w_2^*||=c$ 题画，其中 $c$ 是一個(gè)常數(shù)默辨。令 $w=\frac{{w_1^*+w_2^*}}{2},b=\frac{b_1^*+b_2^*}{2}$ ，則 $(w,b)$ 必然也是一個(gè)可行解苍息，試想兩個(gè)可正確劃分樣本點(diǎn)的超平面中間夾的一個(gè)超平面必然也可以正確劃分樣本點(diǎn)缩幸。但由于 $(w,b)$ 不一定是最優(yōu)解，則有 $c\le||w||\le\frac{1}{2} ||w_1^*||+\frac{1}{2} ||w_2^*||=c$ (中間那個(gè)“ $\le$ ”關(guān)系由 “三角形兩邊之和大于第三邊” 拓展到 n 維得到)竞思。
由上式可得桌粉， $||w||=\frac{1}{2}||w_1^*||+\frac{1}{2}||w_2^*||$ ，從而有 $w_1^*={\lambda}w_2^*$ 衙四， $|\lambda|=1$ （想象若強(qiáng)行令三角形兩邊之和等于第三邊，則三條線段將會(huì)共線）患亿。若 $\lambda=-1$ ,則 $w=0$ 传蹈，與 $(w,b)$ 是可行解相矛盾押逼；因此必有 $\lambda=1$ ，則 $w_1^*=w_2^*$ 惦界， $w^*$ 的唯一性得證挑格。
接下來證明 $b^*$ 的唯一性。假設(shè)存在兩個(gè)最優(yōu)解 $(w^*,b_1^*)$ 和 $(w^*,b_2^*)$ 沾歪，不妨設(shè) $x_1'$ 和 $x_2'$ 對(duì)應(yīng)的 $y$ 值都為 $1$ 漂彤，且它們分別是兩個(gè)最優(yōu)解的支撐超平面上的點(diǎn)，滿足與自己對(duì)應(yīng)的劃分超平面距離為 $\frac{1}{||w||}$ 灾搏，即滿足 $\begin{cases}w^*x_1'+b_1^*=1\\ w^{*}x_2'+b_2^*=1\end{cases}$ 同時(shí)與另一個(gè)劃分超平面距離大于等于 $\frac{1}{||w||}$ 挫望，即 $\begin{cases}w^*x_2'+b_1^*\ge1\\{w^{*}x_1'+b_2^*\ge1} \end{cases}$ 整理得出 ${\begin{cases}w^*x_2'+b_1^*\ge{1}=w^*x_1'+b_1^*\\{w^{*}x_1'+b_2^*\ge{1}=w^*x_2'+b_2^*}\end{cases}} \Rightarrow{\begin{cases}w^*x_2'\ge{w^*x_1'}\\{w^*x_1'\ge{w^*x_2'}}\end{cases}}$ 所以 $w^*x_2'={w^*x_1'}$ 帶入第一對(duì)等式方程即可得 $b_1^*=b_2^*$ ，則 $b^*$ 的唯一性得證狂窑。
至此媳板，我們得知SVM基本型的最優(yōu)解存在且唯一。

1.3.2 小結(jié)

線性可分支持向量機(jī)——最大間隔法（maximum margin method）

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}$ ,
??????其中 $x_i\in R^n$ , $y_i\in\{-1,1 \}$ , $i=1,2,...,m$ 泉哈；
輸出：最大間隔劃分超平面和分類決策函數(shù)蛉幸；

（1）構(gòu)造并求解約束最優(yōu)化問題： $\min\limits_{w,b}\frac{1}{2} {{||w||}^2}$ $\mathrm{s.t.}\quad y_i(w^Tx_i+b)-1\ge0,\ i=1,2,...,m$ ????求得最優(yōu)解 $w^*,b^*$ ;
（2）由此得到劃分超平面： $w^{*T}x+b^*=0$ ????分類決策函數(shù)： $f(x)=\mathrm{sign}(w^{*T}x+b^*)$

二、對(duì)偶形式的推導(dǎo)

首先順帶一提丛晦，上面的基本型是一個(gè)凸二次規(guī)劃問題奕纫，可以直接用現(xiàn)成的優(yōu)化計(jì)算包求解。但若利用“對(duì)偶問題”來求解會(huì)更高效烫沙，所以我們來推導(dǎo)SVM的對(duì)偶形式匹层。

-什么是凸優(yōu)化問題？
-直觀來說就是在定義于凸集中的凸函數(shù)上求最小值斧吐。但需要注意的是又固，國內(nèi)關(guān)于函數(shù)凹凸性的定義和國外是相反的，這里的凸函數(shù)是指開口向上的煤率。由凸集和凸函數(shù)的定義可得出仰冠，凸優(yōu)化問題具有一個(gè)極好的性質(zhì)，即局部最優(yōu)值必定是全局最優(yōu)值蝶糯，因?yàn)樗还苁蔷植窟€是全局都只有那一個(gè)最優(yōu)值洋只。（實(shí)際上這個(gè)性質(zhì)叫做強(qiáng)對(duì)偶性，且需滿足一定的條件才能具備昼捍，我這里為了方便理解講得比較牽強(qiáng)识虚，想具體了解的可點(diǎn)開鏈接）
-什么是二次規(guī)劃問題？
-如果一個(gè)問題的目標(biāo)函數(shù)是變量的二次函數(shù)妒茬，約束條件是變量的線性函數(shù)担锤，我們將其稱為二次規(guī)劃問題。

2.1 拉格朗日函數(shù)

拉格朗日函數(shù)是拉格朗日乘子法的核心組成部分乍钻，此法思想為：將有約束優(yōu)化問題從形式上轉(zhuǎn)化為等價(jià)的無約束優(yōu)化問題肛循。（建議對(duì)此法陌生的同學(xué)進(jìn)去看看圖文并茂的講解）

優(yōu)化問題存在很多形式铭腕，比如目標(biāo)函數(shù)有求最大值的，也有求最小值的多糠；約束條件有用大于式表示的累舷，也有用小于式的。而上面說到凸優(yōu)化問題具有“局部最優(yōu)值必定是全局最優(yōu)值”這一良好性質(zhì)夹孔，所以我們可以通過移項(xiàng)將SVM基本型寫成凸優(yōu)化問題的標(biāo)準(zhǔn)形式： $\begin{array}{lcl}\, \min\limits_x\quad \,\, f\; (x)\,,\ x \in R^{\, n} \\ \,\;\mathrm{s.t.} \quad\,\; g_i(x)\le0,{\ } i=1,2,..., p \\ \qquad \quad \,\, h_j(x)=0,\ j=1,2,...,q\end{array}$ SVM原始形式： $\begin{array}{lcl}\,\,\min \limits_{w,b} \ \ \,\, \frac{1}{2}{||w||}^2 \\ \ \ \,\mathrm{s.t.}\quad y_i(w^Tx_i+b)-1\ge 0,\ i=1,2,...,m \end{array}$ 只含有不等式約束被盈，將其改寫成： $\begin{array}{lcl} \ \min \limits_{w,b} \ \ \,\, \frac{1} {2}{||w||}^2 \\ \ \ \,\mathrm{s.t.}\quad 1-y_i(w^Tx_i+b) \le 0,\ i=1,2,...,m \end{array}$ 則其拉格朗日函數(shù)為： $\begin{align}&\mathcal{L}(w,b,\alpha)={ \frac{1}{2}}{||w||}^2 + {\sum_{i=1}^{m}\alpha_i[1-y_i(w^Tx_i+b)]} \\&\;\mathrm{s.t.}\quad \alpha_i\ge0,\ i=1,2,...,m \end{align}$ 接下來到了關(guān)鍵的一步，所以我們需要再明確一遍搭伤，將問題改寫成拉格朗日函數(shù)僅僅只是從形式上改變它只怎，而實(shí)質(zhì)上必須是等價(jià)的。那么接下來我要說明以下兩個(gè)問題是等價(jià)的：
① 求 ${\frac{1}{2}} {||w||}^2$ 闷畸，在 $1-y_i(w^Tx_i+b)\le0,\ i=1,2,...,m$ 這個(gè)條件下尝盼；
② 求 $\max\limits_{\alpha}\mathcal{L}(w,b,\alpha)$ ，在 $\alpha_i\ge0,\ i=1,2,...,m$ 這個(gè)條件下佑菩；

從問題②入手盾沫，當(dāng)它滿足自身約束條件時(shí)，拉格朗日函數(shù) $\mathcal{L}(w,b,\alpha)$ 表達(dá)式中的累加項(xiàng)內(nèi)容為非負(fù)常數(shù) $\alpha_i$ 和 $[1-y_i(w^Tx_i+b)]$ 的乘積殿漠，那么欲求其最大值必須滿足 $[1-y_i(w^Tx_i+b)]\le0$ 赴精，否則調(diào)整 $\alpha_i$ 可以達(dá)到無窮大，失去意義绞幌，所以我們發(fā)現(xiàn)問題②是自帶問題①的約束條件的（這里希望讀者可以從中體會(huì)原始規(guī)定不等式約束的拉格朗日乘子 $\alpha_i\ge0$ 的巧妙)蕾哟；
接下來我們會(huì)注意到, $\begin{array}\ \sum_{i=1}^{m}\alpha_i[1-y_i(w^Tx_i+b)] \end{array}$ 作為一個(gè)非正項(xiàng)，其最大值就是 $0$ 莲蜘，所以求 $\max\mathcal{L}(w,b,\alpha)$ 的值就是求 ${\frac{1}{2}} {||w||}^2$ 的值谭确。至此，我們發(fā)現(xiàn)問題②是與問題①等價(jià)的票渠。
所以我們可以將原問題做如下轉(zhuǎn)變： $\begin{array}{lcl} \ \min \limits_{w,b} \ \ \;\; {\frac{1}{2}}{||w||}^2 \\ \ \ \, \mathrm{s.t.}\quad \ 1-y_i(w^Tx_i+b)\le0,\ i=1,2,..., m\end{array}$ $\Big\Downarrow$ $\begin{array}{lcl}\min\limits_{w,b} \max\limits_{\alpha}\ \ \mathcal{L}(w,b,\alpha) \\\,\mathrm{s.t.}\quad \ \alpha_i\ge0,\ i=1,2,...,m\end{array}$

這時(shí)我們?cè)儆蒙贤箖?yōu)化問題的強(qiáng)對(duì)偶性逐哈，即不管局部還是全局都只有同一個(gè)最優(yōu)解，可將極小極大的求解順序換成求極大極小以便于運(yùn)算：

$\begin{array}{lcl} \max\limits_{\alpha}\min\limits_{w,b}\ \ \mathcal{L}(w,b,\alpha) \\ \,\mathrm{s.t.}\quad\ \, \alpha_i\ge0,\ i=1,2,...,m \end{array}$

2.2 KKT條件

前面點(diǎn)開了朗格朗日乘子法這個(gè)鏈接的同學(xué)可能會(huì)發(fā)現(xiàn)问顷，其中介紹的是僅含有等式約束的優(yōu)化問題昂秃。實(shí)際上此法的原始形式中就只包含等式約束，而為了將其泛化到可求帶有不等式約束的優(yōu)化問題杜窄，我們引入KKT條件肠骆。

2.2.1 不等式約束

首先來看不等式約束優(yōu)化問題最簡單的形式：
$\begin{array}{lcl} \min\limits_x \;\; \, f(x)\,,\ x \in R^{\, n} \\ \, \mathrm{s.t.}\quad g(x)\le0 \end{array}$ 其對(duì)應(yīng)的拉格朗日函數(shù)為： $\mathcal{L}(x,\alpha)=f(x)+\alpha g(x)\,,\ \alpha \ge0$ 我們利用圖形來對(duì)其產(chǎn)生一個(gè)直觀的認(rèn)識(shí)：

圖3 拉格朗日函數(shù)

圖中畫出了目標(biāo)函數(shù) $f(x)$ 的等高線和約束區(qū)域 $g(x)$ ，我們的可行解（相當(dāng)于局部最優(yōu)解塞耕，在凸優(yōu)化中即必為最優(yōu)解）需落在約束區(qū)域內(nèi)蚀腿，且最接近 $f(x)$ 的 “中心”，即無約束解扫外。至于無約束解和約束區(qū)域的相對(duì)位置唯咬，有以下兩種可能：

①無約束解落在約束區(qū)域內(nèi)

圖4 無約束解落在約束區(qū)域內(nèi)

此時(shí)纱注，可行解 $x$ 在 $g(x)<0$ 內(nèi)取到無約束解，必然滿足 $g(x)\le0$ 胆胰，相當(dāng)于失去這一約束，即 $\mathcal{L}(x,\alpha)$ 中的拉格朗日乘子 $\alpha$ 取為 $0$ 刻获。

②無約束解落在約束區(qū)域外

圖5 無約束解落在約束區(qū)域外

此時(shí)蜀涨，可行解 $x$ 必然落在約束區(qū)域的邊界上岸蜗，即滿足 $g(x)=0$ 勒庄。至此我們可以得到一個(gè)重要的結(jié)論（記為“結(jié)論 $*$ ”），即無論哪種情況下都有： $\alpha \,g(x)=0$ 接著繼續(xù)考慮可行解 $x$ 落在邊界上的位置熊杨，為了盡量靠近無約束解沐兵，直觀上我們就可以看出别垮，必然要取無約束解與約束區(qū)域中心的連線交于邊界上的那一點(diǎn)。從函數(shù)梯度方面來考慮的話扎谎，目標(biāo)函數(shù)的負(fù)梯度方向（下圖中藍(lán)色小箭頭 $\color{blue}\rightarrow$ ）應(yīng)遠(yuǎn)離約束區(qū)域朝向無約束解碳想，即我們要找到目標(biāo)函數(shù)的負(fù)梯度方向與約束函數(shù)的梯度方向（ $\color{red}\rightarrow$ ）相同的那一點(diǎn)： $-\nabla_xf(x)=\alpha\,\nabla_xg(x),\ \ \alpha>0$ 也即： $\nabla_x\mathcal{L}(x,\alpha)=\nabla_xf(x)+\alpha\,\nabla_xg(x)=0,\ \ \alpha>0$

圖6 邊界上可行解的位置

這里我想舉一個(gè)例子幫助大家理解：假設(shè)山坡上有一只被圈養(yǎng)的小羊，它想去山頂看看毁靶，但不幸的是有一圈柵欄限制了它的活動(dòng)范圍胧奔。所以它只能沿著柵欄走到盡可能靠近山頂?shù)奈恢茫缓笸巾斶氵銍@氣预吆。這里的山頂便是目標(biāo)函數(shù)的無約束解龙填，柵欄便是約束函數(shù)的邊界，此時(shí)羊頭的朝向一定是指向山頂?shù)墓詹妫遗c柵欄的梯度同向岩遗。

-什么是梯度？
-一個(gè)向量凤瘦，指向函數(shù)值上升最快的方向宿礁。假如你是那只小羊，在山坡上朝四面八方走都可以廷粒，而每個(gè)方向你都可以判斷出山坡的陡峭程度窘拯，即各個(gè)方向上你都可以求得方向?qū)?shù)，其中值最大的那個(gè)叫做梯度坝茎。補(bǔ)充一句涤姊，當(dāng)偏導(dǎo)數(shù)連續(xù)時(shí)才有梯度的存在。
關(guān)于梯度嗤放，還有一個(gè)很直觀的例子思喊，想象一滴水沿著光滑的玻璃往下流動(dòng)，其運(yùn)動(dòng)軌跡的反方向即是玻璃表面的梯度方向次酌。

2.2.2 形式化的KKT條件

回到凸優(yōu)化問題的標(biāo)準(zhǔn)形式： $\begin{array}{lcl}\, \min\limits_x\quad\; \, f\; (x)\,,\ x \in R^{\, n} \\ \,\;\mathrm{s.t.} \quad\ \; g_i(x)\le0,{\ } i=1,2,..., p \\ \qquad \quad \,\, h_j(x)=0,\ j=1,2,...,q\end{array}$ 列出拉格朗日函數(shù)得到無約束優(yōu)化問題： $\mathcal{L}(x,\alpha,\beta)=f(x)+\sum_{i=1}^{p}\alpha_ig_i(x)+\sum_{j=1}^{q}\beta_jh_j(x)$ 結(jié)合之前的分析恨课，我們將可行解 $x$ 需滿足的條件匯總舆乔，即為“KKT條件”（Karush-Kuhn-Tucker Conditions）：

$\qquad \quad\ \,\;\,\nabla_x\mathcal{L}(x,\alpha,\beta)=0$ ????????????①
$\qquad \qquad \qquad \quad\ \ \ \ \ \alpha_i \ge0,\;{\ } i=1,2,..., p$ ??????②
$\qquad \qquad \qquad\ \;\;\,\, g_i(x)\le0,\ {\ } i=1,2,..., p$ ????③
$\qquad \qquad \qquad\quad h_j(x)=0,\,\, j=1,2,...,q$ ?????④
$\qquad \qquad \qquad \alpha_i\,g_i(x)=0,\ {\ } i=1,2,..., p$ ????⑤

這一組方程看似很復(fù)雜，但其實(shí)很好理解：
①式：拉格朗日函數(shù)取得可行解的必要條件(羊爬山的例子)剂公；
②式：不等式約束對(duì)應(yīng)的拉格朗日乘子的初始條件希俩；
③~④式：優(yōu)化問題的初始約束條件；
⑤式：前面得到的那個(gè)重要“結(jié)論 $*$ ”纲辽；

總結(jié)一下颜武，KKT條件是“一個(gè)凸優(yōu)化問題存在最優(yōu)解”的充要條件，通過KKT條件我們即可求得凸優(yōu)化問題的最優(yōu)解拖吼。用數(shù)學(xué)語言表述一下就是：
若目標(biāo)函數(shù) $f(x)$ 和不等式約束 $g_i(x)$ 都是凸函數(shù)鳞上，而等式約束 $h_i(x)$ 是仿射函數(shù)（即形如 $w^Tx+b=0$ 的線性函數(shù)），且不等式約束 $g_i(x)$ 的等號(hào)都能成立（這一條件稱為Slater條件）吊档，那么滿足KKT條件的 $x$ 點(diǎn)即為全局最優(yōu)解篙议。

2.3 SVM的對(duì)偶形式

在引入KKT條件之前，我們已經(jīng)將SVM轉(zhuǎn)化成了如下形式: $\begin{array}{lcl} \qquad\quad\ \, \max\limits_{\alpha}\min\limits_{w,b}\ \ \mathcal{L}(w,b,\alpha) \\ \qquad \quad\ \ \; \mathrm{s.t.}\quad\alpha_i\ge0,\ i=1,2,...,m \end{array}$ 其中怠硼， $\mathcal{L}(w,b,\alpha)={\frac{1}{2}}{||w||}^2+\sum_{i=1}^{m}\alpha_i[1-y_i(w^Tx_i+b)]$ 我們發(fā)現(xiàn)鬼贱，求解 $\min\limits_{w,b}\mathcal{L}(w,b,\alpha)$ 是可以利用KKT條件的。

對(duì)于條件①： $\nabla_x\mathcal{L}(x,\alpha,\beta)=0$ 拒名，我們這里的變量為 $w$ 和 $b$ 吩愧，所以有： $\nabla_{w,b} \mathcal{L}(w,b,\alpha)=0 \quad\Longrightarrow \quad \frac{\partial \mathcal{L}}{\partial w}=0\,,\ \frac{\partial \mathcal{L}}{\partial b}=0$ 那么接下來我們就可以進(jìn)行一波愉快的數(shù)學(xué)計(jì)算了。增显。雁佳。(還沒學(xué)過向量函數(shù)求導(dǎo)的小伙伴們，快進(jìn)來現(xiàn)學(xué)一下吧~) $\begin{align} \frac{\partial \mathcal{L}}{\partial w}=0 &=\frac{\partial}{\partial w}[ \frac {1}{2} w^Tw+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy_i(w^Tx_i+b)]\\ &=\frac{\partial}{\partial w}(\frac {1}{2} w^Tw+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy_i w^Tx_i-\sum_{i=1}^{m}\alpha_iy_ib )\\ &=\frac{\partial}{\partial w}(\frac {1}{2} w^Tw-\sum_{i=1}^{m}\alpha_iy_i w^Tx_i )\\ &=\frac{\partial}{\partial w}(\frac {1}{2} w^Tw-w^T\sum_{i=1}^{m}\alpha_iy_i x_i )\\ &=w-\sum_{i=1}^{m}\alpha_iy_i x_i \end{align}$ $\begin{align} \frac{\partial \mathcal{L}} {\partial b}=0&=\frac{\partial} {\partial b}[ \frac {1}{2} w^Tw+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy_i(w^Tx_i+b) ] \\ &=\frac{\partial}{\partial b}(\frac {1}{2} w^Tw+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy_i w^Tx_i-\sum_{i=1}^{m}\alpha_iy_ib )\\ &=\frac{\partial}{\partial b} (-\sum_{i=1}^{m}\alpha_iy_ib )\\ &=\frac{\partial}{\partial b} (-b\sum_{i=1}^{m}\alpha_iy_i )\\ &=-\sum_{i=1}^{m}\alpha_iy_i \end{align}$ 通過這一波求偏導(dǎo)我們得到： $w=\sum_{i=1}^{m}\alpha_iy_i x_i\ \;,\ \,0=\sum_{i=1}^{m}\alpha_iy_i$ 將其帶入 $\mathcal{L}(x,\alpha,\beta)$ 即可得到最小值： $\begin{align} \min\limits_{w,b} \mathcal{L}(w,b,\alpha) &= {\frac {1} {2}} {||w||}^2+\sum_{i=1}^{m}\alpha_i[1-y_i(w^Tx_i+b)]\\ &=\frac{1}{2}w^Tw+\sum_{i=1}^{m}\alpha_i -w^T(\sum_{i=1}^{m}\alpha_i y_i x_i)-b(\sum_{i=1}^{m} \alpha_i y_i)\\ &=\frac{1}{2}w^Tw+\sum_{i=1}^{m}\alpha_i -w^Tw-b\cdot0\\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}(\sum_{i=1}^{m}\alpha_iy_i x_i)^T(\sum_{i=1}^{m}\alpha_iy_i x_i)\\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}(\sum_{i=1}^{m}\alpha_iy_i x_i^T)(\sum_{j=1}^{m}\alpha_jy_j x_j)\\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2} [\sum_{i=1}^{m}\alpha_iy_i x_i^T(\sum_{j=1}^{m}\alpha_jy_j x_j) ] \\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_jx_i^Tx_j \end{align}$ 對(duì)于條件②~⑤同云，SVM不存在等式約束糖权，其余的條件對(duì)應(yīng)為 $\begin{cases}\alpha_i\ge0\;;\\ 1-y_i(w^Tx_i+b)\le0\;;\\ \alpha_i[1-y_i(w^Tx_i+b)]=0\;;\end{cases}$ 前兩個(gè)式子是原始約束條件，而第三個(gè)式子就是之前在2.2.1中提到的“結(jié)論 $*$ ”炸站，當(dāng)時(shí)為什么說它是一個(gè)重要結(jié)論呢星澳，因?yàn)樗|及到了SVM的核心，請(qǐng)看：

當(dāng) $\alpha_i=0$ 時(shí)旱易，則在目標(biāo)函數(shù)的求和項(xiàng)中 $\alpha_iy_i x_i=0$ 禁偎，表示此 $\alpha_i$ 對(duì)應(yīng)的向量不會(huì)對(duì)超平面的確定有任何影響；
當(dāng) $\alpha_i>0$ 時(shí)阀坏，則必有 $y_i(w^Tx_i+b)=1$ ,表示此 $\alpha_i$ 對(duì)應(yīng)的向量在支撐超平面上（圖2中虛線位置）如暖，即支持向量；
這表明忌堂，劃分超平面的確立只與支持向量有關(guān)盒至。同時(shí)，如果我們要找出支持向量，只需找到非零 $\alpha_i$ 對(duì)應(yīng)的向量即可枷遂。所以說樱衷，此式揭示了 $\alpha$ 的物理意義，是深入了解SVM的關(guān)鍵酒唉。

至此矩桂，我們得到了SVM的對(duì)偶形式： $\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1} {2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_jx_i^Tx_j$ $\quad\;\;\;\;\mathrm{s.t.}\;\sum_{i=1}^{m}\alpha_iy_i=0\,,\,\alpha_i\ge0\,,\,i=1,2,...,m$ 接下來的問題是如何求解 $\alpha$ 呢？

三黔州、求解的方法

3.1 SMO算法基本思路

我們可以看到耍鬓，在對(duì)偶問題中存在 $m$ 個(gè)參數(shù) $\alpha$ ，很難直接求得最優(yōu)解流妻。所以我們考慮使用迭代的方法每次只優(yōu)化有限個(gè)參數(shù)。但由于 $\begin{array} \,\sum_{i=1}^{m}\alpha_iy_i=0\end{array}$ 的限制笆制，我們不能單獨(dú)對(duì)某個(gè)參數(shù)更新绅这，所以我們每次選取兩個(gè)更新變量 $\alpha_i$ 和 $\alpha_j$ ，而固定其余參數(shù)在辆，通過反復(fù)的迭代求解對(duì)偶問題证薇。

SMO算法之所以高效，就是因?yàn)楣潭ㄆ溆鄥?shù)后僅優(yōu)化兩個(gè)參數(shù)的過程可以做到很高效匆篓，但為了減少迭代次數(shù)浑度，每次選取哪兩個(gè)參數(shù)還是有講究的。我們知道鸦概，只要 $\alpha_i$ 和 $\alpha_j$ 中有一個(gè)不滿足KKT條件箩张，目標(biāo)函數(shù)就會(huì)在迭代后減小。直觀來看窗市，KKT條件違背的程度越大先慷，則更新變量后可能導(dǎo)致的目標(biāo)函數(shù)值減幅越大，所以我們首先選取一個(gè)違背KKT條件程度最大的變量咨察。第二個(gè)變量應(yīng)該選擇一個(gè)使目標(biāo)函數(shù)值減小最快的變量论熙，但由于比較各變量對(duì)目標(biāo)函數(shù)值的減幅過于復(fù)雜，所以SMO采用了一個(gè)啟發(fā)式(指根據(jù)經(jīng)驗(yàn)或直觀想法設(shè)計(jì)的算法摄狱，每一步不一定最優(yōu)但節(jié)省資源)：使選取的兩變量所對(duì)應(yīng)的樣本點(diǎn)間隔最大脓诡。因?yàn)槲覀冎庇^上可以認(rèn)為，比起對(duì)兩個(gè)相似的變量進(jìn)行更新媒役，對(duì)兩個(gè)有很大差別的變量進(jìn)行更新會(huì)帶給目標(biāo)函數(shù)值更大的變化祝谚。

思路：①每次迭代過程僅優(yōu)化兩個(gè)參數(shù)，存在閉式解刊愚；
??? （即任意參數(shù)都必能求得優(yōu)化后的值踊跟，具體過程中可得證）
???②啟發(fā)式尋找每次要優(yōu)化的兩個(gè)參數(shù)，有效減少迭代次數(shù)；

方法：①設(shè)置 $\alpha$ 列表商玫，并設(shè)其初始值為0箕憾；（每個(gè)數(shù)據(jù)點(diǎn)都對(duì)應(yīng)一個(gè) $\alpha_i$ ）
???②選取兩個(gè)待優(yōu)化變量;（為了便于講解，這里將其記為 $\alpha_1$ 和 $\alpha_2$ ）
???③求解兩個(gè)變量的最優(yōu)解 $\alpha_1^*$ 和 $\alpha_2^*$ 拳昌，并更新至 $\alpha$ 列表中;
???④檢查更新后的 $\alpha$ 列表是否在某個(gè)精度范圍內(nèi)滿足KKT條件袭异，若不滿
????足則返回②；（這里考慮到了計(jì)算機(jī)存在浮點(diǎn)數(shù)的誤差）

3.2 SMO算法基本實(shí)現(xiàn)

我們現(xiàn)在的問題為： $\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1} {2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_jx_i^Tx_j$ $\quad\ \ \,\;\mathrm{s.t.}\;\sum_{i=1}^{m}\alpha_iy_i=0\,,\,\alpha_i\ge0\,,\,i=1,2,...,m$ 當(dāng)選定兩個(gè)待優(yōu)化變量 $\alpha_1$ 和 $\alpha_2$ 炬藤，我們將目標(biāo)函數(shù)展開御铃，去掉無關(guān)項(xiàng)并更新約束條件： $\begin{align} \max_{\alpha_1,\alpha_2} W(\alpha_1,\alpha_2)&=(\alpha_1+\alpha_2+\color{Green} {\sum_{i=3}^{m}\alpha_i})-\frac{1}{2}K_{11}\alpha_1^2-\frac{1}{2}K_{22}\alpha_2^2\\&\quad\; -y_1y_2K_{12}\alpha_1 \alpha_2-y_1\alpha_1 \sum_{i=3}^{m}y_i\alpha_iK_{i1}-y_2\alpha_2 \sum_{i=3}^{m}y_i\alpha_iK_{i2}\\ &=(\alpha_1+\alpha_2)-\frac{1} {2}K_{11}\alpha_1^2-\frac{1}{2}K_{22}\alpha_2^2-y_1y_2K_{12}\alpha_1 \alpha_2\\&\quad\; -y_1\alpha_1 \sum_{i=3}^{m}y_i\alpha_iK_{i1}-y_2\alpha_2 \sum_{i=3}^{m}y_i\alpha_iK_{i2} \end{align}$ $\begin{array} \mathrm{s.t.}\ &\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^{m}y_i\alpha_i=\xi\,,\\ &\alpha_i\ge0\;,\,i=1,2,...,m \end{array}$

其中 $K_{ij}$ 代表 $\alpha_i^T\alpha_j$ ，是核函數(shù)(Kernel Function)沈矿，目前只用知道它等價(jià)于變量在特征空間的內(nèi)積即可上真，后面的章節(jié)會(huì)對(duì)它具體講解。

我們現(xiàn)已將問題轉(zhuǎn)化成一個(gè)二元二次問題羹膳，而利用約束條件我們可將其再次轉(zhuǎn)化為一元二次問題睡互，最后通過比較最值點(diǎn)和可行域之間的關(guān)系即可獲得可行域中的最值。

記 $\quad\, v_i=\sum_{j=3}^{m}y_j\alpha_jK_{ij}=f(x_i)-\sum_{j=1}^{2}y_j\alpha_jK_{ij}-b\;,\,i=1,2$

有： $\;\begin{align}W(\alpha_1,\alpha_2)= & \frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22} \alpha_2^2+y_1y_2K_{12}\alpha_1 \alpha_2\\ &-(\alpha_1+\alpha_2)+y_1v_1\alpha_1+y_2v_2\alpha_2 \end{align}$

回代 $\ \,\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^{m}y_i\alpha_i=\xi\;\Longleftrightarrow\ \alpha_1=(\xi -y_2\alpha_2)y_1$

得: $\qquad \begin{align} W(\alpha_2)=&\frac{1} {2}K_{11}(\xi-\alpha_2y_2)^2+\frac{1}{2}K_{22}\alpha_2^2+y_2K_{12}(\xi-\alpha_2y_2)\alpha_2\\ &-(\xi-\alpha_2y_2)y_1-\alpha_2+v_1(\xi-\alpha_2y_2)+y_2v_2\alpha_2 \end{align}$

對(duì) $\alpha_2$ 求偏導(dǎo)：
$\qquad\begin{align}\frac{\partial W}{\partial \alpha_2}=&K_{11}\alpha_2+K_{22}\alpha_2-2K_{12}\alpha_2-K_{11}\xi y_2\\ &+K_{12}\xi y_2+y_1y_2-1-v_1y_2+y_2v_2 =0 \end{align}$ $\Big\Updownarrow$ $(K_{11}+K_{22}-2K_{12})\alpha_2=y_2( y_2-y_1+\xi K_{11}-\xi K_{12}+v_1-v_2 )$ $\begin{align} &=y_2\Big[y_2-y_1+\xi K_{11}-\xi K_{12}+\big(f(x_1)-\sum_{j=1}^{2}y_j\alpha_jK_{1j}-b \big) \\ &-\big( f(x_2)-\sum_{j=1}^{2}y_j\alpha_jK_{2j}-b \big) \Big] \end{align}$ 將 $\xi =\alpha_1^{old}y_1+\alpha_2^{old}y_2$ 代入陵像，并設(shè) $E_i=f(x_i)-y_i$ 就珠，有：

$\begin{align} & \;(K_{11}+K_{22}-2K_{12}) \alpha_2^{new,unc}\\ &=y_2\Big[(K_{11}+K_{22}-2K_{12})\alpha_2^{old}y_2+y_2-y_1+g(x_1)-g(x_2) \Big]\\ &=(K_{11}+K_{22}-2K_{12})\alpha_2^{old}+y_2(E_1-E_2) \end{align}$ 這里的 $\alpha_2^{new,unc}$ 表示這個(gè) $\alpha_2^{new}$ 還沒有與可行域進(jìn)行比較(unclear)，不一定是最終的 $\alpha_2^{new}$ 醒颖。

記 $\eta=K_{11}+K_{22}-2K_{12}$ ,有： $\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)} {\eta}$ 接下來妻怎，我們要將可行域內(nèi)的得到的最優(yōu)解與可行域的邊界進(jìn)行比較。

$\alpha$ 的可行域： $L\ \le \ \alpha^{new}\le H$ $\alpha_1y_1+\alpha_2y_2=\xi$ 根據(jù) $y_1,y_2$ 的符號(hào)關(guān)系分類有： $\begin{cases} L=\max(0\ ,\, \alpha_2^{old}-\alpha_1^{old}) ,\ H=+\infty, &\mathrm{if}\ \ \, y_1=-y_2 \\ L=0 \ ,\ H=+\infty, \quad &\mathrm{if}\ \ \, y_1=\ \ y_2 \end{cases}$
可得： $\alpha_2^{new} =\begin{cases} H\ , \quad\quad \quad &\alpha_2^{new,unc}\ge H\\ \alpha_2^{new,unc} ,&L\le \alpha_2^{new,unc} \le H\\ L\ ,& \alpha_2^{new,unc}\le H \end{cases}$ 而根據(jù) $\alpha_1^{new}y_1+\alpha_2^{new}y_2=\alpha_1^{old}y_1+\alpha_2^{old}y_2$ 有： $\alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})$

至此我們已經(jīng)得到更新 $\alpha$ 參數(shù)的方法泞歉，下面說說兩個(gè)待優(yōu)化變量如何選取逼侦。

思想：選取的兩個(gè)變量所對(duì)應(yīng)的樣本之間的間隔最大，且違反KKT條件的
?????程度要大疏日，以期待它們帶來的差異能給目標(biāo)函數(shù)值更大的變化偿洁。

方法：①選取第一個(gè)變量
?????便利訓(xùn)練樣本點(diǎn)，檢驗(yàn)它們是否滿足KKT條件(在一定精度范圍內(nèi))沟优，
?????選擇任一違反KKT條件的變量涕滋。
?????②選取第二個(gè)變量
?????在選擇了第一個(gè)變量的基礎(chǔ)上，我們希望選取的第二個(gè)變量能夠帶來
?????足夠的變化量挠阁； $\alpha_2$ 的更新依賴 $|E_1-E_2|$ 宾肺，故當(dāng) $E_1\ge0$ 時(shí)，我
?????們選取最小的 $E_2$ 侵俗，反之選取最小的 $E_2$ 锨用；
?????若更新量不夠，則選擇 $\alpha_2\neq0$ 的點(diǎn)隘谣；
?????若更新量仍不夠增拥，則遍歷剩余的點(diǎn)啄巧；
?????若更新量還不夠，則重新選擇 $\alpha_1$ 掌栅，并按照上述邏輯再次選取 $\alpha_2$ 秩仆；

3.3 算法總結(jié)

當(dāng)我們優(yōu)化更新完所有的 $\alpha_i$ 參數(shù)，便可以得出最優(yōu)劃分超平面的解了猾封！

由之前KKT條件①求偏導(dǎo)那一步可得： $w^*=\sum_{i=1}^{m}\alpha_iy_ix_i$ 由唯一性可知澄耍， $b^*$ 為一確定值，我們選出任一支持向量晌缘，其滿足： $y_i(w^{*T}x_j+b^*)-1=0$ $\Updownarrow$ $y_i^2(w^{*T}x_j+b^*)-y_i=0$ 得出: $b^*=y_i-w^{*T}x_j=y_j-\sum_{i=1}^{m}\alpha_iy_i(x_i^Tx_j)$ 現(xiàn)實(shí)任務(wù)中我們采取一種更魯棒的做法：使用所有支持向量求解再取平均值齐莲，
得出： $\begin{align}&b^*=\frac{1}{|S|}\sum_{s\in S}\Big(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s\Big),\\&\mathcal{s.t.} \quad S= \{{ i\ |\ \alpha_i>0,i=1,2,...,m}\}\end{align}$
最后，我們來做一下總結(jié)：

線性可分支持向量機(jī)

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}$ ,
??????其中 $x_i\in R^n$ , $y_i\in\{-1,1 \}$ , $i=1,2,...,m$ 磷箕；
輸出：最優(yōu)劃分超平面和分類決策函數(shù)选酗；

（1）構(gòu)造并求解約束最優(yōu)化問題： $\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1} {2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_jx_i^Tx_j$ $\quad\ \ \,\;\mathrm{s.t.}\;\sum_{i=1}^{m}\alpha_iy_i=0\,,\,\alpha_i\ge0\,,\,i=1,2,...,m$ ????求得最優(yōu)解 $\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_m^*)^T$ ，并計(jì)算 $\begin{array} \,w^*= &\sum_{i=1}^{m}\alpha_i^*y_ix_i,\\ \,b^*\,=&y_j-\sum_{i=1}^{m}\alpha_i^*y_i(x_i^Tx_j)\end{array}$ （2）由此得到劃分超平面： $w^{*T}x+b^*=0$ ????分類決策函數(shù)： $f(x)=\mathrm{sign}(w^{*T}x+b^*)$

四岳枷、軟間隔SVM及核方法

4.1 軟間隔SVM

在前面的討論中星掰，我們假設(shè)了樣本點(diǎn)是線性可分的，而現(xiàn)實(shí)中的樣本往往很難達(dá)到完全線性可分嫩舟。退一步說，即使可以達(dá)到完全線性可分怀偷，我們找到的超平面也不一定是最好的家厌，很可能會(huì)因?yàn)殂@了一兩個(gè)數(shù)據(jù)點(diǎn)的牛角尖而出現(xiàn)過擬合的現(xiàn)象。緩解該問題的辦法是允許支持向量機(jī)在少部分點(diǎn)上“出錯(cuò)”椎工，為此我們引入“軟間隔(Soft Margin)”的概念饭于。

圖7 軟間隔SVM

如圖7所示，我們?cè)试S部分樣本點(diǎn)不滿足 $1-y_i(w^Tx_i+b)\le0$ 的條件而越過相鄰的支撐超平面维蒙。那么接下來我們需要考慮兩個(gè)方面的指標(biāo)：一是錯(cuò)誤樣本點(diǎn)越界的程度掰吕，二是錯(cuò)誤樣本點(diǎn)的數(shù)量。所以我們引入兩個(gè)新的變量：表示錯(cuò)誤樣本點(diǎn)超出支撐超平面的距離 $\xi_i$ 颅痊，對(duì)錯(cuò)誤樣本點(diǎn)的懲罰程度 $C$ （懲罰程度越高產(chǎn)生的數(shù)量自然越少殖熟，由此來控制數(shù)量和距離）。

增加軟間隔后斑响，我們的優(yōu)化目標(biāo)變?yōu)椋?img class="math-block" src="https://math.jianshu.com/math?formula=%5Cmin_w%5C%20%5C%20%5C%20%5Cfrac%7B1%7D%7B2%7D%7C%7Cw%7C%7C%5E2%2BC%5Csum_%7Bi%3D1%7D%5Em%5Cxi_i" alt="\min_w\ \ \ \frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i" mathimg="1"> $\begin{align} \mathrm{s.t.}\ \ \,& 1-y_i(w^Tx_i+b)-\xi_i\le0,\\ &\xi_i\ge0 \,,\;i=1,2,...,m \end{align}$ 其中 $C$ 是一個(gè)大于 $0$ 的常數(shù)菱属，其值越大表示對(duì)錯(cuò)誤的容忍性越小〗⒎＃可以想象當(dāng) $C$ 趨于無窮大時(shí)纽门， $\xi_i$ 必然趨于無窮小，即回到了線性SVM营罢。

按照處理線性SVM的套路赏陵，我們來優(yōu)化該問題：
①構(gòu)造拉格朗日函數(shù) $\begin{align}L(w,b,\alpha,\xi,\mu)= &\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i-\sum_{i=1}^m\mu_i\xi_i\\ &+\sum_{i=1}^m\alpha_i\big [ 1-\xi_i-y_i(w^T+b)\big] \end{align}$ 其中， $\alpha_i\ge0,\mu_i\ge0$ 是拉格朗日乘子。
②根據(jù)強(qiáng)對(duì)偶性蝙搔，轉(zhuǎn)化問題為 $\max_{\lambda,\mu}\min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)$ ③對(duì)極小化問題利用KKT條件缕溉，令 $L$ 對(duì) $w,b,\xi_i$ 的偏導(dǎo)為 $0$ 可得 $w=\sum_{i=1}^{m}\alpha_iy_ix_i\ ,\ 0=\sum_{i=1}^{m}\alpha_iy_i\ ,\ C=\alpha_i+\mu_i$ 代入拉格朗日函數(shù)可得 $\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1} {2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_jx_i^Tx_j$ $\quad\ \ \,\;\mathrm{s.t.}\;\;\sum_{i=1}^{m}\alpha_iy_i=0\,,\,0\le\alpha_i\le C\,,\,i=1,2,...,m$ 軟間隔SVM的KKT條件還有 $\begin{cases}\alpha_i\ge0\ ,\ \mu_i\ge 0\;;\\ 1-y_i(w^Tx_i+b)-\xi_i\le0\;;\\ \alpha_i[1-y_i(w^Tx_i+b)-\xi_i]=0\;;\\ \xi_i\ge0\ ,\ \mu_i\xi_i=0\;;\end{cases}$ ④利用SMO算法解得拉格朗日乘子 $\alpha^*$ ，得出 $\begin{align}& w^*=\sum_{i=1}^{m}\alpha_iy_ix_i\;,\\ &b^*=\frac{1}{|S|}\sum_{s\in S}\Big(y_s-\sum_{i\in S}\alpha_iy_ix_i^Tx_s\Big),\\&\mathcal{s.t.} \quad S= \{{ i\ |\ \alpha_i>0,i=1,2,...,m} \}\end{align}$ 最終得到最優(yōu)劃分超平面 $w^{*T}x+b^*=0$ 杂瘸；
同樣的倒淫， $\alpha_i\ge0$ 對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為支持向量，這就包括了越界的那些錯(cuò)誤點(diǎn)败玉，它們也是影響超平面的確立的敌土。

4.2 核函數(shù)

前面討論了線性SVM以及軟間隔SVM，它們可應(yīng)用于樣本全部或大部分線性可分的情況运翼，那么如果樣本呈現(xiàn)為圖1中左邊的情況呢返干？

圖1 線性可分

這時(shí)候我們采取的方法是，將二維線性不可分的樣本映射到高維空間中去血淌，并使其可分矩欠。就比如我們不能從年齡，體重來區(qū)分小豬和小羊悠夯，但是我們?cè)黾右粋€(gè)維度角的數(shù)量就可以達(dá)到區(qū)分的目的癌淮，這種方法稱為核技巧(請(qǐng)點(diǎn)開看這個(gè)生動(dòng)的案例)÷俨梗《機(jī)器學(xué)習(xí)》中也提到了一個(gè)簡明的例子乳蓄，“異或”問題。

圖8 核技巧

對(duì)于在有限維度向量空間中線性不可分的樣本夕膀，我們將其映射到更高維度的向量空間里虚倒，再通過間隔最大化的方式，學(xué)習(xí)得到支持向量機(jī)产舞，就是非線性SVM魂奥。我們用 $x$ 表示原來的樣本點(diǎn)，用 $\phi(x)$ 表示映射到新的特征空間后得到的點(diǎn)易猫。那么分割超平面可以表示為： $f(x)=w\phi(x)+b$ 通過同樣的套路耻煤，我們也可以求得非線性SVM的對(duì)偶問題： $\max_\alpha \ \sum_{i=1}^{m}\alpha_i-\frac{1} {2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_iy_j\phi(x_i)^T\phi(x_j)$ $\mathrm{s.t.}\;\;\sum_{i=1}^{m}\alpha_iy_i=0\,,\,\alpha_i\ge0 \,,\,i=1,2,...,m \quad$ 但這時(shí)我們發(fā)現(xiàn)一個(gè)問題，就是該如何去求解高維特征空間中的內(nèi)積呢擦囊？為了避開這個(gè)障礙违霞，我們?cè)O(shè)想有這么一個(gè)函數(shù)： $k(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle=\phi(x_i)^T\phi(x_j)$ 即使得 $x_i$ 與 $x_j$ 在高維特征空間的內(nèi)積就等于它們?cè)谠紭颖究臻g中通過 $k(\cdot\,,\,\cdot)$ 計(jì)算得到的結(jié)果。如果有這樣的函數(shù)存在瞬场，我們將其帶入對(duì)偶問題中即可求得最優(yōu)劃分超平面為： $\begin{align} f(x)&=w^T\phi(x)+b\\ &=\sum_{i=1}^{m}\alpha_i y_i \phi(x_i)^T\phi(x)+b\\ &=\sum_{i=1}^{m}\alpha_i y_i k(x,x_i)+b \end{align}$ 這里的 $k(\cdot\,,\,\cdot)$ 就是“核函數(shù)”(kernel function)买鸽。

那么合適的核函數(shù)是否一定存在呢？什么樣的函數(shù)能做核函數(shù)呢贯被？有哪些常用的核函數(shù)以及如何選取呢眼五？某乎上有很多精彩的回答妆艘，感興趣的同學(xué)可以去翻一翻，我這里就略過了看幼。

五批旺、SVM的優(yōu)缺點(diǎn)及應(yīng)用

5.1 SVM的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

有嚴(yán)格的數(shù)學(xué)理論支持，可解釋性強(qiáng)诵姜，不依靠統(tǒng)計(jì)方法汽煮，從而簡化了通常的分類和回歸問題；
能找出對(duì)任務(wù)至關(guān)重要的關(guān)鍵樣本（即支持向量）棚唆；
采用核技巧之后暇赤，可以處理非線性分類/回歸任務(wù)；
最終決策函數(shù)只由少數(shù)的支持向量所確定宵凌，計(jì)算的復(fù)雜性取決于支持向量的數(shù)目鞋囊，而不是樣本空間的維數(shù)，這在某種意義上避免了“維數(shù)災(zāi)難”瞎惫。

缺點(diǎn)：

訓(xùn)練時(shí)間長溜腐。當(dāng)采用SMO算法時(shí)，由于每次都需要挑選一對(duì)參數(shù)瓜喇，因此時(shí)間復(fù)雜度為 $O(N^2)$ 挺益，其中 N 為訓(xùn)練樣本的數(shù)量；
當(dāng)采用核技巧時(shí)乘寒，如果需要存儲(chǔ)核矩陣矩肩，則空間復(fù)雜度為 $O(N^2)$ ;
模型預(yù)測(cè)時(shí)，預(yù)測(cè)時(shí)間與支持向量的個(gè)數(shù)成正比肃续。當(dāng)支持向量的數(shù)量較大時(shí)，預(yù)測(cè)計(jì)算復(fù)雜度較高叉袍。

因此支持向量機(jī)目前只適合小批量樣本的任務(wù)始锚，無法適應(yīng)百萬甚至上億樣本的任務(wù)。

5.2 SVM的應(yīng)用

SVM技術(shù)在解決小樣本喳逛、非線性及高維度的模式識(shí)別問題中表現(xiàn)出明顯的優(yōu)勢(shì)瞧捌。在許多領(lǐng)域，如文本分類润文、圖像識(shí)別姐呐、生物信息學(xué)等領(lǐng)域中得到了成功的應(yīng)用。

Scikit-learn庫中帶有封裝好的SVM典蝌，我們可以方便地應(yīng)用SVM曙砂。

六、回顧

本文詳細(xì)介紹了支持向量機(jī)的算法原理骏掀，全篇重要知識(shí)點(diǎn)如下：

圖9 SVM思維導(dǎo)圖

后記：通過編寫此文鸠澈，本人自己對(duì)SVM的理解是有所加深的柱告，其實(shí)寫之前我有很多地方都沒懂透。所以說當(dāng)學(xué)習(xí)上遇到困難時(shí)不妨轉(zhuǎn)換角色笑陈，想象自己需要將知識(shí)教授給新手际度，秉持這樣的態(tài)度一來可以激勵(lì)自己，二來可以在學(xué)習(xí)中吸收到更細(xì)微的知識(shí)涵妥。

參考：
[1]《機(jī)器學(xué)習(xí)》周志華
[2]《統(tǒng)計(jì)學(xué)習(xí)方法》李航
[3] 約束優(yōu)化方法之拉格朗日乘子法與KKT條件
[4]【ML】支持向量機(jī)（SVM）從入門到放棄再到掌握
[5]【機(jī)器學(xué)習(xí)】支持向量機(jī) SVM

最后編輯于：2020.04.10 12:17:29

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末乖菱，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子蓬网，更是在濱河造成了極大的恐慌窒所，老刑警劉巖，帶你破解...
沈念sama閱讀 221,635評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件拳缠，死亡現(xiàn)場(chǎng)離奇詭異墩新，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)窟坐，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,543評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門海渊，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人哲鸳，你說我怎么就攤上這事臣疑。” “怎么了徙菠？”我有些...
開封第一講書人閱讀 168,083評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵讯沈，是天一觀的道長。經(jīng)常有香客問我婿奔，道長缺狠，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 59,640評(píng)論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任萍摊，我火速辦了婚禮挤茄，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘冰木。我一直安慰自己穷劈，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 68,640評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布踊沸。她就那樣靜靜地躺著歇终，像睡著了一般。火紅的嫁衣襯著肌膚如雪逼龟。梳的紋絲不亂的頭發(fā)上评凝，一...
開封第一講書人閱讀 52,262評(píng)論 1贊 308
城市分裂傳說
那天，我揣著相機(jī)與錄音腺律，去河邊找鬼肥哎。笑死辽俗，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的篡诽。我是一名探鬼主播崖飘，決...
沈念sama閱讀 40,833評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼杈女！你這毒婦竟也來了朱浴？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,736評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤达椰，失蹤者是張志新（化名）和其女友劉穎翰蠢，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體啰劲，經(jīng)...
沈念sama閱讀 46,280評(píng)論 1贊 319
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡梁沧，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,369評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蝇裤。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片廷支。...
茶點(diǎn)故事閱讀 40,503評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖栓辜，靈堂內(nèi)的尸體忽然破棺而出恋拍，到底是詐尸還是另有隱情，我是刑警寧澤藕甩，帶...
沈念sama閱讀 36,185評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布施敢，位于F島的核電站，受9級(jí)特大地震影響狭莱，放射性物質(zhì)發(fā)生泄漏僵娃。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,870評(píng)論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一腋妙、第九天我趴在偏房一處隱蔽的房頂上張望悯许。院中可真熱鬧，春花似錦辉阶、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,340評(píng)論 0贊 24
一樁弒父案谆甜，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至集绰，卻和暖如春规辱，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背栽燕。一陣腳步聲響...
開封第一講書人閱讀 33,460評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工罕袋，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留改淑，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,909評(píng)論 3贊 376
代替公主和親
正文我出身青樓浴讯，卻偏偏與公主長得像朵夏，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子榆纽，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,512評(píng)論 2贊 359