|
其中?
?是和?
?独立同分布的随机变量。
注意这里要求?
?是有界的，不妨具体到二分类和 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(?
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
