アンサンブル学習

アンサンブル学習#

アンサンブル学習（ensemble learning） は複数のモデル（学習器）を組み合わせて予測精度を向上させる手法の総称。

Bagging#

Bootstrap AGGregatINGの略で、bootstrapによって複数のモデルを学習させ、予測結果をaggregating（例えば平均や多数決）する方法。

決定木のBaggingであるRandom Forestが有名。

Boosting#

ブースティング（boosting）はKearns (1988)の「（0.5よりわずかに正解率が高い程度の）弱い学習器を使って強い学習器を作ることはできるか？」という仮説（boosting hypothethis）から生まれた

The strength of weak learnability#

初期のBoostingの研究では、現代のものとはやや異なるアプローチをとっていた

Schapire (1990) The strength of weak learnability. は以下の方法を提案

  1. 分類器\(h_1\)を\(N\)個のサンプルで訓練する

  2. \(h_1\)で分類に失敗したサンプルと正しく分類できたサンプルを半々にした\(N\)個のサンプルで\(h_2\)を訓練する

  3. \(h_1\)と\(h_2\)で分類結果が一致しない\(N\)個で\(h_3\)を訓練する

  4. ブーストされた分類器\(h_B\)は\(h_1, h_2, h_3\)の分類結果の多数決で分類を行う

AdaBoost#

Freund & Schapire (1997) により AdaBoost というアルゴリズムが提案され、性能の高さから広く普及した。

アルゴリズム（AdaBoost）

訓練データ：\((x_1, y_1),\dots,(x_m,y_m)\) ここで \(x_i \in \mathcal{X}, y_i \in \{-1, +1\}\)

初期化：\(i=1,\dots,m\)について分布（重み）を\(D_1(i) = 1/m\)とする。

\(t=1,\dots,T\) について、

  • 弱学習器を分布\(D_t\)で訓練し、仮説\(h_t: \mathcal{X} \to \{-1, +1\}\)を得る。

  • 目的：重み付き誤差\(\varepsilon_t = P_{i\sim D_t}[h_t(x_i)\neq y_i]\)が低い\(h_t\)を選ぶこと

  • 仮説の信頼度 \(\alpha_t = \frac{1}{2} \ln \left( \frac{1-\varepsilon_t} {\varepsilon_t} \right)\) を定める

  • \(i = 1,\dots,m\)について分布（重み）を更新する

    • \(\displaystyle D_{t+1}(i) = \frac{D_t(i) \exp(-\alpha_t y_i h_t(x_i) )}{ Z_t }\)

    • ここで\(Z_t\)は\(D\)を分布とするための正規化係数（normalization factor）

出力：

最終的な仮説（判別器）は

\[ H(x) = \text{sign} \left(\sum_{t=1}^T \alpha_t h_t(x)\right) \]

なお対数誤差を最小化する予測確率は対数オッズに等しい。

\[ f^*(x) = \arg \min _{f(x)} \mathrm{E}_{Y \mid x}\left(e^{-Y f(x)}\right) =\frac{1}{2} \log \frac{\operatorname{Pr}(Y=1 \mid x)}{\operatorname{Pr}(Y=-1 \mid x)} \]

あるいは等しい別の表現として

\[ \operatorname{Pr}(Y=1 \mid x)=\frac{1}{1+e^{-2 f^*(x)}} \]

となる。

参考

Gradient Boosting Machine#

Friedman, J. H. (2001) はAdaBoostを一般化して勾配ブースティング（gradient boosting）というアルゴリズムに整理した。

勾配ブースティングは誤差の勾配に対して適応的に学習する手法。例えば二乗誤差なら勾配は残差のことなので、\(k\geq 0\)個のモデルを学習した時点\(\sum_{i=0}^k f_i(x)\)の予測の残差が大きいものに対して新たに\(f_{k+1}(x)\)を学習させて追加したモデル\(\sum_{i=0}^{k+1} f_i(x)\)を新たなモデルとする、といった学習を何らかの基準（上限の回数や誤差の基準）を満たすまで繰り返す。

AdaBoostは誤差関数を指数誤差\(\ell(m)=e^{-m}\)にした勾配ブースティングであることが示されている。

勾配ブースティングは決定木と相性が良く、勾配ブースティング決定木（gradient boosted decsision tree: GBDT）として非常に広く使われている。計算量を抑えて学習を高速化する工夫が取られたモダンなGBDTにはXGBoostやLightGBMなどがあり、2024年現在でもテーブルデータの予測においてSOTAと評価されている。

参考

Stacking#

stacking （元の論文では stacked generalization ）は、複数のモデルの予測値を入力（特徴量）として扱い、また別のモデルを使って予測値を構築する、階層的なモデルを構築するアプローチ。

Kaggleでは昔からよく使われ、例えばGBDTベースのモデルを数十個、NNベースのモデルを数十個つくってstackingしまくって精度を上げる、みたいなことをする。

実務では使われているケースを見ない

Contents