機器學習——SVM（支援向量機）

先從一個故事說起

國王為武林高手出了一道題，将紅豆綠豆擺在桌子上，讓他将其分開，于是武林高手輕松的在桌子上畫了一條線，将紅豆綠豆分開，如下圖

于是，國王又将這兩種豆子混子一起散落在桌子上，如圖

又讓武林高手将其分開，心想，這次我看你怎麼分，沒想到，武林高手站在桌子面前，運足内力，用手掌拍在桌子上，豆子瞬間騰空而起，高手用一張紙将豆子分成兩部分，上面的是綠豆，下面的是紅豆

上面的故事其實就是支援向量機的直覺了解，這些豆子叫做data，把線叫做classifier, 最大間隙trick叫做optimization，拍桌子叫做kernelling, 那張紙叫做hyperplane

支援向量機( support vector machines， SVM)是一種二類分類模型。SVM最基本的原理就是尋找一個分隔“平面”将樣本空間一分為二，對于二維平面，分割的其實是一條線，三維平面就需要一個平面來分開，對于 n 維資料，要想将其分開，就需要一個 n-1 維的超平面

支援向量機學習方法包含建構由簡至繁的模型：線性可分支援向量機( linear support vectormachine in linearly separable case)、線性支援向量機( linear support vector machine)及非線性支援向量機(non- linear support vector machine)。 簡單模型是複雜模型的基礎，也是複雜模型的特殊情況。當訓練資料線性可分時， 通過硬間隔最大化( hard margin maximization)，學習一個線性的分類器，即線性可分支援向量機，又稱為硬間隔支援向量機；當訓練資料近似線性可分時，通過軟間隔最大化( soft margin aximization)，也學習一個線性的分類器，即線性支援向量機，又稱為軟間隔支援向量機；當訓練資料線性不可分時，通過使用核技巧( kernel trick)及軟間隔最大化，學習非線性支援向量機

硬間隔最大化模型

下面就從線性可分支援向量機硬間隔最大化說起，以二維為例，如圖

要把資料分開可以有很多種分法，我們要取得就是最好的分法，如上圖，黑色線代表分割直線（平面），藍色區域代表間隔，顯然，間隔越大，代表這個線（面）的區分能力越大。我們的目的就是找到這個線（面），由上圖我們可以看到，絕大多數樣本對這個間隔的大小不起作用，隻有在藍色區域邊上的樣本才能決定間隔的大小，SVM中這些落在邊緣的樣本稱為支援向量，這也就是SVM名字的由來

這個分割平面用公式表示

w T x + b = 0 w^Tx+b=0 wTx+b=0

分類決策函數為

f ( x ) = s i g n ( w T x + b ) f(x)=sign(w^Tx+b) f(x)=sign(wTx+b)

其中 x x x 表示一個 n 維的樣本向量， w w w 是平面的 n 維法向量。雖然從公式上來看和線性回歸很像，但是它們之間的本質差別，線性回歸是用來拟合label的，而SVM的平面方程是用來确定平面方向的。在這個平面一側為一類資料，另一側則為另一類

我們的目标是讓這個間隔最大，樣本到這個分割平面的距離為

d = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ d=\frac{|w^Tx+b|}{||w||} d=∣∣w∣∣∣wTx+b∣​

這個公式其實就是高中學過點到直線距離得演變

d = ∣ A x + B y + C ∣ A 2 + B 2 d=\frac{|Ax+By+C|}{\sqrt{A^2+B^2}} d=A2+B2

​∣Ax+By+C∣​

||w|| 是L2範數

模型假設

首先這個平面要将資料正确分類，在平面上方的資料類别為 y = 1 y=1 y=1，在平面下方的資料類别為 y = − 1 y=-1 y=−1

對于上方資料，到平面距離 w T x + b > 0 w^Tx+b>0 wTx+b>0, 平面下方資料 w T x + b < 0 w^Tx+b<0 wTx+b<0，這樣我們可以用

y i ( w T x i + b ) > 0 y_i(w^Tx_i+b)>0 yi​(wTxi​+b)>0

表示樣本被正确分類

這樣問題就轉化為

{ m a x 2 ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ s . t . y i ( w T x i + b ) > 0 , i = 1 , 2 , 3 … ， n \begin{cases} max&2\frac{|w^Tx+b|}{||w||} \\ s.t.&y_i(w^Tx_i+b)>0, i=1,2,3…，n \end{cases} {maxs.t.​2∣∣w∣∣∣wTx+b∣​yi​(wTxi​+b)>0,i=1,2,3…，n​

在間隔邊緣上的點到分割平面的距離是間隔距離得一半，我們令這個點的函數值為 γ \gamma γ，則

y i ( w T x i + b ) = γ y i ( w T γ x i + b γ ) = 1 y_i(w^Tx_i+b)=\gamma \\ y_i(\frac{w^T}{\gamma}x_i+\frac{b}{\gamma})=1 yi​(wTxi​+b)=γyi​(γwT​xi​+γb​)=1

這裡令新的 w ^ = w T γ \hat{w}=\frac{w^T}{\gamma} w^=γwT​，新的 b ^ = b γ \hat{b}=\frac{b}{\gamma} b^=γb​，可以将這個距離看做是機關 1，這樣就得到 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)≥1 yi​(wTxi​+b)≥1 對于支援向量來說 y i ( w T x i + b ) = 1 y_i(w^Tx_i+b)=1 yi​(wTxi​+b)=1，那麼間隔可以表示為

γ = 2 ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ = 2 ∣ ∣ w ∣ ∣ \gamma=2\frac{|w^Tx+b|}{||w||}=\frac{2}{||w||} γ=2∣∣w∣∣∣wTx+b∣​=∣∣w∣∣2​

為了友善計算，我們要求 2 ∣ ∣ w ∣ ∣ \frac{2}{||w||} ∣∣w∣∣2​的最大值，轉換為 ∣ ∣ w ∣ ∣ 2 ||w||^2 ∣∣w∣∣2 的最小值，問題進一步轉化為

{ m i n w , b ∣ ∣ w ∣ ∣ 2 2 s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , 2 , 3 … ， n \begin{cases} \underset{w,b}{min}&\frac{||w||^2}{2} \\ s.t.&y_i(w^Tx_i+b)\geq1, i=1,2,3…，n \end{cases} ⎩⎨⎧​w,bmin​s.t.​2∣∣w∣∣2​yi​(wTxi​+b)≥1,i=1,2,3…，n​

目标函數本身是一個凸二次規劃問題，能直接用現成的優化計算包求解，這種解法有一個很大的缺點在于沒辦法套用核函數，我們可以有更高效的做法——求解對偶問題

首先要構造朗格朗日函數

我們先看一下拉格朗日乘子法的使用過程，給定一個不等式限制問題：

{ m i n x f ( x ) s . t . g i ( x ) ≤ 0 , i = 1 , 2 , 3 … ， k h i ( x ) = 0 , i = 1 , 2 , 3 … ， m \begin{cases} \underset{x}{min}f(x) \\ \begin{aligned}s.t.g_i(x)≤0, i=1,2,3…，k \\ h_i(x)=0, i=1,2,3…，m\end{aligned}\end{cases} ⎩⎪⎪⎨⎪⎪⎧​xmin​f(x)s.t.gi​(x)≤0,i=1,2,3…，khi​(x)=0,i=1,2,3…，m​​

我們引入一個廣義朗格朗日函數，将它改寫成這樣：

L ( x , α , β ) = f ( x ) + ∑ i = 1 k α i g i ( x ) + ∑ i = 1 m β i h i ( x ) , α i ≥ 0 L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k}\alpha_ig_i(x)+\sum_{i=1}^{m}\beta_ih_i(x),\alpha_i≥0 L(x,α,β)=f(x)+i=1∑k​αi​gi​(x)+i=1∑m​βi​hi​(x),αi​≥0

我們會發現 L ≤ f ( x ) L\leq f(x) L≤f(x)是以我們要求的是 m a x L ( x , α , β ) max L(x,\alpha,\beta) maxL(x,α,β)

最終的目标是

m i n b , w ( m a x α i ≥ 0 L ( b , w , α ) ) \underset{b,w}{min} \big(\underset{\alpha_i\geq0}{max}L(b,w,\alpha)\big) b,wmin​(αi​≥0max​L(b,w,α))

構造的拉格朗日函數為

L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b)) L(w,b,α)=21​∣∣w∣∣2+i=1∑m​αi​(1−yi​(wTxi​+b))

對偶問題

m i n b , w ( m a x α i ≥ 0 L ( b , w , α ) ) \underset{b,w}{min}\big(\underset{\alpha_i\geq0}{max}L(b,w,\alpha)\big) b,wmin​(αi​≥0max​L(b,w,α)) 轉化為 m a x α i ≥ 0 ( m i n b , w L ( b , w , α ) ) \underset{\alpha_i\geq0}{max}\big(\underset{b,w}{min}L(b,w,\alpha)\big) αi​≥0max​(b,wmin​L(b,w,α))

KKT條件

α i ≥ 0 y i ( w T + b ) − 1 ≥ 0 α i ( 1 − y i ( w T + b ) ) = 0 \begin{aligned} \alpha_i&\geq0 \\ y_i(w^T+b)-1&\geq0\\ \alpha_i(1-y_i(w^T+b))&=0 \end{aligned} αi​yi​(wT+b)−1αi​(1−yi​(wT+b))​≥0≥0=0​

分别對 w , b w,b w,b求導

∂ L ∂ b = − ∑ i = 1 m α i y i = 0 ∂ L ∂ w = w − ∑ i = 1 m α i y i x i → w = ∑ i = 1 m α i y i x i \begin{aligned} &\frac{\partial L}{\partial b}=-\sum_{i=1}^{m}\alpha_iy_i=0 \\ &\frac{\partial L}{\partial w}=w-\sum_{i=1}^{m}\alpha_iy_ix_i → w=\sum_{i=1}^{m}\alpha_iy_ix_i \end{aligned} ​∂b∂L​=−i=1∑m​αi​yi​=0∂w∂L​=w−i=1∑m​αi​yi​xi​→w=i=1∑m​αi​yi​xi​​

代入到上面函數

L ( w , b , α ) = 1 2 w T w + ∑ i = 1 m α i − ∑ i = 1 m α i y i w T x i − ∑ i = 1 m α i y i b = − 1 2 ( ∑ i = 1 m α i y i x i ) T ∑ i = 1 m α i y i x i + ∑ i = 1 m α i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j \begin{aligned} L(w,b,\alpha)&=\frac{1}{2}w^Tw+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\alpha_iy_iw^Tx_i-\sum_{i=1}^{m}\alpha_iy_ib \\ &=-\frac{1}{2}(\sum_{i=1}^{m}\alpha_iy_ix_i )^T\sum_{i=1}^{m}\alpha_iy_ix_i +\sum_{i=1}^{m}\alpha_i \\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned} L(w,b,α)​=21​wTw+i=1∑m​αi​−i=1∑m​αi​yi​wTxi​−i=1∑m​αi​yi​b=−21​(i=1∑m​αi​yi​xi​)Ti=1∑m​αi​yi​xi​+i=1∑m​αi​=i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​​

我們要求的是上式的最大值，最終我們的目标是

m i n α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j − ∑ i = 1 m α i \underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i αmin​21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​

s . t .   ∑ i = 1 m α i y i = 0 α i ≥ 0 , i = 1 , 2 , 3 , … , m \begin{aligned} s.t. \ &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &\alpha_i\geq 0, i=1,2,3,…,m \end{aligned} s.t. ​i=1∑m​αi​yi​=0αi​≥0,i=1,2,3,…,m​

唯一的變量 α \alpha α，求出 α \alpha α 就可以推導出對應的 w w w 和 b b b 了

w = ∑ i = 1 m α i y i x i b = y i − w ∗ x i w=\sum_{i=1}^{m}\alpha_iy_ix_i \\ b=y_i-w*x_i w=i=1∑m​αi​yi​xi​b=yi​−w∗xi​

軟間隔最大化模型

在實際場景中，資料不可能都是線性可分的，我們要允許一些樣本出錯，這樣我們就要引入一個松弛變量 ξ \xi ξ，适當放松 y i ( w t x i + b ) ≥ 1 y_i(w^tx_i+b)\geq1 yi​(wtxi​+b)≥1 這個條件，變為 y i ( w t x i + b ) ≥ 1 − ξ y_i(w^tx_i+b)\geq1-\xi yi​(wtxi​+b)≥1−ξ

我們把松弛變量加入到目标函數中

m i n b , w , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i s . t . y i ( w T x i + b ) ≥ 1 − ξ , i = 1 , 2 , 3 … ， n ξ i ≥ 0 , i = 1 , 2 , 3 … n ， \begin{aligned} \underset{b,w,\xi}{min}&\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i\\&s.t. \quad y_i(w^Tx_i+b)\geq1-\xi, i=1,2,3…，n \end{aligned}\\ \xi_i\geq0,i=1,2,3…n， b,w,ξmin​​21​∣∣w∣∣2+Ci=1∑m​ξi​s.t.yi​(wTxi​+b)≥1−ξ,i=1,2,3…，n​ξi​≥0,i=1,2,3…n，

C為一個常數，可以了解為懲罰參數。我們希望 ∣ ∣ w ∣ ∣ 2 ||w||^2 ∣∣w∣∣2盡可能小，也希望 ∑ ξ i \sum\xi_i ∑ξi​盡量小，C就是用來協調兩者的。C越大代表我們對模型的分類要求越嚴格

拉格朗日函數

L ( w , b , ξ , α , β ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m α i ( 1 − ξ i − y i ( w T x i + b ) ) + ∑ i = 1 m β i ( − ξ i ) L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))+\sum_{i=1}^{m}\beta_i(-\xi_i) L(w,b,ξ,α,β)=21​∣∣w∣∣2+Ci=1∑m​ξi​+i=1∑m​αi​(1−ξi​−yi​(wTxi​+b))+i=1∑m​βi​(−ξi​)

我們要求這個函數的最值，也就是

m i n w , b , ξ ( m a x α ≥ 0 , β ≥ 0 L ( w , b , ξ , α , β ) ) \underset{w,b,\xi}{min}\big(\underset{\alpha\geq0,\beta\geq0}{max}L(w,b,\xi, \alpha,\beta)\big) w,b,ξmin​(α≥0,β≥0max​L(w,b,ξ,α,β))

原函數的對偶問題是

m a x α ≥ 0 , β ≥ 0 ( m i n w , b , ξ L ( w , b , ξ , α , β ) ) \underset{\alpha\geq0,\beta\geq0}{max}\big(\underset{w,b,\xi}{min}L(w,b,\xi, \alpha,\beta)\big) α≥0,β≥0max​(w,b,ξmin​L(w,b,ξ,α,β))

分别對 w , b , ξ w,b,\xi w,b,ξ求導

∂ L ∂ w = w − ∑ i = 1 m α i y i x i → w = ∑ i = 1 m α i y i x i ∂ L ∂ b = − ∑ i = 1 m α i y i = 0 ∂ L ∂ ξ = C − α i − β i = 0 → β i = C − α i \begin{aligned} &\frac{\partial L}{\partial w}=w-\sum_{i=1}^{m}\alpha_iy_ix_i → w=\sum_{i=1}^{m}\alpha_iy_ix_i \\ &\frac{\partial L}{\partial b}=-\sum_{i=1}^{m}\alpha_iy_i=0 \\ &\frac{\partial L}{\partial \xi}=C-\alpha_i-\beta_i=0 →\beta_i = C-\alpha_i \end{aligned} ​∂w∂L​=w−i=1∑m​αi​yi​xi​→w=i=1∑m​αi​yi​xi​∂b∂L​=−i=1∑m​αi​yi​=0∂ξ∂L​=C−αi​−βi​=0→βi​=C−αi​​

代入對偶函數得：

L ( w , b , ξ , α , β ) = − 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 m ξ i + ∑ i = 1 m α i ( 1 − ξ i ) − ∑ i = 1 m ( C − α i ) ξ i = ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j \begin{aligned}L(w,b,\xi,\alpha,\beta)&=-\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i)-\sum_{i=1}^{m}(C-\alpha_i)\xi_i\\ &=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned} L(w,b,ξ,α,β)​=−21​∣∣w∣∣2+Ci=1∑m​ξi​+i=1∑m​αi​(1−ξi​)−i=1∑m​(C−αi​)ξi​=i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​​

由于 α i ≥ 0 \alpha_i\geq0 αi​≥0 ，可以得到 0 ≤ α i ≤ C 0\leq\alpha_i\leq C 0≤αi​≤C ,是以最後式子化簡為

m i n α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j − ∑ i = 1 m α i \underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i αmin​21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​

s . t .   ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , 3 , … , m \begin{aligned} s.t. \ &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq\alpha_i\leq C, i=1,2,3,…,m \end{aligned} s.t. ​i=1∑m​αi​yi​=00≤αi​≤C,i=1,2,3,…,m​

下面來看KTT條件，分三個部分

原始問題可行：

1 − ξ i − y i ( w T x i + b ) ≤ 0 − ξ i ≤ 0 \begin{aligned}1-\xi_i-y_i(w^Tx_i+b)&\leq0\\ -\xi_i&\leq0 \end{aligned} 1−ξi​−yi​(wTxi​+b)−ξi​​≤0≤0​

對偶問題可行：

α i ≥ 0 β i = C − α i \begin{aligned}\alpha_i&\geq0\\ \beta_i &= C-\alpha_i \end{aligned} αi​βi​​≥0=C−αi​​

以及松弛可行：

α i ( 1 − ξ i − y i ( w T x i + b ) ) = 0 β i ξ i = 0 \begin{aligned}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))&=0\\ \beta_i\xi_i&=0 \end{aligned} αi​(1−ξi​−yi​(wTxi​+b))βi​ξi​​=0=0​

觀察 α i ( 1 − ξ i − y i ( w T x i + b ) ) = 0 \alpha_i(1-\xi_i-y_i(w^Tx_i+b))=0 αi​(1−ξi​−yi​(wTxi​+b))=0

1.如果 α i = 0 \alpha_i=0 αi​=0，則 β > 0 , \beta>0, β>0, ξ i = 0 \xi_i=0 ξi​=0 那麼 1 − ξ i − y i ( w T x i + b ) ≤ 0 1-\xi_i-y_i(w^Tx_i+b)\leq0 1−ξi​−yi​(wTxi​+b)≤0，即 y i ( w T x i + b ) ≥ 1 y_i(w^Tx_i+b)\geq1 yi​(wTxi​+b)≥1，樣本被正确分類，這些樣本不是支援向量

2.如果 α i > 0 \alpha_i>0 αi​>0，那麼 1 − ξ i − y i ( w T x i + b ) = 0 1-\xi_i-y_i(w^Tx_i+b)=0 1−ξi​−yi​(wTxi​+b)=0，樣本是支援向量。由于 C = α i + β i C=\alpha_i+\beta_i C=αi​+βi​

又可以分為下面兩種情況

（1） 0 < α < C 0<\alpha<C 0<α<C，那麼 β i > 0 \beta_i>0 βi​>0 ，是以 ξ i = 0 \xi_i=0 ξi​=0，樣本在邊界上

（2） α = C \alpha=C α=C，那麼 β i = 0 \beta_i=0 βi​=0 ，此時

• 如果 ξ i < 1 \xi_i<1 ξi​<1，樣本被正确分類
• 如果 ξ i = 1 \xi_i=1 ξi​=1，樣本在超平面上
• 如果 ξ i > 1 \xi_i>1 ξi​>1，樣本分類錯誤

核函數

對于線性不可分的資料集，無法在原始空間找到分離平面，于是我們就要把原始資料映射到更高的次元（如故事中的拍桌子），在高次元上找到一個分割平面。

線上性回歸中，我們用多項式擴充可以将非線性問題轉化為線性問題，我們借鑒這個思路，在SVM中，我們把低維不可分的資料，映射到高維，變成線性可分的。

我們用 Φ \Phi Φ 來表示核函數，樣本經過核函數映射之後，就變為 Φ ( x ) \Phi(x) Φ(x)

m i n α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j − ∑ i = 1 m α i \underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i αmin​21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​−i=1∑m​αi​

s . t .   ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , 3 , … , m \begin{aligned} s.t. \ &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq\alpha_i\leq C, i=1,2,3,…,m \end{aligned} s.t. ​i=1∑m​αi​yi​=00≤αi​≤C,i=1,2,3,…,m​

把核函數代入便得到

m i n α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j Φ ( x i ) T Φ ( x j ) − ∑ i = 1 m α i \underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\Phi(x_i)^T\Phi(x_j)-\sum_{i=1}^{m}\alpha_i αmin​21​i=1∑m​j=1∑m​αi​αj​yi​yj​Φ(xi​)TΦ(xj​)−i=1∑m​αi​

s . t .   ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , 3 , … , m \begin{aligned} s.t. \ &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq\alpha_i\leq C, i=1,2,3,…,m \end{aligned} s.t. ​i=1∑m​αi​yi​=00≤αi​≤C,i=1,2,3,…,m​

我們可以看到，核函數僅僅是将內積 x i T x j x_i^Tx_j xiT​xj​ 變成 Φ ( x i ) T Φ ( x j ) \Phi(x_i)^T\Phi(x_j) Φ(xi​)TΦ(xj​)，如果我們的原始資料是2次元，映射到5維，再做點積運算，複雜度就會大大提高，如果是更高次元，複雜度将會大大增加，而核函數是在低微來計算得，這樣就降低了運算的複雜度，我們把符合這種條件的函數稱為核函數，稱為K

K ( x i , x j ) = K ( x i T x j ) = Φ ( x i ) T Φ ( x j ) K(x_i,x_j)=K(x_i^Tx_j)=\Phi(x_i)^T\Phi(x_j) K(xi​,xj​)=K(xiT​xj​)=Φ(xi​)TΦ(xj​)

核函數作用其實就是把問題映射到更高次元，把求解複雜度降下來，在訓練模型時如果用到了核函數，在與測試也會經過核函數

經過核函數，資料被映射到高維，計算量隻是增加了一點

常用的核函數有

1、線性核函數 K ( x i , x j ) = x i T x j K(x_i,x_j)=x_i^Tx_j K(xi​,xj​)=xiT​xj​

2、多項式核函數 K ( x i , x j ) = ( γ x i T x j + r ) d K(x_i,x_j)=(\gamma x_i^Tx_j+r)^d K(xi​,xj​)=(γxiT​xj​+r)d 其中 γ , r , d \gamma,r,d γ,r,d需要自己調參

3、高斯核函數 K ( x i , x j ) = e x p ( − γ ∣ ∣ x i − x j ∣ ∣ 2 ) K(x_i,x_j)=exp(-\gamma ||x_i-x_j||^2) K(xi​,xj​)=exp(−γ∣∣xi​−xj​∣∣2)

4、sigmoid核函數 K ( x i , x j ) = t a n h ( γ x i T x j + r ) K(x_i,x_j)=tanh(\gamma x_i^Tx_j+r) K(xi​,xj​)=tanh(γxiT​xj​+r) 其中 γ , r \gamma,r γ,r需要自己調參