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

陸萍

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

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

陸萍

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

0　引言

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

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

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

1　LASSO模型

對于線性回歸模型：

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

獲得w，使用矩陣表達為:

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

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

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

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

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

2　鄰近點梯度算法與交替方向乘子法

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

2.1鄰近梯度算法

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

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

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

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

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

2.2ADMM方法

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

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

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

但與一般迭代算法不同，ADMM算法在迭代收斂的停止準則上為雙條件停止閾值判定，即原問題殘差與對偶殘差均要達到收斂閾值：

3　鄰近點梯度算法與ADMM算法的性能比較

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

表1　算法性能比較

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

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

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

4　結(jié)語

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

［1］劉建偉，崔立鵬，劉澤宇，羅雄麟.正則化稀疏模型綜述［J］.計算機學(xué)報，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］李亞峰.稀疏正則化的多目標圖像分割變分模型［J］.電子學(xué)報，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ōu)化算法、圖像處理

2015-11-05

2015-11-10

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

正則化模型；LASSO；鄰近點算法；交替方向乘子法

江蘇省“青藍工程”骨干教師培養(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.