分组最小角回归算法（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 确定的求解方向并不依赖该参数。