本文介绍LAR（Least angle regression，最小角回归），由Efron等（2004）提出。这是一种非常有效的求解LASSO的算法，可以得到LASSO的解的路径。
1 算法介绍
我们直接看最基本的LAR算法，假设有
个样本，自变量是
维的：
- 先对
（
）做标准化处理，使得每个predictor（的每列）满足
，
。我们先假设回归模型中只有截距项，则
，记残差
，而其他的系数
；
- 找出与
相关性最大的
，加入active set；
- 将
从
逐步向LS系数
变动，直到有另一个
，它与的相关系数绝对值，和与的相关系数绝对值一样大；
- 将和
同时向二者的联合LS系数变动，直到再出现下一个
，它与的相关系数满足上一步的条件；
- 重复上述过程，
)
步后，就得到完整的LS解。
2 算法性质
2.1 保持最小角
我们先来看LS估计量的一个性质：若每个predictor与
的相关系的数绝对值相等，从此时开始，将所有系数的估计值同步地从移向LS估计量，在这个过程中，每个predictor与残差向量的相关系数会同比例地减少。
假设我们标准化了每个predictor和，使他们均值为，标准差为
。在这里的设定中，对于任意
，都有
，其中
为常数。LS估计量%5E%7B-1%7DX'y)
，当我们将系数从向
移动了
（![\alpha\in[0,1]](https://math.jianshu.com/math?formula=%5Calpha%5Cin%5B0%2C1%5D)
）比例时，记拟合值为%3D%5Calpha%20X%5Chat%5Cbeta)
。
另外，记%7D)
为只有第
个元素为、其他元素均为的维向量，则%7D)
，再记
，记投影矩阵%5E%7B-1%7DX')
。
这里的问题是，在变大过程中，每一个与新的残差的相关系数，是否始终保持相等？且是否会减小？
由于![\left| x_{\cdot j}' [y-u(\alpha)]\right|=\left|x_{\cdot j}'y - \ell_p^{(j)\prime} X' u(\alpha)\right|=(1-\alpha)N\lambda](https://math.jianshu.com/math?formula=%5Cleft%7C%20x_%7B%5Ccdot%20j%7D'%20%5By-u(%5Calpha)%5D%5Cright%7C%3D%5Cleft%7Cx_%7B%5Ccdot%20j%7D'y%20-%20%5Cell_p%5E%7B(j)%5Cprime%7D%20X'%20u(%5Calpha)%5Cright%7C%3D(1-%5Calpha)N%5Clambda)
，即内积与无关。再由'(y-Py)%3DN-y'Py)
可知
。
相关系数的绝对值
![\begin{aligned} \lambda(\alpha)=& \dfrac{\left| x_{\cdot j}' [y-u(\alpha)]\right|}{\Vert x_{\cdot j}\Vert \Vert y-u(\alpha)\Vert}\\ =& \dfrac{(1-\alpha)N\lambda}{\sqrt{N} \sqrt{[y-u(\alpha)]'[y-u(\alpha)]}}\\ =& \dfrac{(1-\alpha)N\lambda}{\sqrt{N} \sqrt{N(1-\alpha)^2+(2\alpha-\alpha^2)\text{RSS}}}\\ =& \begin{cases} \dfrac{\lambda}{\sqrt{1+\left[-1+\dfrac{1}{(1-\alpha)^2}\right]\dfrac{\text{RSS}}{N}}},&\alpha\in [0,1)\\ 0,&\alpha=1 \end{cases} \end{aligned}](https://math.jianshu.com/math?formula=%5Cbegin%7Baligned%7D%20%5Clambda(%5Calpha)%3D%26%20%5Cdfrac%7B%5Cleft%7C%20x_%7B%5Ccdot%20j%7D'%20%5By-u(%5Calpha)%5D%5Cright%7C%7D%7B%5CVert%20x_%7B%5Ccdot%20j%7D%5CVert%20%5CVert%20y-u(%5Calpha)%5CVert%7D%5C%5C%20%3D%26%20%5Cdfrac%7B(1-%5Calpha)N%5Clambda%7D%7B%5Csqrt%7BN%7D%20%5Csqrt%7B%5By-u(%5Calpha)%5D'%5By-u(%5Calpha)%5D%7D%7D%5C%5C%20%3D%26%20%5Cdfrac%7B(1-%5Calpha)N%5Clambda%7D%7B%5Csqrt%7BN%7D%20%5Csqrt%7BN(1-%5Calpha)%5E2%2B(2%5Calpha-%5Calpha%5E2)%5Ctext%7BRSS%7D%7D%7D%5C%5C%20%3D%26%20%5Cbegin%7Bcases%7D%20%5Cdfrac%7B%5Clambda%7D%7B%5Csqrt%7B1%2B%5Cleft%5B-1%2B%5Cdfrac%7B1%7D%7B(1-%5Calpha)%5E2%7D%5Cright%5D%5Cdfrac%7B%5Ctext%7BRSS%7D%7D%7BN%7D%7D%7D%2C%26%5Calpha%5Cin%20%5B0%2C1)%5C%5C%200%2C%26%5Calpha%3D1%20%5Cend%7Bcases%7D%20%5Cend%7Baligned%7D)
因此，任意predictor与当前残差的相关系数绝对值，会随着的增加，同比例地减小，并且%3D%5Clambda)
，%3D0)
。
现在，我们再回顾一下LAR的过程。在第
步开始时，将所有active set中的predictor的集合记为
，此时在上一步估计完成的系数为
，它是
维且每个维度都非零的向量，记此时残差为
，用
对
做回归后系数为%5E%7B-1%7DX_%7B%5Cmathcal%7BA%7D_k%7D'%20r_k)
，拟合值
。另外，我们知道
，而一个predictor加入的条件就是它与当前的相关系数的绝对值等于中的predictor与当前的相关系数的绝对值，所以
向量的每个维度的绝对值都相等，也即
的每个维度的绝对值都相等，
就是与各个中的predictor的角度都相等的向量，且与它们的角度是最小的，而也是下一步系数要更新的方向，这也是“最小角回归”名称的由来。
2.2 参数更新
那么，在这个过程中，是否需要每次都逐步小幅增加，再检查有没有其他predictor与残差的相关系数绝对值？有没有快速的计算的方法？答案是有的。
在第步的开始，中有个元素，我们记
，其中
，并记
，此时的active set其实就是
。在这里，我们将做个修改，记)
，再令![X_{\mathcal{A}_k}=[\cdots s_jx_{\cdot j}\cdots]_{j\in\mathcal{A}_k}](https://math.jianshu.com/math?formula=X_%7B%5Cmathcal%7BA%7D_k%7D%3D%5B%5Ccdots%20s_jx_%7B%5Ccdot%20j%7D%5Ccdots%5D_%7Bj%5Cin%5Cmathcal%7BA%7D_k%7D)
。
此时更新方向为，
，并取
。更新的规则为%3D%20%5Chat%20y_%7B%5Cmathcal%7BA%7D_k%7D%2B%5Calpha%20u_k)
。因此，任一predictor，与当前残差的内积就为%3D%5Chat%20c_j-%5Calpha%20a_j)
，而对于
，有%5Cright%7C%3D%5Chat%20C-%5Calpha%20%5Chat%20C)
。
对于
，如果要使与当前残差的相关系数绝对值，与在中的predictor与当前残差的相关系数绝对值相等，也即它们的内积的绝对值相等，必须要满足%5Chat%20C)
。问题转化为了求解使它们相等的
，并对于所有的，最小的即为最后的更新步长。
由于
，因此只需考虑
与
的大小关系即可。最后解为
注意到
%7D%7B%5Chat%20C%5E2-a_j%5E2%7D)
因此，当
时，除非
即
，否则必有
。反之，当
时，除非
即
，否则必有
。综上所述，上面的解可以写为
其中
表示只对其中正的元素有效，而丢弃负的元素。
3 LAR与LASSO
LAR虽然是求解LASSO的算法，但它得到的解的路径，在出现了某个系数要穿过的情况时，有可能与LASSO不一样。因此，想要完全得到LASSO的解的路径，还需要做修正。
我们在第1节算法的第4步中加入一个规则：
- 若一个非零系数又变为了，将该predictor从active set中剔除，重新计算当前的LS解作为更新方向。
在修正后，LAR就可以解任意LASSO问题，包括
的问题。
为什么会出现与LASSO解不同的情况？我们注意到，对于LASSO的active set 
中的predictor，它的系数需要满足
%20%3D%20%5Clambda%20%5Ctext%7Bsign%7D(%5Chat%5Cbeta_j))
而对于LAR的active set 
中的predictor，它的系数需要满足
%20%3D%20%5Cgamma%20s_j)
其中
为左边内积的符号。
在正常情况下，上面二者的右侧是相等的，也因此LAR的解就是LASSO的解。但是，当一个非零系数要穿过时，它不再满足LASSO的解条件，因此会被踢出，而LAR的解条件却可能没有突变（因为是由内积的符号而非系数的符号决定的）。在系数到达时，它满足
%20%5Cleq%20%5Clambda)
这恰恰与
中的predictor的条件一致，因此可以将它也踢出，这样就让LAR与LASSO相一致了。
参考文献
- Efron, Bradley, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. "Least angle regression." Annals of statistics 32, no. 2 (2004): 407-499.
- Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
网友评论