A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference
Authors: Emile van Krieken
Thiviyan Thanapalasingam
Jakub M. Tomczak
Frank Van Harmelen
Annette Ten Teije
Venue: NeurIPS 2023 poster (2023)
Keywords: Neurosymbolic Learning
Generative Modeling
Approximate Inference
TL;DR: We scale deep learning models that use symbolic reasoning using a neural network that performs approximate inference

Abstract: We study the problem of combining neural networks with symbolic reasoning. Recently introduced frameworks for Probabilistic Neurosymbolic Learning (PNL), such as DeepProbLog, perform exponential-time exact inference, limiting the scalability of PNL solutions. We introduce Approximate Neurosymbolic Inference (A-NeSI): a new framework for PNL that uses neural networks for scalable approximate inference. A-NeSI 1) performs approximate inference in polynomial time without changing the semantics of probabilistic logics; 2) is trained using data generated by the background knowledge; 3) can generate symbolic explanations of predictions; and 4) can guarantee the satisfaction of logical constraints at test time, which is vital in safety-critical applications. Our experiments show that A-NeSI is the first end-to-end method to solve three neurosymbolic tasks with exponential combinatorial scaling. Finally, our experiments show that A-NeSI achieves explainability and safety without a penalty in performance.

A-NESI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference
Emile van Krieken University of Edinburgh Vrije Universiteit Amsterdam
Thiviyan Thanapalasingam University of Amsterdam
Emile van Krieken@ed.co ac. .uk
Jakub M. Tomczak Eindhoven University of Technology
Frank van Harmelen, Annette ten Teije
Vrije Universiteit Amsterdam
Abstract
We study the problem of combining neural networks with symbolic reasoning. Recently introduced frameworks for Probabilistic Neurosymbolic Learning (PNL), such as DeepProbL perform exponential-tine exact inference, limiting the scalability of PNL solutions. We introduce Approximate Neurosymbolic Inference (A-NESI): new framework for PNL that uses neural networks for scalable approximate inference. A-NESI performs approximate inference in polynomial time without changing the semantics of probabilistic logics; 2) is trained using data generated by the background knowledge; 3) can generate symbolic explanations of predictions; and 4) can guarantee the satisfaction of logical constraints at test time, which is vital safety anfety-criiccal applications. Our experiments show that A-NEST is the first end-to-end method to solve three neurosymbolic tasks with exponential combinatorial scaling. Finally, our experiments show that A-NESI achieves explainability and safety without penalty in performance.
Introduction
Recent work in neurosymbolic learning combines neural perception with symbolic reasoning using symbolic knowledge constrain the neural network [19] to learn perception from weak supervision signals (36), and to improve data efficiency (5 57 Many neurosymbolic methods use
52
38
differentiable logic such fuzzy logies 5 17 probabilistic logies [35] 57 16]. We call the latter Probabilistic Neurosymbolic Learning (PNL) methods. PNL methods add probabilities over discrete truth values to maintain all logical equivalences from classical logic, unlike fuzzy logics [54]. However, performing inference requires solving the weighted model counting (WMC) problem, which is computationally exponential
[3] significantly limiting the kind of tasks that PNL can solve.
We study how to scale PNL to exponentially complex tasks using deep generative modelling (51). Our method called Approximate Neurosymbolic Inference (A-NESI), introduces two neural networks that perform approximate inference over the WMC problem. The prediction model predicts the output of the system, while the explanation model computes which worlds (i.e. which truth assignment to a set of logical symbols) best explain a prediction. We use novel training algorithm to fit both models with data generated using background knowledge: A-NESI samples symbol probabilities from prior and uses the symbolic background knowledge to compute likely outputs given these probabilities. We train both models on these samples. See Figure I for an overview.
A A-NESI combines all benefits of neurosymbolic learning with scalability. Our experiments on the Multi-digit MNISTAdd problem 335 show that, unlike other approaches, A-NESI scales almost
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Forward process
Sample belief
Choose example
Reason
p(P,w,
p(P)
P
p w P)
y
9 (w, y(x)
X
fe
pΦp (y
P p
gΦ (w (wly,
P
- W
Inference model
Perceive
Predict
Explain (optional)
Figure I: Overview of A-NESI. The forward process samples a belief P from a prior, then chooses a world for that belief. The symbolic function e computes its output y. The inference model uses the perception model fe to find a belief P, then uses the prediction model 9s to find the most likely output y for that belief. If also use the optional explanation model, then qy explains the output.
linearly in the number of digits and solves MNISTAdd problems with up 15 digits while maintaining the predictive performance of exact inference. Furthermore, it can produce explanations of predictions and guarantee the satisfaction of logical constraints using a novel symbolic pruner.
The paper is organized as follows. In Section 3 we introduce A-NESI. Section [.1 presents scalable neural networks for approximate inference. Section 3.2
outlines novel training algorithm using data
generated by the background knowledge. Section 3.2.4 extends A-NESI to include an explanation model. Section 3.3 extends A-NESI to guarantee the satisfaction of logical formulas. In Section 4 we perform experiments on three Neurosymbolic tasks that require perception and reasoning. Our experiments on Multi-digit MNISTAdd show that A-NESI learns to predict sums of two numbers with 15 handwritten digits, up from 4 in competing systems. Similarly, A-NESI can classify Sudoku puzzles in 9 grids, up from and find the shortest path in 30 30 grids, up from 12.
2 Problem setup
First, we introduce our inference problem. We will use the MNISTAdd task from 35 as a running example. this problem, we must learn recognize the sum of two MNIST digits using only the sum as a training label. Importantly, we do not provide the labels of the individual MNIST digits.
2.1 Problem components
We introduce four sets representing the spaces of the variables of interest.
X is an input space. In MNISTAdd, this is the pair of MNIST digits x
2. W is structured space of kw different discrete variables wi, each with their domain. Its elements w E W = W1 x X Wkw are worlds or concepts [59] of some x E X. For A the correct world is (5, 8) !0.....9??.
3. Y is structured space of ky discrete variables ys. Elements E = YY= x x Yky represent the output of the neurosymbolic system. Given world = (5,8), the sum is 13. We decompose the sum into individual digits, so (1,3) E {0, x 90.
4. PE A Wil x
A AWWwl where each A [W) is the probability simplex over the options of the variable wi, is belief. assigns probabilities different worlds with p(w) w PP) II P..., That is, P is a parameter for an independent categorical distribution over the kw choices.
kw
We assume access to some symbolic reasoning function W Y that deterministically computes the (structured) output y for any world w. This function captures our background knowledge of the problem and do not impose any constraints its form. For MNISTAdd, takes the two digits (5, 8). sums them, and decomposes the sum by digit to form (1,
2.2 Weighted Model Counting
Together, these components form the Weighted Model Counting (WMC) problem
13
p(y(P) Epp(wp))LL(ww/
(I)

---

The WMC counts the possible worlds v for which produces the output y, and weights each possible world w with p(w P). In PNL, we want to train a perception model fo to compute belief P fa( for an input x E X in which the correct world is likely. Note that possible worlds are not necessarily correct worlds: w (4, 9) also sums 13, but not a symbolic representation of
Given this setup, we interested in efficiently computing the following quantities:
1. p(y = fx(x)): We want to find the most likely outputs for the belief that the perception network computes on the input x.
2. Vpp(y/P = (x)): We want to train our neural network fo, which requires computing the gradient of the WMC problem.
3. p(wly, P= fe fx)))) We want to find likely worlds given predicted output and belief about the perceived digits. The probabilistic logic programming literature calls w arg max p( p(w|y, P) the most probable explanation (MPE) [50].
2.3 The problem with exact inference for WMC
The three quantities introduced in Section 2.2 require calculating or estimating the WMC problem of Equation] ! However, the exact computation of the WMC is #P-hard, which is above NP-hard. Thus, we would need to do a potentially exponential-
computation for each training iteration and test query. Existing PNL methods use probabilistic circuits (PCs) speed up this computation 660 28 35 (7). PCs compile a logical formula into a circuit for which many inference queries are linear in the size of the cireuit. PCs good choice when exact inference is required but do not overcome the inherent exponential complexity of the problem: the compilation step is potentially exponential in time and memory, and there no guarantees the size of the circuit is not exponential.
The Multi-digit MNISTAdd task is excellent for studying the scaling properties of WMC. We can increase the complexity of MNISTAdd exponentially by considering digits (called N 1) but the sum of two numbers with multiple digits. An example of N would be 5 Contrast this to summing two digits: there are only ways to sum to 13. Each increase of leads to 10 times that approximate inference can solve this problem up to N = 15. Solving this using exact inference would require enumerating around 101s options for each query.
only the sum of two single
135. There are 64 ways to sum to 135 using two numbers with two digits.
options consider for exact inference. Our experiments in Section 4 will show
3 A-NESI: Approximate Neurosymbolic Inference
Our goal is to reduce the inference complexity of PNL to allow training neurosymbolic models on much more complex problems. To this end, in the following subsections, introduce Approximate Neurosymbolic Inference (A-NESI). A-NESI approximates the three quantities of interest from Section 2 namely p P). VpP(y(P) and p( (wly, P), using neural networks. We give overview of our method in Figure
3.1 Inference models
A-NESI uses an inference model qo.b defined
40. ( (w, y PP) = qo ( Po P).
We call go (y(y))) (P) the prediction model and (ollwy P) the explanation model. The prediction model should approximate the WMC problem of Equation while the explanation model should predict likely worlds given outputs and beliefs P. One way to model 1o.v is by considering W and Y as two sequences and defining an autoregressive generative model over these sequences:
by II go (yllyii P), 4e (wly,,
kww
g (
II
q (w.y W1
(3)
Possible worlds are also called 'models'. We refrain from using this term to prevent confusion with '(neural network) models'.

---

Algorithm Compute inference model loss
Algorithm A-NEST training loop
fit prior P(P) on onPP I..... Pa
Input: dataset D, params 0, params
P ~ p(P) P)
beliefst []
PP
while not converged do
- ((w)
(x.y) ~
return a log (
P с fe(x)
update beliefs with
@ Algorithm I(beliefs, Φ)
θ <
+ +aVo log 9 (y
Figure 2: The training loop of A-NESI.
This factorization makes the inference model highly flexible. We use simpler models if we know the dependencies between variables in W and Y. The factorization is computationally linear in kw + ky, instead of exponential in kw for exact inference. During testing, use beam search find the most likely prediction from do.0 y P). If the method successfully trained the perception model, then its entropy is low and beam search should easily find the most likely prediction (37.
There are no restrictions on the architecture of the inference model ls. Any neural network with appropriate inductive biases and parameter sharing to speed up training can be chosen. For instance, CNNs over grids variables, graph neural networks 227 for reasoning problems on graphs, or transformers for sets sequences (55)
We use the prediction model to train the perception model fe given dataset D of tuples (x, y). Our novel loss function trains the perception model by backpropagating through the prediction model:
(eere(D, 0) = log g (y = (x)), x. ~
(4)
The gradients of this loss are biased due to the error in the approximation qø. but has no variance outside of sampling from the training dataset.
Training the inference model
We define two variations of our method. The prediction-only variant (Section 1 uses only the prediction model go (y(yPP) P),, while the explainable variant (Section 3.2.4) also uses the explanation model qu. (wly, P).
Efficient training of the inference model relies on two design decisions. The first descriptive factorization of the output space Y, which we discuss in Section 3.2.2 The second is using an informative belief prior p(P), which we discuss Section 3.2.3
We first define the forward process that uses the symbolic function c to generate training data:
p(w, y PP) p(w(P)p(y w, P) p(w P) Ac(w)=y
(5)
We take some example world w and deterministically compute the output of the symbolic function c(w). Then, we compute whether the output c(w) equals y. Therefore, p( p(w,y(p (W)y if c(w) # y (that is, w is not possible world of y).
The belief prior pPP) allows generate beliefs P for the forward process. That is, we generate training data for the inference model using
p(P, w) = p(P)p(w(P)
(6)
where P, w (P, y= c(w.
The belief prior allows us to train the inference model with synthetic data: The prior and the forward process define everything 46 needs to learn. Note that the sampling process P, w p(P, w) is fast and parallelisable. involves sampling from a Dirichlet distribution, and then sampling from a categorical distribution for each dimension of based on the sampled parameters P.
3.2.1 Training the prediction-only variant
In the prediction-only variant, we only train the prediction model g (y (P)).. We use the samples generated by the process in Equation 6 We minimize the expected cross entropy between PPy

---

and 96 (y(P) over the prior PPP):
Crred( = log qs (c(()))))) P. k.w~((P.)
See A for a derivation. In the loss function defined Equation 7 we estimate the expected cross entropy using samples from p(P, w). We use the sampled world w to compute the output y = c(w) and increase its probability under 94. Importantly, we do not need use any data to evaluate this
loss function. We give pseudocode for the full training loop in Figure 2
3.2.2 Output space factorization
The factorization of the output space Y introduced Section 2 is one of the key ideas that allow efficient learning in A- A-N We will illustrate this with MNISTAdd. As the number of digits N increases, the number of possible outputs (i.e., sums) is 2- 10 1. Without factorization, we would need an exponentially large output layer. We solve this by predicting the individual digits of the output so that we need only 10 + 2 outputs similar to [3. Furthermore, recognizing a single digit of the sum is easier than recognizing the entire sum: for its rightmost digit, only the rightmost digits of the input are relevant.
Choosing the right factorization is crucial when applying A-NESI. A general approach is to take the CNF of the symbolic function and predict each clause's 's truth value. However, this requires grounding the formula, which can be exponential, Another option is to predict for what objects universally quantified formula holds, which would be linear in the number of objects.
3.2.3 Belief prior design
How should we choose the Ps for which we train l0.0. ? A naive method would use the perception model fo. sample some training data X1, ......; X2 DD and train the inference model over P1 fo(x1),... Ps = fxx).. However, this means the inference model is only trained on those P occurring the training data. Again, consider the Multi-digit MNISTAdd problem. For N 15, we have a training set of 2000 sums, while there are 2 10a5 1 possible sums. By simulating many beliefs, the inference model sees a much richer set inputs and outputs, allowing to generalize.
A better approach is to fit Dirichlet prior P(P) on PI...., P& that covers all possible combinations of numbers. We choose a Dirichlet prior since is conjugate the discrete distributions, For details, see Appendix During hyperparameter tuning, we found that the prior needs to be high entropy to prevent the inference model from ignoring the inputs P. Therefore, we regularize the prior with an additional term encouraging high-entropy Dirichlet distributions.
3.2.4 Training the explainable variant
The explainable variant uses both the prediction model qs (yl PP) and the optional explanation model te (wly, P). When training the explainable variant, we use the idea that both factorizations of the joint should have the same probability mass, that is, yP)) = qs w. y.yll PP). To this end, we use a novel joint mutching loss inspired by the theory of GFlowNets (9 10 in particular, the trajectory balance loss introduced by 33 which related to variational inference [44. For an in-depth discussion, see Appendix E The joint matching loss is essentially a regression of lø. onto the true joint that we compute closed form:
P0.u W. c(w) P)
2
Exup (#) x/) log
P.w~p(P,N
(8)
p(w
Here use that p(w, cPw) p(w P) since c(w) is deterministic. Like when training the prediction-only variant, we sample random belief P and world w and compute the output y. Then minimize the loss function to match the joints p and 96.v. We further motivate the use of this loss in Appendix D Instead of a classification loss like cross-entropy, the joint matching loss ensures qa. does not become overly confident in a single prediction and allows spreading probability mass easier.
3.3 Symbolic pruner
An attractive option to use symbolic knowledge to ensure the inference model only generates valid outputs. We can compute each factor q ly, W1:-1,, P) (both for world and output variables)
5

---

X
0
X
7 x
3
5
8
P
Y1
Y2
W1
W2
9 X
9
x
9
P = fol 5 8
Tá (31 P)
Ib (y2 1/, P
Tp (1 wyl P
Tub (w2l
P)
For 1/2 prune option 9, as the highest attainable sum is 9 + 18. For W1, {0..... ..... 3] are pruned as there is no second digit to complete the sum. is deterministic given wi, and prunes all branches but 8.
Figure 3: Example rollout sampling an explainable variant on input x
using a neural network Lo.s and symbolic pruner Sy wi:-1 W. {0,1}:
to (w: = jly, WI: P)y w (i)
goo (w j,y, WI Ejee,, to (w; = j' ly, Wix--1, P) (f)
The symbolic pruner sets the probability mass of certain choices for the variable w; zero. Then, de is computed by renormalizing. If we know that by expanding Wisi- it will be impossible to produce a possible world for y. we can set the probability mass under that branch to O: we will know that p( y y) 0 for all such branches. In Figure we give an example for single-digit MNISTAdd. Symbolic pruning significantly reduces the number of branches our algorithm needs to explore during training. Moreover, symbolic pruming is critical in settings where verifiability and safety play crucial roles, such as medicine. We discuss the design symbolic pruners in Appendix G
Experiments
We study three Neurosymbolic reasoning tasks to evaluate the performance and scalability of A- NeSI: Multi-digit MNiSTAdd (37). Visual Sudoku Puzzle Classification 4 and Warcraft path planning. Code is available at hhttps://giiie httpg/tthub.ccom/HBilleeeee optimizer throughout.
We used the ADAM
A-NESI has two prediction methods. 1) Symbolic prediction uses the symbolic reasoning function e to compute the output: ý = c(arg P(w]) = [x()))) 2) Neural prediction predicts with the prediction network 4s using beam search: tasks, neural prediction cannot perform better than symbolic prediction. However, we still use the prediction model to efficiently train the perception model in the symbolic prediction setting. We consider the prediction network adequately trained if it matches the accuracy of symbolic prediction.
arg max, Is Py fo fx))). In our studied
4.1 Multi-digit MNISTAdd
We evaluate A-NESI on the Multi-Digit MNISTAdd task (Section 2) For the perception model, we use the same CNN as in DeepProbLog 35 The prediction model has + factors gos (yi Y1x11, P). while the explanation model has 2N factors 4ep
(wraly (we/ Wı,i-1. 1: P). We model each factor with separate MLP. yi and w, are one-hot encoded digits, except for the first output digit y1 it can only be 0 or 1. We used shared set of hyperparameters for all N. For more details and description of the baselines, see Appendix [.I
Table reports the accuracy of predicting the sum. For all N, A-NESI is close to the reference accuracy, meaning there no significant drop in the accuracy of the perception model as N increases. For small N, it is slightly outperformed by DeepStochLog (56), which can not scale to N 15. A-NEST also performs slightly better than DeepProbLogg showing approximate inference does not hurt the accuracy. With neural prediction, we get the same accuracy for low N, but there is significant drop for N = 15, meaning the prediction network did not perfectly learn the problem. However, compared to training neural network without background knowledge (Embed2Sym with

---

N=1
N=2
N=4
N=15
Symbolic prediction
LTN
77.34 = 35.55
T/O
T/O
DeepProbLog
97.20
95.20 = 1.70
T/O
T/O
DPLA*
08.9011..00
3.60=23..
T/O
T/O
DeepStochLog
96.40 = 0.100
92.70 0.60
T/O
Embed2Sym
97.62 0.29
93.81 1.37
91.65 0.57
20.36
A-NESI (predict)
97.66 0.21
95.96 = 0.38
92.56 + 0.79
75.90
A-NESI (explain)
97.37 0.32
96.04 0.46
92.11 1.06
76.84 + 2.82
A-NESI (pruning)
97.57 0.27
95.82 = 0.33
92.40 = 0.68
76.46 + 1.39
A-NESI (no prior)
76.54 + 27.38
95.67 0.53
44.58 + 38.34
0.03 + 0.09
Neural prediction
Embed2Sym
97.34 0.19
84.35 6.16
0.81 + 0.12
0.00
A-NEST (predict)
97.66 + 0.21
95.95 0.38
92.48 + 0.76
54.66 + 1.87
A-NESI (explain)
97.37 + 0.32
96.05 0.47
92.14 + 1.05
61.77 + 2.37
A-NEST (pruning)
97.57 + 0.27
95.82 0.33
92.38 + 0.64
59.88 + 2.95
A-NESI (no prior)
76.54 + 27.01
95.28 = 0.62
40.76 = 34.29
0.00 + 0.00
Reference
98.01
96.06
92.27
73.97
Table I:
Test accuracy of predicting the correct (timeout) represent computational timeouts. Reference accuracy approximates the accuracy of an MNIST predictor with 0.99 accuracy using 0.992N, Bold numbers signify the highest average accuracy for some N within the prediction categories. predict is the prediction-only variant, explain the explainable variant, pruning adds symbolic pruning (see Appendix Hp. and no prior the prediction-onf, variant without the prior p(P).
the Multi-digit MNISTAdd task. "T/O"
10a
DaepProbl.gg
0,10
[grounding]
Inference time (s)
10
DPLM*
(esplain)
10a
A-NASI (predict)
0,06
(inferencs)
10
0.04
10
0,02
10
0,00
10
12
14
15
N
N
Figure 4: Inference time for a single input for different nr. of digits. The left plot uses a log scale, and the right plot a linear scale. DSL stands for DeepStochLog. We use the GM variant of *
neural prediction). it is much more accurate already for N = 2. Therefore, A-NESI's training loop allows training prediction network with high accuracy large-scale problems.
Comparing the different A-NESI variants, we see the prediction- onnly, explainable and pruned variants perform quite similarly, with significant differences only appearing N 15 where the explainable and pruning variants outperform the predict-only model, especially on neural prediction. However, when removing the prior p(P), the performance degrades quickly. The prediction model sees much fewer beliefs than when sampling from a (high-entropy) prior p(P). A second and more subtle reason is that at the beginning of training, all the belief's P fo (x) will be uniform because the perception model is not yet trained. Then, the prediction model learns to ignore the input belief
Figure 4 shows the runtime for inference on single input x. Inference in DeepProbLog (cor- responding to exact inference) increases with factor 100 as N increases, and DPLA* (another approximation) is not far behind. Inference in DeepStochLog, which uses different semantics, is efficient due to eaching but requires a grounding step that exponential both in time and memory. We could not ground beyond N = because of memory issues. A-NESI avoids having to perform grounding altogether: scales slightly slower than linear. Furthermore, is much faster in practice parallelizing the computation of multiple queries GPUs is trivial.

---

N=4
N=9
CNN
51.50 + 3.34
51.20 + 2.20
Exact inference
86.70
T/O
NeuPSL
89.7 = 2.20
51.50 + 1.37
A A-NESI (symbolic prediction)
89.70 2.08
62.15 2.08
A A-NESI (neural prediction)
89.80 + 2.11
62.25 + 2.20
Table 2: Test accuracy of predicting whether a grid of numbers a Sudoku. For A-NeSI, we used the prediction-only variant.
4.2 Visual Sudoku Puzzle Classification
In this task, the goal is to recognize whether an x N grid of MNIST digits is a Sudoku. We have 100 examples of correct and incorrect grids from 4. We use the same MNIST classifier as in the previous section. We treat w as grid of digits in f .N and designed an easy-to-learn representation of the label. For sudokus, all pairs of digits W., w in a row, column, and block must differ. For each such pair, a dimension in is I if different and otherwise, and the symbolic function computes these interactions from w. The prediction model single MLP that takes the probabilities for the digits P, and P, and predicts the probability that those represent different digits. For additional details, see Appendix 1.2
Table 2 shows the accuracy of classifying Sudoku puzzles. A-NESI is the only method to perform better than random on 9 x sudokus. Exact inference cannot scale to 9 sudokus, while were able to run A-NESI for 3000 epochs in 38 minutes on single NVIDIA RTX A4000.
4.3 Warcraft Visual Path Planning
12 12
30 30
ResNet18 [43
23.0 = 0.3
0.0 0.0
SPL 0
78.2
T/O
I-MLE 41
97.2 + 0.5
93.7 + 0.6
RLOO 29
43.75 = 12.35
12.59 = 16.38
A-NEST
94.57 + 2.27
17.13 + 16.32
A-NESI + RLOO
98.96 1.33
67.57 + 36.76
Table 3: Test accuracy of predicting the lowest-cost path on the Warcraft Visual Path Planning task. For A-NeSI, we used the prediction-only variant.
Figure 5: Example of the Warcraft task.
The Warcraft Visual Path Planning task [43 is to predict shortest path from the top left corner of an N x N grid to the bottom right, given an image from the Warcraft game (Figure 5). The perception model has to learn the cost of each tile the Warcraft image. We use small CNN that takes the tile j j (a 3 x 8 X image) and outputs distribution over 5 possible costs. The symbolic function c(w) is Dijkstra's s algorithm and returns a shortest path y. which we encode as a sequence of the (inter)- directions starting from the top-left corner. We use ResNet1 8 [22] as the prediction model, which we train to predict the next direction given beliefs of the tile costs P and the current location. We pretrain the prediction model on fixed prior and train the perception model with frozen prediction model. See Appendix I.3 for additional details.
Table presents the accuracy of predicting a shortest path. A-NESI is competitive on 12 x 12 grids but struggles on 30 x 30 grids. We believe this because the prediction model is not accurate enough, resulting in gradients with too high bias. Still. A-NESI finds short paths, is far better than a pure neural network, and can scale 30 30 grids, unlike SPL M which uses exact inference. Since both SPL and I-MLE [1] have significantly different setups (see Appendix I.3.2), we added experiments using REINFORCE with the leave-one-ord baseline (RLOO, 29 that we implemented with the Storchastic PyTorch library [53 We find that RLOO has high variance in its performance. Since RLOO is unbiased with high variance and A-NESI biased with no variance, we also tried running A-NEST and RLOO simultaneously. Interestingly, this is the best- pest-performing method on the 12 x 12 grid, and has competitive performance on 30 30 grids, albeit with high variance (6 out 10 runs get to accuracy between 93.3% and 98.5%, while the other runs stuck around 25% accuracy).

---

Related work
A-NESI can approximate multiple PNL methods [6..
DeepProbLogg (35] performs symbolic
reasoning by representing w ground facts in a Prolog program. It enumerates all possible proofs of a query y and weights each proof by p[w] P). NeurASP [58] is a PNL framework closely related to DeepProbLog. but is based on Answer Set Programming 121. Some methods consider constrained structured output prediction 19]. In Appendix B we discuss extending A-NESI to this setting. Semantic Loss [57] improves learning with loss function but does not guarantee that formulas are satisfied at test time. Like A-NESI, Semantic Probabilistic Layers []] solves this with a layer that performs constrained prediction. These approaches perform exact inference using probabilistic circuits (PCs) 660 Other methods perform approximate inference by only considering the top-k proofs in PCs [3
23 However, finding those proofs is hard, especially when beliefs have high entropy, and limiting to top-k significantly reduces performance. Other work considers MCMC approximations (3]] Using neural networks for approximate inference ensures computation time is constant and independent of the entropy of P or long MCMC chains.
[8] which are faster than PNL with exact inference. Although traversing ground formulas is linear time, the grounding is itself often exponential [37]. so the scalability of fuzzy logics often fails to deliver. A-NESI is polynomial in the number of ground atoms and does not traverse the ground formula. Furthermore, background knowledge is often not fuzzy 54
Other neurosymbolic methods use fuzzy logics (S
17 13
20 , and fuzzy semanties does not preserve classical equivalence.
A-NEST performs gradient estimation of the WMC problem. We can extend our method to biased but zero-variance gradient estimation by learning distribution over function outputs (see Appendix C). Many recent works consider continuous relaxations of discrete computation to make them differentiable 42 24] but require many tricks to be computationally feasible. Other methods compute MAP states to compute the gradients [4] I 47] but are restricted to integer linear programs. The score function (or 'REINFORCE') gives unbiased yet high- nigh-variance gradient estimates 40 53
Variance reduction techniques, such as memory augmentation [32] and leave-one ont-out baselines exist reduce this variance.
29]
6 Conclusion, Discussion and Limitations
We introduced A A-NESI, a scalable approximate method for probabilistic neurosymbolic learning. We demonstrated that A-NESI scales to combinatorially challenging tasks without losing accuracy. A A-NESI can be extended to include explanations and hard constraints without loss of performance.
However, there is no 'free lunch': when is A-NESI good approximation? We discuss three aspects of learning tasks that could make it difficult to learn strong and efficient inference model.
Dependencies of variables. When variables in world w are highly dependent, finding an informative prior is hard. We suggest then using a prior that can incorporate dependen- cies such normalizing flow 45] 14 or deep generative models [1 over a Dirichlet distribution.
Structure in symbolic reasoning function. We studied reasoning tasks with a relatively simple structure. Learning the inference model will be more difficult when the symbolic function less structured. Studying the relation between structure and learnability is interesting future work.
Problem size. A- A-NESI did not perfectly train the prediction model in more challenging problems, which is evident from the divergence in performance between symbolic and neural prediction for digits in Table We expect required parameter size and training time to increase with the problem size.
Promising future avenues are studying if the explanation model produces helpful explanations (50). extensions to continuous random variables [2] (see Appendix C for an example), and extensions
to unnormalized distributions such as Markov Logic Networks [46,, as well as (semi-) automated
A A-NESI solutions for neurosymbolic programming languages like DeepProbLog [35).

---

Acknowledgements
We want to thank Robin Manhaeve, Giusseppe Marra, Thomas Winters, Yaniv Aspis, Robin Smet, and Anna Kuzina for helpful discussions. For our experiments, we used the DAS-6 compute cluster We also thank SURF (www.surf.nl) for its support in using the Lisa Compute Cluster.
[
References
[1] Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. Advances in Neural Information Processing Systems, 35:29944-29955 2022.
[2] Kareem Ahmed, Eric Wang, Kai-Wei Chang, and Guy Van den Broeck. Neuro-Symbolic Entropy Regularization. In The 38th Conference on Uncertainty in Artificial Intelligence, June 2022.
[3] Yaniv Aspis, Krysia Broda, Jorge Lobo, and Alessandra Russo. Embed2Sym Scalable Neuro- Symbolic Reasoning via Clustered Embeddings. In Proceedings of the Nineteenth International Conference on Principles of Knowledge Representation and Reasoning, pages 421-431, Haifa, Isracl, July 2022. International Joint Conferences on Artificial Intelligence Organization. ISBN 978-1-956792-00-0) doi: 10.24963/kr.2022/44,
[4] Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Yang Wang, and Lise Getoor. Visual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. In International Workshop on Neural- Seural-Symbolic Learning and Reasoning (NeSy), Windsor, United Kingdom, 2022.
[5] Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic Tensor Networks. Artificial Intelligence, 303:103649, February 2022. ISSN 0004-3702. doi: 10.
103649.
[6] Henri Bal, Dick Epema, Cees de Laat, Rob van Nieuwpoort, John Romein, Frank Seinstra, Cees Snoek, and Harry Wijshoff. A medium-scall distributed system for computer science research: Infrastructure for the long term. Computer, 49(5):54 63, 2016.
[7] Tomas Balyo, Marijn H. Heule, Markus Iser, Matti Järvisalo, Martin Suda, Helsinki Institute for Information Technology, Constraint Reasoning and Optimization research group / Matti Järvisalo, and Department of Computer Science. Proceedings SAT Competition 2022: Solver and Benchmark Descriptions. 2022.
[8] Mare Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforce- ment leaming. In International Conference on Machine Leurning, pages 449-458. PMLR, 2017.
[9] Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation. Advances in Neural Information Processing Systems, 14:27381-22399, 2021.
[10] Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J. Hu, Mo Tiwari, and Emmanuel Bengio. GFlowNet Foundations, August 2022.
[11] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and lean-Philippe Vert. Efficient and modular implicit differentiation. Advances Neural Information Processing Systems, 35:5230-5242. 2022.
[12] Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczyíski. Answer set programming at glance. Communications of ACM, 54(11))92-103, 2011.
[13] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6):772-79, April 2008. ISSN 0004-3702, doi: 10.10166/.artint 2007.11.002
10

---

[14] Xi Chen, Diederik P. Kingma, Tim Salimans, Yan Duan, Prafulla Dhariwal, John Schulman, Ilya Sutskever, and Pieter Abbeel. Variational Lossy Autoencoder. In International Conference on Learning Representations, July 2022.
[15] Alessandro Daniele, Emile van Krieken, Luciano Serafini, and Frank van Harmelen. Refining neural network predictions using background knowledge. Machine Learning, March 2023.
ISSN 1573-0565. doi: 1.11077/110994-02---663
[16] Luc De Raedt, Robin Manhaeve, Sebastijan Dumancic, Thomas Demeester, and Angelika Kimmig. Neuro-symbolie= neural+ logical+ probabilistie. In NeSy' 19@ IJCAI, the 14th International Workshop Neural-Symbolic Learning and Reasoning, 2019.
[17] Michelangelo Diligenti, Marco Gori, and Claudio Sacca. Semantic- regularization for learning and inference. Artificial Intelligence, 244: 144-164, 2017.
[18] Elconora Giunchiglia and Thomas Lukasiewicz. Multi-Label Classification Neural Networks with Hard Logical Constraints. J. Artif. Intell. Res., 72:759 818, 2021. doi: 10. 10.1613/jair.1. 12850.
[19] Elconora Giunchiglia, Mihacla Catalina Stoian, and Thomas Lukasiewicz. Deep Learning with Logical Constraints. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 5478 17788-545..15 ijcai.org, 2022. doi: 10.24966fijccii22227776
[20] Mattia Medina Grespan, Ashim Gupta, and Vivek Srikumar. Evaluating Relaxations of Logic for Neural Networks: A Comprehensive Study. IIXi:22107.33646 [cs], July 2021.
[21] Bernd Gutmann, Manfred Jaeger, and Luc De Raedt. Extending ProbLog with Continuous Distributions. In Paolo Frasconi and Francesca A. Lisi, editors, Inductive Logic Programming, Lecture Notes in Computer Science, pages 76-91, Berlin, Heidelberg, 2011. Springer. ISBN 978-3-642-21295-42 doi: 10. 1007/978-3--62222299566
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[23] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From Probabilistic Deductive Databases Scalable Differentiable Reasoning. In Advances in Neural Information Processing Systems, May 2021.
[24] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizzaioo with gumbel-softmax In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017.
[25] Diederik P. Kingma and Jimmy Ba. 14Xiv:1412.6980 [cs], January 2017.
Adam: A Method for Stochastic Optimization.
[26] Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[27] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks, February 2017.
[28] Doga Kisa and Guy Van den Broeck. Probabilistic sentential decision diagrams. Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 558-567, 2014.
[29] Wouter Kool, Herke van Hoof, and Max Welling. Buy 4 REINFORCE samples, get baseline for free! page 14, 2019.
[30] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.

---

[31] Zenan Li, Yuan Yao, Taolue Chen, Jingwei Xu, Chun Cao, Xiaoxing Ma, and Jian "fu). Softened Symbol Grounding for Neuro-symbolic Systems. In The Eleventh International Conference Learning Representations, February 2023.
[32]
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoe V. Le, and Ni Lao. Memory aug- mented policy optimization for program synthesis and semantic parsing. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018. December 3-8, 2018, Montréal, Canada, pages 10015-10027, 2018.
[33] Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment in GFlowNets. In NeurIPS, 2022.
[34] Nikolay Malkin, Salem Lahlou, Tristan Deleu, Xu Ji, Edward J. Hu, Katie E. Everett, Dinghuai Zhang, and Yoshua Bengio. GFlowNets and variational inference. In The Eleventh International Conference on Learning Representations, February 2023.
[35] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural probabilistic logic programming. In Samy Bengio, Hanna M Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, edi- tors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, 2018.
[36] Robin Manhaeve, Sebastijan Dumančié, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in DeepProbl.og. Artificial Intellignce, 298: 103504, 2021. ISSN 0004-3702. doi: 10. a.t..aartitt.2221103533.
[37] Robin Manhaeve, Giuseppe Marra, and Lue De Raedt. Approximate inference for neural probabilistic logic programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pages 475-486, November 2021. doi: 10.24963/kr.2021/455
(38] Giuseppe Marra, Sebastijan Dumančić, Robin Manhaeve, and Lue De Raedt. From Statistical Relational to Neural Symbolic Artificial Intelligence: Survey. arXiv:2 145/ [cs], August 2021.
[39] Thomas Minka. Estimating dirichlet distribution, 2000.
[40] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. Journal of Machine Learning Research, 21:132:1-132:62 2020.
[41] Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit MLE: Backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 34:144 34:14567-14579, 2021.
[42] Felix Petersen. Learning with Differentiable Algorithms, September 2022.
[43] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
[44] Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Wang, and Lise Getoor. NeuPSL: Neural Probabilistic Soft Logic, June 2022.
[45] Danilo Rezende and Shakir Mohamed. Variational Inference with Normalizing Flows. In Proceedings of the 32nd International Conference on Machine Learning, pages 1530-1538.
PMLR, June 2015.
[46] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62(1):
107-136, February 2006. ISSN 1573-0565. doi: 109400777-199944----88---
12

---

[47] Subham Sekhar Sahoo, Anselm Paulus, Marin Vlastelica, Vít Musil, Volodymyr Kuleshov, and Georg Martius. Backpropagation through Combinatorial Algorithms: Identity with Projection Works. In The Eleventh International Conference on Learning Representations, February 2023.
[48] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli, Maria-Esther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mchwish Alam, editors, The Semantic Web, pages 593-607, Cham, 2018. Springer International Publishing. ISBN 978-3-319-93417-4
[49] John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient estimation using stochastic computation graphs. In Advances in Neural Information Processing Systems, 2015.
[50] Dimitar Shterionov, Joris Renkens, Jonas Vlasselaer, Angelika Kimmig, Wannes Meert, and Gerda Janssens. The Most Probable Explanation for Probabilistic Logic Programs with An- notated Disjunctions. In Jesse Davis and Jan Ramon, editors, Inductive Logic Programming, Lecture Notes in Computer Science, pages 139-153, Cham, 2015. Springer International Publishing. ISBN 778-3-31--2370--4 doi: (1007/97--3-31-237000
[51] Jakub M. Tomczak. Deep Generative Modeling. Springer International Publishing, Cham, 2022. ISBN 000-3-030-9315777 978-3-030-93158- doi: 10. 00.1000//78---0355 3-030-93118-2
[52] Frank van Harmelen and Annette ten Teije. A Boxology of Design Patterns for Hybrid Learning and Reasoning Systems. Journal of Web Engineering, 18(1):97-124, 2019, ISSN 1540-9589, doi: 10. (0.13052//we1554-95599..
[53] Emile van Kricken, Jakub Tomezak, and Annette Ten Teije. Storchastic: A framework for general stochastic automatic differentiation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 7574-7587 Curran Associates, Inc., 2021.
[54] Emile van Kricken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 302:103602, 2022. ISSN 0004-3702. doi: 10.1016/j.artint 2021.103602.
[55] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention All You Need, December 2017.
[56] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Lue De Raedt. DeepStochLog: Neural Stochastic Logie Programming. In Proceedings of the First MiniCon Conference, February 2022.
[57] Jingyi Xu, Zilu Zhang. Tal Friedman, Yitao Liang, and Guy den Broeck. A semantic loss function for deep learning with symbolie knowledge. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5502-5511, Stockholmsmässan, Stockholm Sweden, 2018 PMLR
[58] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 1755-1762. International Joint Conferences on Artificial Intelligence Organization, July 2020. doi: 244966//jaai.2220//44
[59] Chih-Kuan Yeh, Been Kim, Sercan O. Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar, On Completeness-aww aware Sancept-Based Explanations in Deep Neural Networks, February 2022.
[60] Choi Yoojung, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. 2020.
13

---

A Derivation of prediction-only variant loss
L3 Bp(P) Eptr P) [log go (y [P]]
(10)
PP()) [ flo 90 [y[P)]
(11)
Ep(.. w) [log qs (P)
(12)
(reed(0) log qo (c(w))P), P. p(,, w)
(13)
In line 11 we marginalize out w, and use the fact that is deterministic given w.
B Constrained structured output prediction
We consider how implement the constrained structured output prediction task considered in (for example) [2 n [57] in the A-NESI framework. Here, the goal is to learn a mapping of some X to structured output space W, where we have some constraint c(w) that returns if the background knowledge holds, and O otherwise. We can model the constraints using Y = {0, 1}; that is, the "output" our problem setup whether w satisfies the background knowledge or not. We give an example of this setting in Figure 6
Then, design the inference model follows. 1) ( P) is tasked with predicting the probability that randomly sampled outputs w ~ (W((P) will satisfy the background knowledge. 2) qo (wly P) is an approximate posterior over structured outputs w that satisfy the background knowledge c.
This setting changes the interpretation of the set from unobserved worlds to observed outputs. We will train our perception module using "strongly" supervised learning loss where x, Dz:
(e) = - log qu (wly = 1, fe(x)).
(14)
If we also have unlabeled data Du. we use the prediction model to ensure the perception model gives high probabilities for worlds that satisfy the background knowledge. This approximates Semantic Loss [57]: Given x ~ Du,
(0) = log qΦ (v = 1|P fo(x)).
(15)
That is, have some input x for which we have no labelled output. Then, increase the probability that the belief P the perception module fo predicts for x would sample structured outputs w that satisfy the background knowledge.
Training the inference model in this setting can be challenging if the problem is very constrained. Then, random samples P, w p(P, w) will usually not satisfy the background knowledge. Since we are only in the case that = 1, we can choose to sample from the inference model dg and exploit the symbolic pruner to obtain samples that guaranteed satisfy the background knowledge. Therefore, we modify equation to the on-policy joint matching loss
(10g L0. (w, y 1PP) 27 P(w
Exp (P, db 1b) = (wlp=11))
(16)
Here, we incur some sampling bias by not sampling structured outputs from the true posterior, but this bias will reduce q becomes more accurate. We can also choose combine the on- and off-policy losses. Another option to make learning easier is using the suggestions of Section 3.2.2 factorize make more fine-grained.
C A-NESI as a Gradient Estimation method
In this appendix, we discuss using the method A-NESI introduced for general gradient estimation 40 We first define the gradient estimation problem. Consider some neural network fo that predicts the parameters P of a distribution over unobserved variable z E Z: p(z) P = fe (x)). This distribution corresponds to the distribution over worlds p( w wP) in A-NESI. Additionally, assume we have some deterministic function y(z) that we want to maximize in expectation. This maximization requires estimating the gradient
V VeEpterP==/(x>)0(z)))
(17)
14

---

Common methods for estimating this gradient are reparameterization (26], which only applies to continuous random variables and differentiable r, and the score function notoriously high variance.
which has
Instead, gradient estimation method learns an inference model (ø(r(P) approximate the distribution of outcomes r = g(z) for a given P. In A-NESI, this is the prediction network q4 (y())) that estimates the WMC problem of Equation [ Approximating a distribution over outcomes is similar to the idea of distributional reinforcement learning [8]. Our approach is general: Unlike reparameterization, we can use inference models in settings with discrete random variables z and non-differentiable downstream functions g.
We derive the training loss for inference model similar that in Section 3.2.1 First, define the joint on latents z and outcomes r like the joint process in as p(r; P where dgt=) (r) is the dirac-delta distribution that checks the output of on z is equal to r. Then we introduce prior over distribution parameters p (P), much like the prior over beliefs in A-NESI.
() 6gtz)()) (r),
An obvious choice is to use prior conjugate to p(z PP.. We minimize the expected KL-divergence between p(r and yo (r|P) PP):
pp)) (KL(plla))
(18)
= -p((P)
[p((rPP) [log us (r())] + +C
(19)
T/e p(r p(r(P)) log q dr) +C
= (Bp(P)
(20)
Next, we marginalize over z, dropping the constant:
J / p(r, 2 log go gr (r()) draz
Pp)))
(21)
R
/// p(z[P)
/ R
= -Pp(P)
(o(m)(r) log g [P] PP)]drdz
(22)
//2 p(z(P) log go (p(2)))))dz
= PPP)
(23)
-Rp(P x) [log uo (z))
(24)
This gives us a negative-log likeliood loss function similar to Equation
(ins(() = log (o()())) P,
(25)
where we sample from the joint p(z, P) p (PP)p(z(P).
We use a trained inference model to get gradient estimates:
(pEp(sp))((z)) = Vp (r
(26)
We use the chain rule to update the parameters 0. This requires a choice of distribution qs (r P) for which computing the mean (r())) [r] is easy. The simplest option is parameterize go with a univariate normal distribution. We predict the mean and variance using a neural network with parameters Φ. For example, neural network m& would compute μ (P).). Then, the mean parameter is the expectation on the right-hand side of Equation 26 parameterization
The loss function for fe with this
(N) = (fo((x(
X X~1 D
(27)
Interestingly, like A-NESI, this gives zero-variance gradient estimates! Of course, bias comes from the error the approximation of 9Φ-
Like A-NESI, we expect the success of this method to rely on the ease of finding suitable prior over P to allow proper training of the inference model. See the discussion in Section 3.2.3) We also expect that, like A-NESI, will easier to train the inference model if the output = g()) is structured instead of single scalar. We refer to Section 3.2.2 for this idea. Other challenges might be stochastic and noisy output measurements and non-stationarity of g, for instance, when training VAE 226).
15

---

P (y)P)
Satisfying worlds
p(w(P)
A
B
PA + PAfR
11 Pb)
Pa(1 - Pb)
P
y
B
A,
(1 PA)PB
1
(1 PA)(1 - Ph
(1- PA)(1 - Pb)
A
B
A
AVB
Unsatisfying worlds
Figure 6: The tree flow network corresponding to weighted model counting on the formula A V B. Following edges upwards means setting the corresponding binary variable to true (and to false by following edges downwards). We first choose prohabilities for the propositions A and B. then choose whether want sample world that satisfies the formula A V B. y is the WMC of A V B, and equals its outgoing flow PA + PB Pa Terminal states (with two circles) represent choices of the binary variables A and B. These are connected to final sink node, corresponding to the prior over worlds p( ([]]P). The total ingoing and outgoing flow to this network is 1, as we deal with normalized probability distributions p and 4Φ.
D A-NESI and GFlowNets
A-NeSI is heavily inspired by the theory of GFlowNets 9 10 and we use this theory to derive our loss funetion. the current section, we discuss these connections and the potential for future research by taking inspiration from the GFlowNet literature. In this section, will assume the reader is familiar with the notation introduced in [0] and refer to this paper for the relevant background.
D.1 Tree GelowNet representation
The main intuition is that we can treat the inference model 46 in Equation 3 as 'trivial' GFlowNet. We refer to Figure 6 for an intuitive example. shows what flow network would look like for the formula A V B. We take the reward function Ri(,y) y) = p(w,y). We represent states by s == =P Yis, W1:5). ). that is, the belief P, a list of some dimensions of the output instantiated with value and a list of some dimensions of the world assigned to some value. Actions a set some value to the next output or world variable, i..., (ss) Y,+1 or A(s) Wj+1-
Note that this corresponds to a flow network that is a tree everywhere but at the sink since the state representation conditions the whole trajectory observed so far. We demonstrate this in Figure 6 We assume there is some fixed ordering on the different variables in the world, which we generate the value of one by one. Given this setup, Figure shows that the branch going up from the node y corresponds to the regular weighted model count (WMC) introduced in Equation]
The GFlowNet forward distribution Pp is qs defined in Equation 3 The backward distribution PB is p(w. p) at the sink node, which chooses a terminal node. Then, since we have a tree, this determines the complete trajectory from the terminal node the source node. Thus, at all other states, the backward distribution is deterministic. Since our reward function R( C(w,y: P) P(w,y|Po is normalized, trivially know the partition function Z(P) E. Ey R(w,y PP)
D.2 Lattice GFlowNet representation
Our setup of the generative process assumes we are generating each variable in the world in some order. This fine for some problems like MNISTAdd, where we can see the generative process as 'reading left to right'. For other problems, such as Sudoku, the order in which we would like to generate the symbols less obvious. Would we generate block by block? Row by row? Column by column? Or is the assumption that needs to be generated in some fixed order flawed by itself?
16

---

P)
Satisfying worlds
p(w(P)
PA
(A}
PaPn
Pa(1 - Pb)
Pa+ Ps PAPB
(1 PA)PB
A, B
Paln
(1 Pa)Pa
P
y
{B}
(1- PAl(1 - PB)
- PA)(1 P Pa)
0
AVB
Unsatisfying worlds
Figure 7: The lattice flow network corresponding to weighted model counting on the formula A V B. In this representation, nodes represent sets of included propositions. Terminal states represent sets of random variables such that A V B is true given y 1, or false otherwise.
In this section, consider second GFlow representation for the inference model that represents states using sets instead of lists. We again refer to Figure 7 for the resulting flow network of this representation for A V B. We represent states using ly [(l,..., ky and Iw S {I, kw denote the set of variables for which a value is chosen. The possible actions from some state correspond to A(s) Uier W; (and analogous for when y not yet completely generated). For each variable in W for which we do not have the value yet, add its possible values to the action space.
(P, (yehe (w))eee))) where
With this representation, the resulting flow network is longer tree but DAG, as the order in which we generate the different variables is now different for every trajectory. What do we gain from this? When we are primarily dealing with categorical variables, the two gains are 1) we longer need to impose an ordering on the generative process, and 2) it might be easier to implement parameter sharing in the neural network that predicts the forward distributions, single set encoder that can be reused throughout the generative process.
only need
However, the main gain of the set-based approach is when worlds are all (or mostly) binary random variables. illustrate this in Figure Assume W = {00, ke Then we can have the following state and action representations: = (P, Jw). where /w C (1, ..., kw} and A(s)
{1.... kw Iw-
The intuition that II contains the set all binary random variables that are set to (i.c., true), and {I...., kw \ Iw is the set of variables set to 0 (i.c., false). The resulting flow network represents a partial order over the set of all subsets of [1,... kw which is a lattice, hence the name this representation.
With this representation, we can significantly reduce the size and computation of the flow network required to express the WMC problem. As an example, compare Figures 0 and 7 which both represent the WMC of the formula v B. We no longer need two nodes in the branch y = 0 to represent that we generate A and B to be false, as the initial empty set {} already implies they are. This will save us two nodes. Similarly, we can immediately stop generating at {A} and (B), and no longer need to generate the other variable as false, which also saves computation step.
While this is theoretically appealing, the three main downsides are PB is no longer trivial to compute; 2) we have to handle the fact that we no longer have a tree, meaning there is no longer unique optimal Pp and PB; and 3) parallelization becomes much trickier. We leave exploring this direction in practice for future work.
E
Analyzing the Joint Matching Loss
This section discusses the loss function we use to train the joint variant in Equation g We recommend interested readers first read Appendix D.I Throughout this section, we will refer to p == p ((w,y] (Equation 5) and 2o.0 (w. y PP) (Equation 2). We again refer to []0] for notational background.
17

---

E.1
Trajectory Balance
We derive our loss function from the recently introduced Trajectory Balance loss for GFlowNets, which is proven to approximate the true Markovian flow when minimized. This means sampling from the GelowNet allows sampling in proportion to reward R(s,) = p. The Trajectory Balance loss is given by
log F((o) II P=(
((T)
(28)
R(sn) IT Pb(
where so the source state, in our case P. and 8n some terminal state that represents a full generation of y and w. In the tree representation of GFlowNets for inference models (see Appendix D.I.. this computation becomes quite simple:
1. F(so) 1, as R(sn) p normalized;
2. I (r((e(8(-1) = q: The forward distribution corresponds to the inference model
2 (W, yP):
3. R(sa) p. as define the reward to be the true joint probability distribution p(w, (P);
4. IT= (s(ss-1(s:) 1, since the backward distribution is deterministic in tree.
Therefore, the trajectory balance loss for (tree) inference models is
(PP,,,w)
log (log q log
! p
(29)
ie., the term inside the expectation of the joint matching loss in Equation 8 This loss function is stable because we can sum the individual probabilities in log-space.
A second question might then be how we obtain 'trajectories'
(P, y, w) to minimize this loss over. The paper on trajectory balance BB picks on-policy, that is, samples from the forward distribution (in our case, the inference model (. We discussed when this might be favorable in our setting in Appendix ( (Equation [6]. However, the joint matching loss as defined in Equation is off-policy, we sample from p and not from 46.
E.2 Relation to common divergences
These questions open quite some design space, was recently noted when comparing the trajectory balance loss to divergences commonly used in variational inference [34). Redefining Pr- = q and
PB = p. the authors compare the trajectory balance loss with the KL--divergence and the reverse KL-divergence and prove that
V D. = - V
(30)
That is, the on-policy objective minimizes the reverse Kl--divergence between p and g. We do not quite find such a result for the off-policy version we use for the joint matching loss in Equation g
V D nz. (pll)) = E lo
(31)
Ep V C(T(
2-2E-~pp( log 9) V log
(32)
So why do we choose to minimize the joint matching loss rather than the (forward) KL divergence directly? This is because, as clear from the above equations, it takes into account how far the "predicted' log-pro prg--rbbability log currently is from log That is, given sample if log p log q, the joint matching loss will actually decrease log q. Instead, the forward KL will increase the probability for every sample it sees, and whether this particular sample will be too likely under q can only be derived through sampling many trajectories.
Furthermore, we note that the joint matching loss a 'pseudo' f-divergence with f() = log" B4 not true f-divergence since log² is not convex. related well-known f-divergence is the Hellinger distance given by
H2 ETTDI(V v
(33)
18

---

This divergence similarly takes into account the distance between p and q in its derivatives through squaring. However, is much less stable than the joint matching loss since both p and q are computed by taking the product over many small numbers. Computing the square root over this will be much less numerically stable than taking the logarithm of each individual probability and summing.
Finally, we note that we minimize the on-policy joint matching lE, [[lg p log q)² by taking derivatives EgI V. (log log 2) This is technically not minimizing the joint matching, since it ignores the gradient coming from sampling from q-
F Dirichlet prior
This section describes how we fit the Dirichlet prior p(P) used to train the inference model. During training, we keep a dataset of the last 2500 observations of P = fo(x). . We have to drop observations frequently because 0 changes during training, meaning that the empirical distribution over Ps changes as well.
We perform an MLE fit on kw independent Dirichlet priors get parameters for each. The log-likelihood of the Dirichlet distribution cannot be found in closed form [39]. However, since its log-likelihood is convex, we run ADAM (25 for 50 iterations with a learning rate of 0,01 to minimize the negative log-like log-likel We refer to [39] for details on computing the log- ligelikel and alternative options. Since the Dirichlet distribution accepts positive parameters, we apply the softplus function on an unconstrained parameter during training. We initialize all parameters at 0.1.
We added L2 regularization the parameters. This is needed because at the beginning of training, all observations P [x( represent uniform beliefs over digits, which will all be nearly equal. Therefore, fitting the Dirichlet on the data will give increasingly higher parameter values, high parameter values represent low-entropy Dirichlet distributions that produce uniform beliefs. When the Dirichlet is low-entropy, the inference models learn to ignore the input belief P. as it never changes. The L2 regularization encourages low parameter values, which correspond to high-entropy Dirichlet distributions.
G Designing symbolic pruners
We next discuss four high-level approaches for designing the optional symbolic pruner, each with differing tradeoff's in accuracy, engineering time and efficiency:
1. Mathematically derive efficient solvers. For simple problems, could mathematically derive an exact solver. One example of an efficient symbolic pruner, along with a proof for exactness, is given for Multi-digit MNISTAdd Appendix H. This pruner is linear- time. However, for most problems we expect the pruner to be much more computationally expensive.
2. Use SAT-solvers. Add the sampled symbols and Wi:i to CNF-formula, and ask an SAT-solver if there an extension W;-l:k that satisfies the CNF-formula. SAT-solvers are a general approach that will work with every function c, but using them comes at cost. The first is that we would require grounding the logical representation of the problem. Furthermore, to do SAT-solving, we have to solve a linear amount of NP-hard problems. However, competitive SAT solvers can deal with substantial problems due to years of advances in their design 77), and a linear amount of NP-hard calls is a lower complexity class than #P hard. Using SAT-solvers will be particularly attractive in problem settings where safety and verifiability are critical.
3. Prune with local constraints. In many structured prediction tasks, can local constraints of the symbolic problem to prune paths that are guaranteed to lead to branches that can never create possible worlds. However, local constraints do not guarantee that each non-prun con-pruned path contains a possible world, but this does not bias the inference model, as the neural network will (eventually) learn when an expansion would lead to an unsatisfiable state.
One example is the shortest path problem, where we filter out directions that would lead outside the N N grid, or that would create cycles (See Appendix [.3). However, this only ensures find path, but does not ensure it is the shortest onc.
19

---

4. Learn the pruner. Finally, we can learn the pruner, that is, we can train neural network to learn satisfiability checking. One possible approach is reuse the inference model trained on the belief P that uniformly distributes mass over all worlds.
Learned pruners will be as quick as regular inference models, but are less accurate than symbolic pruners and will not guarantee that constraints are always satisfied during test-time. We leave experimenting with learning the pruner for future work.
H MNISTAdd Symbolic Pruner
In this section, describe symbolic pruner for the Multi-digit MNISTAdd problem, which compute in time linear to N. Note that Wi:v represents the first number and WN+112N the second. We define ni = Ei= W; 10 and Ei= WN++ 10 for the integer representations of these numbers, and y EN+1 3/- 10 for the sum label encoded by y. We say that partial generation Wi:k has completion there a W&+1 (o..... 99,2 such that nı n2 = y. Proposition H.1. For all E N. y E {0.1] x (0.....9}N and partial generation Wi:k- E {O..... 9}*h with & E (1..... 2N), the following algorithm rejects all wk for which With has no completions, and accepts all wv for which there are:
k S N: Let 1g = Σ == 10k+1-i and = - wk 10 Let S 1fk N or if the (k 1)th (N + 11tth digit of y are all and S = O otherwise. We compute two boolean conditions for all wx E .0.....99 9}:
0 1 S 10 -
(34)
We reject all wi for which either condition does not hold.
k > N: Let T22 = R1- We reject all we E {0. ... different from we 10 "2 mod 10, and reject all wk if n2 or or n2 2 10
Proof. For k > N, we note that ne is fixed given y and nı through linearity of summation, and we only consider & S. N. We define as = 2i=b42 V/ 10 as the sum of the remaining digits of y. We note that y = 14 N-k + ag.
N+1
Algorithm rejects Wi without completions We first show that our algorithm only rejects wy for which no completion exists. We start with the constraint O < 1 Pk. and show that whenever this constraint is violated (i.e., Pk > [x), Wick has no completion. Consider the smallest possible completion of WK+L:N! setting each to O. Then nı pk 10 First, note that
10N No -1--12 1 ak
Next, add 4 N0 to both sides
(4 + 1) 10 > 4 10 10 - + =
By assumption, pis is an integer upper bound of and pk 2 4 + 1. Therefore,
n1 Pk 10 y
Since nı to be larger than y, n2 has to be negative, which is impossible.
Next, we show the necessity of the second constraint. Assume the constraint is unnecessary. that is, 4. > Pk 10t S. Consider the largest possible completion WE+L:N by setting each to 9. Then
Ps 10 N + N- -1
(px + 1) 10 -
We take n2 to be the maximum value, that is, n2 10º 1. Therefore,
ni + n2 = 10 - (px + 1) 10 -
We show that n, + n2 < y. Since we again have an integer upper bound, we know 4 2 Pk 10
S + 1. Therefore,
y 2 (p+ + + 10 N as
2 nl + n2 + S N - + a
There are two cases.
20

---

S = 0. Then ds < 10N - and SO
2 n1 + 122 + +2+ ag > R1 + +22.
S Then 0g = 10N 1, and so
y 2 n1 n2 1 11 + n2-
Algorithm accepts Wi with completions Next, we show that our algorithm only accepts wy with completions. Assume Equation 34 holds, that is, 4 Pk
10th -. We first consider all possible
completions of Wi-k- Note that ps: 10 $ n S pa 10 and
+ 10 and & ng S 10 1,
Pk 10 - 1 m1 + n2 - (px + 1) 10 + 10 2.
Similarly,
4 N < v (4x + 1) 10 - 1.
By assumption, Pk & l.. so pk
10 < 4 cot 10 For the upper bound, we again consider two cases. We use the second condition 4 S 10 + pæ - S:
S 0. Then (since there are trailing 9s),
y I (7x 1) 10 2 S (10* + Pk + 1) 10 -k
= (p& + 1) -0 + 10 -2
S 1. Then with trailing 9s.
y (4 1) 10 10 -
S (10* + p&) 10
= Ps 10 N- + 10 -1
S (pk + 1) N + 10 2,
since 10 2 1.
Therefore,
10 N
S - (px + 10 + 110 -2
N-A
and so there is valid completion.
I Details of the experiments
I.1 Multi-digit MNISTAdd
we take the MNIST (30 dataset and use each digit exactly once to create data. We follow 36 and require more unique digits for increasing N. Therefore, the training dataset will be of size 60000/2N /NN and the test dataset of size 10000/2N.
Like (36 37),
L1.1 Hyperparameters
We performed hyperparameter tuning on a held-out validation set by splitting the training data into 50.000 and 10.000 digits, and forming the training and validation sets from these digits. We progressively increased N from N 1, N 3, N insights into what hyperparameters are important. The most important parameter, next to learning rate, the weight of the L.2 regularization on the Dirichlet prior's parameters which should very high. We used ADAM 25 throughout, We ran each experiment 10 times to estimate average accuracy, where each run computes 100 epochs over the training dataset. We used Nvidia RTX A4000s GPUs and 24-core AMD EPYC-2 (Rome) 7402P CPUs.
N 8 during tuning to get improved
21

---

Parameter name
Value
Parameter
Value
Learning rate
0.001
Prior learning rate
0.01
Epochs
100
Amount beliefs prior
2500
Batch size
16
Prior initialization
0.1
of samples
600
Prior iterations
50
Hidden layers
3
L2 on prior
900.000
Hidden width
800
Table 4: Final hyperparameters for the multi-digit MNISTAdd task.
Parameter name
Value
Parameter name
Value
Perception Learning rate
0.00055
Prior learning rate
0.0029
Inference learning rate
0.003
Amount beliefs prior
2500
Batch size
20
Prior initialization
0.02
# of samples
500
Prior iterations
Hidden layers
2
L2 on prior
2.500.000
Hidden width
100
Epochs
5000
Pretraining epochs
50
Table Final hyperparameters for the visual Sudoku puzzle classification task.
We give the final hyperparameters in Table We use this same set of hyperparameters for all N. # of samples refers to the number of samples we used to train the inference model in Algorithm [ For simplicity, it also the beam size for the beam search at test time. The hidden layers and width refer to MLP that computes each factor of the inference model. There is no parameter sharing. The perception model is fixed in this task ensure performance gains are due neurosymbolic reasoning (see
35
I.1. Other methods
We compare with multiple neurosymbolic frameworks that previously tackled the MNISTAdd task. Several of those are probabilistic neurosymbolic methods: DeepProbLoog (5). DPLA* 337
NeurASP [58) and NeuPSL. 44 We also compare with the fuzzy logie-based method L.T [5] and
with Embed2Sym 3 and DeepStochLog [56). We take results from the corresponding papers, except for DeepProbLog and NeurASP, which are from [37], and LTN from [44] We reran Embed2Sym, averaging over 10 runs since its paper did not report standard deviations. We do not compare DPLA*
with pre-training because it tackles an easier problem where part of the digits labeled.
Embed2Sym 3 uses three steps to solve Multi-digit MNISTAdd: First, it trains neural network to embed each digit and predict the sum from these embeddings. then clusters the embeddings and uses symbolic reasoning to assign clusters to labels. A-NESI has a similar neural network architecture, we train the prediction network on an objective that does not require data. Furthermore, we train A-NESI end-to-end, unlike Embed2Sym. For Embed2Sym, we use symbolic prediction to refer to Embed2Sym-NS, and neural prediction to refer to Embed2Sym-FN which also uses prediction network but only trained on the training data given and does not use the prior to sample additional data
We believe the accuracy improvements compared to DeepProbLog to come from hyperparameter tuning and longer training times, as A-NESI approximates DeepProbLog's semantics.
1.2
Visual Sudoku Puzzle Classification
1.2.1
A-NeSI definition
First, we will be more precise with the model we use. We see x as a N x N x 784 grid of MNIST images, and beliefs P an N N N grid of distributions over N options (for example. for 4 x 4 puzzle, we have to fill in the digits {0, 2))). For each grid index i, the world variable
Wi, corresponds to the digit at location (i, For correct puzzles, we know that the digits at location
We take the results of LTN from 44 because overestimates its average accuracy.
S averages over the 10 best outcomes of 15 runs and
22

---

(i,5) and location (i') need to be different if -fi= - if (4,j) is in the same block as (",)"). For each pair of locations (i. (i', J') for which this holds, we have dimension y that indicates if the digits at that grid location are indeed different. The symbolic function considers each such pair and returns the corresponding y-
For the prediction model, we use a single MLP fe. That is, for each pair that should be different, we compute d (y PP) fo k.j. pr.r). This introduces the independence assumption that the digits at location (i,j) and location (i', """) being different does not depend on the digits at other locations. This is, clearly, wrong. However, we found it is sufficient to accurately train the perception model.
When training the prediction model, since we sample P from a Dirichlet prior that assumes the different dimensions of w are independent, the grid of digits are highly unlikely represent actual sudoku's s: There are about 10º1 Sudoku's 's and 9a1 possible grids (for 9 x 9 Sudoku's). However, it is quite likely to sample two digits that are different, and this is enough to train the prediction model.
1.2.2 Hyperparameters and other methods
We used the Visual Sudoku Puzzle Classification dataset from [4. This dataset offers many options: We used the simple generator strategy with 200 training puzzles (100 correct, 100 incorrect). We took a corrupt chance of 0.50, and used the dataset with 0 overlap (this means each MNIST digit can only be used once in the 200 puzzles). There are 11 splits of this dataset, independently generated. We did hyperparameter tuning on the 11th split of the 9 x 9 dataset. We used the other 10 splits to evaluate the results, averaging results over runs of each of those.
The final hyperparameters are reported in T The 5000 epochs took on average 20 minutes for the 4 x 4 puzzles, and 38 minutes for the 9 x puzzles on machine with single NVIDIA RTX A4000. The first 50 epochs we only trained the prediction model to ensure provides reasonably accurate gradients.
While 4 used NeuPSL, we had to rerun get accuracy results and results on 9 x 9 grids.
We implemented the exact inference methods using what can best be described as Semantic Loss 557. We encoded the rules of Sudoku described the beginning of this section as a CNP, and used PySDD (https: / //tgttbtt....t// com/ wannesm/ PPSSDD to compile this to an SDD (28] This was almost instant for the 4 4 CNF, but we were not able to compile the 9 x 9 CNF within 4 hours, hence why we report a timeout for exact inference. To implement Semantic Loss, we modified a Py PoTcch implementation available at hhttss///gtthti: to compute in log-space for numerically stable behavior. This modified version is included in our own repository. We ran this method for 300 epochs with a learning rate of 0.001. We ran this method for fewer epochs because it is much slower than A-NeSI even on 4 x 4 puzzles (1 hour and 16 minutes for those 300 epochs, so about 63 times slow).
wtt.ccmmmaaaa.eee http//uuaaaaleeeeeeeeee htw.aatteeemmmcee/////m/aa losslllsppp loss-pytorch
For both A-NESI and exact inference, we train the perception model on correct puzzles by maxi- mizing the probability that p(y 1|P). A-NESI does this by maximizing log ( = PP), while Semantic Loss uses PSDDs to exactly compute logp(y = 1(P). For incorrect puzzles, there is not much to be gained since we cannot assume anything about y. Still, for both methods we added the loss- log(1 - p(y = 1)) for the incorrect puzzles.
1.3 Warcraft Visual Path Planning
I.3.1 A-NeST definition
We see x as N X N x 3 x 8 x 8 real tensor: The first two dimensions indicate the different grid cells, the third dimension indicates the RGB color channels, and the last two dimensions indicate the pixels in each grid cell. The world w is an N x N grid of integers, where each integer indexes five different costs for traversing that cell. The five costs are [0.8, 1.2. 5.3, 7.7, 9.2), and correspond to the five possible costs in the Warcraft game. The symbolic function takes the grid of costs w and returns the shortest path from the top left corner (1, 1) to the bottom right corner (N, N) using Dijkstra's 's algorithm. We encode the shortest path as a sequence of actions to take in the grid, where each action one of the eight (inter-) caardianl directions (down, down-right, right, etc.). The sequence is padded with the do-not-move action to allow for batching.
23

---

For the perception model, we use single small CNN fo for each of the N x N grid cells. That is, for each grid cell, we compute P., fo (...) The CNN has single convolutional layer with output dimensions, 2 x 2 maxpooling layer, a hidden layer of 24 x 84 and a softmax output layer of 24 x 5, with ReI.U activations.
The prediction model is ResNet18 model [22]. with an output layer of 8 options. It takes an image of size 6 X N X N as input. The first 5 channels are the probabilities p and the last channel indicates the current position in the grid. The 8 output actions correspond to the 8 (inter-)carding) directions. We apply symbolic pruning (Section 3.3 to prevent actions that would lead outside the grid or return to a previously visited grid cell. We pretrained the prediction model by repeating Algorithm[[oo a fixed prior using 185.000 iterations (200 samples each) for 12 12, and 370.000 iterations (20 samples) for 30 x 30. We used fewer examples per iteration for the larger grid because Dijkstra's 8 algorithm became computational bottleneck. This took 23 hours for 12 12 and 44 hours for 30 x 30. Both used learning rate of 2.5 10-4 and an independent fixed Dirichlet prior with = 0.005. Standard deviations over 10 runs are reported over multiple perception model training runs the same frozen pretrained prediction model. We trained the perception model for only 1 epoch using learning rate of 0.0084 and a batch size 70.
I.3.2 Other methods
We compare to SPL I1 and I-MLE 41. SPL is also a probabilistic neurosymbolic method, and uses exact inference. Its setup is quite different from ours, however. Instead of using Dijkstra's is algorithm, it trains ResNet18 to predict the shortest path end-to-end, and uses symbolic constraints to ensure the output of the 8 is a valid path. Furthermore, it only considers the cardinal directions instead of all 8 directions. SPL only reports single training rule in their paper.
I-MLE is more similar to our setup and also uses Dijkstra's 's algorithm. It uses the first five layers of a 8 to predict the cell costs given the input image. One big difference to our setup is that I-MLE uses continuous costs instead of choice out of five discrete costs. This may be easier to optimize, as it gives the model more freedom to move costs around. I-MLE is reported using the numbers from the paper, and averages over runs.
To be able to compare to another scalable baseline with the same setup, we added REINFORCE using the leave-one-our baseline (RLOO, 2 implemented using the PyTorch library Storchastic (53). It uses the same small CNN to predict distribution over discrete cell costs, then takes 10 samples, and feeds those through Dijkstra's to get the shortest path. Here, we represent the shortest path as an N x N grid of zeros and ones. The reward function for RLOO is the Hamming loss between the predicted path and the ground truth path. We use a learning rate of 5 10-4 and a batch size of 70. We train for 10 epoch and report the standard deviation over 10 runs. We note that RLOO gets quite expensive for 30 x 30 grids, as it needs 10 Dijkstra calls per training sample.
Finally, we experimented with running A-NESI and RLOO simultaneously. We ran this for 10 epochs with learning rate of 5 10-4 4 and batch size of 70. We report the standard deviation over 10 runs.
24


Reviews:
[{"review_id": "RpvnGzhLFM", "reviewer": "Reviewer_iEEt", "summary": "This paper introduces A-NeSi, a fast approximate procedure for NeSy architectures\nbased on probabilistic logic.  These architectures do not scale gracefully to\nproblems involving many possible worlds, and the goal of A-NeSi is to scale them\nup.  In short, A-NeSi employs a surrogate models (autoregressive neural nets)\nto replace the most computationally intensive steps.  Experiments indicate a\nsizeable speed-up compared to SOTA probabilistic-logical approaches on a\nvariety of tasks - from multidigit MNIST addition to pathfinding.", "questions": "Q1. How strongly does performance of A-NeSi depend on the complexity of the hard constraints/knowledge?  Especially when knowledge encodes long-range interactions between variables (or, if you prefer, tree width).  I would imagine beam search could choke up in these cases, and I'd appreciate some discussion on the expected behavior.", "limitations": "Limitations are clearly discussed in the conclusion.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ Very clearly written.  There's plenty of figures to build intuition, which is good.\n+ Tackles a very prominent problem in neuro-symbolic AI - scalability of MAP inference for probabilistic-logical approaches, a major player in this field.\n+ The idea of using surrogates is simple but very sensible.  (What is not simple is ensuring the output satisfies the knowledge.)\n+ All modeling choices are clearly motivated.\n+ Empirical evaluation is both extensive and very promising.\n+ Related work is both compact and comprehensive, well done.", "weaknesses": "No major deficiencies that I could find.  This is a solid contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments. \n\n> How strongly does performance of A-NeSi depend on the complexity of the hard constraints/knowledge? Especially when knowledge encodes long-range interactions between variables (or, if you prefer, tree width). I would imagine beam search could choke up in these cases, and I'd appreciate some discussion on the expected behavior.\n\nGood question. We believe the complexity of the constraints matters significantly for the learnability of the prediction model. While we leave a proper study for future work, we predict the task's predictability, decomposability and degree of structure are important factors. Addition and sudokus are two tasks that are easy to decompose, making learning the prediction model relatively easy. Path planning is less decomposable and, as you mention, requires more long-range interactions. The prediction model took much longer to train for this task. \n\nThe reviewer proposes the performance of beam search may degrade in challenging tasks. We do not currently see the bottleneck in the (test-time) beam search: In most neurosymbolic tasks, the perception model has low entropy after training, meaning there are few options to consider. For instance, [1] found that finding the MAP state is efficient in low-entropy distributions. \n\n[1] Manhaeve, R., Marra, G., & De Raedt, L. (2021). Approximate inference for neural probabilistic logic programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (pp. 475-486). IJCAI Organization.\n"}, {"review_id": "mx48Sa60S6", "reviewer": "Reviewer_xznW", "summary": "The paper presents a polynomial time solution to the approximate neurosymbolic inference problem for probabilistic neurosymbolic learning problems. The approach is based on a variant of predictive processing, with a prediction model and an explanation model. The results are interesting, and successfully solve three different non-trivial challenge problems: MNISTAdd, Visual Sudoku, and Warcraft Visual Path Planning.", "questions": "- Does this approach lead to an improved algorithm or heuristic for weighted model counting in general? \n\nThanks for the response in the rebuttal.", "limitations": "The limitations listed in the paper are not clear. For example, it is noted that A-NESI did not perfectly train the prediction model in more challenging problems. It would be helpful to make this precise: what is the problem, what makes it challenging, and what was the quantitative performance of A-NESI? If it is one of the problems studied before, perhaps that section can be cited with an explanation.\n\nThe responses from the authors are interesting. I have updated my score to reflect my view and understanding of the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ The paper is an interesting attempt at bringing predictive processing concepts to neuro symbolic reasoning using probabilistic programs.\n+ The idea of output space factorization is useful, as it helps reduce the complexity of the problem. However, it seems that humane effort may be needed to decompose the output in a helpful manner.\n+ The design of belief priors using high-entropy Dirichlet distributions to cover all possible input scenarios or combinations of the factorized  space is an interesting observation.\n+ The pseudocode in Figure 2 is clear and makes the underlying algorithm more easily reproducible.", "weaknesses": "- It is unclear how these experiments in controlled settings like MNISTAdd relate to robust neuro symbolic reasoning in more exciting tasks, like image classification or activity recognition. For example, factorization in such settings may not be easy.\n- The paper has no discussion about how this approach is related to predictive processing. Perhaps, a comparison would be helpful to the readers of the paper.\n- There are no bounds on the approximations being produced by this approach. How do the various design choices impact the quality of the approximation being obtained?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and interesting questions. \n\n> It is unclear how these experiments in controlled settings like MNISTAdd relate to robust neuro symbolic reasoning in more exciting tasks, like image classification or activity recognition. For example, factorization in such settings may not be easy.\n\nIn the settings mentioned by the reviewer, we have background knowledge of what neural network outputs are allowed. For instance, consider scene graph generation. There, we may have rules like $\\forall x, y: \\phi(x, y)$. We have a natural decomposition over the universal quantifier: For each rule and every pair of objects, define a boolean variable with whether the proposition holds. This factorisation is rather large but should be easy to learn. We can also consider other heuristics, such as grouping per object and grouping by some rules. \n\n> The paper has no discussion about how this approach is related to predictive processing.\n\nWe thank the reviewer for the suggestion. We are not experts in cognitive science and do not immediately see the suggested connection to predictive processing. However, the connection of the ideas of A-NeSI to cognitive science is an interesting option for future work. Of course, any suggested similarities from the reviewer are very welcome.\n\n\n> How do the various design choices impact the quality of the approximation being obtained?\n\nThat is a good question. Our paper focused on empirically showcasing the strengths and scalability of our method, leaving approximation bounds for future work. However, we hypothesise these factors will make an impact: The expressiveness and architecture of the neural network, time of training, the divergence between the prior $p(\\mathbf{P})$ and the evaluation distribution, and the complexity of the background knowledge. The latter include problem size, sparsity, connectedness, decomposability and structure. We highlighted some of these concerns in the limitations section and will give it another pass. \n\nExactly how these relate is a complex question; we suspect no easy answer exists yet. There has been a significant amount of research into whether neural networks can learn reasoning tasks, in and out of distribution, and no clear and general answer exists. \n\n> Does this approach lead to an improved algorithm or heuristic for weighted model counting in general?\n\nGood question! Yes, we can use A-NeSI for general approximated WMC. However, we have yet to compare A-NeSI to existing approximation schemes: For this paper, our focus was on efficiently estimating the _gradient_ of the WMC, rather than on the accuracy of the WMC estimate itself. \n\nWe hypothesise that the main benefit of A-NeSI comes from amortisation (like in variational inference): Training on many different values of $\\mathbf{P}$ can be expensive but allows for rapid computation for a new value of $\\mathbf{P}$. Furthermore, A-NeSI is very flexible in computation budgets: We can train for as many iterations as possible in our compute budget to improve our estimations. A downside of A-NeSI is the lack of guarantees on the approximation bounds, as the reviewer mentions. Future work could study this question.\n\n> The limitations listed are unclear. Make this precise: what is the problem, what makes it challenging, and what was the quantitative performance of A-NESI?\n\nThe fact that the prediction model is not trained perfectly is made clear in the divergence between neural and symbolic predictions in Section 4.1 for $N=15$. If there is such a divergence, the most likely answer, according to the prediction model, is not the one reflected by the MAP sum. Here, the increased dimensionality made it harder for the neural network to learn the problem perfectly. We found similar issues in path planning, a much more complicated task in all three dimensions mentioned in our limitations section: We needed much longer training times to get good gradient estimates. We revised the paper to add these examples."}, {"review_id": "QtgL69WTim", "reviewer": "Reviewer_agwr", "summary": "This paper introduces a variant of Probabilistic Neurosymbolic Learning that uses neural networks for approximate inference (vs. prior exponential-time exact inference). The efficacy of this approach is well-supported by various experiments.", "questions": "- The subscripts of $\\textbf{P}$, the belief, seem a bit odd and not well-defined. Is $\\textbf{P}$ a matrix? The subscript notation $_{w_i}$ seems especially odd/undefined. It would be good to make this more precise.\n- Is it correct that, once you know $\\textbf{P}$, you can just read off $p(\\textbf{w}|\\textbf{P})$ directly from $\\textbf{P}$? If so, it seems like $p(\\textbf{w}|\\textbf{P})$ obscures this. Is there an alternative way of writing that to make it more explicit, like $f_P(w)$? (I don't love that notation, either - but I suspect there's a way to make this clearer. What do you think?)\n- Is making the $\\phi$ explicit in the notation accomplishing that much? My sense right now is that it's just obscuring the notation. Am I missing something?\n- $k_W$ , $k_Y$ -- \"discrete choices\" maybe needs a bit more explanation. It's unclear at first whether this is the number of choices *within* $W$ -- i.e., $|W|$ -- or how many choices are drawn from $W$. Maybe specifying $k_W$ in the example -- e.g., $k_W = 2$ in the example -- would be helpful. Same for $k_Y$. Also, maybe this is the right place to introduce the notation $w_i$ for $i \\in \\{1,\\dots,k_W\\}$ and specify the spaces that $w_i$ and $y_i$ live in. If for some reason giving these space symbols is not needed or unnecessarily complicated, could you please explain? It seems more grounded to give them symbols.\n- nit: should equation (5) have an indicator? (dropping it feels a bit too informal)\n- The symbolic pruner notation feels off to me. Is there a separate $s$ for each $i$? Do $q,s$ depend on $i$ in $q \\cdot s$? It seems like it should based on $s = s_i(\\cdot)$, but it seems like it shouldn't if they're vectors (i.e., what are the dimensions of $s,q$?).\n- Is $s_i$ given or learned?\n- \"In our studied tasks, neural prediction cannot perform better than symbolic prediction.\" But sudoku shows slightly better neural prediction than symbolic prediction. It would be good to comment on this.", "limitations": "The authors do a nice job outlining various limitations of this work. I found the presentation honest and straightforward.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is well-written and overall quite clear (i.e., the paper is high-quality in general). The goals are clearly stated. For example, Section 3 starts with \"Our goal is to reduce the inference complexity of PNL.\"\n- The experiments are described thoughtfully with good visualizations and tables.\n- Using MNISTAdd as a running example throughout was a great idea. I think it added a lot.\n- The authors are studying a significant problem -- i.e., that of neurosymbolic learning -- which feels especially timely.\n- It is a bit harder for me to comment on originality. To the best of my knowledge, this work is rather original, but there might be other related prior works not mentioned by the authors of which I'm unaware.", "weaknesses": "My main concerns are about the notation. I think it could be improved, as discussed here and in the Questions section.\n- See questions below. \n- Beyond that, some of the notation is a bit clunky, particularly the double subscripts -- e.g., $q_{\\phi_p}$.\n- Relatedly, it seems like some of these subscripts are a bit inconsistent:\n  - there's a p on the RHS of equation (2) but no p on the LHS of equation (3) - why?\n  - in Section 3.3, there's both $\\phi$ and $\\phi_e$ seemingly inconsistently\n  - more related questions below\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their supportive comments. We appreciate the detailed feedback on notation and useful questions, which we discuss below. \n\n> Double subscripts on parameters are clunky, and their use is inconsistent\n\nYou are correct. We will update this and make it more consistent throughout the text, likely by having different parameters $\\mathbf{\\phi}$ and $\\mathbf{\\psi}$ for the prediction and explanation models.\n\nWe will also update the inconsistencies throughout.\n\n> The subscripts of the belief need to be more well-defined. Is it a matrix?\n\nAgreed, we will do this. $\\mathbf{P}$ is not quite a matrix. It is a list where each element is in some simplex. If $\\Delta_n$ is the n-dimensional simplex, then $\\mathbf{P}_i\\in \\Delta\\_{k\\_{W\\_i}}$, where $k\\_{W\\_i}$ is the number of categories in the $i$th variable of $W$. Therefore, each $\\mathbf{P}_i$ represents a categorical probability distribution over $k\\_{W\\_i}$ options.\n\nIt is like a matrix where the length of each row is variable, but this subtlety would make the notation dense, hence why we treat it informally as a matrix-like object. We will play around with this. Thanks!\n\n> The \"discrete choices\" need more explanation. Clarify their use in the example.\n\nGood question, and related to our answer from above. In an earlier version, we defined these formally, but we dropped this later to this for brevity, since the exact definition of the spaces is not used in the paper. We will reintroduce these definitions to balance these concerns. \n\nTo answer the reviewer's question: Each $w_i\\in \\{1, ..., k_{W_i}\\}$ is a categorical random variable. Here $k_{W_i}$ is the number of categories in the $i$th variable, like above. Then $k_W$ is the number of discrete variables in the problem. \n\n> Can you read of $p(\\mathbf{w}|\\mathbf{P})$ directly from $\\mathbf{P}$? Is there a less obscuring notation?\n\nThis is correct - And yes, it does obscure it somewhat. One option is to use $\\mathsf{Cat}(\\mathbf{w}; \\mathbf{P})$ to emphasise it is a multivariate categorical distribution, but this is more verbose. We will play around with some options, thanks for the suggestion!\n\n> Is making the parameter $\\phi$ explicit accomplishing much?\n\nWe wanted to emphasise that $q$ is a neural network with some parameters that change during training, especially in the two algorithms. We will give this some thought, but will likely keep it.\n\n> nit: should equation (5) have an indicator? (dropping it feels a bit too informal)\n\nCorrect, we (informally) dropped the indicator. We will reintroduce it.\n\n> The symbolic pruner notation feels off\n\nLooking back on this equation, we agree. We defined $\\mathbf{s}$ as a $k\\_{W\\_i}$-dimensional vector, but (as you mention) it is much clearer to define $s$ as a function. Then the definition is $q\\_{\\phi\\_e}(w\\_i=j|\\mathbf{y}, \\mathbf{w}\\_{1: i-1}, \\mathbf{P})=\\frac{\\hat{q}\\_{\\phi\\_{E}}(w_i=j|\\mathbf{y}, \\mathbf{w}_{1: i-1}, \\mathbf{P}) s\\_{\\mathbf{y}, \\mathbf{w}\\_{1: i-1}}(w_i=j)}{\\sum\\_{j'=1}^{k\\_{W\\_i}} \\hat{q}\\_{\\phi\\_{E}}(w_i=j'|\\mathbf{y}, \\mathbf{w}\\_{1: i-1}, \\mathbf{P}) s\\_{\\mathbf{y}, \\mathbf{w}\\_{1: i-1}}(w\\_i=j')}$ (where $s\\_{\\mathbf{y}, \\mathbf{w}\\_{1: i-1}}: W\\_i \\rightarrow \\\\{0, 1\\\\}$). \n\n> Is the symbolic pruner $s$ given or learned?\n\nIn our experiments, we give $s$. In Appendix G, option 4 we describe an extension where $s$ is learned.\n\n> \"In our studied tasks, neural prediction cannot perform better than symbolic prediction.\" But sudoku shows slightly better neural prediction than symbolic prediction. It would be good to comment on this.\n\nThe variance of both of these results is rather high. We believe this discrepancy simply comes from a lack of statistical power, and both prediction methods perform about equally. We will mention this. \n"}, {"review_id": "G9U2H86zlq", "reviewer": "Reviewer_8FBf", "summary": "This paper presents a variational framework for approximating neuro-symbolic inference. It addresses the weighted model counting (WMC) and most probable explanation (MPE) problems by introducing prediction and explanation models. Training techniques, such as output space factorization, regularized Dirichlet prior, and joint matching loss are discussed. To improve training efficiency and ensure logical constraint satisfaction during testing, a symbolic pruner is also proposed . Experimental evaluations demonstrate scalability and performance across three neuro-symbolic tasks.", "questions": "- Should  $\\phi \\leftarrow \\textbf{Algorithm 2}(\\textsf{beliefs}, \\phi)$ be changed to $\\textbf{Algorithm 1}$?\n- Does the framework have requirements for background knowledge? For example, should it be presented in the form of CNF?\n- Is it difficult to design and train the prediction model, given that it involves the approximation of the symbolic reasoning?", "limitations": "Yes, the limitations of the approach have been presented. The work does not have negative social impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and easy to understand, with a clear statement of the problem and methodology.\n- The framework is simple and scalable, which may inspire further improvements in future work.\n- Some training techniques are interesting, particularly the joint matching loss, which is related to GFlowNet.", "weaknesses": "- The authors have carefully discussed some weaknesses in Section 6. \n- The motivation behind the prediction model and explanation model needs to be clarified.\n    - It is unclear why the explanation model is necessary. From my understanding, only the prediction model is needed for neuro-symbolic training: we just need to train the prediction model using Eqn. (7), and then train the neural network using Eqn. (4); or repeat these two steps iteratively.\n    - Another issue is the necessity of the prediction model. First, the prediction model is introduced to approximate weighted model counting, but approximate counting or sampling of $\\mathbf{w}$ is still required during its training. Second, in Line 192, the authors report that the prediction model cannot perform better than using symbolic prediction.\n- Some techniques are so specific that they appear to be designed only for the MNISTAdd task. For instance, as mentioned in Appendix G, the symbolic pruner is highly efficient for MNISTAdd task due to its simple mathematical structure. However, for more complex tasks, a SAT solver must be used, and the number of solver calls is proportional to the problem dimension, which is not acceptable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and appreciate their support of the paper's writing and the framework's simplicity. The reviewer would like a clarification on the motivation behind the prediction and explanation model, which we provide below.\n\n> It is unclear why the explanation model is necessary. From my understanding, only the prediction model is needed for neuro-symbolic training: we just need to train the prediction model using Eqn. (7), and then train the neural network using Eqn. (4); or repeat these two steps iteratively.\n\nThe reviewer is correct: The explanation model is indeed optional. The explanation model approximates the posterior, which can 'explain' a decision with the $\\mathbf{w}$ that is most likely for that decision. As mentioned, interleaving Eq 7 and 4 (the prediction-only variant) is enough to train the perception model in A-NeSI: This is 'A-NeSI (predict)' in Table 1, and Tables 2 and 3 also use this variant.\n\nWe will update the paper to emphasise this point. \n\n> Another issue is the necessity of the prediction model.\n\nThe prediction model is necessary for A-NeSI and is why our method scales while exact inference does not. We will answer both arguments separately:\n\n> First, the prediction model is introduced to approximate weighted model counting, but approximate counting or sampling of $\\\\mathbf{w}$ is still required during its training.\n\nWe do not perform approximate counting during the training of the prediction model. Instead, we indeed sample $\\mathbf{w}$ to train it (see Equation 7). However, this sampling step is fast: To train the prediction model, we do not sample from the posterior $p(\\mathbf{w}|\\mathbf{y}, \\mathbf{P})$ (expensive, requires counting in the normaliser) but from $p(\\mathbf{w}|\\mathbf{P})$ (fast, does not require normalising. It is just a single `torch.multinomial` call). Therefore, we bypass expensive counting or sampling while training the prediction model. Furthermore, evaluating $c(\\mathbf{w})$ is also usually fast. We will highlight this efficiency in the paper.\n\n> Second, in Line 192, the authors report that the prediction model cannot perform better than using symbolic prediction.\n\nThe reviewer is correct that during _testing_, the prediction model can not perform better than symbolic prediction in our tasks. However, the prediction model is still necessary: We need it to (efficiently/scalably) _train_ the perception model (Equation 4). However, we can throw the model away after training and use symbolic prediction for maximum accuracy. We will clarify this in the text.\n\n> Some techniques are so specific that they appear to be designed for the MNISTAdd task. For instance, the symbolic pruner is highly efficient for MNISTAdd task due to its simple mathematical structure. However, for more complex tasks, a SAT solver must be used, and the number of solver calls is proportional to the problem dimension, which is not acceptable.\n\nThe symbolic pruner is very flexible in its design: While in the general case, we can always find a _perfect_ symbolic pruner with SAT-solving (which is, as you mention, quite expensive), we can often design fast imperfect pruners that still help A-NeSI. For instance, we used a fast, imperfect pruner in the Path Planning task to ensure the prediction model always returns a path (see Appendix I.3.1). We called those 'local constraints' in Appendix G.3. In hindsight, imperfect constraints may be more apt. Furthermore, as discussed in Appendix G.4, one could _learn_ an (imperfect) symbolic pruner. \n \nWe will update Appendix G to clarify the possibilities of the design of the symbolic pruner. \n\n> Does the framework have requirements for background knowledge? For example, should it be presented in the form of CNF?\n\nSection 2.1 (problem components) defined the background knowledge as a deterministic black-box function $c$ between discrete input and output variables. Therefore, the two requirements are that $c$ is deterministic and that the domain and co-domain are discrete (although extensions to continuous variables are possible). The background knowledge does not have to be in a specific form (like CNF), but knowing about the form may help us design output factorisations and symbolic pruners. We will clarify this point in the background section.\n\n> Is it difficult to design and train the prediction model, given that it involves the approximation of the symbolic reasoning?\n\nThis paper used simple MLPs for the first two experiments and a standard ResNet for the second. The training of the prediction models went smoothly for most experiments but the most challenging one (the 30x30 path planning). We trained on this problem for 44 hours and observed that the loss decreased slowly and still needed to converge. \n\nDoes this generalise to more complex settings? There has been active research into whether neural networks can learn reasoning tasks, and the main consensus is positive as long as we evaluate the network in-distribution. We are not interested in out-of-distribution generalisation in A-NeSI, especially if the prior gives a good match. Furthermore, A-NeSI gives ample opportunity to design the prediction model with any neural network. In particular, GNNs will often be a good choice.\n\n\n> Should Algorithm 2 be changed to Algorithm 1?\n\nThis is indeed a typing mistake. We will correct this in the revised version. Thanks!"}]

Author rebuttal:
We thank the reviewers for their time and their reviews. The reviewers mention the clear writing and statement of the problem, motivation and methodology (`iEET`, `agwr`, `8FBf`), in particular, the use of the MNISTAdd example (`agwr`), the comprehensiveness of related work (`iEEt`), the description of the experiments (`agwr`) and the pseudocode (`xznW`). The reviewers also mention the importance of the problem A-NeSI tackles (`iEEt`, `agwr`). The reviewers discuss the simplicity of the method (`iEEt`, `8FBf`) with possibilities for future work (`8FBf`) while mentioning that A-NeSI contains several interesting (`xznW`, `8FBf`) and original (`agwr`) ideas. Furthermore, the reviewers note that the empirical evaluation is extensive and promising (`iEEt`), demonstrating scalability and performance (`agwr`, `8FBf`) in non-trivial problems (`xznW`).

Reviewer `8FBf` asked for clarification on the motivation of the prediction and explanation models. We agree with reviewer `8FBf` that the explanation model is optional and discuss the benefits of also modelling the explanations. Furthermore, we clarify why training the prediction model does not require approximate counting or expensive sampling. Finally, while at _test-time_ the prediction model cannot be better than the symbolic prediction, we discuss why we need the prediction model to do scalable _training_. 

Reviewer `agwr` provides valuable in-depth comments about the notation, most of which we implement. In different forms, the reviewers `xznW`, `iEEt` and `8FBf` all ask how the techniques proposed in A-NeSI will generalise to other settings. We answer or clarify these questions in a separate response to the individual reviewers.

Meta-review: This paper aims to scale up neurosymbolic methods by learning predictive models that can stand in for a symbolically computed loss function. The paper addresses an important problem in neurosymbolic AI and the proposed solution performs reasonably well.
Decision: Accept (poster)