Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay

• URL: http://arxiv.org/abs/2008.05803v2
• Date: Wed, 4 Nov 2020 09:48:14 GMT
• Title: Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay
• Authors: Joao Marques-Silva, Thomas Gerspacher, Martin C. Cooper, Alexey Ignatiev, Nina Narodytska
• Abstract summary: We show that PI-explanations can be achieved in log-linear time. We also show that PI-explanations can be obtained with delay.
• Score: 30.014888494169465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work proposed the computation of so-called PI-explanations of Naive Bayes Classifiers (NBCs). PI-explanations are subset-minimal sets of feature-value pairs that are sufficient for the prediction, and have been computed with state-of-the-art exact algorithms that are worst-case exponential in time and space. In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration of PI-explanations can be obtained with polynomial delay. Experimental results demonstrate the performance gains of the new algorithms when compared with earlier work. The experimental results also investigate ways to measure the quality of heuristic explanations

Related papers

• Feature-Specific Coefficients of Determination in Tree Ensembles [10.968795392216606]
  Tree ensemble methods provide promising predictions with models difficult to interpret. Recent introduction of Shapley values for individualized feature contributions, accompanied with several fast computing algorithms for predicted values, shows intriguing results. We propose an efficient algorithm, Q-SHAP, that reduces the computational complexity to time when calculating Shapley values related to quadratic losses.
  arXiv  Detail & Related papers  (2024-07-03T21:27:29Z)
• Distribution Learning Meets Graph Structure Sampling [10.095280456019367]
  This work establishes a novel link between PAC-learning high-dimensional models and the task of (optimal) counting and sampling of graph structures. We show that the average regret incurred by the forecaster's predictions can be used to bound the expected KL divergence between P and the predictions. Known regret bounds for EWA and RWM then yield new sample complexity for learning Bayes nets.
  arXiv  Detail & Related papers  (2024-05-13T16:47:05Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Outlier Explanation via Sum-Product Networks [10.1303427221932]
  Outlier explanation is the task of identifying a set of features that distinguish a sample from normal data. Existing methods are based on beam search in the space of feature subsets. We propose a novel outlier explanation algorithm based on Sum-Product Networks (SPNs)
  arXiv  Detail & Related papers  (2022-07-18T07:47:36Z)
• A Fresh Approach to Evaluate Performance in Distributed Parallel Genetic Algorithms [5.375634674639956]
  This work proposes a novel approach to evaluate and analyze the behavior of multi-population parallel genetic algorithms (PGAs) In particular, we deeply study their numerical and computational behavior by proposing a mathematical model representing the observed performance curves. The conclusions based on the real figures and the numerical models fitting them represent a fresh way of understanding their speed-up, running time, and numerical effort.
  arXiv  Detail & Related papers  (2021-06-18T05:07:14Z)
• On Efficiently Explaining Graph-Based Classifiers [16.199563506727316]
  This paper shows that not only decision trees (DTs) may not be interpretable but also proposed a-time algorithm for computing one PI-explanation of a DT. In addition, the paper also proposes a-time algorithm for computing one contrastive explanation.
  arXiv  Detail & Related papers  (2021-06-02T17:55:41Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We build the connections between the theory of approximate maximum inner product search and the regret analysis of reinforcement learning.
  arXiv  Detail & Related papers  (2021-05-18T05:23:53Z)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  Activation Relaxation (AR) is motivated by constructing the backpropagation gradient as the equilibrium point of a dynamical system. Our algorithm converges rapidly and robustly to the correct backpropagation gradients, requires only a single type of computational unit, and can operate on arbitrary computation graphs.
  arXiv  Detail & Related papers  (2020-09-11T11:56:34Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• Learned Factor Graphs for Inference from Stationary Time Sequences [107.63351413549992]
  We propose a framework that combines model-based algorithms and data-driven ML tools for stationary time sequences. neural networks are developed to separately learn specific components of a factor graph describing the distribution of the time sequence. We present an inference algorithm based on learned stationary factor graphs, which learns to implement the sum-product scheme from labeled data.
  arXiv  Detail & Related papers  (2020-06-05T07:06:19Z)

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.