机器学习

泛化

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

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

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

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

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

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

形式化

问题形式化

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

两点说明：

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

学习成功

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

\begin{align} h^\star = \argmin_{h \in \hc} R(h) = \argmin_{h \in \hc} \eb_{(\xv, y) \sim \ds}[\ib (h(\xv) \ne y)] \end{align}

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

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

退而求其次

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

PAC 学习框架

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

\begin{align} \pb_{\dc \sim \ds^m} [\underbrace{R(h_\dc) - R(h^\star) \le \epsilon}_{近似正确}] \ge \underbrace{1 - \delta}_{大概率} \end{align}

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

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

A：有点复杂，一步步来

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

PAC 学习框架

Q：首先我们能做什么？

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

\begin{align} R_\dc (h) = \frac{1}{m} \sum_{i \in [m]} \ib(h(\xv_i) \ne y_i) \end{align}

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

A：给定$h$，经验风险是关于$\dc$的随机变量，期望是泛化风险

\begin{align} \eb_{\dc \sim \ds^m} [R_\dc (h)] & = \eb_{(\xv_i ,y_i) \sim \ds} \left[ \frac{1}{m} \sum_{i \in [m]} \ib(h(\xv_i) \ne y_i) \right] \\ & = \eb_{(\xv_i ,y_i) \sim \ds} [\ib(h(\xv_i) \ne y_i)] = R(h) \end{align}

PAC 学习框架

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

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

Q：是否有刻画随机变量偏离期望的数学工具从而可以控制误差？

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

霍弗丁不等式：设随机变量 $X_1, \ldots, X_m$相互独立，$X_i \in [a_i, b_i]$，记$S_m = \sum_{i \in [m]} X_i$，对任意$\epsilon > 0$有

\begin{align} & \pb [S_m - \eb[S_m] \ge \epsilon] \le e^{-2 \epsilon^2 / \sum_{i \in [m]} (b_i - a_i)^2} \\ & \pb [S_m - \eb[S_m] \le -\epsilon] \le e^{-2 \epsilon^2 / \sum_{i \in [m]} (b_i - a_i)^2} \end{align}

PAC 学习框架

给定$h$，经验风险$R_\dc(h) = \sum_{i \in [m]} \frac{\ib(h(\xv_i) \ne y_i)}{m}$是$m$个相互独立的随机变量 和，每个$\in [0, \frac{1}{m}]$，由霍弗丁不等式可得

\begin{align} & \pb_{\dc \sim \ds^m} [R_\dc(h) - R(h) \ge \epsilon] \le e^{-2 m \epsilon^2} \\ & \pb_{\dc \sim \ds^m} [R_\dc(h) - R(h) \le -\epsilon] \le e^{-2 m \epsilon^2} \end{align}

根据联合界 (union bound)：$\pb[A \vee B] \le \pb[A] + \pb[B]$可得

\begin{align} \pb_{\dc \sim \ds^m} [|R_\dc(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} (1) \quad \pb_{\dc \sim \ds^m} \left[ |R_\dc(h) - R(h)| \le \sqrt{\frac{\ln (2 / \delta)}{2m}} \right] \ge 1 - \delta \end{align}

PAC 学习框架

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

A：尝试引入$R_\dc(h_\dc)$作为桥接

\begin{align} R(h_\dc) - R(h^\star) & = R(h_\dc) - R_\dc(h_\dc) + R_\dc(h_\dc) - R(h^\star) \\ & \le R(h_\dc) - R_\dc(h_\dc) + R_\dc(h^\star) - R(h^\star) \end{align}

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

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

\begin{align} h_\dc^\erm = \argmin_{h \in \hc} R_\dc(h) \end{align}

PAC 学习框架

Q：目前已有

\begin{align} R(h_\dc^\erm) - R(h^\star) \le R(h_\dc^\erm) - R_\dc(h_\dc^\erm) + R_\dc(h^\star) - R(h^\star) \end{align}

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

A：$h_\dc^\erm$依赖于$\dc$，式$(1)$不可用，$h^\star$独立于$\dc$，是可以用的

式$(1)$用了霍弗丁不等式，前提是$\eb_{\dc \sim \ds^m} [R_\dc (h)] = R(h)$，注意下面两式的区别

\begin{align} & \eb_{\dc \sim \ds^m} [R_\dc (h)] = \pb[\dc_1] R_{\dc_1} (h) + \pb[\dc_2] R_{\dc_2} (h) + \cdots \\[4pt] & \eb_{\dc \sim \ds^m} [R_\dc (h_\dc^\erm)] = \pb[\dc_1] R_{\dc_1} (h_{\dc_1}^\erm) + \pb[\dc_2] R_{\dc_2} (h_{\dc_2}^\erm) + \cdots \end{align}

PAC 学习框架

Q：如何让式$(1)$对$h_\dc^\erm$也能用？

A：$h_\dc^\erm$是从$\hc$中得到的，如果$\hc$中的所有模型都满足式$(1)$，那问题就解决了，但这对$\hc$的要求就太苛刻了，故将其放松成有限集合，再次根据联合界有

\begin{align} \pb_{\dc \sim \ds^m} [\exists h \in \hc: |R_\dc(h) - R(h)| \ge \epsilon] & \le \sum_{h \in \hc} \pb_{\dc \sim \ds^m} [ |R_\dc(h) - R(h)| \ge \epsilon] \\ & \le |\hc| 2 e^{-2 m \epsilon^2} \end{align}

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

\begin{align} (2) \quad \pb_{\dc \sim \ds^m} \left[ |R_\dc(h) - R(h)| \le \sqrt{\frac{\ln (2 |\hc| / \delta)}{2m}} \right] \ge 1 - \delta \end{align}

PAC 学习框架

式$(2)$对$h_\dc^\erm$、$h^\star$均可用，于是

\begin{align} R(h_\dc^\erm) - R(h^\star) & \le |R(h_\dc^\erm) - R_\dc(h_\dc^\erm)| + |R_\dc(h^\star) - R(h^\star)| \\ & \le 2 \max_{h \in \hc} |R_\dc(h) - R(h)| \\ & \le \sqrt{\frac{2\ln (2 |\hc| / \delta)}{m}} ~ with ~ probability \ge 1 - \delta \end{align}

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

\begin{align} \pb_{\dc \sim \ds^m} [R(h_\dc^\erm) - R(h^\star) \le \epsilon] \ge 1 - \delta \end{align}

无限假设空间

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

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

\begin{align} \pb_{\dc \sim \ds^m} [\exists h \in \hc: |R_\dc(h) - R(h)| \ge \epsilon] \le |\hc| 2 e^{-2 m \epsilon^2} \end{align}

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

\begin{align} \Pi_\hc (m) = \max_{\dc \sim \ds^m} |\{ [h(\xv_1), \ldots, h(\xv_m)] \mid h \in \hc \}| \end{align}

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

无限假设空间

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

\begin{align} \pb_{\dc \sim \ds^m} [\exists h \in \hc: |R_\dc(h) - R(h)| \ge \epsilon] \le 4 \Pi_\hc (2m) e^{-m \epsilon^2 / 8} \end{align}

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

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

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

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

无限假设空间

综合前面的所有结果有

\begin{align} \pb_{\dc \sim \ds^m} [\exists h \in \hc: |R_\dc(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} \sup_{h \in \hc} |R_\dc(h) - R(h)| \le \sqrt{\frac{8 d \ln (2em/d) + 8 \ln (4/\delta)}{m}} \end{align}

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

\begin{align} R(h_\dc^\erm) - R(h^\star) \le \sqrt{\frac{32 d \ln (2em/d) + 32 \ln (4/\delta)}{m}} \end{align}

模型选择

设$\vc(\hc) = d$，ERM 算法至少以$1 - \delta$的概率有

\begin{align} & R (h_\dc^\erm) \le R_\dc (h_\dc^\erm) + \sqrt{\frac{8 d \ln (2em/d) + 8 \ln (4/\delta)}{m}} \\ & R(h_\dc^\erm) \le R(h^\star) + \sqrt{\frac{32 d \ln (2em/d) + 32 \ln (4/\delta)}{m}} \end{align}

启示

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

欠拟合 过拟合

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

学习算法：$\class{blue}{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)：将训练集平均分为$k$份，第$i$轮

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

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

偏差方差分解

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

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

其中条件期望$\class{blue}{\eb [y|\xv]}$与$\class{blue}{y}$无关，对交叉项有

\begin{align} \eb_{(\xv,y) \sim \ds} & [(f (\xv) - \eb [y|\xv]) (\eb [y|\xv] - y) ] \\ & = \iint (f (\xv) - \eb [y|\xv]) (\eb [y|\xv] - y) p(\xv, y) \diff \xv \diff y \\ & = \int (f (\xv) - \eb [y|\xv]) \left( \int (\eb [y|\xv] - y) p(\xv, y) \diff y \right) \diff \xv \\ & = \int (f (\xv) - \eb [y|\xv]) \underbrace{ ( \eb [y|\xv] p(\xv) - p(\xv) \overbrace{ \class{yellow}{\int y \cdot p(y|\xv) \diff y}}^{=~\eb [y|\xv]} )}_{=~0} \diff \xv = 0 \end{align}

偏差方差分解

\begin{align} \eb_{(\xv,y)} [(f (\xv) - y)^2] & = \eb_{(\xv,y)} [(\overbrace{f (\xv) - \eb [y|\xv]}^{与y无关})^2] + \overbrace{\eb_{(\xv,y)} [(\eb [y|\xv] - y)^2]}^{与f无关} \\ & = \eb_\xv [(f (\xv) - \eb [y|\xv])^2] + 噪声 \end{align}

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

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

\begin{align} E = \eb_\dc \eb_{(\xv,y)} [(f_\dc (\xv) - y)^2] = \eb_\xv \eb_\dc [(f_\dc (\xv) - \eb [y|\xv])^2] + 噪声 \end{align}

偏差方差分解

泛化均方误差$E = \eb_\xv \eb_\dc [(f_\dc (\xv) - \eb [y|\xv])^2] + 噪声$

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

\begin{align} (f_\dc (\xv) - \eb [y|\xv])^2 & = (f_\dc (\xv) - \eb_\dc [f_\dc (\xv)] + \eb_\dc [f_\dc (\xv)] - \eb [y|\xv])^2 \\ & = (f_\dc (\xv) - \eb_\dc [f_\dc (\xv)])^2 + (\eb_\dc [f_\dc (\xv)] - \eb [y|\xv])^2 \\ & \qquad + 2 (f_\dc (\xv) - \eb_\dc [f_\dc (\xv)]) (\eb_\dc [f_\dc (\xv)] - \eb [y|\xv]) \end{align}

注意$\class{blue}{\eb_\dc [f_\dc (\xv)]}$与$\class{blue}{\dc}$无关，对交叉项有

\begin{align} \eb_\dc [(f_\dc (\xv) - \eb_\dc [& f_\dc (\xv)]) (\overbrace{\eb_\dc [f_\dc (\xv)] - \eb [y|\xv]}^{与\dc无关})] \\ & = (\eb_\dc [f_\dc (\xv)] - \eb [y|\xv]) \underbrace{\eb_\dc [f_\dc (\xv) - \eb_\dc [f_\dc (\xv)]]}_{=~0} = 0 \end{align}

偏差方差分解

\begin{align} E & = \eb_\xv \eb_\dc [(f_\dc (\xv) - \eb_\dc [f_\dc (\xv)])^2] + \eb_\xv \eb_\dc [(\overbrace{\eb_\dc [f_\dc (\xv)] - \eb [y|\xv]}^{与\dc无关})^2] + 噪声 \\ & = \underbrace{\eb_\xv \eb_\dc [(f_\dc (\xv) - \eb_\dc [f_\dc (\xv)])^2]}_{方差} + \underbrace{\eb_\xv [(\eb_\dc [f_\dc (\xv)] - \eb [y|\xv])^2]}_{偏差^2} + 噪声 \end{align}

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

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

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

偏差方差分解

偏差方差窘境

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

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