這篇是寫如何實作SVM，但首先要來講解的是SVM是什麼～不然不知道這個是什麼，要怎麼實作呢？
SVM是什麼？
SVM(Support Vector Machine)支持向量機器，是一種分類器，訂定一個邊界大小，然後畫出一條界線，形成一個邊界帶，來區分不同的群．理想上所有的元素都不會去碰到邊界帶裡面，因此可以很明確地定義元素是屬於哪一個群．
SVM怎麼運作？
原理上的SVM
SVM概念上很簡單，劃一條邊界帶區分兩個族群就對了，但現在要加上一些限制條件，讓它更符合現實．首先，我們先把情境拉到二維的狀況，並且這個二維空間(x,y)平面上面有兩個點，分別為A(1,0), B(5,6)，區分這兩點的其中一種方式就是把AB的向量求出來，並且求出AB的中點C(3,3)當成該區隔線的一個點，畫出一條垂直於AB向量的線段，AB的長度除以2就是邊界帶的寬度，這個寬度的大小就是√((5–1)²+(6–0)²)/2=√13．我們把A標記為＋1,B標記為-1，只要落在A這側的點都會是＋１，落在Ｂ側的點都會是-1．這條線用國中的二元一次方程式表示，就會像這樣：
Line1: y=(-2/3)x+5…(1)
假設今天我們有一個點Ｄ(10,19)，我們就來算點Ｄ跟邊界線的最短距離～我們來找Line1上的一點Ｅ使得ＤＥ的長度離Line1最短，Ｅ為(6/13,61/13) ， ＤＥ的長度為：62√13/13，這個值比邊界帶寬√13大，所以我們確定它一定在邊界帶以外，是可分群的．
但是，如果只有距離，要怎麼分+1還是-1呢？這個就是支持向量機，為甚麼有個“向量“的原因了！
今天，我們把Ａ標記為＋1，就代表我們把（從邊界帶到Ａ側）向量CA的方向定義成正方向，跟ＣＡ同方向的向量都會被當成正的．
反之，和向量CB同方向的向量都會被當成負的．今天我們的向量ED是(124/13,186/13)和CB向量(2,3)是同方向的，因此D點就會被標註成-1．和B點是同一群的．
如果點掉入邊界帶內怎麼辦？
點掉入邊界帶的話，就代表這個邊界線和邊界帶沒辦法有效地分群，此時，我們就會拿掉進邊界帶的點當作新的基準來運算出新的邊界線和邊界帶．要構成一個邊界帶和邊界線，至少需要兩個不同群的基準點來定義．
從純量到向量
今天，我們把上述的xy平面，改變其敘述，變成x1,x2空間，CA之向量(-2,-3)當成一個法向量Ｗ，x為從原點到該空間任意點x=(x1,x2)的一個向量．
今天描述該分界線的方程式將從純量的敘述式變成向量的敘述式：
Ｗ⋅x+𝛿=0 …(2)
𝛿是一個純量，也就是說法向量Ｗ和x向量內積的值加上𝛿以後如果等於0的話，x就是分界線上的一個點．
根據之前純量式的推演C(3,3)為分界線上的一點，因此：
(-2,-3)⋅(3,3)+𝛿=0;
-2 *3-3 *3=-𝛿
-15 =-𝛿
𝛿=15
我們拿基準點Ａ來驗證，在這我們把原點到Ａ點的向量作為基準向量A，更正式的說法：
支持向量Ａ
這就是支持向量機器的“支持向量”的名稱由來～
Ｗ⋅A+𝛿
(-2,-3)⋅(1,0)+15=13
即為邊界帶寬之平方
拿支持向量Ｂ來測試
Ｗ⋅B+𝛿
(-2,-3)⋅(5,6)+15=-13
其值也為邊界帶寬平方，只是多了個負號
為了計算方便，我們會把方程式除以邊界帶寬平方，以讓支持向量算出來的結果剛好為＋1/-1．
因此新方程式為：
w=W/‖W‖²=(-2/13,-3/13)
b=𝛿/‖W‖²=15/13
邊界線的新方程式：
w⋅x+b=0…(3)
A類別的判定範圍：
w⋅x+b≧1…(4)
Ｂ類別的判定範圍：
w⋅x+b≦-1…(5)
今天如果有新的點p要判斷：
其結果y如下：
y=w⋅p+b
如果w⋅p+b≧1,其結果y輸出為1 當作A類別
如果w⋅p+b≦-1,其結果y輸出為-1 當作B類別
以上就是SVM的基本原理
另外，你今天有多少種特徵要丟進去測試，SVM的空間維度就有多少．
上述的例子是兩個維度
拿iris data[4]當做例子，有四個參數
1.sepal length in cm
2. sepal width in cm
3. petal length in cm
4. petal width in cm
所以對SVM而言就有四個維度，至於class就是我們要的y輸出．
實作上的SVM
以現實面來看，不會這麼剛好只有兩個點來算邊界，大部分都是上百上萬，要從成千上萬的點來製作邊界線是一件非常困難的事，要如何選到好的點當作支持向量，就必須依靠好的數學方法～
今天，吾人想求的就是一個分界線的方程式，因此，在這個情況下，法向量w以及純量b就是我們要算出來的未知數．
目前最常用的數學方法，就是拉朗格日法(Lagrange Method)[1]，使用該方法前，得先歸納我們目前有的數學方程式：
- 邊界條件：
從(4)(5)
如果w⋅x+b≧1 ,則 y=1…(6)
如果 w⋅x+b≦-1,則 y=-1…(7)
總和(6)(7)：
g(w,b)=y(w⋅x+b)≧1…(8)
2. 邊界帶寬條件：
由之前推導出的帶寬：√13
以及結合新的法向量條件
w=(-2/13,-3/13),
‖w‖=1/√13
帶寬=1/‖w‖
在SVM裡，我們希望帶寬越大越好(帶寬越大，過度擬合的機會越低)，因此‖w‖越小越好．在這，我們使用
f(w)=(1/2)‖w‖²…(9)
當作最小化‖w‖的目標函數
由(8)和(9)可以帶入Lagrange的方程式
L=f+𝛌g=(1/2)‖w‖²-𝛌(y(w⋅x+b)-1)…(10)
y(w⋅x+b)-1=0
由於今天有成千上萬的點，如果有n點的話，公式(8)和(10)會變成～～
g(w,b)=𝛌1(y1(w⋅x1+b)-1)+𝛌2(y2(w⋅x2+b)-1)+….+𝛌n(yn(w⋅xn+b)-1)…(11)
y1(w⋅x1+b)-1=0,y2(w⋅x2+b)-1=0…yn(w⋅xn+b)-1=0
𝛌n:第n點的𝛌值
yn：第n點的y輸出:+1或-1
xn：第n點的向量
L=f+g=(1/2)‖w‖²+𝛌1(y1(w⋅x1+b)-1)+𝛌2(y2(w⋅x2+b)-1)+….+𝛌n(yn(w⋅xn+b)-1)…(12)
而Lagrange方程式求出小解的條件：
∂L/∂w=0….(13)
∂L/∂b=0…(14)
方程式(13)開展後為：
∂L/∂w=∂f/∂w+∂g/∂w=w+(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)=0
w=-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}…(15)
方程式(14)開展後：
∂L/∂b=∂f/∂b+∂g/∂b=0+(𝛌1)(y1)+(𝛌2)(y2)+…+(𝛌n)(yn)=0
(𝛌1)(y1)+(𝛌2)(y2)+…+(𝛌n)(yn)=0…(16)
利用方程式(15)，代回方程式(6)和(7):
對於空間任一點x，根據該點之y值為+1/-1有(17)或(18)兩個方程式
y=w⋅x+b=-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}⋅x+b≧1 …(17)
y=w⋅x+b=-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}⋅x+b≦-1 …(18)
以及把(15)(16)代回方程式(12):
L=f+g=(1/2)*-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}*-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)} + 𝛌1(y1(w⋅x1+b)-1)+𝛌2(y2(w⋅x2+b)-1)+….+𝛌n(yn(w⋅xn+b)-1)
=(1/2)*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}+{(𝛌1)(y1)(w⋅x1)+(𝛌2)(y2)(w⋅x2)+….+(𝛌n)(yn)(w⋅xn)}-(𝛌1+𝛌2+…+𝛌n)
=(1/2)*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}+{(𝛌1)(y1)(-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}⋅x1)+(𝛌2)(y2)(-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}⋅x2)+….+(𝛌n)(yn)(-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}⋅xn)}-(𝛌1+𝛌2+…+𝛌n)
=(-1/2)*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}*{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}-(𝛌1+𝛌2+…+𝛌n)…(19)
(𝛌1)(y1)+(𝛌2)(y2)+…+(𝛌n)(yn)=0
以及SVM的y值只在該點為支持向量的時候等號成立：
當y(w⋅x+b)-1=0的時候，該點為支持向量點，此時𝛌≦0…(限制1)
當y(w⋅x+b)-1>0的時候，該點非支持向量點，此時𝛌只能為0 …(限制2)
方程式(16)(17)(18)就是我們拿來解SVM的關鍵！
這邊，還是給個例子來幫助理解如何使用方程式
案例推導
今天也是在二維空間，我們有5個已經分類好的點
甲類別：標記為＋１
Ａ(5,10) B(8,20) C(-12,15)
乙類別：標記為-1
D(-3,4) E(10,-4)
寫到這邊，數學感覺敏銳的讀者應該發現，剛好=1或=-1的情況應該只出現在支持向量上，其餘的點要不>1或<-1，要不就掉在邊界帶寬內．那這邊的方程式全部都用=1 或=-1的條件帶入，那算出來的值可信任嗎/或者有辦法算出解嗎？
答案為否！
面對這種並非所有點都是支持向量的情況，其中一種解決手法是在甲類別選一個點出來，乙類別也選一個點出來，當作支持向量來運算．把所有組合的結果都運算完畢後，挑選最好的一組解作為支持向量，如果沒有滿意的，接著甲類別挑兩個，乙類別挑一個，以此類推，把可以是 Linear System的條件都拿來運算，從中挑選一個最好的． 這個解法就需要大量的二次規劃運算（就是方程式(16)~(18)重複運算）．
以下是甲類別挑一個，以類別挑一個來當支持向量的情況：
接著是甲類別挑2個，乙類別挑1個的情況，以AC-D為例子，也藉由這個例子示範二次規劃的運算過程：
點Ａ：
yA=w⋅xA+b=-{(𝛌A)(yA)(xA)+(𝛌C)(yC)(xC)+(𝛌D)(yD)(xD)}⋅xA+b=1
=-(𝛌A)xA⋅xA-(𝛌C)xC⋅xA+(𝛌D)xD⋅xA+b=1
註記：xi⋅xj為點i和點j的內積
=>-(𝛌A)(1)(5*5+10*10)-(𝛌C)(1)(5*-12+10*15)-(𝛌E)(-1)(5*10+10*-4)+b=1
=> -125𝛌A-90𝛌C+10𝛌E+b=1…(20)
點Ｃ:
yC=w⋅xC+b=-{(𝛌A)(yA)(xA)+(𝛌C)(yC)(xC)+(𝛌D)(yD)(xD)}⋅xC+b=1
=>-𝛌A(5*-12+10*15)-𝛌C(-12*-12+15*15)+𝛌E(-12*10+15*-4)+b=1
-90𝛌A-369𝛌C-180𝛌E+b=1…(21)
點E:
yE=w⋅xE+b=-{(𝛌A)(yA)(xA)+(𝛌C)(yC)(xC)+(𝛌D)(yD)(xD)}⋅xE+b=-1
=>-𝛌A(5*10+10*-4)-𝛌C(-12*10+15*-4)+𝛌E(10*10+-4*-4)+b=-1
=>-10𝛌A+180𝛌C+116𝛌E+b=-1…(22)
邊界條件，從方程式(16)而來：
(𝛌A)(yA)+(𝛌C)(yC)+(𝛌E)(yE)=0
=>𝛌A+𝛌C-𝛌E+0b=0…(23)
由(20)~(23)的4個方程式，求4個未知數𝛌A,𝛌C,𝛌E以及b，標準的四元一次方程式的解法．解出來為
[𝛌A 𝛌C 𝛌E b]=[-0.02067491 0.00683286 -0.01384205 -0.83098592]
根據方程式(15)
w=-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}
w=-{(𝛌1)(y1)(x1)+(𝛌2)(y2)(x2)+…+(𝛌n)(yn)(xn)}
w=(0.046948356807511721, 0.15962441314553993)
b=-0.830985915493
但是，根據限制1，𝛌≦0，但𝛌C=0.00683286 不符合我們的要求，因此踢掉．
那，不合條件的圖畫出來會是怎樣的呢？結果如下圖：
我們發現即使不符合限制條件，但還是可以畫出線來，而且結果看起來也不錯～
那我們同樣找一個是不符合𝛌≦0的狀況，ABC-D的狀況．
[𝛌A 𝛌B 𝛌C 𝛌D b]=[ -1.60011321e+14 8.57419157e+13 -3.74366111e+13 -1.11706017e+14 -1.80021841e+00]
這次𝛌B到10的13次方，結果畫出來：
結果把-1的支持向量D也吃掉了，此SVM結果無法採用～
我們找一個符合限制條件的狀況，AC-D
[𝛌A 𝛌C 𝛌D b]=[-0.02063083 -0.01051379 -0.03114461 -1.74647887]
這個條件下就能把+和-區隔開來．
把所有可能的組合計算過後，AC-D為符合所有限制條件的解．
這個就是SVM的運算過程．
上述的做法是理想狀況下的SVM運算，但是有的時候把所有的解都算過一輪，但是都找不到完美區隔兩方的邊界線和其帶寬，這個時候有兩種做法：
一種是容許帶寬(Margin)大小可變動，
另一種是容許邊界帶不完美地區隔兩方．
當然可以兩種一起使用．
不過呢～現行的是容許邊界帶不完美地區隔兩方．
而容許帶寬變化的SVM演算法，我目前見識淺薄，還沒有看到類似的手法．
Soft-Margin SVM
我原本以為Soft-Margin代表其帶寬可以變動，所以對數學方程式的思考方向一整個走歪，直到發現我方程式的未知數怎麼都湊不起來，才發現我好像會錯意了，原來Soft-Margin只是可以容許有點掉在帶寬內，或是錯誤分類，並沒有調整帶寬以及變動Hard-Margin SVM算出來的w的功能．
它的數學式就和上述的SVM（我們稱之為Hard-Margin SVM）有所不同，其數學原理可參考Augmented Lagrangian method[2]
邊界線的方程式：
w⋅x+b=0…(3)
A類別的判定範圍：
w⋅x+b≧1…(4)
Ｂ類別的判定範圍：
w⋅x+b≦-1…(5)
我們在邊界判斷條件上增加一個浮動參數：
w⋅x+b≧1-𝛏…(24)
w⋅x+b≦-1+𝛏…(25)
𝛏≧0
所以我們在求Lagrange method的目標函數會增加一個懲罰的權重C
Cost=C(𝛏1+𝛏2+…+𝛏n)…(26)
因此Lagrange method的目標函數：
f(w,𝛏)=(1/2)‖w‖²+Cost=(1/2)‖w‖²+C(𝛏1+𝛏2+…+𝛏n)…(27)
gi(w,b,𝛏)=yi(w⋅xi+b)-1+𝛏i≧0…(28)
∀i∈ℕ,1≦i≦n
Lagrange equation:
L=(1/2)‖w‖²+C(𝛏1+𝛏2+…+𝛏n)+∑ 𝛌i(yi(w⋅xi+b)-1+𝛏i)+∑𝝁i𝛏i…(29)
∂L/∂w=∂f/∂w+∂g/∂w=w+∑ 𝛌i yi xi=0…(30)
∂L/∂b=∑ 𝛌iyi=0…(31)
∂L/∂𝛏i=C+𝛌i+𝝁i=0…(32)
限制條件：
𝛏i≧0,
𝝁i≦0,
𝝁i𝛏i=0
由於Lagrange multiplier method 在(30)~(32)皆為0時有極值
我們把(32)代回(29)
C+𝛌i+𝝁i=0 =>C=- 𝛌i-𝝁i
𝝁i=0=>0≧𝛌i≧-C
L=(1/2)‖w‖²+(-∑ 𝛌i-∑𝝁i)(𝛏1+𝛏2+…+𝛏n)+∑ 𝛌i(yi(w⋅xi+b)-1+𝛏i)+∑𝝁i𝛏i
=(1/2)‖w‖² -∑ 𝛌i𝛏I-∑𝝁i𝛏i+∑ 𝛌iyi(w⋅xi+b)-∑ 𝛌i+∑ 𝛌i𝛏i+∑𝝁i𝛏i
L=(1/2)‖w‖²+∑ 𝛌i(yi(w⋅xi+b)-1)…(33)
限制條件
0≧𝛌i≧-C
𝛌i(yi(w⋅xi+b)-1)=0
又w+∑ 𝛌i yi xi=0 所以帶入(33)可得：
L=(1/2)∑ 𝛌i yi xi∑ 𝛌j yj xj+∑ 𝛌i(yi(-∑ 𝛌jyj xj⋅xi+b)-1)
=(-1/2)∑ 𝛌i yi xi 𝛌j yj xj-∑ 𝛌i…(34)
這個還是用實際的案例來推導比較好理解
Soft-Margin SVM範例推導
由前述的例子，再加一個乙類別F點(15,15)和G(5.1,10.1)
甲類別：標記為＋１
Ａ(5,10) B(8,20) C(-12,15)
乙類別：標記為-1
D(-3,4) E(10,-4) F(15,15) G(5.1,10.1)
這次選擇A-DE作為範例
(𝛌A,𝛌D,𝛌E)=[-0.02311049 -0.01755604 -0.00555445 ]
w=[0.11267605633802817, 0.18309859154929578]
b=-1.39436619718
在這個案例裡頭，點C被包含進帶寬內，Ｆ點被錯誤分類
點Ｃ之標記為+1，帶回(24)
w⋅xC+b≧1-𝛏C
0.11267605633802817*-12+0.18309859154929578*15–1.39436619718≧1-𝛏C
𝛏C≧1-(0.11267605633802817*-12+0.18309859154929578*15–1.39436619718)=0.9999999999969016
因此𝛏C≧0.9999999999969016
點Ｆ之標記為-1，帶回(25)
w⋅xF+b≦-1+𝛏F
0.11267605633802817*15+0.18309859154929578*15–1.39436619718≦-1+𝛏F
𝛏F≧1+0.11267605633802817*15+0.18309859154929578*15–1.39436619718=4.042253521129859
因此𝛏F≧4.042253521129859
由這個案例可知，偏離原本邊界越遠的點，所需要的𝛏值會越高．
那Ｃ(cost)這個參數到底怎麼運用呢？因為在案例推導中都沒用到～
根據限制條件：
𝛌i(yi(w⋅xi+b)-1)=0…(35)
𝝁i𝛏i=0…(36)
以及方程式(32)C+𝛌i+𝝁i=0
𝝁i=-(C+𝛌i)
帶入(36)
𝝁i𝛏i=-(C+𝛌i)𝛏i=0
在𝛏i不為0的情況下
C=-𝛌i
在幾何上觀察，C設越大，代表-𝛌i也越大，也代表可容許的帶寬越窄
我們用A(5,10) G(5.1,10.1)當例子，其𝛌為
(𝛌A,𝛌G)=(-100, -100)
而w=(-10.00000000001171, -10.00000000001171)
單邊帶寬=0.0707106781186
以ＢＥ來看
(𝛌B,𝛌E)=(-0.00344828 -0.00344828)
w=(-0.0068965517241379344, 0.082758620689655185)
單邊帶寬=12.0415945788
從以上觀察，可以得知當C值越大，可容許的帶寬越小，當C值越小，可容許的帶寬就越大．
當C值給定後，所產生的SVM候選組合會產生各自的∑𝛏i 值，乘上C值後，
Cost=C(∑𝛏i)
選擇Cost最小的當作所產出的SVM．
以上就是Soft-Margin SVM運作的邏輯．
SMO(Sequential Minimal Optimization)
不管是Hard-Margin 或是 Soft-Margin SVM，都需要大量的二次規劃運算，因此當樣本數多的時候，運作起來非常耗時．不過在1998年的時候，SMO[3]橫空出世，利用小量迭代的方法取代掉大量的二次規劃和大矩陣運算，是個使SVM能夠廣泛使用的天才演算法！
SMO的運作
SMO每次運作都會挑選2個點，產生2個Lagrange multipliers，在之前Soft-Margin SVM有提到的C值，就是一個關鍵，由於每一個-𝛌i(之後會以𝛼i取代，𝛼i=-𝛌i)的最大值為C值，最小值為0，加上方程式(37)
ui=𝛼iyi(w⋅xi)-b…(37)
我們任意挑一點
當
𝛼i=0, yiui≥1 SVM的支持向量的邊界
0≦𝛼i≦C, yiui=1 為SVM的支持向量的條件
𝛼i=C,yiui≦1 SVM的支持向量的邊界
如果當兩個點的類別不同時
y1!= y2, 𝛼1-𝛼2=k
上下界
L=max(0,𝛼2 −𝛼1), H=min(C,C+𝛼2 −𝛼1)
相同類別時
y1== y2, 𝛼1+𝛼2=k
上下界
L = max(0,𝛼2 +𝛼1 −C), H = min(C,𝛼2 +𝛼1).
之前提過的目標函數：
Ψ(𝛼)=(1/2)∑ 𝛌i yi xi 𝛌j yj xj+∑ 𝛌i=(1/2)∑ 𝛼i𝛼j yi yj (xi.xj)-∑ 𝛼i…(38)
展開後：
Ψ(𝛼)=(1/2)(𝛼1𝛼1 y1 y1 (x1.x1)+𝛼1𝛼2 y1 y2 (x1.x2)+𝛼2𝛼1 y2 y1 (x2.x1)+𝛼2𝛼2 y2 y2 (x2.x2))+𝛼1+𝛼2…(39)
使𝛼1𝛼2為對角線關係：𝛼1＋𝛼2=0,𝛼1=-𝛼2
變數變換：
𝛼1=t
𝛼2=-t
Ψ(t)=(1/2)(t² y1 y1 (x1.x1)-t² y1 y2 (x1.x2)-t² y2 y1 (x2.x1)+t² y2 y2 (x2.x2))+t+-t=(1/2)(t² y1 y1 (x1.x1)-2t² y1 y2 (x1.x2)+t² y2 y2 (x2.x2))…(40)
∂Ψ/∂t=t.y1. y1. (x1.x1)-2t y1 y2 (x1.x2)+t y2y2 (x2.x2)…(41)
∂²Ψ/∂t²=y1. y1. (x1.x1)-2 y1 y2 (x1.x2)+ y2y2 (x2.x2)…(42)
其二次微分之結果：
η = K ( x1 , x1 ) + K ( x2 , x2 ) − 2 K ( x1 , x2 )…(43)
K是kernel type ，在這裡是線性核，為yi. yj. (xi.xj)
迭代α2的方式如下：
α2new =α2 +y2(E1−E2)/η,…(44)
Ei=ui-yi
對新的α2修剪(clipped) …(45)
if (α2new≥H) α2newclipped= H;
if (L<α2new <H) α2newclipped= α2new;
if (α2new<L) α2newclipped= L;
利用修剪後的α2運算新的α1
α1new =α1+y1y2(α2 −α2newclipped)…(46)
計算b值
當每次α值更新後，b值也會重新計算
b1=E1 +y1(α1new −α1 )K(x1,x1)+y2(α2newclipped −α2 )K(x1,x2 )+b.…(47)
b2=E2 +y1(α1new −α1 )K(x1,x2)+y2(α2newclipped −α2 )K(x2,x2 )+b.…(48)
當b1等於b2時，就是運算搞定的時候，此時就能夠輸出一個向量w當作結果．
以上就是SMO的簡略敘述．
最後附上實作的code:
https://github.com/ZhengLungWu/SVM_C_Sharp/blob/master/SVM.cs
參考資料
[1]http://episte.math.ntu.edu.tw/entries/en_lagrange_mul/index.html
[2]https://en.wikipedia.org/wiki/Augmented_Lagrangian_method
[3]http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.4376&rep=rep1&type=pdf