Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.

The 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.

As 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.

Overall, 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.
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.

A 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.)

I 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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 


This 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). 

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.

The 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. 


I am listing my concerns/questions to the authors in the following. I would be delighted to increase score if authors clarify my understanding.

1. 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? 

2. 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.
In 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?  

3. In line 172, LeNet is introduced without any reference. 

4. What is the intuition behind proofreading layer? How does a slightly noisy identify transformation function benefit in performance?

5. In line 204, what is the precise definition of approxmax used in the experiment?

6. Why are experiments limited to Sudoku problem only? This limits the generalisation of the proposed formulation, at least empirically.

6. 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?

7. In Figure 4, what is the interpretation behind different colors in both figures? 
limitations_and_societal_impact: Authors have discussed limitations and societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: ### Originality

To the best of my knowledge, the proposed distilling clustering result as pre-trained classifier, Symbol Grounding Loss, and proofreading are novel. 

### Quality

The 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}$:
-  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? 
- 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?

Without clarifying this, it is unclear that the main claim about solving ungrounded composite visual reasoning problems is supported.

### Clarity

The paper is clearly written overall, but the experiment section has some details missing.

- 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? 
- 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?
 - 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.
- 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.
- 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?
- 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. 
-  The criteria for early stopping the self-grounded training, which seems very important for the pipeline to perform well, should be explained more concretely.

### Significance
This 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.

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.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

There are a few concerns and questions I would like to raise in this review:

1. 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.

2. 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.

3. 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. 

Minor: Line 99 end, close parenthesis.

In 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".

[1] Mao et al. "The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision", ICLR 2019
[2] Yi et al. "Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding", NeurIPS 2018

Post rebuttal:
I 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".
limitations_and_societal_impact: The limitations and societal impact of this paper is sufficiently discussed.
review_title: null

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)