机器学习:线性支持向量机与软间隔最大化

线性支持向量机

线性可分问题的支持向量机的学习方法,对线性不可分的训练数据是不适用的,因为这时上述方法中的不等式约束不能都成立。为了使其扩展到线性不可分问题,需要将硬间隔最大化修改为软间隔最大化。通常情况是,训练数据中有一些特异点,将这些特异点出去后,剩下大部分样本点组成的集合是线性可分的。
线性不可分以为着这些样本点 ( x i , y i ) (x_i,y_i) (xi,yi)不能满足函数间隔大于一的约束条件。为了解决这个问题,可以对每一个样本点引进一个松弛变量 ξ i > 0 \xi_i >0 ξi>0使函数加上松弛变量大于等于1.这样约束条件变为:
y i ( w ∗ x i + b ) > = 1 − ξ i ( 1 ) y_i(w*x_i+b)>=1-\xi_i (1) yi(wxi+b)>=1ξi1
同时,为每一个松弛变量支付一个代价 ξ i \xi_i ξi
目标函数由 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 21w2变为 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i 21w2+Ci=1Nξi
这里C>0称为惩罚参数,一般由应用问题解决,C值大时对于误分类的惩罚增加,C值小时惩罚减小。式子(1)包含两层含义:使 1 2 ∣ ∣ w ∣ ∣ 2 \frac{1}{2}||w||^2 21w2尽量小即间隔尽量大,同时使误分类点的个数尽量小。C是调和二者的系数。
有了上面的思路,可以和训练集线性可分时一样来考虑训练数据集线性不可分的线性支持向量机学习问题。相应于硬间隔最大化,它成为软间隔最大化。
线性不可分的线性支持向量机的学习问题变为如下的二次凸优化问题:
min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i \min_{w,b,\xi}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i minw,b,ξ21w2+Ci=1Nξi
s . t . y i ( w ∗ x i + b ) > = 1 − ξ i i = 1 , 2 , . . . , N s.t. y_i(w*x_i+b)>=1-\xi_ii=1,2,...,N s.t.yi(wxi+b)>=1ξii=1,2,...,N
ξ i > = 0 , i = 1 , 2 , . . . , N \xi_i>=0,i=1,2,...,N ξi>=0,i=1,2,...,N

线性支持向量机的定义

对于给定线性不可分的训练数据集,通过求解凸二次规划问题,即软件最大化问题,得到的分离超平面为
w ∗ x + b = 0 w*x+b=0 wx+b=0
以及相应的分类决策函数:
f ( x ) = s i g n ( w ∗ x + b ) f(x)=sign(w*x+b) f(x)=sign(wx+b)
称为线性支持向量机

学习的对偶算法

原始问题的对偶问题
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( x i ∗ x j ) − ∑ i = 1 N α i \min_\alpha \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy(x_i*x_j)-\sum_{i=1}^{N}\alpha_i minα21i=1Nj=1Nαiαjyiy(xixj)i=1Nαi
s . t . ∑ i = 1 N a i y i = 0 s.t.\sum_{i=1}^{N}a_iy_i=0 s.t.i=1Naiyi=0
a < = α i < = C , i = 1 , 2 , . . . , N a<=\alpha_i<=C,i=1,2,...,N a<=αi<=C,i=1,2,...,N
原始问题的拉格朗日函数
L ( w , b , ξ , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 N ξ i + ∑ i = 1 N α i ( y i ( w ∗ x + b ) − 1 + ξ i ) − ∑ i = 1 N μ i ξ i L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i+\sum_{i=1}^{N}\alpha_i(y_i(w*x+b)-1+\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i L(w,b,ξ,α,μ)=21w2+Ci=1Nξi+i=1Nαi(yi(wx+b)1+ξi)i=1Nμiξi
α i > = 0 , μ i > = 0 \alpha_i>=0,\mu_i>=0 αi>=0,μi>=0
对偶问题是拉格朗日的极大极小问题。首先求对L函数对 w , b , ξ w,b,\xi w,b,ξ的极小,由
∇ w L = 0 , ∇ b = 0 , ∇ ξ = 0 得 到 \nabla_wL=0,\nabla_b=0,\nabla_\xi=0得到 wL=0,b=0,ξ=0
w = ∑ i = 1 N α i y i x i , ∑ i = 1 N a i y i = 0 , C − α i − μ i = 0 w=\sum_{i=1}^{N}\alpha_iy_ix_i,\sum_{i=1}^{N}a_iy_i=0,C-\alpha_i-\mu_i=0 w=i=1Nαiyixi,i=1Naiyi=0,Cαiμi=0得到
min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ∗ x j ) + ∑ i = 1 N α i \min_{w,b,\xi}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^{N}\alpha_i minw,b,ξL(w,b,ξ,α,μ)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi
在对 min ⁡ w , b , ξ L ( w , b , ξ , α , μ ) \min_{w,b,\xi}L(w,b,\xi,\alpha,\mu) minw,b,ξL(w,b,ξ,α,μ) α \alpha α的极大,即得到对偶问题:
max ⁡ α L ( w , b , ξ , α , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ∗ x j ) + ∑ i = 1 N α i \max_{\alpha}L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^{N}\alpha_i maxαL(w,b,ξ,α,μ)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi
s . t . ∑ i = 1 N α i y i = 0 s.t.\sum_{i=1}^{N}\alpha_iy_i=0 s.t.i=1Nαiyi=0
C − α i − μ i = 0 C-\alpha_i-\mu_i=0 Cαiμi=0
α i > = 0 \alpha_i>=0 αi>=0
μ i > = 0 , i = 1 , 2 , . . . , N \mu_i>=0,i=1,2,...,N μi>=0,i=1,2,...,N
将对偶最优化问题进行变换消去 μ i \mu_i μi只留下 α i \alpha_i αi,并将约束中写成 0 < = α i < = C 0<=\alpha_i<=C 0<=αi<=C
在将目标函数转化为极小,就得到
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( x i ∗ x j ) − ∑ i = 1 N α i \min_\alpha \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy(x_i*x_j)-\sum_{i=1}^{N}\alpha_i minα21i=1Nj=1Nαiαjyiy(xixj)i=1Nαi

线性支持向量机学习算法

输入:训练数据及
输出:分离超平面和决策函数
(1)选择惩罚参数C>0。构造并求解凸二次规划问题
min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y ( x i ∗ x j ) − ∑ i = 1 N α i \min_\alpha \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy(x_i*x_j)-\sum_{i=1}^{N}\alpha_i minα21i=1Nj=1Nαiαjyiy(xixj)i=1Nαi
s . t . ∑ i = 1 N a i y i = 0 s.t.\sum_{i=1}^{N}a_iy_i=0 s.t.i=1Naiyi=0
a < = α i < = C , i = 1 , 2 , . . . , N a<=\alpha_i<=C,i=1,2,...,N a<=αi<=C,i=1,2,...,N
求得最优解 α ∗ = ( a 1 ∗ , a 2 ∗ , . . . , a N ∗ ) T \alpha^*=(a_1^*,a_2^*,...,a_N^*)^T α=(a1,a2,...,aN)T
(2)计算 w ∗ w^* w,选择 α ∗ \alpha^* α的一个分量 α j ∗ \alpha_j^* αj适合条件 0 < α i ∗ < C 的 α j ∗ 0<\alpha_i^*0<αi<Cαj计算 b ∗ b^* b
(3)求得分离超平面和决策函数
步骤(2)中,任意一个适合条件都能求出一个 b ∗ b^* b,但是由于原始问题对b的解并不是唯一,所以实际计算可以取所有的b的平均值。

支持向量

在线性不可分的情况下,将对偶问题的解 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T α=(α1,α2,...,αN)T中对应于 α ∗ > 0 \alpha^*>0 α>0的实例样本点称为支持向量(软间隔的支持向量)。这时的支持向量要比线性可分时的情况复杂一些。实例点 x i x_i xi到间隔边界的距离为 ξ i ∣ ∣ w ∣ ∣ \frac{\xi_i}{||w||} wξi.
软间隔的支持向量 x i x_i xi或者在间隔边界上,或者在间隔边界与分离超平面之间,或者在分离超平面误分一侧。若 α i < C \alpha_iαi<C ξ i = 0 \xi_i=0 ξi=0,支持向量 x i x_i xi恰好在间隔边界上, a i = C , 0 < ξ i < 1 a_i=C,0<\xi_i<1 ai=C0<ξi<1,则分类正确, x i x_i xi在间隔边界与分离超平面之间;若 a i = C a_i=C ai=C ξ i = 1 \xi_i=1 ξi=1 x i x_i xi在分离超平面上,若 a i > C , ξ > 1 a_i>C,\xi>1 ai>C,ξ>1 x i x_i xi位于超平面误分一侧。

合页损失函数

你可能感兴趣的