NeurASP: Embracing Neural Networks into Answer Set Programming
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.
Zhun Yang, Adam Ishay, Joohyung Lee
# NeurASP: Embracing Neural Networks into Answer Set Programming

###### Abstract

We present \(\mathrm{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, \(\mathrm{NeurASP}\) provides a simple and effective way to integrate sub-symbolic and symbolic computation. We demonstrate how \(\mathrm{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, \(\mathrm{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

The integration of low-level perception with high-level reasoning is one of the oldest problems in Artificial Intelligence. Today, the topic is revisited with the recent rise of deep neural networks. Several proposals were made to implement the reasoning process in complex neural network architectures, e.g., [1, 1, 1, 2, 3, 4, 5, 6, 7]. However, it is still not clear how complex and high-level reasoning, such as default reasoning [15], ontology reasoning [1], and causal reasoning [2], can be successfully computed by these approaches. The latter subject has been well-studied in the area of knowledge representation (KR), but many KR formalisms, including answer set programming (ASP) [11, 12], are logic-oriented and do not incorporate high-dimensional vector space and pre-trained models for perception tasks as handled in deep learning, which limits the applicability of KR in many practical applications involving data and uncertainty.

In this paper, we present a simple extension of answer set programs by embracing neural networks. Following the idea of DeepProbLog [13], by treating the neural network output as the probability distribution over atomic facts in answer set programs, the proposed \(\mathrm{NeurASP}\) provides a simple and effective way to integrate sub-symbolic and symbolic computation.

We demonstrate how \(\mathrm{NeurASP}\) can be useful for some tasks where both perception and reasoning are required. Reasoning can help identify perception mistakes that violate semantic constraints, which in turn can make perception more robust. For example, a neural network for object detection may return a bounding box and its classification "car," but it may not be clear whether it is a real car or a toy car. The distinction can be made by applying reasoning about the relations with the surrounding objects and using commonsense knowledge. Or when it is unclear whether a round object attached to the car is a wheel or a doughnut, the reasoner could conclude that it is more likely to be a wheel by applying commonsense knowledge. In the case of a neural network that recognizes digits in a given Sudoku board, the neural network may get confused if a digit next to \(1\) in the same row is \(1\) or \(2\), but the reasoner can conclude that it cannot be \(1\) by applying the constraints for Sudoku.

Another benefit of this hybrid approach is that it alleviates the burden of neural networks when the constraints/knowledge are already given. Instead of building a large end-to-end neural network that learns to solve a Sudoku puzzle given as an image, we can let a neural network only do digit recognition and use ASP to find the solution of the recognized board. This makes the design of the neural network simpler and the required training dataset much smaller. Also, when we need to solve some variation of Sudoku, such as Anti-knight or Offset Sudoku, the modification is simpler than training another large neural network from scratch to solve the new puzzle.

\(\mathrm{NeurASP}\) can also be used to train a neural network together with rules so that a neural network not only learns from implicit correlations from the data but also from explicit complex semantic constraints expressed by ASP rules. The _semantic loss_[22] obtained from the reasoning module can be backpropagated into the rule layer and then further into neural networks via neural atoms. This sometimes makes a neural network learn better even with fewer data.

Compared to DeepProbLog, \(\mathrm{NeurASP}\) supports a rich set
of KR constructs supported by answer set programming that allows for convenient representation of complex knowledge. It utilizes an ASP solver in computation instead of constructing circuits as in DeepProbLog.

The paper is organized as follows. Section 2 introduces the syntax and the semantics of \(\mathrm{NeurASP}\). Section 3 illustrates how reasoning in \(\mathrm{NeurASP}\) can enhance the perception result by considering relations among objects perceived by pre-trained neural networks. Section 4 presents learning in \(\mathrm{NeurASP}\) where ASP rules work as a semantic regularizer for training neural networks so that neural networks are trained not only from data but also from rules. Section 5 examines related works and Section 6 concludes.

The implementation of \(\mathrm{NeurASP}\), as well as codes used for the experiments, is publicly available online at

[https://github.com/azreasoners/NeurASP](https://github.com/azreasoners/NeurASP).

## 2 \(\mathrm{NeurASP}\)

We present the syntax and the semantics of \(\mathrm{NeurASP}\).

### Syntax

We assume that neural network \(M\) allows an arbitrary tensor as input whereas the output is a matrix in \(\mathbb{R}^{e\times n}\), where \(e\) is the number of random events predicted by the neural network and \(n\) is the number of possible outcomes for each random event. Each row of the matrix represents the probability distribution of the outcomes of each event. For example, if \(M\) is a neural network for MNIST digit classification, then the input is a tensor representation of a digit image, \(e\) is \(1\), and \(n\) is \(10\). If \(M\) is a neural network that outputs a Boolean value for each edge in a graph, then \(e\) is the number of edges and \(n\) is \(2\). Given an input tensor \(\mathbf{t}\), by \(M(\mathbf{t})\), we denote the output matrix of \(M\). The value \(M(\mathbf{t})[i,j]\) (where \(i\in\{1,\ldots,e\}\), \(j\in\{1,\ldots,n\}\)) is the probability of the \(j\)-th outcome of the \(i\)-th event upon the input \(\mathbf{t}\).

In \(\mathrm{NeurASP}\), the neural network \(M\) above can be represented by a _neural atom_ of the form

\[nn(m(e,t),[v_{1},\ldots,v_{n}]), \tag{1}\]

where (i) \(nn\) is a reserved keyword to denote a neural atom; (ii) \(m\) is an identifier (symbolic name) of the neural network \(M\); (iii) \(t\) is a list of terms that serves as a "pointer" to an input data; related to it, there is a mapping \(\mathbf{D}\) (implemented by an external Python code) that turns \(t\) into an input tensor; (iv) \(v_{1},\ldots,v_{n}\) represent all \(n\) possible outcomes of each of the \(e\) random events.

Each neural atom (1) introduces propositional atoms of the form \(c=v\), where \(c\in\{m_{1}(t),\ldots,m_{e}(t)\}\) and \(v\in\{v_{1},\ldots,v_{n}\}\). The output of the neural network provides the probabilities of the introduced atoms (defined in Section 2.2).

**Example 1**: _Let \(M_{digit}\) be a neural network that classifies an MNIST digit image. The input of \(M_{digit}\) is (a tensor representation of) an image and the output is a matrix in \(\mathbb{R}^{1\times 10}\). The neural network can be represented by the neural atom_

\[nn(digit(1,d),\ [0,1,2,3,4,5,6,7,8,9]),\]

_which introduces propositional atoms \(digit_{1}(d)=0\), \(digit_{1}(d)=1\), \(\ldots\), \(digit_{1}(d)=9\)._

**Example 2**: _Let \(M_{sp}\) be another neural network for finding the shortest path in a graph with 24 edges. The input is a tensor encoding the graph and the start/end nodes of the path, and the output is a matrix in \(\mathbb{R}^{24\times 2}\). This neural network can be represented by the neural atom_

\[nn(sp(24,g),\ [\textsc{true},\textsc{false}]).\]

A \(\mathrm{NeurASP}\)_program_\(\Pi\) is the union of \(\Pi^{asp}\) and \(\Pi^{nn}\), where \(\Pi^{asp}\) is a set of propositional rules (standard rules as in ASP-Core 2 (Calimeri _et al._, 2020)) and \(\Pi^{nn}\) is a set of neural atoms. Let \(\sigma^{nn}\) be the set of all atoms \(m_{i}(t)=v_{j}\) that is obtained from the neural atoms in \(\Pi^{nn}\) as described above. We require that, in each rule \(\imath Head\leftarrow\imath Body\) in \(\Pi^{asp}\), no atoms in \(\sigma^{nn}\) appear in \(\imath Head\).

We could allow schematic variables into \(\Pi\), which are understood in terms of grounding as in standard answer set programs. We find it convenient to use rules of the form

\[nn(m(e,t),[v_{1},\ldots,v_{n}])\leftarrow\imath Body \tag{2}\]

where \(\imath Body\) is either identified by \(\top\) or \(\bot\) during grounding so that (2) can be viewed as an abbreviation of multiple (variable-free) neural atoms (1).

**Example 3**: _An example \(\mathrm{NeurASP}\) program \(\Pi_{digit}\) is as follows, where \(d_{1}\) and \(d_{2}\) are terms representing two images. Each image is classified by neural network \(M_{digit}\) as one of the values in \(\{0,\ldots,9\}\). The addition of two digit-images is the sum of their values._

\[\begin{array}{l}img(d_{1}).\\ img(d_{2}).\\ nn(digit(1,X),[0,1,2,3,4,5,6,7,8,9])\leftarrow img(X).\\ addition(A,B,N)\leftarrow\mathit{digit}_{1}(A)=N_{1},digit_{1}(B)=N_{2},\\ N=N_{1}+N_{2}.\end{array} \tag{3}\]

_The neural network \(M_{digit}\) outputs 10 probabilities for each image. The addition is applied once the digits are recognized and its probability is induced from the perception as we explain in the next section._

### Semantics

For any \(\mathrm{NeurASP}\) program \(\Pi=\Pi^{asp}\cup\Pi^{nn}\), we first obtain its ASP counterpart \(\Pi^{\prime}=\Pi^{asp}\cup\Pi^{ch}\) where \(\Pi^{ch}\) consists of the following set of rules for each neural atom (1) in \(\Pi^{nn}\)

\[\{m_{i}(t)=v_{1};\ \ldots;m_{i}(t)=v_{n}\}=1\quad\text{for }i\in\{1,\ldots e\}.\]

The above rule (in the language of clingo) means to choose exactly one atom in between the set braces.1 We define the _stable models_ of \(\Pi\) as the stable models of \(\Pi^{\prime}\), and define the _total choices_ of \(\Pi\) as the stable models of \(\Pi^{ch}\). For each total choice \(C\) of \(\Pi\), we use \(\imath Num(C,\Pi)\) to denote the number of stable models of \(\Pi\) that satisfy \(C\). We require a \(\mathrm{NeurASP}\) program \(\Pi\) to be _coherent_ such that \(\imath Num(C,\Pi)>0\) for every total choice \(C\) of \(\Pi\).

Footnote 1: In practice, each atom \(m_{i}(t)=v\) is written as \(m(i,t,v)\).

To define the probability of a stable model, we first define the probability of an atom \(m_{i}(t)=v_{j}\) in \(\sigma^{nn}\). Recall that there is an external mapping \(\mathbf{D}\) that turns \(t\) into a specific
input tensor of \(M\). The probability of each atom \(m_{i}(t)\!=\!v_{j}\) is defined as \(M(\mathbf{D}(t))[i,j]\):

\[P_{\Pi}(m_{i}(t)\!=\!v_{j})=M(\mathbf{D}(t))[i,j].\]

For instance, recall that the output matrix of \(M_{digit}(\mathbf{D}(d))\) in Example 3 is in \(\mathbb{R}^{1\times 10}\). The probability of atom \(digit_{1}(d)=k\) is \(M_{digit}(\mathbf{D}(d))[1,k\!+\!1]\).

Given an interpretation \(I\), by \(I|_{\sigma^{nn}}\), we denote the projection of \(I\) onto \(\sigma^{nn}\). Since \(I|_{\sigma^{nn}}\) is a total choice of \(\Pi\), \(1Num(I|_{\sigma^{nn}},\Pi)\) is the number of stable models of \(\Pi\) that agree with \(I|_{\sigma^{nn}}\) on \(\sigma^{nn}\).

The probability of a stable model \(I\) of \(\Pi\) is defined as the product of the probability of each atom \(c=v\) in \(I|_{\sigma^{nn}}\), divided by the number of stable models of \(\Pi\) that agree with \(I|_{\sigma^{nn}}\) on \(\sigma^{nn}\). That is, for any interpretation \(I\),

\[P_{\Pi}(I)=\begin{cases}\frac{\prod\limits_{c=v\in I|_{\sigma^{nn}}}P_{\Pi}( c=v)}{1Num(I|_{\sigma^{nn}},\Pi)}&\text{if $I$ is a stable model of $\Pi$;}\\ 0&\text{otherwise.}\end{cases}\]

An _observation_ is a set of ASP constraints (i.e., rules of the form \(\perp\leftarrow\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
The neural network model \(M_{label}\) outputs that the red boxes are persons, the yellow boxes are cars, and the green box is a truck. Upon this input and the rules above, \(\mathrm{NeurASP}\) allows us to derive that the two cars in image \(i_{1}\) are _toy_ cars, whereas the two cars in image \(i_{2}\) are not: although they are surrounded by smaller boxes than those of humans, their boxes are not closer to the camera.

### Example: Solving Sudoku Puzzle in Image

Consider the task of solving a Sudoku puzzle given as an image. In \(\mathrm{NeurASP}\), we could use a neural network to recognize the digits in the given puzzle and use an ASP solver to compute the solution instead of having a single network that accounts for both perception and solving.

We use the following \(\mathrm{NeurASP}\) program \(\Pi_{sudoku}\) to first identify the digits in each grid cell on the board and then find the solution by assigning digits to all empty grid cells. 3

Footnote 3: The expression \(\{a(R,C,N):N=1..9\}=1\) is a shorthand for \(\{a(R,C,1);\ldots;a(R,C,9)\}=1\) in the language of clingo.

% identify the number in each of the 81 positions nn(identify(81, img), [empty,1,2,3,4,5,6,7,8,9]).

% assign one number N to each position (R,C)

(R,C,N) :- identify(Pos, img,N), R=Pos/9, C=Pos\(\backslash\)9, N!=empty.

{a(R,C,N):N=1..9}=1 - identify(Pos, img, empty), R=Pos/9, C=Pos\(\backslash\)9.

% no number repeats in the same row

:- a(R,C,N), a(R,C2,N), C11=C2.

% no number repeats in the same column

:- a(R,C,N), a(R2,C,N), R11=R2.

% no number repeats in the same 3*3 box

:- a(R,C,N), a(R1,C1,N), R1=R1, C1=C1,

((R/3)*3 + C/3) = ((R1/3)*3 + C/3) = ((R1/3)*3 + C1/3).

The neural network model \(M_{identify}\) is rather simple. It is composed of 5 convolutional layers with dropout, a max pooling layer, and a \(1\times 1\) convolutional layer followed by softmax. Given a Sudoku board image (,png file), neural network \(M_{identify}\) outputs a matrix in \(\mathbb{R}^{81\times 10}\), which represents the probabilities of the values (empty, 1,..., 9) in each of the 81 grid cells. The network \(M_{identify}\) is pre-trained using \(\langle image,label\rangle\) pairs, where each \(image\) is a Sudoku board image generated by _OpenSky Sudoku Generator_ ([http://www.opensky.ca/~jdhildeb/software/sudokugen/](http://www.opensky.ca/~jdhildeb/software/sudokugen/)) and each \(label\) is a vector of length 81 in which 0 is used to represent an empty cell at that position.

Let \(Acc_{identify}\) denote the accuracy of identifying all empty cells and the digits on the board given as an image without making a single mistake in a grid cell. Let \(Acc_{sol}\) denote the accuracy of solving a given Sudoku board without making a single mistake in a grid cell. Let \(r\) be the following rule in \(\Pi_{sudoku}\):

{a(R,C,N):N=1..9}=1 :- identify(Pos, img, empty), R=Pos/9, C=Pos\(\backslash\)9.

Intuitively, \(\Pi_{sudoku}\setminus r\) only checks whether the identified numbers (by neural network \(M_{identify}\)) satisfy the three constraints (the last three rules of \(\Pi_{sudoku}\)), while \(\Pi_{sudoku}\) further checks whether there exists a solution given the identified numbers. As shown in Table 1, the use of reasoning in \(\mathrm{NeurASP}\) program \(\Pi_{sudoku}\setminus r\) improves the accuracy \(Acc_{identify}\) of the neural network \(M_{identify}\) as explained in the introduction. The accuracy \(Acc_{identify}\) is further improved by trying to solve Sudoku completely using \(\Pi_{sudoku}\). Note that the solution accuracy \(Acc_{sol}\) of \(\Pi_{sudoku}\) is equal to the perception accuracy \(Acc_{identify}\) of \(\Pi_{sudoku}\) since the ASP yields a 100% correct solution once the board is correctly identified.

Palm _et al._ [2018] use a Graph Neural Network to solve Sudoku but the work restricts attention to textual input of the Sudoku board, not images as we do. Their work achieves 96.6% accuracy after training with 216,000 examples. In comparison, even with the more challenging task of accepting images as input, the number of training examples we used is \(15-25\), which is much less than the number of training examples used in [Palm _et al._, 2018]. Our work takes advantage of the fact that in a problem like Sudoku, where the constraints are explicitly given, a neural network only needs to focus on perception tasks, which is simpler than learning the perception and reasoning together.

Furthermore, using the same trained perception neural network \(M_{identify}\), we can solve some elaborations of Sudoku problems by adding the following rules:

**[Anti-knight Sudoku]** No number repeats at a knight move

:- a(R1,C1,N), a(R2,C2,N), |R1-R2|+|C1-C2|=3.

**[Sudoku-X]** No number repeats at the diagonals

:- a(R1,C1,N), a(R2,C2,N), R1=C1, R2=C2, R11=R2.

:- a(R1,C1,N), a(R2,C2,N), R1+C1=8, R2+C2=8, R11=R2.

With neural network only approach, since the neural network needs to learn both perception and reasoning, each of the above variations would require training a complex and different model with a big dataset. However, with \(\mathrm{NeurASP}\), the neural network only needs to recognize digits on the board. Thus solving each Sudoku variation above uses the same pre-trained model for the image input and we only need to add the aforementioned rules to \(\Pi_{sudoku}\).

Some Sudoku variations, such as Offset Sudoku, are in colored images. In this case, we need to increase the number of

\begin{table}
\begin{tabular}{c|c|c|c|c} \hline \hline Num of & \(Acc_{identify}\) of & \(Acc_{identify}\) of & \(Acc_{identify}\) of & \(Acc_{sol}\) of \\ Train Data & \(M_{identify}\) & \(\mathrm{NeurASP}\) w/ & \(\mathrm{NeurASP}\) w/ & \(\mathrm{NeurASP}\) w/ \\  & & \(\Pi_{sudoku}\setminus r\) & \(\Pi_{sudoku}\) & \(\Pi_{sudoku}\) \\ \hline
15 & 15\% & 49\% & 71\% & 71\% \\
17 & 31\% & 62\% & 80\% & 80\% \\
19 & 72\% & 90\% & 95\% & 95\% \\
21 & 85\% & 95\% & 98\% & 98\% \\
23 & 93\% & 99\% & 100\% & 100\% \\
25 & 100\% & 100\% & 100\% & 100\% \\ \hline \hline \end{tabular}
\end{table}
Table 1: Sudoku: Accuracy on Test Data
channels of \(M_{identify}\) from 1 to 3, and need to retrain the neural network with the colored images. Although not completely elaboration tolerant, compared to the pure neural network approach, this is significantly simpler. For instance, the number of training data needed to get 100% perception accuracy for Offset Sudoku (\(Acc_{identify}\)) is 70, which is still much smaller than what the end-to-end Sudoku solver would require. Using the new network trained, we only need to add the following rule to \(\Pi_{sudoku}\).

**[Offset Sudoku]** No number repeats at the same relative position in 3*3 boxes

:- a(R1,C1,N), a(R2,C2,N), R1\(\backslash\)3 = R2\(\backslash\)3, C1\(\backslash\)3 = C2\(\backslash\)3, R1!= R2, C1!= C2.

## 4 Learning in \(\mathrm{NeurASP}\)

We show how the semantic constraints expressed in \(\mathrm{NeurASP}\) can be used to train neural networks better.

### Gradient Ascent with \(\mathrm{NeurASP}\)

In this section, we denote a \(\mathrm{NeurASP}\) program by \(\Pi(\mathbf{\theta})\) where \(\mathbf{\theta}\) is the set of the parameters in the neural network models associated with \(\Pi\). Assume a \(\mathrm{NeurASP}\) program \(\Pi(\mathbf{\theta})\) and a set \(\mathbf{O}\) of observations such that \(P_{\Pi(\mathbf{\theta})}(O)>0\) for each \(O\in\mathbf{O}\). The task is to find \(\hat{\mathbf{\theta}}\) that maximizes the log-likelihood of observations \(\mathbf{O}\) under program \(\Pi(\mathbf{\theta})\), i.e.,

\[\hat{\mathbf{\theta}}\in\underset{\mathbf{\theta}}{\mathrm{argmax}}\ log(P_{\Pi(\mathbf{ \theta})}(\mathbf{O})),\]

which is equivalent to

\[\hat{\mathbf{\theta}}\in\underset{\mathbf{\theta}}{\mathrm{argmax}}\ \sum\limits_{O\in \mathbf{O}}log(P_{\Pi(\mathbf{\theta})}(O)).\]

Let \(\mathbf{p}\) denote the probabilities of the atoms in \(\sigma^{nn}\). Since \(\mathbf{p}\) is indeed the outputs of the neural networks in \(\Pi(\mathbf{\theta})\), we can compute the gradient of \(\mathbf{p}\) w.r.t. \(\mathbf{\theta}\) through backpropagation. Then the gradient of \(\sum\limits_{O\in\mathbf{O}}log(P_{\Pi(\mathbf{\theta})}(O))\) w.r.t. \(\mathbf{\theta}\) is

\[\underset{O\in\mathbf{O}}{\frac{\partial\sum\limits_{O\in\mathbf{O}}log(P_{ \Pi(\mathbf{\theta})}(O))}{\partial\mathbf{\theta}}} =\sum\limits_{O\in\mathbf{O}}\frac{\partial log(P_{\Pi(\mathbf{\theta })}(O))}{\partial\mathbf{p}}\times\frac{\partial\mathbf{p}}{\partial\mathbf{\theta}}\]

where \(\frac{\partial\mathbf{p}}{\partial\mathbf{\theta}}\) can be computed through the usual neural network backpropagation, while \(\frac{\partial log(P_{\Pi(\mathbf{\theta})}(O))}{\partial p}\) for each \(p\in\mathbf{p}\) can be computed as follows.

**Proposition 1**: _Let \(\Pi(\mathbf{\theta})\) be a \(\mathrm{NeurASP}\) program and let \(O\) be an observation such that \(P_{\Pi(\mathbf{\theta})}(O)>0\). Let \(p\) denote the probability of an atom \(c=v\) in \(\sigma^{nn}\), i.e., \(p\) denotes \(P_{\Pi(\mathbf{\theta})}(c=v)\). We have that4_

Footnote 4: \(\frac{P_{\Pi(\mathbf{\theta})}(I)}{P_{\Pi(\mathbf{\theta})}(c=v)}\) and \(\frac{P_{\Pi(\mathbf{\theta})}(I)}{P_{\Pi(\mathbf{\theta})}(c=v^{\prime})}\) are still well-defined since the denominators have common factors in \(P_{\Pi(\mathbf{\theta})}(I)\).

\[\frac{\partial log(P_{\Pi(\mathbf{\theta})}(O))}{\partial p}=\frac{\sum\limits_{I,\ I=0}^{I,\ T=0}\frac{P_{\Pi(\mathbf{\theta})}(I)}{P_{\Pi(\mathbf{\theta})}(c=v)}- \sum\limits_{I,\nu:\ l=0}^{I,\nu:\ l=0}\frac{P_{\Pi(\mathbf{\theta})}(I)}{P_{\Pi( \mathbf{\theta})}(c=v^{\prime})}}{\sum\limits_{I:\ l=0}P_{\Pi(\mathbf{\theta})}(I)}.\]

Intuitively, the proposition tells us that each interpretation \(I\) that satisfies \(O\) tends to increase the value of \(p\) if \(I\models c=v\), and decrease the value of \(p\) if \(I\models c=v^{\prime}\) such that \(v^{\prime}\neq v\). \(\mathrm{NeurASP}\) internally calls clingo to find all stable models \(I\) of \(\Pi(\mathbf{\theta})\) that satisfy \(O\) and uses PyTorch to obtain the probability of each atom \(c=v\) in \(\sigma^{nn}\).

### Experiment 1: Learning Digit Classification from Addition

All experiments in Section 4 were done on Ubuntu 18.04.2 LTS with two 10-cores CPU Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz and four GP104 [GeForce GTX 1080].

The digit addition problem is a simple example used in [10] to illustrate DeepProbLog's ability for both logical reasoning and deep learning. The task is, given a pair of digit images (MNIST) and their sum as the label, to let a neural network learn the digit classification of the input images.

The problem can be represented by \(\mathrm{NeurASP}\) program \(\Pi_{digit}\) in Example 3. For comparison, we use the same dataset and the same structure of the neural network model used in [10] to train the digit classifier \(M_{digit}\) in \(\Pi_{digit}\). For each pair of images denoted by \(d_{1}\) and \(d_{2}\) and their sum \(n\), we construct the ASP constraint \(\leftarrow\)\({\it{not}}\,addition(d_{1},d_{2},n)\) as the observation \(O\). The training target is to maximize \(log(P_{\Pi_{digit}}(O))\).

Figure 2 shows how the forward and the backward propagations are done for \(\mathrm{NeurASP}\) program \(\Pi_{digit}\) in Example 3. The left-to-right direction is the forward computation of the neural network extended with the rule layer, whose output is the probability of the observation \(O\). The right-to-left direction shows how the gradient from the rule layer is backpropagated further into the neural network by the chain rule to update all neural network parameters so as to find the parameter values that maximize the probability of the given observation.

Figure 3 shows the accuracy on the test data after each training iteration. The method CNN denotes the baseline used in [10] where a convolutional neural network (with more parameters) is trained to classify the concatenation of the two images into the 19 possible sums. As we can see, the neural networks trained by \(\mathrm{NeurASP}\) and DeepProbLog converge much faster than CNN and have almost the same accuracy at each iteration. However, \(\mathrm{NeurASP}\) spends much less time on training compared to DeepProbLog. The time reported is for one epoch (30,000 iterations in gradient descent). This is because DeepProbLog constructs an

Figure 2: NeurASP Gradient Propagation
SDD (Sequential Decision Diagram) at each iteration for each training instance (i.e., each pair of images). This example illustrates that generating many SDDs could be more time-consuming than enumerating stable models in \(\mathrm{NeurASP}\) computation. In general, there is a trade-off between the two methods and other examples may show the opposite behavior.

### Experiment 2: Learning How to Solve Sudoku

In section 3.2, we used a neural network \(M_{identify}\) to identify the numbers on a Sudoku board and used ASP rules to solve the Sudoku problem. In this section, we use a neural network to learn to solve Sudoku problems. The task is, given the _textual representation_ of an unsolved Sudoku board (in the form of a \(9\times 9\) matrix where an empty cell is represented by 0), to let a neural network learn to predict the solution of the Sudoku board.

We use the neural network \(M_{sol}\) from [10] as the baseline. \(M_{sol}\) is composed of 9 convolutional layers and a 1x1 convolution layer followed by softmax. Park trained \(M_{sol}\) using 1 million examples and achieved 70% accuracy using an "inference trick": instead of predicting digits for all empty cells at once, which leads to a poor accuracy, the most probable grid-cell value was predicted one by one.

Since the current \(\mathrm{NeurASP}\) implementation is not as scalable as neural network training, training on 1 million examples takes too long. Thus, we construct a dataset of 63,000 + 1000 \(\langle config,label\rangle\) pairs for training and testing. Using Park's method on this relatively small dataset, we observe that \(M_{sol}\)'s highest whole-board accuracy \(Acc_{sol}\)5 is only 29.1% and \(M_{sol}\)'s highest grid-cell accuracy6 is only 89.3% after 63 epochs of training.

Footnote 5: The percentage of Sudoku examples that are correctly solved.

Footnote 6: The percentage of grid cells having correct digits regardless whether the Sudoku solution is correct.

We get a better result by training \(M_{sol}\) with the \(\mathrm{NeurASP}\) program \(\Pi_{sol}\). The program is almost the same as \(\Pi_{identify}\) in Section 3.2 except that it uses \(M_{sol}\) in place of \(M_{identify}\) and the first three rules of \(\Pi_{identify}\) are replaced with

```
nn(sol(81,img),[1,2,3,4,5,6,7,8,9]). n(R,C,N):-sol(Pos,img,N),R=Pos/9,C=Pos\(\backslash\)9.
```

because we do not have to assign the value empty in solving Sudoku.

We trained \(M_{sol}\) using \(\mathrm{NeurASP}\) where the training target is to maximize the probability of all stable models that satisfy the observation. On the same test data, after 63 epochs of training, the highest whole-board accuracy of \(M_{sol}\) trained this way is 66.5% and the highest grid-cell accuracy is 96.9% (In other words, we use rules only during training and not during testing). This indicates that including such structured knowledge sometimes helps the training of the neural network significantly.

### Experiment 3: Learning Shortest Path (SP)

The experiment is about, given a graph and two points, finding the shortest path between them. We use the dataset from [20], which was used to demonstrate the effectiveness of semantic constraints for enhanced neural network learning. Each example is a 4 by 4 grid \(G=(V,E)\), where \(|V|=16,|E|=24\). The source and the destination nodes are randomly picked up, as well as 8 edges are randomly removed to increase the difficulty. The dataset is divided into 60/20/20 train/validation/test examples.

The following \(\mathrm{NeurASP}\) program 7

Footnote 7: \(sp(X,g,true)\) means edge \(X\) is in the shortest path. \(sp(X,Y)\) means there is a path between nodes \(X\) and \(Y\) in the shortest path.

...

\(\mathrm{sp(X,Y):-sp(Y,X)}\).

together with the union of the following 4 constraints defines the shortest path.

```
%[nr]l.Noremovededgesshouldbepredicted :-sp(X,g,true),removed(X).
```

%[p]2.Predictionmustformasimplepath,i.e.,%thedegreeofeachnodemustbeeither0or2 :-X=0..15,#count(Y:sp(X,Y))=1. :-X=0..15,#count(Y:sp(X,Y))>=3. ```

%[r]3.Every2nodesinthepredictionmustbe

%reachable reachable(X,Y):-sp(X,Y). reachable(X,Y):-reachable(X,Z),sp(Z,Y). :-sp(X,A),sp(Y,B),notreachable(X,Y).

%[o]4.Predictedpathshouldcontainleastedges :->sp(X,g,true).[1,X]

In this experiment, we trained the same neural network model \(M_{sp}\) as in [20], a 5-layer Multi-Layer Perceptron (MLP), but with 4 different settings: (i) MLP only; (ii) together with \(\mathrm{NeurASP}\) with the simple-path constraint **(p)** (which is the only constraint used in [20]); 8 (iii) together with \(\mathrm{NeurASP}\) with simple-path, reachability, and optimization constraints **(p-r-o)**; and (iv) together with \(\mathrm{NeurASP}\) with all 4 constraints **(p-r-o-nr)**. 9

Figure 3: \(\mathrm{NeurASP}\) vs. DeepProbLog
Table 2 shows, after 500 epochs of training, the percentage of the predictions on the test data that satisfy each of the constraints **p**, **r**, and **nr**, the path constraint (i.e., **p-r**), the shortest path constraint (i.e., **p-r-o-nr**), and the accuracy w.r.t. the ground truth.

The accuracies for the first experiment (MLP Only) show that \(M_{sp}\) was not trained well only by minimizing the cross-entropy loss of its prediction: 100-28.3 = 71.7% of the predictions are not even a simple-path.

In the remaining experiments (MLP (x)), instead of minimizing the cross-entropy loss, our training target is changed to maximizing the probability of all stable models under certain constraints. The accuracies under the 2nd and 3rd experiments (MLP (p) and MLP (p-r-o) columns) are increased significantly, showing that (i) including such structured knowledge helps the training of the neural network and (ii) the more structured knowledge included, the better \(M_{sp}\) is trained under \(\mathrm{NeurASP}\). Compared to the results from [22], \(M_{sp}\) trained by \(\mathrm{NeurASP}\) with the simple-path constraint **p** (in the 2nd experiment MLP (p) column) obtains a similar accuracy on predicting the label (28.9% v.s. 28.5%) but a higher accuracy on predicting a simple-path (96.6% v.s. 69.9%).

In the 4th experiment (MLP (p-r-o-nr) column) where we added the constraint **nr** saying that "no removed edges can be predicted", the accuracies go down. This is because the new constraint **nr** is about randomly removed edges, changing from one example to another, which is hard to be generalized.

## 5 Related Work

Recent years have observed the rising interests of combining perception and reasoning. As mentioned, the work on DeepProbLog [15] is closest to our work. Some differences are: (i) The computation of DeepProbLog relies on constructing circuits such as sequential decision diagrams (SDD) whereas we use an ASP solver internally. (ii) \(\mathrm{NeurASP}\) employs expressive reasoning originating from answer set programming, such as defaults, aggregates, and optimization rules. This not only gives more expressive reasoning but also allows the more semantic-rich constructs as guide to learning. (iii) DeepProbLog requires each training data to be a single atom, while \(\mathrm{NeurASP}\) allows each training data to be arbitrary propositional formulas.

Also related is using the semantic constraints to train neural networks better [23], but the constraints used in that work are simple propositional formulas whereas we use answer set programming language, in which it is more convenient to encode complex KR constraints. Logic Tensor Network [1] is also related in that it uses neural networks to provide fuzzy values to atoms.

Another approach is to embed logic rules in neural networks by representing logical connectives by mathematical operations and allowing the value of an atom to be a real number. For example, Neural Theorem Prover (NTP) [11] adopts the idea of dynamic neural module networks [1] to embed logic conjunction and disjunction in and/or-module networks. A proof-tree like end-to-end differentiable neural network is then constructed using Prolog's backward chaining algorithm with these modules. Another method that also constructs a proof-tree like neural network is TensorLog [1], which uses matrix multiplication to simulate belief propagation that is tractable under the restriction that each rule is negation-free and can be transformed into a polytree.

Graph neural network (GNN) [18] is a neural network model that is gaining more attention recently. Since a graph can encode objects and relations between objects, by learning message functions between the nodes, one can perform certain relational reasoning over the objects. For example, in [13], it is shown that GNN can do well on Sudoku, but the input there is not an image but a textual representation. However, this is still restrictive compared to the more complex reasoning that KR formalisms provide.

Neuro-Symbolic Concept Learner [16] separates between visual perception and symbolic reasoning. It shows the data-efficiency by using only 10% of the training data and achieving the state-of-the-art 98% accuracy on CLEVR dataset. Our results are similar in the sense that using symbolic reasoning, we could use fewer data to achieve a high accuracy.

\(\mathrm{NeurASP}\) is similar to \(\mathrm{LP}^{\mathrm{MLN}}\)[10] in the sense that they are both probabilistic extensions of ASP and their semantics are defined by translations into ASP [10]. \(\mathrm{LP}^{\mathrm{MLN}}\) allows any rules to be weighted, whereas \(\mathrm{NeurASP}\) uses standard ASP rules.

## 6 Conclusion

We showed that \(\mathrm{NeurASP}\) can improve the neural network's perception result by applying reasoning over perceived objects and also can help neural network learn better by compensating the small size data with knowledge and constraints. Since \(\mathrm{NeurASP}\) is a simple integration of ASP with neural networks, it retains each of ASP and neural networks in individual forms, and can directly utilize the advances in each of them.

The current implementation is a prototype and not highly scalable due to a naive computation of enumerating stable models. The future work includes how to make learning faster, and also analyzing the effects of the semantic constraints more systematically.

\begin{table}
\begin{tabular}{c|c|c|c} \hline \hline Predictions & MLP Only & MLP & MLP \\ satisfying & & (p) & (p-r-o) & (p-r-o-nr) \\ \hline p & 28.3\% & 96.6\% & **100**\% & 30.1\% \\ r & 88.5\% & **100**\% & **100**\% & 87.3\% \\ nr & 32.9\% & 36.3\% & 45.7\% & **70.5**\% \\ p-r & 28.3\% & 96.6\% & **100**\% & 30.1\% \\ p-r-o-nr & 23.0\% & 33.2\% & **45.7**\% & 24.2\% \\ label (ground truth) & 22.4\% & 28.9\% & **40.1**\% & 22.7\% \\ \hline \hline \end{tabular}
\end{table}
Table 2: Shortest Path: Accuracy on Test Data: columns denote MLPs trained with different rules; each row represents the percentage of predictions that satisfy the constraints
## Acknowledgments

We are grateful to the anonymous referees for their useful comments. This work was partially supported by the National Science Foundation under Grant IIS-1815337.
