Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a similarity-based consistency measure for abduction, which takes the idea that samples in the same category are similar in feature space while samples of different classes are dissimilar.

main_review: The authors propose ABductive Learning with Similarity (ABLSim), which adopts beam search to solve the optimization problem of finding the best abduced labels. 

The paper is well written and the concepts are clear. The proposed approach is novel wrt the other neural symbolic approaches.

The experimental evaluation prove the validity of the proposed approach in term of time efficiency. As regards the accuracy score when compared to  Neural-Grammar-Symbolic model a test should be reported to assess the statistical difference.


limitations_and_societal_impact: The rules in the BK should be manually defined
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a new method for implementing abductive learning proposed by Wang-Zhou Dai et al. (NeurIPS 2019 [4]). The main difference lies in replacing the objective function that maximizes consistency with minimal revisions with a new objective function that maximizes a score for samples relevant to abduced labels, where the score considers both the confidence for samples being classified to abduced labels and the similarity between samples. Experimental results on four knowledge-enhanced datasets demonstrate that this revision on the objective function leads to the state-of-the-art performance and faster converge rate, whereas on the criminal judgement dataset [12] demonstrate that the proposed method achieves better performance with weaker domain knowledge.
main_review: Although the proposed method builds upon the established abductive learning framework [4], the training objective function is completely different and carefully verified by extensive experiments, thus the novelty of the paper is moderate. As far as I can see from the paper and the supplemented source code, the proposed method is technically sound and has sufficient experiments designed to justify the contribution parts. Since the abductive learning framework is a fundamental approach to integrating perceptual intelligence with cognitive intelligence, the development of a more efficient and effective method to implement the framework is very desirable and can have significant impacts. As for the clarity, the paper is well organized and well written except some minor questions remained to me. First, it is unclear how to determine the weighting coefficient between similarity score and confidence score. In particular, it is unclear how this coefficient is set in the experimental method ABLSim. Second, it is unclear whether the comparison method ABL-Conf is simplified from ABLSim by fixing the weighting coefficient to zero or is extended from ABL [4]. The paper says that ABL is inferior to its -Conf version, which means that ABL-Conf is extended from ABL, but it is unclear how to extend ABL to ABL-Conf. Finally, it is unknown how well ABLSim works on the criminal judgement dataset [12] with full domain knowledge. If it works worse with full domain knowledge than with partial domain knowledge, it should be very sensitive to domain knowledge selected. This would imply a limitation that the domain knowledge needs to be carefully introduced.
limitations_and_societal_impact: Yes. Almost all limitations are adequately addressed. A potential limitation may lie in the search space of abductive solutions. With complex domain knowledge, the search space of abductive solutions could be very large or even infinite. The current treatment that computes all abductive solutions before selecting some of them by beam search may not be practical for some scenarios.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper works on the topic of neural-symbolic learning by abductive reasoning. Specifically, the task is to learn a perception model, given symbolic background knowledge and weak supervision. The authors propose a novel abduction strategy to speed up the search in abduction, which is based on the similarity between samples, rather than the output information from the perceptual model used in previous methods. Based on this strategy, this paper presents a neural-symbolic learning framework called "ABductive Learning with Similarity (ABLSim)", which uses beam search to approximate the combinatorial search problem in finding the abduced labels during training. The authors conduct extensive experiments on four tasks: MNIST Addition, Handwritten Formula Recognition, CIFAR-10 Decimal Equation Decipherment, and Theft Judicial Sentencing. The experimental results show that ABLSim is much more efficient than the state-of-the-art neural-symbolic learning methods.

main_review: Strengths:
1. It is interesting and novel to develop a similarity-based consistency measure to guide the abduction process. The main idea is that after the abduction, the samples in the same (pseudo-)category should be similar in the feature space while samples from different categories should be not. 

2. The derivation of the similarity-based consistency measure in Section 4 is reasonable and sound. Here unsupervised or self-supervised learning approaches can be used to obtain a good feature extractor without using any labels.

3. As shown in Table 1, the proposed framework ABLSim outperforms the state-of-the-art methods in terms of both accuracy and efficiency.

4. The paper is overall well-written and easy to follow.

Weaknesses:
1. My major concern is that the comparison between ABLSim and baselines (DeepProbLog, NGS) is a little unfair because ABLSim uses an extra pretrained feature extractor based on contrastive learning (SimCLR). This feature extractor provides an implicit clustering initialization and makes the learning easier in ABLSim, especially for CIFAR-10. I suggest that a more fair comparison be to also pretrain the perceptual model in baselines by unsupervised learning approach [1,2,3], such as SCAN [1], which is also based on SimCLR. FYI, SCAN can obtain ~88% accuracy on CIFAR-10 without using any labels during training.

[1] Van Gansbeke, Wouter, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool. 2020. “SCAN: Learning to Classify Images without Labels.” In ECCV. http://arxiv.org/abs/2005.12320.

[2] Ji, Xu, João F. Henriques, and Andrea Vedaldi. 2019. “Invariant Information Clustering for Unsupervised Image Classification and Segmentation.” In ICCV. http://arxiv.org/abs/1807.06653.

[3] Park, Sungwon, Sungwon Han, Sundong Kim, Danu Kim, Sungkyu Park, Seunghoon Hong, and Meeyoung Cha. 2020. “Improving Unsupervised Image Clustering With Robust Learning.” arXiv [cs.CV]. arXiv. http://arxiv.org/abs/2012.11150.

2. The computation efficiency of ABLSim is a little surprising to me (if I don't miss important details). As defined by Line 147, isn't $A$ exponentially huge in terms of the length of $z$? If so, shouldn't the max operation in Eq.(1) be very time-consuming? The Cartesian product in Line 6 of Algorithm 1 would make it further slower. The authors state in Line 203~205 that ABLSim could be accelerated by GPU and parallel computations. Could the authors elaborate on it? Besides, how much efficiency gain is brought by the parallel computations during beam search? I quickly went through the submitted code and found that multiprocess parallel is used during abduction ("abducer.py"). I was wondering how ABLSim would perform without such multiprocess parallel computations.
limitations_and_societal_impact: The comparison between ABLSim and baselines is a little unfair because ABLSim uses pretrained feature extractor and multiprocess parallel computations to speed up the search in abduction. The authors might perform a more fair comparison as suggested in the main review.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: In the setting of neuro-symbolic approaches, this paper defines new consistency measures for improving the performance of abductive learning. The overall ABLSim framework uses two key components: a perception model $f$ that maps raw data instances $\mathbf x$ into symbolic instances $\mathbf z$, and a knowledge base $KB$ used to reason about symbolic instances $\vec z$, together with observed labels $y$. The goal of abductive learning is to revise the predictions made by the perception model $f$ according to the logic reasoning; notably, if a given label $y$ cannot be a logical consequence of $KB$ and a predicted instance $\mathbf z$, then by abduction the knowledge base $KB$ provides a set of new candidates $\mathbb A$. Since $\mathbb A$ can include multiple candidates, the key idea of this study is to choose the best ones using a ranking approach (Algorithm 1), together with consistency measures combining similarity scores and confidence scores (12). The ABLSim framework is validated in various experiments.

main_review: The topic of abductive learning is well-motivated, and the experimental results look promising. Unfortunately, I am not convinced that the paper can be accepted in its current state, due to many technical issues.  

(i) The key bottleneck of abductive reasoning lies in the complexity of inferring and enumerating explanations. Virtually nothing is said about these critical issues. Namely, given a first-order knowledge base $KB$ and a fact $y = 1$, what is the computational complexity of inferring a candidate $\mathbf z$ such that $KB \land \mathbf z \models (y = 1)$? To this very point, I guess that the authors have used a restricted (and decidable) fragment of first-order logic for the language upon which $KB$ is defined. More generally, since $\mathbb A$ can be of exponential size (this is indeed the case even for propositional Horn formulas), does there exist an output polynomial algorithm for enumerating from $KB$ the candidates in $\mathbb A$?

(ii) Several notions are incorrectly defined or left unspecified. For example, what is the beam width $b$ in Algorithm 1? What is the meaning of the expression $\mathrm{TopN}(\mathbb A, \mathit{score}, b)$? What is the meaning of $\mathrm{Update}(f, \mathbf X, \mathbf Z)$ ... Namely, how do we update the learning model $f$? When the denominator in (3) or (4) is zero, the expression (5) is left undefined. The explanation “we use the average inter-class/intra-class distance of other $x_j$ as the estimated distance of $x_i$” is a bit confusing; it would be preferable to reformulate (5) using the equality in Line 156. 


(iii) Finally, Algorithm 1 requires exponential space, due to the fact that Line (5) computes sets $\mathbb A_k$ of (possibly) exponential size, together with the fact that Line (6) builds a Cartesian product of these sets. To this very point, I do not think that $\mathbb A_k$ should be stored, since each candidate can be evaluated on the fly according to (12). In other words, the exponential space required by Algorithm 1 is not necessary. This observation is connected to the idea of "parallelizing" the algorithm, which is suggested in the SM. But the algorithm should be rewritten properly in order to clarify the fact that its space complexity remains polynomial in the size of the input dataset and knowledge base.


limitations_and_societal_impact: As mentioned by the authors, the fact that $KB$ must be given in advance is a limitation in abductive learning. Based on the preview,  I would also say that an exponential space algorithm is also a key limitation.
review_title: null

Meta-review: There were two main concerns with this paper --- the algorithm requires exponential space and a concern about the fairness in the experimental results.  I am not worried about the worst case exponential space requirement of the exact algorithm.  Many algorithms have bad worst case behavior while having fast and effective approximations (as several reviewers note).  The one low score on this paper is due to the exponential space issue. Also, the discussion of the fairness of empirical comparisons convince me that this is an issue in the clarity of the writing rather than a fundamental issue with the paper.
Decision: Accept (Poster)