基于随机L-BFGS的二阶非凸稀疏优化算法

刘光宇，张令威，杭仁龙

(南京信息工程大学江苏省大数据分析技术重点实验室，江苏 南京 210044)

1 引言

近年来随着科学技术的发展与信息开放性的提高，社会中如电子信息、卫星遥感和医学成像等领域都随时随地地产生着海量的视频、图像与文本数据。通常情况下，这些数据都具有维度过高的特性，其中部分数据的维度甚至超过了样本本身的数量。但是这些超高维的特征可能只有部分与最后的预测结果相关，所以如何挖掘到这些有用的特征成为了机器学习领域一项十分重要的研究内容，同时也是稀疏学习中最重要的研究课题之一[2]。在以往的稀疏学习任务中，通常需要通过施加l0约束来实现模型参数的稀疏化。一般来说，一个高效且鲁棒的稀疏模型对稀疏问题的解决有很大的帮助。以下是一个稀疏化模型的通用形式

(1)

2 相关工作

近年来，研究人员提出了很多优秀的算法来解决问题(1)[[2]，比如，如果将式中的损失函数设置为最小二乘损失函数，那么它就是压缩感知领域中一个十分重要的问题[3]。Joel 等人提出了正交匹配追踪(OMP)算法[4]，该算法在每次迭代过程中选取和测量向量相关性数值最大的原子，然后重新更新系数以保证所选原子与残差是正交的。在OMP算法基础上，Needell等人提出压缩采样匹配追踪算法(CoSaMP)[5]，论文中借鉴了多种算法思想以保证算法的收敛速度。Thomas等人提出了另外一种具有较好鲁棒性特性的算法——迭代硬阈值法(IHT)[6]，该算法在每次迭代过程中只保留具有最大绝对值的元素，将其它元素设为0，取得了良好的效果，与此同时作者也提供了充分的理论来证明该算法的有效性。通过结合CoSaMP和IHT算法，Foucart提出了硬阈值追踪法(HTP)[7]，该算法具有更快的收敛速度。上述算法都是压缩感知领域的经典算法，而如果问题(1)的模型是逻辑回归模型或者图网络模型，那这个问题就转化成机器学习领域的重要问题。Bahmani等人将梯度信息与参数信息都进行截断操作，提出了梯度支持追踪法(GraSP)[8]。上文中提到的IHT算法同样可以被运用到机器学习领域，Yuan等人将IHT算法的思想与梯度下降法结合，提出了梯度硬阈值追踪法(GraHTP)[9]。基于随机方差缩减梯度法(SVRG)[10]，Li等人引入了IHT算法思想来解决稀疏约束问题，提出了SVR-GHT算法[11]。通过改变独特的采样方法，Zhou提出混合随机梯度硬阈值法[12]。除一阶优化算法外，基于二阶稀疏优化的算法也引起了学业界的关注[13]。

本文算法受Philipp等人Stochastic L-BFGS[14]算法以及Rite Kolte工作[15]的启发，通过在参数更新的过程中引入二阶信息的方式提升模型的性能。二阶优化算法与一阶优化算法相比，可以取得更快的收敛速度。传统的二阶优化算法是牛顿法[16]，在参数更新过程中算出损失函数对应于参数的二阶导数(即Hessian矩阵)，并将其运用到参数更新过程中去。但是牛顿法很少被运用到机器学习中，原因是要求Hessian矩阵必须是半正定，而且Hessian矩阵及其逆矩阵的计算对计算机的算力要求很高，运用到高维或者超高维的数据中不是很现实。例如，要是一个数据的特征维度是d，那么算出的Hessian矩阵维度d×d，如果是高维或者超高维的数据，那么其计算量将会很大，一般的个人计算机的算力是无法满足这种要求的。所以本文采用了拟牛顿法的思想，用一阶曲率信息来近似二阶信息，算法采用L-BFGS算法，该算法可以通过一阶信息近似Hessian矩阵，达到节省算力的目的。与此同时，本文采用迭代硬阈值(IHT)算法对参数施加稀疏约束。为了叙述方便，本论文将算法简称为SLH算法。

本篇论文的主要贡献有以下几点：①本文提出了一种新的用于稀疏约束的算法，该算法与一些经典的稀疏优化算法相比，有更快的收敛速度与准确度； ②该算法将二阶信息利用到参数更新的过程中去，所以有更快的收敛速度。与传统的牛顿法相比，本算法不需要计算Hessian矩阵及其逆矩阵，大大节省了模型的运算量； ③本文算法具有良好的泛化性，可以运用到很多经典的机器学习模型上，取得了良好的效果。

3 算法

在本节中，将首先简要介绍优化算法的一些知识，然后介绍随机 L-BFGS算法与IHT算法。本文将IHT运用在随机L-BFGS算法中来保证稀疏约束条件，提出了新的SLH算法，获得了更好的模型性能。

3.1 预备知识

对于一般的优化算法，将会使用如下的通用的参数更新规则

wp+1=wp-ηpHpvp

(2)

若使用的是以牛顿法为代表的二阶优化算法，式(2)中的Hp就是Hessian矩阵的逆矩阵[17]。但是由于Hessian矩阵的计算复杂度过大，常常用一阶曲率信息来近似Hessian矩阵[18]-[20]。本文采用的是L-BFGS算法[19]，该算法会在下面的算法介绍中具体提到。

3.2 随机L-BFGS算法

Stochastic L-BFGS[14]算法是SVRG算法和L-BFGS算法的结合，该算法被证明在强凸性和光滑的损失函数上可以达到线性收敛的速度。算法的参数更新规则如下

xt+1=xt-ηHvt

(3)

其中vt的获取是通过SVRG算法得到的。

(4)

3.3 迭代硬阈值法(IHT)

迭代硬阈值法[6]是一种用于压缩感知重构恢复的算法，该算法是一种迭代算法，在每次迭代过程中，取向量初始值β0=0，迭代公式如下：

(5)

其中case1 指的是如果|βn，i|属于前k个数值上最大的元素。

3.4 SLH算法

受文献[11]中算法启发，本文将硬阈值截断操作放在内循环之后，具体算法流程如下SLH算法伪代码所示。

SLH算法

输入：初始化参数w0；参数m，n；批量样本个数b；步长η；稀疏化参数k

1) 初始化：H0=I，p=0，t=0

2)Forp=0，…，n-1

3) 计算全局梯度：μp=∇f(wp)，依据(4)式计算Hp，β0=wp

4)Fort=0，…，m-1

5) 样本采样：Sp，t={1，2，…，b}

6) 计算采样样本梯度：∇fSp，t(βt)

7) 计算方差衰减梯度：

vt=∇fSp，t(βt)-∇fSp，t(wp)+μp

8) 参数更新：βt+0.5=βt-ηHpvt

9) 执行截断操作：βt+1=HTk(βt+0.5)

Endfor

10)wp+1=βm

EndFor

输出：wn

本算法与文献[11]算法最大的不同就是在参数过程中引入了拟牛顿项，也就是引入了二阶信息，由于二阶信息较一阶信息而言搜索范围更加广泛，所以这种操作可以有效地加速算法的收敛速度。相较于一般的牛顿算法，该算法不需要直接计算Hessian矩阵及其逆矩阵，只需用到一阶曲率信息，所以计算量大大减少，收敛速度也大大加快。

依据文献[14]，在不执行截断操作时，即不执行步骤9时，上述算法符合单调递减的性质。但是需要符合两个假设：

假设1：损失函数fi是凸函数且符合二阶可微条件；

假设2：存在两个常量λ和Λ，满足以下条件

λI≤∇2fτ(w)≤ΛI，

(6)

如果符合上述两个假设，当m和η满足：γλ>1/2mη+2ηΓ2Λ2，上述算法是单调递减的，其中γ=1/(d+M)Λ，M为Stochastic L-BFGS算法关于曲率存储量的参数，由人为设定，d为所学习参数的维数，Γ=((d+M)Λ)d+M-1/λd+M。

本算法在计算Hp时会花费大量的资源，因为算法在需要存储必要的曲率信息，即每次更新的参数值以及参数的梯度值，同时构造Hessian矩阵近似值也需要花费资源。所以，适当减少Hp的计算频率或者适当选取M都可以减少算法的资源消耗量。

4 实验

本部分主要证明所提出的算法的有效性，本文算法被运用到线性回归模型(Linear Regression)和逻辑回归模型(Logistic Regression)中，所用的数据集是RCV 1数据集以及20Newsgroup数据集，算法实验环境为四核的2.60 GHz的CPU和8GB的RAM，使用MATLAB R2015a平台对算法进行了编程实现。

4.1 实验模型

如上文所说，本文将提出的算法运用于线性回归模型以及逻辑回归模型。

4.1.1 线性回归模型

线性回归模型是机器学习领域中十分常见的一种模型，其表达方式如下所示

y=wTx+e

(7)

式中w是需要学习的参数，(x，y) 分别为监督学习数据以及标签，e是服从0均值正态分布的误差项。为学习上述模型，最常使用的方法是最小二乘法，其损失函数的形式如下

(8)

上式中n是总样本个数，λ是正则化系数。

4.1.2 逻辑回归模型

逻辑回归是机器学习领域十分常见的分类器，该分类模型是一种广义的线性分析模型，常用于数据挖掘等领域，该分类器常常运用于做二分类问题，即该机器学习任务的标签只有两个值。逻辑回归损失函数可以表示为：

(9)

式中，w是需要学习的线性模型的参数，yi∈{-1，1}是学习任务中的二值化标签，xi∈d是训练集数据中d维的特征向量。在一般的机器学习任务中，常常在逻辑回归的损失函数后面加入l2正则化项，这么做的好处是可以有效减少过拟合的问题：

(10)

式中λ>0表示的是正则化参数，可以由人工设定，表征对参数的惩罚程度。

4.2 数据集

在本实验中，用了两个不同的数据集。其中RCV1数据集包含路由社(Reuters)英文文本以及对应类别的数据[21]，该数据既可以应用于文本分类和自然语言处理的任务，数据集中共有20242个训练数据以及677399个训练数据，每个数据共有47236个特征。在本文的实验中选用所有的20242个训练样本，并且选用20000个测试样本。

20Newsgroup数据集[22]是由大约20000个不同的新闻文件组成的数据集，该数据集有10000个训练样本和9996个测试样本，每个样本含有1355191个特征。

4.3 对比算法

以下是本文采用的四种一阶优化对比实验算法。

FCFGS：FCFGS[24]算法是一种正向贪婪选择算法，该算法依据梯度信息来进行稀疏化操作。

GraSP：GraSP[8]算法是一种迭代贪婪算法，该算法在做稀疏化操作时同时考虑梯度以及参数大小。

GraHTP：GraHTP[9]算法在标准梯度下降法的基础上加入迭代硬阈值算法的思想，从而满足了稀疏化约束。

FoBa：FoBa[24]算法在正向传播的基础上加入自适应反向传播，加快了算法收敛速度。

图1 线性回归模型实验结果图

本文选取的算法均属于一阶稀疏优化算法，通过与上述的一阶稀疏优化算法对比，可以发现二阶优化算法在稀疏优化学习中的性能更优越。本文算法(简称SLH)就算法运行时间(CPU Time)以及算法分类准确度(Classification Error)对各种算法进行了实验比较。

4.4 实验结果

本节将展示SLH算法与各类对比算法在线性回归模型以及逻辑回归模型上面应用的结果。

4.4.1 线性回归模型

本小节将展示各类算法在线性回归任务中的实验结果。实验采用RCV1数据集，实验中所有的正则化参数λ均取值10-5，稀疏度k∈[100：100：1000]，实验结果如下图1所示，可以看出在算法收敛方面，本文提出的算法(SLH)略优于FCFGS算法，在算法准确度方面，与GraSP算法实验结果相当。综上所述，在同时考虑准确度与效率的情况下，本算法性能优于其它算法。

4.4.2 逻辑回归模型

本小节将展示各类算法在逻辑回归任务上的实验结果，实验分别采用了RCV1与20Newsgroup两个数据集，实验中正则化参数λ均取值10-5，稀疏度在RCV1数据集上k∈[100：100：1000]，在20Newsgroup数据集上，本文分别采用了四种不同的稀疏度：k∈{1000，2000，5000，10000}。在RCV1数据集上运行的结果如图2所示，可以看出，在算法效率方面，本算法优于其它所有算法，在算法准确度方面，本算法结果与GraHTP以及GraSP算法相当，综上所述，本算法在逻辑回归分类任务中的性能优于其它算法。在20Newsgroup数据集上，本实验记录分类结果以及得出该结果所用的时间，(括号内是时间标准差)。实验结果如表1所示，其中加粗的部分是最好的实验结果。可以看出，GraSP可以得出最好的分类结果，但是耗时很长。而SLH算法可以在很短的时间内便能取得仅略逊于GraSP算法的结果，所以综合而言本算法性能仍优于其它对比算法。

图2 逻辑回归模型实验结果图

表1 逻辑回归在20Newsgroup数据集回归结果

5 结论

本文提出了一种用于解决l0稀疏约束问题的优化算法(SLH)，算法的主要思想是在随机LBFGS算法中引入迭代硬阈值(IHT)操作，从而将二阶拟牛顿算法运用到稀疏学习领域中，在具有二阶优化算法优势的同时避免了直接求取Hessian矩阵，有效的提升了模型效率。在本文中算法被运用到线性回归任务以及逻辑回归任务，实验结果表明SLH算法可以在保证模型高性能的前提下更快收敛，较传统一阶算法拥有更高的效率，可以投入更广泛的应用。