SVM（support victor machine）
1、支持向量機(jī)發(fā)展歷史
1963年，Vapnik在解決模式識別問題時提出了支持向量方法。起決定性作用的樣本為支持向量
1971年，Kimeldorf構(gòu)造基于支持向量構(gòu)建核空間的方法
1995年，Vapnik等人正式提出統(tǒng)計學(xué)習(xí)理論。
通俗來講，SVM是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機(jī)的學(xué)習(xí)策略便是間隔最大化，最終可轉(zhuǎn)化為一個凸二次規(guī)劃問題的求解。
二類分類模型 ——
這里我們考慮的是一個兩類的分類問題，就是將一堆數(shù)據(jù)集通過建立模型將其分成兩類，典型的二類分類模型，有neural network的感知器，
線性分類器 ——
其中，數(shù)據(jù)點用 x （ x 是 n 維向量）來表示，wT 中的 T 代表轉(zhuǎn)置，而類別用 y 來表示，可以取 1 或者 -1 ，分別代表兩個不同的類。一個線性分類器的學(xué)習(xí)目標(biāo)就是要在 n 維的數(shù)據(jù)空間中找到一個分類 超平面 ，其方程可以表示為： wTx+b=0
上面給出了線性分類的定義描述，但或許讀者沒有想過：為何用y取1 或者 -1來表示兩個不同的類別呢？其實，這個1或-1的分類標(biāo)準(zhǔn)起源于logistic回歸。
首先，講講‘間隔’的來源，如上圖所述，可以有無窮個線性分類器將數(shù)據(jù)集分開，但是如何描述最好的分類器呢？
如上圖的Margin width就是兩條邊緣之間的間距。注意，區(qū)別于求歐式空間內(nèi)兩個向量的距離（2-范數(shù)）。
2.常用的機(jī)器學(xué)習(xí)方法比較
上個世紀(jì)90年代，支持向量機(jī)獲得全面發(fā)展，在實際應(yīng)用中，獲得比較滿意的效果，成為機(jī)器學(xué)習(xí)領(lǐng)域的標(biāo)準(zhǔn)工具.
1)概率分布的方法-------------Bayes方法, GMMs 用于復(fù)雜分布建模
2)決策樹的方法（C4.5）---屬性具有明確含義時使用，一種經(jīng)典的方法
3)近鄰分類-----------------------簡單的方法，如果樣本有代表性，維數(shù)不高時好用
4)支撐向量機(jī)--------------------高維空間的小樣本學(xué)習(xí)
5)Boosting算法-----------------大量訓(xùn)練樣本下可以取得好的效果，速度很快
6)人工神經(jīng)網(wǎng)絡(luò)ANN----------大量訓(xùn)練樣本下可以取得好的效果，速度較慢
例如，手寫體數(shù)字識別例子——貝爾實驗室對美國郵政手寫數(shù)字庫進(jìn)行的實驗，該數(shù)據(jù)共包含7291個訓(xùn)練樣本，2007個測試數(shù)據(jù)，輸入數(shù)據(jù)的維數(shù)為16x16維
VC維與經(jīng)驗風(fēng)險 ———
Vapnik-Chervonenkis (VC) dimension，VC 維定義為一組函數(shù)，如平面、直線等在空間打散（任意分類）樣本的能力。
正是因為SVM關(guān)注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數(shù)是無關(guān)的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當(dāng)然，有這樣的能力也因為引入了核函數(shù)）。
結(jié)構(gòu)風(fēng)險最小化原則 ———
結(jié)構(gòu)風(fēng)險最小聽上去很陌生，但是我們從學(xué)初中物理就明白相似的概念——測量誤差與實際誤差之間的差別，其實說的也無非是下面這回事。
機(jī)器學(xué)習(xí)本質(zhì)上就是一種對問題真實模型的逼近（我們選擇一個我們認(rèn)為比較好的近似模型，這個近似模型就叫做一個假設(shè)），但毫無疑問，真實模型一定是不知道的（如果知道了，我們干嗎還要機(jī)器學(xué)習(xí)？直接用真實模型解決問題不就可以了？對吧，哈哈）既然真實模型不知道，那么我們選擇的假設(shè)與問題真實解之間究竟有多大差距，我們就沒法得知。比如說我們認(rèn)為宇宙誕生于150億年前的一場大爆炸，這個假設(shè)能夠描述很多我們觀察到的現(xiàn)象，但它與真實的宇宙模型之間還相差多少？誰也說不清，因為我們壓根就不知道真實的宇宙模型到底是什么。
這個與問題真實解之間的誤差，就叫做風(fēng)險（更嚴(yán)格的說，誤差的累積叫做風(fēng)險）。我們選擇了一個假設(shè)之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實結(jié)果（因為樣本是已經(jīng)標(biāo)注過的數(shù)據(jù)，是準(zhǔn)確的數(shù)據(jù)）之間的差值來表示。這個差值叫做經(jīng)驗風(fēng)險Remp(w)。以前的機(jī)器學(xué)習(xí)方法都把經(jīng)驗風(fēng)險最小化作為努力的目標(biāo)，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達(dá)到100%的正確率，在真實分類時卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時的情況便是選擇了一個足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數(shù)據(jù)一律分類錯誤?；仡^看看經(jīng)驗風(fēng)險最小化原則我們就會發(fā)現(xiàn)，此原則適用的大前提是經(jīng)驗風(fēng)險要確實能夠逼近真實風(fēng)險才行（行話叫一致），但實際上能逼近么？答案是不能，因為樣本數(shù)相對于現(xiàn)實世界要分類的文本數(shù)來說簡直九牛一毛，經(jīng)驗風(fēng)險最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當(dāng)然不能保證在更大比例的真實文本上也沒有誤差。
統(tǒng)計學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實風(fēng)險應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗風(fēng)險，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準(zhǔn)確的值（所以叫做泛化誤差界，而不叫泛化誤差）。
置信風(fēng)險與兩個量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學(xué)習(xí)結(jié)果越有可能正確，此時置信風(fēng)險越小；二是分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險會變大。
泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)
線性SVM ——
1.SVM從線性可分情況下的分類面發(fā)展而來
2.Margin最大化分類面不僅僅要求經(jīng)驗風(fēng)險盡可能的小，且使分類間隔最大
把一個空間按照類別切分兩部分的平面，在二維空間中，分類面相當(dāng)于一條直線，三維空間中相當(dāng)于一個平面,高維空間為超平面 線性分類面函數(shù)形式為：f(x)=wTx+b，（wT,b是分類面函數(shù)參數(shù),x是輸入的樣本, wT權(quán)向量,b是偏移量 ）
過兩類樣本中離分類面最近的點且平行于分類面的訓(xùn)練樣本就叫做支持向量
線性SVM求解 —— （此段借用**博客，寫的實在是簡單明了）
凸二次規(guī)劃，在這個問題中，自變量就是w，而目標(biāo)函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（哎，千萬不要把xi當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問題有個很有名氣的稱呼——二次規(guī)劃（Quadratic Programming，QP），而且可以更進(jìn)一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。
讓我再一次比較完整的重復(fù)一下我們要解決的問題：我們有屬于兩個類別的樣本點（并不限定這些點在二維空間中）若干，如圖，
圓形的樣本點定為正樣本（連帶著，我們可以把正樣本所屬的類叫做正類），方形的點定為負(fù)例。我們想求得這樣一個線性函數(shù)（在n維空間中的線性函數(shù)）：g(x)=wx+b
使得所有屬于正類的點x+代入以后有g(shù)(x+)≥1，而所有屬于負(fù)類的點x-代入后有g(shù)(x-)≤-1（之所以總跟1比較，無論正一還是負(fù)一，都是因為我們固定了間隔為1，注意間隔和幾何間隔的區(qū)別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。
求這樣的g(x)的過程就是求w（一個n維向量）和b（一個實數(shù)）兩個參數(shù)的過程（但實際上只需要求w，求得以后找某些樣本點代入就可以求得b）。因此在求g(x)的時候，w才是變量。
你肯定能看出來，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因為它就是wx+b=0嘛，哈哈），那么H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了（因為我們求的是最優(yōu)的那三條，當(dāng)然是唯一的），我們解優(yōu)化問題的過程也只不過是把這個確定了的東西算出來而已。
樣本確定了w，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn，式子中的αi是一個一個的數(shù)（在嚴(yán)格的證明過程中，這些α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數(shù)。為了方便描述，以下開始嚴(yán)格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會用α1x1表示數(shù)字和向量的乘積，而用<x1,x2>表示向量x1,x2的內(nèi)積（也叫點積，注意與向量叉積的區(qū)別）。因此g(x)的表達(dá)式嚴(yán)格的形式應(yīng)該是：g(x)=<w,x>+b
但是上面的式子還不夠好，你回頭看看圖中正樣本和負(fù)樣本的位置，想像一下，我不動所有點的位置，而只是把其中一個正樣本點定為負(fù)樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危Y(jié)果怎么樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正確分開）！這說明w不僅跟樣本點的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標(biāo)簽”有關(guān)）。因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn（式1）
其中的yi就是第i個樣本的標(biāo)簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)，當(dāng)然，更嚴(yán)格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持（撐）向量?。诌€挺形象吧，他們“撐”起了分界線。）
于是，我們可以定義Lagrange函數(shù)：L(w,b,a)如下：
凸二次空間 —— 由拉格朗日函數(shù)引出二次函數(shù)的最值問題。
前面在討論的線性分類器,器如其名，只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡單，線性分類器的求解程序會無限循環(huán)，永遠(yuǎn)也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？
有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個例子是網(wǎng)絡(luò)早就有的，在此借用，并加進(jìn)了我自己的解說而已。
例子是下面這張圖：
我們把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負(fù)類。試問能找到一個線性函數(shù)把兩類正確分開么？不能，因為二維空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。
但我們可以找到一條曲線，例如上面這一條： 顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數(shù)值，會發(fā)現(xiàn)負(fù)類的點函數(shù)值一定比0大，而正類的一定比0?。?。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為(問題只是它不是一個線性函數(shù)，但是，下面要注意看了，新建一個向量y和a：)：
這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實際上f(y)的形式就是：g(x)=f(y)=ay
在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)（只不過其中的a和y都是多維向量罷了），因為自變量y的次數(shù)不大于1。
看出妙在哪了么？原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。
而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個映射，沒有系統(tǒng)性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。
由上圖得到啟發(fā)，在低維不可分的情況下找到某種映射（核函數(shù)）使得投影到高維空間下線性可分。
核函數(shù)------ 如果 K(xi,xj) 總可以寫成 K(xi,xj)= φ(xi)T*φ(xj) (T是φ(xi)的轉(zhuǎn)置)，則K可以做 核函數(shù)
現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。
圓形和方形的點各有成千上萬個（畢竟，這就是我們訓(xùn)練集中文檔的數(shù)量嘛，當(dāng)然很大了）?，F(xiàn)在想象我們有另一個訓(xùn)練集，只比原先這個訓(xùn)練集多了一篇文章，映射到高維空間以后（當(dāng)然，也使用了相同的核函數(shù)），也就多了一個樣本點，如上圖所示。
就是圖中黃色那個點，它是方形的，因而它是負(fù)類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點線性不可分）叫做“近似線性可分”的問題。以我們?nèi)祟惖某ＷR來判斷，說有一萬個點都符合某種規(guī)律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢（因而規(guī)則應(yīng)該為它而做出修改）？
其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓(xùn)練集的同學(xué)人工分類時一打瞌睡錯放進(jìn)去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響.但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達(dá)式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎(chǔ)上尋找正負(fù)類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負(fù)的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。
因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點的控制，這是很危險的（盡管有句話說真理總是掌握在少數(shù)人手中，但那不過是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。
但解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達(dá)形式的簡潔。我們原先對樣本點的要求是： （如下式子1所示）
意思是說離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許 （如式子2所示）
因為松弛變量是非負(fù)的，因此最終的結(jié)果是要求間隔可以比1小。但是當(dāng)某些點出現(xiàn)這種間隔比1小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。把損失加入到目標(biāo)函數(shù)里的時候，就需要一個 懲罰因子 （cost，也就是libSVM的諸多參數(shù)中的C），原來的優(yōu)化問題就變成了下面這樣：
這個式子有這么幾點要注意：
一是并非所有的樣本點都有一個松弛變量與其對應(yīng)。實際上只有“離群點”才有，或者也可以這么看，所有沒離群的點松弛變量都等于0（對負(fù)類來說，離群點就是在前面圖中，跑到H2右側(cè)的那些負(fù)樣本點，對正類來說，就是跑到H1左側(cè)的那些正樣本點）。
二是松弛變量的值實際上標(biāo)示出了對應(yīng)的點到底離群有多遠(yuǎn)，值越大，點就越遠(yuǎn)。
三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當(dāng)所有離群點的松弛變量的和一定時，你定的C越大，對目標(biāo)函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標(biāo)函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。
四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就是一個參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值，要記住。
五是盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題（汗，這不廢話么），解它的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。
從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標(biāo)函數(shù)的值算一算，再換一組三條直線（你可以看到，分類的直線位置如果移動了，有些原來離群的點會變得不再離群，而有的本來不離群的點會變成離群點），再把目標(biāo)函數(shù)的值算一算，如此往復(fù)（迭代），直到最終找到目標(biāo)函數(shù)最小時的w。
啰嗦了這么多，讀者一定可以馬上自己總結(jié)出來，松弛變量也就是個解決線性不可分問題的方法罷了，但是回想一下，核函數(shù)的引入不也是為了解決線性不可分的問題么？為什么要為了一個問題使用兩種方法呢？
其實兩者還有微妙的不同。一般的過程應(yīng)該是這樣，還以文本分類為例。在原始的低維空間中，樣本相當(dāng)?shù)牟豢煞?，無論你怎么找分類平面，總會有大量的離群點，此時用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（就是達(dá)到了近似線性可分的狀態(tài)），此時再用松弛變量處理那些少數(shù)“冥頑不化”的離群點，就簡單有效得多啦。
