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

这为我们的 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 不等式来讨论好了。

（编辑：ASP站长网）