Rule Extraction from GBDT

Fire: An optimization approach for fast interpretable rule extraction. (KDD2023)¶

Fire（Fast Interpretable Rule Extraction） は、決定木アンサンブル（Random Forest や Boosted Trees）から 少数で解釈しやすいルール集合 を抽出するための最適化ベースのフレームワークである。 Fire は、

• スパース選択（非凸ペナルティ） により代表的なルールを厳選し、

• 融合正則化（fused LASSO） により共通の前提条件（if-then antecedents）を共有するルール群を促す。

これにより、解釈性を保ちながら高性能な小規模モデルを生成できる。

Fire は問題規模と非凸性のため既存ソルバーでは扱いにくいが、論文では ブロック座標降下（BCD）＋貪欲選択（greedy selection） に基づく専用ソルバーを開発し、既存手法より最大40倍高速に動作することを示した。

前提の考え方¶

決定木の葉ノードはif-thenルールの連鎖になる。例えば閾値$s$, 入力$x$, 葉の値$v$について

のように表すことができる。

アンサンブルは葉の重み付き和

であるため、重要度の低い葉の重み$w_j$をゼロにすることで予測精度への悪影響を抑えつつルールをシンプルにし、人間にとっての解釈可能性を上げることができる。

目的関数¶

スパース化のための項と、ルールの融合のための項をつけた目的関数を使う

スパース化¶

正則化項にLASSOではなくMCP（Minimax Concave Penalty）を採用

$\gamma > 1$ はハイパーパラメータで、$\gamma \approx 1$では$\ell_0$ペナルティ、$\gamma$が無限までの大きいときは$\ell_1$ペナルティ（＝LASSO）に近づく

融合項¶

隣接ノードの重みの差へのペナルティをかける fused LASSO を導入

近いノードをまとめてグループ化し、ルールの共有や内部ノードの削減を促す