大數據嶺回歸的最優(yōu)子抽樣

陳云璐，張 楠

(復旦大學 大數據學院，上海 200433)

線性回歸是一種用于描述響應變量y∈Y?與協(xié)變量x∈X?p關系的經典方法。對于n個獨立同分布數據考慮線性模型其中：εi是均值為0、方差為σ2的獨立同分布誤差項。模型可以寫成如下的矩陣形式:

y=Xβ+ε。

嶺回歸[1]于1970年被初次提出，最初用于解決計算最小二乘估計時X病態(tài)的問題。嶺回歸估計定義為

(1)

式中:λ>0，它被稱作嶺參數。嶺回歸估計的優(yōu)化函數可以寫成

(2)

懲罰項給估計帶來了偏差，但同時也降低了方差，我們可以通過調節(jié)嶺參數λ達到偏差與方差的權衡[2-3]，常用的方法為交叉驗證(Cross Validation, CV)和廣義交叉驗證(Generalized Cross Validation, GCV)[4]。

在海量數據上做估計往往會受到計算能力的限制，因此如何在大矩陣上處理計算問題成為了近年的研究熱點，不同領域學者從矩陣低秩估計[5-6]、機器學習算法的coreset研究[7-8]、sketching[9-11]等各角度提出了相應的方法。具體到嶺回歸這一問題中，研究者關注到了嶺杠桿值這一變量，即矩陣X(XTX+λI)-1XT的對角元素[12]，并在近年的研究中將它拓展使用于低秩投影方法中[13]。此外，有學者對壓縮矩陣是稀疏伯努利形式時的特殊嶺回歸估計問題進行研究，得到了子樣本估計的偏差和方差[14]。

子抽樣可被視作隨機投影或sketching的一種特殊情形，其一般步驟是: 從原始數據中依照某種抽樣準則來選取相應的子樣本后，使用該子樣本進行估計。根據抽樣的準則可以將現(xiàn)有研究大致分為決定性方法和隨機性方法兩類。決定性方法是指當原始觀測及子數據的數據量確定的時候，重復這一類方法得到的子樣本也是確定的，在計算子樣本估計量的方差時，這種確定性具有特定優(yōu)勢。例如，Wang等[15]提出對設計矩陣的每個維度選擇擁有極端值的觀測數據作為最優(yōu)子數據，該最優(yōu)性旨在使選出的子樣本能夠使得其信息矩陣的行列式的界被控制。隨機性方法是指給定選中每個數據的概率進行抽取，其優(yōu)點在于方法的魯棒性更強，不易受到離群值的影響。比如在大樣本線性回歸問題中，Drineas等[16]和Ma等[17-18]提出了使用杠桿值相關的量(杠桿值指X(XTX)-1XT的對角線元素)進行隨機性子抽樣。此外，在邏輯回歸[19]、分位數回歸[19]及廣義回歸[21]的框架下均有相應的隨機性子抽樣方法的研究。

本文旨在減輕大數據嶺回歸的計算負擔，即考慮樣本量n遠大于維度p的情況。Ma等[17-18]在研究普通線性回歸子抽樣問題的工作中，以子樣本估計的漸近結果為出發(fā)點，得到了線性回歸下的最優(yōu)子抽樣概率。受其啟發(fā)，我們研究了基于子樣本的嶺回歸估計的漸近偏差與方差，并使用漸近均方誤差作為抽樣概率選取的優(yōu)化準則，以期達到偏差與方差的權衡。通過計算，我們可以得到最優(yōu)子抽樣概率，其與嶺杠桿值及協(xié)變量的L2范數均有關。大部分現(xiàn)有的子抽樣方法基于回歸框架，并不考慮懲罰項，而在嶺回歸子抽樣問題中我們需額外考慮如何選擇恰當的嶺參數。由于大樣本計算的時間空間資源限制，我們很難直接在大數據整體上去計算嶺參數和嶺杠桿值。作為替代，對于嶺參數的計算，我們選擇使用在規(guī)模較小的子樣本上進行交叉驗證的方法。進一步地，對于每個嶺杠桿值，我們用其均值近似地替代其本身，這樣得到的最優(yōu)子抽樣概率正比于樣本的L2范數。我們將在理論部分闡述這兩點調整的合理性，并在仿真及真實數據上進行實驗結果的展示。

1 研究方法

1.1 子抽樣框架

(3)

在上述的基本步驟中仍有兩個問題需要解決:

我們將在后續(xù)的子章節(jié)中回答這兩個問題。

1.2 嶺參數的選擇

使用原始樣本的不同部分進行重復擬合的過程會導致很高的計算成本，尤其是在樣本量很大的情況下。廣義交叉驗證[4]被提出來以期降低交叉驗證的計算成本，其主要思想如下: 考慮留一交叉驗證(Leave-One-Out Cross-Validation, LOOCV)，即取K=n，

(4)

1.3 最優(yōu)子抽樣

當嶺參數給定時，我們可以對每個觀測計算子抽樣概率，而后以這個概率從總樣本中有放回地抽取子樣本，我們期望這個基于子樣本的估計能達到一定的最優(yōu)性。在偏差和方差權衡恰當時，嶺回歸估計能比最小二乘估計表現(xiàn)得更好，因此我們考慮一個形式上同時包含偏差和方差的優(yōu)化目標，即均方誤差。

(5)

在下面的引理中，我們給出了估計式(4)與全樣本估計式(1)之間的差值的近似。

(6)

證 通過對式(5)右邊乘I=(XTX+λI)(XTX+λI)-1，我們可以把子樣本估計重新寫成

(7)

對式(7)右邊的逆項部分使用泰勒展開，得

對另一部分，有

(XTX+λI)-1XTWy=(XTX+λI)-1{XTy+XT(W-I)y}=

由于(XTX+λI)-1XT(W-I)y，(XTX+λI)-1XT(W-I)e與(XTX+λI)-1XT(W-I)X同階，因此

(8)

第2個等號成立基于嶺回歸的正規(guī)方程。□

EAMS(Tm)=E(ZTΨmZ)=

tr(DA(Tm))+(EA(Tm)-T)T(EA(Tm)-T)。

的跡。

式中:D(x)表示方差；a=(XTX+λI)-1b。而通過嶺回歸的正規(guī)方程，我們可以將這一方差寫成

然后，使用Lindeberg-Lévy中心極限定理，可得總和的方差同樣為

由Cramer-Wold定理即可得到結論1)。

(9)

定理2得到了每個觀測的最優(yōu)子抽樣概率，它與嶺杠桿值及L2范數有關。值得注意的是，我們的子抽樣方法與從sketching角度出發(fā)的嶺杠桿值抽樣方法[13]相關但又不同，后者只與嶺杠桿值有關，在后續(xù)的仿真與真實數據上，我們將比較它們的表現(xiàn)。

2 算 法

算法1基于最優(yōu)子抽樣的嶺回歸估計

步驟2 使用子樣本計算嶺回歸估計,

相比于精確計算嶺杠桿值，這一算法避免了直接對大規(guī)模矩陣X進行處理，因此在實際操作中可以進一步去并行計算L2范數來降低計算時間。在仿真實驗中，我們將算法1的結果和使用精確嶺杠桿值的抽樣算法進行比較，從而說明嶺杠桿值近似的有效性。

3 仿真數據實驗

在仿真數據上，我們首先比較使用精確嶺杠桿值和近似嶺杠桿值抽樣的結果，然后將新方法與其他大數據嶺回歸子抽樣方法及線性回歸子抽樣方法進行比較，其中用于比較的大數據嶺回歸子抽樣方法是嶺杠桿值抽樣[13]和均勻抽樣，線性回歸子抽樣方法是最優(yōu)子抽樣[18]和基于信息的子樣本選擇方法[15]。

圖1 仿真1—6上，新方法與使用精確嶺杠桿值方法的對數均方誤差Fig.1 Logarithm of MSE comparison of our algorithm and accurate ridge leverage score subsampling on simulation 1—6

圖2 仿真1—6上，不同子抽樣方法的對數均方誤差Fig.2 Logarithm of MSE comparison of different subsampling estimators on simulation 1—6

4 實際數據實驗

本節(jié)我們關注網絡新聞數據的流行度預測，并采用相應的實際數據進行子抽樣回歸實驗。在當今這一信息爆炸的時代，人們在互聯(lián)網上晝夜不停地被各種不同來源的新聞所轟炸，對于線上媒體而言了解哪種新聞能夠引起公眾的關注至關重要，因此對新聞流行度的預測成為了一個熱門的研究話題。為了提升預測的準確性，新聞內容、關鍵字、發(fā)布日期等多類特征被提取出來后放入回歸模型中以進行新聞轉發(fā)數的預測。在本章中，我們使用的是UC Irvine提供的公開機器學習網絡新聞流行度數據集(Online News Popularity Data Set)(http:∥archive.ics.uci.edu/ml/datasets/Online+News+Popularity)。

圖3所示為通過不同方法計算出的估計量的均方誤差。在子樣本量比較小的情況下，新方法已經有了較大的優(yōu)勢，換言之，對這一實際數據，新方法能在提升計算效率的同時達到比較好的估計效果?？梢钥吹剑藭r另4個競爭方法中，線性回歸最優(yōu)子抽樣(OPT)方法和嶺回歸下的均勻抽樣(RUNIF)方法相對表現(xiàn)較好，而新方法相當于結合了這兩種方法在抽樣概率計算及懲罰項引入上的優(yōu)勢。在子樣本量較大時，新方法的表現(xiàn)依舊最優(yōu)，線性回歸下基于信息的子樣本選擇(IBOSS)方法次之，盡管IBOSS方法在子樣本量為1 600和3 200時一度接近新方法，但該方法本身在不同大小的子樣本下的表現(xiàn)差距很大。這是由于它是一種決定性方法，容易受離群值的影響，而新方法作為隨機性方法則更為魯棒，因此在不同子樣本量下新方法保持了其優(yōu)勢。

圖3 實際數據上，不同子抽樣方法的 對數均方誤差Fig.3 Logarithm of MSE comparison of different subsampling estimators on real data

表1 不同子樣本量下的對數測試集誤差比較

在不同子樣本量下，新方法的表現(xiàn)相較于各競爭方法始終更優(yōu)。此外，通過比較嶺回歸下的均勻抽樣方法和線性回歸最優(yōu)子抽樣方法在子樣本量較大時的表現(xiàn)，我們發(fā)現(xiàn)懲罰項的引入在控制測試集誤差上起到了一定的作用。相較于子樣本估計與全樣本估計的均方誤差，測試集誤差能夠更好地比較各個方法，原因在于全樣本估計和模型真實參數可能存在偏差。然而在實際數據上我們無法確知真實參數，所有樣本構成了我們可以得到的全信息。測試集誤差最小說明了新方法不僅較好地接近全樣本估計，而且也比較接近真實模型的情形。