Fast Abductive Learning by Similarity-based Consistency Optimization
Year: 2021

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.

heading: 1 Introduction
text: 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 [1]. Neuro-Symbolic Learning [8, 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 an end-to-end manner, which usually demand a large number of labeled data.
Abductive Learning (ABL) [5, 29] is a novel framework attaching machine learning models to a firstorder 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 the requirement for massive labeled data. The logical reasoning model adopts abductive reasoning [20], or abduction, to search for the labels of the unlabeled 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.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Hence, a well-designed consistency measure improves the quality of the abduced labels and leads to a high-performance 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, 29]; 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, 4, 2].
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 inputs 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 a 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) [9].
Inspired by this phenomenon, we develop 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. 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 to 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.

heading: 2 Related Work
text: Neuro-symbolic (NeSy) learning [8, 22] proposes to enhance machine learning with symbolic reasoning. It tries to 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 is used for building the structure of neural networks [8, 25, 11, 10, 24, 27]. However, most of these methods replace the symbolic representation with distributed representation and approximate logic inference with fuzzy operations. As a 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 in this area is DeepProbLog [21], 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 to train machine learning and perform logical reasoning simultaneously, e.g., the Abductive Learning (ABL) [5, 29] 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 a set of revised pseudo-labels 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 NeuralGrammar-Symbolic model (NGS) [19] shares a similar idea of abduction. It takes context-free grammar as the knowledge base and uses Markov Chain Monte Carlo (MCMC) sampling to revise the pseudo-labels according to their posterior, which suffers from the same problem when the neural
network is under-trained. Different from these approaches, ABLSim considers the similarity between input examples in the feature space rather than the output space.

heading: 3 Abductive Learning

heading: 3.1 Inference
text: The Abductive Learning (ABL) framework contains a perception model and a reasoning model. The perception model is used for mapping the raw input data x ∈ X into discrete symbols z ⊆ Z , where X is the input space and Z is the output space of the perception model; x and z are the input example and extracted symbols, respectively, where x = {x1, x2, . . .} and z = {z1, z2, . . .} are the bags of meaningful instances detected from x and the corresponding symbolic labels. For the example in Figure 1, an input image of the equation is x; the segmented instances of CIFAR-10 images and operation symbols are xi; the sequence of predicted equation string is z, with each of its characters as zi; whether the equation satisfies KB is denoted as y = True or y = False.
The reasoning model contains knowledge base KB of first-order logic rules, which receives the symbols z and reasons about the final output y ∈ Y . Note that Z and Y are subsets of the Herbrand base of KB, i.e., elements in Z ∪ Y are ground facts of the predicates defined in KB. For example, given the symbolic rules of decimal arithmetic, the reasoning model would output a ground fact y = True when the input fact is z =“1+1=2”, and a ground fact y = False when input is z =“1+9=10”. Figure 1(a) gives an example of the inference process in the CIFAR-10 Decimal Equation Decipherment task (cf. Section 6.3).

heading: 3.2 Abductive Reasoning
text: Abduction (i.e. abductive reasoning) [14, 20] is a 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 = cat = 1”, “dog = 2 ∧ cat = 0” or “dog = 0 ∧ cat = 2”.

heading: 3.3 Learning
text: Formally, given unlabeled data X = {x〈1〉,x〈2〉, . . .}, the knowledge base KB and the final desired output Y = {y〈1〉, y〈2〉, . . .}, the target is to learn a perception model f : X 7→ Z that accurately predicts the labels of the input instances that together with KB entails y. Since we do not have any supervision on z, we call it pseudo-label just like in weakly-supervised learning [28].
The ABL framework involves three steps—predict pseudo-labels, abduce revised labels and update the model. First, the perception model f is used to obtain the symbolic predictions z = f(x) as pseudo-labels. Then ABL revises the pseudo-labels z to z̄ by abductive reasoning. Usually, there are several candidates z̄ that are consistent with KB. The reasoning model abduces the most likely correct pseudo-labels z̄ under the principle of minimal inconsistency between the data and knowledge base. Finally, ABL treats the z̄ as ground-truth labels to update the perception model, and the above routine repeats iteratively.
Figure 1(b) gives an example, where the ground-truth labels of the input are “2+9=11” and y = True. The perception model f predicts the wrong pseudo-labels z =“2+9=10”. After minimizing the inconsistency in abduction, z̄ =“2+9=11” is selected as the final revised label to update f .

heading: 3.4 Consistency Measure
text: Consistency measure for abduction plays an important role in ABL. It is used to guide the search of the abduced labels z̄ from the set of consistent candidate labels A = {z̄ | KB ∪ z̄ |= y}, where |= means logical entailment. Because z̄ 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 is inaccurate or not properly initialized [4, 2]. We verify this in our experiments in Section 6.

heading: 4 The Similarity-based Consistency Measure
text: We propose 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. It is motivated by how humans perform abductive reasoning. Take the example in Figure 1(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 “1+9=10”, “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 the 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.e., A = {z̄ | KB ∪ z̄ |= y}. The consistency optimization problem is equivalent to selecting the best revised labels z̄ in A, which can be formalized as follows:
max z̄∈A SimilarityScore(x, z̄), (1)
where the SimilarityScore measures the consistency of the revised labels z̄. We define the consistency as the average difference between each sample’s inter-class distance and intra-class distance:
SimilarityScore (x, z̄) = 1 | x | ∑ xi∈x (InterclassDis(xi, z̄)− IntraclassDis(xi, z̄)) . (2)
The inter-class distance InterclassDis(xi, z̄) of sample xi stands for the average distance of other instances xj that have different revised labels as xi; while the intra-class distance IntraclassDis(xi, z̄) defines the average distance of other instances xj that have the same revised labels as xi, i.e.,
InterclassDis(xi, z̄) = 1 | Di,z̄ | ∑
xj∈Di,z̄
Dis(xi, xj), (3)
IntraclassDis(xi, z̄) = 1 | Si,z̄ | ∑
xj∈Si,z̄
Dis(xi, xj), (4)
where Di,z̄ = {xj | z̄j 6= z̄i, j 6= i} is the set of instances whose labels are different from xi’s, and Si,z̄ = {xj | z̄j = z̄i, j 6= i} is the set of the other instances that share the same revised labels as xi. Note that Di,z̄ ∪ Si,z̄ ∪ xi = x. Dis(xi, xj) is the distance between xi and xj , which will be explained later. If | Di,z̄ |= 0 or | Si,z̄ |= 0, where the denominator becomes 0, we use the
Algorithm 1 ABLSim Learning Input: Unlabeled data X = (x〈1〉,x〈2〉, · · · ,x〈m〉); Final output y = (y〈1〉, y〈2〉, · · · , y〈m〉);
Current model f ; Knowledge base KB; Beam width (beam size of beam search) b Output: Model f
1: for t = 1 to T do 2: A← [] # the candidate labels 3: for k = 1 to m do 4: z〈k〉 ← f(x〈k〉) # generate pseudo-labels 5: A〈k〉 ← Abduce(KB,z〈k〉, y〈k〉) # abduce all consistent revised pseudo-labels 6: A← A× A〈k〉 # Cartesian product 7: x←X[1 : k] 8: score← [] # the score of each candidate labels 9: for z̄ ∈ A do
10: score.append(Score(x, z̄)) # get the score of candidate labels according to Eq. (12) 11: end for 12: A← TopN(A, score, b) # select ’b’ candidate labels in A with the highest score 13: end for 14: Z̄ ← TopN(A, score, 1) # select the label in A with the highest score 15: f ← Update(f,X, Z̄) # update model f using data X and abduced labels Z̄ 16: end for
average inter-class/intra-class distance of other xj as the estimated distance of xi. The details on the calculation when the denominator becomes 0 are shown in the supplementary material.
Combining (1)-(4), the similarity-based consistency measure optimization problem becomes:
max z̄∈A
1 | x | ∑ xi∈x  1 | Di,z̄ | ∑ xj∈Di,z̄ Dis(xi, xj)− 1 | Si,z | ∑ xj∈Si,z̄ Dis(xi, xj)  . (5) The distance Dis(xi, xj) in (3)-(5) measures the similarity between instances xi and xj , where the higher the similarity, the smaller the distance. It can be represented as follows:
Dis(xi, xj) = Distance(φ(xi), φ(xj)). (6)
where φ 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 in (6). In this work, we use the cosine distance in our implementation, i.e., Dis(xi, xj) = CosineDistance(φ(xi), φ(xj)).
Obviously, maximizing the score in (2) means maximizing the average gap between InterclassDis(xi, z̄) and IntraclassDis(xi, z̄). In other words, among all revised labels candidates that are consistent, the one with a large inter-class distance and a small intra-class distance is preferred.
Calculating the similarity between instances does not depend on any supervised training. Hence, one could use any unsupervised learning approaches to obtain a good φ without accessing any label information [3, 7]. This consistency measure can be regarded as an implicit clustering initialization 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.

heading: 5 Abductive Learning with Similarity
text: Based on the proposed consistency measure, we present the Abductive Learning with Similarity (ABLSim) approach, which is optimized through a greedy beam search. And then we show that ABLSim can be simply combined with other consistency measures to enhance abduction-based neuro-symbolic learning. Algorithm 1 shows an outline of ABLSim.
Automobile:1 Plane:2 Horse:3 …
2+8=10
1+9=10
2+9=11
3+8=11
…
1+2=3
0+4=4
1+3=4
1+1=2
…
Revised labels candidates and their scores
1+2=3
0+4=4
1+3=4
1+1=2
…
[]
1+2=3
2+1=3
1+1=2
2+2=4 …
1+2=3
2+1=3
1+1=2
2+2=4 … 0.67 0.55 0.52 0.67
0.66
0.73
0.64
0.62
0.60
0.63
0.67
0.58
0.71
0.79
0.83
0.72
0.61
0.64
0.62
0.60
First equation Second equation Third equation
digit 1
digit 2
digit 3
plus
equal
…
Meanings of images
digit 9
  
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 in the candidate set. In the second iteration, “2+9=11 1+2=3” and “3+8=11 0+4=4” rank top 2 among all candidate revised labels, while other candidates are pruned. In the last iteration, we get the final abduced label “2+9=11 1+2=3 2+1=3” according to the computed scores of consistency measure.

heading: 5.1 Optimization
text: One possible situation when applying ABLSim is that the number of instances in x is usually small, and for some example x〈k〉 there is no 〈i, j〉 such that z̄〈k〉i = z̄ 〈k〉 j , making it challenging to calculate the intra-class distance. For example in Figure 1(b), the size |x| = 6, and for the revised pseudo-labels candidate z̄ =“2+9=11”, we could not measure the intra-class distance of the first image x1 because there is no other sample xj whose revised label z̄j is digit 2. Moreover, even if instances with the same revised label exist, the average distance may deviate due to limited samples.
To get a 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 x〈1〉,x〈2〉, · · · ,x〈m〉. Each example x〈k〉 has a corresponding final output y〈k〉 and the candidate set of revised labels is A〈k〉. If labeled data exists, it can also be regarded as bags of instances, whose candidate pseudo-label set A〈k〉 contains only the ground-truth labels. Let X = (x〈1〉,x〈2〉, · · · ,x〈m〉) be the set of input examples, and Z̄ = (z̄〈1〉, z̄〈2〉, · · · , z̄〈m〉) be the set of corresponding bags of abduced labels. If Z̄ is consistent with knowledge base, it should be an element of the Cartesian product of A〈k〉, i.e., Z̄ ∈ A〈1〉 × A〈2〉 × · · · × A〈m〉. The abduction problem for set X can be formalized as follows:
max Z̄
Score(X, Z̄), (7)
s.t. X = (x〈1〉,x〈2〉, · · · ,x〈m〉), (8) Z̄ ∈ A〈1〉 × A〈2〉 × · · · × A〈m〉, (9) A〈k〉 = {z̄ | KB ∪ z̄ |= y〈k〉}. (10)
This is a combinatorial optimization problem where the search space of Z̄ grows exponentially with m. ABLSim uses beam search to solve this optimization problem greedily. Eventually, the element with the highest score in the final candidate set A will be selected as the best abduced labels. Figure 2 gives an example of the beam search in ABLSim in the CIFAR-10 Equation Decipherment task. There are three unlabeled examples x〈1〉,x〈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 Z̄ =“2+9=11 1+2=3 2+1=3”, which is the ground-truth label.
The above ABLSim algorithm could be accelerated by GPU and parallel computations. The basic idea is that the score of each candidate label z̄ in A (cf. Line 9-10 in Algorithm 1) can be computed separately, and we formulate the calculation as matrix operations for parallel computations with GPU.
During the beam search, the score of each z̄ is updated incrementally based on the previous results, which further reduces the memory and time consumption. Please refer to the supplementary material for details.

heading: 5.2 Combining Similarity and Confidence in Consistency Measure
text: ABLSim can also be combined with other consistency measures. For example, the confidence score of a revised pseudo-label z̄ could be defined as follows:
ConfidenceScore(x, z̄) = 1 | x | ∏ xi∈x Confidence(xi, z̄i), (11)
where Confidence(xi, z̄i) indicates the confidence that sample xi belongs to label z̄i.
Combining (2) and (11), we get the final score for ABLSim’s consistency measure:
Score(x, z̄) = θ · SimilarityScore(x, z̄) + (1− θ) · ConfidenceScore(x, z̄), (12) where θ ∈ R is the weighting coefficient. The similarity score and confidence score need to be normalized before computing the final score.

heading: 6 Experiments
text: This section presents the experimental results on four neuro-symbolic tasks, including two benchmark datasets and two hard tasks with increased perception difficulty, to demonstrate that ABLSim can perform more efficient and effective abduction than previous state-of-the-art methods by leveraging the similarity among samples. Furthermore, we verify whether it 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 on a server with Intel Xeon Gold 6248R CPU and Nvidia Tesla V100S GPU. In experiments, we simply fix the coefficient θ of ABLSim to 0.96, though it may be better to let it vary with training. The hyperparameters of ABLSim are determined by cross-validation on training data. The code is available for download1.

heading: 6.1 MNIST (CIFAR-10) Addition
text: This task was first introduced in [21], the inputs are pairs of MNIST [17] images and the outputs are their sums. We also prepare a hard version of this task by replacing the MNIST images with CIFAR10 [16] images. We compare ABLSim with the Neural-Grammar-Symbolic (NGS) model [19] (with default and fine-tuned parameters) and DeepProbLog [21]. All methods share the same knowledge base and perception model (LeNet [17] for MNIST and ResNet-50 [12] for CIFAR-10), which are initialized randomly. The feature for calculating the similarity score is obtained from the second last layer in the perceptual neural net.
Table 1 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
1https://github.com/AbductiveLearning/ABLSim
program is time-consuming. The performance of NGS-dft is greatly affected by initialization, which leads to a large standard deviation in the table. For the CIFAR-10 version, DeepProbLog and NGS-dft fail to converge, while NGS-opt converges slower than ABLSim, which solves all tasks efficiently and achieves higher accuracy.

heading: 6.2 Handwritten Formula Recognition
text: The HWF dataset [19] contains images of decimal formulas and their computed results. We also create a (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-training curriculum, which are deleted in our experiments. Thus our results are different from those in [19].
As shown in Table 1, 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-based consistency optimization. Both NGS and DeepProbLog are trapped in local minimum and fail to 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.

heading: 6.3 CIFAR-10 Decimal Equation Decipherment

heading: 6.3.1 Dataset and Knowledge base
text: 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 by MNIST images, here we use CIFAR-10 [16] images to encode decimal equations. An example of this dataset is shown in Figure 2. The task’s inputs are sequential images of randomly generated decimal equations, which consist of twelve symbols (0,1,· · · ,9,+,=). Besides, the knowledge base contains symbolic rules about how to carry out decimal addition operations. The correctness labels (True or False) of training equations are provided in the form of logical facts.

heading: 6.3.2 Experimental Setup
text: 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) ABL-Conf: Abductive learning that measures consistency using only the confidence predicted by neural net, i.e., θ = 0 in equation (12). 3) ABL-pre-train: ABL with model pretrained on a small set of labeled images. 4) ABL-Conf-pre-train: 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, a ResNet-50 [12], is initialized by self-supervised learning [3] on training images. Note that this process is unsupervised and does NOT use any image labels.

heading: 6.3.3 Results
text: Learning Curve. The learning curves of all models are shown in Figure 3(a). The proposed ABLSim 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 pseudolabels 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-Conf-pre-train gets a similar accuracy as 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 3(b) 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. In the first few iterations, the abduction success rate is relatively low. However, the extracted embeddings of
images are gradually improved during training, which provide a better similarity metric for abductive reasoning. Therefore, the rate of successful abduction reaches 1.0 just in a 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 in Figure 3(c)-(d), in 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 is 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 2. The successful abduction increases as 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 a beam width of 600 in our implementation to achieve the balance between convergence rate and time complexity.

heading: 6.4 Theft Judicial Sentencing
text: 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 Part ABLSim-10 0.851 0.828
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 0.786
Part SS-ABL-50 0.862 0.803 Part ABLSim-50 0.866 0.783

heading: 7 Conclusion
text: In this paper, we propose a novel consistency measure for abduction-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 state-of-the-art 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 can use it. The limitation of the method is that the rules of the domain knowledge base need to be constructed manually. In future work, we will try to incorporate techniques like predicate invention into our approach to discover new classes and new knowledge, so that we can automatically extend the knowledge base.
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 EPSRC Robot Synthetic Biologist Project (EP/R034915/1). Stephen H. Muggleton wants to thank the support from EPSRC Network on Human-Like Computing (EP/R022291/1).

Review summaries:
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. 

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.

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.