PaperlayerView exact revision on arXiv

Source-linked AI summary

NeurASP: Embracing Neural Networks into Answer Set Programming

Zhun Yang, Adam Ishay, Joohyung Lee

arXiv:2307.07700v1cs.AIcs.LGcs.SC

TL;DR

NeurASP addresses the gap between neural perception and logic-oriented ASP by embedding neural-network outputs into answer set programs. It represents those outputs as probabilities over atomic facts and uses ASP reasoning for perception-dependent tasks and rule-guided learning. The paper reports improved perception in reasoning tasks and shows that ASP constraints can support learning with fewer data, while assuming a neural network output structure of e × n probabilities.

  • Problem

    ASP supports complex symbolic reasoning but does not incorporate the high-dimensional representations and pre-trained perception models used in deep learning.

  • Method

    NeurASP extends answer set programs by treating neural-network outputs as probability distributions over atomic facts and integrating them with ASP rules.

  • Results

    NeurASP improves perception results through symbolic reasoning and can train neural networks with explicit ASP constraints, sometimes learning better with fewer data.

  • Takeaways & Limitations

    The framework supports hybrid tasks in which neural networks perform perception while ASP supplies semantic reasoning and constraint-based learning.

  • Takeaways & Limitations

    NeurASP assumes neural networks produce an e × n output matrix representing probabilities for e events and n outcomes per event.

Abstract

from arXiv · show

We present NeurASP, a simple extension of answer set programs by embracing neural networks. By treating the neural network output as the probability distribution over atomic facts in answer set programs, NeurASP provides a simple and effective way to integrate sub-symbolic and symbolic computation. We demonstrate how NeurASP can make use of a pre-trained neural network in symbolic computation and how it can improve the neural network's perception result by applying symbolic reasoning in answer set programming. Also, NeurASP can be used to train a neural network better by training with ASP rules so that a neural network not only learns from implicit correlations from the data but also from the explicit complex semantic constraints expressed by the rules.

1 Introduction

NeurASP extends answer set programming with neural networks to connect perception and symbolic reasoning. It supports reasoning over neural outputs, simplifies constraint-based tasks, and trains networks using explicit ASP semantic constraints.

  • Contribution: NeurASP treats neural-network outputs as probability distributions over atomic facts, integrating sub-symbolic computation with symbolic answer set reasoning.The framework extends answer set programs while retaining ASP-based knowledge representation.
  • Contribution: Reasoning can identify perception mistakes that violate semantic constraints, improving robustness in tasks requiring both perception and reasoning.Examples include object detection, object-relation disambiguation, and digit recognition in Sudoku.
  • Motivation: Separating neural perception from ASP solving can simplify network design, reduce required training data, and ease adaptation to puzzle variants.For Sudoku, the network recognizes digits while ASP finds a solution and encodes variant-specific constraints.
  • Learning: NeurASP trains neural networks with explicit complex semantic constraints in ASP rules alongside implicit correlations learned from data.Semantic loss from the reasoning module can be backpropagated through the rule layer into neural networks via neural atoms.
  • Novelty: Compared with DeepProbLog, NeurASP supports richer ASP knowledge constructs and uses an ASP solver rather than constructing circuits.The paper highlights defaults, aggregates, and optimization rules as expressive constructs.

2 NeurASP

NeurASP combines ASP rules with neural atoms whose outputs define probabilities for possible outcomes. Its semantics convert neural atoms into ASP choices and assign probabilities to stable models consistent with those choices.

  • 2.1 Syntax: A neural network receives an arbitrary tensor and outputs an e × n matrix of outcome probabilities for e random events with n possible outcomes each.For MNIST, e=1 and n=10; for Boolean edge predictions, n=2.
  • 2.1 Syntax: A neural atom names a network, points to input data through terms mapped to tensors, and lists all possible outcomes.The form nn(m(e, t), [v1, . . . , vn]) introduces outcome atoms whose probabilities come from the network.
  • Examples: Each neural atom introduces propositional outcome atoms, such as ten digit assignments for an MNIST image or Boolean edge assignments in a graph.The digit and shortest-path examples instantiate the general neural-atom representation.
  • Program structure: A NeurASP program combines propositional ASP rules with neural atoms, while neural atoms are excluded from the heads of ASP rules.Rules can express relations such as adding two recognized digit values.
  • 2.2 Semantics: NeurASP obtains an ASP counterpart by replacing neural atoms with exactly-one choice rules and defines stable models and total choices from that counterpart.The program must be coherent, meaning every total choice has at least one agreeing stable model.
  • 2.2 Semantics: The probability of a neural atom outcome is the corresponding neural-network output, and a stable-model probability multiplies selected outcome probabilities before dividing by the number of agreeing stable models.Observations use ASP constraints, and probabilities over sets of observations are multiplied.

3 Inference with NeurASP

NeurASP combines neural-network perception with ASP rules to reason about recognized objects and solve structured tasks such as image-based Sudoku. Inference can correct perception using semantic constraints and reuse the same perception model across Sudoku variations.

  • Commonsense Reasoning about Image: NeurASP integrates neural-network outputs with ASP rules to reason about objects recognized in images.The implementation combines PyTorch for neural processing with CLINGO for stable-model computation.
  • Commonsense Reasoning about Image: Reasoning about object sizes and spatial relations distinguishes toy cars from real cars in the two example images.The rules derive that both cars in image i1 are toy cars, while the cars in image i2 are not because their boxes are not closer to the camera.
  • Example: Solving Sudoku Puzzle in Image: For image-based Sudoku, NeurASP uses a neural network to identify digits and ASP rules to assign values and enforce row, column, and box constraints.The perception network outputs probabilities for empty and digit values in all 81 cells, while ASP completes empty cells subject to the rules.
  • Example: Solving Sudoku Puzzle in Image: Reasoning improves Sudoku perception accuracy, and complete solving further improves it; solution accuracy equals perception accuracy because ASP returns a fully correct solution after correct identification.The program without the solution rule checks constraint satisfaction, whereas the full program also checks whether a solution exists.
  • Example: Solving Sudoku Puzzle in Image: The same trained perception model can support Sudoku variants by adding rules, avoiding a separate end-to-end model and large dataset for each variation.For Offset Sudoku, colored images require retraining with three channels; 70 training examples were reported for 100% perception accuracy.

4 Learning in NeurASP

NeurASP trains neural networks by backpropagating probabilities and semantic constraints through an ASP rule layer. Across digit addition, Sudoku, and shortest-path experiments, structured rules improved or constrained learning, while computational scalability remained a boundary.

  • 4.1 Gradient Ascent with NeurASP: NeurASP trains neural networks by maximizing the probability of observations or stable models satisfying ASP constraints.Gradients from the rule layer are backpropagated through neural atoms into neural-network parameters.
  • 4.2 Experiment 1: Learning Digit Classification from Addition: In digit addition, NeurASP and DeepProbLog converged much faster than CNN and achieved almost the same accuracy at each iteration.NeurASP required less training time than DeepProbLog in this experiment.
  • 4.2 Experiment 1: Learning Digit Classification from Addition: NeurASP’s lower training time than DeepProbLog reflects a computational trade-off between stable-model enumeration and constructing SDDs.The paper notes that other examples may show the opposite behavior.
  • 4.3 Experiment 2: Learning How to Solve Sudoku: Current NeurASP implementation is not as scalable as neural-network training, making training on 1 million Sudoku examples take too long.Using a smaller dataset, the baseline reached 29.1% whole-board accuracy and 89.3% grid-cell accuracy.
  • 4.3 Experiment 2: Learning How to Solve Sudoku: 66.5% whole-board accuracy and 96.9% grid-cell accuracy were achieved by Msol trained with NeurASP on Sudoku.These results were obtained after 63 epochs, with rules used during training but not testing.
  • 4.4 Experiment 3: Learning Shortest Path (SP): For shortest-path learning, adding simple-path, reachability, and optimization constraints significantly improved training, whereas the randomly varying removed-edge constraint reduced accuracy.With the simple-path constraint, label accuracy was 28.9% and simple-path accuracy was 96.6%.

5 Related Work

NeurASP belongs to a broader effort to combine neural perception with symbolic reasoning. It differs from related approaches through ASP-based computation and support for more expressive knowledge-representation constraints.

  • Neural-symbolic integration: DeepProbLog is the closest related approach, but it relies on sequential decision diagrams while NeurASP uses an ASP solver internally.Both approaches integrate neural outputs with logical reasoning.
  • Expressive reasoning: NeurASP supports expressive ASP reasoning, including defaults, aggregates, and optimization rules.This distinguishes its reasoning language from approaches using simpler constraint formalisms.
  • Semantic constraints: Unlike the simple propositional constraints used by Xu et al., NeurASP uses ASP to encode complex knowledge-representation constraints more conveniently.The comparison concerns the expressiveness and encoding convenience of the constraint language.
  • Differentiable logic models: Neural Theorem Prover embeds logical conjunction and disjunction into differentiable neural modules constructed from proof trees.This represents a different strategy from NeurASP’s extension of answer set programs.
  • Relational neural models: Graph neural networks perform relational reasoning by learning message functions between nodes, but the cited Sudoku example uses textual rather than image input.The paper characterizes this input setting as restrictive compared with its broader target.
  • Data efficiency: Neuro-Symbolic Concept Learner used 10% of CLEVR training data while achieving 98% accuracy, and the paper relates this data-efficiency pattern to symbolic reasoning.The comparison is presented as qualitatively similar to NeurASP’s fewer-data results.

6 Conclusion

NeurASP combines ASP reasoning with neural networks to improve perception and learning, including when data are limited. Its prototype implementation remains not highly scalable because stable models are enumerated naively.

  • NeurASP improves neural-network perception by applying reasoning over perceived objects.
  • NeurASP helps neural networks learn better by using knowledge and constraints to compensate for small datasets.
  • Its simple ASP–neural-network integration preserves the individual forms of both components and can use advances in each.
  • The current implementation is a prototype and is not highly scalable because it naively enumerates stable models.

A Extend NeurASP With Probabilistic Rules

This section extends NeurASP with probabilistic rules by defining semantics through a translation to Multi-Valued Probabilistic Programs. It assumes familiarity with ASP-Core2.

  • The extended NeurASP includes probabilistic rules in addition to its existing framework.
  • Its semantics are defined by translating the extended program to Multi-Valued Probabilistic Programs.
  • The presentation assumes that readers are familiar with ASP-Core2.

A.1 Multi-Valued Probabilistic Programs

Multi-Valued Probabilistic Programs combine probabilistic rules with regular ASP rules and define stable-model probabilities from probabilistic atom assignments and model multiplicity.

  • Probabilistic rules: A probabilistic rule assigns probabilities to all values of one probabilistic constant, with probabilities summing to 1.
  • Program structure: An MVPP is the union of probabilistic rules and regular ASP rules whose heads contain no probabilistic constants.
  • Semantics: The translation replaces each probabilistic rule with an exactly-one choice over its possible values.
  • Semantics: Non-probabilistic constants may have no assigned values under the translated ASP program.
  • Semantics: The probability of a stable model multiplies the probabilities of its probabilistic atoms and divides by the number of stable models agreeing with that assignment.

A.2 Define NeurASP On a Translation to MVPP

NeurASP represents neural-network predictions as probabilistic atoms and defines its stable models and probabilities through an MVPP counterpart. Neural atoms connect symbolic terms to network inputs and outputs.

  • Neural atoms: A neural atom is shorthand for probabilistic rules whose probabilities come from neural-network outputs.
  • Network interface: The network output is a matrix whose rows represent random events and whose columns represent their possible outcomes.
  • Neural atoms: The neural-atom syntax names a network, points to input data through terms, and lists all possible outcomes.
  • Network interface: Each neural atom introduces propositional atoms for network outcomes, and the network output supplies their probabilities.
  • Translation semantics: NeurASP replaces each neural atom with probabilistic rules whose atom probabilities are obtained from the network output for the mapped input tensor.
  • Translation semantics: Stable models and their probabilities are inherited from the resulting MVPP counterpart.

B Proof of Proposition 1

The proof characterizes the probability of an atom by restricting probability mass to stable models and using the fact that each stable model assigns one value to the atom.

  • Stable models that do not satisfy the NeurASP program contribute zero probability.The proof explicitly uses PΠ(θ)(I) = 0 when I is not a stable model of Π(θ).
  • Every stable model assigns c one value v∗, so probability mass over c's possible values is fully accounted for.
  • The probability of an alternative value c = v′ is obtained from the remaining probability mass after subtracting the other values.

D Detailed Description of Learning Algorithms for NeurASP

NeurASP trains neural-network parameters by maximizing the log-likelihood of observed ASP constraints, using either exact or sampled stable-model computations. Neural outputs provide atom probabilities, while ASP stable models and CLINGO supply the symbolic structure needed for gradient estimation and learning.

  • Learning objective: The learning objective is to find parameters θ̂ that maximize the log-likelihood of observations with positive program probability.Observations are ASP constraints O, and each input mapping D_i supplies tensors to the neural networks.
  • Gradient computation: Neural-network outputs are converted into atom probabilities, whose gradients with respect to θ are computed by back-propagation.The gradients of probabilities over stable models are then computed from these neural-output gradients.
  • Exact computation: Exact learning enumerates all stable models satisfying each observation and applies gradientsSM to update θ.Algorithm 1 repeatedly computes neural outputs, back-propagates through them, finds satisfying stable models with CLINGO, and updates the parameters.
  • Sampling computation: Sampling-based learning approximates the stable-model gradients by drawing a specified number of satisfying stable models according to their probability distribution.Algorithm 3 samples models after computing neural outputs and uses the sampled set in gradientsSM.
  • Exact computation: gradientsSM handles singleton and multiple stable-model sets with separate gradient calculations for atom assignments and probability normalization.The procedure returns one gradient for each neural atom probability.
  • Sampling computation: sampleSM repeatedly samples choice-rule assignments, enumerates the resulting stable models with CLINGO, and stops after collecting enough samples.Choice rules are replaced by facts according to the atom-probability distribution before stable-model generation.
Loading 2307.07700v1…