Understanding Post-hoc Explainers: The Case of Anchors

Gianluigi Lopardo, Frédéric Precioso, Damien GarreauarXiv 2023 · OpenReview

Abstract

In many scenarios, the interpretability of machine learning models is a highly required but difficult task. To explain the individual predictions of such models, local model-agnostic approaches have been proposed. However, the process generating the explanations can be, for a user, as mysterious as the prediction to be explained. Furthermore, interpretability methods frequently lack theoretical guarantees, and their behavior on simple models is frequently unknown. While it is difficult, if not impossible, to ensure that an explainer behaves as expected on a cutting-edge model, we can at least ensure that everything works on simple, already interpretable models. In this paper, we present a theoretical analysis of Anchors (Ribeiro et al., 2018): a popular rule-based interpretability method that highlights a small set of words to explain a text classifier's decision. After formalizing its algorithm and providing useful insights, we demonstrate mathematically that Anchors produces meaningful results when used with linear text classifiers on top of a TF-IDF vectorization. We believe that our analysis framework can aid in the development of new explainability methods based on solid theoretical foundations.

Introduction: The Transparency Gap in XAI

As machine learning models become increasingly complex, the need for transparency has led to the development of "post-hoc" explainers. Tools such as LIME, SHAP, and Anchors are designed to sit atop pre-trained models to clarify their decision-making processes. Specifically, Anchors seeks to identify a "rule"—a minimal set of features (e.g., specific words) that, when present, ensure the model maintains its prediction with high probability.

Example of an Anchor explanation for a sentiment classifier, showing highlighted words and associated precision/coverage metrics.

However, a fundamental problem persists: the mathematical validity of these explainers is often unproven. If an explainer cannot reliably identify the most influential features in a transparent linear model, its utility for complex architectures like large language models is questionable. This research addresses this gap by providing a formal theoretical framework for analyzing Anchors' behavior on linear text classifiers.

Methodology: Formalization and Linear Analysis

The study adopts a two-pronged approach to evaluate the Anchors algorithm:

  1. Exhaustive $p$-Anchors: While the original algorithm utilizes a multi-armed bandit approach (KL-LUCB) for efficiency, the authors define an "exhaustive" version. This version considers all possible feature combinations to identify the theoretically optimal anchor, making the mathematical analysis tractable.
  2. Linear Model Framework: The analysis focuses on binary linear classifiers (e.g., Logistic Regression) utilizing TF-IDF vectorization.
  3. Probabilistic Approximation: To calculate "precision"—the likelihood that a text perturbation preserves the prediction—the authors employ a Berry-Esseen-type statement. This allows the complex probability of a prediction to be approximated using the cumulative distribution function (CDF) of a standard normal distribution.
  4. Sampling Dynamics: The research analyzes the default "UNK-replacement" sampling method, where features outside the anchor are replaced by a special unknown token, effectively neutralizing their impact on the model.

Theoretical Insights

The formal analysis yielded several critical findings regarding the behavior of Anchors on linear models:

  • Positive Influence Guarantee: Mathematically, Anchors is guaranteed to retain only words that positively influence the prediction. It will not erroneously highlight a "negative" word as a justification for a "positive" classification in a linear context.
  • Greedy Selection Logic: The algorithm prioritizes words based on their "weighted impact" ($\lambda_j v_j$), where $\lambda$ represents the model weight and $v$ is the TF-IDF score. It constructs explanations by iteratively selecting the most impactful words until the precision threshold is satisfied.
  • Precision-Coverage Trade-off: The paper formalizes the inherent tension between "coverage" (how broadly the rule applies) and "precision" (the certainty of the prediction). Anchors aims for the shortest word list that maintains high precision.

Empirical Results and Validation

The theoretical predictions were validated against empirical data from three sentiment analysis datasets: Restaurant Reviews, Yelp Reviews, and IMDB Movie Reviews. Logistic regression models were trained on these datasets, achieving accuracies between 85% and 88%.

Theoretical feature ordering and Jaccard similarity results comparing the Anchors software output to the theoretically optimal anchors.

The researchers measured the Jaccard Similarity between the words selected by the Anchors software and the "theoretically optimal" words derived from their analysis. In scenarios where the model was less confident (e.g., $P < 0.75$), the similarity was remarkably high, reaching 0.82 for the Restaurant dataset and 0.80 for Yelp. These results confirm that the algorithm effectively identifies the minimal set of words with the highest positive coefficients, as predicted by the paper's theoretical propositions.

Limitations and Future Directions

While this work establishes a vital "sanity check" for XAI, it acknowledges certain constraints:

  • Model Linearity: The current proofs are limited to linear models, which do not fully capture the nuances of deep neural networks.
  • Binary Scope: The analysis is restricted to binary classification tasks.
  • Anchor Constraints: The proofs assume the anchor length is less than half the total document length.

Future research will focus on extending this analytical framework to non-linear models, such as decision trees and neural networks, and exploring its applicability to image and tabular data. By grounding explainability in solid theory, this work paves the way for more reliable and trustworthy AI systems.

Summary updated

Abstract

In many scenarios, the interpretability of machine learning models is a highly required but difficult task. To explain the individual predictions of such models, local model-agnostic approaches have been proposed. However, the process generating the explanations can be, for a user, as mysterious as the prediction to be explained. Furthermore, interpretability methods frequently lack theoretical guarantees, and their behavior on simple models is frequently unknown. While it is difficult, if not impossible, to ensure that an explainer behaves as expected on a cutting-edge model, we can at least ensure that everything works on simple, already interpretable models. In this paper, we present a theoretical analysis of Anchors (Ribeiro et al., 2018): a popular rule-based interpretability method that highlights a small set of words to explain a text classifier's decision. After formalizing its algorithm and providing useful insights, we demonstrate mathematically that Anchors produces meaningful results when used with linear text classifiers on top of a TF-IDF vectorization. We believe that our analysis framework can aid in the development of new explainability methods based on solid theoretical foundations.
BibTeX
@misc{lopardo2023understanding,
  author = {Gianluigi Lopardo and Frédéric Precioso and Damien Garreau},
  title = {{Understanding Post-hoc Explainers: The Case of Anchors}},
  year = {2023},
  eprint = {2303.08806},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.08806},
}
Figure