One-for-many Counterfactual Explanations by Column Generation

• URL: http://arxiv.org/abs/2402.09473v1
• Date: Mon, 12 Feb 2024 10:03:31 GMT
• Title: One-for-many Counterfactual Explanations by Column Generation
• Authors: Andrea Lodi and Jasone Ram\'irez-Ayerbe
• Abstract summary: We consider the problem of generating a set of counterfactual explanations for a group of instances. For the first time, we solve the problem of minimizing the number of explanations needed to explain all the instances. A novel column generation framework is developed to efficiently search for the explanations.
• Score: 10.722820966396192
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we consider the problem of generating a set of counterfactual explanations for a group of instances, with the one-for-many allocation rule, where one explanation is allocated to a subgroup of the instances. For the first time, we solve the problem of minimizing the number of explanations needed to explain all the instances, while considering sparsity by limiting the number of features allowed to be changed collectively in each explanation. A novel column generation framework is developed to efficiently search for the explanations. Our framework can be applied to any black-box classifier, like neural networks. Compared with a simple adaptation of a mixed-integer programming formulation from the literature, the column generation framework dominates in terms of scalability, computational performance and quality of the solutions.

Related papers

• Generating collective counterfactual explanations in score-based classification via mathematical optimization [4.281723404774889]
  A counterfactual explanation of an instance indicates how this instance should be minimally modified so that the perturbed instance is classified in the desired class. Most of the Counterfactual Analysis literature focuses on the single-instance single-counterfactual setting. By means of novel Mathematical Optimization models, we provide a counterfactual explanation for each instance in a group of interest.
  arXiv  Detail & Related papers  (2023-10-19T15:18:42Z)
• Explanation Selection Using Unlabeled Data for Chain-of-Thought Prompting [80.9896041501715]
  Explanations that have not been "tuned" for a task, such as off-the-shelf explanations written by nonexperts, may lead to mediocre performance. This paper tackles the problem of how to optimize explanation-infused prompts in a blackbox fashion.
  arXiv  Detail & Related papers  (2023-02-09T18:02:34Z)
• Cluster Explanation via Polyhedral Descriptions [0.0]
  Clustering is an unsupervised learning problem that aims to partition unlabelled data points into groups with similar features. Traditional clustering algorithms provide limited insight into the groups they find as their main focus is accuracy and not the interpretability of the group assignments. We introduce a new approach to explain clusters by constructing polyhedra around each cluster while minimizing either the complexity of the resulting polyhedra or the number of features used in the description.
  arXiv  Detail & Related papers  (2022-10-17T07:26:44Z)
• Explainable Clustering via Exemplars: Complexity and Efficient Approximation Algorithms [30.369731369945296]
  We propose an explainable-by-design clustering approach that finds clusters and exemplars to explain each cluster. The use of exemplars for understanding is supported by the exemplar-based school of concept definition in psychology. We show that finding a small set of exemplars to explain even a single cluster is computationally intractable.
  arXiv  Detail & Related papers  (2022-09-20T12:09:51Z)
• Fidelity of Ensemble Aggregation for Saliency Map Explanations using Bayesian Optimization Techniques [0.0]
  We present and compare different pixel-based aggregation schemes with the goal of generating a new explanation. We incorporate the variance between the individual explanations into the aggregation process. We also analyze the effect of multiple normalization techniques on ensemble aggregation.
  arXiv  Detail & Related papers  (2022-07-04T16:34:12Z)
• Unsupervised Summarization with Customized Granularities [76.26899748972423]
  We propose the first unsupervised multi-granularity summarization framework, GranuSum. By inputting different numbers of events, GranuSum is capable of producing multi-granular summaries in an unsupervised manner.
  arXiv  Detail & Related papers  (2022-01-29T05:56:35Z)
• Explanations for Monotonic Classifiers [26.044285532808075]
  In many classification tasks there is a requirement of monotonicity. Despite comprehensive efforts on learning monotonic classifiers, dedicated approaches for explaining monotonics are scarce. This paper describes novel algorithms for the computation of one formal explanation of a black-box monotonic classifier. The paper presents a practically efficient model-agnostic algorithm for enumerating formal explanations.
  arXiv  Detail & Related papers  (2021-06-01T00:14:12Z)
• Text Modular Networks: Learning to Decompose Tasks in the Language of Existing Models [61.480085460269514]
  We propose a framework for building interpretable systems that learn to solve complex tasks by decomposing them into simpler ones solvable by existing models. We use this framework to build ModularQA, a system that can answer multi-hop reasoning questions by decomposing them into sub-questions answerable by a neural factoid single-span QA model and a symbolic calculator.
  arXiv  Detail & Related papers  (2020-09-01T23:45:42Z)
• Unsupervised Multi-view Clustering by Squeezing Hybrid Knowledge from Cross View and Each View [68.88732535086338]
  This paper proposes a new multi-view clustering method, low-rank subspace multi-view clustering based on adaptive graph regularization. Experimental results for five widely used multi-view benchmarks show that our proposed algorithm surpasses other state-of-the-art methods by a clear margin.
  arXiv  Detail & Related papers  (2020-08-23T08:25:06Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• ClarQ: A large-scale and diverse dataset for Clarification Question Generation [67.1162903046619]
  We devise a novel bootstrapping framework that assists in the creation of a diverse, large-scale dataset of clarification questions based on postcomments extracted from stackexchange. We quantitatively demonstrate the utility of the newly created dataset by applying it to the downstream task of question-answering. We release this dataset in order to foster research into the field of clarification question generation with the larger goal of enhancing dialog and question answering systems.
  arXiv  Detail & Related papers  (2020-06-10T17:56:50Z)

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.