UA MATH574M 統計學習 Variable Selection：Cross Validation

• LOOCV
• • LOOCV score的計算
• K-fold CV
• Generalized CV

故事要從線性回歸開始講起。我們知道線性回歸有很多優點，模型簡單容易解釋性質良好，但它在復雜一點的現實問題中表現很差（因為現實數據質量差、結構復雜、維數高等原因）。線性回歸雖然能搞出無偏估計但方差很大，所以MSE也就不小了?，F代統計為了在解決現實問題上有所突破，選擇給估計量增加一些約束，放棄無偏性，試圖讓模型的MSE變小，這些約束放在損失函數中被稱為懲罰項。一個很重要的問題是應該怎么確定懲罰項的系數，或者說怎么調參。首先有幾個基本原則：1）數據是很貴的，所以調參要盡可能不浪費訓練模型的數據；2）調參方法不能太繁瑣，要在盡可能快的時間內完成調參；3）調參的過程最好可解釋、可推廣。如果數據真的很充裕，可以考慮在訓練集和測試集之外再設置一個validation set用來調參；如果模型比較特殊，比如線性回歸、時間序列模型等，可以推導一些理論的criteria來確定參數；除此之外最常用的是重抽樣法調參，而重抽樣法中最常用的是Cross-validation（CV）方法，所以這一講主要聊Cross-validation。

考慮監督學習算法$Y=f(X)+?$，數據集為$\{(X_i,Y_i){\}}_{i=1}^n$，我們要把這個數據集分成training set和validation set，分別用來訓練模型和調參。

LOOCV

最早提出Leave-one-out（LOO）思想的是Mosteller and Tukey (1968)，這個思想也在Allen (1971)中被用來計算PRESS（參考回歸那個系列的博文UA MATH571A 多元線性回歸II 變量選擇）。它的idea很簡單，就是每一次拿掉一個樣本，用剩下的樣本訓練模型，預測拿掉的這個樣本，計算validation error，最后通過最小化validation error來選擇超參。如果被拿走的是第$i$個，用剩下的$n?1$個樣本訓練出來的算法是${\hat{f}}_{?i}$，則validation error也被稱為LOOCV score：
$$LOOCV=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,{\hat{f}}_{?i}(X_i))$$
調參的思路是找能最小化LOOCV score的參數即可。關于LOOCV我們想了解兩個問題：LOOCV score與監督學習算法的測試誤差如何互相聯系，根據LOOCV調參是否能保證算法一定具有不錯的泛化能力？按LOOCV的定義，我們需要估計$n$次模型才能計算出LOOCV score，這貌似有點麻煩，有沒有更簡單一點的不用每leave one out都要估計一下模型的計算方法？

LOOCV score的計算

先介紹一個看起來是廢話的性質：
Leave-one-out Property 如果把$(X_i,{\hat{f}}_{?i}(X_i))$添加到去掉的第$i$個樣本的位置，我們就又有了一個$n$個樣本的數據集，用它來訓練監督學習算法，記為${\tilde{f}}_{?i}$，則
$${\tilde{f}}_{?i}(X_j)={\hat{f}}_{?i}(X_j),?j=1,?,n$$
這其實是說，如果把監督學習算法比作是貼近樣本點的某種曲面，那么把曲面上除樣本點以外的點再添加一個在樣本里面，重新估計得到的新的曲面就是原來這個曲面。我們可以把算法輸出看成$Y$的某種線性平滑：
$$\hat{f}(X)=SY$$
其中$S$是一個$n\times n$的平滑矩陣，它與$X$的取值有關；$\hat{f}(X)=[\hat{f}(X_1),?,\hat{f}(X_n){]}^T$。從而
$$\hat{f}(X_i)?{\tilde{f}}_{?i}(X_i)=S_{ii}(Y_i?{\hat{f}}_{?i}(X_i))$$
Leave-one-out Property保證了
$$\begin{gathered} \hat{f}(X_i)?{\hat{f}}_{?i}(X_i)=S_{ii}(Y_i?{\hat{f}}_{?i}(X_i)) \\ ?{\hat{f}}_{?i}(X_i)=\hat{f}(X_i)?S_{ii}(Y_i?{\hat{f}}_{?i}(X_i)) \\ ?Y_i?{\hat{f}}_{?i}(X_i)=\frac{Y_i?\hat{f}(X_i)}{1?S_{ii}} \end{gathered}$$
第二行給出了避免做n次模型估計的代換方法；如果是平方損失，則根據第三行，
$$LOOCV=\frac{1}{n}\sum _{i=1}^n{\left[\frac{Y_i?\hat{f}(X_i)}{1?S_{ii}}\right]}^2$$
這種計算方法只需要額外估計擬合值與$Y$的平滑矩陣$S$的對角元。Luntz and Brailovsky（1969）證明了LOOCV validation error是幾乎無偏的，它的期望等于$n?1$個樣本訓練的監督學習算法的預測誤差的期望。Devroye（1978）證明了在分類任務中，當去掉一個樣本訓練出來的算法與用完整數據訓練出來的算法非常接近時，LOOCV validation error的方差上界為$1/n$。

K-fold CV

Multifold CV的思想最早是Geisser (1975)提出來的，它的思想是每次移走$d$（$d>1$）個樣本，這樣一共就有$C_n^d$種移法，用移走$d$個剩下的樣本作為訓練集訓練模型，然后在這$d$個樣本上計算validation error，最后做這$C_n^d$個validation的簡單平均作為最后的validation error，通過最小化這個validation error來調參。Zhang (1993)證明了這種方法與信息準則的漸近等價性。

K-fold CV的思想最早出現在Breiman et al. (1984)中，這種方法按組移動樣本而不是針對單個或者多個樣本進行移動。假設$n$個樣本被分為$K$組，每一組具有數目相同的樣本數，每一次用除第$k$組外的其他數據訓練模型，然后計算模型在第$k$組上的validation error，重復$K$次，計算這些validation error的簡單平均作為最后的validation error。記$\kappa :\{1,2,?,n\}\to \{1,2,?,K\}$記錄樣本與組數的對應關系，則
$$C{V}_K=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,{\hat{f}}_{?\kappa (i)}(X_i))$$
如果取$\kappa (i)=i$，則K-fold CV就變成LOOCV。Zhang (1993)指出用$K=5,10$的效果一般是比較好的。

Generalized CV

Generalized CV（GCV）是對LOOCV的計算的進一步修正，平方損失下計算LOOCV score需要
$$LOOCV=\frac{1}{n}\sum _{i=1}^n{\left[\frac{Y_i?\hat{f}(X_i)}{1?S_{ii}}\right]}^2$$
如果$S_{ii}$們相差不大，我們就可以用他們的均值來做個近似：
$$S_{ii}\approx tr(S)/n$$
并定義基于這種近似計算的LOOCV score為GCV score
$$GCV=\frac{1}{n}\sum _{i=1}^n{\left[\frac{Y_i?\hat{f}(X_i)}{1?tr(S)/n}\right]}^2$$
它可以進一步減少計算量，并且這個東西有更好的統計性質。

總結

以上是生活随笔為你收集整理的UA MATH574M 统计学习 Variable Selection：Cross Validation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。