Fast Abductive Learning by Similarity-based Consistency Optimization
Authors: Yu-Xuan Huang
Wang-Zhou Dai
Le-Wen Cai
Stephen Muggleton
Yuan Jiang
Venue: NeurIPS 2021 Poster (2021)
Keywords: abductive learning
abduction
symbolic learning
neuro-symbolic learning

Abstract: To utilize the raw inputs and symbolic knowledge simultaneously, some recent neuro-symbolic learning methods use abduction, i.e., abductive reasoning, to integrate sub-symbolic perception and logical inference. While the perception model, e.g., a neural network, outputs some facts that are inconsistent with the symbolic background knowledge base, abduction can help revise the incorrect perceived facts by minimizing the inconsistency between them and the background knowledge. However, to enable effective abduction, previous approaches need an initialized perception model that discriminates the input raw instances. This limits the application of these methods, as the discrimination ability is usually acquired from a thorough pre-training when the raw inputs are difficult to classify. In this paper, we propose a novel abduction strategy, which leverages the similarity between samples, rather than the output information by the perceptual neural network, to guide the search in abduction. Based on this principle, we further present ABductive Learning with Similarity (ABLSim) and apply it to some difficult neuro-symbolic learning tasks. Experiments show that the efficiency of ABLSim is significantly higher than the state-of-the-art neuro-symbolic methods, allowing it to achieve better performance with less labeled data and weaker domain knowledge.

Fast Abductive Learning by Similarity-based Consistency Optimization
Yu-Xuan Huang', Wang-Zhou Daï Le-Wen Cai', Stephen Muggleton', Yuan Jiang'
National Key Laboratory for Novel Software Technology
Nanjing University, Nanjing 210023, China
(huangyx, cailw, jiangy) nju. edu.
Department of Computing, Imperial College London, London SW7 2AZ, UK [w. dai, 8. .mmggletonneimmerriaa. aa..riialla..............
Abstract
To utilize the raw inputs and symbolic knowledge simultaneously, some recent neuro-symbolic learning methods use abduction, i.e., abductive reasoning, to inte- grate sub-symbolic perception and logical inference. While the perception model, e.g., a neural network, outputs some facts that are inconsistent with the symbolic background knowledge base, abduction can help revise the incorrect perceived facts by minimizing the inconsistency between them and the background knowledge. However, to enable effective abduction, previous approaches need an initialized per- ception model that discriminates the input raw instances. This limits the application of these methods, as the discrimination ability is usually acquired from a thorough pre vre-training when the raw inputs difficult to classify. In this paper, we propose a novel abduction strategy, which leverages the similarity between samples, rather than the output information by the perceptual neural network, to guide the search in abduction. Based on this principle, we further present ABductive Learning with Similarity (ABLSim) and apply some difficult neuro-symbolic learning tasks. Experiments show that the efficiency of ABL.Sim is significantly higher than the state-of-the-arr art seeub--ymmbllc methods, allowing achieve better performance with less labeled data and weaker domain knowledge.
Introduction
To address the limitations of current machine learning methods, the next generation of Artificial Intelligence calls for the integration of data-driven machine learning and knowledge-driven reasoning such as logic inference [T]. Souro-Symboolc Learning [8, [2,22 and Statistical Relational AI (23) are representative works in this direction. However, most of these approaches try to approximate logical calculus with differentiable functions using distributed representations in a neural network, and train the model in end-to-end manner, which usually demand large number of labeled data.
is novel framework attaching machine learning models first- order logical reasoning model while preserving the full expressive power of each side: The machine learning model learns to convert raw input data (e.g.. images, text) into symbolic representations, and the logical model tries to reason about them. Because ABL allows full-featured logical reasoning, it can directly consult symbolic background knowledge bases and reduce requirement for massive labeled data. The logical reasoning model adopts abductive reasoning [20), or abduction, to search for the labels of the unlabcled instances, which are used for updating the machine learning model. Because abductive reasoning is non-deterministic, for each unlabeled instance there could be multiple abduced labels. To choose the best labels, one needs to minimize the inconsistency between the abduced labels and the symbolic background knowledge.
Abductive Learning (ABL)
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Hence, a well-designed consistency measure improves the quality of the abduced labels and leads to a high- perfforrromme model. For example, some approaches take the consistency score as the size of the largest subset of unlabeled examples with abduced labels that are consistent with knowledge base, leading to a subset-selection problem that is difficult to solve [5] [9]; some other works measure the confidence of the predicted labels by the perceptual machine learning model, which could be unreliable when the model is under-trained [19 2.22
According to its definition, abduction refers to the process of inferring specific facts that give the best explanation to observations based on background knowledge [20). Hence, not only the symbolized information the labels predicted by perception model and the symbolic background knowledge base, but also the observed raw representation of the imputs contribute to the goodness of abduced labels. For example, when babies start learning an unknown language, although they could not make sense of the acoustic syllables in sentence, they can amazingly learn from a handful of examples and understand a few words by distinguishing different sound patterns (raw representation) as well as identifying frequently occurred syllable combinations (symbolic relations)
Inspired by this phenomenon, we develop a similarity- 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. It can be regarded as the clustering initialization for the perception model [29], and then the metric for clustering in embedding space is improved when the model gets updated by the abduced labels during training. Applying this principle, we propose ABductive Learning with Similarity (ABLSim), which adopts beam search solve the optimization problem of finding the best abduced labels. We verify the effectiveness of ABLSim on four neuro-symbolic tasks. Compared with other methods, ABLSim can abduce higher quality labels for unlabeled data and accelerate the model training, bringing a significantly better performance. Moreover, even when we increase the difficulty of abduction by removing some rules from the knowledge base, ABLSim still achieves comparable results as the other abduction-based neuro-symbolic learning methods with a full knowledge base.
2 Related Work
Neuro-symbolic (NeSy) learning g 22 proposes to enhance machine learning with symbolic reasoning. It tries learn the ability for both perception from the environment and reasoning from what has been perceived. Most of the approaches model this pipeline with an end-to-end deep neural network, in which a symbolic domain knowledge base used for building the structure of neural networks 8, 25, 10 24 (27). However, most of these methods replace the symbolic representation with distributed representation and approximate logic inference with fuzzy operations. As consequence, they usually require a large amount of labeled training data and are difficult to extrapolate.
Probabilistic Logic Program (PLP) 6 and Statistical Relational Learning (SRL) 15 23 supply symbolic models with a probabilistic semantic and preserve the logical formulation. PLP extends first-order logic to accommodate probabilistic groundings to include probabilistic inference; SRL tries to leverage domain knowledge to construct a probabilistic graphical model structure for statistical inference. They usually require direct semantic level input and are difficult to be applied to raw input data such as images. A typical exception this area is DeepProbLog (2T). which unifies probabilistic logical inference with neural network training by gradient descent. However, due to the exponential complexity of the probabilistic distribution on the Herbrand base, the probabilistic inference in these methods could be inefficient for complicated tasks.
Recently, some approaches leverage abduction train machine learning and perform logical reasoning simultancously, c.g., the Abductive Learning (ABL) [5] framework. ABL uses machine learning models to predict pseudo-labels for the unlabeled data, and then uses first-order logical abduction to revise them and update the machine learning model. The abduction searches for set of revised pseudo-labed to minimize the inconsistency between data and knowledge base. However, when the model is under-trained, the revision becomes difficult because the predicted pseudo-labels are mostly incorrect, and the abduction could be easily trapped in local optima 4 2 The Neural- Grammar-Symbolicc model (NGS) [9 shares similar idea of abduction. It takes context-free free grammar as the knowledge base and uses Markov Chain Monte Carlo (MCMC) sampling to revise the pscudo-labels according to their posterior, which suffers from the same problem when the neural
2

---

Automobile:1
Plane:2
Dog:9
Minimal
2+5-11
Inconsistency
2+8-10
Reason
1+9-10
2. Abduce
2+9-11
Update
Knowledge
Abduced Labels
Model
Base
Knowledge Base
Model
Predict
1+1-2
1. Predict
2-9-10
Pabudo-Labels
(a) Inference.
(b) Learning.
Figure 1: An example of the inference and learning process of ABL. In the inference process, the input data decimal equation represented by several CIFAR-10 images, e-g-, the images "plane" represent digit "automobile" for digit 2, "dog" by the perception model and the knowledge base. In the learning stage, the reasoning model abduces several consistent revised houdo-labell, and searches for the best one by minimizing the inconsistency, which are then used to update the perception model.
digit 9. final output the reasoning result on both symbols predicted
network is under-trained Different from these approaches, ABLSim considers the similarity between input examples in the feature space rather than the output space.
Abductive Learning
3.1 Inference
The Abductive Learning (ABL) framework contains perception model and a reasoning model. The perception model is used for mapping the raw input data æ E X' into discrete symbols C 2, where X' is the imput space and Z is the output space the perception model; æ and x are the input example and extracted symbols, respectively, where meaningful instances detected from æ and the corresponding symbolic labels. For the cxample in Figure 1, input image of the equation is the segmented instances of CIFAR-10 10 images and operation symbols are z;; the sequence of predicted equation string is 2, with each of its characters 23 whether the equation satisfies K B is denoted y True or y False.
{ .2....} and {21, 22, ...} } are the bags of
The reasoning model contains knowledge base KB first-order logic rules, which receives symbols z and reasons about the final output y. Note that 2 and y are subsets of the Herbrand base of K B, i.e., elements Z U are ground facts of the predicates defined K B. For example, given the symbolic rules of decimal arithmetic. the reasoning model would output ground fact y = True when the input fact is ="1+1=2", and a ground fact False when input is =1+9=100" Figure ((a) gives example of the inference process in the CIFAR-10 Decimal Equation Decipherment task (cf. Section 6.3
3.2 Abductive Reasoning
Abduction (i.e. abductive reasoning) 14 20 is basic form of logical inference that seeks the best explanation for observations based on implication. It is a non-deterministic process that may have multiple answers. For example, when observing an arithmetic puzzle "dog cat 2". based on our background knowledge in mathematics, we could explain it with three abduced facts: "dog 0 cat 2".
"dog cat 1", "dog 2 A cat
3.3 Learning
Formally, given unlabeled data X =x (2) ...). the knowledge base KB and the final desired output Y (1) (/1)),22)) ,2.))...)) the target is to learn a perception model f X' Z that accurately predicts the labels of the input instances that together with K entails y. Since we do not have any supervision call pseudo-label just like in weakly-superviser learning (28).

---

The ABL framework involves three steps predict pseudo-labele abduce revised labels and update the model. First, the perception model used obtain the symbolic predictions = f(x) as pseudo-labels. Then ABI. revises the pseudo-labels Z to E by abductive reasoning. Usually, there are several candidates that are consistent with K B. The reasoning model abduces the most likely correct pseudo-labels E under the principle of minimal inconsistency between the data and knowledg base. Finally, ABL treats the z as ground-truth labels to update the perception model, and the above routine repeats iteratively.
Figure [(b) gives an example, where the ground -tunt labels of the input are "2+9=11" and y = True. The perception model f predicts the wrong pseudo-labels ="2+9=10". After minimizing the inconsistency in abduction, ="249=11" selected as the final revised label update f.
3.4 Consistency Measure
Consistency measure for abduction plays important role in ABL. is used to guide the search of the abduced labels from the set of consistent candidate labels = {z K = v}, where } means logical entailment. Because Σ will be treated as ground-truth to update the perception model, whether and how the model improves mainly depends on the design of this consistency measure. Current consistency measures mainly depend on the model's output labels or confidence, which could perform poorly when f inaccurate or not properly initialized 2 experiments in 6
We verify this in our
4 The Similarity- Consistency Measure
We propose a similarity based consistency measure for abduction, which takes the idea that samples in the same category are similar feature space while samples of different classes are dissimilar. is motivated by how humans perform abductive reasoning. Take the example in Figure [(b) If we misclassified the last image to digit 0 and the prediction becomes "2+9=10", which is inconsistent with the knowledge base. Revisions "149=10", "2""=1110"""0 "2+8=10" and "2+9=11" are all consistent revisions.
By looking at the images directly, we could observe that the last two images are similar, while other pairwise combinations of these images look quite different. Therefore, the last two images probably share the same label. Finally, we conclude that "2+9=11" are the most likely correct labels, which could be regarded as the best abduced labels.
Given the final output y and knowledge base KB, let A be the set of all consistent candidates by abductive reasoning, i.c., A = { KB U z - y}. The consistency optimization problem is equivalent to selecting the best revised labels z in A, which can be formalized as follows:
max SEA
SimilarityScore(an
where the SimilarityScore measures the consistency of the revised labels z. We define the consistency the average difference between each sample's inter-class distance and intra-class distance:
SimilarityScore (a, x)
[InterclassDis(z,, x) IntraclassDis(z;, 2)).
(2)
E.E
The inter-class distance Interclass siterllassDi((r,,, Dis(,, z) of sample x; stands for the average distance of other instances zy that have different revised labels as zı while the intra-class distance IntraclassDis(a;, z) defines the average distance of other instances zy that have the same revised labels as F;, i...
InterclassDis((;,
Σ
Dis(2,,
(3)
Dr,
myEDi,
Intraclass Dislla,
Dis(
(4)
S
Jy E
where Dr,g = (ay 2 + Ei, i is the set of instances whose labels are different from x; xs's, and S = (r, Σj 2, o i) is the set of the other instances that share the same revised labels as 2;, Note that TD,, U Si,z Uu; = n. Dis(a,, my) is the distance between v; and Wys which will
be explained later. If Dis |= or S |= O, where the denominator becomes 0, we use the

---

Algorithm ABLSim Learning
Input: Unlabeled data X = (xx xx x ); Final output (y y²²²
ymm))
Current model ʃ: Knowledge base K B; Beam width (beam size of beam search)
Output: Model f
for 1 to I do
2:
A <- [ # the candidate labels
3:
for k
m do
4:
z (A) < ((x(k)) # generate pseudo-labels
5:
A (R) + Abduce(KB,, ) # abduce all consistent revised pseudo-labels
6:
A - A x ( Cartesian product
7:
< x k)
8:
score < []
# the score of each candidate labels
9:
for E A do
10:
score www.e.pppendSSore((CC 2)) # get the score of candidate labels according to Eq.
11:
end for A + TopN A score, b) # select "b' candidate labels in A with the highest score
12:
13:
end for
14:
Z TopN(A, score, 1) select the label in A with the highest score
15:
f f Update X, Z)
# update model f using data X and abduced labels Z
16:
end for
average anter-class/ittr--llas distance of other as the estimated distance of The details on the calculation when the denominator becomes 0 shown the supplementary material.
Combining the similarity-based consistency measure optimization problem becomes:
max SEA
Σ EDE
Dis(r;,
Dis(Ii,
(5)
D
Si,z
Exr
The distance Dis xyy in (3) (3-(5) measures the similarity between instances x; and zj. where the higher the similarity, the smaller the distance. It can be represented as follows:
Dis(s,, Distance(d(x;), o(x,))
(6)
where e is the feature map function. For example, for images or text, we can use a neural network as á to extract the embedding for samples; for tabular data, can be the normalization function. In practice, we can use any appropriate metrics (6. this work, we use the cosine distance in our implementation, i.c., Dis(x,, x,) Cosine Distance(((za) o(zz)).
Obviously, maximizing the score in means maximizing the average gap between Interclass Dis(z, &) and Intraclass Dis(: 2). In other words, among all revised labels candi- dates that are consistent, the one with large inter-class distance and small intra-class distance preferred.
Calculating the similarity between instances does not depend on any supervised training. Hence, one could use any unsupervised learning approaches to obtain good & without accessing any label implicit clustering initialization
information 3 7 This consistency measure be regarded on the output space of function & [29]. In addition, if we use the perception model f's embedding layer as the function @ the & and the distance measurement could be further improved during the subsequent neuro-symbolic learning and accelerates the abduction reasoning.
Abductive Learning with Similarity
Based on the proposed consistency measure, we present the Abductive Learning with Similarity (ABLSim) approach, which is optimized through greedy beam search. And then we show that ABI.Sim can simply combined with other consistency measures to enhance abduction-base neuro-symbolic learning, Algorithm shows outline of ABLSim.
5

---

First equation
Second equation
Third equation
0.66
1+1-2
digit
1+2=3
0.73
1+2=3
0.79
X digit
0+4=4
0.64
2+1-3
0.83
digit
2+9-11
0.67
1+1=2
0.62
2+2=4
0.72
2+8=10
0.55
digit 1
1+9=10
0.52
1+3=4
0.60
0.61
plus
3+8=11
0.63
1+2-3
0.64
0.67
2+1+3
0.62
equal
1+1=2
0.58
2+2-4
0.60
Meanings of images
Revised labels candidates and their scores
Figure 2: An example of beam search in ABLSim. It involves three unlabeled and consistent equations whose
ground-truth labels are "2+9=11", "1+2=3", "2+1=3", and the beam width is 2. In the first iteration, after computing the scores, "2+9=11" and "3+8=11" are kept the candidate set. In the second iteration, "2+9=11 1+2=3" and "348=11 0+4=4" rank top among all candidate revised labels, while other candidates pruned. the last iteration, we get final abduced label "2+9=11 142=3 2+1=3" according to computed scores of consistency measure.
5.1 Optimization
One possible situation when applying ABL.Sm is that the number of instances in x is usually small, and for some example (k) there is no (i,j) such that 2(() 2 making it challenging to calculate the intra-class distance. For For example in Figure [(b)] the size | 6, and for the revised pseudo-labels candidate ="2+9=11" we could not measure the intra-class distance of the first image I1 because there is other sample zy whose revised label ž is digit 2. Moreover, even if instances with the same revised label exist, the average distance may deviate due to limited samples.
To get sound and reliable score for consistency measure, we borrow some more samples to conduct the abductive reasoning. Assume that there are m examples, denoted as a (1) (x) ... x (mm) Each example (k) has a corresponding final output (² and the candidate set of revised labels is A (k), labeled data exists, can also be regarded as bags of instances, whose candidate pseudo-label set A (k) contains only the ground-truth labels. Let X (xx11,, _ (m)) ) be the of input examples, and Z (=(1) (22) ... z(m) be the set of corresponding bags of abduced labels. If Z is consistent with knowledge base, it should be element of the Cartesian product of A (R) i.e., Z E A (1) X A (2) ... A (m)) The abduction problem for set X can be formalized as follows:
Score X, 22)).
max 2
s.t.
X (1) (2)
(m))
(8)
Z E A (1) A (2)
A (m²)
(9)
(K) {z KBU 30)
(10)
This is combinatorial optimization problem where the search space Z grows exponentially with m. ABLSim uses beam search to solve this optimization problem greedily. Eventually, the element with the highest score the final candidate set will be selected as the best abduced labels.
Figure gives an example of the beam search in AimSim in the CIFAR-1O Equation Decipherment task. There are three unlabeled examples (!)) (2) x (3) consistent with the knowledge base and the beam width b 2. In each iteration, ABLSim keeps the top-2 candidates ranked by their scores. The final abduced label is Ž -2++9=11 1+2=3 2+1=3",, which is the ground-truth label.
The above ABL.Sim algorithm could be accelerated by GPU and parallel computations. The basic idea that the score of each candidate label A (ef. Line 9-10 in Algorithm) I can computed separately, and we formulate the calculation as matrix operations for parallel computations with GPU.

---

Table 1:
Image test accuracy and convergence time of different methods. The convergence time stands for the time taken to accuracy 95% in handwritten images and 85% for CIFAR-10. NGS-dft stands for NGS with default parameters, and NGS-opt for the fine-tuned optimal parameters, We set the time limit to 10 hours for all tasks. indicates ABLSim is significantly better than compared methods (paired t-tests at 95% significance level)
Method
Addition
Addition (CIFAR)
HWF
HWF (CIFAR)
DoepProbLog
9
21.6=1.70
32.2:10.6
15.2+2.6
NGS-dft
39.9154.1
38.7:35.1
99.610.2
23.8 6.
Acc/ /%
NGS-opt
98.5+1.33
88.7=0.8 68.9-+0.5
99.620.2
66.0:t14.5
ABI .Sim (ours)
98.8++0.1
99.9+-0.1
88.4+-0.7
DeepProbl og NGS-dft
396+3
time out time out 6954+558 6066-799
time out
time out time time out 7263++122 122
time
299+-36
Time /s
NGS-opt
46+4
240+7
ABLSim (ours)
42+55
130++
During the beam search, the score of each is updated incrementally based the previous results, which further reduces the memory and time consumption. Please refer to the supplementary material for details.
5.2 Combining Similarity and Confidence in Consistency Measure
ABL.Sim can also combined with other consisteney measures. For example, the confidence score of revised pseudo-label E could be defined as follows:
ConfidenceScorc(z, 2)
II .r
Confidenco(1;; Z)).
(11)
where Confidence(2;, 2,) indicates the confidence that sample x; belongs to label 2
Combining and (1I.. get the final score for ABLSim's consistency measure:
Score x. z) SimilarityScore(r.. x) + (1 - 0) ConfidenceScore(zz.22
(12)
where A E IR is the weighting coefficient. The similarity score and confidence score need to be normalized before computing the final score.
6 Experiments
This section presents the experimental results on four neuro-symbolic tasks, including two benchmark datasets and two hard tasks with increased perception difficulty, demonstrate that ABLSim can perform more efficient and effective abduction than previous nate-of-the-an methods by leveraging the similarity among samples. Furthermore, we verify whether can help the perception model learn faster and achieve better performance with less labeled data and weaker domain knowledge. All experiments are repeated five times server with Intel Xeon Gold 6248R CPU and Nvidia Tesla V100S GPU. In experiments, we simply fix the coefficient 0 of ABLSim to 0.96, though it may be better let vary with training. The hyperparameterss of ABLSim are determined by validation on training data. The code is available for download
6.1 MNIST (CIFAR-10) Addition
This task was first introduced in (21), the inputs pairs of MNIST [17 images and the outputs their sums. We also prepare a hard version of this task by replacing the MNIST images with CIFAR- 10 [16] images. We compare ABLSim with the Siiral-Grammar-SS
(NGS) model [19 (with default and fine-tuned parameters) and DeepProbLogg (2T]. All methods share the same knowledge base and perception model (LeNet (17] for MNIST and ResNet-50 [12] for CIFAR-10), which
initialized randomly. The feature for calculating the similarity score is obtained from the second last
layer in the perceptual neural net.
Table shows the experimental results. In the MNIST Addition task, all methods except NGS-dft converge. DeepProbLog converges slowly because computing gradients of the probabilistic logic

---

program is time- conneminn..nn The performance of NGS-dft is greatly affected by initialization. which leads to large standard deviation in the table. For the CIFAR- version, DoepProbLog and NGS dit fail to converge, while NGS-opt converges slower than ABLSim, which solves all tasks efficiently and achieves higher accuracy.
6.2 Handwritten Formula Recognition
The HWF dataset 19 contains images of decimal formulas and their computed results. We also
create (perceptual) harder version by replacing the digit images with CIFAR-10 [16] images.
The perception neural networks are initialized randomly for all methods. Note that the HWF in the original paper of NGS includes length-one equations as a pre- pre-training curriculum, which are deleted in our experiments. Thus our results are different from those in [19
As shown Table [ ABLSim significantly outperforms others by time efficiency and predictive accuracy. Because the background knowledge is the same, this result verifies the benefit of leveraging the similarity-base consistency optimization. Both NGS and DeepProbLog are trapped in local minimum and fail converge in the hard version tasks, this is probably caused by the unreliable confidence output from the perception neural network when it is not pre-trained.
6.3 CIFAR-10 Decimal Equation Decipherment
6.3.1 Dataset and Knowledge base
This task is the most challenging one in our experiments, which extends the Digital Binary Additive equations experiment in ABL [5] with decimal digits. The input contains images of an arithmetic equation and the output is the label of its correctness. Instead of learning binary equations represented example
by MNIST images, here we use CIFAR- 10 [66 images to encode decimal equations. of this dataset is shown in Figure The task's inputs are sequential images of randomly generated decimal equations, which consist of twelve symbols (0,1,...,94 ,9,+.)). Besides, the knowledge base contains symbolic rules about how to carry out decimal addition operations. The correctness labels (True or F False) training equations are provided in the form of logical facts.
6.3.2 Experimental Setup
We compare ABLSim with four baselines: 1) ABL: Abductive learning [5] that maximizes consistency with minimal revisions. If multiple abduced labels have the minimal revisions, it would randomly select one. 2) ABI-Coof: Abductive learning that measures consistency using only the confidence predicted by neural net, i.e., 0 0 in equation ) 3) ABL-pre-train: ABL with model pre- trained on a small set of labeled images. 4) ABL--Coff-pre-rraie
ABL-Conf with a pre-trained network. ABLSim uses the perception model's embedding layer to calculate the similarity. For the non-pre-trained methods, including ABLSim, the perception model, ResNet-50 [[2), is initialized by self-supervised learning (3] on training images. Note that this process is unsupervised and does NOT use any image labels.
6.3.3 Results
Learning Curve. The learning curves of all models are shown in Figure 3(a). The proposed ABLSSm converges much faster and achieves higher accuracy than other methods. ABL-Conf and ABL fail to converge and get low accuracy because their abduction processes are based on the pseudo- labels or label confidence predicted by the perception model, which are unreliable when there lacks supervised pre-train. Both ABL and ABL-pre-train are inferior to their "-Conf" versions, indicating that pseudo-label confidence is helpful. Starting from high initial accuracy, ABL-CCoffpre--ree gets similar accuracy ABLSim, but it converges slower than our presented ABLSim, which learns without any supervised pre-training and has the fastest converge rate.
Rate of Successful Abduction. Figure illustrates the curves of different methods' abduction success rate, i.e., the proportion of the correctly abduced labels. ABLSim converges faster and achieves a nearly optimal result, where the abduced labels are exactly the ground-truth labels. the first few iterations, the abduction success rate is relatively low, However, the extracted embeddings of
8

---

(c) 1st iteration
60-
AB15
60:58m
40-Corf
ABL Protrn
30
20
30
50
60
30
20
60
76
(a) Perception model test accuracy.
(b) Rate of successful abduction.
(d) 10th iteration
Figure 3: Learning curves and the t-SNE visualization of the learned embeddings d).
Table The rate successful abduction w.r.t. different beam width the first itcration.
Beam Width
16
32
64
128
256
512
1024
2048
Successful Abductions
62%
63%
65%
71%
72%
73%
75%
75%
images are gradually improved during training, which provide better similarity metric for abductive reasoning. Therefore, the rate of successful abduction reaches 1.0 just few iterations.
Embedding Visualization. To verify whether the extracted embeddings of neural network are improved during training, we plot t-SNE [26) visualizations on the second last layer of neural network that we use for calculating the consistency score. As shown Figure ((c))(d), the beginning. the embeddings of classes are not well separated. However, during abductive learning, the distance between the different classes becomes larger after the neural net updated with the abduced labels, which will in turn help accelerate the abduction.
Influence of Beam Width. We study the influence of beam width in optimization, and the results are presented in Table The successful abduction increases beam width becomes larger, while the time cost grows linear at the same time. The improvement becomes marginal when the beam width is larger than 1k. We use beam width of 600 in our implementation achieve the balance between convergence rate and time complexity.
6.4 Theft Judicial Sentencing
Table 3: Micro-Fl-score of the model, and
This is a real-world task in [13] which aims to train model that outputs sentencing elements from criminal judgment texts, and optimize the parameters in knowledge base to predict the sentence of a defendant. We use same knowledge base and BERT model 7 as in [[3] where the knowledge base contains many law articles rep- resented by logic rules. We additionally make the task more challenging by removing some pre-defined rules to weaken the background knowledge base [1]
MAE of the predicted sentence. The label rates denoted as suffixes.
KB
Method
F1
MAE
N/A
PL-10
0.814
0.862
N/A
Tri-10
0.812
0.840
Full
SS-ABL-10
0.862
0.824
Full
ABLSim-10
0.861
0.825
Part
SS-ABL-10
0.833
0.835
We compare ABLSim with SS-ABL [3 and two semi- supervised methods Pseudo-Label
Part
ABLSim-10
0.851
0.828
(PL) (18) and Tri-
training (Tri) [30] It takes about hour to train the model. As shown in table 3 ABL-based models are superior to the semi-supervised methods. When the number of la- beled pre-train data is small (10%), the performance of ABLSim with weaker KB is even comparable to the SS- 0.786
N/A
PL-50
0.858
0.832
N/A
Tri-50
0.861
0.810
Full
SS-ABL-50
0.865
0.788
Full
ABLSim-50
0.866
Part
SS-ABL-50
0.862
0.803
ABL with a full KB. When the number of labeled pre-train data increased to 50%, ABI Sim achieves the highest per- formance with less pre-defined domain knowledge.
Part
5BL
0.866
0.783

---

7 Conclusion
In this paper, we propose a novel consistency measure for abduction-basee based neuro-symbolic learning. and further present the Abductive Learning with Similarity (ABLSim) method. Compared to previous approaches, it not only exploits the full-featured logical reasoning ability, but also utilizes the information hidden in the feature space of the input data. The proposed consistency measure leverages the similarity between samples, which previous approaches have never considered. Empirical evaluation validates that ABLSim significantly outperforms the ofate-of-the-ar neuro-symbolic learning approaches in terms of speed and performance with less labeled data. The proposed consistency measure is general, and any other abduction-based approach the method that the rules of the domain knowledge hase need to be constructed manually. In future work, we will try to incorporate techniques like predicate invention into approach to discover new classes and new knowledge, so that we can automatically extend the knowledge base.
use it. The limitation of
Acknowledgments and Disclosure of Funding
This work is supported by the National Key Research and Development Program of China No.2020AAA0109400 Wang-Zhou Dai acknowledges the financial support from the UK's EP- SRC Robot Synthetic Biologist Project (EP/R034915/1) Stephen H. Muggleton wants to thank the support from EPSRC Network Human-Like Computing (EP/R022291/1).
References
[1] Yoshua Bengio. The consciousness prior. arXiv preprint 1709 2017.
[2] Le-Wen Cai, Wang-Zhou Dai, Yu-Xuan Huang, Yu-Feng Li, Stephen Muggleton, and Yuan Jiang. Abduc- tive learning with ground knowledge base. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI). pages 1811, 2021.
[3] Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 1597-1607, 2020.
Wang-Zhou Dai and Stephen H. Muggleton. Abductive knowledge induction from data. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 1845-1851, 2021.
[5] Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging machine learning and logical reasoning by abductive learning. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 281 2811-2822. 2019.
[6] Luc De Raedt and Angelika Kimmig. Probabilistic (logic) programming concepts. Machine Leurning. 100(1):5-47 2015.
[7] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirec- tional transformers for language understanding. arXiv preprint arXiv: 1810,04805, 2018.
[8] A Garcez, M Gori, LC Lamb, L Serafini, M Spranger, and SN Tran. Neural-symbolt computing: An effective methodology for principled integration of machine learning and reasoning. Journal of Applied Logics, 6(4):61 1-632, 2019.
[9] Rebecca Gómez and LouAnn Gerken. Infant artificial language learning and language acquisition. Trends in cognitive sciences, 4(5):178-186, 2000.
[10] Alex Graves, Greg Wayne, Malcolm Reynolds, et al. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626):471-777 2016.
[11] Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In Sixth International Conference on Learning Representations (ICLR), 2018.
[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
10

---

[13] Yu- Xu-X Huang, Wang-Zhou Dai. Jian Yang, Le-Wen Cai. Shaofen Cheng, Ruizhang Huang, Yu-Feng Li. and Zhi-Hua Zhou. Semi-supervised abductive learning and its application theft judicial sentencing. In Proceedings of the 20th IEEE International Conference on Data Mining (ICDM), pages 1070-1075. IEBE, 2020.
[14] John R Josephson and Susan G Josephson. Abductive inference: Computation, philosophy, technology. Cambridge University Press, 1996.
[15] Daphne Koller, Nir Friedman, Saão Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Pieter Abbeel, Ming-Fai Fai Wong. David Heckerman, Chris Meek, et al. Introduction to statistical relational learning. The MIT Press, 2007.
[16] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[17] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(1 1):22788-2223 2324,, 1998.
[18] Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In ICML Workshop on Challenges in Representation Learning, 2013.
[19] Qing Li. Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song-Cling Chun Zhu. Closed loop nemral-symbolic learning via integrating neural perception, grammar parsing. and symbolic reasoning. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 5884-5894. PMLR, 2020.
[20] Lorenzo Magnani. Abductive cognition: The epistemological and eco-cognitive dimensions of hypothetical reasoning, volume Springer Science & Business Media, 2009.
[21] Robin Manhacve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in Neural Information Processing Systems 31 (NeurIPS), pages 3749 3759, 2018.
[22] Luc De Raedt, Sebastijan Dumancic, Robin Manhaeve, Giuseppe Marra. From statistical relational to neuro-symbolic artificial intelligence. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 4943-4950, 2020.
[23] Luc De Raedt, Kristian Kersting. Sriraam Natarajan, and David Poole. Statistical relational artificial intelligence: Logie, probability, and computation. Synthesis Lectures on Artificial Intelligence and Machine Learning, 10(2):1-199, 2016.
[24] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Advances Neural Information Processing Systems 30 (NIPS), pages 4967-4976. 2017.
[25] Andrew Trask, Felix Hill, Scott E Reed, Jack Rac, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. Advances Neural Information Processing Systems 3/ (NeurIPS), pages 8035-8044, 2018.
[26] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, (11), 2008.
[27] Po- Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 6545-6554, 2019.
[28] Zhi-Hua Zhou. brief introduction weakly supervised learning. National science review, 5(1):44-53,
2018.
[29] Zhi- Hua Zhou. Abductive learning: towards bridging machine learning and logical reasoning. Science China Information Sciences, 62(7))76101, 2019.
[30] Zhi-Hua Zhou and Ming Li. Tri-training: Exploiting unlabeled data using three classifiers. IEEE Transactions on Knowledge and Data Engineering. 17(11):1529-155 1541, 2005.
11


Reviews:
[{"review_id": "qopmaeUfFlB", "reviewer": "Reviewer_ZiCC", "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.\n", "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": "The authors propose ABductive Learning with Similarity (ABLSim), which adopts beam search to solve the optimization problem of finding the best abduced labels. \n\nThe paper is well written and the concepts are clear. The proposed approach is novel wrt the other neural symbolic approaches.\n\nThe 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The rules in the BK should be manually defined", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "o_NE3Sh8RwL", "reviewer": "Reviewer_QmdE", "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.", "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": "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "eKgmx27Swlw", "reviewer": "Reviewer_Nytp", "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.\n", "questions": "", "limitations": "", "rating": 4, "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 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.  \n\n(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$?\n\n(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. \n\n\n(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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {"ethical_concerns": "It seems that the \"Theft Judicial Sentencing\" task, examined in Section 6.4. and further detailed in the SM can raise some ethical issues. Indeed, the dataset contains 687 court records of theft, which happened in China during 2017–2018. I think that this dataset has been anonymized with no possible way to identify a person, but this should be explicitly written in a revised version of the paper.  Since the authors have used the knowledge base in [6,12], I believe that this base does not include any reference to some person. But again, this ethical point should be explicitly written in the revised version. "}}, {"review_id": "0VqRd7ZtD5", "reviewer": "Reviewer_jmHQ", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. 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. \n\n2. 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.\n\n3. As shown in Table 1, the proposed framework ABLSim outperforms the state-of-the-art methods in terms of both accuracy and efficiency.\n\n4. The paper is overall well-written and easy to follow.\n\nWeaknesses:\n1. 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.\n\n[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.\n\n[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.\n\n[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.\n\n2. 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

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)