机器学习系列——最小角回归

在介绍最小角回归之前，需要先看看两个预备算法：

• 前向选择算法
• 前向梯度算法

前向选择算法

前向选择算法的原理是一种典型的贪心算法。要解决的问题是：

这样的线性关系，如何求解系数。其中是的向量，是的矩阵，为的向量。为样本数量，为特征维度。

把矩阵看成个的向量。在这个向量中选择一个与目标的余弦距离最大的一个，用来逼近，得到下式：
，其中

即是在上的投影。那么，可以定义残差：。由于是投影，可知和是正交的。再以作为新的因变量，去掉后的剩下的自变量的集合作为新的自变量集合，重复刚才投影和残差的操作，直到残差为0，或者所有的自变量都用完了，才停止算法。

当只有2维时，如上图所示，和最接近的是，首先在上投影，残差如上图长虚线。此时模拟了，模拟了（仅仅模拟了一个维度）。接着发现最接近的是，此时用残差接着在投影，残差为图中短虚线。由于没有其他自变量了，此时模拟了，对应的模拟了两个维度的即为最终结果。

此算法对每个变量只需执行一次操作，效率高，运算快。但，当自变量不是正交的时候，每次都在做投影，所以算法只能给出一个局部近似解。这个简单的算法太粗糙，不能直接用于Lasso回归。

前向梯度算法

前向梯度算法和前向选择算法有类似的地方，也是在个中选择和目标最为接近(余弦距离最大)的一个变量，用来逼近。但前向梯度算法不是粗暴的用投影，而是每次在最为接近的自变量的方向移动一小步，然后再看残差和哪个最为接近。此时我们也不会把去除，因为我们只前进了一小步，有可能下面最接近的自变量还是。如此进行下去，直到残差减小到足够小，算法停止。

当只有2维时，例子如上图，和最接近的是，首先在上面走一小段距离，此处为一个较小的常量，发现此时的残差还是和最接近。那么接着沿走，一直走到发现残差不是和最接近，而是和最接近，此时残差如上图长虚线。接着沿着走一小步，发现残差此时又和最接近，那么开始沿着走，走完一步后发现残差为0，那么算法停止。此时由刚才所有的所有步相加而模拟，对应的算出的系数即为最终结果。

最小角回归算法

最小角回归对前向梯度和前向选择做了这种，保留了前向梯度算法一定程度上的精确性，同时简化了前向梯度算法一步步迭代的过程：

首先，找到与因变量最接近或相关度最高的自变量，使用类似于前向梯度算法中的残差计算方法，得到新的目标，此时不用和前向梯度算法一样小步小步的走，而是直接向前走直到出现一个，使得和的相关度和与的相关度是一样的，此时残差就在和的角平分线上，此时我们开始沿着这个残差角平分线走，直到出现第三个特征和的相关度等于与的一样。将其也加入到的逼近特征集合中，并用的逼近特征集合的共同角分线，作为新的逼近方向，循环直到足够小或者所有变量都取完位置。

当只有2维时。例子如上图，和最接近的是,首先在上走一段距离，直到残差在和的角平分线上，此时沿着角平分线走，直到残差足够小才停止。此时对应的系数即为最终的结果。

最小角回归法是一个适用于高维数据的回归算法，其主要的优点有：

1）特别适合于特征维度n 远高于样本数m的情况。

2）算法的最坏计算复杂度和最小二乘法类似，但是其计算速度几乎和前向选择算法一样

3）可以产生分段线性结果的完整路径，这在模型的交叉验证中极为有用

主要的缺点是：

由于LARS的迭代方向是根据目标的残差而定，所以该算法对样本的噪声极为敏感