Categories

Calendar

October 2017
M T W T F S S
« Jun    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

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

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

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

定理 1:设 $X_1,\ldots,X_n$ 是独立同分布的随机变量,并且 $\mathbb{E}|X_i|<\infty$ ,记 $\mu=\mathbb{E}X_i$ ,$\mu_n = \sum_{i=1}^nX_i/n$ ,则随着 $n\rightarrow\infty$
  1. 强大数定理:$\mu_n$ 几乎处处(逐点)收敛于 $\mu$ ,亦即

    \[
    P(\lim_{n\rightarrow\infty}\mu_n = \mu) = 1
    \]

  2. 弱大数定理:$\mu_n$ 依概率收敛于 $\mu$ ,亦即 $\forall \epsilon>0$

    \[
    \lim_{n\rightarrow\infty}P(|\mu_n-\mu|\geq\epsilon)=0
    \]

直观来说,就是随着 $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 不等式来讨论好了。

定理 2(Hoeffding 不等式):设随机变量 $Z$ 满足 $Z\in [a,b]$ ,则

\[
P\left(\left|\frac{1}{n}\sum_{i=1}^nZ_i – \mathbb{E}Z\right|>\epsilon\right) \leq 2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right)
\]

其中 $\{Z_i\}_{i=1}^n$ 是和 $Z$ 独立同分布的随机变量。

注意这里要求 $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$ 个元素的情况,得到下面的命题:

命题 3:设 $\mathcal{F}=\{f_1,\ldots,f_N\}$ ,且 $\ell_f(X,Y)\in [a,b]$ ,则

\[
P\left(\sup_{f\in\mathcal{F}}\left|R_n(f)-R(f)\right|>\epsilon\right) \leq 2N\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right)
\]

于是,我们可以以 $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 中游击士协会和七曜教会骑士团的各位以及他们的亲密伙伴们。

11 comments to 机器学习物语(2):大数定理军团

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>