1嘁灯、手推SVM

整體思路：

定義樣本點到目標(biāo)超平面的幾何距離：
$\frac{y_i(wx_i+b)}{||w||}$
定義間隔（margin）為各樣本點到超平面的最小距離：
$margin=\min_{w,b}\frac{y_i(wx_i+b)}{||w||}$
根據(jù)間隔最大化的目標(biāo)寫出規(guī)劃：
$\begin{equation*} \begin{array} \text{ max} & r\\ \text{s.t.} & \min_{w,b}\frac{y_i(wx_i+b)}{||w||} \ge r \\ \end{array} \end{equation*}$
由于 $(w,b)$ 和 $(\lambda w,\lambda b)$ 對應(yīng)超平面相同欺冀，故令 $\min_{w,b}y_i(wx_i+b)=1$ 赦颇，得到：
$\begin{equation*} \begin{array} \text{ max} &\frac{1}{||w||} \\ \text{s.t.} &y_i(wx_i+b)\ge 1 \\ \end{array} \end{equation*}$

變形得到：
$\begin{equation*} \begin{array} \text{ min} &\frac{1}{2}{||w||}^2 \\ \text{s.t.} &y_i(wx_i+b) - 1 \ge 0\\ \end{array} \end{equation*}$

構(gòu)建拉格朗日函數(shù)：
$L(w,b,\alpha)= \frac{1}{2}{||w||}^2+\sum_{i=1}^{N}\alpha_i[1-y_i(wx_i+b)]$

原問題轉(zhuǎn)化為：
$\min_{w,b}\max_{\alpha}L(w,b,\alpha)$
寫出其對偶：
$\max_{\alpha}\min_{w,b}L(w,b,\alpha)$
解對偶內(nèi)層最優(yōu)化問題啊鸭，即令 $L(w,b,\alpha)$ 對 $w$ 和 $b$ 偏導(dǎo)數(shù)為0蛇摸，得到：
$\begin{aligned} &w =\sum_{ i=1}^{N}\alpha_i y_i x_i \\ &\sum_{i=1}^{N}\alpha_i y_i = 0 \\ \end{aligned}$
帶入 $L(w,b,\alpha)$ 得到：
$L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i$
從而對偶問題變成：
$\begin{aligned} \max_{\alpha}&\ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i \\ s.t.&\ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ &\ \ \alpha_i \ge 0 \\ \end{aligned}$

即：

$\begin{aligned} \min_{\alpha}&\ \ \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)-\sum_{i=1}^N \alpha_i \\ s.t.&\ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ &\ \ \alpha_i \ge 0 \\ \end{aligned}$

求解此規(guī)劃得到 $\alpha^*=(\alpha^*_1,\alpha^*_2,\dots,\alpha^*_N)^T$ 急迂。

寫出KKT條件：

(1) 原始可行(滿足約束)：
$y_i(w^* \cdot x_i+b^*)-1\ge 0$

(2) 對偶可行(滿足約束)：
$\alpha^*\ge 0$

(3) 原始內(nèi)層最優(yōu)：
$\alpha_i[y_i(w^* \cdot x_i+b^*)-1]=0$

(4) 對偶內(nèi)層最優(yōu)：
$\begin{aligned} &w^* - \sum_{ I=1 }^N \alpha^*_i y_i x_i=0 \\ &\sum_{ I=1 }^{N}\alpha_i y_i = 0 \\ \end{aligned}$

由 $\alpha^*$ 得到 $w^*$ 和 $b^*$ ：
$w^*=\sum_{i=1}^N \alpha^*_i y_i x_i$

找到任意 $\alpha^*_j>0$ (必定存在)影所，由(3)可得：
$y_j(w^* \cdot x_j+b^*)-1=0$

兩邊同乘 $y_j$ 可得：
$(w^* \cdot x_j+b^*)-y_j=0$

故：
$\begin{aligned} b^* & =y_j-w^* \cdot x_j \\ & = y_j-\sum_{i=1}^N \alpha^*_i y_i (x_i \cdot x_j) \\ \end{aligned}$

若把硬間隔替換為軟間隔，則大體推導(dǎo)過程相同僚碎，唯一區(qū)別是對偶問題變成：
$\begin{aligned} \max_{\alpha}&\ \ -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i \cdot x_j)+\sum_{i=1}^N \alpha_i \\ s.t.& \ \ \sum_{i=1}^{N}\alpha_i y_i = 0 \\ & \ \ 0 \le \alpha_i \le C \\ \end{aligned}$

即約束由 $\alpha_i\ge 0$ 變成 $0 \le \alpha_i \le C$ 猴娩。

相應(yīng)的，在求解 $b^*$ 的時候要選擇滿足 $0<\alpha^*_j<C$ 的 $\alpha_j^*$ 勺阐。

若由線性推廣到非線性卷中，則把最優(yōu)解表達(dá)式中的 $(x_i \cdot x_j)$ 替換成 $\phi(x_i)\cdot \phi(x_j)$ 來進行求解，這一過程具體說來就是將特征通過 $\phi$ 映射到高維空間渊抽，然后將映射后的結(jié)果做內(nèi)積蟆豫，由于高維空間的內(nèi)積計算量較大，因此我們考慮核技巧懒闷，將兩步合為一步十减，即找到合適的 $K(x_i,x_j)$ 使得：

$K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j)$

這樣一來，就可以不顯示的寫出映射的高維空間而達(dá)成同樣的目的愤估，既實現(xiàn)了非線性又簡化了計算帮辟。

2、簡述SVM 原理

SVM 是一種二類分類模型玩焰。它的基本模型是在特征空間中尋找間隔最大化的分離超平面的線性分類器由驹。

當(dāng)訓(xùn)練樣本線性可分時，通過硬間隔最大化昔园，學(xué)習(xí)一個線性分類器蔓榄，即線性可分支持向量機闹炉；
當(dāng)訓(xùn)練數(shù)據(jù)近似線性可分時，引入松弛變量润樱，通過軟間隔最大化渣触，學(xué)習(xí)一個線性分類器，即線性支持向量機壹若；
當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時嗅钻，使用核技巧及軟間隔最大化，學(xué)習(xí)非線性支持向量機店展。

3养篓、SVM 為什么采用間隔最大化

當(dāng)訓(xùn)練數(shù)據(jù)線性可分時，存在無窮多個分離超平面可以將兩類數(shù)據(jù)正確分開赂蕴。

線性可分支持向量機利用間隔最大化求得最優(yōu)分離超平面柳弄，間隔最大化能夠使得樣本都盡量遠(yuǎn)離分類決策超平面，這會使得模型的結(jié)構(gòu)風(fēng)險最小概说，降低模型對數(shù)據(jù)擾動的敏感性碧注，也就意味著模型有著更強的泛化能力。

4糖赔、為什么要將求解 SVM 的原始問題轉(zhuǎn)換為其對偶問題

改變了問題的復(fù)雜度萍丐。在原問題中，參數(shù)數(shù)量與樣本的維度（即 $w$ 的維度）有關(guān)放典。在對偶問題中逝变，參數(shù)數(shù)量只與樣本數(shù)量 $N$ 有關(guān)。所以 SVM 對于高維空間中較稀疏的樣本表現(xiàn)較好奋构。
求解更高效壳影。因為只用求解 $\alpha$ 系數(shù)，而只有支持向量的 $\alpha$ 系數(shù)才非0弥臼，其它全部為0宴咧。求得最優(yōu)的 $\alpha^*$ 后， $w^*,b^*$ 都可由 $\alpha^*$ 得到醋火。
方便核函數(shù)的引入悠汽。只有通過求解對偶問題，先消去 $w,b$ 芥驳，才能得到內(nèi)積的形式柿冲，從而運用核技巧自然地將線性支持向量機推廣到非線性支持向量機。

5兆旬、為什么 SVM 要引入核函數(shù)

當(dāng)樣本在原始空間線性不可分時假抄，可將樣本從原始空間映射到一個更高維的特征空間，使得樣本在這個特征空間內(nèi)線性可分。

因為特征空間維數(shù)可能很高宿饱，甚至可能是無窮維熏瞄，因此直接計算 $?(x)·?(y)$ 是困難的。相反谬以，直接計算 $K(x,y)$ 比較容易（即直接在原來的低維空間中進行計算强饮，而不需要顯式地寫出映射后的結(jié)果）。

核函數(shù)的定義： $K(x,y)=<?(x),?(y)>$ 为黎，即在特征空間的內(nèi)積等于它們在原始樣本空間中通過核函數(shù) $K$ 計算的結(jié)果邮丰。

除了 SVM 之外，任何將計算表示為數(shù)據(jù)點的內(nèi)積的方法铭乾，都可以使用核方法進行非線性擴展剪廉。

P.S.核函數(shù)還有一個特點：對于給定的核函數(shù)，高維空間 $H$ 和映射函數(shù) $?$ 的取法并不唯一炕檩，也就是說斗蒋，某種程度上，一個核函數(shù)的選取可以同時檢驗多種特征映射的效果笛质。

6泉沾、列舉幾個常用核函數(shù)并簡要說明優(yōu)缺點

線性核函數(shù)： $K(u,v) = u\cdot v$
多項式核函數(shù)： $K(u,v) = (\gamma\cdot u\cdot v + \epsilon)^p$
高斯核函數(shù)： $K(u,v) = e^{(-\gamma||u-v||^2)}$

最常用的是Linear核與RBF核。

Linear核：主要用于線性可分的情形经瓷。參數(shù)少爆哑，速度快，對于一般數(shù)據(jù)舆吮，分類效果已經(jīng)很理想了。
RBF核：RBF核函數(shù)可以將一個樣本映射到一個更高維的空間队贱，主要用于線性不可分的情形色冀。參數(shù)多，分類結(jié)果非常依賴于參數(shù)柱嫌。
核函數(shù)參數(shù)的多少直接影響函數(shù)的復(fù)雜程度锋恬。多項式函數(shù)參數(shù)數(shù)量較多，且多項式的階數(shù)比較高時编丘，核矩陣的元素值將趨于無窮大或無窮小与学，造成數(shù)值計算上的困難。與多項式核函數(shù)相比嘉抓，RBF需要確定的參數(shù)要少索守，且會減少數(shù)值計算的困難。

具體實踐中抑片，如果特征維數(shù)很高卵佛，往往線性可分（SVM解決非線性分類問題的思路就是將樣本映射到更高維的特征空間中），可以采用線性核函數(shù)；如果樣本數(shù)量很多截汪，由于求解最優(yōu)化問題的時候疾牲，目標(biāo)函數(shù)涉及兩兩樣本計算內(nèi)積，使用高斯核等非線性核函數(shù)計算量會明顯大于線性核衙解，所以可以手動添加一些特征阳柔，使得線性可分，然后再使用線性核函數(shù)蚓峦；如果不滿足上述兩點舌剂，即特征維數(shù)少，樣本數(shù)量正常枫匾，可以使用高斯核函數(shù)架诞。

7、為什么 SVM 對缺失值敏感干茉，對異常值不敏感

這里說的缺失數(shù)據(jù)是指缺失某些特征數(shù)據(jù)谴忧。

首先，SVM 沒有處理缺失值的策略（決策樹有）角虫。其次沾谓，SVM 是基于距離的算法，而距離的計算要求數(shù)據(jù)各個維度都不能有缺失戳鹅。類似的均驶，KNN 也是基于距離的算法，因此對缺失值也很敏感枫虏。
異常值也就是所謂的離群點妇穴。SVM 的解只由支持向量決定，也就是由分類超平面附近的點決定隶债，因此離群點并不會改變 SVM 產(chǎn)生的分類超平面腾它。

8、SVM 如何處理多分類問題

直接法：直接在目標(biāo)函數(shù)上修改死讹，將多個分類面的參數(shù)求解合并到一個最優(yōu)化問題里面瞒滴。看似簡單但是計算量卻非常的大赞警。
間接法：對訓(xùn)練器進行組合妓忍。比較典型的有一對一和一對多。

一對多愧旦，就是對每個類都訓(xùn)練出一個分類器世剖，由于 SVM 是二分類，所以將此而分類器的兩類設(shè)定為目標(biāo)類為一類忘瓦，其余類為另外一類搁廓。這樣針對 $k$ 個類可以訓(xùn)練出 $k$ 個分類器引颈，訓(xùn)練時第 $i$ 個分類器時取訓(xùn)練集中第 $i$ 類為正類，其余類別點為負(fù)類進行訓(xùn)練境蜕。判別時蝙场，輸入信號分別經(jīng)過 $k$ 個分類機共得到 $k$ 個輸出值 $f_i(x)=sgn(g_i(x))$ ，若只有一個+1出現(xiàn)粱年，則其對應(yīng)類別為輸入信號類別售滤；若輸出不只一個+1(不只一類聲稱它屬于自己)，或者沒有一個輸出為+1(即沒有一個類聲稱它屬于自己)台诗，則比較 $g_i(x)$ 輸出值完箩，最大者對應(yīng)類別為輸入的類別。這種方法的優(yōu)點是拉队，對 $k$ 類問題弊知，只需要訓(xùn)練 $k$ 個二分類支持向量機；缺點是粱快，各分類器訓(xùn)練時樣本類別不均衡秩彤，bias 比較高。

一對一事哭，就是針對任意兩個類訓(xùn)練出一個分類器漫雷，如果有 $k$ 類，一共訓(xùn)練出 $C_k^2$ 個分類器鳍咱，這樣當(dāng)有一個新的樣本要來的時候降盹，用這 $C_k^2$ 個分類器來測試，每當(dāng)被判定屬于某一類的時候谤辜，該類票數(shù)就加一蓄坏，最后票數(shù)最多的類別被認(rèn)定為該樣本所屬的類。

9丑念、SVM 怎么防止過擬合

軟間隔的支持向量機中剑辫，我們?yōu)楦鱾€樣本引入的松弛變量 $\epsilon_i$ 就是用來防止過擬合的。

10渠欺、SVM 的優(yōu)缺點

優(yōu)點：

有嚴(yán)格的數(shù)學(xué)理論支持，可解釋性強椎眯。
能找出對任務(wù)至關(guān)重要的關(guān)鍵樣本（即：支持向量）挠将。
由于SVM是一個凸優(yōu)化問題，所以求得的解一定是全局最優(yōu)而不是局部最優(yōu)编整。
不僅適用于線性線性問題還適用于非線性問題(用核技巧)舔稀。
高維數(shù)據(jù)也能用 SVM，這是因為 SVM 對偶形式求解的復(fù)雜度與樣本數(shù)量而不是維數(shù)相關(guān)掌测，因此 SVM 很擅長解決高維稀疏的問題内贮。

缺點：

二次規(guī)劃問題求解將涉及 $N$ 階矩陣的計算( $N$ 為樣本的個數(shù)), 因此 SVM 不適用于超大數(shù)據(jù)集。
訓(xùn)練時間長。當(dāng)采用 SMO 算法時夜郁，由于每次都需要挑選一對參數(shù)什燕，因此時間復(fù)雜度為 $O(N^2)$ ，其中 $N$ 為樣本的個數(shù)竞端，也就是訓(xùn)練樣本的數(shù)量屎即。
模型預(yù)測時，預(yù)測時間與支持向量的個數(shù)成正比事富。當(dāng)支持向量的數(shù)量較大時技俐，預(yù)測計算復(fù)雜度較高。因此支持向量機目前只適合小批量樣本的任務(wù)统台，無法適應(yīng)百萬甚至上億樣本的任務(wù)雕擂。
只適用于二分類問題(可以通過多個SVM的組合來解決多分類問題)。

SVM（面試準(zhǔn)備）