SVM

SVM簡(jiǎn)介

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

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

　　它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過(guò)使用非線性映射算法將低維輸入空間線性不可分的樣本轉(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ī)，是常見(jiàn)的一種判別方法。在機(jī)器學(xué)習(xí)領(lǐng)域，是一個(gè)有監(jiān)督的學(xué)習(xí)模型，通常用來(lái)進(jìn)行模式識(shí)別、分類(lèi)以及回歸分析。

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

　　它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過(guò)使用非線性映射算法將低維輸入空間線性不可分的樣本轉(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í)，首先要弄清楚這種方法考慮問(wèn)題的特點(diǎn)，這就要從線性可分的最簡(jiǎn)單情況討論起，在沒(méi)有弄懂其原理之前，不要急于學(xué)習(xí)線性不可分等較復(fù)雜的情況，支持向量機(jī)在設(shè)計(jì)時(shí)，需要用到條件極值問(wèn)題的求解，因此需用拉格朗日乘子理論，但對(duì)多數(shù)人來(lái)說(shuō)，以前學(xué)到的或常用的是約束條件為等式表示的方式，但在此要用到以不等式作為必須滿足的條件，此時(shí)只要了解拉格朗日理論的有關(guān)結(jié)論就行。

　　一般特征

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

　　原理介紹

　　SVM方法是通過(guò)一個(gè)非線性映射p，把樣本空間映射到一個(gè)高維乃至無(wú)窮維的特征空間中（Hilbert空間），使得在原來(lái)的樣本空間中非線性可分的問(wèn)題轉(zhuǎn)化為在特征空間中的線性可分的問(wèn)題．簡(jiǎn)單地說(shuō)，就是升維和線性化．升維，就是把樣本向高維空間做映射，一般情況下這會(huì)增加計(jì)算的復(fù)雜性，甚至?xí)?ldquo;維數(shù)災(zāi)難”，因而人們很少問(wèn)津．但是作為分類(lèi)、回歸等問(wèn)題來(lái)說(shuō)，很可能在低維樣本空間無(wú)法線性處理的樣本集，在高維特征空間中卻可以通過(guò)一個(gè)線性超平面實(shí)現(xiàn)線性劃分（或回歸）．一般的升維都會(huì)帶來(lái)計(jì)算的復(fù)雜化，SVM方法巧妙地解決了這個(gè)難題：應(yīng)用核函數(shù)的展開(kāi)定理，就不需要知道非線性映射的顯式表達(dá)式；由于是在高維特征空間中建立線性學(xué)習(xí)機(jī)，所以與線性模型相比，不但幾乎不增加計(jì)算的復(fù)雜性，而且在某種程度上避免了“維數(shù)災(zāi)難”．這一切要?dú)w功于核函數(shù)的展開(kāi)和計(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í)世界的問(wèn)題：

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

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

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

　　SVM算法已廣泛應(yīng)用于生物科學(xué)和其他科學(xué)領(lǐng)域。它們已被用于對(duì)高達(dá)90%正確分類(lèi)的化合物進(jìn)行蛋白質(zhì)分類(lèi)。已經(jīng)提出基于SVM權(quán)重的置換測(cè)試作為解釋SVM模型的機(jī)制。支持向量機(jī)權(quán)重也被用于解釋過(guò)去的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)人類(lèi)的學(xué)習(xí)行為，以獲取新的知識(shí)或技能，重新組織已有的知識(shí)結(jié)構(gòu)使之不斷改善自身的性能。它是人工智能的核心，是使計(jì)算機(jī)具有智能的根本途徑，其應(yīng)用遍及人工智能的各個(gè)領(lǐng)域。

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

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

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

　　SVM一般是用來(lái)分類(lèi)的（一般先分為兩類(lèi)，再向多類(lèi)推廣一生二，二生三，三生萬(wàn)物哈）

　　問(wèn)題的描述

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

　　樣本表示方法：

　　SVM線性分類(lèi)器

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

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

　　圖例：

　　問(wèn)題描述：

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

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

　　進(jìn)行歸一化：

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

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

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

　　看下面這張圖：

　　下面我們要開(kāi)始優(yōu)化上面的式子，因?yàn)橥茖?dǎo)要用到拉格朗日定理和KKT條件，所以我們先了解一下相關(guān)知識(shí)。在求取有約束條件的優(yōu)化問(wèn)題時(shí)，拉格朗日乘子法（Lagrange Multiplier） 和KKT條件是非常重要的兩個(gè)求取方法，對(duì)于等式約束的優(yōu)化問(wèn)題，可以應(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)化問(wèn)題：

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

　　制約條件：

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

　　求偏倒方程

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

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

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

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

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

　　可以列出方程：

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

　　KKT條件詳解

　　對(duì)于含有不等式約束的優(yōu)化問(wèn)題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫(xiě)為一個(gè)式子L（a， b， x）= f（x） + a*g（x）+b*h（x），KKT條件是說(shuō)最優(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ì)的來(lái)源，如支持向量的概念。

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

　　為什么要這么求能得到最優(yōu)值？先說(shuō)拉格朗日乘子法，設(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é)果。（上述描述，我不知道描述清楚沒(méi)，如果與我物理位置很近的話，直接找我，我當(dāng)面講好理解一些，注：下圖來(lái)自wiki）。

　　而KKT條件是滿足強(qiáng)對(duì)偶條件的優(yōu)化問(wèn)題的必要條件，可以這樣理解：我們要求min f（x）， L（a， b， x） = f（x） + a*g（x） + b*h（x），a》=0，我們可以把f（x）寫(xiě)為：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ù)可以寫(xiě)為 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ì)偶就是說(shuō)對(duì)偶式子的最優(yōu)值是等于原問(wèn)題的最優(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），我們來(lái)看看中間兩個(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ì)上是說(shuō) min_x f（x） + a*g（x） + b*h（x） 在x0取得了最小值，用Fermat定理，即是說(shuō)對(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)為零。

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

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

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

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

　　最大化：

　　條件：

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

　　松弛變量（slack vaviable）

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

　　所以我們引入松弛變量對(duì)問(wèn)題進(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)化問(wèn)題：

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

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

　　……

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

　　最終得到：

　　最大化：

　　條件：

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

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

　　核函數(shù)

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

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

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

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

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

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

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

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

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

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

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

　　Sin（ax）的VC維為無(wú)窮大。

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

　　咱們接著要說(shuō)說(shuō)為啥要映射。

　　例子是下面這張圖：

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

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

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

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

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

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

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

　　g（x）=f（y）=ay

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

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

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

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

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

　　g（x）=ax+b

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

　　y=g（x）=ax+b

　　即

　　y=ax+b

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

　　再看看

　　f（y）=ay

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

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

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

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

　　你發(fā)現(xiàn)了什么？我們其實(shí)只關(guān)心那個(gè)高維空間里內(nèi)積的值，那個(gè)值算出來(lái)了，分類(lèi)結(jié)果就算出來(lái)了。而從理論上說(shuō)， x’是經(jīng)由x變換來(lái)的，因此廣義上可以把它叫做x的函數(shù)（有一個(gè)x，就確定了一個(gè)x’，對(duì)吧，確定不出第二個(gè)），而w’是常量，它是一個(gè)低維空間里的常量w經(jīng)過(guò)變換得到的，所以給了一個(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哦）。

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

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

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

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

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

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

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

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

　　感性理解，映射圖：

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

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

　　高斯核函數(shù)：

　　定義：

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

　　求，其中

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