Understanding Boolean Function Learnability on Deep Neural Networks

• URL: http://arxiv.org/abs/2009.05908v2
• Date: Wed, 16 Jun 2021 19:50:28 GMT
• Title: Understanding Boolean Function Learnability on Deep Neural Networks
• Authors: Anderson R. Tavares, Pedro Avelar, Jo\~ao M. Flach, Marcio Nicolau, Luis C. Lamb, Moshe Vardi
• Abstract summary: Computational learning theory states that many classes of formulas are learnable in time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyse boolean formulas associated with the decision version of combinatorial optimisation problems, model sampling benchmarks, and random 3-CNFs with varying degrees of constrainedness. Our extensive experiments indicate that: (i) regardless of the combinatorial optimisation problem, relatively small and shallow neural networks are very good approximators of the associated formulas; (ii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iii) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Source code and relevant datasets are publicly available (https://github.com/machine-reasoning-ufrgs/mlbf).

Related papers

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable satisfiability layer based on an extension of the classic Sinkhorn algorithm for jointly encoding multiple sets of marginal distributions.
  arXiv  Detail & Related papers  (2024-07-18T22:05:21Z)
• NeuralFastLAS: Fast Logic-Based Learning from Raw Data [54.938128496934695]
  Symbolic rule learners generate interpretable solutions, however they require the input to be encoded symbolically. Neuro-symbolic approaches overcome this issue by mapping raw data to latent symbolic concepts using a neural network. We introduce NeuralFastLAS, a scalable and fast end-to-end approach that trains a neural network jointly with a symbolic learner.
  arXiv  Detail & Related papers  (2023-10-08T12:33:42Z)
• Memorization With Neural Nets: Going Beyond the Worst Case [5.03863830033243]
  In practice, deep neural networks are often able to easily interpolate their training data. We introduce a simple randomized algorithm that constructs an interpolating three-layer neural network in time. We obtain guarantees that are independent of the number of samples and hence move beyond worst-case memorization capacity bounds.
  arXiv  Detail & Related papers  (2023-09-30T10:06:05Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• Deep learning applied to computational mechanics: A comprehensive review, state of the art, and the classics [77.34726150561087]
  Recent developments in artificial neural networks, particularly deep learning (DL), are reviewed in detail. Both hybrid and pure machine learning (ML) methods are discussed. History and limitations of AI are recounted and discussed, with particular attention at pointing out misstatements or misconceptions of the classics.
  arXiv  Detail & Related papers  (2022-12-18T02:03:00Z)
• Efficient, probabilistic analysis of combinatorial neural codes [0.0]
  neural networks encode inputs in the form of combinations of individual neurons' activities. These neural codes present a computational challenge due to their high dimensionality and often large volumes of data. We apply methods previously applied to small examples and apply them to large neural codes generated by experiments.
  arXiv  Detail & Related papers  (2022-10-19T11:58:26Z)
• Benchmarking Compositionality with Formal Languages [64.09083307778951]
  We investigate whether large neural models in NLP can acquire the ability tocombining primitive concepts into larger novel combinations while learning from data. By randomly sampling over many transducers, we explore which of their properties contribute to learnability of a compositional relation by a neural network. We find that the models either learn the relations completely or not at all. The key is transition coverage, setting a soft learnability limit at 400 examples per transition.
  arXiv  Detail & Related papers  (2022-08-17T10:03:18Z)
• Gaussian Process Surrogate Models for Neural Networks [6.8304779077042515]
  In science and engineering, modeling is a methodology used to understand complex systems whose internal processes are opaque. We construct a class of surrogate models for neural networks using Gaussian processes. We demonstrate our approach captures existing phenomena related to the spectral bias of neural networks, and then show that our surrogate models can be used to solve practical problems.
  arXiv  Detail & Related papers  (2022-08-11T20:17:02Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Learn Like The Pro: Norms from Theory to Size Neural Computation [3.848947060636351]
  We investigate how dynamical systems with nonlinearities can inform the design of neural systems that seek to emulate them. We propose a Learnability metric and quantify its associated features to the near-equilibrium behavior of learning dynamics. It reveals exact sizing for a class of neural networks with multiplicative nodes that mimic continuous- or discrete-time dynamics.
  arXiv  Detail & Related papers  (2021-06-21T20:58:27Z)
• Gone Fishing: Neural Active Learning with Fisher Embeddings [55.08537975896764]
  There is an increasing need for active learning algorithms that are compatible with deep neural networks. This article introduces BAIT, a practical representation of tractable, and high-performing active learning algorithm for neural networks.
  arXiv  Detail & Related papers  (2021-06-17T17:26:31Z)
• Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces [5.863264019032882]
  We study the computational complexity of (deterministic or randomized) algorithms based on approximating or integrating functions. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates.
  arXiv  Detail & Related papers  (2021-04-06T18:55:20Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  We study the potential gains in sample efficiency that can bring in the principle of minimum description length. We use Turing machines to represent universal models and circuits. We highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.
  arXiv  Detail & Related papers  (2021-03-23T17:03:10Z)
• Reinforcement Learning with External Knowledge by using Logical Neural Networks [67.46162586940905]
  A recent neuro-symbolic framework called the Logical Neural Networks (LNNs) can simultaneously provide key-properties of both neural networks and symbolic logic. We propose an integrated method that enables model-free reinforcement learning from external knowledge sources.
  arXiv  Detail & Related papers  (2021-03-03T12:34:59Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• ODEN: A Framework to Solve Ordinary Differential Equations using Artificial Neural Networks [0.0]
  We prove a specific loss function, which does not require knowledge of the exact solution, to evaluate neural networks' performance. Neural networks are shown to be proficient at approximating continuous solutions within their training domains. A user-friendly and adaptable open-source code (ODE$mathcalN$) is provided on GitHub.
  arXiv  Detail & Related papers  (2020-05-28T15:34:10Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  We take one of the simplest inference methods, a truncated max-product Belief propagation, and add what is necessary to make it a proper component of a deep learning model. This BP-Layer can be used as the final or an intermediate block in convolutional neural networks (CNNs) The model is applicable to a range of dense prediction problems, is well-trainable and provides parameter-efficient and robust solutions in stereo, optical flow and semantic segmentation.
  arXiv  Detail & Related papers  (2020-03-13T13:11:35Z)

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.