SVM

SVM簡(jiǎn)介

　　SVM（Support Vector Machine）指的是支持向量機(jī)，是常見的一種判別方法。在機(jī)器學(xué)習(xí)領(lǐng)域，是一個(gè)有監(jiān)督的學(xué)習(xí)模型，通常用來進(jìn)行模式識(shí)別、分類以及回歸分析。

　　Vapnik等人在多年研究統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上對(duì)線性分類器提出了另一種設(shè)計(jì)最佳準(zhǔn)則。其原理也從線性可分說起，然后擴(kuò)展到線性不可分的情況。甚至擴(kuò)展到使用非線性函數(shù)中去，這種分類器被稱為支持向量機(jī)（Support Vector Machine，簡(jiǎn)稱SVM）。支持向量機(jī)的提出有很深的理論背景。支持向量機(jī)方法是在后來提出的一種新方法。SVM的主要思想可以概括為兩點(diǎn)：

　　它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對(duì)樣本的非線性特征進(jìn)行線性分析成為可能。

　　它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中構(gòu)建最優(yōu)超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望以某個(gè)概率滿足一定上界。

SVM百科

　　SVM（Support Vector Machine）指的是支持向量機(jī)，是常見的一種判別方法。在機(jī)器學(xué)習(xí)領(lǐng)域，是一個(gè)有監(jiān)督的學(xué)習(xí)模型，通常用來進(jìn)行模式識(shí)別、分類以及回歸分析。

　　Vapnik等人在多年研究統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上對(duì)線性分類器提出了另一種設(shè)計(jì)最佳準(zhǔn)則。其原理也從線性可分說起，然后擴(kuò)展到線性不可分的情況。甚至擴(kuò)展到使用非線性函數(shù)中去，這種分類器被稱為支持向量機(jī)（Support Vector Machine，簡(jiǎn)稱SVM）。支持向量機(jī)的提出有很深的理論背景。支持向量機(jī)方法是在后來提出的一種新方法。SVM的主要思想可以概括為兩點(diǎn)：

　　它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對(duì)樣本的非線性特征進(jìn)行線性分析成為可能。

　　它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中構(gòu)建最優(yōu)超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望以某個(gè)概率滿足一定上界。

　　例子

　　如右圖：將1維的“線性不可分”上升到2維后就成為線性可分了。⑵它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望風(fēng)險(xiǎn)以某個(gè)概率滿足一定上界。在學(xué)習(xí)這種方法時(shí)，首先要弄清楚這種方法考慮問題的特點(diǎn)，這就要從線性可分的最簡(jiǎn)單情況討論起，在沒有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)在設(shè)計(jì)時(shí)，需要用到條件極值問題的求解，因此需用拉格朗日乘子理論，但對(duì)多數(shù)人來說，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時(shí)只要了解拉格朗日理論的有關(guān)結(jié)論就行。

　　一般特征

　?、臩VM學(xué)習(xí)問題可以表示為凸優(yōu)化問題，因此可以利用已知的有效算法發(fā)現(xiàn)目標(biāo)函數(shù)的全局最小值。而其他分類方法（如基于規(guī)則的分類器和人工神經(jīng)網(wǎng)絡(luò)）都采用一種基于貪心學(xué)習(xí)的策略來搜索假設(shè)空間，這種方法一般只能獲得局部最優(yōu)解。⑵SVM通過最大化決策邊界的邊緣來控制模型的能力。盡管如此，用戶必須提供其他參數(shù)，如使用核函數(shù)類型和引入松弛變量等。⑶通過對(duì)數(shù)據(jù)中每個(gè)分類屬性引入一個(gè)啞變量，SVM可以應(yīng)用于分類數(shù)據(jù)。⑷SVM一般只能用在二類問題，對(duì)于多類問題效果不好。

　　原理介紹

　　SVM方法是通過一個(gè)非線性映射p，把樣本空間映射到一個(gè)高維乃至無窮維的特征空間中（Hilbert空間），使得在原來的樣本空間中非線性可分的問題轉(zhuǎn)化為在特征空間中的線性可分的問題．簡(jiǎn)單地說，就是升維和線性化．升維，就是把樣本向高維空間做映射，一般情況下這會(huì)增加計(jì)算的復(fù)雜性，甚至?xí)?ldquo;維數(shù)災(zāi)難”，因而人們很少問津．但是作為分類、回歸等問題來說，很可能在低維樣本空間無法線性處理的樣本集，在高維特征空間中卻可以通過一個(gè)線性超平面實(shí)現(xiàn)線性劃分（或回歸）．一般的升維都會(huì)帶來計(jì)算的復(fù)雜化，SVM方法巧妙地解決了這個(gè)難題：應(yīng)用核函數(shù)的展開定理，就不需要知道非線性映射的顯式表達(dá)式；由于是在高維特征空間中建立線性學(xué)習(xí)機(jī)，所以與線性模型相比，不但幾乎不增加計(jì)算的復(fù)雜性，而且在某種程度上避免了“維數(shù)災(zāi)難”．這一切要?dú)w功于核函數(shù)的展開和計(jì)算理論．選擇不同的核函數(shù)，可以生成不同的SVM，常用的核函數(shù)有以下4種：⑴線性核函數(shù)K（x，y）=x·y；⑵多項(xiàng)式核函數(shù)K（x，y）=［（x·y）+1］^d；⑶徑向基函數(shù)K（x，y）=exp（-|x-y|^2/d^2）⑷二層神經(jīng)網(wǎng)絡(luò)核函數(shù)K（x，y）=tanh（a（x·y）+b）．

　　應(yīng)用

　　SVM可用于解決各種現(xiàn)實(shí)世界的問題：

　　支持向量機(jī)有助于文本和超文本分類，因?yàn)樗鼈兊膽?yīng)用程序可以顯著減少對(duì)標(biāo)準(zhǔn)感應(yīng)和轉(zhuǎn)換設(shè)置中標(biāo)記的訓(xùn)練實(shí)例的需求。

　　圖像的分類也可以使用SVM進(jìn)行。實(shí)驗(yàn)結(jié)果表明，只有三到四輪的相關(guān)性反饋，支持向量機(jī)的搜索精度要比傳統(tǒng)的查詢優(yōu)化方案高得多。圖像分割系統(tǒng)也是如此，包括使用Vapnik建議的使用特權(quán)方法的修改版SVM的系統(tǒng)。

　　使用SVM可以識(shí)別手寫字符。

　　SVM算法已廣泛應(yīng)用于生物科學(xué)和其他科學(xué)領(lǐng)域。它們已被用于對(duì)高達(dá)90%正確分類的化合物進(jìn)行蛋白質(zhì)分類。已經(jīng)提出基于SVM權(quán)重的置換測(cè)試作為解釋SVM模型的機(jī)制。支持向量機(jī)權(quán)重也被用于解釋過去的SVM模型。Posthoc解釋支持向量機(jī)模型為了識(shí)別模型使用的特征進(jìn)行預(yù)測(cè)是一個(gè)比較新的研究領(lǐng)域，在生物科學(xué)中具有特殊的意義。

　　手把手教你實(shí)現(xiàn)SVM算法

　　機(jī)器學(xué)習(xí)是研究計(jì)算機(jī)怎樣模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為，以獲取新的知識(shí)或技能，重新組織已有的知識(shí)結(jié)構(gòu)使之不斷改善自身的性能。它是人工智能的核心，是使計(jì)算機(jī)具有智能的根本途徑，其應(yīng)用遍及人工智能的各個(gè)領(lǐng)域。

　　機(jī)器學(xué)習(xí)的大致分類：

　　1）分類（模式識(shí)別）：要求系統(tǒng)依據(jù)已知的分類知識(shí)對(duì)輸入的未知模式（該模式的描述）作分析，以確定輸入模式的類屬，例如手寫識(shí)別（識(shí)別是不是這個(gè)數(shù)）。

　　2）問題求解：要求對(duì)于給定的目標(biāo)狀態(tài)，尋找一個(gè)將當(dāng)前狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)的動(dòng)作序列。

　　SVM一般是用來分類的（一般先分為兩類，再向多類推廣一生二，二生三，三生萬物哈）

　　問題的描述

　　向量表示：假設(shè)一個(gè)樣本有n個(gè)變量（特征）：Ⅹ= （X1，X2，…，Xn）T

　　樣本表示方法：

　　SVM線性分類器

　　SVM從線性可分情況下的最優(yōu)分類面發(fā)展而來。最優(yōu)分類面就是要求分類線不但能將兩類正確分開（訓(xùn)練錯(cuò)誤率為0），且使分類間隔最大。SVM考慮尋找一個(gè)滿足分類要求的超平面，并且使訓(xùn)練集中的點(diǎn)距離分類面盡可能的遠(yuǎn)，也就是尋找一個(gè)分類面使它兩側(cè)的空白區(qū)域（margin）最大。

　　過兩類樣本中離分類面最近的點(diǎn)且平行于最優(yōu)分類面的超平面上H1，H2的訓(xùn)練樣本就叫做支持向量。

　　圖例：

　　問題描述：

　　假定訓(xùn)練數(shù)據(jù) ：

　　可以被分為一個(gè)超平面：

　　進(jìn)行歸一化：

　　此時(shí)分類間隔等于：

　　即使得：最大間隔最大等價(jià)于使最小

　　下面這兩張圖可以看一下，有個(gè)感性的認(rèn)識(shí)。那個(gè)好？

　　看下面這張圖：

　　下面我們要開始優(yōu)化上面的式子，因?yàn)橥茖?dǎo)要用到拉格朗日定理和KKT條件，所以我們先了解一下相關(guān)知識(shí)。在求取有約束條件的優(yōu)化問題時(shí)，拉格朗日乘子法（Lagrange Multiplier） 和KKT條件是非常重要的兩個(gè)求取方法，對(duì)于等式約束的優(yōu)化問題，可以應(yīng)用拉格朗日乘子法去求取最優(yōu)值；如果含有不等式約束，可以應(yīng)用KKT條件去求取。當(dāng)然，這兩個(gè)方法求得的結(jié)果只是必要條件，只有當(dāng)是凸函數(shù)的情況下，才能保證是充分必要條件。KKT條件是拉格朗日乘子法的泛化。之前學(xué)習(xí)的時(shí)候，只知道直接應(yīng)用兩個(gè)方法，但是卻不知道為什么拉格朗日乘子法（Lagrange Multiplier） 和KKT條件能夠起作用，為什么要這樣去求取最優(yōu)值呢？

　　拉格朗日乘子法和KKT條件

　　定義：給定一個(gè)最優(yōu)化問題：

　　最小化目標(biāo)函數(shù)：

　　制約條件：

　　定義拉格朗日函數(shù)為：

　　求偏倒方程

　　可以求得的值。這個(gè)就是神器拉格朗日乘子法。

　　上面的拉格朗日乘子法還不足以幫我們解決所有的問題，下面引入不等式約束

　　最小化目標(biāo)函數(shù)：

　　制約條件變?yōu)椋?/p>

　　定義拉格朗日函數(shù)為：

　　可以列出方程：

　　新增加的條件被稱為KKT條件

　　KKT條件詳解

　　對(duì)于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個(gè)式子L（a， b， x）= f（x） + a*g（x）+b*h（x），KKT條件是說最優(yōu)值必須滿足以下條件：

　　1. L（a， b， x）對(duì)x求導(dǎo)為零；

　　2. h（x） =0;

　　3. a*g（x） = 0;

　　求取這三個(gè)等式之后就能得到候選最優(yōu)值。其中第三個(gè)式子非常有趣，因?yàn)間（x）《=0，如果要滿足這個(gè)等式，必須a=0或者g（x）=0. 這是SVM的很多重要性質(zhì)的來源，如支持向量的概念。

　　二。 為什么拉格朗日乘子法（Lagrange Multiplier） 和KKT條件能夠得到最優(yōu)值？

　　為什么要這么求能得到最優(yōu)值？先說拉格朗日乘子法，設(shè)想我們的目標(biāo)函數(shù)z = f（x）， x是向量， z取不同的值，相當(dāng)于可以投影在x構(gòu)成的平面（曲面）上，即成為等高線，如下圖，目標(biāo)函數(shù)是f（x， y），這里x是標(biāo)量，虛線是等高線，現(xiàn)在假設(shè)我們的約束g（x）=0，x是向量，在x構(gòu)成的平面或者曲面上是一條曲線，假設(shè)g（x）與等高線相交，交點(diǎn)就是同時(shí)滿足等式約束條件和目標(biāo)函數(shù)的可行域的值，但肯定不是最優(yōu)值，因?yàn)橄嘟灰馕吨隙ㄟ€存在其它的等高線在該條等高線的內(nèi)部或者外部，使得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切的時(shí)候，可能取得最優(yōu)值，如下圖所示，即等高線和目標(biāo)函數(shù)的曲線在該點(diǎn)的法向量必須有相同方向，所以最優(yōu)值必須滿足：f（x）的梯度 = a* g（x）的梯度，a是常數(shù)，表示左右兩邊同向。這個(gè)等式就是L（a，x）對(duì)參數(shù)求導(dǎo)的結(jié)果。（上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當(dāng)面講好理解一些，注：下圖來自wiki）。

　　而KKT條件是滿足強(qiáng)對(duì)偶條件的優(yōu)化問題的必要條件，可以這樣理解：我們要求min f（x）， L（a， b， x） = f（x） + a*g（x） + b*h（x），a》=0，我們可以把f（x）寫為：max_{a，b} L（a，b，x），為什么呢？因?yàn)閔（x）=0， g（x）《=0，現(xiàn)在是取L（a，b，x）的最大值，a*g（x）是《=0，所以L（a，b，x）只有在a*g（x） = 0的情況下才能取得最大值，否則，就不滿足約束條件，因此max_{a，b} L（a，b，x）在滿足約束條件的情況下就是f（x），因此我們的目標(biāo)函數(shù)可以寫為 min_x max_{a，b} L（a，b，x）。如果用對(duì)偶表達(dá)式： max_{a，b} min_x L（a，b，x），由于我們的優(yōu)化是滿足強(qiáng)對(duì)偶的（強(qiáng)對(duì)偶就是說對(duì)偶式子的最優(yōu)值是等于原問題的最優(yōu)值的），所以在取得最優(yōu)值x0的條件下，它滿足 f（x0） = max_{a，b} min_x L（a，b，x） = min_x max_{a，b} L（a，b，x） =f（x0），我們來看看中間兩個(gè)式子發(fā)生了什么事情：

　　f（x0） = max_{a，b} min_x L（a，b，x） = max_{a，b} min_x f（x） + a*g（x） + b*h（x） = max_{a，b} f（x0）+a*g（x0）+b*h（x0） = f（x0）

　　可以看到上述加黑的地方本質(zhì)上是說 min_x f（x） + a*g（x） + b*h（x） 在x0取得了最小值，用Fermat定理，即是說對(duì)于函數(shù) f（x） + a*g（x） + b*h（x），求取導(dǎo)數(shù)要等于零，即

　　f（x）的梯度+a*g（x）的梯度+ b*h（x）的梯度 = 0

　　這就是KKT條件中第一個(gè)條件：L（a， b， x）對(duì)x求導(dǎo)為零。

　　而之前說明過，a*g（x） = 0，這時(shí)KKT條件的第3個(gè)條件，當(dāng)然已知的條件h（x）=0必須被滿足，所有上述說明，滿足強(qiáng)對(duì)偶條件的優(yōu)化問題的最優(yōu)值都必須滿足KKT條件，即上述說明的三個(gè)條件?？梢园袺KT條件視為是拉格朗日乘子法的泛化。

　　上面跑題了，下面我繼續(xù)我們的SVM之旅。

　　經(jīng)過拉格朗日乘子法和KKT條件推導(dǎo)之后

　　最終問題轉(zhuǎn)化為：

　　最大化：

　　條件：

　　這個(gè)是著名的QP問題。決策面：其中 為問題的優(yōu)化解。

　　松弛變量（slack vaviable）

　　由于在采集數(shù)據(jù)的過程中，也可能有誤差（如圖）

　　所以我們引入松弛變量對(duì)問題進(jìn)行優(yōu)化。

　　式子就變?yōu)?img alt="clip_image052" border="0" height="25" src="http://images.cnitblog.com/blog/458371/201212/31223705-c648f3b4460c4054839619d3e09e19a7.jpg" width="252" />

　　最終轉(zhuǎn)化為下面的優(yōu)化問題：

　　其中的C是懲罰因子，是一個(gè)由用戶去指定的系數(shù)，表示對(duì)分錯(cuò)的點(diǎn)加入多少的懲罰，當(dāng)C很大的時(shí)候，分錯(cuò)的點(diǎn)就會(huì)更少，但是過擬合的情況可能會(huì)比較嚴(yán)重，當(dāng)C很小的時(shí)候，分錯(cuò)的點(diǎn)可能會(huì)很多，不過可能由此得到的模型也會(huì)不太正確。

　　上面那個(gè)個(gè)式子看似復(fù)雜，現(xiàn)在我?guī)Т蠹乙黄鹜频挂幌?/p>

　　……

　　…（草稿紙上，敲公式太煩人了）

　　最終得到：

　　最大化：

　　條件：

　　呵呵，是不是感覺和前面的式子沒啥區(qū)別內(nèi)，親，數(shù)學(xué)就是這么美妙啊。

　　這個(gè)式子看起來beautiful，但是多數(shù)情況下只能解決線性可分的情況，只可以對(duì)線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡(jiǎn)單，線性分類器的求解程序會(huì)無限循環(huán)，永遠(yuǎn)也解不出來。但是不怕不怕。我們有殺手锏還沒有出呢。接著咱要延伸到一個(gè)新的領(lǐng)域：核函數(shù)。嘻嘻，相信大家都應(yīng)該聽過這廝的大名，這個(gè)東東在60年代就提出來，可是直到90年代才開始火起來（第二春哈），主要是被Vapnik大大翻出來了。這也說明計(jì)算機(jī)也要多研讀經(jīng)典哈，不是說過時(shí)了就不看的，有些大師的論文還是有啟發(fā)意義的。廢話不多說，又跑題了。

　　核函數(shù)

　　那到底神馬是核函數(shù)呢？

　　介個(gè)咱得先介紹一下VC維的概念。

　　為了研究經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化函數(shù)集的學(xué)習(xí)一致收斂速度和推廣性，SLT定義了一些指標(biāo)來衡量函數(shù)集的性能，其中最重要的就是VC維（Vapnik-Chervonenkis Dimension）。

　　VC維定義：對(duì)于一個(gè)指示函數(shù)（即只有0和1兩種取值的函數(shù)）集，如果存在h個(gè)樣本能夠被函數(shù)集里的函數(shù)按照所有可能的2h種形式分開，則稱函數(shù)集能夠把h個(gè)樣本打散，函數(shù)集的VC維就是能夠打散的最大樣本數(shù)目。

　　如果對(duì)任意的樣本數(shù)，總有函數(shù)能打散它們，則函數(shù)集的VC維就是無窮大。

　　看圖比較方便（三個(gè)點(diǎn)分類，線性都可分的）。

　　如果四個(gè)點(diǎn)呢？哈哈，右邊的四個(gè)點(diǎn)要分為兩個(gè)類，可能就分不啦。

　　如果四個(gè)點(diǎn)，一條線可能就分不過來啦。

　　一般而言，VC維越大， 學(xué)習(xí)能力就越強(qiáng)，但學(xué)習(xí)機(jī)器也越復(fù)雜。

　　目前還沒有通用的關(guān)于計(jì)算任意函數(shù)集的VC維的理論，只有對(duì)一些特殊函數(shù)集的VC維可以準(zhǔn)確知道。

　　N維實(shí)數(shù)空間中線性分類器和線性實(shí)函數(shù)的VC維是n+1。

　　Sin（ax）的VC維為無窮大。

　　對(duì)于給定的學(xué)習(xí)函數(shù)集，如何計(jì)算其VC維是當(dāng)前統(tǒng)計(jì)學(xué)習(xí)理論研究中有待解決的一個(gè)難點(diǎn)問題，各位童鞋有興趣可以去研究研究。

　　咱們接著要說說為啥要映射。

　　例子是下面這張圖：

　　下面這段來自百度文庫(kù)http://wenku.baidu.com/view/8c17ebda5022aaea998f0fa8.html

　　俺覺得寫的肯定比我好，所以咱就選擇站在巨人的肩膀上啦。

　　我們把橫軸上端點(diǎn)a和b之間紅色部分里的所有點(diǎn)定為正類，兩邊的黑色部分里的點(diǎn)定為負(fù)類。試問能找到一個(gè)線性函數(shù)把兩類正確分開么？不能，因?yàn)槎S空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。

　　但我們可以找到一條曲線，例如下面這一條：

　　顯然通過點(diǎn)在這條曲線的上方還是下方就可以判斷點(diǎn)所屬的類別（你在橫軸上隨便找一點(diǎn)，算算這一點(diǎn)的函數(shù)值，會(huì)發(fā)現(xiàn)負(fù)類的點(diǎn)函數(shù)值一定比0大，而正類的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達(dá)式可以寫為：

　　問題只是它不是一個(gè)線性函數(shù)，但是，下面要注意看了，新建一個(gè)向量y和a：

　　這樣g（x）就可以轉(zhuǎn)化為f（y）=《a，y》，你可以把y和a分別回帶一下，看看等不等于原來的g（x）。用內(nèi)積的形式寫你可能看不太清楚，實(shí)際上f（y）的形式就是：

　　g（x）=f（y）=ay

　　在任意維度的空間中，這種形式的函數(shù)都是一個(gè)線性函數(shù)（只不過其中的a和y都是多維向量罷了），因?yàn)樽宰兞縴的次數(shù)不大于1。

　　看出妙在哪了么？原來在二維空間中一個(gè)線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。

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

　　為什么說f（y）=ay是四維空間里的函數(shù)？

　　大家可能一時(shí)沒看明白。回想一下我們二維空間里的函數(shù)定義

　　g（x）=ax+b

　　變量x是一維的，為什么說它是二維空間里的函數(shù)呢？因?yàn)檫€有一個(gè)變量我們沒寫出來，它的完整形式其實(shí)是

　　y=g（x）=ax+b

　　即

　　y=ax+b

　　看看，有幾個(gè)變量？?jī)蓚€(gè)。那是幾維空間的函數(shù)？

　　再看看

　　f（y）=ay

　　里面的y是三維的變量，那f（y）是幾維空間里的函數(shù)？

　　用一個(gè)具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運(yùn)作，想象一下，我們文本分類問題的原始空間是1000維的（即每個(gè)要被分類的文檔被表示為一個(gè)1000維的向量），在這個(gè)維度上問題是線性不可分的。現(xiàn)在我們有一個(gè)2000維空間里的線性函數(shù)

　　f（x’）=《w’，x’》+b

　　注意向量的右上角有個(gè) ’哦。它能夠?qū)⒃瓎栴}變得可分。式中的 w’和x’都是2000維的向量，只不過w’是定值，而x’是變量（好吧，嚴(yán)格說來這個(gè)函數(shù)是2001維的，哈哈），現(xiàn)在我們的輸入呢，是一個(gè)1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個(gè)變換后的向量x’與向量w’的內(nèi)積，再把這個(gè)內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。

　　你發(fā)現(xiàn)了什么？我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來了，分類結(jié)果就算出來了。而從理論上說， x’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x’，對(duì)吧，確定不出第二個(gè)），而w’是常量，它是一個(gè)低維空間里的常量w經(jīng)過變換得到的，所以給了一個(gè)w 和x的值，就有一個(gè)確定的f（x’）值與其對(duì)應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K（w，x），他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值《w’，x’》？

　　如果有這樣的函數(shù)，那么當(dāng)給了一個(gè)低維空間的輸入x以后，

　　g（x）=K（w，x）+b

　　f（x’）=《w’，x’》+b

　　這兩個(gè)函數(shù)的計(jì)算結(jié)果就完全一樣，我們也就用不著費(fèi)力找那個(gè)映射關(guān)系，直接拿低維的輸入往g（x）里面代就可以了（再次提醒，這回的g（x）就不是線性函數(shù)啦，因?yàn)槟悴荒鼙ＷCK（w，x）這個(gè)表達(dá)式里的x次數(shù)不高于1哦）。

　　萬幸的是，這樣的K（w，x）確實(shí)存在（發(fā)現(xiàn)凡是我們?nèi)祟惸芙鉀Q的問題，大都是巧得不能再巧，特殊得不能再特殊的問題，總是恰好有些能投機(jī)取巧的地方才能解決，由此感到人類的渺小），它被稱作核函數(shù)（核，kernel），而且還不止一個(gè)，事實(shí)上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個(gè)低維空間里的向量，能夠計(jì)算出經(jīng)過某個(gè)變換后在高維空間里的向量?jī)?nèi)積值。幾個(gè)比較常用的核函數(shù)，俄，教課書里都列過，我就不敲了（懶?。?。

　　回想我們上節(jié)說的求一個(gè)線性分類器，它的形式應(yīng)該是：

　　現(xiàn)在這個(gè)就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 ’），我們就可以用一個(gè)低維空間里的函數(shù)（再一次的，這個(gè)低維空間里的函數(shù)就不再是線性的啦）來代替，

　　又發(fā)現(xiàn)什么了？f（x’） 和g（x）里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當(dāng)它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積的時(shí)候就用你選定的核函數(shù)來算。這樣求出來的α再和你選定的核函數(shù)一組合，就得到分類器啦！

　　明白了以上這些，會(huì)自然的問接下來兩個(gè)問題：

　　1． 既然有很多的核函數(shù)，針對(duì)具體問題該怎么選擇？

　　2． 如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？

　　第一個(gè)問題現(xiàn)在就可以回答你：對(duì)核函數(shù)的選擇，現(xiàn)在還缺乏指導(dǎo)原則！各種實(shí)驗(yàn)的觀察結(jié)果（不光是文本分類）的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講，徑向基核函數(shù)是不會(huì)出太大偏差的一種，首選。（我做文本分類系統(tǒng)的時(shí)候，使用徑向基核函數(shù)，沒有參數(shù)調(diào)優(yōu)的情況下，絕大部分類別的準(zhǔn)確和召回都在85%以上。

　　感性理解，映射圖：

　　常用的兩個(gè)Kernel函數(shù)：

　　多項(xiàng)式核函數(shù)：

　　高斯核函數(shù)：

　　定義：

　　將核函數(shù)帶入，問題又轉(zhuǎn)化為線性問題啦，如下：

　　求，其中

　　式子是有了，但是如何求結(jié)果呢？不急不急，我會(huì)帶著大家一步一步的解決這個(gè)問題，并且通過動(dòng)手編程使大家對(duì)這個(gè)有個(gè)問題有個(gè)直觀的認(rèn)識(shí)。（PS：大家都對(duì)LIBSVM太依賴了，這樣無助于深入的研究與理解，而且我覺得自己動(dòng)手實(shí)現(xiàn)的話會(huì)比較有成就感）