目标函数

Lasso相当于带有L1正则化项的线性回归。先看下目标函数： $RSS\left(w\right)+\lambda \parallel w{\parallel }_1={\sum }_{i=0}^N(y_i-{\sum }_{j=0}^D{w}_j{h}_j\left(x_i\right){)}^2+\lambda {\sum }_{j=0}^D\mid w_j\mid$RSS(w)+λ∥w∥1​=∑i=0N​(yi​−∑j=0D​wj​hj​(xi​))2+λ∑j=0D​∣wj​∣
这个问题由于正则化项在零点处不可求导，所以使用非梯度下降法进行求解，如坐标下降法或最小角回归法。

坐标下降法

本文介绍坐标下降法。
坐标下降算法每次选择一个维度进行参数更新，维度的选择可以是随机的或者是按顺序。
当一轮更新结束后，更新步长的最大值少于预设阈值时，终止迭代。

下面分为两部求解

RSS偏导

下面做一下标记化简
${\rho }_j={\sum }_{i=1}^N{h}_j\left(x_i\right)(y_i-{\sum }_{k\ne j}{w}_k{h}_k(x_i\left)\right)$ρj​=∑i=1N​hj​(xi​)(yi​−∑k̸​=j​wk​hk​(xi​))
$z_j={\sum }_{i=1}^N{h}_j(x_i{)}^2$zj​=∑i=1N​hj​(xi​)2
上式化简为 $\frac{\partial }{\partial w_j}RSS\left(w\right)=-2{\rho }_j+2w_j{z}_j$∂wj​∂​RSS(w)=−2ρj​+2wj​zj​

正则项偏导

次梯度方法(subgradient method)是传统的梯度下降方法的拓展，用来处理不可导的凸函数。

$\lambda {\partial }_{w_j}\mid w_j\mid =\{\begin{array}{cc}-\lambda & w_j\&lt;0\\ [-\lambda ,\lambda ]& w_j=0\\ \lambda & w_j\&gt;0\end{array}$λ∂wj​​∣wj​∣=⎩⎪⎨⎪⎧​−λ[−λ,λ]λ​wj​<0wj​=0wj​>0​

整体偏导数

$\lambda {\partial }_{w_j}\text{[lasso cost]}=2z_j{w}_j-2{\rho }_j+\{\begin{array}{cc}-\lambda & w_j\&lt;0\\ [-\lambda ,\lambda ]& w_j=0\\ \lambda & w_j\&gt;0\end{array}=\{\begin{array}{cc}2z_j{w}_j-2{\rho }_j-\lambda & w_j\&lt;0\\ [-2{\rho }_j-\lambda ,-2{\rho }_j+\lambda ]& w_j=0\\ 2z_j{w}_j-2{\rho }_j+\lambda & w_j\&gt;0\end{array}$λ∂wj​​[lasso cost]=2zj​wj​−2ρj​+⎩⎪⎨⎪⎧​−λ[−λ,λ]λ​wj​<0wj​=0wj​>0​=⎩⎪⎨⎪⎧​2zj​wj​−2ρj​−λ[−2ρj​−λ,−2ρj​+λ]2zj​wj​−2ρj​+λ​wj​<0wj​=0wj​>0​
要想获得最有解，令

$\lambda {\partial }_{w_j}\text{[lasso cost]}=0$λ∂wj​​[lasso cost]=0。
解得，
${\widehat{w}}_j=\{\begin{array}{cc}({\rho }_j+\lambda /2)/z_j& {\rho }_j\&lt;-\lambda /2\\ 0& {\rho }_j\text{ in }[-\lambda /2,\lambda /2]\\ ({\rho }_j-\lambda /2)/z_j& {\rho }_j\&gt;\lambda /2\end{array}$w^j​=⎩⎪⎨⎪⎧​(ρj​+λ/2)/zj​0(ρj​−λ/2)/zj​​ρj​<−λ/2ρj​ in [−λ/2,λ/2]ρj​>λ/2​

伪代码

预计算 $z_j={\sum }_{i=1}^N{h}_j(x_i{)}^2$zj​=∑i=1N​hj​(xi​)2
初始化参数w（全0或随机）
循环直到收敛:

for j = 0,1,…D
$ \space \space\space\space\rho_j=\sum_{i=1}^Nh_j(x_i)(y_i-\sum_{k \neq j }w_kh_k(x_i))$
$update{w}_j$    update wj​
选择变化幅度最大的维度进行更新

概率解释

拉普拉斯分布

随机变量 $X\sim Laplace(\mu ,b)$X∼Laplace(μ,b)，其中 $\mu$μ是位置参数， $b\&gt;0$b>0是尺度参数。
概率密度函数为
$f(x\mid \mu ,b)=\frac{1}{2b}exp(-\frac{\mid x-\mu \mid }{b})$f(x∣μ,b)=2b1​exp(−b∣x−μ∣​)

MAP推导

假设 ${ϵ}_i\sim N(0,{\sigma }^2)$ϵi​∼N(0,σ2)， $w_i\sim Laplace(0,\frac{1}{\lambda })$wi​∼Laplace(0,λ1​)

等价于