---
# System prepended metadata

title: Ch13 Hazard of Overfitting
tags: [機器學習基石下：方法篇]

---

---
tags: 機器學習基石下：方法篇
---

Ch13 Hazard of Overfitting
===

## Content

[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [What is Overfitting?](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/uD0k3/what-is-overfitting)

### Bad Generalization
![](https://i.imgur.com/X6l9z8Z.png)
- 這之前都教過就不多贅述


### Bad Generalization and Overfitting
![](https://i.imgur.com/zPmvAxU.png)
- **bad generalization 是描述一個點的狀態：低的 $E_{in}$，高的 $E_{out}$**
- **overfitting 是在描述一個過程：$E_{in}$ 變低了，$E_{out}$ 變高了。**


### Cause of Overfitting: A Driving Analogy(比喻)
![](https://i.imgur.com/RqZnTmA.png)
- **overfit 過程之後，產生了 bad generalization 的狀態。**
- 比喻：
    - overfit
        - 出車禍
    - 使用太多 model complexity 的 power
        - 開車開太快
    - 有 noise
        - 路不平
    - 受限的資料量 $N$
        - 受限的視野，看不清路況


## [The Role of Noise and Data Size](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/deDzL/the-role-of-noise-and-data-size)

### Case Study
![](https://i.imgur.com/PSU636r.png)
- 假設我們有兩個 dataset
    - target distribution 是 10 次多項式 + 一些 noise
    - target distribution 是 50 次多項式，沒有 noise
- 那麼現在我們各用兩種 hypothesis set 去 fit 看會怎樣
    - 所有 2 次(以下)多項式 $\mathcal H_2$
    - 所有 10 次(以下)多項式 $\mathcal H_{10}$


![](https://i.imgur.com/rrXxM5A.png)
- 可以觀察到 overfitting 的過程發生了，從 $g_2$ 切換到 $g_{10}$ 的過程。
- **你居然發現，不論 target distribution 是 10 次多項式+noise 還是 50 次多項式，我從 $g_2$ 切換到 $g_{10}$ 都發生了 overfitting**


### Irony of Two Learners
![](https://i.imgur.com/F2Xypwb.png)
- 先來看看 target function 是 10 次多項式的 case 為什麼會這樣?


### Learning Curves Revisited
![](https://i.imgur.com/l2nXdY7.png)
- 資料量 $N$ 小的時候
    - $E_{in}$：$\mathcal H_{10}$ 會比 $\mathcal H_2$ 低
    - $E_{out}$：$\mathcal H_{10}$ 會比 $\mathcal H_2$ 高


### The 'No Noise' Case
![](https://i.imgur.com/hKxwvxL.png)
- 現在已經沒有 noise 了，要 fit 50 次多項式，為何 $g_{10}$ 還是做不好？
- 真的沒有 noise 嗎？其實還是有的
- **當我的 target function 很複雜，我 2 次多項式做不到，我 10 次多項式也做不到，這些差距其實都是 noise。**
- 下一堂課會更詳細的探討這個現象。


### Fun Time: Overfitting
![](https://i.imgur.com/8EjqXJ6.png)


## [Deterministic Noise](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/WLS7O/deterministic-noise)

### A Detailed Experiment
![](https://i.imgur.com/CkTKAUF.png)
- 做實驗來探討各個變數對我們的 overfit 有什麼樣的影響
    - noise level $\sigma^2$
    - target function 的次方 $Q_f$
    - 資料量 $N$


### The Overfit Measure
![](https://i.imgur.com/rGBS941.png)
- 如果 $g_{10}$ 和 $g_2$ 的 $E_{out}$ 沒有差很遠，那代表沒有什麼 overfit；差很遠的話，代表 overfit 很兇。


### The Results
![](https://i.imgur.com/e9yzKl2.png)
- 越紅越 overfit；越藍越不 overfit。
- 左圖並不怎麼意外
- 右圖就比較有趣了
    - 大部分時候它跟左圖差不多，**target complexity 扮演的角色就像 noise，complexity 越大，越容易 overfit。**
    - 那下面那部份呢？
- 下面那個就是我們課程的 logo RRRRRR居然
    - 左上&右下就是 overfitting 的圖
    - 右上是 linear model
    - 左下是 nonlinear transform
    - 這些就是 machine learning 的核心、基礎概念


### Impact of Noise and Data Size (Stochastic & Deterministic Noise)
![](https://i.imgur.com/lsEfmy5.png)
- 我們把一般的 noise 稱為 **stochastic noise**
- 我們把 target function 太過複雜所產生的類似 noise 的影響稱為 **deterministic noise**
- 所以現在有四種狀況會發生 overfitting
    - data size $N$ 不夠的時候(左右圖)
    - stochastic noise 上升的時候(左圖)
    - deterministic noise 上升的時候(右圖)
    - 當 model complexity 超過 target complexity 的時候，也就是 VC dimension 太多。(右圖下方)


### Deterministic Noise
![](https://i.imgur.com/GTGVauP.png)
- 當 target function $f$ 不同於 $\mathcal H$ 時，我們找到的最好的 $h^*$ 終究沒辦法捕捉到真正的資料分布，這之間一定會有一段差距(對應到圖中的灰色部分)，稱之為 deterministic noise
- 對 overfitting 來說，deterministic noise 跟 stochastic 的其實沒什麼兩樣
    - 學電腦科學的應該都懂，跟我們用 deterministic function 來建立 pseudo-random number 一樣意思
- 但 stochastic 跟 deterministic noise 還是有一些不一樣
    - **對同樣的 $x$ 去取 $y$ 很多次的話，會得到同樣的 deterministic 的 noise，但會得到不同的 stochastic 的 noise**
    - 除此之外，並沒有什麼不一樣。
- 我們得到的哲學是，當你今天在教一個比較簡單的 hypothesis set 的時候，不要教它太難的東西，這樣 deterministic noise 會比較小。


### Fun Time: Deterministic Noise
![](https://i.imgur.com/UxsRkYj.png)


## [Dealing with Overfitting](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/wsIPf/dealing-with-overfitting)

### Driving Analogy Revisited
![](https://i.imgur.com/Ec0vEft.png)
- 同樣的，我們用開車的比喻來說明如何避免 overfitting
    - 先使用簡單的模型
        - 開慢一點
    - 把資料清理乾淨，減少 noise
        - 使用更精準的路況資訊
    - data hinting 有時候我們沒辦法弄到更多資料，那就從我們自己對問題的瞭解去產生新的，或多的資料
    - regularization
        - 雖然可以開快車，但適時地踩煞車
    - validation
        - 隨時查看儀錶板
- 等等會先講 data cleaning/pruning 和 hinting。regularization 跟 validation 留到後面課程說明。
- 有時候這些實務上幫助機器學習做得更好的事情，甚至比演算法本身來得更重要。


### Data Cleaning/Pruning
![](https://i.imgur.com/bfFP2B3.png)
- 先偵測一下錯誤資料，怎麼偵測
    - 可能 class x 的某資料離 class o 太近了
    - 或者 class x 的某資料離 class x 太遠了
- 可以更正 label (data cleaning)
- 或者移除這個 example (data pruning)


### Data Hinting
![](https://i.imgur.com/Lk0ejBc.png)
- 小幅度的轉動/平移圖片，仍然代表相同的事情
- 加入的這些資料我們又稱 **virtual examples**
- **要注意，當你加入這些 example 也表示你的 data 不再是 i.i.d. 來自原本的 $P(x,y)！**
    - 所以加進去的 data 要注意不能偏離原來的 distribution 太遠。


### Fun Time: Data Hinting
![](https://i.imgur.com/e3O50h9.png)


### Summary
![](https://i.imgur.com/MSss1jx.png)

