Merlin-Arthur Classifiers

Interpretable multi-agent classifiers with provable guarantees on feature relevance, inspired by interactive proof systems.

Merlin-Arthur Classifiers
Interpretability Guarantees with Merlin-Arthur Classifiers
AISTATS 2024
Paper Code Poster
Stephan Wäldchen
Stephan Wäldchen1
Kartikey Sharma
Kartikey Sharma1
Berkant Turan
Berkant Turan1
Max Zimmer
Max Zimmer1
Sebastian Pokutta
Sebastian Pokutta1
1 Zuse Institute Berlin & TU Berlin

Abstract

We propose an interactive multi-agent classifier that provides provable interpretability guarantees even for complex agents such as neural networks. These guarantees consist of lower bounds on the mutual information between selected features and the classification decision. Our results are inspired by the Merlin-Arthur protocol from Interactive Proof Systems and express these bounds in terms of measurable metrics such as soundness and completeness. Compared to existing interactive setups, we rely neither on optimal agents nor on the assumption that features are distributed independently. Instead, we use the relative strength of the agents as well as the new concept of Asymmetric Feature Correlation, which captures the precise kind of correlations that make interpretability guarantees difficult.

Method

The Merlin-Arthur setup: Merlin (Prover) selects a subset of features; Arthur (Verifier) classifies based solely on those features. The interaction yields provable mutual information lower bounds.

BibTeX

@InProceedings{pmlr-v238-waldchen24a,
  title     = {Interpretability Guarantees with {M}erlin-{A}rthur Classifiers},
  author    = {W\"{a}ldchen, Stephan and Sharma, Kartikey and Turan, Berkant and Zimmer, Max and Pokutta, Sebastian},
  booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
  pages     = {1963--1971},
  year      = {2024},
  volume    = {238},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR}
}