10.8-10.9 スパムフィルタとブースティング木

決定木を「領域と値」で再定義する

ブースティング木を理解するには、まず決定木を式で書けるようにしておく必要があります。

決定木とは「if-thenルールを枝分かれさせた図」——という説明は直感的ですが、数学的に扱いにくい。 代わりにこう考えてみてください。

決定木 = 入力空間を箱で区切り、各箱に1つの数を貼り付けたもの

入力空間を互いに重ならない $J$ 個の領域$R_1, R_2, \ldots, R_J$ に分割し、 各領域 $R_j$ に予測値 $\gamma_j$ を割り当てます。 新しいデータ $x$ が来たら、「$x$ がどの箱に入るか」を見て、その箱の値を返すだけです。

これを式で書くと驚くほどシンプルです：

ここで $I(x \in R_j)$ は指示関数——$x$ が領域 $R_j$ に入っていれば1、入っていなければ0。 だから和の中で実際に効くのは1つの項だけです。「どの箱か」を1にして、「その箱の値」を返す——これが決定木の正体です。

パラメータは $\Theta = \{R_j, \gamma_j\}_{j=1}^J$ という2種類の情報を含みます：

• $R_j$：「どこで」予測するか（領域の形）
• $\gamma_j$：「何を」予測するか（その領域での値）

この2種類のパラメータの違いは、後で「最適化のしやすさ」に直結します。$\gamma_j$ は領域が決まっていれば簡単に求まります（平均か中央値）。 しかし $R_j$ そのものを最適化するのは難しい—— 可能な分割の数が爆発的に多いからです。

ブースティング木 — 弱い木を「足し算」する

決定木が「領域と値の集合」だと分かれば、ブースティング木の定義はあっけないです。

つまり、$M$ 個の決定木を足し合わせるだけです。 それぞれの木 $T(x; \Theta_m)$ は独自のパラメータ$\Theta_m = \{R_j^{(m)}, \gamma_j^{(m)}\}$ を持ちます。

ここで「弱い」とはどういう意味でしょうか。弱い学習器とは 「単独では精度が低いが、ランダム推測よりはマシな予測器」のことです。 ブースティング木では通常、葉の数 $J$ が 2〜8程度の浅い決定木を使います。 深く複雑な1本ではなく、わざと弱くした多数の木を組み合わせるのがコツです。

なぜ「足し算」がうまく機能するのでしょうか？

1本の弱い木だけだと、データを正しく分けられない領域が必ず残ります。 それを補うように2本目の木が前の木の間違いを修正する形で追加されます。 3本目はさらに残った間違いを修正します。こうして、各木が前の木の弱点を埋め合いながら積み上がっていきます。

この「前の木に追加して全体の誤差を減らす」という発想を式にすると、各段階で解くべき問題は：

ここで $f_{m-1}(x_i)$ は「これまでに足された $m-1$ 本の木の予測の合計」です。 新しい木 $T(x; \Theta_m)$ を加えたとき、累積予測が真の答え $y_i$ にどれだけ近づくか—— それを損失関数 $L$ で測り、最小化します。

これは逐次的最適化です。一度に $M$ 本の木を同時に決めるのではなく、1本ずつ前の結果を受けて決める。各ステップは局所的に最適でも、全体としては強力な予測器が出来上がります。

損失関数が決める「簡単さ」

ブースティング木の最適化は、選んだ損失関数 $L$ によって難しさが劇的に変わります。

ケース1：二乗誤差 $L(y, f) = (y - f)^2$

このとき、最適化は驚くほどシンプルになります。展開してみましょう：

$r_i = y_i - f_{m-1}(x_i)$ と置けば、これは 「残差 $r_i$ に対する回帰木」を学習する問題と完全に等価です。 普通の決定木アルゴリズムをそのまま使えます。

ケース2：指数損失 $L(y, f) = \exp(-y f)$

これがAdaBoostです。$y \in \{-1, +1\}$ の2値分類で使われます。 指数損失の場合、「最適な木はどんな形か？」という問いに式変形だけで答えが書ける—— これを閉形式解と呼びます。前章のAdaBoostで見た「誤分類点に重みを付け直して新しい木を学習する」という手順そのものです。

ケース3：一般的な損失関数（Huber損失、ロジスティック損失など）

ここで状況が一気に難しくなります。 「Huber損失」は外れ値に強い回帰の損失、 「ロジスティック損失（デビアンス損失）」は2値分類で確率を推定する自然な損失です。 どちらも実用的ですが、ブースティング木に当てはめると、式変形だけでは「最適な領域 $R_j$ と値 $\gamma_j$」が求まりません。

この困難さを乗り越えるために考案されたのが、勾配ブースティング（Gradient Boosting）です。 次節（10.10）で詳しく見ますが、要点はこうです：

「真の答えに直接合わせる木」を作る代わりに、「損失を減らす方向を指し示す木」を作る。

通常の勾配降下法は「パラメータを少し動かして損失を減らす」手法ですが、 勾配ブースティングは「1本の木を加えて損失を減らす」と読み替えます。 動かす対象がパラメータではなく関数（予測器全体）になるイメージです。

つまり、損失関数の選択は単なる「好み」ではなく、ブースティング木の解き方そのものを決めるのです。

スパムフィルタの実例 — 57変数のうち効くのは数個

理論を見たところで、ブースティング木が実データでどう振る舞うかを確かめてみましょう。

舞台はSpamデータセット——4601通のメールから抽出された特徴量で、 各メールがスパムかどうかを判定する2値分類問題です。特徴量は全部で57個です。

特徴量の中身は、メール本文中の特定の単語の出現頻度（例：free、money、hp、george）、 特定の文字の頻度（!、$、#）、連続する大文字の長さなどです。

ブースティング木を試してみると、結果は明白です：

ブースティング木が他を引き離して最良です。 CART木との差（4.5% vs 8.7%）は2倍近い。 1本の木よりも、弱い木を多数組み合わせた方が圧倒的に強いことが分かります。

しかし本当に面白いのは、ブースティング木が自動的に学習する変数の重要度です。 57個の変数のうち、本当に判定に使える変数はどれでしょうか？

変数重要度のスペクトラム — 自動的に「効く特徴」を発見する

ブースティング木は学習過程で、「どの特徴量が判定に役立っているか」を副産物として教えてくれます。 これが変数重要度（variable importance）です。

考え方はシンプルです：

各分割で、その変数を使うことで損失がどれだけ減ったか。 それを全ての木・全ての分割について足し合わせる。

「よく使われる」だけでなく、「使ったときに大きく損失が減る」変数が重要視されます。

Spamデータでのトップ10を見てみましょう。1位を100%として相対化すると：

直感的に納得できます。「!!!」や「$$$」を多用するメールはスパムの典型的なシグナルですし、 「remove」も「クリックで購読解除」というスパムの常套句です。

一方、「hp」が上位にあるのは少し意外かもしれません。これはこのデータがHP社の社内メールから集められたため—— スパムでないメールには会社固有の単語が頻繁に登場するからです。

注目すべきは、下位の変数（857、415、tableなど）の重要度がほぼゼロであること。 ブースティング木はノイズに惑わされず、本当に効く特徴量を自動で選び出しています。 これは「特徴量選択」を別工程で行わなくてよいという、実用上の大きな利点です。

交互作用の発見 — 加法モデルでは届かない深み

ブースティング木のもう一つの強さは、変数間の交互作用を自然に捉えることです。

加法モデル（J=2、すなわち各木が単純に1回だけ分割する）はエラー率4.7%。 一方、より深い木（J=5、4回分割できる）は4.5%——わずか0.2%の改善ですが、これが交互作用の存在を示しています。

なぜ J=2 が「加法モデル」と等価なのでしょうか。J=2 の木は1回だけ分割するので、 ある1変数の閾値で「右か左か」を決め、それぞれの葉に値を割り当てるだけです。 つまり1本の木は「1つの変数の効果」しか表現できない。これを多数足し合わせると、各変数の効果を独立に加える形

に必ず収まります。これが「加法的（additive）」という言葉の意味です。

交互作用とは何か？

変数Aの影響が、変数Bの値によって変わる現象

例：「! の頻度が高い」というだけならスパムの可能性が高いですが、 「hp の頻度も高い」場合は社内メールの可能性が上がります。! 単独の効果ではなく、hp の値との組み合わせで判定が変わります。

これを視覚化するのが部分従属プロット（partial dependence plot）です。 2変数の組み合わせに対する予測値を3D曲面で表します。

! と hp の部分従属プロットを見ると、平面ではなく曲面になっていることが分かります。hp が低いときは ! の増加でスパム確率が急上昇しますが、hp が高いときは ! が増えてもスパム確率はあまり上がりません。hp が ! の影響を打ち消すような形です。

加法モデルでは、このような「打ち消し合い」「強め合い」の関係を表現できません。 なぜなら加法モデルは

という形しか取れないからです。$x_1$ の効果は$x_2$ と独立になります。

これに対して、J=5の木は1本の中で複数の変数を順番に分割するため、 自然に「Aを見て、その結果でBを違う形で見る」という構造を持ちます。深い木 = 高次の交互作用を捉える能力です。

まとめ — 単純な足し算が「最強」を生む

このページで見てきたことを振り返りましょう。

理論的な構造：

1. 決定木は「領域 $R_j$ と値 $\gamma_j$ の集合」として表現できる
2. ブースティング木は「$M$ 本の決定木の和」として定義される
3. 各木は前の累積予測を見て、損失を最小化する形で逐次的に追加される
4. 損失関数の選択が最適化の難しさを決め、勾配ブースティング（次節）に繋がる

実データでの強さ（Spamデータ）：

1. テストエラー率4.5%で他の手法を圧倒
2. 57変数中の本当に効く数個を自動で抽出（変数重要度）
3. 交互作用を捉えて加法モデルを超える精度を実現

ブースティング木の本質は、「弱い学習器の累積」というシンプルな発想です。 1本の木は粗い予測しかできないが、足し合わせることで滑らかで強力な予測器になります。

ここで考えてみてほしいのです：

なぜ「最強の1本」を目指すよりも「弱い多数」を組み合わせる方が強いのか？

答えの一部はバイアス・バリアンスの分解（第7章）にあります。 深く複雑な1本の木はバリアンスが大きく不安定です。浅い木を多数組み合わせれば、平均化によってバリアンスが小さくなります。

しかしブースティング木は単なる平均ではありません。前の木の弱点を補うように次の木が作られます—— これが「逐次的に賢くなる」というブースティングの核心です。

次の節（10.10）では、この「逐次的最適化」を任意の損失関数に一般化する勾配ブースティングを見ていきます。 そこでは「関数空間での勾配降下法」という美しい視点が登場します。