Rule Extraction from GBDT

Rule Extraction from GBDT#

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

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

Liu, B., & Mazumder, R. (2023, August). Fire: An optimization approach for fast interpretable rule extraction. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1396-1405).

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\)について

\[ r_3(x)=1\left(x_1>s_1\right) \cdot 1\left(x_3 \leq s_3\right) \cdot v_3 \]

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

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

\[ \hat{y}=\sum_j w_j r_j(x) \]

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

目的関数#

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

\[ \min _w \frac{1}{2}\|y-M w\|_2^2+h\left(w, \lambda_s\right)+g\left(w, \lambda_f\right) \]
\[ h\left(w, \lambda_s\right)=\sum_{j=1}^R P_\gamma\left(w_j, \lambda_s\right) \]

スパース化#

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

\[\begin{split} P_\gamma\left(w_j, \lambda_s\right)= \begin{cases}\lambda_s\left|w_j\right|-\frac{w_j^2}{2 \gamma}, & \left|w_j\right| \leq \lambda_s \gamma \\ \frac{1}{2 \gamma} \lambda_s^2, & \left|w_j\right|>\lambda_s \gamma\end{cases} \end{split}\]

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

融合項#

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

\[ g\left(w, \lambda_f\right)=\lambda_f \sum_{t=1}^T\left\|D_t w_t\right\|_1 \]

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

Contents