1.4 Lasso方法

本節(jié)介紹Lasso方法的基本思想，以及求解用的坐標(biāo)下降法的基本理論，并介紹Lasso方法的發(fā)展，如組Lasso和圖Lasso等方法.更多詳細(xì)內(nèi)容可參考文獻(xiàn)[86].

1.4.1 回歸模型的 Lasso 方法

1.Lasso方法的定義

Lasso（Least absolute selectionand shrinkage operator）方法^[46]是指將最小二乘法的損失函數(shù)與?₁范數(shù)相結(jié)合，即對(duì)回歸系數(shù)的絕對(duì)值之和施加約束.與最小二乘法相比，?₁范數(shù)所添加的約束可以收縮系數(shù)，甚至可以迅速使系數(shù)為零，在參數(shù)估計(jì)的同時(shí)實(shí)現(xiàn)了模型選擇.因此 Lasso 方法為線性回歸提供了一種自動(dòng)選擇模型的方法.與其他的模型選擇方法不同的是，該方法得到的優(yōu)化問題是凸的，從而能夠有效地解決大規(guī)模數(shù)據(jù)處理的問題.

設(shè)有n對(duì)觀測(cè)數(shù)據(jù)（x_i，y_i），其中x_i=（x_i1，x_i2，…，x_ip）（i=1，2，…，n）是由p個(gè)解釋變量組成的向量， y_i是相應(yīng)的響應(yīng)變量，一般的線性模型形式為

令β=（β₁，β₂，…，β_p）^T為p維的系數(shù)向量，β₀為截距項(xiàng).一般地，對(duì)（β₀，β）的估計(jì)是通過最小二乘法，即最小化平方誤差的損失函數(shù)而得到的，因此有

而 Lasso 回歸等價(jià)于在最小二乘法估計(jì)的基礎(chǔ)上對(duì)估計(jì)值的大小增加一個(gè)?₁范數(shù)的約束（或稱懲罰），因此有

式（1-41）中，約束可以簡(jiǎn)化為?₁范數(shù)約束||β||₁≤t，其中，||·||₁表示?₁范數(shù).

2.Lasso方法的求解

Lasso方法的求解是一個(gè)最優(yōu)化問題，屬于帶有凸約束的二次規(guī)劃問題.為方便起見，將式（1-41）改寫成拉格朗日形式的目標(biāo)函數(shù)

假定對(duì)y_i和解釋變量觀測(cè)值x_ij進(jìn)行了歸一化處理，即，，此時(shí)，截距項(xiàng)β₀可以省略.

（1）單變量情形的軟閾值法

首先，考慮單變量的情形，訓(xùn)練樣本為（為方便起見，可將z _j看成x_ij），回歸系數(shù)為β（這里為常量），||β||₁即β，有

對(duì)于單個(gè)變量的最小化問題，通過軟閾值法，直接求解式（1-29）可以得到

式中，軟閾值算子為，以參數(shù)λ使x向0平移.

（2）多變量情形的循環(huán)坐標(biāo)下降法

坐標(biāo)下降（Coordinate Descent）法是一種簡(jiǎn)單且高效的非梯度優(yōu)化方法，其核心思想是依次沿著坐標(biāo)軸的方向最小化目標(biāo)函數(shù)的值，將一個(gè)復(fù)雜的優(yōu)化問題分解為一系列簡(jiǎn)單的優(yōu)化問題進(jìn)而去求解.

其求解過程的實(shí)質(zhì)是，每次只優(yōu)化一維變量，將其余變量視為常量，每次優(yōu)化完成后，同時(shí)在變量循環(huán)中更新相關(guān)方程；而在一般情況下，最小化的變量在眾多參數(shù)中不隨循環(huán)而改變，因此整個(gè)迭代過程將很快完成.該方法是一種迭代算法，其原理是在每次迭代中沿著當(dāng)前點(diǎn)處的一個(gè)坐標(biāo)軸方向進(jìn)行搜索，如此通過循環(huán)使用不同的坐標(biāo)方向來達(dá)到目標(biāo)函數(shù)的局部極小值.

從單變量的情形可以看出：對(duì)一般形式的Lasso問題，能夠用一種簡(jiǎn)單的逐坐標(biāo)方法求解，也就是按某種固定順序（如 j=1，2，…， p）依次求解.第 j步，令k=\ j時(shí)的系數(shù)不變，最小化k= j時(shí)的目標(biāo)函數(shù)，以更新系數(shù).

式（1-42）可以重新寫成

可以看到，每個(gè)β_j的解均可以用偏殘差表示，定義為

在此，僅保留當(dāng)前擬合結(jié)果的第 j個(gè)變量，借助偏殘差，第 j個(gè)系數(shù)可以更新為

其等價(jià)形式為

式中，為整體殘差.整個(gè)算法會(huì)通過更新軟閾值算子的方式循環(huán)更新的坐標(biāo)以及由此得到的殘差向量.本節(jié)的坐標(biāo)下降法采用了循環(huán)坐標(biāo)下降法，即每次沿一個(gè)坐標(biāo)軸的方向最小化凸目標(biāo)函數(shù)的值，可以快速求解Lasso問題.

1.4.2 組 Lasso 方法

在一些回歸問題中，具有某一相同特征的解釋變量存在天然的分組結(jié)構(gòu)，因此在建立回歸模型時(shí)就需要使同一組內(nèi)的回歸變量的回歸系數(shù)同時(shí)為 0 或同時(shí)不為 0.例如，對(duì)于解釋變量中包含多個(gè)因子水平值的定性變量，常用的方法是引入一組虛擬變量來表示多個(gè)因子水平值，這些虛擬解釋變量共同反映了定性變量的影響，在建模時(shí)應(yīng)該將其視為一組具有組效應(yīng)的變量，一起引入模型中或從模型中剔除.Lasso方法不能對(duì)數(shù)據(jù)類型存在組效應(yīng)的解釋變量進(jìn)行整個(gè)組的變量選擇，不能反映出組結(jié)構(gòu)信息，在參數(shù)估計(jì)和變量選擇時(shí)沒有充分利用數(shù)據(jù)的分組信息以提高計(jì)算速度.Yuan等^[47]提出組Lasso（group Lasso）方法，對(duì)同一組解釋變量的回歸系數(shù)施加相同的懲罰項(xiàng)，克服了Lasso方法不能對(duì)具有組結(jié)構(gòu)的解釋變量進(jìn)行組間變量選擇的缺點(diǎn).

組Lasso方法是指先對(duì)估計(jì)的回歸系數(shù)進(jìn)行分組，將每個(gè)組中待估計(jì)的回歸系數(shù)的解釋變量整體視為“單個(gè)”變量進(jìn)行變量選擇，也就是說，如果該組的系數(shù)估計(jì)值都不是0，則該組所對(duì)應(yīng)的具有組結(jié)構(gòu)的解釋變量將被全部選擇；反過來說，如果該組的系數(shù)估計(jì)值均為 0，那么該組所對(duì)應(yīng)的具有組結(jié)構(gòu)的解釋變量將被全部剔除掉.這在很大程度上增加了組間的稀疏性.

1.組Lasso方法的定義

考慮一個(gè)包含J組解釋變量的線性回歸模型， j=1，2，…，J，向量表示第 j組解釋變量.目標(biāo)是基于解釋變量集合（Z₁，Z₂，…，Z_J）預(yù)測(cè)響應(yīng)變量Y∈R.回歸模型為，其中，表示一組p _j個(gè)回歸系數(shù).

給定一組樣本量為n的觀測(cè)數(shù)據(jù)集合，組Lasso方法可以求解下面的凸優(yōu)化問題

式中，是向量θ_j的歐幾里得范數(shù).

式（1-48）是Lasso方法的組推廣形式，具有如下性質(zhì)：

（1）對(duì)于λ≥0，向量或者整體為0，或者全都不為0；

（2）當(dāng)p _j=1時(shí)，有，因此如果所有組中都只包含一個(gè)變量，優(yōu)化問題（1-48）就會(huì)變?yōu)槠胀ǖ腖asso問題.

2.組Lasso方法的求解

首先，利用矩陣—向量方式來重寫優(yōu)化問題（1-48），可得

這里為了簡(jiǎn)單起見，忽略了截距項(xiàng)θ₀，因?yàn)榭梢詫?duì)所有的響應(yīng)變量及解釋變量進(jìn)行歸一化處理，從而去掉θ₀.對(duì)于這個(gè)問題，令次梯度為0就會(huì)得到如下方程：

式中，是在處范數(shù)的次微分.如果，則必然有；如果，則為滿足條件的任意向量.

3.零次梯度法

零次梯度法首先固定所有的塊向量，然后求解.這樣做相當(dāng)于對(duì)組Lasso目標(biāo)函數(shù)采用了塊坐標(biāo)下降法.因?yàn)閱栴}是凸的，且懲罰項(xiàng)是塊可分的，所以保證了其可以收斂到一個(gè)最優(yōu)解.固定所有的，則有

式中，是第 j個(gè)偏殘差.由與次梯度相關(guān)的條件可知：如果，則，否則最小值必須滿足下式：

迭代公式（1-51）除懲罰參數(shù)λ與有關(guān)外，對(duì)沒有閉合解，除非Z_j標(biāo)準(zhǔn)正交.在這種特殊情況下，該迭代公式可以簡(jiǎn)化為

在函數(shù)（·）₊=max{0，t}中，若變量為正數(shù)，則返回該變量，否則返回0.

4.復(fù)合梯度法

復(fù)合梯度法也被稱為近點(diǎn)梯度法，其通過在每個(gè)塊中進(jìn)行計(jì)算從而實(shí)現(xiàn)迭代.每迭代一次，塊優(yōu)化問題就有一個(gè)更簡(jiǎn)單的近似問題，這樣就會(huì)得到式（1-53）的迭代公式.迭代公式的具體形式為

式中，v是步長(zhǎng)參數(shù).

1.4.3 圖 Lasso 方法

在隨機(jī)變量集合（X₁，X₂，…，X_p）的圖模型G=（V，E）的結(jié)構(gòu)學(xué)習(xí)中，常用的方法是對(duì)其協(xié)方差矩陣的逆矩陣進(jìn)行估計(jì)，即通過逆協(xié)方差矩陣中非0元素與邊集的對(duì)應(yīng)關(guān)系得到圖模型.但是隨著變量維數(shù)的增加，傳統(tǒng)的矩陣估計(jì)方法（如最大似然估計(jì)方法）在樣本量小于待估計(jì)參數(shù)個(gè)數(shù)時(shí)不可用.而 Lasso 方法的基本思想是在回歸系數(shù)的絕對(duì)值之和小于一個(gè)常數(shù)的約束條件下，使殘差平方和最小化，從而產(chǎn)生某些嚴(yán)格等于0的回歸系數(shù)，得到可以解釋的模型.通過稀疏性約束，可以處理樣本少而待估計(jì)參數(shù)過多的問題.Yuan^[87]提出了一種懲罰似然估計(jì)方法，稱之為圖Lasso 方法，用?₁懲罰約束精度矩陣的稀疏性，解決最大似然估計(jì)方法中的最大化問題.

假設(shè)來自p維高斯分布N（μ，Σ_p）的n個(gè)相互獨(dú)立樣本x₁，x₂，…，x_n，其樣本協(xié)方差矩陣記為S，則有

圖Lasso問題是使帶懲罰的對(duì)數(shù)似然函數(shù)最大化的問題，即

式中，‖Θ‖₁為?₁范數(shù)（即Θ的元素絕對(duì)值之和），tr表示矩陣的跡，det表示矩陣的行列式，λ表示懲罰參數(shù)，且有λ≥0.

設(shè)W 為協(xié)方差陣Σ_p的估計(jì)，通過坐標(biāo)下降法由W 中對(duì)應(yīng)的行和列來解決式（1-56）的最大化問題，將W 和S分塊得到

式中， s₁₂應(yīng)滿足下式

利用凸問題的對(duì)偶性，式（1-58）等號(hào)右邊等價(jià)于

式（1-59）相當(dāng)于Lasso最小二乘問題.次梯度等式可寫為

其可以由坐標(biāo)下降法求解.