Neurosymbolic Reasoning and Learning with Restricted Boltzmann Machines

Son N. Tran, Artur S. d'Avila GarcezAAAI 2023 · DOI

Introduction

The integration of learning and reasoning remains a primary challenge in Artificial Intelligence. While deep learning excels at pattern recognition, it often fails at explicit rule-based reasoning. Conversely, symbolic AI is interpretable but struggles with noisy data. This paper introduces Logical Boltzmann Machines (LBMs), a framework that establishes a formal equivalence between propositional logic and Restricted Boltzmann Machines (RBMs). By mapping logical formulas into a neural network's energy landscape, LBMs enable efficient reasoning and learning from both data and background knowledge.

Methodology: Logical Boltzmann Machines

The core innovation of this work is the mathematical proof that any propositional logic formula can be represented by an RBM. In this mapping, truth value assignments that satisfy the formula correspond to the global minima of the network's energy function.

Energy-Logic Equivalence

To achieve this, formulas are first converted into Strict Disjunctive Normal Form (SDNF). This "flattening" allows a standard two-layer RBM to represent complex logic without requiring higher-order connections. Reasoning is then performed by seeking the state with the lowest energy.

Energy landscapes across different clause counts (c). The plots demonstrate how both Minimum Energy and Free Energy align with the number of satisfied clauses, enabling logical search via energy minimization.

A key feature is the use of Free Energy, which transforms the discrete Boolean Satisfiability (SAT) problem into a continuous optimization task. This allows the use of gradient-based methods to navigate the logical search space.

Evaluation and Results

LBMs were evaluated on synthetic large-scale formulas, Inductive Logic Programming (ILP) benchmarks (e.g., Mutagenesis, Alzheimer’s drug-design), and semantic image interpretation tasks.

Reasoning Efficiency and Scalability

In large-scale tests, LBMs demonstrated remarkable efficiency. For formulas with search spaces exceeding one billion possible assignments, the system consistently identified all satisfying solutions in under 70 seconds.

Scalability of LBM reasoning. The blue line represents the exponential growth of the search space, while the red line shows the corresponding time taken to find solutions, highlighting the system's efficiency.

Learning Performance

In ILP benchmarks, LBMs outperformed purely symbolic systems like Aleph and other neurosymbolic models like CILP++ in 5 out of 7 datasets. Furthermore, when integrated with Convolutional Neural Networks (CNNs) for image interpretation, LBMs surpassed state-of-the-art neurosymbolic frameworks like Logic Tensor Networks (LTN) in predicting complex object relationships.

Key Insights

  • Bidirectional Reasoning: Unlike feed-forward networks, LBMs are symmetrical, allowing them to perform both Modus Ponens and Modus Tollens naturally.
  • Search Sparsity: LBMs found satisfying assignments by exploring less than 0.75% of the state space, indicating that the energy landscape effectively guides the search process.

Limitations and Future Work

While LBMs represent a significant advancement, they currently do not match the performance of specialized symbolic SAT solvers like MiniSat. Future research aims to extend this framework to First-Order Logic (handling variables and quantifiers) and incorporate probabilistic weighting for handling uncertain rules.

Summary updated

BibTeX
@inproceedings{tran2023neurosymbolic,
  author = {Son N. Tran and Artur S. d'Avila Garcez},
  title = {{Neurosymbolic Reasoning and Learning with Restricted Boltzmann Machines}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25806},
}
Figure