Tractable Boolean and Arithmetic Circuits

• URL: http://arxiv.org/abs/2202.02942v1
• Date: Mon, 7 Feb 2022 05:01:38 GMT
• Title: Tractable Boolean and Arithmetic Circuits
• Authors: Adnan Darwiche
• Abstract summary: We review the foundations of tractable circuits and some associated milestones. We focus on their core properties and techniques that make them particularly useful for the broad aims of neuro-symbolic AI.
• Score: 11.358487655918676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tractable Boolean and arithmetic circuits have been studied extensively in AI for over two decades now. These circuits were initially proposed as "compiled objects," meant to facilitate logical and probabilistic reasoning, as they permit various types of inference to be performed in linear-time and a feed-forward fashion like neural networks. In more recent years, the role of tractable circuits has significantly expanded as they became a computational and semantical backbone for some approaches that aim to integrate knowledge, reasoning and learning. In this article, we review the foundations of tractable circuits and some associated milestones, while focusing on their core properties and techniques that make them particularly useful for the broad aims of neuro-symbolic AI.

Related papers

• Analog Alchemy: Neural Computation with In-Memory Inference, Learning and Routing [0.08965418284317034]
  I explore an alternative way with memristive devices for neural computation, where the unique physical dynamics of the devices are used for inference, learning and routing. I will provide hardware evidence of adaptability of local learning to memristive substrates, new material stacks and circuit blocks that aid in solving the credit assignment problem and efficient routing between analog crossbars for scalable architectures.
  arXiv  Detail & Related papers  (2024-12-30T10:35:03Z)
• KLay: Accelerating Neurosymbolic AI [5.342751235300229]
  A popular approach to neurosymbolic AI involves mapping logic formulas to arithmetic circuits. We introduce knowledge layers (KLay) to represent arithmetic circuits that can be efficiently parallelized. We empirically show that KLay achieves speedups of multiple orders of magnitude over the state of the art.
  arXiv  Detail & Related papers  (2024-10-15T09:02:55Z)
• Transformer Circuit Faithfulness Metrics are not Robust [0.04260910081285213]
  We measure circuit 'faithfulness' by ablating portions of the model's computation. We conclude that existing circuit faithfulness scores reflect both the methodological choices of researchers as well as the actual components of the circuit. The ultimate goal of mechanistic interpretability work is to understand neural networks, so we emphasize the need for more clarity in the precise claims being made about circuits.
  arXiv  Detail & Related papers  (2024-07-11T17:59:00Z)
• Learning Interpretable Differentiable Logic Networks [3.8064485653035987]
  We introduce a novel method for learning interpretable differentiable logic networks (DLNs) We train these networks by softening and differentiating their discrete components, through binarization of inputs, binary logic operations, and connections between neurons. Experimental results on twenty classification tasks indicate that differentiable logic networks can achieve accuracies comparable to or exceeding that of traditional NNs.
  arXiv  Detail & Related papers  (2024-07-04T21:58:26Z)
• Coding for Intelligence from the Perspective of Category [66.14012258680992]
  Coding targets compressing and reconstructing data, and intelligence. Recent trends demonstrate the potential homogeneity of these two fields. We propose a novel problem of Coding for Intelligence from the category theory view.
  arXiv  Detail & Related papers  (2024-07-01T07:05:44Z)
• Reasoning Algorithmically in Graph Neural Networks [1.8130068086063336]
  We aim to integrate the structured and rule-based reasoning of algorithms with adaptive learning capabilities of neural networks. This dissertation provides theoretical and practical contributions to this area of research.
  arXiv  Detail & Related papers  (2024-02-21T12:16:51Z)
• Brain-Inspired Computational Intelligence via Predictive Coding [89.6335791546526]
  Predictive coding (PC) has shown promising performance in machine intelligence tasks. PC can model information processing in different brain areas, can be used in cognitive control and robotics.
  arXiv  Detail & Related papers  (2023-08-15T16:37:16Z)
• 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)
• Bayesian Learning for Neural Networks: an algorithmic survey [95.42181254494287]
  This self-contained survey engages and introduces readers to the principles and algorithms of Bayesian Learning for Neural Networks. It provides an introduction to the topic from an accessible, practical-algorithmic perspective.
  arXiv  Detail & Related papers  (2022-11-21T21:36:58Z)
• 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)
• Spiking Neural Networks Hardware Implementations and Challenges: a Survey [53.429871539789445]
  Spiking Neural Networks are cognitive algorithms mimicking neuron and synapse operational principles. We present the state of the art of hardware implementations of spiking neural networks. We discuss the strategies employed to leverage the characteristics of these event-driven algorithms at the hardware level.
  arXiv  Detail & Related papers  (2020-05-04T13:24:00Z)

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.