Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option

• URL: http://arxiv.org/abs/2603.14096v1
• Date: Sat, 14 Mar 2026 19:45:37 GMT
• Title: Concisely Explaining the Doubt: Minimum-Size Abductive Explanations for Linear Models with a Reject Option
• Abstract summary: In critical domains such as healthcare and finance, a reject option allows the model to abstain when evidence is insufficient.<n>In these settings, explanations must not only be interpretable, but also faithful to the underlying model.<n>In this work, we bridge these lines of research by computing minimum-size abductive explanations for linear models with a reject option.
• Score: 1.1470070927586018
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Trustworthiness in artificial intelligence depends not only on what a model decides, but also on how it handles and explains cases in which a reliable decision cannot be made. In critical domains such as healthcare and finance, a reject option allows the model to abstain when evidence is insufficient, making it essential to explain why an instance is rejected in order to support informed human intervention. In these settings, explanations must not only be interpretable, but also faithful to the underlying model and computationally efficient enough to support real-time decision making. Abductive explanations guarantee fidelity, but their exact computation is known to be NP-hard for many classes of models, limiting their practical applicability. Computing \textbf{minimum-size} abductive explanations is an even more challenging problem, as it requires reasoning not only about fidelity but also about optimality. Prior work has addressed this challenge in restricted settings, including log-linear-time algorithms for computing minimum-size abductive explanations in linear models without rejection, as well as a polynomial-time method based on linear programming for computing abductive explanations, without guarantees of minimum size, for linear models with a reject option. In this work, we bridge these lines of research by computing minimum-size abductive explanations for linear models with a reject option. For accepted instances, we adapt the log-linear algorithm to efficiently compute optimal explanations. For rejected instances, we formulate a 0-1 integer linear programming problem that characterizes minimum-size abductive explanations of rejection. Although this formulation is NP-hard in theory, our experimental results show that it is consistently more efficient in practice than the linear-programming-based approach that does not guarantee minimum-size explanations.

Related papers

• WENDy for Nonlinear-in-Parameters ODEs [2.066079080612853]
  WENDy-MLE approximates a maximum likelihood estimator via local non- convergence optimization methods.<n>WENDy-MLE has better accuracy, a substantially larger domain of convergence, and often is faster than other weak form methods and the conventional output error least squares method.<n>We present extensive numerical results comparing our method, other weak form methods, and output error least squares on a suite of benchmark systems of ODEs.
  arXiv  Detail & Related papers  (2025-02-13T01:40:21Z)
• Learning Model Agnostic Explanations via Constraint Programming [8.257194221102225]
  Interpretable Machine Learning faces a recurring challenge of explaining predictions made by opaque classifiers in terms that are understandable to humans. In this paper, the task is framed as a Constraint Optimization Problem, where the constraint solver seeks an explanation of minimum error and bounded size for an input data instance and a set of samples generated by the black box. We evaluate the approach empirically on various datasets and show that it statistically outperforms the state-of-the-art Anchors method.
  arXiv  Detail & Related papers  (2024-11-13T09:55:59Z)
• Logic-based Explanations for Linear Support Vector Classifiers with Reject Option [0.0]
  Support Vector (SVC) is a well-known Machine Learning (ML) model for linear classification problems. We propose a logic-based approach with formal guarantees on the correctness and minimality of explanations for linear SVCs with reject option.
  arXiv  Detail & Related papers  (2024-03-24T15:14:44Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• From Robustness to Explainability and Back Again [3.7950144463212134]
  This paper addresses the poor scalability of formal explainability and proposes novel efficient algorithms for computing formal explanations.<n>The proposed algorithm computes explanations by answering instead a number of queries, and such robustness that the number of such queries is at most linear on the number of features.
  arXiv  Detail & Related papers  (2023-06-05T17:21:05Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  It is common to address the curse of dimensionality in Markov decision processes (MDPs) by exploiting low-rank representations. We consider an alternative definition of linear MDPs that automatically ensures normalization while allowing efficient representation learning. We demonstrate superior performance over existing state-of-the-art model-based and model-free algorithms on several benchmarks.
  arXiv  Detail & Related papers  (2022-07-14T18:18:02Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  parameter-free algorithms are online learning algorithms that do not require setting learning rates. We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
  arXiv  Detail & Related papers  (2022-03-19T13:39:49Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Linear Adversarial Concept Erasure [108.37226654006153]
  We formulate the problem of identifying and erasing a linear subspace that corresponds to a given concept.<n>We show that the method is highly expressive, effectively mitigating bias in deep nonlinear classifiers while maintaining tractability and interpretability.
  arXiv  Detail & Related papers  (2022-01-28T13:00:17Z)
• $\partial$-Explainer: Abductive Natural Language Inference via Differentiable Convex Optimization [2.624902795082451]
  This paper presents a novel framework named $partial$-Explainer (Diff-Explainer) that combines the best of both worlds by casting the constrained optimization as part of a deep neural network. Our experiments show up to $approx 10%$ improvement over non-differentiable solver while still providing explanations for supporting its inference.
  arXiv  Detail & Related papers  (2021-05-07T17:49:19Z)
• Causality-based Counterfactual Explanation for Classification Models [11.108866104714627]
  We propose a prototype-based counterfactual explanation framework (ProCE) ProCE is capable of preserving the causal relationship underlying the features of the counterfactual data. In addition, we design a novel gradient-free optimization based on the multi-objective genetic algorithm that generates the counterfactual explanations.
  arXiv  Detail & Related papers  (2021-05-03T09:25:59Z)
• Non-parametric Models for Non-negative Functions [48.7576911714538]
  We provide the first model for non-negative functions from the same good linear models. We prove that it admits a representer theorem and provide an efficient dual formulation for convex problems.
  arXiv  Detail & Related papers  (2020-07-08T07:17:28Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  We present a novel approach to formulate different notions of causal reasoning, over binary acyclic models, as optimization problems. We show that both notions are efficiently automated. Using models with more than $8000$ variables, checking is computed in a matter of seconds, with MaxSAT outperforming ILP in many cases.
  arXiv  Detail & Related papers  (2020-06-05T10:56:52Z)

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.