---
# System prepended metadata

title: Ch15 Validation
tags: [機器學習基石下：方法篇]

---

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

Ch15 Validation
===

## Content

[TOC]

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


## [Model Selection Problem](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/eXysb/model-selection-problem)

### So Many Models Learned (So Many Choices)
![](https://i.imgur.com/3shLZ1L.png)
- 即使只是做 binary classification 仍然有太多選擇
    - iteration 次數?
    - 每一步跨多大?
    - feature transform?
    - regularizer 種類?
    - regularizer 強弱?
- 太多組合了，總要選一種R


### Model Selection Problem
![](https://i.imgur.com/0IwvBRI.png)
- 怎麼選呢？用眼睛去選嗎？
- 如果還記得 Lecture 12 的話，就知道
    - 高維度資料根本無法視覺化
    - 即使只有 2 維可以視覺化，我們決定 feature transform 的過程其實也要考慮腦袋裡面強大的 VC dimension，這樣算下來不見得有好處。
- **所以我們要避免用視覺化的方式去做選擇。**


### Model Selection by Best $E_{in}$
![](https://i.imgur.com/gIzYwCM.png)
- 如果只看 $E_{in}$ 去選呢？
- 那一定選到最複雜的 model 而且不加 regularization
- 而且假設就算只有兩種 model 在比較，這樣也會造成我們整體的演算法實際上就是從這兩個 model 的 hypothesis set 的集合 $\mathcal H_1\cup\mathcal H_2$ 裡面，挑出 $E_{in}$ 最小的，這樣 $\mathcal H$ 變更大RRRR
    - 會付出更多的 model complexity 的代價。


### Model Selection by Best $E_{test}$
![](https://i.imgur.com/upBACzR.png)
- finite-bin Hoeffding 可以給我們理論的保證，這之前講過了
    - $E_{out}(g_{m^*})\leq E_{test}(g_{m^*})+O(\sqrt{\dfrac{\log M}{N_{test}}})$
    - > Q: 可是忘記怎麼導出這個Q_Q，到時候再回去看
- 但是實際上不可能取得 testing data


### Comparison between $E_{in}$ and $E_{test}$
![](https://i.imgur.com/WJZ0Z9O.png)
- 搭拉~ validation~
- legal cheating


### Fun Time: Model Selection
![](https://i.imgur.com/L1FHgSX.png)
- 2 仔細思考會發現是錯的


## [Validation](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/JxUZl/validation)

### Validation Set $D_{val}$
![](https://i.imgur.com/NOWLeGV.png)
- 把 $D$ 分割成 $D_{train}$ 和 $D_{val}$
    - $D$ 有 $N$ 筆資料
    - $D_{train}$ 有 $N-K$ 筆資料
    - $D_{val}$ 有 $K$ 筆資料
- 只使用 $D_{train}$ 得到的 function 我們稱 $g_m^-$
- 這樣得到的理論保證就是 $E_{out}(g_m^-)\leq E_{val}(g_m^-)+O(\sqrt{\frac{\log M}{K}})$
    - $M$：演算法的選擇有 $M$ 種


### Model Selection by Best $E_{val}$
![](https://i.imgur.com/H6ej7x1.png)
- 找到最好的模型設定後，要用整個 $D$ 再去 train，實務上通常會比較好。


### Validation in Practice
![](https://i.imgur.com/I6xGoCn.png)
- 實務上，最後再重用整個 $D$ 下去 train 的確比較好
- $g_m^-$ 後面變爛的原因就是 $D_{train}$ 變小了。


### The Dilemma about $K$ (Size of Validation Set)
![](https://i.imgur.com/p0jG9ji.png)
- 我們希望 $E_{out}(g)\approx E_{out}(g^-)$
    - 希望 $g$ 跟 $g^-$ 越接近越好
    - 這樣需要比較小的 $K$ (因為這樣 $D_{train}$ 才會接近 $D$)
- 又希望 $E_{out}(g^-)\approx E_{val}(g^-)$
    - 希望 $E_{out}$ 跟 $E_{val}$ 越接近越好
    - 這樣需要比較大的 $K$ (根據 finite-bin Hoeffding)
- 這樣 $K$ 要用多少？常見的做法是 $\dfrac N 5$


### Fun Time: Validation Set
![](https://i.imgur.com/yCuBA0E.png)
- $25(\frac {4N}5)^2+N^2=17N^2$
- 值得注意的是，使用 validation set 來選 model，可能還比使用 $E_{in}$ 來選 model 快($25N^2$)！


## [Leave-One-Out Cross Validation](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/ftdeF/leave-one-out-cross-validation)

### Extreme Case: $K=1$
![](https://i.imgur.com/O2c11Ed.png)
- 假設 $K=1$
    - 這樣我的 $g$ 跟 $g^-$ 的確會很接近
    - 但是 $E_{in}$ 跟 $E_{out}$ 會差很多
- 定義一下 notation
    - $g_n^-$ 就是把第 $n$ 筆資料去掉的 $D_{train}$ 訓練出來的 model
    - $e_n$ 就是把第 $n$ 筆資料當 validation set，計算出來的 error
- 可是只有一筆資料算出來的 0/1 error，不是 0 就是 1 啊
- 那我們把所有可能的 $e_n$ 平均起來，是不是就會接近 $E_{out}$ 了
- leave-one-out cross validation estimate
    - $E_{loocv}(\mathcal H,\mathcal A)=\frac 1N\sum_\limits{n=1}^N e_n$


### Illustration of Leave-One-Out
![](https://i.imgur.com/PdOUDKr.png)
- 在 linear model 跟 constant model 選一個
- 結果用 loocv 會去選擇使用常數的那個模型 (因為我們使用平方誤差，左上那個誤差會被放大)


### Theoretical Guarantee of Leave-One-Out Estimate
![](https://i.imgur.com/TUgIZjT.png)
- $E_{loocv}(\mathcal {H,A})$
    - 對某 $N$ 筆資料做 leave-one-out cross validation 的 error
- $\mathbb E_\mathcal D [E_{loocv}(\mathcal {H,A})]$
    - 對所有可能的 $N$ 筆資料做 loocv 的 error 期望值
- $\overline{E_{out}}(N-1)$
    - 用 $N-1$ 筆資料 train 出來的 $g^-$ 得到的 $E_{out}$ 平均值。
    - 也就是 $\overline{E_{out}}(g^-)$
- 我們要證明 $\mathbb E_\mathcal D[E_{loocv}(\mathcal {H,A})]=\overline{E_{out}}(N-1)$
    - $\mathbb E_\mathcal D[E_{loocv}(\mathcal {H,A})]$
    - $=\mathbb E_\mathcal D[\frac 1N\sum_n e_n]$
        - 這是定義
    - $=\frac 1N\sum_n\mathbb E_\mathcal D [e_n]$
        - 期望值的性質
    - $=\frac 1N\sum_n\mathbb E_{\mathcal D_n}[\mathbb E_{(x_n,y_n)}[\text{err}(g_n^-(x_n),y_n)]]$
        - 對所有可能的 $D$ 我們都把它切出 $D_n$ 和 $(x_n,y_n)$
        - 這裡 $\mathcal D_n$ 表示把第 $n$ 筆資料拿掉的 $\mathcal D_{train}$
    - $=\frac 1N\sum_n\mathbb E_{\mathcal D_n}[E_{out}(g_n^-)]$
        - $\mathbb E_{(x_n,y_n)}[\text{err}(g_n^-(x_n),y_n)]$ 其實就代表了 $E_{out}(g_n^-)$
    - $=\mathbb E_{\mathcal D_n}[E_{out}(g_n^-)]$
        - 常數加 N 次再除 N 還是常數。
- **所以 leave-one-out cross validation 的 error 期望值會等於 $E_{out}(g^-)$ 的期望值，幾乎就等於 $E_{out}(g)$ 的期望值了。**
    - ***但是只看期望值不看 variance 太不切實際??? 這樣我只評估一筆 data 的期望值應該也差不多???***


### Leave-One-Out in Practice
![](https://i.imgur.com/jwuxAld.png)


### Fun Time: Leave-One-Out
![](https://i.imgur.com/i7vfhMR.png)


## [V-Fold Cross Validation](https://www.coursera.org/learn/ntumlone-algorithmicfoundations/lecture/6dMDR/v-fold-cross-validation)

### Disadvantages of Leave-One-Out Estimate
![](https://i.imgur.com/Fx6b9vN.png)
- loocv 有兩個主要缺點
    - Computation
    - Stability
        - 因為我現在是對單一資料點去算 $\text{err}$ 所以跳動會很大，這樣就不穩定
            - > Q: 可是這樣不是只有 0/1 error 的 case 不穩定嗎？


### V-fold Cross Validation
![](https://i.imgur.com/hvCGFTL.png)
- 實務上常見 $V=10$


### Final Words on Validation
![](https://i.imgur.com/6SylG8m.png)
- validation 因為我們還是有在做選擇，所以仍然會得到比較樂觀的結果


### Fun Time: Cross Validation
![](https://i.imgur.com/BM0PbcF.png)


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