TL;DR
While most Explainable AI (XAI) focuses on why a model made a specific prediction, this paper tackles a neglected question: Why did the model refuse to make a prediction at all? The authors propose a framework using counterfactual explanations to explain "reject options" in Learning Vector Quantization (LVQ) classifiers, providing users with actionable feedback on what would need to change for the model to feel certain enough to classify an input.
What Problem Does This Paper Address?
In safety-critical fields like medicine or autonomous driving, "I don't know" is often a better answer than a wrong guess. Many machine learning models use reject options—mechanisms that allow the model to withhold a prediction if the input is too ambiguous (near a decision boundary) or too "weird" (out-of-distribution).
However, a rejection without an explanation is frustrating and unhelpful. If a diagnostic tool rejects a patient's data, the clinician needs to know if it's because the data is corrupted, or if the patient presents a borderline case that requires a specialist. Despite the explosion of XAI research, explaining why a sample was rejected has been almost entirely overlooked. This paper fills that gap for prototype-based models.
Methods
The authors focus on Learning Vector Quantization (LVQ), a class of models that classify data by comparing inputs to "prototypes" (representative points in the feature space). They investigate three common reject strategies:
- Relative Similarity (RelSim): Rejects if the distance to the closest prototype is too similar to the distance to the second-closest prototype of a different class.
- Decision Boundary Distance: Rejects if the sample is physically too close to the hyperplane separating two classes.
- Probabilistic Certainty: Rejects if the estimated class probability falls below a threshold.
To explain these rejects, the authors use Counterfactual Explanations. A counterfactual answer looks like: "If feature X were 0.5 units higher, the model would have accepted this input and classified it as Class A."
The technical core of the paper involves formulating these explanations as optimization problems. They show that for RelSim and Boundary Distance, the "closest" counterfactual can be found efficiently using Convex Quadratic Programming and Linear Programming. For the more complex Probabilistic Certainty, they propose a convex approximation that guarantees a valid explanation even when the underlying probability function is "ugly" and non-convex.
Datasets
The researchers evaluated their algorithms on four diverse datasets:
- Wine: A small dataset for predicting wine cultivators (13 features).
- Breast Cancer: Classifying samples as benign or malignant (30 features).
- Flip: A medical dataset for predicting liver fibrosis (12 features).
- T21: A large, highly imbalanced dataset (50,000+ samples) for early diagnosis of chromosomal abnormalities in pregnancy.
Key Insights and Ideas
- Sparsity Equals Interpretability: The authors use an $L_1$-norm in their optimization. This forces the explanation to change as few features as possible. A "simple" explanation (changing one or two variables) is much more useful to a human than one that tweaks 30 variables simultaneously.
- Rejects are not Predictions: Explaining a reject is mathematically different from explaining a class. You aren't moving the point to a new class; you are moving it into the "certainty zone" of any class.
- Efficiency via Divide-and-Conquer: Because LVQ models are based on discrete prototypes, the authors can break the global problem into many smaller, convex sub-problems (one for each prototype), ensuring they find the globally optimal explanation.
Key Results
- Superior Sparsity: The proposed specialized algorithms consistently found much sparser explanations (fewer changed features) compared to "black-box" solvers or simply looking for the nearest accepted sample in the training data.
- Ground Truth Recovery: In a "goodness" test, the authors intentionally perturbed specific features to trigger a reject. Their counterfactual algorithms were able to identify and "fix" those exact features in the explanation nearly 100% of the time for most datasets.
- Reliability: Unlike general-purpose black-box explanation tools, the proposed convex optimization approach is guaranteed to find a valid counterfactual if one exists.
Limitations and Future Work
- Model Specificity: The current math is tailored specifically to LVQ and prototype-based models. While the concept of explaining rejects is general, the specific algorithms aren't directly applicable to Deep Neural Networks or Random Forests without further derivation.
- The "Human" Factor: While the authors measure "goodness" via feature recovery and sparsity, they acknowledge that a proper user study is needed to confirm if these specific counterfactuals are actually helpful to practitioners in the field.
- Complexity Trade-offs: Their most accurate algorithm for probabilistic rejects has quadratic complexity relative to the number of classes, which might become a bottleneck for datasets with hundreds of categories.
Summary updated