LARSの整理・その１

LASSOをまとめていると、LARS（最小角回帰法：Least Angle Regression）が出てきたので、これを機会に手順をちゃんと理解しようと思う。

行列と角度、高校や大学で習ったものの、いざ実データで、となるとどうしてもピンと来ない。実装してようやく理解できたので、その記録。

LARSとは

LARSは、LASSOを効率的に計算できるスパースモデリングの一種です。

回帰分析において、変数選択と回帰係数の推定を同時に行うアルゴリズムであり、特徴量が非常に多い高次元データセットに対して効率的に特徴選択できる強みがある。

LARSが生まれた背景

• LARSはLASSOが持つ課題を開設するために考案されたスパースモデリングの一種。
• 数値的な最適化手法でパラメータを推定するLASSOがもつ計算コストや収束性の課題に対して、LARSは解析的なパラメータ決定を提供した。
• 説明変数と残差が成す角度が最も小さい変数を順に選択して、説明変数と残差の角度が等しくなるまで回帰係数の更新を繰り返す。
• この変数選択法は、LASSOよりも計算コストや収束性などが改善していて、効率的とされている。
• また、このアプローチは、説明変数間に相関がある場合でも、有効に変数選択や次元削減できる。

LARSの流れ

LARSは最小二乗法をベースにしていて、目的変数との係数がゼロにならない説明変数のセット（アクティブセット）、それを使って求める予測値、この予測値と目的変数の残差を考えます。

次のような流れで計算が進みます。

1. 初期値として全ての回帰係数を0にする。
2. 目的変数となす角度が最も小さい（目的変数との相関係数の絶対値が最も大きい）説明変数を求め、この選択した説明変数をアクティブセットにする。
3. アクティブセットの線形結合で表される方向に沿って、目的変数との残差が小さくなるように回帰係数を更新する。
4. 更新した後の残差となす角度が最も小さい説明変数を求め、この選択した説明変数をアクティブセットに加える。
5. アクティブセットの線形結合で表される方向（プロジェクションの方向）に沿って、残差を減らすように回帰係数を更新する。
6. この残差とアクティブセット以外の列ベクトルとの角度が同じになるまで、4,5を繰り返す。
7. 残差とアクティブセット以外の列ベクトルとの角度が同じになったら、その列ベクトルをアクティブセットに加える。また、残差ベクトルとアクティブセット内の列ベクトルとの角度が180度になったら、その列ベクトルをアクティブセットから除く。
8. 全ての説明変数がアクティブセットになるか、残差が0になったら終了する。

\[
\begin{align*}
&\text{Step 1: 初期化} \\
&\quad \beta = \mathbf{0} \quad \text{(全ての回帰係数をゼロベクトルで初期化)} \\
&\quad r = y \quad \text{(残差を目的変数で初期化)} \\
&\quad X_{\text{active}} = \emptyset \quad \text{(アクティブセットを空に初期化)} \\
\\
&\text{Step 2: メインループ} \\
&\quad \text{while } \|\beta\|_0 < p \quad \text{(非ゼロ要素の数が説明変数の総数より小さい間ループ)} \\
\\
&\quad \quad \text{Step 2.1: 最大相関の説明変数を選択} \\
&\quad \quad \text{if } X_{\text{active}} = \emptyset \quad \text{(最初のステップの場合)} \\
&\quad \quad \quad j_{\text{max}} = \text{argmax}_j |\langle X_j, r \rangle| \quad \text{(説明変数\(X_j\)と残差\(r\)の内積の絶対値が最大のインデックス)} \\
&\quad \quad \text{else} \quad \text{(2回目以降のステップの場合)} \\
&\quad \quad \quad X_{\text{active}}^c = X_{\text{active}} \quad \text{(アクティブセットから選択されていない変数のインデックス)} \\
&\quad \quad \quad Z = X^T_{\text{active}} X_{\text{active}}^c \quad \text{(アクティブセットの変数同士の内積行列)} \\
&\quad \quad \quad a = X^T r \quad \text{(各変数と残差の内積)} \\
&\quad \quad \quad j_{\text{max}} = \text{argmax}_j |\langle Z_j, a \rangle| \quad \text{(\(Z_j\)は行列\(Z\)の各列ベクトル)} \\
\\
&\quad \quad \text{Step 2.2: 選択された変数をアクティブセットに追加} \\
&\quad \quad X_{\text{active}} = X_{\text{active}} \cup \{j_{\text{max}}\} \\
\\
&\quad \quad \text{Step 2.3: アクティブセットに対する回帰係数を計算} \\
&\quad \quad \beta_{\text{active}} = (X_{\text{active}}^T X_{\text{active}})^{-1} X_{\text{active}}^T y \\
\\
&\quad \quad \text{Step 2.4: アクティブセットに対する回帰係数を全変数に拡張} \\
&\quad \quad \beta = \mathbf{0} \quad \text{(全ての回帰係数をゼロベクトルで初期化)} \\
&\quad \quad \beta_{\text{active}} \text{の対応する位置に}\beta_{\text{active}} \text{の値をセット} \\
\\
&\quad \quad \text{Step 2.5: 残差の更新} \\
&\quad \quad r = y - X \beta \\
\\
&\quad \quad \text{Step 2.6: 新しい相関を計算} \\
&\quad \quad c = X^T r \\
\\
&\text{Step 3: モデルの終了条件の判定} \\
&\quad \text{if } \|\beta\|_0 = p \text{ または } \|r\|_2 = 0 \quad \text{(全ての説明変数がアクティブセットになるか、残差が0になったら終了)}
\end{align*}
\]

LARSの比較表

LARSはLASSOの解を求めるアルゴリズムなので、RidgeやElastic Netと比較した表はこうなる。

解析法	正則化項	変数選択	説明変数間の相関	計算コスト
LARS	L1ノルム（LASSO）など	可能（LASSO）など	有利	低い
LASSO	L1ノルム	可能	不利	高い
Ridge	L2ノルム	不可能	有利	低い
Elastic Net	L1ノルム+L2ノルム	可能	有利	高い

LARSは計算コストを抑えてLASSOと同等の性能を出せるらしく、他と比べると使いどころがありそうです。

もちろん、変数選択や次元削減は問題、データの質に強く依存します。 どの方法も万能ではなく、目的に合わせて試行錯誤が必須なことは、言うまでもないですね。