Techniques for Symbol Grounding with SATNet
Authors: Sever Topan
David Rolnick
Xujie Si
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Symbol Grounding
MAXSAT
Neurosymbolic Reasoning
Self-Supervision
Visual Reasoning
SATNet

Abstract: Many experts argue that the future of artificial intelligence is limited by the field’s ability to integrate symbolic logical reasoning into deep learning architectures. The recently proposed differentiable MAXSAT solver, SATNet, was a breakthrough in its capacity to integrate with a traditional neural network and solve visual reasoning problems. For instance, it can learn the rules of Sudoku purely from image examples. Despite its success, SATNet was shown to succumb to a key challenge in neurosymbolic systems known as the Symbol Grounding Problem: the inability to map visual inputs to symbolic variables without explicit supervision ("label leakage"). In this work, we present a self-supervised pre-training pipeline that enables SATNet to overcome this limitation, thus broadening the class of problems that SATNet architectures can solve to include datasets where no intermediary labels are available at all. We demonstrate that our method allows SATNet to attain full accuracy even with a harder problem setup that prevents any label leakage. We additionally introduce a proofreading method that further improves the performance of SATNet architectures, beating the state-of-the-art on Visual Sudoku. 

Techniques for Symbol Grounding with SATNet
Sever Topan 1.2, David Rolnick and Xujie Si McGill University, "NVIDIA, "Mila-Quebec AT Institute, 'CIFAR AT Research Chair {stopan, drolnick, xsi] ea.3)esmmmgill.ca
Abstract
Many experts argue that the future of artificial intelligence limited by the field's ability to integrate symbolic logical reasoning into deep learning architectures. The recently proposed differentiable MAXSAT solver, SATNet, was a breakthrough in its capacity to integrate with a traditional neural network and solve visual reasoning problems. For instance, it can learn the rules of Sudoku purely from image examples. Despite its success, SATNet was shown to succumb to key challenge in neurosymbolic systems known as the Symbol Grounding Problem: the inability map visual inputs symbolic variables without explicit supervision ("label leakage"). In this work, we present self-supervised pre-training pipeline that enables SATNet overcome this limitation, thus broadening the class of problems that SATNet architectures can solve to include datasets where no intermediary labels are available at all. We demonstrate that our method allows SATNet to attain full accuracy even with a harder problem setup that prevents any label leakage. We additionally introduce a proofreuding method that further improves the performance of SATNet architectures, beating the state-of-the-art on Visual Sudoku.
Introduction
Recent years have seen significant advancements in deep learning, providing breakthroughs in image, video, and audio processing [1]. Despite its success, deep learning has many known limitations, such as low interpretability, vulnerability to adversarial attacks, and difficulty in solving problems requiring hard logical constraints [2-5]. To overcome these limitations, experts have described the need to migrate from purely deep learning based systems to neurosymbolic artificial intelligence systems, which integrate neural networks with logical reasoning [6]. this work we focus on improving promising development in this field: the award-winning architecture known as SATNet [7].
SATNet is differentiable MAXSAT solver based low-rank semidefinite relaxation approach. can be integrated into traditional Deep Neural Networks (DNNs) to solve composite learning problems that require both logical reasoning and visual understanding. One such problem is Visual Sudoku, where the model must learn the rules of Sudoku puzzle purely from visual examples. When trained end-to-end, SATNet is able achieve 63. .2%% total board accuracy this task while traditional DNN architectures are unable to exceed 0% [7]. This was regarded as significant breakthrough for neurosymbolic architectures. However, was recently noted that SATNet training relies upon "leakage" of labels through the logical constraint layer to the DNN used to classify digits [8].
This leakage essentially means that SATNet learning in supervised stages, where it first trains its digit classification component under direct supervision, and only then trains its SAT layer to learn the logical constraints delineating Sudoku. When the leakage is removed, SATNet'ss ability to solve Visual Sudoku drops to 0% [8]. This is significant, because taken independently, these two sub-problems are significantly easier. Digit classification considered solved problem, and while SAT constraint mining is more difficult, it could be argued that the differentiable aspect is no longer beneficial if the system needs supervision on its inputs to learn regardless. For instance, there exist other SAT constraint miners that are not differentiable but outperform SATNet [9]. Overall, the issue
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of being unable to learn to solve composite visual reasoning problems end-to-end is referred to as the Symbol Grounding Problem, and is considered one of the fundamental prerequisites for artificial intelligence to perform practical logical reasoning [8, 10].
Forward Pass: Solves MAXSAT to salve Visual Sudoku
Bockward Pass: Learns MAXSAT CNF constraints for Visual Sudoku from examples
100004062
49 060041
0.001010
12igit Classifier
SATNe
Sudoku Solution
50 50 100
00307 1
7 0 0 DOD
0500000
Figure 1: The SATNet architecture used to solve Visual Sudoku. The red line shows the label leakage issue, which when removed, results in the Symbol Grounding Problem.
We observe a key challenge of symbol grounding is the large gap between the compositional nature of logical reasoning and the end-to-end gradient-based nature of neural networks. The former helps to reduce sophisticated reasoning system into simple, independent modules, each of which can be designed manually or learned, while the latter encourages fusing all components together and using gradients as a universal means for learning. Many recent approaches aim bridge this gap by relaxing logical constraint solving through numerical optimisations [11-14]. Although such end-to- end gradient-base based optimisation is appealing. can fail address seemingly simple tasks like Visual Sudoku. The success of SATNet is in fact due to inadvertent supervision of intermediate modules. We argue that compositionality does not have to be the opposite of the end-to-end learning design. The latter is particularly preferable because it eliminates the need for supervision of intermediate modules, which is often required by a compositional design. compositionality can be trained using self- supervision (i.e. without manual effort), compositionality would then be at least equally preferable. This is the approach that we take in the present work, synergistically combining compositionality with end-to-end learning without any explicit intermediate supervision. We envision our methodology forming a new paradigm for tackling neurosymbolic learning.
We describe supe-vuue pre-training method that can be used to bootstrap SATNet in order to overcome the Symbol Grounding Problem. Our methodology enables us to tackle a class of what we call Ungrounded MAXSAT problems, where label data are available only for the output variables of the MAXSAT problem. In the Visual Sudoku case, this formulation manifests itself as a dataset where, as before, inputs consist of images of digits describing the input cells of Sudoku board. The labels of the dataset, however, consist of numerical representations only for the board cells that were not given inputs. This means that there is way of identifying what digit each input image refers to except by learning the rules of the Sudoku puzzle in parallel to predict the non-input values. We refer to this problem as Ungrounded Visual Sudoku. We show that method improves the state of the art on this problem from 0% to 64.8%, achieving similar performance on Ungrounded Visual Sudoku SATNet with label leakage does in the grounded version of the same problem. In short, our main contributions are the following:
1. We describe self-supervised clustering and distillation process for training visual classifier within a SATNet architecture.
2. We introduce Symbol Grounding Loss that makes it possible train logical constraint layers on an ungrounded symbol representation.
3. We show empirically that our methodology allows SATNet to achieve full performance ungrounded Visual Sudoku (where label leakage is impossible), task where previous state-of-the-art was 0%.
4. We introduce a Proofreader that improves the performance of any SATNet system (grounded ungrounded), achieving oftt--of-the-ar performance Visual Sudoku.

---

2
Background
Our contribution draws from several areas. We begin with preliminaries describing the problem, before discussing related work.
2.1 The Problem
MAXSAT, the optimisation analog of SAT, represents rich set of problems to which many program complexity classes can reduced. MAXSAT Solver S aims maximally satisfy a set of boolean clauses over variables by modulating the values of the variables. These clauses typically written in Conjunctive Normal Form, and represented numerically as a matrix M e R=x" We can further enrich this system by partitioning our variables m into subset of fixed inputs a) "...... and variable outputs "k+ I...... The system can then be framed functionally:
out Ok+l....m S(aa M), for 1 S k S m.
(1)
This formulation be used to capture Sudoku, example used extensively in this work, where aM represents the input cells a given Sudoku board, a out represents the cells that we aim to solve for, and M encodes the rules of Sudoku.
MAXSAT Solvers can be leveraged to solve a broader class of problems that we refer to here Visual MAXSAT Problems. These entail MAXSAT problem where the inputs at must first be derived from some other representation aiisaal This essentially results a two-step training problem for which neurosymbolic architectures are optimised'.
in
We have now established the preliminaries necessary to describe the Symbol Grounding Problem in the context of Visual MAXSAT solvers. is the problem of identifying at given only auisual and aut This motivates the distinction between two types of Visual MAXSAT Datasets: grounded and ungrounded. An ungrounded dataset contains a @issaal as data and auu as labels, while grounded dataset additionally contains am in its labels (See Figure
8 O
8 5
8 O
57
6
2
9
3 4
4 7]
3
4 a in visuul
0
7
a in vissul
in out
a out
Grounded Dataset
Ungrounded Dataset
Figure 2: Examples of Grounded and Ungrounded Visual MAXSAT Datasets, focusing on a x portion of a larger Sudoku board. Blue entries represent input cells. In previous work, SATNet is able to solve only the grounded version of the problem.
We note that it is significantly more difficult to solve the ungrounded version of Visual MAXSAT problem, as training cannot trivially broken up into two stages. It is this the class of problems that we tackle in this work.
2.2 Logical Constraint Solvers & SATNet
There has been significant recent interest in architectures that integrate symbolic reasoning layers within neural networks. Many approaches. however, are only capable of integrating pre-existing logical constraints into these models [15-19]. In the context of our formalism, this is analogous to having fixed set of clauses M for particular problem. Conversely, there exists family of approaches that are not differentiable, but are able to learn logical constraints by example [9, 20, 21]. SATNet, however, sits somewhere in between these approaches, as it is both differentiable and able learn matrix M in order fit some input data [7]. There are few other algorithms in this class, such OptNet and 0-Explainer [11, 12, 22].
While it is also possible to train system end- mod-to-end to derive a directly from a. we argue that internally the system would need have some form of representation of this two-step approach regardless.

---

2.3 Self-Supervised Pre-Training
supervieee pre-training has long history in machine learning, notably being used navigate highly non-convex loss landscapes in Deep Belief Networks (DBNs) [23, 24]. More recently, better methods for end-to-end training have emerged and self-supervision has now been used to pre-train image tasks on large, cheap unlabeled datasets to obtain slightly better performance on supervised tasks [25, 26].
In our work we return to the insight that motivated the original use of self-supervision for DBNs. The Symbol Grounding Problem essentially represents significant non-convexity in the problem space- both symbol meanings and the way in which symbols interact with one another must be learned in parallel, with local optima existing many combinations of prospective groundings. sulf-vupe pre-trainn pre-training enables us to start training from a favorable position on this loss landscape.
2.4 Clustering Algorithms & InfoGAN
Data clustering is mtag-stnn and rich field of computer science [27]. We leverage clustering in our method in order to conduct self-supervised pre-training. While many clustering algorithms exist, for our purposes we choose use InfoGAN, as is able to cluster across the semantic dimension which we are interested in for MNIST with very high accuracy [28].
InfoGAN is Generative Adversarial Network architecture which boasts disentangled, interpretable latent encodings [29]. It maximizes the mutual information between a subset of the noise fed into its generator, and the observation which the discriminator makes. It is thus able cluster data according to several interpretable variables. In the case of MNIST, these include handwritten digit thickness, slant, and most useful us, the actual digit shape. This latter property is what we aim leverage in this work. Specifically, InfoGAN can cluster MNIST digits according to their numerical value with 95% accuracy completely unsupervised fashion [28].
2.5 Knowledge Distillation
Knowledge Distillation is a technique for training machine learning models to reach comparable performance inference time larger reference model, an ensemble of models [30-33]. While more complex distillation techniques exist, our work leverages the concept in one of its most basic forms simply training smaller model from dataset generated by a larger one in order drastically improve inference time.
3 Method
Our main contribution is a pre-training pipeline used to bootstrap the learning process such that SATNet can bypass the Symbol Grounding Problem. Overall method entails the following steps.
1. Clustering: We first perform unsupervised clustering of the input data, and distill the knowledge of the clusters into a digit classifier.
2. Self-Grounded Training: We then employ a custom Symbol Grounding Loss to identify how clusters map to the labels we have in our training data. Once the grounding is learned, we freeze it and train the rest of the system.
3. Proofreading: We conelude with an optional proofreading step which trains an additional layer in the SATNet architecture while the rest remain frozen. This was found to slightly improve performance in all SATNee architectures tested.
Before diving in to each of these steps, we will formalize the composite visual understanding/logical reasoning problem. Assume we look at a single instance of a MAXSAT problem with N variables which can fall into one of K classes, where each of the N variables is represented by an image of size C' x H x W. Our input data is then tensor x E R Nx xW and our desired one-hot encoded output y E RNNK Our digit classifier D takes input x and returns output D(x:) = úim N We feed this result into our SATNet layer S such that S(jim) ) Dout E NR For Ungrounded Visual Sudoku using MNIST, we have = 81 (one MAXSAT variable for each cell of the x 9 Sudoku board), K (digits 1 through 9), and C x H W 1 1x 28 x 28 (MNIST images).

---

0 0 000000000
000004000
4 060048
000 000010100
Digit Classifier
Proofreader
SATNet S
P
Sudoku
5 5003+0 340000000
Solution
003311011
Figure 3: The architecture proposed in this work. It leverages self- self-supe pre-training to solve Grounded Visual Sudoku, thereby overcoming the Symbol Grounding Problem affecting the original SATNet method.
3.1
Clustering
Our first step solving an Ungrounded MAXSAT problem is identifying the patterns that exist in the input data. Intuitively, we do not have to start training digit classifier from scratch when training composite visual reasoning architectures. There exists some semantic aspect the input image which is of relevance to the MAXSAT problem at hand, and it can often be at least partially identified in self-supervised setting. In the Visual Sudoku case, this entails clustering our images into groups (corresponding values through 9).
In our experiments, we use InfoGAN to perform the clustering, is capable of clustering MNIST digits with 95% accuracy [28]. Any clustering algorithm may be used here however, even ones that not differentiable. Once the clustering is complete, into a differentiable digit classifier. In our case, we generate dataset using the clustering algorithm, and train LeNet on the cluster allocations of the training data [34]. By doing this we implicitly map each cluster onto some one-hol representation within Pin. However, this one-hot encoding of the MAXSAT variables may not match with the encoding present in the labels y. We deal with this next.
can distill the clustering knowledge back
3.2 Self-Grounded Training
While clustering algorithm might be able achieve high accuracy, it doesn't 't have any information about which numerical digit each cluster is actually associated with, since we don't have access to input cell labels. This is the crux of the Symbol Grounding Problem. In an Ungrounded MAXSAT setting, the only way to learn the association between digits and numerical clusters involves jointly learning the MAXSAT problem. In the case of Sudoku, this means that must solve for the rules of puzzle and learn what each digit means simultaneously.
To reason about this, consider two sets of encodings for digits: the pre-trained encoding (PTE) and the (correct) label encoding (LE), which we notate using superscripts. The digit classifier from the previous step outputs PTE-encoded predictions i There exists some unknown permutation matrix P R K that translates between encodings via J p = i.L Our goal is to align the PTE encoding with the LE encoding, so that we can make use of the training labels. The question of performing this translation before after the SATNet layer is irrelevant, however. This is because the MAXSAT CNF clauses which SATNet implements are that long supervision is provided correctly, g. In our approach we pass the prior through SATNet, and are left with J predictions.
[35]. This means train the SATNet layer S on either 2 or
We learn the correct permutation (without access any of the input labels) simultaneously with training the SATNet layer, by introducing a Symbol Grounding Loss, which is intended to be a smooth function that is minimized when GPT P zy y for some permutation matrix P.
Note that / and E are N x K matrices, and let ETE (i) and - (i) denote the ith columns of these matrices. Then, E (in the correct label encoding), while / (t) is a vector of predicted probabilities that the output is
(i) is 1-hot vector capturing the entries of the output that are labeled i
While this expected, this was not explicitly stated in the original SATNet paper. We were able to verify this empirically by applying permutation on the one hot encodings of the digits in the nonvisual Sudoku setting and SATNet's performance is identical even without re-training.
5

---

labeled i (in the pre- pre-trained label encoding). We define the following loss L:
Ciouu ,y 1 mean, (max(exx ()) (i))),
(2)
where BCE(-,-) denotes the binary cross-entropy loss between two vectors:
BCE(U, w) = - Σ Uh Log(wa) )+
+
(1 E
uk log(1 - wxx)
km1
Proposition 3.1. Suppose L is defined as in (2). Then:
1. C(yond F) minimized if and only if F PPEEP- y I. for some permutation matrix P.
2. In this case, the matrix P is given by P. == expl- BCE(yL (i))]
This proposition, which is proven in Appendix A, shows that by minimizing L, we learn approxi- mate permutation matrix P ~ P, given by:
P.j = expl- (. (T))
In practice, we do not minimize L, since the max function presents an obstacle to effective training. Therefore, we relax the max operation to a function approxmax. This finally gives us our Symbol Grounding Loss Lsc:
LsclWbut PTE ( = - mean, (appr((ppppxxmxxxeexppp BCEbp/
Do (O)))-
(4)
In our experiments, we set approxmax equal to the 2-norm; however, we did not find that performance was sensitive the exact choice of арproxmax, and other choices are also reasonable.
Having defined Lsc, we incorporate it into our training pipeline as follows: First, we freeze the digit classifier D, and train S under Lsg- This begins to train S while also learning permutation matrix P 2: P (defined by (3)). Note that since the permutation matrix is learned by means of SATNet itself, and it is impossible for labels to be leaked, since the training process does not even have access labels for the input entries.
working with the Ungrounded Visual Sudoku task,
Second, once P has converged to clear permutation matrix, freeze this permutation and use it to align the PTE labels with the correct LE labels by multiplying the final outputs PTE by the learned P. Now that the Symbol Grounding Loss is no longer needed, we switch to the traditional BCE loss and complete the training of S, also unfreezing D allow additional training.
3.3 Proofreading
The performance of a SATNet architecture can be improved by the addition of a Proofreader layer. This consists of linear layer added just before the SATNet layer S, initialized to slightly noisy identity transform IR x + R. (In the Sudoku case, N = 81 and K 9.) We freeze the layers in the original model, and train only the proofreader layer. This an optional final step resulting in slight performance improvement. We find that the Proofreader layer also improves the performance of the original SATNet (with label leakage), in both the visual and nonvisual Sudoku settings.
4 Results
The above procedure allows us to achieve comparable results on an Ungrounded Visual Sudoku Dataset as the original SATNet architecture has the grounded setting", with results being presented in Table 1. We may thus claim to solve the Symbol Grounding Problem in the case of Visual Sudoku.
All experiments were carried out on Nvidia GTX1070 across 100 epochs, with each epoch taking roughly 2 minutes. The Adam optimiser was used with learning rate of 2 x 10-3 for the SATNet layer, and 10-$ for the digit classifier [36]. Standard deviations were calculated across 5 runs. We used the Sudoku Dataset made available under an MIT License from the original SATNet work [7].
Note that training under grounded dataset equivalent to the label leakage problem described in [8]

---

Model Configuration
Grounded
Total Board
Per-Cell
Visual
Ungrounded Data
Accuracy (%)
Accuracy (%)
Accuracy (%)
Original SATNet
grounded
66.5 1.0
98.8 + 0.1
99.0
Original SATNet
ungrounded
0 + 0.0
11.2 + 0.1
11.6 + 0.0
Our Method
ungrounded
64.8 3.0
98.4 = 0.2
98.9 0.1
Performance of our method compared to the original SATNet architecture between grounded and ungrounded versions of the Visual Sudoku problem. Note that distinguish the total board accuracy (how many 81-cell boards are completely correct) from per-cell accuracy (how many board cells are correct) and visual accuracy (how many input board cells correct). Our method achieves comparable performance on a significantly more difficult version of the problem, thus solving the Symbol Grounding Problem.
Table 1:
Permutation matrices extracted from the Symbol Grounding Loss function. On the left is matrix extracted given clustering with high accuracy, and the right matrix shows the results in case where the clustering accuracy below the necessary threshold (see Section 4.1).
Figure 4:
During our pre-training pipeline, the clustering step achieves 95.6 + 0.4% clustering accuracy. Under the Symbol Grounding Loss, our self-grounded training achieves 22.3 + 1.0% per-cell accuracy. One thing to note is that the self- groundeddddd training step is susceptible to overfitting, and one needs to employ early stopping on the basis of per-cell error in order to learn the permutation matrix P. See Figure for an example of a learned p matrix.
Note that it is expected that the ungrounded version of the dataset will produce slightly worse results since it carries less information in its labels than its grounded counterpart. Another relevant aspect is that InfoGAN itself is sensitive random seed. 4/10 runs converge to clustering below the threshold necessary to ground symbols. We discuss this limitation further in Section 4.1.
4.1
Effect of Clustering Accuracy
An important ablation test to define some limitations of our approach is study the effect of clustering accuracy on our pre-training perfor- mance. It is difficult measure this, as performance could vary based on the distribution of predictions across clusters, not only raw clustering accu- racy. In this study against InfoGAN at different stages of its training. In this way the cluster assignments start out uniform (based on noisy initialization) and gradually anneal to 89.6 + 7.7% accurate clus- tering. We find that our system re- quires roughly at least 88% clustering accuracy order for the rest of pipeline to progress. This is shown in Figure 5. While this is notable lim- itation to our approach, solving Un-
Trial Readd Aecunary S0L vinimum nor Accuracy
60
30
our pipeline
82.5
$25.0
$2.0
Dign: Luceeing Ausuraacy
Figure 5: The effect of InfoGAN's clustering accuracy on method's total board accuracy (bluc) and per-cell ac- curacy during the Symbol Grounding Loss training phase (orange). Each pair of points connected by dashed line indicates a different experiment. We note the sharp perfor- mance drop roughly 88% clustering accuracy.
7

---

grounded Visual Sudoku was not at all possible with SATNet prior to this work. Furthermore, threshold of 88% aceuracy nearly as high as one might naively expect. Given that our input dataset contains on average 36.2 input cells per board, 88% digit classification accuracy gives less than 0.1% chance of identifying an input board state perfectly with the initial clustering.
4.2 Effect of Distillation
In the case that the clustering algorithm used in our first pre-training phase is differentiable, the distillation step becomes optional. Despite this, is desirable to distill our clustering model if there exists some smaller architecture that can achieve similar performance in the supervised setting. This the case with InfoGAN, which in its standard form uses an architecture with 7,307,99 ,999 parameters. We distill this into LeNet-derived architecture [34], with only 1,049,080 parameters and comparable performance, as shown in Table Training speed changes from 602 = seconds/epoch to 255 + seconds/epoch between the two architectures.
Digit Classifier Digit Clustering Accuracy (%)
InfoGAN
89.6 + 7.7
Distilled LeNet
86.2 13.5
Table 2: The effect distilling InfoGAN into a smaller LeNet-based convolutional architecture. InfoGAN performance has tendency to plateau at different levels based on seed. Here we show performance across all runs, whereas successful ones are used the downstream pipeline. A "successful" InfoGAN run will plateau at roughly 95% accuracy.
4.3 Effect of Proofreading
Proofreading improves the performance of both visual and non-visual Sudoku, as seen in Table 3. We achieve the following results by training the proofreader with ungrounded Datasets even if the original model which augments was trained with the grounded version.
Model
Proofreader Present?
Total Board
Per-Cell
Visual
Configuration
Accuracy (%)
Accuracy (%)
Accuracy (%)
Original Non-visual no
96.6 + 0.3
99.9 + 0.0
N/A
Original Non-visual
yes
97.1 + 0.3
99.9 + 0.0
N/A
Original Visual
no
66.5 + 1,0
98.8 = 0.1
99.0 = 0.0
Original Visual
yes
67.6 + 1.2
98.6 + 0.1
99.0 0.0
Our Method Our Method
no
62.8 + 3.2
98.6 + 0.1
98.9 + 0.1
yes
64.8 + 3.0
98.4 + 0.2
98.9 0.1
Table 3: The effect of adding proofreading layer to the original versions of SATNet for both visual and non-visual Sudoku datasets, as well as the pre-training method proposed this paper. We show that proofreader uniformly improves the Total Board Accuracy of SATNet.
We note that the numbers above from the original architectures reflect our reproduction of the results in the original paper. Please see Appendix for further details.
Discussion
5.1 Sensitivity of SATNet to Random Seeds
It was described in [8] that SATNet exhibits high sensitivity to the choice of random seed. For instance, 8 out of 10 random seeds would fail even with label leakage. While we initially reproduced this behavior, such sensitivity can in fact be circumvented with minor correction to the PyTorc implementation, detailed further in Appendix B. We use the corrected, stable model for comparison in all our results.

---

5.2 Incorrect Upper Performance Bound
In the original SATNet paper, it is argued that the performance of the visual Sudoku model bound by the probability of identifying all the input cells on particular board correctly. Thus when using LeNet, which has classification accuracy of 99. 29,2%, the best performance we can expect on our dataset with 36.2 input cells on average is 0.99236.2 2 74.8% [34, 7J. This is not exactly accurate.
It is not necessarily true that the SATNet layer cannot solve board correctly if some number of input cells are wrong. Intuitively, if one finds two of the same numbers as inputs in a row of a Sudoku puzzle, one can infer that one of those inputs might have been classified incorrectly. This can then be used to make an educated guess about the correct final board state. We are able to show that the SATNet layer is actually able reason about incorrect input cells to a certain extent. Interestingly, SATNet's 's ability to reason is affected by whether an incorrectly labeled digit results in an unsolvable board or not. It also affected by the presence of a Proofreader layer. Details on these experiments can be found in Appendix C.
While the upper bound posed originally may not be strictly correct, it is still good guideline. Deriving a strict upper performance bound is likely quite difficult as the mathematics of logical problems such Sudoku are not fully understood.
6 Limitations & Future Work
While our method is able to address a new class of Visual MAXSAT problems with SATNet, it is limited by the need to prime the digit classifier with correct data clusters (see Section 4.1.. This imposes a constraint on which datasets can be used as visual inputs to this pipeline. One facet of this limitation is the fact that the current Symbol Grounding Loss function only supports inferring a permutation between the pre-trained encoding and the label encoding. This means that if there are K label classes, the clustering algorithm must cluster the input data accurately in K clusters. One might imagine allowing the Symbol Grounding Loss to support a more general surjective mapping between encoding domains, allowing for a higher number of clusters (and consequently a higher accuracy).
A second limitation is the tendency of the Symbol Grounding Loss to overfit somewhat quickly. While we experimented with several loss function formulations, further experimentation may prove useful. Implementation of regularisers in the architecture may also be an interesting avenue of research.
We believe neither of these limitations is fundamental; future investigation may help alleviate them.
7 Societal Impacts
The goal of the present work is to advance methods integrating deep learning and logical reasoning, which has long been a goal of artificial intelligence and admits broad range of applications. We also alleviate reproducibility issues with prior SATNet systems, describing in Section 5.1 how to fix previously observed training instabilities [8].
Potential negative implications from our work are largely indirect and hard to assess. We envision the possibility of work neurosymbolic methods leading unrealistic expectations of the power of deep learning methods, which are not yet capable of sophisticated reasoning. This could lead to inappropriate trust placed in current deep learning methods, to backlash if expectations fall short.
8 Conclusion
Our work lays out a foundation for distinguishing between grounded and ungrounded variants of Visual MAXSAT problems, and presents self-supervised pre-training methodology which enables SATNet to solve both classes. The ability to solve the more difficult Ungrounded Visual MAXSAT problems contrasts markedly with the previous state of the art, which was unable to surpass 0% accuracy on these tasks. Further, we describe proofreading methodology which can be used to incrementally improve both our architecture and prior models. This work extends the current state of the art for logical constraint-learning neurosymbolic methods, promising area of research which boasts the potential to dramatically broaden the range of problems which machine learning can address.

---

Acknowledgments
We thank the anonymous reviewers for insightful comments. This work was supported. in part, by Individual Discovery Grants from the Natural Sciences and Engineering Research Council of Canada, and the Canada CIFAR Al Chair Program.
References
[1] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521((553):436 444, May 2015.
[2] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On Evaluating Adversarial Robustness. Preprint arXiv: (exXiv::002000100 1902.0675, 2019.
[3] Samuel Henrique Silva and Peyman Najafirad. Opportunities and Challenges in Deep Learning Adversarial Robustness: A Survey. Preprint arXiv:2007.00753 2020.
[4] Erico Tjoa and Cuntai Guan. A Survey Explainable Artificial Intelligence (XAI): Towards Medical XAI. Preprint arXiv:1907.07372 2019.
[5] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of Gradient-Basee Deep Learning. In International Conference Machine Learning (ICML), 2017.
[6] Artur d' Avila Garcez and Luis C. Lamb. Neurosymbolic Al: The 3rd Wave. Preprini arXiv:2012.05876, 2020.
[7] Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. SATNet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference on Machine Learning (ICML), 2019.
[8] Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger. Assessing SATNet's ability solve the symbol grounding problem. In H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS), 2020.
[9] Tao Meng and Kai-Wei Chang. An Integer Linear Programming Framework for Mining Constraints from Data. Preprint arXiv:2006.1088 10836, 2020.
[10] Stevan Harnad. The symbol grounding problem. Physica D Nonlinear Phenomena, 42(1-3):335- 346, June 1990.
[11] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-End Constrained Optimization Learning: A Survey, Preprint 1rX1v:2103..6678, 2021.
[12] Brandon Amos and Zico Kolter. OptNet: Differentiable Optimization as Layer in Neural Networks. In International Conference on Machine Learning (ICML), 2017.
[13] Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In International Conference on Machine Learning (ICML), 2020.
[14] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations (ICLR), 2020.
[15] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning SAT Solver from Single-Bit Supervision. In International Conference on Learning Representations (ICLR), 2019.
[16] Robin Manhaeve, Sebastijan Dumančic, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. DeepProbLog: Neural Probabilistic Logic Programming. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[17] Wang-Zhou Dai, Qiu-Ling Xu, Yang Yu, and Zhi- Zhou. Tunneling Neural Perception and Logic Reasoning through Abductive Learning. Preprint arXiv:1802.01173, 2018.
10

---

[18] Rasmus Berg Palm, Ulrich Paquet, and Ole Winther. Recurrent Relational Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[19] Richard Evans and Edward Grefenstette. Learning Explanatory Rules from Noisy Data. Journal of Artifiical Intelligence Research, 2017.
[20] Sebastian Nowozin and Christoph Lampert. Structured learning and prediction in computer vision. Foundations and Trends in Computer Graphics and Vision, 6:185-365, 01 2011.
[21] Christian Bessière, Abderrazak Daoudi, Emmanuel Hébrard, George Katsirelos, Nadjib Lazaar, Younes Mechqrane, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. New Approaches Constraint Acquisition. In Data Mining and Constraint Programming, volume 10101 of Lecture Notes in Computer Science, pages 51-76. Springer International Publishing AG, 2016.
[22] Mokanarangan Thayaparan, Marco Valentino, Deborah Ferreira, Julia Rozanova, and An- dré Freitas. O-Explainer: Abductive Natural Language Inference via Differentiable Convex Optimization. Preprint arXiv:2105.034117 2021.
[23] G. E. Hinton, S. Osindero, and Y. W. Teh. A fast learning algorithm for deep belief nets. Neural Comput, 1877::1527-1554 Jul 2006.
[24] Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In Advances in Neural Information Processing Systems (NeurIPS), 2007.
[25] Huanru Henry Mao. A Survey on Self-supervised Pre-training for Sequential Transfer Learning in Neural Networks. Preprint arXiv:2007.00800, 2020.
[26] Mathilde Caron, Piotr Bojanowski, Julien Mairal, and Armand Joulin. Unsupervised Pre- Training of Image Features on Non-Curated Data. In International Conference on Computer Vision (ICCV), 2019.
[27] Dongkuan Xu and Yingjie Tian. comprehensive survey of clustering algorithms. Annals of Data Science, 2(2):165-192 Jun 2015.
[28] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Ad- versarial Nets. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[29] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2014.
[30] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in a Neural Network. Preprint arXiv:1503.022
2015.
[31] Lei Jimmy Ba and Rich Caruana. Do Deep Nets Really Need to be Deep? In Advances in Neural Information Processing Systems (NeurIPS), 2014.
[32] Andrei A. Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy Distillation. In International Conference on Learning Representations (ICLR), 2016.
[33] Gregor Urban, Krzysztof J. Geras, Samira Ebrahimi Kahou, Ozlem Aslan, Shengjie Wang, Rich Caruana, Abdelrahman Mohamed, Matthai Philipose, and Matt Richardson. Do Deep Convolutional Nets Really Need to be Deep and Convolutional? In International Conference on Learning Representations (ICLR), 2016.
[34] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324, 1998.
[35] Luis C. Lamb, Artur Garcez, Marco Gori, Marcelo Prates, Pedro Avelar, and Moshe Vardi. Graph Neural Networks Meet Neural- Symbolcy Computing: A Survey and Perspective. In International Joint Conference on Artificial Intelligence (IJCAI), 2020.
[36] Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference Learning Representations (ICLR), 2015.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] See Section 7
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
3.2 and Appendix
(b) Did you include complete proofs all theoretical results? [Yes] See Section 3.2 and Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] Included as Supplemental Material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section 4.
(b) Did you mention the license of the assets? [Yes] See Section
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you't rr using/curating? [Yes] No personally identifiable data used, data and code was made available under license (mentioned in Section 4).
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] None present, discussed in Section 7.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] No human subject research conducted.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] No human subject research conducted.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] No human subject research conducted.
12


Reviews:
[{"review_id": "tBXt0kSeNn2", "reviewer": "Reviewer_rhk1", "summary": "Advancement of deep leaning comes with several limitations such as lack of interpretability, adversarial attacks and difficulties in incorporating logical constraints. To alleviate these limitations, neurosymbolic AI has been studied that integrates neural networks with logical reasoning. One recent breakthrough is SATNet, which proposes a differentiable MaxSAT solver and finds its application in visual reasoning problems, such as learning rules of Sudoku solely from image examples. \n\n\nThis paper tackles the symbol grounding problem in neurosymbolic systems which is the inability to map visual inputs to symbolic variables without supervision (also known as label leakage). In this paper, authors argue that without any label leakage (that is, without any supervision in digit classification task), SATNet’s abilility to solve Sudoku drops to 0%. As a result, this paper proposes a self-supervised pre-training pipeline that enables SATNet to solve ungrounded MaxSAT problems, where label data are available only for output variables of the MaxSAT problem. The contributions of the papers are (i) proposing a self-supervised clustering and a distillation process to train a visual classifier within a SATNet architecture, (ii) introducing a loss function specific to symbol grounding problems that allows to train logical constraints on ungrounded symbol representation. Empirical evaluation shows a similar performance on ungrounded MaxSAT problem compared to grounded MaxSAT problem (which allows label leakage). \n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "The paper is generally well written. The running example of Sudoku helps understand the technical contribution of the paper. Symbol grounding problem is well explained in the paper, specially in the context of Sudoku game.\n\nThe paper is somewhat incremental to previously proposed SATNet model. I am motivated that label leakage is a challenging problem in case of visual Sudoku where individual tasks such as image classification and logical reasoning can be separately solved successfully. However, without any label leakage, the problem is indeed difficult to solve. Thus, the paper would get attention from research community in neurosymbolic AI. \n\n\nI am listing my concerns/questions to the authors in the following. I would be delighted to increase score if authors clarify my understanding.\n\n1. The paper presents the main technical details with a running example of Sudoku. What other problems apart from Sudoku can be covered by the proposed integration to SATNet? \n\n2. The paper introduces/discusses MaxSAT in a more abstract sense. How does SATNet solve Sudoku using MaxSAT? An illustration of MaxSAT formulation is missing in the paper, which arises the following question.\nIn line 155, authors mention that each of N variables represent an image of Sudoku. Are these variables Boolean? If so, how can a Boolean variable represent an image?  \n\n3. In line 172, LeNet is introduced without any reference. \n\n4. What is the intuition behind proofreading layer? How does a slightly noisy identify transformation function benefit in performance?\n\n5. In line 204, what is the precise definition of approxmax used in the experiment?\n\n6. Why are experiments limited to Sudoku problem only? This limits the generalisation of the proposed formulation, at least empirically.\n\n6. In table 1, for “grounded” version of SATNet, if per-cell accuracy is 99%, why is total-board accuracy only 67%? Moreover, why is total-board accuracy around 65% for both grounded and ungrounded cases? Any intuition behind that? Is this an average result? If so, how many different Sudoku samples are considered in the experiment?\n\n7. In Figure 4, what is the interpretation behind different colors in both figures? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have discussed limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "XjWq7mYh_uA", "reviewer": "Reviewer_bNAF", "summary": "This work focuses on the problem of symbolic grounding in order to solve a sudoku task with perceptual input. The proposed method extends SATNet, a previous work based on the differentiable MAXSAT solver, and introduces several improvements that enable the model to solve the task without label leakage. Experiments are conducted on a visual sudoku dataset, demonstrating a superior performance of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The incorporation of neural and symbolic methods in solving end-to-end tasks has been an important yet challenging direction of modern AI. This work contributes to this direction by tackling the symbolic grounding problem on an ungrounded visual sudoku task, on which previous methods fail completely. The experiments are sufficiently conducted to assess the effectiveness and limitations of the proposed method. The paper is very well written.\n\nThere are a few concerns and questions I would like to raise in this review:\n\n1. In the problem setting, each input sudoku is automatically cut into 81 pieces into single-digit images, this throws away the \"geometric\" information of the game and drastically simplifies the perceptual module. I wonder if there is going to be any improvements if this geometric information is coupled to the learning of the game rules, as they are strongly related in reality.\n\n2. Another direction of grounding symbols to perceptual inputs is via reinforcement learning, which has been demonstrated in the visual question answering task [1][2]. A discussion on the relationship between these approaches will contribute to the strength of this paper.\n\n3. One can imagine the optimization during the self-grounded training is very sensitive to the structure of the underlying rules (or are they?). Working with one example of visual sudoku is insufficient to demonstrate the generality of this approach. \n\nMinor: Line 99 end, close parenthesis.\n\nIn general, I think this is a well-written paper with solid results, but I also find the technical novelty of this work is slightly below the bar of this conference (since this work builds on top of an existing model and it is unclear how well the pretraining scheme can be adopted in other models and tasks). My score on this paper is \"weak accept\".\n\n[1] Mao et al. \"The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision\", ICLR 2019\n[2] Yi et al. \"Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding\", NeurIPS 2018\n\nPost rebuttal:\nI thank the authors for their efforts in addressing the comments from the reviewers. Even though the technical complexity of the task is limited and more work is needed to further establish the merit of the full method, I feel this is still a good paper to be presented in NeurIPS. My final assessment of this paper remains \"weak accept\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and societal impact of this paper is sufficiently discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "PT-pWre6Uvv", "reviewer": "Reviewer_HyEa", "summary": "The paper addresses how the symbol grounding problem arises in Visual Sudoku problem and proposes a self-supervised approach to grounding symbols in the SATNet architecture without relying on inadvertent label leakage. The leakage problem and its impact on SATNet for Visual Sudoku was known for previous work, so the paper’s key contributions revolve around a solution to this problem. In particular, it introduces a perceptual pre-training stage (clustering and distillation), a symbol grounding loss, and the performance boosting “proofreader” technique.", "questions": "", "limitations": "", "rating": 9, "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": "The essence of the proposed approach is to identify the symbol grounding problem as resolving a mapping between latent perceptual categories and latent symbolic categories suggested by the symbolic labels in the training outputs. In the situation examined, this reduces to learning a permutation matrix (under the assumption that the two vocabularies have a 1:1 relation). Although this reduction is not particularly general, the solution offered (learning a linear alignment matrix) seems to be much more general by comparison. The combination of (1) self-supervised learning to anchor latent categories in the *input* images and (2) the symbol grounding loss to anchor the latent categories in the *output* symbols is novel, valuable, and thought provoking.\n\nThe proposal for the proofreader network seems unrelated to the core idea of the paper. If we think of the proofreader instead as a slight architectural improvement on LeNet, it’s not surprising that performance improves in both cases.\n\nAs an alternative to separate clustering and distillation, the authors might consider the setup used in VQVAEs and VQGANs (e.g. https://compvis.github.io/taming-transformers/). These networks learn to assign discrete codes to grids of tiles in a self-supervised manner. Replacing clustering and distillation in your work with VQGANs would not threaten your key exciting results. Using non-VQ VAEs or GANs could learn useful latent representation and leave their discretization to the proofreader network -- now possibly seen as a learned quantization/categorization layer.\n\nOverall, while the paper is centered on a toy problem, it convincingly uses the focus on the toy problem to identify and advance solutions to some very wide-scale problems in AI.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Choosing a clustering approach that is known to distinguish MNIST digits with 95% accuracy and then going on to apply it to MNIST digits feels like another form of inadvertent label leakage, though certainly not as egregious as the original form of leakage considered by the authors. Even telling the clustering algorithm to define 9 clusters (should it actually be 10 to represent the visual symbol “0”?) feels like a kind of leakage, even though it is much less significant. If we think of digit classification as multi-class classification with labels like “1”, “2”, “3”, clustering avoids leaking these labels. However, if we think of the *hard* parts of digit classification as being able to accurately judge sameDigit(a,b), then carefully chosen clustering approaches can leak lots of labels for this kind of digit classifier.\n\nA revision of this paper should briefly discuss this potential problem of leaking pairwise categorization information. (This reviewer would love to see a paper on a taxonomy of things like label leakage as they pertain to the symbol grounding problem.)\n\nI believe the authors are really getting at the heart of the symbol grounding problem with their work, but a small change in the experiment might allay concerns that clustering is implicitly leaking the hardest part of the task (identifying the useful categories): Try changing the number of clusters to something other than 9, say 100. We still need to solve the symbol grounding task to identify the 9 or 10 significant latent concepts, but this way we are pretty sure that the clustering is also including distracting concepts (e.g. different styles of “8”s) -- grounding would require recovering more than just a permutation. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "N96t90YGvoA", "reviewer": "Reviewer_Aqg2", "summary": "This paper proposes to solve composite visual reasoning problems represented by ungrounded visual Sudoku through augmenting SATNet with several extra learning stages. A differentiable digit classifier is first obtained through distilling unsupervised clustering, which produces quite accurately clustered but potentially classes-permuted classification results. A Symbol Grounding Loss is developed to align the correspondingly permuted prediction from SATNet with ground truth classes, while also supervising the reasoning result. The experiments on ungrounded visual Soduku demonstrate that the additional training steps substantially improved the performance. It is also shown that a proofreader, neural network that finetunes the digit classification before SATNet, further improves the performance.", "questions": "", "limitations": "", "rating": 7, "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": "### Originality\n\nTo the best of my knowledge, the proposed distilling clustering result as pre-trained classifier, Symbol Grounding Loss, and proofreading are novel. \n\n### Quality\n\nThe methods presented make sense intuitively and are supported by prior works or theoretical results. Experiments demonstrate substantial improvement upon prior SATNet results over ungrounded Soduku. However, one of my main concerns is the potential label leaking via $y^{LE}$:\n-  To avoid label leaking, $y^{LE}$ should not contain labels for input variables, i.e. the digits given on the board, during both permutations matrices training and normal supervised training. However, it is not clear from the text that whether this is the case and how are these input variables are handled in the Symbol Grounding Loss and normal BCE loss. Are they just omitted from the term? \n- In Appendix B, it is noted that the gradient computation would be different by outputting the input variable predictions using $ y_{out}^{PTE} $ versus $ y_{in}^{PTE} $ (there should be hat on y). But if the input variable predictions are not supervised at all in the ungrounded visual Suduku, why would the gradient computation change?\n\nWithout clarifying this, it is unclear that the main claim about solving ungrounded composite visual reasoning problems is supported.\n\n### Clarity\n\nThe paper is clearly written overall, but the experiment section has some details missing.\n\n- On line 233 and figure 5, it is reported that the per-cell accuracy with self-grounding training is about 20%. This number seems very low compared to the final 98.4% per-cell accuracy reported in table 1 and the high clustering accuracies. Why is this the case? Also, why does the per-cell accuracy barely increases as the clustering accuracy increases? \n- The InfoGAN clustering accuracy is reported as $95.6 \\pm 0.4 $% on line 232, but $89.6 \\pm 7.7 $% is reported in table 2 and line 255. Are the settings different?\n - In figure 5, is the clustering accuracy referring to InfoGAN accuracy or distilled LeNet accuracy? I assume that LeNet distillation is used as the real digit classifier when performing the corresponding self-grounded training.\n- Distilled LeNet is reported to have a quite large variance in table 2. Does the distillation step incur variance? i.e. for single trained InfoGAN, what is the variance of the LeNet training trials.\n- Since InfoGAN and Distilled LeNet performance affect the symbol grounding quality drastically, are the results in tables 1 and 3 produced by using a selected run of InfoGAN and LeNet? Or are their variance also accounted for?\n- In table 6 (the updated version of table 3 in the appendix), the bolding seems incorrect for per-cell accuracy for the last two rows. \n-  The criteria for early stopping the self-grounded training, which seems very important for the pipeline to perform well, should be explained more concretely.\n\n### Significance\nThis work presents a novel and effective approach to jointly perform reasoning and symbol grounding, which is an important mark of intelligence. The exact training procedure seems relatively fragile with the need to select lucky runs of clustering and early stop self-grounded learning training. Nonetheless, this work demonstrates a working pipeline that future works can improve upon.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed several limitations throughout the paper. However, one additional critical limitation remains unaddressed: Since the clustering step is task agnostic, it might not produce the symbols required by the task. For example, what if the rule is based on the handwriting style of the digit rather than the class of the digit? Or both of them matter? It seems hard for the later end-to-end training with the distilled differentiable classifier to adjust such a mismatch.\n\n\n\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a wonderful paper for which reviewers showed significant support. In particular, reviewers view that the paper address a very important problem of symbol grounding and the proposed approach is novel, and effective. The authors are advised to take extensive feedback by reviewers into account for the final version. 
Decision: Accept (Spotlight)