支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。
在上面的图中，a和b都可以作为分类超平面，但最优超平面只有一个，最优分类平面使间隔最大化。 那是不是某条直线比其他的更加合适呢? 我们可以凭直觉来定义一条评价直线好坏的标准: 距离样本太近的直线不是最优的，因为这样的直线对噪声敏感度高，泛化性较差。 因此我们的目标是找到一条直线（图中的最优超平面），离所有点的距离最远。 由此， SVM算法的实质是找出一个能够将某个值最大化的超平面，这个值就是超平面离所有训练样本的最小距离。这个最小距离用SVM术语来说叫做间隔(margin) 。
线性可分支持向量机与硬间隔最大化
给定训练样本集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … ( x m , y m ) } , y i ∈ { − 1 , + 1 } D=\{(x_1,y_1),(x_2,y_2),\dots(x_m,y_m)\},y_i\in\{-1,+1\} D = {( x 1 , y 1 ) , ( x 2 , y 2 ) , … ( x m , y m )} , y i ∈ { − 1 , + 1 } D D D
直观上看，应该去找位于两类训练样本“正中间”的划分超平面，即上图红色那个，因为该划分超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比上图中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而红色的超平面受影响最小。换言之，这个超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
在样本空间中，划分超平面可通过如下线性方程来描述：
w T x + b = 0 w^T x+b=0 w T x + b = 0
以及相应的分类决策函数：
f ( x ) = sign ( w T x + b ) f(x)=\mathop{\text{sign}}(w^T x+b) f ( x ) = sign ( w T x + b )
其中 w = ( w 1 ; w 2 ; … ; w d ) w=(w_1;w_2;\dots;w_d) w = ( w 1 ; w 2 ; … ; w d ) b b b w w w b b b ( w , b ) (w,b) ( w , b ) x x x ( w , b ) (w,b) ( w , b ) r = ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ r= \frac{|w^T x+b|}{||w||} r = ∣∣ w ∣∣ ∣ w T x + b ∣ 点到直线距离arrow-up-right 公式 ∣ A x 0 + b y 0 + C ∣ A 2 + B 2 \frac{|Ax_0+by_0+C|}{\sqrt{A^2+B^2}} A 2 + B 2 ∣ A x 0 + b y 0 + C ∣
函数间隔(Functional margin)
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面 w T x + b = 0 w^Tx+b=0 w T x + b = 0 ∣ w T x + b ∣ |w^Tx+b| ∣ w T x + b ∣ x x x w T x + b w^Tx+b w T x + b y y y y ( w T x + b ) y(w^Tx+b) y ( w T x + b )
定义 ：对于给定的训练数据集 T T T ( w , b ) (w,b) ( w , b ) ( w , b ) (w,b) ( w , b ) ( x i , y i ) (x_i,y_i) ( x i , y i ) a = b a = b a = b ( w , b ) (w,b) ( w , b ) T T T T T T ( x i , y i ) (x_i,y_i) ( x i , y i ) γ ^ = min i = 1 , … , N γ ^ i \hat{\gamma} = \mathop{\min}\limits_{i=1,\dots,N}\hat{\gamma}_i γ ^ = i = 1 , … , N min γ ^ i
几何间隔(Geometric margin)
函数间隔可以表示分类预测的正确性及确信度，但是选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变 w w w b b b 2 w 2w 2 w 2 b 2b 2 b w w w ∣ ∣ w ∣ ∣ = 1 ||w||=1 ∣∣ w ∣∣ = 1
下图给出了超平面 ( w , b ) (w,b) ( w , b ) w w w A A A x i x_i x i y i = + 1 y_i=+1 y i = + 1 A A A ( w , b ) (w,b) ( w , b ) A B AB A B γ i \gamma_i γ i
γ i = w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ \gamma_i=\frac{w}{||w||}\cdot x_i+\frac{b}{||w||} γ i = ∣∣ w ∣∣ w ⋅ x i + ∣∣ w ∣∣ b
其中， ∣ ∣ w ∣ ∣ ||w|| ∣∣ w ∣∣ w w w L 2 L_2 L 2 A A A A A A y i = − 1 y_i=-1 y i = − 1
γ i = − ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) \gamma_i=-(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}) γ i = − ( ∣∣ w ∣∣ w ⋅ x i + ∣∣ w ∣∣ b )
一般地，当样本点 ( x i , y i ) (x_i,y_i) ( x i , y i ) ( w , b ) (w,b) ( w , b ) x i x_i x i
γ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) \gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}) γ i = y i ( ∣∣ w ∣∣ w ⋅ x i + ∣∣ w ∣∣ b )
定义 ：对于给定的训练数据集 T T T ( w , b ) (w,b) ( w , b ) ( x i , y i ) (x_i,y_i) ( x i , y i ) γ i = y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) \gamma_i=y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}) γ i = y i ( ∣∣ w ∣∣ w ⋅ x i + ∣∣ w ∣∣ b ) ( w , b ) (w,b) ( w , b ) T T T T T T ( x i , y i ) (x_i,y_i) ( x i , y i ) γ = min i = 1 , … , N γ i \gamma = \mathop{\min}\limits_{i=1,\dots,N}\gamma_i γ = i = 1 , … , N min γ i
超平面 ( w , b ) (w,b) ( w , b ) ( x i , y i ) (x_i,y_i) ( x i , y i ) γ ^ \hat{\gamma} γ ^ γ \gamma γ
γ i = γ ^ i ∣ ∣ w ∣ ∣ → min γ = γ ^ ∣ ∣ w ∣ ∣ \gamma_i = \frac{\hat{\gamma}_i}{||w||} \ \ \mathop{\to}\limits^{\min}\ \ \gamma = \frac{\hat{\gamma}}{||w||} γ i = ∣∣ w ∣∣ γ ^ i → m i n γ = ∣∣ w ∣∣ γ ^
如果 ∣ ∣ w ∣ ∣ = 1 ||w||=1 ∣∣ w ∣∣ = 1 w w w b b b
支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个(等价于感知机)，但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。
如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：
max w , b γ s . t . y i ( w ∣ ∣ w ∣ ∣ ⋅ x i + b ∣ ∣ w ∣ ∣ ) ≥ γ , i = 1 , 2 , … , N \mathop{\max}\limits_{w,b}\gamma \ \ \ s.t. \ y_i(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||})\geq\gamma,\ i=1,2,\dots,N w , b max γ s . t . y i ( ∣∣ w ∣∣ w ⋅ x i + ∣∣ w ∣∣ b ) ≥ γ , i = 1 , 2 , … , N
我们希望最大化超平面 ( w , b ) (w,b) ( w , b ) γ \gamma γ γ \gamma γ
max w , b γ ^ ∣ ∣ w ∣ ∣ s . t . y i ( w ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , … , N \mathop{\max}\limits_{w,b}\frac{\hat{\gamma}}{||w||} \ \ \ s.t. \ y_i(w\cdot x_i+b)\geq\hat{\gamma},\ i=1,2,\dots,N w , b max ∣∣ w ∣∣ γ ^ s . t . y i ( w ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , … , N
函数间隔 γ ^ \hat{\gamma} γ ^ w w w b b b λ w \lambda w λ w λ b \lambda b λb λ γ ^ \lambda \hat{\gamma} λ γ ^ γ ^ = 1 \hat{\gamma} =1 γ ^ = 1 γ ^ = 1 \hat{\gamma} =1 γ ^ = 1 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣ w ∣∣ 1 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 2 1 ∣∣ w ∣ ∣ 2 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣ w ∣∣ 1 ∣ ∣ w ∣ ∣ ||w|| ∣∣ w ∣∣ 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 2 1 ∣∣ w ∣ ∣ 2
min w b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N \mathop{\min}\limits_{wb}\frac{1}{2}||w||^2\ \ \ s.t.\ y_i(w\cdot x+b)\geq1,\ i=1,2,\dots,N w b min 2 1 ∣∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N
所以求解出最优解 w ∗ , b ∗ w^*,\ b^* w ∗ , b ∗
w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*= 0 w ∗ ⋅ x + b ∗ = 0
从而得到分类决策函数
f ( x ) = sign ( w ∗ ⋅ x + b ∗ ) f(x)=\mathop{\text{sign}}(w^*\cdot x+b^*) f ( x ) = sign ( w ∗ ⋅ x + b ∗ )
我们希望求解 m i n w b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N \mathop{min}\limits_{wb}\frac{1}{2}||w||^2\ \ \ s.t.\ y_i(w\cdot x+b)\geq1,\ i=1,2,\dots,N w b min 2 1 ∣∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N α i ≥ 0 \alpha_i\geq0 α i ≥ 0
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 + ∑ i = 1 N α i ( 1 − y i ( w ⋅ x i + b ) ) \mathcal{L}(w,b,\alpha) = \frac{1}{2}||w||^2+\sum\limits_{i=1}^N\alpha_i(1-y_i(w\cdot x_i+b)) L ( w , b , α ) = 2 1 ∣∣ w ∣ ∣ 2 + i = 1 ∑ N α i ( 1 − y i ( w ⋅ x i + b ))
其中 α = ( α 1 ; α 2 ; … ; α N ) \alpha=(\alpha_1;\alpha_2;\dots;\alpha_N) α = ( α 1 ; α 2 ; … ; α N ) L ( w , b , α ) \mathcal{L}(w,b,\alpha) L ( w , b , α ) w w w b b b
w = ∑ i = 1 N α i y i x i w = \sum\limits_{i=1}^N\alpha_iy_ix_i w = i = 1 ∑ N α i y i x i 0 = ∑ i = 1 N α y y i 0 = \sum\limits_{i=1}^N\alpha_yy_i 0 = i = 1 ∑ N α y y i
将 w = ∑ i = 1 N α i y i x i w = \sum\limits_{i=1}^N\alpha_iy_ix_i w = i = 1 ∑ N α i y i x i 0 = ∑ i = 1 N α y y i 0 = \sum\limits_{i=1}^N\alpha_yy_i 0 = i = 1 ∑ N α y y i
min w b 1 2 ∣ ∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N \mathop{\min}\limits_{wb}\frac{1}{2}||w||^2\ \ \ s.t.\ y_i(w\cdot x+b)\geq1,\ i=1,2,\dots,N w b min 2 1 ∣∣ w ∣ ∣ 2 s . t . y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N
max α ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j s . t . ∑ i = 1 N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N \mathop{\max}\limits_{\alpha}\sum\limits_{i=1}^N\alpha_i-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i^Tx_j\ \ \ s.t.\ \sum\limits_{i=1}^N\alpha_iy_i=0,\ \alpha_i\geq0,\ i=1,2,\dots,N α max i = 1 ∑ N α i − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j x i T x j s . t . i = 1 ∑ N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N
解出 α \alpha α w w w b b b
f ( x ) = w ⋅ x + b = ∑ i = 1 N α i y i x i T x + b f(x)=w\cdot x+b = \sum\limits_{i=1}^N\alpha_iy_ix_i^Tx+b f ( x ) = w ⋅ x + b = i = 1 ∑ N α i y i x i T x + b
从对偶问题解出的 α i \alpha_i α i ( x i , y i ) (x_i,y_i) ( x i , y i ) y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N \ y_i(w\cdot x+b)\geq1,\ i=1,2,\dots,N y i ( w ⋅ x + b ) ≥ 1 , i = 1 , 2 , … , N
{ α i ≥ 0 y i f ( x i ) − 1 ≥ 0 α i ( y i f ( x i ) − 1 ) = 0 \begin{cases}\alpha_i\geq0\\ y_if(x_i)-1\geq0\\ \alpha_i(y_if(x_i)-1)=0\end{cases} ⎩ ⎨ ⎧ α i ≥ 0 y i f ( x i ) − 1 ≥ 0 α i ( y i f ( x i ) − 1 ) = 0
于是，对任意训练样本 ( x i , y i ) (x_i,y_i) ( x i , y i ) α i = 0 \alpha_i=0 α i = 0 y i f ( x i ) = 1 y_if(x_i)=1 y i f ( x i ) = 1 α i = 0 \alpha_i=0 α i = 0 f ( x ) = w ⋅ x + b = ∑ i = 1 N α i y i x i T x + b f(x)=w\cdot x+b = \sum\limits_{i=1}^N\alpha_iy_ix_i^Tx+b f ( x ) = w ⋅ x + b = i = 1 ∑ N α i y i x i T x + b f ( x ) f(x) f ( x ) α i > 0 \alpha_i>0 α i > 0 y i f ( x i ) = 1 y_if(x_i)=1 y i f ( x i ) = 1
那么，如何求解 max α ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j s . t . ∑ i = 1 N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N \mathop{\max}\limits_{\alpha}\sum\limits_{i=1}^N\alpha_i-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i^Tx_j\ \ \ s.t.\ \sum\limits_{i=1}^N\alpha_iy_i=0,\ \alpha_i\geq0,\ i=1,2,\dots,N α max i = 1 ∑ N α i − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j x i T x j s . t . i = 1 ∑ N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N
线性可分问题的支持向量机学习方法对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束不能成立。为了扩展到线性不可分问题，就需要修改硬间隔最大化，使其成为软间隔最大化。
线性不可分意味着某些样本点 ( x i , y i ) (x_i,y_i) ( x i , y i ) 1 1 1 ξ i ≥ 0 \xi_i\geq0 ξ i ≥ 0 1 1 1
y i ( w ⋅ x + b ) ≥ 1 − ξ i y_i(w\cdot x+b)\geq1-\xi_i y i ( w ⋅ x + b ) ≥ 1 − ξ i
同时，对每个松弛变量 ξ i \xi_i ξ i ξ i \xi_i ξ i 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 2 1 ∣∣ w ∣ ∣ 2
1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\xi_i 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i
这里， C > 0 C>0 C > 0 C C C C C C 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 2 1 ∣∣ w ∣ ∣ 2 C C C
有了上面的思路，可以和训练数据集线性可分时一样来考虑训练数据集线性不可分时的线性支持向量机学习问题。相应于硬间隔最大化，它成为软间隔最大化。线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题：
min w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i s . t . y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , … , N ξ i ≥ 0 , i = 1 , 2 , … , N \mathop{\min}\limits_{w,b,\xi}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\xi_i\ \ \ s.t.\ y_i(w\cdot x_i+b)\geq1-\xi_i,\ i=1,2,\dots,N\ \ \xi_i\geq0, i=1,2,\dots,N w , b , ξ min 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i s . t . y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , … , N ξ i ≥ 0 , i = 1 , 2 , … , N
问题是一个凸二次规划问题，因而关于 ( w , b , ξ ) (w,b,\xi) ( w , b , ξ ) w w w b b b w ∗ , b ∗ w^*,\ b^* w ∗ , b ∗ w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 w ∗ ⋅ x + b ∗ = 0 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^*\cdot x+b^*) f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ )
优化目标函数可写为
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ℓ 0 / 1 ( y i ( w ⋅ x i + b ) − 1 ) \mathop{\min}\limits_{w,b}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\ell_{0/1}(y_i(w\cdot x_i+b)-1) w , b min 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ℓ 0/1 ( y i ( w ⋅ x i + b ) − 1 )
其中 C > 0 C>0 C > 0 ℓ 0 / 1 \ell_{0/1} ℓ 0/1
ℓ 0 / 1 ( z ) = { 1 , if z < 0 0 , otherwise \ell_{0/1}(z)=\begin{cases}1,\ \text{if}\ z<0\\ 0,\ \text{otherwise}\end{cases} ℓ 0/1 ( z ) = { 1 , if z < 0 0 , otherwise
显然， C C C y i ( w ⋅ x i + b ) ≥ 1 y_i(w\cdot x_i+b)\geq1 y i ( w ⋅ x i + b ) ≥ 1 C C C ℓ 0 / 1 \ell_{0/1} ℓ 0/1 ℓ 0 / 1 \ell_{0/1} ℓ 0/1 ℓ 0 / 1 \ell_{0/1} ℓ 0/1
1、 hinge损失： ℓ h i n g e ( z ) = max ( 0 , 1 − z ) \ell_{hinge}(z)=\max(0,1-z) ℓ hin g e ( z ) = max ( 0 , 1 − z )
2、 指数损失： ℓ exp ( z ) = exp ( − z ) \ell_{\exp}(z)=\exp(-z) ℓ e x p ( z ) = exp ( − z )
3、 对率损失： ℓ log ( z ) = log ( 1 + exp ( − z ) ) \ell_{\log}(z)=\log(1+\exp(-z)) ℓ l o g ( z ) = log ( 1 + exp ( − z ))
每个样本都有一个对应的松弛变量，用以表征该样本不满足约束的程度。但是仍是一个二次规划问题.于是，通过拉格朗日乘子法可得到拉格朗日函数
L ( w , b , α , ξ , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( 1 − ξ i − y i ( w ⋅ x i + b ) ) − ∑ i = 1 N μ i ξ i \mathcal{L}(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\xi_i+\sum\limits_{i=1}^N\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))-\sum\limits_{i=1}^N\mu_i\xi_i L ( w , b , α , ξ , μ ) = 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ξ i + i = 1 ∑ N α i ( 1 − ξ i − y i ( w ⋅ x i + b )) − i = 1 ∑ N μ i ξ i
其中 α i ≥ 0 , μ i ≥ 0 \alpha_i \geq0, \mu_i\geq0 α i ≥ 0 , μ i ≥ 0
令 L ( w , b , α , ξ , μ ) \mathcal{L}(w,b,\alpha,\xi,\mu) L ( w , b , α , ξ , μ ) w , b , ξ i w,b,\xi_i w , b , ξ i
w = ∑ i = 1 N α i y i x i w=\sum\limits_{i=1}^N\alpha_iy_ix_i w = i = 1 ∑ N α i y i x i 0 = ∑ i = 1 N α i y i 0 = \sum\limits_{i=1}^N\alpha_iy_i 0 = i = 1 ∑ N α i y i C = α i + μ i C=\alpha_i+\mu_i C = α i + μ i
将上面三式代入拉格朗日函数即可得对偶问题
max α ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j s . t . ∑ i = 1 N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N \mathop{\max}\limits_{\alpha}\sum\limits_{i=1}^N\alpha_i-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i^Tx_j\ \ \ \ \ s.t.\ \sum\limits_{i=1}^N\alpha_iy_i=0,\ 0\leq\alpha_i\leq C,\ i=1,2,\dots,N α max i = 1 ∑ N α i − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j x i T x j s . t . i = 1 ∑ N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N
可以看出软间隔和硬间隔唯一的差别就在于对偶变量的约束不同：前者是 0 ≤ α i ≤ C 0\leq\alpha_i\leq C 0 ≤ α i ≤ C 0 ≤ α i 0\leq\alpha_i 0 ≤ α i
{ α i ≥ 0 , μ i ≥ 0 y i f ( x i ) − 1 + ξ i ≥ 0 α i ( y i f ( x i ) − 1 + ξ i ) = 0 ξ i ≥ 0 , μ i ξ i = 0 \begin{cases}\alpha_i\geq0,\ \mu_i\geq0\\ y_if(x_i)-1+\xi_i\geq 0\\ \alpha_i(y_if(x_i)-1+\xi_i)=0\\ \xi_i\geq0,\ \mu_i\xi_i=0\end{cases} ⎩ ⎨ ⎧ α i ≥ 0 , μ i ≥ 0 y i f ( x i ) − 1 + ξ i ≥ 0 α i ( y i f ( x i ) − 1 + ξ i ) = 0 ξ i ≥ 0 , μ i ξ i = 0
于是，对任意训练样本( x i , y i ) (x_i,y_i) ( x i , y i ) α i = 0 \alpha_i=0 α i = 0 y i f ( x i ) = 1 − ξ i y_if(x_i)=1-\xi_i y i f ( x i ) = 1 − ξ i C = α i + μ i C=\alpha_i+\mu_i C = α i + μ i
若 α i = 0 \alpha_i=0 α i = 0 f ( x ) f(x) f ( x )
若 α i > 0 \alpha_i>0 α i > 0 y i f ( x i ) = 1 − ξ i y_if(x_i)=1-\xi_i y i f ( x i ) = 1 − ξ i
若 α i < C \alpha_i<C α i < C μ i > 0 \mu_i>0 μ i > 0 ξ i = 0 \xi_i=0 ξ i = 0
若 α i = C \alpha_i=C α i = C μ i = 0 \mu_i=0 μ i = 0 ξ i ≤ 1 \xi_i\leq1 ξ i ≤ 1
若 ξ i > 1 \xi_i>1 ξ i > 1
由此可看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性
对解线性分类问题，线性支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机。本节叙述非线性支持向量机，其主要特点是利用核技巧。
非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。比如下图
非线性问题往往不好求解，所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。用线性分类方法求解非线性分类问题分为两步：
2、然后在新空间里用线性分类学习方法从训练数据中学习分类模型
核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将空间(欧氏空间或离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应特征空间中的超平面模型。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。
比如下面这张图位于第一、二象限内。我们关注红色的门，以及“北京四合院”这几个字下面的紫色的字母。我们把红色的门上的点看成是“+”数据，紫色字母上的点看成是“-”数据，它们的横、纵坐标是两个特征。显然，在这个二维空间内，“+”“-”两类数据不是线性可分的。
我们现在考虑核函数 K ( v 1 , v 2 ) = < v 1 , v 2 > 2 K(v_1,v_2)=<v_1,v_2>^2 K ( v 1 , v 2 ) =< v 1 , v 2 > 2 v 1 = ( x 1 , y 1 ) , v 2 = ( x 2 , y 2 ) v_1=(x_1,y_1),v_2=(x_2,y_2) v 1 = ( x 1 , y 1 ) , v 2 = ( x 2 , y 2 )
这个核函数对应着二维到三维空间的映射，它的表达式是： P ( x , y ) = ( x 2 , 2 x y , y 2 ) P(x,y)=(x^2,\sqrt{2}xy,y^2) P ( x , y ) = ( x 2 , 2 x y , y 2 ) < P ( v 1 ) , P ( v 2 ) > = < ( x 1 2 , 2 x 1 y 1 , y 1 2 ) , ( x 2 2 , 2 x 2 y 2 , y 2 2 ) > <P(v_1),P(v_2)>=<(x_1^2,\sqrt{2}x_1y_1,y_1^2),(x_2^2,\sqrt{2}x_2y_2,y_2^2)> < P ( v 1 ) , P ( v 2 ) >=< ( x 1 2 , 2 x 1 y 1 , y 1 2 ) , ( x 2 2 , 2 x 2 y 2 , y 2 2 ) >
= x 1 2 x 2 2 + 2 x 1 x 2 y 1 y 2 + y 1 2 y 2 2 = ( x 1 x 2 + y 1 y 2 ) 2 = < v 1 , v 2 > 2 = K ( v 1 , v 2 ) =x_1^2x_2^2+2x_1x_2y_1y_2+y_1^2y_2^2=(x_1x_2+y_1y_2)^2 = <v_1,v_2>^2=K(v_1,v_2) = x 1 2 x 2 2 + 2 x 1 x 2 y 1 y 2 + y 1 2 y 2 2 = ( x 1 x 2 + y 1 y 2 ) 2 =< v 1 , v 2 > 2 = K ( v 1 , v 2 )
在P这个映射下，原来二维空间中的图在三维空间中的像是这个样子：
注意到绿色的平面可以完美地分割红色和紫色，也就是说，两类数据在三维空间中变成线性可分的了。
而三维中的这个判决边界，再映射回二维空间中是这样的：
这是一条双曲线，它不是线性的。核函数的作用就是隐含着一个从低维空间到高维空间的映射，而这个映射可以把低维空间中线性不可分的两类点变成线性可分的。它们映射到的高维空间的维数也比例子（三维）高得多，甚至是无穷维的。这样，就可以期待原来并不线性可分的两类点变成线性可分的了。
在机器学习中常用的核函数，一般有这么几类，也就是LibSVM中自带的这几类：
1) 线性：
上面的例子是 2)多项式核函数中
我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中的内积 x i ⋅ x j x_i\cdot x_j x i ⋅ x j K ( x i , x j ) = ϕ ( x i ) ⋅ ϕ ( x j ) K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j) K ( x i , x j ) = ϕ ( x i ) ⋅ ϕ ( x j )
W ( α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i W(\alpha)=\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum\limits_{i=1}^N\alpha_i W ( α ) = 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j K ( x i , x j ) − i = 1 ∑ N α i
同样，分类决策函数中的内积也可以用核函数代替，而分类决策函数式成为
f ( x ) = sign ( ∑ i = 1 N α i ∗ y i ϕ ( x i ) ⋅ ϕ ( x ) + b ∗ ) = sign ( ∑ i = 1 N α i ∗ y i K ( x i , x ) + b ∗ ) f(x)=\mathop{\text{sign}}(\sum\limits_{i=1}^N\alpha^*_iy_i\phi(x_i)\cdot\phi(x)+b^*)=\mathop{\text{sign}}(\sum\limits_{i=1}^N\alpha^*_iy_iK(x_i,x)+b^*) f ( x ) = sign ( i = 1 ∑ N α i ∗ y i ϕ ( x i ) ⋅ ϕ ( x ) + b ∗ ) = sign ( i = 1 ∑ N α i ∗ y i K ( x i , x ) + b ∗ )
这等价于经过映射函数 ϕ \phi ϕ x i ⋅ x j x_i\cdot x_j x i ⋅ x j ϕ ( x i ) ϕ ( x j ) \phi(x_i)\phi(x_j) ϕ ( x i ) ϕ ( x j )
也就是说，在核函数 K ( x , z ) K(x,z) K ( x , z )
如上所述，利用核技巧，可以将线性分类的学习方法应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机对偶形式中的内积换成核函数。
从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划，学习得到的分类决策函数
f ( x ) = sign ( ∑ i = 1 N α i ∗ y i K ( x , x i ) + b ∗ ) f(x)=\mathop{\text{sign}}(\sum\limits_{i=1}^N\alpha^*_iy_iK(x,x_i)+b^*) f ( x ) = sign ( i = 1 ∑ N α i ∗ y i K ( x , x i ) + b ∗ )
称为非线性支持向量， K ( x , z ) K(x,z) K ( x , z )
具体算法如下
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} T = {( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N )} x i ∈ X = R n x_i\in \mathcal{X}=R^n x i ∈ X = R n y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , … , N y_i\in \mathcal{Y}=\{-1,+1\},i=1,2,\dots,N y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , … , N
(1) 选取适当的核函数 K ( x , z ) K(x,z) K ( x , z ) C C C
min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x , z ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N \mathop{\min}\limits_\alpha\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jK(x,z)-\sum\limits_{i=1}^N\alpha_i\ \ \ \ s.t.\ \sum\limits_{i=1}^N\alpha_iy_i=0,\ 0\leq\alpha_i\leq C,\ i=1,2,\dots,N α min 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j K ( x , z ) − i = 1 ∑ N α i s . t . i = 1 ∑ N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N
得到最优解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T \alpha^*=(\alpha^*_1,\alpha^*_2,\dots,\alpha^*_N)^T α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T
(2) 选择 α ∗ \alpha^* α ∗ 0 < α j ∗ < C 0<\alpha_j^*<C 0 < α j ∗ < C
b ∗ = y j − ∑ i = 1 N α i ∗ y i K ( x i , x j ) b^*=y_j-\sum\limits_{i=1}^N\alpha_i^*y_iK(x_i,x_j) b ∗ = y j − i = 1 ∑ N α i ∗ y i K ( x i , x j )
f ( x ) = sign ( ∑ i = 1 N α i ∗ y i K ( x ⋅ x i ) + b ∗ ) f(x)=\mathop{\text{sign}}(\sum\limits_{i=1}^N\alpha_i^*y_iK(x\cdot x_i)+b^*) f ( x ) = sign ( i = 1 ∑ N α i ∗ y i K ( x ⋅ x i ) + b ∗ )
支持向量机的学习问题可以形式化求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。序列最小最优化算法(Sequential Minimal Optimization, SMO)为高效地实现支持向量机学习提供一个解决途径。
SMO算法要解如下凸二次规划的对偶问题：
min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N \mathop{\min}\limits_\alpha\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum\limits_{i=1}^N\alpha_i\ \ \ s.t.\ \sum\limits_{i=1}^N\alpha_iy_i=0,\ 0\leq\alpha_i\leq C,\ i=1,2,\dots,N α min 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j K ( x i , x j ) − i = 1 ∑ N α i s . t . i = 1 ∑ N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , … , N
在这个问题中，变量是拉格朗日乘子，一个变量 α i \alpha_i α i ( x i , y i ) (x_i,y_i) ( x i , y i ) N N N
SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解成子问题并对子问题求解，进而达到求解原问题的目的。
注意，子问题的两个变量中只有一个是自由变量。假设 α 1 , α 2 \alpha_1,\alpha_2 α 1 , α 2 α 3 , α 4 , … , α N \alpha_3,\alpha_4,\dots,\alpha_N α 3 , α 4 , … , α N ∑ i = 1 N α i y i = 0 \sum\limits_{i=1}^N\alpha_iy_i=0 i = 1 ∑ N α i y i = 0
α 1 = − y i ∑ i = 2 N α i y i \alpha_1=-y_i\sum\limits_{i=2}^N\alpha_iy_i α 1 = − y i i = 2 ∑ N α i y i
如果 α 2 \alpha_2 α 2 α 1 \alpha_1 α 1
整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。
SMO算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑 α i , α j \alpha_i,\alpha_j α i , α j ∑ i = 1 N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N \sum\limits_{i=1}^N\alpha_iy_i=0,\ \alpha_i\geq0,i=1,2,\dots,N i = 1 ∑ N α i y i = 0 , α i ≥ 0 , i = 1 , 2 , … , N
α i y i + α j y j + ∑ k ≠ i , j α k y k = 0 , α i ≥ 0 , α j ≥ 0 \alpha_iy_i+\alpha_jy_j+\sum\limits_{k\neq i,j}\alpha_ky_k=0,\ \alpha_i\geq0,\alpha_j\geq0 α i y i + α j y j + k = i , j ∑ α k y k = 0 , α i ≥ 0 , α j ≥ 0
设 c = − ∑ k ≠ i , j α k y k c = -\sum\limits_{k\neq i,j}\alpha_ky_k c = − k = i , j ∑ α k y k
α i y i + α j y j = c \alpha_iy_i+\alpha_jy_j=c α i y i + α j y j = c
代入对偶问题 max α ∑ i = 1 N α i − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j \mathop{\max}\limits_{\alpha}\sum\limits_{i=1}^N\alpha_i-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N\alpha_i\alpha_jy_iy_jx_i^Tx_j α max i = 1 ∑ N α i − 2 1 i = 1 ∑ N j = 1 ∑ N α i α j y i y j x i T x j α j \alpha_j α j α i \alpha_i α i α i ≥ 0 \alpha_i\geq0 α i ≥ 0 α i , α j \alpha_i,\alpha_j α i , α j
如何确定偏移项 b b b ( x s , y s ) (x_s,y_s) ( x s , y s ) y s f ( x s ) = 1 y_sf(x_s)=1 y s f ( x s ) = 1
y s ( ∑ i ∈ S α i y i x i T x s + b ) = 1 y_s(\sum\limits_{i\in S}\alpha_iy_ix_i^Tx_s+b)=1 y s ( i ∈ S ∑ α i y i x i T x s + b ) = 1
其中 S = { i ∣ α i > 0 , i = 1 , 2 , … , N } S=\{i|\alpha_i>0,i=1,2,\dots,N\} S = { i ∣ α i > 0 , i = 1 , 2 , … , N } b b b
b = 1 ∣ S ∣ ∑ s ∈ S ( 1 y s − ∑ s ∈ S α i y i x i T x s ) b=\frac{1}{|S|}\sum\limits_{s\in S}(\frac{1}{y_s}-\sum\limits_{s\in S}\alpha_iy_ix^T_ix_s) b = ∣ S ∣ 1 s ∈ S ∑ ( y s 1 − s ∈ S ∑ α i y i x i T x s )
注意到只需选取的 α 1 , α 2 \alpha_1,\alpha_2 α 1 , α 2
传统回归模型通常直接基于模型输出 f ( x ) f(x) f ( x ) y y y f ( x ) f(x) f ( x ) y y y f ( x ) f(x) f ( x ) y y y ϵ \epsilon ϵ f ( x ) f(x) f ( x ) y y y ϵ \epsilon ϵ f ( x ) f(x) f ( x ) 2 ϵ 2\epsilon 2 ϵ
于是，SVR问题可形式化为
min w , b 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ℓ ϵ ( f ( x i ) − y i ) \mathop{\min}\limits_{w,b}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N\ell_\epsilon(f(x_i)-y_i) w , b min 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ℓ ϵ ( f ( x i ) − y i )
其中 C C C ℓ ϵ \ell_\epsilon ℓ ϵ
ℓ ϵ ( z ) = { 0 , if ∣ z ∣ ≤ ϵ ∣ z ∣ − ϵ , otherwiae \ell_\epsilon(z)=\begin{cases}0,\ \ \ \ \ \ \ \ \ \ \text{if}\ |z|\leq\epsilon\\ |z|-\epsilon, \ \text{otherwiae}\end{cases} ℓ ϵ ( z ) = { 0 , if ∣ z ∣ ≤ ϵ ∣ z ∣ − ϵ , otherwiae
引入松弛变量 ξ i \xi_i ξ i ξ ^ i \hat{\xi}_i ξ ^ i
min w , b , ξ i , ξ ^ i 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ( ξ i + ξ ^ i ) \mathop{\min}\limits_{w,b,\xi_i,\hat{\xi}_i}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N(\xi_i+\hat{\xi}_i) w , b , ξ i , ξ ^ i min 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ( ξ i + ξ ^ i )
s . t . f ( x i ) − y i ≤ ϵ + ξ i , y i − f ( x i ) ≤ ϵ + ξ ^ i , ξ i ≥ 0 , ξ ^ i ≥ 0 , i = 1 , 2 , … , N s.t.\ f(x_i)-y_i\leq\epsilon+\xi_i,\ \ \ \ y_i-f(x_i)\leq\epsilon+\hat{\xi}_i,\ \ \ \ \xi_i\geq0,\ \hat{\xi}_i\geq0,\ i=1,2,\dots,N s . t . f ( x i ) − y i ≤ ϵ + ξ i , y i − f ( x i ) ≤ ϵ + ξ ^ i , ξ i ≥ 0 , ξ ^ i ≥ 0 , i = 1 , 2 , … , N
引入拉格朗日乘子 μ i ≥ 0 , μ ^ i ≥ 0 , α i ≥ 0 , α ^ i ≥ 0 \mu_i\geq0, \hat{\mu}_i\geq0,\ \alpha_i\geq0,\ \hat{\alpha}_i\geq0 μ i ≥ 0 , μ ^ i ≥ 0 , α i ≥ 0 , α ^ i ≥ 0
L ( w , b , α , α ^ , ξ , ξ ^ , μ , μ ^ ) \mathcal{L}(w,b,\alpha,\hat{\alpha},\xi,\hat{\xi},\mu,\hat{\mu}) L ( w , b , α , α ^ , ξ , ξ ^ , μ , μ ^ )
= 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ( ξ i + ξ ^ i ) − ∑ i = 1 N μ i ξ i − ∑ i = 1 N μ ^ i ξ ^ i =\frac{1}{2}||w||^2+C\sum\limits_{i=1}^N(\xi_i+\hat{\xi}_i)-\sum\limits_{i=1}^N\mu_i\xi_i-\sum\limits_{i=1}^N\hat{\mu}_i\hat{\xi}_i = 2 1 ∣∣ w ∣ ∣ 2 + C i = 1 ∑ N ( ξ i + ξ ^ i ) − i = 1 ∑ N μ i ξ i − i = 1 ∑ N μ ^ i ξ ^ i
+ ∑ i = 1 N α i ( f ( x i ) − y i − ϵ − ξ i ) + ∑ i = 1 N α ^ i ( y i − f ( x i ) − ϵ − ξ ^ i ) +\sum\limits_{i=1}^N\alpha_i(f(x_i)-y_i-\epsilon-\xi_i)+\sum\limits_{i=1}^N\hat{\alpha}_i(y_i-f(x_i)-\epsilon-\hat{\xi}_i) + i = 1 ∑ N α i ( f ( x i ) − y i − ϵ − ξ i ) + i = 1 ∑ N α ^ i ( y i − f ( x i ) − ϵ − ξ ^ i )
将 f ( x ) = w ⋅ x + b f(x)=w\cdot x+b f ( x ) = w ⋅ x + b L ( w , b , α , α ^ , ξ , ξ ^ , μ , μ ^ ) \mathcal{L}(w,b,\alpha,\hat{\alpha},\xi,\hat{\xi},\mu,\hat{\mu}) L ( w , b , α , α ^ , ξ , ξ ^ , μ , μ ^ ) w , b , ξ i , ξ ^ i w,b,\xi_i,\hat{\xi}_i w , b , ξ i , ξ ^ i
w = ∑ i = 1 N ( α ^ i − α i ) x i w = \sum\limits_{i=1}^N(\hat{\alpha}_i-\alpha_i)x_i w = i = 1 ∑ N ( α ^ i − α i ) x i 0 = ∑ i = 1 N ( α ^ i − α i ) 0 = \sum\limits_{i=1}^N(\hat{\alpha}_i-\alpha_i) 0 = i = 1 ∑ N ( α ^ i − α i ) C = α i + μ i C = \alpha_i+\mu_i C = α i + μ i C = α ^ i + μ ^ i C = \hat{\alpha}_i+\hat{\mu}_i C = α ^ i + μ ^ i
代入拉格朗日函数，即可得到SVR的对偶问题
max α , α ^ ∑ i = 1 N y i ( α ^ i − α i ) − ϵ ( α ^ i + α ) − 1 2 ∑ i = 1 N ∑ j = 1 N ( α ^ i − α i ) ( α ^ j − α j ) x i T x j \mathop{\max}\limits_{\alpha,\hat{\alpha}}\sum\limits_{i=1}^Ny_i(\hat{\alpha}_i-\alpha_i)-\epsilon(\hat{\alpha}_i+\alpha)-\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N(\hat{\alpha}_i-\alpha_i)(\hat{\alpha}_j-\alpha_j)x^T_ix_j α , α ^ max i = 1 ∑ N y i ( α ^ i − α i ) − ϵ ( α ^ i + α ) − 2 1 i = 1 ∑ N j = 1 ∑ N ( α ^ i − α i ) ( α ^ j − α j ) x i T x j
s . t . ∑ i = 1 N ( α ^ i − α i ) = 0 , 0 ≤ α i , α ^ i ≤ C s.t.\ \sum\limits_{i=1}^N(\hat{\alpha}_i-\alpha_i)=0,\ \ 0\leq\alpha_i,\hat{\alpha}_i\leq C s . t . i = 1 ∑ N ( α ^ i − α i ) = 0 , 0 ≤ α i , α ^ i ≤ C
上述过程中需满足KKT条件，即要求
{ α i ( f ( x i ) − y i − ϵ − ξ i ) = 0 α ^ i ( y i − f ( x ) − ϵ − ξ ^ i ) = 0 α i α ^ i = 0 , ξ i ξ ^ i = 0 ( C − α i ) ξ i = 0 , ( C − α ^ i ) ξ ^ i = 0 \begin{cases}\alpha_i(f(x_i)-y_i-\epsilon-\xi_i)=0\\ \hat{\alpha}_i(y_i-f(x)-\epsilon-\hat{\xi}_i)=0\\ \alpha_i\hat{\alpha}_i=0,\ \xi_i\hat{\xi}_i=0\\ (C-\alpha_i)\xi_i=0,\ (C-\hat{\alpha}_i)\hat{\xi}_i=0\end{cases} ⎩ ⎨ ⎧ α i ( f ( x i ) − y i − ϵ − ξ i ) = 0 α ^ i ( y i − f ( x ) − ϵ − ξ ^ i ) = 0 α i α ^ i = 0 , ξ i ξ ^ i = 0 ( C − α i ) ξ i = 0 , ( C − α ^ i ) ξ ^ i = 0
可以看出，当且仅当 f ( x i ) − y i − ϵ − ξ i = 0 f(x_i)-y_i-\epsilon-\xi_i=0 f ( x i ) − y i − ϵ − ξ i = 0 α i \alpha_i α i y i − f ( x ) − ϵ − ξ ^ i = 0 y_i-f(x)-\epsilon-\hat{\xi}_i=0 y i − f ( x ) − ϵ − ξ ^ i = 0 α ^ i \hat{\alpha}_i α ^ i ϵ \epsilon ϵ α i \alpha_i α i α ^ i \hat{\alpha}_i α ^ i f ( x ) − y i − ϵ − ξ i = 0 f(x)-y_i-\epsilon-\xi_i=0 f ( x ) − y i − ϵ − ξ i = 0 y i − f ( x ) − ϵ − ξ ^ i = 0 y_i-f(x)-\epsilon-\hat{\xi}_i=0 y i − f ( x ) − ϵ − ξ ^ i = 0 α i \alpha_i α i α ^ i \hat{\alpha}_i α ^ i
f ( x ) = ∑ i = 1 N ( α ^ i − α i ) x i T x + b f(x)=\sum\limits_{i=1}^N(\hat{\alpha}_i-\alpha_i)x^T_ix+b f ( x ) = i = 1 ∑ N ( α ^ i − α i ) x i T x + b
能使上式中的 ( α ^ i − α ) ≠ 0 (\hat{\alpha}_i-\alpha)\neq0 ( α ^ i − α ) = 0 ϵ \epsilon ϵ
由KKT条件可看出，对每个样本都有 ( C − α i ) ξ i = 0 (C-\alpha_i)\xi_i=0 ( C − α i ) ξ i = 0 α i ( f ( x i ) − y i − ϵ − x i i ) = 0 \alpha_i(f(x_i)-y_i-\epsilon-xi_i)=0 α i ( f ( x i ) − y i − ϵ − x i i ) = 0 α i \alpha_i α i 0 < α i < C 0<\alpha_i<C 0 < α i < C ξ i = 0 \xi_i=0 ξ i = 0
b = y i + ϵ − ∑ j = 1 N ( α ^ j − α j ) x j T x i b=y_i+\epsilon-\sum\limits_{j=1}^N(\hat{\alpha}_j-\alpha_j)x^T_jx_i b = y i + ϵ − j = 1 ∑ N ( α ^ j − α j ) x j T x i
因此，在求解式子得到 α i \alpha_i α i 0 < α i < C 0<\alpha_i<C 0 < α i < C b b b 0 < α i < C 0<\alpha_i<C 0 < α i < C b b b
若考虑特征映射形式，则式形如 w = ∑ i = 1 N ( α ^ i − α i ) ϕ ( x i ) w = \sum\limits_{i=1}^N(\hat{\alpha}_i-\alpha_i)\phi(x_i) w = i = 1 ∑ N ( α ^ i − α i ) ϕ ( x i ) f ( x ) = ∑ i = 1 N ( α ^ i − α i ) K ( x , x i ) + b f(x)=\sum\limits{i=1}^N(\hat{\alpha}_i-\alpha_i)K(x,x_i)+b f ( x ) = ∑ i = 1 N ( α ^ i − α i ) K ( x , x i ) + b K ( x i , x j ) = ϕ ( x i ) T ϕ ( x j ) K(x_i,x_j)=\phi(x_i)^T\phi(x_j) K ( x i , x j ) = ϕ ( x i ) T ϕ ( x j )
