# 林軒田機器學習基石筆記 - 第五講、第六講
###### tags: `林軒田` `Maching Learning` `機器學習基石`

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第五講 : Training versus Testing
機器學習基石第六講 : Theory of Generalization**
>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>

---

回顧上一篇的結論，只要 Hypothesis set $\mathbb{H}$ 是有限集 (#$\mathbb{H}=M$ is finite)，且dataset $\mathbb{D}$ 有夠多的資料(#$\mathbb{D}=N$ is large enough)，我們就能確定 :

$\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)$ 有一個很小的上界$2Me^{-2\epsilon^2N}$

$\implies E_{out}$與 $E_{in}$ 夠接近 ( Learning Algorithm 從 $\mathbb{H}$ 選出來的 $g$ ，$E_{out}(g)$與 $E_{in}(g)$ 夠接近 )

$\implies E_{in}(g) \rightarrow 0$ 則 $E_{out}(g) \rightarrow 0$
<br>

那我們現在有兩個問題要解決 :

1. **$2Me^{-2\epsilon^2N}$這個上界夠好嗎?**
2. **如果 $\mathbb{H}$ 是 $infinite\ set$ ?**

這兩個問題其實是一體兩面，解決了一個，另外一個也就能順利解決。
我們能不能找到一個足以代表 $infinite\ \mathbb{H}$ 的一個 $finite\ number\ -m_{\mathbb{H}}$ 替換掉 $M$ ，形成一個更逼近的上界，也可以處理 $infinite\ \mathbb{H}$沒有上界的情況 ?

### $2Me^{-2\epsilon^2N}$這個上界夠好嗎?
<br>


這是一個簡單的文式圖，如果我們今天要算 $B_1\cup B_2\cup B_3$ 數量的上界，最簡單的莫過於直接把三者數量相加， $B_1+B_2+B_3$ 絕對是 $B_1\cup B_2\cup B_3$的其中一個上界，但我們也很清楚的知道，當三者重疊部分越多，這樣的上界越不逼近。

但在上一篇的證明中，我們卻利用這樣的方法找出其上界


當 $M$ 為 $finite$ 時還行得通，反正我們只要確定有上界即可逼近，但當 $M$ 為 $infinite$ 時就會出現很大的問題。

### 如果 $\mathbb{H}$ 是 $infinite\ set$ ?
---
在處理這個問題以前，我們先定義一些概念:
1. **dichotomy**
以 $\mathbb{R}^2$ 為例，在其中有$N$個資料點 $\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N$，則顯然的能將這 $N$個資料點進行二元分類的 $\mathbb{H}$ 是一個 $infinite\ set$ (任何一條在 $\mathbb{R}^2$ 的直線都是一個 $h$)。
從數學的角度來說， $dichotomy$ 代表的是一個族 ( $family$ )，就 hypothesis $\mathbb{H}$ 來看，若把對 $\mathbb{X}_1,\mathbb{X}_2,...,$family$\mathbb{X}_N$ 進行同一種分類的 $h$ 視為同一族，那麼我們便可以將無限多的 $h$ 變成有限個 $dichotomies$。

2. **Growth Function $m_\mathbb{H}(N)$ :** $\mathbb{H}\rightarrow\mathbb{R}^1$
$m_\mathbb{H}(N)=\max\limits_{\forall x_i\in\chi}(\mathbb{H}(\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N ))$，這函數白話一點來說，就是所有的 $h$ 到底可以把資料點做出多少種不同的二元分類。在 Machine Learning 的討論中，$N$ 都是有限正整數，那麼$m_\mathbb{H}(N)$出來的值也必然會是有限正整數 ( $\leq2^N$ )[^1]

[^1]:為什麼 $m_\mathbb{H}(N)$ 不一定會等於要取 $\max$ ? 為什麼不等於$2^N$?
從排列組合的觀點來看，$N$ 個點的二元分類應該要有 $2^N$ 種，但我們這裡要的是 $"Linear\ separable"$ 所以會有所差異。
從上圖可以看出來，$N=4$ 時，應該會有16種二分法，但是由於我們要求線性可分，因此一定「至少」有兩種 ( 圖中打 X 的狀況以及其對稱情況 )不符合我們的需求。 為什麼是「至少」? 如果這 $N$ 筆資料有特別的排列情況(EX:共線)，當然有可能有更多種狀況會被排除，但，$m_\mathbb{H}(N)$函數要的是「max」，也就是說我現在要看的是被排除最少的情況，所以在 $N=4$ 時，$m_\mathbb{H}(4)=14$ ( 那兩種被排除的狀況，就是不管四筆資料怎麼分布，絕對都會被排除 )
當然，$m_\mathbb{H}(N)$也會跟資料本身處的維度空間有關。

3. **shatter**
我們說 $\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N$ 可以被 $shatter$ $\implies m_\mathbb{H}(N)=2^N$ (所有的分類情況都會發生)。所以在 $\mathbb{R}^2$ 情況下，$\mathbb{X}_1,\mathbb{X}_2,...,\mathbb{X}_N$ 可以被 $shatter$ (當 $N\leq3$)

$Mathematical\ \ \ Definition\ :$
$C\ shatters\ A\ \ if\ \ \forall a\in A，\exists c\in C\ \ s.t\ \ a=c\cap A \\ i.e.\ \mathbb{P}(A)=\left\{ c\cap A \mid\ c\in C\right\}$
<br>
4. **Break Point**
第一個不會被 $shatter$ 的 $N$，在 $\mathbb{R}^2$ 情況下，$break\ point=4$
> Break Point是一項很重要的指標，代表著當 $N>Break\ Point$ 時，整個成長會大幅趨緩 ( $O(N)\ll 2^N,when\ N>Break\ Point$ )。

5. **Big O** ( Time complexity 、成長速度、無限大漸進概念)

$Mathematical\ \ \ Definition\ :$
$Given f(x),g(x)\ \ \\\exists\ M,x_0\ \ \forall\ x\geq x_0\ \ s.t.\ \mid f(x)\mid\leq M\mid g(x)\mid \\\implies\ f(x)\in O(g(x)) \ or\ f(x)=O(g(x))$

| 資料空間 &分類型態[^2] | Break Point | $m_\mathbb{H}(N)$ | O(N) |
| -------- | -------- | -------- | -------- |
| 1-D Positive ray | 2 | N+1 | $O(N)$|
| 1-D Positive interval | 3 | $\frac{1}{2}N^2+\frac{1}{2}N+1$ | $O(N^2)$ |
| Convex Set | $\infty$ | $2^N$ | -- |
| 2-D Perceptron | 4 | $<2^N$ (in some cases) | $O(N^3)$ |

[^2]:林軒田教授在課堂上講了四種的資料空間及分類型態 :
**2-D Preceptron , 1-D Positive Ray , 1-D Positive interval and Convex Set**
<br>
 

6. **Bounding Function $B(N,K)=\max\limits_{N>K}(m_{\mathbb{H}}),\ where\ K=Break\ Point$**
這樣看起來還是有點抽象，我引用林軒田與Yaser S . Abu-Mostafa所著的 " Learning From Data " 一書的說法比較清楚 :
$$B (N, k)\ is\ the\ maximum\ number\ of\ dichotomies\\ on\ N\ points\ such\ that\ no\ subset\ of\ size\ k\ of\ the\ N\ points\ can\ be\ shattered\\ by\ these\ dichotomies.$$
在討論Bounding Function時，我們已經不管分類的型態是什麼，單純只看Break Point K為多少。(1-D perceptron 或是 1-D positive ray K值都是3)

(這邊在課堂上都保守的以 $\leq$ 表示，但實際上有更強的 $=$ 關係)

從上圖我們可以發現Bounding Function的幾個重要性質[^3] :
$$B(N,K)=B(N-1,K)+B(N-1,K-1)$$$$m_\mathbb{H}(N)\leq B(N,K)$$

[^3]:**試證明 $B(N,K)=B(N-1,K)+B(N-1,K-1)$**
Claim : $B(N,K)=\sum\limits_{j=0}^{K-1}{{N}\choose{j}}$
<p.f>
$B(N,K)\\=2^N-{{N}\choose{K}}-{{N}\choose{K+1}}-...-{{N}\choose{N}}\\={{N}\choose{0}}+{{N}\choose{1}}+{{N}\choose{2}}+...+{{N}\choose{K-1}}\\=\sum\limits_{j=0}^{K-1}{{N}\choose{j}}$
$B(N,K)$的最高次項為$N^{K-1}$
因為最後一項為$\frac{N(N-1)(N-2)...(N-K+1)}{K!}$
<br>
$\because B(N,K)=\sum\limits_{j=0}^{K-1}{{N}\choose{j}}={{N}\choose{0}}+{{N}\choose{1}}+{{N}\choose{2}}+...+{{N}\choose{K-1}}\\
={{N}\choose{0}}+({{N-1}\choose{1}}+{{N-1}\choose{0}})+({{N-1}\choose{2}}+{{N-1}\choose{1}})+...+({{N-1}\choose{k-1}}+{{N-1}\choose{k-2}})\\
={{N-1}\choose{0}}+({{N-1}\choose{1}}+{{N-1}\choose{2}}+..+{{N-1}\choose{k-1}})+({{N-1}\choose{0}}+{{N-1}\choose{1}}+..+{{N-1}\choose{k-2}})\\
=\sum\limits_{j=0}^{K-2}{{N}\choose{j}}+\sum\limits_{j=0}^{K-1}{{N-1}\choose{j}}$

---
現在所有的工具都準備好了，我們該準備來面對上面的問題了~
為了避免因為 $infinite\ \mathbb{H}$ 而造成的上界快速擴張狀況，我們用$m_\mathbb{H}(N)$來取代原本的 $M$
最後可以得到一個比較逼近的上界[^4] :
$$\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)\leq 4m_\mathbb{H}(N)e^{\frac{1}{8}\epsilon^2N}$$
我們稱之為 $Vapnik-Chervonenkis Bound\ (VC\ Bound)$

[^4]: 證明 $\mathbb{P}(\mid E_{out}(\mathbb{H})-E_{in}(\mathbb{H}) \mid>\epsilon)\leq 4m_\mathbb{H}(N)e^{\frac{1}{8}\epsilon^2N}$
<p.f>
Step1 :
Assume $D'$ iid with $D$ is a data set with size N (ghost data)
(若$E_{in}$與$E_{out}$離得很遠，則$D$裡面N筆資料大多沒選到error點，那母體種再取N個點($D'$)就會包含比較多的error，$E'_{in}$與$E_{out}$就會有較大機率會比較靠近)
<br>
PS: $E_{in},E'_{in}\ and\ E_{out}$，其實就是個別代表著實務上的 $E_{train},E_{val}\ and\ E_{test}$
<br>
Step2 :
當$N$足夠大時，$E_{in}(E'_{in})$的整體分布狀況會近似於以$E_{out}$為中心的常態分佈，$E_{in}$越往右跑，$E'_{in}$會越往左靠
<br>
$\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})$
$\geq\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\ and\ \sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
$=\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)\times\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\ \
\mid \ \sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
|$\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\mid\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$|
| -------- |
| $\mathbb{P}(A\mid B)$ :在B條件下，A發生的機率 |
| $\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2}\mid\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$ $\geq\mathbb{P}(\mid E_{in}(h^*)-E'_{in}(h^*)\mid>\frac{\epsilon}{2}\mid\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$ $(\because\mid E_{in}(h^*)-E'_{in}(h^*)\mid>\frac{\epsilon}{2}\implies\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})$ $\geq\mathbb{P}(\mid E_{in}(h^*)-E'_{in}(h^*)\mid\leq \frac{\epsilon}{2}\mid\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$ $(\because\mid E'_{in}(h^*)-E_{out}(h^*)\mid\leq \frac{\epsilon}{2}\ and\ \sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon$ $\implies\mid E_{in}(h^*)-E'_{in}(h^*)\mid>\frac{\epsilon}{2})\\\geq 1-2e^{-2({\frac{\epsilon}{2}})^2N}$
$\therefore\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq(1-2e^{-2({\frac{\epsilon}{2}})^2N})\times\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
<br>
Step3 :
W.L.O.G assum : $e^{\frac{1}{2}\epsilon^2N}< \frac{1}{4}$
(if not ,VC BOund 顯然為真)
$\therefore\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq\frac{1}{2}\times\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
$\therefore 2\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\geq\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
<br>
Step4 :
現在整個母體的機率已經被我們用$D\ and\ D'$限制住
$\mathbb{P}(\mid E_{in}(h)-E_{out}(h)\mid>\epsilon)$
$\leq2\mathbb{P}(\sup\limits_{h\in\mathbb{H}}\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})$
$\leq 2\sum\limits_{h\in\mathbb{H}}\mathbb{P}(\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})$
$=2m_\mathbb{H}(2N)\times\mathbb{P}(\mid E_{in}(h)-E'_{in}(h)\mid>\frac{\epsilon}{2})\mid)$
($\because$把$D,D'$作為一個母體來看)
$=2m_\mathbb{H}(2N)\times\mathbb{P}(\mid E_{in}(h)-\frac{E_{in}(h)-E'_{in}(h)}{2}\mid>\frac{\epsilon}{2})>\frac{\epsilon}{4}\mid)$
($\because E_{in}(h)-E'_{in}(h)<\frac{\epsilon}{2}\implies\frac{E_{in}(h)-E'_{in}(h)}{2}<\frac{\epsilon}{4}\implies E_{in}(h)-\frac{E_{in}(h)}{2}-\frac{E'_{in}(h)}{2}<\frac{\epsilon}{4}$)
$\leq 2m_\mathbb{H}(2N)\cdot 2\cdot e^{-2e^{-2({\frac{\epsilon}{2}})^2N}}$($\because$針對單一$h$，所以$M=1$)
$=4m_\mathbb{H}(2N)e^{-\frac{1}{8}\epsilon^2N}$得證

<br>

### 結論
$\mathbb{P}(\mid E_{in}(g)-E_{out}(g)\mid>\epsilon)$
$\leq 4m_\mathbb{H}(2N)\cdot e^{-\frac{1}{8}\epsilon^2N}$
$\leq 4(2N)^{K-1}\cdot e^{-\frac{1}{8}\epsilon^2N}\ ,\ if\ N\ is\ large\ enough\ and\ K\ exists.$
($\because m_\mathbb{H}(N)\leq B(N,K)\leq N^{K-1}$)
<br>
$\therefore$存在 $Break\ point$ 且 $N$ 夠大的情況下，即使 $infinite\ \mathbb{H}$，演算法從$E_{in}$很小的條件下挑出一個 $g$，都一定會有一個有限上界可以確保$E_{in}$跟$E_{out}$夠接近。