SVM學習筆記——（一）
-
- 超平面了解
- 間隔與幾何間隔
- 目标轉換
- 數學背景
- 問題的轉化，直覺角度
- 為何需要核函數
超平面了解
C1和C2是要區分的兩個類别，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數，它可以将兩類樣本完全分開。一般的，如果一個線性函數能夠将樣本完全正确的分開，就稱這些資料是線性可分的，否則稱為非線性可分的。
什麼叫線性函數呢？在一維空間裡就是一個點，在二維空間裡就是一條直線，三維空間裡就是一個平面，可以如此想象下去，如果不關注空間的維數，這種線性函數還有一個統一的名稱——超平面（Hyper Plane）！
線性函數 ：g(x)=wx+b
上式的x不是二維坐标系中的橫軸，而是樣本的向量表示。
中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數叫做分類面。
中間那條分界線并不是唯一的，我們把它稍微旋轉一下，隻要不把兩類資料分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。
間隔與幾何間隔
每一個樣本由一個 向量 和一個 标記 組成。
Di=(xi,yi)
分類的标記隻有兩個值，1和-1（用來表示屬于還是不屬于這個類）
定義一個樣本點到某個超平面的間隔：
δi=yi(wxi+b)
現在把w和b進行一下歸一化，即用w/||w||和b/||w||分别代替原來的w和b，那麼間隔就可以寫成
點到超平面g(x)=0的距離
當用歸一化的w和b代替原值之後的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離
定義一個點的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點的距離
幾何間隔與樣本的誤分次數間存在關系
原來幾何間隔越大的解，它的誤差上界越小。是以最大化幾何間隔成了我們訓練階段的目标
目标轉換
可以看出來：
δ=||w||δ幾何
注意到幾何間隔與||w||是成反比的，是以最大化幾何間隔與最小化||w||完全是一回事。
而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的||w||。
我們常常使用另一個完全等價的目标函數來代替：
||w||=0的時候就得到了目标函數的最小值。
限制條件：樣本點必須在H1或H2的某一側（或者至少在H1和H2上）
前文提到過把 間隔固定為1 ，這是指把所有樣本點中間隔最小的那一點的間隔定為1（這也是集合的間隔的定義，有點繞嘴），也就意味着集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立：
yi[(w·xi)+b]≥1 (i=1,2,…,l) （l是總的樣本數）
yi[(w·xi)+b]-1≥0 (i=1,2,…,l) （l是總的樣本數）
兩類分類問題也被我們轉化成了它的數學形式，一個帶限制的最小值的問題：
數學背景
從最一般的定義上說，一個求最小值的問題就是一個優化問題（也叫尋優問題，更文绉绉的叫法是規劃——Programming），它同樣由兩部分組成，目标函數和限制條件，可以用下面的式子表示：
限制條件用函數c來表示，就是constrain的意思啦。你可以看出一共有p+q個限制條件，其中p個是不等式限制，q個等式限制。
式中的x是自變量，但不限定它的維數必須為1
關于可行域還有個概念不得不提，那就是凸集，凸集是指有這麼一個點的集合，其中任取兩個點連一條直線，這條線上的點仍然在這個集合内部，是以說“凸”是很形象的。
在這個問題中，自變量就是w，而目标函數是w的二次函數，所有的限制條件都是w的線性函數（哎，千萬不要把xi當成變量，它代表樣本，是已知的），這種規劃問題有個很有名氣的稱呼——二次規劃（Quadratic Programming，QP），而且可以更進一步的說，由于它的可行域是一個凸集，是以它是一個凸二次規劃。
對于一般意義上的規劃問題，兩個問題的答案都是不一定，但凸二次規劃讓人喜歡的地方就在于，它有解（教科書裡面為了嚴謹，常常加限定成分，說它有全局最優解，由于我們想找的本來就是全局最優的解，是以不加也罷），而且可以找到！（當然，依據你使用的算法不同，找到這個解的速度，行話叫收斂速度，會有所不同）
因為我們實際上并不知道該怎麼解一個帶限制的優化問題。如果你仔細回憶一下高等數學的知識，會記得我們可以輕松的解一個不帶任何限制的優化問題（實際上就是當年背得爛熟的函數求極值嘛，求導再找0點呗，誰不會啊？笑），我們甚至還會解一個隻帶等式限制的優化問題，也是背得爛熟的，求條件極值，記得麼，通過添加拉格朗日乘子，構造拉格朗日函數，來把這個問題轉化為無限制的優化問題雲雲（如果你一時沒想通，我提醒一下，構造出的拉格朗日函數就是轉化之後的問題形式，它顯然沒有帶任何條件）。
讀者問：如果隻帶等式限制的問題可以轉化為無限制的問題而得以求解，那麼可不可以把帶不等式限制的問題向隻帶等式限制的問題轉化一下而得以求解呢？
聰明，可以，實際上我們也正是這麼做的。下一節就來說說如何做這個轉化，一旦轉化完成，求解對任何學過高等數學的人來說，都是小菜一碟啦。
問題的轉化，直覺角度
較完整的重複一下我們要解決的問題：我們有屬于兩個類别的樣本點（并不限定這些點在二維空間中）若幹，如圖，
圓形的樣本點定為正樣本（連帶着，我們可以把正樣本所屬的類叫做正類），方形的點定為負例。我們想求得這樣一個線性函數（在n維空間中的線性函數）：
使得所有屬于正類的點x+代入以後有 g(x+)≥1，而所有屬于負類的點x-代入後有 g(x-)≤-1（之是以總跟1比較，無論正一還是負一，都是因為我們固定了間隔為1，注意間隔和幾何間隔的差別）。代入g(x)後的值如果在1和-1之間，我們就拒絕判斷。
求這樣的g(x)的過程就是求w（一個n維向量）和b（一個實數）兩個參數的過程（但實際上隻需要求w，求得以後找某些樣本點代入就可以求得b）。是以在求g(x)的時候，w才是變量。
求這樣的g(x)的過程就是求 w（一個n維向量）和 b（一個實數）兩個參數的過程（但實際上隻需要求w，求得以後找某些樣本點代入就可以求得b）。是以在求g(x)的時候，w才是變量。
你肯定能看出來，一旦求出了w（也就求出了b），那麼中間的 直線H就知道了（因為它就是wx+b=0嘛，哈哈），那麼H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。那麼w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一确定了（因為我們求的是最優的那三條，當然是唯一的），我們解優化問題的過程也隻不過是把這個确定了的東西算出來而已。
樣本确定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：
w=α1x1+α2x2+…+αnxn
式子中的αi是一個一個的數（在嚴格的證明過程中，這些α被稱為 拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數。為了友善描述，以下開始嚴格差別 數字與向量的乘積 和 向量間的乘積，我會用α1x1表示數字和向量的乘積，而用 <x1,x2> 表示向量x1,x2的内積（也叫點積，注意與向量叉積的差別）。是以g(x)的表達式嚴格的形式應該是：
g(x)=<w,x>+b
但是上面的式子還不夠好，你回頭看看圖中正樣本和負樣本的位置，想像一下，我不動所有點的位置，而隻是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變為方形），結果怎麼樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正确分開）！這說明w不僅跟樣本點的位置有關，還跟樣本的類别有關（也就是和樣本的“标簽”有關）。是以用下面這個式子表示才算完整：
w=α1y1x1+α2y2x2+…+αnynxn
其中的yi就是第i個樣本的标簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，隻有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子後面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的确定了分類函數，當然，更嚴格的說，這些樣本的一部分就可以确定，因為例如确定一條直線，隻需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支援（撐）向量！（名字還挺形象吧，他們“撐”起了分界線）
式子也可以用求和符号簡寫一下：
是以原來的g(x)表達式可以寫為：
注意式子中x才是變量，也就是你要分類哪篇文檔，就把該文檔的向量表示代入到 x的位置，而所有的xi統統都是已知的樣本。還注意到式子中隻有xi和x是向量，是以一部分可以從内積符号中拿出來，得到g(x)的式子為：
發現了什麼？w不見啦！從求w變成了求α。
但肯定有人會說，這并沒有把原問題簡化呀。嘿嘿，其實簡化了，隻不過在你看不見的地方，以這樣的形式描述問題以後，我們的優化問題少了很大一部分不等式限制（記得這是我們解不了極值問題的萬惡之源）。
為何需要核函數
我們把橫軸上端點a和b之間紅色部分裡的所有點定為正類，兩邊的黑色部分裡的點定為負類。試問能找到一個線性函數把兩類正确分開麼？不能，因為二維空間裡的線性函數就是指直線，顯然找不到符合條件的直線。
顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類别（你在橫軸上随便找一點，算算這一點的函數值，會發現負類的點函數值一定比0大，而正類的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數表達式可以寫為：
問題隻是它不是一個線性函數，但是，下面要注意看了，建立一個向量y和a：
這樣g(x)就可以轉化為 f(y)=<a,y>，你可以把y和a分别回帶一下，看看等不等于原來的g(x)。用内積的形式寫你可能看不太清楚，實際上f(y)的形式就是：
在任意次元的空間中，這種形式的函數都是一個線性函數（隻不過其中的a和y都是多元向量罷了），因為自變量y的次數不大于1。
看出妙在哪了麼？原來在二維空間中一個線性不可分的問題，映射到四維空間後，變成了線性可分的！是以這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉化，使其變得線性可分。
而轉化最關鍵的部分就在于找到x到y的映射方法。遺憾的是，如何找到這個映射，沒有系統性的方法（也就是說，純靠猜和湊）。
用一個具體文本分類的例子來看看這種向高維空間映射進而分類的方法如何運作，想象一下，我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個次元上問題是線性不可分的。現在我們有一個2000維空間裡的線性函數
注意向量的右上角有個 ’哦。它能夠将原問題變得可分。式中的 w’和x’都是2000維的向量，隻不過w’是定值，而x’是變量（好吧,嚴格說來這個函數是2001維的,哈哈），現在我們的輸入呢，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然後求這個變換後的向量x’與向量w’的内積，再把這個内積的值和b相加，就得到了結果，看結果大于門檻值還是小于門檻值就得到了分類結果。
你發現了什麼？我們其實隻關心那個高維空間裡内積的值，那個值算出來了，分類結果就算出來了。而從理論上說， x’是經由x變換來的，是以廣義上可以把它叫做x的函數（有一個x，就确定了一個x’，對吧，确定不出第二個），而w’是常量，它是一個低維空間裡的常量w經過變換得到的，是以給了一個w 和x的值，就有一個确定的f(x’)值與其對應。這讓我們幻想，是否能有這樣一種函數K(w,x),他接受低維空間的輸入值，卻能算出高維空間的内積值<w’,x’>？
如果有這樣的函數，那麼當給了一個低維空間的輸入x以後，
這兩個函數的計算結果就完全一樣，我們也就用不着費力找那個映射關系，直接拿低維的輸入往g(x)裡面代就可以了（再次提醒，這回的g(x)就不是線性函數啦，因為你不能保證K(w,x)這個表達式裡的x次數不高于1哦）。
萬幸的是，這樣的K(w,x)确實存在（發現凡是我們人類能解決的問題，大都是巧得不能再巧，特殊得不能再特殊的問題，總是恰好有些能投機取巧的地方才能解決，由此感到人類的渺小），它被稱作 核函數（核，kernel），而且還不止一個，事實上，隻要是滿足了Mercer條件的函數，都可以作為核函數。核函數的基本作用就是接受兩個低維空間裡的向量，能夠計算出經過某個變換後在高維空間裡的向量内積值。
回想我們上節說的求一個線性分類器，它的形式應該是：
現在這個就是高維空間裡的線性函數（為了差別低維和高維空間裡的函數和向量，我改了函數的名字，并且給w和x都加上了 ’），我們就可以用一個低維空間裡的函數（再一次的，這個低維空間裡的函數就不再是線性的啦）來代替，
又發現什麼了？f(x’) 和g(x)裡的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當它是線性問題來求解，隻不過求解過程中，凡是要求内積的時候就用你標明的核函數來算。這樣求出來的α再和你標明的核函數一組合，就得到分類器啦！
明白了以上這些，會自然的問接下來兩個問題：
1． 既然有很多的核函數，針對具體問題該怎麼選擇？
2． 如果使用核函數向高維空間映射後，問題仍然是線性不可分的，那怎麼辦？
第一個問題現在就可以回答你：對核函數的選擇，現在還缺乏指導原則！各種實驗的觀察結果（不光是文本分類）的确表明，某些問題用某些核函數效果很好，用另一些就很差，但是一般來講，徑向基核函數是不會出太大偏差的一種，首選。（我做文本分類系統的時候，使用徑向基核函數，沒有參數調優的情況下，絕大部分類别的準确和召回都在85%以上，可見。雖然libSVM的作者林智仁認為文本分類用線性核函數效果更佳，待考證）