「AdaBoostは過学習しにくい」——ブースティングを勉強すると必ず出会う話だ。訓練誤差が0になった後もブースティングを続けるとテスト誤差がさらに下がっていく、という有名な実験があり、「弱学習器を何百個も足しているのにモデルは複雑になりすぎない」という一見矛盾した現象は、マージン理論(訓練誤差が0になった後もマージンの分布は改善し続けている)で説明される。Schapireらの1998年の論文のタイトルは “Boosting the margin” で、この現象はブースティングという手法の看板みたいなものだ。

一方で、教科書の隅にはこうも書いてある。「AdaBoostはラベルノイズに弱い」。指数損失が間違えた点のサンプル重みを指数的に増やし続けるので、そもそもラベルが間違っている点があると、そこに延々と執着してしまうらしい。

「過学習しない」と「ノイズに弱い」。この2つは矛盾しているようで、たぶん両立する。ならば自分の手で境目を見てみたい。クリーンなラベルでは本当に過学習しないのか、そしてラベルを何%汚したらその神話は崩れるのか。決定株(深さ1の決定木)のAdaBoostをnumpyで書いて、ラベルノイズ0〜30% × ブースティング回数1〜1,000回の全組み合わせで実測した。対照群にはアンサンブルの多様性の記事でも登場したRandom Forestを同じ条件で走らせる。

実験に使ったコードの全文はGitHubに置いています。

実験設計: 「クリーン」を本当にクリーンにする

データはおなじみtwo moonsだが、今回はひと工夫した。sklearnのmake_moonsはノイズを大きくすると2つの月が重なり、「そもそもどちらのクラスか原理的に決まらない点」が生まれてしまう。それでは「クリーンなラベル」の実験にならないので、点の座標はmake_moons(noise=0.2)で散らしつつ、ラベルは「2本の理想的な月の弧のどちらに近いか」で決定的に付け直した。こうするとラベルは座標の決定的な関数になり、ベイズ誤差は0。つまり「原理的には完璧に分類できる問題」になる。ここにラベルノイズを注入するときは、訓練データのラベルを指定した割合だけランダムに反転する。テストデータ2,000点のラベルは常にクリーンなまま使う(知りたいのは「真の規則にどれだけ近づけたか」なので)。訓練データは300点だ。

AdaBoost本体は決定株をベース学習器とする2クラスの離散AdaBoost(AdaBoost.M1)をnumpyで自作した。決定株は「どの特徴量が閾値を超えたら+1(または-1)」を出すだけの、深さ1の決定木だ。各ラウンドで重み付き誤分類率を最小にする決定株を全探索し、その誤り率 $\epsilon_t$ から係数 $\alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}$ を決め、間違えた点の重みを $e^{\alpha_t}$ 倍、正解した点の重みを $e^{-\alpha_t}$ 倍して正規化する。この「間違えた点の重みを指数的に釣り上げる」更新が今回の主役になる。

for t in range(self.n_rounds):
    j, thr, pol, err = train_stump(X, y, w)  # 重み付き誤差最小の決定株を全探索
    alpha = 0.5 * np.log((1 - err) / err)
    h = stump_predict(X, j, thr, pol)
    w = w * np.exp(-alpha * y * h)  # 間違えた点(y*h=-1)の重みが指数的に増える
    w /= w.sum()

実装の正しさはsklearnのAdaBoostClassifier(SAMME、決定株)と照合した。1ラウンド目の訓練誤差・テスト誤差は完全一致(0.1533 / 0.1715)、200ラウンド時点のテスト予測の一致率は99.6%。途中経過は決定株の選び方のタイブレークで多少ずれるが、収束先はほぼ同じだったので、以降は自作実装で進める。

クリーンなラベルでは、通説はほぼ本当だった

まずノイズ0%。訓練誤差とテスト誤差をブースティング回数1〜1,000で追う(5シード平均)。

訓練誤差は中央値33回(シードにより20〜67回)で0に到達する。注目はその後で、残りの約970回、モデルは「全問正解している訓練データ」に対して弱学習器を足し続けているにもかかわらず、テスト誤差は壊れない。訓練誤差が0になった時点のテスト誤差は平均2.8%、1,000回時点でも3.2%。30倍回してこの程度なら「過学習しない」と呼んでいい振る舞いだと思う。

ただし正直に書くと、有名な実験で強調される「訓練誤差0のあともテスト誤差が下がり続ける」は、今回の設定でははっきりとは見えなかった。シードごとのテスト誤差の最小値は平均2.6%で、訓練誤差0の時点(2.8%)より確かにわずかに低く、最小を付けるラウンドが訓練誤差0より後のシードもあった(例: seed 0は33回で訓練誤差0、47回でテスト誤差最小)。でも動きとしては「下がり続ける」より「張り付いて動かない」が実感に近い。2次元のtwo moonsは弧の形さえ捉えれば終わりの簡単な問題なので、マージン改善の恩恵が誤差の数字に出にくいのだろう。「壊れない」は再現、「下がり続ける」は微妙、というのがクリーン側の結果だ。

ラベルノイズを入れると「回すほど悪化する」に切り替わる

次に訓練ラベルをフリップしていく。ノイズ0/10/20/30%でのテスト誤差カーブがこれだ(5シード平均)。破線は同じノイズのデータで学習したRandom Forest(300本)の水準を示している。

クリーンで見た「張り付いて動かない」水平線は、ノイズを入れた瞬間にU字カーブに変わる。数字で並べるとこうなる(5シード平均)。

• ノイズ0%: 最小2.6% → 1,000回時点3.2%(ほぼ横ばい)
• ノイズ5%: 1,000回時点で6.6%。たった5%の汚染で、クリーンの2倍のテスト誤差になる
• ノイズ10%: 34回付近で最小5.4% → 1,000回で10.7%。回し続けると最小値の2.0倍
• ノイズ20%: 25回付近で最小 → 1,000回で18.0%
• ノイズ30%: 21回付近で最小 → 1,000回で25.2%。コイン投げ(50%)には遠いが、最小値(9〜13%)の2倍以上

「AdaBoostは過学習しない」の神話は、ラベルノイズ5%であっさり崩れた。しかも崩れ方が特徴的で、どのノイズ率でも「最初の20〜40回」は健全に誤差が下がる。壊れるのはその後だ。序盤のAdaBoostと終盤のAdaBoostは、ほとんど別のアルゴリズムのように振る舞う。

決定境界が誤ラベル点に「食いつく」瞬間

何が起きているのかは、決定境界とサンプル重みを一緒に動かすとよく分かる。ノイズ10%のデータでの学習過程をGIFにした。マーカーの大きさがそのままサンプル重み、赤い縁取りが誤ラベル点だ。

ラウンド40あたりまでは、境界は月の形を素直になぞり、テスト誤差も3.8%と最良水準にある。この時点ですでに誤ラベル点(赤縁)のマーカーだけが膨らみ始めているのが分かる。正しい月の形に沿った境界を引く限り、誤ラベル点は必ず「誤分類」され続けるので、指数損失の重み更新則がその点の重みを毎ラウンド釣り上げるのだ。そして重みが十分に大きくなると、決定株にとって「その1点を正しく分類する」ことが重み付き誤差の意味で割に合う仕事になってしまい、境界が誤ラベル点に向かって半島や飛び地を伸ばし始める。1,000回時点の境界は、30個の誤ラベル点を律儀に囲い込んだ迷路になっている。「過学習しない」はずのアルゴリズムが、教科書通りの過学習の絵を描いていく様子は、動かして見るとなかなか壮観だった。

ヒートマップで見る「谷の位置」

ブースティング回数×ノイズ率の全平面でテスト誤差を塗ったのがこれだ(5シード平均)。

事前の予想では、この平面に「回数×ノイズの非単調な縞模様」のような複雑な構造が出るのではと期待していた。実際に出てきたのはもっと素直な地形で、回数方向にはU字(非単調)、ノイズ方向には単調悪化。ただ、面白いのは各行の最小値(白い星)の位置だ。ノイズが0%でも30%でも、最適なブースティング回数は16〜70回の狭い帯に収まっている。ノイズが増えると谷が浅く・早くなるだけで、位置はほぼ動かない。「何回回すべきか」の答えがノイズ率にほとんど依存しないというのは、実務的にはむしろありがたい性質かもしれない。少なくともこのデータでは「迷ったら数十回で止めて検証誤差を見ろ」で済む。

重みは「爆発」ではなく「高止まり」だった

指数損失が誤ラベル点の重みをどう扱ったのか、ノイズ10%の学習過程で誤ラベル30点とクリーン270点の平均重みを追跡した。

データの10%しかない誤ラベル点が、ラウンド1の時点ですでに総重みの17%を握り、60回付近からは総重みの約39%を占め続ける。1点あたりの平均重みはクリーン点の5.7倍。AdaBoostは学習時間の大半を、ラベルが間違っている30点の機嫌を取ることに費やしていたわけだ。

ただここでも、事前のイメージは少し裏切られた。「指数損失が重みを爆発させる」と言うときに私が想像していたのは、重みが発散に向かってどこまでも増え続ける絵だった。実測では重みは60回付近で頭打ちになり、以降は高いところで釣り合う。考えてみれば当然で、重みが上がる→境界がその点に食いつく→その点が正しく分類される→重みが下がる、というネガティブフィードバックがかかるからだ。GIFで境界が誤ラベル点を囲い込んでいたのはまさにこの「重みを下げるための食いつき」で、爆発は起きない代わりに、総重みの4割を人質に取られた定常状態が続く。テスト誤差がU字の右側でじわじわ悪化し続けるのは、この定常状態の中で境界の飛び地が少しずつ増えていくためだった。

対照群Random Forestと、意外な逆転

同じデータ・同じノイズでRandom Forest(300本)を走らせた結果を重ねる。AdaBoostは「1,000回回し切った場合」と「テスト誤差最小のラウンドで止めた場合(オラクル早期停止)」の2通りを載せた。

まず順当な部分。ノイズがある限り、回し切ったAdaBoost(赤)はすべてのノイズ率でRandom Forest(オレンジ)に負ける。ノイズ10%なら10.7%対4.9%でダブルスコアだ。バギングは各木が独立にデータの多数派に従うだけで、誤ラベル点を「重点的に狙う」機構を持たないので、木を増やしても悪化しない。「ノイズがあるならブースティングよりバギング」という教科書のアドバイスはきれいに再現された。

意外だったのはその先だ。ノイズを25〜30%まで上げると、Random Forestも決して無事ではない(30%で誤差22.3%)。深さ無制限の木は個々が誤ラベル点を丸暗記してしまい、ノイズ30%ともなると「その近傍では誤ラベルに投票する木」が多数派を取る領域が出てくるのだろう。一方、早期停止したAdaBoost(青)は30%ノイズでも誤差9.2%で踏みとどまり、5シードすべてでRandom Forestを大差で上回った(seedごとに8〜13% 対 21〜26%)。序盤のAdaBoostは重みがまだ暴れておらず、少数の決定株で大づかみな境界だけを引くので、結果的に強い正則化がかかっているのと同じことになる。「AdaBoostはノイズに弱い」も、止めどきさえ知っていれば絶対ではない——ただしこの青い線は「テスト誤差を見て最良の点で止める」というズルをしているので、その点は次で正直に書く。

正直に書いておくべきこと(限界・スコープ)

• オラクル早期停止はズルである。図5の青い線はテスト誤差最小のラウンドを事後的に選んでおり、実務でそのまま得られる数字ではない。実際は検証データで止めることになり、そのぶん誤差は上振れする。ただ図4で見た通り最適回数は16〜70回の狭い帯に集中しているので、検証データでの停止でも大きくは外さないはずだ
• 実験は2次元のtwo moons 1種類、訓練300点での話だ。低次元・小データはブースティングが誤ラベル点1つ1つに飛び地を作りやすい、いわば神話が壊れやすい設定でもある。高次元・大データで同じ崩れ方をするかは確認していない
• ノイズは一様ランダムなフリップ(対称ノイズ)のみ。境界付近に集中するノイズや、クラス片側だけのノイズでは別の挙動になりうる
• ベース学習器は決定株のみ。深い木をベースにしたAdaBoostや、勾配ブースティング(XGBoost等)の「ノイズ耐性」は指数損失ではなく別の損失の話になるので、今回の結果をそのまま外挿はできない
• Random Forestはsklearnのデフォルト設定(深さ無制限)で300本。max_depthやmin_samples_leafを絞ればRF側のノイズ耐性はさらに上がる余地がある
• クリーン条件で「テスト誤差が下がり続ける」が弱かったのは、問題が簡単すぎてテスト誤差が早期に床に着いたためと思われる。マージン分布そのものは測っていないので、「マージン理論が成り立っていない」という主張はしていない

手を動かして意外だったこと

一番の驚きは、神話が崩れる瞬間の安さだった。クリーンなら1,000回回しても3.2%で微動だにしないのに、ラベルを5%汚しただけで誤差は2倍。ノイズ耐性が「あるかないか」ではなく、0%と5%の間に崖がある。この崖の正体が、図6の「ラウンド1の時点で誤ラベル点がすでに総重みの17%を握っている」という数字に出ていると思う。指数重み更新は誤ラベルを見つけるのが速すぎる。

次に、「重みの爆発」という言い回しを自分が誤解していたこと。重みは発散せず、境界の食いつきとのネガティブフィードバックで高止まりの定常状態に入る。崩壊は一発の爆発ではなく、総重みの4割を人質に取られたまま飛び地が増殖していく慢性疾患だった。二重降下の記事のときも思ったが、「過学習」とひとことで呼ばれる現象の中身は、実際に動かすとそれぞれ全く違う絵をしている。

そして、早期停止したAdaBoostが高ノイズ域でRandom Forestに勝ったこと。これは実験前には全く予想していなかった。「AdaBoost=ノイズに弱い」「RF=ノイズに強い」という教科書の対比は、「回数を固定して比べれば」という条件付きの話で、止めどきを含めてチューニングするなら序盤のAdaBoostは案外タフだ。通説を1つ検証しにいったら、別の通説の但し書きが増えて帰ってきた。

まとめ

• 決定株ベースのAdaBoostをnumpyで自作し(sklearnとテスト予測99.6%一致)、ベイズ誤差0のtwo moons(訓練300点)でラベルノイズ0〜30% × ブースティング1〜1,000回を実測した
• クリーンなラベルでは通説はほぼ本当: 訓練誤差は中央値33回で0になり、その後970回弱学習器を足し続けてもテスト誤差は2.8%→3.2%とほぼ横ばい。ただし「下がり続ける」というより「張り付く」だった
• ノイズ5%で神話は崩れる: 1,000回時点のテスト誤差はクリーンの2倍(6.6%)。ノイズ10%では最小値5.4%→10.7%と、回し続けるだけで誤差が2.0倍になる
• 原因は指数損失の重み更新で、データの10%の誤ラベル点が総重みの39%を占める定常状態に入る(1点あたりクリーン点の5.7倍)。重みは「爆発」ではなく60回付近から「高止まり」し、決定境界が誤ラベル点を1つずつ囲い込んでいく
• テスト誤差が最小になる回数は、ノイズ率によらず16〜70回の狭い帯に集中していた。谷の深さは変わるが位置は動かない
• 回し切ったAdaBoostは全ノイズ率でRandom Forestに負ける(10%ノイズで10.7%対4.9%)。ただしノイズ25〜30%ではRFも崩れ始め(誤差17〜22%)、最良の回数で止めたAdaBoostが5シード全てでRFに大差で勝った(30%ノイズで9.2%対22.3%)。「ブースティングはノイズに弱い」は、止めどき込みで考えると条件付きの真実だった

• 実践記
• 機械学習

関連記事

• 二重降下を実験で再現した。補間閾値でテスト誤差が76.8倍に跳ね上がり、そこから64分の1まで下がったが、シンプルな次数5モデルには最後まで届かなかった
• アンサンブルの「多様性」は本当に効くのか。seed違いの浅い多様性とbagging+幅の多様性を対決させたら不一致率が3.1倍だった
• 敵対的サンプル(FGSM)を自作分類器に実装したら、εを2.5まで上げても反転率は45%で頭打ちだった

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。