safe

本文介绍了一种在 l1 惩罚最小二乘法回归（或 LASSO）问题中消除特征（变量）的快速方法。消除特征可大幅缩短运行时间，尤其是在惩罚参数值较大的情况下。这个方法不是启发式的：它只消除在求解 LASSO 问题后保证不存在的特征。特征消除步骤易于并行化，可以独立测试每个特征的消除情况。此外，与求解 LASSO 问题相比，这一方法的计算量可以忽略不计–大致相当于单梯度步骤。这个方法扩展了现有 LASSO 算法的范围，使其可以处理以前无法处理的更大数据集。本文展示了如何将此方法扩展到一般的 l1 惩罚凸问题，并介绍了稀疏支持向量机和逻辑回归问题的初步结果。

insight

作者几乎是单纯的从数学角度提出了这一巧妙的方法，着实令人佩服，后面无论多少文章在本质上都是对此方法的改进。

核心理论

先定义一下本文用到的符号：

训练的 data：X = (a₁, …, a_m)^T ∈ ℝ^m × n，每一行为一个样本，因此每一列即为一个特征。

lasso 原问题：

$$ \mathcal{P}(\lambda) : \phi(\lambda):=\min_w {\frac{1}{2}} \|Xw-y\|_2^2+\lambda\|w\|_1 $$

lasso 对偶问题：

𝒟(λ) : ϕ(λ) := max_θG(θ) : |θ^Tx_k| ≤ λ, k = 1, …, n

其中

$$ G(\theta)={\frac{1}{2}} \|y \|_{2}^{2}-{\frac{1}{2}}\|\theta\|+\|y \|_{2}^{2} $$

θ 是求解对偶问题中引入的量，表示残差：Xw − y。

这全部的奥妙就在这约束条件 |θ^Tx_k| ≤ λ 上了，不难的凸优化分析即可告诉我们：

|θ^⋆Tx_k| < λ ⇒ (w^⋆)_k = 0

也就是说对于满足这样的判断的 w 分量，我们可以断言其为 0，从而断言此分量对应的那一列特征是无用的，可以剔除掉。

然而我们只有求解完 lasso 才能做出上面的断言呀，如何在求解开始之前预先识别并剔除无用特征呢？作者为此提出了一种通用策略：

开始将策略之前先做一些必要的铺垫，我们不难发现 λ 越大，得到的解的稀疏程度越大，取恰好使得 w = 0 的 λ₀，根据我们的筛选规则，不难看出：

λ₀ = max_{1 ≤ j ≤ n}|y^Tx_j| = ∥X^Ty∥_∞

对应的

θ₀^⋆ = −y

第一步

尽管在开始训练前，我们无法精确找到最优解 θ^*，但是可以尝试构建一个必定包含 θ^* 的集合 Θ，如果我们可以验证 ∀θ ∈ Θ，均有 |θ^Tx_k| < λ，那么也可以断言第 k 个特征无效。

因此构建一个尽量小的 Θ 即可。作者采用的策略是构建两个必定包含 θ^* 的集合 Θ₁, Θ₂，取二者交集作为 Θ，定义：

注意到对偶问题 G(θ)，任取一个可行点（比如上面提到的 λ₀ 系列）得到 γ := G(θ_s)，可以构建出一个球形约束区域：

Θ₁ := {θ ∣ G(θ) ≥ γ}

（对于 γ 的得到作者采用了对偶缩放的技巧，这不是重点，暂且按下不谈）

作者用一阶条件构建了第二个区域：

Θ₂ := {θ ∣ g^T(θ − θ₀^⋆) ≤ 0}

第二步

可以舍弃的特征的指标集合可以表示为：

ℰ = {k ∣ λ > max (P(γ, x_k), P(γ, −x_k))}

其中

P(γ, x_k) := max_θx_k^Tθ  subject to  G(θ) ≥ γ,  g^T(θ − θ₀^⋆) ≥ 0

可以用凸优化方法求出这个问题的封闭解。

如果我们有某个 λ 下对应的最优解 w，两个区域是不难构建的；即使我们没有某个 λ 下对应的最优解 w，我们也可以选择恰好使得 w = 0 的 λ₀，在这种情况下，解集还可以有一个优雅地表达：

λ > ρ_kλ_max

其中

$$ \rho_k = {\frac{ \| y \|_2 \| x_k \|_2 + | y^T x_k | }{ \| y \|_2 \| x_k \|_2 + \lambda_{\max} }} $$

算法

以上分析可以产生两种算法，解决两类问题。

拓展

作者对更一般的带 l1 正则化的凸优化问题给出了解析，包括 logistics 回归，稀疏支持向量机等等。

实验

对于有内存限制下的求解问题，SAFE 表现出色，圆满完成了限制内存的任务。

在不同 lasso solver 的实验中，safe 方法均表现出了较好的提前筛选效果。

改进：strong rules

strong rules 提出的强规则并非万无一失，但在实践中很少失效。这些规则非常简单，并可辅以对 Karush-Kuhn-Tucker (KKT) 条件的简单检查，以确保提供凸问题的精确解。这些规则为各种统计优化问题节省了大量计算时间和内存。

本文符号定义：

$$ \hat{\boldsymbol{\beta}}=\underset{\boldsymbol{\beta}}{\operatorname*{argmin}} {\frac{1}{2}} \|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|_2^2+\lambda\|\boldsymbol{\beta}\|_1 $$

上一篇文章的筛选规则可以写为：

$$ |\mathbf{x}_j^T\mathbf{y}| < \lambda - \|\mathbf{x}_j\|_2 \|\mathbf{y}\|_2 {\frac{ \lambda_{\max} - \lambda }{ \lambda_{\max} }} $$

如果我们对 X 进行了归一化，上面的式子可以进一步写为：

$$ \lambda-\|\mathbf{y}\|_{2} {\frac{\lambda_{\max}-\lambda}{\lambda_{\max}}} $$

作者采取了大胆的缩放，定义：

$$ \mathbf{r}=\mathbf{y}-\mathbf{X}\hat{\boldsymbol{\beta}}(\lambda_0) $$

则有：

|x_j^Tr| < 2λ − λ₀

作者进行了一系列分析来阐述他的动机和上述式子几乎不会失误，尽管效果惊人的显著，不过他毕竟还是不安全的。后续工作也几乎不再与此工作进行比较，因此不再赘述。

SLORES：适用于 logistic 回归的强且安全的筛选法则

要注意 SLORES 是针对于逻辑回归提出的，也正因如此才能利用上强凸性。

原问题：

$$ \min_{\beta,c} {\frac{1}{m}}\sum_{i=1}^m\log(1+\exp(-\langle\beta,\bar{\mathbf{x}}_i\rangle-b_ic))+\lambda\|\beta\|_1 $$

对偶问题，定义 f(y) = ylog (y) + (1 − y)log (1 − y) for y ∈ (0, 1)：

$$ \min_\theta {g(\theta)={\frac{1}{m}}\sum_{i=1}^m f(\theta_i): \|\bar{\mathbf{X}}^T\theta\|_\infty\leq m\lambda, \langle\theta,\mathbf{b}\rangle=0, \theta\in\mathcal{C}} $$

针对于逻辑回归的筛选规则可以表达为：

$$ T(\theta_\lambda^*,\bar{\mathbf{x}}^j):=\max_{\theta\in\mathcal{A}_\lambda}|\langle\theta,\bar{\mathbf{x}}^j\rangle|<m\lambda\Rightarrow[\beta_\lambda^*]_j=0 $$

下面就是构建区域了，作者利用强凸性构建了一个理论上和实践上都很紧的球形区域：

$$ \|\theta_\lambda^*-\theta_{\lambda_0}^*\|_2^2\leq{\frac{m}{2}}\left[g\left({\frac{\lambda}{\lambda_0}}\theta_{\lambda_0}^*\right)-g(\theta_{\lambda_0}^*)+\left(1-{\frac{\lambda}{\lambda_0}}\right)\langle\nabla g(\theta_{\lambda_0}^*),\theta_{\lambda_0}^*\rangle\right] $$

并结合其他的一些必要条件做出了部分约束，求出了筛选规则的闭式解，效果显著。

$$ a{\frac{a}{b}}b $$