Ch6 Theory of Generalization (舉一反三)

  • Break Point限制 :
    1. 當 $N>k$ 時，Break Point $k$ 會大大限制 $m_\mathcal{H} (N)$ 的最大可能值
      • EX : minimun breal point = 2
        • $N=1$ : $m_\mathcal{H} (N)=2$
        • $N=2$ : MAX possible $m_\mathcal{H} (N)=3 \lt 2^2$
        • $N=3$ : MAX possible $m_\mathcal{H} (N)=4 \lt \lt 2^3$
  • Bounding Function $B(N,k)$ : MAX possible $m_\mathcal{H}(N)$ when break point = $k$
    • EX: $B(N,3)$ bounds both :
      • Positive Intervals (k = 3)
      • 1D Perceptrons (k = 3)
    • 各種情況 :
      • $N=K$ : $B(N,k)=2^N-1$
      • $N<k$ : $B(N,k)=2^N$
      • $B(N,1)=1$
      • 其他 : $B(N,k) \le B(N-1,k)+B(N-1,k-1)$
    • $B(N,k)$
    • 而$B(N, k)=\Sigma_{i=0}^{k-1}$ ( N i ) ，其中最高項為$N^{K-1}$
    • 以上可推得，如果Break Point存在，則$m_\mathcal{H}(N)$ 為 $\text{Poly}(N)$
  • Vapnik-Chervonenkis (VC) Bound : $$\Bbb{P}[\exists h \in \mathcal{H},\text{s.t.} |E_{in}(h) - E_{out}(h)| > \epsilon] \le {\color{red}{4}} m_\mathcal{H}({\color{blue}{2}}N)\cdot exp(-{\color{purple}{\frac{1}{8}}} \epsilon^2 N)$$
    • 用 $E_{in}’$ 取代 $E_{out}$
    • decompose $\mathcal{H}$ by kind
    • use Hoeffding without replacement