Cardinality-Minimal Explanations for Monotonic Neural Networks

• URL: http://arxiv.org/abs/2205.09901v3
• Date: Tue, 2 May 2023 14:46:44 GMT
• Title: Cardinality-Minimal Explanations for Monotonic Neural Networks
• Authors: Ouns El Harzli, Bernardo Cuenca Grau, Ian Horrocks
• Abstract summary: In this paper, we investigate whether tractability can be regained by focusing on neural models implementing a monotonic function. Although the relevant decision problems remain intractable, we can show that they become solvable in favourable time.
• Score: 25.212444848632515
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In recent years, there has been increasing interest in explanation methods for neural model predictions that offer precise formal guarantees. These include abductive (respectively, contrastive) methods, which aim to compute minimal subsets of input features that are sufficient for a given prediction to hold (respectively, to change a given prediction). The corresponding decision problems are, however, known to be intractable. In this paper, we investigate whether tractability can be regained by focusing on neural models implementing a monotonic function. Although the relevant decision problems remain intractable, we can show that they become solvable in polynomial time by means of greedy algorithms if we additionally assume that the activation functions are continuous everywhere and differentiable almost everywhere. Our experiments suggest favourable performance of our algorithms.

Related papers

• A new approach to generalisation error of machine learning algorithms: Estimates and convergence [0.0]
  We introduce a new approach to the estimation of the (generalisation) error and to convergence. Our results include estimates of the error without any structural assumption on the neural networks.
  arXiv  Detail & Related papers  (2023-06-23T20:57:31Z)
• Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
  The linearized-Laplace approximation (LLA) has been shown to be effective and efficient in constructing Bayesian neural networks. We study the usefulness of the LLA in Bayesian optimization and highlight its strong performance and flexibility.
  arXiv  Detail & Related papers  (2023-04-17T14:23:43Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  Neuro-symbolic approaches typically resort to fuzzy approximations of a probabilistic objective. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles.
  arXiv  Detail & Related papers  (2023-02-28T00:04:22Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Stochastic Langevin Differential Inclusions with Applications to Machine Learning [5.274477003588407]
  We show some foundational results regarding the flow and properties of Langevin-type Differential Inclusions. In particular, we show strong existence of the solution, as well as an canonical- minimization of the free-energy functional.
  arXiv  Detail & Related papers  (2022-06-23T08:29:17Z)
• Constrained Monotonic Neural Networks [0.685316573653194]
  Wider adoption of neural networks in many critical domains such as finance and healthcare is being hindered by the need to explain their predictions. Monotonicity constraint is one of the most requested properties in real-world scenarios. We show it can approximate any continuous monotone function on a compact subset of $mathbbRn$.
  arXiv  Detail & Related papers  (2022-05-24T04:26:10Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Modeling Implicit Bias with Fuzzy Cognitive Maps [0.0]
  This paper presents a Fuzzy Cognitive Map model to quantify implicit bias in structured datasets. We introduce a new reasoning mechanism equipped with a normalization-like transfer function that prevents neurons from saturating.
  arXiv  Detail & Related papers  (2021-12-23T17:04:12Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization [0.0]
  Many supervised machine learning methods are cast as optimization problems. For prediction models which are linear in their parameters, this often leads to problems for prediction guarantees. In this paper, we consider two-layer neural networks with homogeneous activation functions.
  arXiv  Detail & Related papers  (2021-10-15T13:25:32Z)
• Relaxing the Constraints on Predictive Coding Models [62.997667081978825]
  Predictive coding is an influential theory of cortical function which posits that the principal computation the brain performs is the minimization of prediction errors. Standard implementations of the algorithm still involve potentially neurally implausible features such as identical forward and backward weights, backward nonlinear derivatives, and 1-1 error unit connectivity. In this paper, we show that these features are not integral to the algorithm and can be removed either directly or through learning additional sets of parameters with Hebbian update rules without noticeable harm to learning performance.
  arXiv  Detail & Related papers  (2020-10-02T15:21:37Z)

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.