McXai: Local Model-Agnostic Explanation As Two Games

Yiran Huang, Nicole Schaal, Michael Hefenbrock, Yexu Zhou, Till Riedel, Michael Beigl

TL;DR

McXai (Monte Carlo tree search for eXplainable AI) transforms the challenge of interpreting "black-box" machine learning models into a strategic game. By using Monte Carlo Tree Search to identify both the features that support a decision and those that lead to errors, it provides hierarchical, tree-based explanations that capture complex feature dependencies better than industry standards like LIME or SHAP.

What Problem Does This Paper Address?

As machine learning moves into high-stakes environments like medicine and law, "black-box" models—where we see the output but don't understand the internal logic—become a liability. Existing local interpretability methods, which explain individual predictions, have three major flaws:

  1. Feature Independence: Most methods (like LIME) treat features as independent, ignoring the fact that some features only matter when present alongside others.
  2. One-Sided Focus: They usually focus on what supports a decision, ignoring the "misleading" features that might cause a model to fail.
  3. Complexity: The explanations themselves can be as difficult to parse as the models they are trying to explain.

The authors propose McXai to address these gaps by providing a human-friendly tree structure that maps out feature relationships and identifies both positive and negative influences on a prediction.

Methods

The core innovation of McXai is framing explanation as two distinct games played using Monte Carlo Tree Search (MCTS):

  • The Classification Game: The agent tries to find the smallest set of features necessary to maintain the correct classification. It "masks" (hides) features one by one, searching for the "skeleton" of the decision.
  • The Misclassification Game: The agent searches for features to which the model is overly sensitive—those that, when perturbed, lead to incorrect labels.

Why MCTS? Just as MCTS allows AI to play Chess or Go by exploring future possibilities, here it explores the "state space" of feature combinations. Each node in the tree represents a version of the input with certain features masked. The "reward" for the agent is a balance between how much the model's confidence changes and how few features were needed to cause that change. This naturally highlights the most influential feature dependencies.

Datasets

The authors evaluated McXai across a diverse range of data types to prove its "model-agnostic" nature:

  • Images: MNIST (handwritten digits), Face (4096 features), and a Dog-vs-Cat dataset.
  • Relational/Tabular: Covertype (forest cover types) and KDDCup (network intrusion detection).
  • Text: The 20 Newsgroups dataset.

Key Insights and Ideas

  • Beyond Heatmaps: Unlike traditional saliency maps that just highlight pixels, McXai produces a tree. This allows a user to see a hierarchy: "This feature is the most important, but if you remove it, these other three features become the secondary drivers."
  • Identifying "Negative" Features: One of the most striking insights is that models often fixate on "distractor" features that don't actually belong to the target class (e.g., a specific background pattern in a cat photo).
  • Explanation as a Debugger: The authors found that by identifying these negative features in the "Misclassification Game" and removing them from the training data, they could actually retrain the model to be more accurate and robust. This moves XAI from a passive observation tool to an active model-improvement tool.
  • Handling Redundancy: McXai handles "multicollinearity" (when two features provide the same information). It recognizes that while two features might be equally important individually, only one is needed for a successful prediction.

Key Results

  • Efficiency (Number of Steps): To test the quality of explanations, the authors measured how many features (steps) needed to be removed to flip a model's prediction. In almost all categories (MNIST, Covertype, Face), McXai required significantly fewer steps than LIME or SHAP, indicating it identifies the "true" influential features more accurately.
  • Model Improvement: In the Dog-vs-Cat experiment, retraining models after removing the "negative" features identified by McXai led to consistent accuracy boosts. For example, the MnasNet0_5 model improved from 87.78% to 89.16% accuracy.
  • Stability: Removing misleading features didn't just improve raw accuracy; it reduced the variance in model performance, leading to more stable and reliable classifiers.

Limitations and Future Work

  • Computational Cost: MCTS is an iterative process. While the authors note it is faster than SHAP in some text-based scenarios, it is generally slower than simpler methods like LIME. Analyzing a single image can take several minutes.
  • Feature Granularity: For high-resolution images, the search space becomes massive. The paper primarily uses "superpixels" or downsampled images to keep the tree search manageable.
  • Future Directions: The authors suggest that the "Misclassification Game" could be further developed to defend against adversarial attacks by identifying and neutralizing the specific features that attackers exploit.

Summary updated

Abstract

To this day, various approaches for providing local explanation of black box machine learning models have been introduced. Despite these efforts, existing methods suffer from deficiencies such as being difficult to comprehend, only considering one feature at a time and disregarding inter-feature dependencies, lacking meaningful values for each feature, or only highlighting features that support the model's decision. To overcome these drawbacks, this study presents a new approach to explain the predictions of any black box classifier, called Monte Carlo tree search for eXplainable Artificial Intelligence (McXai). It employs a reinforcement learning strategy and models the explanation generation as two distinct games. In the first game, the objective is to identify feature sets that support the model's decision, while in the second game, the aim is to find feature sets that lead to alternative decisions. The output is a human-friendly representation in the form of a tree structure, where each node represents a set of features to be examined, with less specific interpretations at the top of the tree. Our experiments demonstrate that the features identified by McXai are more insightful with regard to the classifications compared to traditional algorithm like LIME and Gram-cam. Furthermore, the ability to identify misleading features provides guidance towards improved robustness of the black box classifier.
BibTeX
@inproceedings{huang2023mcxai,
  author = {Yiran Huang and Nicole Schaal and Michael Hefenbrock and Yexu Zhou and Till Riedel and Michael Beigl},
  title = {{McXai: Local Model-Agnostic Explanation As Two Games}},
  booktitle = {IJCNN},
  year = {2023},
  doi = {10.1109/ijcnn54540.2023.10191756},
}
Figure