鄰近點(diǎn)梯度法與交替方向乘子法求解LASSO的性能比較分析

陸萍

（蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院機(jī)電與信息學(xué)院，蘇州 215009）

鄰近點(diǎn)梯度法與交替方向乘子法求解LASSO的性能比較分析

陸萍

（蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院機(jī)電與信息學(xué)院，蘇州 215009）

0　引言

在機(jī)器學(xué)習(xí)與壓縮感知等領(lǐng)域，為了獲得具有更優(yōu)泛化性能的模型，通常需要在求解模型時(shí)對最小化經(jīng)驗(yàn)誤差施加約束，從而達(dá)到模型選擇的功能，以避免模型在訓(xùn)練集上取得優(yōu)秀的性能，但在測試集上表現(xiàn)很差的情況。即通過對模型添加正則懲罰，避免發(fā)生模型“過擬合”現(xiàn)象。通過對模型添加正則化項(xiàng)，還可以達(dá)到增加唯一解的可能性與實(shí)現(xiàn)變量選擇的功能，降低或避免僅使用經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化優(yōu)化時(shí)帶來的不適定問題，對模型起到修正作用，降低模型的復(fù)雜度。特別是在求解樣本維度遠(yuǎn)高于樣本數(shù)量的欠定方程中，適當(dāng)?shù)恼齽t可以帶來問題解的稀疏化，從而使得此類病態(tài)問題能夠獲得比較好的解。

在正則化項(xiàng)的選取上，嶺回歸［2］（Ridge Regression）獲得了廣泛的應(yīng)用，它不僅能夠很好地降低模型的復(fù)雜度，避免模型的過擬合，而且使用的L2范數(shù)正則項(xiàng)具有光滑可導(dǎo)的優(yōu)秀性質(zhì)，可以使得模型在求解時(shí)直接獲得解析解，在眾多領(lǐng)域獲得了廣泛的應(yīng)用。但L2范數(shù)正則不具備解的稀疏化能力，為此Tibshirani［2］將其替換為L1范數(shù)，獲得LASSO（Least Absolute Shrinkage and Selection Operator）模型，產(chǎn)生稀疏模型的能力，而在取得稀疏解的同時(shí)亦即實(shí)現(xiàn)了變量的選擇與降維，對于求解欠定問題非常有效。盡管在LASSO之前已有橋回歸［1］（Bridge Regression）模型，但在求解模型的算法上卻不及求解LASSO的LAR（Least Angel Regression，LAR）算法高效，因此未獲得廣泛的應(yīng)用。與LASSO模型相類似，使用矩陣Frobinus范數(shù)、核范數(shù)、譜范數(shù)、跡范數(shù)等作為正則項(xiàng)的模型也在壓縮感知、計(jì)算機(jī)視覺與推薦系統(tǒng)等領(lǐng)域中獲得廣泛的應(yīng)用。

本文對使用L1范數(shù)正則的LASSO模型進(jìn)行了簡要的介紹，并對最近提出的鄰近點(diǎn)梯度方法［3］（Proximal Gradient）與交替方向乘子法［4］（Alternating Direction Multiplier Method，ADMM）兩類適合于求解大規(guī)模問題的算法，在求解LASSO時(shí)的性能進(jìn)行了比較分析。

1　LASSO模型

對于線性回歸模型：

其中x∈Rd為回歸變量，w∈Rd為權(quán)值向量，y∈R為對應(yīng)的響應(yīng)。若當(dāng)前樣本數(shù)為N，可以通過Least Square Regression優(yōu)化:

獲得w，使用矩陣表達(dá)為:

其中X∈RN×d為樣本矩陣，y∈Rd為響應(yīng)向量。但由于抽取樣本x中隨機(jī)噪聲的存在，所需解決的問題則成為:

假設(shè)噪聲變量為獨(dú)立同分布，Ei～N（0，σ2）。基于Least Square可獲得解為w=（XTX）-1XT（y-著）。然而當(dāng)樣本中數(shù)據(jù)的維數(shù)比較高時(shí)，使用Least Square會傾向于過擬合，一種有效的方法是選擇盡量少的與輸出相關(guān)度最高的變量維度，從而只使用這些維度進(jìn)行回歸，達(dá)到特征選擇與降維的作用，而且可以比較好地解釋數(shù)據(jù)，即獲得與響應(yīng)相關(guān)度最高的維度，此即為選擇特征子集（Subset Selection）的思想。一種有效的選擇方法即為最優(yōu)子集選擇 （Best-Subset Selection），即從一個(gè)空的子集中逐漸加入與目標(biāo)函數(shù)相關(guān)系數(shù)最大的特征，或從完整的特征集合中逐步丟棄掉相關(guān)度最低的特征。然而當(dāng)樣本的維度的相當(dāng)高時(shí)，這種思想運(yùn)算量過大。而采用L2范數(shù)正則化的模型方法：

即嶺回歸對于回歸系數(shù)雖然能夠進(jìn)行一定的壓縮，但無法將其壓縮為零，因此無法產(chǎn)生稀疏解，式中的λ為正則系數(shù)，其實(shí)現(xiàn)在對數(shù)據(jù)的擬合與正則之間的平衡。與之不同的是，如果將其中的L2范數(shù)替換為L1范數(shù)正則，則可以將較小的回歸系數(shù)壓縮為0，從而可以產(chǎn)生稀疏解與實(shí)現(xiàn)特征選擇：

此即為LASSO模型。對于LASSO與嶺回歸的不同之處，在二維空間上如圖1所示。左圖為使用L1范數(shù)正則的LASSO模型，右側(cè)為使用L2范數(shù)正則的嶺回歸模型。圖中橢圓形顯示的為風(fēng)險(xiǎn)誤差函數(shù)的取值等高線，藍(lán)色的菱形或圓形區(qū)域則對應(yīng)于L1與L2范數(shù)正則項(xiàng)。由于L1范數(shù)的約束，同時(shí)滿足兩者條件的點(diǎn)可取到部分維度為0，但對于L2范數(shù)由于其約束為圓形因此很難取得部分維度為0的解。

圖1　二維空間中LASSO（左）與嶺回歸（右）示意圖

2　鄰近點(diǎn)梯度算法與交替方向乘子法

與嶺回歸具有顯式解不同的是，由于L1范數(shù)不可導(dǎo)，LASSO無法獲得其顯式解，而只可以采用基于次梯度（Subgradient）的算法迭代求解。不過由于LASSO模型仍為凸函數(shù)，從而保證了算法的最優(yōu)解的唯一性。在求解LASSO時(shí)，L1范數(shù)正則約束下的稀疏解在各維度組合上可以具有相當(dāng)大的組合數(shù)，尤其是在樣本維度高時(shí)，求解此問題成為NP-hard問題，直到LAR算法的提出，LASSO才得以獲得實(shí)際有效的應(yīng)用。使用坐標(biāo)下降（Coordinate Descent）類算法也可用來求解LASSO及其變形模型如 group LASSO，adaptive LASSO，sparse group LASSO等問題。當(dāng)前在凸優(yōu)化領(lǐng)域基于鄰近點(diǎn)算子 （Proximal Operator）的鄰近點(diǎn)梯度（Proximal Gradient Algorithm）算法，與基于分解思想的交替方向乘子法（ADMM）已被證明適合于求解大規(guī)模機(jī)器學(xué)習(xí)問題，它們也適用于求解LASSO，這里對這兩種算法進(jìn)行性能比較與分析。

2.1鄰近梯度算法

首先定義函數(shù)f（x）的鄰近點(diǎn)算子為：

即為在當(dāng)前點(diǎn)v∈Rd的周圍尋找極小化f（x）的鄰近點(diǎn)x，因此可以通過設(shè)置初始點(diǎn)，通過不斷迭代獲得最優(yōu)解x*。對于一般的使用非光滑范數(shù)正則的優(yōu)化問題：

其中f（x）為可微的凸函數(shù)，g（x）為任意的非光滑不可微凸函數(shù)。鄰近點(diǎn)梯度算法的迭代為：

對于使用L1范數(shù)約束的LASSO，由于L1范數(shù)可以求得其次梯度，其迭代過程化為逐點(diǎn)運(yùn)算的軟閾值（Iterative Soft-thresholding Algorithm，ISTA）算法:

基于鄰近點(diǎn)梯度算法，在迭代求解時(shí)，不僅使用前一次搜索到的鄰近點(diǎn)x（k），還使用更前一次搜索到的點(diǎn)x（k-1），即：

2.2ADMM方法

ADMM算法基于對變量分解與坐標(biāo)輪換的思想，對于形如：

的優(yōu)化問題，創(chuàng)建如下的增廣Lagrange目標(biāo)函數(shù)：

與式（8）類似，式（12）中f（x）與g（z）均為凸函數(shù)，通常f（x）可微，而g（z）不可微。其中為增廣Lagrange系數(shù)。通過對此增廣Lagrange函數(shù)中涉及的變量輪流優(yōu)化即可獲得最優(yōu)解。其一般迭代框架為：

但與一般迭代算法不同，ADMM算法在迭代收斂的停止準(zhǔn)則上為雙條件停止閾值判定，即原問題殘差與對偶?xì)埐罹_(dá)到收斂閾值：

3　鄰近點(diǎn)梯度算法與ADMM算法的性能比較

為了對鄰近點(diǎn)梯度算法與ADMM算法的求解LASSO的性能進(jìn)行比較，在實(shí)驗(yàn)中選取樣本維度為中等規(guī)模的d=2500，為了進(jìn)一步查看算法求解次定問題的性能，選擇樣本數(shù)為N=500。樣本各維度均由服從N （0，1）分布的隨機(jī)抽樣獲得，對回歸系數(shù)w的稀疏度取為0.05，且各元素服從N（0，1）標(biāo)準(zhǔn)正態(tài)分布，并對正確響應(yīng)向量添加0.001倍的高斯噪聲。實(shí)驗(yàn)硬件環(huán)境為Core i7 3720 CPU+8GB RAM，采用MATLAB環(huán)境，對鄰近點(diǎn)梯度算法（PG）、加速鄰近點(diǎn)梯度算法（APG）與ADMM算法的標(biāo)準(zhǔn)耗時(shí)與最優(yōu)目標(biāo)函數(shù)值進(jìn)行了比較分析。實(shí)驗(yàn)結(jié)果如下：

表1　算法性能比較

表中的“CVX”為采用CVX優(yōu)化工具箱直接求解結(jié)果。由表1可以看出ADMM算法在求解結(jié)果的性能上明顯優(yōu)于鄰近點(diǎn)梯度算法及其加速版本，無論是在求解的目標(biāo)函數(shù)值的精度上還是在算法的執(zhí)行耗時(shí)上，其性能都非常突出，可見ADMM算法在求解問題時(shí)具有顯著的優(yōu)勢。而對于鄰近點(diǎn)算法較之于基本優(yōu)化算法也具有相當(dāng)不錯(cuò)的效果，在耗時(shí)上只需基本優(yōu)化算法的1%，而其加速版本中由于利用了再前一次的搜索到的鄰近點(diǎn)信息，在求解精度上能夠稍有改進(jìn)，而耗時(shí)上也減少接近一半。

圖2　各算法目標(biāo)函數(shù)值迭代曲線

上述各算法的目標(biāo)函數(shù)值迭代曲線如圖2所示。由圖中可以看出ADMM的實(shí)際迭代次數(shù)也明顯少于其他算法，能夠很快收斂。

4　結(jié)語

本文對LASSO模型進(jìn)行了介紹，對最近提出的鄰近點(diǎn)梯度算法與交替方向乘子法在求解LASSO問題的框架進(jìn)行了分析，并通過實(shí)驗(yàn)對兩類算法在求解中等規(guī)模LASSO問題的性能上進(jìn)行比較分析。實(shí)驗(yàn)結(jié)果表明交替方向乘子法無論在求解精度還是在算法耗時(shí)上都具有顯著優(yōu)勢，因此也更適合于求解大規(guī)模機(jī)器學(xué)習(xí)問題。

［1］劉建偉，崔立鵬，劉澤宇，羅雄麟.正則化稀疏模型綜述［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（7）.

［2］Trevor Hastie，Robert Tibshirani，Jerome Friedman.The Elements of Statistical Learning:Data Mining，Inference and Prediction［M］. New York:Springer Verlag，2001.

［3］Neal Parikh，Stephen Boyd.Proximal Algorithms［J］.Foundations and Trends in Optimization，2013，1，（3）：123-231.

［4］Stephen Boyd，Neal Parikh，Eric Chu，Borja Peleato and Jonathan Eckstein.Distributed Optimization and Statistical Learning Via the Alternating Directional Method of Multipliers［J］.Foundations and Trends in Optimization，2010，3（1）：1-122.

［5］Ingrid Daubechies，Michel Defrise，Christine De Mol.An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint.arXiv，2013.

［6］Nicholas G.Polson，James G.Scott.Proximal Algorithms in Statistics and Machine Learning，arXiv，2015.

［7］Simon N，F(xiàn)riedman J，Tibshirani R.A Sparse-Group LASSO.Jounal of Computational and Graphical Statistics，2013，22（2）:231-245

［8］李亞峰.稀疏正則化的多目標(biāo)圖像分割變分模型［J］.電子學(xué)報(bào)，2013，7（7）:1329-1336

Regularized Model；LASSO；Proximal Gradient；ADMM

Performance Comparison and Analysis of Proximal Gradient and ADMM for Solving LASSO

LU Ping
（Suzhou Institute of Trade and Commerce，Suzhou 215009）

1007-1423（2015）32-0010-05

10.3969/j.issn.1007-1423.2015.32.003

陸萍（1979-），女，江蘇太倉人，講師，碩士，研究方向?yàn)閮?yōu)化算法、圖像處理

2015-11-05

2015-11-10

正則化模型是機(jī)器學(xué)習(xí)、壓縮感知與推薦系統(tǒng)等領(lǐng)域的一類重要模型，其具有變量選擇與稀疏化處理等功能，可以有效地避免模型的過擬合，完成信號重建或矩陣補(bǔ)全等工作。對稀疏正則化模型進(jìn)行介紹，分析鄰近點(diǎn)梯度算子與交替方向乘子法等最新的求解方法，并對它們的性能進(jìn)行比較分析。

正則化模型；LASSO；鄰近點(diǎn)算法；交替方向乘子法

江蘇省“青藍(lán)工程”骨干教師培養(yǎng)對象，蘇州經(jīng)貿(mào)學(xué)院院科研課題KY-ZR1407

The regularized models play an important role in a lot of fields,such as:machine learning,compressing sensing,recommending system, and so on.With the ability of variable selection and generating sparse solution,the regularized models can avoid over-fitting.They may also be applied to signal reconstruction and matrix completion.Introduces the regularized models,and analyzes two recently developed algorithms:proximal gradient and ADMM,compares the performances on solving LASSO.