机器学习物语(2)：大数定理军团

机器学习理论帝国崛起，大数定理军团功不可没，称之为军团毫不夸张，在前军先锋强大数定理和副将弱大数定理后面，是铠甲上刻着“Concentration of Measure”的古老印记的战士们，不妨暂且忽略他们之间乱七八糟的“血缘”关系，而罗列一些名字：Chebyshev 不等式、 Markov 不等式、 Bernstein 不等式、 Hoeffding 不等式、 McDiarmid 不等式、 Chernoff 不等式……虽然他们之间互相关系微妙，但是在战斗中却是各有千秋，特别是在装备了现代化的“大规模杀伤性武器”——一致收敛性之后，……写不下去了，我这点文学功底，果然连 yy 小说也没法写的。 :p

总而言之，我们这次的主角是大数定理 (Law of Large Numbers, LLN)，以及它们在学习理论中如何起到关键作用。不妨先来看看大数定理吧：

直观来说，就是随着 $n$ 增大，由采用数据估计出来的平均值 $\mu_n$ 会越来越接近真实平均值 $\mu$ 。强大数定理可以（用 Egorov 定理）推出弱大数定理。这在机器学习里有什么用呢？上一次我们已经稍微做了一点剧透，这一次让我们来仔细研究一下这个问题，一切还得从 Empirical Risk Minimization (ERM) 说起。

我们上次提到过，ERM 就是根据训练数据 $S_n=\{(x_i,y_i)\}_{i=1}^n$ 在给定的函数空间 $\mathcal{F}$ 中寻找最小化经验误差

\[
R_n(f)=\frac{1}{n}\sum_{i=1}^n\ell_f(x_i,y_i)
\]

的函数 $f_n^*$ 的过程。由于 $S_n$ 是已知的，所以 $R_n$ 是可以求值的，于是 ERM 就可以做了——当然这只是从理论上来说，比如，具体到二分类和 0-1 loss 函数的话，做 ERM 的优化是一个组合问题，非常困难；另外， ERM 问题经常都是 ill-conditioned ，不太容易直接求解。不过关于这些问题的解决方案不是今天要讲的内容，而是要留到将来了。

虽然 ERM 算法看起来很自然，但是他是不是一个好的算法呢？回忆一下我们在世界观设定中提到的 supervised learning 的目的是最小化 Risk $R(f)$ ，所以，现在需要检查的问题就是，通过 ERM 算法求出来的 $f_n^*$ ，其 Risk 是不是也比较小呢？和最优的 Bayes Risk $R^*$ 或者在 $\mathcal{F}$ 里能达到的最优 Risk $R_\mathcal{R}$ 差多少呢？首先来看 Bayes Risk

\[
R(f_n^*)-R^* = \color{red}{R(f_n^*)-R_\mathcal{F}} + \color{blue}{R_\mathcal{F}}-R^*
\]

这里右边红色的项叫做 estimation error ，因为它是由通过训练数据 $S_n$ 去进行 estimate 造成的误差，而蓝色的项叫做 approximation error ，注意到它与具体的训练数据无关，而只与函数空间 $\mathcal{F}$ 的选取有关，它的名字的由来是表示这是用 $\mathcal{F}$ 中的函数去对 Bayes classifier $f^*$ 进行近似所造成的误差。

这里有一个 trade-off ：如果增大 $\mathcal{F}$ ，那么 approximation error 会相应地减小，比如，当 $\mathcal{F}$ 增大到包含了 $f^*$ 的话，approximation error 就等于零了。不过，随着 $\mathcal{F}$ 的增大，（对于固定的 $n$）第一项 estimation error 却会增大。这其实类似于更具体的统计模型里的 bias-variance trade-off 。至于为什么 estimation error 会随着 $\mathcal{F}$ 的增大而增大——当然，从直观上来想想还是比较好理解的，不过到本文末尾的时候，我们应该也能对这个问题有一个稍微严格一点的认识了。

现在我们先假定 $\mathcal{F}$ 已经固定了，因此 approximation error 就成为了一个固定值，这部分的 Risk 是问题本身造成的，不是我们通过训练数据或者算法所能控制的了，于是我们把视线集中到 estimation error 上。为了推导更简便一点，我们设 $\inf_{f\in\mathcal{F}}R(f)$ 在 $f_\mathcal{F}\in\mathcal{F}$ 取到。由于 $f_n^*$ 是使得 $R_n(f)$ 最小的解，因此有 $R_n(f_\mathcal{F})-R_n(f_n^*) \geq 0$ ，于是：

\[
\begin{aligned}
R(f_n^*)-R_\mathcal{F} &= R(f_n^*)-R(f_\mathcal{F}) \\
&\leq R(f_n^*)-R(f_\mathcal{F}) + R_n(f_\mathcal{F})-R_n(f_n^*) \\
&= \color{red}{R(f_n^*)-R_n(f_n^*)} + \color{blue}{R_n(f_\mathcal{F})-R(f_\mathcal{F})} \\
&\leq \color{red}{\sup_{f\in\mathcal{F}}|R_n(f)-R(f)|} + \color{blue}{\sup_{f\in\mathcal{F}}|R_n(f)-R(f)|} \\
&= 2 \sup_{f\in\mathcal{F}}|R_n(f)-R(f)|
\end{aligned}
\]

这为我们的 estimation error 提供了一个上界，如果我们能保证这个上界很小的话，自然就能保证 estimation error 小了。不直接去算 estimation error 而迂回一下搞一个上界的原因很明显：estimation error 太难算，而这个上界形式优良，容易估计：因为它和大数定理联系起来了！ 🙂

如果你觉得看得不太清楚的话，我们不妨来整理一下记号。首先固定一个 $f\in\mathcal{F}$ ，记 $Z=\ell_f(X,Y)$ ，这是 $\mathcal{X}\times\mathcal{Y}$ 上的一个随机变量，根据 Risk 和 Empirical Risk 的定义：

\[
\begin{aligned}
R(f) &= \mathbb{E}[\ell_f(X,Y)] = \mathbb{E}Z \\
R_n(f) &= \frac{1}{n}\sum_{i=1}^n\ell_f(X_i,Y_i) = \frac{1}{n}\sum_{i=1}^nZ_i\triangleq \overline{Z}_n
\end{aligned}
\]

也就是说，$Z$ 的期望就是 $f$ 的 Risk ，而 sample $S_n$ 估计出来的均值 $\overline{Z}_n$ 对应 $f$ 的 Empirical Risk 。根据大数定理，随着 $n\rightarrow\infty$ ，$\overline{Z}_n$ 将会趋向于 $\mathbb{E}Z$ ，于是将刚才推出的 estimation error 的上界限制住的希望出现了。需要注意的是，传统的大数定理在这里还不能直接用，因为注意到我们得到的上界里有一个针对所有 $f\in\mathcal{F}$ 的上确界，因此需要对大数定理进行改造，使得收敛必须对于所有 $f\in\mathcal{F}$ 是一致的。不过在讨论这个问题之前，我们先来看一下大数定理的不等式形式，因为仅仅是极限情况下看起来太遥远了，在实际问题中，我们希望的是，对于某个（有限的） $n$ ，估计出误差的一个具体的界。下面不妨就挑 Hoeffding 不等式来讨论好了。

注意这里要求 $Z$ 是有界的，不妨具体到二分类和 0-1 loss 问题，注意 0-1 loss $\ell_f(X,Y)$ 只能取 0 和 1 两个值，因此随机变量 $Z=\ell_f(X,Y)$ 是有界的（ $\in[0,1]$ ），于是可以用 Hoeffding 不等式，得到以 $1-\delta$ 的概率，有

\[
|\overline{Z}_n-\mathbb{E}Z|\leq (b-a)\sqrt{\frac{1}{2n}\ln\frac{2}{\delta}}=\sqrt{\frac{1}{2n}\ln\frac{2}{\delta}}
\]

可见，我们对置信度要求越高（$\delta$ 越接近 0 ），不等式右边的值就越大，因此 bound 就越松，不过随着 $n$ 的增大，我们可以得到越来越好的 bound 。用不等式的好处是，我们有明确的数值可以参考，比如，用 1000 个点的 sample ，我们可以以 99% 的概率保证对期望 $\mathcal{E}Z$ 的估计误差不超过 0.05 ，虽然这个 bound 不一定 tight ，也就是说，实际结果可能比这里估计的还要好得多，但是至少给了我们一个很“实在”的感觉。

但是有一个问题，从刚才开始我们一直就强调这里的结果是对于某个固定的 $f$ 成立的，但是学习的过程是在整个函数空间 $\mathcal{F}$ 中进行的，我们需要保证收敛性在 $\mathcal{F}$ 一致成立，前面关于 $R(f_n^*)-R_\mathcal{F}$ 的不等式右边的上确界正是明确了这个要求。注意，即便对于任意 $f\in\mathcal{F}$ 都满足收敛性，也不能保证所有 $f$ 一致收敛，作为一个可能不是那么形象的示意图：

图中横坐标表示函数空间 $\mathcal{F}$ ，红颜色的线表示 Risk ，而蓝色的线表示某个具有 $n$ 个数据点的训练数据 $S_n$ 对应的 Empirical Risk 。对于某个固定的 $f$ ，随着 $n$ 的增大，$R_n(f)$ 和 $R(f)$ 直接的距离逐渐趋向于零。但是对于任意固定的 $S_n$ ，如果 $\mathcal{F}$ 足够“大”的话，就可以找到 $f\in\mathcal{F}$ 使得 $R(f)$ 和 $R_n(f)$ 直接相差很大。没有一致收敛的话，就无法保证蓝线的最小值对应的 $f_n^*$ 收敛到红线的最小值对应的 $f^*$ 了。

让我们明确一下目的，之前通过 Hoeffding 不等式，我们得出了 $|R_n(f)-R(f)|$ 的一个 bound ，现在我们需要一个一致的 bound ，也就是说，针对 $\sup_{f\in\mathcal{F}}\;|R_n(f)-R(f)|$ 的 bound 。这个时候我们又得再为我们的“午餐”支付额外的费用了：为了得到一致收敛性，我们不得不限制 $\mathcal{F}$ 的大小。上一次我们曾经举了一个很 trivial 的例子，在 $\mathcal{F}$ 是所有的从 $\mathcal{X}$ 到 $\mathcal{Y}$ 的函数这么巨大无比的一个空间的情况下，我们可以找到使得 Empirical Risk 最小化（等于零）的解 $f$ ，然而 $f$ 几乎完全没有任何预测能力，其真实 Risk 甚至可以被构造得任意大（可以依赖于未知的 $P$ 来构造，因为我们只是要证明存在性，而不是要进行学习过程，所以可以利用未知的量）。这个例子说明，当函数空间过“大”时，一致收敛是非常困难的。

最简单的情况就是 $\mathcal{F}=\{f\}$ ：函数空间只有一个元素的情况，这个时候我们什么都不用干，原始的 Hoeffding 不等式和大数定理已经足够了。不过如果 $\mathcal{F}$ 只有一个元素，那也不用做什么 learning 了……接下来让我们考虑稍微不那么 trivial 一点的情况，$\mathcal{F}=\{f_1,f_2\}$ 。 :p

记 $\xi=\ell_{f_1}(X,Y)$ 、$\zeta=\ell_{f_2}(X,Y)$ 分别是 $f_1$ 和 $f_2$ 对应的随机变量，并设他们都有界：$\xi,\zeta\in[a,b]$ 。则我们有

\[
\begin{aligned}
P\left( \sup_{f\in\{f_1,f_2\}}|R_n(f)-R(f)|>\epsilon \right) &= P\left( \{|\overline{\xi}_n-\mathbb{E}\xi|>\epsilon\}\bigcup\{|\overline{\zeta}_n-\mathbb{E}\zeta|>\epsilon\} \right) \\
&\leq P\left( \{|\overline{\xi}_n-\mathbb{E}\xi|>\epsilon\}\right)+P\left(\{|\overline{\zeta}_n-\mathbb{E}\zeta|>\epsilon\} \right) \\
&\leq 2\times 2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right)
\end{aligned}
\]

最后一个不等式是对两项分别应用 Hoeffding 不等式得到的。如此一来，就可以直接将 $\mathcal{F}$ 包含两个元素的情况推广到包含 $N$ 个元素的情况，得到下面的命题：

于是，我们可以以 $1-\delta$ 的概率保证

\[
\sup_{f\in\mathcal{F}}\left|R_n(f)-R(f)\right|\leq (b-a)\sqrt{\frac{1}{2n}\ln\frac{2N}{\delta}}
\]

以对数依赖于 $\mathcal{F}$ 的元素个数的，似乎还算不错了，结合前面的结论，让我们来看一下具体的数值。假设有 1000 个数据点，在 1000 个函数上进行学习，考虑分类问题和 0-1 loss，则我们能以 99% 的概率保证

\[
R(f_n^*)-R_\mathcal{F}\leq 2\sup_{f\in\mathcal{F}}|R_n(f)-R(f)|\leq 2\sqrt{\frac{1}{2n}\ln\frac{2N}{\delta}} \approx 0.16
\]

对 $\sqrt{\ln}$ 级别的增长在这里是很有用的，比如，我们将函数空间的元素个数增加到 1000000 个，误差上界也才增加到 0.20 而已。但是确实是随着函数空间的复杂化而增长的，这从一定程度上解释了先前提到的 estimation error 随着函数空间的增大而增大的断言。当然，只是说“从一定程度上”解释，因为我们这里只是得到一个上界而已，上界的增大并不一定意味着真实值也增大的。

到此为止，我们已经完成了对 ERM 算法的一个 theoretical justification ：至少在一个有限的函数空间 $\mathcal{F}$ 中进行学习，ERM 算法是合理的，因为我们可以得到 ERM 算法找出的函数 $f_n^*$ 的 Risk 与 $\mathcal{F}$ 里所能达到的最小 Risk $R_\mathcal{F}$ 之差的一个 bound ，并且，这个 bound 会随着 $n\rightarrow\infty$ 而趋向于 0 ，也就是说，随着数据点的个数趋向于无穷，ERM 能够保证收敛都真实的最优解。

当然，故事还远远没有结束呢，还有众多的问题没有解决，其中最为严重的一个就是函数空间 $\mathcal{F}$ 的大小问题，这里的结论只能适用于 $\mathcal{F}$ 有限的情况，但是这实在是非常大的限制。正常一点的函数空间，像 “$\mathbb{R}^m$ 上的线性函数”之类的都远远不是有限的。为了解决无限的情况，我们需要挖掘一下 $\mathcal{F}$ 的结构，注意我们刚才在推导一致 bound 的时候只是把 $\mathcal{F}$ 看成一个普通的集合来看待的，但是如果 $\mathcal{F}$ 有一些拓扑或者度量或者其他的结构呢？比如说，$\mathcal{F}$ 上存在度量，那么如果有一团一团的函数彼此之间是很相似的的话，是不是可以用其中的某个函数来“代表”其他的函数，从而减少空间的“有效大小”？在数学上有没有什么“把无限划归为有限”的方法？不过这些问题，要留到下一次来解决了。

封面人物（们）：大数定理军团 Falcom 的 RPG 游戏英雄传说 6：空之轨迹 3rd 中游击士协会和七曜教会骑士团的各位以及他们的亲密伙伴们。