[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^*}\) 對應的演算法為 \(A_{m^*}\)
但 \(E_{out}\) 未知，該如何選？

• 用眼睛看？
• 不行
• 在第十二講提過，內部大腦運作後，加進去不見得比較好
• 最好的 \(E_{in}\)？ \(m^* = \underset{1 \le m \le M}{argmin}(E_m=E_{in}(A_m(D)))\)
• 不行
• \(\Phi _{1126}\) 永遠比 \(\Phi _1\)  好，加了 \(\lambda \) 的反而比較差
• 假設在 \(H_1,H_2,\cdots , H_M\) 挑出 \(g_{m^*} \)，相當於在聯集 \(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^* = \underset{1 \le m \le M}{argmin}(E_m=E_{test}(A_m(D)))\)
• 似乎可行
• \(E_{out}(g_{m^*}) \le E_{test}(g_{m^*})+O(\sqrt{\frac{log M}{N_{test}}})\)
  第四講的 finite-bin Hoeffding \(\mathbb{P}[E_{in}(g)-E_{out}(g)>\epsilon ] \le 2Me^{-2\epsilon ^2N}\)
• 該如何找出測試資料？不可能，存在於未來的考試
• 最好的 \(E_{val}\)？ \(m^* = \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{log M}{K}}) $$

流程圖

$$ E_{out}(g_{m^*}) \le E_{out}(g_{m^*}^-) \le E_{val}(g_{m^*}^-)+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^*}\) ？

$$ \begin{align*} T &= 25*(\frac{4}{5}N)^2+N^2\\ &= 17N^2\\ \end{align*} $$ 可以發現，若直接找最小的 \(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{align*} \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{align*} $$

從下圖看出，使用 \(E_{loocv}\) 比 \(E_{in}\) 好

缺點 Leave-one-out Cross Validation

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

V-Fold Cross Validation

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

$$ E_{cv}(H,A)=\frac{1}{V}\sum_{v=1}^{V}E_{val}^{(v)}(g_v^-)\\ m^*=\underset{1 \le m \le M}{argmin}(E_m=E_{cv}(H_m,A_m)) $$

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

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

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

結論

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