一、SVM简介

支持向量机（suport vector mechine，SVM）主要用于解决二分类问题。这里简单介绍一下线性SVM，希望能对SVM的入门者有所帮助。

SVM是如何对样本对进行分类的呢？假设我们有一组数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\} D={(x1​,y1​),(x2​,y2​),...,(xn​,yn​)}，其中 x i x_i xi​是第 i i i个实例， y i y_i yi​是 x i x_i xi​的分类标签，并且有 y i ∈ { − 1 , 1 } y_i∈\{-1,1\} yi​∈{−1,1}。SVM通过一个超平面 ω ⋅ x + b = 0 \omega·x+b=0 ω⋅x+b=0将不同类别的实例 x i x_i xi​划分开，如下图。

二、分清 几何间隔 与 函数间隔

对于各个实例点，其到超平面的几何间隔为 d i = ∣ w . x i + b ∣ ∣ ∣ w ∣ ∣ = y i ( w ∣ ∣ w ∣ ∣ . x i + b ∣ ∣ w ∣ ∣ ) . . . ( 1 ) d_i=\frac{|w.x_i+b|}{||w||}=y_i(\frac{w}{||w||}.x_i+\frac{b}{||w||}) \ \ ...\ \ (1) di​=∣∣w∣∣∣w.xi​+b∣​=yi​(∣∣w∣∣w​.xi​+∣∣w∣∣b​)...(1)如果你了解平面上点到直线的距离公式，你应该会很快了解这个公式的意义。除了几何间隔，还有一个定义叫做函数间隔，公式为： ( d l ) i = ∣ w . x i + b ∣ = y i ( w . x i + b ) . . . ( 2 ) (d_l)_i=|w.x_i+b|=y_i(w.x_i+b) \ \ ...\ \ (2) (dl​)i​=∣w.xi​+b∣=yi​(w.xi​+b)...(2)

我们定义 d = m i n d i d=min \ d_i d=mindi​， d l = m i n ( d l ) i d_l=min (d_l)_i dl​=min(dl​)i​，不难得出， d l d_l dl​与 d d d的关系为 d l = d ⋅ ∣ ∣ w ∣ ∣ . . . ( 3 ) d_l=d·||w|| \ \ ...\ \ (3) dl​=d⋅∣∣w∣∣...(3)

三、我们希望优化什么？

我们希望优化 d d d，使得d最大。相比于所有实例点距离超平面很近，我们希望更希望这些点距离超平面很远，因为这样会使我们更确信这个超平面能够将两种类别的实例分开。

仅仅优化 d d d就足够了吗？不够，我们不希望 y i ( w ∣ ∣ w ∣ ∣ . x i + b ∣ ∣ w ∣ ∣ ) y_i(\frac{w}{||w||}.x_i+\frac{b}{||w||}) yi​(∣∣w∣∣w​.xi​+∣∣w∣∣b​)小于d，因此我们还需要加上 y i ( w ∣ ∣ w ∣ ∣ . x i + b ∣ ∣ w ∣ ∣ ) > = d y_i(\frac{w}{||w||}.x_i+\frac{b}{||w||})>=d yi​(∣∣w∣∣w​.xi​+∣∣w∣∣b​)>=d的约束条件。

于是我们得到我们需要优化的目标： m a x d s . t . y i ( w ∣ ∣ w ∣ ∣ . x i + b ∣ ∣ w ∣ ∣ ) > = d max\ \ d \\ s.t. \ \ y_i(\frac{w}{||w||}.x_i+\frac{b}{||w||})>=d maxds.t.yi​(∣∣w∣∣w​.xi​+∣∣w∣∣b​)>=d

将 d d d换成 d l d_l dl​，

m a x d l ∣ ∣ w ∣ ∣ s . t . y i ( w . x i + b ) > = d l max\ \ \frac{d_l}{||w||} \\ s.t. \ \ y_i(w.x_i+b)>=d_l max∣∣w∣∣dl​​s.t.yi​(w.xi​+b)>=dl​

设定函数间隔 d l = 1 d_l=1 dl​=1，并且不影响 d d d，因为根据公式(2)当 d l d_l dl​扩倍n的话， ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣也会扩倍n，则根据公式(3)，有 d = n . d l n . ∣ ∣ w o l d ∣ ∣ = 1 ∣ ∣ w n e w ∣ ∣ d=\frac{n.d_l}{n.||w_{old}||}=\frac{1}{||w_{new}||} d=n.∣∣wold​∣∣n.dl​​=∣∣wnew​∣∣1​。并且 m a x 1 ∣ ∣ w ∣ ∣ max \ \ \frac{1}{||w||} max∣∣w∣∣1​相当于 m i n 1 2 ∣ ∣ w ∣ ∣ 2 min \ \ \frac{1}{2}||w||^2 min21​∣∣w∣∣2。

带约束的优化目标：

m i n 1 2 ∣ ∣ w ∣ ∣ 2 s . t . ( y i ( w . x i + b ) − 1 ) > = 0 min\ \ \frac{1}{2}||w||^2 \\ s.t. \ \ (y_i(w.x_i+b)-1)>=0 min21​∣∣w∣∣2s.t.(yi​(w.xi​+b)−1)>=0

由拉格朗日乘子法，我们得到我们最终优化目标的拉格朗日函数： L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 N a i y i ( w . x i + b ) + ∑ i = 0 N a i . . . ( 4 ) L(w,b,a)=\frac{1}{2}||w||^2-\sum_{i=1}^Na_iy_i(w.x_i+b)+\sum_{i=0}^Na_i \ \ ... \ \ (4) L(w,b,a)=21​∣∣w∣∣2−i=1∑N​ai​yi​(w.xi​+b)+i=0∑N​ai​...(4)

其中 a = ( a 1 , a 2 , . . . , a n ) T a=(a_1,a_2,...,a_n)^T a=(a1​,a2​,...,an​)T是拉格朗日乘子向量，并且 a i > = 0 a_i>=0 ai​>=0。这是原始问题，我们通常将其变换为对偶问题求解。根据拉格朗日对偶性，原始问题的对偶问题为极大极小问题：

m a x a m i n w , b L ( w , b , a ) max_{a}\ min_{w,b}\ \ L(w,b,a) maxa​minw,b​L(w,b,a)

也就是先求 L ( w , b , a ) L(w,b,a) L(w,b,a)对 w , b w,b w,b的极小，再求 L ( w , b , a ) L(w,b,a) L(w,b,a)对 a a a的极大。

第一步， m i n w , b L ( w , b , a ) min_{w,b}\ \ L(w,b,a) minw,b​L(w,b,a)：∇ w L = w − ∑ i = 1 N a i y i x i = 0 . . . ( 5 ) \nabla_w \ L = w-\sum_{i=1}^Na_iy_ix_i=0 \ \ ... \ \ (5) ∇w​L=w−i=1∑N​ai​yi​xi​=0...(5) ∇ b L = − ∑ i = 1 N a i y i = 0 . . . ( 6 ) \nabla_b \ L=-\sum_{i=1}^Na_iy_i=0 \ \ ... \ \ (6) ∇b​L=−i=1∑N​ai​yi​=0...(6)将式(5)、(6)代入式(4)并合并同类项，得：

m i n w , b L ( w , b , a ) = − 1 2 ∑ i = 1 N ∑ j = 1 N a i a j y i y j ( x i . x j ) + ∑ i = 1 N a i min_{w,b}\ \ L(w,b,a)=-\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i.x_j)+\sum_{i=1}^Na_i minw,b​L(w,b,a)=−21​i=1∑N​j=1∑N​ai​aj​yi​yj​(xi​.xj​)+i=1∑N​ai​

第二步，求 m i n w , b L ( w , b , a ) min_{w,b}\ \ L(w,b,a) minw,b​L(w,b,a)对 a a a的极大：m a x a − 1 2 ∑ i = 1 N ∑ j = 1 N a i a j y i y j ( x i . x j ) + ∑ i = 1 N a i . . . ( 7 ) max_a \ \ -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i.x_j)+\sum_{i=1}^Na_i \ \ ... \ \ (7) maxa​−21​i=1∑N​j=1∑N​ai​aj​yi​yj​(xi​.xj​)+i=1∑N​ai​...(7)不要忘记所有的 a i > = 0 a_i>=0 ai​>=0，另外有 ∑ i = 1 N a i y i = 0 \sum_{i=1}^Na_iy_i=0 ∑i=1N​ai​yi​=0的限制条件。除此之外可将式(7)转化为极小的等价式，得到最终的优化问题为：

m i n a 1 2 ∑ i = 1 N ∑ j = 1 N a i a j y i y j ( x i . x j ) − ∑ i = 1 N a i . . . ( 8 ) s . t . ∑ i = 1 N a i y i = 0 . . . ( 9 ) a i > = 0 , i = 1 , 2 , . . . , N . . . ( 10 ) min_a \ \ \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i.x_j)-\sum_{i=1}^Na_i \ \ ... \ \ (8) \\\ s.t. \ \ \ \sum_{i=1}^{N}a_iy_i=0 \ \ ... \ \ (9) \\\ \ \ \ \ a_i>=0, i=1,2,...,N \ \ ... \ \ (10) mina​21​i=1∑N​j=1∑N​ai​aj​yi​yj​(xi​.xj​)−i=1∑N​ai​...(8)s.t.i=1∑N​ai​yi​=0...(9)ai​>=0,i=1,2,...,N...(10)

好了，出现了，式(7)(8)(9)就是线性SVM的优化目标了。

四、支持向量与 a i a_i ai​的关系

我们定义 d = m i n d i d=min \ d_i d=mindi​，并且最终优化 m a x d max\ d maxd 。在线性可分情况下，我们称训练数据集的样本点中与分离超平面最近的样本点的实例为支持向量。这些支持向量会使得约束条件式 y i ( w . x i + b ) − 1 ≥ 0 y_i(w.x_i+b)-1\geq 0 yi​(w.xi​+b)−1≥0的等号成立，即 y i ( w . x i + b ) − 1 = 0 y_i(w.x_i+b)-1=0 yi​(w.xi​+b)−1=0对于 y i = + 1 y_i=+1 yi​=+1的正例点，支持向量在超平面 H 1 : w . x + b = 1 H_1:w.x+b=1 H1​:w.x+b=1上，对于 y i = − 1 y_i=-1 yi​=−1的负例点，支持向量在超平面 H 2 : w . x + b = − 1 H_2:w.x+b=-1 H2​:w.x+b=−1上。

我们希望优化的是 1 2 ∣ ∣ w ∣ ∣ \frac{1}{2}||w|| 21​∣∣w∣∣，因此对于式(4)的其他项，要求当

y i ( w . x i + b ) − 1 > 0 y_i(w.x_i+b)-1>0 yi​(w.xi​+b)−1>0时 a i = 0 a_i=0 ai​=0；当 y i ( w . x i + b ) − 1 = 0 y_i(w.x_i+b)-1=0 yi​(w.xi​+b)−1=0时 a i > 0 a_i>0 ai​>0。

这样就能保证我们优化的是 1 2 ∣ ∣ w ∣ ∣ \frac{1}{2}||w|| 21​∣∣w∣∣。根据以上两个条件，我们知道，支持向量对应的拉格朗日乘子 a i > 0 a_i>0 ai​>0。

因此在决定分离超平面时只有支持向量起作用，所以将该分类模型叫做支持向量机。一般支持向量机的个数很少，所以支持向量机是一种由很少的重要的训练样本决定的算法。

五、解决部分非线性可分问题的线性SVM—软间隔最大化

对于数据集D中大部分样本对是线性可分的，但是存在几个特异点 ( x i , y i ) (x_i,y_i) (xi​,yi​)使得数据集D线性不可分。怎么解决此类问题是本段的关注点。

之前设定 d l = 1 d_l=1 dl​=1是不是有点太直接太生硬了？生硬，也因此 d l = 1 d_l=1 dl​=1被称为硬间隔，在 d l = 1 d_l=1 dl​=1的条件下优化式(4)叫硬间隔最大化。为什么生硬？因为存在的特异点 ( x i , y i ) (x_i,y_i) (xi​,yi​)使得 y i ( w . x i + b ) ≥ 1 y_i(w.x_i+b)\geq 1 yi​(w.xi​+b)≥1的条件无法满足，不仅会使数据集部分数据线性不可分，还会影响SVM的训练。

因此我们希望引进松弛变量 ξ i > = 0 \xi_i>=0 ξi​>=0使得 y i ( w . x i + b ) > = 1 − ξ i y_i(w.x_i+b)>=1- \xi_i yi​(w.xi​+b)>=1−ξi​，另外对每一个松弛变量 ξ i \xi_i ξi​支付一个代价，则 m i n 1 2 ∣ ∣ w ∣ ∣ 2 min\ \ \frac{1}{2}||w||^2 min21​∣∣w∣∣2变成了 m i n 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i min\ \ \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i min21​∣∣w∣∣2+C∑i=1N​ξi​，其中C是惩罚因子。此时的线性支持向量机就可以解决一些线性不可分的问题。

此时解决的优化问题属于软间隔最大化问题，算是成功解决了 d 1 = 1 d_1=1 d1​=1比较生硬的问题。此时的线性支持向量机需要优化如下的目标： m i n 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i s . t . y i ( w . x i + b ) > = 1 − ξ i , ξ i > = 0 min\ \ \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i \\ s.t. \ \ y_i(w.x_i+b)>=1-\xi_i\ ,\xi_i>=0 min21​∣∣w∣∣2+Ci=1∑N​ξi​s.t.yi​(w.xi​+b)>=1−ξi​,ξi​>=0

此原始问题的拉格朗日函数是： L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i − ∑ i = 1 N a i ( y i ( w . x i + b ) − 1 + ξ i ) − ∑ i 1 N u i ξ i . . . ( 11 ) L(w,b,a)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^Na_i(y_i(w.x_i+b)-1+\xi_i)-\sum_{i_1}^Nu_i\xi_i \ \ ... \ \ (11) L(w,b,a)=21​∣∣w∣∣2+Ci=1∑N​ξi​−i=1∑N​ai​(yi​(w.xi​+b)−1+ξi​)−i1​∑N​ui​ξi​...(11)其中 a i > = 0 , u i > = 0 a_i>=0,u_i>=0 ai​>=0,ui​>=0。

同样，对偶问题是拉格朗日函数的极大极小问题，首先求出 L ( w , b , ξ , a , u ) L(w,b,\xi,a,u) L(w,b,ξ,a,u)对 w , b , ξ w,b,\xi w,b,ξ的极小：

∇ w L = w − ∑ i = 1 N a i y i x i = 0 . . . ( 12 ) \nabla_wL=w-\sum_{i=1}^Na_iy_ix_i=0\ \ ...\ \ (12) ∇w​L=w−i=1∑N​ai​yi​xi​=0...(12) ∇ b L = − ∑ i = 1 N a i y i = 0 . . . ( 13 ) \nabla_b L=-\sum_{i=1}^Na_iy_i=0\ \ ... \ \ (13) ∇b​L=−i=1∑N​ai​yi​=0...(13) ∇ ξ i L = C − a i − u i . . . ( 14 ) \nabla_{\xi_i}L=C-a_i-u_i \ \ ... \ \ (14) ∇ξi​​L=C−ai​−ui​...(14)将式(12)(13)(14)代入(11)得：

m i n w , b , ξ L ( w , b , ξ , a , u ) = − 1 2 ∑ i = 1 N ∑ j = 1 N a i a j y i y j ( x i . x j ) + ∑ i = 1 N a i . . . ( 15 ) min_{w,b,\xi}\ \ L(w,b,\xi,a,u)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i.x_j)+\sum_{i=1}^Na_i \ \ ... \ \ (15) minw,b,ξ​L(w,b,ξ,a,u)=−21​i=1∑N​j=1∑N​ai​aj​yi​yj​(xi​.xj​)+i=1∑N​ai​...(15)此时有 C − a i − u i = 0 , a i > = 0 , u i > 0 C-a_i-u_i=0,a_i>=0,u_i>0 C−ai​−ui​=0,ai​>=0,ui​>0，合并这三个式子可得 C ≥ a i ≥ 0 C\geq a_i\geq0 C≥ai​≥0。然后再对式(15)求 a a a的极大值，对偶问题为： m i n a 1 2 ∑ i = 1 N ∑ j = 1 N a i a j y i y j ( x i . x j ) − ∑ i = 1 N a i . . . ( 16 ) s . t . ∑ i = 1 M a i y i = 0 , C ≥ a i ≥ 0 ， i = 1 , 2 , , N . . . ( 17 ) min_a\ \ \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i.x_j)-\sum_{i=1}^Na_i \ \ ...\ \ (16) \\\ s.t.\ \ \ \sum_{i=1}^Ma_iy_i=0,\ \ C\geq a_i\geq0，i=1,2,~,N \ \ ... \ \ (17) mina​21​i=1∑N​j=1∑N​ai​aj​yi​yj​(xi​.xj​)−i=1∑N​ai​...(16)s.t.i=1∑M​ai​yi​=0,C≥ai​≥0，i=1,2,,N...(17)

我们对SVM的求解，也最终变成了对式(16)(17)的求解。

六、对偶问题的求解

无论是式(16)(17)，还是式(8)(9)(10)，其求解也是复杂的。序列最小最优化算法（sequential minimal optimization，SMO）是一个高效且能求得最优界的算法。

关于SMO的介绍请参考：

《支持向量机 三: 序列最小最优化算法—SMO》

七、分离超平面 与 目标决策函数

首先，通过SMO算法我们求得式(16)(17)的最优解 a = ( a 1 ∗ , a 2 ∗ , . . . , a N ∗ ) T a=(a_1^*,a_2^*,...,a_N^*)^T a=(a1∗​,a2∗​,...,aN∗​)T其次，由式(5)我们求得 w ∗ = ∑ i = 1 N a i ∗ y i x i w^*=\sum_{i=1}^Na_i^*y_ix_i w∗=i=1∑N​ai∗​yi​xi​然后，我们从 a ∗ a^* a∗中选择一个分量 a j ∗ a_j^* aj∗​（要求 0 < a j ∗ < C 0< a_j^*< C 0<aj∗​<C，即选择支持向量中的样本点，这也表明 b ∗ b^* b∗不唯一），由支持向量的条件计算 b ∗ = y j − ∑ i = 1 N y i a i ∗ ( x i . x j ) b^*=y_j-\sum_{i=1}^Ny_ia_i^*(x_i.x_j) b∗=yj​−i=1∑N​yi​ai∗​(xi​.xj​)于是，我们求得分离超平面： ∑ i = 1 N a i ∗ y i ( x i ⋅ x ) + b ∗ = 0 \sum_{i=1}^Na_i^*y_i(x_i·x)+b^*=0 i=1∑N​ai∗​yi​(xi​⋅x)+b∗=0还有分类决策函数： f ( x ) = s i g n ( ∑ i = 1 N a i ∗ y i ( x i ⋅ x ) + b ∗ ) f(x)=sign(\sum_{i=1}^Na_i^*y_i(x_i·x)+b^*) f(x)=sign(i=1∑N​ai∗​yi​(xi​⋅x)+b∗)

对非线性支持向量机感兴趣的朋友，欢迎阅读

《支持向量机 二：非线性支持向量机》