机器学习碎碎念：霍夫丁不等式

关键时刻，第一时间送达！

红色石头每天碎碎念一些机器学习知识和概念，大家一起学习，每天进步一点点！喜欢的话别忘了文末点赞支持一下哦~

如果有一个装有很多（数量很大数不过来）橙色球和绿色球的罐子，我们能不能推断橙色球的比例 u？统计学上的做法是，从罐子中随机取出 N 个球，作为样本，计算这N 个球中橙色球的比例 v，那么就可以估计出罐子中橙色球的比例约为 v。

这种随机抽取的做法能否说明罐子里橙色球的比例一定是 v 呢？答案是否定的。但是从概率的角度来说，样本中的 v 很有可能接近我们未知的 u。当 N 足够大的时候，v接近于 u。这就是霍夫丁不等式（Hoeffding’s inequality）：

其中，P 表示概率。霍夫丁不等式说明当 N 很大的时候，v 与 u 相差不会很大，它们之间的差值被限定在ϵ 之内。

重点，对应到机器学习中，我们可以令训练误差 Ein = v，泛化误差 Eout = u。那么，当训练样本数目足够多的时候，可以得到相应的霍夫丁不等式：

上面的霍夫丁不等式说明了，选择合适的足够训练样本，训练的模型一般能使 Ein 与 Eout 近似相等，即泛化能力较好（除非过拟合）。总的来看，霍夫丁不等式是保证机器可以学习的一个条件！

- End -