Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations

• URL: http://arxiv.org/abs/2501.06078v1
• Date: Fri, 10 Jan 2025 16:14:35 GMT
• Title: Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations
• Authors: Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth, Bernardo Subercaseaux, José Verschae,
• Abstract summary: We argue that $barx$ explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features. We study abductive explanations such as "minimum sufficient reasons", which correspond to sets of features in $barx$ that are enough to guarantee its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations.
• Score: 48.13753926484667
• License:
• Abstract: Despite the wide use of $k$-Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neighbors classifiers offer interpretability from a "data perspective", in which the classification of an input vector $\bar{x}$ is explained by identifying the vectors $\bar{v}_1, \ldots, \bar{v}_k$ in the training set that determine the classification of $\bar{x}$, we argue that such explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features and it is not clear what their relative importance is. Hence, we focus on understanding nearest neighbor classifications through a "feature perspective", in which the goal is to identify how the values of the features in $\bar{x}$ affect its classification. Concretely, we study abductive explanations such as "minimum sufficient reasons", which correspond to sets of features in $\bar{x}$ that are enough to guarantee its classification, and "counterfactual explanations" based on the minimum distance feature changes one would have to perform in $\bar{x}$ to change its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations, distinguishing between discrete and continuous feature spaces, and considering the impact of the choice of distance function involved. Finally, we show that despite some negative complexity results, Integer Quadratic Programming and SAT solving allow for computing explanations in practice.

Related papers

• Repeated Observations for Classification [0.2676349883103404]
  We study the problem nonparametric classification with repeated observations. In the analysis, we investigate particular models like robust detection by nominal densities, prototype classification, linear transformation, linear classification, scaling.
  arXiv  Detail & Related papers  (2023-07-19T10:50:36Z)
• On Computing Probabilistic Abductive Explanations [30.325691263226968]
  The most widely studied explainable AI (XAI) approaches are unsound. PI-explanations also exhibit important drawbacks, the most visible of which is arguably their size. This paper investigates practical approaches for computing relevant sets for a number of widely used classifiers.
  arXiv  Detail & Related papers  (2022-12-12T15:47:10Z)
• Zero-Shot Classification by Logical Reasoning on Natural Language Explanations [56.42922904777717]
  We propose the framework CLORE (Classification by LOgical Reasoning on Explanations) CLORE parses explanations into logical structures and then explicitly reasons along thess structures on the input to produce a classification score. We also demonstrate that our framework can be extended to zero-shot classification on visual modality.
  arXiv  Detail & Related papers  (2022-11-07T01:05:11Z)
• Don't Explain Noise: Robust Counterfactuals for Randomized Ensembles [50.81061839052459]
  We formalize the generation of robust counterfactual explanations as a probabilistic problem. We show the link between the robustness of ensemble models and the robustness of base learners. Our method achieves high robustness with only a small increase in the distance from counterfactual explanations to their initial observations.
  arXiv  Detail & Related papers  (2022-05-27T17:28:54Z)
• Obstructing Classification via Projection [2.456909016197174]
  We study a geometric problem which models a possible approach for bias removal. A priori we assume that it is "easy" to classify the data according to each property. Our goal is to obstruct the classification according to one property by a suitable projection to a lower-dimensional Euclidean space Rm.
  arXiv  Detail & Related papers  (2021-05-19T10:28:15Z)
• Contrastive Explanations for Model Interpretability [77.92370750072831]
  We propose a methodology to produce contrastive explanations for classification models. Our method is based on projecting model representation to a latent space. Our findings shed light on the ability of label-contrastive explanations to provide a more accurate and finer-grained interpretability of a model's decision.
  arXiv  Detail & Related papers  (2021-03-02T00:36:45Z)
• Counterfactual Explanations for Oblique Decision Trees: Exact, Efficient Algorithms [0.0]
  We consider counterfactual explanations, the problem of minimally adjusting features in a source input instance so that it is classified as a target class under a given classification. This has become a topic of recent interest as a way to query a trained model and suggest possible actions to overturn its decision.
  arXiv  Detail & Related papers  (2021-03-01T16:04:33Z)
• The Struggles of Feature-Based Explanations: Shapley Values vs. Minimal Sufficient Subsets [61.66584140190247]
  We show that feature-based explanations pose problems even for explaining trivial models. We show that two popular classes of explainers, Shapley explainers and minimal sufficient subsets explainers, target fundamentally different types of ground-truth explanations.
  arXiv  Detail & Related papers  (2020-09-23T09:45:23Z)
• SCOUT: Self-aware Discriminant Counterfactual Explanations [78.79534272979305]
  The problem of counterfactual visual explanations is considered. A new family of discriminant explanations is introduced. The resulting counterfactual explanations are optimization free and thus much faster than previous methods.
  arXiv  Detail & Related papers  (2020-04-16T17:05:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.