? ? ? ? ? ? ? ? ? ? ? ? ?SVM（support victor machine）
1、支持向量機發(fā)展歷史
? ??? 1963年，Vapnik在解決模式識別問題時提出了支持向量方法。起決定性作用的樣本為支持向量
? ? ? 1971年，Kimeldorf構造基于支持向量構建核空間的方法
? ? ? 1995年，Vapnik等人正式提出統(tǒng)計學習理論。
? ? ? 通俗來講，SVM是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機的學習策略便是間隔最大化，最終可轉化為一個凸二次規(guī)劃問題的求解。
? ? ? 這里解釋一下幾個名詞---‘二類分類模型’、‘線性分類器’、‘間隔’、‘凸二次空間’
二類分類模型——?這里我們考慮的是一個兩類的分類問題，就是將一堆數據集通過建立模型將其分成兩類，典型的二類分類模型，有neural network的感知器，

線性分類器——

???

? ? ??其中，數據點用x（x是n維向量）來表示，wT中的T代表轉置，而類別用?y?來表示，可以取?1或者?-1，分別代表兩個不同的類。一個線性分類器的學習目標就是要在?n維的數據空間中找到一個分類?超平面?，其方程可以表示為：wTx+b=0

? ? ??上面給出了線性分類的定義描述，但或許讀者沒有想過：為何用y取1 或者 -1來表示兩個不同的類別呢？其實，這個1或-1的分類標準起源于logistic回歸。

間隔——

? ? ??首先，講講‘間隔’的來源，如上圖所述，可以有無窮個線性分類器將數據集分開，但是如何描述最好的分類器呢？

? ? ? 如上圖的Margin width就是兩條邊緣之間的間距。注意，區(qū)別于求歐式空間內兩個向量的距離（2-范數）。

2.常用的機器學習方法比較
? ? ??上個世紀90年代，支持向量機獲得全面發(fā)展，在實際應用中，獲得比較滿意的效果，成為機器學習領域的標準工具.
? ?1)概率分布的方法-------------Bayes方法, GMMs 用于復雜分布建模
? ?2)決策樹的方法（C4.5）---屬性具有明確含義時使用，一種經典的方法
? ?3)近鄰分類-----------------------簡單的方法，如果樣本有代表性，維數不高時好用
? ?4)支撐向量機--------------------高維空間的小樣本學習
? ?5)Boosting算法-----------------大量訓練樣本下可以取得好的效果，速度很快
? ?6)人工神經網絡ANN----------大量訓練樣本下可以取得好的效果，速度較慢
? ? ? ?例如，手寫體數字識別例子——貝爾實驗室對美國郵政手寫數字庫進行的實驗，該數據共包含7291個訓練樣本，2007個測試數據，輸入數據的維數為16x16維
測試結果比較如下：

3.結構風險最小化

VC維與經驗風險———

? ??Vapnik-Chervonenkis (VC) dimension，VC 維定義為一組函數，如平面、直線等在空間打散（任意分類）樣本的能力。
? ? 例，直線的VC 維為3，當4個樣本點時，無法任意分類

? ? ??正是因為SVM關注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數是無關的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當然，有這樣的能力也因為引入了核函數）。
結構風險最小化原則———
? ? ???結構風險最小聽上去很陌生，但是我們從學初中物理就明白相似的概念——測量誤差與實際誤差之間的差別，其實說的也無非是下面這回事。
? ? ? ?機器學習本質上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設），但毫無疑問，真實模型一定是不知道的（如果知道了，我們干嗎還要機器學習？直接用真實模型解決問題不就可以了？對吧，哈哈）既然真實模型不知道，那么我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。比如說我們認為宇宙誕生于150億年前的一場大爆炸，這個假設能夠描述很多我們觀察到的現象，但它與真實的宇宙模型之間還相差多少？誰也說不清，因為我們壓根就不知道真實的宇宙模型到底是什么。
? ? ? ?這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。我們選擇了一個假設之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數據上的分類的結果與真實結果（因為樣本是已經標注過的數據，是準確的數據）之間的差值來表示。這個差值叫做經驗風險Remp(w)。以前的機器學習方法都把經驗風險最小化作為努力的目標，但后來發(fā)現很多分類函數能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時的情況便是選擇了一個足夠復雜的分類函數（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數據一律分類錯誤?；仡^看看經驗風險最小化原則我們就會發(fā)現，此原則適用的大前提是經驗風險要確實能夠逼近真實風險才行（行話叫一致），但實際上能逼近么？答案是不能，因為樣本數相對于現實世界要分類的文本數來說簡直九牛一毛，經驗風險最小化原則只在這占很小比例的樣本上做到沒有誤差，當然不能保證在更大比例的真實文本上也沒有誤差。
? ? ? 統(tǒng)計學習因此而引入了泛化誤差界的概念，就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。
? ? ? 置信風險與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越??；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。
? ? ? 泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)
? ? ? 公式中R(w)就是真實風險，Remp(w)就是經驗風險，Ф(n/h)就是置信風險。統(tǒng)計學習的目標從經驗風險最小化變?yōu)榱藢で蠼涷烇L險與置信風險的和最小，即結構風險最小。 ? ? ? ? ??SVM正是這樣一種努力最小化結構風險的算法。
線性SVM——
? ???1.SVM從線性可分情況下的分類面發(fā)展而來
? ? ?2.Margin最大化分類面不僅僅要求經驗風險盡可能的小，且使分類間隔最大
? ? ?3.SVM考慮尋找一個滿足分類要求的分類面

分類面———

? ? ? ?把一個空間按照類別切分兩部分的平面，在二維空間中，分類面相當于一條直線，三維空間中相當于一個平面,高維空間為超平面 線性分類面函數形式為：f(x)=wTx+b，（wT,b是分類面函數參數,x是輸入的樣本, wT權向量,b是偏移量 ）

支持向量———

? ? ? ? 過兩類樣本中離分類面最近的點且平行于分類面的訓練樣本就叫做支持向量

??

? ??

線性關系——

線性SVM求解——（此段借用**博客，寫的實在是簡單明了）

? ? ? ?凸二次規(guī)劃，在這個問題中，自變量就是w，而目標函數是w的二次函數，所有的約束條件都是w的線性函數（哎，千萬不要把xi當成變量，它代表樣本，是已知的），這種規(guī)劃問題有個很有名氣的稱呼——二次規(guī)劃（Quadratic Programming，QP），而且可以更進一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。

? ? ? 讓我再一次比較完整的重復一下我們要解決的問題：我們有屬于兩個類別的樣本點（并不限定這些點在二維空間中）若干，如圖，

? ? ???圓形的樣本點定為正樣本（連帶著，我們可以把正樣本所屬的類叫做正類），方形的點定為負例。我們想求得這樣一個線性函數（在n維空間中的線性函數）：g(x)=wx+b
? ? ? ?使得所有屬于正類的點x+代入以后有g(x+)≥1，而所有屬于負類的點x-代入后有g(x-)≤-1（之所以總跟1比較，無論正一還是負一，都是因為我們固定了間隔為1，注意間隔和幾何間隔的區(qū)別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。
? ? ? ?求這樣的g(x)的過程就是求w（一個n維向量）和b（一個實數）兩個參數的過程（但實際上只需要求w，求得以后找某些樣本點代入就可以求得b）。因此在求g(x)的時候，w才是變量。
? ? ? ?你肯定能看出來，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因為它就是wx+b=0嘛，哈哈），那么H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了（因為我們求的是最優(yōu)的那三條，當然是唯一的），我們解優(yōu)化問題的過程也只不過是把這個確定了的東西算出來而已。
? ? ? ? 樣本確定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn，式子中的αi是一個一個的數（在嚴格的證明過程中，這些α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數。為了方便描述，以下開始嚴格區(qū)別數字與向量的乘積和向量間的乘積，我會用α1x1表示數字和向量的乘積，而用<x1,x2>表示向量x1,x2的內積（也叫點積，注意與向量叉積的區(qū)別）。因此g(x)的表達式嚴格的形式應該是：g(x)=<w,x>+b
? ? ? ? 但是上面的式子還不夠好，你回頭看看圖中正樣本和負樣本的位置，想像一下，我不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危?，結果怎么樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正確分開）！這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關（也就是和樣本的“標簽”有關）。因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn（式1）

? ? ? ? 其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數，當然，更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持（撐）向量?。诌€挺形象吧，他們“撐”起了分界線。）

? ? ? 于是，我們可以定義Lagrange函數：L(w,b,a)如下：

? ?

凸二次空間——由拉格朗日函數引出二次函數的最值問題。

? ? ??前面在討論的線性分類器,器如其名，只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程序會無限循環(huán)，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數據變得線性可分呢？

有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個例子是網絡早就有的，在此借用，并加進了我自己的解說而已。

例子是下面這張圖：

? ? ? 我們把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。

? ? ? ?但我們可以找到一條曲線，例如上面這一條：顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數值，會發(fā)現負類的點函數值一定比0大，而正類的一定比0?。＿@條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為(問題只是它不是一個線性函數，但是，下面要注意看了，新建一個向量y和a：)：

? ? ??這樣g(x)就可以轉化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內積的形式寫你可能看不太清楚，實際上f(y)的形式就是：g(x)=f(y)=ay
? ? ? 在任意維度的空間中，這種形式的函數都是一個線性函數（只不過其中的a和y都是多維向量罷了），因為自變量y的次數不大于1。
看出妙在哪了么？原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉化，使其變得線性可分。

? ? ? 而轉化最關鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個映射，沒有系統(tǒng)性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數已經如此之高，也常常是線性不可分的，還要向更高的空間轉化。其中的難度可想而知。

? ? ? ?

? ?由上圖得到啟發(fā)，在低維不可分的情況下找到某種映射（核函數）使得投影到高維空間下線性可分。

核函數------如果 K(xi,xj) 總可以寫成?K(xi,xj)= φ(xi)T*φ(xj)?(T是φ(xi)的轉置)，則K可以做核函數

??

?

? ? ?現在我們已經把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。

? ? ? ?圓形和方形的點各有成千上萬個（畢竟，這就是我們訓練集中文檔的數量嘛，當然很大了）?，F在想象我們有另一個訓練集，只比原先這個訓練集多了一篇文章，映射到高維空間以后（當然，也使用了相同的核函數），也就多了一個樣本點，如上圖所示。

? ? ? 就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數點線性不可分）叫做“近似線性可分”的問題。以我們人類的常識來判斷，說有一萬個點都符合某種規(guī)律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢（因而規(guī)則應該為它而做出修改）？

? ? ? 其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓練集的同學人工分類時一打瞌睡錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響.但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。

因此由上面的例子中也可以看出，硬間隔的分類法其結果容易受少數點的控制，這是很危險的（盡管有句話說真理總是掌握在少數人手中，但那不過是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。

? ? ? 但解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達形式的簡潔。我們原先對樣本點的要求是：（如下式子1所示）

? ? ??意思是說離分類面最近的樣本點函數間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許（如式子2所示）

? ? ? 因為松弛變量是非負的，因此最終的結果是要求間隔可以比1小。但是當某些點出現這種間隔比1小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。把損失加入到目標函數里的時候，就需要一個懲罰因子（cost，也就是libSVM的諸多參數中的C），原來的優(yōu)化問題就變成了下面這樣：

? ? ??這個式子有這么幾點要注意：

? ? ? 一是并非所有的樣本點都有一個松弛變量與其對應。實際上只有“離群點”才有，或者也可以這么看，所有沒離群的點松弛變量都等于0（對負類來說，離群點就是在前面圖中，跑到H2右側的那些負樣本點，對正類來說，就是跑到H1左側的那些正樣本點）。

? ? ?二是松弛變量的值實際上標示出了對應的點到底離群有多遠，值越大，點就越遠。

? ? ?三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，你定的C越大，對目標函數的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標函數的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。

? ? ?四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數據看看結果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就是一個參數尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值，要記住。

? ? ?五是盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題（汗，這不廢話么），解它的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。

? ? ? 從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標函數的值算一算，再換一組三條直線（你可以看到，分類的直線位置如果移動了，有些原來離群的點會變得不再離群，而有的本來不離群的點會變成離群點），再把目標函數的值算一算，如此往復（迭代），直到最終找到目標函數最小時的w。

啰嗦了這么多，讀者一定可以馬上自己總結出來，松弛變量也就是個解決線性不可分問題的方法罷了，但是回想一下，核函數的引入不也是為了解決線性不可分的問題么？為什么要為了一個問題使用兩種方法呢？

? ? ? 其實兩者還有微妙的不同。一般的過程應該是這樣，還以文本分類為例。在原始的低維空間中，樣本相當的不可分，無論你怎么找分類平面，總會有大量的離群點，此時用核函數向高維空間映射一下，雖然結果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（就是達到了近似線性可分的狀態(tài)），此時再用松弛變量處理那些少數“冥頑不化”的離群點，就簡單有效得多啦。

?