分组最小角回归算法（group LARS）

继续前两篇博文中对于最小角回归（LARS)和lasso的介绍。在这篇文章中，我打算介绍一下分组最小角回归算法（Group LARS）。本文的主要观点均来自Ming Yuan和Yi Lin二人2006合作发表在JRSSB上的论文Model selection and estimation in regression with grouped variables.

首先，我想说明一下，为何要引入分组变量（grouped variable)的概念。举一个简单的例子，在可加的多项式模型中，每一项都是多项式。这个多项式有可能可以通过最初的变量的线性组合来表达。在进行这种类型的回归中，挑选重要的变量其实质是挑选重要的因子（factor），而因子则是最初的那些变量的线性组合。分组变量的回归问题，实际上就是我们一般所说的回归问题的推广。如果我们把每一个单独的变量都看成一个因子，那么这种情况下的回归就是一般意义下的回归。下面用公式更加直白的说明这个问题：

$$ Y=\sum_{j=1}^JX_j\beta_j+e $$

其中$Y$是个$n$维向量，$e~N_n(0,\sigma^2I)$.$X_j$是$n\times p_j$矩阵，代表的是第j个因子（factor，是变量variables的线性组合)。$\beta_j$是$p_j$维的系数向量。依然假定$Y$是中心化的，$X_j$是中心化并且正交化的（$X_j’X_j=I$）。这个就是分组变量的回归模型。

在小弟之前的文章中介绍过最小角回归（LARS）算法，对于变量选择来说，这种算法是比较易于计算机实现的，而且比传统的向前逐步回归（forward selection）更加谨慎，但是没有逐段回归（stagewise）那么谨小慎微。对于分组变量的回归模型选择问题来说，直接套用LARS算法可能会挑选出一些不必要的因子进入回归模型中。因此在文章中，作者提出了分组最小角回归（group LARS).这种算法对最小角回归进行了推广，下面简单介绍一下这种算法。

推广是循序渐进的，因此，我们先来看看$p_j$均相等的情况（注意这里$p_j$未必等于1）。在传统的LARS算法中，我们是要保证入选变量和当前残差的角度都相同。如今，我们就需要保证入选的因子们（再次强调，这里是因子，是原始变量的线性组合）与当前残差的角度相同。直观地来定义一个角度$\theta(r,X_j)$，这个角度就是向量$r$与$X_j$中的变量所构成的空间的夹角，也就是$r$与它在$X_j$中的变量所构成空间的投影的夹角。（再废话两句，这个夹角越小，就意味着$r$与$X_j$中的变量构成的空间中的相关系数越大。）当$r$是当前残差的时候，我们就可以确定求解路径（solution path）为当前残差在$X_j$中的变量所构成的空间上的投影的方向。

上面说的可能还不够清楚，下面我分步骤具体介绍每一步的做法。

1. 最开始时，回归变量集依然是空集，此时的残差就是$Y$,我们寻找和$Y$夹角最小的$X_j$.记它为$X_{j1}$.（这里要插一句，就是如何度量这个角度。用这个角的余弦值的平方即可：$cos^2(\theta(r,X_j))=\frac{|X_j’r|^2}{|r|^2}$，角度越小，这个值越大。）
2. 确定求解路径为$Y$在$X_{j1}$中的变量所构成的空间上的投影的方向。然后在这个路径上前进，直到出现第二个因子$X_{j2}$,使得当前残差$r$与这两个因子的夹角同样小。也就是$|X_{j1}’r|^2=|X_{j2}’r|^2$。
3. 计算新的求解路径，这个路径其实就是当前残差在$X_{j1}$和$X_{j2}$的变量所构成的空间中投影的方向。然后再沿着这条路径前进，直到第三个因子出现，使得当前残差和这三个因子的夹角都是同样小。

然后继续按照上面的步骤，计算出求解路径，然后继续前进。直到找到第四个满足条件的因子。

这些步骤和原始的LARS的进程是同样的。只不过在确定求解方向时有了变化。

上面介绍的都是$p_j$相同的情况，当$p_j$不同的时候，只要对上面的过程做一个小的改动即可。用$\frac{|X_j’r|^2}{p_j}$代替$|X_j’r|^2$,其他过程都不变。这种对于LARS算法的推广是比较直观的。而且M.Yuan和Y.Lin在文章中还指出，这种算法相对于正交化$X_j$的过程是稳定的，通过Gram-Schmidt方法进行正交化本来是依赖于选择的参数的，但是分组LARS确定的求解方向并不依赖该参数。