Accelerating the Global Aggregation of Local Explanations

Alon Mor, Yonatan Belinkov, Benny Kimelfeld

Abstract

Local explanation methods highlight the input tokens that have a considerable impact on the outcome of classifying the document at hand. For example, the Anchor algorithm applies a statistical analysis of the sensitivity of the classifier to changes in the token. Aggregating local explanations over a dataset provides a global explanation of the model. Such aggregation aims to detect words with the most impact, giving valuable insights about the model, like what it has learned in training and which adversarial examples expose its weaknesses. However, standard aggregation methods bear a high computational cost: a naive implementation applies a costly algorithm to each token of each document, and hence, it is infeasible for a simple user running in the scope of a short analysis session. We devise techniques for accelerating the global aggregation of the Anchor algorithm. Specifically, our goal is to compute a set of top-k words with the highest global impact according to different aggregation functions. Some of our techniques are lossless and some are lossy. We show that for a very mild loss of quality, we are able to accelerate the computation by up to 30 times, reducing the computation from hours to minutes. We also devise and study a probabilistic model that accounts for noise in the Anchor algorithm and diminishes the bias toward words that are frequent yet low in impact.

Introduction

Understanding the decision-making process of complex machine learning models, particularly large language models, is a critical challenge in AI safety and interpretability. Local explanation methods, such as the Anchor algorithm, identify specific "anchor" tokens that are sufficient to lock in a model's prediction. While local explanations are useful for debugging individual instances, researchers often require global explanations—a ranked list of the most impactful words across an entire dataset—to understand the model's general learned heuristics.

However, generating global explanations is computationally prohibitive. A perturbation-based method like Anchor requires testing thousands of document variations, making it infeasible for large datasets in real-time analysis sessions. Furthermore, simple aggregation strategies (e.g., summing occurrences) often fail to distinguish between meaningful features and frequent "stop words."

Methodology

We propose a framework that combines a novel statistical aggregation model with several algorithmic optimizations to accelerate the discovery of global explanations.

Probabilistic Global Aggregation ($G_{pr}$)

To address the noise inherent in simple counting methods, we introduce a probability-based aggregation function, $G_{pr}$. We model the dataset as being generated by two distinct distributions: one for "anchors" ($q$) and one for "background" words ($p$). By applying Maximum Likelihood Estimation (MLE), we can identify words that have the highest probability of being true anchors while filtering out frequent but non-impactful noise.

Comparison of various aggregation functions across multiple datasets. The proposed $G_{pr}$ (black line) consistently achieves high AOPC scores across different values of $k$.

Runtime Optimizations

Our acceleration techniques include:

  • Anytime Algorithm: The system maintains a running top-$k$ list, providing immediate feedback to the user that improves as more data is processed.
  • Candidate Filtering: We use optimistic upper bounds to prune words that cannot mathematically reach the top-$k$ list, skipping expensive local explanation steps.
  • Hyperparameter Tuning: We found that the global aggregation is robust to noise in individual local explanations. By lowering the precision and confidence requirements of the Anchor algorithm, we achieve massive speedups with minimal impact on global quality.
  • Masking Optimization: Reducing the number of suggestions from the Masked Language Model (DistilBERT) during the perturbation phase significantly cuts computation time.

Evaluation and Results

We evaluated our approach on four text classification tasks from Kaggle, including sentiment analysis and spam detection.

Speed and Quality Trade-offs

The optimized "anytime" approach achieved up to a 30x speedup, reducing computation time from over an hour to approximately two minutes. Despite this acceleration, the quality of the explanations—measured by the Area Over the Perturbation Curve (AOPC)—remains high. AOPC measures the drop in model confidence when top-ranked words are removed; a steeper curve indicates more impactful global features.

Quality (AOPC) as a function of computation time. The proposed optimized method (red line) reaches peak quality significantly faster than standard sum and average baselines.

Key Insights

  • Robustness to Local Noise: Perfect local explanations are not a prerequisite for accurate global insights. Aggregation naturally filters out the noise introduced by faster, less precise local searches.
  • Feature Influence: Counterfactual tests confirmed the influence of the identified words. Appending the top-10 words found by $G_{pr}$ to documents of the opposite class caused model accuracy to drop by approximately 50%.

Conclusion

This work demonstrates that global model explanations can be computed efficiently without sacrificing interpretability. By leveraging probabilistic modeling and targeted algorithmic optimizations, we enable real-time global analysis of black-box models. Future work will explore extending these techniques to multi-word phrases and non-textual data modalities.

Summary updated

Abstract

Local explanation methods highlight the input tokens that have a considerable impact on the outcome of classifying the document at hand. For example, the Anchor algorithm applies a statistical analysis of the sensitivity of the classifier to changes in the token. Aggregating local explanations over a dataset provides a global explanation of the model. Such aggregation aims to detect words with the most impact, giving valuable insights about the model, like what it has learned in training and which adversarial examples expose its weaknesses. However, standard aggregation methods bear a high computational cost: a naive implementation applies a costly algorithm to each token of each document, and hence, it is infeasible for a simple user running in the scope of a short analysis session. We devise techniques for accelerating the global aggregation of the Anchor algorithm. Specifically, our goal is to compute a set of top-k words with the highest global impact according to different aggregation functions. Some of our techniques are lossless and some are lossy. We show that for a very mild loss of quality, we are able to accelerate the computation by up to 30 times, reducing the computation from hours to minutes. We also devise and study a probabilistic model that accounts for noise in the Anchor algorithm and diminishes the bias toward words that are frequent yet low in impact.
BibTeX
@inproceedings{mor2024accelerating,
  author = {Alon Mor and Yonatan Belinkov and Benny Kimelfeld},
  title = {{Accelerating the Global Aggregation of Local Explanations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=xyQXc7cBqy},
}
Figure