• Statistical Learning Flow中的差異 :
    • Testing : $E_{out}(g) \approx E_{in}(g)$
    • Training : $E_{in}(g) \approx 0$
  • Learning的核心問題 :
    1. 要如何讓 $E_{out}(g)$ close enough to $E_{in}(g)$
    2. 要如何讓 $E_{in}(g)$ small enough
  • Effective Number of Lines : (以平面為例)
    N effective(N)
    1 2
    2 4
    3 8
    4 14 $\lt 2^N$
    • 若 :
      1. effective(N)可取代 $M$
      2. effective<< $2^N$
    • 則Learning is possible with infinite lines

      即$\Bbb{P}[|E_{in}(g) - E_{out}(g)| > \epsilon] \le 2 \cdot \color{blue}{\text{effective(N)}} \cdot exp(-2 \epsilon^2 N)$

  • Dichotomy(二分) : N個點產生了幾種可能性
    • 表示 : $\mathcal{H}(x_1,x_2,\cdots x_N)$
    • 差異 :
      Hypothesis $\mathcal{H}$ Dichotomies $\mathcal{H}(x_1,x_2,\cdots x_N)$
      e.g. all lines in $\Bbb{R}^2$ {ooxx,oooo,oxxx…}
      size possibly infinite $\le 2^N$
    • 為降低對$x$的依賴性，故只取所有可能組合的最大值 : $m_\mathcal{H} (N)$，a.k.a. Growth Function
    • 若$m_\mathcal{H} (N)=2^N$，則可稱$N$個輸入可以被shattered(擊倒)
  • Break point :
    • Def : 若無 $k$ 個input可以被 $\mathcal{H}$ shattered，則可稱 $k$ 為 $\mathcal{H}$ 的Break Point
      • 即$m_\mathcal{H} (k) \lt 2^k$
      • $k+1, k+2,\cdots$也是Break Point
    • EX :
      • Positive Rays : break point at 2
      • Positive Intervals : break point at 3
      • Convex Sets : No break point
      • 2D Perceptrons : break point at 4