Evaluating the Correctness of Explainable AI Algorithms for Classification

Orcun Yalcin, Xiuyi Fan, Siyuan LiuarXiv 2021 · OpenReview

Abstract

Explainable AI has attracted much research attention in recent years with feature attribution algorithms, which compute "feature importance" in predictions, becoming increasingly popular. However, there is little analysis of the validity of these algorithms as there is no "ground truth" in the existing datasets to validate their correctness. In this work, we develop a method to quantitatively evaluate the correctness of XAI algorithms by creating datasets with known explanation ground truth. To this end, we focus on the binary classification problems. String datasets are constructed using formal language derived from a grammar. A string is positive if and only if a certain property is fulfilled. Symbols serving as explanation ground truth in a positive string are part of an explanation if and only if they contributes to fulfilling the property. Two popular feature attribution explainers, Local Interpretable Model-agnostic Explanations (LIME) and SHapley Additive exPlanations (SHAP), are used in our experiments. We show that: (1) classification accuracy is positively correlated with explanation accuracy; (2) SHAP provides more accurate explanations than LIME; (3) explanation accuracy is negatively correlated with dataset complexity.

Introduction

The proliferation of "black-box" machine learning models has led to a surge in Explainable AI (XAI) techniques. Methods like LIME and SHAP are frequently employed to provide feature attribution, identifying which inputs most heavily influence a model's decision. However, a fundamental challenge remains: how do we know if these explanations are actually correct? In real-world datasets, we lack an objective "ground truth" for feature importance, often relying on subjective human intuition for validation. This paper introduces a framework to generate synthetic datasets with mathematically defined explanation ground truth using formal grammars.

Methodology: The E-Grammar Framework

To create a benchmark for XAI correctness, the authors propose the Explanation-Grammar (e-grammar). This approach generates string datasets where the classification label is tied to the internal structure of the string's derivation.

Data Generation and Labeling

Strings are generated based on a set of production rules. A string is labeled as "Positive" (POS) if a specific target production rule is triggered more than a predefined threshold $t$. The terminal symbols produced by these specific rule applications constitute the "ground truth" explanation for that instance.

Parse trees for two different strings generated by the same formal grammar.

By tracking the number of times each rule is used during the generation of a string, we can objectively determine its label and the specific features (symbols) responsible for that label.

Production rule usage counts for a generated string, used to determine ground truth labels.

Measuring Complexity and Accuracy

The study introduces Grammatical Complexity (G-complexity), defined as the total number of production rules in the grammar. This allows for controlled experiments on how structural complexity affects XAI performance. To evaluate the explainers, the authors use k-accuracy, which measures the overlap between the top $k$ features identified by the explainer and the $k$ ground truth features.

Experimental Results

The researchers compared two prominent XAI algorithms: Local Interpretable Model-agnostic Explanations (LIME) and SHapley Additive exPlanations (SHAP).

SHAP vs. LIME

Across various synthetic datasets, SHAP (specifically TreeSHAP) consistently outperformed LIME. SHAP's explanations were found to be 26% to 49% more accurate than LIME's. This superiority is likely due to SHAP's theoretical foundation in game theory, which ensures a more consistent distribution of feature importance.

The Impact of Complexity

A key finding is the strong negative correlation (often $r < -0.90$) between dataset complexity and explanation accuracy. As the number of rules in the grammar increases, it becomes significantly harder for XAI tools to pinpoint the correct features. Notably, explanation accuracy often declines more rapidly than classification accuracy, suggesting that models can learn to predict correctly even when the underlying reasons become too complex for current XAI tools to extract reliably.

Correlation with Model Performance

The study also observed a positive correlation between classification accuracy and explanation accuracy. This implies that an explainer's ability to provide a "correct" reason is fundamentally limited by the model's own understanding of the data patterns.

Conclusion

This work provides a much-needed quantitative benchmark for evaluating XAI algorithms. By using formal grammars to create datasets with known ground truth, the authors demonstrate that SHAP is generally more reliable than LIME, but both methods struggle as data complexity grows. Future work will involve extending this framework to continuous data and conducting human validation studies to align grammatical ground truth with human interpretability.

Summary updated

Abstract

Explainable AI has attracted much research attention in recent years with feature attribution algorithms, which compute "feature importance" in predictions, becoming increasingly popular. However, there is little analysis of the validity of these algorithms as there is no "ground truth" in the existing datasets to validate their correctness. In this work, we develop a method to quantitatively evaluate the correctness of XAI algorithms by creating datasets with known explanation ground truth. To this end, we focus on the binary classification problems. String datasets are constructed using formal language derived from a grammar. A string is positive if and only if a certain property is fulfilled. Symbols serving as explanation ground truth in a positive string are part of an explanation if and only if they contributes to fulfilling the property. Two popular feature attribution explainers, Local Interpretable Model-agnostic Explanations (LIME) and SHapley Additive exPlanations (SHAP), are used in our experiments.We show that: (1) classification accuracy is positively correlated with explanation accuracy; (2) SHAP provides more accurate explanations than LIME; (3) explanation accuracy is negatively correlated with dataset complexity.
BibTeX
@misc{yalcin2021evaluating,
  author = {Orcun Yalcin and Xiuyi Fan and Siyuan Liu},
  title = {{Evaluating the Correctness of Explainable AI Algorithms for Classification}},
  year = {2021},
  eprint = {2105.09740},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.09740},
}
Figure