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

于是，我们可以以? 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 ?上存在度量，那么如果有一团一团的函数彼此之间是很相似的的话，是不是可以用其中的某个函数来“代表”其他的函数，从而减少空间的“有效大小”？在数学上有没有什么“把无限划归为有限”的方法？不过这些问题，要留到下一次来解决了。

?是独立同分布的随机变量，并且? ?，记? ， ?，则随着?

1. 强大数定理： ?几乎处处（逐点）收敛于? ?，亦即

   （编辑：ASP站长网）