1. 前言

前文：支持向量机（SVM）详解（一）
前文详细介绍了线性可分情况下，支持向量机如何将寻找最优分类直线或线性超平面的问题转化为一个凸优化问题。当训练样本集非线性可分，显然，前文所述优化问题无解，即不存在 W W W和 b b b满足所有n个限制条件。
对于非线性可分情况，支持向量机通过适当放松限制条件，使得前文所述优化问题变得有解。同时，支持向量机通过将特征空间由低维映射到高维，提升训练样本集被线性可分的概率，从而提升分类效果。

2. 实际问题是否为线性可分问题的探讨

前文介绍了线性可分情况下，支持向量机寻找最优分类直线或线性超平面的过程。然而不幸的是，实际问题中，大多数分类问题都是非线性可分的。
1969年，人工智能先驱之一Marvin Minsky出版了《感知器》（Perceptrons）一书，在书中他明确地定义了线性可分和非线性可分的概念，同时他用大量实际的例子，并用严格的数学论证了大量现实生活中的很多分类问题都是非线性可分的。其中一个例子如下：
如图1所示，识别一幅图像是否为连通图，是一个非线性可分问题。
连通图与非连通图

证明：
将图中每条边进行标号如图1中左图所示，则图一至图四可表示为 X 1 = ( 1 , 1 , 1 , 0 , 1 , 1 , 0 ) T , X 2 = ( 1 , 1 , 1 , 1 , 0 , 0 , 1 ) T , X 3 = ( 1 , 1 , 1 , 1 , 1 , 0 , 0 ) T , X 4 = ( 1 , 1 , 1 , 0 , 0 , 1 , 1 ) T X_1=(1,1,1,0,1,1,0)^T, X_2=(1,1,1,1,0,0,1)^T, X_3=(1,1,1,1,1,0,0)^T, X_4=(1,1,1,0,0,1,1)^T X1​=(1,1,1,0,1,1,0)T,X2​=(1,1,1,1,0,0,1)T,X3​=(1,1,1,1,1,0,0)T,X4​=(1,1,1,0,0,1,1)T。其中1表示相应位置边存在，0表示相应位置边不存在。
假设上述问题线性可分，则必存在 W = ( w 1 , w 2 , w 3 , w 4 , w 5 , w 6 , w 7 ) T W=(w_1, w_2, w_3, w_4, w_5, w_6, w_7)^T W=(w1​,w2​,w3​,w4​,w5​,w6​,w7​)T和 b b b使得：
W T X 1 + b = w 1 + w 2 + w 3 + w 5 + w 6 + b > 0                         ( 1 ) W T X 2 + b = w 1 + w 2 + w 3 + w 4 + w 7 + b > 0                         ( 2 ) W T X 3 + b = w 1 + w 2 + w 3 + w 4 + w 5 + b < 0                         ( 3 ) W T X 4 + b = w 1 + w 2 + w 3 + w 6 + w 7 + b < 0                         ( 4 ) W^TX_1+b=w_1+w_2+w_3+w_5+w_6+b>0~~~~~~~~~~~~~~~~~~~~~~~(1)\\ W^TX_2+b=w_1+w_2+w_3+w_4+w_7+b>0~~~~~~~~~~~~~~~~~~~~~~~(2)\\ W^TX_3+b=w_1+w_2+w_3+w_4+w_5+b<0~~~~~~~~~~~~~~~~~~~~~~~(3)\\ W^TX_4+b=w_1+w_2+w_3+w_6+w_7+b<0~~~~~~~~~~~~~~~~~~~~~~~(4) WTX1​+b=w1​+w2​+w3​+w5​+w6​+b>0                       (1)WTX2​+b=w1​+w2​+w3​+w4​+w7​+b>0                       (2)WTX3​+b=w1​+w2​+w3​+w4​+w5​+b<0                       (3)WTX4​+b=w1​+w2​+w3​+w6​+w7​+b<0                       (4)
(1) + (2) = 2 w 1 + 2 w 2 + 2 w 3 + w 4 + w 5 + w 6 + w 7 + 2 b > 0                         ( 5 ) 2w_1+2w_2+2w_3+w_4+w_5+w_6+w_7+2b>0~~~~~~~~~~~~~~~~~~~~~~~(5) 2w1​+2w2​+2w3​+w4​+w5​+w6​+w7​+2b>0                       (5)
(3) + (4) = 2 w 1 + 2 w 2 + 2 w 3 + w 4 + w 5 + w 6 + w 7 + 2 b < 0                         ( 6 ) 2w_1+2w_2+2w_3+w_4+w_5+w_6+w_7+2b<0~~~~~~~~~~~~~~~~~~~~~~~(6) 2w1​+2w2​+2w3​+w4​+w5​+w6​+w7​+2b<0                       (6)
显然， 2 w 1 + 2 w 2 + 2 w 3 + w 4 + w 5 + w 6 + w 7 + 2 b 2w_1+2w_2+2w_3+w_4+w_5+w_6+w_7+2b 2w1​+2w2​+2w3​+w4​+w5​+w6​+w7​+2b不可能同时大于0且小于0,式(5)和(6)矛盾。
假设不成立，即上述问题非线性可分。

3. 基本定义

3.1 核函数（Kernel Function）

设 φ \varphi φ是向量 X X X到向量 φ ( X ) \varphi(X) φ(X)的映射，如果对任意两个向量 X 1 和 X 2 X_1和X_2 X1​和X2​，存在 K ( X 1 , X 2 ) = φ ( X 1 ) T φ ( X 2 ) K(X_1, X_2)=\varphi(X_1)^T\varphi(X_2) K(X1​,X2​)=φ(X1​)Tφ(X2​)，则称函数 K ( X 1 , X 2 ) K(X_1, X_2) K(X1​,X2​)为核函数。
核函数 K K K和映射 φ \varphi φ是一一对应的关系，核函数必须满足如下条件才能被分解成两个 φ \varphi φ内积的形式。 K ( X 1 , X 2 ) K(X_1, X_2) K(X1​,X2​)能写成 φ ( X 1 ) T φ ( X 2 ) \varphi(X_1)^T\varphi(X_2) φ(X1​)Tφ(X2​)的充要条件如下：

  1. 交换性： K ( X 1 , X 2 ) = K ( X 2 , X 1 ) K(X_1, X_2)=K(X_2, X_1) K(X1​,X2​)=K(X2​,X1​)
  2. 半正定性： ∀ c i , X i ( i = 1 ∼ n ) , 有 ： ∑ i = 1 n ∑ j = 1 n c i c j K ( X i , X j ) ⩾ 0 \forall c_i, X_i(i=1\sim n), 有：\sum_{i=1}^n\sum_{j=1}^nc_ic_jK(X_i, X_j) \geqslant 0 ∀ci​,Xi​(i=1∼n),有：∑i=1n​∑j=1n​ci​cj​K(Xi​,Xj​)⩾0

3.2 原问题（Prime Problem）与对偶问题（Dual Problem）

设原问题形式如下：
最 小 化 ： f ( W )                          ( 7 ) 限 制 条 件 ： g i ( W ) ⩽ 0 ,         i = 1 ∼ k                    ( 8 )                      h j ( W ) = 0 ,        j = 1 ∼ m                  ( 9 ) 最小化：f(W)~~~~~~~~~~~~~~~~~~~~~~~~(7)\\ 限制条件：g_i(W) \leqslant 0, ~~~~~~~i=1\sim k~~~~~~~~~~~~~~~~~~(8)\\ \ ~~~~~~~~~~~~~~~~~~~h_j(W) = 0, ~~~~~~j=1\sim m~~~~~~~~~~~~~~~~(9) 最小化：f(W)                        (7)限制条件：gi​(W)⩽0,       i=1∼k                  (8)                    hj​(W)=0,      j=1∼m                (9)
定义函数： L ( W , A , B ) = f ( W ) + ∑ i = 1 k α i g i ( W ) + ∑ j = 1 m β j h j ( W ) = f ( W ) + A T G ( W ) + B T H ( W ) L(W,\Alpha,\Beta) = f(W) + \sum_{i=1}^k \alpha_ig_i(W) + \sum_{j=1}^m\beta_jh_j(W) = f(W) + \Alpha^TG(W) + \Beta^TH(W) L(W,A,B)=f(W)+∑i=1k​αi​gi​(W)+∑j=1m​βj​hj​(W)=f(W)+ATG(W)+BTH(W)

其中 A = [ α 1 , α 2 , . . . , α k ] T          B = [ β 1 , β 2 , . . . , β m ] T          G ( W ) = [ g 1 ( W ) , g 2 ( W ) , . . . , g k ( W ) ] T          H ( W ) = [ h 1 ( W ) , h 2 ( W ) , . . . , h m ( W ) ] T \Alpha = [\alpha_1, \alpha_2, ..., \alpha_k]^T\\ \ ~~~~~~~\Beta = [\beta_1, \beta_2, ..., \beta_m]^T\\ \ ~~~~~~~G(W) = [g_1(W), g_2(W), ..., g_k(W)]^T\\ \ ~~~~~~~H(W) = [h_1(W), h_2(W), ..., h_m(W)]^T A=[α1​,α2​,...,αk​]T        B=[β1​,β2​,...,βm​]T        G(W)=[g1​(W),g2​(W),...,gk​(W)]T        H(W)=[h1​(W),h2​(W),...,hm​(W)]T

在定义了函数 L ( W , A , B ) L(W, \Alpha, \Beta) L(W,A,B)的基础上，定义对偶问题如下：
             最 大 化 ： θ ( A , B ) = inf ⁡ W { L ( W , A , B ) }                ( 10 ) 限 制 条 件 ： α i ⩾ 0 ,       i = 1 ∼ k                        ( 11 ) \ ~~~~~~~~~~~最大化：\theta(\Alpha, \Beta) = \inf\limits_W\{L(W, \Alpha, \Beta)\}~~~~~~~~~~~~~~(10)\\ 限制条件：\alpha_i \geqslant 0, ~~~~~i=1\sim k~~~~~~~~~~~~~~~~~~~~~~(11)             最大化：θ(A,B)=Winf​{L(W,A,B)}              (10)限制条件：αi​⩾0,     i=1∼k                      (11)

inf ⁡ \inf inf表示遍历所有求最小。
θ \theta θ是 A \Alpha A和 B \Beta B的函数，这个函数表示：给定 A , B \Alpha, \Beta A,B,去遍历 L ( W , A , B ) L(W, \Alpha, \Beta) L(W,A,B)定义域内所有 W W W,找到使 L ( W , A , B ) L(W, \Alpha, \Beta) L(W,A,B)值最小的那个 W W W,同时将 L ( W , A , B ) L(W, \Alpha, \Beta) L(W,A,B)的这个最小值赋值给 θ ( A , B ) \theta(\Alpha, \Beta) θ(A,B)。

3.2.1 对偶差距（Duality Gap）

如果 W ∗ W^* W∗是原问题的解， ( A ∗ , B ∗ ) (\Alpha^*, \Beta^*) (A∗,B∗)是对偶问题的解，则对偶差距 G = f ( W ∗ ) − θ ( A ∗ , B ∗ ) G=f(W^*)-\theta(\Alpha^*, \Beta^*) G=f(W∗)−θ(A∗,B∗)，且 G ⩾ 0 G\geqslant0 G⩾0。

证明：
θ ( A ∗ , B ∗ ) = inf ⁡ W { L ( W , A ∗ , B ∗ ) }                           ( 12 )                   ⩽ L ( W ∗ , A ∗ , B ∗ )                                      ( 13 )                                                    = f ( W ∗ ) + ( A ∗ ) T G ( W ∗ ) + ( B ∗ ) T H ( W ∗ )                              ( 14 ) ⩽ f ( W ∗ )                                    ( 15 ) \theta(\Alpha^*, \Beta^*) = \inf\limits_W\{L(W, \Alpha^*, \Beta^*)\}~~~~~~~~~~~~~~~~~~~~~~~~~(12)\\ \ ~~~~~~~~~~~~~~~~\leqslant L(W^*, \Alpha^*, \Beta^*)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(13)\\ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~=f(W^*) + (\Alpha^*)^TG(W^*) + (\Beta^*)^TH(W^*)~~~~~~~~~~~~~~~~~~~~~~~~~~~~(14)\\ \leqslant f(W^*)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(15) θ(A∗,B∗)=Winf​{L(W,A∗,B∗)}                         (12)                 ⩽L(W∗,A∗,B∗)                                    (13)                                                  =f(W∗)+(A∗)TG(W∗)+(B∗)TH(W∗)                            (14)⩽f(W∗)                                  (15)
说明：
( 12 ) ⇒ ( 13 ) ： (12)\rArr(13)： (12)⇒(13)：因为 inf ⁡ W { L ( W , A ∗ , B ∗ ) } \inf\limits_W\{L(W, \Alpha^*, \Beta^*)\} Winf​{L(W,A∗,B∗)}表示遍历定义域内所有 W W W取函数 L L L最小值，则该最小值一定会小于或等于指定某个具                          体 的 W ∗ ~~~~~~~~~~~~~~~~~~~~~~~~体的W^*                         体的W∗所得到的函数 L L L的值；
( 13 ) ⇒ ( 14 ) ： (13)\rArr(14)： (13)⇒(14)：根据函数 L ( W , A , B ) L(W,\Alpha,\Beta) L(W,A,B)的定义展开；
( 14 ) ⇒ ( 15 ) ： (14)\rArr(15)： (14)⇒(15)：因为 H ( W ∗ ) H(W^*) H(W∗)的每个分量均等于0， G ( W ∗ ) G(W^*) G(W∗)的每个分量均小于或等于0， A ∗ \Alpha^* A∗的每个分量均大于或等于0，因此                          ( A ∗ ) T G ( W ∗ ) + ( B ∗ ) T H ( W ∗ ) ⩽ 0 ~~~~~~~~~~~~~~~~~~~~~~~~(\Alpha^*)^TG(W^*) + (\Beta^*)^TH(W^*) \leqslant 0                         (A∗)TG(W∗)+(B∗)TH(W∗)⩽0。

3.2.2 强对偶定理（Strong Duality Theorem）

如果 g i ( W ) = a i W + b i , h j ( W ) = c j W + d j , ( i = 1 ∼ k , j = 1 ∼ m ) , f ( W ) g_i(W)=a_iW+b_i, h_j(W)=c_jW+d_j, (i=1\sim k, j=1\sim m), f(W) gi​(W)=ai​W+bi​,hj​(W)=cj​W+dj​,(i=1∼k,j=1∼m),f(W)为凸函数，则有 f ( W ∗ ) = θ ( A ∗ , B ∗ ) f(W^*)=\theta(\Alpha^*, \Beta^*) f(W∗)=θ(A∗,B∗)，即对偶差距G等于0。

如果原问题的目标函数是凸函数，限制条件是线性函数，则原问题的解与对偶问题的解相等，即 f ( W ∗ ) = θ ( A ∗ , B ∗ ) 。 f(W^*)=\theta(\Alpha^*, \Beta^*)。 f(W∗)=θ(A∗,B∗)。

3.2.3 KKT条件

若 f ( W ∗ ) = θ ( A ∗ , B ∗ ) f(W^*)=\theta(\Alpha^*, \Beta^*) f(W∗)=θ(A∗,B∗)，则 ∀ i = 1 ∼ k \forall i=1\sim k ∀i=1∼k，要么 α i ∗ = 0 \alpha_i^*=0 αi∗​=0，要么 g i ( W ∗ ) = 0 g_i(W^*)=0 gi​(W∗)=0。

因为 f ( W ∗ ) = θ ( A ∗ , B ∗ ) f(W^*)=\theta(\Alpha^*, \Beta^*) f(W∗)=θ(A∗,B∗)，则 ( A ∗ ) T G ( W ∗ ) + ( B ∗ ) T H ( W ∗ ) (\Alpha^*)^TG(W^*) + (\Beta^*)^TH(W^*) (A∗)TG(W∗)+(B∗)TH(W∗)必定等于0。所有要么 A ∗ \Alpha^* A∗的分量 α i ∗ = 0 \alpha_i^*=0 αi∗​=0，要么 G ( W ∗ ) G(W^*) G(W∗)的分量 g i ( W ∗ ) = 0 g_i(W^*)=0 gi​(W∗)=0。

4. 支持向量机——非线性可分情况

回顾线性可分情况下，支持向量机优化问题如下：
最 小 化 :    1 2 ∣ ∣ W ∣ ∣ 2                                                       ( 16 ) 限 制 条 件 ：    y i ( W T X i + b ) ⩾ 1 ,    i = 1 ∼ n                  ( 17 ) 最小化:~~\frac{1}{2}||W||^2~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(16)\\ 限制条件：~~y_i(W^TX_i+b)\geqslant1,~~i=1\sim n~~~~~~~~~~~~~~~~(17) 最小化:  21​∣∣W∣∣2                                                     (16)限制条件：  yi​(WTXi​+b)⩾1,  i=1∼n                (17)
对于非线性可分情况，需要适当放松限制条件，使上述线性可分情况下的最优化问题变得有解。放松限制条件的基本思路是：对训练集中的每个训练样本及标签 ( X i , y i ) (X_i, y_i) (Xi​,yi​)，设置一个松弛变量 δ i \delta_i δi​(Slack Variable)，将限制条件改写为： y i ( W T X i + b ) ⩾ 1 − δ i ,    i = 1 ∼ n y_i(W^TX_i+b)\geqslant1-\delta_i,~~i=1\sim n yi​(WTXi​+b)⩾1−δi​,  i=1∼n。
改造后的支持向量机优化问题如下：
最 小 化 ：    1 2 ∣ ∣ W ∣ ∣ 2 + c ∑ i = 1 n δ i    或    1 2 ∣ ∣ W ∣ ∣ 2 + c ∑ i = 1 n δ i 2                ( 18 ) 限 制 条 件 ：    ( 1 )    δ i ⩾ 0 ,    i = 1 ∼ n                                                   ( 19 )               ( 2 )    y i ( W T X i + b ) ⩾ 1 − δ i ,    i = 1 ∼ n             ( 20 ) 最小化：~~\frac{1}{2}||W||^2+c\sum_{i=1}^n\delta_i~~或~~\frac{1}{2}||W||^2+c\sum_{i=1}^n\delta_i^2~~~~~~~~~~~~~~(18)\\ 限制条件：~~(1)~~\delta_i\geqslant0,~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(19)\\ ~~~~~~~~~~~~~(2)~~y_i(W^TX_i+b)\geqslant1-\delta_i,~~i=1\sim n~~~~~~~~~~~(20) 最小化：  21​∣∣W∣∣2+ci=1∑n​δi​  或  21​∣∣W∣∣2+ci=1∑n​δi2​              (18)限制条件：  (1)  δi​⩾0,  i=1∼n                                                 (19)             (2)  yi​(WTXi​+b)⩾1−δi​,  i=1∼n           (20)

c c c称为比例因子，是人为设定的。一个算法中需要人为事先设定的参数叫做算法的超参数（Hyper Parameter）。一般来说，在实际运用中，会不断变化 c c c的值，同时测试算法的识别率，然后选取使识别率最大的超参数 c c c的值。支持向量机是超参数很少的算法模型。
c ∑ i = 1 n δ i c\sum_{i=1}^n\delta_i c∑i=1n​δi​和 c ∑ i = 1 n δ i 2 c\sum_{i=1}^n\delta_i^2 c∑i=1n​δi2​称为正则项（Regulation Term）。在优化函数中加入正则项，表明尽量在不放松限制条件的情况下，求解最优分类直线或超平面。如果不约束 δ i \delta_i δi​的取值，显然当 δ i \delta_i δi​取非常大的正数时，任意 W 和 b W和b W和b均会满足限制条件(1)。因此，求解出来的 W W W和 b b b所对应的直线或超平面，分类效果将会非常差。

非线性可分

对于图1所示非线性可分数据集，运用上述改造后的支持向量机优化问题，仍可求解出合理的分类直线。

5. 特征空间映射到高维的解决方法

5.1 低维到高维的映射

考虑如下图2所示情况，使用上述改造后的支持向量机优化问题，求解出一条分类直线。如图2中的直线所示，求解出的分类直线效果非常差，和瞎猜没什么区别，问题出在哪里？
无法求得合理的分类直线
因为支持向量机限定了分类两类的决策函数是线性的，即支持向量机从无数条直线或超平面中寻找最优的分类直线或超平面。但是在图2所示数据集中，任何直线均无法合理地分开两类。显然，分开两类的决策函数应该是一条类似椭圆的曲线。
人工神经网络等算法，通过多层非线性函数的组合，能够产生类似于椭圆这样的曲线，从而将图2所示中这类训练样本集合理二分。
支持向量机扩大可选函数范围，从而将图2所示中的这类训练样本集合理二分的方法可谓独竖一帜。支持向量机通过将特征空间由低维映射到高维，然后在高维特征空间中，仍然使用线性超平面对训练样本进行分类。

存在定理如下：
在一个M维空间中随机取N个训练样本，随机地对每个训练样本赋予标签+1或-1。设这些训练样本线性可分的概率为P(M)，则当M趋于无穷大时，P(M)=1。
举例说明如下：
考量如图4所示异或问题，其中黑色点为一类，白色点为另一类，即 X 1 = ( 0 , 0 ) T ∈ C 1 , X 2 = ( 1 , 1 ) T ∈ C 1 , X 3 = ( 1 , 0 ) T ∈ C 2 , X 4 = ( 0 , 1 ) T ∈ C 2 X_1=(0,0)^T\in C_1, X_2=(1, 1)^T\in C_1, X_3=(1, 0)^T\in C_2, X_4= (0, 1)^T\in C_2 X1​=(0,0)T∈C1​,X2​=(1,1)T∈C1​,X3​=(1,0)T∈C2​,X4​=(0,1)T∈C2​，显然该样本集非线性可分。
异或问题
构造如下2维到5维的映射 φ ( X ) : \varphi(X): φ(X):
X = ( x 1 , x 2 ) T → φ ( X ) = ( x 1 2 , x 2 2 , x 1 , x 2 , x 1 x 2 ) T X=(x_1, x_2)^T\to\varphi(X)=(x_1^2, x_2^2, x_1, x_2, x_1x_2)^T X=(x1​,x2​)T→φ(X)=(x12​,x22​,x1​,x2​,x1​x2​)T
则 φ ( X 1 ) = ( 0 , 0 , 0 , 0 , 0 ) T , φ ( X 2 ) = ( 1 , 1 , 1 , 1 , 1 ) T , φ ( X 3 ) = ( 1 , 0 , 1 , 0 , 0 ) , φ ( X 4 ) = ( 0 , 1 , 0 , 1 , 0 ) T \varphi(X_1)=(0,0,0,0,0)^T, \varphi(X_2)=(1,1,1,1,1)^T, \varphi(X_3)=(1,0,1,0,0), \varphi(X_4)=(0,1,0,1,0)^T φ(X1​)=(0,0,0,0,0)T,φ(X2​)=(1,1,1,1,1)T,φ(X3​)=(1,0,1,0,0),φ(X4​)=(0,1,0,1,0)T。设 W = ( − 1 , − 1 , − 1 , − 1 , 6 ) T , b = 1 ， 则 ： W=(-1,-1,-1,-1,6)^T, b=1，则： W=(−1,−1,−1,−1,6)T,b=1，则：
W T φ ( X 1 ) + b = 1 > 0 W T φ ( X 2 ) + b = 3 > 0 W T φ ( X 3 ) + b = − 1 < 0 W T φ ( X 4 ) + b = − 1 < 0 W^T\varphi(X_1)+b=1>0\\ W^T\varphi(X_2)+b=3>0\\ W^T\varphi(X_3)+b=-1<0\\ W^T\varphi(X_4)+b=-1<0 WTφ(X1​)+b=1>0WTφ(X2​)+b=3>0WTφ(X3​)+b=−1<0WTφ(X4​)+b=−1<0
因此， φ ( X 1 ) , φ ( X 2 ) , φ ( X 3 ) , φ ( X 4 ) \varphi(X_1), \varphi(X_2), \varphi(X_3), \varphi(X_4) φ(X1​),φ(X2​),φ(X3​),φ(X4​)线性可分。
可见2维非线性可分数据集，其特征空间映射到5维后，变成了线性可分数据集。

当 X X X映射成 φ ( X ) \varphi(X) φ(X)，支持向量机优化问题转变成如下形式：
最 小 化 ：    1 2 ∣ ∣ W ∣ ∣ 2 + c ∑ i = 1 n δ i                                                      ( 21 ) 限 制 条 件 ：    ( 1 )    δ i ⩾ 0 ,    i = 1 ∼ n                                                   ( 22 )                     ( 2 )    y i ( W T φ ( X i ) + b ) ⩾ 1 − δ i ,    i = 1 ∼ n             ( 23 ) 最小化：~~\frac{1}{2}||W||^2+c\sum_{i=1}^n\delta_i~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(21)\\ 限制条件：~~(1)~~\delta_i\geqslant0,~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(22)\\ ~~~~~~~~~~~~~~~~~~~(2)~~y_i(W^T\varphi(X_i)+b)\geqslant1-\delta_i,~~i=1\sim n~~~~~~~~~~~(23) 最小化：  21​∣∣W∣∣2+ci=1∑n​δi​                                                    (21)限制条件：  (1)  δi​⩾0,  i=1∼n                                                 (22)                   (2)  yi​(WTφ(Xi​)+b)⩾1−δi​,  i=1∼n           (23)

当 X X X映射成 φ ( X ) \varphi(X) φ(X)， W W W的维度须保持与 φ ( X ) \varphi(X) φ(X)保持一致。高维情况下优化问题的解法和低维情况下是完全类似的。

5.2 转化为对偶问题

将特征空间由低维映射到高维，可使得低维情况下非线性可分数据集变得线性可分。而且高维情况下的优化问题的解法和低维情况下完全类似。因此，只剩下最后一个问题：低维到高维的映射 φ ( X ) \varphi(X) φ(X)的具体形式如何确定？
支持向量机的创始人Vapnik在关于低维到高维的映射 φ ( X ) \varphi(X) φ(X)具体形式这个问题上的回答是极具创造性的。他指出，不用知道 φ ( X ) \varphi(X) φ(X)的具体形式，如果对任意两个向量 X 1 X_1 X1​和 X 2 X_2 X2​，我们知道一个核函数 K ( X 1 , X 2 ) = φ ( X 1 ) T φ ( X 2 ) K(X_1, X_2)=\varphi(X_1)^T\varphi(X_2) K(X1​,X2​)=φ(X1​)Tφ(X2​)，那么我们可以通过一些技巧获得一个测试样本 X X X的类别信息，从而完成对测试样本类别的预测。
对任意一个测试样本，仅需知道核函数 K K K，而不用知道低维到高维的映射 φ ( X ) \varphi(X) φ(X)，就能知道其类别信息。推导过程如下：
首先将支持向量机的优化问题转化为对偶问题。为了将支持向量机的优化问题转化为对偶问题，须改变支持向量机的优化问题形式，使之和原问题与对偶问题定义中原问题形式保持一致。然后根据定义，对照写出支持向量机的优化问题的对偶问题。
考量3.2中原问题形式，其通过优化变量 W W W，使得函数 f ( W ) f(W) f(W)值最小。存在 k k k个不等式限制条件，形式为 g i ( W ) ⩽ 0 g_i(W) \leqslant 0 gi​(W)⩽0。存在 m m m个等式限制条件，形式为 h j ( W ) = 0 h_j(W) = 0 hj​(W)=0。
考量支持向量机优化问题(21)—(23)，可以发现优化问题中限制条件形式与原问题定义中形式不一致。首先将 δ i ⩾ 0 , ( i = 1 ∼ n ) \delta_i\geqslant0, (i=1\sim n) δi​⩾0,(i=1∼n)转变成为 δ i ⩽ 0 , ( i = 1 ∼ n ) \delta_i\leqslant0, (i=1\sim n) δi​⩽0,(i=1∼n)，即将支持向量机的优化问题中所有 δ \delta δ的值全部取其相反数，优化问题转变成如下形式：
最 小 化 ：    1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i                           ( 24 ) 限 制 条 件 ： ( 1 )    δ i ⩽ 0 ,    i = 1 ∼ n                         ( 25 )                                           ( 2 )    y i ( W T φ ( X i ) + b ) ⩾ 1 + δ i ,    i = 1 ∼ n           ( 26 ) 最小化：~~\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i~~~~~~~~~~~~~~~~~~~~~~~~~(24)\\ 限制条件：(1)~~\delta_i\leqslant0,~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~(25)\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(2)~~y_i(W^T\varphi(X_i)+b)\geqslant1+\delta_i,~~i=1\sim n~~~~~~~~~(26) 最小化：  21​∣∣W∣∣2−ci=1∑n​δi​                         (24)限制条件：(1)  δi​⩽0,  i=1∼n                       (25)                                         (2)  yi​(WTφ(Xi​)+b)⩾1+δi​,  i=1∼n         (26)

当 δ i ⩾ 0 , ( i = 1 ∼ n ) \delta_i\geqslant0, (i=1\sim n) δi​⩾0,(i=1∼n)转变成为 δ i ⩽ 0 , ( i = 1 ∼ n ) \delta_i\leqslant0, (i=1\sim n) δi​⩽0,(i=1∼n)，整个优化问题中所有 δ i \delta_i δi​均需取其相反数。因此最小化： 1 2 ∣ ∣ W ∣ ∣ 2 + c ∑ i = 1 n δ i \frac{1}{2}||W||^2+c\sum_{i=1}^n\delta_i 21​∣∣W∣∣2+c∑i=1n​δi​须换变成为 1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i \frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i 21​∣∣W∣∣2−c∑i=1n​δi​。限制条件（2）须转变成为 y i ( W T φ ( X i ) + b ) ⩾ 1 + δ i ,    i = 1 ∼ n y_i(W^T\varphi(X_i)+b)\geqslant1+\delta_i,~~i=1\sim n yi​(WTφ(Xi​)+b)⩾1+δi​,  i=1∼n。

考量式（26），可以发现其与原问题定义中形式不一致，将其移项转变成： 1 + δ i − y i ( W T φ ( X i ) + b ) ⩽ 0 1+\delta_i-y_i(W^T\varphi(X_i)+b)\leqslant0 1+δi​−yi​(WTφ(Xi​)+b)⩽0。经过整理，可将支持向量机优化问题写成如下形式：
最 小 化 ：    1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i                           ( 27 ) 限 制 条 件 ： ( 1 )    δ i ⩽ 0 ,    i = 1 ∼ n                         ( 28 )                                                  ( 2 )    1 + δ i − y i W T φ ( X i ) − y i b ⩽ 0 ,    i = 1 ∼ n           ( 29 ) 最小化：~~\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i~~~~~~~~~~~~~~~~~~~~~~~~~(27)\\ 限制条件：(1)~~\delta_i\leqslant0,~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~(28)\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(2)~~1+\delta_i-y_iW^T\varphi(X_i)-y_ib\leqslant0,~~i=1\sim n~~~~~~~~~(29) 最小化：  21​∣∣W∣∣2−ci=1∑n​δi​                         (27)限制条件：(1)  δi​⩽0,  i=1∼n                       (28)                                                (2)  1+δi​−yi​WTφ(Xi​)−yi​b⩽0,  i=1∼n         (29)

原问题定义中的优化变量 W = ( W , b , Δ ) = ( w 1 , w 2 , . . . , w l , b , δ i , δ 2 , . . . , δ n ) W=(W,b,\Delta)=(w_1,w_2,...,w_l,b,\delta_i,\delta_2,...,\delta_n) W=(W,b,Δ)=(w1​,w2​,...,wl​,b,δi​,δ2​,...,δn​)，其中 l l l等于向量 φ ( X i ) \varphi(X_i) φ(Xi​)的维数；
原问题定义中的目标函数 f ( W ) = 1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i f(W)=\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i f(W)=21​∣∣W∣∣2−c∑i=1n​δi​；
原问题中限制条件 g i ( W ) ⩽ 0 ,   i = 1 ∼ k g_i(W) \leqslant 0, ~i=1\sim k gi​(W)⩽0, i=1∼k等同于① δ i ⩽ 0 ,   i = 1 ∼ n \delta_i\leqslant0,~i=1\sim n δi​⩽0, i=1∼n，② 1 + δ i − y i W T φ ( X i ) − y i b ⩽ 0 ,    i = 1 ∼ n 1+\delta_i-y_iW^T\varphi(X_i)-y_ib\leqslant0,~~i=1\sim n 1+δi​−yi​WTφ(Xi​)−yi​b⩽0,  i=1∼n。其中原问题定义中的 k k k在该优化问题中等于 2 n 2n 2n，即总共存在 2 n 2n 2n个不等式形式的限制条件；
原问题中限制条件 h j ( W ) = 0 ,    j = 1 ∼ m h_j(W) = 0, ~~j=1\sim m hj​(W)=0,  j=1∼m在该优化问题中不存在，即不存在等式形式的限制条件。

考量原问题与对偶问题定义中定义的函数 L ( W , A , B ) = f ( W ) + ∑ i = 1 k α i g i ( W ) + ∑ j = 1 m β j h j ( W ) L(W, \Alpha, \Beta)=f(W) + \sum_{i=1}^k \alpha_ig_i(W) + \sum_{j=1}^m\beta_jh_j(W) L(W,A,B)=f(W)+∑i=1k​αi​gi​(W)+∑j=1m​βj​hj​(W)，在支持向量机的优化问题中：
L ( W , A , B ) = 1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i + ∑ i = 1 n α i [ 1 + δ i − y i W T φ ( X i ) − y i b ] + ∑ i = 1 n β i δ i           ( 30 ) L(W, \Alpha, \Beta)=\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i+\sum_{i=1}^n\alpha_i[1+\delta_i-y_iW^T\varphi(X_i)-y_ib]+\sum_{i=1}^n\beta_i\delta_i~~~~~~~~~(30) L(W,A,B)=21​∣∣W∣∣2−ci=1∑n​δi​+i=1∑n​αi​[1+δi​−yi​WTφ(Xi​)−yi​b]+i=1∑n​βi​δi​         (30)

由于原问题中限制条件 g i ( W ) ⩽ 0 ,   i = 1 ∼ k g_i(W) \leqslant 0, ~i=1\sim k gi​(W)⩽0, i=1∼k等同于① δ i ⩽ 0 ,   i = 1 ∼ n \delta_i\leqslant0,~i=1\sim n δi​⩽0, i=1∼n，② 1 + δ i − y i W T φ ( X i ) − y i b ⩽ 0 ,    i = 1 ∼ n 1+\delta_i-y_iW^T\varphi(X_i)-y_ib\leqslant0,~~i=1\sim n 1+δi​−yi​WTφ(Xi​)−yi​b⩽0,  i=1∼n， L ( W , A , B ) L(W, \Alpha, \Beta) L(W,A,B)中 g i ( W ) g_i(W) gi​(W)前的系数 α i \alpha_i αi​在式（30）中，被拆成两部分，即 α i \alpha_i αi​和 β i \beta_i βi​。

因此，支持向量机优化问题的对偶问题应写成如下形式：
最 大 化 ： θ ( A , B ) = inf ⁡ W , b , Δ { 1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i + ∑ i = 1 n α i [ 1 + δ i − y i W T φ ( X i ) − y i b ] + ∑ i = 1 n β i δ i }           ( 31 ) 限 制 条 件 ： ( 1 ) α i ⩾ 0 ,        i = 1 ∼ n                   ( 32 )                      ( 2 ) β i ⩾ 0 ,        i = 1 ∼ n                   ( 33 ) 最大化：\theta(\Alpha, \Beta) = \inf\limits_{W,b,\Delta}\{\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i+\sum_{i=1}^n\alpha_i[1+\delta_i-y_iW^T\varphi(X_i)-y_ib]+\sum_{i=1}^n\beta_i\delta_i\}~~~~~~~~~(31)\\ 限制条件：(1)\alpha_i\geqslant0,~~~~~~i=1\sim n~~~~~~~~~~~~~~~~~(32)\\ ~~~~~~~~~~~~~~~~~~~~(2)\beta_i\geqslant0,~~~~~~i=1\sim n~~~~~~~~~~~~~~~~~(33) 最大化：θ(A,B)=W,b,Δinf​{21​∣∣W∣∣2−ci=1∑n​δi​+i=1∑n​αi​[1+δi​−yi​WTφ(Xi​)−yi​b]+i=1∑n​βi​δi​}         (31)限制条件：(1)αi​⩾0,      i=1∼n                 (32)                    (2)βi​⩾0,      i=1∼n                 (33)
对式（31）进行化简，由于 inf ⁡ W , b , Δ \inf\limits_{W,b,\Delta} W,b,Δinf​表示遍历所有 W , b , Δ W,b,\Delta W,b,Δ，并取最小值，为一个典型的函数求极值问题。因此对 ( W , b , δ i ) (W, b, \delta_i) (W,b,δi​)求偏导，并令偏导数等于0。将求解出的结果带入式（31），即简化式（31）：
∂ θ ∂ W = W − ∑ i = 1 n α i y i φ ( X i ) = 0                           ( 34 ) ∂ θ δ i = − c + α i + β i = 0                                    ( 35 ) ∂ θ ∂ b = − ∑ i = 1 n α i y i = 0                                         ( 36 ) \frac{\partial\theta}{\partial W}=W-\sum_{i=1}^n\alpha_iy_i\varphi(X_i)=0~~~~~~~~~~~~~~~~~~~~~~~~~(34)\\ \frac{\partial\theta}{\delta_i}=-c+\alpha_i+\beta_i=0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(35)\\ \frac{\partial\theta}{\partial b}=-\sum_{i=1}^n\alpha_iy_i=0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(36) ∂W∂θ​=W−i=1∑n​αi​yi​φ(Xi​)=0                         (34)δi​∂θ​=−c+αi​+βi​=0                                  (35)∂b∂θ​=−i=1∑n​αi​yi​=0                                       (36)

若 W = ( w 1 , w 2 , . . . , w m ) T , f ( W ) W=(w_1,w_2,...,w_m)^T,f(W) W=(w1​,w2​,...,wm​)T,f(W)为 W W W的函数，则 ∂ f ∂ W = ( ∂ f ∂ w 1 , ∂ f ∂ w 2 , . . . , ∂ f ∂ w m ) T \frac{\partial f}{\partial W}=(\frac{\partial f}{\partial w_1},\frac{\partial f}{\partial w_2},...,\frac{\partial f}{\partial w_m})^T ∂W∂f​=(∂w1​∂f​,∂w2​∂f​,...,∂wm​∂f​)T；
若 f ( W ) = 1 2 ∣ ∣ W ∣ ∣ 2 f(W)=\frac{1}{2}||W||^2 f(W)=21​∣∣W∣∣2，则 ∂ f ∂ W = W \frac{\partial f}{\partial W}=W ∂W∂f​=W；
若 f ( W ) = W T g ( X ) f(W)=W^Tg(X) f(W)=WTg(X)，则 ∂ f ∂ W = g ( X ) \frac{\partial f}{\partial W}=g(X) ∂W∂f​=g(X)。
具体参见：向量求导法则

从式(34)—(36)可以推出：
W = ∑ i = 1 n α i y i φ ( X i )                         ( 37 ) α i + β i = c                                      ( 38 ) ∑ i = 1 n α i y i = 0                                     ( 39 ) W=\sum_{i=1}^n\alpha_iy_i\varphi(X_i)~~~~~~~~~~~~~~~~~~~~~~~(37)\\ \alpha_i+\beta_i=c~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(38)\\ \sum_{i=1}^n\alpha_iy_i=0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(39) W=i=1∑n​αi​yi​φ(Xi​)                       (37)αi​+βi​=c                                    (38)i=1∑n​αi​yi​=0                                   (39)
将式(37)—(39)代入式(31)：【这里看上去有一点点复杂，但是实际上并不难理解。我写得很详细，你绝对能够看明白， 我 保 证 ！ \color{red}我保证！ 我保证！请静下心来，深呼吸一次，跟着我的思路，结合下面的解释，一步一步慢慢查看推导过程。】
θ ( A , B ) = inf ⁡ W , b , Δ { 1 2 ∣ ∣ W ∣ ∣ 2 − c ∑ i = 1 n δ i + ∑ i = 1 n α i [ 1 + δ i − y i W T φ ( X i ) − y i b ] + ∑ i = 1 n β i δ i }                     ( 40 ) = inf ⁡ W , b , Δ { 1 2 ∣ ∣ W ∣ ∣ 2 + ∑ i = 1 n α i [ 1 − y i W T φ ( X i ) − y i b ] }                                                ( 41 ) = inf ⁡ W , b , Δ { 1 2 ∣ ∣ W ∣ ∣ 2 + ∑ i = 1 n α i [ 1 − y i W T φ ( X i ) ] }                                                          ( 42 ) = inf ⁡ W , b , Δ { ∑ i = 1 n α i + 1 2 ∣ ∣ W ∣ ∣ 2 − ∑ i = 1 n α i y i W T φ ( X i ) }                                                    ( 43 ) = inf ⁡ W , b , Δ { ∑ i = 1 n α i + 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j ) − ∑ i = 1 n α i y i W T φ ( X i ) }          ( 44 ) = inf ⁡ W , b , Δ { ∑ i = 1 n α i + 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j ) − ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j ) }                 ( 45 ) = inf ⁡ W , b , Δ { ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j ) }                                             ( 46 ) = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j )                                                          ( 47 ) = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( X i , X j )                                                               ( 48 ) \theta(\Alpha, \Beta) = \inf\limits_{W,b,\Delta}\{\frac{1}{2}||W||^2-c\sum_{i=1}^n\delta_i+\sum_{i=1}^n\alpha_i[1+\delta_i-y_iW^T\varphi(X_i)-y_ib]+\sum_{i=1}^n\beta_i\delta_i\}~~~~~~~~~~~~~~~~~~~(40)\\ =\inf\limits_{W,b,\Delta}\{\frac{1}{2}||W||^2+\sum_{i=1}^n\alpha_i[1-y_iW^T\varphi(X_i)-y_ib]\}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(41)\\ =\inf\limits_{W,b,\Delta}\{\frac{1}{2}||W||^2+\sum_{i=1}^n\alpha_i[1-y_iW^T\varphi(X_i)]\}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(42)\\ =\inf\limits_{W,b,\Delta}\{\sum_{i=1}^n\alpha_i+\frac{1}{2}||W||^2-\sum_{i=1}^n\alpha_iy_iW^T\varphi(X_i)\}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(43)\\ =\inf\limits_{W,b,\Delta}\{\sum_{i=1}^n\alpha_i+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)-\sum_{i=1}^n\alpha_iy_iW^T\varphi(X_i)\}~~~~~~~~(44)\\ =\inf\limits_{W,b,\Delta}\{\sum_{i=1}^n\alpha_i+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)-\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)\}~~~~~~~~~~~~~~~(45)\\ =\inf\limits_{W,b,\Delta}\{\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)\}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(46)\\ =\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(47)\\ =\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(X_i,X_j)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(48) θ(A,B)=W,b,Δinf​{21​∣∣W∣∣2−ci=1∑n​δi​+i=1∑n​αi​[1+δi​−yi​WTφ(Xi​)−yi​b]+i=1∑n​βi​δi​}                   (40)=W,b,Δinf​{21​∣∣W∣∣2+i=1∑n​αi​[1−yi​WTφ(Xi​)−yi​b]}                                              (41)=W,b,Δinf​{21​∣∣W∣∣2+i=1∑n​αi​[1−yi​WTφ(Xi​)]}                                                        (42)=W,b,Δinf​{i=1∑n​αi​+21​∣∣W∣∣2−i=1∑n​αi​yi​WTφ(Xi​)}                                                  (43)=W,b,Δinf​{i=1∑n​αi​+21​i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)−i=1∑n​αi​yi​WTφ(Xi​)}        (44)=W,b,Δinf​{i=1∑n​αi​+21​i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)−i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)}               (45)=W,b,Δinf​{i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)}                                           (46)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)                                                        (47)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​K(Xi​,Xj​)                                                             (48)

推导过程辅助解释：
(40) ⇒ \rArr ⇒(41)：因为 α i + β i = c \alpha_i+\beta_i=c αi​+βi​=c，因此可消去式（40）中 − c ∑ i = 1 n δ i 、 ∑ i = 1 n α i δ i 、 ∑ i = 1 n β i δ i -c\sum_{i=1}^n\delta_i、\sum_{i=1}^n\alpha_i\delta_i、\sum_{i=1}^n\beta_i\delta_i −c∑i=1n​δi​、∑i=1n​αi​δi​、∑i=1n​βi​δi​，得到式（41）；
(41) ⇒ \rArr ⇒(42)：因为 ∑ i = 1 n α i y i = 0 \sum_{i=1}^n\alpha_iy_i=0 ∑i=1n​αi​yi​=0，因此可消去式（41）中 ∑ i = 1 n α i y i b \sum_{i=1}^n\alpha_iy_ib ∑i=1n​αi​yi​b，得到式（42）；
(42) ⇒ \rArr ⇒(43)：将 ∑ i = 1 n α i \sum_{i=1}^n\alpha_i ∑i=1n​αi​与括号内每一项相乘；
(43) ⇒ \rArr ⇒(44)：
1 2 ∣ ∣ W ∣ ∣ 2 = 1 2 W T W                                                                         ① = 1 2 [ ∑ i = 1 n α i y i φ ( X i ) ] T [ ∑ j = 1 n α j y j φ ( X j ) ]              ② = 1 2 [ ∑ i = 1 n α i y i φ ( X i ) T ] [ ∑ j = 1 n α j y j φ ( X j ) ]              ③ = 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j )                   ④ ① ： 因 为 W 是 一 个 列 向 量 ， 所 以 ∣ ∣ W ∣ ∣ 2 = W T W                                              ② ⇒ ③ ： 因 为 α i 、 y i 为 常 数 ， φ ( X i ) 为 向 量 ， 所 以 [ ∑ i = 1 n α i y i φ ( X i ) ] T = ∑ i = 1 n α i y i φ ( X i ) T \frac{1}{2}||W||^2=\frac{1}{2}W^TW~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~①\\ =\frac{1}{2}[\sum_{i=1}^n\alpha_iy_i\varphi(X_i)]^T[\sum_{j=1}^n\alpha_jy_j\varphi(X_j)]~~~~~~~~~~~~②\\ =\frac{1}{2}[\sum_{i=1}^n\alpha_iy_i\varphi(X_i)^T][\sum_{j=1}^n\alpha_jy_j\varphi(X_j)]~~~~~~~~~~~~③\\ =\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)~~~~~~~~~~~~~~~~~④\\ ①：因为W是一个列向量，所以||W||^2=W^TW~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ ②\rArr③：因为\alpha_i、y_i为常数，\varphi(X_i)为向量，所以[\sum_{i=1}^n\alpha_iy_i\varphi(X_i)]^T=\sum_{i=1}^n\alpha_iy_i\varphi(X_i)^T 21​∣∣W∣∣2=21​WTW                                                                       ①=21​[i=1∑n​αi​yi​φ(Xi​)]T[j=1∑n​αj​yj​φ(Xj​)]            ②=21​[i=1∑n​αi​yi​φ(Xi​)T][j=1∑n​αj​yj​φ(Xj​)]            ③=21​i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)                 ④①：因为W是一个列向量，所以∣∣W∣∣2=WTW                                            ②⇒③：因为αi​、yi​为常数，φ(Xi​)为向量，所以[i=1∑n​αi​yi​φ(Xi​)]T=i=1∑n​αi​yi​φ(Xi​)T
(44) ⇒ \rArr ⇒(45)：
∑ i = 1 n α i y i W T φ ( X i ) = ∑ i = 1 n α i y i [ ∑ j = 1 n α j y j φ ( X j ) ] T φ ( X i )                                             ① = ∑ i = 1 n α i y i [ ∑ j = 1 n α j y j φ ( X j ) T ] φ ( X i )              ② = ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X j ) T φ ( X i )                ③ = ∑ i = 1 n ∑ j = 1 n α i α j y i y j φ ( X i ) T φ ( X j )                 ④ ③ ⇒ ④ ： 调 换 i 和 j 。 相 当 于 双 重 f o r 循 环 ， 循 环 变 量 先 为 i 还 是 先 为 j ， 都 是 一 样 的 。 \sum_{i=1}^n\alpha_iy_iW^T\varphi(X_i)=\sum_{i=1}^n\alpha_iy_i[\sum_{j=1}^n\alpha_jy_j\varphi(X_j)]^T\varphi(X_i)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~①\\ =\sum_{i=1}^n\alpha_iy_i[\sum_{j=1}^n\alpha_jy_j\varphi(X_j)^T]\varphi(X_i)~~~~~~~~~~~~②\\ =\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_j)^T\varphi(X_i)~~~~~~~~~~~~~~③\\ =\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\varphi(X_i)^T\varphi(X_j)~~~~~~~~~~~~~~~④\\ ③\rArr④：调换i和j。相当于双重for循环，循环变量先为i还是先为j，都是一样的。 i=1∑n​αi​yi​WTφ(Xi​)=i=1∑n​αi​yi​[j=1∑n​αj​yj​φ(Xj​)]Tφ(Xi​)                                           ①=i=1∑n​αi​yi​[j=1∑n​αj​yj​φ(Xj​)T]φ(Xi​)            ②=i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xj​)Tφ(Xi​)              ③=i=1∑n​j=1∑n​αi​αj​yi​yj​φ(Xi​)Tφ(Xj​)               ④③⇒④：调换i和j。相当于双重for循环，循环变量先为i还是先为j，都是一样的。
(46) ⇒ \rArr ⇒(47)：因为已经将式(37)—(39)全部代入式(31)了，因此可以去掉 inf ⁡ W , b , Δ \inf\limits_{W,b,\Delta} W,b,Δinf​了。实际上式（46）中也已经没有了 W , b , Δ W,b,\Delta W,b,Δ；
(47) ⇒ \rArr ⇒(48)：因为核函数 K ( X 1 , X 2 ) = φ ( X 1 ) T φ ( X 2 ) K(X_1, X_2)=\varphi(X_1)^T\varphi(X_2) K(X1​,X2​)=φ(X1​)Tφ(X2​)。

综上所述【终于看到这亲切的四个字了！】，将支持向量机的优化问题转化成对偶问题如下：
最 大 化 ：    θ ( A ) = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( X i , X j )                   ( 49 ) 限 制 条 件 ：    ( 1 )   0 ⩽ α i ⩽ c ,      i = 1 ∼ n                                                      ( 50 ) ( 2 )   ∑ i = 1 n α i y i = 0 ,      i = 1 ∼ n                             ( 51 ) 最大化：~~\theta(\Alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(X_i,X_j)~~~~~~~~~~~~~~~~~(49)\\ 限制条件：~~(1)~0\leqslant\alpha_i\leqslant c,~~~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(50)\\ (2)~\sum_{i=1}^n\alpha_iy_i=0,~~~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~~~~~(51) 最大化：  θ(A)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​K(Xi​,Xj​)                 (49)限制条件：  (1) 0⩽αi​⩽c,    i=1∼n                                                    (50)(2) i=1∑n​αi​yi​=0,    i=1∼n                           (51)

式（49）中 θ ( A , B ) \theta(\Alpha,\Beta) θ(A,B)可以写成 θ ( A ) \theta(\Alpha) θ(A)是因为，支持向量机优化问题原问题中不存在等式形式的限制条件，即不存在变量 B \Beta B；
式（50）是综合式(32)、(33)、(38)所得；
式（51）来源于式（39）。
在上述对偶问题中， α i 、 α j \alpha_i、\alpha_j αi​、αj​是待求变量， y i 、 y j 、 X i 、 X j , n y_i、y_j、X_i、X_j,n yi​、yj​、Xi​、Xj​,n是已知的。其中 y i 、 y j y_i、y_j yi​、yj​是训练样本的标签， X i 、 X j X_i、X_j Xi​、Xj​是训练样本， n n n是训练样本数量。 c c c是算法的超参数，需要人为事先设定。 K K K为核函数，需要人为事先设定。
该问题也是一个典型的凸优化问题，同样可以使用SMO算法求解。

5.3 核函数戏法（Kernel Trick）

回顾我们的目标是什么？对于任意一个测试样本 X t X_t Xt​，需要知道其属于哪一类，即需要知道 W T φ ( X t ) + b W^T\varphi(X_t)+b WTφ(Xt​)+b的值大于或等于0还是小于0。
W T φ ( X t ) + b = ∑ i = 1 n α i y i φ ( X i ) T φ ( X t ) + b            ( 52 )                       = ∑ i = 1 n α i y i K ( X i , X t ) + b               ( 53 ) W^T\varphi(X_t)+b=\sum_{i=1}^n\alpha_iy_i\varphi(X_i)^T\varphi(X_t)+b~~~~~~~~~~(52)\\ ~~~~~~~~~~~~~~~~~~~~~=\sum_{i=1}^n\alpha_iy_iK(X_i,X_t)+b~~~~~~~~~~~~~(53) WTφ(Xt​)+b=i=1∑n​αi​yi​φ(Xi​)Tφ(Xt​)+b          (52)                     =i=1∑n​αi​yi​K(Xi​,Xt​)+b             (53)

(52)：据式(37)， W = ∑ i = 1 n α i y i φ ( X i ) W=\sum_{i=1}^n\alpha_iy_i\varphi(X_i) W=∑i=1n​αi​yi​φ(Xi​)，代入可得式（52）；
α i \alpha_i αi​：根据式(49)—(51)所述对偶问题，只需知道核函数 K K K，即可使用SMO算法求解该凸优化问题，从而得到所有 α i    ( i = 1 ∼ n ) \alpha_i~~(i=1\sim n) αi​  (i=1∼n)。

至此，只剩下最后一个问题：如何求 b b b？
因 为 ， W = ∑ i = 1 n α i y i φ ( X i ) 所 以 ， W T φ ( X i ) = [ ∑ j = 1 n α j y j φ ( X j ) ] T φ ( X i ) = ∑ j = 1 n α j y j φ ( X j ) T φ ( X i ) 又 因 为 ， φ ( X j ) T φ ( X i ) = K ( X j , X i ) 所 以 ， W T φ ( X i ) = ∑ j = 1 n α j y j K ( X j , X i ) 可 知 ， 支 持 向 量 机 优 化 问 题 的 对 偶 问 题 满 足 3.2.2 所 述 强 对 偶 定 理 要 求 ， 因 此 根 据 3.2.3 所 述 K K T 条 件 有 ： { α i [ 1 + δ i − y i W T φ ( X i ) − y i b ] = 0 β i δ i = 0    ⇒    ( c − α i ) δ i = 0 对 于 所 有 α i ≠ 0 且 α i ≠ c ， 根 据 K K T 条 件 ， 必 有 ： { 1 + δ i − y i W T φ ( X i ) − y i b = 0 δ i = 0 即 ， 1 − y i W T φ ( X i ) − y i b = 0 即 ， 1 − ∑ j = 1 n α j y i y j K ( X j , X i ) − y i b = 0 所 以 只 需 找 一 个 α i    ( 0 < α i < c ) ， 取 该 α i 对 应 的 X i 和 y i ，                                      则 b = 1 − ∑ j = 1 n α j y i y j K ( X j , X i ) y i                                        ( 54 ) 因为，W=\sum_{i=1}^n\alpha_iy_i\varphi(X_i)\\ 所以，W^T\varphi(X_i)=[\sum_{j=1}^n\alpha_jy_j\varphi(X_j)]^T\varphi(X_i)=\sum_{j=1}^n\alpha_jy_j\varphi(X_j)^T\varphi(X_i)\\ 又因为，\varphi(X_j)^T\varphi(X_i)=K(X_j,X_i)\\ 所以，W^T\varphi(X_i)=\sum_{j=1}^n\alpha_jy_jK(X_j,X_i)\\ 可知，支持向量机优化问题的对偶问题满足3.2.2所述强对偶定理要求，\\ 因此根据3.2.3所述KKT条件有：\\ \begin{cases} \alpha_i[1+\delta_i-y_iW^T\varphi(X_i)-y_ib]=0\\ \beta_i\delta_i=0~~\rArr~~(c-\alpha_i)\delta_i=0 \end{cases}\\ 对于所有\alpha_i\not=0且\alpha_i\not=c，根据KKT条件，必有：\\ \begin{cases} 1+\delta_i-y_iW^T\varphi(X_i)-y_ib=0\\ \delta_i=0 \end{cases}\\ 即，1-y_iW^T\varphi(X_i)-y_ib=0\\ 即，1-\sum_{j=1}^n\alpha_jy_iy_jK(X_j,X_i)-y_ib=0\\ 所以只需找一个\alpha_i~~(0<\alpha_i<c)，取该\alpha_i对应的X_i和y_i，\\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~则b=\frac{1-\sum_{j=1}^n\alpha_jy_iy_jK(X_j,X_i)}{y_i}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(54) 因为，W=i=1∑n​αi​yi​φ(Xi​)所以，WTφ(Xi​)=[j=1∑n​αj​yj​φ(Xj​)]Tφ(Xi​)=j=1∑n​αj​yj​φ(Xj​)Tφ(Xi​)又因为，φ(Xj​)Tφ(Xi​)=K(Xj​,Xi​)所以，WTφ(Xi​)=j=1∑n​αj​yj​K(Xj​,Xi​)可知，支持向量机优化问题的对偶问题满足3.2.2所述强对偶定理要求，因此根据3.2.3所述KKT条件有：{αi​[1+δi​−yi​WTφ(Xi​)−yi​b]=0βi​δi​=0  ⇒  (c−αi​)δi​=0​对于所有αi​​=0且αi​​=c，根据KKT条件，必有：{1+δi​−yi​WTφ(Xi​)−yi​b=0δi​=0​即，1−yi​WTφ(Xi​)−yi​b=0即，1−j=1∑n​αj​yi​yj​K(Xj​,Xi​)−yi​b=0所以只需找一个αi​  (0<αi​<c)，取该αi​对应的Xi​和yi​，                                    则b=yi​1−∑j=1n​αj​yi​yj​K(Xj​,Xi​)​                                      (54)
最后，可以得到判别标准如下：
如 果 ∑ i = 1 n α i y i K ( X i , X t ) + b ⩾ 0 ， 那 么 X t ∈ C 1 ； 如 果 ∑ i = 1 n α i y i K ( X i , X t ) + b < 0 ， 那 么 X t ∈ C 2 。 如果\sum_{i=1}^n\alpha_iy_iK(X_i,X_t)+b\geqslant0，那么X_t\in C_1；\\ 如果\sum_{i=1}^n\alpha_iy_iK(X_i,X_t)+b<0，那么X_t\in C_2。 如果i=1∑n​αi​yi​K(Xi​,Xt​)+b⩾0，那么Xt​∈C1​；如果i=1∑n​αi​yi​K(Xi​,Xt​)+b<0，那么Xt​∈C2​。

这种不知道 φ ( X ) \varphi(X) φ(X)，只知道核函数 K ( X 1 , X 2 ) K(X_1,X_2) K(X1​,X2​)也可以算出 W T φ ( X ) + b W^T\varphi(X)+b WTφ(X)+b值的方法被称为“核函数戏法”。

6. 总结支持向量机训练和测试流程

6.1 训练流程

① 输入训练数据 { ( X i , y i ) } ,    i = 1 ∼ n \{(X_i, y_i)\},~~i=1\sim n {(Xi​,yi​)},  i=1∼n，其中 y i y_i yi​是标签， y i = ± 1 y_i=\pm1 yi​=±1；
② 指定超参数的值、核函数 K ( X i , X j ) K(X_i,X_j) K(Xi​,Xj​)的具体形式；
③ 求解如下优化问题，求出所有 α i ,    i = 1 ∼ n \alpha_i,~~i=1\sim n αi​,  i=1∼n：
最 大 化 ：    θ ( A ) = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( X i , X j ) 限 制 条 件 ：    ( 1 )   0 ⩽ α i ⩽ c ,      i = 1 ∼ n                                     ( 2 )   ∑ i = 1 n α i y i = 0 ,      i = 1 ∼ n            最大化：~~\theta(\Alpha)=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(X_i,X_j)\\ 限制条件：~~(1)~0\leqslant\alpha_i\leqslant c,~~~~i=1\sim n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ (2)~\sum_{i=1}^n\alpha_iy_i=0,~~~~i=1\sim n~~~~~~~~~~ 最大化：  θ(A)=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​K(Xi​,Xj​)限制条件：  (1) 0⩽αi​⩽c,    i=1∼n                                   (2) i=1∑n​αi​yi​=0,    i=1∼n          
④ 求出 A \Alpha A，知道了 A \Alpha A的每一个分量 α i \alpha_i αi​之后，通过下式求 b b b：
找 一 个 α i    ( 0 < α i < c ) ， 取 该 α i 对 应 的 X i 和 y i ， b = 1 − ∑ j = 1 n α j y i y j K ( X j , X i ) y i 找一个\alpha_i~~(0<\alpha_i<c)，取该\alpha_i对应的X_i和y_i，\\ b=\frac{1-\sum_{j=1}^n\alpha_jy_iy_jK(X_j,X_i)}{y_i} 找一个αi​  (0<αi​<c)，取该αi​对应的Xi​和yi​，b=yi​1−∑j=1n​αj​yi​yj​K(Xj​,Xi​)​
⑤ 知道了 A \Alpha A的每一个分量 α i \alpha_i αi​和 b b b之后，就完成了支持向量机的训练过程。

6.2 测试流程

① 考察测试数据 X t X_t Xt​，预测其类别 y y y;
② 如果 ∑ i = 1 n α i y i K ( X i , X t ) + b ⩾ 0 \sum_{i=1}^n\alpha_iy_iK(X_i,X_t)+b\geqslant0 ∑i=1n​αi​yi​K(Xi​,Xt​)+b⩾0，则 y = + 1 y=+1 y=+1；
     ~~~~     如果 ∑ i = 1 n α i y i K ( X i , X t ) + b < 0 \sum_{i=1}^n\alpha_iy_iK(X_i,X_t)+b<0 ∑i=1n​αi​yi​K(Xi​,Xt​)+b<0，则 y = − 1 y=-1 y=−1。

7. 后记

万字长文，洋洋洒洒，文不加点，一气呵成！
支持向量机（SVM）详解（二）全文总17319字，详细推导了在非线性可分情况下，支持向量机寻找最优分类决策直线或线性超平面的过程。清晰地展现了支持向量机如何引入松弛变量，放松限制条件，改造目标函数使得在非线性可分情况下，优化问题仍然可解。同时详细推导了支持向量机如何将特征空间由低维映射到高维，将优化问题转化为对偶问题，使用核函数戏法判断测试样本类别的过程。
后续，我将向大家介绍支持向量机各种常用核函数，各种超参数的调整方法，支持向量机求解多分类问题的方法，以及使用支持向量机解决实际问题的经验。
后文：支持向量机（SVM）详解（三）

创作不易，期待点赞、评论、收藏、分享支持鸽鸽（作者）！
如果您觉得鸽鸽特别棒，也可以请鸽鸽喝咖啡 ⇓ \color{red}\Large\Downarrow ⇓，谢谢~

# 机器学习 # 支持向量机 # 算法 # 人工智能
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

数据库范式那些事

简单的说，bc范式是在第三范式的基础上的一种特殊情况，既每个表中只有一个候选键（在一个数据库中每行的值都不相同，则可称为候选键），在上面第三范式的noNf表中可以看出，每一个员工的email都是唯一的（难道两个人用同一个email?数据库范式在数据库设计中的地位一直很暧昧，教科书中对于数据库范式倒是都给出了学术性的定义，但实际应用中范式的应用却不甚乐观，这篇文章会用简单的语言和一个简单的数据库DE

avatar 2048 AI社区
cover

基于SpringAI的在线考试系统-DDD业务领域模块设计思路

avatar 2048 AI社区

CSS AI 编程

AI 技术的飞速发展正在深刻改变开发者的工作方式。在 HTML 网页开发中，我们常常被大量细微却高频的重复操作降低效率。因此，AI 的出现可以改变我们的编程方式与提高效率。AI 对我们来说就是一个可靠的编程助手，给我们提供了实时的建议和解决方案，无论是根据图片生成前端页面、快速修复错误，或者查找关键文档和资源，AI 作为编程助手都能让你事半功倍。

avatar 2048 AI社区