決定木剪定（けっていぎせんてい）は、Machine learningにおける手法であり、予測力がほとんどない木の部分を除去することで決定木のサイズを縮小する。主な目的は、複雑性を減らし過学習を緩和することで、未見データに対するモデルの汎化性能を向上させるとともに、解釈可能性を高め、学習時間と推論時間を短縮することである。
剪定は、完全に成長した決定木が訓練データに過度に適合し、ノイズや外れ値を捉えてしまうため不可欠である。これにより、新しいデータに対する性能が低下する。木を単純化することで、剪定は訓練誤差のわずかな増加と引き換えに検証誤差の大幅な減少をもたらし、より頑健なモデルを実現する。
剪定の種類
剪定方法は、事前剪定（前方剪定とも呼ばれる）と事後剪定（後方剪定）の2つの大きなカテゴリに分類される。
事前剪定は、構築中に特定の基準が満たされたときに木の成長を停止する。一般的な基準には、最大深さ、葉あたりの最小サンプル数、最小情報利得の閾値、分割の統計的有意性検定などがある。事前剪定は単純で効率的だが、成長を早すぎる段階で停止させ、重要な交互作用を見逃す可能性がある。これは初期の決定木文献で議論され、1960年代のBernard Widrowによる適応システムに関する研究を含むが、正式な概念は後のアルゴリズムとより関連している。
事後剪定は、最初に完全な木を構築し、その後で枝を除去する。このアプローチは、木全体の構造を考慮するため、一般的により効果的である。手法には、コスト複雑性剪定（最小コスト複雑性剪定とも呼ばれる）や誤差ベース剪定が含まれる。事後剪定は、どの枝を除去するかを決定するために、別の検証セットや交差検証をしばしば使用する。
最もよく知られた事後剪定アルゴリズムは、1984年にBreimanらがCARTの書籍で導入したコスト複雑性剪定である。これは、誤差率と葉の数の両方に基づいて各部分木にコストを割り当て、トレードオフを最小化する部分木を選択する。これは、木のサイズにペナルティを課すハイパーパラメータalphaを用いて達成される。
重要な参考文献として、Christopher Bishopが1995年の著書「Neural Networks for Pattern Recognition」で、ニューラルネットワークの文脈で剪定を議論しているが、同じ原理が決定木にも適用される。決定木の文献では、J. Ross QuinlanがC4.5アルゴリズム（1993年）向けに誤差ベース剪定を開発し、Quinlanは初期の研究で縮小誤差剪定も導入した。
アルゴリズムと実装
実際には、ID3、C4.5、CART、およびその後継であるC5.0などのアルゴリズムが、さまざまな剪定方法を組み込んでいる。コスト複雑性剪定の場合、標準的な実装には以下が含まれる。
- 完全な木を成長させる。
- 各ノードのalpha値を計算する。
- 最小のalphaを持つノードを順次剪定する。
- コスト複雑性スコアを最小化する部分木を選択する。
Pythonライブラリscikit-learnでは、コスト複雑性剪定はccp_alphaパラメータとして実装されている。あるいは、XGBoostやLightGBMなどのライブラリは、独自のヒューリスティックを用いた事後剪定を使用し、多くの現代のライブラリは事前剪定（max_depthなどのパラメータによる）と事後剪定の両方をサポートしている。Carnegie Mellon UniversityのオープンソースプロジェクトやSambaNovaのML環境では、剪定は分散訓練パイプラインに統合されることが多い。
剪定と他の手法の比較
決定木剪定は、Artificial intelligenceにおけるシンボリックモデルのサイズ削減に使用されるより広い用語であるModel Pruningと概念的に関連している。深層モデルにおけるパラメータ剪定（重みを除去する）とは対照的に、木の剪定は枝や部分木全体を除去する。さらに、DropoutやRegularizationは代替手法であるが、木には直接適用できないものの、同じ目的を果たす。
多くの実践者は、汎化性能をさらに高めるために、剪定をData Augmentationなどの他の手法と組み合わせる。Neural networkの文脈での剪定が推論の計算コストを削減することが多いのに対し、木の剪定は主に汎化性能と解釈可能性を向上させる。
応用と影響
決定木剪定の実用的な影響は、医療診断、信用スコアリング、不正検出など、モデルの解釈可能性が重要となる領域で大きい。例えば、医療専門家は、ブラックボックスにさらされていない患者に決定を正当化するために透明なモデルを必要とする。不要な枝を除去することで、臨床医は最も重要なルールに集中できる。金融分野では、規制当局が決定の説明を検証可能かつ解釈可能であることを要求することが多い。
性能面では、剪定は結果として得られる木が小さく実行が単純になるため、推論を高速化する。これは、Amazon Web Servicesに展開されたリアルタイムシステムや、Samsung Electronicsのようなエッジデバイスで特に重要であり、遅延が問題となる。また、Generative AIの分野ではモデルが大きいため、剪定は木ベースの手法ほど頻繁には使用されないが、モデル単純化の知識とアイデアに貢献している。
課題とベストプラクティス
評価における重要な課題は、適切な剪定基準を選択することである。過度に積極的な剪定は過小適合を引き起こす可能性があり、剪定が少なすぎると過学習が残る。剪定レベルを調整するために別の検証セットを使用する手法は標準的であり、alphaの選択は交差検証によって行われることが多い。最適な木が構築された後に事後剪定を効果的に使用し、計算予算が重視される場合には事前剪定を使用することが推奨される。
もう1つの課題は、多くのレベルを持つカテゴリ変数の処理である。剪定は、まれに見られるが重要なグループをカバーする枝を除去する可能性がある。実際には、剪定はドメインの期待とバランスを取るべきであり、例えば医療や金融では、誤差を減らさなくても臨床的に重要であるため、まれな枝を保持しなければならない場合がある。
プロジェクト開発では、剪定の要約をモデル検証後、偏りのないテストセットを使用して実行することが推奨される。多くのソフトウェアライブラリには、事前剪定と事後剪定の両方の方法を含むデフォルトパラメータがあり、それらの相互作用を理解することは簡単ではなく、経験的なテストが必要である。
2020年代現在、決定木剪定は依然として標準的な手法であり、Google CloudやOracle Cloud Infrastructureなどの大手テクノロジープロバイダーがサポートする多くのツールや、オープンソースの配布物に組み込まれている。他の手法が登場しているが、木の表現がこれほど単純化されているため、ノイズオブジェクトを除去するほど単純で効果的な方法はない。