Efficient Explanations With Relevant Sets

• URL: http://arxiv.org/abs/2106.00546v1
• Date: Tue, 1 Jun 2021 14:57:58 GMT
• Title: Efficient Explanations With Relevant Sets
• Authors: Yacine Izza, Alexey Ignatiev, Nina Narodytska, Martin C. Cooper, Joao Marques-Silva
• Abstract summary: This paper investigates solutions for tackling the practical limitations of $delta$-relevant sets. The computation of the subset of $delta$-relevant sets is in NP, and can be solved with a number of calls to an NP oracle.
• Score: 30.296628060841645
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work proposed $\delta$-relevant inputs (or sets) as a probabilistic explanation for the predictions made by a classifier on a given input. $\delta$-relevant sets are significant because they serve to relate (model-agnostic) Anchors with (model-accurate) PI- explanations, among other explanation approaches. Unfortunately, the computation of smallest size $\delta$-relevant sets is complete for ${NP}^{PP}$, rendering their computation largely infeasible in practice. This paper investigates solutions for tackling the practical limitations of $\delta$-relevant sets. First, the paper alternatively considers the computation of subset-minimal sets. Second, the paper studies concrete families of classifiers, including decision trees among others. For these cases, the paper shows that the computation of subset-minimal $\delta$-relevant sets is in NP, and can be solved with a polynomial number of calls to an NP oracle. The experimental evaluation compares the proposed approach with heuristic explainers for the concrete case of the classifiers studied in the paper, and confirms the advantage of the proposed solution over the state of the art.

Related papers

• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• On Computing Probabilistic Abductive Explanations [30.325691263226968]
  The most widely studied explainable AI (XAI) approaches are unsound. PI-explanations also exhibit important drawbacks, the most visible of which is arguably their size. This paper investigates practical approaches for computing relevant sets for a number of widely used classifiers.
  arXiv  Detail & Related papers  (2022-12-12T15:47:10Z)
• On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
  "sufficient reasons" are a kind of explanation in which given a decision tree $T$ and an instance $x$, one explains the decision $T(x)$. Our paper settles the computational complexity of $delta$-sufficient-reasons over decision trees. We identify structural restrictions of decision trees that make the problem tractable, and show how SAT solvers might be able to tackle these problems in practical settings.
  arXiv  Detail & Related papers  (2022-06-30T21:58:31Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Provably Precise, Succinct and Efficient Explanations for Decision Trees [32.062312674333775]
  Decision trees (DTs) embody interpretable classifiers. Work has demonstrated that predictions in DTs ought to be explained with rigorous explanations. delta-relevant sets denote that are succinct and provably precise.
  arXiv  Detail & Related papers  (2022-05-19T13:54:52Z)
• On Deciding Feature Membership in Explanations of SDD & Related Classifiers [0.685316573653194]
  The paper shows that the feature membership problem (FMP) is hard for $SigmaP$ for a broad class of classifiers. The paper proposes propositional encodings for classifiers represented with Sentential Decision Diagrams (SDDs) and for other propositional languages.
  arXiv  Detail & Related papers  (2022-02-15T16:38:53Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
  PAC-learning usually aims to compute a small subset ($varepsilon$-sample/net) from $n$ items. Inspired by smoothed analysis, we suggest a natural generalization: approximate the emphaverage (instead of the worst-case) error over the queries.
  arXiv  Detail & Related papers  (2020-06-09T18:25:34Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

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.