|
的函数?
f?n
?的过程。由于?
Sn
?是已知的，所以?
Rn
?是可以求值的，于是 ERM 就可以做了——当然这只是从理论上来说，比如，具体到二分类和 0-1 loss 函数的话，做 ERM 的优化是一个组合问题，非常困难；另外， ERM 问题经常都是 ill-conditioned ，不太容易直接求解。不过关于这些问题的解决方案不是今天要讲的内容，而是要留到将来了。
虽然 ERM 算法看起来很自然，但是他是不是一个好的算法呢？回忆一下我们在世界观设定中提到的 supervised learning 的目的是最小化 Risk?
R(f)
?，所以，现在需要检查的问题就是，通过 ERM 算法求出来的?
f?n
?，其 Risk 是不是也比较小呢？和最优的 Bayes Risk?
R?
?或者在
F
?里能达到的最优 Risk?
RR
?差多少呢？首先来看 Bayes Risk
R(f?n)?R?=R(f?n)?RF+RF?R?
这里右边红色的项叫做 estimation error ，因为它是由通过训练数据?
Sn
?去进行 estimate 造成的误差，而蓝色的项叫做 approximation error ，注意到它与具体的训练数据无关，而只与函数空间?
F
?的选取有关，它的名字的由来是表示这是用?
F
?中的函数去对 Bayes classifier?
f?
进行近似所造成的误差。
这里有一个 trade-off ：如果增大?
F
?，那么 approximation error 会相应地减小，比如，当?
F
增大到包含了?
f?
?的话，approximation error 就等于零了。不过，随着?
F
?的增大，（对于固定的?
n
）第一项 estimation error 却会增大。这其实类似于更具体的统计模型里的 bias-variance trade-off 。至于为什么 estimation error 会随着?
F
?的增大而增大——当然，从直观上来想想还是比较好理解的，不过到本文末尾的时候，我们应该也能对这个问题有一个稍微严格一点的认识了。
现在我们先假定?
F
?已经固定了，因此 approximation error 就成为了一个固定值，这部分的 Risk 是问题本身造成的，不是我们通过训练数据或者算法所能控制的了，于是我们把视线集中到 estimation error 上。为了推导更简便一点，我们设?
inff∈FR(f)
?在?
fF∈F
?取到。由于?
f?n
?是使得?
Rn(f)
?最小的解，因此有?
Rn(fF)?Rn(f?n)≥0
?，于是：
R(f?n)?RF=R(f?n)?R(fF)≤R(f?n)?R(fF)+Rn(fF)?Rn(f?n)=R(f?n)?Rn(f?n)+Rn(fF)?R(fF)≤supf∈F|Rn(f)?R(f)|+supf∈F|Rn(f)?R(f)|=2supf∈F|Rn(f)?R(f)|
（编辑：晋中站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
