Generating Explainable Rule Sets from Tree-Ensemble Learning Methods by Answer Set Programming

Akihiro Takemura, Katsumi InouearXiv 2021 · DOI

In the world of machine learning, there is a notorious tug-of-war between accuracy and interpretability. High-performance models like Random Forests and Gradient Boosted Decision Trees (GBDTs) are the workhorses of modern data science, but they are often "black boxes"—collections of hundreds of trees that no human can realistically audit.

A recent paper by Akihiro Takemura and Katsumi Inoue, presented at ICLP 2021, offers a bridge between these two worlds. They propose a framework that uses Answer Set Programming (ASP) to sift through the complex logic of tree ensembles and extract a concise, human-readable set of rules that explain the model's behavior.

TL;DR

The authors present a method to generate explainable rule sets from complex tree-ensemble models (like LightGBM or Random Forest) by treating rule selection as a logic optimization problem. By using Answer Set Programming (ASP), they allow users to declaratively define what makes an explanation "good"—such as high accuracy, small size, or minimal overlap—and automatically find the optimal set of rules.

What Problem Does This Paper Address?

While a single decision tree is easy to understand, an ensemble of 100 trees is not. Existing "post-hoc" explanation methods often provide local explanations (why this specific prediction happened) or importance scores (which features matter most), but they rarely provide a global, symbolic summary of the model's logic.

The challenge is that a tree ensemble contains thousands of potential rules (paths from root to leaf). Simply picking the "top" rules often leads to redundancy or sets that are still too large for a human to grasp. There is a need for a flexible, automated way to select a small, high-quality subset of rules that accurately represents the ensemble's decision-making process.

Methods

The authors propose a two-step "decompositional" framework:

  1. Rule Extraction & Metric Assignment:
    • They decompose every tree in the ensemble into its constituent paths. Each path becomes a candidate rule (e.g., IF x1 < 0.5 AND x2 > 4.5 THEN Class 1).
  2. For every candidate rule, they calculate performance metrics: accuracy, precision, recall, F1-score, support (how many data points it covers), and size (number of conditions).
  3. ASP-Based Rule Selection:
    • This is the core innovation. Instead of writing a custom search algorithm, they encode the selection criteria into Answer Set Programming (ASP), a declarative logic programming paradigm.
  4. Local Constraints: Filter out weak rules (e.g., "only keep rules with support > 10").
  5. Pairwise Constraints (Dominance): Automatically discard a rule if another rule exists that is strictly better across all chosen metrics.
  6. Global Constraints: Set limits on the final rule set (e.g., "the total number of conditions across all selected rules must not exceed 30").
  7. Multi-Objective Optimization: Use ASP’s #minimize and #maximize statements to find the "Pareto optimal" set of rules that balances accuracy, coverage, and simplicity.

Datasets

The framework was evaluated using 10 publicly available datasets from the UCI Machine Learning Repository, covering a variety of classification tasks:

  • Medical: Autism, Breast Cancer, Heart Disease, Kidney Disease.
  • Financial/Social: Census Income, Credit Approval (two versions), Voting Records.
  • Technical: Ionosphere, Krvskp (Chess).

Key Insights and Ideas

  • Declarative Flexibility: The biggest "aha moment" is the use of ASP. In traditional programming, changing your definition of a "good explanation" requires rewriting the algorithm. In ASP, you simply add or change a single line of logic (a constraint), and the solver handles the search.
  • Overlap Minimization: The authors introduced a specific optimization to minimize the number of shared conditions between rules. This ensures the final rule set is diverse and covers different "logical neighborhoods" of the data, rather than repeating the same information.
  • Faithfulness to the Model: Because the rules are extracted directly from the paths of the trained trees, the resulting explanations are guaranteed to be "faithful" to the original ensemble's internal logic.
  • The Power of LightGBM + ASP: Interestingly, combining the high-performance LightGBM algorithm with ASP-based selection often yielded better results than using Random Forests, suggesting that more "opinionated" ensembles provide better raw material for rule extraction.

Key Results

  • Interpretability: The proposed method consistently produced smaller rule sets than RuleFit and was often more concise than RIPPER (a classic rule-based learner). For example, on the autism dataset, it reduced the model to a single, highly effective rule.
  • Performance: While there is usually a slight drop in accuracy when moving from a full ensemble to a few rules, the "LightGBM + ASP" approach maintained very competitive performance.
  • High Recall: The extracted rule sets showed particularly high recall ratios (often > 1.0 relative to the original model), meaning the rules were excellent at capturing the majority of positive cases identified by the complex model.

Limitations and Future Work

  • Scalability: ASP solvers face an exponential search space. While it worked well for the tested datasets (solving within 600 seconds), very large datasets or massive ensembles might require stricter local constraints to prune the search space before the ASP solver takes over.
  • Regression: The current work is limited to classification. Extending this to regression (predicting continuous values) would require a different way of defining rule "consequents."
  • Rule Simplification: The method extracts paths exactly as they appear in the trees. Future work could involve "pruning" or simplifying individual rules (e.g., if a rule says x > 5 AND x > 10, it should just say x > 10) before the selection process.
  • Integration: The authors aim to explore how this symbolic reasoning can be more deeply integrated into the training phase of machine learning, rather than just being a post-hoc interpretation tool.

Summary updated

BibTeX
@misc{takemura2021generating,
  author = {Akihiro Takemura and Katsumi Inoue},
  title = {{Generating Explainable Rule Sets from Tree-Ensemble Learning Methods by Answer Set Programming}},
  year = {2021},
  doi = {10.4204/eptcs.345.26},
}
Figure