坐标下降法(coordinate descent method)求解LASSO的推导


坐标下降法(coordinate descent method)求解LASSO推导

LASSO在尖点是singular的,因此传统的梯度下降法、牛顿法等无法使用。常用的求解算法有最小角回归法、coordinate descent method等。
由于coordinate descent method是相对较简单的做法,放在第一个介绍。

坐标下降法思想

坐标下降法基于的思想很简单,就是当面对最小化一个多元函数的问题时,我们每一次迭代的时候只改变一个目标变量的值。也就是固定其他变量不动,只在该变量的维度上寻找一个使函数最小的值。这种思想类似于贪心算法。

推导过程

定义Loss function为:
\[ \frac{1}{N}\sum_{i=1}^{N}(y_i-x_i^T\cdot \beta) \]
其中,\(x_i\)是p·1维的向量,\(\beta\)是p·1维的向量。

Penalty为Lasso penalty:
\[ \sum_{j=1}^p|\beta_j| \]
定义超参数为\(\lambda\)

目标函数为:
\[ L=\frac{1}{N}\sum_{i=1}^{N}(y_i-x_i^T\cdot \beta+\lambda\sum_{j=1}^p|\beta_j|) \]
应用坐标下降法的思想,我们固定住\(x_k\ne x_j\)的变量,然后在每一轮迭代中只优化\(x_j\)

可以采用的迭代顺序是从j=1依次到p进行迭代,然后再从j=1开始。

当固定住其他变量时,求object function的极小值就等价于求解一元LASSO的问题。
\[L=\frac{1}{N}\sum_{i=1}^{N}(r_i-\beta_jx_{ji})^2+\lambda \beta_j \tag{1}\]

其中,\(r_i=y_i-\sum_{k\ne j}x_{ik}\beta_k\),也就是只用其他变量拟合y的残差。

将式1稍微化简一下,可以得到:
\[ L=\beta_j^2\frac{\sum_{i=1}^{N}x_{ji}^2}{N}-2\beta_j\frac{\sum_{i=1}^{N}r_ix_{ji}}{N}+\frac{\sum_{i=1}^{N}r_i^2}{N}+\lambda{|\beta_j|} \]
这是一个二次函数。由于涉及到绝对值,我们需要分两个区间讨论:\(\beta_j<0\)\(\beta_j>0\)

相当于我们将\(\beta_j\)的取值划成了两个空间,分别讨论极值。最后的极值是把这两个空间的极值再取最小值。

  • 第一个区间, \(\beta_j>0\)
    可以观察到object function是一个开口向上二次函数,全局最小点在\(\beta_j=\frac{2\frac{\sum r_ix_i}{N}-\lambda}{2\sum x_i^2}{N}\)处取得。
    但是我们这时的定义域限制在 \(\beta_j>0\),因此需要分类讨论是否能取全局最小点:
    \[ if (2\frac{\sum r_ix_i}{N}-\lambda>0):\\ {\beta_j^{*}=\frac{2\frac{\sum r_ix_i}{N}-\lambda}{2\sum x_i^2}{N}}\\ Else:\\ {\beta_j^{*}=0} \]

  • 第二个区间,\(\beta_j<0\)
    全局最小点在\(\beta_j=\frac{2\frac{\sum r_ix_i}{N}+\lambda}{2\sum x_i^2}{N}\)处取得。

但是我们这时的定义域限制在 \(\beta_j<0\),因此需要分类讨论是否能取全局最小点:
\[ if (2\frac{\sum r_ix_i}{N}+\lambda<0):\\ {\beta_j^{*}=\frac{2\frac{\sum r_ix_i}{N}+\lambda}{2\sum x_i^2}{N}}\\ Else:\\ {\beta_j^{*}=0} \]

综合上面的讨论,

  • case1:\(2\frac{\sum r_ix_i}{N}<-\lambda\)
    \(\beta_j^{*}=\frac{2\frac{\sum r_ix_i}{N}+\lambda}{2\sum x_i^2}{N}\)

  • case2:\(-\lambda<2\frac{\sum r_ix_i}{N}<\lambda\)
    \(\beta_j^{*}=0\)

  • case3:\(\lambda<2\frac{\sum r_ix_i}{N}\)
    \(\beta_j^{*}=\frac{2\frac{\sum r_ix_i}{N}-\lambda}{2\sum x_i^2}{N}\)

定义一个软阈值函数来统一三个case

\[ \beta_j^{*}=\frac{\text{soft threshold}({2\frac{\sum r_ix_i}{N},\lambda)}}{2\frac{\sum x_i^2}{N}} \]

comment

对于用L2 loss function作为损失函数的回归问题,由于object function是关于\(\beta\)的凸函数,因此我们一定可以找到一个全局最优点。迭代过程是收敛的。


作者:跑得飞快的凤凰花,发布于:2019/05/16
原文:https://www.cnblogs.com/zzqingwenn/p/10874522.html