牛客网算法八股刷题系列(七)正则化(软间隔SVM再回首)

题目描述

关于支持向量机$(\text{Support Vector Machine,SVM})$，下列说法错误的是$()$

$\mathcal{A}{L}_2$正则项，作用是最大化分类间隔，使得分类器拥有更强的泛化能力

$\mathcal{B}\text{Hinge}$损失函数，作用是最小化经验风险错误

$\mathcal{C}$分类间隔$\begin{array}{r}\frac{1}{||\mathcal{W}||}\end{array}$，其中$||\mathcal{W}||$代表向量的模

$\mathcal{D}{L}_1$正则化对所有参数的惩罚力度都一样，可以让一部分权重变为零，因此产生稀疏模型，能够去除某些特征

正确答案：$\mathcal{C}$

题目解析

开端：关于函数间隔问题解释的补充

该部分对照支持向量机——模型构建思路进行阅读。

这里依然以二分类任务为例。已知数据集合$\mathcal{D}$以集合内的标签集合表示如下：
D={(x(i),y(i))}i=1Ny(i)∈{+1,−1}\mathcal D = \{(x^{(i)},y^{(i)})\}_{i=1}^N \quad y^{(i)} \in \{+1,-1\}D={(x(i),y(i))}i=1N​y(i)∈{+1,−1}

在支持向量机——模型构建思路介绍了分类正确的标志：模型输出结果${\mathcal{W}}^T{x}^{(i)}+b$与对应标签结果$y^{(i)}$同号：
$$\{\begin{array}{l}{\mathcal{W}}^T{x}^{(i)}+b>0y^{(i)}=+1\\ {\mathcal{W}}^T{x}^{(i)}+b<0y^{(i)}=-1\end{array}$$
从而确定模型的决策边界(超平面)：
$${\mathcal{W}}^{T}x+b=0$$
虽然找到了决策边界，但出现了新的问题：决策边界不唯一。我们可以对上述决策边界进行任意缩放 $\Rightarrow$ 等式两侧同时乘以常数$k$，决策边界并不发生影响。
$$k\cdot ({\mathcal{W}}^{T}x+b)=k\cdot 0=0$$
但是对应的函数间隔$(\text{Functional Margin}){\mathcal{H}}^{(i)}=y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)(x^{(i)},y^{(i)}\in \mathcal{D})$发生了变化：
$$\{\begin{array}{l}\text{Original : }{\mathcal{H}}^{(i)}=y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\\ \text{Expand/Reduce : }k\cdot {\mathcal{H}}^{(i)}=y^{(i)}\left[k\cdot ({\mathcal{W}}^T{x}^{(i)}+b)\right]\end{array}$$
不同的决策边界，会导致某个样本点会存在多个函数间隔的判别结果。这意味着：仅通过${\mathcal{W}}^T{x}^{(i)}+b$和$y^{(i)}$同号这个约束，没有办法让模型收敛。通过对函数间隔的描述，可以通过公式对该描述进行表达：
$$\exists \gamma >0\Rightarrow \underset{x^{(i)},y^{(i)}\in \mathcal{D}}{\min }{y}^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)=\underset{x^{(i)},y^{(i)}\mathcal{D}}{\min }{\mathcal{H}}^{(i)}=\gamma$$
为了方便计算，设定$\gamma =1$。也就是说，无论对决策边界扩张还是收缩，都可以通过对$\mathcal{W},b$进行相应的缩放，使得等式成立：

• 由于$\mathcal{W},b$都是向量，缩放变换后的${\mathcal{W}}^{\prime },b^{\prime }$必然和原结果线性相关。并没有影响对权重特征的描述。
• 该部分见《机器学习(周志华著)》P122 左侧小字解释部分
  $$\underset{x^{(i)},y^{(i)}\in \mathcal{D}}{\min }{y}^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)=1\iff y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\ge 1$$

最终可将支持向量机——最大间隔分类器表示为如下基本型：
$$\{\begin{array}{l}\begin{array}{r}\underset{\mathcal{W},b}{\min }\frac{1}{2}||\mathcal{W}|{|}^2\end{array}\\ s.t.y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\ge 1(x^{(i)},y^{(i)})\in \mathcal{D}\end{array}$$

软间隔$\text{SVM}$

该部分对照支持向量机——软间隔$\text{SVM}$进行阅读。

关于软间隔构建损失函数的动机 可描述为：

• 假设损失函数为$\mathcal{L}$，如果某样本被划分正确，那么对应的$\mathcal{L}=0$；
• 相反，如果某样本没有被划分正确，意味着$y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)<1$，那么对应的函数结果为：
  可以看出，该结果是一个$\le 1$的正值。
  $$(x^{(i)},y^{(i)})\Rightarrow {\mathcal{L}}^{(i)}=1-y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)$$

可以看出，该损失函数大于等于$0$恒成立，并且这些正值是由划分错误的样本累积起来产生的。

基于上述动机，我们尝试使用$0/1$损失函数描述上述两种情况：
该函数的特点：无论划分错误的偏差有多大，都被一视同仁为数值$1$.
$${\mathcal{L}}_{0/1}\left[y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)-1\right]=\{\begin{array}{l}1y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)-1<0\\ 0\text{Otherwise}\end{array}$$
从而对应拉格朗日函数可描述为如下形式：
依然是‘拉格朗日乘数法’。
$$\underset{\mathcal{W},b}{\min }\frac{1}{2}||\mathcal{W}|{|}^2+\mathcal{C}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}{\mathcal{L}}_{0/1}\left[y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)-1\right]$$

$\text{Hinge}$损失函数

由于$0/1$损失函数在定义域内并非处处连续，在优化过程中因无法处处可导导致无法求解出迭代最优解；并且${\sum }_{x^{(i)},y^{(i)}\in \mathcal{D}}{\mathcal{L}}_{0/1}\left[y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)-1\right]$的结果是一个正整数，对于划分错误的样本偏差描述得不够细致。

因此，另一种方法是将偏差值直接作为损失函数的一部分，具体数学描述表示如下：
$$\mathcal{L}=\{\begin{array}{l}0y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\ge 1\\ 1-y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\text{Otherwise}\end{array}$$

和上述$0/1$损失函数的动机相比，该函数在以$y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)$的定义域内处处连续，并且该方法累积的偏差是真实的偏差结果。将上述两种情况使用一个公式进行表达：
$${\mathcal{L}}_{Hinge}=\max \left\{0,1-y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\right\}$$
该函数的图像表示为如下形式：

该函数由于形似一个开合的书页，也被称作合页损失函数($\text{Hinge Loss Function}$)，记作${\mathcal{L}}_{Hinge}$。最终，基于该函数的拉格朗日函数可描述为如下形式：
$$\underset{\mathcal{W},b}{\min }\frac{1}{2}||\mathcal{W}|{|}^2+\mathcal{C}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}\max \left\{0,1-y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\right\}$$

支持向量机的正则化

上面介绍了两种损失函数：$0/1$损失函数，合页损失函数。实际上，无论是哪种损失函数，我们关注的是它们整体的优化目标，也就是拉格朗日函数。
$$\{\begin{array}{l}\begin{array}{r}\underset{\mathcal{W},b}{\min }\frac{1}{2}||\mathcal{W}|{|}^2+\mathcal{C}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}{\mathcal{L}}_{0/1}\left[y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)-1\right]\end{array}\\ \begin{array}{r}\underset{\mathcal{W},b}{\min }\frac{1}{2}||\mathcal{W}|{|}^2+\mathcal{C}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}\max \left\{0,1-y^{(i)}({\mathcal{W}}^T{x}^{(i)}+b)\right\}\end{array}\end{array}$$
观察上述两个函数，它们存在共性：

• 第一项：都是通过调整合适的参数${\mathcal{W}}^{\ast }$，并尽可能使最大间隔$||\mathcal{W}|{|}^2$达到最小；
• 第二项：针对划分错误样本产生的误差$({\mathcal{L}}_{0/1},{\mathcal{L}}_{Hinge})$达到最小。

关于上述拉格朗日函数的通式表示如下：
详见《机器学习》(周志华著) P133 6.5 支持向量回归 公式6.42
$$\underset{f}{\min }\Omega (f)+\mathcal{C}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}\mathcal{L}[f(x^{(i)}),y^{(i)}]$$

• 我们通常称第一项$\Omega (f)$为结构风险($\text{Structual Risk}$)，在支持向量机中结构风险是指对模型$f$的结构——最大间隔逻辑进行优化；
• 第二项被称为经验风险($\text{Empirical Risk}$)，具体描述模型与数据之间的契合程度。$\text{Hinge}$函数作为减小经验风险的损失函数，$\mathcal{B}$ 选项正确。

至此，我们要纠正两个误区：

• 真正的损失函数指的是经验风险。通过观察，结构风险$||\mathcal{W}|{|}^2$自身 就是正则化的表达形式。因此，正则化的功能都能在结构风险中进行表达。

  这里关于 $\mathcal{A}$ 选项中选择$L_2$正则化项描述最大间隔的逻辑正确。

• 关于结构风险$||\mathcal{W}|{|}^2$，它并不是$||\mathcal{W}|{|}_2$，在之前关于$||\mathcal{W}|{|}^2={\mathcal{W}}^T\mathcal{W}$只是选择了$L_2$正则化进行示例。实际上，在描述最大间隔的时候，不一定仅使用欧氏距离。在$\text{K-Means}$算法介绍中提到过明可夫斯基距离，比较有代表性的是曼哈顿距离，对应的$L_1$正则化；以及欧式距离，对应$L_2$正则化。

在正则化——权重衰减角度(直观现象)中补充了$L_1$正则化稀疏权重特征的过程。在迭代过程中，$L_1$正则化产生的权重点仅让一部分权重分量描述，而剩余的权重分量没有参与，从而导致权重分量尽量稀疏；
一部分权重分量没有发挥作用，对应的权重结果就是$0$。

并且$L_1$正则化对应所有权重分量均是一次项，对应的权重分量不会出现非线性的提高/打压，因而$L_1$对权重的惩罚力度相同，$\mathcal{D}$ 选项正确。

相反，$L_2$正则化会倾向于将迭代的权重分摊在各个权重分量 上使各分量取值尽量平衡。从而使非零分量的数量更加稠密。

$\mathcal{C}$ 选项中的$\begin{array}{r}\frac{1}{||\mathcal{W}||}\end{array}$描述的是支持向量到最优决策边界的距离；而分类间隔表示最优决策边界两侧支持向量之间的距离。即$\begin{array}{r}2\times \frac{1}{||\mathcal{W}||}=\frac{2}{||\mathcal{W}||}\end{array}$。因此 $\mathcal{C}$ 选项错误。
求解过程详见支持向量机——模型求解.

相关参考：
《机器学习》(周志华著)