Counterfactual Explanations for Linear Optimization

• URL: http://arxiv.org/abs/2405.15431v1
• Date: Fri, 24 May 2024 10:58:00 GMT
• Title: Counterfactual Explanations for Linear Optimization
• Authors: Jannis Kurtz, Ş. İlker Birbil, Dick den Hertog,
• Abstract summary: The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs appears to be computationally intractable, we show that calculating relative CEs can be done efficiently. By detecting and exploiting the hidden convex structure of the optimization problem that arises in the latter case, we show that obtaining relative CEs can be done in the same magnitude of time as solving the original linear optimization problem. This is confirmed by an extensive numerical experiment study on the NETLIB library.

Related papers

• Introducing User Feedback-based Counterfactual Explanations (UFCE) [49.1574468325115]
  Counterfactual explanations (CEs) have emerged as a viable solution for generating comprehensible explanations in XAI. UFCE allows for the inclusion of user constraints to determine the smallest modifications in the subset of actionable features. UFCE outperforms two well-known CE methods in terms of textitproximity, textitsparsity, and textitfeasibility.
  arXiv  Detail & Related papers  (2024-02-26T20:09:44Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation [19.065904250532995]
  We propose Provably RObust and PLAusible Counterfactual Explanations (PROPLACE) We formulate an iterative algorithm to compute provably robust CEs and prove its convergence, soundness and completeness. We show that PROPLACE achieves state-of-the-art performances against metrics on three evaluation aspects.
  arXiv  Detail & Related papers  (2023-09-22T00:12:09Z)
• Counterfactual Explanation via Search in Gaussian Mixture Distributed Latent Space [19.312306559210125]
  Counterfactual Explanations (CEs) are an important tool in Algorithmic Recourse for addressing two questions. guiding the user's interaction with AI systems by proposing easy-to-understand explanations is essential for the trustworthy adoption and long-term acceptance of AI systems. We introduce a new method to generate CEs for a pre-trained binary classifier by first shaping the latent space of an autoencoder to be a mixture of Gaussian distributions.
  arXiv  Detail & Related papers  (2023-07-25T10:21:26Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Finding Regions of Counterfactual Explanations via Robust Optimization [0.0]
  A counterfactual explanation (CE) is a minimal perturbed data point for which the decision of the model changes. Most of the existing methods can only provide one CE, which may not be achievable for the user. We derive an iterative method to calculate robust CEs that remain valid even after the features are slightly perturbed.
  arXiv  Detail & Related papers  (2023-01-26T14:06:26Z)
• Counterfactual Explanations Using Optimization With Constraint Learning [0.0]
  We propose a generic and flexible approach to counterfactual explanations using optimization with constraint learning (CE-OCL) Specifically, we discuss how we can leverage an optimization with constraint learning framework for the generation of counterfactual explanations. We also propose two novel modeling approaches to address data manifold closeness and diversity, which are two key criteria for practical counterfactual explanations.
  arXiv  Detail & Related papers  (2022-09-22T13:27:21Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• Generating Interpretable Counterfactual Explanations By Implicit Minimisation of Epistemic and Aleatoric Uncertainties [24.410724285492485]
  We introduce a simple and fast method for generating interpretable CEs in a white-box setting without an auxiliary model. Our experiments show that our proposed algorithm generates more interpretable CEs, according to IM1 scores, than existing methods.
  arXiv  Detail & Related papers  (2021-03-16T10:20:24Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

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.