Feasibility of Learning
这一节课，探讨机器学习的可行性。
一开始，老师给出了一个例子，说机器学习并不能确保学习到的 g 近似等于 f。
从上图我们可以看出来，即使我们能确保在我们手头上的 x 上，g 确确实实等于 f，但是，在data之外的数据，我们不能说 g≈ f，因为这里可能性的 f 有太多种了，无论 g 选其中的哪一个 f，adversarial teacher
都可以说你是错误的。
那么，难道机器就不能学习了吗？
其实，在一定的假设条件下，我们还是可以说， g≈f 的。
我们先来看一个定理不等式Hoeffding’s Inequality：
其中，v是独立同分布事件x_1,x_2,...,x_n平均值，也即(x_1+x_2+...+x_n)/n。而 u 是一个事件发生的期望。hoelfding 不等式告诉我们，当我的样本规模n取的足够大的时候，多个事件发生的平均就近似等于一个事件发生的期望。也就是说，v 和 u 是大概率近似相等（PAC）的。
接下来，我们把 v 事件看成是 g(x)≠f(x) 这个事件。那么，只要当data规模足够大（D中的数据是独立同分布的），并且 v 要足够小，我们就可以说，不论在D中还是D外，都有 g(x)≠f(x) 并且这个事件发生的概率很小。也就是说，g≈f。
但是以上我们都只考虑了一个hepothesis。 如果这个 hepothesis的g(x)≠f(x)发生的概率小还好，但是一旦它很大，我们选它就会很离谱。所以考虑多个hepothesis，让机器可以选择，才能避免这种情况。
BAD sampel:
看起来g(x)≠f(x) 在D中发生的很少，但是在D外却经常发生，所以选到这些sample就很不好。所以我们需要想办法去避免这些BAD sample吗？
我们可以从这看出：当我们选取M个时，改进的Heolfding不等式：
也就是说，当M有限时，坏的数据对于任意一个hepothesis来说，都是很小很小的，所以，PAC假设还是成立的。这时，我们只要选取一个看起来g(x)≠f(x) 发生概率最小的hepothesis作为 g 就可以了。
网友评论