第六讲
第五讲主要讲了机器学习可能性，两个问题，（1）(E_{in} 要和 E_{out}) 有很接近，（2）(E_{in})要足够小。
对于第一个假设，根据Hoefding's Inequality 可以得到，( P[|E_{in} - E_{out}| > epsilon] < 2Mexp(-2epsilon^2N))
对于上述的(M)来说，如果 (M < infty)，则当(N)足够大时，(P)会比较小，也就是坏事情出现的概率比较小，机器学习是可能的，但是当(M = infty)时，就无法进行学习了。
那怎么办？考虑到or的过程中有不少重叠的部分，就从数据的角度来看到底有多少种可能的 effective Hypothesis，多少种可能的Hypothesis就是成长函数的值，Break Point的概念也就出来了，就是当(m_{mathcal{H}}(k) < 2^k)，(k)就是Break Point。 Break Point有什么用呢？
本节引出一个新概念，Break Function，是指最小的Break Point (k)，Growth Function 可能的最大值，记为(B(N,k))。
当( k = 1)时，( B(N,1) = 2^0 = 1)
当( k > N)时，(B(N,k) = 2^{N})
当( k = N)时，(B(N,k) = 2^{N} - 1)，最大的可能值
根据上述两条会得到一个矩阵的一部分数据，
重点要考虑( k < N)的情况，怎么算呢？ 林老师给出一个图示，在第六讲的12页-17页，
(B(4,3)) 可以有11个可能的Hypothesis，对于Break Point是3来说，应该只能Shattered 2个点的情况，2个点的所有情况是4，那么如果遮住(x_{4})，再去重之后应该不超过(2B(3,3))。
也就是说，从三个点扩展到四个点的过程中，只有部分的dichotomy被复制了，我们把这部分被复制的点的个数称为(alpha)，没被复制的点的个数称为(eta)。满足(0leq alpha, eta leq B(3,3))。可知 ( B(3,3) geq alpha + eta , B(4,3) = 2alpha + eta) ，单独看(alpha)部分，因为Break Point是 3，故任何三个都不能被Shattered，那么，如果只看(alpha)部分，则，( x_{1}, x_{2}, x_{3}) 中任意两个都不能被Shattered，（如果可以，加上(x_{4})则有3个点被Shattered）则，(alpha leq B(3,2) )，有如下三个结果：
（1） ( B(4,3) = 2alpha + eta)
（2）( B(3,3) geq alpha + eta)
（3） (B(3,2) geq alpha)
综合上面三个公式，可得：
( B(4,3) leq B(3,3) + B(3,2))
推广得：( B(N,k) leq B(N-1,k) + B(N-1, k-1))
根据数学归纳法，
( B(N,k) leq sum_{i=0}^{k-1}inom{N}{i})
从上面这个式子可以更为欣喜的得到，之前的概率上界是可以在多项式里的，这样当(N) 足够大时，出现坏事情的概率就会比较小。这样学习就会更为可行。
下面就要去求解一个上界：VC Bound
want:
( P[ exists h in mathcal{H} s.t. |E_{in}(h) - E_{out}(h)| > epsilon] leq 2 m_{mathcal{H}}(N) exp(-2epsilon^2N))