题目描述

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

AL2\\mathcal A \\quad L_2AL2​正则项，作用是最大化分类间隔，使得分类器拥有更强的泛化能力

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

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

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

正确答案：$\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}

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

• 由于$\mathcal{W},b$都是向量，缩放变换后的W′,b′\\mathcal W',b'W′,b′必然和原结果线性相关。并没有影响对权重特征的描述。
• 该部分见《机器学习(周志华著)》P122 左侧小字解释部分
  min⁡x(i),y(i)∈Dy(i)(WTx(i)+b)=1⇔y(i)(WTx(i)+b)≥1\\mathop{\\min}\\limits_{x^{(i)},y^{(i)} \\in \\mathcal D} y^{(i)}(\\mathcal W^Tx^{(i)} + b) = 1 \\Leftrightarrow y^{(i)} (\\mathcal W^Tx^{(i)} + b) \\geq 1x(i),y(i)∈Dmin​y(i)(WTx(i)+b)=1⇔y(i)(WTx(i)+b)≥1

最终可将支持向量机——最大间隔分类器表示为如下基本型：
{min⁡W,b12∣∣W∣∣2s.t.y(i)(WTx(i)+b)≥1(x(i),y(i))∈D\\begin{cases} \\begin{aligned}\\mathop{\\min}\\limits_{\\mathcal W,b} \\frac{1}{2} ||\\mathcal W||^2\\end{aligned} \\\\ s.t. \\quad y^{(i)}(\\mathcal W^Tx^{(i)} + b) \\geq 1 \\quad (x^{(i)},y^{(i)}) \\in \\mathcal D \\end{cases}⎩⎨⎧​W,bmin​21​∣∣W∣∣2​s.t.y(i)(WTx(i)+b)≥1(x(i),y(i))∈D​

软间隔$\text{SVM}$

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

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

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

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

基于上述动机，我们尝试使用$0/1$损失函数描述上述两种情况：
该函数的特点：无论划分错误的偏差有多大，都被一视同仁为数值$1$.
L0/1[y(i)(WTx(i)+b)−1]={1y(i)(WTx(i)+b)−1<00Otherwise\\mathcal L_{0/1}\\left[y^{(i)}(\\mathcal W^Tx^{(i)} + b) - 1\\right] = \\begin{cases} 1 \\quad y^{(i)}(\\mathcal W^Tx^{(i)} + b) - 1 < 0 \\\\ 0 \\quad \\text{Otherwise} \\end{cases}L0/1​[y(i)(WTx(i)+b)−1]={1y(i)(WTx(i)+b)−1<00Otherwise​
从而对应拉格朗日函数可描述为如下形式：
依然是‘拉格朗日乘数法’。
min⁡W,b12∣∣W∣∣2+C∑x(i),y(i)∈DL0/1[y(i)(WTx(i)+b)−1]\\mathop{\\min}\\limits_{\\mathcal W,b} \\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^Tx^{(i)} + b) - 1\\right]W,bmin​21​∣∣W∣∣2+Cx(i),y(i)∈D∑​L0/1​[y(i)(WTx(i)+b)−1]

$\text{Hinge}$损失函数

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

因此，另一种方法是将偏差值直接作为损失函数的一部分，具体数学描述表示如下：
L={0y(i)(WTx(i)+b)≥11−y(i)(WTx(i)+b)Otherwise\\mathcal L = \\begin{cases} 0 \\quad y^{(i)}(\\mathcal W^Tx^{(i)} + b) \\geq 1 \\\\ 1 - y^{(i)}(\\mathcal W^Tx^{(i)} + b) \\quad \\text{Otherwise} \\end{cases}L={0y(i)(WTx(i)+b)≥11−y(i)(WTx(i)+b)Otherwise​

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

该函数由于形似一个开合的书页，也被称作合页损失函数($\text{Hinge Loss Function}$)，记作LHinge\\mathcal L_{Hinge}LHinge​。最终，基于该函数的拉格朗日函数可描述为如下形式：
min⁡W,b12∣∣W∣∣2+C∑x(i),y(i)∈Dmax⁡{0,1−y(i)(WTx(i)+b)}\\mathop{\\min}\\limits_{\\mathcal W,b} \\frac{1}{2}||\\mathcal W||^2 + \\mathcal C \\sum_{x^{(i)},y^{(i)} \\in \\mathcal D} \\max \\left\\{0,1 - y^{(i)}(\\mathcal W^Tx^{(i)} + b) \\right\\}W,bmin​21​∣∣W∣∣2+Cx(i),y(i)∈D∑​max{0,1−y(i)(WTx(i)+b)}

支持向量机的正则化

上面介绍了两种损失函数：$0/1$损失函数，合页损失函数。实际上，无论是哪种损失函数，我们关注的是它们整体的优化目标，也就是拉格朗日函数。
{min⁡W,b12∣∣W∣∣2+C∑x(i),y(i)∈DL0/1[y(i)(WTx(i)+b)−1]min⁡W,b12∣∣W∣∣2+C∑x(i),y(i)∈Dmax⁡{0,1−y(i)(WTx(i)+b)}\\begin{cases} \\begin{aligned}\\mathop{\\min}\\limits_{\\mathcal W,b} \\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^Tx^{(i)} + b) - 1\\right] \\end{aligned}\\\\ \\begin{aligned} \\mathop{\\min}\\limits_{\\mathcal W,b} \\frac{1}{2}||\\mathcal W||^2 + \\mathcal C \\sum_{x^{(i)},y^{(i)} \\in \\mathcal D} \\max \\left\\{0,1 - y^{(i)}(\\mathcal W^Tx^{(i)} + b) \\right\\} \\end{aligned} \\end{cases}⎩⎨⎧​W,bmin​21​∣∣W∣∣2+Cx(i),y(i)∈D∑​L0/1​[y(i)(WTx(i)+b)−1]​W,bmin​21​∣∣W∣∣2+Cx(i),y(i)∈D∑​max{0,1−y(i)(WTx(i)+b)}​​
观察上述两个函数，它们存在共性：

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

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

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

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

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

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

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

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

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

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

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

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