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

的函数? ?的过程。由于? ?是已知的，所以? ?是可以求值的，于是 ERM 就可以做了——当然这只是从理论上来说，比如，具体到二分类和 0-1 loss 函数的话，做 ERM 的优化是一个组合问题，非常困难；另外， ERM 问题经常都是 ill-conditioned ，不太容易直接求解。不过关于这些问题的解决方案不是今天要讲的内容，而是要留到将来了。

世界观设定中提到的 supervised learning 的目的是最小化 Risk? ?，所以，现在需要检查的问题就是，通过 ERM 算法求出来的? ?，其 Risk 是不是也比较小呢？和最优的 Bayes Risk? ?或者在 ?里能达到的最优 Risk? ?差多少呢？首先来看 Bayes Risk

这里右边红色的项叫做 estimation error ，因为它是由通过训练数据? ?去进行 estimate 造成的误差，而蓝色的项叫做 approximation error ，注意到它与具体的训练数据无关，而只与函数空间? ?的选取有关，它的名字的由来是表示这是用? ?中的函数去对 Bayes classifier? 进行近似所造成的误差。

这里有一个 trade-off ：如果增大? ?，那么 approximation error 会相应地减小，比如，当? 增大到包含了? ?的话，approximation error 就等于零了。不过，随着? ?的增大，（对于固定的? ）第一项 estimation error 却会增大。这其实类似于更具体的统计模型里的 bias-variance trade-off 。至于为什么 estimation error 会随着? ?的增大而增大——当然，从直观上来想想还是比较好理解的，不过到本文末尾的时候，我们应该也能对这个问题有一个稍微严格一点的认识了。

现在我们先假定? ?已经固定了，因此 approximation error 就成为了一个固定值，这部分的 Risk 是问题本身造成的，不是我们通过训练数据或者算法所能控制的了，于是我们把视线集中到 estimation error 上。为了推导更简便一点，我们设? ?在? ?取到。由于? ?是使得? ?最小的解，因此有? ?，于是：

（编辑：ASP站长网）