1.4 Lasso方法

本节介绍Lasso方法的基本思想，以及求解用的坐标下降法的基本理论，并介绍Lasso方法的发展，如组Lasso和图Lasso等方法.更多详细内容可参考文献[86].

1.4.1 回归模型的 Lasso 方法

1.Lasso方法的定义

Lasso（Least absolute selectionand shrinkage operator）方法 ^[46] 是指将最小二乘法的损失函数与 ℓ ₁ 范数相结合，即对回归系数的绝对值之和施加约束.与最小二乘法相比， ℓ ₁ 范数所添加的约束可以收缩系数，甚至可以迅速使系数为零，在参数估计的同时实现了模型选择.因此 Lasso 方法为线性回归提供了一种自动选择模型的方法.与其他的模型选择方法不同的是，该方法得到的优化问题是凸的，从而能够有效地解决大规模数据处理的问题.

设有 n 对观测数据（ x _i ， y _i ），其中 x _i =（ x _{i 1} ， x _{i 2} ， … ， x _ip ）（ i =1，2， … ， n ）是由 p 个解释变量组成的向量， y _i 是相应的响应变量，一般的线性模型形式为

令 β =（ β ₁ ， β ₂ ， … ， β _p ） ^T 为 p 维的系数向量， β ₀ 为截距项.一般地，对（ β ₀ ， β ）的估计是通过最小二乘法，即最小化平方误差的损失函数而得到的，因此有

而 Lasso 回归等价于在最小二乘法估计的基础上对估计值的大小增加一个 ℓ ₁ 范数的约束（或称惩罚），因此有

式（1-41）中，约束 可以简化为 ℓ ₁ 范数约束|| β || ₁ ≤ t ，其中，||·|| ₁ 表示 ℓ ₁ 范数.

2.Lasso方法的求解

Lasso方法的求解是一个最优化问题，属于带有凸约束的二次规划问题.为方便起见，将式（1-41）改写成拉格朗日形式的目标函数

假定对 y _i 和解释变量观测值 x _ij 进行了归一化处理，即 ， ，此时，截距项 β ₀ 可以省略.

（1）单变量情形的软阈值法

首先，考虑单变量的情形，训练样本为 （为方便起见，可将 z _j 看成 x _ij ），回归系数为 β （这里为常量），|| β || ₁ 即 β ，有

对于单个变量的最小化问题，通过软阈值法，直接求解式（1-29）可以得到

式中，软阈值算子为 ，以参数 λ 使 x 向0平移.

（2）多变量情形的循环坐标下降法

坐标下降（Coordinate Descent）法是一种简单且高效的非梯度优化方法，其核心思想是依次沿着坐标轴的方向最小化目标函数的值，将一个复杂的优化问题分解为一系列简单的优化问题进而去求解.

其求解过程的实质是，每次只优化一维变量，将其余变量视为常量，每次优化完成后，同时在变量循环中更新相关方程；而在一般情况下，最小化的变量在众多参数中不随循环而改变，因此整个迭代过程将很快完成.该方法是一种迭代算法，其原理是在每次迭代中沿着当前点处的一个坐标轴方向进行搜索，如此通过循环使用不同的坐标方向来达到目标函数的局部极小值.

从单变量的情形可以看出：对一般形式的Lasso问题，能够用一种简单的逐坐标方法求解，也就是按某种固定顺序（如 j =1，2， … ， p ）依次求解.第 j 步，令 k =\ j 时的系数 不变，最小化 k = j 时的目标函数，以更新系数 .

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

可以看到，每个 β _j 的解均可以用偏残差表示，定义为

在此，仅保留当前拟合结果的第 j 个变量，借助偏残差，第 j 个系数可以更新为

其等价形式为

式中， 为整体残差.整个算法会通过更新软阈值算子的方式循环更新 的坐标以及由此得到的残差向量.本节的坐标下降法采用了循环坐标下降法，即每次沿一个坐标轴的方向最小化凸目标函数的值，可以快速求解Lasso问题.

1.4.2 组 Lasso 方法

在一些回归问题中，具有某一相同特征的解释变量存在天然的分组结构，因此在建立回归模型时就需要使同一组内的回归变量的回归系数同时为 0 或同时不为 0.例如，对于解释变量中包含多个因子水平值的定性变量，常用的方法是引入一组虚拟变量来表示多个因子水平值，这些虚拟解释变量共同反映了定性变量的影响，在建模时应该将其视为一组具有组效应的变量，一起引入模型中或从模型中剔除.Lasso方法不能对数据类型存在组效应的解释变量进行整个组的变量选择，不能反映出组结构信息，在参数估计和变量选择时没有充分利用数据的分组信息以提高计算速度.Yuan等 ^[47] 提出组Lasso（group Lasso）方法，对同一组解释变量的回归系数施加相同的惩罚项，克服了Lasso方法不能对具有组结构的解释变量进行组间变量选择的缺点.

组Lasso方法是指先对估计的回归系数进行分组，将每个组中待估计的回归系数的解释变量整体视为“单个”变量进行变量选择，也就是说，如果该组的系数估计值都不是0，则该组所对应的具有组结构的解释变量将被全部选择；反过来说，如果该组的系数估计值均为 0，那么该组所对应的具有组结构的解释变量将被全部剔除掉.这在很大程度上增加了组间的稀疏性.

1.组Lasso方法的定义

考虑一个包含 J 组解释变量的线性回归模型， j =1，2， … ， J ，向量 表示第 j 组解释变量.目标是基于解释变量集合（ Z ₁ ， Z ₂ ， … ， Z _J ）预测响应变量 Y ∈ R .回归模型为 ，其中， 表示一组 p _j 个回归系数.

给定一组样本量为 n 的观测数据集合 ，组Lasso方法可以求解下面的凸优化问题

式中， 是向量 θ _j 的欧几里得范数.

式（1-48）是Lasso方法的组推广形式，具有如下性质：

（1）对于 λ ≥0，向量 或者整体为0，或者全都不为0；

（2）当 p _j =1时，有 ，因此如果所有组中都只包含一个变量，优化问题（1-48）就会变为普通的Lasso问题.

2.组Lasso方法的求解

首先，利用矩阵—向量方式来重写优化问题（1-48），可得

这里为了简单起见，忽略了截距项 θ ₀ ，因为可以对所有的响应变量及解释变量进行归一化处理，从而去掉 θ ₀ .对于这个问题，令次梯度为0就会得到如下方程：

式中， 是在 处范数 的次微分.如果 ，则必然有 ；如果 ，则 为满足条件 的任意向量.

3.零次梯度法

零次梯度法首先固定所有的块向量 ，然后求解 .这样做相当于对组Lasso目标函数采用了块坐标下降法.因为问题是凸的，且惩罚项是块可分的，所以保证了其可以收敛到一个最优解.固定所有的 ，则有

式中， 是第 j 个偏残差.由与次梯度相关的条件可知：如果 ，则 ，否则最小值 必须满足下式：

迭代公式（1-51）除惩罚参数 λ 与 有关外，对 没有闭合解，除非 Z _j 标准正交.在这种特殊情况下，该迭代公式可以简化为

在函数（·） ₊ =max{0， t }中，若变量为正数，则返回该变量，否则返回0.

4.复合梯度法

复合梯度法也被称为近点梯度法，其通过在每个块中进行计算从而实现迭代.每迭代一次，块优化问题就有一个更简单的近似问题，这样就会得到式（1-53）的迭代公式.迭代公式的具体形式为

式中， v 是步长参数.

1.4.3 图 Lasso 方法

在随机变量集合（ X ₁ ， X ₂ ， … ， X _p ）的图模型 G =（ V ， E ）的结构学习中，常用的方法是对其协方差矩阵的逆矩阵进行估计，即通过逆协方差矩阵中非0元素与边集的对应关系得到图模型.但是随着变量维数的增加，传统的矩阵估计方法（如最大似然估计方法）在样本量小于待估计参数个数时不可用.而 Lasso 方法的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下，使残差平方和最小化，从而产生某些严格等于0的回归系数，得到可以解释的模型.通过稀疏性约束，可以处理样本少而待估计参数过多的问题.Yuan ^[87] 提出了一种惩罚似然估计方法，称之为图Lasso 方法，用 ℓ ₁ 惩罚约束精度矩阵的稀疏性，解决最大似然估计方法中的最大化问题.

假设来自 p 维高斯分布 N （ μ ， Σ _p ）的 n 个相互独立样本 x ₁ ， x ₂ ， … ， x _n ，其样本协方差矩阵记为 S ，则有

图Lasso问题是使带惩罚的对数似然函数最大化的问题，即

式中， ‖ Θ ‖ ₁ 为 ℓ ₁ 范数（即 Θ 的元素绝对值之和），tr表示矩阵的迹，det表示矩阵的行列式， λ 表示惩罚参数，且有 λ ≥0.

设 W 为协方差阵 Σ _p 的估计，通过坐标下降法由 W 中对应的行和列来解决式（1-56）的最大化问题，将 W 和 S 分块得到

式中， s ₁₂ 应满足下式

利用凸问题的对偶性，式（1-58）等号右边等价于

式（1-59）相当于Lasso最小二乘问题.次梯度等式可写为

其可以由坐标下降法求解. uPH2qTvFaQkW8xwz+iGElIgiyjr3wX6cZjNJZAK+CsJp9Myf0UD1XFmOXJDQ2klP