# Two Central Questions

機器學習的兩個核心問題：

- 我們能否確保 $E_{in}(g) \approx E_{out}(g)$
- 我們能否讓 $E_{in}(g)$ 夠小

# 處理 M

原本 Hoeffding's 推廣出 M 種 h 就會有一個最粗估的上界：

$$
\mathbb{P}_{\mathcal{D}}[BAD\ \mathcal{D}] \le 2Me^{-2\epsilon ^{2}N}
$$

這是做最壞的打算，等號發生在全部的 $h$ 的壞資料都不重疊的時候。

但對於某些 $h$ 來說，他們的壞資料其實「蠻類似的」，也就是說重疊的部分很大，那麼這個上界就會不太實用。

所以我們改以「資料」的角度出發。

# 到底有幾種線

舉例來說，如果只有一個點的話，那麼線其實就只有兩種，一種線會將該點判斷為 O，另一種則是 X；同樣的邏輯推導下來，如果有 N 個點，理論上應該只有：

$$
\text{Effective # lines}\le 2^{N}
$$

這麼多種線而已，因為 N 越大後，有些情形的線會不存在，所以是小於等於。

對於 Binary Calssification ，可以發現如果有 3 個點，我們依舊可以用一條線分出 8 種 $\circ \times$ 的情形，但如果是 4 個點就不行分出 16 種情形了。
> 只有 14 種。

# Dichotomies

採用新的記號表示對一個 $\mathcal{H}$ 來說，如果給定某 N 筆資料，則到底有「幾種 $h$」：

$$
\mathcal{H}(\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{N})
$$

像上面提到的，如果只有一個點，那麼就只有兩種線而已：

$$
|\mathcal{H}(\mathbf{x}_{1})|=2
$$

# Growth Function

但是相同的 N，資料點的分佈也會造成影響，所以我們要找的是「最多有幾種情形」：

$$
m_{\mathcal{H}}(N)=\max_{\mathbf{x}_{1},...,\mathbf{x}_{N} \in \mathcal{X}}|\mathcal{H}(\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{N})|
$$

這個最多有幾種情形又叫做「成長函數 Growth Function」，這就是我們**可能可以**替換掉 M 的東西。

順帶一提這個成長函數有明確的上限：

$$
m_{\mathcal{H}}(N)\le 2^N
$$

- 在 Positive Ray 的情形中
- 也就是某個點向右是 1，向左是 -1
- 最多就是 N + 1 種
- 在 Positive and Negative Ray 的情形中
- 也就是某個點向右是 1，向左是 -1，或向左是 1，向右是 -1
- 最多就是 2(N + 1) - 2 = 2N 種
- 因為均正均負的情形會重複算到，所以要 -2
- 在 Positive Intervals 的情形中
- 最多就是 $\frac{N^{2}+N}{2} + 1$ 種
- 在 Convex Sets 情形中
- 資料點散佈在一個圓上面
- Convex Sets 指在某個「有角的區域內」是 1，以外是 -1
- 由於各種情形的資料點分佈都可以用一種多邊形表示
- 所以成長函數就是上界 $2^{N}$
- 在 2D Perceptrons 中
- 也就是我們一開始討論的用線畫分
- 雖然找不到 Growth Function 但是視情況而不同
- 可以描述為 $\le 2^{N}$

Convex Set 跟用線畫分不一樣，用線是看能用「線」將資料畫分出幾種可能的 $\circ\times$；Convex Set 則是用「多邊形」畫分出幾種可能的 $\circ\times$。

可以看到有些 $\mathcal{H}$ 的成長函數，並非是指數的 $2^N$，這樣在 Hoeffging 中，只要 N 夠大，就會被 exp 的項壓下來。

但是現在另一個問題是，有些 $\mathcal{H}$ 的成長函數，我們不知道它長怎樣。

---

# Break Point

對一個 $\mathcal{H}$ 來說，假如 $N < K$ 時滿足：

$$
m_{\mathcal{H}}(N)= 2^N
$$

此時會說這 N 個 input 「can be shattered by $\mathcal{H}$」

但是一旦 $N \ge K$：

$$
m_{\mathcal{H}}(N)< 2^N
$$

則這個 K 叫做 Break Point。

## 性質

如果是在第 K 個出現 break Point：

$$
m_{\mathcal{H}}(K) < 2^{K}
$$

那麼 K + 1，K + 2...也會滿足這個性質。證明用反證法就可以了：

$$
\text{if } m_{\mathcal{H}}(N+1) = 2^{N+1}\\
\text{then if you cover one point, there are N points remain}\\
\text{these N points must satisfy } m_{\mathcal{H}}(N) = 2^{N} \text{ which lead to a contradiction}
$$