机器算法验证 - 如何将迭代重加权最小二乘 (IRLS) 方法应用于 LASSO 模型？ - 吾爱随笔录

如何将迭代重加权最小二乘 (IRLS) 方法应用于 LASSO 模型？

机器算法验证物流广义线性模型特征选择套索凸的

2022-03-20 00:33:50

我已经使用IRLS 算法编写了逻辑回归。我想应用LASSO 惩罚以自动选择正确的功能。在每次迭代中，解决以下问题：

(X^{T} W X) δ \hat{β} = X^{T} (y - p)

$\mathbf{\left(X^TWX\right) \delta\hat\beta=X^T\left(y-p\right)}$

让 $\lambda$ 是一个非负实数。我没有像The Elements of 中建议的那样惩罚拦截。统计学习。同样适用于已经为零的系数。否则，我从右侧减去一个术语：

X^{T} (y - p) - λ \times s i g n (\hat{β})

$\mathbf{X^T\left(y-p\right)-\lambda\times \mathrm{sign}\left(\hat\beta\right)}$

但是，我不确定 IRLS 算法的修改。这是正确的做法吗？

编辑：虽然我对此没有信心，但这是我最终想出的解决方案之一。有趣的是这个解决方案对应于我现在对 LASSO 的理解。每次迭代确实有两个步骤，而不仅仅是一个：

第一步与之前相同：我们对算法进行迭代（好像 $\lambda=0$ 在上面的梯度公式中），
第二步是新的：我们对每个组件应用一个软阈值（除了组件 $\beta_0$ ，对应于向量的截距） $\beta$ 第一步获得。这称为迭代软阈值算法。

\forall i \geq 1, β_{i} \leftarrow s i g n (β_{i}) \times max (0, | β_{i} | - λ)

$\forall i \geq 1, \beta_{i}\leftarrow\mathrm{sign}\left(\beta_{i}\right)\times\max\left(0,\,\left|\beta_{i}\right|-\lambda\right)$

4个回答

这个问题通常通过坐标下降拟合来解决（见这里）。这种方法在数值上更安全更有效，在算法上更容易实现并且适用于更通用的模型阵列（也包括 Cox 回归）。R包glmnet中提供了 R 实现。这些代码是开源的（部分在 C 中，部分在 R 中），因此您可以将它们用作蓝图。

LASSO 损失函数在每个轴上的不连续性为零，因此 IRLS 会遇到问题。我发现顺序最小优化 (SMO) 类型的方法非常有效，参见例如

http://bioinformatics.oxfordjournals.org/content/19/17/2246

带有 MATLAB 软件的版本是

http://bioinformatics.oxfordjournals.org/content/22/19/2348

该软件可在此处获得：

http://theoval.cmp.uea.ac.uk/~gcc/cbl/blogreg/

基本思想是一次优化一个系数，并测试一次是否跨越一个系数的不连续性，这很容易，因为您正在执行标量优化。这听起来可能很慢，但实际上非常有效（尽管我希望从那以后开发出更好的算法——可能是由 Keerthi 或 Chih-Jen Lin 开发的，他们都是这类事情的领先专家）。

您可以查看论文：Efficient L1-regularizedlogistic regression，这是一种基于 IRLS 的 LASSO 算法。关于实施，该链接可能对您有用（http://ai.stanford.edu/~silee/softwares/irlslars.htm）。

LASSO 问题的 IRLS 如下：

\arg min_{x} \frac{1}{2} {‖ A x - b ‖}_{2}^{2} + λ {‖ x ‖}_{1} = \arg min_{x} \frac{1}{2} {‖ A x - b ‖}_{2}^{2} + λ x^{T} W x

$\arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} = \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda {x}^{T} W {x}$

在哪里 $W$ 是对角矩阵 - ${W}_{i, i} = \frac{1}{ \left| {x}_{i} \right| }$ .
这来自 $\left\| x \right\|_{1} = \sum_{i} \left| {x}_{i} \right| = \sum_{i} \frac{ {x}_{i}^{2} } { \left| {x}_{i} \right| }$ .

现在，以上只是Tikhonov 正则化。
然而，由于 $W$ 取决于 $x$ 必须迭代地解决它（这也取消了 Tikhonov 正则化中的 2 因子，作为 ${x}^{T} W x$ 关于 $x$ 在持有的同时 $x$ 常数是 $\operatorname{diag} \left( \operatorname{sign} \left( x \right) \right)$ 这等于 $W x$ ):

x^{k + 1} = {(A^{T} A + λ W^{k})}^{- 1} A^{T} b

${x}^{k + 1} = \left( {A}^{T} A + \lambda {W}^{k} \right)^{-1} {A}^{T} b$

在哪里 ${W}_{i, i}^{K} = \frac{1}{ \left| {x}^{k}_{i} \right| }$ .

初始化可以通过 $W = I$ .

请注意，这不适用于较大的值 $\lambda$ 你最好使用 ADMM 或坐标下降。

其它你可能感兴趣的问题

上一篇如何从数据样本中估计 Zipf 截断分布的参数？下一篇快速评估（视觉）R 中有序分类数据之间的相关性？