一、線性分類器：

首先給出一個非常非常簡單的分類問題（線性可分）挠锥，我們要用一條直線漩怎，將下圖中黑色的點和白色的點分開勋颖，很顯然，圖上的這條直線就是我們要求的直線之一（可以有無數(shù)條這樣的直線）

假如說勋锤，我們令黑色的點 = -1饭玲， 白色的點 =? +1，直線f(x) = w.x +

b叁执，這兒的x茄厘、w是向量矮冬，其實寫成這種形式也是等價的f(x) = w1x1 + w2x2 … + wnxn + b,

當(dāng)向量x的維度=2的時候，f(x) 表示二維空間中的一條直線次哈， 當(dāng)x的維度=3的時候胎署，f(x) 表示3維空間中的一個平面，當(dāng)x的維度=n

> 3的時候窑滞，表示n維空間中的n-1維超平面琼牧。這些都是比較基礎(chǔ)的內(nèi)容，如果不太清楚哀卫，可能需要復(fù)習(xí)一下微積分巨坊、線性代數(shù)的內(nèi)容。

剛剛說了此改，我們令黑色白色兩類的點分別為+1,

-1趾撵，所以當(dāng)有一個新的點x需要預(yù)測屬于哪個分類的時候，我們用sgn(f(x))带斑，就可以預(yù)測了鼓寺，sgn表示符號函數(shù)，當(dāng)f(x) >

0的時候勋磕，sgn(f(x)) = +1, 當(dāng)f(x) < 0的時候sgn(f(x)) = –1妈候。

但是，我們怎樣才能取得一個最優(yōu)的劃分直線f(x)呢挂滓？下圖的直線表示幾條可能的f(x)

一個很直觀的感受是苦银，讓這條直線到給定樣本中最近的點最遠(yuǎn)，這句話讀起來比較拗口赶站，下面給出幾個圖幔虏，來說明一下：

第一種分法：

第二種分法：

這兩種分法哪種更好呢？從直觀上來說贝椿，就是分割的間隙越大越好想括，把兩個類別的點分得越開越好。就像我們平時判斷一個人是男還是女烙博，就是很難出現(xiàn)分錯的情況瑟蜈，這就是男、女兩個類別之間的間隙非常的大導(dǎo)致的渣窜，讓我們可以更準(zhǔn)確的進(jìn)行分類铺根。在SVM中，稱為Maximum Marginal乔宿，是SVM的一個理論基礎(chǔ)之一位迂。選擇使得間隙最大的函數(shù)作為分割平面是由很多道理的，比如說從概率的角度上來說，就是使得置信度最小的點置信度最大（聽起來很拗口）掂林，從實踐的角度來說臣缀，這樣的效果非常好，等等党饮。這里就不展開講肝陪，作為一個結(jié)論就ok了，:)

上圖被紅色和藍(lán)色的線圈出來的點就是所謂的支持向量(support vector)刑顺。

上圖就是一個對之前說的類別中的間隙的一個描述氯窍。Classifier Boundary就是f(x)，紅色和藍(lán)色的線（plus

plane與minus plane）就是support vector所在的面蹲堂，紅色狼讨、藍(lán)色線之間的間隙就是我們要最大化的分類間的間隙。

這里直接給出M的式子：（從高中的解析幾何就可以很容易的得到了柒竞，也可以參考后面Moore的ppt）

另外支持向量位于wx + b = 1與wx + b = -1的直線上政供，我們在前面乘上一個該點所屬的類別y（還記得嗎?y不是+1就是-1），就可以得到支持向量的表達(dá)式為：y(wx + b) = 1朽基，這樣就可以更簡單的將支持向量表示出來了布隔。

當(dāng)支持向量確定下來的時候，分割函數(shù)就確定下來了稼虎，兩個問題是等價的衅檀。得到支持向量，還有一個作用是霎俩，讓支持向量后方那些點就不用參與計算了哀军。這點在后面將會更詳細(xì)的講講。

在這個小節(jié)的最后打却，給出我們要優(yōu)化求解的表達(dá)式：

||w||的意思是w的二范數(shù)杉适，跟上面的M表達(dá)式的分母是一個意思，之前得到柳击，M = 2 / ||w||猿推，最大化這個式子等價于最小化||w||,

另外由于||w||是一個單調(diào)函數(shù)，我們可以對其加入平方捌肴，和前面的系數(shù)彤守，熟悉的同學(xué)應(yīng)該很容易就看出來了，這個式子是為了方便求導(dǎo)哭靖。

這個式子有還有一些限制條件，完整的寫下來侈离，應(yīng)該是這樣的：（原問題）

s.t的意思是subject

to试幽，也就是在后面這個限制條件下的意思，這個詞在svm的論文里面非常容易見到。這個其實是一個帶約束的二次規(guī)劃(quadratic

programming,

QP)問題铺坞，是一個凸問題起宽，凸問題就是指的不會有局部最優(yōu)解，可以想象一個漏斗济榨，不管我們開始的時候?qū)⒁粋€小球放在漏斗的什么位置坯沪，這個小球最終一定可以掉出漏斗，也就是得到全局最優(yōu)解擒滑。s.t.后面的限制條件可以看做是一個凸多面體腐晾，我們要做的就是在這個凸多面體中找到最優(yōu)解。這些問題這里不展開丐一，因為展開的話藻糖，一本書也寫不完。如果有疑問請看看wikipedia库车。

二巨柒、轉(zhuǎn)化為對偶問題，并優(yōu)化求解:

這個優(yōu)化問題可以用拉格朗日乘子法去解柠衍，使用了KKT條件的理論洋满，這里直接作出這個式子的拉格朗日目標(biāo)函數(shù)：

求解這個式子的過程需要拉格朗日對偶性的相關(guān)知識（另外pluskid也有一篇文章專門講這個問題），并且有一定的公式推導(dǎo)珍坊，如果不感興趣牺勾，可以直接跳到后面用藍(lán)色公式表示的結(jié)論，該部分推導(dǎo)主要參考自plukids的文章垫蛆。

首先讓L關(guān)于w禽最，b最小化，分別令L關(guān)于w袱饭，b的偏導(dǎo)數(shù)為0川无，得到關(guān)于原問題的一個表達(dá)式

將兩式帶回L(w,b,a)得到對偶問題的表達(dá)式

新問題加上其限制條件是（對偶問題）:

這個就是我們需要最終優(yōu)化的式子。至此虑乖，得到了線性可分問題的優(yōu)化式子懦趋。

求解這個式子，有很多的方法疹味，比如SMO等等仅叫，個人認(rèn)為，求解這樣的一個帶約束的凸優(yōu)化問題與得到這個凸優(yōu)化問題是比較獨立的兩件事情糙捺，所以在這篇文章中準(zhǔn)備完全不涉及如何求解這個話題诫咱，如果之后有時間可以補上一篇文章來談?wù)?)。

三洪灯、線性不可分的情況（軟間隔）：

接下來談?wù)劸€性不可分的情況坎缭，因為線性可分這種假設(shè)實在是太有局限性了：

下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區(qū)域，每個區(qū)域只包含一種顏色的點掏呼。

要想在這種情況下的分類器坏快，有兩種方式，一種是用曲線去將其完全分開憎夷，曲線就是一種非線性的情況莽鸿，跟之后將談到的核函數(shù)有一定的關(guān)系：

另外一種還是用直線，不過不用去保證可分性拾给，就是包容那些分錯的情況祥得，不過我們得加入懲罰函數(shù)，使得點分錯的情況越合理越好鸣戴。其實在很多時候啃沪，不是在訓(xùn)練的時候分類函數(shù)越完美越好，因為訓(xùn)練函數(shù)中有些數(shù)據(jù)本來就是噪聲窄锅，可能就是在人工加上分類標(biāo)簽的時候加錯了创千，如果我們在訓(xùn)練（學(xué)習(xí)）的時候把這些錯誤的點學(xué)習(xí)到了，那么模型在下次碰到這些錯誤情況的時候就難免出錯了（假如老師給你講課的時候入偷，某個知識點講錯了追驴，你還信以為真了，那么在考試的時候就難免出錯）疏之。這種學(xué)習(xí)的時候?qū)W到了“噪聲”的過程就是一個過擬合（over-fitting）殿雪，這在機器學(xué)習(xí)中是一個大忌，我們寧愿少學(xué)一些內(nèi)容锋爪，也堅決杜絕多學(xué)一些錯誤的知識丙曙。還是回到主題，用直線怎么去分割線性不可分的點：

我們可以為分錯的點加上一點懲罰其骄，對一個分錯的點的懲罰函數(shù)就是這個點到其正確位置的距離：

在上圖中亏镰，藍(lán)色、紅色的直線分別為支持向量所在的邊界拯爽，綠色的線為決策函數(shù)索抓，那些紫色的線表示分錯的點到其相應(yīng)的決策面的距離，這樣我們可以在原函數(shù)上面加上一個懲罰函數(shù)毯炮，并且?guī)掀湎拗茥l件為：

公式中藍(lán)色的部分為在線性可分問題的基礎(chǔ)上加上的懲罰函數(shù)部分逼肯，當(dāng)xi在正確一邊的時候，ε=0桃煎，R為全部的點的數(shù)目篮幢，C是一個由用戶去指定的系數(shù)，表示對分錯的點加入多少的懲罰为迈，當(dāng)C很大的時候洲拇，分錯的點就會更少奈揍，但是過擬合的情況可能會比較嚴(yán)重，當(dāng)C很小的時候赋续，分錯的點可能會很多，不過可能由此得到的模型也會不太正確另患，所以如何選擇C是有很多學(xué)問的纽乱，不過在大部分情況下就是通過經(jīng)驗嘗試得到的。

接下來就是同樣的昆箕，求解一個拉格朗日對偶問題鸦列，得到一個原問題的對偶問題的表達(dá)式：

藍(lán)色的部分是與線性可分的對偶問題表達(dá)式的不同之處。在線性不可分情況下得到的對偶問題鹏倘，不同的地方就是α的范圍從[0, +∞)薯嗤，變?yōu)榱薣0, C]，增加的懲罰ε沒有為對偶問題增加什么復(fù)雜度纤泵。

四骆姐、核函數(shù)：

剛剛在談不可分的情況下，提了一句捏题，如果使用某些非線性的方法玻褪，可以得到將兩個分類完美劃分的曲線，比如接下來將要說的核函數(shù)公荧。

我們可以讓空間從原本的線性空間變成一個更高維的空間带射，在這個高維的線性空間下，再用一個超平面進(jìn)行劃分循狰。這兒舉個例子窟社，來理解一下如何利用空間的維度變得更高來幫助我們分類的（例子以及圖片來自pluskid的kernel函數(shù)部分）：

下圖是一個典型的線性不可分的情況

但是當(dāng)我們把這兩個類似于橢圓形的點映射到一個高維空間后，映射函數(shù)為：

用這個函數(shù)可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)绪钥，并且對映射后的坐標(biāo)加以旋轉(zhuǎn)之后就可以得到一個線性可分的點集了灿里。

用另外一個哲學(xué)例子來說：世界上本來沒有兩個完全一樣的物體，對于所有的兩個物體昧识，我們可以通過增加維度來讓他們最終有所區(qū)別钠四，比如說兩本書，從(顏色跪楞，內(nèi)容)兩個維度來說缀去，可能是一樣的，我們可以加上作者這個維度甸祭，是在不行我們還可以加入頁碼缕碎，可以加入擁有者，可以加入購買地點池户，可以加入筆記內(nèi)容等等咏雌。當(dāng)維度增加到無限維的時候凡怎，一定可以讓任意的兩個物體可分了。

回憶剛剛得到的對偶問題表達(dá)式：

我們可以將紅色這個部分進(jìn)行改造赊抖，令：

這個式子所做的事情就是將線性的空間映射到高維的空間,k(x, xj)有很多種统倒，下面是比較典型的兩種：

上面這個核稱為多項式核，下面這個核稱為高斯核氛雪，高斯核甚至是將原始空間映射為無窮維空間房匆，另外核函數(shù)有一些比較好的性質(zhì)，比如說不會比線性條件下增加多少額外的計算量报亩，等等浴鸿，這里也不再深入。一般對于一個問題弦追，不同的核函數(shù)可能會帶來不同的結(jié)果岳链，一般是需要嘗試來得到的。

五劲件、一些其他的問題：

1）如何進(jìn)行多分類問題：

上面所談到的分類都是2分類的情況掸哑，當(dāng)N分類的情況下，主要有兩種方式寇仓，一種是1 vs (N – 1)一種是1 vs 1举户，前一種方法我們需要訓(xùn)練N個分類器，第i個分類器是看看是屬于分類i還是屬于分類i的補集（出去i的N-1個分類）遍烦。

后一種方式我們需要訓(xùn)練N * (N – 1) / 2個分類器俭嘁，分類器(i,j)能夠判斷某個點是屬于i還是屬于j。

這種處理方式不僅在SVM中會用到服猪，在很多其他的分類中也是被廣泛用到供填，從林教授（libsvm的作者）的結(jié)論來看，1 vs 1的方式要優(yōu)于1 vs (N – 1)罢猪。

2）SVM會overfitting嗎近她？

SVM避免overfitting，一種是調(diào)整之前說的懲罰函數(shù)中的C膳帕，另一種其實從式子上來看粘捎，min

||w||^2這個看起來是不是很眼熟？在最小二乘法回歸的時候危彩，我們看到過這個式子攒磨，這個式子可以讓函數(shù)更平滑，所以SVM是一種不太容易o(hù)ver-fitting的方法汤徽。

參考文檔：

主要的參考文檔來自4個地方飞蹂，wikipedia（在文章中已經(jīng)給出了超鏈接了）茧跋，pluskid關(guān)于SVM的博文，Andrew moore的ppt（文章中不少圖片都是引用或者改自Andrew Moore的ppt，以及prml