[ML] 機器學習基石：第十五講 Validation

ML：基礎學習
課程：機器學習基石
簡介：第十五講 Validation

Model 挑選的問題

假設有 M 個 models $H_1,H_2,\cdots ,H_M$ 對應的演算法則有 $A_1,A_2,\cdots ,A_M$
目標：選出最小 $E_{out}$ 的 $H_{m^{\ast }}$ 對應的演算法為 $A_{m^{\ast }}$
但 $E_{out}$ 未知，該如何選？

• 用眼睛看？
• 不行
• 在第十二講提過，內部大腦運作後，加進去不見得比較好
• 最好的 $E_{in}$？ $m^{\ast }=\underset{1\le m\le M}{argmin}(E_m=E_{in}(A_m(D)))$
• 不行
• ${\mathrm{\Phi }}_{1126}$ 永遠比 ${\mathrm{\Phi }}_1$  好，加了 $\lambda$ 的反而比較差
• 假設在 $H_1,H_2,\cdots ,H_M$ 挑出 $g_{m^{\ast }}$，相當於在聯集 $H_1\cup H_2\cup \cdots \cup H_M$ 取，這會造成 model 複雜度上升 $d_{VC}(H_1\cup H_2\cup \cdots \cup H_M)$
• 最好的 $E_{test}$？ $m^{\ast }=\underset{1\le m\le M}{argmin}(E_m=E_{test}(A_m(D)))$
• 似乎可行
• $E_{out}(g_{m^{\ast }})\le E_{test}(g_{m^{\ast }})+O(\sqrt{\frac{logM}{N_{test}}})$
  第四講的 finite-bin Hoeffding $\mathbb{P}[E_{in}(g)-E_{out}(g)>ϵ]\le 2M{e}^{-2{ϵ}^{2}N}$
• 該如何找出測試資料？不可能，存在於未來的考試
• 最好的 $E_{val}$？ $m^{\ast }=\underset{1\le m\le M}{argmin}(E_m=E_{val}(A_m(D_{train})))$
• 從原有的 $D$ 分出一些資料 $D_{val}$
• 乾淨，未被任何演算法污染過

驗證

$$E_{out}(g_m^{-})\le E_{val}(g_m^{-})+O(\sqrt{\frac{logM}{K}})$$

流程圖

$$E_{out}(g_{m^{\ast }})\le E_{out}(g_{m^{\ast }}^{-})\le E_{val}(g_{m^{\ast }}^{-})+O(\sqrt{\frac{logM}{K}})$$

由下圖可看出

• $E_{val}(g^{-})\approx E_{out}(g^{-})$
• 需要較大的 K，才能保證兩者很接近
• $E_{out}(g^{-})\approx E_{out}(g)$
• 需要較小的 K，這樣訓練的資料才會多，才能保證兩者很接近
• 實務經驗上通常 $K=\frac{N}{5}$

訓練 $N$ 個資料，需要花 $N^2$ 的時間
若 $K=\frac{N}{5}$，且有 25 個 model，請問需要花多少時間找到 $g_{m^{\ast }}$ ？

$$\begin{array}{rl}T& =25\ast (\frac{4}{5}N{)}^2+N^2\\ & =17N^2\end{array}$$ 可以發現，若直接找最小的 $E_{in}$ 反而時間還花得比較多 $25N^2$

Leave-one-out Cross Validation

假設 K=1，$D_{val}^{(n)}=({\mathbf{x}}_n,y_n)$ 且 $E_{val}^{(n)}(g_n^{-})=err(g_n^{-}({\mathbf{x}}_n),y_n)=e_n$
那麼 $e_n$ 如何接近 $E_{out}(g)$ 呢？取平均的 $E_{val}^{(n)}$

$$E_{loocv}(H,A)=\frac{1}{N}\sum _{n=1}^N{e}_n=\frac{1}{N}\sum _{n=1}^{N}err(g_n^{-}({\mathbf{x}}_n),y_n)$$ $$\begin{array}{rl}\underset{D}{\mathbb{E}}{E}_{loocv}(H,A)& =\underset{D}{\mathbb{E}}\frac{1}{N}\sum _{n=1}^N{e}_n\\ & =\frac{1}{N}\sum _{n=1}^N\underset{D}{\mathbb{E}}{e}_n\\ & =\frac{1}{N}\sum _{n=1}^N\underset{D_{train}}{\mathbb{E}}\underset{({\mathbf{x}}_n,y_n)}{\mathbb{E}}{e}_n\\ & =\frac{1}{N}\sum _{n=1}^N\underset{D_{train}}{\mathbb{E}}\underset{({\mathbf{x}}_n,y_n)}{\mathbb{E}}err(g_n^{-}({\mathbf{x}}_n),y_n)\\ & =\frac{1}{N}\sum _{n=1}^N\underset{D_{train}}{\mathbb{E}}{E}_{out}(g_n^{-})\\ & =\frac{1}{N}\sum _{n=1}^N\overline{E_{out}}(N-1)\\ & =\overline{E_{out}}(N-1)\end{array}$$

從下圖看出，使用 $E_{loocv}$ 比 $E_{in}$ 好

缺點 Leave-one-out Cross Validation

• 極度花時間
• linear regression 有公式解，故可實現
• Error 不夠穩定
• 在實務上不常使用

V-Fold Cross Validation

想法與 leave-one-out 一樣，但不是只拿一筆，而是切成十等份，然後輪流做為驗證

$$\begin{gathered} E_{cv}(H,A)=\frac{1}{V}\sum _{v=1}^V{E}_{val}^{(v)}(g_v^{-}) \\ {m}^{\ast }=\underset{1\le m\le M}{argmin}(E_m=E_{cv}(H_m,A_m)) \end{gathered}$$

實際經驗上，通常切為十份

訓練 $N$ 個資料，需要花 $N^2$ 的時間
若為 10-fold，且有 25 個 model，請問需要花多少時間找到 $g_{m^{\ast }}$ ？

$$\begin{array}{rl}T& =(\frac{9}{10}N{)}^2\ast 10\ast 25+N^2\\ & =\frac{81}{100}{N}^2\ast 10\ast 25+N^2\\ & =\frac{81}{2}{N}^2\ast 5+N^2\\ & =\frac{405}{2}{N}^2+N^2\\ & =\frac{407}{2}{N}^2\end{array}$$

結論

• 驗證工具選用
• 若計算上允許，V-Fold 會比只有一次的驗證還好
• 5-Fold or 10-Fold 通常已足夠好，不需用到 Leave-One-Out
• 實際流程
1. 訓練：在各個 hypotheses 選出第一名
2. 驗證：針對每個第一名測試，並再選出最好
3. 測試：實際上戰場，不做任何選擇
• 驗證還是比測試樂觀，因有選擇就可能存在污染的風險
  驗證的表現再好，都沒用，只有測試的表現才最重要