机器学习 - 支持向量机（1）- 线性可分 SVM（间隔最大化）

机器学习 -支持向量机（1）- 线性可分 SVM（间隔最大化）

* 线性可分 SVM
<https://blog.csdn.net/weixin_37352167/article/details/85541583#_SVM_2>
* 函数间隔与几何间隔
<https://blog.csdn.net/weixin_37352167/article/details/85541583#_8>
* 几何间隔 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_12>
* 函数间隔 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_20>
* 关系 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_26>
* 硬间隔最大化 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_31>
* 对偶算法 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_73>
* 支持向量 <https://blog.csdn.net/weixin_37352167/article/details/85541583#_136>


*
<>线性可分 SVM

对于线性可分的数据，SVM 与之前讲过的 感知器算法
<https://blog.csdn.net/weixin_37352167/article/details/84838773>
有异曲同工之妙。二者都是通过学得一个超平面以对数据进行分类，都是有解的。只不过 感知器算法有无数个解，而 SVM 只有一个最优解。

下面开始介绍 SVM 的相关内容。

*
<>函数间隔与几何间隔

所谓间隔，在这里是指样本点到超平面的距离，也可以用来表示分类预测的置信度（间隔越大，则分类有更高的置信度，反之同理）。

*
<>几何间隔

几何间隔类似于“点到线的距离”：d=∣w⋅x+b∣∣∣w∣∣d = \frac{| w·x+b |}{||w||}d=∣∣w∣∣∣w⋅x+b∣​，∣∣w∣∣
||w||∣∣w∣∣ 表示 L2 范数。

以此对于样本点 xix_ixi​，定义其到超平面的几何间隔为：ri=yiw⋅xi+b∣∣w∣∣r_i = y_i\frac{w·x_i+b}{||w||}ri
​=yi​∣∣w∣∣w⋅xi​+b​.

rir_iri​ 的正负可表示分类是否正确：yi与w⋅xi+b∣∣w∣∣y_i 与 \frac{w·x_i+b}{||w||}yi​与∣∣w∣∣w⋅xi​+b
​ 同号，则表示分类正确；异号则表示分类错误。

*
<>函数间隔

几何间隔中，我们可用 w⋅x+bw·x+bw⋅x+b 来相对地表示样本点 xix_ixi​ 到超平面的距离以及类别。同样根据符号是否相同来判断分类是否正确。

以此对于样本点 xix_ixi​，定义其到超平面的函数间隔为：ri‾=yi(w⋅xi+b)\overline{r_i} = y_i(w·x_i+b)ri​​=
yi​(w⋅xi​+b).

*
<>关系

若 ∣∣w∣∣=1||w||=1∣∣w∣∣=1，两间隔相等；
若 w,bw,bw,b 成比例改变，函数间隔也按比例改变，而几何间隔不变。

*
<>硬间隔最大化

对于线性可分数据，我们能够得到无穷个分离超平面，但是使得所有样本点到超平面的距离之和最大的超平面是唯一的。


之前说过点到超平面的距离可表示分类的置信度，那么间隔最大的超平面可以以最大的置信度对数据进行分类。也就是说，我们不仅要将正负样本点分开，还要有足够大的把握将他们分开。这样的超平面的泛化能力应当也很好。

*
求几何间隔最大的分离超平面可表示为下面的约束优化问题：

w,bmax⁡r\mathop{}_{w,b}^{\max} rw,bmax​r

s.t.s.t.s.t. yi[w⋅xi+b∣∣w∣∣]≥r,i=1,2,...,My_i[\frac{w·x_i+b}{||w||}] \ge
r,i=1,2,...,Myi​[∣∣w∣∣w⋅xi​+b​]≥r,i=1,2,...,M

*
而几何间隔可用函数间隔表示：r=r‾∣∣w∣∣r=\frac{\overline{r}}{||w||}r=∣∣w∣∣r​，则约束问题改变为：

w,bmax⁡r‾∣∣w∣∣\mathop{}_{w,b}^{\max} \frac{\overline{r}}{||w||}w,bmax​∣∣w∣∣r​

s.t.s.t.s.t. yi(w⋅xi+b)≥r‾,i=1,2,...,My_i(w·x_i+b) \ge \overline{r},i=1,2,...,M
yi​(w⋅xi​+b)≥r,i=1,2,...,M

*
其中 r‾\overline{r}r 的大小对约束问题没有影响（可以在 w,bw,bw,b 中对 r‾\overline{r}r
的变化进行同倍数抵消），所以可取r‾=1\overline{r}=1r=1，得到：

w,bmax⁡1∣∣w∣∣\mathop{}_{w,b}^{\max} \frac{1}{||w||}w,bmax​∣∣w∣∣1​

s.t.s.t.s.t. yi(w⋅xi+b)≥1,i=1,2,...,My_i(w·x_i+b) \ge 1,i=1,2,...,Myi​(w⋅xi​+b)
≥1,i=1,2,...,M

*
又因 最大化1∣∣w∣∣\frac{1}{||w||}∣∣w∣∣1​ 等价于 最小化12∣∣w∣∣2\frac{1}{2}||w||^221​∣∣w∣∣2
，所以最终约束问题转化为：

w,bmax⁡12∣∣w∣∣2\mathop{}_{w,b}^{\max} \frac{1}{2}||w||^2w,bmax​21​∣∣w∣∣2

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

（平方是为了去根号，12\frac{1}{2}21​ 是为了在后续求导中约掉平方）

*
最终

求得最优解 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∗)

*
<>对偶算法

在求解约束问题最优解时，可以应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解
<https://blog.csdn.net/weixin_37352167/article/details/84675233>，更容易求解。

*
构建拉格朗日函数

L(w,b,α)=12∣∣w∣∣2−∑i=1Mαi[yi(w⋅xi+b)−1]
L(w,b,α)=\frac{1}{2}||w||^2-\sum_{i=1}^{M}α_i[y_i(w·x_i+b)-1]L(w,b,α)=21​∣∣w∣∣2−
∑i=1M​αi​[yi​(w⋅xi​+b)−1]

                   =12∣∣w∣∣2−∑i=1Mαiyi(w⋅xi+b)+∑i=1Mαi
=\frac{1}{2}||w||^2-\sum_{i=1}^{M}α_iy_i(w·x_i+b)+\sum_{i=1}^{M}α_i=21​∣∣w∣∣2−∑i
=1M​αi​yi​(w⋅xi​+b)+∑i=1M​αi​

                    αi≥0,i=1,2,...,Mα_i\ge0,i=1,2,...,Mαi​≥0,i=1,2,...,M

*
根据对偶性，将原始“最小最大”问题转化为“最大最小”问题

w,bmin⁡αmax⁡L(w,b,α)⟹αmax⁡w,bmin⁡L(w,b,α)
\mathop{}_{w,b}^{\min}\mathop{}_{α}^{\max} L(w,b,α) \Longrightarrow
\mathop{}_{α}^{\max}\mathop{}_{w,b}^{\min} L(w,b,α)w,bmin​αmax​L(w,b,α)⟹αmax​w,b
min​L(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

得

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

将结果代回，得

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​

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

       αi≥0,i=1,2,...,Mα_i\ge0,i=1,2,...,Mαi​≥0,i=1,2,...,M

*
求 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​

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

       αi≥0,i=1,2,...,Mα_i\ge0,i=1,2,...,Mαi​≥0,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​

又因 yj(w∗xj+b∗)−1=0y_j(w^*x_j+b^*)-1=0yj​(w∗xj​+b∗)−1=0，且注意到 yj2=1y_j^2=1yj2​=1

可得到 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∗)

*
<>支持向量

根据 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
​) 可知，

w∗,b∗w^*,b^*w∗,b∗ 只依赖与训练数据中对应于 αi∗>0α_i^*>0αi∗​>0
的样本点，而其他样本点对它们没有影响，所以我们将训练数据中对应于αi∗>0α_i^*>0αi∗​>0 的样本点 xi∈Rnx_i∈R^nxi​∈Rn
称为支持向量，且w∗xi+b∗=−+1w^*x_i+b^*=\mathop{}_{-}^{+}1w∗xi​+b∗=−+​1，即 xix_ixi​
一定在决策边界上。

• « 上一篇：计算机组成原理期末试题
• » 下一篇：国内测试看Netflix