机器学习基石的泛化理论及VC维部分整理

 第四讲 机器学习的可行性

Hoeffding‘s Inequality

$P[\left | \nu -\mu \right |>\epsilon ] \leq 2exp(-2\epsilon^{2}N)$ 　　　　　　　　　　　　　　(1)

in-sample error, 也就是在样本里出现的error， $E_{in}$ is probably close to out-of-sample error $E_{out}$ (within $\epsilon$ )

推出一个类似的公式：  $P[\left | E_{in} - E_{out} \right |>\epsilon ] \leq 2exp(-2\epsilon^{2}N)$ 　　　　(2)

也就是说，公式（2）说明了问题可以学习的两个条件：

（1） $E_{in} \approx E_{out}$ ：这个代表  $E_{out}$ 要和  $E_{in}$ 差不多大

（2） $E_{in}(h) \approx 0$ ：这个代表 $E_{in}$ 要差不多是0

机器学习基石的泛化理论及VC维部分整理

原文：http://www.cnblogs.com/tsat/p/3543012.html