UA MATH574M 統(tǒng)計(jì)學(xué)習(xí) Variable Selection：Cross Validation

• LOOCV
• • LOOCV score的計(jì)算
• K-fold CV
• Generalized CV

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

考慮監(jiān)督學(xué)習(xí)算法$Y=f(X)+?$，數(shù)據(jù)集為$\{(X_i,Y_i){\}}_{i=1}^n$，我們要把這個(gè)數(shù)據(jù)集分成training set和validation set，分別用來(lái)訓(xùn)練模型和調(diào)參。

LOOCV

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

LOOCV score的計(jì)算

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

K-fold CV

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

K-fold CV的思想最早出現(xiàn)在Breiman et al. (1984)中，這種方法按組移動(dòng)樣本而不是針對(duì)單個(gè)或者多個(gè)樣本進(jìn)行移動(dòng)。假設(shè)$n$個(gè)樣本被分為$K$組，每一組具有數(shù)目相同的樣本數(shù)，每一次用除第$k$組外的其他數(shù)據(jù)訓(xùn)練模型，然后計(jì)算模型在第$k$組上的validation error，重復(fù)$K$次，計(jì)算這些validation error的簡(jiǎn)單平均作為最后的validation error。記$\kappa :\{1,2,?,n\}\to \{1,2,?,K\}$記錄樣本與組數(shù)的對(duì)應(yīng)關(guān)系，則
$$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）是對(duì)LOOCV的計(jì)算的進(jìn)一步修正，平方損失下計(jì)算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}$們相差不大，我們就可以用他們的均值來(lái)做個(gè)近似：
$$S_{ii}\approx tr(S)/n$$
并定義基于這種近似計(jì)算的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$$
它可以進(jìn)一步減少計(jì)算量，并且這個(gè)東西有更好的統(tǒng)計(jì)性質(zhì)。

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。