PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Logic Machines

Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, Denny Zhou

arXiv:1904.11694v1cs.AIcs.LGstat.ML

TL;DR

The paper addresses learning logical rules that generalize across increasingly large relational and decision-making tasks. It proposes Neural Logic Machines, a differentiable neural-symbolic architecture that realizes first-order Horn-clause reasoning. Experiments show that NLMs learn underlying logical rules from small-scale tasks and generalize to large-scale tasks, while retaining polynomial growth in predicates.

  • Problem

    Existing systems struggle either with scaling inductive logic programming beyond small rule sets or with learning lifted rules and higher-order relational reasoning.

  • Method

    NLMs use a fully differentiable neural-symbolic architecture that approximates Boolean logic operations and realizes first-order quantifiers through neural-module wiring.

  • Results

    NLMs learn underlying logical rules from small-scale tasks and generalize to large-scale tasks, including arrays of arbitrary length with learned algorithms interpretable as sorting procedures.

  • Takeaways & Limitations

    NLMs learn lifted rules directly from input-output pairs without human-designed rules or a predefined knowledge base.

  • Takeaways & Limitations

    NLMs require symbolic input, and their maximum reasoning depth must be specified for each problem.

Abstract

from arXiv · show

We propose the Neural Logic Machine (NLM), a neural-symbolic architecture for both inductive learning and logic reasoning. NLMs exploit the power of both neural networks---as function approximators, and logic programming---as a symbolic processor for objects with properties, relations, logic connectives, and quantifiers. After being trained on small-scale tasks (such as sorting short arrays), NLMs can recover lifted rules, and generalize to large-scale tasks (such as sorting longer arrays). In our experiments, NLMs achieve perfect generalization in a number of tasks, from relational reasoning tasks on the family tree and general graphs, to decision making tasks including sorting arrays, finding shortest paths, and playing the blocks world. Most of these tasks are hard to accomplish for neural networks or inductive logic programming alone.

1 INTRODUCTION

The paper motivates a neural-symbolic approach to learning and reasoning that combines neural approximation with symbolic logic, targeting systematic generalization beyond small tasks. It introduces Neural Logic Machines to address challenges involving lifted rules, higher-order relations, quantifiers, and scalable rule learning.

  • Traditional inductive logic programming faces exponentially large search spaces as the number of compositional rules grows, limiting scalability beyond small rule sets.This scalability problem motivates a neural implementation of rule induction.
  • Blocks world requires transforming an initial configuration into a target configuration through a sequence of Move operations subject to moveability and placeability conditions.A block can be moved onto another block or the ground when the relevant objects satisfy these conditions.
  • Learning systems must recover lifted rules that apply uniformly to objects and generalize from small training instances to larger ones.The introduction highlights failures to generalize from short arrays to longer arrays as an intuition for this challenge.
  • The target learning system must handle high-order relational data and quantifiers beyond typical graph-structured neural networks.The transitivity example requires jointly inspecting three objects and using an existentially quantified intermediate object.
  • Neural Logic Machines combine neural networks with logic programming to realize Horn clauses in first-order logic.Logical ANDs and ORs are approximated by neural networks, while neural-module wiring realizes logic quantifiers.

2 NEURAL LOGIC MACHINES (NLM)

Neural Logic Machines represent predicates over objects as tensors and apply sequential neural operators to realize lifted first-order logic rules, including Boolean operations and quantification. Their layered, arity-grouped architecture supports deduction over relational data while generalizing across object counts, subject to acyclic rule references and bounded depth and breadth.

  • Logic predicates as tensors: NLMs sequentially apply first-order rules to grounded predicate tensors, producing conclusions such as whether an object is moveable.Under the Closed-World Assumption, premises such as IsGround(u) and Clear(u) can support inferring Moveable(u).
  • Logic predicates as tensors: Each predicate is grounded over a fixed object set as a probabilistic tensor whose entries represent the probability that the predicate is True.For an r-ary predicate over m mutually exclusive grounded objects, the tensor has shape [m^r].
  • Logic predicates as tensors: NLMs stack predicates by arity and use expansion and reduction to connect groups with different arities, up to a task-dependent maximum breadth B.This organization represents unary properties, pairwise relations, and higher-order relational data within one architecture.
  • Neural Logic Machines: An NLM has D layers and B + 1 arity-specific computation groups, with layer-by-layer propagation interpreted as a sequence of rule applications forming higher-level predicates.The architecture uses intra-group computation between layers and inter-group computation across neighboring arities.
  • Logic rules as neural operators: Boolean-rule modules apply a shared MLP across all grounding entries after permuting object-index axes, making the learned rule lifted and independent of the number of objects.The module can instantiate rules such as Moveable(x) ← ¬IsGround(x) ∧Clear(x), while uniform application parallels implicit Horn-clause unification.
  • Neural Logic Machines: NLMs can induce lifted rules and generalize across object counts, but the presented system excludes cyclic predicate references and bounds deduction steps by depth.Forward or backward propagation costs O(mBDC^2), and with B treated as constant, complexity is quadratic in the number of allowed predicates.

3 EXPERIMENTS

NLM is evaluated across relational reasoning and decision-making tasks, using small training instances and larger tests. The experiments compare NLM with neural and symbolic baselines and report generalization and algorithmic behavior.

  • Evaluation scope: NLM experiments cover family-tree reasoning, graph reasoning, blocks-world decision making, sorting, and path finding.The evaluation uses supervised learning for some tasks and reinforcement learning for decision-making tasks.
  • Baselines: The main baselines are Memory Networks and Differentiable Inductive Logic Programming, with additional comparisons to eligible neural models.MemNN represents inputs sequentially and performs iterative memory queries, while ∂ILP receives grounded base predicates.
  • Relational reasoning: 100% accuracy is achieved by both ∂ILP and NLM on the reported family-tree and graph-reasoning test set, outperforming the neural baseline.Table 1 notes that ∂ILP cannot scale up in 2-OutDegree.
  • Family tree reasoning: Family-tree models train on 20 members and test on 20 and 100 members, evaluating properties over objects and relations over object pairs.The evaluation averages accuracy across all relevant objects or object pairs.
  • Blocks world: The blocks-world task uses sparse positive rewards and actions that move movable objects onto placeable objects until the operating world matches the target world.Move(i, j) has no effect when invalid; otherwise, it changes the state coordinates.
  • General algorithms: Learned sorting algorithms generalize to arrays of arbitrary length and can be interpreted as Selection-Sort or Bubble-Sort.The paper reports this behavior across different hyper-parameters and random seeds.

4 RELATED WORKS AND DISCUSSIONS

The discussion positions NLMs between neural and symbolic approaches by learning lifted rules over arbitrary objects while retaining differentiable computation. It contrasts NLM’s scaling behavior and input requirements with ILP, graph networks, and program-induction systems.

  • Complexity: NLM complexity and parameter size grow polynomially with the number of allowed predicates but factorially with breadth, or maximum predicate arity.This contrasts with the exponential dependence on predicate count reported for ∂ILP.
  • Rule induction: NLMs learn lifted rules directly from input-output pairs without human-designed rules or a supplied knowledge base.This distinguishes the architecture from approaches that use neural networks to augment symbolic rule induction.
  • Symbolic reasoning: Existing symbolic relational reasoning methods commonly assume that predicates on both sides of a rule are already known in the knowledge base.The discussion contrasts this setting with NLM’s rule-capturing architecture.
  • Graph reasoning: Unlike many graph neural networks restricted to predefined nodes and binary connections, NLM captures lifted rules over any set of objects.The paper identifies the graph-network restriction as limiting expressive power for general-purpose reasoning.
  • Integration: NLMs are fully differentiable and can be integrated with existing convolutional or recurrent neural architectures for logic reasoning.The paper supports this claim alongside quantitative results across relational reasoning and algorithmic decision-making tasks.
  • Related neural methods: Neural Turing Machines and neural program-induction systems address tasks such as sorting through external memory or learned program construction.These approaches form a related neural-abstraction and program-induction line of work.

5 CONCLUSIONS AND DISCUSSIONS

The paper presents NLM as a differentiable neural-symbolic architecture for first-order logic deduction. Experiments indicate that it learns logical rules from small tasks and generalizes them to larger tasks, while several scope and usability limitations remain.

  • Conclusion: NLM conducts first-order logic deduction through a fully differentiable architecture trainable end to end.The model is described as a neural-symbolic architecture.
  • Conclusion: Empirical evaluations show that NLM learns underlying logical rules from small-scale tasks and generalizes to large-scale tasks.This conclusion summarizes the reported empirical behavior across the paper’s tasks.
  • Limitations: The model requires symbolic input, and its maximum depth must currently be specified separately for each problem.The paper identifies real-valued inputs and adaptive depth selection as future directions.
  • Limitations: NLM training remains nontrivial and may require curriculum learning, while its learned rules are implicitly encoded in neural-network weights rather than human-readable form.The paper proposes simpler optimization and rule-extraction methods as future work.

SUPPLEMENTARY MATERIAL

The supplementary material provides training and implementation details, deferred extension discussions, and a proof concerning NLM’s realization of Horn-clause forward chaining.

  • Supplementary organization: Appendix A details training, including curriculum learning for reinforcement-learning tasks.The supplementary material also covers implementation details and hyperparameters in Appendix B.
  • Supplementary organization: Appendix B supplies implementation details and task-specific hyperparameters, while Appendix C discusses NLM extensions.The supplement also includes a proof concerning forward chaining for Horn clauses.

A TRAINING METHOD AND CURRICULUM LEARNING

This section details the training method and data-generation procedures used for the experiments.

  • The section introduces hyper-parameter details, exam-guided curriculum learning for reinforcement learning, and data-generation procedures.

A.1 TRAINING METHOD

The training method combines task-specific optimization with an exam-guided curriculum that increases instance difficulty and reuses failure cases.

  • Supervised tasks use Softmax-Cross-Entropy with batch size 4, while reinforcement-learning tasks use REINFORCE with one episode per batch.
  • The reinforcement-learning update combines discounted rewards with a policy-entropy term to encourage exploration.The entropy coefficient β varies across environments and learning stages.
  • The reinforcement-learning setup rewards task completion with 1.0, penalizes each move by −0.01, and uses γ = 0.99.
  • A.2 CURRICULUM LEARNING GUIDED BY EXAMS AND FAILS: Curriculum learning groups instances into lessons by complexity and presents them in increasing order of difficulty.In BlocksWorld, complexity is defined by the number of blocks.
  • A.2 CURRICULUM LEARNING GUIDED BY EXAMS AND FAILS: Training samples are drawn from recorded positive and negative cases, with sampling probability Ω assigned to the positive set.

B IMPLEMENTATION DETAILS AND HYPER-PARAMETERS

This section describes implementation details including residual connections between input and deduced predicate representations.

  • The implementation section summarizes model and experiment details for NLM and the MemNN baseline.
  • Residual connections concatenate base predicates with conclusive predicates group-wise at each model layer.Unary inputs connect to deduced unary predicates, and binary inputs connect to deduced binary predicates.

B.2 HYPER-PARAMETERS FOR NLM

This section specifies NLM hyper-parameters, data generation, auxiliary training, and empirical accuracy evaluation, including a BlocksWorld confidence estimate.

  • NLM uses no hidden layer in its internal MLPs and sets each layer’s intermediate-predicate dimension to 8.Reinforcement-learning graduation means achieving a 100% success rate on the final exam.
  • 20% graduation for maternal great uncle prediction reflects the relatively small number of such relations in randomly generated training cases.Increasing the maximum number of people in training examples to 30 raises the graduation ratio to 50%.
  • The experiments use random generation for family trees, graphs, sorting permutations, and BlocksWorld configurations.
  • BlocksWorld training adds a supervised action-validity or action-effect prediction task to the REINFORCE objective.The auxiliary cross-entropy loss receives weight 0.1.
  • Action selection in BlocksWorld combines current and target object representations before pairwise relational scoring and Softmax selection.
  • Accuracy statistics are estimated empirically on 1000 randomly generated test examples rather than proved directly from induced rules.
  • 99.7% confidence supports at least 99.98% accuracy after testing a BlocksWorld model on 100,000 samples with no failures.

C NEURAL LOGIC MACHINES (NLM) EXTENSIONS

NLMs extend neural-symbolic reasoning to noisy visual inputs and realize finite, non-recursive Horn-clause computations through neural operators and tensor transformations.

  • Reasoning over noisy input: NLMs can reason over noisy inputs by taking properties or relations derived from neural architectures such as CNNs.The architecture remains fully differentiable, allowing perception and reasoning modules to be optimized together.
  • Reasoning over noisy input: 99.4% accuracy was achieved on 1,000 MNIST-based testing examples with m=50 after joint CNN-NLM training on 100,000 examples with m=10.LeNet extracts node-number features while the reasoning model is optimized jointly with perception.
  • Horn-clause realization: The realization result is limited to a partial set of finite Horn clauses with sufficient depth and breadth, while cyclic predicate references remain future work.The proof assumes flexible, sufficiently large architectural capacity and excludes cyclic references.
  • Horn-clause realization: NLMs realize definite Horn clauses by expanding predicate arities, applying neural Boolean logic and permutations, reducing quantified variables, and expanding head-only variables.This compositional construction is described as a four-step computation flow for chain-like rules.
  • Horn-clause realization: NLM forward propagation realizes forward chaining by sequentially applying rule-specific NLMs ordered according to non-recursive rule dependencies.Initial facts are represented as grounded base predicates, and stacked NLMs derive later conclusions.

E SAMPLE BLOCKS WORLD RULES

The Blocks World example expresses action selection through layered relational rules and shows how NLM computation is implemented across predicate arities.

  • Blocks World rules: ShouldMove(x) is defined using initial-world membership, moveability, and the existence of an unmatched block below x.The supplied rule set expands these conditions through helper predicates such as Clear, Moveable, Match, and HaveUnmatchedBelow.
  • Blocks World rules: The complete Blocks World policy must additionally determine where to move a block, beyond deciding whether it should move.The displayed ShouldMove rules represent only part of the logic needed to complete the challenge.
  • Neural implementation: Expand replicates tensors along a new object dimension, while Reduce aggregates over a quantified dimension using maximum or minimum operations.The implementation includes masking for tuple constraints and permutation of relation dimensions before neural processing.
  • Neural implementation: The implementation applies dense neural logic to permutations of aggregated inputs and can optionally concatenate residual links to the outputs.Inputs are aggregated across neighboring predicate arities before neural processing.
  • Neural implementation: NLMs implement predicates at nullary, unary, binary, and ternary arities using tensors, permutation-based neural logic, expansion, and reduction operations.The breadth-3 layer accepts four predicate tensor groups and returns corresponding output groups.
Loading 1904.11694v1…