SVM教學講解課件

SupportVectorMachine

支持向量機

1SupportVectorMachine

支持向量機整體概述概述二點擊此處輸入相關文本內容概述一點擊此處輸入相關文本內容概述三點擊此處輸入相關文本內容2整體概述概述二概述一概述三2

內容SVM簡介線性分類器核函數松弛變量LIBSVM介紹實驗3內容SVM簡介3SVM簡介支持向量機(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現出許多特有的優(yōu)勢，并能夠推廣應用到函數擬合等其他機器學習問題中。

4SVM簡介支持向量機(SupportVectorMachSVM簡介支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。5SVM簡介支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和SVM簡介VC維：所謂VC維是對函數類的一種度量，可以簡單的理解為問題的復雜程度，VC維越高，一個問題就越復雜。正是因為SVM關注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數是無關的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決像文本分類這樣的問題，當然，有這樣的能力也因為引入了核函數）。6SVM簡介VC維：所謂VC維是對函數類的一種度量，可以簡單的SVM簡介結構風險最小原理：就是追求“經驗風險”與“置信風險”的和最小。7SVM簡介結構風險最小原理：就是追求“經驗風險”與“置信風險SVM簡介風險：機器學習本質上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設），但毫無疑問，真實模型一定是不知道的。既然真實模型不知道，那么我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。8SVM簡介風險：機器學習本質上就是一種對問題真實模型的逼近（SVM簡介經驗風險Remp(w)

：我們選擇了一個假設之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數據上的分類的結果與真實結果（因為樣本是已經標注過的數據，是準確的數據）之間的差值來表示。這個差值叫做經驗風險Remp(w)。9SVM簡介經驗風險Remp(w)：我們選擇了一個假設之后（SVM簡介

以前的一些機器學習方法把經驗風險最小化作為努力的目標，但后來發(fā)現很多分類函數能夠在樣本集上輕易達到100%的正確率，在真實分類時卻不好（即所謂的推廣能力差，或泛化能力差）。此時的情況是因為選擇了一個足夠復雜的分類函數（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數據一律分類錯誤。因為經驗風險最小化原則適用的大前提是經驗風險要確實能夠逼近真實風險才行。但實際上不太可能，經驗風險最小化原則只在這占很小比例的樣本上做到沒有誤差，不能保證在更大比例的真實文本上也沒有誤差。10SVM簡介以前的一些機器學習方法把經驗風SVM簡介泛化誤差界：為了解決剛才的問題，統(tǒng)計學提出了泛化誤差界的概念。就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知樣本上分類的結果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。11SVM簡介泛化誤差界：為了解決剛才的問題，統(tǒng)計學提出了泛化誤SVM簡介置信風險：與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越??；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。12SVM簡介置信風險：與兩個量有關，一是樣本數量，顯然給定的樣SVM簡介泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)

公式中R(w)就是真實風險，Remp(w)表示經驗風險，Ф(n/h)表示置信風險。此時目標就從經驗風險最小化變?yōu)榱藢で蠼涷烇L險與置信風險的和最小，即結構風險最小。13SVM簡介泛化誤差界的公式為：13SVM簡介小樣本：并不是說樣本的絕對數量少（實際上，對任何算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的復雜度比起來，SVM算法要求的樣本數是相對比較少的。14SVM簡介小樣本：并不是說樣本的絕對數量少（實際上，對任何算SVM簡介非線性：是指SVM擅長應付樣本數據線性不可分的情況，主要通過松弛變量（也叫懲罰變量）和核函數技術來實現，這一部分是SVM的核心內容，后面會詳細說明。15SVM簡介非線性：是指SVM擅長應付樣本數據線性不可分的情況SVM簡介高維模式識別：是指樣本維數很高，SVM也可以應付。這主要是因為SVM產生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數很高，也不會給存儲和計算帶來大麻煩。16SVM簡介高維模式識別：是指樣本維數很高，SVM也可以應付。線性分類器線性分類器：一定意義上，也可以叫做感知機，是最簡單也很有效的分類器形式。在一個線性分類器中，可以看到SVM形成的思路，并接觸很多SVM的核心概念。下面舉例說明。17線性分類器線性分類器：一定意義上，也可以叫做感知機，是最簡線性分類器用一個二維空間里僅有兩類樣本的分類問題來舉例子。如圖所示：C1和C2是要區(qū)分的兩個類別。中間的直線就是一個分類函數，它可以將兩類樣本完全分開。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。

18線性分類器用一個二維空間里僅有兩類樣本的分類問題來舉例子。如線性分類器線性函數在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關注空間的維數，這種線性函數還有一個統(tǒng)一的名稱——超平面（HyperPlane）。19線性分類器線性函數19線性分類器例如我們有一個線性函數

g(x)=wx+b

我們可以取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)>0，就判別為類別C1，若g(xi)<0，則判別為類別C2（等于的時候我們就拒絕判斷）。此時也等價于給函數g(x)附加一個符號函數sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數。20線性分類器例如我們有一個線性函數20線性分類器關于g(x)=wx+b這個表達式要注意三點：1.式中的x不是二維坐標系中的橫軸，而是樣本的向量表示，例如一個樣本點的坐標是(3,8)，則xT=(3,8)，而不是x=3（一般說向量都是說列向量）。2.這個形式并不局限于二維的情況，在n維空間中仍然可以使用這個表達式，只是式中的w成為了n維向量（在二維的這個例子中，w是二維向量，注意這里的w嚴格的說也應該是轉置的形式，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉置）。3.g(x)不是中間那條直線的表達式，中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數叫做分類面。21線性分類器關于g(x)=wx+b這個表達式要注意三點：21線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍微旋轉一下，只要不把兩類數據分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。此時就牽涉到一個問題，對同一個問題存在多個分類函數的時候，哪一個函數更好呢？顯然必須要先找一個指標來量化“好”的程度，通常使用叫做“分類間隔”的指標。

22線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍線性分類器

比如在進行文本分類的時候，我們可以讓計算機這樣來看待我們提供給它的訓練樣本，每一個樣本由一個向量（就是那些文本特征所組成的向量）和一個標記（標示出這個樣本屬于哪個類別）組成。如下：Di=(xi,yi)

xi就是文本向量（維數很高），yi就是分類標記。23線性分類器比如在進行文本分類的時候，我們可線性分類器

在二元的線性分類中，這個表示分類的標記只有兩個值，1和-1（用來表示屬于還是不屬于這個類）。有了這種表示法，我們就可以定義一個樣本點到某個超平面的間隔：δi=yi(wxi+b)首先如果某個樣本屬于該類別的話，那么wxi+b>0，而yi也大于0；若不屬于該類別的話，那么wxi+b<0，而yi也小于0，這意味著yi(wxi+b)總是大于0的，而且它的值就等于|wxi+b|，也就是|g(xi)|。24線性分類器在二元的線性分類中，這個表示分線性分類器

現在把w和b進行歸一化處理，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成：

這就是解析幾何中點xi到直線g(x)=0的距離公式，也就是到超平面g(x)=0的距離。

25線性分類器現在把w和b進行歸一化處理，即用w線性分類器||w||叫做向量w的范數，范數是對向量長度的一種度量。我們常說的向量長度其實指的是它的2-范數，范數最一般的表示形式為p-范數，可以寫成如下表達式向量w=(w1,w2,w3,……wn)它的p-范數為：當我們不指明p的時候，就意味著我們不關心p的值，用幾范數都可以。當用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫幾何間隔，表示的是點到超平面的歐氏距離。26線性分類器||w||叫做向量w的范數，范數是對向量長度線性分類器

下面這張圖直觀的展示出了幾何間隔的現實含義：

H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。27線性分類器下面這張圖直觀的展示出了幾何間隔的線性分類器

之所以如此關心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數間存在關系：

其中的δ是樣本集合到分類面的幾何間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長度最長的值（也就是說代表樣本的分布有多么廣）。誤分次數一定程度上代表分類器的誤差。而從上式可以看出，在樣本已知的情況下，誤分次數的上界由幾何間隔決定！幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了訓練階段的目標。28線性分類器之所以如此關心幾何間隔這個東西線性分類器間隔：δ=y(wx+b)=|g(x)|幾何間隔：

可以看出δ=||w||δ幾何。幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是把所有樣本點中間隔最小的那一點的間隔固定（例如固定為1），尋找最小的||w||。29線性分類器間隔：δ=y(wx+b)=|g(x)|29線性分類器

如果直接來解這個求最小值問題，當||w||=0的時候就得到了目標函數的最小值。但是無論給什么樣的數據，都是這個解！反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點都跑到了H1和H2中間，進入了無法分類的灰色地帶。

造成這種結果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件。30線性分類器如果直接來解這個求最小值問題，線性分類器

之前把所有樣本點中間隔最小的那一點的間隔定為1，這就相當于讓下面的式子總是成立：

yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數）即：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總的樣本數）因此我們的兩類分類問題也被我們轉化成了它的數學形式，一個帶約束的最小值的問題：

31線性分類器之前把所有樣本點中間隔最小的那線性分類器

從最一般的定義上說，一個求最小值的問題就是一個優(yōu)化問題（也叫規(guī)劃），它同樣由兩部分組成，目標函數和約束條件，可以用下面的式子表示：

約束條件用函數c來表示，就是constrain的意思。一共有p+q個約束條件，其中p個是不等式約束，q個等式約束。32線性分類器從最一般的定義上說，一個求最小線性分類器

這個式子中的x是自變量，但不限定它的維數必須為1（視乎你解決的問題空間維數）。要求f(x)在哪一點上取得最小值，但不是在整個空間里找，而是在約束條件所劃定的可行域里找。注意可行域中的每一個點都要求滿足所有p+q個條件，同時可行域邊界上的點有一個額外好的特性，它們可以使不等式約束取得等號！而邊界內的點不行。33線性分類器33線性分類器

這對一般的優(yōu)化問題可能提供不了什么幫助，但對SVM來說，邊界上的點有其特殊意義，實際上是它們唯一決定了分類超平面，這些點（就是以前的圖中恰好落在H1和H2上的點，在文本分類問題中，每一個點代表一個文檔，因而這個點本身也是一個向量）就被稱為支持向量。34線性分類器這對一般的優(yōu)化問題可能提供不了什線性分類器

回頭再看線性分類器問題的描述：

在這個問題中，自變量就是w，目標函數是w的二次函數，所有的約束條件都是w的線性函數（不要把xi當成變量，它代表樣本，是已知的），這種規(guī)劃問題也叫做二次規(guī)劃（QuadraticProgramming，QP）。而且，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。凸二次規(guī)劃的優(yōu)點在于它有全局最優(yōu)解。35線性分類器回頭再看線性分類器問題的描述：線性分類器

但是實際上我們并不知道該怎么解一個帶約束的優(yōu)化問題。我們可以輕松的解一個不帶任何約束的優(yōu)化問題（實際上就是函數求極值，求導再找0點），我們甚至還會解一個只帶等式約束的優(yōu)化問題，就是求條件極值，通過添加拉格朗日乘子，構造拉格朗日函數，來把這個問題轉化為無約束的優(yōu)化問題。如果只帶等式約束的問題可以轉化為無約束的問題來求解，那么可不可以把帶不等式約束的問題向只帶等式約束的問題轉化而得以求解呢？答案是可以。36線性分類器但是實際上我們并不知道該怎么解線性分類器

我們想求得這樣一個線性函數（在n維空間中的線性函數）：g(x)=wx+b

求g(x)的過程就是求w（一個n維向量）和b（一個實數）兩個參數的過程（但實際上只需要求w，求得以后找某些樣本點代入就可以求得b）。因此在求g(x)的時候，w才是變量。37線性分類器我們想求得這樣一個線性函數（在n線性分類器

樣本確定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn

式子中的αi是一個一個的數（在嚴格的證明過程中，這些α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數。為了方便描述，以下開始嚴格區(qū)別數字與向量的乘積和向量間的乘積，用α1x1表示數字和向量的乘積，而用<x1,x2>表示向量x1,x2的內積。因此g(x)的表達式嚴格的形式應該是：g(x)=<w,x>+b38線性分類器樣本確定了w，用數學的語言描述，線性分類器

但是上面的式子還不夠好，如果我不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危?，那么三條直線都必須移動。這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的不等于0（不等于0才對w起決那一堆拉格朗日乘子中，只有很少的一部分定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數。更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以。這部分樣本點，就叫做支持（撐）向量！

39線性分類器但是上面的式子還不夠好，線性分類器

式子也可以用求和符號簡寫一下：

因此原來的g(x)表達式可以寫為：

注意式子中x才是變量，如果要分類哪篇文檔，就把該文檔的向量表示代入到x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內積符號中拿出來，得到g(x)的式子為：

40線性分類器

式子也可以用求和符號簡寫一下：線性分類器

至此w不見了，從求w變成了求α。看似沒有簡化問題，其實簡化了原來的問題，因為以這樣的形式描述問題以后，我們的優(yōu)化了不等式約束。之后的求解就變得很容易了。下面遇到一個問題：如果提供的樣本線性不可分，怎么辦？所以必須要提到SVM中比較重要的內容——核函數。41線性分類器至此w不見了，從求w變成了求α。核函數

之前一直在討論的線性分類器。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程序會無限循環(huán)，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，那么就必須尋找讓線性不可分的數據變得線性可分的方法。42核函數之前一直在討論的線性分類器。如果提核函數

用一個二維平面中的分類問題作例子，如圖：把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。43核函數用一個二維平面中的分類問題作例子，如圖核函數

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

顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別。這條曲線就是我們熟知的二次曲線，它的函數表達式是：44核函數但我們可以找到一條曲線，例如下面這一條：核函數

問題只是它不是一個線性函數，但是，做一下變換，新建一個向量y和a：這樣g(x)就可以轉化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內積的形式寫你可能看不太清楚，實際上f(y)的形式就是：g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數都是一個線性函數，因為自變量y的次數不大于1。原來在二維空間中一個線性不可分的問題，映射到高維空間后，變成了線性可分的！因此也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉化，使其變得線性可分。45核函數問題只是它不是一個線性函數，但是，核函數

用一個具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運作，如果我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的?，F在我們有一個2000維空間里的線性函數f(x’)=<w’,x’>+b

它能夠將原問題變得可分。式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量?，F在我們的輸入呢，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個變換后的向量x’與向量w’的內積，再把這個內積的值和b相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。46核函數用一個具體文本分類的例子來看看這核函數

所以只需要關心那個高維空間里內積的值。而從理論上說，x’是經由x變換來的，因此廣義上可以把它叫做x的函數（因為有一個x，就確定了一個x’），而w’是常量，它是一個低維空間里的常量w經過變換得到的，所以給了一個w和x的值，就有一個確定的f(x’)值與其對應。所以，需要這樣一種函數K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內積值<w’,x’>。也就是當給了一個低維空間的輸入x以后：g(x)=K(w,x)+bf(x’)=<w’,x’>+b

這兩個函數的計算結果就完全一樣，我們也就用不著費力找那個映射關系，直接拿低維的輸入往g(x)里面代就可以了。47核函數所以只需要關心那個高維空核函數

這樣的函數確實存在，它被稱作核函數（核，kernel），而且不止一個，事實上，只要是滿足了Mercer條件的函數，都可以作為核函數。核函數的基本作用就是接受兩個低維空間里的向量，能夠計算出經過某個變換后在高維空間里的向量內積值。這就是說，盡管給的問題是線性不可分的，但是就硬當它是線性問題來求解，只不過求解過程中，凡是要求內積的時候就用選定的核函數來算。這樣求出來的α再和選定的核函數一組合，就得到分類器。。48核函數這樣的函數確實存在，它被稱作核函數（核函數幾個比較常用的核函數如下：49核函數幾個比較常用的核函數如下：49核函數

接下來還有兩個問題：

1.既然有很多的核函數，針對具體問題該怎么選擇？

2.如果使用核函數向高維空間映射后，問題仍然是線性不可分的，那怎么辦？50核函數接下來還有兩個問題：50核函數

對核函數的選擇，現在還缺乏指導原則！各種實驗的觀察結果（不光是文本分類）的確表明，某些問題用某些核函數效果很好，用另一些就很差，但是一般來講，徑向基核函數（RBF）是不會出太大偏差的一種。51核函數對核函數的選擇，現在還缺乏指導原則！核函數

在常用的核函數中，應用最廣泛的是具有較好學習能力的RBF核，無論低維、高維、小樣本、大樣本等情況，RBF核均適應，具有較寬的收斂域，是較為理想的分類依據函數。KeerthiSS等人證明了線性核和多項式核是RBF核的特殊情況。

LinCJ等說明了在某些參數情況下，

Sigmoid核同RBF核具有相似的性能。52核函數在常用的核函數中，應用最廣泛的是具有松弛變量解決第二個問題：

舉個例子，比如我們已經把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的?，F在有這樣一個訓練集，只比原先這個訓練集多了一篇文章，映射到高維空間以后也就多了一個樣本點，但是這個樣本的位置如下圖：53松弛變量解決第二個問題：53松弛變量

就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數點線性不可分）叫做“近似線性可分”的問題。

54松弛變量54松弛變量

按照常識判斷，如果有一萬個點都符合某種規(guī)律，只有一個點不符合，那這個樣本點可能是噪聲。所以即便簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。但程序并沒有這種容錯性。由于在原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點，并在此基礎上尋找正負類之間的最大幾何間隔，而幾何間隔代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。55松弛變量按照常識判斷，如果有一萬個點都符松弛變量

為此引入一個非負的松弛項，有兩種常用的方式：另一種是：其中l(wèi)都是樣本的數目。兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做一階軟間隔分類器，第二種就叫做二階軟間隔分類器。

56松弛變量為此引入一個非負的松弛項，有兩種松弛變量

把損失加入到目標函數里的時候，就需要一個懲罰因子（cost，也就是libSVM的諸多參數中的C），原來的優(yōu)化問題就變成了下面這樣：

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

1.并非所有的樣本點都有一個松弛變量與其對應。只有“離群點”才有。

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

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

4.是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個必須事先指定的值，指定這個值以后，解一下，就得到一個分類器，然后用測試數據看看結果好不好，不好再換一個C的值。如此就是一個參數尋優(yōu)的過程。另外，當遇到數據集偏斜問題時，也是通過調整懲罰因子來解決。58松弛變量3.懲罰因子C決定了你有多重視離群點帶來的損松弛變量核函數與松弛變量作用的區(qū)別：雖然二者的引入都是為了解決線性不可分的問題。但兩者還有微妙的不同。以文本分類為例。在原始的低維空間中，樣本相當的不可分，無論怎么找分類平面，總會有大量的離群點，此時用核函數向高維空間映射一下，雖然結果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)，就是達到了近似線性可分的狀態(tài)。此時再用松弛變量處理那些少數的離群點，就簡單有效得多了。59松弛變量核函數與松弛變量作用的區(qū)別：59SVM用于多類分類一次性得到多個分類面的方法：就是真的一次性考慮所有樣本，并求解一個多目標函數的優(yōu)化問題，一次性得到多個分類面，如下圖：

只可惜這種算法還基本停留在紙面上，因為一次性求解的方法計算量實在太大，大到無法實用的地步。

60SVM用于多類分類一次性得到多個分類面的方法：就是真的一次性SVM用于多類分類“一類對其余”的方法：比如有5個類別，第一次就把類別1的樣本定為正樣本，其余2，3，4，5的樣本合起來定為負樣本，得到一個兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2的樣本定為正樣本，把1，3，4，5的樣本合起來定為負樣本，得到一個分類器，如此下去。但這種方法容易導致分類重疊現象和不可分類現象人為造成“數據集偏斜”問題。61SVM用于多類分類“一類對其余”的方法：比如有5個類別，第一SVM用于多類分類“一對一單挑”的方法：每次選一個類的樣本作正類樣本，而負類樣本則變成只選一個類。因此第一個只回答“是第1類還是第2類”，第二個只回答“是第1類還是第3類”，如此下去。在真正用來分類的時候，把一篇文章扔給所有分類器，讓每一個都投上自己的一票，最后統(tǒng)計票數，如果類別“1”得票最多，就判這篇文章屬于第1類。這種方法使得兩類分類器數目為k(k-1)/2）。類別數如果是1000，要調用的分類器數目會上升至約500000個，過于復雜。62SVM用于多類分類“一對一單挑”的方法：每次選一個類的樣本作SVM用于多類分類

所以必須在分類的時候下功夫。舉個例子，還是像一對一方法那樣來訓練，只是在對一篇文章進行分類之前，先按照下面圖的樣子來組織分類器：

分類時，先問分類器“1對5”（意思是它能夠回答“是第1類還是第5類”），如果回答5，就往左走，再問“2對5”這個分類器，如果還是“5”，繼續(xù)往左走，這樣一直下去，就可以得到分類結果。63SVM用于多類分類所以必須在分類的時候下SVM用于多類分類

這是一個有向無環(huán)圖，因此這種方法也叫做DAGSVM），調用了k-1（K是類別數）個分類器。速度快，且沒有分類重疊和不可分類現象。缺點是假如最一開始的分類器回答錯誤，那么后面的分類器是無法糾正它的錯誤。對下面每一層的分類器都存在這種錯誤向下累積的現象。但是DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論可以證明。并且可以通過調整“根節(jié)點的選取”及輸出“置信度”來改善效果。64SVM用于多類分類這是一個有向無環(huán)圖，因此LIBSVM介紹LIBSVM是臺灣大學林智仁教授2001年開發(fā)的一套支持向量機的庫，運算速度快，可以很方便的對數據做分類或回歸。由于LIBSVM程序小，運用靈活，輸入參數少，并且是開源的，易于擴展，因此成為目前國內應用最多的SVM的庫。這套庫目前已經發(fā)展到2.9版。65LIBSVM介紹LIBSVM是臺灣大學林智仁教授2001年開LIBSVM介紹

工具包里主要有5個文件夾：

1.Java主要是應用于java平臺；

2.Python是用來參數優(yōu)選的工具，稍后介紹；

3.svm-toy是一個可視化的工具，用來展示訓練數據和分類界面，里面是源碼，其編譯后的程序在windows文件夾下；

4.tools—主要包含四個python文件，用來數據集抽樣(subset)，參數優(yōu)選（grid），集成測試(easy),數據檢查(checkdata)；

5.windows包含libSVM四個exe程序包，我們所用的庫就是他們。其中svm-scale.exe是用來對原始樣本進行縮放的；svm-train.exe主要實現對訓練數據集的訓練，并可以獲得SVM模型；svmpredict是根據訓練獲得的模型，對數據集合進行預測。還有一個svm-toy.exe之前已經交待過，是一個可視化工具。66LIBSVM介紹工具包里主要有5個文件夾：LIBSVM介紹libSVM的數據格式如下：Label1:value2:value…Label是類別的標識，比如上節(jié)train.model中提到的1-1，你可以自己隨意定，比如-10，0，15。如果是回歸，這是目標值，就要實事求是了。

Value就是要訓練的數據，從分類的角度來說就是特征值，數據之間用空格隔開，比如：

-151:0.7082:10563:-0.3333

需要注意的是，如果特征值為0，特征冒號前面的(姑且稱做序號)可以不連續(xù)。如：

-151:0.7083:-0.3333

表明第2個特征值為0，從編程的角度來說，這樣做可以減少內存的使用，并提高做矩陣內積時的運算速度。67LIBSVM介紹libSVM的數據格式實驗

實驗樣本選擇工具包下存在的樣本文件：heart_scale。內容截圖如下：68實驗實驗樣本選擇工具包下存在的樣本文件：h實驗

訓練：首先用svm-train進行訓練，輸入以下命令：svm-trainheart_scaletrain.model得到一個結果文件：train.model

69實驗訓練：首先用svm-train進行訓練，輸入以下命實驗可以看到結果：optimizationfinished,#iter=162nu=0.431029obj=-100.877288,rho=0.424462nSV=132,nBSV=107TotalnSV=132

其中，#iter為迭代次數，nu是選擇的核函數類型的參數，obj為SVM文件轉換為的二次規(guī)劃求解得到的最小值，rho為判決函數的偏置項b，nSV為標準支持向量個數(0<a[i]<c)，nBSV為邊界上的支持向量個數(a[i]=c)，TotalnSV為支持向量總個數（對于兩類來說，因為只有一個分類模型TotalnSV=nSV，但是對于多類，這個是各個分類模型的nSV之和）。70實驗可以看到結果：70實驗train.model文件用記事本打開如下圖：

71實驗train.model文件用記事本打開如下圖：71實驗svm_typec_svc//所選擇的svm類型，默認為c_svckernel_typerbf//訓練采用的核函數類型，此處為RBF核

gamma0.0769231//RBF核的參數γnr_class2//類別數，此處為兩分類問題

total_sv132//支持向量總個數

rho0.424462//判決函數的偏置項blabel1-1//原始文件中的類別標識

nr_sv6468//每個類的支持向量機的個數

SV//以下為各個類的權系數及相應的支持向量

11:0.1666672:13:-0.333333…10:-0.90322611:-112:-113:10.51048321289851641:0.1252:13:0.333333…10:-0.80645212:-0.33333313:0.5

………-11:-0.3752:13:-0.333333….10:-111:-112:-113:1-11:0.1666672:13:1….10:-0.87096812:-113:0.572實驗svm_typec_svc實驗

使用svm-predict，根據訓練獲得的模型，對數據集合進行預測。輸入命令：svm-predictheart_scale

heart_scale.modelheart_scale.out

得到準確率是：86.667%。結果如下圖所示：73實驗使用svm-predict，根據訓實驗74實驗74Q&A問答環(huán)節(jié)

敏而好學，不恥下問。

學問學問，邊學邊問。

He

is

quick

and

eager

to

learn.

Learning

is

learning

and

asking.75Q&A問答環(huán)節(jié)

敏而好學，不恥下問。

學問學問，邊學邊問。

感謝參與本課程，也感激大家對我們工作的支持與積極的參與。課程后會發(fā)放課程滿意度評估表，如果對我們課程或者工作有什么建議和意見，也請寫在上邊結束語76感謝參與本課程，也感激大家對我們工作的支持與積極的參與。課程感謝您的觀看與聆聽本課件下載后可根據實際情況進行調整77感謝您的觀看與聆聽本課件下載后可根據實際情況進行調整77SupportVectorMachine

支持向量機

78SupportVectorMachine

支持向量機整體概述概述二點擊此處輸入相關文本內容概述一點擊此處輸入相關文本內容概述三點擊此處輸入相關文本內容79整體概述概述二概述一概述三2

內容SVM簡介線性分類器核函數松弛變量LIBSVM介紹實驗80內容SVM簡介3SVM簡介支持向量機(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現出許多特有的優(yōu)勢，并能夠推廣應用到函數擬合等其他機器學習問題中。

81SVM簡介支持向量機(SupportVectorMachSVM簡介支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。82SVM簡介支持向量機方法是建立在統(tǒng)計學習理論的VC維理論和SVM簡介VC維：所謂VC維是對函數類的一種度量，可以簡單的理解為問題的復雜程度，VC維越高，一個問題就越復雜。正是因為SVM關注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數是無關的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決像文本分類這樣的問題，當然，有這樣的能力也因為引入了核函數）。83SVM簡介VC維：所謂VC維是對函數類的一種度量，可以簡單的SVM簡介結構風險最小原理：就是追求“經驗風險”與“置信風險”的和最小。84SVM簡介結構風險最小原理：就是追求“經驗風險”與“置信風險SVM簡介風險：機器學習本質上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設），但毫無疑問，真實模型一定是不知道的。既然真實模型不知道，那么我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。85SVM簡介風險：機器學習本質上就是一種對問題真實模型的逼近（SVM簡介經驗風險Remp(w)

：我們選擇了一個假設之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數據上的分類的結果與真實結果（因為樣本是已經標注過的數據，是準確的數據）之間的差值來表示。這個差值叫做經驗風險Remp(w)。86SVM簡介經驗風險Remp(w)：我們選擇了一個假設之后（SVM簡介

以前的一些機器學習方法把經驗風險最小化作為努力的目標，但后來發(fā)現很多分類函數能夠在樣本集上輕易達到100%的正確率，在真實分類時卻不好（即所謂的推廣能力差，或泛化能力差）。此時的情況是因為選擇了一個足夠復雜的分類函數（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數據一律分類錯誤。因為經驗風險最小化原則適用的大前提是經驗風險要確實能夠逼近真實風險才行。但實際上不太可能，經驗風險最小化原則只在這占很小比例的樣本上做到沒有誤差，不能保證在更大比例的真實文本上也沒有誤差。87SVM簡介以前的一些機器學習方法把經驗風SVM簡介泛化誤差界：為了解決剛才的問題，統(tǒng)計學提出了泛化誤差界的概念。就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知樣本上分類的結果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。88SVM簡介泛化誤差界：為了解決剛才的問題，統(tǒng)計學提出了泛化誤SVM簡介置信風險：與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越小；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。89SVM簡介置信風險：與兩個量有關，一是樣本數量，顯然給定的樣SVM簡介泛化誤差界的公式為：R(w)≤Remp(w)+Ф(n/h)

公式中R(w)就是真實風險，Remp(w)表示經驗風險，Ф(n/h)表示置信風險。此時目標就從經驗風險最小化變?yōu)榱藢で蠼涷烇L險與置信風險的和最小，即結構風險最小。90SVM簡介泛化誤差界的公式為：13SVM簡介小樣本：并不是說樣本的絕對數量少（實際上，對任何算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的復雜度比起來，SVM算法要求的樣本數是相對比較少的。91SVM簡介小樣本：并不是說樣本的絕對數量少（實際上，對任何算SVM簡介非線性：是指SVM擅長應付樣本數據線性不可分的情況，主要通過松弛變量（也叫懲罰變量）和核函數技術來實現，這一部分是SVM的核心內容，后面會詳細說明。92SVM簡介非線性：是指SVM擅長應付樣本數據線性不可分的情況SVM簡介高維模式識別：是指樣本維數很高，SVM也可以應付。這主要是因為SVM產生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本），使得即使樣本維數很高，也不會給存儲和計算帶來大麻煩。93SVM簡介高維模式識別：是指樣本維數很高，SVM也可以應付。線性分類器線性分類器：一定意義上，也可以叫做感知機，是最簡單也很有效的分類器形式。在一個線性分類器中，可以看到SVM形成的思路，并接觸很多SVM的核心概念。下面舉例說明。94線性分類器線性分類器：一定意義上，也可以叫做感知機，是最簡線性分類器用一個二維空間里僅有兩類樣本的分類問題來舉例子。如圖所示：C1和C2是要區(qū)分的兩個類別。中間的直線就是一個分類函數，它可以將兩類樣本完全分開。一般的，如果一個線性函數能夠將樣本完全正確的分開，就稱這些數據是線性可分的，否則稱為非線性可分的。

95線性分類器用一個二維空間里僅有兩類樣本的分類問題來舉例子。如線性分類器線性函數在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關注空間的維數，這種線性函數還有一個統(tǒng)一的名稱——超平面（HyperPlane）。96線性分類器線性函數19線性分類器例如我們有一個線性函數

g(x)=wx+b

我們可以取閾值為0，這樣當有一個樣本xi需要判別的時候，我們就看g(xi)的值。若g(xi)>0，就判別為類別C1，若g(xi)<0，則判別為類別C2（等于的時候我們就拒絕判斷）。此時也等價于給函數g(x)附加一個符號函數sgn()，即f(x)=sgn[g(x)]是我們真正的判別函數。97線性分類器例如我們有一個線性函數20線性分類器關于g(x)=wx+b這個表達式要注意三點：1.式中的x不是二維坐標系中的橫軸，而是樣本的向量表示，例如一個樣本點的坐標是(3,8)，則xT=(3,8)，而不是x=3（一般說向量都是說列向量）。2.這個形式并不局限于二維的情況，在n維空間中仍然可以使用這個表達式，只是式中的w成為了n維向量（在二維的這個例子中，w是二維向量，注意這里的w嚴格的說也應該是轉置的形式，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉置）。3.g(x)不是中間那條直線的表達式，中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數叫做分類面。98線性分類器關于g(x)=wx+b這個表達式要注意三點：21線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍微旋轉一下，只要不把兩類數據分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。此時就牽涉到一個問題，對同一個問題存在多個分類函數的時候，哪一個函數更好呢？顯然必須要先找一個指標來量化“好”的程度，通常使用叫做“分類間隔”的指標。

99線性分類器分類間隔：下圖中間那條分界線并不是唯一的，把它稍線性分類器

比如在進行文本分類的時候，我們可以讓計算機這樣來看待我們提供給它的訓練樣本，每一個樣本由一個向量（就是那些文本特征所組成的向量）和一個標記（標示出這個樣本屬于哪個類別）組成。如下：Di=(xi,yi)

xi就是文本向量（維數很高），yi就是分類標記。100線性分類器比如在進行文本分類的時候，我們可線性分類器

在二元的線性分類中，這個表示分類的標記只有兩個值，1和-1（用來表示屬于還是不屬于這個類）。有了這種表示法，我們就可以定義一個樣本點到某個超平面的間隔：δi=yi(wxi+b)首先如果某個樣本屬于該類別的話，那么wxi+b>0，而yi也大于0；若不屬于該類別的話，那么wxi+b<0，而yi也小于0，這意味著yi(wxi+b)總是大于0的，而且它的值就等于|wxi+b|，也就是|g(xi)|。101線性分類器在二元的線性分類中，這個表示分線性分類器

現在把w和b進行歸一化處理，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成：

這就是解析幾何中點xi到直線g(x)=0的距離公式，也就是到超平面g(x)=0的距離。

102線性分類器現在把w和b進行歸一化處理，即用w線性分類器||w||叫做向量w的范數，范數是對向量長度的一種度量。我們常說的向量長度其實指的是它的2-范數，范數最一般的表示形式為p-范數，可以寫成如下表達式向量w=(w1,w2,w3,……wn)它的p-范數為：當我們不指明p的時候，就意味著我們不關心p的值，用幾范數都可以。當用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫幾何間隔，表示的是點到超平面的歐氏距離。103線性分類器||w||叫做向量w的范數，范數是對向量長度線性分類器

下面這張圖直觀的展示出了幾何間隔的現實含義：

H是分類面，而H1和H2是平行于H，且過離H最近的兩類樣本的直線，H1與H，H2與H之間的距離就是幾何間隔。104線性分類器下面這張圖直觀的展示出了幾何間隔的線性分類器

之所以如此關心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數間存在關系：

其中的δ是樣本集合到分類面的幾何間隔，R=max||xi||

i=1,...,n，即R是所有樣本中向量長度最長的值（也就是說代表樣本的分布有多么廣）。誤分次數一定程度上代表分類器的誤差。而從上式可以看出，在樣本已知的情況下，誤分次數的上界由幾何間隔決定！幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了訓練階段的目標。105線性分類器之所以如此關心幾何間隔這個東西線性分類器間隔：δ=y(wx+b)=|g(x)|幾何間隔：

可以看出δ=||w||δ幾何。幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是把所有樣本點中間隔最小的那一點的間隔固定（例如固定為1），尋找最小的||w||。106線性分類器間隔：δ=y(wx+b)=|g(x)|29線性分類器

如果直接來解這個求最小值問題，當||w||=0的時候就得到了目標函數的最小值。但是無論給什么樣的數據，都是這個解！反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點都跑到了H1和H2中間，進入了無法分類的灰色地帶。

造成這種結果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件。107線性分類器如果直接來解這個求最小值問題，線性分類器

之前把所有樣本點中間隔最小的那一點的間隔定為1，這就相當于讓下面的式子總是成立：

yi[(w·xi)+b]≥1(i=1,2,…,l)（l是總的樣本數）即：

yi[(w·xi)+b]-1≥0(i=1,2,…,l)（l是總的樣本數）因此我們的兩類分類問題也被我們轉化成了它的數學形式，一個帶約束的最小值的問題：

108線性分類器之前把所有樣本點中間隔最小的那線性分類器

從最一般的定義上說，一個求最小值的問題就是一個優(yōu)化問題（也叫規(guī)劃），它同樣由兩部分組成，目標函數和約束條件，可以用下面的式子表示：

約束條件用函數c來表示，就是constrain的意思。一共有p+q個約束條件，其中p個是不等式約束，q個等式約束。109線性分類器從最一般的定義上說，一個求最小線性分類器

這個式子中的x是自變量，但不限定它的維數必須為1（視乎你解決的問題空間維數）。要求f(x)在哪一點上取得最小值，但不是在整個空間里找，而是在約束條件所劃定的可行域里找。注意可行域中的每一個點都要求滿足所有p+q個條件，同時可行域邊界上的點有一個額外好的特性，它們可以使不等式約束取得等號！而邊界內的點不行。110線性分類器33線性分類器

這對一般的優(yōu)化問題可能提供不了什么幫助，但對SVM來說，邊界上的點有其特殊意義，實際上是它們唯一決定了分類超平面，這些點（就是以前的圖中恰好落在H1和H2上的點，在文本分類問題中，每一個點代表一個文檔，因而這個點本身也是一個向量）就被稱為支持向量。111線性分類器這對一般的優(yōu)化問題可能提供不了什線性分類器

回頭再看線性分類器問題的描述：

在這個問題中，自變量就是w，目標函數是w的二次函數，所有的約束條件都是w的線性函數（不要把xi當成變量，它代表樣本，是已知的），這種規(guī)劃問題也叫做二次規(guī)劃（QuadraticProgramming，QP）。而且，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。凸二次規(guī)劃的優(yōu)點在于它有全局最優(yōu)解。112線性分類器回頭再看線性分類器問題的描述：線性分類器

但是實際上我們并不知道該怎么解一個帶約束的優(yōu)化問題。我們可以輕松的解一個不帶任何約束的優(yōu)化問題（實際上就是函數求極值，求導再找0點），我們甚至還會解一個只帶等式約束的優(yōu)化問題，就是求條件極值，通過添加拉格朗日乘子，構造拉格朗日函數，來把這個問題轉化為無約束的優(yōu)化問題。如果只帶等式約束的問題可以轉化為無約束的問題來求解，那么可不可以把帶不等式約束的問題向只帶等式約束的問題轉化而得以求解呢？答案是可以。113線性分類器但是實際上我們并不知道該怎么解線性分類器

我們想求得這樣一個線性函數（在n維空間中的線性函數）：g(x)=wx+b

求g(x)的過程就是求w（一個n維向量）和b（一個實數）兩個參數的過程（但實際上只需要求w，求得以后找某些樣本點代入就可以求得b）。因此在求g(x)的時候，w才是變量。114線性分類器我們想求得這樣一個線性函數（在n線性分類器

樣本確定了w，用數學的語言描述，就是w可以表示為樣本的某種組合：w=α1x1+α2x2+…+αnxn

式子中的αi是一個一個的數（在嚴格的證明過程中，這些α被稱為拉格朗日乘子），而xi是樣本點，因而是向量，n就是總樣本點的個數。為了方便描述，以下開始嚴格區(qū)別數字與向量的乘積和向量間的乘積，用α1x1表示數字和向量的乘積，而用<x1,x2>表示向量x1,x2的內積。因此g(x)的表達式嚴格的形式應該是：g(x)=<w,x>+b115線性分類器樣本確定了w，用數學的語言描述，線性分類器

但是上面的式子還不夠好，如果我不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危?，那么三條直線都必須移動。這說明w不僅跟樣本點的位置有關，還跟樣本的類別有關因此用下面這個式子表示才算完整：w=α1y1x1+α2y2x2+…+αnynxn

其中的yi就是第i個樣本的標簽，它等于1或者-1。其實以上式子的不等于0（不等于0才對w起決那一堆拉格朗日乘子中，只有很少的一部分定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本唯一的確定了分類函數。更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以。這部分樣本點，就叫做支持（撐）向量！

116線性分類器但是上面的式子還不夠好，線性分類器

式子也可以用求和符號簡寫一下：

因此原來的g(x)表達式可以寫為：

注意式子中x才是變量，如果要分類哪篇文檔，就把該文檔的向量表示代入到x的位置，而所有的xi統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有xi和x是向量，因此一部分可以從內積符號中拿出來，得到g(x)的式子為：

117線性分類器

式子也可以用求和符號簡寫一下：線性分類器

至此w不見了，從求w變成了求α?？此茮]有簡化問題，其實簡化了原來的問題，因為以這樣的形式描述問題以后，我們的優(yōu)化了不等式約束。之后的求解就變得很容易了。下面遇到一個問題：如果提供的樣本線性不可分，怎么辦？所以必須要提到SVM中比較重要的內容——核函數。118線性分類器至此w不見了，從求w變成了求α。核函數

之前一直在討論的線性分類器。如果提供的樣本線性不可分，結果很簡單，線性分類器的求解程序會無限循環(huán)，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，那么就必須尋找讓線性不可分的數據變得線性可分的方法。119核函數之前一直在討論的線性分類器。如果提核函數

用一個二維平面中的分類問題作例子，如圖：把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數把兩類正確分開么？不能，因為二維空間里的線性函數就是指直線，顯然找不到符合條件的直線。120核函數用一個二維平面中的分類問題作例子，如圖核函數

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

顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別。這條曲線就是我們熟知的二次曲線，它的函數表達式是：121核函數但我們可以找到一條曲線，例如下面這一條：核函數

問題只是它不是一個線性函數，但是，做一下變換，新建一個向量y和a：這樣g(x)就可以轉化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內積的形式寫你可能看不太清楚，實際上f(y)的形式就是：g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數都是一個線性函數，因為自變量y的次數不大于1。原來在二維空間中一個線性不可分的問題，映射到高維空間后，變成了線性可分的！因此也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉化，使其變得線性可分。122核函數問題只是它不是一個線性函數，但是，核函數

用一個具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運作，如果我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的。現在我們有一個2000維空間里的線性函數f(x’)=<w’,x’>+b

它能夠將原問題變得可分。式中的w’和x’都是2000維的向量，只不過w’是定值，而x’是變量?，F在我們的輸入呢，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x’，然后求這個變換后的向量x’與向量w’的內積，再把這個內積的值和b相加，就得到了結果，看結果大于閾值還是小于閾值就得到了分類結果。123核函數用一個具體文本分類的例子來看看這核函數

所以只需要關心那個高維空間里內積的值。而從理論上說，x’是經由x變換來的，因此廣義上可以把它叫做x的函數（因為有一個x，就確定了一個x’），而w’是常量，它是一個低維空間里的常量w經過變換得到的，所以給了一個w和x的值，就有一個確定的f(x’)值與其對應。所以，需要這樣一種函數K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內積值<w’,x’>。也就是當給了一個低維空間的輸入x以后：g(x)=K(w,x)+bf(x’)=<w’,x’>+b

這兩個函數的計算結果就完全一樣，我們也就用不著費力找那個映射關系，直接拿低維的輸入往g(x)里面代就可以了。124核函數所以只需要關心那個高維空核函數

這樣的函數確實存在，它被稱作核函數（核，kernel），而且不止一個，事實上，只要是滿足了Mercer條件的函數，都可以作為核函數。核函數的基本作用就