NeurASP: Embracing Neural Networks into Answer Set Programming

Zhun Yang, Adam Ishay, Joohyung LeeIJCAI 2020 · DOI

TL;DR

This paper introduces NeurASP, a novel framework that seamlessly integrates neural networks with Answer Set Programming (ASP). By treating neural network outputs as probability distributions over atomic facts, NeurASP enables symbolic reasoning to enhance neural network perception and allows ASP rules to act as powerful regularizers for neural network training, leading to improved performance with less data.

What Problem Does This Paper Address?

The field of Artificial Intelligence has long sought to bridge the gap between low-level perception (often handled by deep neural networks) and high-level reasoning (traditionally the domain of symbolic AI, like ASP). While deep learning excels at pattern recognition in high-dimensional data, it struggles with complex, explicit reasoning tasks such as default reasoning or ontology reasoning. Conversely, symbolic AI formalisms like ASP are powerful for reasoning but lack the ability to directly process raw, high-dimensional data like images. This disconnect limits the applicability of KR in practical scenarios involving both data and uncertainty. NeurASP aims to address this by creating a unified framework where neural networks and ASP can mutually benefit each other.

Methods

NeurASP extends Answer Set Programming by introducing "neural atoms." These atoms represent the output of a pre-trained neural network, where the network's output is interpreted as a probability distribution over possible outcomes for a given event.

  • Neural Atoms: A neural atom nn(m(e, t), [v1, ..., vn]) signifies a neural network m that takes input t and predicts e events, each with n possible outcomes v1 to vn. The output of the neural network provides probabilities for propositional atoms like m_i(t) = v_j.
  • Semantics: The semantics of NeurASP are defined by translating neural atoms into standard ASP rules. Specifically, for each neural atom, a set of rules is generated that forces the selection of exactly one outcome for each event. The probability of a stable model is then calculated based on the probabilities assigned by the neural network to the selected atoms.
  • Integration: NeurASP programs consist of standard ASP rules (Hasp) and neural atoms (Inn). The framework allows for reasoning about neural network outputs and using ASP rules to guide neural network learning.

Datasets

The paper describes experiments using the following datasets:

  • MNIST: Used for digit classification experiments.
  • Sudoku Datasets: Generated using OpenSky Sudoku Generator for Sudoku solving experiments.
  • Shortest Path Dataset: A dataset from [Xu et al., 2018] for shortest path finding experiments on 4x4 grids.

No new benchmarks were introduced; existing datasets were adapted to the NeurASP framework.

Key Insights and Ideas

  • Perception Enhancement through Reasoning: ASP rules can identify and correct perception mistakes made by neural networks by enforcing semantic constraints. For example, reasoning can help distinguish a toy car from a real car based on context or ensure Sudoku digits adhere to puzzle rules.
  • Simplified Neural Network Design: By offloading complex reasoning to ASP, neural networks can be designed to focus solely on perception tasks, leading to simpler architectures and smaller training datasets.
  • Semantic Regularization for Training: ASP rules can act as powerful semantic regularizers during neural network training. This allows networks to learn not only from implicit correlations in data but also from explicit, complex semantic constraints, potentially leading to better learning with less data.
  • Flexibility for Problem Variations: NeurASP makes it easier to adapt to variations of a problem (e.g., different Sudoku types) by simply adding new ASP rules, rather than retraining a large end-to-end neural network from scratch.

Key Results

  • Sudoku Solving: NeurASP significantly improved the accuracy of identifying digits in Sudoku puzzles compared to using the neural network alone. For instance, with 21 training examples, NeurASP achieved 95% identification accuracy, compared to 85% for the neural network alone. The overall Sudoku solving accuracy reached 98%.
  • Shortest Path Finding: Integrating ASP constraints with a neural network for shortest path prediction led to substantial improvements in satisfying various path constraints (e.g., simple path, reachability). For example, using the "simple path" constraint improved prediction accuracy from 28.3% to 96.6%.
  • Digit Addition Learning: NeurASP and DeepProbLog (a related approach) showed faster convergence and comparable accuracy to a baseline CNN for learning digit classification from addition, with NeurASP demonstrating less training time.

Limitations and Future Work

  • Scalability: The current implementation's naive computation of enumerating stable models limits its scalability.
  • Future Work: The authors suggest making learning faster and systematically analyzing the effects of semantic constraints. They also mention that while NeurASP is "elaboration tolerant" to some extent (e.g., handling colored images for Sudoku), it's not completely so, suggesting further research into handling more complex variations.

Summary updated

BibTeX
@inproceedings{yang2020neurasp,
  author = {Zhun Yang and Adam Ishay and Joohyung Lee},
  title = {{NeurASP: Embracing Neural Networks into Answer Set Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/243},
}
Figure