邻近点梯度法与交替方向乘子法求解LASSO的性能比较分析

陆萍

（苏州经贸职业技术学院机电与信息学院，苏州 215009）

邻近点梯度法与交替方向乘子法求解LASSO的性能比较分析

陆萍

（苏州经贸职业技术学院机电与信息学院，苏州 215009）

0　引言

在机器学习与压缩感知等领域，为了获得具有更优泛化性能的模型，通常需要在求解模型时对最小化经验误差施加约束，从而达到模型选择的功能，以避免模型在训练集上取得优秀的性能，但在测试集上表现很差的情况。即通过对模型添加正则惩罚，避免发生模型“过拟合”现象。通过对模型添加正则化项，还可以达到增加唯一解的可能性与实现变量选择的功能，降低或避免仅使用经验风险最小化优化时带来的不适定问题，对模型起到修正作用，降低模型的复杂度。特别是在求解样本维度远高于样本数量的欠定方程中，适当的正则可以带来问题解的稀疏化，从而使得此类病态问题能够获得比较好的解。

在正则化项的选取上，岭回归［2］（Ridge Regression）获得了广泛的应用，它不仅能够很好地降低模型的复杂度，避免模型的过拟合，而且使用的L2范数正则项具有光滑可导的优秀性质，可以使得模型在求解时直接获得解析解，在众多领域获得了广泛的应用。但L2范数正则不具备解的稀疏化能力，为此Tibshirani［2］将其替换为L1范数，获得LASSO（Least Absolute Shrinkage and Selection Operator）模型，产生稀疏模型的能力，而在取得稀疏解的同时亦即实现了变量的选择与降维，对于求解欠定问题非常有效。尽管在LASSO之前已有桥回归［1］（Bridge Regression）模型，但在求解模型的算法上却不及求解LASSO的LAR（Least Angel Regression，LAR）算法高效，因此未获得广泛的应用。与LASSO模型相类似，使用矩阵Frobinus范数、核范数、谱范数、迹范数等作为正则项的模型也在压缩感知、计算机视觉与推荐系统等领域中获得广泛的应用。

本文对使用L1范数正则的LASSO模型进行了简要的介绍，并对最近提出的邻近点梯度方法［3］（Proximal Gradient）与交替方向乘子法［4］（Alternating Direction Multiplier Method，ADMM）两类适合于求解大规模问题的算法，在求解LASSO时的性能进行了比较分析。

1　LASSO模型

对于线性回归模型：

其中x∈Rd为回归变量，w∈Rd为权值向量，y∈R为对应的响应。若当前样本数为N，可以通过Least Square Regression优化:

获得w，使用矩阵表达为:

其中X∈RN×d为样本矩阵，y∈Rd为响应向量。但由于抽取样本x中随机噪声的存在，所需解决的问题则成为:

假设噪声变量为独立同分布，Ei～N（0，σ2）。基于Least Square可获得解为w=（XTX）-1XT（y-着）。然而当样本中数据的维数比较高时，使用Least Square会倾向于过拟合，一种有效的方法是选择尽量少的与输出相关度最高的变量维度，从而只使用这些维度进行回归，达到特征选择与降维的作用，而且可以比较好地解释数据，即获得与响应相关度最高的维度，此即为选择特征子集（Subset Selection）的思想。一种有效的选择方法即为最优子集选择 （Best-Subset Selection），即从一个空的子集中逐渐加入与目标函数相关系数最大的特征，或从完整的特征集合中逐步丢弃掉相关度最低的特征。然而当样本的维度的相当高时，这种思想运算量过大。而采用L2范数正则化的模型方法：

即岭回归对于回归系数虽然能够进行一定的压缩，但无法将其压缩为零，因此无法产生稀疏解，式中的λ为正则系数，其实现在对数据的拟合与正则之间的平衡。与之不同的是，如果将其中的L2范数替换为L1范数正则，则可以将较小的回归系数压缩为0，从而可以产生稀疏解与实现特征选择：

此即为LASSO模型。对于LASSO与岭回归的不同之处，在二维空间上如图1所示。左图为使用L1范数正则的LASSO模型，右侧为使用L2范数正则的岭回归模型。图中椭圆形显示的为风险误差函数的取值等高线，蓝色的菱形或圆形区域则对应于L1与L2范数正则项。由于L1范数的约束，同时满足两者条件的点可取到部分维度为0，但对于L2范数由于其约束为圆形因此很难取得部分维度为0的解。

图1　二维空间中LASSO（左）与岭回归（右）示意图

2　邻近点梯度算法与交替方向乘子法

与岭回归具有显式解不同的是，由于L1范数不可导，LASSO无法获得其显式解，而只可以采用基于次梯度（Subgradient）的算法迭代求解。不过由于LASSO模型仍为凸函数，从而保证了算法的最优解的唯一性。在求解LASSO时，L1范数正则约束下的稀疏解在各维度组合上可以具有相当大的组合数，尤其是在样本维度高时，求解此问题成为NP-hard问题，直到LAR算法的提出，LASSO才得以获得实际有效的应用。使用坐标下降（Coordinate Descent）类算法也可用来求解LASSO及其变形模型如 group LASSO，adaptive LASSO，sparse group LASSO等问题。当前在凸优化领域基于邻近点算子 （Proximal Operator）的邻近点梯度（Proximal Gradient Algorithm）算法，与基于分解思想的交替方向乘子法（ADMM）已被证明适合于求解大规模机器学习问题，它们也适用于求解LASSO，这里对这两种算法进行性能比较与分析。

2.1邻近梯度算法

首先定义函数f（x）的邻近点算子为：

即为在当前点v∈Rd的周围寻找极小化f（x）的邻近点x，因此可以通过设置初始点，通过不断迭代获得最优解x*。对于一般的使用非光滑范数正则的优化问题：

其中f（x）为可微的凸函数，g（x）为任意的非光滑不可微凸函数。邻近点梯度算法的迭代为：

对于使用L1范数约束的LASSO，由于L1范数可以求得其次梯度，其迭代过程化为逐点运算的软阈值（Iterative Soft-thresholding Algorithm，ISTA）算法:

基于邻近点梯度算法，在迭代求解时，不仅使用前一次搜索到的邻近点x（k），还使用更前一次搜索到的点x（k-1），即：

2.2ADMM方法

ADMM算法基于对变量分解与坐标轮换的思想，对于形如：

的优化问题，创建如下的增广Lagrange目标函数：

与式（8）类似，式（12）中f（x）与g（z）均为凸函数，通常f（x）可微，而g（z）不可微。其中为增广Lagrange系数。通过对此增广Lagrange函数中涉及的变量轮流优化即可获得最优解。其一般迭代框架为：

但与一般迭代算法不同，ADMM算法在迭代收敛的停止准则上为双条件停止阈值判定，即原问题残差与对偶残差均要达到收敛阈值：

3　邻近点梯度算法与ADMM算法的性能比较

为了对邻近点梯度算法与ADMM算法的求解LASSO的性能进行比较，在实验中选取样本维度为中等规模的d=2500，为了进一步查看算法求解次定问题的性能，选择样本数为N=500。样本各维度均由服从N （0，1）分布的随机抽样获得，对回归系数w的稀疏度取为0.05，且各元素服从N（0，1）标准正态分布，并对正确响应向量添加0.001倍的高斯噪声。实验硬件环境为Core i7 3720 CPU+8GB RAM，采用MATLAB环境，对邻近点梯度算法（PG）、加速邻近点梯度算法（APG）与ADMM算法的标准耗时与最优目标函数值进行了比较分析。实验结果如下：

表1　算法性能比较

表中的“CVX”为采用CVX优化工具箱直接求解结果。由表1可以看出ADMM算法在求解结果的性能上明显优于邻近点梯度算法及其加速版本，无论是在求解的目标函数值的精度上还是在算法的执行耗时上，其性能都非常突出，可见ADMM算法在求解问题时具有显著的优势。而对于邻近点算法较之于基本优化算法也具有相当不错的效果，在耗时上只需基本优化算法的1%，而其加速版本中由于利用了再前一次的搜索到的邻近点信息，在求解精度上能够稍有改进，而耗时上也减少接近一半。

图2　各算法目标函数值迭代曲线

上述各算法的目标函数值迭代曲线如图2所示。由图中可以看出ADMM的实际迭代次数也明显少于其他算法，能够很快收敛。

4　结语

本文对LASSO模型进行了介绍，对最近提出的邻近点梯度算法与交替方向乘子法在求解LASSO问题的框架进行了分析，并通过实验对两类算法在求解中等规模LASSO问题的性能上进行比较分析。实验结果表明交替方向乘子法无论在求解精度还是在算法耗时上都具有显著优势，因此也更适合于求解大规模机器学习问题。

［1］刘建伟，崔立鹏，刘泽宇，罗雄麟.正则化稀疏模型综述［J］.计算机学报，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，Friedman J，Tibshirani R.A Sparse-Group LASSO.Jounal of Computational and Graphical Statistics，2013，22（2）:231-245

［8］李亚峰.稀疏正则化的多目标图像分割变分模型［J］.电子学报，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-），女，江苏太仓人，讲师，硕士，研究方向为优化算法、图像处理

2015-11-05

2015-11-10

正则化模型是机器学习、压缩感知与推荐系统等领域的一类重要模型，其具有变量选择与稀疏化处理等功能，可以有效地避免模型的过拟合，完成信号重建或矩阵补全等工作。对稀疏正则化模型进行介绍，分析邻近点梯度算子与交替方向乘子法等最新的求解方法，并对它们的性能进行比较分析。

正则化模型；LASSO；邻近点算法；交替方向乘子法

江苏省“青蓝工程”骨干教师培养对象，苏州经贸学院院科研课题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.