网站建设湖南,网站建设开发工具,要实现对网站中的所有内容进行搜索代码应该怎么写,wordpress 分享本文牛客网算法八股刷题系列——正则化[软间隔SVM再回首]题目描述正确答案#xff1a;C\mathcal CC题目解析开端#xff1a;关于函数间隔问题解释的补充软间隔SVM\text{SVM}SVMHinge\text{Hinge}Hinge损失函数支持向量机的正则化题目描述
关于支持向量机(Support Vector Machine…
牛客网算法八股刷题系列——正则化[软间隔SVM再回首]题目描述正确答案C\mathcal CC题目解析开端关于函数间隔问题解释的补充软间隔SVM\text{SVM}SVMHinge\text{Hinge}Hinge损失函数支持向量机的正则化题目描述
关于支持向量机(Support Vector Machine,SVM)(\text{Support Vector Machine,SVM})(Support Vector Machine,SVM)下列说法错误的是()(\quad)()
AL2\mathcal A \quad L_2AL2正则项作用是最大化分类间隔使得分类器拥有更强的泛化能力
BHinge\mathcal B \quad \text{Hinge}BHinge损失函数作用是最小化经验风险错误
C\mathcal C \quadC分类间隔1∣∣W∣∣\begin{aligned}\frac{1}{||\mathcal W||}\end{aligned}∣∣W∣∣1其中∣∣W∣∣||\mathcal W||∣∣W∣∣代表向量的模
DL1\mathcal D \quad L_1DL1正则化对所有参数的惩罚力度都一样可以让一部分权重变为零因此产生稀疏模型能够去除某些特征
正确答案C\mathcal CC
题目解析
开端关于函数间隔问题解释的补充 该部分对照支持向量机——模型构建思路进行阅读。 这里依然以二分类任务为例。已知数据集合D\mathcal DD以集合内的标签集合表示如下 D{(x(i),y(i))}i1Ny(i)∈{1,−1}\mathcal D \{(x^{(i)},y^{(i)})\}_{i1}^N \quad y^{(i)} \in \{1,-1\}D{(x(i),y(i))}i1Ny(i)∈{1,−1}
在支持向量机——模型构建思路介绍了分类正确的标志模型输出结果WTx(i)b\mathcal W^Tx^{(i)} bWTx(i)b与对应标签结果y(i)y^{(i)}y(i)同号 {WTx(i)b0y(i)1WTx(i)b0y(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)b0y(i)1WTx(i)b0y(i)−1 从而确定模型的决策边界(超平面) WTxb0\mathcal W^Tx b 0WTxb0 虽然找到了决策边界但出现了新的问题决策边界不唯一。我们可以对上述决策边界进行任意缩放 ⇒\Rightarrow⇒ 等式两侧同时乘以常数kkk决策边界并不发生影响。 k⋅(WTxb)k⋅00k \cdot (\mathcal W^Tx b) k \cdot 0 0k⋅(WTxb)k⋅00 但是对应的函数间隔(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⇒minx(i),y(i)∈Dy(i)(WTx(i)b)minx(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)∈Dminy(i)(WTx(i)b)x(i),y(i)DminH(i)γ 为了方便计算设定γ1\gamma 1γ1。也就是说无论对决策边界扩张还是收缩都可以通过对W,b\mathcal W,bW,b进行相应的缩放使得等式成立
由于W,b\mathcal W,bW,b都是向量缩放变换后的W′,b′\mathcal W,bW′,b′必然和原结果线性相关。并没有影响对权重特征的描述。该部分见《机器学习(周志华著)》P122 左侧小字解释部分 minx(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)∈Dminy(i)(WTx(i)b)1⇔y(i)(WTx(i)b)≥1
最终可将支持向量机——最大间隔分类器表示为如下基本型 {minW,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,bmin21∣∣W∣∣2s.t.y(i)(WTx(i)b)≥1(x(i),y(i))∈D
软间隔SVM\text{SVM}SVM 该部分对照支持向量机——软间隔SVM\text{SVM}SVM进行阅读。 关于软间隔构建损失函数的动机 可描述为
假设损失函数为L\mathcal LL如果某样本被划分正确那么对应的L0\mathcal L 0L0相反如果某样本没有被划分正确意味着y(i)(WTx(i)b)1y^{(i)}(\mathcal W^Tx^{(i)} b) 1y(i)(WTx(i)b)1那么对应的函数结果为 可以看出该结果是一个≤1\leq 1≤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)
可以看出该损失函数大于等于000恒成立并且这些正值是由划分错误的样本累积起来产生的。
基于上述动机我们尝试使用0/10/10/1损失函数描述上述两种情况 该函数的特点无论划分错误的偏差有多大都被一视同仁为数值111. L0/1[y(i)(WTx(i)b)−1]{1y(i)(WTx(i)b)−100Otherwise\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)−100Otherwise 从而对应拉格朗日函数可描述为如下形式 依然是‘拉格朗日乘数法’。 minW,b12∣∣W∣∣2C∑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,bmin21∣∣W∣∣2Cx(i),y(i)∈D∑L0/1[y(i)(WTx(i)b)−1]
Hinge\text{Hinge}Hinge损失函数
由于0/10/10/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)∈DL0/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/10/10/1损失函数的动机相比该函数在以y(i)(WTx(i)b)y^{(i)}(\mathcal W^Tx^{(i)} b)y(i)(WTx(i)b)的定义域内处处连续并且该方法累积的偏差是真实的偏差结果。将上述两种情况使用一个公式进行表达 LHingemax{0,1−y(i)(WTx(i)b)}\mathcal L_{Hinge} \max \left\{0,1 - y^{(i)}(\mathcal W^Tx^{(i)} b)\right\}LHingemax{0,1−y(i)(WTx(i)b)} 该函数的图像表示为如下形式 该函数由于形似一个开合的书页也被称作合页损失函数(Hinge Loss Function\text{Hinge Loss Function}Hinge Loss Function)记作LHinge\mathcal L_{Hinge}LHinge。最终基于该函数的拉格朗日函数可描述为如下形式 minW,b12∣∣W∣∣2C∑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,bmin21∣∣W∣∣2Cx(i),y(i)∈D∑max{0,1−y(i)(WTx(i)b)}
支持向量机的正则化
上面介绍了两种损失函数0/10/10/1损失函数合页损失函数。实际上无论是哪种损失函数我们关注的是它们整体的优化目标也就是拉格朗日函数。 {minW,b12∣∣W∣∣2C∑x(i),y(i)∈DL0/1[y(i)(WTx(i)b)−1]minW,b12∣∣W∣∣2C∑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,bmin21∣∣W∣∣2Cx(i),y(i)∈D∑L0/1[y(i)(WTx(i)b)−1]W,bmin21∣∣W∣∣2Cx(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 minfΩ(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)]
我们通常称第一项Ω(f)\Omega(f)Ω(f)为结构风险(Structual Risk\text{Structual Risk}Structual Risk)在支持向量机中结构风险是指对模型fff的结构——最大间隔逻辑进行优化第二项被称为经验风险(Empirical Risk\text{Empirical Risk}Empirical Risk)具体描述模型与数据之间的契合程度。Hinge\text{Hinge}Hinge函数作为减小经验风险的损失函数B\mathcal B \quadB 选项正确。
至此我们要纠正两个误区 真正的损失函数指的是经验风险。通过观察结构风险∣∣W∣∣2||\mathcal W||^2∣∣W∣∣2自身 就是正则化的表达形式。因此正则化的功能都能在结构风险中进行表达。 这里关于 A\mathcal A \quadA 选项中选择L2L_2L2正则化项描述最大间隔的逻辑正确。 关于结构风险∣∣W∣∣2||\mathcal W||^2∣∣W∣∣2它并不是∣∣W∣∣2||\mathcal W||_2∣∣W∣∣2在之前关于∣∣W∣∣2WTW||\mathcal W||^2 \mathcal W^T\mathcal W∣∣W∣∣2WTW只是选择了L2L_2L2正则化进行示例。实际上在描述最大间隔的时候不一定仅使用欧氏距离。在K-Means\text{K-Means}K-Means算法介绍中提到过明可夫斯基距离比较有代表性的是曼哈顿距离对应的L1L_1L1正则化以及欧式距离对应L2L_2L2正则化。
在正则化——权重衰减角度(直观现象)中补充了L1L_1L1正则化稀疏权重特征的过程。在迭代过程中L1L_1L1正则化产生的权重点仅让一部分权重分量描述而剩余的权重分量没有参与从而导致权重分量尽量稀疏 一部分权重分量没有发挥作用对应的权重结果就是000。
并且L1L_1L1正则化对应所有权重分量均是一次项对应的权重分量不会出现非线性的提高/打压因而L1L_1L1对权重的惩罚力度相同D\mathcal D \quadD 选项正确。
相反L2L_2L2正则化会倾向于将迭代的权重分摊在各个权重分量 上使各分量取值尽量平衡。从而使非零分量的数量更加稠密。
C\mathcal C \quadC 选项中的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。因此 C\mathcal C \quadC 选项错误。 求解过程详见支持向量机——模型求解.
相关参考 《机器学习》(周志华著)
