# 最小角回帰 ## 定義 最小角回帰(Least Angle Regression, LAR)は、Efron et al. (2004)が提案した回帰アルゴリズムで、[[部分集合選択]]の**forward-stepwise選択の「民主的」な一般化**として位置づけられる。forward-stepwiseが各ステップで選んだ変数を完全に最小二乗フィットさせるのに対し、LARは変数を「それが値するだけ」連続的に取り入れる: 最初に応答と最も相関する変数を見つけ、その係数を最小二乗値へ向けて連続的に動かし(残差との相関が単調に減少)、別の変数が相関で追いつくとその変数も活性集合に加えて係数を共同で動かす。この操作を全変数が活性集合に入るまで繰り返す(Algorithm 3.2)。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.4.4) ## lassoパスとの関係 LARに1行の修正(Algorithm 3.2a: 非零係数が0を通過したら、その変数を活性集合から除外して共同最小二乗方向を再計算する)を加えると、**lassoパス全体を単一の最小二乗フィットと同程度の計算量で計算できる**。両者の解パスは、係数が符号を跨いで0を通過するまでは完全に一致し、そこで初めて分岐する。この一致は、LARの停留条件(3.56)とlassoのKKT停留条件(3.58)を比較すると、活性変数の係数の符号が内積の符号と一致する限り両者が同一の条件を満たすことから導かれる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.4.4) もう1つの修正(Algorithm 3.2b)は、非負最小二乗フィットに制約することで**infinitesimal forward stagewise回帰(FS$_0$)**を実装する。LAR・lasso・FS$_0$の3つは、係数プロファイルが単調であれば完全に一致し、単調でなくとも0を跨がなければLARとlassoは一致する。FS$_0$はlassoよりもさらに制約が強く(L1弧長あたりの残差減少を最適化するlassoに対し、FS$_0$はL1弧長そのものを最小化する微分方程式の解であり方向転換が抑制される)、$p \gg N$ の状況で滑らかな係数パスを生みやすい。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.4.4, §3.8.1) ## 自由度の公式 一般の適応的モデルの有効自由度は $\mathrm{df}(\hat y) = \sigma^{-2}\sum_i \mathrm{Cov}(\hat y_i, y_i)$(ESL式3.60)で定義される。best-subset選択にはこの量の閉形式がなくシミュレーションでしか推定できないのに対し、**LARの $k$ ステップ目終了時点の有効自由度はちょうど $k$ に等しい**ことが示せる。lassoでは変数が脱落しうるため定義がやや近似的になるが、各時点の有効自由度はおおむねその時点の非零パラメータ数に一致する。この「扱いやすさ」こそが、LAR・lassoが部分集合選択よりも理論的解析に適する理由の一つである。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.4.4) ## 横断的知見 - (今後の ingest で複数ソースの突き合わせが蓄積され次第、ここに追記する。現時点では ESL 第3章単独の知見のみのため空とする。) ## 未解決の問い - LAR・lasso・FS$_0$がほぼ同一の経路をたどるという経験的観察(ESL Ch.3 図3.16)は、どのような条件下で崩れるか。予測変数間の相関構造との関係は。 - LARの効率性(単一の最小二乗フィットと同程度の計算量)は、[[縮小推定]]で扱う一般の $L_q$罰則やelastic-netにどこまで拡張できるか(§3.8.2の区分線形パス条件との関係)。 - Dantzig selector(§3.8.3)はLAR/lassoと類似の停留条件を持ちながら活性集合の選び方が異なり、erratic(不規則)な係数パスを生むことがある(Efron et al., 2007)。この不安定性の根本原因は何か。 ## 関連 - 概念: [[部分集合選択]] / [[縮小推定]] / [[統計的機械学習]] - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 3, §3.4.4. - Efron, B., Hastie, T., Johnstone, I., Tibshirani, R. (2004). Least Angle Regression. *Annals of Statistics*.