部分集合選択 - yuuk1's Digital Garden

# 部分集合選択 ## 定義部分集合選択(subset selection)とは、線形回帰モデルにおいて予測変数の一部だけを残し残りを除外することでモデルを単純化する手法群であり、残された変数には通常の最小二乗法を適用する。動機は2つある: (1) 予測精度――最小二乗推定量は低バイアス・高分散になりがちで、いくつかの係数を0にすることでバイアスと引き換えに分散を下げ全体の予測誤差を改善できる、(2) 解釈性――多数の予測変数から効果の強い小さな部分集合を取り出し「大きな絵」を把握する。**変数を残すか捨てるかという二値判断**が、[[縮小推定]]が持つ連続的な係数の縮小と対照をなす。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.3) ## 主な手法 - **best-subset選択**: 各サイズ $k \in \{0,\dots,p\}$ ごとに残差平方和最小の部分集合を求める。leaps-and-bounds手続き(Furnival and Wilson, 1974)で $p\le30$–40程度まで実行可能。best-subset曲線(サイズごとの最小RSS)は単調減少するため、それ単独ではサイズ $k$ を選べない。 - **forward-stepwise選択**: 切片から出発し、最も適合を改善する変数を逐次追加する貪欲algorithm。QR分解を使った更新で $p \gg N$ でも計算可能。 - **backward-stepwise選択**: 全変数のモデルから出発し、寄与最小(Z得点最小)の変数を逐次削除する。$N>p$ が必要。 - **forward-stagewise回帰(FS)**: forward-stepwiseよりさらに制約が強く、各ステップで残差と最も相関する変数の単純回帰係数を現在の係数へ加算するのみで、他の変数の係数は調整しない。最小二乗解への到達に $p$ を大きく超えるステップを要するが、高次元問題では有利に働くことがある。いずれも「訓練データを使ってモデルの複雑さを1つのパラメータで indexed した系列を作る」という共通の構造を持つ。複雑さパラメータ(部分集合サイズ $k$)の選択は交差検証やAIC基準に委ねる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.3.1–§3.3.3) ## 縮小推定への接続部分集合選択が離散的な過程であるのに対し、[[縮小推定]](ridge・lasso等)は連続的にモデルの複雑さを制御する。両者は「制約付き最小二乗」という共通の枠組みの両端に位置づけられ、$\sum_j|\beta_j|^q$ 罰則(ESL式3.53)において $q=0$ が部分集合選択(非零パラメータ数を数える罰則)に対応する。forward-stepwise選択と[[縮小推定]]を橋渡しする具体的アルゴリズムが[[最小角回帰]](LAR)である。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.4.3, §3.4.4) ## 横断的知見 - **「変数を残すか捨てるか」の二値選択は、基底展開の文脈では「基底関数を残すか捨てるか」として再現される**: 第5章は基底展開の複雑さ制御をrestriction・selection・regularizationの3方式に分類し(→[[基底展開]])、そのうちselectionは本ページの部分集合選択技法をそのまま流用できるとする。具体的には、第5章§5.2.2の南アフリカ心疾患データの例で、4個の自然スプライン基底を1つの項として扱いbackward stepwise削除(AIC基準)を行っており、これは第3章のbackward-stepwise選択を「変数」から「項(基底関数群)」へ一般化しただけの手続きである。また回帰スプライン(regression spline)の射影行列 $H_\xi$(冪等、固有値が1かゼロのみ)は、部分集合選択が係数を残すか完全にゼロにするかの二値選択であることの関数版であり、[[平滑化スプライン]]の連続的な縮小(shrinking smoother)との対比が、本ページが述べる部分集合選択対[[縮小推定]]の対比とちょうど並行する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 5 Basis Expansions and Regularization]] §5.1, §5.2.2, §5.4.1) - **$p\gg N$では部分集合選択の前提そのものが崩れ、縮小推定側の手法が事実上の選択を代行する**: 本ページのbackward-stepwise選択は「$N>p$が必要」と明記したが、第18章§18.3.4はこれを具体的な失敗例で裏づける。Ramaswamy et al. (2001)の癌分類データ(144訓練例・16,063遺伝子)にrecursive feature elimination(小さい係数の変数を後ろ向きに削っていく手法)を適用すると、遺伝子数を減らすほど精度が悪化するという著者らも説明できない挙動が観察された。一方、同じ$p\gg N$設定でlasso(L1縮小推定)を使うと、convex dualityにより非零係数数が凸最適化の帰結として自動的に高々$N$個に抑えられ(§18.4)、意図的な離散選択の手続きを経ずに部分集合選択と同じ効果(特徴量の大半を0にする)が得られる。すなわち高次元では、部分集合選択に固有の逐次削除アルゴリズムが不安定化する一方、[[縮小推定]]のL1罰則がその代替として選択の役割を安定的に引き受けるという分業が生じる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.3.2, [[@2009__Springer__The Elements of Statistical Learning - Chapter 18 High-Dimensional Problems - p >> N]] §18.3.4, §18.4) - **forward-stagewise回帰が高次元で有利に働く理由は、ESL第16章が木の辞書へ一般化することで明らかになる**: 本ページの未解決の問いは、forward-stagewise回帰(FS、変数追加後に他の係数を調整しない制約の強い逐次法)が「ゆっくり適合すること」でなぜ高次元問題に有利かを、ブースティングとの関係でどこまで一般化できるかを問うていた。第16章§16.2.1のAlgorithm 16.1(前向き段階的線形回帰)は、まさにこのforward-stagewise回帰を「変数」から「木を基底とする巨大な辞書」へ一般化した手続きであり、各反復で残差に最もよく適合する基底を選び係数を微小量 $\varepsilon$ だけ更新する。この一般化された手続きが、木の辞書上でのlasso正則化パス(縮小推定のL1罰則)を近似することが示され、ゆっくり適合すること($\varepsilon\to0$)がlassoのより滑らかでスパースな解パスに近づく機構として説明される。すなわちforward-stagewise選択が高次元で有利になる理由は、部分集合選択(離散的な変数選択)としての性質ではなく、[[縮小推定]]のL1正則化パスを極めて小さいステップで辿ることによる連続近似としての性質に起因する。ブースティングの縮小(shrinkage、学習率)は、この一般化されたforward-stagewise回帰のステップ幅 $\varepsilon$ に対応する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] §3.3.3, [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]] §16.2.1) - **無向グラフィカルモデルの「グラフ構造の推定」は、対象が変数集合から辺集合へ移った部分集合選択の一種であり、本ページが確立した「離散選択(部分集合選択) vs 連続緩和([[縮小推定]])」という対比がここでも再現される**: 第17章§17.3.2は、精度行列$\Theta$のどの非対角成分が非零か(=どの辺が存在するか)を決めるグラフ構造推定の問題を扱う。Meinshausen and Bühlmann (2006)のneighborhood selectionは、各変数を目的変数・残りを説明変数とするnode-wiseな回帰を全変数に対し行い、非零係数の有無から辺を判定する手続きであり、これは本ページのforward-stepwise選択などの「変数を残すか捨てるか」という二値判断を、辺という別の対象へそのまま適用したものとみなせる。ただし第17章が採用する主要な手法はneighborhood selectionではなくgraphical lasso(精度行列へのL1罰則、[[縮小推定]]参照)であり、ここでも本ページが§18.3.4で確立した知見――「$p\gg N$設定では離散的な逐次選択(部分集合選択・backward stepwise)より、L1罰則付き縮小推定(lasso・graphical lasso)の方が構造推定において安定した代替になる」という分業――が、変数選択からグラフの辺選択という文脈に拡張された形で成立する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]] §17.3.2) ## 未解決の問い - best-subset・forward-stepwise・backward-stepwiseの性能は「多くの場合非常によく似る」とESL Ch.3 §3.3.2は述べるが、どのようなデータ特性(相関構造・信号対雑音比)がこの類似を崩すか。第18章のrecursive feature eliminationの失敗例(§18.3.4)は類似が崩れる一事例だが、著者ら自身「説明を持たない」としており、原因は未解明のまま残る。 - 部分集合選択の有効自由度には閉形式がなく、シミュレーションで直接推定するしかない(ESL Ch.3 §3.4.4)。これはモデル選択基準(AIC/BIC)の適用にどう影響するか。[[平滑化スプライン]]の有効自由度 $\mathrm{df}_\lambda=\mathrm{trace}(S_\lambda)$ は閉形式を持つ(第5章§5.4.1)が、この差はprojection smoother(部分集合選択・regression spline)とshrinking smoother(縮小推定・平滑化スプライン)という性質の違いに由来するのか。 ## 関連 - 概念: [[縮小推定]] / [[最小角回帰]] / [[統計的機械学習]] / [[基底展開]] / [[平滑化スプライン]] / [[アンサンブル学習]](forward-stagewise回帰の木辞書への一般化) / [[無向グラフィカルモデル]](グラフ構造推定=辺の部分集合選択) - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 3 Linear Methods for Regression]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 5 Basis Expansions and Regularization]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]](forward-stagewise回帰の一般化) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 17 Undirected Graphical Models]](グラフ構造推定=辺の部分集合選択、neighborhood selection) / [[@2009__Springer__The Elements of Statistical Learning - Chapter 18 High-Dimensional Problems - p >> N]](p≫Nでの選択手続きの不安定性) ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 3, §3.3; Chapter 5, §5.1-§5.2; Chapter 16, §16.2.1; Chapter 17, §17.3.2; Chapter 18, §18.3.4.