陳云璐，張 楠

(復(fù)旦大學(xué) 大數(shù)據(jù)學(xué)院，上海 200433)

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

y=Xβ+ε。

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

(1)

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

(2)

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

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

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

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

1 研究方法

1.1 子抽樣框架

(3)

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

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

1.2 嶺參數(shù)的選擇

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

(4)

1.3 最優(yōu)子抽樣

當(dāng)嶺參數(shù)給定時，我們可以對每個觀測計算子抽樣概率，而后以這個概率從總樣本中有放回地抽取子樣本，我們期望這個基于子樣本的估計能達到一定的最優(yōu)性。在偏差和方差權(quán)衡恰當(dāng)時，嶺回歸估計能比最小二乘估計表現(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ī)方程?！?/p>

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定理即可得到結(jié)論1)。

(9)

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

2 算 法

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

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

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

3 仿真數(shù)據(jù)實驗

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

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

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

4 實際數(shù)據(jù)實驗

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

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

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

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

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