8.9 Bumping — 確率的探索で局所最適から脱出する

最適化アルゴリズムの「死角」

機械学習のモデルを学習するとは、突き詰めれば「最良の関数を探す」ことです。 決定木なら最適な分割を、ニューラルネットなら最適な重みを探します。

ですが、ここに大きな落とし穴があります。

多くのアルゴリズムは、目の前で一番良くなる選択を積み重ねる「貪欲法（greedy algorithm）」を使っています。 これは速く動きますが、全体としての最適解にたどり着けないことがあるのです。

たとえば、登山に例えてみましょう。霧の中で「いま立っている場所から一番高い方向へ進む」 というルールで山を登ると、近くの小さな丘の頂上にたどり着いて、そこで満足してしまいます。 本当の最高峰は、いったん谷を降りた先にあるのに。

これを 局所最適（local optimum） に陥る、と呼びます。

そして実は、機械学習のアルゴリズムが特に苦手とする「意地悪なデータ配置」が いくつか知られています。後の Section 6 で具体例を見ますが、それらの配置では、貪欲アルゴリズムが 最初の一刀で諦めてしまい、本来見抜けるはずの構造を見逃してしまうのです。

この章で考えたい問い: データを少しだけ揺らしてみれば、貪欲アルゴリズムの 「死角」を覆せるのでしょうか？

「平均する」と「選ぶ」の違い

Bumping を理解する前に、すでに学んだ Bagging との対比で 位置づけておきましょう。

どちらも出発点は同じです。元の訓練データから、ブートストラップサンプル（重複ありで抜き取った擬似データセット）を何度も作り、 それぞれでモデルを学習します。すると B 個のモデル $\hat{f}^{*1}, \hat{f}^{*2}, \ldots, \hat{f}^{*B}$ が手に入る。

ここからの扱いが、Bagging と Bumping ではっきり分かれます。

• Bagging: B 個の予測を 平均する。 複数の予測のブレが打ち消し合って、最終予測の「ふらつき（分散）」が下がる。
• Bumping: B 個の中から 一番良いものをひとつ選ぶ。 残りは捨てる。

「捨てる」と聞くと、もったいない印象を受けるかもしれません。実際、Bagging のような 分散削減効果は Bumping にはありません。

ですが、Bumping が狙うのは別のものです。それは 「探索」 です。

複数のブートストラップを試すことで、モデル空間のいろいろな場所を見て回り、 貪欲法では届かなかった良いモデルを偶然見つけることを目指します。データを揺らすことが、 最適化アルゴリズムを「別の地形」に連れて行ってくれるのです。

ポイント: Bagging は「平均化で安定化」、Bumping は「ランダム探索で良い解を発見」。

Bumping のアルゴリズム

具体的な手順を見ていきましょう。Bumping は驚くほどシンプルです。

1. 元の訓練データから、ブートストラップサンプル $Z^{*1}, Z^{*2}, \ldots, Z^{*B}$ を作る
2. それぞれに同じ学習アルゴリズムを適用し、モデル $\hat{f}^{*1}, \hat{f}^{*2}, \ldots, \hat{f}^{*B}$ を得る
3. 各モデルを 元の訓練データ全体 で評価する
4. 訓練誤差が最も小さいモデルを選ぶ

ここで一番のポイントは、評価は必ず「元の訓練データ」で行うということです。

各モデルはそれぞれ異なるブートストラップで学習されていますが、評価は同じ土俵（元データ）で揃える。 こうしないと、「自分が学習したデータでうまく当たるのは当たり前」となってしまい、 フェアな比較になりません。

しかし、もうひとつ重要な慣習があります。

ブートストラップサンプルの集合に、元の訓練データそのものも候補として含めるのです。 こうすれば、もし揺らしたサンプルから得られたどのモデルも元のモデルを超えなかった場合、 最低でも元のモデルを返せる。「保険」のような役割を果たします。

選択基準の数式

Bumping の選択ルールを数式で書くとこうなります。

各記号の意味を一つずつ見ていきましょう。

• $b$ は、 ブートストラップサンプルのインデックス（1 から B まで）です
• $\hat{f}$ の右上にあるアスタリスク（*）は「ブートストラップで学習したものですよ」という慣習的な印です。 元データから直接学習したモデル $\hat{f}$ と区別するためにつけます
• $\hat{f}^{*b}(x_i)$ は、 ブートストラップサンプル $b$ で学習したモデルが、元データの $i$ 番目の点 $x_i$ に対して出す予測です
• $L(y_i, \hat{f}^{*b}(x_i))$ は、 その予測と真の値 $y_i$ との損失です
• $\sum_{i=1}^{N}$ は、 元データのすべての点について損失を足し合わせるという意味です
• $\arg\min_b$ は、 その合計を最小にする $b$ を探す、という記号です

つまりこの式は、「B 個のモデルそれぞれで元データの総損失を計算し、 最も損失が小さかったモデルの番号を $\hat{b}$ とする」と読めます。

平方誤差のときには、より具体的にこう書けます。

最終的な予測モデルは、選ばれた番号 $\hat{b}$ を使って $\hat{f}^{*\hat{b}}(x)$ となります。 新しい入力 $x$ が来たら、選ばれたモデルにだけ尋ねるのです。

なぜ「揺らす」と局所最適から抜け出せるのか

ここでひとつ、疑問が湧きませんか？

ブートストラップでデータを揺らすだけで、本当に貪欲アルゴリズムの「死角」を覆せるのでしょうか？

答えはこうです。ブートストラップは、悪さをしているデータ点を一時的に除外してくれることがあるからです。

ブートストラップサンプルは元データから N 個を「重複ありで」選びます。 すると、元データの各点は およそ 37% の確率で選ばれない のです。

なぜ 37% なのかというと、1 回の抽選で選ばれない確率が $1 - 1/N$、 これを N 回繰り返すと、ある特定の点が一度も選ばれない確率は $(1 - 1/N)^N$ になります。 N が大きいとき、この値は数学定数 $e$ の逆数 $1/e \approx 0.368$、 つまり約 36.8% に近づきます。

ということは、「数個の点がアルゴリズムを混乱させて悪い解に導いている」場合、 それらの点が偶然除外されたブートストラップサンプルでは、もっと良い解が見つかる可能性があります。

教科書の言葉を借りれば、

By perturbing the data, bumping tries to move the fitting procedure around to good areas of model space.

データを揺らすことで、最適化手続きをモデル空間の良い領域へ「揺さぶり寄せる」。 Bumping という名前は、文字通り「ぶつけて動かす」イメージなのです。

XOR の例で見る Bumping の威力

教科書には、Bumping の効果を象徴的に示す例が載っています。 それが XOR データ です。

二次元平面上に、左下と右上に「青クラス」、左上と右下に「黄クラス」のデータが配置されているとします。 これは、x₁ と x₂ の符号が一致するかどうか、というシンプルな構造です。

ところが、決定木にこのデータを与えると、 悲しいことが起こります。

通常の貪欲アルゴリズム（CART）は、まず「x₁ か x₂ のどちらか一方で切る」ことを試みます。 ですが、どちらの軸で切っても、両側に青と黄が半分ずつ残ってしまう。「役に立つ最初の分割が存在しない」ように見えるのです。

結果、決定木はランダムに近い分割をしてしまい、XOR の本質的な構造（縦と横の両方で切れば 四つのきれいな領域に分かれる）を見抜けません。

ここで Bumping の出番です。

B = 20 個のブートストラップサンプルを作って、それぞれで木を育てる。 すると、ある何個かのサンプルでは偶然、青や黄のクラスのバランスが崩れて、 x₁ = 0 や x₂ = 0 に近いところで意味のある分割が起こります。たとえばあるサンプルでは 「左下にあった青い点がたまたま少なく抜き取られた」結果、x₁ = 0 で切ると有効な不均衡が生まれる、 といった具合です。

そして、20 個の木を元データで評価すると、それらの「たまたま良かった木」が一番低い誤差を示します。 Bumping はそれを選び、結果としてほぼ完璧な XOR 認識を達成します。

たった 20 回のサンプリングで、貪欲アルゴリズムが越えられなかった壁を越えるのです。

Bumping を使うときの注意点

Bumping は強力ですが、正しく使うためのコツがいくつかあります。

まとめ — 揺らすことで道が開ける

Bumping を改めて振り返りましょう。

それは、「複数のモデルを作って、最良のひとつを選ぶ」という、 シンプルすぎるくらいの方法です。Bagging のように分散を下げる効果はなく、 得られるのは結局たったひとつのモデルです。

それでも Bumping が意味を持つのは、最適化が貪欲法に頼っていて、データを少し揺らすだけで 結果が劇的に変わるような問題で、確率的探索が威力を発揮するからです。

XOR の例で見たように、貪欲アルゴリズムが諦めてしまう構造でも、20 回のブートストラップサンプルを 試せば、その中に「たまたま良い分割を見つけた木」が混じっている。Bumping はそれを掬い上げるのです。

機械学習の世界では、しばしば「もっと複雑なモデル」「もっと多くのデータ」が解決策として持ち出されます。 ですが Bumping は、「同じデータを何度も揺らして見直す」ことの価値を教えてくれます。

最適化アルゴリズムが見落とした宝物は、すぐ近くの「揺らしたデータの世界」に隠れているかもしれない。 そう信じて、確率的に探してみる。Bumping は、その素直な実装なのです。