---
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
- 這之前都教過就不多贅述

### Bad Generalization and Overfitting
- **bad generalization 是描述一個點的狀態：低的 $E_{in}$，高的 $E_{out}$**
- **overfitting 是在描述一個過程：$E_{in}$ 變低了，$E_{out}$ 變高了。**

### Cause of Overfitting: A Driving Analogy(比喻)
- **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
- 假設我們有兩個 dataset
- target distribution 是 10 次多項式 + 一些 noise
- target distribution 是 50 次多項式，沒有 noise
- 那麼現在我們各用兩種 hypothesis set 去 fit 看會怎樣
- 所有 2 次(以下)多項式 $\mathcal H_2$
- 所有 10 次(以下)多項式 $\mathcal H_{10}$

- 可以觀察到 overfitting 的過程發生了，從 $g_2$ 切換到 $g_{10}$ 的過程。
- **你居然發現，不論 target distribution 是 10 次多項式+noise 還是 50 次多項式，我從 $g_2$ 切換到 $g_{10}$ 都發生了 overfitting**

### Irony of Two Learners
- 先來看看 target function 是 10 次多項式的 case 為什麼會這樣?

### Learning Curves Revisited
- 資料量 $N$ 小的時候
- $E_{in}$：$\mathcal H_{10}$ 會比 $\mathcal H_2$ 低
- $E_{out}$：$\mathcal H_{10}$ 會比 $\mathcal H_2$ 高

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

### Fun Time: Overfitting

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

### A Detailed Experiment
- 做實驗來探討各個變數對我們的 overfit 有什麼樣的影響
- noise level $\sigma^2$
- target function 的次方 $Q_f$
- 資料量 $N$

### The Overfit Measure
- 如果 $g_{10}$ 和 $g_2$ 的 $E_{out}$ 沒有差很遠，那代表沒有什麼 overfit；差很遠的話，代表 overfit 很兇。

### The Results
- 越紅越 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)
- 我們把一般的 noise 稱為 **stochastic noise**
- 我們把 target function 太過複雜所產生的類似 noise 的影響稱為 **deterministic noise**
- 所以現在有四種狀況會發生 overfitting
- data size $N$ 不夠的時候(左右圖)
- stochastic noise 上升的時候(左圖)
- deterministic noise 上升的時候(右圖)
- 當 model complexity 超過 target complexity 的時候，也就是 VC dimension 太多。(右圖下方)

### Deterministic Noise
- 當 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

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

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

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

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

### Fun Time: Data Hinting

### Summary