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

---

>* **本文為一系列課程之筆記，建議從" [機器學習基石筆記-1](https://hackmd.io/s/ryxzB7LwN) "開始閱讀**
>>
>* **本文討論內容請參考:
機器學習基石第十三講 : Hazard of Overfitting**

>
>* **本篇所有圖片部分由筆者製作，其它均為機器學習基石課程內容講義**
>
---

## Overfitting

如果我們手中有 N 個資料點，可以在圖形上面標示出來，高中數學告訴我們，必然存在唯一一個 N-1 次曲線 $g$ 可以通過這 N個點，而此時 $E_{in}(g)=0$


在現實情況下，這樣 $E_{in}$ 極低的情況往往在新的、未見過的資料的預測能力會非常差 ，也就是 $E_{out}$ 會非常高，這樣的「狀態」，我們稱之為 'Bad Generalization'

而我們常聽到的 'Overfitting' 或是 'Underfitting' 其實是一個「過程」

'Overfitting' 就是從 $d_{vc}^*$ 往 'Bad Generalization'移動，且 $E_{in}$遞減， $E_{out}$遞增的過程

'Underfitting' 就是從 $d_{vc}^*$ 往 'Bad Generalization'移動，且 $E_{in}$遞增， $E_{out}$遞增的過程


在機器學習的過程中，導致 Overfitting 的成因大致如下 :
1. $d_{vc}$太高
2. 太多的 $Noise$
3. 受限的 data size $N$

我們可以用下面的兩張圖來看看 $d_{vc}$、$Noise$ 與 $N$ 的關係


這圖看起來有點複雜，簡單來說結論就是 :「<font color="#dd0000">**不管我的 target function 長什麼樣子，也不管有沒有 noise，比較簡單的 model 都會有比較好的預測能力**</font>」 ，雖然不管什麼狀況 $E_{in}(g_2)>E_{in}(g_{10})$，但是 $E_{out}(g_2)\ll\ll E_{out}(g_{10})$

**究竟我們能不能從 $Noise$ 的角度來解釋左右兩遍為什麼始終都是2次模型做得比較好呢 ?**

## Stochastic Noise & Deterministic Noise

我們可以將上圖以數學式來表達 :

$y=f(x)+\epsilon$ , where $\epsilon\sim Gaussian(\sum\limits_{q=0}^{Q_f}\alpha_qx^q , \sigma^2)$
( $\epsilon$ 是從高斯分布隨機選出 with level $\sigma^2$ ; $Q_f$ 為 $f$ 的 complexity level )
並且我們可以定義出 overfit measure = $E_{out}(g_{10})-E_{out}(g_2)$

如果固定 $Q_f$，$\sigma^2$ 不同，則為左圖情形，產生的是我們熟悉的 noise ，稱為 Stochastic Noise ; 若固定 $\sigma^2$，$Q_f$ 不同，則為右圖情形，我們原本以為不會產生 Noise ，但其實 target function $f$ 的複雜度本身也會製造出 noise，這種我們稱之為 Deterministic Noise

如果今天 $f$ 的複雜度很高，即使資料本身並不存在 Stochastic Noise，在有限的資料數 N 中我們即使拿複雜度相同的 model 來fit，也會失準，因為有限資料數還是無法完全代表所有資料，這中間就會產生 Deterministic Noise , 導致我們無法找出一個絕對準確的模型。

下面的圖其實就是 $(Q_f,\sigma^2,N)$ 與 Overfitting 的關係 :

( 左邊是 Stochastic Noise 在不同資料量下對 overfitting 的影響狀況，右圖則代表著 Deterministic Noise 在不同資料量下對 overfitting 的影響狀況 )

從上圖我們可以總結 Overfitting 產生的情形通常來自於 :
(1) 資料量 N 太小
(2) Stochastic Noise 太大
(3) Deterministic Noise 太大
(4) Model Complexity 太高

## 如何避免 Overfitting ?

1. Start from simple model ( 不要一開始就使用複雜的模型 )
2. Data cleaning / Data pruning ( 對可能的 Noise 先進行處理 )
3. Data Hinting ( 以現有資料盡可能地擴展出更多資料 virtual examples )
4. Regularization (正則化 :對權重加以限制，不要無條件求最優解 )
5. Validation ( 驗證 : 將現有資料分出一部分作為驗證集，來避免掉overfitting 的狀況 )