上QQ阅读APP看本书，新人免费读10天
设备和账号都新为新人
技术附录
A.NFL定理
定义A为算法，xin为样本内数据，xout为样本外数据（N个），c为目标函数，h为假设函数。在考虑所有c的情况下，算法A在样本外的误差期望如下所示。
在第4行中，当c为均匀分布时，c和h的预测结果有一半不一致。那么c一共有2N个预测结果，一半就是2N-1。上述结果与算法A无关，可见“胡乱猜”的算法和高级算法的期望误差或者期望性能相同。
B.霍夫丁不等式
霍夫丁不等式（Hoeffding's Inequality）是根据切诺夫上界（Chernoff Bound）和霍夫丁引理（Hoeffding's Lemma）证明出来的，而切诺夫上界由马尔可夫不等式（Markov's Inequality）证明出来的。
它们的关系如右图所示。
证明霍夫丁不等式
马尔可夫不等式、切诺夫上界、霍夫丁引理和霍夫丁不等式的具体证明如下表所示。
当Zi服从伯努利分布时，那么a=0，b=1，将上式和机器学习结合得到
[1]NFL定理证明见本章附录A。
[2]霍夫丁不等式证明见本章附录B。
[3]增长函数的上界推导比较烦琐，见本章参考资料[1]。