第四讲 机器学习的可行性
一、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
这就推出，\( h \approx f\) with respect to \(P\)
我们的学习思路就是，从一些hypothesis set 中找到最好的 \(h\)，使得\( h \approx f\)
二、真实的学习
面对多个\( h \) 时，容易出现问题。
BAD Sample：\( E_{in} and E_{out} \) far away
那么，Bad Sample的概率有多大呢？我们认为，在众多的hypothesis set上的每一个\(h_{i}\)，只要有一个是坏的，则都是坏的
\(P_{\mathfrak{D}}\left [ BAD \mathfrak{D} \right ] \)
\( = P_{\mathfrak{D}}\left [ BAD \mathfrak{D} for h_{1} or BAD \mathfrak{D} for h_{2} or ... or BAD \mathfrak{D} for h_{M} \right ] \)
\( \leq P_{D} \left [ BAD D for h_{1} \right ] + P_{D} \left [ BAD D for h_{2} \right] + ... + P_{D} \left [ BAD D for h_{M} \right] \)
(\( Union Bound \))
\( \leq 2exp(-2\epsilon^2N) + 2exp(-2\epsilon^2N) + ... + 2exp(-2\epsilon^2N) \)
\( = 2M\cdot exp(-2\epsilon^2N)\)
当hypothesis set为有限时，（\( M\) 固定），当\(N\)足够大时，因为后面的\(exp(-2\epsilon^2N)\) 随着\(N\)增大会变得特别小，故总体值是很小的。
此时学习是有效的。
当hypothesis set 为无穷大时，\( M = \infty \) 则有问题了，具体问题下一部分讨论。