Explaining abstention, not just predictions: MINABRO computes minimum-size abductive explanations for linear models with a reject option
Synopsis
Linear classifiers with a reject option abstain when evidence is insufficient, but no method previously guaranteed both faithful and minimum-size explanations for those abstentions. MINABRO keeps a greedy ordering for classified instances, yielding minimum-size abductive explanations in O(n log n) time over bounded feature domains, and formulates rejected instances as a 0–1 integer linear program. Across ten public datasets it ran faster than the sampling-based Anchors and the linear-programming AbLinRO, even while solving the NP-hard rejection form.
Interpretation
A linear classifier with a reject option can now give provably minimum-size abductive explanations for abstained instances, not merely some irredundant feature subset. Earlier logic-based explanation methods covered linear models without rejection, or gave explanations for linear models with rejection without a minimum-size guarantee. On ten public binary classification datasets from UCI and OpenML, MINABRO was compared with two reference methods, Anchors and AbLinRO; MINABRO and AbLinRO both guarantee fidelity to the model, and only MINABRO guarantees minimum explanation size.
Explanations for classified instances come from a single sort: each feature is ranked by how much fixing it raises the worst-case score, and features are added until the rejection threshold is crossed. A log-linear-time greedy algorithm already existed for linear models without rejection, but its criterion was the standard decision boundary at 0 rather than the positive rejection threshold. The greedy procedure computes each feature's gain in O(n), sorts in O(n log n), and scans for the shortest feasible prefix, giving overall O(n log n) complexity.
Explanations for rejected instances are written as a 0–1 integer linear program: binary variables mark whether a feature is fixed, and the objective minimizes the number of fixed features. Rejection requires the score to stay above the lower threshold and below the upper threshold, so both the worst-case maximum and minimum scores must be constrained. The formulation is NP-hard in theory, yet in experiments MINABRO remained faster on rejected instances than AbLinRO, which calls a linear-programming solver repeatedly, once per feature.
Perspective
The demonstrated scope is linear classifiers with a reject option, with feature values scaled to [0,1] and treated as bounded domains; experiments use logistic regression on ten public binary classification datasets, and the authors list multiclass settings, inflated abductive explanations and local linear surrogates with a reject option for deep networks as future work.
Explanations for rejected instances are on average larger than those for classified instances on most datasets, because they must satisfy both score bounds at once; the rejection formulation remains NP-hard in theory, and its practical speed is an experimental observation rather than a complexity guarantee.
