---
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)
- 即使只是做 binary classification 仍然有太多選擇
- iteration 次數?
- 每一步跨多大?
- feature transform?
- regularizer 種類?
- regularizer 強弱?
- 太多組合了，總要選一種R

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

### Model Selection by Best $E_{in}$
- 如果只看 $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}$
- 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}$
- 搭拉~ validation~
- legal cheating

### Fun Time: Model Selection
- 2 仔細思考會發現是錯的

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

### Validation Set $D_{val}$
- 把 $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}$
- 找到最好的模型設定後，要用整個 $D$ 再去 train，實務上通常會比較好。

### Validation in Practice
- 實務上，最後再重用整個 $D$ 下去 train 的確比較好
- $g_m^-$ 後面變爛的原因就是 $D_{train}$ 變小了。

### The Dilemma about $K$ (Size of Validation Set)
- 我們希望 $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
- $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$
- 假設 $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
- 在 linear model 跟 constant model 選一個
- 結果用 loocv 會去選擇使用常數的那個模型 (因為我們使用平方誤差，左上那個誤差會被放大)

### Theoretical Guarantee of Leave-One-Out Estimate
- $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

### Fun Time: Leave-One-Out

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

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

### V-fold Cross Validation
- 實務上常見 $V=10$

### Final Words on Validation
- validation 因為我們還是有在做選擇，所以仍然會得到比較樂觀的結果

### Fun Time: Cross Validation

### Summary