1. 算法
1.1 從最簡(jiǎn)單的數(shù)學(xué)問題說起
要理解SVM算法霉囚，首先就要理解SVM解決的問題是什么达椰，損失函數(shù)是如何推導(dǎo)來的，這是最關(guān)鍵最基礎(chǔ)的部分堤尾，請(qǐng)看下面這張圖。
我們以二維特征空間中的一個(gè)二分類問題為例來講解迁客。SVM就是希望尋找一個(gè)最優(yōu)的決策邊界郭宝，這個(gè)邊界距離兩個(gè)類別的最近的樣本點(diǎn)最遠(yuǎn)。這里有兩個(gè)重要概念掷漱，這個(gè)最優(yōu)決策邊界就叫做超平面粘室，而兩個(gè)類別中距離這個(gè)決策邊界最近的點(diǎn)就叫做支持向量。也就是說我們希望各類別的支持向量到超平面的距離最常卜范，這就是SVM研究的基本問題衔统，下面我們將這個(gè)問題轉(zhuǎn)化成數(shù)學(xué)形式，并推導(dǎo)他的損失函數(shù)海雪，這個(gè)推導(dǎo)過程需要的數(shù)學(xué)基礎(chǔ)非常簡(jiǎn)單好理解锦爵。
超平面的描述方程：
二維空間點(diǎn)到直線
距離：
擴(kuò)展到n維空間點(diǎn)到直線
距離:
，
根據(jù)支持向量的定義我們知道喳魏，支持向量到超平面的距離為 d棉浸，其他點(diǎn)到超平面的距離大于 d。于是我們寫出這樣一個(gè)公式：
稍作轉(zhuǎn)化可以得到：
?是正數(shù)刺彩，我們暫且令它為 1（之所以令它等于 1迷郑，是為了方便推導(dǎo)和優(yōu)化枝恋，且這樣做對(duì)目標(biāo)函數(shù)的優(yōu)化沒有影響），故：
將兩個(gè)方程合并嗡害，我們可以簡(jiǎn)寫為：
這個(gè)方程的含義是：支持向量到超平面的距離等于 d焚碌，其他點(diǎn)到超平面的距離大于 d。y是每個(gè)點(diǎn)的類別標(biāo)簽霸妹，在超平面一側(cè)的為1十电，超平面另一側(cè)的為-1。
每個(gè)支持向量到超平面的距離可以寫為：
由：
得到：
所以每個(gè)支持向量到超平面的距離可以化為：
支持向量的方程為（這個(gè)方程如果不理解請(qǐng)仔細(xì)再理解一下前面關(guān)于每個(gè)點(diǎn)到超平面的距離推導(dǎo)）叹螟，所以上面那個(gè)方程又可以簡(jiǎn)化為：
還記得我們最開始提到的SVM基本數(shù)學(xué)問題嗎鹃骂？我們需要將支持向量到超平面的距離最大化，因此我們求解的優(yōu)化問題是：
為了求解的方便罢绽，我們需要對(duì)這個(gè)優(yōu)化問題做一系列的簡(jiǎn)單轉(zhuǎn)化畏线，例如，分?jǐn)?shù)求導(dǎo)不方便良价，因此我們可以將最大化寝殴，轉(zhuǎn)化成最小化
，
有根號(hào)計(jì)算明垢，因此轉(zhuǎn)化成最小化
蚣常，由此就得到了我們最后的優(yōu)化問題：
寫成以下形式：
1.2 拉格朗日乘子與KKT條件
SVM優(yōu)化是一個(gè)不等式約束條件下的優(yōu)化問題，數(shù)學(xué)核心理論就是拉格朗日乘子和針對(duì)不等式優(yōu)化的KKT條件痊银，具體可以參考這兩個(gè)鏈接：
https://www.zhihu.com/question/38586401?如何理解拉格朗日乘子法（講的特別好）
https://www.zhihu.com/question/23311674?不等式優(yōu)化中的KKT條件
我們得到以下這個(gè)式子：
1.3 繁瑣的優(yōu)化推導(dǎo)
這個(gè)優(yōu)化問題的求解過程是非常繁瑣的抵蚊，感興趣的可以自己推一推，主要是以下幾個(gè)步驟：
以上就是線性可分情況下曼验，二分類問題的SVM算法求解過程泌射。需要注意的是，SVM的編程實(shí)現(xiàn)過程是SMO算法：首先驗(yàn)證KKT條件鬓照，然后固定迭代求解得到，根據(jù)上文中的公式計(jì)算得到
與
孤紧，最后根據(jù)分類決策函數(shù)判斷類別豺裆。
2. 補(bǔ)充
2.1 軟間隔
如下圖所示，在實(shí)際分類中号显，二分類問題基本都不能找到一個(gè)完美的超平面臭猜，因?yàn)閮蓚€(gè)類別的交界處總是會(huì)存在錯(cuò)分的情況，因此我們引入軟間隔的概念押蚤。
相比于硬間隔的苛刻條件蔑歌，我們?cè)试S個(gè)別樣本點(diǎn)出現(xiàn)在間隔帶里面，比如：
在兩條虛線內(nèi)的向量都是支持向量揽碘，那么我們求解的優(yōu)化問題就變成了了如下次屠，具體的推導(dǎo)過程在此略去园匹。
2.2 核函數(shù)
對(duì)于線性不可分的問題，我們使用核函數(shù)劫灶，將向量映射到高維空間裸违，使其變得線性可分。
2.3 多分類問題
以上我們已經(jīng)解決了二分類問題中的所有情況供汛，但針對(duì)多分類問題如何解決呢？
方式一：將訓(xùn)練樣本集中的某一類當(dāng)成一類涌穆，其他所有類當(dāng)成一類怔昨，進(jìn)行二分類。這種方式下宿稀，n個(gè)類別就需要建立n個(gè)分類器朱监。
方式二：將訓(xùn)練樣本集中的類別每?jī)深惗紗为?dú)訓(xùn)練一個(gè)分類器。n個(gè)類別就需要建立個(gè)分類器原叮。
在預(yù)測(cè)的時(shí)候赫编，所有分類器都跑一遍，得到的所有結(jié)果中奋隶，出現(xiàn)次數(shù)最多的標(biāo)簽就是該樣本的類別擂送。
通常情況下使用方式一解決多分類問題，因?yàn)楸M管方式二更加精確唯欣，但耗費(fèi)的時(shí)間也更多嘹吨。時(shí)間與空間，速度與質(zhì)量進(jìn)行權(quán)衡境氢。
3. 優(yōu)缺點(diǎn)
3.1 優(yōu)點(diǎn)
有嚴(yán)格的數(shù)學(xué)理論支持蟀拷，可解釋性強(qiáng)，不依靠統(tǒng)計(jì)方法萍聊，從而簡(jiǎn)化了通常的分類和回歸問題问芬；
能找出對(duì)任務(wù)至關(guān)重要的關(guān)鍵樣本（即：支持向量）；
采用核技巧之后寿桨，可以處理非線性分類/回歸任務(wù)此衅；
最終決策函數(shù)只由少數(shù)的支持向量所確定，計(jì)算的復(fù)雜性取決于支持向量的數(shù)目亭螟，而不是樣本空間的維數(shù)挡鞍，這在某種意義上避免了“維數(shù)災(zāi)難”。
3.2 缺點(diǎn)
訓(xùn)練時(shí)間長(zhǎng)预烙。當(dāng)采用 SMO 算法時(shí)墨微，由于每次都需要挑選一對(duì)參數(shù)，因此時(shí)間復(fù)雜度為 扁掸，其中 N 為訓(xùn)練樣本的數(shù)量翘县；
當(dāng)采用核技巧時(shí)最域，如果需要存儲(chǔ)核矩陣，則空間復(fù)雜度為 炼蹦；
模型預(yù)測(cè)時(shí)羡宙，預(yù)測(cè)時(shí)間與支持向量的個(gè)數(shù)成正比。當(dāng)支持向量的數(shù)量較大時(shí)掐隐，預(yù)測(cè)計(jì)算復(fù)雜度較高狗热。
因此支持向量機(jī)目前只適合小批量樣本的任務(wù)，無法適應(yīng)百萬甚至上億樣本的任務(wù)虑省。
4. 調(diào)參
5. 相關(guān)鏈接
【機(jī)器學(xué)習(xí)】支持向量機(jī) SVM（非常詳細(xì)）
