目标函数
Lasso相当于带有L1正则化项的线性回归。先看下目标函数：RSS(w)+λ∥w∥1=∑Ni=0(yi−∑Dj=0wjhj(xi))2+λ∑Dj=0|wj|
这个问题由于正则化项在零点处不可求导，所以使用非梯度下降法进行求解，如坐标下降法或最小角回归法。
坐标下降法
本文介绍坐标下降法。
坐标下降算法每次选择一个维度进行参数更新，维度的选择可以是随机的或者是按顺序。
当一轮更新结束后，更新步长的最大值少于预设阈值时，终止迭代。
下面分为两部求解
RSS偏导
∂∂wjRSS(w)=−2∑i=1Nhj(xi)(yi∑j=0Dwjhj(xi))=−2∑i=1Nhj(xi)(yi−∑k≠jwkhk(xi)−wjhj(xi))=−2∑i=1Nhj(xi)(yi−∑k≠jwkhk(xi))+2wj∑i=1Nhj(xi)2
下面做一下标记化简
ρj=∑Ni=1hj(xi)(yi−∑k≠jwkhk(xi)) zj=∑Ni=1hj(xi)2
上式化简为
∂∂wjRSS(w)=−2ρj+2wjzj
正则项偏导
次梯度方法(subgradient method)是传统的梯度下降方法的拓展，用来处理不可导的凸函数。
λ∂wj|wj|=⎧⎩⎨⎪⎪−λ[−λ,λ]λwj<0wj=0wj>0
整体偏导数
λ∂wj[lasso cost]=2zjwj−2ρj+⎧⎩⎨⎪⎪−λ[−λ,λ]λwj<0wj=0wj>0=⎧⎩⎨⎪⎪2zjwj−2ρj−λ[−2ρj−λ,−2ρj+λ]2zjwj−2ρj+λwj<0wj=0wj>0
要想获得最有解，令
λ∂wj[lasso cost]=0。
解得，
w^j=⎧⎩⎨⎪⎪(ρj+λ/2)/zj0(ρj−λ/2)/zjρj<−λ/2ρj in [−λ/2,λ/2]ρj>λ/2
伪代码
预计算zj=∑Ni=1hj(xi)2
初始化参数w（全0或随机）
循环直到收敛:
for j = 0,1,…D
ρj=∑Ni=1hj(xi)(yi−∑k≠jwkhk(xi))
update wj
选择变化幅度最大的维度进行更新
概率解释
拉普拉斯分布
随机变量X∼Laplace(μ,b)，其中μ是位置参数，b>0是尺度参数。
概率密度函数为
f(x|μ,b)=12bexp(−|x−μ|b)
MAP推导
假设ϵi∼N(0,σ2)，wi∼Laplace(0,1λ)
argmaxwL(w)=likelihood×prior=P(x,y|w)×P(w)=ln∏i=1n1σ2π−−√exp(−12(yi−xiwTσ)2)⋅∏j=1dλ2exp(−λ|wj|)=ln∏n+ln∏d=∑nln+∑dln=∑nlnexp(−12(yi−xiwTσ)2)−∑nlnσ2π−−√+∑dlnexp(−λ|wj|)−∑dln2λ=∑n−12(yi−xiwTσ)2−∑nlnσ2π−−√+∑d(−λ|wj|)−∑dln2λ=−12σ2∑n(yi−xiwT)2−λ∑d|wj|−∑nlnσ2π−−√−∑dln2λ=−12σ2∑n(yi−xiwT)2−λ∑d|wj|+constant
等价于
argminwf(w)=∑i=1n(yi−xiwT)2+λ∑j=1d|wj|=||y−XwT||22+λ||w||1
