技术附录

A.NFL定理

定义A为算法，x_in为样本内数据，x_out为样本外数据（N个），c为目标函数，h为假设函数。在考虑所有c的情况下，算法A在样本外的误差期望如下所示。

在第4行中，当c为均匀分布时，c和h的预测结果有一半不一致。那么c一共有2^N个预测结果，一半就是2^N-1。上述结果与算法A无关，可见“胡乱猜”的算法和高级算法的期望误差或者期望性能相同。

B.霍夫丁不等式

霍夫丁不等式（Hoeffding's Inequality）是根据切诺夫上界（Chernoff Bound）和霍夫丁引理（Hoeffding's Lemma）证明出来的，而切诺夫上界由马尔可夫不等式（Markov's Inequality）证明出来的。

它们的关系如右图所示。

马尔可夫不等式、切诺夫上界、霍夫丁引理和霍夫丁不等式的具体证明如下表所示。

当Z_i服从伯努利分布时，那么a=0，b=1，将上式和机器学习结合得到

---

^[1]NFL定理证明见本章附录A。

^[2]霍夫丁不等式证明见本章附录B。

^[3]增长函数的上界推导比较烦琐，见本章参考资料[1]。