LASSOをまとめていると、LARS（最小角回帰法：Least Angle Regression）が出てきたので、これを機会に手順をちゃんと理解しようと思う。
行列と角度、高校や大学で習ったものの、いざ実データで、となるとどうしてもピンと来ない。実装してようやく理解できたので、その記録。
LARS をまとめる
LARS を理解する上で、引っかかったのは「最小二乗法」と「プロジェクションの方向」でした。
最小二乗法
高校までは二次元だった最小二乗法は、大学で多次元になります。行列で処理するわけですが、行列に苦手意識があって、理解が曖昧になりがちです。改めて、最小二乗法を整理してみると、意外と理解できました。
実装したコードだと、最小二乗法は、G <- solve(t(X_active) %*% X_active) %*% t(X_active)で使っていて、いわゆる疑似逆行列を求めて係数$\beta$を推定しています。
残差の二乗和（RSS）を、目的変数を(y)、予測値を(\hat{y})、その残差を(\varepsilon)は、次の関係になる。 [ \varepsilon = y - \hat{y} ] [ \text{RSS} = \varepsilonT \varepsilon = (y - \hat{y})T (y - \hat{y}) ]
また、説明変数行列(X)と係数ベクトル(\beta)の積が予測値(\hat{y})になる。 [ \hat{y} = X \beta ]
(\beta)を微分して RSS を 0 にすると、式は$y$、$X$、$\beta$の式になる。 [ \frac{\partial \text{RSS}}{\partial \beta} = \frac{\partial}{\partial \beta} \left( (y - X \beta)T (y - X \beta) \right) = 0 ] [ \frac{\partial \text{RSS}}{\partial \beta} = -2 XT (y - X \beta) = 0 ] [ -2 XT X \beta + 2 XT y = 0 ] [ XT X \beta = XT y ]
(X^{T} X)が正則なので、疑似逆行列を使って式を変形する。 [ (XT X)^{-1}(XT X) \beta = (XT X)^{-1}XT y ] [ I \beta = (XT X)^{-1}XT y ] [ \beta = (XT X)^{-1} XT y ]
プロジェクションの方向
LARS は、残差ベクトルと絶対値が最も高い説明変数を選び、アクティブセットと呼ばれる変数の集合に加えます。説明変数の係数を更新する際に、残差ベクトルとアクティブセット内の説明変数の符号付き線形結合ベクトルとの内積が最大になる（相関が等しくなる）ようにします。なお、符号付き線形結合ベクトルとは、説明変数の係数にその相関係数の符号（正か負か）を掛けたものです。残差ベクトルと符号付き線形結合ベクトルの内積が最大になると（相関が等しくなると）、なす角が 0 に近づきます。これが「最少角」の名前の由来です。
このとき、符号付き線形結合ベクトルがプロジェクションの方向を示します。例えば、アクティブセット $X$ が $x_1$ と $x_2$ からなる行列で、係数ベクトルが $\beta$ とすると、残差ベクトルは $y - X\beta$ になります。LARS はこの $y - X\beta$ と $x_1$ と $x_2$ との内積が最大に（相関が等しく）なるようにします。つまり、
$$ XT(y - X\beta) = (c_1, c_2)T $$
$$ XTy - XTX\beta = (c_1, c_2)T $$
$$ \beta = (XTX)^{-1}XTy - (XTX)^{-1}(c_1, c_2)T $$
ここで、$c_1$ と $c_2$ はそれぞれ $y - X\beta$ と $x_1$ と $x_2$ との内積です。この式は、残差ベクトルとプロジェクション方向（符号付き線形結合ベクトル）のなす角が最小（0 に近い）ことを意味します。
この $(XTX)^{-1}XTy$ がプロジェクション項、$(XTX)^{-1}(c_1, c_2)T$ が補正項になります。プロジェクション項は、教師データをアクティブセット内の説明変数で近似したものです。これは、教師データをアクティブセット内の説明変数で張られた部分空間に射影したものに相当します。補正項は、プロジェクション項から係数ベクトルをずらすためのものです。これは、残差ベクトルとプロジェクション方向が同じ角度になるように設定されます。
このとき、$s$ を補正項の大きさを決めるインデックス、相関ベクトルのノルムを $C = \sqrt{c_12 + c_22}$ と置くと、
$$ (XTX)^{-1}(c_1, c_2)T = (XTX)^{-1}C(c_s/C)T $$
と変換できます。なお、この相関ベクトルをノルムで割った $(c_s/C)$ は、その $s$ 番目の要素以外がゼロであるベクトルになります。
LARS では、残差ベクトルとアクティブセット外の説明変数との内積(相関)が等しくなるように$s$を選びます。これにより、補正項が最も大きくなります。補正項が大きくなれば、係数ベクトルはプロジェクション項から離れます。つまり、プロジェクション方向は残差ベクトルと同じ角度になるように決められます。
