机器学习

泛化

NFL 定理的例子表明，在已知数据上表现好不算什么

设$D = \{ (\xv_i, y_i) \}_{i \in [m]}$，$D^+ = \{ \xv_i \mid y_i = 1 \}$、$D^- = \{ \xv_i \mid y_i = -1 \}$

$$ \begin{align*} \quad h(\xv) = - \prod_{i: y_i = 1} \| \xv - \xv_i \| \begin{cases} = 0, & \text{若 } \xv \in D^+ \\ < 0, & \text{若 } \xv \in D^- \end{cases} \end{align*} $$

易知$\sgn(h(\xv))$在任意数据集上都可以做到百分百对，但它没有在学习，他只是记住了数据集中的正样本，没有任何预测能力

机器学习的最终目的是要模型在未知数据上表现好，即所谓的泛化性能 (generalization performance) 好

• 根据历史天气数据训练的模型是为了预测准明后天的天气
• 根据历史交易数据训练的模型是为了预测准明后天的涨跌

形式化

问题形式化

• $\Xcal$为样本空间，$\Ycal$为标记集合
• $\Dcal$为定义在$\Xcal \times \Ycal$上的未知概率分布
• $D = \{ (\xv_i, y_i) \}_{i \in [m]}$为独立同分布 (iid) 采样于$\Dcal$的训练数据集
• $\Hcal = \{ h: \Xcal \mapsto \Ycal \}$是候选模型构成的假设空间
• $R(h) = \Ebb_{(\xv, y) \sim \Dcal}[\Ibb (h(\xv) \ne y)]$为模型$h$的泛化风险 (generalization risk)
• $\min_{h \in \Hcal} R(h)$就是机器学习的目标：泛化风险最小化

两点说明：

1. 训练样本$(\xv_i, y_i) \overset{\mathrm{iid}}{\sim} \Dcal$以及计算泛化风险的$(\xv, y) \sim \Dcal$是学习的前提
2. 数据分布$\Dcal$定义在$\Xcal \times \Ycal$上，即允许不同的样本有相同的$\xv$、不同的$y$，这种设定称为不可知 (agnostic) 学习；若$\Dcal$只定义在$\Xcal$上，类标记由未知函数$c: \Xcal \mapsto \Ycal$给出，则相同的$\xv$必然有相同的$y$，这种设定比前者要简单

学习成功

Q：如何定义“学习成功”？记假设空间$\Hcal$中的最优模型为

$$ \begin{align*} \quad h^\star = \argmin_{h \in \Hcal} R(h) = \argmin_{h \in \Hcal} \Ebb_{(\xv, y) \sim \Dcal}[\Ibb (h(\xv) \ne y)] \end{align*} $$

把$h^\star$求出来就算成功了吗？

A：数据分布$\Dcal$未知，泛化风险无法计算，$h^\star$不可求

退而求其次

• 训练数据集$D$只有有限个样本，或许$\Hcal$中有多个模型与$h^\star$表现相同，算法根本没法区分它们的好坏，因此不要求算法输出$h^\star$，只要输出的模型与$h^\star$差别不大就算学习成功
• 训练数据集$D$是依未知分布$\Dcal$有限次采样得到的，不排除采出很差数据集的可能 (例如全是正类)，因此不要求算法每次都能对随机采样的$D$学习成功，只要求失败的概率不大即可

PAC 学习框架

概率近似正确 (probably approximately correct, PAC) 学习框架

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [\underbrace{R(h_D) - R(h^\star) \le \epsilon}_{\text{近似正确}}] \ge \underbrace{1 - \delta}_{\text{大概率}} \end{align*} $$

Q：给定某个任务，算法能输出满足上式的$h_D$就算学习成功，那如何判断一个任务是“可学习”的？

换言之，给定某个任务和任意正数$\epsilon$、$\delta$，如何判断这样的算法存在？数据集$D$、假设空间$\Hcal$是否需满足一些条件？

A：有点复杂，一步步来

PAC 学习框架由英国皇家学会会员、美国科学院院士、哈佛大学教授 Leslie Valiant 于 1984 年提出，是计算学习理论的奠基性工作，Leslie Valiant 教授也因此获得了 2010 年图灵奖。

PAC 学习框架

Q：首先我们能做什么？

A：对任意$h$，能求的只有经验风险 (empirical risk)

$$ \begin{align*} \quad R_D (h) = \frac{1}{m} \sum_{i \in [m]} \Ibb(h(\xv_i) \ne y_i) \end{align*} $$

Q：经验风险和泛化风险的关系是什么？

A：给定$h$，经验风险是关于$D$的 r.v.，期望是泛化风险

$$ \begin{align*} \quad \Ebb_{D \sim \Dcal^m} [R_D (h)] & = \Ebb_{(\xv_i ,y_i) \sim \Dcal} \left[ \frac{1}{m} \sum_{i \in [m]} \Ibb(h(\xv_i) \ne y_i) \right] \\ & = \Ebb_{(\xv_i ,y_i) \sim \Dcal} [\Ibb(h(\xv_i) \ne y_i)] = R(h) \end{align*} $$

PAC 学习框架

Q：是否可以用经验风险替代泛化风险？

A：这样做肯定会引入误差，但 PAC 学习框架本来也是允许有误差的，只是误差要可控

Q：是否有刻画 r.v. 偏离期望的数学工具从而可以控制误差？

A：集中不等式 (concentration inequality) 就是这样一类工具

Hoeffding's 不等式：设 r.v. $X_1, \ldots, X_m$相互独立，$X_i \in [a_i, b_i]$，记$S_m = \sum_{i \in [m]} X_i$，对任意$\epsilon > 0$有

$$ \begin{align*} \quad & \Pbb [S_m - \Ebb[S_m] \ge \epsilon] \le e^{-2 \epsilon^2 / \sum_{i \in [m]} (b_i - a_i)^2} \\ & \Pbb [S_m - \Ebb[S_m] \le -\epsilon] \le e^{-2 \epsilon^2 / \sum_{i \in [m]} (b_i - a_i)^2} \end{align*} $$

PAC 学习框架

给定$h$，经验风险$R_D(h) = \sum_{i \in [m]} \frac{\Ibb(h(\xv_i) \ne y_i)}{m}$是$m$个相互独立的 r.v. 和，每个$\in [0, \frac{1}{m}]$，由 Hoeffding's 不等式可得

$$ \begin{align*} \quad & \Pbb_{D \sim \Dcal^m} [R_D(h) - R(h) \ge \epsilon] \le e^{-2 m \epsilon^2} \\ & \Pbb_{D \sim \Dcal^m} [R_D(h) - R(h) \le -\epsilon] \le e^{-2 m \epsilon^2} \end{align*} $$

根据 union bound：$\Pbb[A \cup B] \le \Pbb[A] + \Pbb[B]$可得

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [|R_D(h) - R(h)| \ge \epsilon] \le 2 e^{-2 m \epsilon^2} \end{align*} $$

令$2 e^{-2 m \epsilon^2} = \delta$可得$\epsilon = \sqrt{\frac{\ln (2 / \delta)}{2m}}$，综上对任意给定的$h$有

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} \left[ |R_D(h) - R(h)| \le \sqrt{\frac{\ln (2 / \delta)}{2m}} \right] \ge 1 - \delta \tag {1} \end{align*} $$

PAC 学习框架

Q：式$(1)$已经接近 PAC 学习框架的形式了，但式$(1)$中是同一个模型$h$的经验风险、泛化风险相减，而 PAC 学习框架中是输出模型$h_D$和最优模型$h^\star$的泛化风险相减，如何将其联系起来？

A：尝试引入$R_D(h_D)$作为桥接

$$ \begin{align*} \quad R(h_D) - R(h^\star) & = R(h_D) - R_D(h_D) + R_D(h_D) - R(h^\star) \\ & \le R(h_D) - R_D(h_D) + R_D(h^\star) - R(h^\star) \tag {2} \end{align*} $$

如果式$(2)$能成立，目标就变成了两项之和，都是同一个模型的经验风险、泛化风险相减，式$(1)$或许就可以用起来了

欲使$R_D(h_D) \le R_D(h^\star)$，只需令$h_D$为经验风险最小化模型

$$ \begin{align*} \quad h_D^{\text{ERM}} = \argmin_{h \in \Hcal} R_D(h) \end{align*} $$

PAC 学习框架

Q：目前已有

$$ \begin{align*} \quad R(h_D^{\text{ERM}}) - R(h^\star) \le R(h_D^{\text{ERM}}) - R_D(h_D^{\text{ERM}}) + R_D(h^\star) - R(h^\star) \end{align*} $$

是不是再代入两遍式$(1)$就搞定了？

A：$h_D^{\text{ERM}}$依赖于$D$，式$(1)$不可用，$h^\star$独立于$D$，是可以用的

式$(1)$用了 Hoeffding's 不等式，前提是$\Ebb_{D \sim \Dcal^m} [R_D (h)] = R(h)$，注意下面两式的区别

$$ \begin{align*} \quad & \Ebb_{D \sim \Dcal^m} [R_D (h)] = \Pbb[D_1] R_{D_1} (h) + \Pbb[D_2] R_{D_2} (h) + \cdots \\[4pt] & \Ebb_{D \sim \Dcal^m} [R_D (h_D^{\text{ERM}})] = \Pbb[D_1] R_{D_1} (h_{D_1}^{\text{ERM}}) + \Pbb[D_2] R_{D_2} (h_{D_2}^{\text{ERM}}) + \cdots \end{align*} $$

PAC 学习框架

Q：如何让式$(1)$对$h_D^{\text{ERM}}$也能用？

A：$h_D^{\text{ERM}}$是从$\Hcal$中得到的，如果$\Hcal$中的所有模型都满足式$(1)$，那问题就解决了，但这对$\Hcal$的要求就太苛刻了，故将其放松成有限集合，再次根据 union bound 有

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [\exists h \in \Hcal: |R_D(h) - R(h)| \ge \epsilon] & \le \sum_{h \in \Hcal} \Pbb_{D \sim \Dcal^m} [ |R_D(h) - R(h)| \ge \epsilon] \\ & \le |\Hcal| 2 e^{-2 m \epsilon^2} \end{align*} $$

令$|\Hcal| 2 e^{-2 m \epsilon^2} = \delta$可得$\epsilon = \sqrt{\frac{\ln (2 |\Hcal| / \delta)}{2m}}$，故对$\forall h \in \Hcal$有

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} \left[ |R_D(h) - R(h)| \le \sqrt{\frac{\ln (2 |\Hcal| / \delta)}{2m}} \right] \ge 1 - \delta \tag {2} \end{align*} $$

PAC 学习框架

式$(2)$对$h_D^{\text{ERM}}$、$h^\star$均可用，于是

$$ \begin{align*} \quad R(h_D^{\text{ERM}}) - R(h^\star) & \le |R(h_D^{\text{ERM}}) - R_D(h_D^{\text{ERM}})| + |R_D(h^\star) - R(h^\star)| \\ & \le 2 \max_{h \in \Hcal} |R_D(h) - R(h)| \\ & \le \sqrt{\frac{2\ln (2 |\Hcal| / \delta)}{m}} \text{ with probability} \ge 1 - \delta \end{align*} $$

综上给定任务和$\epsilon$、$\delta$，若$\Hcal$有限且样本数$m \ge \frac{2 \ln (2 |\Hcal| / \delta)}{\epsilon^2}$，则该任务是可学习的，ERM 算法可以学习成功

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [R(h_D^{\text{ERM}}) - R(h^\star) \le \epsilon] \ge 1 - \delta \end{align*} $$

无限假设空间

通常学习任务面临的$\Hcal$都是无限的

之前用来证明下式的 union bound 不能再用，否则右边是无穷大

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [\exists h \in \Hcal: |R_D(h) - R(h)| \ge \epsilon] \le |\Hcal| 2 e^{-2 m \epsilon^2} \end{align*} $$

我们需设法将$\Hcal$的无穷归约到有穷，注意训练样本是有穷的，因此定义增长函数 (growth function) 为$\Hcal$对$m$个样本的最大不同预测结果数

$$ \begin{align*} \quad \Pi_{\Hcal} (m) = \max_{D \sim \Dcal^m} |\{ [h(\xv_1), \ldots, h(\xv_m)] \mid h \in \Hcal \}| \end{align*} $$

这相当于将$\Hcal$中无穷多的模型分成了$\Pi_{\Hcal} (m)$类，对样本预测结果相同的都看成一类

无限假设空间

1971 年，支持向量机的提出者 Vladimir Vapnik 教授证明了

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [\exists h \in \Hcal: |R_D(h) - R(h)| \ge \epsilon] \le 4 \Pi_{\Hcal} (2m) e^{-m \epsilon^2 / 8} \end{align*} $$

1972 年，Sauer 教授证明了增长函数的上界

$$ \begin{align*} \quad \Pi_{\Hcal} (m) \le \sum_{i=0}^d \binom{m}{i} \le \left( \frac{em}{d} \right)^d \end{align*} $$

其中$d$为$\Hcal$的$\text{VC}$维，$\text{VC} (\Hcal) = \max \{ m: \Pi_{\Hcal} (m) = 2^m \}$

$\Pi_{\Hcal} (m)$和$\text{VC} (\Hcal)$都是用来度量假设空间$\Hcal$的表示能力的，越大说明$\Hcal$适应不同任务的能力越强，此外，还有 Rademacher 复杂度、packing number、covering number 等工具，都是类似的作用

无限假设空间

综合前面的所有结果有

$$ \begin{align*} \quad \Pbb_{D \sim \Dcal^m} [\exists h \in \Hcal: |R_D(h) - R(h)| \ge \epsilon] \le 4 \left( \frac{2em}{d} \right)^d e^{-m \epsilon^2 / 8} \end{align*} $$

令右边为$\delta$得$\epsilon = \sqrt{\frac{8 d \ln (2em/d) + 8 \ln (4/\delta)}{m}}$，故至少以$1 - \delta$的概率有

$$ \begin{align*} \quad \mathrm{sup}_{h \in \Hcal} |R_D(h) - R(h)| \le \sqrt{\frac{8 d \ln (2em/d) + 8 \ln (4/\delta)}{m}} \end{align*} $$

仿照前面的推理可知至少以$1 - \delta$的概率有

$$ \begin{align*} \quad R(h_D^{\text{ERM}}) - R(h^\star) \le \sqrt{\frac{32 d \ln (2em/d) + 32 \ln (4/\delta)}{m}} \end{align*} $$

模型选择

设$\text{VC}(\Hcal) = d$，ERM 算法至少以$1 - \delta$的概率有

$$ \begin{align*} \quad & R (h_D^{\text{ERM}}) \le R_D (h_D^{\text{ERM}}) + \sqrt{\frac{8 d \ln (2em/d) + 8 \ln (4/\delta)}{m}} \\ & R(h_D^{\text{ERM}}) \le R(h^\star) + \sqrt{\frac{32 d \ln (2em/d) + 32 \ln (4/\delta)}{m}} \end{align*} $$

启示

• 右边第一项随$\Hcal$复杂度的增加而减小，第二项随$\Hcal$复杂度的增加而增大，因此选择假设空间时既不能太复杂、也不能太简单，要跟任务相适应
• 样本数$m$可以一定程度上制衡$\Hcal$的复杂度，因此当数据量很大时，可以选择较复杂的$\Hcal$，这也解释了为何深度神经网络在大数据集上表现更好

欠拟合 过拟合

数据分布：$p(x) = \Ucal[0,1]$，$y = \cos (3 \pi x / 2) + \Ncal(0, 1) / 10$

学习算法：$n$阶多项式回归

$$ \begin{align*} \min_{w_j} ~ F (w_j) = \frac{1}{2} \sum_{i \in [m]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right)^2 \end{align*} $$

其中$w_0, w_1, \ldots, w_n$为待求参数

假设空间

• 1 阶多项式
• 4 阶多项式
• 30 阶多项式

欠拟合 过拟合

左图：1 阶多项式欠拟合 (underfitting)，经验均方误差很大

中图：4 阶多项式拟合地最好，最贴近真实模型

右图：30 阶多项式过拟合 (overfitting)，经验均方误差很小

选对假设空间至关重要！

模型选择 验证

事先确定一组候选模型集合$\{ f_1, f_2, \ldots, f_n \}$，从中挑选最好的

从训练集中随机选择一部分样本作为验证集 (validation set)

• 在剩余的训练集上依次训练$f_1, f_2, \ldots, f_n$
• 在验证集上依次评估$f_1, f_2, \ldots, f_n$

交叉验证 (cross validation)：将训练集平均分为$n$份，第$i$轮

• 在其中的第$[n] \setminus \{ i \}$份上依次训练$f_1, f_2, \ldots, f_n$
• 在第$i$份上依次评估$f_1, f_2, \ldots, f_n$

遍历$i \in [n]$取平均作为$f_1, f_2, \ldots, f_n$的性能，从中挑选最好的

偏差方差分解

以回归问题为例，对任意样本$(\xv,y) \sim \Dcal$，均方误差可分解为

$$ \begin{align*} \quad (f (\xv) & - y)^2 = (f (\xv) - \Ebb [y|\xv] + \Ebb [y|\xv] - y)^2 \\ & = (f (\xv) - \Ebb [y|\xv])^2 + (\Ebb [y|\xv] - y)^2 + 2 (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) \end{align*} $$

其中条件期望$\Ebb [y|\xv]$与$y$无关，对交叉项有

$$ \begin{align*} \quad \Ebb_{(\xv,y) \sim \Dcal} & [(f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) ] \\ & = \iint (f (\xv) - \Ebb [y|\xv]) (\Ebb [y|\xv] - y) p(\xv, y) \diff \xv \diff y \\ & = \int (f (\xv) - \Ebb [y|\xv]) \left( \int (\Ebb [y|\xv] - y) p(\xv, y) \diff y \right) \diff \xv \\ & = \int (f (\xv) - \Ebb [y|\xv]) \underbrace{ ( \Ebb [y|\xv] p(\xv) - p(\xv) \overbrace{ \class{yellow}{\int y \cdot p(y|\xv) \diff y}}^{=~\Ebb [y|\xv]} )}_{=~0} \diff \xv = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} \quad \Ebb_{(\xv,y)} [(f (\xv) - y)^2] & = \Ebb_{(\xv,y)} [(\overbrace{f (\xv) - \Ebb [y|\xv]}^{\text{与}y\text{无关}})^2] + \overbrace{\Ebb_{(\xv,y)} [(\Ebb [y|\xv] - y)^2]}^{\text{与}f\text{无关}} \\ & = \Ebb_{\xv} [(f (\xv) - \Ebb [y|\xv])^2] + \text{噪声} \end{align*} $$

• 根据第一项，使得泛化均方误差最小的$f^\star (\xv) = \Ebb [y|\xv]$，但由于真实分布$p(y|\xv)$未知，因此没法计算$\Ebb [y|\xv]$，$f^\star (\xv)$不可求
• 第二项噪声是不可知 (agnostic) 学习固有的，只和真实分布有关，与模型无关

上面的式子是针对给定模型的，算法在不同数据集$D$上得到的模型$f_D$也不同，因此泛化均方误差

$$ \begin{align*} \quad E & = \Ebb_D \Ebb_{(\xv,y)} [(f_D (\xv) - y)^2] \\ & = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \text{噪声} \end{align*} $$

偏差方差分解

泛化均方误差$E = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb [y|\xv])^2] + \text{噪声}$

引入$\xv$的期望预测$\Ebb_D [f_D (\xv)]$，易知有分解

$$ \begin{align*} \quad (f_D (\xv) - \Ebb [y|\xv])^2 & = (f_D (\xv) - \Ebb_D [f_D (\xv)] + \Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & = (f_D (\xv) - \Ebb_D [f_D (\xv)])^2 + (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2 \\ & \qquad + 2 (f_D (\xv) - \Ebb_D [f_D (\xv)]) (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \end{align*} $$

注意$\Ebb_D [f_D (\xv)]$与$D$无关，对交叉项有

$$ \begin{align*} \quad \Ebb_D [(f_D (\xv) - \Ebb_D [& f_D (\xv)]) (\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\text{与}D\text{无关}})] \\ & = (\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]) \underbrace{\Ebb_D [f_D (\xv) - \Ebb_D [f_D (\xv)]]}_{=~0} = 0 \end{align*} $$

偏差方差分解

$$ \begin{align*} E & = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2] + \Ebb_{\xv} \Ebb_D [(\overbrace{\Ebb_D [f_D (\xv)] - \Ebb [y|\xv]}^{\text{与}D\text{无关}})^2] + \text{噪声} \\ & = \underbrace{\Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]}_{\text{方差}} + \underbrace{\Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]}_{\text{偏差 }^2} + \text{噪声} \end{align*} $$

综上，泛化均方误差可分解为$E = \text{偏差}^2 + \text{方差} + \text{噪声}$

• $\text{偏差}^2 = \Ebb_{\xv} [(\Ebb_D [f_D (\xv)] - \Ebb [y|\xv])^2]$，期望预测与最优模型预测的差别，体现学习算法的拟合能力，越小拟合能力越强
• $\text{方差} = \Ebb_{\xv} \Ebb_D [(f_D (\xv) - \Ebb_D [f_D (\xv)])^2]$，$D$上模型的预测与期望预测的差别，体现学习算法对数据集扰动的敏感度，越小越不敏感

我们要选择低偏差同时低方差的模型！

偏差方差分解

偏差方差窘境

偏差、方差往往是两难选择，即便对于单模型亦存在

• 训练不足时，模型还很糙，拟合能力不强，偏差占主导
• 训练程度加深后，模型开始捕捉数据细节，方差占主导