一.什么是支持向量機(jī)
1、支持向量機(jī)（Support Vector Machine，常簡(jiǎn)稱為SVM）是一種 監(jiān)督式學(xué)習(xí)的方法列荔，可廣泛地應(yīng)用于統(tǒng)計(jì)分類以及回歸分析。支持向量機(jī)屬于一般化線性分類器枚尼，這族分類器的特點(diǎn)是他們能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)贴浙，因此支持向量機(jī)也被稱為最大邊緣區(qū)分類器。
2署恍、支持向量機(jī)將向量映射到一個(gè)更高維的空間里崎溃，在這個(gè)空間里建立有一個(gè)最大間隔超平面。在分開(kāi)數(shù)據(jù)的超平面的兩邊建有兩個(gè)互相平行的超平面盯质，分隔超平面使兩個(gè)平行超平面的距離最大化袁串。假定平行超平面間的距離或差距越大，分類器的總誤差越小呼巷。
3囱修、假設(shè)給定一些分屬于兩類的2維點(diǎn)，這些點(diǎn)可以通過(guò)直線分割王悍， 我們要找到一條最優(yōu)的分割線破镰，如何來(lái)界定一個(gè)超平面是不是最優(yōu)的呢?
二、求解過(guò)程
最優(yōu)超平面可以有無(wú)數(shù)種表達(dá)方式压储，即通過(guò)任意的縮放 w 和 b 鲜漩。 習(xí)慣上我們使用以下方式來(lái)表達(dá)最優(yōu)超平面。
我們令兩類的點(diǎn)分別為+1, -1集惋，所以當(dāng)有一個(gè)新的點(diǎn)x需要預(yù)測(cè)屬于哪個(gè)分類的時(shí)候宇整，我們用
sgn(f(x))，就可以預(yù)測(cè)了芋膘，sgn表示符號(hào)函數(shù)鳞青，當(dāng)f(x) > 0的時(shí)候霸饲，sgn(f(x)) = +1, 當(dāng)f(x) < 0的時(shí)候sgn(f(x)) = –1。
通過(guò)幾何學(xué)的知識(shí)臂拓，我們知道點(diǎn) x 到超平面 的距離為:
對(duì)于超平面, 表達(dá)式中的分子為1,
然后得到目標(biāo)函數(shù)
這是一個(gè)拉格朗日優(yōu)化問(wèn)題厚脉，可以通過(guò)拉格朗日乘數(shù)法得到最優(yōu)超平面的權(quán)重向量W和偏置b
三、拉格朗日對(duì)偶
如何確定w和b呢胶惰？
答案是尋找兩條邊界端或極端劃分直線中間的最大間隔（之所以要尋最大間隔是為了能更好的劃分不同類的點(diǎn)傻工，下文你將看到：為尋最大間隔，導(dǎo)出1/2||w||^2孵滞，繼而引入拉格朗日函數(shù)和對(duì)偶變量a中捆，化為對(duì)單一因數(shù)對(duì)偶變量a的求解），從而確定最終的最大間隔分類超平面hyper plane和分類函數(shù)坊饶；
拉格朗日對(duì)偶的原理
上述式子有兩個(gè)條件（等式條件和不等式條件）由此我們定義一般化的拉格朗日公式
由此我們定義一般化的拉格朗日公式
這里的P代表primal泄伪。我們?cè)O(shè)如下約束條件（primal constraints）：
如果條件不全部滿足的話，我們總可以調(diào)整
α和β使最大值出現(xiàn)正無(wú)窮匿级，即會(huì)出現(xiàn)下面情況(這里比較重要蟋滴，說(shuō)明了為什么要求最大)
因此我們可以得出如下式子：
這樣我們?cè)瓉?lái)要求的min f(w)可以轉(zhuǎn)換成求了
這個(gè)問(wèn)題就是原問(wèn)題的對(duì)偶問(wèn)題，相對(duì)于原問(wèn)題只是更換了min和max的順序痘绎，而一般更換順序的結(jié)果是
Max Min(X) <= Min Max(X)津函。然而在這里兩者相等。由此我們可以設(shè)如下
四孤页、最優(yōu)間隔分類器求解（求解過(guò)程尔苦，上兩步是鋪墊）**
在之前為了尋找最有分類器，我們提出了如下優(yōu)化問(wèn)題
在這里我們可以把約束條件改寫(xiě)成如下：
很顯然我們可以看出實(shí)線是最大間隔超平面行施，假設(shè)×號(hào)的是正例蕉堰，圓圈的是負(fù)例。在虛線上的點(diǎn)和在實(shí)線上面的兩個(gè)一共這三個(gè)點(diǎn)稱作支持向量”辏現(xiàn)在我們結(jié)合KKT條件分析下這個(gè)圖。
這個(gè)也就說(shuō)明[圖片上傳中個(gè)
gi(w)時(shí)冰寻，w處于可行域的邊界上须教，這時(shí)才是起作用的約束。
1斩芭、那我們現(xiàn)在可以構(gòu)造拉格朗日函數(shù)如下：
2轻腺、接下來(lái)我們對(duì)w和b分別求偏導(dǎo)數(shù)
3、將上式帶回到拉格朗日函數(shù)中得到：
4.優(yōu)化等式
6.最終問(wèn)題
五划乖、核函數(shù) ——高維空間映射贬养，在低維時(shí)空里解決
如下所示，無(wú)法線性標(biāo)示進(jìn)行分割琴庵，但是可以用二次函數(shù)簡(jiǎn)單分割
映射到高維空間误算，可以很容易進(jìn)行分割
在計(jì)算的時(shí)候仰美，它可以讓x和z不用通過(guò)H()映射到高維空間再計(jì)算內(nèi)積，而是直接在低維空間里計(jì)算了儿礼。
我們用K()表示核函數(shù)咖杂，那么核函數(shù)作用就是：K(x,z)=
避開(kāi)了X映射到H(X)，Y映射到H(Y)這么一個(gè)過(guò)程
線性核：
高斯核：
通過(guò)調(diào)控參數(shù)σ蚊夫，高斯核具有相當(dāng)?shù)撵`活性
六诉字、SMO算法求解α
要解決的是在參數(shù){α1, α2,...α3}上求最大值W(α)的問(wèn)題，至于xi,yi都是已知數(shù)知纷。C由我們預(yù)先設(shè)定壤圃，也是已知數(shù)。
按照坐標(biāo)上升的思路琅轧，我們首先固定除α1 以外的所有參數(shù)伍绳，然后在α2上求極值。等一下鹰晨，這個(gè)思路有問(wèn)題墨叛，因?yàn)槿绻潭?code>α1以外的所有參數(shù)，那么α2 將不再是變量（可以由其他值推出）
SMO的主要步驟如下：
- 1.選擇連個(gè)
α模蜡， 如α1漠趁、α2，選取方法使用啟發(fā)式方法忍疾，固定其他參數(shù) - 2.確定極值
W闯传，αi由αj表示
假設(shè)確定了α1、α2卤妒，則：
{α1, α2,...α3}都是已知固定值甥绿，因此為了方便，可將等式右邊標(biāo)記成實(shí)數(shù)值
當(dāng)y(i),y(j) 異號(hào)時(shí)则披，也就是一個(gè)為1共缕，一個(gè)為-1時(shí)，他們可以表示成一條直線士复，斜率為1图谷。如下圖：
當(dāng)y(i),y(j) 同號(hào)時(shí)
然后我們打算將α1用α2表示：
α2滿足以下條件：
w、b求解公式
啟發(fā)式搜索的方法和求b值的公式
[1] http://www.tuicool.com/articles/2aYryeV
[2] https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-1.html
