3.4.4 最小角回帰（Least Angle Regression）
Lassoを一瞬で解く方法
前の章で学んだLasso。強力な手法ですが、1つ問題がありました。
「最適なλ（ペナルティの強さ）をどう選ぶか？」
普通は、いろんなλの値を試して、交差検証（データを分割して検証する方法）で比較します。 λを100通り試すなら、100回最適化問題を解く必要がある。これは時間がかかります。
ところが、ある巧妙なアルゴリズムを使えば、すべてのλに対する解を、たった1回の計算で求められるのです。
そのアルゴリズムが「最小角回帰」（Least Angle Regression、略してLAR）。
今回は、LARのアイデアを見ていきましょう。 変数選択の本質に迫る、美しい構造が見えてきます。
変数選択のジレンマ
まず、変数選択の問題を別の角度から考えてみましょう。
Lasso以外にも、変数を選ぶ方法はあります。 最もシンプルなのが「Forward Stepwise Selection」。1つずつ変数を追加していく方法です。
- 最も予測に役立つ変数を1つ選ぶ
- 次に役立つ変数を1つ追加する
- これを繰り返す
シンプルで直感的。でも、問題があります。
「最も役立つ変数を1つ選ぶ」というのは、極端な決定です。 2番目に良い変数は完全に無視される。 そして、一度選ばれた変数の係数は、ステップごとに最小二乗法解に一気にジャンプします。
これは「貪欲すぎる」のでは？
もし、複数の変数を「少しずつ」追加できたらどうでしょう？
ここに、LARのアイデアがあります。
LARの基本アイデア - 「公平に」変数を追加
最小角回帰（LAR）は、Forward Stepwiseを「民主化」したアルゴリズムです。
どういう意味でしょうか？
LARでは、1つの変数を完全に追加する代わりに、複数の変数を「少しずつ」追加します。
アルゴリズムを直感的に説明しましょう。
まず「残差」という言葉を確認しておきます。 残差とは、現在のモデルでは説明しきれない部分、つまり「予測値と実際の値のズレ」のことです。 この残差を減らすことが、モデルを良くするということ。
ステップ1: 残差と最も相関が高い（残差を最も減らせそうな）変数を見つける
ステップ2: その変数の係数を、残差との相関が他の変数と「同率」になるまで増やす
ステップ3: 2つの変数を「同時に」、両方との相関が同率のまま減少するように係数を増やす
ステップ4: 3つ目の変数が追いつくまで続け、追いついたら3つ同時に...
このプロセスを、すべての変数がモデルに入るまで繰り返します。
重要なのは、「追いついた」変数は完全に無視されず、すぐにモデルに参加できることです。 これが「民主的」という意味です。
なぜ「最小角」なのか
アルゴリズムの名前「Least Angle」（最小角）は、どこから来ているのでしょうか？
LARの各ステップで、係数が進む方向を考えてみましょう。
ここで「アクティブな変数」という用語を使います。 アクティブな変数とは、現在モデルに参加していて、係数が変化し続けている変数のことです。
2つの変数がアクティブ（残差との相関が最大で同率）のとき、 係数の更新方向は、この2つの変数の方向と「等しい角度」を成す方向です。
つまり、どちらの変数にも「公平に」近い方向。 これが「最小角」の意味です。
幾何学的には、アクティブな変数たちの方向を平均化した方向に進みます。
この式は複雑に見えますが、意味は単純です。
- $X_{A_k}$：現在アクティブな変数の行列
- $(X_{A_k}^T X_{A_k})^{-1}$：これらの変数間の相関を考慮した逆行列
- $\mathbf{1}$：すべて1のベクトル（各変数に等しい重みをかける）
結果として得られる方向は、アクティブなすべての変数と等しい角度を成します。
3つ以上の変数がアクティブな場合も同様です。 すべてのアクティブな変数と等しい角度を成す方向に進みます。
LARとLassoの驚くべき関係
ここで驚くべき発見があります。
LARとLassoは、ほとんど同じなのです。
実際、LARにたった1つの修正を加えるだけで、完全なLassoの係数パスが得られます。
その修正とは：
「係数がゼロを通過しようとしたら、その変数をアクティブセットから外す」
これだけです。
LARでは、一度アクティブになった変数は最後まで残ります。 しかしLassoでは、ペナルティの効果で係数がゼロに戻ることがあります。
LARをLassoに変換するには、係数がゼロになった瞬間にその変数を「非活性化」するだけ。
この発見（Efron et al., 2004）により、Lassoの完全な係数パスを、 通常の最小二乗法1回分とほぼ同じ計算量で求められるようになりました。
係数パスの区分線形性
LARとLassoには、もう1つ重要な性質があります。
係数パスが「区分線形」（piecewise linear）なのです。
どういう意味でしょうか？
正則化パラメータλを変化させたとき、係数の軌跡を見てみましょう。 この軌跡は、直線を折れ線でつないだ形になっています。
なぜこれが重要？
区分線形であれば、「折れ点」（kink）の位置だけを計算すればよいのです。 折れ点と折れ点の間は、単純な直線補間で求められます。
これがLARの計算効率の秘密です。
従来、Lassoの解を求めるには様々なλの値で最適化問題を解く必要がありました。 LARを使えば、折れ点だけを順番に計算することで、すべてのλに対する解が一度に得られます。
- $\hat{\beta}_{k-1}$：ステップk-1終了時点の係数
- $\delta_k$：ステップk内での係数変化の方向
- $s$：ステップ内での進行度合い
各ステップ内では、係数は一定の方向$\delta_k$に沿って線形に変化します。 ステップの境界（折れ点）でのみ方向が変わります。
計算効率の革命
ここまでの説明で、LARの美しい構造が見えてきました。 でも、実用上最も重要なのは計算効率です。
従来、Lassoの解を求めるには「座標降下法」などを使っていました。 座標降下法とは、変数を1つずつ順番に最適化していく方法です。
この方法で問題なのは、λ（ペナルティの強さ）の各値ごとに最適化が必要なこと。
100通りのλを試したければ、100回の最適化。 1000通りなら1000回。
ところがLARなら、完全な係数パス（すべてのλに対する解）が一度に得られます。
なぜでしょう？
答えは「区分線形性」にあります。 係数パスは折れ線で、折れ点は有限個しかありません。 折れ点の位置さえ分かれば、その間は単純な直線補間で求められる。
結果として、計算量は：
- 最小二乗法：O(p²n) または O(p³)
- LAR（完全パス）：O(p²n) または O(p³)
ほぼ同じなのです。
λの最適値を交差検証で探すとき、この効率性は決定的。 全てのλに対する解が一度に得られるので、検証が劇的に高速化します。
まとめ
この章で学んだことを振り返りましょう。
変数選択のジレンマから出発
- Forward Stepwiseは「貪欲すぎる」
- 変数を「少しずつ」追加するアイデア
最小角回帰（LAR）の本質
- アクティブな変数と等しい角度を成す方向に進む
- これが「公平に」変数を追加するということ
LARとLassoの驚くべき関係
- LARにたった1つの修正（ゼロでの停止）を加えるとLasso
- 2つの手法は双子のように近い
区分線形性と計算効率
- 係数パスは折れ線（区分線形）
- 折れ点だけ計算すれば、全てのλに対する解が得られる
- 計算量は最小二乗法と同程度
LARは単なる「計算の効率化」ではありません。
Forward Stepwise、LAR、Lasso。 一見バラバラに見えるこれらの手法が、実は深いところでつながっている。 「貪欲に選ぶ」か「公平に選ぶ」か、その連続的なスペクトルの上に、すべてが並んでいる。
この構造的な理解こそが、LARがもたらした最大の洞察なのです。