Induction of Non-Monotonic Logic Programs to Explain Boosted Tree Models Using LIME

Farhad Shakerin, Gopal GuptaAAAI 2019 · DOI

Abstract

Modern machine learning models, particularly Gradient Boosted Trees like XGBoost, offer high predictive accuracy but function as "black boxes," lacking human-interpretable explanations. This paper presents LIME-FOLD, a novel framework that bridges the gap between statistical performance and symbolic interpretability. By integrating Local Interpretable Model-agnostic Explanations (LIME) with non-monotonic logic induction (FOLD), the proposed method generates concise, accurate global rule sets. Evaluations on ten benchmark datasets show that LIME-FOLD produces significantly more compact models and operates up to 80 times faster than traditional Inductive Logic Programming (ILP) systems.

Introduction

While statistical models achieve state-of-the-art results in classification tasks, their lack of transparency poses challenges in high-stakes domains like medicine and finance. Inductive Logic Programming (ILP) offers a path toward interpretability by learning human-readable "if-then" rules. However, traditional ILP algorithms, such as ALEPH, suffer from scalability issues and a tendency to produce overly complex rule sets when faced with noisy data. LIME-FOLD addresses these limitations by using local feature importance to prune the search space for symbolic learning.

Methodology: The LIME-FOLD Pipeline

LIME-FOLD operates through a three-stage integration of local explanations and global rule induction:

  1. Local Explanation (LIME): For each instance in the training set, LIME identifies the most influential features contributing to the black-box model's prediction.
  2. Feature Filtering: The dataset is transformed by retaining only the features flagged as important by LIME. This targeted filtering prevents the logic learner from being overwhelmed by irrelevant or noisy data.
  3. Non-Monotonic Logic Induction (FOLD): The First Order Learner of Defaults (FOLD) algorithm is applied to the filtered data. Unlike standard logic, FOLD utilizes non-monotonic reasoning (Negation-As-Failure), allowing it to learn default rules and their exceptions (e.g., "If X, then Y, unless Z").
Figure 1: LIME dashboard showing local feature importance and prediction probabilities for a heart disease classification task.

Experimental Evaluation

The researchers evaluated LIME-FOLD against the industry-standard ALEPH system across ten UCI Machine Learning Repository benchmarks. These datasets, ranging from medical diagnostics (Breast Cancer, Kidney Disease) to technical classifications (Ionosphere, Sonar), provided a diverse testing ground for rule conciseness, accuracy, and computational efficiency.

Key Results

The experimental results highlight three major advantages of the LIME-FOLD approach:

  • Conciseness: LIME-FOLD consistently generated fewer rules (clauses) than ALEPH. By focusing on locally relevant features and employing non-monotonic logic, the system avoids the "rule bloat" typical of traditional ILP. For example, on the "Credit-j" dataset, ALEPH produced nearly 30 rules, while LIME-FOLD produced a significantly more compact set.
  • Accuracy: LIME-FOLD achieved a superior $F_1$ score in 9 out of 10 tested datasets, demonstrating that its concise rules capture the underlying decision logic more effectively than complex rule sets.
  • Efficiency: LIME-FOLD demonstrated a massive leap in performance, running an average of 80 times faster than ALEPH. For instance, in the Ionosphere dataset, processing time was reduced from over 1,000 seconds to under 5 seconds.
Figure 2: Comparison of rule conciseness (number of clauses) between ALEPH, LIME-ALEPH, and LIME-FOLD across ten benchmark datasets.

Conclusion and Future Work

LIME-FOLD successfully demonstrates that local explanations can be aggregated to form robust, global symbolic models. By leveraging the strengths of both statistical and symbolic AI, the framework provides a scalable solution for explaining complex black-box models. Future research will explore the discovery of sub-concepts through clustering and the automated construction of new descriptive features to further enhance the depth of the generated logic programs.

Summary updated

BibTeX
@inproceedings{shakerin2019induction,
  author = {Farhad Shakerin and Gopal Gupta},
  title = {{Induction of Non-Monotonic Logic Programs to Explain Boosted Tree Models Using LIME}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013052},
}
Figure