10.1-10.4 ブースティングとAdaBoost

なぜ、ランダム予測とほぼ変わらない粗末な分類器が、最先端の複雑なモデルより賢くなれるのか？

その謎が、機械学習の歴史を変えた「ブースティング」の核心にあります。弱い学習器たちの「苦手克服の積み重ね」がいかにして驚異的な精度を生み出すのか、そしてその背後にある美しい数学的構造を一緒に探っていきましょう。

弱い学習器から強い学習器へ

こんな問いから始めてみましょう。

「コイン投げより、ほんの少しだけ賢い予測器を100個集めたら、どうなるだろう？」

これが「ブースティング」の出発点です。

弱い学習器（weak classifier）とは、ランダムな予測（当たる確率50%）よりわずかに良い程度の分類器のことです。たとえば「決定株（decision stump）」——1つの特徴量だけで判断する、こんな単純なルールです：「年収が50万円以上？なら『購入する』、そうでなければ『購入しない』」。

驚くべきことに、そのような弱い学習器でも、繰り返し組み合わせることで、非常に高精度な分類器を作れることが証明されています。

ブースティングの反復学習過程。青い点（クラス+1）と赤い点（クラス-1）の散布図で、各ラウンドごとに誤分類された点が大きくなり（重みが増加）、決定境界が更新されていく — 各ラウンドで誤分類された点（大きく表示）への重みが増加し、次の学習器がそこに特化して学ぶ

そのカラクリは「苦手克服」にあります。最初は全データを均等に扱います。 1回目の学習器が間違えたデータに対して「次回はそこを重点的に攻めよう」と重みを増やします。 2回目の学習器はその重みに従って、前回が苦手だった部分に特化して学習します。

この繰り返しで、「自分の苦手な場所で貢献する専門家たち」の委員会が完成します。そして最終的な答えは、委員全員の加重多数決で決定されます。

最終分類器は弱い学習器の加重多数決投票です：

G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)

ここで $$G_m(x)$$ は第 $$m$$ 番目の弱い学習器（ $$+1$$ または $$-1$$ を返す）、 $\alpha_m$ はその信頼度スコアです。精度が高い学習器ほど大きな $\alpha_m$ を持ち、最終投票での発言権が大きくなります。 $\text{sign}(\cdot)$ は合計がプラスなら $$+1$$ 、マイナスなら $$-1$$ を返す関数です。

AdaBoost.M1アルゴリズム — 具体的にどう動くか

では、この「苦手克服の繰り返し」を具体的にどう実装するのでしょうか？

1997年にFreundとSchapireが提案した AdaBoost（Adaptive Boosting） は、その答えを鮮やかに示しました。

AdaBoostの1イテレーション。左パネル（イテレーション前）では均等サイズの点が散布し決定境界が引かれる。右パネル（イテレーション後）では誤分類された点が大きくなり、新しい境界が更新される — 左: 1イテレーション前（全重み均等） / 右: 1イテレーション後（誤分類点の重みが増加）

アルゴリズムは次のように動きます：

ステップ1: 初期化
全 $$N$$ 個のデータポイントに均等な重みを設定： $$w_i = 1/N$$ 。誰も特別扱いしない公平なスタートです。

ステップ2: $$M$$ 回の繰り返し

(a) 現在の重み $$w_i$$ を使って弱い学習器 $$G_m(x)$$ を学習。重みが大きいデータほど「重要な問題」として扱われます。

(b) この学習器の加重誤差率を計算：

\text{err}_m = \frac{\sum_{i=1}^{N} w_i \cdot I(y_i \neq G_m(x_i))}{\sum_{i=1}^N w_i}

（誤分類したデータの重みの合計 ÷ 全重みの合計）

\alpha_m = \log\frac{1 - \text{err}_m}{\text{err}_m}

(d) 重みを更新：誤分類されたデータの重みを増やし、正解したデータの重みは変えない。

ステップ3: 最終分類器
全学習器の加重多数決で予測します。

$\alpha_m$ の式を見てください。誤差率 $\text{err}_m$ が低い（良い学習器）ほど $\alpha_m$ は大きくなります。誤差率が50%（ランダムと同じ）なら $\alpha_m = 0$ で発言権なし。完璧（誤差率=0）なら $\alpha_m \to \infty$ となります。

重みの更新式は次の通りです：

w_i \leftarrow w_i \cdot \exp\left[\alpha_m \cdot I(y_i \neq G_m(x_i))\right]

指示関数 $I(\cdot)$ は条件が成立すれば $$1$$ 、成立しなければ $$0$$ を返します。誤分類された観測値（ $$I = 1$$ ）は重みが $e^{\alpha_m}$ 倍に増え、正解した観測値（ $$I = 0$$ ）は $$e^0 = 1$$ 倍のまま変わりません。その後、全重みを正規化して合計が $$1$$ になるよう調整します。

百聞は一見にしかず — 数字で実感する

では実際にどれほど効果的なのか、数字で見てみましょう。

スパムメール分類を想像してください。「特定の単語を含むか？」という 1つの条件だけで判断する決定株を使います。こんな単純な分類器の誤差率は45%—— コインを投げるのとほぼ変わりません。

ブースティングの反復回数と誤差率の関係グラフ。横軸が反復回数（0〜400）、縦軸が誤差率（0〜0.5）。赤の点線が単体決定株（45%）、黄の点線が大きな決定木（25%）のベースライン、青い曲線がAdaBoostの誤差（急降下して5%台に到達）、緑の点線が最終水準を示す — AdaBoost（青）は反復を重ねるごとに誤差率が急降下し、単体決定株（赤点線）や大きな決定木（黄点線）を大幅に上回る

しかし！ AdaBoostで400回繰り返すと、誤差率は 5%台 にまで低下します。同じ問題に対して244ノードもある大きな決定木（誤差率約25%）と比べても圧倒的です。

イテレーション数が増えるにつれてテスト誤差が劇的に低下していく曲線は、まるでジェットコースターのように急降下します。しかも、ある時点で訓練誤差がゼロになった後も、テスト誤差は下がり続けるという不思議な現象が起きます。

「なぜ、訓練誤差がゼロなのにまだ改善するのか？」

この謎への答えが、次のセクションで明らかになります。

ブースティングの正体——実は加法モデルだった

ここで視点を変えましょう。AdaBoostのアルゴリズムを外から眺めると、何に見えますか？

実は 加法モデル（additive model） の学習です。

加法モデルとは、シンプルな関数を次々と足し合わせて複雑な関数を表現する方法です：

f(x) = \sum_{m=1}^{M} \beta_m b(x; \gamma_m)

加法モデルの視覚化。1次元グラフ上で黄色・橙・赤などの矩形関数（基底関数）が次々と加わり、青い合計線がリアルタイムに変化してデータのパターンに近づいていく — 個々の弱い関数（各色の矩形）が積み重なって、合計（青い線）がデータの構造を捉えていく

$b(x; \gamma)$ は「基底関数」と呼ばれる部品の関数で、 AdaBoostの場合は弱い分類器 $$G_m(x)$$ がこれに当たります。 $\beta_m$ は各部品の「重み（重要度）」、 $\gamma_m$ は各部品の形を決めるパラメータです（木の場合は分割点など）。

この形は、実は多くの機械学習手法が共通して持つ骨格です：

ニューラルネットワーク：シグモイド関数の和
ウェーブレット変換：位置とスケールを変えた基底関数の和
MARS（9.4章）：ヒンジ関数の和

では、なぜ「訓練誤差がゼロでもテスト誤差が改善し続ける」のか？それは、加法モデルがまだ「より良い近似」を作り続けているからです。分類の正解/不正解という二値の目標ではなく、その背後にある確率的な構造を段階的に学んでいます。

この視点から、次の問いが生まれます：「どうやって加法モデルを効率よく学習するか？」

前向き段階的モデリング — 一度に1つずつ

「加法モデルを学習する」とはどういうことか？

理想を言えば、 $$M$$ 個の基底関数のパラメータ全てを同時に最適化したい。しかし $$M$$ が大きくなると、この最適化は計算量的に爆発します。 $$M = 100$$ の場合、互いに絡み合う100個のパラメータを同時に最適化するのは、現実的に不可能です。

そこで登場するのが 前向き段階的加法モデリング（Forward Stagewise Additive Modeling） です。アイデアはシンプル：「一度に1つの基底関数だけ追加する。過去に追加したものは変えない」。

前向き段階的モデリングの可視化。上パネルではデータ点と現在のモデル曲線（青）が表示され、ステップごとに新しい基底関数（黄色）が加わりモデルが改善する。下パネルでは残差（赤点）がゼロ線に向かって縮小していく — 上: モデルが段階的に改善 / 下: 残差がゼロに近づいていく（残差フィッティングの本質）

具体的には：

$$f_0(x) = 0$$ という「何も予測しないモデル」から始める
ステップ $$m$$ で、既存の $f_{m-1}(x)$ を固定したまま、新しい1個の基底関数とその係数を探す：

(\beta_m, \gamma_m) = \underset{\beta, \gamma}{\arg\min} \sum_{i=1}^{N} L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma))

（「損失を最も小さくする $(\beta, \gamma)$ の組み合わせを探せ」という意味）

モデルを更新： $f_m(x) = f_{m-1}(x) + \beta_m b(x; \gamma_m)$

二乗誤差損失 $$L(y, f) = (y - f)^2$$ の場合、このアルゴリズムが何をしているか、特に綺麗に見えます。ステップ $$m$$ の損失を展開すると：

L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma)) = (r_{im} - \beta b(x_i; \gamma))^2

ここで $r_{im} = y_i - f_{m-1}(x_i)$ は残差（residual）—— 現在のモデルの「予測ミスの量」です。

つまり：現在の残差に最もフィットする基底関数を追加するだけ！前のステップで覚えたことを活かしながら、まだ説明できていない部分を学んでいきます。

AdaBoostの正体 — 指数損失の最小化

ここで驚くべき事実が明らかになります。

Section 2のAdaBoostの重み更新式をもう一度見てください。

w_i \leftarrow w_i \cdot \exp\left[\alpha_m \cdot I(y_i \neq G_m(x_i))\right]

この「 $\exp$ （指数関数）を使った重み更新」は、どこから来たのでしょうか？

答えは損失関数にあります。AdaBoost.M1は、以下の損失関数を使った前向き段階的加法モデリングと、数学的に完全に等価です：

L(y, f(x)) = \exp(-y \cdot f(x))

これを 指数損失（exponential loss） と呼びます。

3つの損失関数の比較グラフ。横軸がマージン（yf(x)）、縦軸が損失値。赤の階段関数が0-1損失、青の曲線が指数損失（マージン負で急上昇）、黄色のU字型が二乗損失。二乗損失はマージンが正の領域でも損失が増加する問題点（黄色の太線部分）があり、左側の誤分類領域は青い楕円でハイライトされている — 3つの損失関数の比較。二乗損失（黄）はマージンが大きくなっても損失が増えてしまう問題がある。指数損失（青）は誤分類領域で急速にペナルティを与える

なぜ等価か確かめましょう。指数損失を使って前向き段階的モデリングを行うと、ステップ $$m$$ の最適化問題は：

(\beta_m, G_m) = \arg\min_{\beta, G} \sum_{i=1}^{N} w_i^{(m)} \exp(-\beta y_i G(x_i))

ここで $w_i^{(m)} = \exp(-y_i f_{m-1}(x_i))$ —— これはSection 2のAdaBoostで各ステップ終了時の重みと全く同じです（ $\alpha_m = 2\beta_m$ という定数倍の違いだけ）。この問題を解くと、自然にAdaBoostの $\alpha_m$ の式と重み更新ルールが導出されます。

指数損失を選ぶ理由は 計算の美しさ にあります。指数関数の性質により、各ステップの最適化が綺麗に分解でき、単純な重み更新ルールが得られます。

指数損失の最小化と $\alpha_m$ の導出：

\beta_m = \frac{1}{2}\log\frac{1 - \text{err}_m}{\text{err}_m}

AdaBoostの $\alpha_m = \log\frac{1 - \text{err}_m}{\text{err}_m} = 2\beta_m$ と一致します。

さらに、指数損失を最小化する関数 $$f^*(x)$$ を求めると：

f^*(x) = \frac{1}{2}\log\frac{\Pr(Y=1|x)}{\Pr(Y=-1|x)}

これは クラスの対数オッズ（log-odds）の半分 です。つまりAdaBoostは、「どちらのクラスに属する確率が高いか」という確率的な情報を推定しているのです。分類の結果（+1か-1か）を出力しながら、その裏では確率構造を学んでいました。

ここまでの旅を振り返ると

弱い学習器の組み合わせ：コイン投げ並みの分類器でも、苦手克服の繰り返しで強力になれる
AdaBoostの仕組み：重みを動的に更新し、難しい例に集中して学ぶ
加法モデルとの等価性：ブースティングは基底関数を積み重ねた加法モデルの学習
前向き段階的モデリング：一度に1つの「差分」を学ぶ効率的な最適化戦略
指数損失の正体：AdaBoostは指数損失を最小化しており、クラス確率の対数オッズを推定している

次の章では、この問いに答えます。損失関数を一般化することで、分類だけでなく回帰にも使える勾配ブースティング（Gradient Boosting）という、現代の機械学習で最も広く使われる手法の1つへと発展します。