SVM支持向量機(jī)

本片文章主要記錄在學(xué)習(xí)《統(tǒng)計(jì)學(xué)習(xí)方法》中 SVM 章節(jié)的難點(diǎn)茅信，不對(duì)詳細(xì)內(nèi)容進(jìn)行講解酝豪。主要是分析筆者在學(xué)習(xí)的過(guò)程中遇到的難點(diǎn)

支持向量機(jī)分為：

1. 線性可分支持向量機(jī)
2. 線性支持向量機(jī)
3. 非線性支持向量機(jī)：通過(guò)核函數(shù)轉(zhuǎn)換為 線性支持向量機(jī) 而求得解

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

這是一種最簡(jiǎn)單的支持向量機(jī)了，我們只要能夠找到一個(gè)超平面將數(shù)據(jù)集分為 2 個(gè)部分，一個(gè)部分是全部為正例，一個(gè)部分為全部是反例，這一點(diǎn)與下面的 線性支持向量機(jī) 有所不同

超平面.jpg

那么我們分類的決策函數(shù)就是

決策函數(shù).jpg

函數(shù)間隔與幾何間隔

函數(shù)間隔

按照機(jī)器學(xué)習(xí)的方法作箍，我們需要找出一個(gè)損失函數(shù)或者叫風(fēng)險(xiǎn)函數(shù)，然后最小化該函數(shù)來(lái)找到我們的超平面前硫。
在 SVM 中將數(shù)據(jù)集中的樣本點(diǎn)到超平面的距離遠(yuǎn)近作為分類預(yù)測(cè)的確信程度胞得，也就是樣本點(diǎn)距離超平面越遠(yuǎn)，其可信的程度就越高屹电。如果樣本點(diǎn)越近阶剑，那么樣本的預(yù)測(cè)準(zhǔn)確度就越低跃巡。

最直接的，直接計(jì)算幾何上的距離來(lái)表示遠(yuǎn)近牧愁，點(diǎn)到面的距離推導(dǎo)如下：

在超平面上有 xi 和 xj 這 2 個(gè)點(diǎn)素邪，那么就有以下式子

很明顯的，將 2 個(gè)式子相減得到下面的式子

法向量.jpg

很明顯猪半，由向量的知識(shí)可以知道兔朦，wT 是超平面的法向量了

假設(shè)在超平面外有 1 個(gè)點(diǎn) x1 ，那么假設(shè)有向量 (x1-xi)磨确，通過(guò)向量的基本知識(shí)我們知道沽甥，向量乘以某個(gè)方向的單位向量，那么就能得到向量在該方向的長(zhǎng)度乏奥。結(jié)合上面的超平面法向量安接，那么我們直接將 (x1-xi) 乘以 w 的單位向量就得到點(diǎn) x1 到超平面的距離，其中||w||是 w 的L2范式英融，也就是平方和再開根

距離.jpg

結(jié)合(2)式，可以得到

因?yàn)?(6)式 是帶有方向性的歇式，我們?cè)賹?y1 乘上去后驶悟，那么這個(gè)距離就是非負(fù)的，無(wú)論 x1 在超平面的哪一邊材失，所以最終我們得到的距離式子如下

將 x1 和 y1 用一般性的 x 和 y代替痕鳍，這樣就能得到最終的 幾何間隔距離

一般距離.jpg

那么按照一開始說(shuō)的，我們只要讓數(shù)據(jù)集的每一個(gè)樣本點(diǎn)的距離最大化龙巨，就能保證我們有充分大的確信度來(lái)讓我們正確地分類笼呆，那么我們就需要優(yōu)化 w 和 b 來(lái)得到這樣的超平面，所以我們就要求解w 和 b

用符號(hào)來(lái)表示 幾何間隔

幾何間隔.jpg

并有

距離公式.jpg

（筆者開始時(shí)連基本的數(shù)學(xué)都給忘了旨别，所以記下來(lái)好好給自己提個(gè)醒）

函數(shù)間隔

函數(shù)間隔 是為了讓計(jì)算更加簡(jiǎn)單而使用的诗赌，參考附錄的《函數(shù)間隔為什么可以為1》

函數(shù)間隔為：

函數(shù)間隔.jpg

在 SVM 的約束問(wèn)題中，我們讓函數(shù)間隔為 1 而便于計(jì)算秸弛，參考附錄的《函數(shù)間隔為什么可以為1》

其本質(zhì)的理解就是：讓距離的變化全部都體現(xiàn)在 w 和 b 上铭若，從而來(lái)求得解

支持向量

支持向量是什么呢？因?yàn)槭浅矫娴堇溃敲淳痛嬖诰嚯x超平面最近的點(diǎn)叼屠，而我們要做的就是不斷的調(diào)整超平面，讓超平面離這些最近的點(diǎn)的距離最遠(yuǎn)绞铃，這里有點(diǎn)繞口镜雨，讀者們可以好好理解一下。因?yàn)榫嚯x超平面最近的點(diǎn)的距離是未知的儿捧，所以我們可以不斷的調(diào)整這個(gè)距離荚坞，讓這個(gè)距離達(dá)到最大挑宠。

而這些距離超平面最近的點(diǎn)就是支持向量，其實(shí)可以這么理解西剥，這些點(diǎn)對(duì)超平面的影響是最大的

而從約束條件來(lái)看痹栖，其實(shí)就是 y(w·x+b)=0 的那些點(diǎn)(這里比較抽象，需要結(jié)合書籍來(lái)看瞭空，筆者不多贅述揪阿，有需要可以留言交流)

可分線性約束條件.jpg

對(duì)偶解法

SVM 使用了對(duì)偶解法，但要注意的是咆畏，這里是使用 2 次對(duì)偶南捂，也就是對(duì)對(duì)偶問(wèn)題的極小化問(wèn)題再使用一次對(duì)偶

線性對(duì)偶.jpg

我們先求最小化問(wèn)題，也就是分別對(duì) w 和 b 求導(dǎo)后另其為 0 旧找。這樣就求得到了最小化了

那么我們剩下最大化問(wèn)題溺健，最大化問(wèn)題我們依舊可以轉(zhuǎn)換為最小化問(wèn)題，最簡(jiǎn)單就的取反值嘛钮蛛，事實(shí)上也確實(shí)是這么做的鞭缭，那么我們又得到了一個(gè)最小化問(wèn)題，既然是最小化問(wèn)題魏颓，那么我們?cè)俅问褂脤?duì)偶來(lái)求解岭辣，而這次的約束條件則是使用第一次最小化問(wèn)題得來(lái)的解，也就是拿第一次最小化后的解來(lái)作為這次最小化的約束條件

最終的優(yōu)化問(wèn)題是甸饱，也就是對(duì)求解下面的約束問(wèn)題沦童，我們就求得了解

最終約束問(wèn)題.jpg

我們可以從上面的式子中看出，式子是跟數(shù)據(jù)集的數(shù)量 N 存在關(guān)系的叹话，也就是 N 影響了訓(xùn)練的輪數(shù)偷遗，N 越多，我們需要處理越多次驼壶。因?yàn)橛羞@一層的關(guān)系氏豌，所以支持向量機(jī)在數(shù)據(jù)量少的時(shí)候也能得到很好的分類性能，前提是數(shù)據(jù)集是優(yōu)質(zhì)的

那么這樣热凹，第二次的對(duì)偶問(wèn)題的最優(yōu)解就是原始問(wèn)題的最優(yōu)解

書中給出了最優(yōu)化之后 w 和 b 的表達(dá)式箩溃，那么我們?cè)谇蟪?a 之后，求出w 和 b 從而得到超平面

SVM與數(shù)據(jù)集

書里面有一句話需要注意Ｂ掂帧；林肌！在P107

w 和 b只依賴于訓(xùn)練數(shù)據(jù)中對(duì)應(yīng)的 ai > 0的樣本點(diǎn)股冗，而其他樣本點(diǎn)對(duì) w 和 b 沒(méi)有影響霹陡，我們將訓(xùn)練數(shù)據(jù)中對(duì)應(yīng)于 ai > 0的實(shí)例點(diǎn)稱之為支持向量

這句話解釋了為什么支持向量機(jī)只需要少量的數(shù)據(jù)樣本就能得到了很好的效果。

書中 105 頁(yè)有以下式子：
（筆者對(duì) 對(duì)偶的kkt條件不熟悉，是當(dāng)成結(jié)論來(lái)用烹棉，有需要的讀者自行查閱資料攒霹，）
由KKT條件推導(dǎo)得（可以手動(dòng)推導(dǎo)得到）

線性可分kkt條件.jpg

因?yàn)閹缀尉嚯x最近的點(diǎn)就是函數(shù)間隔最小的點(diǎn)(如果這一點(diǎn)沒(méi)理解的話參考附錄鏈接)，根據(jù)上面的式子浆洗，我們知道：

數(shù)量.png

由上面可知催束，我們只需要那些距離超平面最近的點(diǎn)就可以了，其余的點(diǎn)是沒(méi)有效果的伏社，如果我們有這樣的數(shù)據(jù)集(距離超平面距離最小)就可以訓(xùn)練出很好的SVM

總結(jié)

1. 寫出表達(dá)式
2. 使用距離(間隔)來(lái)表示確信度
3. 最大化距離超平面最近的點(diǎn)的函數(shù)間隔
4. 使用兩次對(duì)偶問(wèn)題來(lái)求解函數(shù)間隔的約束問(wèn)題

線性支持向量機(jī)

有些數(shù)據(jù)集具有一些特點(diǎn)點(diǎn)抠刺，這些特異點(diǎn)不滿足線性可分
可理解為：

1. 明明是正例，但它卻在超平面的反例區(qū)域內(nèi)
2. 明明是反例摘昌，但它卻在超平面的正例區(qū)域內(nèi)
3. 特異點(diǎn)在函數(shù)間隔小于1的范圍內(nèi)
   以上的點(diǎn)都是特異點(diǎn)速妖，而我們需要加入松弛變量來(lái)讓他們變得線性可分，為什么加入松弛變量之后就線性可分呢聪黎？筆者有一種簡(jiǎn)單粗暴的理解：就是加入松弛變量后相當(dāng)于讓他們的函數(shù)間隔變得更小罕容，小于1的點(diǎn)我也當(dāng)你是支持向量。
   因?yàn)檫@種數(shù)據(jù)集不能用一個(gè)簡(jiǎn)單的超平面就把它們分開稿饰，所以沒(méi)有可分倆字了锦秒，是線性支持向量機(jī)

約束條件

通過(guò)一系列推導(dǎo)，書中P110-P111給出了我們最終需要優(yōu)化的對(duì)偶問(wèn)題

線性約束條件.jpg

同理喉镰，結(jié)合線性可分支持向量機(jī)章節(jié) 的 SVM與數(shù)據(jù)集小節(jié)旅择，按照書中P111的式子7.52我們可以推導(dǎo)出以下關(guān)系，這個(gè)關(guān)系很重要梧喷，下一節(jié)的難點(diǎn)會(huì)用到，滿足下面關(guān)系的點(diǎn)都是滿足KKT條件的點(diǎn)脖咐。

線性KKT條件.png

這里需要注意铺敌，每一個(gè)點(diǎn)(xi,yi)都會(huì)有一個(gè)ai與之對(duì)應(yīng)，如果這些點(diǎn)的ai不滿足下面的條件屁擅，那么說(shuō)明這個(gè)點(diǎn)的ai還不是最優(yōu)化的偿凭，需要通過(guò)某種辦法進(jìn)行優(yōu)化

注意！Ｅ筛琛弯囊！在解線性支持向量機(jī) 時(shí)，我們需要選定一個(gè)懲罰參數(shù) C胶果，這個(gè)是我們需要手動(dòng)選擇的

最后 w 和 b 的表達(dá)式請(qǐng)查看書中的P110-P111匾嘱，這里不多做贅述，書上已經(jīng)講得非常好了

其實(shí)P112給了我們一個(gè)更加簡(jiǎn)潔的公式來(lái)表示超平面早抠，如下：

可見(jiàn)這個(gè)公式直接去掉了 w霎烙，使用了 ai 來(lái)直接表示公式中w

合頁(yè)函數(shù)

線性支持向量機(jī) 優(yōu)化的另外一種方法就是最小化下面的式子

線性目標(biāo)函數(shù).jpg

書中P114給出了，最小化該式子就是最小化對(duì)偶問(wèn)題

第 1 項(xiàng)被稱為合頁(yè)損失函數(shù)

合頁(yè)函數(shù).jpg

第 2 項(xiàng)是正則化項(xiàng)，也就是懲罰項(xiàng)

懲罰項(xiàng).jpg

非線性支持向量機(jī)

有些數(shù)據(jù)集是無(wú)法通過(guò)簡(jiǎn)單的線性超平面來(lái)分類悬垃，所以我們需要將這些數(shù)據(jù)集映射到線性空間游昼，意思就是讓這些非線性分布的數(shù)據(jù)集映射到一個(gè)線性分布的空間

核函數(shù)

映射數(shù)據(jù)集的手段是找到一個(gè)映射函數(shù)來(lái)映射數(shù)據(jù)集。但在書中P116中講到尝蠕，使用核函數(shù)我們可以不用求得映射函數(shù)就能映射數(shù)據(jù)集

附錄中的《關(guān)于核函數(shù)的一些思考》寫得非常好烘豌，有需要的讀者可以參考一下

這里簡(jiǎn)要說(shuō)一下筆者的理解：核函數(shù)的作用就是將數(shù)據(jù)在低緯度的空間映射到高緯度的空間，從而將數(shù)據(jù)集線性分開看彼，然后我們求得高緯度空間的超平面來(lái)分開高緯度空間中的數(shù)據(jù)集廊佩，從而實(shí)現(xiàn)了使用線性超平面求解非線性數(shù)據(jù)集

那怎么判定一個(gè)給定的函數(shù) K(x,z) 是核函數(shù)的？其實(shí)就是證明這個(gè)函數(shù)是正定核函數(shù)闲昭，證明過(guò)程復(fù)雜罐寨，請(qǐng)閱讀書中P118

當(dāng)然啦，類似筆者這種水平是無(wú)法求解到核函數(shù)的序矩，但是好在有一些先賢幫我們找出了一些常用核函數(shù)鸯绿，比如高斯核函數(shù)，多項(xiàng)式核函數(shù)等等簸淀。

約束條件

根據(jù)書中推導(dǎo)瓶蝴，我們能夠得到最后的最優(yōu)化問(wèn)題，如下：

非線性約束條件.jpg

其實(shí)就是將 x 的部分換成了核函數(shù)租幕，按照這樣的道理舷手，最后 w 和 b 的解也是將 X 換位核函數(shù)

SMO算法

上面我已經(jīng)得出了w 和 b 的表達(dá)式，但是它們兩者都和 ai 掛鉤劲绪，我們需要求出 ai 才能求出它們男窟，而 SMO算法 就是求出 ai 的方法

附錄《SMO算法剖析》講得非常不錯(cuò)，讀者們可以閱讀一下贾富。

下面筆者將一下這里面需要注意的細(xì)節(jié)

SMO 算法的過(guò)程大致是：

1. 找出 2 個(gè) ai歉眷，而其他的參數(shù)則固定為常量（這種方法類似坐標(biāo)上升法）
2. 不斷的優(yōu)化這 2 個(gè) ai ，直到這 2 個(gè) ai 滿足 KKT條件
3. 再找出其他的 2 個(gè)ai颤枪，進(jìn)行同樣的處理汗捡。

假設(shè)我們找到了 2 個(gè)ai，分別是a1 和 a2畏纲，然后將最優(yōu)化問(wèn)題轉(zhuǎn)換為轉(zhuǎn)換為關(guān)于這 2 個(gè)參數(shù)的函數(shù)扇住，也就是最優(yōu)化函數(shù)轉(zhuǎn)換為W(a1,a2)，我們最小化這個(gè)函數(shù)就行盗胀，而這個(gè)函數(shù)通過(guò)關(guān)系式可以轉(zhuǎn)換為 a2 的一元函數(shù) W(a2)艘蹋，所以我們能夠求解得到 a2，如下：

a2unc.jpg

其中的 new unc 表示的是說(shuō) a2 還沒(méi)確定其值（官方的說(shuō)法叫做裁剪）票灰。

為什么叫沒(méi)確定其值簿训？
因?yàn)?a2 不是什么數(shù)都能取的咱娶，因?yàn)?ai 本身就有限制，求出的a2可能會(huì)超出取值范圍强品，所以我們要將a2變成取值范圍內(nèi)的數(shù)膘侮。

如何找到 a2 的取值范圍？附錄鏈接已經(jīng)解答了這個(gè)問(wèn)題的榛，筆者不多做贅述琼了，給大家公式看看

a2求法.jpg

上面有帶 old 的a1 和 a2 ，是什么意思呢夫晌，old 從哪里來(lái)呢雕薪？其實(shí)我們需要實(shí)現(xiàn)對(duì)所有的 ai 都初始化為 0，再進(jìn)行計(jì)算晓淀，所以old 就好理解啦所袁，當(dāng)然是前面一次的值了

那么我們還剩下一個(gè)問(wèn)題，如何尋找這 2 個(gè)參數(shù)呢凶掰？
書中講得比較晦澀燥爷，筆者自己的理解如下：
找出 2 個(gè)參數(shù)需要進(jìn)行 2 層循環(huán)
一、內(nèi)層循環(huán)
內(nèi)層循環(huán)的為了找到 1 個(gè)違反 KKT條件的樣本點(diǎn)a1懦窘，注意了前翎，是違反KKT條件

1. 初始化所有 ai 為0

2. 遍歷整個(gè)樣本集計(jì)算符合KKT條件的點(diǎn)，也就是如下圖所示的條件

   
   
   非線性KKT..png

但是有 3 個(gè)條件畅涂，哪一個(gè)條件優(yōu)先判斷呢港华？
1、優(yōu)先找出yg(x)=1 的樣本點(diǎn)午衰，也就是支持向量點(diǎn)立宜，并查看這些點(diǎn)的ai是否滿足0<ai<C
2、如果沒(méi)找到臊岸，那么在判斷其余的兩個(gè)條件橙数，筆者的理解是隨便選擇 1 項(xiàng)優(yōu)先判斷，或者 2 項(xiàng)一起判斷

二扇单、內(nèi)層循環(huán)
經(jīng)過(guò)內(nèi)層循環(huán)后我們能找到一個(gè)樣本點(diǎn)是嚴(yán)重違反KKT條件的商模，在此基礎(chǔ)上我們?cè)龠M(jìn)行 1 次內(nèi)層循環(huán)奠旺，內(nèi)存循環(huán)是為了找到一個(gè)樣本點(diǎn)a2蜘澜，這個(gè)樣本點(diǎn)它有足夠大的變化

1. 因?yàn)榇_定了a1，所以可以計(jì)算出E1
2. 遍歷整個(gè)樣本集找出 |E1-Ei| 最大的ai作為a2
   這里需要注意一下如果 E1 是負(fù)的响疚，那么選擇最大的 Ei 作為 E2鄙信，如果 E1 是正的，則選擇最小的 Ei 作為 E2

通過(guò)上面的查找忿晕，我們能夠確定出一組a1装诡、a2，然后我們對(duì)這組 a1、a2 用我們上面的公式進(jìn)行優(yōu)化鸦采，直到都滿足 KKT條件宾巍。根據(jù)書中P129-P130所講，優(yōu)化迭代 1 次a1渔伯、a2后我們都需要重新計(jì)算 b 跟 E1顶霞、E2 的值，用于下一次迭代锣吼。

當(dāng)我們優(yōu)化完一組 a1选浑、a2 之后再對(duì)下一組進(jìn)行優(yōu)化，當(dāng)優(yōu)化完所有的ai后玄叠，我們的b也就隨之確定了古徒，最終完成我們的算法

后語(yǔ)

總算說(shuō)完了，但筆者也只是講了SVM的冰山一角读恃，盡量將筆者在閱讀《統(tǒng)計(jì)學(xué)習(xí)方法》中的SVM章節(jié)時(shí)遇到的重難點(diǎn)給記錄下來(lái)隧膘，希望能夠幫助到跟我一樣遇到困難的。當(dāng)然了狐粱，有些東西使用文字描述實(shí)在不易舀寓，還是需要各位讀者去推導(dǎo)，去計(jì)算肌蜻，這樣才能有心領(lǐng)神會(huì)互墓。因?yàn)楸疚闹攸c(diǎn)在于疏導(dǎo)思路，所以有些地方并不會(huì)講得非常清楚蒋搜，甚至有些地方還需要讀者自行推導(dǎo)公式篡撵，但筆者也是自己推導(dǎo)過(guò)來(lái)的。相信各位讀者結(jié)合《統(tǒng)計(jì)學(xué)習(xí)方法》的內(nèi)容自己去推導(dǎo)很快能夠得到答案的豆挽。當(dāng)然育谬，《統(tǒng)計(jì)學(xué)習(xí)方法》中的SVM筆者感覺(jué)也比較初級(jí)，許多地方只給結(jié)論不給過(guò)程帮哈，但是我相信膛檀，能夠理解到里面的內(nèi)容，應(yīng)該是SVM入門了吧娘侍，但也僅僅是入門咖刃，畢竟光是SVM就有一本導(dǎo)論可以閱讀了。

以上就是SVM的簡(jiǎn)單的理論記錄憾筏，畢竟SVM博大精深嚎杨，關(guān)于動(dòng)手部分就需要各位讀者自行找代碼去閱讀運(yùn)行了

附錄

SVM幾何間隔計(jì)算：https://www.zhihu.com/question/20466147/answer/197520556
函數(shù)間隔為什么可以為1：https://www.zhihu.com/question/64568136/answer/257874428
關(guān)于核函數(shù)的一些思考：http://www.reibang.com/p/70426f1a468e
SMO算法剖析：https://blog.csdn.net/luoshixian099/article/details/51227754
關(guān)于SVM數(shù)學(xué)細(xì)節(jié)邏輯的個(gè)人理解三部曲：https://www.cnblogs.com/xxrxxr/p/7538430.html