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

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

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

现在我们先假定? F ?已经固定了，因此 approximation error 就成为了一个固定值，这部分的 Risk 是问题本身造成的，不是我们通过训练数据或者算法所能控制的了，于是我们把视线集中到 estimation error 上。为了推导更简便一点，我们设? inff∈FR(f) ?在? fF∈F ?取到。由于? f?n ?是使得? Rn(f) ?最小的解，因此有? Rn(fF)?Rn(f?n)≥0 ?，于是：

R(f?n)?RF=R(f?n)?R(fF)≤R(f?n)?R(fF)+Rn(fF)?Rn(f?n)=R(f?n)?Rn(f?n)+Rn(fF)?R(fF)≤supf∈F|Rn(f)?R(f)|+supf∈F|Rn(f)?R(f)|=2supf∈F|Rn(f)?R(f)|

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

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

R(f)Rn(f)=E[?f(X,Y)]=EZ=1n∑i=1n?f(Xi,Yi)=1n∑i=1nZi?Z?n

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

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

|Z?n?EZ|≤(b?a)12nln2δ????????√=12nln2δ?√

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

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

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

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

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

记? ξ=?f1(X,Y) ?、 ζ=?f2(X,Y) ?分别是? f1 ?和? f2 ?对应的随机变量，并设他们都有界： ξ,ζ∈[a,b] ?。则我们有

P(supf∈{f1,f2}|Rn(f)?R(f)|>?)=P({|ξ??n?Eξ|>?}?{|ζ?n?Eζ|>?})≤P({|ξ?n?Eξ|>?})+P({|ζ?n?Eζ|>?})≤2×2exp(?2n?2(b?a)2)

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

于是，我们可以以? 1?δ ?的概率保证

supf∈F|Rn(f)?R(f)|≤(b?a)12nln2Nδ?√

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

R(f?n)?RF≤2supf∈F|Rn(f)?R(f)|≤212nln2Nδ?√≈0.16 对? ln?√ ?级别的增长在这里是很有用的，比如，我们将函数空间的元素个数增加到 1000000 个，误差上界也才增加到 0.20 而已。但是确实是随着函数空间的复杂化而增长的，这从一定程度上解释了先前提到的 estimation error 随着函数空间的增大而增大的断言。当然，只是说“从一定程度上”解释，因为我们这里只是得到一个上界而已，上界的增大并不一定意味着真实值也增大的。

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

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

直观来说，就是随着? ?增大，由采用数据估计出来的平均值? ?会越来越接近真实平均值? ?。强大数定理可以（用?Empirical Risk Minimization (ERM)?说起。

我们上次提到过，ERM 就是根据训练数据? ?在给定的函数空间? ?中寻找最小化经验误差

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

世界观设定中提到的 supervised learning 的目的是最小化 Risk? ?，所以，现在需要检查的问题就是，通过 ERM 算法求出来的? ?，其 Risk 是不是也比较小呢？和最优的 Bayes Risk? ?或者在 ?里能达到的最优 Risk? ?差多少呢？首先来看 Bayes Risk

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

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

现在我们先假定? ?已经固定了，因此 approximation error 就成为了一个固定值，这部分的 Risk 是问题本身造成的，不是我们通过训练数据或者算法所能控制的了，于是我们把视线集中到 estimation error 上。为了推导更简便一点，我们设? ?在? ?取到。由于? ?是使得? ?最小的解，因此有? ?，于是：

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

如果你觉得看得不太清楚的话，我们不妨来整理一下记号。首先固定一个? ?，记? ?，这是? ?上的一个随机变量，根据 Risk 和 Empirical Risk 的定义：

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

注意这里要求? ?是有界的，不妨具体到二分类和 0-1 loss 问题，注意 0-1 loss? ?只能取 0 和 1 两个值，因此随机变量? ?是有界的（? ?），于是可以用 Hoeffding 不等式，得到以? ?的概率，有

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

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

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

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

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

记? ?、 ?分别是? ?和? ?对应的随机变量，并设他们都有界： ?。则我们有

n?Eζ|>?})≤2×2exp(?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!