风险的凸化#

背景#

在二元分类问题中, 为简化讨论, 聚焦于输出$y \in \{-1, 1\}$的情况, 并采用0 - 1损失函数. 尽管如此, 其中多数概念能推广至更一般的结构化预测场景.

我们的目标是估计一个二元值函数. 常规做法是在二元值函数的假设空间（等同于$\mathcal{X}$的子集空间）上最小化经验风险. 但此方法存在弊端：

一方面, 会引发组合问题, 计算过程极为复杂；

另一方面, 难以对这类假设空间进行模型容量控制, 即正则化操作存在困难.

解决方法#

摒弃直接学习取值为$\{-1, 1\}$的二元函数$f$, 转而学习一个实值函数$g: \mathcal{X} \to \mathbb{R}$, 通过$f(x) = \text{sign}(g(x))$来确定最终的二元分类结果. 其中$\text{sign}(a)$的定义为：

当$a \geq 0$时, $\text{sign}(a)= 1$；当$a < 0$时, $\text{sign}(a)= -1$ . 特别地, 当$a = 0$时, $\text{sign}(a)$也可选$-1$, 这对应了在面对高度模糊的观测数据时, 随机从两个标签中选择一个的情况, 此时错误概率为50%.

风险函数#

函数$f = \text{sign} \circ g$的风险记为$\mathcal{R}(g)$ , 从本质上来说, 它表示分类错误的概率. 具体可转化为$\mathcal{R}(g) = \mathbb{P}(\text{sign}(g(x)) \neq y) = \mathbb{E}(1_{\text{sign}(g(x)) \neq y}) = \mathbb{E}(1_{yg(x) < 0}) = \mathbb{E}\Phi_{0 - 1}(yg(x))$ . 这里的$\Phi_{0 - 1}: \mathbb{R} \to \mathbb{R}$, 且$\Phi_{0 - 1}(u) = 1_{u < 0}$, 被称作“基于间隔”的0 - 1损失函数, 简称0 - 1损失函数. 需要留意的是, 此处的0 - 1损失函数定义在$\mathbb{R}$上.

经验风险最小化问题#

在实际应用中, 为实现经验风险最小化, 需要针对$g: \mathcal{X} \to \mathbb{R}$最小化相应的经验风险$\frac{1}{n}\sum_{i = 1}^{n}\Phi_{0 - 1}(y_ig(x_i))$. 然而, $\Phi_{0 - 1}$函数具有不连续性, 并非凸函数, 这使得优化过程面临较大困难.

二次损失： $\Phi(u) = (u - 1)^2$ . 因为$y^2 = 1$, 所以

$\Phi(yg(x))=(y - g(x))^2=(g(x) - y)^2.$

这样就回到了最小二乘法, 并且我们直接忽略了标签必须属于$\{-1, 1\}$这一事实, 通过取$g(x)$的符号来进行预测.

需要注意的是, 当$y\Phi(x)$为正值时, 会出现过度惩罚的情况, 而下面介绍的其他损失函数（它们是非递增的）则不会出现这种情况.

逻辑损失： $\Phi(u)=\log(1 + e^{-u})$ , 由此可得

其中, $\sigma(v)=\frac{1}{1 + e^{-v}}$是sigmoid函数. 注意这里与最大似然估计的联系, 我们通过$\mathbb{P}(y = 1|x)=\sigma(f(x))$ 和$\mathbb{P}(y = -1|x)=\sigma(-f(x)) = 1 - \sigma(f(x))$ 来定义模型.

此时, 风险就是负的条件对数似然$\mathbb{E}[-\log p(y|x)]$ . 它也常被称为交叉熵损失.

我们不最小化经典风险$\mathcal{R}(g)$ 或其经验版本, 而是最小化$\Phi$风险（及其经验版本）, 其定义如下：

在这种情况下, 函数$g$有时被称为分数函数 或评分函数.

支持向量机(SVM)的原理#

支持向量机常被用于分类任务. 这里考虑的是数据可分的情况, 即存在一个仿射超平面（在二维空间中是直线, 三维空间中是平面, 更高维就是超平面）能把不同类别的数据分开. 数据点用$(x_{i}, y_{i})$表示, $x_{i}$是$d$维的特征向量, $y_{i}$是类别标签, 取值为$-1$或者$1$ , 代表两个不同的类别.

数据可分#

如果存在向量$w \in \mathbb{R}^{d}$（超平面的法向量）和实数$b \in \mathbb{R}$ , 使得对于所有的$i$（从$1$到$n$） , 都有$y_{i}(w^{\top}x_{i} + b) > 0$ , 那就说明数据是可分的. 这里$w^{\top}x_{i} + b = 0$就是超平面的方程, $y_{i}(w^{\top}x_{i} + b) > 0$表示正类（$y_{i}=1$）的数据点在超平面一侧, 负类（$y_{i} = -1$）的数据点在超平面另一侧.

距离计算#

根据点到超平面的距离公式, 点$x_{i}$到超平面$\{x \in \mathbb{R}^{d}, w^{\top}x + b = 0\}$的距离是 $\frac{|w^{\top}x_{i} + b|}{\|w\|_{2}}.$ 因为$y_{i}$的取值是$\pm1$ , 并且数据可分, 所以可以把距离写成$\frac{y_{i}(w^{\top}x_{i} + b)}{\|w\|_{2}}$ . 那么数据集中离超平面最近的点的距离就是 $\min_{i \in \{1, \ldots, n\}}\frac{y_{i}(w^{\top}x_{i} + b)}{\|w\|_{2}}.$

优化问题转化#

支持向量机的目标是最大化这个最小距离. 又因为对$w$和$b$进行相同的缩放（乘以一个非零标量）, 超平面是不变的, 所以可以将原问题转化为一个更方便求解的约束优化问题：

在满足对于任意$i \in \{1, \ldots, n\}$ , $y_{i}(w^{\top}x_{i} + b) \geq 1$的条件下, 最小化 $\frac{1}{2}\|w\|_{2}^{2}.$ 这里加个$\frac{1}{2}$是为了后续求导计算方便, 本质上和最小化$\|w\|_{2}^{2}$是一样的.

这种转化后的优化问题, 通过求解就能得到合适的$w$和$b$ , 从而确定最优的超平面, 也就是支持向量机的分类模型. 而那些使得$y_{i}(w^{\top}x_{i} + b) = 1$的数据点就被称为支持向量, 它们决定了超平面的位置.

一般数据#

引入松弛变量#

当数据不能被超平面分开时, 之前可分数据情况下的约束条件 $y_{i}(w^{\top}x_{i} + b) \geq 1$ 无法全部满足. 为了让模型能处理这种情况, 引入松弛变量 $\xi_{i} \geq 0$（$i = 1, \ldots, n$）, 将约束条件放宽为 $y_{i}(w^{\top}x_{i} + b) \geq 1 - \xi_{i}$. 这样即使有些点不能满足原来严格的分类条件, 也可以通过给它一个合适的松弛量来纳入模型考虑.

构建目标函数#

• 一方面, 我们仍希望超平面的法向量 $w$ 的范数尽量小, 也就是让 $\frac{1}{2}\|w\|_{2}^{2}$ 尽可能小, 这和可分数据时寻找“最优超平面”的思路一致, 保证超平面的稳定性和泛化能力.

• 另一方面, 为了控制松弛的程度, 不能让松弛变量随意取值过大, 所以要对松弛变量进行约束. 这里通过最小化所有松弛变量的总和 $\sum_{i = 1}^{n}\xi_{i}$ 来实现. 同时, 引入一个惩罚参数 $C > 0$ 来平衡 $\frac{1}{2}\|w\|_{2}^{2}$ 和 $\sum_{i = 1}^{n}\xi_{i}$ 这两项的重要性. $C$ 越大, 表示对分类错误（即松弛变量的存在）的惩罚越重.

综合这两方面, 就构建出了目标函数 $\frac{1}{2}\|w\|_{2}^{2} + C\sum_{i = 1}^{n}\xi_{i},$

并且要在约束条件“对于任意 $i \in \{1, \ldots, n\}$, 有 $y_{i}(w^{\top}x_{i} + b) \geq 1 - \xi_{i}$ 且 $\xi_{i} \geq 0$”下, 求该目标函数关于 $w \in \mathbb{R}^{d}$、$b \in \mathbb{R}$ 和 $\xi \in \mathbb{R}^{n}$ 的最小值, 即： $\min_{w \in \mathbb{R}^{d}, b \in \mathbb{R}, \xi \in \mathbb{R}^{n}} \frac{1}{2}\|w\|_{2}^{2} + C\sum_{i = 1}^{n}\xi_{i}$

等价变换#

令 $\lambda = \frac{1}{nC}$, 对上述问题进行进一步的等价变换. 这里利用了铰链损失函数 $(1 - y_{i}(w^{\top}x_{i} + b))_{+}$ 的性质（其中 $(\cdot)_{+}$ 表示取正数部分, 即 $z_{+} = \max\{0, z\}$ ）, 将问题转化为：

$\min_{w \in \mathbb{R}^{d}, b \in \mathbb{R}} \frac{1}{n}\sum_{i = 1}^{n}(1 - y_{i}(w^{\top}x_{i} + b))_{+} + \frac{\lambda}{2}\|w\|_{2}^{2}$

这个式子就是带有铰链损失的 $\ell_{2}$ 正则化经验风险最小化问题, 它从另一个角度描述了在数据不可分情况下, 支持向量机通过最小化经验风险（包含铰链损失部分）和正则化项（$\frac{\lambda}{2}\|w\|_{2}^{2}$ ）来寻找合适的参数 $w$ 和 $b$ 的过程 .

从$\min_{w \in \mathbb{R}^{d}, b \in \mathbb{R}, \xi \in \mathbb{R}^{n}} \frac{1}{2}\|w\|_{2}^{2} + C\sum_{i = 1}^{n}\xi_{i}$（满足$y_{i}(w^{\top}x_{i} + b) \geq 1 - \xi_{i}$且$\xi_{i} \geq 0$）转化为$\min_{w \in \mathbb{R}^{d}, b \in \mathbb{R}} \frac{1}{n}\sum_{i = 1}^{n}(1 - y_{i}(w^{\top}x_{i} + b))_{+} + \frac{\lambda}{2}\|w\|_{2}^{2}$ , 主要有以下步骤：

已知约束条件$y_{i}(w^{\top}x_{i} + b) \geq 1 - \xi_{i}$, 移项可得$\xi_{i} \geq 1 - y_{i}(w^{\top}x_{i} + b)$. 又因为$\xi_{i} \geq 0$, 那么$\xi_{i}$应该取$\max\{0, 1 - y_{i}(w^{\top}x_{i} + b)\}$, 也就是$(1 - y_{i}(w^{\top}x_{i} + b))_{+}$ .

这一步的原理是, $\xi_{i}$要同时满足非负和对原分类条件的松弛要求, 所以它的取值就是$1 - y_{i}(w^{\top}x_{i} + b)$ 为正的部分（如果为负就取$0$ ）.

令$\lambda = \frac{1}{nC}$, 即$C = \frac{1}{n\lambda}$ .

原目标函数$\frac{1}{2}\|w\|_{2}^{2} + C\sum_{i = 1}^{n}\xi_{i}$, 将$\xi_{i} = (1 - y_{i}(w^{\top}x_{i} + b))_{+}$ 和$C = \frac{1}{n\lambda}$代入可得：

同时, 由于已经通过对$\xi_{i}$的等价替换, 将其约束条件融入到新的表达式中, 所以优化变量从$w \in \mathbb{R}^{d}$、$b \in \mathbb{R}$ 和$\xi \in \mathbb{R}^{n}$变为$w \in \mathbb{R}^{d}$ 和$b \in \mathbb{R}$ .

这样就完成了从最初带有松弛变量的优化问题到带有铰链损失的$\ell_{2}$正则化经验风险最小化问题的转化 .

拉格朗日对偶与支持向量#

考虑非负的拉格朗日乘子$\alpha_{i}$和$\beta_{i}$, 其中$i \in \{1, \ldots, n\}$, 并构建如下拉格朗日函数：

$\mathcal{L}(w, b, \xi, \alpha, \beta)=\frac{1}{2}\|w\|_{2}^{2}+C\sum_{i = 1}^{n}\xi_{i}-\sum_{i = 1}^{n}\alpha_{i}(y_{i}(w^{\top}x_{i}+b)-1+\xi_{i})-\sum_{i = 1}^{n}\beta_{i}\xi_{i}$

关于$\xi\in\mathbb{R}^{n}$求最小值, 会得到约束条件：对于任意$i \in \{1, \ldots, n\}$, $\alpha_{i}+\beta_{i}=C$；关于$b$求最小值, 会得到约束条件$\sum_{i = 1}^{n}y_{i}\alpha_{i}=0$ . 最后, 关于$w$求最小值可以得到闭式解$w = \sum_{i = 1}^{n}\alpha_{i}y_{i}x_{i}$ . 这就得到了对偶优化问题：

$\max_{\alpha\in\mathbb{R}^{n}}\sum_{i = 1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i, j = 1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{\top}x_{j}$, 约束条件为$\sum_{i = 1}^{n}y_{i}\alpha_{i}=0$且对于任意$i \in \{1, \ldots, n\}$, $\alpha_{i}\in[0, C]$

正如我们将在第7章针对所有带有线性预测器的$\ell_{2}$正则化学习问题中所展示的那样, 该优化问题仅依赖于点积$x_{i}^{\top}x_{j}$（$i, j = 1, \ldots, n$）, 并且最优预测器可以写成输入数据点$x_{i}$（$i = 1, \ldots, n$）的线性组合. 此外, 对于最优的原变量和对偶变量, 线性不等式约束的“互补松弛性”条件会得出$\alpha_{i}(y_{i}(w^{\top}x_{i}+b)-1+\xi_{i}) = 0$以及$(C - \alpha_{i})\xi_{i}=0$ . 这意味着只要$y_{i}(w^{\top}x_{i}+b)<1$, 就有$\alpha_{i}=0$ . 因此, 许多$\alpha_{i}$都等于$0$, 而最优预测器只是少数几个数据点$x_{i}$的线性组合, 这些数据点就被称为“支持向量” .

条件$\Phi$风险与分类校准#

大多数凸替代损失函数都是0 - 1损失的上界, 并且通过重新缩放都能成为上界. 仅将此作为凸替代损失函数性能良好的理由是具有误导性的, 除非是贝叶斯（即最优）预测器的风险几乎为零的问题（只有在这种情况下才可能出现贝叶斯风险为零） .

如果我们记$\eta(x)=\mathbb{P}(y = 1|x)\in[0, 1]$, 那么我们有$\mathbb{E}[y|x]=2\eta(x)-1$, 则

$\mathcal{R}(g)=\mathbb{E}[\Phi_{0 - 1}(yg(x))]=\mathbb{E}[\mathbb{E}[1_{(g(x)y)\neq y}|x]]\geqslant\mathbb{E}[\min(\eta(x), 1 - \eta(x))]=\mathcal{R}^{*}$

并且一个最优分类器是$f^{*}(x)=\text{sign}(2\eta(x)-1)$. 除了$2\eta(x)-1$之外, 还有许多其他可能的函数$g(x)$, 使得$f^{*}(x)=\text{sign}(g(x))$是最优的.

第一个（不太重要的）原因是当$\eta(x)=1/2$时, 预测的选择具有任意性. 另一个原因是$g(x)$只需与$2\eta(x)-1$具有相同的符号, 这就导致了除$2\eta(x)-1$之外的许多可能性.

为了研究使用$\Phi$风险的影响, 我们首先来看条件风险（对于给定的$x$, 就像对于0 - 1损失一样, 使$\Phi$风险最小化的函数$g$可以通过分别研究每个$x$来确定） .

条件$\Phi$风险#

设$g:\mathcal{X}\to\mathbb{R}$, 我们将条件$\Phi$风险定义为 $\mathbb{E}[\Phi(yg(x))|x]=\eta(x)\Phi(g(x))+(1 - \eta(x))\Phi(-g(x))a,$ 我们记为$C_{\eta(x)}(g(x)),$ 其中

对于凸替代损失函数, 我们至少可以期望在总体情况下, 当所有$x$相互独立时, 通过最小化条件$\Phi$风险得到的最优$g(x)$能产生与贝叶斯预测器完全相同的预测（至少当该预测是唯一的时候）.

换句话说, 由于预测是$\text{sign}(g(x))$, 我们希望对于任意$\eta\in[0, 1]$时

（正的最优预测） $\eta>1/2\Leftrightarrow\underset{\alpha\in\mathbb{R}}{\arg\min}C_{\eta}(\alpha)\subset\mathbb{R}_{+}^{*}$

（负的最优预测） $\eta<1/2\Leftrightarrow\underset{\alpha\in\mathbb{R}}{\arg\min}C_{\eta}(\alpha)\subset\mathbb{R}_{-}^{*}$

满足这两个条件的函数$\Phi$被称为分类校准的, 或简称为校准的. 结果表明, 当$\Phi$是凸函数时, 有一个简单的充要条件：

命题: 设$\Phi:\mathbb{R}\to\mathbb{R}$为凸函数. $\Phi$是校准的, 当且仅当$\Phi$在$0$点可微且$\Phi'(0)<0$.

证明: 由于$\Phi$是凸函数, 对于任意$\eta\in[0,1]$, $C_{\eta}$也是凸函数. 因此, 我们只需考虑在$0$点的左导数和右导数, 以得到关于极小值点位置的条件, 有以下两种情况（极小值点在$\mathbb{R}^+$中, 当且仅当在$0$点的右导数严格为负；极小值点在$\mathbb{R}^-$中, 当且仅当在$0$点的左导数严格为正）：

(a) 假设$\Phi$是校准的. 在公式(4.6)中, 令$\eta$趋于$1/2+$, 可得$(C_{1/2})_+(0)'=\frac{1}{2}[\Phi_+'(0)-\Phi_-'(0)]\leq0$. 由于$\Phi$是凸函数, 我们总有$\Phi_+'(0)-\Phi_-'(0)\geq0$. 因此, 左导数和右导数相等, 这意味着$\Phi$在$0$点可微. 然后$C_{\eta}'(0)=(2\eta - 1)\Phi'(0)$, 我们需要$\Phi'(0)<0$.

(b) 假设$\Phi$在$0$点可微且$\Phi'(0)<0$, 那么$C_{\eta}'(0)=(2\eta - 1)\Phi'(0)$；

风险与F风险之间的关系#

F风险:Φ - 风险

既然我们知道对于任意$x \in \mathcal{X}$, 关于$g(x)$最小化$C_{\eta(x)}(g(x))$ 可通过$\text{sign}(g(x))$得到最优预测, 我们希望确保对超额Φ - 风险进行显式控制能够进而对原始超额风险进行显式控制.

换句话说, 我们要寻找一个单调函数$H:\mathbb{R}_{+} \to \mathbb{R}_{+}$, 使得$\mathcal{R}(g) - \mathcal{R}^* \leq H[\mathcal{R}_{\Phi}(g) - \mathcal{R}_{\Phi}^*],$其中$\mathcal{R}_{\Phi}^*$是可能的最小Φ - 风险. 函数$H$通常被称为校准函数.

与最小二乘回归的情况不同（在最小二乘回归中, 用于测试的损失函数直接就是经验风险最小化中所使用的损失函数）, 这里有两个概念：测试误差$\mathcal{R}(g)$, 它是在对函数$g$进行零阈值处理后得到的；以及量$\mathcal{R}_{\Phi}(g)$, 有时也被称为测试损失.

命题: 对于任意函数$g:\mathcal{X} \to \mathbb{R}$, 以及对于贝叶斯预测器$g^*$： $\mathcal{R}(g) - \mathcal{R}(g^*) = \mathbb{E}[1_{g(x)g^*(x) < 0} \cdot |2\eta(x) - 1|]$. 此外, 我们有$\mathcal{R}(g) - \mathcal{R}(g^*) \leq \mathbb{E}[|2\eta(x) - 1 - g(x)|]$.

证明: 我们将超额风险表示为： $\mathcal{R}(g) - \mathcal{R}(g^*) = \mathbb{E}[|1_{\text{sign}(g(x)) \neq y} - 1_{\text{sign}(g^*(x)) \neq y}| |x]$, 这是根据0 - 1损失的定义得到的.

对于任意给定的$x \in \mathcal{X}$, 我们可以考虑$\eta(x) - 1/2$和$g(x)$的符号的两种可能情况, 这会导致$g$和$g^*$有不同的预测结果, 即 (a) $\eta(x) > 1/2$且$g(x) < 0$, 以及 (b) $\eta(x) < 1/2$且$g(x) > 0$（等式情况无关紧要）. 对于第一种情况, 关于$y$的期望是$\eta(x) - (1 - \eta(x)) = 2\eta(x) - 1$；而对于第二种情况, 我们得到$1 - 2\eta(x)$. 通过将这两种情况合并为条件$g(x)g^*(x) < 0$以及条件期望$|2\eta(x) - 1|$, 我们得到第一个结果.

对于第二个结果, 我们简单利用这样一个事实：如果$g(x)g^*(x) < 0$, 那么, 通过将情况分为两种（第一种是$\eta(x) > 1/2$且$g(x) < 0$, 第二种是$\eta(x) < 1/2$且$g(x) > 0$）, 我们得到$|2\eta(x) - 1| \leq |2\eta(x) - 1 - g(x)|$, 从而得到第二个结果.

风险最小化分解#

我们考虑一个预测函数族$\mathcal{F}$, 其中的预测函数$f:\mathcal{X} \to \mathcal{Y}$. 经验风险最小化的目标是找到 $\hat{f} \in \underset{f\in\mathcal{F}}{\arg\min} \widehat{\mathcal{R}}(f) = \frac{1}{n} \sum_{i = 1}^{n} \ell(y_i, f(x_i))$ .

我们可以将风险分解为如下两项：

一个经典的例子是函数族由$\mathbb{R}^d$的一个子集进行参数化的情况, 即$\mathcal{F} = \{f_{\theta}, \theta \in \Theta\}$, 其中$\Theta \subset \mathbb{R}^d$. 这涵盖了神经网络, 以及最简单的线性模型形式$f_{\theta}(x) = \theta^{\top} \varphi(x)$（对于某个特征向量$\varphi(x)$ , 如第3章中所述） . 我们将使用具有利普希茨连续损失函数的线性模型作为示例, 并且通常会对$\ell_2$ - 范数$\|\theta\|_2$添加约束或惩罚项.

现在我们分别来讨论近似误差和估计误差.

近似误差#

对近似误差进行界定, 相当于对$\underset{f\in\mathcal{F}}{\inf} \mathcal{R}(f) - \mathcal{R}^*$ 进行界定, 这需要对贝叶斯预测器（有时也称为“目标函数”）$f^*$ 做出假设（因此也涉及到测试分布）, 以便实现非零的学习收益.

在本节中, 我们将重点关注模型族$\mathcal{F} = \{f_{\theta}, \theta \in \Theta\}$ , 其中$\Theta \subset \mathbb{R}^d$（我们将在第7章考虑无穷维的情况）以及凸的利普希茨连续损失函数. 假设$\theta_*$ 是在$\theta \in \mathbb{R}^d$ 范围内$\mathcal{R}(f_{\theta})$ 的极小值点（通常, 它不属于$\Theta$ ）. 这意味着近似误差可分解为：

• 第二项$\underset{\theta\in\mathbb{R}^d}{\inf} \mathcal{R}(f_{\theta}) - \mathcal{R}^*$ 是由所选的模型集$f_{\theta}$ 产生的不可压缩近似误差.
• 函数$\theta \mapsto \mathcal{R}(f_{\theta}) - \underset{\theta\in\mathbb{R}^d}{\inf} \mathcal{R}(f_{\theta})$ 是$\mathbb{R}^d$ 上的一个正值函数, 通常可以由某个范数（或其平方）$\Omega(\theta - \theta_*)$ 给出上界. 我们可以将上面的第一项$\underset{\theta\in\Theta}{\inf} \mathcal{R}(f_{\theta}) - \underset{\theta\in\mathbb{R}^d}{\inf} \mathcal{R}(f_{\theta})$ 看作是$\theta_*$ 和$\Theta$ 之间的“距离”.

例如: 如果所考虑的损失函数关于第二个变量是$G -$ 利普希茨连续的

$\mathcal{R}(f_{\theta}) - \mathcal{R}(f_{\theta'}) = \mathbb{E}[\ell(y, f_{\theta}(x)) - \ell(y, f_{\theta'}(x))] \leq G\mathbb{E}[|f_{\theta}(x) - f_{\theta'}(x)|]$ , 因此, 近似误差的这第二部分由$G$ 乘以$f_{\theta_*}$ 与$\mathcal{F} = \{f_{\theta}, \theta \in \Theta\}$ 之间的距离给出上界, 这里特定的距离$d(\theta, \theta') = \mathbb{E}[|f_{\theta}(x) - f_{\theta'}(x)|]$ .

一个经典的例子是$f_{\theta}(x) = \theta^{\top} \varphi(x)$ , 且$\Theta = \{\theta \in \mathbb{R}^d, \|\theta\|_2 \leq D\}$ , 这会得到上界$G\mathbb{E}[\|\varphi(x)\|_2](\|\theta_*\|_2 - D)_+$ , 如果$\|\theta_*\|_2 \leq D$ , 该上界等于$0$（模型设定恰当的情况）.

练习: 针对$\Theta$ 上的$\ell_1$ 范数进行相同的计算.

证明: 已知损失函数关于第二个变量是$G -$ 利普希茨连续的, 即

$f_{\theta}(x)=\theta^{\top}\varphi(x)$ , 在本题中我们要考虑$\Theta = \{\theta\in\mathbb{R}^d,\|\theta\|_1\leq D\}$ , 其中$\|\theta\|_1=\sum_{i = 1}^{d}|\theta_i|$ . 设$\theta_*$ 是在$\theta\in\mathbb{R}^d$ 范围内$\mathcal{R}(f_{\theta})$ 的极小值点.

计算$\mathbb{E}[|f_{\theta}(x)-f_{\theta'}(x)|]$

• 首先, $f_{\theta}(x)-f_{\theta'}(x)=\theta^{\top}\varphi(x)-\theta'^{\top}\varphi(x)=(\theta - \theta')^{\top}\varphi(x)=\sum_{i = 1}^{d}(\theta_i-\theta_i')\varphi_i(x)$ .
• 根据绝对值不等式$\left|\sum_{i = 1}^{d}a_ib_i\right|\leq\sum_{i = 1}^{d}|a_i||b_i|$ , 这里$a_i = \theta_i-\theta_i'$ , $b_i=\varphi_i(x)$ , 则$\left|f_{\theta}(x)-f_{\theta'}(x)\right|=\left|\sum_{i = 1}^{d}(\theta_i - \theta_i')\varphi_i(x)\right|\leq\sum_{i = 1}^{d}|\theta_i-\theta_i'||\varphi_i(x)|$ .
• 对其求期望可得$\mathbb{E}[|f_{\theta}(x)-f_{\theta'}(x)|]\leq\mathbb{E}\left[\sum_{i = 1}^{d}|\theta_i-\theta_i'||\varphi_i(x)|\right]=\sum_{i = 1}^{d}|\theta_i-\theta_i'|\mathbb{E}[|\varphi_i(x)|]$ .

计算近似误差上界

• 近似误差的第二部分由$G$ 乘以$f_{\theta_*}$ 与$\mathcal{F} = \{f_{\theta},\theta\in\Theta\}$ 之间的距离给出上界.
• 我们要找$\theta\in\Theta$ 使得$\mathbb{E}[|f_{\theta}(x)-f_{\theta_*}(x)|]$ 最小. 因为$\Theta = \{\theta\in\mathbb{R}^d,\|\theta\|_1\leq D\}$ , 根据$\ell_1$ 范数的性质, $\mathbb{E}[|f_{\theta}(x)-f_{\theta_*}(x)|]\leq\sum_{i = 1}^{d}|\theta_i-\theta_{*,i}|\mathbb{E}[|\varphi_i(x)|]$ .
• 由$\|\theta\|_1=\sum_{i = 1}^{d}|\theta_i|\leq D$ , 我们可以得到近似误差上界为$G\sum_{i = 1}^{d}\mathbb{E}[|\varphi_i(x)|](\|\theta_*\|_1 - D)_+$ , 其中$(a)_+=\max(0,a)$ . 当$\|\theta_*\|_1\leq D$ 时, 上界等于$0$ .

综上, 针对$\Theta$ 上的$\ell_1$ 范数, 近似误差的上界为

估计误差#

估计误差通常利用$g \in \underset{g\in\mathcal{F}}{\arg\min} \mathcal{R}(g)$（我们模型类的期望风险的极小值点）以及$\hat{f} \in \underset{f\in\mathcal{F}}{\arg\min} \widehat{\mathcal{R}}(f)$（经验风险的极小值点）来进行分解：

通常, 该式进一步由$2\sup_{f\in\mathcal{F}} \left|\widehat{\mathcal{R}}(f) - \mathcal{R}(f)\right|$给出上界. 可以得出以下几点结论：

• 当$\hat{f}$不是$\widehat{\mathcal{R}}$的全局极小值点, 而仅仅满足$\widehat{\mathcal{R}}(\hat{f}) \leq \underset{f\in\mathcal{F}}{\inf} \widehat{\mathcal{R}}(f)+\varepsilon$时, 那么优化误差$\varepsilon$必须添加到上述上界中.

• 均匀偏差会随着$\mathcal{F}$的“规模”增大而增加, 并且通常会随着样本数量$n$的增加而减小.

• 一个关键问题是, 我们需要对所有$f \in \mathcal{F}$进行统一控制：对于单个$f$, 我们可以对随机变量$\ell(y, f(x))$应用任何集中不等式, 以得到$O(1/\sqrt{n})$量级的上界；然而, 在控制多个$f$值的最大偏差时, 总是存在一种小概率情况, 即这些偏差中的某一个会变得很大.

MacDiarmid不等式的应用#

麦克迪尔米德不等式： 设$Z_1,\ldots,Z_n$是相互独立的随机变量（在任意可测空间$\mathcal{Z}$中）, 且$f:\mathcal{Z}^n \to \mathbb{R}$是一个“有界变差”函数, 即对于所有的$i$, 以及所有的$z_1,\ldots,z_n,z_i' \in \mathcal{Z}$, 我们有：

$$\left|f(z_1,\ldots,z_{i - 1},z_i,z_{i + 1},\ldots,z_n)-f(z_1,\ldots,z_{i - 1},z_i',z_{i + 1},\ldots,z_n)\right| \leq c$$

那么

$$\mathbb{P}\left(\left|f(Z_1,\ldots,Z_n)-\mathbb{E}f(Z_1,\ldots,Z_n)\right| \geq t\right) \leq 2\exp\left(-2t^2/(nc^2)\right)$$

设$H(z_1, \ldots, z_n)=\sup_{f\in\mathcal{F}} \left\{\mathcal{R}(f) - \widehat{\mathcal{R}}(f)\right\}$, 其中随机变量$z_i=(x_i, y_i)$相互独立且同分布, $\widehat{\mathcal{R}}(f)=\frac{1}{n}\sum_{i = 1}^{n}\ell(y_i, f(x_i))$. 我们用$\ell_{\infty}$表示在数据生成分布的支撑集中, 对于所有$(x, y)$以及$f \in \mathcal{F}$, 损失函数的最大绝对值 .

当将单个$z_i \in \mathcal{X} \times \mathcal{Y}$变为$z_i' \in \mathcal{X} \times \mathcal{Y}$时, $H$的偏差几乎必然至多为$\frac{2}{n}\ell_{\infty}$ .

因此, 应用麦克迪尔米德不等式, 在概率大于$1 - \delta$的情况下, 我们有：

因此, 我们只需要对$\sup_{f\in\mathcal{F}} \{\mathcal{R}(f) - \widehat{\mathcal{R}}(f)\}$ 和$\sup_{f\in\mathcal{F}} \{\widehat{\mathcal{R}}(f) - \mathcal{R}(f)\}$ 的期望进行界定（通常它们会有相同的上界）, 然后在此基础上加上$\frac{\ell_{\infty}\sqrt{2}}{\sqrt{n}}\sqrt{\log\frac{1}{\delta}}$ .

二次函数#

我们将展示在二次损失函数和$\ell_2$球约束下的情况. 我们记得在这种情况下, $\ell(y, \theta^{\top}\varphi(x)) = (y - \theta^{\top}\varphi(x))^2$ . 由此我们得到：

因此, 上确界可以用封闭形式给出上界：

其中$\|M\|_{\text{op}}$是矩阵$M$的算子范数, 定义为$\|M\|_{\text{op}} = \sup_{\|u\|_2 = 1}\|Mu\|_2$ .

因此, 为了得到一个一致的上界, 我们只需要对这三个非一致的偏差期望进行上界界定, 它们的阶数为$O(1/\sqrt{n})$, 这样我们就能得到一个整体的一致偏差上界. 对于这种特殊情况, 得到$O(1/\sqrt{n})$的收敛速度是可能的, 但对于除二次损失之外的其他类型的损失函数, 要得到这样的收敛速度通常是不可能的.

练习: 给出上述$\sup_{\|\theta\|_2\leq D}|\mathcal{R}(f) - \widehat{\mathcal{R}}(f)|$ 的显式上界, 并将其与4.5节中拉德马赫复杂度的应用进行比较. 可以使用1.2.3节中关于矩阵平均值的集中不等式.

证明: 计算$\sup_{\|\theta\|_2\leq D}|\mathcal{R}(f) - \widehat{\mathcal{R}}(f)|$的显式上界 已知

第一项： 设$M_n=\frac{1}{n}\sum_{i = 1}^{n}\varphi(x_i)\varphi(x_i)^{\top}$, $M_0 = \mathbb{E}[\varphi(x)\varphi(x)^{\top}]$. 根据矩阵的集中不等式, 对于独立同分布的矩阵随机变量$\varphi(x_i)\varphi(x_i)^{\top}$, 在一定条件下（如$\varphi(x)$的各元素有界等）, 存在常数$C_1$使得