接着我們看感覺機模型的損失函數優化，它的思想是讓所有誤分類的點(定義為M)到超平面的距離和最小，即最小化下式：
∑xi∈M−y(i)(wTx(i)+b)/||w||2∑xi∈M−y(i)(wTx(i)+b)/||w||2
當w和bw和b成比例的增加，比如,當分子的w和bw和b擴大N倍時，分母的L2範數也會擴大N倍。也就是說，分子和分母有固定的倍數關系。那麼我們可以固定分子或者分母為1，然後求另一個即分子自己或者分母的倒數的最小化作為損失函數，這樣可以簡化我們的損失函數。在感覺機模型中，我們采用的是保留分子，固定分母||w||2=1||w||2=1,即最終感覺機模型的損失函數為：
∑xi∈M−y(i)(wTx(i)+b)∑xi∈M−y(i)(wTx(i)+b)
如果我們不是固定分母，改為固定分子，作為分類模型有沒有改進呢？
這些問題在我們引入SVM後會詳細解釋。
在正式介紹SVM的模型和損失函數之前，我們還需要先了解下函數間隔和幾何間隔的知識。
在分離超平面固定為wTx+b=0wTx+b=0的時候，|wTx+b||wTx+b|表示點x到超平面的距離。通過觀察wTx+bwTx+b和y是否同号，我們判斷分類是否正确，這些知識我們在感覺機模型裡都有講到。這裡我們引入函數間隔的概念，定義函數間隔γ′γ′為：
γ′=y(wTx+b)γ′=y(wTx+b)
可以看到，它就是感覺機模型裡面的誤分類點到超平面距離的分子。對于訓練集中m個樣本點對應的m個函數間隔的最小值，就是整個訓練集的函數間隔。
函數間隔并不能正常反應點到超平面的距離，在感覺機模型裡我們也提到，當分子成比例的增長時，分母也是成倍增長。為了統一度量，我們需要對法向量ww加上限制條件，這樣我們就得到了幾何間隔γγ,定義為：
γ=y(wTx+b)||w||2=γ′||w||2γ=y(wTx+b)||w||2=γ′||w||2
幾何間隔才是點到超平面的真正距離，感覺機模型裡用到的距離就是幾何距離。
在感覺機模型中，我們可以找到多個可以分類的超平面将資料分開，并且優化時希望所有的點都離超平面遠。但是實際上離超平面很遠的點已經被正确分類，我們讓它離超平面更遠并沒有意義。反而我們最關心是那些離超平面很近的點，這些點很容易被誤分類。如果我們可以讓離超平面比較近的點盡可能的遠離超平面，那麼我們的分類效果會好有一些。SVM的思想起源正起于此。
如下圖所示，分離超平面為wTx+b=0wTx+b=0，如果所有的樣本不光可以被超平面分開，還和超平面保持一定的函數距離（下圖函數距離為1），那麼這樣的分類超平面是比感覺機的分類超平面優的。可以證明，這樣的超平面隻有一個。和超平面平行的保持一定的函數距離的這兩個超平面對應的向量，我們定義為支援向量，如下圖虛線所示。
支援向量到超平面的距離為1/||w||21/||w||2,兩個支援向量之間的距離為2/||w||22/||w||2。
SVM的模型是讓所有點到超平面的距離大于一定的距離，也就是所有的分類點要在各自類别的支援向量兩邊。用數學式子表示為：
maxγ=y(wTx+b)||w||2s.tyi(wTxi+b)=γ′(i)≥γ′(i=1,2,...m)maxγ=y(wTx+b)||w||2s.tyi(wTxi+b)=γ′(i)≥γ′(i=1,2,...m)
一般我們都取函數間隔γ′γ′為1，這樣我們的優化函數定義為：
max1||w||2s.tyi(wTxi+b)≥1(i=1,2,...m)max1||w||2s.tyi(wTxi+b)≥1(i=1,2,...m)
也就是說，我們要在限制條件yi(wTxi+b)≥1(i=1,2,...m)yi(wTxi+b)≥1(i=1,2,...m)下，最大化1)||w||21)||w||2。可以看出，這個感覺機的優化方式不同，感覺機是固定分母優化分子，而SVM是固定分子優化分母，同時加上了支援向量的限制。
由于1||w||21||w||2的最大化等同于12||w||2212||w||22的最小化。這樣SVM的優化函數等價于：
min12||w||22s.tyi(wTxi+b)≥1(i=1,2,...m)min12||w||22s.tyi(wTxi+b)≥1(i=1,2,...m)
L(w,b,α)=12||w||22−∑i=1mαi[yi(wTxi+b)−1]滿足αi≥0L(w,b,α)=12||w||22−∑i=1mαi[yi(wTxi+b)−1]滿足αi≥0
由于引入了朗格朗日乘子，我們的優化目标變成：
minw,bmaxαi≥0L(w,b,α)min⏟w,bmax⏟αi≥0L(w,b,α)
和最大熵模型一樣的，我們的這個優化函數滿足KKT條件，也就是說，我們可以通過拉格朗日對偶将我們的優化問題轉化為等價的對偶問題來求解。如果對凸優化和拉格朗日對偶不熟悉，建議閱讀鮑德的《凸優化》。
也就是說，現在我們要求的是：
maxαi≥0minw,bL(w,b,α)max⏟αi≥0min⏟w,bL(w,b,α)
從上式中，我們可以先求優化函數對于w和bw和b的極小值。接着再求拉格朗日乘子αα的極大值。
首先我們來求w和bw和b的極小值，即minw,bL(w,b,α)min⏟w,bL(w,b,α)。這個極值我們可以通過對w和bw和b分别求偏導數得到：
∂L∂w=0⇒w=∑i=1mαiyixi∂L∂w=0⇒w=∑i=1mαiyixi
∂L∂b=0⇒∑i=1mαiyi=0∂L∂b=0⇒∑i=1mαiyi=0
從上兩式子可以看出，我們已經求得了w和αw和α的關系，隻要我們後面接着能夠求出優化函數極大化對應的αα，就可以求出我們的ww了，至于b，由于上兩式已經沒有b，是以最後的b可以有多個。
好了，既然我們已經求出w和αw和α的關系，就可以帶入優化函數L(w,b,α)L(w,b,α)消去ww了。我們定義:
ψ(α)=minw,bL(w,b,α)ψ(α)=min⏟w,bL(w,b,α)
現在我們來看将ww替換為αα的表達式以後的優化函數ψ(α)ψ(α)的表達式：
ψ(α)=12||w||22−∑i=1mαi[yi(wTxi+b)−1]=12wTw−∑i=1mαiyiwTxi−∑i=1mαiyib+∑i=1mαi=12wT∑i=1mαiyixi−∑i=1mαiyiwTxi−∑i=1mαiyib+∑i=1mαi=12wT∑i=1mαiyixi−wT∑i=1mαiyixi−∑i=1mαiyib+∑i=1mαi=−12wT∑i=1mαiyixi−∑i=1mαiyib+∑i=1mαi=−12wT∑i=1mαiyixi−b∑i=1mαiyi+∑i=1mαi=−12(∑i=1mαiyixi)T(∑i=1mαiyixi)−b∑i=1mαiyi+∑i=1mαi=−12∑i=1mαiyixTi∑i=1mαiyixi−b∑i=1mαiyi+∑i=1mαi=−12∑i=1mαiyixTi∑i=1mαiyixi+∑i=1mαi=−12∑i=1,j=1mαiyixTiαjyjxj+∑i=1mαi=∑i=1mαi−12∑i=1,j=1mαiαjyiyjxTixj(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(1)ψ(α)=12||w||22−∑i=1mαi[yi(wTxi+b)−1](2)=12wTw−∑i=1mαiyiwTxi−∑i=1mαiyib+∑i=1mαi(3)=12wT∑i=1mαiyixi−∑i=1mαiyiwTxi−∑i=1mαiyib+∑i=1mαi(4)=12wT∑i=1mαiyixi−wT∑i=1mαiyixi−∑i=1mαiyib+∑i=1mαi(5)=−12wT∑i=1mαiyixi−∑i=1mαiyib+∑i=1mαi(6)=−12wT∑i=1mαiyixi−b∑i=1mαiyi+∑i=1mαi(7)=−12(∑i=1mαiyixi)T(∑i=1mαiyixi)−b∑i=1mαiyi+∑i=1mαi(8)=−12∑i=1mαiyixiT∑i=1mαiyixi−b∑i=1mαiyi+∑i=1mαi(9)=−12∑i=1mαiyixiT∑i=1mαiyixi+∑i=1mαi(10)=−12∑i=1,j=1mαiyixiTαjyjxj+∑i=1mαi(11)=∑i=1mαi−12∑i=1,j=1mαiαjyiyjxiTxj
其中，(1)式到(2)式用到了範數的定義||w||22=wTw||w||22=wTw, (2)式到(3)式用到了上面的w=∑i=1mαiyixiw=∑i=1mαiyixi， (3)式到(4)式把和樣本無關的wTwT提前，(4)式到(5)式合并了同類項，(5)式到(6)式把和樣本無關的bb提前，(6)式到(7)式繼續用到w=∑i=1mαiyixiw=∑i=1mαiyixi，（7）式到(8)式用到了向量的轉置。由于常量的轉置是其本身，所有隻有向量xixi被轉置，（8）式到(9)式用到了上面的∑i=1mαiyi=0∑i=1mαiyi=0，（9）式到(10)式使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運算法則，（10）式到(11)式僅僅是位置的調整。
從上面可以看出，通過對w,bw,b極小化以後，我們的優化函數ψ(α)ψ(α)僅僅隻有αα向量做參數。隻要我們能夠極大化ψ(α)ψ(α)，就可以求出此時對應的αα，進而求出w,bw,b.
對ψ(α)ψ(α)求極大化的數學表達式如下:
maxα−12∑i=1m∑j=1mαiαjyiyj(xi∙xj)+∑i=1mαimax⏟α−12∑i=1m∑j=1mαiαjyiyj(xi∙xj)+∑i=1mαi
s.t.∑i=1mαiyi=0s.t.∑i=1mαiyi=0
αi≥0i=1,2,...mαi≥0i=1,2,...m
可以去掉負号，即為等價的極小化問題如下：
minα12∑i=1m∑j=1mαiαjyiyj(xi∙xj)−∑i=1mαimin⏟α12∑i=1m∑j=1mαiαjyiyj(xi∙xj)−∑i=1mαi
隻要我們可以求出上式極小化時對應的αα向量就可以求出w和bw和b了。具體怎麼極小化上式得到對應的αα，一般需要用到SMO算法，這個算法比較複雜，我們後面會專門來講。在這裡，我們假設通過SMO算法，我們得到了對應的αα的值α∗α∗。
那麼我們根據w=∑i=1mαiyixiw=∑i=1mαiyixi，可以求出對應的ww的值
w∗=∑i=1mα∗iyixiw∗=∑i=1mαi∗yixi
求b則稍微麻煩一點。注意到，對于任意支援向量(xx,ys)(xx,ys)，都有
ys(wTxs+b)=ys(∑i=1SαiyixTixs+b)=1ys(wTxs+b)=ys(∑i=1SαiyixiTxs+b)=1
假設我們有S個支援向量，則對應我們求出S個b∗b∗,理論上這些b∗b∗都可以作為最終的結果， 但是我們一般采用一種更健壯的辦法，即求出所有支援向量所對應的b∗sbs∗，然後将其平均值作為最後的結果。
怎麼得到支援向量呢？根據KKT條件中的對偶互補條件α∗i(yi(wTxi+b)−1)=0αi∗(yi(wTxi+b)−1)=0，如果αi>0αi>0則有yi(wTxi+b)=1yi(wTxi+b)=1 即點在支援向量上，否則如果αi=0αi=0則有yi(wTxi+b)≥1yi(wTxi+b)≥1，即樣本在支援向量上或者已經被正确分類。
這裡我們對線性可分SVM的算法過程做一個總結。
輸入是線性可分的m個樣本(x1,y1),(x2,y2),...,(xm,ym),(x1,y1),(x2,y2),...,(xm,ym),,其中x為n維特征向量。y為二進制輸出，值為1，或者-1.
輸出是分離超平面的參數w∗和b∗w∗和b∗和分類決策函數。
算法過程如下：
1）構造限制優化問題
2）用SMO算法求出上式最小時對應的αα向量的值α∗α∗向量.
3) 計算w∗=∑i=1mα∗iyixiw∗=∑i=1mαi∗yixi
4) 找出所有的S個支援向量,即滿足αs>0對應的樣本(xs,ys)αs>0對應的樣本(xs,ys)，通過 ys(∑i=1SαiyixTixs+b)=1ys(∑i=1SαiyixiTxs+b)=1，計算出每個支援向量(xx,ys)(xx,ys)對應的b∗sbs∗,計算出這些b∗s=ys−∑i=1SαiyixTixsbs∗=ys−∑i=1SαiyixiTxs. 所有的b∗sbs∗對應的平均值即為最終的b∗=1S∑i=1Sb∗sb∗=1S∑i=1Sbs∗
這樣最終的分類超平面為：w∗∙x+b∗=0w∗∙x+b∗=0，最終的分類決策函數為：f(x)=sign(w∗∙x+b∗)f(x)=sign(w∗∙x+b∗)
線性可分SVM的學習方法對于非線性的資料集是沒有辦法使用的， 有時候不能線性可分的原因是線性資料集裡面多了少量的異常點，由于這些異常點導緻了資料集不能線性可分， 那麼怎麼可以處理這些異常點使資料集依然可以用線性可分的思想呢？ 我們在下一節的線性SVM的軟間隔最大化裡繼續講。
本文轉自劉建平Pinard部落格園部落格，原文連結：http://www.cnblogs.com/pinard/p/6097604.html，如需轉載請自行聯系原作者