机器学习 -支持向量机(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,bmax⁡12∣∣w∣∣2+C∑i=1Mξi\mathop{}_{w,b}^{\max}
\frac{1}{2}||w||^2+C\sum_{i=1}^{M}ξ_iw,bmax​21​∣∣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⁡αmax⁡L(w,b,α,ξ,μ)⟹αmax⁡w,b,ξmin⁡L(w,b,α,ξ,μ)
\mathop{}_{w,b,ξ}^{\min}\mathop{}_{α}^{\max} L(w,b,α,ξ,μ) \Longrightarrow
\mathop{}_{α}^{\max}\mathop{}_{w,b,ξ}^{\min} L(w,b,α,ξ,μ)w,b,ξmin​αmax​L(w,b,α,ξ
,μ)⟹αmax​w,b,ξmin​L(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∇
w​L(w,b,α,ξ,μ)=w−∑i=1M​αi​yi​xi​=0

∇bL(w,b,α,ξ,μ)=∑i=1Mαiyi=0\nabla_bL(w,b,α,ξ,μ)=\sum_{i=1}^{M}α_iy_i=0∇b​L(w,b,α
,ξ,μ)=∑i=1M​αi​yi​=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​αi​yi​xi​

∑i=1Mαiyi=0\sum_{i=1}^{M}α_iy_i=0∑i=1M​αi​yi​=0

C−αi−μi=0C-α_i-μ_i=0C−αi​−μi​=0

将结果代回,得

w,bmin⁡L(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,bmin​L(w,b,α,ξ,μ)=−21​∑i=1M​∑j=1M​αi​αj​yi​yj​(xi​⋅xj​)+∑i=1M​αi​

*
求 w,bmin⁡L(w,b,α,ξ,μ)\mathop{}_{w,b}^{\min} L(w,b,α,ξ,μ)w,bmin​L(w,b,α,ξ,μ) 对 α
αα 的极大 αmax⁡w,bmin⁡L(w,b,α,ξ,μ)\mathop{}_{α}^{\max}\mathop{}_{w,b}^{\min}
L(w,b,α,ξ,μ)αmax​w,bmin​L(w,b,α,ξ,μ)

添 “负号”将求极大转化为求极小,得到,

αmin⁡12∑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α
min​21​∑i=1M​∑j=1M​αi​αj​yi​yj​(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

最终问题变为

αmin⁡12∑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α
min​21​∑i=1M​∑j=1M​αi​αj​yi​yj​(xi​⋅xj​)−∑i=1M​αi​

s.t.s.t.s.t. ∑i=1Mαiyi=0\sum_{i=1}^{M}α_iy_i=0∑i=1M​αi​yi​=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∗​yi​xi​

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,支持向量在分离超平面误分类一侧;

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信