2-Is learning feasible ?

该图的实验贯穿了整个lecture。 从一个bin中sample出来的N个样本样本， 然后从样本学习出v， 并且希望v≈u (u是bin中的red marble的比例）

Hoeffding's inequality。来源自大数定理， 我们希望v与u的差异在一个小范围epsilon之外的概率缩小在一个很小的范围。这点可以通过增大样本个数N或者放宽epsilon。在本lecture中， 是以u，v举例， 这是对应二元的情况， 对于其它多元的情况， 也可以用均值E来衡量差异。P.A.C.指的是probably， approximately， correct。probably指的是等式右端的概率很小(violation is small), approximately 指u， v close to each other.

样本视作是从bin采样产生

之所以用多个bin， 指我们的模型是有多个h的， 每个h都产生不一样的u和v

in sample 指的是采样出来的点， out of sample指的是original的点。

事情还没完成， 因为上述讨论的只是针对一个bin， 而实际是讨论多个bin才有意义。 我们是从多个bin对应的多个h选出来一个g作为终选的hypothesis， 必须保证其最优。

最终的推导如下， 利用了概率论中的union法则。 最后的式子的M代表了hypothesis的数量， 当M过大的时候， 可能导致右边的式子为大于1的数， 这样式子显然成立。 这是因为M过大， 模型过于复杂了， 过拟合！