5.6 练习

5.1 软边缘超平面。用于软边缘超平面优化问题的松弛变量的函数形式为:$\xi \mapsto \sum _{i=1}^m{\xi }_i$。相反，我们可以使用$\xi \mapsto \sum _{i=1}^m{\xi }_i^p$，其中$p>1$。

(a)给出这个一般情况下的对偶问题。

(b)这种更一般的公式$\left(p>1\right)$与标准设置$\left(p=1\right)$相比如何？在$p=2$的情况下，优化仍然是凸的吗？

5.2 更紧的Rademacher界。推导定理5.9的以下更紧版本界限:对于任意的 $\delta >0$ ，在至少 $1-\delta$ 的概率下，对于所有的 $h\in \mathcal{H}$ 和 $\rho \in (0,1]$ ，以下成立:

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+\frac{2\gamma }{\rho }{\Re }_m\left(\mathcal{H}\right)+\sqrt{\frac{\log {\log }_{\gamma }\frac{\gamma }{\rho }}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}\text{\hspace{1em}(5.49)}$$

对于任意的 $\gamma >1$ 。

5.3 加权重要性的支持向量机(SVM)。假设你希望使用SVM来解决一个学习问题，其中某些训练数据点比其他点更重要。更正式地说，假设每个训练点由一个三元组 $\left(x_i,y_i,p_i\right)$ 组成，其中 $0\le p_i\le 1$ 是第 $i$ 个点的重要性。重写原始SVM约束优化问题，使得错误标记一个点 $x_i$ 的惩罚按优先级 $p_i$ 缩放。然后将这个修改带到对偶解的推导中。

5.4 序贯最小优化(SMO)。SMO算法是一种优化算法，用于加速SVM的训练。SMO将一个(潜在的)大型二次规划(QP)优化问题简化为一系列只涉及两个拉格朗日乘子的优化。SMO减少了内存需求，绕过了数值QP优化的需要，并且易于实现。在这个问题中，我们将推导出在SVM问题的对偶形式中SMO算法的更新规则。

(a)假设我们只想优化方程(5.33)中的 ${\alpha }_1$ 和 ${\alpha }_2$ 。证明优化问题简化为

$$\underset{{\alpha }_1,{\alpha }_2}{\max }\underset{{\Psi }_1\left({\alpha }_1,{\alpha }_2\right)}{\underbrace{{\alpha }_1+{\alpha }_2-\frac{1}{2}{K}_{11}{\alpha }_1^2-\frac{1}{2}{K}_{22}{\alpha }_2^2-s{K}_{12}{\alpha }_1{\alpha }_2-y_1{\alpha }_1{v}_1-y_2{\alpha }_2{v}_2}}$$

约束条件: $0\le {\alpha }_1,{\alpha }_2\le C\wedge {\alpha }_1+s{\alpha }_2=\gamma$ ，

其中 $\gamma =y_1\sum _{i=3}^m{y}_i{\alpha }_i,s=y_1{y}_2\in \{-1,+1\},K_{ij}=\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)$ 和 $v_i=$ $\sum _{j=3}^m{\alpha }_j{y}_j{K}_{ij}$ 对于 $i=1,2$ 。

(b)将线性约束 ${\alpha }_1=\gamma -s{\alpha }_2$ 代入 ${\Psi }_1$ 以获得一个新的目标函数 ${\Psi }_2$ ，该函数仅依赖于 ${\alpha }_2$ 。证明使 ${\Psi }_2$ 最小化的 ${\alpha }_2$ (在不考虑约束 $0\le {\alpha }_1,{\alpha }_2\le C)$ 的情况下)可以表示为

$${\alpha }_2=\frac{s\left(K_{11}-K_{12}\right)\gamma +y_2\left(v_1-v_2\right)-s+1}{\eta },$$

其中 $\eta =K_{11}+K_{22}-2K_{12}$ .

(c) 证明

$$v_1-v_2=f\left({\mathbf{x}}_1\right)-f\left({\mathbf{x}}_2\right)+{\alpha }_2^{\ast }{y}_2\eta -s{y}_2\gamma \left(K_{11}-K_{12}\right)$$

其中 $f\left(\mathbf{x}\right)=\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i\left({\mathbf{x}}_i\cdot \mathbf{x}\right)+b^{\ast }$ 和 ${\alpha }_i^{\ast }$ 是在 ${\alpha }_1$ 和 ${\alpha }_2$ 优化之前的拉格朗日乘数值(同样，$b^{\ast }$ 是偏移量之前的值)。

(d) 证明

$${\alpha }_2={\alpha }_2^{\ast }+y_2\frac{\left(y_2-f\left({\mathbf{x}}_2\right)\right)-\left(y_1-f\left({\mathbf{x}}_1\right)\right)}{\eta }.$$

(e) 对于 $s=+1$ ，定义 $L=\max \{0,\gamma -C\}$ 和 $H=\min \{C,\gamma \}$ 为 ${\alpha }_2$ 的下界和上界。类似地，对于 $s=-1$ ，定义 $L=\max \{0,-\gamma \}$ 和 $H=\min \{C,C-\gamma \}$ 。SMO的更新规则涉及对 $s=+1$ 值的“剪辑”

即，

$${\alpha }_2^{clip}=\{\begin{array}{ll}{\alpha }_2& \text{if }L<{\alpha }_2<H\\ L& \text{if }{\alpha }_2\le L\\ H& \text{if }{\alpha }_2\ge H\end{array}.$$

我们随后求解 ${\alpha }_1$ ，以满足等式约束，从而得到 ${\alpha }_1={\alpha }_1^{\ast }+s\left({\alpha }_2^{\ast }-{\alpha }_2^{\text{clip }}\right)$ 。为什么需要“剪辑”？在 $s=+1$ 的情况下，$L$ 和 $H$ 是如何推导出来的？

5.5 SVMs 实践。

(a) 从以下地址下载并安装 libsvm 软件库:

$$\text{http://www.csie.ntu.edu.tw/ cjlin/libsvm/.}$$

(b) 下载位于以下位置的 satimage 数据集:

$$\text{http://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/.}$$

将训练集和验证集合并为一个。从此我们将这个集合称为训练集。归一化训练和测试向量。

(c) 考虑二元分类问题，即区分类别6和其他数据点。使用结合多项式核的SVM(见第6章)来解决这个分类问题。为此，将训练数据随机分成十个大小相等的互不相交的集合。对于每个多项式度数 $d=1,2,3,4$ ，绘制平均交叉验证误差加上或减去一个标准差作为 $C$ 的函数。让libsvm中多项式核的其他参数 $\gamma$ 和 $c$ 保持默认值1。报告在验证集上测量的最佳折中常数 $C$ 的值。

(d) 设 $\left(C^{\ast },d^{\ast }\right)$ 为之前找到的最佳对。将 $C$ 固定为 $C^{\ast }$ 。绘制十折交叉验证的训练和测试误差，作为 $d$ 的函数得到的假设。绘制 $d$ 的函数，得到支持向量的平均数量的图像。

(e) 有多少支持向量位于边缘超平面上？

(f) 在标准二分类问题中，正类和负类上的错误以相同的方式处理。然而，假设我们希望对负点上的错误(假阳性错误)$k>0$ 倍于正点上的错误进行惩罚。给出相应于以这种方式修改的SVM的对偶优化问题。

(g) 假设 $k$ 是一个整数。展示如何在不编写任何额外代码的情况下使用libsvm找到刚刚描述的修改后SVM的解。

(h) 将修改后的SVM应用于之前研究过的分类任务，并与 $k=2,4,8,16$ 的先前SVM结果进行比较。

5.6 稀疏SVM。可以提出两种支持SVM算法的论点:一种基于支持向量的稀疏性，另一种基于边缘的概念。假设我们不是选择最大化边缘，而是选择通过最小化 $L_p$ 范数来最大化稀疏性，该范数定义了权重向量 $\alpha$ 的向量 $\mathbf{w}$ ，对于某些 $p\ge 1$ 。首先，考虑 $p=2$ 的情况。这给出了以下优化问题:

$$\underset{\alpha ,b}{\min }\frac{1}{2}\sum _{i=1}^m{\alpha }_i^2+C\sum _{i=1}^m{\xi }_i\text{\hspace{1em}(5.50)}$$ $$\text{subject to}{y}_i\left(\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_i\cdot {\mathbf{x}}_j+b\right)\ge 1-{\xi }_i,i\in \left[m\right]$$ $${\xi }_i,{\alpha }_i\ge 0,i\in \left[m\right]\text{.}$$

(a) 证明在 $\alpha$ 的非负约束下，该问题与SVM原优化问题的一个实例相一致。

(b) 推导 (5.50) 问题的对偶优化。

(c) 设置 $p=1$ 将导致 $\alpha$ 更加稀疏。推导这种情况下的对偶优化。

5.7 标准超平面的 VC 维数。这个问题的目标是推导出标准超平面 VC 维数的上界，该上界不依赖于

特征空间的维度。设 $S\subseteq \{\mathbf{x}:\parallel \mathbf{x}\parallel \le r\}$ 。我们将证明集合的标准超平面的 VC 维数 $d$ $\{x\mapsto \mathrm{sgn}\left(\mathbf{w}\cdot \mathbf{x}\right):\underset{x\in S}{\min }\mid \mathbf{w}$ 。 $\mathbf{x}\mid =1\wedge \parallel \mathbf{w}\parallel \le \Lambda \}$ 验证

$$d\le r^2{\Lambda }^2\text{\hspace{1em}(5.51)}$$

(a) 设 $\left\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_d\right\}$ 是一个可以被击碎的集合。证明对于所有的 $\mathbf{y}=$ $\left(y_1,\dots ,y_d\right)\in \{-1,+1{\}}^d,d\le \Lambda \Vert \begin{array}{c}\sum _{i=1}^d{y}_i{\mathbf{x}}_i\end{array}\Vert .$

(b) 使用标签的随机化 $\mathbf{y}$ 和 Jensen 不等式来证明 $d\le \Lambda \sqrt{\sum _{i=1}^d{\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert }^2}$

(c) 得出结论 $d\le r^2{\Lambda }^2$ 。