最小角回归(Least Angle Regression，下面简称为LARS)是一种模型选择算法。和传统的模型选择方法相比，它是一个相对不那么”贪心”的版本，同时表现出很好的性能。通过对LARS的一点小改动，它可以用来实现LASSO和前向阶进回归(Forward Stagewise linear regression)。LARS的一大优点是计算开销小。
模型选择算法
模型选择方法的目标是从同一个数据集上选择一个最适应的模型，经典的模型选择算法有：前向选择(Forward Selection)，后向删除(Backward Elimination)，全子集回归(All Subsets Regression)等。
模型选择也可以看作是对特征进行选择：前向选择就是选择对模型贡献最大的$k$个特征，后向删除就是逐一删除贡献最小的特征直到剩下$k$个特征；除了这些离散的方法，还有相对连续的特征选择方法，比如LASSO。
下面，我们讨论两种优秀的模型选择算法：LASSO和前向阶进回归。
OLS（Ordinary Least Square）
记 $\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_m$ 为若干$n$维向量，代表自变量。$\mathbf{y}$代表$n$个样本的响应值(responses)。通过归一化，我们总可以让自变量的均值为0，且向量$\mathbf{x}$长度为1，使得响应值的均值也为0，即
$$\sum_{i=1}^n y_i=0,\quad \sum_{i=1}^n x_{ij}=0,\quad \text{and} \quad \sum_{i=1}^n x_{ij}^2 =1\quad \text{for $j = 1,2,\cdots,m$}\tag{1}$$
给定一组回归系数 $\hat{\boldsymbol{\beta}}=(\hat{\beta_1},\hat{\beta_2},\cdots,\hat{\beta_m})^T$就可以给出一组预测值 $\hat{\boldsymbol{\mu}}$
$$\hat{\boldsymbol{\mu}}=\sum_{j=1}^m\mathbf{x}_j\hat{\beta_j}=X\hat{\boldsymbol{\beta}} \quad [X_{n\times m}=(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_m)]\tag{2}$$
对应的总平方误差为
$$S(\hat{\boldsymbol{\beta}})=||\mathbf{y}-\hat{\boldsymbol{\mu}}||^2=\sum_{i=1}^n(y_i-\hat{\mu_i})^2\tag{3}$$
一般的最小化平方差的线性回归等价于下面的无约束优化问题：
$$\min S(\hat{\boldsymbol{\beta}})\tag{4}$$
前向阶进回归（Forward Stagewise Selection）
前向阶进回归与经典的前向选择很相似。
前向选择的基本思想是：逐个选择对模型贡献最大的变量，直到满足一个停止条件（可以是变量的数目，也可以是新加变量对模型改进效果的某种度量）。具体过程可描述为：给定一个变量的集合，我们从中选出与响应值 $y$ 相关度最大的变量，比方说 $x_{j1}$，然后做 $y$ 关于 $x_{j1}$ 的线性回归。得到的残差向量与 $x_{j1}$ 正交（为什么正交后面会说明），把这个残差当作响应值，重复这个过程，找出下一个相关度最高的变量。在 $k$ 步之后，我们就得到了 $k$ 个变量的集合 $x_{j1},x_{j2},\cdots,x_{jk}$ ，用它们构成最终的线性回归模型。
不过，前向选择是一种过于贪心的算法，它在每一步只关心局部最优，可能会在第二部排除某个和 $x_{j1}$ 相关但却很有用的变量，导致最后得到的模型并不是一个好的模型。
而前向阶进更像是前向选择的一个更小心的版本，每一步迈得小很多，可能要走几千步才能得到最终得模型。
开始时，设 $\hat{\boldsymbol{\mu}}=0$ 然后一小步一小步迭代地构建起整个回归模型。如果 $\hat{\boldsymbol{\mu}}$ 是某时刻算法的预测值，设$\mathbf{c}(\hat{\boldsymbol{\mu}})$为此时的相关度向量
$$\hat{\mathbf{c}}=\mathbf{c}(\hat{\boldsymbol{\mu}})=X^T(\mathbf{y}-\hat{\boldsymbol{\mu}})\tag{5}$$
则$\hat{c_j}$正比于变量$x_j$和残差向量之间的相关度。下一步是选择具有最大绝对相关度的方向，更新$\hat{\boldsymbol{\mu}}$
$$\hat{j}=\arg\max|\hat{c_j}|\quad \text{and}\quad \hat{\boldsymbol{\mu}}\to \hat{\boldsymbol{\mu}}+\epsilon\cdot\text{sign}(\hat{c_j})\cdot\mathbf{x}_{\hat{j}}\tag{6}$$
其中，$\epsilon$是一个小的常数。这里的“小”非常关键，如果$\epsilon$选得比较大，比如$\epsilon=|\hat{c_{\hat{j}}}|$就会变成了经典前向选择算法，则会排除掉那些与$x_{\hat{j}}$相关的变量。
Lasso
用 $T(\hat{\boldsymbol{\beta}})$ 表示 $\hat{\boldsymbol{\beta}}$ 的绝对值范数
$$T(\hat{\boldsymbol{\beta}})=\sum_{j=1}^m|\hat{\beta_j}|\tag{7}$$
则Lasso即为下面的约束优化问题：
$$\min S(\hat{\boldsymbol{\beta}}) \quad \text{s.t.} \quad T(\hat{\boldsymbol{\beta}}) \le t\tag{8}$$
Lasso也可以作为一种收缩方法用来防止过拟合，类似于岭回归，等价于下面的优化问题：
$$\min S(\hat{\boldsymbol{\beta}})+\lambda T(\hat{\boldsymbol{\beta}})\tag{9}$$
只不过在岭回归中，使用的是$L_2$范数。这里的$\lambda$与$t$具有一一对应关系。
Lasso是least absolute shrinkage and selection operator的缩写
比较
对于一个含有10个变量的回归问题，下图描述了用Lasso和阶进算法时，每个变量的系数随所有系数绝对值之和的变化。
每条线旁边的编号代表变量的编号。随着$t$的不断增大，逐渐有新的变量被纳入到模型中。横轴上的顺序表示变量纳入模型的顺序，即$3,9,4,7,2,\cdots,1$，反映变量对模型的贡献度，其中$x_3,x_9$最大，依次次之。越往后，变量系数$\hat{\beta_j}$之间的差距越大（尤其是$x_5$），表明模型为了减少偏差，使方差变得过大，发生过拟合。
当 $t=3460$ 时，$\hat{\boldsymbol{\beta}}$ 和OLS得到的系数是相同的。也就是说 $t$ 的约束已经失去作用。可以看出，Lasso会将OLS的系数收缩到0，收缩效果在 $t$ 比较小的时候尤为明显。
我们注意到，这两张图几乎一样，除了局部的细微差别($x_8$)。这样高的相似性并不是偶然，我们在后面会解释这两种算法其实都是LARS的不同变体。
LARS 算法
LARS类似于阶进算法，也是不断迭代运行。不过LARS只需要 $m$ 步迭代就可以完成，$m$ 是变量的个数。对于上图中 $m=10$ 的例子，LARS就只需要10步，而阶进算法需要多达6000步。
LARS算法的过程大致如下：首先，像传统的前向选择一样，将所有系数 $\hat{\beta_j}$ 置为0，然后选择一个与响应值相关度最大的变量，比方说$x_{j1}$。然后，在这个方向上前进尽可能大的一步（增大/小系数$\hat{\beta_{j1}}$），直到另一个变量，比如$x_{j2}$，与目前的残差有同样大的相关度。这时候，LARS算法和前向选择分道扬镳。不向前向选择中那样继续沿 $x_{j1}$ 方向前进，LARS选择 $x_{j1}$ 与 $x_{j2}$ 的角平分线方向前进（即同时等量增大/小$\hat{\beta_{j1}}$和$\hat{\beta_{j2}}$），直到第三个变量 $x_{j3}$ 达到相关度的要求，进入到这个”最相关”的集合中，然后再沿这三个变量的角平分线方向前进（同时等量增大/小$\hat{\beta_{j1}}$、$\hat{\beta_{j2}}$ 和 $\hat{\beta_{j2}}$），依次类推。
LARS逐步构建起模型 $\hat{\boldsymbol{\mu}}=X\hat{\boldsymbol{\beta}}$，每一步添加一个变量进去。所以，在 $k$ 步后，只有 $k$ 个系数 $\hat{\beta_j}$ 是非零的。下图展示了在 $m=2$ 时，即 $X=(\mathbf{x}_1,\mathbf{x}_2)$ 时，LARS的过程。此时，相关度只依赖于 $\mathbf{y}$ 在由 $\mathbf{x}_1$ 和 $\mathbf{x}_2$ 确定的线性空间$\mathcal{L}(X)$ 上的投影 $\overline{\mathbf{y}}_2$。
$$\mathbf{c}(\hat{\boldsymbol{\mu}})=X^T(\mathbf{y}-\hat{\boldsymbol{\mu}})=X^T(\overline{\mathbf{y}}_2-\hat{\boldsymbol{\mu}})\tag{10}$$
算法从 $\hat{\boldsymbol{\mu}}_0=\mathbf{0}$ 开始。在上图中，$\overline{\mathbf{y}}_2-\hat{\boldsymbol{\mu}}_0$ 与 $\mathbf{x}_1$ 的夹角比 $\mathbf{x}_2$ 小，即说明 $c_1(\hat{\boldsymbol{\mu}}_0) > c_2(\hat{\boldsymbol{\mu}}_0)$，故LARS沿着 $\mathbf{x}_1$ 方向增加 $\hat{\boldsymbol{\mu}}_0$
$$\hat{\boldsymbol{\mu}}_1 = \hat{\boldsymbol{\mu}}_0 + \hat{\gamma}_1\mathbf{x}_1\tag{11}$$
阶进算法会选择 $\hat{\gamma}_1$ 等于某个很小的值 $\epsilon$，所以会重复迭代很多步。当沿图中的 $\mathbf{x}_1$ 方向一小步一小步地增加到 $\hat{\boldsymbol{\mu}}_1$ 时，$c_1(\hat{\boldsymbol{\mu}}_1) = c_2(\hat{\boldsymbol{\mu}}_1)$。然后阶进算法沿$\mathbf{x}_1$前进了一小步，发现有相关度更大的变量，于是就沿$\mathbf{x}_2$的方向前进一小步（图中的竖直方向有误），之后又发现此时的$\mathbf{x}_1$具有更大的相关度，依此类推，故整个路径是一个折线。
前向选择采用十分激进的做法，相当于选择足够大的 $\hat{\gamma}_1$ 使得 $\hat{\boldsymbol{\mu}}_1 = \overline{\mathbf{y}}_1$（$\overline{\mathbf{y}}_1$ 为 $\mathbf{y}$ 在 $\mathcal{L}(\mathbf{x}_1)$ 上的投影）。我们可以发现，此时的残差 $\overline{\mathbf{y}}_2-\overline{\mathbf{y}}_1$ 与 $\mathbf{x}_1$ 是正交的。在后面的选择过程中，前向选择会更倾向于选择那些与 $\mathbf{x}_1$ 正交的变量，因为残差在这个方向的投影为0，与 $\mathbf{x}_1$ 相关程度大的向量与残差的相关度便会很小。前项选择方法似乎认为在某轮迭代过程中，$y$ 在某个方向的分量是“全部”由这个变量造成的，从而激进地选择了前进很大的一步（选择大的 $\hat{\gamma}_1$）。以上图为例，前向选择会沿 $\mathbf{x}_2$ 的方向前进，步长为残差在 $\mathbf{x}_2$ 上的投影长度，如下图中 $\hat{\mathbf{u}}_2$ 所示，然而这并不是一个好的模型。
LARS选了一个大小适中的 $\hat{\gamma}_1$，不向阶进算法那么小，也不像前向选择那么大。选择这样的 $\hat{\gamma}_1$ 值使得残差 $\overline{\mathbf{y}}_2-\hat{\mathbf{u}}_1$ 与 $\mathbf{x}_1$ 和 $\mathbf{x}_2$ 的相关度相同，即残差沿着 $\mathbf{x}_1$ 和 $\mathbf{x}_2$ 的角平分线方向。记这个方向上的单位向量为 $\mathbf{u}_2$，则下一次更新 $\hat{\boldsymbol{\mu}}$ 为
$$\hat{\boldsymbol{\mu}}_2 = \hat{\boldsymbol{\mu}}_1 + \hat{\gamma}_2\mathbf{u}_2\tag{12}$$
当 $m=2$ 时，选择 $\hat{\gamma}_2$ 使得 $\hat{\boldsymbol{\mu}}_2 = \overline{\mathbf{y}}_2$。当 $m>2$ 时，则选择更小一点的 $\hat{\gamma}_2$，使一个新的变量加入到这个“最相关”的集合中。LARS算法也可以视为让 $\epsilon\to 0$ 时的阶进算法，不过计算开销要小很多（$\epsilon\to 0$ 时阶进算法开销趋向无穷）。
完整描述
理解了LARS算法的思想后，我们就可以来完整地用更抽象的数学语言来描述这个算法。
确定方向 $\mathbf{u}$
我们假设向量 $\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_m$ 之间是线性独立的。对于索引集合 $\{1,2,\cdots,m\}$ 的一个子集 $\mathcal{A}$，我们定义矩阵
$$X_{\mathcal{A}}=(\cdots s_j\mathbf{x}_j\cdots)_{j\in\mathcal{A}}\tag{13}$$
其中符号变量 $s_j$ 可以取1或-1，令
$$\mathcal{G}_{\mathcal{A}}=X_{\mathcal{A}}’X_{\mathcal{A}} \quad\text{and}\quad A_{\mathcal{A}}=(1_{\mathcal{A}}\mathcal{G}_{\mathcal{A}}^{-1}1_{\mathcal{A}})^{-\frac{1}{2}}\tag{14}$$
其中，$1_{\mathcal{A}}$ 是长度为 $\mathcal{A}$ 的维度的全1向量。则
$$\mathbf{u}_{\mathcal{A}}=X_{\mathcal{A}}w_{\mathcal{A}}\quad\text{where}\quad w_{\mathcal{A}}=A_{\mathcal{A}}\mathcal{G}_{\mathcal{A}}^{-1}1_{\mathcal{A}}\tag{15}$$
$\mathbf{u}_{\mathcal{A}}$ 是使各个变量与之夹角相等（小于90度）的方向单位向量，即有
$$X’_{\mathcal{A}}\mathbf{u}_{\mathcal{A}}=A_{\mathcal{A}}1_{\mathcal{A}}\quad\text{and}\quad||\mathbf{u}_{\mathcal{A}}||^2=1\tag{16}$$
对于为什么这样计算出来的方向是角平分线方向（与各个变量夹角相等），参考资料1中有详细的证明过程。
完整过程
我们先从 $\hat{\boldsymbol{\mu}}_0=\mathbf{0}$ 一步一步建立起 $\hat{\boldsymbol{\mu}}$ 。假设 $\hat{\boldsymbol{\mu}}_{\mathcal{A}}$ 是当前LARS算法的估计，于是
$$\hat{\mathbf{c}}=X’(\mathbf{y}-\hat{\boldsymbol{\mu}}_{\mathcal{A}})\tag{17}$$
是当前的相关度向量。“活跃集” $\mathcal{A}$ 是与 $\mathbf{y}$ 具有最大绝对相关度的变量的下标集合
$$\hat{C}=\max_j\{|\hat{c}_j|\}\quad\text{and}\quad \mathcal{A}=\{j:|\hat{c}_j|=\hat{C}\}\tag{18}$$
让
$$s_j=\text{sign}\{\hat{c}_j\}\quad\text{for}\quad j\in\mathcal{A}\tag{19}$$
用(13)~(15)式计算出$X_{\mathcal{A}},A_{\mathcal{A}},\mathbf{\mathcal{A}}$，计算出向量
$$\mathbf{a}\equiv X’\mathbf{u}_{\mathcal{A}}\tag{20}$$
LARS算法的下一步就是更新 $\hat{\boldsymbol{\mu}}_{\mathcal{A}}$，即
$$\hat{\boldsymbol{\mu}}_{\mathcal{A}_+}=\hat{\boldsymbol{\mu}}_{\mathcal{A}}+\hat{\gamma}\mathbf{u}_{\mathcal{A}}\tag{21}$$
其中
$$\hat{\gamma}=\text{min}^+_{j\in\mathcal{A}^c}\left\{\cfrac{\hat{C}-\hat{c}_j}{A_{\mathcal{A}}-a_j},\cfrac{\hat{C}+\hat{c}_j}{A_{\mathcal{A}}+a_j}\right\}\tag{22}$$
$\text{min}^+$ 表示只取正的最小值。
式(21)和(22)有以下解释：定义
$$\boldsymbol{\mu}(\gamma)=\hat{\boldsymbol{\mu}}_{\mathcal{A}}+\gamma\mathbf{u}_{\mathcal{A}}\tag{23}$$
对于 $\gamma>0$，当前的相关度为
$$c_j(\gamma)=\mathbf{x}’_j(\mathbf{y}-\boldsymbol{\mu}(\gamma))=\hat{c}_j-\gamma a_j\tag{24}$$
对于 $j\in\mathcal{A}$，式(16)-(18)可得出
$$|c_j(\gamma)|=\hat{C}-\gamma A_{\mathcal{A}}\tag{25}$$
这意味着所有的当前最大绝对相关度是同等下降的。对于$j\in\mathcal{A}^c$，让式(24)和式(25)相等可以得到：在 $\gamma=(\hat{C}-\hat{c}_j)/(A_{\mathcal{A}}-a_j)$ 时 $c_j(\gamma)$ 取得最大值；在 $\gamma=(\hat{C}+\hat{c}_j)/(A_{\mathcal{A}}+a_j)$ 时负相关度 $-c_j(\gamma)$ 取得最大值。因此式(22)中的 $\hat{\gamma}$ 应该取这两个中较小的正值 $\gamma$，使得新的下标 $\hat{j}$ 加入到“活跃集”中。新的“活跃集”为 $\mathcal{A}_+=\mathcal{A}\cup \{\hat{j}\}$，新的最大绝对相关度为 $\hat{C}_+=\hat{C}-\hat{\gamma}A_{\mathcal{A}}$ 。
如下图所示，新变量加入后，每个最大绝对相关度下降都是相同的，体现为最外侧的蓝线所代表的变量越来越多：在第一段只有变量3，第二段有变量3和9，第三段有变量3、4和9，……
随着变量越来越多，最大绝对相关度越来越小，说明能已选择的变量已经能很好地解释 $\mathbf{y}$，剩下没选的变量对模型的贡献很小。
与Lasso和前向阶进的联系
这部分内容单独写在另外的文章中。
参考资料：
- Least Angle Regression
- The Elements of Statistical Learning
- 《机器学习》 周志华 著
- The Lasso