如果需要完整代碼可以關注下方公眾號，后臺回復“代碼”即可獲取，阿光期待著您的光臨~

2021人工智能領域新星創作者，帶你從入門到精通，該博客每天更新，逐漸完善機器學習各個知識體系的文章，幫助大家更高效學習，

一、概述

本篇文章將講解機器學習中的一個非常強的演算法——支持向量機（SVM），一聽到它的名字就會感到這個演算法非常的厲害，確實是這樣，在神經網路還沒有發展起來的一段時間，它確實稱霸了很久，而且也具有較高的能力，

支持向量機最開始是一個簡單的二分類模型，后面不斷發展引入了核函式、非線性因子等將其精度變得更加精準，能夠適應更加復雜的資料，

它的演算法原理就是，假設我們的資料樣本分布在二維平面，有兩個分類，支持向量機的做法就是要找到一條直線可以將所有的樣本進行區分，這里假設線性可分，如果不可分需要引入核函式，之后的文章會進行講解，本篇側重講解線性可分的二分類資料，

我們可以看到上面的圖片，存在3條直線可以將我們的樣本進行區分，但是我們可以發現A線是最好的，為什么？因為A線的魯棒性最好，什么是魯棒性？你可以理解為模型的牛逼程度，如果魯棒性越強，模型越健壯，抗煩擾能力越強，如果此時有一個新的樣本點在靠近C線或者B線的邊緣，模型很有可能會將其進行誤分類，而A卻能很好的進行區分，因為A線對于所有的樣本點的距離都很遠，誤分類的幾率很低，這個分類邊界有個很響亮的名字叫做最大間隔分類超平面，

這個平面有兩條性質：

• 能夠將兩個類別的資料分到平面兩端
• 距離兩個類別樣本最近的樣本最遠

其中圖中最邊緣的兩條直線包含了距離分類平面最近的樣本，它們被稱作支持向量，而我們的目的是要使兩條直線之間的距離最大，

這里解釋一下，可能很多地方講的最大化距離不太一樣，有的是最大化上面兩條直線之間的距離，有的是最大化所有樣本到超平面的距離，還有的是最大化所有樣本到分類界面的距離當中最小的距離，

其實沒有關系，上面只是不同角度理解，不會影響結果的，從不同的角度引出待優化的目標，最終經過轉換都是會轉化成同一個優化函式的，

二、相關概念

1.超平面

所謂的超平面就是我們的決策邊界，能夠將我們資料進行區分的一個面，如果在二維是一條直線，三維是一個平面，在高維中可能是別的維度空間的一種形狀，所以叫做超平面，總是n-1個維度，

這里假設還是以二維平面進行講解，假設我們的超平面為 w T x + b = 0 w^Tx+b=0 wTx+b=0 ，其中 w w w 為平面的法向量，例如： w 1 x 1 + w 2 x 2 + b = 0 w_1x_1+w_2x_2+b=0 w1?x1?+w2?x2?+b=0 ，其中的 w 1 , w 2 w_1,w_2 w1?,w2? 就為該平面的法向量，b為平面的偏移量，至于為什么另外兩條直線為 w T x + b = 1 ( ? 1 ) w^Tx+b=1(-1) wTx+b=1(?1) ，我們下面會講，

因為是二分類問題，假設兩個分類為 ? 1 ， 1 {-1，1} ?1，1 ，如果樣本處于左上方就是+1類，與之對應-1類，這也就對應著：
w T x + b ≥ 1 , y = + 1 w^Tx+b\geq1,y=+1 wTx+b≥1,y=+1

w T x + b ≤ 1 , y = ? 1 w^Tx+b\leq1,y=-1 wTx+b≤1,y=?1

然而這兩個式子我們可以將其進行合并，成為 ： y ( w T x + b ) ≥ 1 y(w^Tx+b)\geq 1 y(wTx+b)≥1?

2.優化目標

我們引出優化函式的方式有三種，分別進行講解

2.1方法一

我們上面說到了為了要使兩條直線間的間隔最大，即我們的優化目標為： m a x 2 ∣ ∣ w ∣ ∣ max \frac{2}{||w||} max∣∣w∣∣2? ，這可以用空間直線與直線之間的距離公式得出，所以現在就是：
m a x w , b 2 ∣ ∣ w ∣ ∣ max_{w,b} \frac{2}{||w||} maxw,b?∣∣w∣∣2?

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m) s.t.yi?(wTxi?+b)≥1,(i=1,2,...m)

第一個式子是我們需要最大化的距離，第二個是需要滿足的條件約束，就是要滿足將所有樣本正確分類的情況下求得使距離最大的w，

因為一般情況下，我們都是算最小化，所以需要將max進行轉化，求它的最大值就是求分母的最小值，我們就是要分母最小，這時我們的優化函式就變成了：
m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2 minw,b?21?∣∣w∣∣2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m) s.t.yi?(wTxi?+b)≥1,(i=1,2,...m)

我們可以看到從原來的L2范數直接加了平方，其實這是等價的，兩個方程通解，加入1/2 的目的就是為了使之后的求導方便，直接消去2，

2.2 方法二

其實支持向量機是一種最大間隔分類器，意思就是要使我們所有樣本到超平面的距離的最小值最大化，什么意思？就是每個樣本到超平面都會有一個距離，肯定存在一個樣本到該平面的距離最小，如果我們使得這個最小距離最大化的化，那么其它樣本的距離也是會變大的，我們就是要最小的變大，從而使整體變大，那么我們就會引入一個式子：
m a r g i n ( w , b ) = m i n d i s t a n c e ( w , b , x i ) margin(w,b)=min\quad distance(w,b,x_i) margin(w,b)=mindistance(w,b,xi?)

m i n 1 ∣ ∣ w ∣ ∣ ∣ w T x i + b ∣ min\frac{1}{||w||}|w^Tx_i+b| min∣∣w∣∣1?∣wTxi?+b∣

這個公式很容易理解，就是每個樣本到超平面的距離，

那么我們的優化函式就變成了：
m a x m i n 1 ∣ ∣ w ∣ ∣ ∣ w T x i + b ∣ = m a x 1 ∣ ∣ w ∣ ∣ m i n ∣ w T x i + b ∣ max\quad min\frac{1}{||w||}|w^Tx_i+b|=max\frac{1}{||w||}min|w^Tx_i+b| maxmin∣∣w∣∣1?∣wTxi?+b∣=max∣∣w∣∣1?min∣wTxi?+b∣

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m) s.t.yi?(wTxi?+b)≥1,(i=1,2,...m)

那么根據第二個式子，我們可以得到 m i n y i ( w T x i + b ) = 1 min\ y_i(w^Tx_i+b)=1 min yi?(wTxi?+b)=1，由于第一個式子看起來較為復雜，嘗試化簡一下，首先要將絕對值去掉，怎么去呢？我們知道 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\geq1 yi?(wTxi?+b)≥1?，所以可以將 ∣ w T x i + b ∣ |w^Tx_i+b| ∣wTxi?+b∣ 乘上個 y i y_i yi? 將絕對值去掉，因為 y i y_i yi? 的絕對值為1，不會造成影響，所以結果為 m i n y i ( w T x i + b ) min\ y_i(w^Tx_i+b) min yi?(wTxi?+b)，我們剛剛從第二個式子得到個結論就是該值的最小值為1，帶入，那么第一個優化函式就變成了 m a x 1 ∣ ∣ w ∣ ∣ max\frac{1}{||w||} max∣∣w∣∣1? ，這就和上面的一樣，只不過上面的分子是2，這個是1，其實沒有關系，我們注重的是分母，仍根據上面所說想要整體最大，則分母最小，那么優化函式仍為：
m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2 minw,b?21?∣∣w∣∣2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m) s.t.yi?(wTxi?+b)≥1,(i=1,2,...m)

2.3 方法三

其實方法三和上面兩種差不多，這里就不細致講解了，感興趣可以看看李航的統計學習那本書，我就簡單說說，

它的原理就是我們同樣和方法二要最大化每個樣本到超平面的距離，但是服從的條件是我們所有的資料樣本到該超平面的資料都大于我們要求的最大距離，就是說它保持所有樣本到超平面的距離都大于我們要求的距離，這其實和方法二等價，即最大化最小的距離，方法三也是這樣，每個樣本距離都大于它，那么就說明我們優化的是所有樣本中距離最小的，這里有個不一樣的地方，就是引入了函式距離和幾何距離，這里就不細講了，

三、演算法流程

整個演算法流程為：

• 獲取優化目標函式
• 將目標函式與約束條件結合進行拉格朗日乘子法
• 強對偶性，轉化求解問題
• 二次規劃求解 λ \lambda λ
• 獲取最優解 w ? , b ? w^*,b^* w?,b?

1.獲取優化函式

我們需要優化的函式就是上面推匯出的，如果單是對第一個式子進行優化很容易求導，梯度下降，但是對于本問題來說，求解第一個式子的時候，會有m個約束條件，顯然不能夠直接進行計算，所以需要下面的幾步進行轉化成我們可以求解的目標函式，第一步就是要能不能將整個帶有約束條件的函式轉化為無約束的呢？肯定是能，這就引出了拉格朗日乘子法，

m i n w , b 1 2 ∣ ∣ w ∣ ∣ 2 min_{w,b}\frac{1}{2}||w||^2 minw,b?21?∣∣w∣∣2

s . t . y i ( w T x i + b ) ≥ 1 , ( i = 1 , 2 , . . . m ) s.t. y_i(w^Tx_i+b)\geq1,(i=1,2,...m) s.t.yi?(wTxi?+b)≥1,(i=1,2,...m)

2.拉格朗日乘子法

我們高數中學過拉格朗日乘法，就是有一個函式 f ( x ) f(x) f(x)，要求其極值我們可以直接進行求導，如果存在一定條件就要使用拉格朗日乘法，引入乘子變成 L = f ( x ) + λ g ( x ) L=f(x)+\lambda g(x) L=f(x)+λg(x)，其中的 g ( x ) g(x) g(x) 就為約束條件，但是這只是針對等式約束條件，而上面我們遇到的是不等式約束條件，那么怎么弄呢？

這就引出了松弛變數這個概念， 松弛變數的引入常常是為了便于在更大的可行域內求解，我們可以嘗試引入松弛變數將上面的不等式變成等式，具體怎么做？看！另：
m i n f ( w ) = m i n 1 2 ∣ ∣ w ∣ ∣ 2 minf(w)=min\frac{1}{2}||w||^2 minf(w)=min21?∣∣w∣∣2

g i ( w ) = 1 ? y i ( w T x i + b ) ≤ 0 g_i(w)=1-y_i(w^Tx_i+b)\leq0 gi?(w)=1?yi?(wTxi?+b)≤0

引入松弛變數后就變成了：
h i ( w , a i ) = g i ( w ) + a i 2 = 0 h_i(w,a_i)=g_i(w)+a_i^2=0 hi?(w,ai?)=gi?(w)+ai2?=0
因為 g ( x ) g(x) g(x) 為小于等于0的，所以加上一個大于0的數，肯定是能夠等于0的，這里 a i 2 a_i^2 ai2? 的作用就可以理解為一種動態調節因子，能夠調節自身使上面的等式成立，那么這樣就將原來的不等式轉化成了等式，就可以使用拉格朗日乘子法了：
L ( w , b , λ , a ) = f ( w ) + ∑ i = 1 m λ i h i ( w ) = f ( w ) + ∑ i = 1 m λ i [ g i ( w ) + a i 2 ] L(w,b,\lambda,a)=f(w)+\sum_{i=1}^m\lambda_ih_i(w)=f(w)+\sum_{i=1}^m\lambda_i[g_i(w)+a_i^2] L(w,b,λ,a)=f(w)+i=1∑m?λi?hi?(w)=f(w)+i=1∑m?λi?[gi?(w)+ai2?]
我們的目標就是要對該式求極值：
{ ? L ? w i = ? f ? w i + ∑ i = 1 m λ i ? g i ? w i ? L ? a i = 2 λ i a i = 0 ? L ? λ i = g i ( w ) + a i 2 = 0 λ i ≥ 0 \begin{cases} \frac{\partial L}{\partial w_i}=\frac{\partial f}{\partial w_i}+\sum_{i=1}^m\lambda_i\frac{\partial g_i}{\partial w_i}\\ \frac{\partial L}{\partial a_i}=2\lambda_ia_i=0\\ \frac{\partial L}{\partial \lambda_i}=g_i(w)+a_i^2=0\\ \lambda_i\geq0 \end{cases} ???????????wi??L?=?wi??f?+∑i=1m?λi??wi??gi???ai??L?=2λi?ai?=0?λi??L?=gi?(w)+ai2?=0λi?≥0?
這里解釋一下為什么 λ \lambda λ 要大于0：

根據第二個式子我們可以知道 λ \lambda λ 和 a i a_i ai? 之間至少有一個為0，但不能同時為0，如果同時為0，那么我們上面的約束條件將對所有的樣本不起作用，所以針對每個樣本，二者其中有一個為0，所以產生兩種情況：

1. λ i = 0 , a i ≠ 0 \lambda_i=0,a_i\neq0 λi?=0,ai??=0

如果 λ i \lambda_i λi? 為0的話，那么與之對應的樣本將不會起到約束條件，同時根據第三個式子，因為 g ( w ) + a i 2 = 0 g(w)+a_i^2=0 g(w)+ai2?=0 ,又 a i ≠ 0 a_i\neq0 ai??=0 ，所以此時我們的 g ( w ) < 0 g(w)<0 g(w)<0? ，那就對應 y i ( w T x i + b ) ≠ 1 y_i(w^Tx_i+b)\neq1 yi?(wTxi?+b)?=1 ，也就是此時對應的樣本在兩條直線的外側，

2. λ i ≠ 0 , a i = 0 \lambda_i\neq0,a_i=0 λi??=0,ai?=0

因為 a i a_i ai? 為0，根據第三個式子，則說明此時 g ( w ) = 0 g(w)=0 g(w)=0 那么說明此時 y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1 yi?(wTxi?+b)=1 ，則此時樣本落在兩條直線上，同時 λ i ≠ 0 \lambda_i\neq0 λi??=0，那么此時與之對應的樣本就會起到約束作用，

所以綜上所述，真正起到作用的是 λ i ≠ 0 \lambda_i\neq0 λi??=0 對應的樣本，也就是落在兩條直線上的樣本，它們叫做支持向量，所以整個演算法的核心就是圍繞支持向量，支持向量外的樣本資料的分布是對模型沒有影響的，

將這兩點結合起來，就引出了KKT條件：
{ ? L ? w i = ? f ? w i + ∑ i = 1 m λ i ? g i ? w i λ i g i ( w ) = 0 g i ( w ) ≤ 0 λ i ≥ 0 \begin{cases} \frac{\partial L}{\partial w_i}=\frac{\partial f}{\partial w_i}+\sum_{i=1}^m\lambda_i\frac{\partial g_i}{\partial w_i}\\ \lambda_ig_i(w)=0\\ g_i(w)\leq0\\ \lambda_i\geq0 \end{cases} ???????????wi??L?=?wi??f?+∑i=1m?λi??wi??gi??λi?gi?(w)=0gi?(w)≤0λi?≥0?
其中更新的第二個式子和第三個式子就是根據上面得出的結論得到的，

也就是說對于支持向量滿足 g ( w ) = 0 g(w)=0 g(w)=0 ，即落在兩條直線上，而且對應 λ i \lambda_i λi? 不為0，對于其它的向量滿足 g ( w ) < 0 g(w)<0 g(w)<0 ,即對應除了支持向量之外的所有向量，此時 λ i = 0 \lambda_i=0 λi?=0 ,也就是沒有任何作用，

所以我們之前求 m i n 1 2 w T w min\ \frac{1}{2}w^Tw min 21?wTw 就變為了 m i n L ( w , b , λ , a ) min\ L(w,b,\lambda,a) min L(w,b,λ,a) ，但是此時又引入了a這個變數，嘗試把它去掉，首先將拉格朗日函式進行展開：
L ( w , b , λ , a ) = f ( w ) + ∑ i = 1 m λ i [ g i ( w ) + a i 2 ] = f ( w ) + ∑ i = 1 m λ i g i ( w ) + ∑ i = 1 m λ i a i 2 L(w,b,\lambda,a)=f(w)+\sum_{i=1}^m\lambda_i[g_i(w)+a_i^2]=f(w)+\sum_{i=1}^m\lambda_ig_i(w)+\sum_{i=1}^m\lambda_ia_i^2 L(w,b,λ,a)=f(w)+i=1∑m?λi?[gi?(w)+ai2?]=f(w)+i=1∑m?λi?gi?(w)+i=1∑m?λi?ai2?
因為之前求得 ? L ? a i = 2 λ i a i = 0 \frac{\partial L}{\partial a_i}=2\lambda_ia_i=0 ?ai??L?=2λi?ai?=0，所以二者得乘積為0，最后一項就消掉了，之后就變成了：
L ( w , b , λ ) = f ( w ) + ∑ i = 1 m λ i g i ( w ) L(w,b,\lambda)=f(w)+\sum_{i=1}^m\lambda_ig_i(w) L(w,b,λ)=f(w)+i=1∑m?λi?gi?(w)
所以此時待優化得就是 m i n L ( w , b , λ ) min L(w,b,\lambda) minL(w,b,λ) ，將其進一步轉化

假設此時我們的 g ( w ) < = 0 g(w)<=0 g(w)<=0 那么說明， m a x L ( w , b , λ ) maxL(w,b,\lambda) maxL(w,b,λ) 就變成了 f ( w ) + 0 f(w)+0 f(w)+0 ，為什么是0，因為 λ \lambda λ 大于0，而 g i ( w ) g_i(w) gi?(w) 小于0，只有為0時才能取得最大值，

如果 g ( w ) > 0 g(w)>0 g(w)>0 ,此時的 m a x L ( w , b , λ ) maxL(w,b,\lambda) maxL(w,b,λ) 就變成了 f ( w ) + ∞ f(w)+\infty f(w)+∞，因為 λ \lambda λ 是大于0的，而 g ( w ) g(w) g(w) 也是大于0的，那么最大值就會取到正無窮，

那么此時我們的優化函式又變為了：
m i n m a x L ( w , b , λ ) min\ maxL(w,b,\lambda) min maxL(w,b,λ)
又因為L的最大值肯定是 f ( w ) f(w) f(w) 那么就變成了， m i n f ( x ) = m i n 1 2 w T w min f(x)=min\frac{1}{2}w^Tw minf(x)=min21?wTw，而且此時是在 g ( w ) < = 0 g(w)<=0 g(w)<=0 的條件下，因為在該條件下L的最大值才為 f ( x ) f(x) f(x) ，這也就對應最開始我們的函式，滿足 y i ( w T x i + b ) > = 1 y_i(w^Tx_i+b)>=1 yi?(wTxi?+b)>=1 的條件下進行優化 m i n 1 2 w T w min\frac{1}{2}w^Tw min21?wTw ，

此時優化函式就是：
m i n m a x L ( w , b , λ ) min\ maxL(w,b,\lambda) min maxL(w,b,λ)

λ i > = 0 \lambda_i>=0 λi?>=0

3.強對偶性

我們上面得到了優化函式，但是求解起來不太方便，所以我們需要用到強對偶的方法，將其換個方式進行求解，針對于強對偶的兩個方程是同解的，

這里解釋下什么是弱對偶和強對偶，

如果針對一個函式 f ( x ) f(x) f(x) 我們存在：
m i n m a x f ( x ) > = m a x m i n f ( x ) min\ maxf(x)>=max minf(x) min maxf(x)>=maxminf(x)
那么則說明兩者為弱對偶關系，怎么理解上面的不等式呢？

從大的里面挑出最小的要大于從小的里面挑出最大的，或者你可以理解為清華里的菜雞要強于專科里的學霸，這個例子很好理解吧，

那么強對偶就是滿足等號成立，即 m i n m a x f ( x ) = m a x m i n f ( x ) min\ maxf(x)=max minf(x) min maxf(x)=maxminf(x)

我們引出這個就是為個將上文獲得的優化函式進行對偶轉化，所以：
m i n m a x L ( w , b , λ ) min\ maxL(w,b,\lambda) min maxL(w,b,λ)
就變成了：
m a x m i n L ( w , b , λ ) max\ minL(w,b,\lambda) max minL(w,b,λ)
我們就可以優化新的方程式了，對偶的目的是將原來難以求解的問題轉化為一個容易求解的問題，同時我們之前說的KKT條件就是強對偶性的充要條件，

這里因為我們的L是凸函式，所以可以直接確定能夠進行強對偶，

4.二次規劃求解 λ \lambda λ

m a x m i n L ( w , b , λ ) max\ minL(w,b,\lambda) max minL(w,b,λ)

根據上文，我們最終優化函式是這個，首先將min和max分離，先計算內層min函式，因為是凸函式，所以可以直接進行求導，由于此時 λ \lambda λ 為常數，所以只需對 w 、 b w、b w、b 進行求導：
? L ? w = w ? ∑ i = 1 m λ i x i y i = 0 \frac{\partial L}{\partial w}=w-\sum_{i=1}^m\lambda_ix_iy_i=0 ?w?L?=w?i=1∑m?λi?xi?yi?=0

? L ? b = ∑ i = 1 m λ i y i = 0 \frac{\partial L}{\partial b}=\sum_{i=1}^m\lambda_iy_i=0 ?b?L?=i=1∑m?λi?yi?=0
我們可以獲得 ： w = ∑ i = 1 m λ i x i y i w=\sum_{i=1}^m\lambda_ix_iy_i w=∑i=1m?λi?xi?yi??

我們將這兩個式子帶入到原式當中進行化簡，由于是凸函式，所以導數為0的點就是其最小值，我們把w、b的值帶入后就可以得到 m i n L ( w , b , λ ) minL(w,b,\lambda) minL(w,b,λ) ，

此時的 m i n L ( w , b , λ ) = ∑ j = 1 m λ i ? 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) minL(w,b,\lambda)=\sum_{j=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j) minL(w,b,λ)=∑j=1m?λi??21?∑i=1m?∑j=1m?λi?λj?yi?yj?(xiT?xj?)?

我們的優化函式就變成了：
m a x m i n L ( w , b , λ ) = m a x ∑ j = 1 m λ i ? 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) maxminL(w,b,\lambda)=max\sum_{j=1}^m\lambda_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j) maxminL(w,b,λ)=maxj=1∑m?λi??21?i=1∑m?j=1∑m?λi?λj?yi?yj?(xiT?xj?)
一般我們習慣優化最小值將上式加個符號就變成了：
m a x ? ∑ j = 1 m λ i + 1 2 ∑ i = 1 m ∑ j = 1 m λ i λ j y i y j ( x i T x j ) max-\sum_{j=1}^m\lambda_i+\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\lambda_i\lambda_jy_iy_j(x_i^Tx_j) max?j=1∑m?λi?+21?i=1∑m?j=1∑m?λi?λj?yi?yj?(xiT?xj?)

∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0 i=1∑m?λi?yi?=0

注意上面的這個條件不能丟，因為該優化函式滿足的前提是對b的偏導為0得來的，為什么沒有考慮對w的偏導，因為現在的優化函式與w引數沒關系，所以不需要，而b的偏導為0的條件是 ∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0 ∑i=1m?λi?yi?=0 是對優化函式有影響的，需要保留，

接下來的問題就是如何求取滿足最大值的 λ \lambda λ ，

這里采用一種演算法叫做SMO演算法，其核心思想非常簡單：每次只優化一個引數，其他引數先固定住，僅求當前這個優化引數的極值，

由于優化函式同時存在兩個優化變數，所以需要根據約束條件消去一個，

由于有 ∑ i = 1 m λ i y i = 0 \sum_{i=1}^m\lambda_iy_i=0 ∑i=1m?λi?yi?=0 ，所以存在：
λ i y i + λ j y j = c \lambda_iy_i+\lambda_jy_j=c λi?yi?+λj?yj?=c
其中 c = ? ∑ k ≠ i , j λ k y k c=-\sum_{k\neq i,j}\lambda_ky_k c=?∑k?=i,j?λk?yk? ，由此可以得出 λ j = c ? λ i y i y j \lambda_j=\frac{c-\lambda_iy_i}{y_j} λj?=yj?c?λi?yi?? ，也就是我們可以利用 λ i \lambda_i λi? 的運算式代替 λ j \lambda_j λj? ，這就相當于把目標問題轉化成了僅有一個約束條件的最優化問題，僅有的約束就剩下了 λ i > = 0 \lambda_i>=0 λi?>=0 ，

對于單變數優化問題我們就可以使用梯度下降或者其它迭代演算法進行求解，

5.求解最優解 w ? , b ? w^*,b^* w?,b?

說了這么這么多，到底怎么獲得最終模型的引數和偏置呢？

我們之前對拉格朗日進行求導，獲得：
w = ∑ i = 1 m λ i y i x i w=\sum_{i=1}^m\lambda_iy_ix_i w=i=1∑m?λi?yi?xi?
由于我們在第四步，已經通過SMO演算法求出了每個樣本對應的 λ i \lambda_i λi? ，所以可以直接帶入上式，求出 w ? w^* w? ，

那么如果求取 b ? b^* b? 呢？

我們之前講到我們的支持向量是滿足 y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1 yi?(wTxi?+b)=1 的，也就是支持向量一定在該條直線上，所以說我們可以隨便找個支持向量，然后帶入就可以得到：
y k ( w T x k + b ) = 1 y_k(w^Tx_k+b)=1 yk?(wTxk?+b)=1
其中（x_k，y_k）對應著支持向量的資訊，

此時上式兩邊同時左乘 y k y_k yk? ，得到：
y k 2 ( w T x k + b ) = y k y_k^2(w^Tx_k+b)=y_k yk2?(wTxk?+b)=yk?
因為 y k y_k yk? 只能為1或者-1，所以 y k 2 y_k^2 yk2? 的值為1，所以此時滿足 w T x k + b = y k w^Tx_k+b=y_k wTxk?+b=yk? ，得到：
b ? = y k ? w T x k b^*=y_k-w^Tx_k b?=yk??wTxk?
又因為為了使我們的模型更加的穩定，魯棒性更強，所以我們可以求得所有支持向量的均值：
b = 1 ∣ S ∣ ∑ s ∈ S ( y k ? w T x k ) b=\frac{1}{|S|}\sum_{s\in S}(y_k-w^Tx_k) b=∣S∣1?s∈S∑?(yk??wTxk?)
其中 ∣ S ∣ |S| ∣S∣ 代表支持向量的個數，

這樣我們就求出了模型最優解系數 w ? w^* w?和偏置 b ? b^* b? ，得到模型：
w ? T x + b ? = 0 {w^*}^Tx+b^*=0 w?Tx+b?=0
決策函式為：
f ( x ) = s i g n ( w ? T x + b ? ) f(x)=sign({w^*}^Tx+b^*) f(x)=sign(w?Tx+b?)
其中的 s i g n ( . ) sign(.) sign(.) 為越階函式：
s i g n ( x ) = { ? 1 x < 0 0 x = 0 1 x > 0 sign(x)=\begin{cases} -1&x<0\\ 0&x=0\\ 1&x>0\\ \end{cases} sign(x)=???????101?x<0x=0x>0?
這樣我們的支持向量機線性可分分類器就構建成功了，但是這只是針對線性可分的資料有用，如果我們的資料線性不可分，找不到一個超平面進行分割，那么那么我們的模型就會沒用，進而引出了核函式和軟間隔的概念，如何處理線性不可分資料，下篇文章再講，

寫在最后

大家好，我是阿光，覺得文章還不錯的話，記得“一鍵三連”哦！！！