生存？還是毀滅？——哈姆雷特
可分？還是不可分？——支援向量機
之前一直在讨論的線性分類器,器如其名（汗，這是什麼說法啊），隻能對線性可分的樣本做處理。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程式會無限循環，永遠也解不出來。這必然使得它的适用範圍大大縮小，而它的很多優點我們實在不原意放棄，怎麼辦呢？是否有某種方法，讓線性不可分的資料變得線性可分呢？
有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個例子是網絡早就有的，我一時找不到原作者的正确資訊，在此借用，并加進了我自己的解說而已。
例子是下面這張圖：
我們把橫軸上端點a和b之間紅色部分裡的所有點定為正類，兩邊的黑色部分裡的點定為負類。試問能找到一個線性函數把兩類正确分開麼？不能，因為二維空間裡的線性函數就是指直線，顯然找不到符合條件的直線。
但我們可以找到一條曲線，例如下面這一條：
顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類别（你在橫軸上随便找一點，算算這一點的函數值，會發現負類的點函數值一定比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的映射方法。遺憾的是，如何找到這個映射，沒有系統性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數已經如此之高，也常常是線性不可分的，還要向更高的空間轉化。其中的難度可想而知。
用一個具體文本分類的例子來看看這種向高維空間映射進而分類的方法如何運作，想象一下，我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個次元上問題是線性不可分的。現在我們有一個2000維空間裡的線性函數
f(x’)=<w’,x’>+b
注意向量的右上角有個 ’哦。它能夠将原問題變得可分。式中的 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)=K(w,x)+b
f(x’)=<w’,x’>+b
這兩個函數的計算結果就完全一樣，我們也就用不着費力找那個映射關系，直接拿低維的輸入往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的作者林智仁認為文本分類用線性核函數效果更佳，待考證）
對第二個問題的解決則引出了我們下一節的主題：松弛變量。