McXai: Local model-agnostic explanation as two games

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

Introduction

As machine learning models are increasingly deployed in high-stakes domains like medicine and law, the "black-box" nature of these systems becomes a significant liability. While local interpretability methods aim to explain individual predictions, existing tools like LIME and SHAP often struggle with feature dependencies, focus solely on positive evidence, and produce complex outputs that are difficult for humans to parse.

McXai (Monte Carlo tree search for eXplainable AI) addresses these challenges by reframing model interpretation as a strategic game. By utilizing Monte Carlo Tree Search (MCTS), McXai identifies both the features that support a decision and those that lead to errors, providing hierarchical, tree-based explanations that capture complex relationships more effectively than current industry standards.

Methodology: The Dual-Game Approach

The core innovation of McXai is the conceptualization of explanation as two distinct games played within a feature state space:

  1. The Classification Game: The agent seeks to identify the minimal set of features required to maintain the model's correct classification. By iteratively "masking" features, the search uncovers the essential "skeleton" of the decision.
  2. The Misclassification Game: The agent searches for features to which the model is overly sensitive—specifically those that, when perturbed or highlighted, lead the model toward incorrect labels.
The McXai framework conceptualized as two strategic games (a) and applied to an image classification task (b), showing how specific features are isolated.

By using MCTS, the system explores the vast state space of feature combinations similarly to how an AI might explore moves in Chess or Go. Each node in the resulting tree represents a version of the input with specific features masked. The agent is rewarded based on a balance between the change in model confidence and the sparsity of the features used, naturally highlighting the most influential dependencies.

Key Insights and Model Debugging

McXai moves beyond traditional saliency maps (heatmaps) by producing a hierarchical tree. This allows users to see not just which feature is most important, but how secondary features become relevant if primary ones are removed.

A critical finding of the research is that models often fixate on "distractor" features—background patterns or irrelevant artifacts that do not belong to the target class. By identifying these via the Misclassification Game, McXai serves as a powerful debugger. The authors demonstrated that removing these misleading features from training data and retraining the model led to significant accuracy boosts. For instance, the MnasNet0_5 model improved from 87.78% to 89.16% accuracy when refined using McXai's insights.

Comparative Performance

The authors evaluated McXai across diverse datasets, including MNIST, Face, Dog-vs-Cat, and tabular data like Covertype. To quantify the quality of explanations, they measured the "efficiency" of the explanation—how many features must be removed to flip a model's prediction.

Comparison of McXai with LIME and SHAP on the MNIST dataset (a), and the corresponding MCTS exploration tree (b) showing feature importance weights.

In nearly all categories, McXai required significantly fewer steps than LIME or SHAP to identify the true influential features. Furthermore, McXai demonstrated superior stability; removing the misleading features it identified reduced performance variance, resulting in more reliable classifiers.

Limitations and Future Outlook

While powerful, McXai is computationally intensive. As an iterative process, analyzing a single high-resolution image can take several minutes, making it slower than simpler methods like LIME. To manage this, the current implementation often relies on "superpixels" or downsampled data to keep the search space manageable.

Future work aims to scale the search efficiency and explore the use of the Misclassification Game as a defense mechanism against adversarial attacks, identifying and neutralizing the specific feature sensitivities that attackers exploit.

Summary updated

BibTeX
@inproceedings{huang2023mcxai,
  author = {Yiran Huang and Nicole Schaal and Michael Hefenbrock and Yexu Zhou and Till Riedel and Likun Fang and Michael Beigl},
  title = {{McXai: Local model-agnostic explanation as two games}},
  booktitle = {IJCNN},
  year = {2023},
  doi = {10.1109/ijcnn54540.2023.10191756},
}
Figure