## 定義 ブートストラップ(bootstrap, Efron 1979)は、統計量$S(Z)$の統計的精度(分散・バイアス等)を評価するための汎用的な標本再利用手法である。訓練データ$Z=(z_1,\ldots,z_N)$から重複を許して同サイズ$N$の標本を$B$回(例: $B=100$)復元抽出してブートストラップ標本$Z^{*1},\ldots,Z^{*B}$を作り、各標本で$S(Z^{*b})$を計算する。これらの値から$S(Z)$の分散を $\widehat{\text{Var}}[S(Z)] = \frac{1}{B-1}\sum_{b=1}^{B}\left(S(Z^{*b})-\bar S^*\right)^2$ のようにモンテカルロ推定できる。これは、データの経験分布関数$\hat F$からの標本抽出によるMonte-Carlo近似とみなせる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11, 式7.53) ## 予測誤差推定への応用と過学習バイアス ブートストラップ標本上でモデルを当てはめ、元の訓練集合での予測誤差$\widehat{\text{Err}}_{boot}=\frac{1}{B}\frac{1}{N}\sum_b\sum_i L(y_i,\hat f^{*b}(x_i))$を計算する素朴な方法は、ブートストラップ標本と元の訓練集合に重複があるため過学習した予測を不当に良く見せ、良い誤差推定を与えない。ある観測$i$が特定のブートストラップ標本$b$に含まれない確率は $\Pr(i \in \text{sample } b) = 1-(1-1/N)^N \approx 1-e^{-1} = 0.632$ であり、1最近傍分類(目的変数と説明変数が無関係、真の誤差率0.5)の例では$\widehat{\text{Err}}_{boot}$の期待値は約$0.5\times0.368=0.184$と大きく過小評価される。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11, 式7.54-7.55) ## leave-one-out bootstrapと`.632`推定量 観測$i$を含まないブートストラップ標本のみで$i$を予測する**leave-one-out bootstrap**推定量$\widehat{\text{Err}}^{(1)}$は過学習の問題を解消するが、各ブートストラップ標本に含まれる相異なる観測の平均個数が約$0.632N$にとどまるため、2分割交差検証に似た(訓練集合サイズ縮小に由来する)上方バイアスを持つ。このバイアスを緩和するのが $\widehat{\text{Err}}^{(.632)} = 0.368\cdot\text{err} + 0.632\cdot\widehat{\text{Err}}^{(1)}$ である。`.632`推定量は「軽い当てはめ」の状況ではうまく機能するが、過学習が強い状況(1最近傍法など)では破綻しうる。例えば目的変数と入力が無関係な1最近傍分類では$\text{err}=0$、$\widehat{\text{Err}}^{(1)}=0.5$より$\widehat{\text{Err}}^{(.632)}=0.316$となり、真の誤差率0.5から大きく外れる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11, 式7.56-7.57) ## `.632+`推定量 過学習の度合いを明示的に取り込むため、無情報誤差率(目的変数と説明変数が無関係だった場合の誤差率)$\hat\gamma=\frac{1}{N^2}\sum_i\sum_{i'}L(y_i,\hat f(x_{i'}))$と、相対過学習率 $\hat R = \frac{\widehat{\text{Err}}^{(1)}-\text{err}}{\hat\gamma-\text{err}}$ を定義する($\hat R=0$は過学習なし、$\hat R=1$は過学習が無情報値に達した状態)。重み$\hat w=0.632/(1-0.368\hat R)$を使って $\widehat{\text{Err}}^{(.632+)} = (1-\hat w)\cdot\text{err} + \hat w\cdot\widehat{\text{Err}}^{(1)}$ とする。$\hat w$は$\hat R=0$で0.632(`.632`推定量に一致)、$\hat R=1$で1(leave-one-out bootstrapに一致)の範囲をとる。1最近傍(目的変数と入力が無関係)の例では$\hat w=\hat R=1$となり正しい期待値0.5を回復する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11, 式7.58-7.61) ## 実測されたバイアスの比較 4種類のシミュレーション設定(k-NN/線形モデル × 回帰/分類)で、10分割交差検証と`.632+`ブートストラップは、最良モデルに対する相対誤差の分布がAICとほぼ同等(やや劣る程度)に良好だった。さらに、AIC・BICが最終モデルの予測誤差を平均30〜51%過大評価したのに対し、交差検証・ブートストラップは0〜4%程度とほぼ不偏だった。一方、木構造のような適応的手法では、探索(木構造の選択)自体が検証セットに強く影響されるため、交差検証・ブートストラップのいずれも真の誤差を約10%過小評価しうる。この場合は独立したテストセットのみが不偏な推定を与える。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11.1) ## 横断的知見 - **ノンパラメトリックブートストラップは実質的にノンパラメトリック最尤推定の計算装置であり、パラメトリックブートストラップは正規誤差モデルの下で最小二乗推定(および最尤推定)と一致する**。第7章では`.632+`推定量のように予測誤差の分散評価にブートストラップを使ったが、第8章はその同じ「重複を許す復元抽出」の手続きを、公式が存在しない設定(適応的な結節点選択を伴う平滑化等)での最尤推定の標準誤差計算装置として再解釈する。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] §7.11, [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.2.1-§8.2.3) - **無情報事前分布(事前分散→∞)の下で、ブートストラップ分布はパラメータの近似的な事後分布(ベイズ推定)と一致する**。ガウスモデルでは、対数尤度が最尤推定$\hat\theta$のみを通じてデータに依存し、かつ$\theta$と$\hat\theta$について対称という2条件のもとで厳密に成り立つ。多項分布のノンパラメトリックな場合にも、対称ディリクレ事前分布の無情報極限とブートストラップによる標本比率の分布が支持・平均・共分散をほぼ共有することから近似的に拡張される。ゆえにノンパラメトリックブートストラップ分布は「貧者のベイズ事後分布」とみなせる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.4) - **バギング([[アンサンブル学習]])は、ブートストラップ=ベイズ事後近似という関係をモデル改善に転用したものである**: バギング推定値$\hat f_{bag}(x)$はブートストラップ標本上の予測の平均であり、近似的な事後平均とみなせる。一方、元の訓練標本上の推定値$\hat f(x)$は事後分布の最頻値(モード)に相当する。二乗誤差損失を最小化するのはモードではなく平均であるため、バギングが平均二乗誤差をしばしば改善する理由をベイズ的に説明できる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] §8.7-§8.8) ## 未解決の問い - ブートストラップとバギング([[アンサンブル学習]])・ランダムフォレストのOOB(out-of-bag)誤差推定は同じ「重複を許す復元抽出」を土台とするが、後者は誤差推定と同時にモデル平均化(予測性能の向上)も狙う点で目的が異なる。第8章はバギング(モデル平均化)側の理論的根拠(二乗誤差損失下での分散削減、式8.52)を明確にしたが、OOB誤差推定とバギング予測を同一のブートストラップ標本群からどう同時に得るかという実装上の関係は、第15章(ランダムフォレスト)の取り込み時に明確化する。 - `.632+`推定量の重み$\hat w$は無情報誤差率$\hat\gamma$の推定に依存するが、多クラス分類や連続値予測など、章本文で扱われなかった損失関数に対する$\hat\gamma$の一般化はどう定式化されるか。 - ノンパラメトリックブートストラップに対しパラメトリックブートストラップが予測誤差推定で優位になる場面: 第8章の平滑化例題では、パラメトリックブートストラップは(誤差の正規性という仮定が正しければ)最尤推定と厳密に一致する信頼帯を与えることが示された(§8.2.1)。この意味では、モデルの分布族の仮定が妥当な場面ではパラメトリックブートストラップの方が理論的に裏付けられた推定を与えるが、分布族の仮定が誤っている場合の頑健性の比較は本章の範囲外である。 ## 関連 - source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 7 Model Assessment and Selection]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 8 Model Inference and Averaging]] - concept: [[交差検証]] / [[バイアス-バリアンストレードオフ]] / [[ベイズ推定]] / [[アンサンブル学習]] / [[EMアルゴリズム]] ## 出典 - Hastie, T., Tibshirani, R., Friedman, J., *The Elements of Statistical Learning*, 2nd Edition, Springer, 2009, Chapter 7, §7.11; Chapter 8, §8.2-§8.4.