Learning where and when to reason in neuro-symbolic inference
Authors: Cristina Cornelio
Jan Stuehmer
Shell Xu Hu
Timothy Hospedales
Venue: ICLR 2023 notable top 5% (2023)

Abstract: The integration of hard constraints on neural network outputs is a very desirable capability. This allows to instill trust in AI by guaranteeing the sanity of that neural network predictions with respect to domain knowledge. Recently, this topic has received a lot of attention. However, all the existing methods usually either impose the constraints in a "weak" form at training time, with no guarantees at inference, or fail to provide a general framework that supports different tasks and constraint types. We tackle this open problem from a neuro-symbolic perspective. Our pipeline enhances a conventional neural predictor with (1) a symbolic reasoning module capable of correcting structured prediction errors and (2) a neural attention module that learns to direct the reasoning effort to focus on potential prediction errors, while keeping other outputs unchanged. This framework provides an appealing trade-off between the efficiency of constraint-free neural inference and the prohibitive cost of exhaustive reasoning at inference time. We show that our method outperforms the state of the art on visual-Sudoku, and can also benefit visual scene graph prediction. Furthermore, it can improve the performance of existing neuro-symbolic systems that lack our explicit reasoning during inference.

Published as a conference paper at ICLR 2023
LEARNING WHERE AND WHEN TO REASON IN NEURO-SYMBOLIE SYMBOLIC INFERENCE
Cristina Cornelio', Jan Stuchmer' Shell Xu Hut, Timothy Hospedales* Samsung AI, Cambridge
{c. cornelic, shell hu, t. hospedales [ com @samsung.
'Hiiellberg Institute for Theoretical Studies and Karlsruhe Institute of Technology [jan. st seuhmer) -itttts.. org. com
ABSTRACT
The integration of hard constraints on neural network outputs is a very desirable capability. This allows instill trust in AI by guaranteeing the sanity of that neu- ral network predictions with respect to domain knowledge. Recently, this topic has received a lot of attention. However, all the existing methods usually either impose the constraints in "weak" form at training time, with no guarantees at inference, or fail provide a general framework that supports different tasks and constraint types. We tackle this open problem from a neuro-symbolic perspective. Our pipeline enhances a conventional neural predictor with (1) a symbolic rea- soning module capable of correcting structured prediction errors and (2) neural attention module that Iearns to direct the reasoning effort to focus on potential pre- diction errors, while keeping other outputs unchanged. This framework provides an appealing trade-off between the efficiency of constraint- free neural inference and the prohibitive cost of exhaustive reasoning at inference time. We show that our method outperforms the state of the art on visual-Sudoku, and can also benefit visual scene graph prediction. Furthermore, can improve the performance of ex- isting neuro-symbor neurolsymbolic systems that lack our explicit reasoning during inference.
INTRODUCTION
Despite the rapid advance of machine learning (ML), it is still difficult for deep learning archi- tectures to solve a certain classes of problems, especially those that require non-trivial symbolic reasoning (e.g. automated theorem proving or scientific discovery). very practical example of this limitation even in applications that are typical deep learning territory such as image processing is the difficulty of imposing hard symbolic constraints on model outputs. This is relevant when learning systems produce outputs for which domain knowledge constraints apply (e.g.. Figure 2 The common situation today, that ML systems violate such constraints regularly, is both a missed opportunity to improve performance and more importantly source of reduced public trust in Al.
This issue has motivated a growing body of work in neuro- syuro-yymbolic methods that aim to exploit do- main knowledge constraints and reasoning to improve performance. Most of these methods address neuro-symbolic learning. where constraints are applied the loss function (e.g.. Xu et al. (2018); Xie et al. (2019): Li et al. (2019); Wang & Pan (020 and predictions that violate those constraints are penalised. In this way, during learning, the model "encouraged" to move close to a solution that satisfies the constraints/rules. However, high-capacity deep networks in any case usually fit their training sets, and thus violate no constraints on the output labels during supervised learning. The central issue of whether constraints are also met upon inference during deployment unaddressed by these methods and is under-studied more generally Giunchiglia et al. (2022b); Dash et al. (2022); von Rueden et al. (202T). A minority of studies have worked towards exploiting constraints dur- ing inference. Since in general reasoning to guarantee that constraints are met is expensive, some methods try to apply soft relaxations (Daniele & Serafini, 2019 [i & Srikumar 2019 Wang al.) 2019), which is unhelpful for trust and guarantees. The few methods that manage to impose exact constraints are either restricted to very simple or restrictive rules (Yu al. 2017 Giunchiglia et al.
Work done while Samsung AI, Cambridge

---

Published as a conference paper at ICLR 2023
2022b) that are not expressive enough, involve invoking full reasoning engine during inference Manhaeve et al. (2018): Yang et al. 2020). which is prohibitively costly in general.
In this work we explore new ncuro-symbolic integration approach to manage the trade-off be- tween the cost, expressivity, and exactness of reasoning during inference. Our Neural Attention for Symbolic Reasoning (NASR) pipeline leverages the best of neural and symbolic worlds. Rather than performing inexact, inexpressive, or intractable reasoning, we first execute an efficient neural- solver to solve task, and then delegate a symbolic solver to correct any mistakes of the neural solver. By reasoning over only a subset of neural fact predictions we maintain efficiency. So long as the facts selected have no false positives, we guarantee constraints are met during inference. Thus we enjoy most of the benefit of symbolic reasoning about the solution with a cost similar to neu- ral inference. This dual approach aligned with the 'two systems' perspective of [Sloman| (1996) and Kahneman (201T) that has recently been applied in Al (e.g. [Booch et al. (202T) and LeCun (2022). More specifically, our NASR framework is built upon three components: A neural network (Neuro-Solver) is trained to solve a given task directly; symbolic engine that reasons over the output of the Neuro-Solver, and can revise its predictions in accordance with domain knowledge; and a hard attention neural network Mass--Predictor,, that decides which subset of Neuro-Solver predictions should be eligible for revision by the reasoning engine using domain knowledge. The Mask-Predicts essentially learns when and where to reason in order to effectively achieve high pre- diction accuracy and constraint satisfaction with low computation cost. Since the reasoning engine not generally differentiable, we train our framework with reinforcement learning (RL).
The contributions of our work can be summarized as follows: (1) We provide a novel neuro-symbolic integration pipeline with novel neural-attention module Mask-Predictoon that works with any type of constraints/rules (2) We apply such architecture in the case of the visual-Sudoku task (given an im- age of a incomplete Sudoku board, the goal is to provide complete symbolic solution) considerably improving the thate-of-the-art (3) Finally, we show that when wrapping an existing state-of-the-ar (replacing Neuro-Solver), our framework significantly improves its model performance.
The code is available at:
1.1 RELATED WORKS
There has been a lot of recent research regarding the imposition of constrains in neural networks This can be roughly divided in the following categories: 1) Modification of the Loss function: Xu al. (2018) add a component the loss function quantifying the level of disagreement with the constraints; A similar idea can be found in the work of Xie et al. (2019) and Li et al. (2019); Wang & Pan (2020) instead exploit a parallel neuro-reasoning engine to produce the same output as the neural process and then add the distance between the two outcomes in the loss. 2) Adversarial
training: In the work of Ashok et al.] (2021) they integrate NN with violation function gener- ating new data; A similar idea can be found in the work of Minervini & Riedel (2018). 3) Adding an ad-hoe constraint output layer: One example is adding layer to the network which manipu- lates the output enforcing the constraints Giunchiglia & Lukasiewic7 (202T); Ahmed et al. (2022) adds a compiled logic circuit layer to the network enforcing the constraints; Yang et al. (2020) and Manhaeve et al.) (2018) instead create a parallel between the logic predicates with their neural ver- sion. 4) Logic relaxations: Daniele & Serafini (2019) use a differentiable relaxation of logic to extend NN with an output logic layer to increase the probability of compliant outcomes; Li & Srikumar (2019) have similar approach but on the internal layers, augmenting the likelihood of neuron when a rule is satisfied: Wang al. (2019) introduce a differentiable MAXSAT solver that can be integrated into neural networks; Similar ideas using different types of logic relaxations can be found in the work of Gan et al.] (202T): Sachan al. (2018); Donadello & Serafini (2019) and Marra et al. (2019). 5) Neuro-symbolic integrations: The alternating of purely symbolic compo- nents with neural ones can be found in the work of Agarwal et al. (202T) where the authors create an encoder/decoder with a standard reasoner in the middle. In another approach, Yang et al. (2020) combine answer set programs with the output of a neural network. Similar methods are the one of Tsamoura et al. (2021) and of Manhaeve et al. (2018). Other neuro-symbolic integration methods worth mentioning (that consider the specific show case of the Visual Sudoku task) are: Brouard et al.
(020) extract preferences from data and push it into Cost Function Networks; Mulamba et al. (2020) combine a neural perception module with purely symbolic reasoner; and Yiwei et al. (202)) use curriculum-learingg waw.uuuu---eaningiii-----ee with-restarts framework to boost the performance of Deep Reasoning Nets.
2

---

Published as a conference paper at ICLR 2023
Neural Component
Symbolic Component
Symbolic
Madking
Neuro solver
Salutian vector
vector
Rules
Fral salition
Mask Predictor
Perception traedaiis an
complete symbolc solution
to its symbok rppres invernntttion
Solvertii gontrates 3
identifies the components violate the rulcs
Logie Solver corrects the predictions
Sol Lltiinn vector
Musland
057
Figure 1: Pipeline for solving visual-Sudoku with our Neural Attention for Symbolic Reasoning.
METHOD
In this work consider the type of tasks where multiple interpretable "facts" are predicted by neural model on which the imposition of hard constraints is desirable. More formally, we consider set of input data points (æ: E X) representing instances solve (e.g. the picture of a partially filled Sudoku board), and, a set multi multi-dimensional output data points (y E )) that correspond complete interpretable (symbolic) solutions (e.g. the symbolic representation of completely filled Sudoku board). The collection of N of these pairs of data points will form the task dataset D far, v 1- Moreover, we require that the task (e.g. completing a partially filled Sudoku board) can be expressed (fully or partially) by a set of rules R. in the form of bomain-knowledd constraints (e.g. the rules of the Sudoku game).
The goal is to learn function f X' - y that associates solution to given input instance, and which further satisfies the rules R.. To solve this class of problems, we propose neuro-syme symbolic pipeline that integrates 3 components, the Neuro-Solver, the Mask-Predictor and the Symbolic- Solver and that works as follows: An input instance is first processed by the Neuro-Solver that outputs approximate solution. The solution is then analyzed by the Mask-Predictor that has the role of identifying the components of the Neuro-Solver predictions that do not satisfy the set of domain-knowledde knowledge constraints/rules R. The masking output of the Mask-Predictor is then com- bined with the probability distribution predicted by the Neuro-Solver. This is done by deleting the wrong elements of the predictions, leaving the corresponding components "empty" (the component is filled by an additional class 0, indicating masked element). This masked probability distribution then fed to the Symbolic-Solver that fills the gaps with feasible solution (satisfying the con- straints/rules R). In brief, the role of the Symbolic-Solver is to correct the Neuro-Solver prediction errors identified by the
More formally: 1) The Neuro-Solver is function ns(() that that maps input E X' (where X the set of all possible inputs for the task under consideration) (where )' is the set of all the possible complete solutions): 2) The Maask-Predictor is a function mp(-) that takes in input a probability distribution over ) and produce as output a probability distribution over Z [0. 1] (where & is the dimension of y E V); 3) The Symbolic Solver is function sb(-) that maps y (where )" is y with an additional class 0, corresponding to a masked solution element) to probability distribution over y
probability distribution over y
The final hypothesis function fe. mapping X' to a probability distribution over y and representing the neuro-symbolic pipeline approximating the target function f(-), is defined as:
fo(x)) =b(( ns(x)) arg max(mp(nssz)))
R
where O is the Hadamard (element wise) product and are the learnable parameters of ns and mp
Figure shows the pipeline architecture for the Visual Sudoku task.
Example 1 An example application is the visual Sudoku task (Figure 7 This task consists of pro- viding a complete Sudoku board y E y corresponding to the solution of an incomplete input board
This assumes the solver expects 0 to indicate symbol to fill. If the solver expects another symbol (or generally), we add adapter function as fo(z) sb{ adapt( na(z), arg (mp((s(<)))) ) R.
3

---

Published as a conference paper at ICLR 2023
Neuro Salvor
PaskoPradictor
Symbolic-Solvve
Hone
ham
Tal
Horse
hes
Tai
Horse
Tail
In fromt
hont
front
ceing
Jacket
Jocket
Weatleg
Jacket
Person
Person
Persn
WeGuting
Weating
1ntt
Hlst
Motivating example: Predicate classification in scene graphs. The Neuro-Solver predicts a set of triples between the given objects. The Mask-Prediccue identifies the components that poten- tially violate domain rules (e.g. the predicate in front is not symmetric and the object jacket is not in the range of the predicate riding). Finally, the Symbolic-Solver corrects the predictions.
Figure 2:
in the form of an image I E X. X is defined as [0, 1| 1|222x252 and corresponds to the set of the images of a Sudoku board (each Sudoku cell has dimension 28 x 28). y is defined as (1.....9) 9]81 and corresponds digits. Z is defined as {0, 1) 1881 y" is defined as (0....99) 9)81
the set of symbolic solutions where each cell is one of the possible 9 Sudoku and corresponds to the set of symbolic solutions with the 9 possible Sudoku digits and the digit 0 indicating empty cells. R contains the Sudoku rules: each cell needs to be filled with numbers in (1...., .9), without repeating any num- bers within the row, column or block. These can be formalized in different ways, depending on the Symbolic-Solver choice.
Example 2
Another example application is the the Predicate Classification task (Figure 2 This task consists of predicting the right predicate between a set of objects (given in impul in the form of labeled and localized bounding boxes) in an image. X corresponds
the input images with the set of labeled bounding boxes. This can be vectorized in different ways using appropriate embedding techniques (e.g. see Zellers al. (0188). y is defined as (B {1....,m) x B) and corresponds to the set of solutions. A solution is a set of k. triples with an object pair and a predicate between them (chosen within the set of m possible predicates). B is the space of all possible labeled bounding boxes and is defined as IR x (1.....11 where is the number of possible objects labels. Z is defined as {0, 1 Y is defined as x {0,..... ........, m) x By and corresponds to the set of symbolic solutions Y augmented with the class O indicating the "empty" predicate (to be filled by the Symbolic-Solvery R is an ontology describing the set of object and predicates in the dataset. Some examples are type- rudes constraining the domain and range of the predicates (e.g. the object cat is not in the domain of the predicate riding) or the symmetry/ reflexivity rules (e.g. the predicate in front is not symmetric).
(0,
Pipeline qualities and limitations. This architecture is particularly useful for solving the tasks in which exhaustive (probabilistic) reasoning is not feasible (in most real-word scenarios standard reasoning techniques are scalable) while purely neural architectures are not accurate enough (making mistakes that violates the domain-knowledge constraints/rules). By performing a quick approximate solution, and then focusing the attention of the expensive reasoning engine only on the parts that will benefit from reasoning, we achieve favourable efficiency--ccuraad trade-off.
By adding the symbolic component, we increase the performance at the cost of additional of running time, which will be higher compared to purely neural model. We discuss this trade-off in more details in Section 4.2 Since the attention is done by neural model (aesk-Predictor), there is no guarantee that all of the prediction mistakes will be found. However, some techniques can be used to minimize this risk (see Section 3.2)
Given the modularity of our NASR pipeline, it is possible to substitute each component with al- ternative ones. We will see an example of this in Section 4 where we integrate the SatNet method (Wang et al. (2019) in our pipeline and significantly improve its performance. For the same reason, our pipeline works independently of the input type, that can be imagery, text, symbolic, etc.
'The Hadamard product is intended between the predicate vector p E (l...., m²} part of a solution y E (B (1,..., m, B and the mask vector m {0. 13 since bounding boxes/lahels given in input.
4

---

Published as a conference paper at ICLR 2023
2.1 LEARNING PARADIGM
Learning is done in two steps: the Neuro-Solver and the Mask-Predictor are first pre-trained individ- ually in a supervised fashion and then integrated together and refined using reinforcement learning (RI.. We refer to our complete pipeline as NASR, and disambiguate ablations where appropriate.
Supervised Learning. To train the Neuro-Solver we use the task dataset D = {x², y') Vi== (also used for the whole pipeline). For training the Mask-Predictor generate synthetic dataset Dmp where: yn is a symbolic solution instance with the addition of noise that violates the Somainnknnowlede
{yh m') Ji=1 )
constraints; and m is the corresponding masking solution. A masking vector m has the same dimension of the input yn and has on the components of yn that do not violate the rules R. and 0 for the components in which noise has been introduced.
The generation of Dmp can be done in different ways depending on the type of data we are consid- ering: 1) the input data yn. can be either generated by perturbing the y in D or 2) it can be generated synthetically following a uniform distribution over the possible y; D. In the former option, each data point Y/ E Dmp has a corresponding data point modified. The corresponding masking vector m will have a 1 on the components of yo that has not been modified and 0 for the components in which noise has been introduced. In general, the latter option is not always possible: for example, in the case of the visual Sudoku task (see Example [ this would require the ability to sample minima symbolic Sudoku boards uniformly random, which is still non-trivial open problem.
D of which some components have been
Symbolic Solver. The Synbolic-Solver will reason about the subset of outputs identified by the Mask-Predictor. The choice of the Symbolic Solver is strongly connected to the type of con- straints/rules: For logic based constraints, classical symbolic reasoners can be used, such Pro- log engines (e.g. SWI-Prolog (swi), probabilistic logic engines (c.g. ProbLog, Raedt et al 2007). python libraries that mimic symbolic reasoning engines (e.g. PySwip. Tekol & contributor 2020). theorem provers (e.g. Vampire prover Riazanov & Voronkovp002), etc.; For arithmetic constraints, constraints-solvee can be used (e.g. ILP or MILP solvers), general mathematical tools (e.g. Mathe- matica mat) or ad-hoe brute force algorithms that exhaustively explore the symbolic solution search space. In this work we mostly consider logic rules and ontologies.
Reinforcement Learning. While the Neuro-Solver and Mask-Predictor can be trained indepen- dently with supervised learning, the use of reinforcement learning is necessary for end-to-end learning (since the Symbolic-Solver is not differentiable). End-to-end learning is important so that the neural components can adapt to the expected interventions of the Symbolic-Solver this work use the REINFORCE algorithm Williams (1992), with its standard policy loss: [(x; = -r log Pa (m))s(z)) where r indicates the RL reward obtained when applying the Symbolic-Solver on the prediction ns(x)) masked by m (for the Visual Sudoku case, see eq. 4 However, it is possible to use an alternative reinforcement learning algorithms without changing the overall pipeline.
In
3 EXPERIMENTS SETUP
3.1 VISUAL SUDOKU DATASETS
We considered total of four Sudoku datasets, summarised in Table]] Three were drawn from an online repository onling 1) big ,kaggle contains 100'000 puzzles. is a subset of a bigger dataset containing 1 million boards hosted on Kaggld targeting ML models. These puzzles have average of 33.82 hints per board (berween 29 and 37); 2) minimal /7 is a complete or nearly-complete d of minimal Sudoku boards, with only 17-clues (17 is the minimum number of hints in Sudoku board leading to unique solution); and 3) multiple_se sol containing 10' 000 puzzles with two or more solutions. We converted these symbolic datasets into images using MNIST digits LeCun
Kaggleftargeting
In minimal Sudoku boards, hints cannot be removed without losing uniqueness of the solution.
/schoo1 .mt.tsthh..mmm.... uwa.
edu. wwt.a///grrdmmm/kkkm.....m

---

Published as a conference paper at ICLR 2023
dataset
# hints [min max]
size
# of solutions
challenge
hig_ kaggle
33.82 [29-37]
1000000
unique
scaling
minimal_17
17.00 [17-17]
50'000
unique
minimal number of hints multiple solutions
multiple.sue
34.75 [34-35]
10'000
multiple
sarnet data
36.22 [31-42]
107000
unique
Table 1: Sudoku datasets statistics.
& Cortes (010)) 4) Finally, we considered the dataset released with SatNet(Wang et al. (019) (denoted as safnel sata). This dataset contains 100000 Sudoku boards (both in image and symbolic form) with an average number of hints equal to 36.22 (minimum 31 and maximum 42).
We generated the Dmp datasets for the Mask- by introducing noise in the task instances in D: for each board y in the original dataset we generated a noisy board yn adding noise both in the the hint cells (swapping some of the hints digits) as well in the solution cells (swapping some of solution cells). We perturbed these two sets separately. For smaller datasets (e.g. satnet _data and multiple-soff we generated multiple masking boards per original board: for each board y the D we generated k- = 10 noisy board V. Un: ....
3.2 IMPLEMENTATION DETAILS AND COMPETITORS
The Neuro-Solver is the first component of the pipeline and has the role of producing a full symbolic solution from a input image board. It takes in input an image x; E X' and output probability distribution over the set of possible complete Sudoku solution boards y = (1..... 9))1. In our implementation we divided this module in two sub-components: the Perception and the SolverNN.
The Perception model parses an input image of 252 x 252 into its symbolic representation of 9 x 9 (9 1). In our implementation the Perception is a straightforward extension of the convo- lutional neural network (CNN) for single MNIST digit prediction LeCun et al. (999) to multi-digit prediction by applying the CNN to each patch of 28 28. Formally, the Perception has an output layer of 81 nodes returning 10-dimensional (the 9 input hints digits and the class 0 for the empty cells) posterior distribution over the digits 0- 9 for each input image x; E X = [0. 1 2 of an incomplete Sudoku board. The output is then probability distribution over )" = {0. ....... 9)81 Each MNIST digit of the input image (corresponding to a single cell) is classified by the CNN inde- pendently The Perception model is trained to minimize the negative log likelihood loss (with log softmax as output layer), and is optimized via the ADADELTA optimizer.
The SolverNN model takes input probability distribution over )" (O..... 9988 the set of partially filled Sudoku boards and outputs a probabilistic solution belonging to the space In our implementation SolverNN is Transformer model with linear layer
Y' (1,... 9 9)81 mapping the input distribution (which is the output of the Perception) to 81 tokens/nodes of length 196, followed by 4 sequential self-attention blocks on top of these tokens; the input is positionally encoded to preserve the spatial information presented in the 9 x 9 Sudoku board (e.g the concepts of row, column, and 3 x block). The output of the SolverNN a probability distribution over the possible complete solutions y (1..... 99.1; 81 output nodes returning 9- 9-dimensional posterior distribution over the digits 1 Entropy with logits loss, and is optimized via Adam optimizer with weight decay.
The SolverNN model is trained minimize the Binary Cross
a Transformer, with the same architecture and training loss as the SolverNN, with the only difference on the dimension of the output layer (1 (l-dimensional). The Mask-Predictor takes in input a probability distribution over the set of complete solutions y = (1....,9) 9]81, the output of the SolverNN model (81 nodes returning 9-dimensional posterior distribution over the digits - 9, that can also be the one-hot representation of completely filled Sudoku boards when trained alone and not in the pipeline) and outputs probability distribution over Z = {0, 1)81. For the Wask-Predictor we add more weight to negative examples in the loss, since it is preferred to mask more cells, at the cost of masking correct ones, rather than non masking some of the errors in
The
Note that the digits treated independently just for simplicity and that the image can he processed in its entirety without significantly changes to the overall pipeline.

---

Published as a conference paper at ICLR 2023
the SolverNN predictions. This is because, given that we are considering non-probabilistic logic solver, a single error in the Symbolic-Sole Sollerr input will make it fail.
The Symbolic-Solver takes in imput masked solution vector (the element-wise product of the output of the Neuro-Solver and the output of the Mask-Predictor) which is a partially filled 81- dimensional symbolic vector. The Symbolic-Solver will then attempt solve it using the rules R providing a full symbolic solution vector as output. We considered two (non- tnon-probabiilittiq) Symbolic-Solvers 1) PySwip, a Python library to interface with SWI-Prolog, reasoning engine for the Prolog programming language; 2) a brute force backtrack-basse algorithm. Since we use a non-probabilistic Symbolic-reasone
our hypothesis function corresponds to eq. w an additional argmaz (since we cannot provide the full probability distribution over the classes, but only the most probable value for each cell):
fz) = sb( arg max(ns(z)) @ arg max(mp(ns(z)) In the case in which an unsatisfiable neural prediction is given in input to the Symbolic-Solver, no solution is generated an thus the whole board is counted as wrong.
R)
(2)
Learning Algorithm (and RL). As mentioned in Section 2 we first train the models in fully supervised manner (details above) and then use reinforcement learning to refine the pipeline end- to-end. We define the RI. scenario as follows: The input state y/ corresponds to a solution board provided by the Neuro-Solver (Perception+Solverll) all possible complete masking boards configurations Z {0, 1181, Each action m coincides with the simultaneous execution of 81 independent sub-actions corresponding to the decision of masking or not a single cell in the solution board y/-- For each Sudoku board we sample an action m E Z following the policy distribution. The final state yt+1 corresponds to the solution board provided as output by the Symbolic-Solvy corresponds to the application of the masking over the solution board provided by the Neuro-Solver followed by the deterministic application of the Symbolic-Solver to the masked solution board.
The action space corresponds to the set of
(with input R and y/ = arg max(y)) @ m). The action we perform
We use REINFORCE (Williams 1992), with its standard policy loss. For each batch B, we have:
L(B:0) = Σ rlg Po (o(m)s(())) = - Σ ZEB
log Po(m)))s(=:))
B
S=0
We use only positive rewards. Given an output board b' and its ground truth board b, we consider two types of rewards with two different order of magnitude: the main reward, re E (0, 10), when the entire board is correct and marginal reward ro [0, 1] for each correct cell i.
81
re + 10-10-000 8y,0 + 81 im0
(4)
We normalize the rewards to improve training stability, since each board difficulty can vary.
Baselines. We compare NASR with different baselines. As Symbolic Baseline we considered the execution of the Symbolic-Solver directly from the output the Perception module (after applying the arg max operator). Another possibility would be adapting the prediction-correcionn part of the pipeline in the work Giunchigla et al. (2022a). Using a probabilistic reasoning engine and using the whole (or partial, c.g. the top l candidates output distribution of the Perception module as neuro-symbolic
input, is computationally unfcasible. We also compared with two statc-of-the-as methods: SatNer Wang et al.] (2019), differentiable MAXSAT solver that can be integrated into neural networks; and NeurASP Yang et al. (2020), an extension of answer set programs (ASPs) that consider a neural network output as the probability distribution over atomic facts in ASPs.
4 RESULTS
The main results can be summarized as follows: 1) we outperform the baseline in most of the cases (and never perform worst); 2) we improve the performance of an existing method, by integrating in our pipeline; 3) we are more efficient, compared to the other methods, in terms computational time vs. performance; and 4) our method more robust to noise compared to the symbolic baseline.
A prohabilistic Symbolic-Solveris is unfeasible in this scenario due to the combinatorial nature of the possi- ble Sudoku boards.
7

---

Published as a conference paper at ICLR 2023
big kaggle
minimal,17
multiple_sol*
satnet_data
Symbolic Baseline
74.56
87.70
63,50
63.20
SatNet (Wang et al. 2019 SatNet (Wang et
63.44
0.00
0.00
60.10
NASR
69.05
0.02
24.20
81.40
NeurASPT Yang et a. 2020
timcout
189.00
timeout
timeout
Our NASR
84.24
$7.00
73.00
82.20
Table 2: Results for the visual Sudoku task: percentage completely correct solution boards. The multiple_so dataset likely due to
best results are in bold font. *The pipeline is underperforming the fact that each input board admits more than one solution but only one is provided at training. itested only 200 of the 5000 test images due to the long run-time (days).
big kaggle
minimal 17
multiple sol
salnet data
Perception SolverNN Mask-Predictor
99.64
74.56
99.84
87.70
99.48
65.70
99.32
63
100-98.33
62.68
100-61.56
0.00
100-93.72
46.70
100-94.84
24.00
99.92-99.71
99.54-35.26
99.02-76.12
99.90-96.06
Neurn-Solver
47.03
0.00
28.80
14.40
NASR w/o RL NASR with RL
80.02
1.59
60.00
76.40
84.24
87.00
73.00
82.20
NauR-Heur.Mask
73.11
66.99
55.60
42.80
Table 3: Results of our pipeline on the visual Sudoku datasets, divided by the different modules. The metric used in the right column for each dataset correspond to the percentage of completely correct predicted boards. In addition that we report (in the left column of each dataset): for the Perception the number of correctly predicted cells on average; for the SolverNN preservation of input cells- correctness of solutions cells, for the Mask-Predictor true negative true positive (that corresponds to correct solution cells that are not masked error solution cells that are masked).
4.1 OVERALL PERFORMANCE
In Table 2 we report the performance of our pipeline (with RL) on the different datasets compared with the different baselines. We can see that outperform all the neuro-symbolie methods and in one instance match the Symbolic Baseline (which we outperform in all the other datasets). Note that symbolic baseline fails if even one digit incorrectly recognised, and thus it is not noise robust. NASR can be integrated with SatNet (Wang et al.) 2019) by replacing our Neuro-Solver with SatNet. The results (SatNet NASR) show that the soft constraints enforced by SatNet can be improved, sometimes substantially by injection of hard constraints via NASR
In Table we report the performance of our pipeline analyzing each module separately. We that for more challenging datasets (c.g. minimal_17 with only 17 hints minimal Sudoku boards and multiple_so with multiple solutions) the performance of the Neuro-Solver is very low. In particular, for the minimal 17 dataset this is even more evident, since the SolverNN cannot produce any com- pletely correct solution board (only 60% of the solution cells is correct on average per board) and the Mask-Predictee identifies only 30% of the errors. RL is necessary to refine all the parts together.
Comparing Table 2 and Table B we observe that, as expected, the performance of the Symbolic Baseline corresponds to the performance (in terms of percentage of completely correct converted boards) of the Perception module. This is because, given the use of non-probabillittcc logic solver, single perception error will make the Symbolic-Solle Soller fail. The Symbolic bascline is thus not noise robust and finds datasets with more than the minimal number of hints harder to solve. Section A.2 systematically analyses the greater noise robustness of our framework the symbolic baseline.
We performed an ablation study to verify the impact of the simple heuristic. We masked Neuro- Solver outputs the basis of confidence, with threshold set by grid search and Bayesian optimization (Akiba et al. (219)). The results Table 2 show that while this can perform well (e.g. in big kaggle) it is significantly
by substituting it with a
compared to our pipeline.
8

---

Published as a conference paper at ICLR 2023
NASR with RI.
Performance
NASR RL
Performance
baselinee
NaSR
SalDec
0.2
NASI with ILL NASH
Time
-10m2
(a) Pareto front (purple line) maximizing the perfor- mance (percentage completely correct boards) and minimizing the computational time. The optimization objective is located on the top left corner of the plot.
Performance analysis for when limiting the putational time the pipeline. The metric the per- centage of completely correct boards, while increasing the timeout limit.
Figure 3: Time efficiency analysis for buggle dataset.
(a) SolverNN Cell (1.1) (b) SolverNN Cell (5,4) (c) Mask-Preer Baes. Cell (1,1) (d) Mask Pred. Cell (8.8)
Figure 4: Attention maps for the SolverNN on big kaggle and for the Mask-Predicton minimal J7.
4.2 FURTHER ANALYSIS AND CONCLUSIONS
Time efficiency. Our system is faster than the symbolic baseline (Perception+-Smmoolic Solver). This is because our Symbolic Solver needs to fill less empty cells and thus its search space is reduced. In Figure we analyse the efficiency in terms of trade-off between the performance (percentage of completely predicted Sudoku boards), and computational time for the big kaggle dataset (see Supplementary Material for other datasets). Figure 3a shows the Parcto front considering the two optimization objectives of minimal computational time and maximal performance. Our method, is always on the Pareto front and usually the closest to the optimization objective (top left corner of the plot). Figure Bg) compares the performance of each system when limiting the computation time by different timeout values. We can see that with small timeout limits the neural models behave time.
better compared the Symbolic-Basellin which requires
Attention Maps. To better understand the Neuro-Solver and frek--rreiittor networks, we analyse their attention maps for evidence of learning the rules of Sudoku. Figure shows the average of all the attention layers for the SolverNN and for the Mask Pask-Predicctor on the big kaggle and minimal I7 dataset respectively. We can see that for each cell, both the SolverNN and the consider the information in the row, the column and the 3 x 3 block, which corresponds to the Sudoku rules. The results are clearer for SolverNN on big kaggle dataset compared to the Mask- Predictor minimal_17 dataset due to the dataset size.
Preliminary Results on Scene Graph. We performed a preliminary study for Predicate Classifi cation (see Example 2 for the GQA dataset (Hudson & Manning (2019)) using simple ontology containing only domain/range information for the predicates. The results are consistent with the Sudoku scenario (more information can be found in the Appendix A.8).
Conclusions. We presented a neuro-symbolic method that aims to efficiently satisfy domain- knowledge constraints at inference. This enables favourable trade-off between accurate predic- tions, noise robustness, and computation cost. Our framework generic and can applied to different types of input (image, text, symbols, etc.) and types of constraints (logic, arithmetic, etc.).

---

Published as a conference paper at ICLR 2023
REFERENCES
Wolfram Mathematica. http://www.woffrmm.cm Version: 12.
SWI-prolog. https//wwww.swiipoooggoggg Version: 8.3.3.
Ananye Agarwal, P. Shenoy, and Mausam. End-to-end neuro-symbolic architecture for image-to- image reasoning tasks. ArXiv, abs/2106.03121, 2021.
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck. and Antonio Vergari, Seman- tic probabilistic layers for neuro-symbolic learning. In NeurlPS, 2022.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama, Optuna: next-generation hyperparameter optimization framework. In Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Dhananjay Ashok, Joseph Scott, Sebastian J. Wetzel, Maysum Panju, and Vijay Ganesh. Logic guided genetic algorithms (student abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Grady Booch, Francesco Fabiano, Lior Horesh, Kiran Kate, Jonathan Lenchner, Nick Linck, An- dreas Loreggia, Keerthiram Murgesan, Nicholas Mattei, Francesca Rossi, and Biplav Srivastava. Thinking fast and slow in ai. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Celine Brouard, de Givry Simon, and Schiex Thomas. Pushing data into ep models using graphical model learning and solving. In International Conference on Principles and Practice of Constraint Programming. Springer International Publishing, 2020.
Alessandro Daniele and Luciano Serafini. Knowledge enhanced neural networks. In PRICAI 2019;
Trends in Artificial Intelligence, 2019.
Tirtharaj Dash, Sharad Chitlangia, Aditya Abuja, and Ashwin Srinivasan. A review of some tech- niques for inclusion of domain-knowledge into deep neural networks. Scientific Reports, 12(1), 2022.
Ivan Donadello and Luciano Serafini. Compensating supervision incompleteness with prior knowl- edge in semantic image interpretation. IJCNN, 2019.
Leilei Gan, Kun Kuang, Yi Yang, and Fei Wu. Judgment prediction via injecting legal knowledge into neural networks. Proceedings of the AAAI Conference Artificial Intelligence, (14), 2021.
Elconora Giunchiglia and Thomas Lukasiewicz. Multi-label classification neural networks with hard logical constraints. Journal of Artificial Inteliience Research, 72:759-818 -188, November 2021.
Eleonora Giunchiglia, Mihaela Stoian, Salman Khan, Fabio Cuzzolin, and Thomas Lukasiewicz. Road-r: The autonomous driving dataset with logical requirements. In Machine Learning, 2022a.
Eleonora Giunchiglia, Mihaela Catalina Stoian, and Thomas Lukasiewicz. Deep learning with log- ical constraints. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, 2022b. Survey Track.
Drew Hudson and Christopher Manning. GQA: A new dataset for real-world visual reasoning and compositional question answering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, New York, 2011.
Boris Knyazev, Harm de Vries, Catalina Cangea, Graham Taylor, Aaron C. Courville, and Eu- gene Belilovsky. Graph density-aware losses for novel compositions in scene graph generation. In BMYC, 2020.
Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li. David A Shamma, Michael Bernstein, and Li Fei-Fei. Vi- sual genome: Connecting language and vision using crowdsourced dense image annotations. In International Journal of Computer Vision, 2016.
10

---

Published as a conference paper at ICLR 2023
Yann LeCun. A path towards autonomous machine intelligence. 2022.
URL
https://
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL htthhttpp/yaan
lecun wwwpw/cb//m/mmtttteceeccommm/eet
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, volume 86, pp. 2278-2324 1998.
Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
Tao Li, Vivek Gupta, Maitrey Mehta, and Vivek Srikumar. A logic-driven framework for consistency of neural models. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2019.
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In Advances in Neural Information Pro- cessing Systems, 2018.
Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, and Marco Gori. Constraint-based visual generation. In ICANN, 2019.
Pasquale Minervini and Sebastian Riedel. Adversarially regularising neural nli models to integrate logical background knowledge. In Proceedings the 22nd Conference on Computational Natural Language Learning (CoNLL 2018), 2018.
Maxime Mulamba, Jayanta Mandi, Rocsildes Canoy, and Tias Guns. Hybrid classification and reasoning for image-based constraint solving. International Conference on Integration of Con- straint Programming, Artificial Intelligence, and Operations Research (CPAIOR-20). 2020.
Lue De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: probabilistic prolog and its
application in link discovery. In IJCAI, 2007.
Alexandre Riazanov and Andrei Voronkov. The design and implementation of VAMPIRE. AI communications, 15(2, 31:91-110, 2002.
Mrinmaya Sachan, Kumar Avinava Dubey, Tom M Mitchell, Dan Roth, and Eric Xing. Learning pipelines with limited data and domain knowledge: A study in parsing physics problems. In Advances in Neural Information Processing Systems, 2018.
Steven A. Sloman. The empirical case for two systems of reasoning. In Psychological Bulletin, volume 119(1), pp. 3-22, 1996.
Yüce Tekol and contributors. PySwip v0.2.10, 2020. URL pyswip
Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael. Neural-symbolic integration: A compositional perspective. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Laura von Rueden, Sebastian Mayer, Katharina Beckh, Bogdan Georgiev, Sven Giesselbach, Raoul Heese, Birgit Kirsch, Julius Pirommer, Annika Pick, Rajkumar Ramamurthy, Michal Walczak, Jochen Garcke, Christian Bauckhage, and Jannis Schuecker. Informed machine learning tax- onomy and survey of integrating prior knowledge into learning systems. IEEE Transactions on Knowledge and Data Engineering. 2021.
Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In ICML, 2019.
Wenya Wang and Sinno Jialin Pan. Integrating deep learning with logic fusion for information extraction. Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Ronald Williams. Simple statistical ceudient-followigg algorithms for connectionist reinforcement learning. Mach. Learn., 8(3 8(3-4):229-23 may 1992.

---

Published as a conference paper at ICLR 2023
Yaqi Xie, Ziwei Xu, Mohan S Kankanhalli, Kuldeep S Meel, and Harold Soh. Embedding symbolic knowledge into deep networks. In Advances in Neural Information Processing Systems, 2019.
Danfei Xu, Yuke Zhu, Christopher Choy, and Li Fei-Fei. Scene graph generation by iterative mes-
sage passing. In Computer Vision and Puttern Recognition (CVPR), 2017.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference on Machine Learning, 2018.
Zhun Yang, Adam Ishay, and Joohyung Lec. NeurASP: Embracing neural networks into answer set programming. In IJCAI, 2020.
Bai Yiwei, Di Chen, and Carla Gomes. Clr-drets: Curriculum learning with restarts solve visual combinatorial games. In 27th International Conference on Principles and Practice of Constraint Programming (CP-21), 2021.
Ruichi Yu, Ang Li, Vlad I. Morariu, and Larry S. Davis. Visual relationship detection with ternal and external linguistic knowledge distillation. In 2017 IEEE International Conference Computer Vision (ICCV), 2017.
Rowan Zellers, Mark Yatskar, Sam Thomson, and Yejin Choi. Neural motifs: Scene graph parsing with global context. In Conference on Computer Vision and Pattern Recognition, 2018.
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 TRAINING CONVERGENCE
In Figure we provide the lerning curves for the reinforcement learning training on minimal 17 dataset. In particular we can see in Figure 56 how the average reward on the training set improves only few (~~ 30) iterations.
10
yod 104 Molayan
train reward
-50
-100
2
100
125
50
100
150
175
(a) Loss.
(b) Reward.
Figure 5: Reinforcement learning curves for refining with RI our pipeline on the minimal 17 dataset.
Using bigger models can further improve the overall performance. For example, using a transformer with 12 attention modules (instead of 4) on the big kaggle substantially improves the Neuro-Solver, achieving a boost of ~ 30% completely correct boards. This improvement is less evident considering the whole pipeline, gaining only 5% improvement compared to smaller models.
A.2 ADDITIONAL ANALYSIS: NOISE ROBUSTNESS
Our pipeline is more robust to noise: in Figure 6 we can see the drop in performance of the baseline and our method adding two different type noise in the input images at inference time. Figure 6b shows the results when adding Gaussian blur to the images, while Figure when rotating the digits with a random angle in [-45, 45). We can see that our pipeline has a smaller and slower drop in performance compared the symbolic baseline") These results pipeline using RI. We can see that with a high amount of noise the performance gap with the Symbolic-Solver is smaller (e.g. with rotation between [-40, 40] degrees, our pipeline refined with RL solves 20.33 20.3% more boards compared to the Symbolic-Solvert while for a medium amount is higher (e.g. with rotation between [-25, 25) degrees our pipeline refined with RL solves 32.2% more boards compared to the Symbolic-Solven difference between the pipeline with or without RL probably due the fact that, the latter, the Mask-Predictos is trained on simulated noise while in the former the Mask-Predicton is refined on the actual noise produced by the Ncuro-Solver. Thus, when adding a new and unseen type noise the latter is expected to behave better.
less evident in the refined
of noise the gap with the Symbolic-Solee
The
A.3 ADDITIONAL RESULTS: EFFICIENCY.
As mentioned Section 4.2 we can see that we obtain similar efficiency results for the remaining datasets: minimal_17 (Figure multiple_sol (Figure R); and satnet_data (Figure 9)
Note that these experiments are done training the Mask-Predictor with an expected amount of noise be- tween 0% and 10%. The Mask-Predictor he retrained and optimized for the specifie amount of noise expected input, leading better performance.
13

---

Published as a conference paper at ICLR 2023
100
hundiiz
senri basliie NASK
J
80
Performance
60
20
61-02
0243
0.42
8445
0n47
0742
10.2
1..2
Noise test time: digit rotation.
(h) Noise time: Gaussian blur.
Figure 6: Performance of the Symbolic Baseline compared to our two pipelines (with or without RI. when adding noise on the dataset multiple sol test time. Similar results hold for the other datasets.
symb. leaelin:
symb. baselin
NASR RL
Performance
Performance
0.6
0.4
0.4
0.2
NASR
NASR w/o RL
salnel
0.1
Time (s)
Timeout values
(a) Pareto front (purple line) for the minimal_17 dataset
(b) Performance analysis for the minimal_17 // dataset
maximizing the performance (percentage of com-
when limiting the computational time of the pipeline.
pletely correct boards) and minimizing the computa-
The metric is the percentage completely correct
tional time. The optimization objective is located on
boards, while increasing the timeout limit.
the top left corner of the plot.
Figure 7: Time efficiency plots minimal 17 dataset.
14

---

Published as a conference paper at ICLR 2023
synbolic beseline
NASR w/o RL
NASR with RL
NASR w/o RL
Performance
Performance
0.6
symb buseline
0.4
0.4
salnet+NASR
0.2
satnet
2.5
Time (8)
Timeout values
(a) Pareto front (purple line) for the multiple_sol dataset maximizing the performance (percentage of
(b) Performance analysis for the multiple soo dataset
when limiting the computational time of the pipeline.
completely correct boards) and minimizing the com- putational time. The optimization objective is located the top left corner of the plot.
The metric is the percentage completely correct
boards, while increasing the timeout limit.
Figure Time efficiency plots multiple sol dataset.
0.9
NASR with RL
0.8
Performance
0.8
Performance
SalRet+NASR
0.7
NASR w/o RT.
sycab. baseline
Safnet
saunet
0.6
0.2
NASR wio RL
symb.haslline
satnrl-NASR
0.5
0.2
0.4
0.6
1.2
1.4
Time
-10
Timeout values
(a) Pareto front (purple line) for the satnet data dataset maximizing the performance (percentage of com-
(b) Performance analysis for the samer satner_data dataset
when limiting the computational time of the pipeline.
pletely correct boards) and minimizing computa-
percentage completely correct boards, while increasing the timcout limit.
The metric
tional time. The optimization objective is located on
the top left corner of the plot.
Figure 9: Time efficiency plots sateet data dataset.
15

---

Published as a conference paper at ICLR 2023
A.4 ADDITIONAL RESULTS: ATTENTION MAPS.
Additional plots for the attention maps considering more cells are shown in Figure T0
We remark that the attention maps depend the dataset. In particular, if dataset contains some bias (e.g. multiple_sol from how it has been generated, the networks will try to exploit the biases (e.g. learning relaxed version of the rules R. some simpler heuristic) instead of learning the proper Sudoku rules.
(a) SolverNN Cell (1.1)
(b) SolverNN Cell (5,4)
(c) SolverNN Cell (8.8)
(d) Mask-Predictor- Cell (1,1)
(c) Mask-Predictor Cell (5,4)
(f) Mask-Predictor- Cell (8,8)
Figure 10: Attention maps for the SolverNN on big saggle and for the Mask-Predictor on mini- mal 17.
16

---

Published as a conference paper at ICLR 2023
7
/2 2
7 8
7
3
4
7804 126
78
4 9
5
9
6
/
6
5
9
6 6
6 6
6
7 8
Neuro-Solver
4
9
5
8
8 Pr
4 2 2
5
50
7
4
2
9 5
7574430
4
5 7575438 6
9
3
299
8
3
29 2 5
934 6 8
26/7 76/75820
4
93
1
G
8
9 93 4 6
85
8
5
4
E 7
8
3 O
4
5 8 14
4
T
8
T
4
3 6
9
7
3
2
7
5
Figure 11: Pipeline example for the visual Sudoku task. The Neuro-Solvee outputs complete board. The Mask-Predictor identifies the cells that violate the Sudoku rules (in the first block there are two cells with value 7). Finally, the Symbolie-oolver corrects the predictions.
A.5 SUDOKU RULES FORMULATION FOR PYSWIP
In what follows we provide the rules used in pyswip (Tekol & contributors 2020) for finding symbolic solution for partially filled Sudoku board Tu The masked cells are provided as "." symbol. The query corresponds to the example shown in Figure and Figure
Sudoku rules
use_module e (1 (b
sudoku (Rows)
append (Rows, Vsl, Vs ins 1..9, length (Rows, 9), maplist (same length (Rows), Rows),
(al__disinnt Rows),
transpose (Rows, Columns), maplist (all_ditinnn, Columns), Rows [As, Bs, Cs, Ds, Gs, Hs, Is], blocks (As, Bs, Cs), blocks (Ds, Es, Fs), blocks (Gs, Hs, Is), label (Vs). $ default strategy min (follows order in Vs 1..9)
blocks([] [], [])
blocks ([N1, N3, N6 [N7, N8, N9 N933)31) all_distinct [N1, N2, N3, N5, N6, N7, N8, N9]), blocks (Nsl, Ns2, Ns3).
query Rows
4,,,8,..,339,,,,,,
16,1,2,,,,,5,3,4.911
(4,9,3,,,2,,,5,_888
18,5,7,9,443/22,,111
12,,,,,,,
[9,3,4,1,6,2,7,8,5]
9,
2, 6,
13, 4, 9, 2,4,,,2,1,,,,
sudcku (Rows).
10This is standard implementation of Sudoku rules, and it is modified version of the one at https: 7/swi sh. swi pori-proloo ogg http pfd-sudokkdou sudoku
17

---

Published as a conference paper at ICLR 2023
A.6 TRAINING TIMES
In Table we report the training times for the different methods. The training time of the Symbolic Baseline corresponds to the training time of the Perception, since it needs the Perception output as input of the Symbolic-Solver. The training time for NASR is the sum of perception, SolverNN, Pred-Prre and optionally RL. The first three of these can trivially be parallelised. We trained the transformer models for 200 epochs, while the Perception models for 100 epochs. RL refinement trained for 20 epochs. For SatNet and NeurASP we used the default configuration (100 epochs for both models). NeurASP-Infer uses our pretrained Perception to convert the image to symbolic form, while NeurASP uses their own CNN.
big kaggle
minimal_17
multiple_sol
satnet_data
Perception SolverNN
108.84
57.71
11.68
14.14
85.58
41.97
9.01
26.51
Mask-Predices
81.43
40.15
8.87
128.98
RL
121.07
241.31
24.86
16.44
NASR w/o RL
275.85 (108 84)
139.83 57.71)
29.56 (11.68)
169.63 (128.98)
NASR with RL
396.92 (229.91)
381.14
(299.02)
54.42 (36.54)
186.07
(145.42)
Symb. Baseline
108.84
$7.71
11.68
14.14 14
SatNet
1151.25
582.13
41.66
108.51
NaurASP-Infer
108.84
57.71
11.68
14.14
NeurASP
94.34
91.53
99.96
90
Table 4: Training times (minutes) of the different systems for the visual Sudoku task. For NASR we report the training time when training the different models sequentially and in brackets the training time when training the Perception, SolverNN and Mask-Predices modules in parallel.
A.7 ANALYSIS ON THE DIFFERENT ROLES OF NASR MODULES IN ERROR CORRECTION
In Table 5 we report the results of two experiments that help to understand how the different com- ponents NASR interact with each other for the Visual Sudoku task.
In the first experiment we look at the input (hints) cells that have been incorrectly predicted by the Perception but have been corrected by NASR (2nd and 3rd column). The goal of this experiment to see the proportion, of this type of errors, that are corrected directly by the SolverNN or thanks to the Mask-Predices We can observe that Perception errors are almost all corrected by SolverNN, while only small portion remain to be identified by the
The second experiment (4th and 5th column) aims to understand the between the errors in the input cells (the original hints) and the errors in the solutions cells. We can see that the percentage errors identified in the hint cells (4th column) and in the solution cells (5th column) has distinctive pattern. We conclude that the mask-Predictor does not systematically prefer either of the two. It corrects both types of errors.
distinguishes
Perception errors corrected by NASR w/o RL
SolverNN errors identified by
identified by identified by
Mask-Predicht
SolverNN
hint cells
solutions cells
big kaggle
85,90
14.10
53.17
77.42
minimal_17
95.90
4.10
8.21
32.24
multiple_sol
87.21
12.79
42.09
24.73
satnet_data 85.43
14.57
44.76
71.16
Table 5: Statistics the interplay of the different component of the NASR pipeline in the case of Visual Sudoku task in regard to error correction. All the results corresponds to percentages. The reported results refer NASR without RL. Similar results hold for NASR with RL.
18

---

Published as a conference paper at ICLR 2023
A.8 PRELIMINARY RESULTS ON SCENEGRAPH
We evaluate NASR w/o RL the task of predicate classification (PredCIs). Recall that the task consists in providing the right predicate label given the ground truth object labels and bounding boxes.
A.8.1 DATASET AND BASELINE
We consider the GQA dataset introduced by Hudson & Manning (2019). GQA is a more balanced split of Visual Genome (VG) dataset (Krishna et al.) (2066) with cleaner, larger, and more dense scene graphs and with a larger and more balanced variety of objects and predicates (for more details see Hudson & Manning (019)). It contains 22M pairs of question/answer for real-world visual reasoning and the corresponding scene graphs. We are interested in the latter.
In the GQA dataset there are 311 predicates and 1705 classes for the subject/object element of triple. Statistics of the train/val main/val/test split that we used are provided in table The ZeroShot versions of the validation and test set contains only triples that has not been observed during training.
# images
triples
# unique triples
train
66078
3455468
470129
val shots)
4903
306494
89411
test (all - shots)
10055
530326
147534
val (zero shots)
3025
23371
18638
(zero shots)
6418
45135
37116
Table 6: GQA dataset statistics.
As baseline, we consider the model developed by Knyazev et al. (220) which modified version (that exploits a Censity-normalizer edge loss) of the Message Passing (MP) architecture introduced by Xu et al.) (2017). We adopted the data split and evaluation metries used in their work. For our experiments, we trained their models on the GQA dataset (the code is available at https: 7/github. wtoo//kkyaz//ste /gg)).
A.8.2 IMPLEMENTATION DETAILS
The input and output spaces of the pipeline modules follow what was introduced in Example 2
As Neuro-Solver chose the architecture introduced Knyazev et al. (2020) mentioned above. takes in input an image with the corresponding labels and bounding boxes of the objects and outputs probability distribution over the predicates for each identified triples. For more details about this architecture see the work of Knyazev et al. (202)).
(4-layer) MLP model that embeds predicate classes and object/subject classes differently. It takes in input a probability distribution over the set of predicates (311- dimensional) and the one-hot encoding (700--dimensioal) of subject and object for each triple. The output of the Mask-Predictor is probability distribution over Z = {0. } The number of triples & can vary for every image (they are considered as independent from each other since we are considering a simple domain-range ontology).
The Mask-Predicte
The Mask predictor is trained on a synthetic dataset generated from the domain-range ontology (an ontology containing all the possible domain and range classes for each predicate). We sampled an equal number of triples for each of the following 4 scenarios: triples that do not violate the ontology, triples with both unfeasible domain and unfeasible range, triples with only unfeasible domain and triples with only unfeasible range.
The Symbolic-Solver is simple solver, implemented in python, that takes in input masked lution and finds the next most probable predicate, after excluding the not feasible ones, for a given object/subject pair.
19

---

Published as a conference paper at ICLR 2023
A.8.3 RESULTS
The results considering a simple domain-range ontology are provided in Table using the standard image-level Recall metric and Table using the image-level mRecall metric, introduced by Knyazev al. (2020). Recall consider only the top-1 prediction (predicate) between each pairs of objects, while mRecall allows to rank multiple predictions (predicates) between each pairs of objects.
We report the results for the Baseline (the work of Knyazev et al. (2020)) and the improvement over the Baseline of by the Probabilistic Symbolic Baseline (PSB). PSB consists of running the probabilistic symbolic solver directly on the output of the Baseline model. This computationally very expensive, especially if we consider sightly more dense ontology. With more complex ontology this would became computationally intractable. The improvement given by the PSB the case of PredCI is upper-bound (Max-im (ax-oemprovemnt) for the performance of NASR. The results of NASR w/o RL are reported as percentage of error correction achieved when compared to the PSB upper bound.
The results show that NASR achieves good performance, and is able to recover the majority of the recoverable errors given the simple domain-range ontology used. This leads, for example, to improvement between I 1 and 2% for the zero-shots predictions. Since we are considering a very noticeable as in the Visual Sudoku case. However when
simple ontology, the improvement is using a more complex ontology, we expect this difference to become more pronounced.
R@20
R@50
R@ 100
R@200
R@ 300
All shots
Baseline Knyazev et al.
2020
29.22
42.35
48.48
50.75
51.11
Max-improvement (PSB) % improvement of NASR w/o RI.
0.12
0.23
0.32
0.35
0.36
99.71
99.58
99.69
99.64
99.64
Zero shots
Baseline Knyazev
2020
16.62
27.65
34.10
37.41
38.11
Max-improvement (PSB) % improvement of NASR w/o RL
0.91
1.43
1.93
2.18
2.33
100.00
100.00
100.00
100.00
100.00
Table 7: Results the PredCl task for the GQA dataset. We consider the Recall metric used both for VG and the GQA datasets (see Hudson & Manning (2019) for more details), NASR results are given percentage of the max achievable improvement under the given ontology, defined by PSB.
mR 20
mR@ m0
mR@ 100
mR@ 200
mR 300
shots
Baseline Knyazev et al. (2020)
36.24
60.84
79.08
91.12
94.76
Max-improvente (PSBB
0.18
0.33
0.50
0.51
0.56
% improvement of NASR w/o RL
98.09
91.20
91.16
90.25
87.90
Zero shots
Baseline Knyazev et al. 2020
19.16
37.46
54.64
69.72
76.12
Max-improvement (PSB)
0.08
0.46
0.89
1.93
% improvement of NASR w/o RL
100.00
86.77
93.05
88.99
86.00
Table 8: Results on the PredCI task for the GQA dataset. We consider the mRecall metric introduced for the GQA dataset by Knyazev et al. (2000). NASR results are given as percentage of the max achievable improvement under the given ontology, defined by PSB.
20


Reviews:
[{"review_id": "szmFVms4-bO", "reviewer": "Reviewer_PAJH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel neurosymbolic method that allows an efficient (but potentially error-prone) neural solver to be corrected by a precise (but inefficient) symbolic module. The intervention from the symbolic module is mediated by a learned neural module, allowing the overall system to exploit both the efficiency of the neural solver, and the precision of the symbolic solver only when needed. ", "summary_of_the_review": "The paper proposes an interesting neurosymbolic method that can exploit both the efficiency of a neural reasoning approach together with the precision of a symbolic reasoning approach, mediated by a neural module that learns when to invoke the symbolic module. The method elegantly optimizes the tradeoff between efficiency and precision, and outperforms competing neurosymbolic methods.", "strength_and_weaknesses": "## Strengths\n- The proposed method presents an interesting and elegant way of combining the relative strengths of neural and symbolic reasoning approaches. The use of a learned module to decide when to invoke the symbolic reasoning module is a nice solution that avoids the circular challenge of using a symbolic module to check whether the neural solver is correct, and the approach works surprisingly well (one might have expected that the learned mask-predictor would suffer from the same limitations that the neural solver does in the first place).\n- The method performs well against other neurosymbolic approaches (and against purely neural or purely symbolic approaches) on a challenging visual sudoko task.\n- The model is robust to perceptual noise, and can solve problems in an efficient manner.\n\n## Weaknesses\n- The major weakness is that the approach still requires the use of handcoded, task-specific knowledge, i.e. the rules of sudoku are programmed into the symbolic module, rather than being able to learn the rules or receive the rules in natural language as human reasoners do. However, despite this limitation (which is broadly shared by current neurosymbolic methods, and a major open challenge), the proposed method constitutes an elegant solution to a specific problem in integrating neural and symbolic approaches, and should be a useful contribution to the literature.\n\n### Other notes\n- There is an interesting connection between the proposed approach and the 'two systems' perspective in psychology (e.g. [1] and [2]).\n\n[1] Kahneman, D. (2011). Thinking, fast and slow.\n\n[2] Sloman, S. A. (1996). The empirical case for two systems of reasoning. Psychological bulletin, 119(1), 3. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "GYNC8xBqThZ", "reviewer": "Reviewer_8rGg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors introduce a hybrid neuro-symbolic pipeline, denoted NASR, that combines a fast but inaccurate neural reasoner with an accurate but slow symbolic reasoner.  The two components are combined using a neural module trained to identify mistakes in the output of the neural reasoner, and using the symbolic reasoner to fill in the gaps.  The resulting pipeline is trained using a mixture of supervised learning and reinforcement learning.  Empirical results on four visual sudoku data sets with different characteristics are reported, showing improved accuracy over the neural reasoner at a much lower cost than a fully symbolic solution.", "summary_of_the_review": "Intuitively appealing and promising contribution with flawed empirical evaluation.", "strength_and_weaknesses": "PROS\n- The method is significant in that it targets a known weakness of existing NeSy approaches.\n- The proposed pipeline (and accompanying training procedure) is intuitively appealing.\n- The empirical results on visual sudoku look promising.\n- The text is generally well structured and easy to follow.\n- The related work section is reasonable and gives an overall fair representation of existing approaches.\n\nCONS\n- The evaluation only considers visual sudoku.\n- The results do not report the time required for training the various models.\n- Improvement over the symbolic baseline can be small if the neural method makes many mistakes.\n- Some references are missing.\n- Some aspects of the pipeline are a bit unclear.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CsuYjFVbEA-", "reviewer": "Reviewer_ndKP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new model to enforce hard logical constraints on neural networks. The model proposed, called NASR, has three main components: \n\n1) A neuro-solver: which is made of one (or more) neural networks. It takes as input the datapoints in the dataset and returns an initial prediction (which might contain violations of the constraints), \n\n2) A Mask-predictor: which is a neural-based model that takes as input the initial prediction made by the neuro-solver at returns a mask over such output. The $i$th element of the mask is equal to 1 if the $i$th element needs to be changed in order to satisfy the constraints, and 0 otherwise. \n\n3) A Symbolic Solver: which (as the name says) is a symbolic solver that will correct those elements of the prediction (or facts, as they are called in the paper) which have been identified by the mask-predictior to make the final output compliant with the constraints. ", "summary_of_the_review": "TL;DR: paper could improve a lot if some parts were rewritten and a lot of details clarified. ", "strength_and_weaknesses": "**Strengths:**\n- The paper presents the novel idea of selecting which facts need to be changed in order to make the prediction complaint with the constraints. This effectively reduces the search space for the solver, and it might be a useful intuition for future works.\n- The presented method is intuitively easy to understand. \n\n**Weaknesses:**\n- The paper needs significant rewriting. It lacks a lot of details, and while intuitively is easy to follow, when it comes to the details it becomes a very fuzzy. This is the main problem I have with the paper, which I though think can be solved with some effort. See comments on Clarity below for more details on how to address the issue.\n- The experimental analysis has been done on a single task which limits the understanding on how this model would perform in real-world datasets. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6cTlJfSiAq", "reviewer": "Reviewer_6T4W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors proposes a new framework that tries to combine neural perception and symbolic reasoning.  In general, this framework consists of three components: (1) Neural Solver (NS) (2) Mask Predictor (MP) and (3) Logical Solver (LS).  The NS computes an initial solution for the input tasks, then the MP predicts the incorrect parts of the initial solution and a masked solution (the incorrect parts are masked as 0) is generated. Fianlly, this masked solution is fed into the LS to get the final solution. The NS and MP models are trained with supervised learning firstly. Then the reinforcement learning (RL) is employed to fine-tune the NS and MP models leveraging the LS results. The authors validate their framework on Visual-Sudoku tasks and shows that in most cases, they can perform better than the state-of-the-art methods.", "summary_of_the_review": "The paper proposes a novel neural-symbol framework. Its basic idea is to use neural network to compute an intial answer, and predict the incorrect parts of it then use a logical solver to get the final answer. However, the framework is only validated on a single domain: visual Sudoku. ", "strength_and_weaknesses": "Strength:\n    (1) Use reinforcement learning to combine the perception part and the reasoning part. \n    (2) Predict the incorrect parts of the initial solution to reduce the search space for the logical solver.\n\nWeaknesses:\n    (1) It would be better to show how the framework on another domain, now there is only one single domain: Visual Sudoku. The predicate classification task is really a good one.\n    (2) It would be better to give or show the inituion of why the framewoke works. From the experimental results, the framework works better on SATNET dataset (avg 36 hints) v.s. the 17hints dataset. That's very interesting since from the sudoku perspective, 17 hints is supposed to be much harder than 36 hints. But for here, this can be understand since 36 hints means more images (\"noisy digits\") that the model needs to recongnise. So here comes the question, is the framework learned which digits are classified incorrect or learned something else?\n    (3) The input of the mask predictor is only the solution generated by the neural solver, following (2), then this mask predictor cannot consider the error of the perception results. So I am wondering if the mask predictor can also consider use the the original problem as part of the input? \n    (4) Some literature are missing, e.g., [1][2][3]. Though you are focusing on different perspectives and the setting are not the same. But it would be better to talk about them in the paper.\n\n[1] Brouard, Céline, Simon de Givry, and Thomas Schiex. \"Pushing data into cp models using graphical model learning and solving.\" International Conference on Principles and Practice of Constraint Programming. Springer, Cham, 2020.\n[2] Mulamba, Maxime, et al. \"Hybrid classification and reasoning for image-based constraint solving.\" International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, 2020.\n[3] Bai, Yiwei, Di Chen, and Carla P. Gomes. \"CLR-DRNets: Curriculum Learning with Restarts to Solve Visual Combinatorial Games.\" 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%