LASSO(least absolute shrinkage and selection operator) 回归中 如何用梯度下降法求解?

即求解在|βi|<t的约束下 0<t< t(max)使损失函数最小的β ,t的最大值为对所有变量进行回归(original least square)的参数的绝对值之和
关注者
230
被浏览
10084
首先你要知道l-1 norm的导数是连续不光滑的,所以没有办法直接求导利用梯度下降来求解。 可以考虑最简单的情况,即x只有一维
f(x) = (x-a)^2 + c |x|
我们首先需要定义|x|在0点的梯度,我们叫做subgradient。

像上面图里画的,直观理解,函数在某一点的导数可以看成函数在这一点上的切线,那么在原点,因为这一点不是光滑的(左右导数不一样),所以可以找到实线下方的无数条切线,形成一个曲线族。我们就把这些切现斜率的范围定义为这一点的subgradient.
也就是 |x|在0点的导数是在-1到1范围内的任意值。具体的数据推到在这里就不写了。
那么我们可以写出f(x)的导数
2(x-a) + cx when x>0
f'(x) = 2a + d when x=0 and -c < d < c
2(x-a) - cx when x<0

我们可以发现,当 -c < 2a < c,x=0时, f‘(x)恒等于0,也就是f(x)到达极值点。这也就解释了为什么在l_1 penalty下得到的解会稀疏,因为当c在一定范围内时,只要x为0,f’(x)就为0。当然,上面的式子也可以用梯度下降方法去优化。

但是,当x扩展为多维向量的时候,问题就变得更复杂了,因为导数方向的变化范围更大。下面有几种常见的思路解这个问题,只说一下基本的思想,具体的算法可以看相关paper。
1. 贪心算法,每次先找跟目标最相关的feature,然后固定其他的系数,优化这一个feature的系数,具体的求导也要用到上面的subgradient。代表算法有LARS,feature-sign search等。
2. 逐一优化。就每次固定其他的dimension,选择一个dimension进行优化。因为只有一个方向有变化,所以都可以转化为上面简单的subgradient问题。最后反复迭代所有的dimension,达到收敛。代表算法有 coordinate descent,block coordinate descent等。
3. 还有一类算法,就是proximal及其扩展方法。这类算法可以解决一系列的sparse norm优化问题,基本思想就是不断的迭代需要优化的稀疏。每一次迭代上上一次优化结果的邻域找一个新的点,而且新的点需要在优化目标的限定区域内。这个限定区域可以通过找到原始优化问题的对偶问题得到。