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