|
于是，我们可以以?
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
?上存在度量，那么如果有一团一团的函数彼此之间是很相似的的话，是不是可以用其中的某个函数来“代表”其他的函数，从而减少空间的“有效大小”？在数学上有没有什么“把无限划归为有限”的方法？不过这些问题，要留到下一次来解决了。
?是独立同分布的随机变量，并且?
?，记?
，
?，则随着?
-
强大数定理：
?几乎处处（逐点）收敛于?
?，亦即
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
