這章要進入機器學習的核心問題，到底為什麼機器可以學到東西？如果 Hypothesis Set 無限大的話會發生什麼事情？

Recap and Preview

前一章證明了如果 Hypothesis Set $H$ 是有限的 $M$ 個，而且資料量 $N$ 夠大，不管演算法 $A$ 選出來的 $g$ 是什麼，$E_{in}$ 和 $E_{out}$ 都會很接近。

而如果 $A$ 找到了一個 $g$ 使得 $E_{in}$ 接近 $0$，那麼 PAC 可以保證 $E_{in}$ 也大概會是 $0$，如此一來機器學習是可行的。

• Two Central Questions
  從第一堂課到現在，我們把機器學習的核心拆成了兩個問題：

1. 我們希望 $E_{in}$ 和 $E_{out}$ 很接近，也就是測試的結果跟訓練時得到的結果很接近
2. 我們希望 $E_{out}(g)$ 很小
   針對這兩個問題，Hypothesis Set 的大小 $M$ 又扮演什麼樣的角色？

• Trade-off on $M$
  如果 Hypothesis Set 很小，也就是 $M$ 很小，我們可以保證 $E_{in}$ 接近 $E_{out}$，但也因為 $M$ 小，演算法的選擇有限，也因此 $E_{in}$ 可能不會是一個很小的值，誤差會很大。

如果 Hypothesis Set 很大，演算法比較容易選到一個好的 $g$，如此一來可以得到一個比較好的 $E_{in}$，誤差比較小，但是 $M$ 太大的時候，我們就無法保證 $E_{in}$ 和 $E_{out}$ 接近。（根據 Hoeffding’s Inequality，壞事發生的機率會變很大很大）

選擇正確的 $M$ 和未來機器學習可以學得多好有很大的關係。

• Preview
  從上一張投影片可以知道如果 $M$ 無限大，是不是就沒辦法做了？所以接下來要探討的問題是，我們要如何解決無限大的 $M$。

Effective Number of Lines

• Where did $M$ Come From?
  Finite-bin version of Hoeffding’s Inequality 的推導是因為 $E_{in}$ - $E_{out}$ 大於誤差的事件 $B_{m}$ 發生，為了讓演算法 $A$ 可以在 Hypothesis Set 裡自由選擇，於是把每一個 hypothesis 發生不好的事情的機率 or 起來。

而最壞的情況是 $B_{m}$ 沒有重疊，每個 $P$ 都不是 0，這時候如果 $M$ 是無限大，那麼聯集也沒有上限，那這個 union bound 就沒有意義了。

• Where did Uniform Bound Fail?
  可以用 union bound 是因為每個假設會發生大誤差事件的資料集都不一樣。但實際上許多種大誤差事件發生的情況都很相似，也就是說這些事件發生的情況有很大一部份是重疊的（如右下圖）。這也造成我們高估了 union bound，導致我們沒有辦法處理 $M$ 無限大的狀況。

那麼我們能不能把這無限多個 hypothesis，分成有限多類？讓實際內容差不多的假設成為一類。

• How many Lines are there?
  怎麼把這些 hypothesis 分類呢？考慮平面上所有的線是我們的 hypothesis，有無限多條。如果只看一個資料點，其實只有兩種線，一種是將 $x_{1}$ 分成 o 的，另一種線是將 $x_{1}$ 分成 x 的。

如果看兩個資料點，就會有四種線。

• How Many Kinds of Lines for Three Inputs?
  如果有三個點呢？八種嗎？但其實有些情形是沒有辦法用一條直線來產生的。所以實際上會小於八種線。

• How Many Kinds of Lines for Four Inputs?
  四個呢？除了下圖中的被刪掉的情況無法用一條線分開，另外七張圖都可以，而且是對稱的，所以最多會有十四種可能。

• Effective Number of Lines
  隨著輸入變多，有效的線會從指數成長變成非指數成長。也就是說就算今天有無限多條線，有效的線還是有限的。如果可以用這個有限的數字 $N$ 取代掉 $M$，而這個有效的數字又比 $2^{N}$ 小，不等式的右項就會趨近於 $0$，可以保證機器可以學到東西。

Effective Number of Hypotheses

• Dichotomies: Mini-hypotheses
  如果要用線以外的 Hypothesis Set，如平面、曲線，要怎麼說我們到底有幾種假設？

我們將輸入空間變成 o 和 x 兩種情形，dichotomy 把這些點分成兩堆，產生很多 o 和 x 的組合。我們想知道一個 Hypothesis Set 可以產生多少種不同的 dichotomy。

Hypothesis Set $H$ 是指平面上所有的線，每個 $h$ 對輸入空間 $X$ 中所有的點都可以取值，且可能有無限多條。而 dichotomy $H(x_{1}, x_{2}, …, x_{N})$ 只對 $N$ 個特定的點來取值，最多只會有 $2^{N}$ 種，而這個數字可以用來取代 Hoeffding’s Inequality 裡的 $M$。

• Growth Function
  Dichotomy Set $H(x_{1}, x_{2}, …, x_{N})$ 受限於事先選好的 $x_{1}, x_{2}, …, x_{N}$，所以我們只用最大的 Dichotomy Set 的大小來當作衡量的依據，稱為 $m_{H}$，將來用來取代 $M$。$m_{H}$ 又稱為 growth function，這個函數的輸出一定是有限的。

• Growth Function for Positive Rays
  簡單的 Hypothesis Set: Positive Rays，輸入是一維的實數，都在數線上。取一個門檻值，如果輸入比門檻值大，就是 $+1$，比門檻小就是 $-1$，不同的門檻值決定不一樣的假設。可以想成 1D 的 Perceptron。

如果用這個 Hypothesis Set 可以切出 $N+1$ 種 dichotomies。

• Growth Function for Positives Intervals
  有一個區間，在區間裡就是 $+1$，區間外是 $-1$。如果是這樣的 Hypothesis Set 可以產生 $\frac{1}{2}N^{2} + \frac{1}{2}N + 1$ 種 dichotomies。

• Growth Function for Convex Sets
  定義一個 Hypothesis Set，裡頭的每個假設對應到平面上的一個 convex set（凸的集合），在集合裡的是 $+1$，集合外的是 $-1$。

這個 Hypothesis Set 的成長函數則是 $2^{N}$。如果我們找到特別的 $N$ 個點，可以根據它們把 $2^{N}$ 種 dichotomies 都做出來，就叫做 $N$ shattered by $H$。

Break Point

• The Four Growth Functions
  前面提到了三種成長函數，另外還有一種 2D Perceptrons。我們想要用成長函數取代 $M$，如果成長函數是多項式，後面 exponential 的項會減少得比較快，當 $N$ 夠大的時候，壞事發生的機率會越來越來小。如果成長函數是指數型成長，那麼就不能夠確保 $E_{in}$ 和 $E_{out}$ 接近。

那 PLA 屬於哪一種呢？

• Break Point of $H$
  當下一個輸入出現時，dichotomies 組合不再是指數型成長的的那個點，就是 break point。比如說在 2D perceptrons 時，如果只有 3 個輸入，可以做出 8 種 dichotomies，但是當有 4 個輸入時，就沒有辦法做出 16 種 dichotomies 了，所以 4 這個點就是 break point。

在這個 break point 上，$m_{H}(k) < 2^{k}$，有了一個 break point $k$ 之後，比 $k$ 大的那些也都是 break point，所以 $k$ 也叫做 min. break point。

• The Four Break Points
  Positive rays 的 break point 是 2，成長函數是 $O(N)$；positive intervals 的 break point 是 3，成長函數是 $O(N^{2})$；convex sets 沒有 break point；而在 2D perceptrons 時，break point 是 4。

這樣看下來，break point 可能跟成長函數成長的速度有一點關係。我們是否可以證明有 break point 的時候，如果 break point 在 $k$ 發生，成長函數成長的速度會跟 $N^{k-1}$ 有關係？下一堂課來證明吧！

Summary

• Recap and Preview
• Effective Number of Lines: at most 14 through the eye of 4 inputs
• Effective Number of Hypothesis: at most $m_{H}(N)$ through the eye of $N$ inputs
• Break Points: when$m_{H}(N)$ becomes ‘non-exponential’
• Slides: https://www.csie.ntu.edu.tw/~htlin/mooc/doc/05_present.pdf