LASSO的解法

LASSO非常实用，但由于它的惩罚项不可以常规地进行求导，使得很多人以为它无法显式地求出解析解。但其实并不是这样的。

1 单变量情形：软阈值法

1.1 软阈值的分类讨论

将(N)个样本的真实值记为(N)维向量(y)，将(N)个样本的自变量记为(z)，假设我们已经将自变量做过标准化，即(z' ell_n=0)，(z'z/N=1)，这也意味着在LASSO模型中截距项为(0)。系数(eta)是要优化的参数，惩罚项参数为(lambdagt 0)。

LASSO就是要求解

[argmin_eta dfrac{1}{2N}(y-zeta)'(y-zeta)+lambda |eta| ag{1} ]

忽略常数项后，上式等价于

[argmin_eta dfrac{1}{2}eta^2 -dfrac{y'z}{N}eta+ lambda |eta| ]

将损失函数写成分段函数形式：

[f(eta)=egin{cases} f_1(eta) = dfrac{1}{2}eta^2 -left(dfrac{y'z}{N} + lambda ight)eta , eta lt 0\ f_2(eta) = dfrac{1}{2}eta^2 -left(dfrac{y'z}{N}- lambda ight)eta, eta geq 0 end{cases} ]

分类讨论：

• 若(dfrac{y'z}{N}gt lambda)，则(f_1(eta) gt 0)，(f_2(eta))在(hateta=dfrac{y'z}{N}- lambda)处取到最小值(f_2(hateta)lt 0)，因此解为(hateta=dfrac{y'z}{N}- lambda)；
• 若(left|dfrac{y'z}{N} ight|leq lambda)，则(f_1(eta) geq 0)，(f_2(eta) geq 0)，且在(hateta=0)处有(f_1(hateta)=f_2(hateta)=0)，因此解为(hateta=0)；
• 若(dfrac{y'z}{N}lt -lambda)，则(f_2(eta) gt 0)，(f_1(eta))在(hateta=dfrac{y'z}{N}+lambda)处取到最小值(f_1(hateta)lt 0)，因此解为(hateta=dfrac{y'z}{N}+lambda)。

利用软阈值算子（soft-thresholding operator）(S_lambda(x)= ext{sign}(x)(|x|-lambda)_+)，可将以上三种解统一为

[hateta=S_lambda(y'z/N) ]

其实在我们的设定下，OLS估计量为( ildeeta=y'z/N)，因此，将OLS估计量通过一个软阈值算子的操作，就变成了LASSO估计量。

1.2 次梯度

如果引入次梯度（subgradient）的概念，可以更直接地求解((1))式。设(|eta|)的次梯度为(sin ext{sign}(eta))，它的形式是，当(eta eq 0)时有(s= ext{sign}(eta))，当(eta = 0)时有(sin [-1,1])。根据凸优化（convex optimization）理论，求解((1))相当于求解

[-dfrac{1}{N}z'(y-zeta) +lambda s =0 ]

的解((hateta,hatlambda))。化简后得到(y'z/N = eta+lambda sineta+lambda ext{sign}(eta))，最终同样可以解出(hateta=S_lambda(y'z/N))。比如(eta=0)时，就意味着(y'z/N in[-lambda,lambda])。

2 多变量情形：循环坐标下降法

我们来看多变量的完整版LASSO问题。将自变量排成(N imes p)的矩阵(X)，我们要求解的是

[argmin_{etain mathbb{R}^p} dfrac{1}{2N}leftVert y-XetaVert_2^2+lambda ightVertetaVert_1 ]

在这里，我们使用循环坐标下降法（cyclic coordinate descent），它的思想是，按一定顺序依次对(p)个参数进行优化，比如按(j=1,ldots,p)的顺序，在第(j)次优化时，保持其他所有系数不变，变动(eta_j)使损失函数最小化。

根据以上思想，我们将第(j)次的最优化目标写为

[argmin_{eta_jin mathbb{R}^p} dfrac{1}{2N}leftVert y-sum_{k eq j}x_{cdot k}eta_k-x_{cdot j}eta_j ightVert^2_2+lambda sum_{k eq j}|eta_k| +lambda |eta_j| ]

记(r^{(j)}=y-sum_{k eq j}x_{cdot k}hat{eta}_k)，这称为partial residual，那么根据第1.1节中的结果，我们可以得出

[hateta_j = S_lambda (x_{cdot j}' r^{(j)}/N) ]

记(r = r^{(j)}-x_{cdot j}hateta_j)，上式相当于更新规则

[hateta_j leftarrow S_lambda (hateta_j +x_{cdot j}' r/N) ]

由于目标函数是凸的，没有局部的极小值，因此，每次更新一个坐标，最终可以收敛到全局最优解。

Pathwise coordinate descent（逐路径坐标下降）：可以先取一个使(hateta=0)的最小的(lambda)，然后，略微减小(lambda)的值，并以上一次得到的(hateta)作为“warm start”，用坐标下降法迭代直到收敛，不断重复这个过程，最终就可以得到在(lambda)的一系列变化范围内的解。

那么，怎样才能使(hateta=0)？利用次梯度，我们可以知道，对于(hateta_j=0)，必有(x_{cdot j}'y /N in [-lambda,lambda])，即要求(lambda geq |x_{cdot j}'y| /N)，若要使整个(hateta=0)，则可取(lambda =max_j |x_{cdot j}'y| /N)，这就是使(hateta=0)的最小的(lambda)。

3 其他解法

求解LASSO还有其他的解法，如homotopy method，它可以从(0)开始，得到序列型的解的路径，路径是分段线性的。

还有LARS（least angle regression）算法，这是homotopy method之一，可以有效得到分段线性路径。

这里不作展开。

4 正交基

在上面的过程中，如果将自变量正交化，可以大大简化计算。如在第2节中，如果自变量之间是正交的，则(x_{cdot j}' r^{(j)}/N = x_{cdot j}' y/N)，此时(hateta_j)就是将(y)对(x_{cdot j})做回归的OLS解，通过软阈值算子后的值。