通俗易懂的支持向量機(jī)SVM
SVM 的原理和目標(biāo)
幾個基本概念
線性可分SVM——線性 SVM——非線性 SVM
1、線性可分SVM歹颓，表示可以用一根線非常清晰的劃分兩個區(qū)域殃姓；線到支持向量的距離 d 就是最小的。
2童芹、線性 SVM涝滴，表示用一根線劃分區(qū)域后绣版，可能存在誤判點(diǎn)，但還是線性的歼疮；線到支持向量的距離不一定是最小的杂抽，但忽略其他非規(guī)則的支持向量。
3韩脏、非線性 SVM缩麸，表示使用核函數(shù)之后，把低維的非線性轉(zhuǎn)換為高維線性
復(fù)習(xí)下函數(shù)和向量
假如有個方程
y=x/2-1可以變化為 -x+2y+2=0
f(x,y)=-x+2y+2,其中紅色的就是他的法向量
寫成向量的形式：
改寫下
前面的系數(shù)項(xiàng)可以令其為
x赡矢，y 的那一項(xiàng)杭朱，其實(shí)可以演變?yōu)?n行，所以可以簡化為
后面的2是常數(shù)項(xiàng)济竹，用 b 代替
這樣處理完痕檬，我們的式子可以修改為
其中 w 就是我們的法線方向，x 是我們的參數(shù)送浊，b 是截距項(xiàng)。
此時如果有個 帶入式子得到是正值丘跌，那么就在法線的同方向袭景；否則在法線的逆方向。如果等于0闭树，那么該點(diǎn)就在線上耸棒。
f(x1，x2)代表一個線报辱，f(x1,x2,x3)代表一個面与殃，如果是 n 維的，那么給他一個牛逼的名稱“超平面”，由于這個名字太牛逼幅疼，所以低維的也叫超平面米奸。
計算過程和算法步驟
接入給定一個特征空間上的訓(xùn)練數(shù)據(jù)集，
其中
這里為什么 y 取值+1和-1爽篷？
因?yàn)檫@樣取值方便后面的推導(dǎo)悴晰，如果非要把+1和-1換為+3和-8什么的，其實(shí)沒有什么不同逐工。后面推導(dǎo)不受影響铡溪。
寫成+1和-1的話，那么我們的,那么泪喊，兩邊同時乘以 yj棕硫，得到，這樣我們就可以很方便的得到兩個標(biāo)記相乘等于兩個標(biāo)記相除袒啼。如果選擇不同的值饲帅，就得不到上面的式子。
推導(dǎo)目標(biāo)函數(shù)
分割平面：
訓(xùn)練集：x1瘤泪，x2灶泵，x3......
目標(biāo)集：y1，y2,y3...... y屬于1和-1的集合
新數(shù)據(jù)的分類：sign(y(x))
根據(jù)題設(shè)
其中就是一個映射对途，就是原封不動一階映射赦邻，二階映射的例子如下：
{1，x1实檀，x2,x3}==>{1,x1,x2,x3,x12,x22,x3^2,x1x2,x2x3,x1x3}把原來的四維轉(zhuǎn)換成10維惶洲。
接下來就有
其中：y(x)為預(yù)測值，y 為真實(shí)值膳犹，他們互為推導(dǎo)恬吕。最終他們的乘積大于0.
從而可以得到下面的公式（其實(shí)是點(diǎn)到直線的距離）
我們的目標(biāo)函數(shù)：
解釋：對于所有的樣本到平面的距離求最近，也就是最小值须床，然后得到的這些平面里面根據(jù) w 和 b再求 最大值铐料。
如何優(yōu)化
轉(zhuǎn)換等價問題，直接來解決的確棘手豺旬。先來看
線性可分的這個圖
可以看出钠惩，有3個支持向量。
上虛線五角星的那個點(diǎn)到紅線的距離是一個值族阅，而且是最近的一個距離篓跛，假如該距離為 d=3，那么也就是
兩邊同時除以3
也就是范數(shù) w 乘以3坦刀，但是對整個方程來說位置是不發(fā)生變化的愧沟。（其實(shí) w 是我們要求的蔬咬，可以隨便設(shè)置，總能得到右邊為1）
打個比方沐寺，假如有個方程 f(x,y)=ax+by+c=0,有個點(diǎn)到該線的距離為d林艘，那么我們可以除以 d，使得到改線的距離為1芽丹，可以認(rèn)為是距離歸一處理北启。那么同理我們總能得到一個 w，使得五角星那個點(diǎn)到紅線的距離為1拔第，就得有個約束條件就是咕村，好了，現(xiàn)在這個值要求取最小值蚊俺，而且又是大于等于1懈涛，那么就直接取1就是最小值。
那么新的目標(biāo)函數(shù)就變化為
一個數(shù)的倒數(shù)求最大泳猬，也就是這個數(shù)求最小批钠，也就是求這個數(shù)的平方最小，也就是求這個數(shù)平方的一半最小得封，好了埋心，公式繼續(xù)演變?yōu)椋?br>
這個就是我們需要求解的目標(biāo)，假如 n=10000（n 是樣本個數(shù)）忙上，也就是有1萬個下面的約束條件下求上式子的最小值拷呆，對于這個目標(biāo)函數(shù)如何來求呢？帶有約束條件的求極值問題疫粥，就想到拉格朗日乘子法茬斧。
拉格朗日乘子法和KKT條件
其實(shí)拉格朗日乘子法的約束條件是要求等于某個條件，而這里是不等于梗逮，也可以這么做项秉。
這個式子的暫且放一邊，我們來梳理下拉格朗日乘子法慷彤。
假設(shè)有個函數(shù)要求最小值娄蔼，min f(x)，其中有兩部分要求瞬欧，第一部分是不等式部分：
這里所有條件的方向可以修改為
贷屎，因?yàn)榭梢栽黾迂?fù)號來改變方向，不是什么大問題艘虎。
最終也就是
第二部分是等式部分，記為
本科階段的拉格朗日乘子法只有等式部分咒吐，現(xiàn)在這里增加了不等式部分野建，針對不等式部分属划，做如下操作。
先設(shè)置一系列的候生，構(gòu)造一個新的函數(shù)
這個就是拉格朗日函數(shù)同眯。對于這個函數(shù)來說，以w為變量唯鸭，對其求導(dǎo)數(shù)须蜗，可得系數(shù)為,在二維坐標(biāo)上就是一條線，同理等目溉。
將他們畫在一張坐標(biāo)系里面明肮，
對于這3個線段求取每個 x 點(diǎn)的最小值，得到的是紅色的這個區(qū)域的線缭付，同理柿估，n 條這樣的線也可以得到這樣一個凹函數(shù)，凹函數(shù)必有最大值陷猫，并且是全局最大秫舌。
那么到底是什么？
繼續(xù)看下
因?yàn)?/p>
而绣檬，所以
因?yàn)?div id="ersnjeu" class="image-package">
image
足陨，所以無論 lambda 取什么值，
,這就是說 G(x)是一個 f(x)加上一個負(fù)數(shù)娇未，那么也就是說 G(x)的最大也就是 f(x)了墨缘。
，那么要求 minf(x)也就是求
可以找到他的對偶函數(shù)
再回到我們原來的式子忘蟹，
這個式子比上面的理論要簡單點(diǎn)飒房，沒有等式約束。那么他的原始極小極大問題
他的對偶問題為極大極小問題
為了求最小值媚值，我們需要對w 和 b 分別求導(dǎo)狠毯，并且使之為0，
其中
最終得到
也就是
接下來褥芒，對 b 求偏導(dǎo)數(shù)嚼松，得到
w 不就是法向量嘛，其中包含的 alpha=0的點(diǎn)不是支撐向量锰扶，而 alpha 不為0 的才是 SV献酗。pha(x）就是核函數(shù)，所有的這些在這里可以體現(xiàn)出來了坷牛。
歸納下：
繼續(xù)推導(dǎo)罕偎。。京闰。帶入 w 和 b颜及，剩下 alpha 的式子甩苛。
最后得到求 alpha 的式子
使用某種方法（SMO）求得 alpha，帶入 w 和 b 就可以求得 w俏站。
SMO 算法讯蒲，由條件可知，
[圖片上傳失敗...(image-ab4eb3-1526290967990)]
我們需要調(diào)節(jié)2個 alpha 參數(shù)肄扎，一大一小墨林，使得為0，滿足條件后求得 alpha 較大值犯祠，然后慢慢調(diào)節(jié)旭等，再得到一個較大值，這樣的按照序列求得最大的優(yōu)化方法叫 SMO
掉個方向雷则，得到
舉個例子看的明白些：
給定3個數(shù)據(jù)點(diǎn)辆雾，正例點(diǎn)x1=(3,3)T,x2=(4,3)T,反例點(diǎn) x3=(1,1)T, 求解線性可分的SVM。
解：目標(biāo)函數(shù)是
[圖片上傳失敗...(image-fbc4d6-1526290967990)]
根據(jù)
可得
其中正例就是 x1=(3,3,1) x2=(4,3,1);負(fù)例x3=(1,1,-1)
最后是表示 y 的值月劈。x1對應(yīng)的系數(shù) alpha1度迂，x2對應(yīng)的系數(shù)是 alpha2，x3對應(yīng)的系數(shù)是 alpha3.
將 alpha3=alpha1+alpha2帶入式子計算得到關(guān)羽 alpha1和 alpha2 的han 函數(shù)
對 alpha1和 alpha2求偏導(dǎo)令他為0猜揪，得到在（1.5惭墓，-1）這個點(diǎn)取到極值，但是改點(diǎn)不滿足 alpha2>0這個條件而姐，所以最小值在邊界上沒有達(dá)到腊凶。
令 alpha1=0，最小值 s（0拴念，2/13）=-2/13=-0.1538
令 alpha2=0钧萍，最小值 s（1/4，0）=-1/4=-0.25
所以得到s(alpha1,alpha2)在1/4,0處達(dá)到最小政鼠，此時 alpha3=alpha1+alpha2=0.25
所以 alpha1=alpha3=0.25對應(yīng)點(diǎn) x1和 x3構(gòu)成支持向量风瘦。
帶入公式：
這里 fai(xi)就是 xi
得到 w1=w2=0.5 b=-2
所以超平面為
圖形
x1的系數(shù)和x3的系數(shù)是0.25，而x2的系數(shù)是0公般，也就是說 x2沒有參與支持向量的構(gòu)建万搔，不是支持向量。
以上是線性可分官帘，那么線性不一定可分的咋辦呢瞬雹？
如圖
按照可分那就是實(shí)線，貌似虛線應(yīng)該更好刽虹。
若線性不可分酗捌，需要加入松弛因子[圖片上傳失敗...(image-8be0f1-1526290967990)]>=0，
此時約束條件變成：
當(dāng)
=0就是線性可分。
目標(biāo)函數(shù)：
這個式子中意敛，當(dāng) C 趨向無窮大的時候馅巷，
只能取0才能保證能取最小值膛虫。C 可以認(rèn)為是允許犯錯誤的容忍程度草姻，C 太大，表示對錯誤完全不能容忍稍刀，必須要線性可分撩独。從另外角度來說，C 太大账月，那么不允許犯錯誤综膀，那么過渡帶就會窄。C 小些的話局齿，過渡帶會寬些剧劝，也就是泛化能力較強(qiáng)。
歸納下：
對應(yīng)的拉格朗日函數(shù)（注意符號抓歼，ξ>=0的變化）
然后對其求偏導(dǎo)數(shù)
將三個式子帶入
把 μ消掉了
對上式子求關(guān)羽 α 的極大讥此，得到
上式右下角的條件限制了α的取值范圍是縮小了的。
進(jìn)一步整理得到對偶問題
再進(jìn)一步構(gòu)造最優(yōu)化問題
求解得 a^*
然后計算出w 和 b
注意：計算 b 的時候需要滿足α在（0谣妻，C）之間
最終求得超平面：
損失函數(shù)分析
圓圈的點(diǎn)：他們的α=C萄喳，他們是有損失的，并且哪些紅色線段表示損失值蹋半；雖然他們分的是對的他巨。但是已經(jīng)進(jìn)入敏感地帶。
方塊的星：他們的0 < α < C,是支持向量
其他點(diǎn)：α = 0
損失值=1-d减江；d 是點(diǎn)到超平面的距離染突，那么過渡帶之外的損失值為0，于是得到 SVM 損失函數(shù)圖(Hindge損失）
也就是
但得到這個最小的時候辈灼，求得新的 w 和 b份企。
我們再看下
[圖片上傳失敗...(image-faff7c-1526290967990)]
這里出現(xiàn)了損失函數(shù)，經(jīng)過變換得到新的損失函數(shù)
后面一項(xiàng)是 L2正則
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
序言：七十年代末茵休，一起剝皮案震驚了整個濱河市薪棒，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌榕莺，老刑警劉巖俐芯，帶你破解...
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異钉鸯，居然都是意外死亡吧史，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
文/潘曉璐 我一進(jìn)店門唠雕，熙熙樓的掌柜王于貴愁眉苦臉地迎上來贸营，“玉大人吨述，你說我怎么就攤上這事〕” “怎么了揣云？”我有些...
文/不壞的土叔 我叫張陵，是天一觀的道長冰啃。 經(jīng)常有香客問我工碾，道長禽笑，這世上最難降的妖魔是什么橄抹？ 我笑而不...
正文 為了忘掉前任屈梁，我火速辦了婚禮，結(jié)果婚禮上扇调，老公的妹妹穿的比我還像新娘矿咕。我一直安慰自己，他們只是感情好狼钮，可當(dāng)我...
文/花漫 我一把揭開白布碳柱。 她就那樣靜靜地躺著，像睡著了一般燃领。 火紅的嫁衣襯著肌膚如雪士聪。 梳的紋絲不亂的頭發(fā)上，一...
那天猛蔽，我揣著相機(jī)與錄音剥悟，去河邊找鬼。 笑死曼库，一個胖子當(dāng)著我的面吹牛区岗，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播毁枯，決...
文/蒼蘭香墨 我猛地睜開眼慈缔，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了种玛？” 一聲冷哼從身側(cè)響起藐鹤，我...
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎赂韵，沒想到半個月后娱节，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
正文 獨(dú)居荒郊野嶺守林人離奇死亡祭示，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
正文 我和宋清朗相戀三年肄满，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
序言：一個原本活蹦亂跳的男人離奇死亡稠歉，死狀恐怖掰担，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情怒炸，我是刑警寧澤带饱，帶...
正文 年R本政府宣布，位于F島的核電站横媚，受9級特大地震影響纠炮，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜灯蝴，卻給世界環(huán)境...
文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望孝宗。 院中可真熱鬧穷躁，春花似錦、人聲如沸因妇。這莊子的主人今日做“春日...
文/蒼蘭香墨 我抬頭看了看天上的太陽婚被。三九已至狡忙，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間址芯，已是汗流浹背灾茁。 一陣腳步聲響...
我被黑心中介騙來泰國打工， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留谷炸，地道東北人北专。 一個月前我還...
正文 我出身青樓，卻偏偏與公主長得像旬陡，于是被迫代替她去往敵國和親拓颓。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
SVM 的原理和目標(biāo) 幾個基本概念 線性可分SVM——線性 SVM——非線性 SVM 1描孟、線性可分SVM驶睦，表示可以...
【概述】 SVM訓(xùn)練分類器的方法是尋找到超平面，使正負(fù)樣本在超平面的兩側(cè)（分類正確性即“分得開”）匿醒，且樣本到超平面...
結(jié)合Scikit-learn介紹幾種常用的特征選擇方法 作者：Edwin Jarvis 特征選擇(排序)對于數(shù)據(jù)科...
【轉(zhuǎn)載】線性代數(shù)基礎(chǔ)知識 原文地址：http://blog.csdn.net/longxinchen_ml/art...
SVM支持向量機(jī) 本片文章主要記錄在學(xué)習(xí)《統(tǒng)計學(xué)習(xí)方法》中 SVM 章節(jié)的難點(diǎn)场航，不對詳細(xì)內(nèi)容進(jìn)行講解。主要是分析筆...
