這章節要來講一般化，白話一點就是機器怎麼舉一反三的。上一章節的最後，我們知道了成長函數跟 break point 有某些關係，這一章節我們要來慢慢導出這個關係。

Restriction of Break Point

• The Four Break Points
  成長函數指的是我們的 Hypothesis Set 在 $N$ 個點上最多可以產生多少組 dichotomies。從上一章節我們知道成長函數至少會小於 $2^{N}$，且如果 break point 在 $k$，那麼 $k+1, k+2,…$ 都會是 break point。那這個 break point 有沒有為我們未來會產生多少 dichotomies 有更強的限制呢？

• Restriction of Break Point
  如果有一個 Hypothesis Set 的 min. break point 在 $k=2$ 的地方，這說明如果 $N=1$，那麼可以產生兩組 dichotomies（可以被 shattered）。當 $N=2$，就無法被 shattered，最多就是三組 dichotomies。

那麼當 $k=2, N=3$ 呢？一個個舉出來，會發現最多就是四種組合，只要加入第五種，就會有任兩點被 shattered。（break point $k$ 時，表示任意 $k$ 個點都無法被 shattered）

當 $N > k$ 時，$k$ 限制了 $m_{H}$ 的最大可能。

可以用這個想法來推論當成長函數 $m_{H}$ 有 break point $k$ 的時候，如果最多可以產生的可能性是一個多項式，那麼就可以說成長函數也是一個多項式。如果可以再把這個多項式放進 Hoeffding’s Inequality 的話，那麼我們就可以說在 Perceptron 這樣的情形，機器學習是做得到的。

Bounding Function: Basic Cases

• Bounding Function
  上限函數 Bounding function 是說當成長函數有一個 break point $k$ 的時候，這個成長函數最多會有多少 dichotomies 的可能。可以想像成有一堆 dichotomy 向量，由 o x 組成，向量長度是 $N$。如果只看其中 $k$ 的維度，都不能出現 shatter 的情況。

那我們能不能證明上限函數是個多項式？

• Table of Bounding Function
  那就一個個列出來看吧。藉由前一小節的推導，可以知道 $B(2, 2) = 3$ 以及 $B(3, 2) = 4$。

接下來，從上一小節的 Fun Time 我們知道，如果連一個點都沒辦法 shatter，那不可能產生第二種組合。

上限函數是說有 $N$ 個點，任何 $k$ 個點不能 shatter。如果 $N < k$ ，選出來的 $k$ 也是重複的點，那麼最多可以產生 $2^{N}$ 種組合。

當 $N = k$ 時，上限函數就是 $2^{N} - 1$。

Bounding Function: Inductive

• Estimating $B(4, 3)$
  繼續填表，找出 $B(4, 3)$ 和 $B(3, ?)$ 之間的關係。

• Achieving Dichotomies of $B(4, 3)$
  寫一支程式把所有可能性列出來，再去檢查是否符合條件，會得到 $B(4, 3) = 11$。

• Reorganized Dichotomies of $B(4, 3)$
  重新整理一下剛剛的結果。橘色底的表示成雙成對 $x_{1}, x_{2}, x_{3}$ 都相同，只有 $x_{4}$ 一個是 o 一個是 x。另外三個組合目前單身 😢

• Estimating Part of $B(4, 3)$
  以這個例子來看，$B(4, 3) = 2 \alpha + \beta$。如果不看 $x_{4}$，會有 $\alpha + \beta$ 種dichotomies 組合。根據 $B(4, 3)$ 的定義，任意三個點不能被 shattered，所以我們可以推出 $\alpha + \beta \leq B(3, 3)$。

再丟掉紫色的部分，剩下的橘色裡，如果任兩個點 shatter，加上 $x_{4}$ 也會 shatter，那就不是我們要的。這裡可以推出 $\alpha \leq B(3, 2)$。

• Putting It All Together
  把剛剛推出來的東西整理在一起，可以得到 $B(4, 3) \leq B(3, 3) + B(3, 2)$。把 $N$, $k$ 分別代進去，就可以得到上限。

• Bounding Function: The Theorem
  成長函數會被上限函 bound 住，上限函數會被上限的上限 bound 住，而這個「上限的上限」則會被一個多項式 bound 住，這個多項式會跟 break point 有關。所以我們可以說只要 break point 存在，那成長函數一定可以被一個多項式 bound 住。

• The Three Break Points
  我們可以透過找到的 break point 來找出成長函數。

A Pictorial Proof

• BAD Bound for General $H$
  有了上一小節的推導，我們把成長函數直接放進去原本的 Hoeffding’s Inequality，那麼當 $N$ 很大、並且做了一些轉換之後，可以得到下面的式子，跟本來的不等式長得很像的式子。

那這些轉換、多出來的常數是怎麼出現的呢？

• Sketch of Proof
  接下來就要來證明上圖中下面的那個式子成立。

首先，把 $E_{out}$ 換成 $E’_{in}$。

因為 $E_{out}$ 有無限多個，所以我們用驗證集合 $D’$ 估計出來的 $E’_{in}$ 來取代，那 $E_{in}$ 與 $E_{out}$ 發生壞事情的情況，應該跟$E_{in}$ 與 $E’_{in}$ 發生壞事的情況接近。所以我們可以把 $E’_{in}$ 拿來取代 $E_{out}$。

$E_{in}$ 有 $m_{H}(N)$ 種，$E’_{in}$ 也有 $m_{H}(N)$ 種。我們在乎的所有的壞事都只需要 $D$ 和 $D’$ 來決定。也就是說，如果 hypothesis 在 $D$ 和 $D’$上做出一樣的預測，那麼$E_{in}$ 跟$E’_{in}$ 也會長一樣。那麼我們只需要看在 $D$ 和 $D’$ 的 $2N$ 個點上可以產生多少組 dichotomies，而這最多可以有 $m_{H}(2N)$ 種。

最後我們想知道一個 sample 跟所有平均的差別。這就很像桶子裡有 $2N$ 顆球，現在抽了 $N$ 顆出來，比較這 $N$ 顆球跟桶子裡 $N$ 顆球的差別。抽完不放回，這是 Hoeffding without replacement。

得到結果之後代進去原本的式子。

我們證明了 VC bound 定理。將 $E_{out}$ 用 $E’_{in}$ 來取代出現了常數 $2$，接著拆開跑出 $2N$，最後再代進 Hoeffding Inequality 出現了 $\frac{1}{8}$。

從這裡我們知道了關於 2D perceptrons，它的 break point 是 4，成長函數是 $O(N^{3})，所以我們可以說當點夠多的時候，PLA 是可以達到機器學習的效果的。

Summary

• Restriction of Break Point: Break point ‘breaks’ consequent points
• Bounding Function - Basic Cases: $B(N, k)$ bounds $m_{H}(N)$ with break point $k$
• Bounding Function - Inductive Cases: $B(N, k)$ is $poly(N)$
• A Pictorial Proof: $m_{H}(N)$ can replace $M$ with a few changes
• Slides: https://www.csie.ntu.edu.tw/~htlin/mooc/doc/06_present.pdf