机器学习 -支持向量机(2)- 线性 SVM(软间隔最大化)
* 线性 SVM
<https://blog.csdn.net/weixin_37352167/article/details/85563158#_SVM_2>
* 软间隔最大化 <https://blog.csdn.net/weixin_37352167/article/details/85563158#_8>
* 对偶算法 <https://blog.csdn.net/weixin_37352167/article/details/85563158#_36>
* 支持向量 <https://blog.csdn.net/weixin_37352167/article/details/85563158#_105>
*
<>线性 SVM
上一篇文章介绍了在数据线性可分时 SVM
的构建过程,即硬间隔最大化。而当数据线性不可分时,硬间隔最大化是不适用的。(对比与感知器算法,感知器算法在面对线性不可分的数据时是无法收敛的。)
为了解决线性不可分的数据,我们使用软间隔最大化。
*
<>软间隔最大化
线性不可分意味着某些数据样本不满足点到超平面距离大于等于 1 的约束条件,所以我们可以对每一个样本点加入一个松弛变量,使得函数间隔加上松弛变量后大于等于
1,此时对原本就满足约束条件的样本点也没有影响。
则约束条件变为:yi(w⋅xi+b)−1+ξi≥0y_i(w·x_i+b)-1+ξ_i \ge 0yi(w⋅xi+b)−1+ξi≥0
同时对每一个松弛变量 ξiξ_iξi,付出一个代价的 ξiξ_iξi,则目标函数变为:12∣∣w∣∣2+C∑i=1Mξi
\frac{1}{2}||w||^2 + C\sum_{i=1}^{M}ξ_i21∣∣w∣∣2+C∑i=1Mξi
这里 C > 0 称为惩罚参数,一般根据不同的应用场景决定。C 值越大,意味着对误分类的惩罚越大;C
值越小,意味着对误分类的惩罚越小。此时最小化目标函数包含了两层含义:使12∣∣w∣∣2\frac{1}{2}||w||^221∣∣w∣∣2
尽量小即间隔尽量大,同时使误分类点的个数尽量小,C 是调和二者的系数。
那么此时线性 SVM 的学习问题变成如下凸二次规划(Convex quadratic programming)问题:
w,bmax12∣∣w∣∣2+C∑i=1Mξi\mathop{}_{w,b}^{\max}
\frac{1}{2}||w||^2+C\sum_{i=1}^{M}ξ_iw,bmax21∣∣w∣∣2+C∑i=1Mξi
s.t.s.t.s.t. yi(w⋅xi+b)−1≥0,i=1,2,...,My_i(w·x_i+b)-1 \ge 0,i=1,2,...,Myi(w⋅xi
+b)−1≥0,i=1,2,...,M
ξi≥0,i=1,2,...,Mξ_i\ge0,i=1,2,...,Mξi≥0,i=1,2,...,M
解上述约束问题,得最优解 w∗,b∗w^*,b^*w∗,b∗,得到分离超平面 w∗x+b∗=0w^*x+b^*=0w∗x+b∗=0,存在且唯一;
决策函数 f(x)=sign(w∗x+b∗)f(x)=sign(w^*x+b^*)f(x)=sign(w∗x+b∗)
从问题描述中我们可以看出,线性 SVM 是包含之前所讲的线性可分 SVM 的,而且由于现实中数据往往线性不可分,所以线性 SVM 具有更广的适用性。
值得注意的是,在最终的分离超平面以及决策函数中没有 ξξξ 的出现。因为 ξξξ 所对应的样本点是误分类点,即到超平面距离小于 1 的点,它只影响 w∗,b∗
w^*,b^*w∗,b∗ 的值,一旦 w∗,b∗w^*,b^*w∗,b∗ 确定以后,这些点就没有用了。我们需要的仍然只是支持向量。
*
<>对偶算法
线性 SVM 的学习过程与线性可分 SVM 的过程是类似的:
*
构建 拉格朗日函数 <https://blog.csdn.net/weixin_37352167/article/details/84675233>
L(w,b,α,ξ,μ)=12∣∣w∣∣2+C∑i=1Mξi−∑i=1Mαi[yi(w⋅xi+b)−1+ξi]−∑i=1Mμiξi
L(w,b,α,ξ,μ)=\frac{1}{2}||w||^2+C\sum_{i=1}^{M}ξ_i-\sum_{i=1}^{M}α_i[y_i(w·x_i+b)-1+ξ_i]-\sum_{i=1}^{M}μ_iξ_i
L(w,b,α,ξ,μ)=21∣∣w∣∣2+C∑i=1Mξi−∑i=1Mαi[yi(w⋅xi+b)−1+ξi]−∑i=1Mμiξi
*
根据 对偶性,将原始“最小最大”问题转化为“最大最小”问题
<https://blog.csdn.net/weixin_37352167/article/details/84675233>
w,b,ξminαmaxL(w,b,α,ξ,μ)⟹αmaxw,b,ξminL(w,b,α,ξ,μ)
\mathop{}_{w,b,ξ}^{\min}\mathop{}_{α}^{\max} L(w,b,α,ξ,μ) \Longrightarrow
\mathop{}_{α}^{\max}\mathop{}_{w,b,ξ}^{\min} L(w,b,α,ξ,μ)w,b,ξminαmaxL(w,b,α,ξ
,μ)⟹αmaxw,b,ξminL(w,b,α,ξ,μ)
*
对 w,b,ξw,b,ξw,b,ξ 求偏导并令其等于 0
∇wL(w,b,α,ξ,μ)=w−∑i=1Mαiyixi=0\nabla_wL(w,b,α,ξ,μ)=w-\sum_{i=1}^{M}α_iy_ix_i=0∇
wL(w,b,α,ξ,μ)=w−∑i=1Mαiyixi=0
∇bL(w,b,α,ξ,μ)=∑i=1Mαiyi=0\nabla_bL(w,b,α,ξ,μ)=\sum_{i=1}^{M}α_iy_i=0∇bL(w,b,α
,ξ,μ)=∑i=1Mαiyi=0
∇ξL(w,b,α,ξ,μ)=C−αi−μi=0\nabla_ξL(w,b,α,ξ,μ)=C-α_i-μ_i=0∇ξL(w,b,α,ξ,μ)=C−αi−μ
i=0
得
w=∑i=1Mαiyixiw=\sum_{i=1}^{M}α_iy_ix_iw=∑i=1Mαiyixi
∑i=1Mαiyi=0\sum_{i=1}^{M}α_iy_i=0∑i=1Mαiyi=0
C−αi−μi=0C-α_i-μ_i=0C−αi−μi=0
将结果代回,得
w,bminL(w,b,α,ξ,μ)=−12∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)+∑i=1Mαi\mathop{}_{w,b}^{\min}
L(w,b,α,ξ,μ)=-\frac{1}{2}\sum_{i=1}^{M}\sum_{j=1}^{M}α_iα_jy_iy_j(x_i·x_j)+\sum_{i=1}^{M}α_i
w,bminL(w,b,α,ξ,μ)=−21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)+∑i=1Mαi
*
求 w,bminL(w,b,α,ξ,μ)\mathop{}_{w,b}^{\min} L(w,b,α,ξ,μ)w,bminL(w,b,α,ξ,μ) 对 α
αα 的极大 αmaxw,bminL(w,b,α,ξ,μ)\mathop{}_{α}^{\max}\mathop{}_{w,b}^{\min}
L(w,b,α,ξ,μ)αmaxw,bminL(w,b,α,ξ,μ)
添 “负号”将求极大转化为求极小,得到,
αmin12∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi\mathop{}_{α}^{\min}
\frac{1}{2}\sum_{i=1}^{M}\sum_{j=1}^{M}α_iα_jy_iy_j(x_i·x_j)-\sum_{i=1}^{M}α_iα
min21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi
根据 C−αi−μi=0C-α_i-μ_i=0C−αi−μi=0 可将 μiμ_iμi 消去,从而只留下变量 αiα_iαi,所以约束变为
0≤αi≤C0\leα_i\le C0≤αi≤C
最终问题变为
αmin12∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi\mathop{}_{α}^{\min}
\frac{1}{2}\sum_{i=1}^{M}\sum_{j=1}^{M}α_iα_jy_iy_j(x_i·x_j)-\sum_{i=1}^{M}α_iα
min21∑i=1M∑j=1Mαiαjyiyj(xi⋅xj)−∑i=1Mαi
s.t.s.t.s.t. ∑i=1Mαiyi=0\sum_{i=1}^{M}α_iy_i=0∑i=1Mαiyi=0
0≤αi≤C,i=1,2,...,M0\leα_i\le C,i=1,2,...,M0≤αi≤C,i=1,2,...,M
*
求得最优解 α∗=(α1,α2,...,αM)Tα^*=(α_1,α_2,...,α_M)^Tα∗=(α1,α2,...,αM)T,根据 KKT 条件
<https://blog.csdn.net/weixin_37352167/article/details/84675233>,
由此可得到
w∗=∑i=1Mαi∗yixiw^*=\sum_{i=1}^{M}α_i^*y_ix_iw∗=∑i=1Mαi∗yixi
b∗=yj−∑i=1Mαi∗yi(xi⋅xj)b^*=y_j-\sum_{i=1}^{M}α_i^*y_i(x_i·x_j)b∗=yj−∑i=1Mαi∗
yi(xi⋅xj)
*
最终
分离超平面可写成:∑i=1Mαi∗yi(x⋅xj)+b∗=0\sum_{i=1}^{M}α_i^*y_i(x·x_j)+b^*=0∑i=1Mαi∗yi(
x⋅xj)+b∗=0
分类决策函数可写成:f(x)=sign(∑i=1Mαi∗yi(x⋅xj)+b∗)
f(x)=sign(\sum_{i=1}^{M}α_i^*y_i(x·x_j)+b^*)f(x)=sign(∑i=1Mαi∗yi(x⋅xj)+b∗)
*
<>支持向量
在线性不可分的情况下,将对应于 αi∗>0α_i^*>0αi∗>0 的数据样本 xix_ixi 称为支持向量。
在软间隔最大化的情况中,支持向量要比线性可分时的硬间隔最大化复杂一些。
*
分类正确:
若 αi∗<Cα_i^*<Cαi∗<C,则 ξi=0ξ_i=0ξi=0,支持向量恰好落在间隔边界上;
若 αi∗=Cα_i^*=Cαi∗=C,0<ξi<10<ξ_i<10<ξi<1,支持向量在间隔边界与分离超平面之间;
若 αi∗=Cα_i^*=Cαi∗=C,ξi=1ξ_i=1ξi=1,支持向量在分离超平面上;
*
分类错误
若 αi∗=Cα_i^*=Cαi∗=C,ξi>1ξ_i>1ξi>1,支持向量在分离超平面误分类一侧;
热门工具 换一换