Proofs as Explanations: Short Certificates for Reliable Predictions

Explanations can be built from training data: The paper proposes that AI predictions can be explained by identifying a small subset of training examples that "prove" the prediction is correct—meaning any reasonable classifier trained on those examples would make the same prediction. For linear classifiers, this subset can be as small as d+1 examples (where d is the number of features).

Certificate size depends on the model and tolerance for errors: The paper introduces the concept of "robust hollow star number" to measure how large these proof sets need to be. This size varies depending on what type of classifier is used and how many mistakes in the training data are tolerated—providing a theoretical framework for understanding explanation complexity across different AI systems.

Shorter explanations are more trustworthy and practical: By characterizing the minimum possible size of these proof sets, the research shows that some AI systems can provide very concise explanations (small subsets of training data) while others require larger ones. Shorter certificates are more useful in practice because they're easier for humans to verify and understand.

The approach assumes clean data and correct model class: The method only works reliably if the training data contains few errors and if the true underlying pattern actually belongs to the model class being used. This highlights an important limitation: explanations are only as trustworthy as the data and model assumptions behind them.