コスト複雑度剪定

1 基本概念

1.1 剪定の必要性

決定木学習アルゴリズムでは、訓練データに対して過度に適合する過学習が発生しやすい。木が深くなるほどノード数が増加し、ノイズや外れ値に敏感になる。剪定は、この過学習を抑制するための手法であり、完全に成長した木から不要な枝を除去することで、汎化性能を向上させる。

1.2 コスト複雑度の定義

2 数学的定式化

2.1 誤分類コスト

誤分類コストR(T)は、木Tが訓練データに対して生じる誤分類率を表す。分類問題では、各葉ノードにおける誤分類サンプル数の割合、または重み付けされた誤分類コストとして計算される。

2.2 複雑度ペナルティ

2.3 コスト複雑度関数

3 実装と手順

3.1 弱最適剪定

弱最適剪定は、完全に成長した木に対して、すべての内部ノードを評価し、コスト複雑度関数の増加が最小となる部分木を逐次的に剪定する手法である。剪定の各段階で、最小のコスト複雑度増加をもたらす枝が除去される。

3.1.1 アルゴリズム手順

3.1.1.1 再帰的剪定プロセス

まず、完全成長木T0から開始する。各内部ノードtについて、そのノードを根とする部分木Ttと、そのノードを葉ノードに置き換えた単一ノード木{t}のコスト複雑度差を計算する。この差が最小となるノードを剪定し、新しい木T1を得る。このプロセスを根ノードのみになるまで繰り返し、木の系列{T0, T1, ..., Tk}を生成する。

3.2 交差検証によるα選択

生成された木の系列から最適な木を選択するために、交差検証が用いられる。訓練データをK分割し、各分割で異なるα値に対する木の誤分類率を評価する。誤分類率が最小となるαを選択し、対応する木を最終モデルとする。これにより、データに依存した適切な複雑度が決定される。

4 理論的性質

4.1 剪定パスの一意性定理

コスト複雑度剪定において、αの変化に伴って生成される木の系列は一意に定まる。任意のαに対して、コスト複雑度関数を最小化する木は、弱最適剪定によって得られる系列の中に必ず存在し、かつその系列はαの値に依存しない。

4.1.1 証明のスケッチ

証明は、剪定の各段階で除去される枝が、αの増加に対して臨界値を持つことに基づく。各内部ノードには、そのノードを剪定するかどうかの閾値となるαの値が存在し、この閾値の大小関係によって剪定順序が一意に決定される。すべてのノードの閾値を計算することで、αの全域にわたる剪定パスが一意的に構築できる。

4.2 バイアス・バリアンストレードオフ

コスト複雑度剪定は、決定木におけるバイアスとバリアンスのトレードオフを直接的に調整する。αが小さい場合、複雑な木は低バイアスだが高バリアンスとなる。αが大きい場合、単純な木は高バイアスだが低バリアンスとなる。交差検証によるα選択は、このトレードオフを最適化する。

5 限界と発展

5.1 計算量の課題

コスト複雑度剪定は、完全成長木の生成と逐次剪定に計算コストを要する。大規模データセットでは、木の深さが増加し、剪定プロセスが指数関数的な時間を要する可能性がある。また、交差検証の実行はさらに計算負荷を増大させる。

5.2 代替手法との比較

5.2.1 ランダムフォレストへの拡張

コスト複雑度剪定は単一の決定木に適用されるが、ランダムフォレストでは複数の木のアンサンブルにより過学習が抑制される。ランダムフォレストでは、各木の剪定を省略し、深い木をそのまま使用することで多様性を確保する。剪定による単純化よりも、ブートストラップと特徴量サブサンプリングが汎化性能に寄与する。

5.2.2 深層学習との関係

深層学習では、正則化手法（L1/L2正則化、ドロップアウト、バッチ正規化など）が過学習を抑制する。コスト複雑度剪定は、決定木における構造的正則化と見なせる。ただし、深層ネットワークは連続的なパラメータ空間を持つため、剪定に相当する操作は重みの削減やニューロンの刈り込みとして実装される。両者はモデルの複雑さ制御という点で共通するが、適用対象と手法が異なる。