On the Hardness of Probabilistic Neurosymbolic Learning

• URL: http://arxiv.org/abs/2406.04472v1
• Date: Thu, 6 Jun 2024 19:56:33 GMT
• Title: On the Hardness of Probabilistic Neurosymbolic Learning
• Authors: Jaron Maene, Vincent Derkinderen, Luc De Raedt,
• Abstract summary: We study the complexity of differentiating probabilistic reasoning in neurosymbolic models. We introduce WeightME, an unbiased gradient estimator based on model sampling. Our experiments indicate that the existing biased approximations indeed struggle to optimize even when exact solving is still feasible.
• Score: 10.180468225166441
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The limitations of purely neural learning have sparked an interest in probabilistic neurosymbolic models, which combine neural networks with probabilistic logical reasoning. As these neurosymbolic models are trained with gradient descent, we study the complexity of differentiating probabilistic reasoning. We prove that although approximating these gradients is intractable in general, it becomes tractable during training. Furthermore, we introduce WeightME, an unbiased gradient estimator based on model sampling. Under mild assumptions, WeightME approximates the gradient with probabilistic guarantees using a logarithmic number of calls to a SAT solver. Lastly, we evaluate the necessity of these guarantees on the gradient. Our experiments indicate that the existing biased approximations indeed struggle to optimize even when exact solving is still feasible.

Related papers

• Non-asymptotic convergence analysis of the stochastic gradient Hamiltonian Monte Carlo algorithm with discontinuous stochastic gradient with applications to training of ReLU neural networks [8.058385158111207]
  We provide a non-asymptotic analysis of the convergence of the gradient Hamiltonian Monte Carlo to a target measure in Wasserstein-1 and Wasserstein-2 distance. To illustrate our main results, we consider numerical experiments on quantile estimation and on several problems involving ReLU neural networks relevant in finance and artificial intelligence.
  arXiv  Detail & Related papers  (2024-09-25T17:21:09Z)
• Stochastic Marginal Likelihood Gradients using Neural Tangent Kernels [78.6096486885658]
  We introduce lower bounds to the linearized Laplace approximation of the marginal likelihood. These bounds are amenable togradient-based optimization and allow to trade off estimation accuracy against computational complexity.
  arXiv  Detail & Related papers  (2023-06-06T19:02:57Z)
• 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)
• Monte Carlo Neural PDE Solver for Learning PDEs via Probabilistic Representation [59.45669299295436]
  We propose a Monte Carlo PDE solver for training unsupervised neural solvers. We use the PDEs' probabilistic representation, which regards macroscopic phenomena as ensembles of random particles. Our experiments on convection-diffusion, Allen-Cahn, and Navier-Stokes equations demonstrate significant improvements in accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-02-10T08:05:19Z)
• Learning a Single Neuron with Bias Using Gradient Descent [53.15475693468925]
  We study the fundamental problem of learning a single neuron with a bias term. We show that this is a significantly different and more challenging problem than the bias-less case.
  arXiv  Detail & Related papers  (2021-06-02T12:09:55Z)
• A Bayesian Perspective on Training Speed and Model Selection [51.15664724311443]
  We show that a measure of a model's training speed can be used to estimate its marginal likelihood. We verify our results in model selection tasks for linear models and for the infinite-width limit of deep neural networks. Our results suggest a promising new direction towards explaining why neural networks trained with gradient descent are biased towards functions that generalize well.
  arXiv  Detail & Related papers  (2020-10-27T17:56:14Z)
• A Deterministic Approximation to Neural SDEs [38.23826389188657]
  We show that obtaining well-calibrated uncertainty estimations from NSDEs is computationally prohibitive. We develop a computationally affordable deterministic scheme which accurately approximates the transition kernel. Our method also improves prediction accuracy thanks to the numerical stability of deterministic training.
  arXiv  Detail & Related papers  (2020-06-16T08:00:26Z)
• Path Sample-Analytic Gradient Estimators for Stochastic Binary Networks [78.76880041670904]
  In neural networks with binary activations and or binary weights the training by gradient descent is complicated. We propose a new method for this estimation problem combining sampling and analytic approximation steps. We experimentally show higher accuracy in gradient estimation and demonstrate a more stable and better performing training in deep convolutional models.
  arXiv  Detail & Related papers  (2020-06-04T21:51:21Z)

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.