決定木

決定木は「この座標は閾値以下か」を一問ずつ尋ねます。学習では候補を採点し、情報利得が最大の切分けを貪欲に選んで子集合へ再帰します。予測は根から葉へ質問をたどり、葉の多数クラスを返します。

本課は軸に沿う切分けだけを許すため、一つの葉は軸平行の長方形です。同じクラスは複数の長方形を持てます。深さの予算が質問数を制限し、この二条件が表現力と誤りを決めます。

仕組み

a 個の A と b 個の B を持つ領域のエントロピーは：

H = −p_A log₂ p_A − p_B log₂ p_B

純粋なら 0、半々なら 1 bit、比率ゼロの項は極限として 0 です。情報利得は親のエントロピーから、子のエントロピーを標本数で加重した和を引きます。

特徴ごとに異なる座標値を整列し、隣接値の中点を候補にします。同じ隙間のどの閾値でも訓練点の分割は同じなので、中点一つで代表できます。画面の下端と左端の棒が各候補の利得です。

最良の分割後、各子は自分の点だけを使います。純粋な節はそのクラスを返し、depth==max_depth は多数を返します。一般実装は同座標の矛盾ラベルなど、混合していても分割不能な節を多数葉で止める必要があります。本課にその重複はありません。

規約は、≤ が左子、利得同点は特徴番号の小さい方、次に低い閾値を優先。最良値は厳密に上回る場合だけ更新します。票数同点は A。切線はその節の領域だけを横切り、兄弟領域へ伸びません。長方形は条件から導かれます。

ステップごとの例

初期値は 11 点、A 6、B 5、max_depth=2、問い合わせ (3,3)。左に A 四点、右下に B 四点、右上に A 二点と教材上のノイズ B (3,4) を置きます。

1. 根は 6:5、エントロピー約 0.99 bit。
2. x₁ の縦候補六つを調べます。x₁≤−0.5 が最大で、0.99−(4/11)×0−(7/11)×0.86≈0.44 bit。左は純粋な A です。
3. x₂ の七候補では x₂≤−2.5 が約 0.24。x₁ に負けます。
4. x₁≤−0.5 を確定し、二長方形と根の質問を作ります。
5. 左は A 四点、エントロピー 0 なので深さ 1 で A の葉になります。
6. 右は A 2、B 5、約 0.86。この節の x₁ 最大は約 0.08、x₂≤0.5 は約 0.47 で後者を選びます。横線は右長方形だけを切ります。
7. 右下は B 四点の純粋葉です。
8. 右上は A 2、B 1 の混合ですが深さ 2 で停止し、A を返します。B (3,4) は A と判定。三葉、誤り 1/11 です。
9. 問い合わせ (3,3) は 3>−0.5 で右、3>0.5 で右上へ進み、2:1 で A。これは訓練計数で、校正された 67% ではありません。

深さと過学習

深さ 3 なら右上で x₂≤3.5、利得約 0.92 の分割を追加できます。ノイズ B 一点だけの細い葉ができ、訓練誤りはゼロです。しかし領域全体を支える観測は一点。高利得や純粋さだけでは汎化を保証しません。

深さ 1 は右半分を多数 B として本物の A 二点を失い、2 誤り。深さ 2 は 1 誤り、深さ 3 はノイズを独立させて 0。同じ貪欲木を延長した訓練誤差は増えませんが、一段ごとに必ず下がるわけでもありません。深さを検証データで選び、独立テストで評価します。剪定、最小葉標本数、ランダムフォレスト、勾配ブースティングなどは単木の分散に対処しますが、無条件の解決ではありません。

長方形と斜線

二島データは線形分類器と同じ点配置で、3 クラスを 2 クラスにまとめたものです。同一クラスが対角、別クラスが通路にあると凸領域では分けられません。木は x₁≤−1.5 で一島、x₂≤1.5 でもう一島を囲み、誤りゼロです。同クラスの長方形の和集合は凸でなくてよいからです。根では両軸の利得が 0.31 で、低い番号の軸を選ぶ規則も見えます。

対角線プリセットは逆です。八点は x₂=x₁ 一本で分離できますが、木は斜めの質問を使えません。x₁≤−3、x₂≤−1、x₁≤1 と階段を作り、深さ 3 でも一点を誤ります。破線は比較用の線形境界です。許される質問とデータ形の相性が必要な深さと葉数を左右します。

計算費用

候補ごとに数え直す素朴な走査は一節あたり約 O(d n²) で、別に整列があります。整列後の累積計数などで改善できます。予測は一経路だけで O(depth)、訓練点を再走査しません。本課は二特徴十一点なので全候補を確認できます。

境界ケース

• 純粋なら予算が残っていても停止します。初期の左節は深さ 1 で終わります。
• 混合節で深さ上限なら多数決となり、少数点が誤ります。
• 一軸が一値だけなら中点候補はありません。全軸で分割不能なら一般実装は多数葉を返し、純粋だと仮定しません。
• 利得同点は特徴番号と閾値の順です。二島の根で確認できます。
• 多数票同点は A。公開した規約であり、学習した事実ではありません。

よくある間違い

• 木が長方形の地図を保存すると思う。質問を保存し、経路条件が地図を作ります。
• 高利得の一点葉を信頼する。支持標本数と検証成績も必要です。
• 訓練ゼロ誤りを成功とする。許された分割で区別でき、ラベルが矛盾しない有限データなら深い木は記憶できますが、汎化規則とは限りません。
• 貪欲法が最小の木を見つけると思う。局所最良を固定し全体を探索しません。最適木構成の関連問題は NP-hard で、走査は折衷です。
• 葉の「A が 2/3」を校正確率と読む。小領域内の訓練頻度です。

簡略化の範囲

エントロピーと情報利得を使う二分閾値木で、ID3 の選択思想に近く、連続特徴の中点を用います。二特徴、深さ制限、十一整数点で手計算できます。他の実装は Gini 不純度を使うこともあり、候補順は同じとは限りません。

d 次元でも一問は一座標と閾値で、葉は軸平行の超長方形になります。実際の木は回帰、欠損値方針、コスト複雑度剪定、最小葉標本なども扱いますが、対応は実装次第です。複数木の組合せは単木の不安定さに対処します。学習と評価は学習ループも参照してください。