这一讲主要是分析上一讲中联合错误界中常数$M$的分析。在上一讲中，我们得知

• If $|H|=M$ finite, $N$ large enouph, for wahtever $g$ picked by $A$, $E_{out}(g)\approx E_{in}(g)$;

• If $A$ finds one $g$ with $E_{in}(g)\approx 0$, PAC guarantee for $E_{out}(g)\approx 0$.

  $\Rightarrow $ Learning possible. 

1. learning split to two central questions:

• can we make sure that $E_{out}(g)$ is close enough to $E_{in}(g)$?

• can we make $E_{in}(g)$ small enough?

  
  

2.我们已知了错误上界，现在的目的在于如何限定$M$使得错误界更加紧凑。

3. 利用集合的联合导出的上述错误界，其实是对学习错误的过高估计，因为：

4.Growth Function：remove dependence by taking max of all possible $(x_1; x_2;\cdots; x_N)$

   $m_H(N) = \max\limits_{x_1;x_2;\cdots;x_N\in \mathcal{X}} |H(x_1; x_2; \cdots ; x_N)|$

其中，$|H(x_1; x_2; \cdots ; x_N)|$是这N个样本产生的假设的个数。

 $m_H(N)$ finite and upper-bounded by 2N.

下图是几个学习算法的成长函数(Growth Function)值：

由此，我们可以猜测

5.Break Point of $\mathcal{H}$

if no $k$ inputs can be shattered by $H$, call $k$ a break point for $H$:

• $m_H(k) < 2^k$;

• $k + 1, k + 2, k + 3, \cdots$ also break points!

• we will study minimum break point $k$.

Break point 的几个例子：

6. 最后给出假设，引出下一讲