线性对偶算法
为了使SVM可以解决线性不可分问题，需要修改硬间隔最大化，使用软间隔最大化，假设给定一个特征空间上的训练数据集 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={(x1,y1),(x2,y2),…,(xN,yN)} 其中， x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , … , N x_i\in\mathcal{X}=\mathbb{R}^n, y_i\in\mathcal{Y}=\{-1, +1\}, i=1, 2, \dots, N xi∈X=Rn,yi∈Y={−1,+1},i=1,2,…,N，其中 x i x_i xi为第 i i i个特征向量， y i y_i yi为类 x i x_i xi的标记，线性不可分表示某些样本点不能满足函数间隔大于等于1的约束条件，可以引入松弛变量 ξ i \xi_i ξi，使得约束条件变为 y i ( w ⋅ x i + b ) ≥ 1 − ξ i y_i(w\cdot x_i+b)\geq 1-\xi_i yi(w⋅xi+b)≥1−ξi 同时在目标函数中加入惩罚项 ξ i \xi_i ξi，使得目标函数变为 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i \frac{1}{2}\lVert w\rVert^2+C\sum_{i=1}^N\xi_i 21∥w∥2+Ci=1∑Nξi 其中 C > 0 C>0 C>0为惩罚参数，目标函数有两部分，其中 1 2 ∥ w ∥ 2 \frac{1}{2}\lVert w\rVert^2 21∥w∥2表示分离间隔尽可能大， ∑ i = 1 N ξ i \sum_{i=1}^N \xi_i ∑i=1Nξi表示误分类点尽可能少， C C C为两部分之间的调和系数，这种目标函数也x被称为软间隔最大化. 这样线性不可分的线性支持向量机的学习问题变成如下凸二次规划(convex quadratic programming)问题 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 (1) \begin{aligned} &\min_{w, b, \xi}\frac{1}{2}\lVert w\rVert^2+C\sum_{i=1}^N\xi_i\\ &s.t. \begin{cases} y_i(w\cdot x_i+b)\geq 1-\xi_i, i=1, 2, \dots, N\\ \xi_i\geq 0, i=1, 2, \dots, N \end{cases} \end{aligned}\tag{1} w,b,ξmin21∥w∥2+Ci=1∑Nξis.t.{yi(w⋅xi+b)≥1−ξi,i=1,2,…,Nξi≥0,i=1,2,…,N(1) 原问题 ( 1 ) (1) (1)是一个QP问题，所以关于 ( w , b , ξ ) (w, b, \xi) (w,b,ξ)的解是存在的，并且可以证明 w w w的解是唯一的，但是 b b b的解不唯一，设模型最优解为 w ∗ w^* w∗和 b ∗ b^* b∗，可以得到分离超平面 w ∗ x + b ∗ = 0 w^*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)=sign(w∗⋅x+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)=sign(w∗⋅x+b∗) 称为线性支持向量机.
模型 ( 1 ) (1) (1)的对偶问题为 min α 1 2 ∑ i = 1 N ∑ i = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . { ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C \begin{aligned} &\min_\alpha\frac{1}{2}\sum_{i=1}^N\sum_{i=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ &s.t. \begin{cases} \sum\limits_{i=1}^N\alpha_iy_i=0\\ 0\leq \alpha_i\leq C \end{cases} \end{aligned} αmin21i=1∑Ni=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.⎩⎨⎧i=1∑Nαiyi=00≤αi≤C 原问题的拉格朗日函数为 L ( w , b , ξ , α , μ ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i − ∑ i = 1 N α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i = 1 N μ i ξ i L(w, b, \xi, \alpha, \mu)=\frac{1}{2}\lVert w\rVert^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i L(w,b,ξ,α,μ)=21∥w∥2+Ci=1∑Nξi−i=1∑Nαi(yi(w⋅xi+b)−1+ξi)−i=1∑Nμiξi 其中， α i ≥ 0 , μ i ≥ 0 \alpha_i\geq 0, \mu_i\geq 0 αi≥0,μi≥0，由于对偶问题是 max − min \max-\min max−min问题，求出 L ( w , b , ξ , α , μ ) L(w, b, \xi, \alpha, \mu) L(w,b,ξ,α,μ)的一阶条件如下 { ∇ w L = w − ∑ i = 1 N α i y i x 0 ∇ b L = − ∑ i = 1 N α i y i = 0 ∇ ξ i L = C − α i − μ i = 0 \left\{ \begin{aligned} &\nabla_wL=w-\sum_{i=1}^N\alpha_iy_ix_0\\ &\nabla_bL=-\sum_{i=1}^N\alpha_iy_i=0\\ &\nabla_{\xi_i}L=C-\alpha_i-\mu_i=0 \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧∇wL=w−i=1∑Nαiyix0∇bL=−i=1∑Nαiyi=0∇ξiL=C−αi−μi=0 将求出等式带入原目标函数，得到对偶问题. 定理：设 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) \alpha^*=(\alpha_1^*, \alpha_2^*, \dots, \alpha_N^*) α∗=(α1∗,α2∗,…,αN∗)是对偶问题的一个解，如果存在 α ∗ \alpha^* α∗的一个分量 α j ∗ ， 0 < α j ∗ < C \alpha_j^*， 0<\alpha_j^*<C αj∗，0<αj∗<C，则原始问题的解 w ∗ , b ∗ w^*, b^* w∗,b∗可以按以下方程求出 { w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y j − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) (2) \left\{ \begin{aligned} & w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\\ &b^*=y_j-\sum_{i=1}^Ny_i\alpha_i^*(x_i\cdot x_j) \end{aligned} \right.\tag{2} ⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧w∗=i=1∑Nαi∗yixib∗=yj−i=1∑Nyiαi∗(xi⋅xj)(2) 证明：因为原问题是QP问题，解满足KKT条件，即 { ∇ w L = w ∗ − ∑ i = 1 N α i ∗ y i x i = 0 ∇ b L = − ∑ i = 1 N α i ∗ y i = 0 ∇ ξ L = C − α ∗ − μ ∗ = 0 α i ∗ ( y i ( w ∗ ⋅ x i + b ∗ ) − 1 − ξ i ∗ ) = 0 μ i ∗ ξ i ∗ = 0 y i ( w ∗ ⋅ x i + b ∗ ) − 1 + ξ i ∗ ≥ 0 ξ ∗ ≥ 0 α i ∗ ≥ 0 μ i ∗ ≥ 0 , i = 1 , 2 , … , N \left\{ \begin{aligned} &\nabla_wL=w^*-\sum_{i=1}^N\alpha^*_iy_ix_i=0\\ &\nabla_bL=-\sum_{i=1}^N\alpha_i^*y_i=0\\ &\nabla_\xi L=C-\alpha^*-\mu^*=0\\ &\alpha_i^*(y_i(w^*\cdot x_i+b^*)-1-\xi^*_i)=0\\ &\mu_i^*\xi_i^*=0\\ &y_i(w^*\cdot x_i+b^*)-1+\xi_i^*\geq 0\\ &\xi^*\geq 0\\ &\alpha_i^*\geq 0\\ &\mu_i^*\geq 0, i=1, 2, \dots, N \end{aligned} \right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧∇wL=w∗−i=1∑Nαi∗yixi=0∇bL=−i=1∑Nαi∗yi=0∇ξL=C−α∗−μ∗=0αi∗(yi(w∗⋅xi+b∗)−1−ξi∗)=0μi∗ξi∗=0yi(w∗⋅xi+b∗)−1+ξi∗≥0ξ∗≥0αi∗≥0μi∗≥0,i=1,2,…,N 当存在 0 < α j ∗ < C 0<\alpha_j^*<C 0<αj∗<C时，即 μ = C − α ∗ > 0 ⇒ ξ ∗ = 0 \mu=C-\alpha^*>0 \Rightarrow \xi^*=0 μ=C−α∗>0⇒ξ∗=0，由互补松弛条件可以得到 y i ( w ∗ ⋅ x i + b ∗ ) = 1 − ξ i ∗ = 1 y_i(w^*\cdot x_i+b^*)=1-\xi_i^*=1 yi(w∗⋅xi+b∗)=1−ξi∗=1. 所以，分离超平面为 ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ = 0 \sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0 i=1∑Nαi∗yi(x⋅xi)+b∗=0 分类决策函数为 f ( x ) = s g n ( ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ ) f(x)=sgn(\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*) f(x)=sgn(i=1∑Nαi∗yi(x⋅xi)+b∗) 可以得到线性支持向量机算法如下 Input：训练数据集 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=(x1,y1),(x2,y2),…,(xN,yN)，其中 x i ∈ X = R n x_i\in\mathcal{X}=\mathbb{R}^n xi∈X=Rn output：分离超平面和分类决策函数 1.选择惩罚参数 C > 0 C>0 C>0，构造并求解凸二次规划问题 min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . { ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , … , N \begin{aligned} &\min_\alpha \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ &s.t.\begin{cases} \sum\limits_{i=1}^N\alpha_iy_i=0\\ 0\leq \alpha_i\leq C, i=1, 2, \dots, N \end{cases} \end{aligned} αmin21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.⎩⎨⎧i=1∑Nαiyi=00≤αi≤C,i=1,2,…,N 求出最优解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T \alpha^*=(\alpha_1^*, \alpha_2^*, \dots, \alpha_N^*)^T α∗=(α1∗,α2∗,…,αN∗)T 2.计算 w ∗ = ∑ i = 1 N α i ∗ y i x i w^*=\sum\limits_{i=1}^N\alpha_i^*y_ix_i w∗=i=1∑Nαi∗yixi 选择 α ∗ \alpha^* α∗的一个分量 α j ∗ \alpha_j^* αj∗适合条件 0 < α j ∗ < C 0<\alpha_j^*<C 0<αj∗<C，计算 b ∗ = y j − ∑ i = 1 N y i α i ∗ ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^Ny_i\alpha^*_i(x_i\cdot x_j) b∗=yj−i=1∑Nyiαi∗(xi⋅xj) 3.求出分离超平面 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)=sign(w∗⋅x+b∗)
在线性不可分的情况下，对偶问题的解 α ∗ = ( α 1 ∗ , α 2 ∗ , … , α N ∗ ) T \alpha^*=(\alpha_1^*, \alpha_2^*, \dots, \alpha_N^*)^T α∗=(α1∗,α2∗,…,αN∗)T对于 α i ∗ > 0 \alpha_i^*>0 αi∗>0的样本点 ( x i , y i ) (x_i, y_i) (xi,yi)为软间隔的支持向量. 软间隔的支持向量 x i x_i xi或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在误分类一侧
支持向量状态分类结果 α i ∗ < C , ξ i = 0 \alpha_i^*<C, \xi_i=0 αi∗<C,ξi=0支持向量 x i x_i xi恰好在间隔边界上 α i ∗ = C , 0 < ξ i < 1 \alpha_i^*=C,0< \xi_i<1 αi∗=C,0<ξi<1分类正确， x i x_i xi在间隔边界与分离超平面之间 α i ∗ = C , ξ i = 1 \alpha_i^*=C, \xi_i=1 αi∗=C,ξi=1则 x i x_i xi在分离超平面上 α i ∗ = C , ξ i > 1 \alpha_i^*=C,\xi_i>1 αi∗=C,ξi>1则 x i x_i xi位于分离超平面误分一侧统计学习方法 清华大学出版社 李航 第七章 支持向量机 支持向量机习题
