Semi-Supervised Learning using Differentiable Reasoning

Introduction

Semi-supervised learning is a common class of methods for machine learning tasks where we consider not just labeled data, but also make use of unlabeled data . This can be very beneficial for training in tasks where labeled data is much harder to acquire than unlabeled data.

One such task is Semantic Image Interpretation (SII) in which the goal is to generate a semantic description of the objects on an image . This description is represented as a labeled directed graph, which is known as a scene graph . An example of a labeled dataset for this problem is VisualGenome which contains 108,077 images to train 156,722 different unary and binary predicates. The binary relations in particular make this dataset very sparse, as there are many different pairs of objects that could be related. However, a far larger, though unfortunately unlabeled, dataset like ImageNet contains over 14 million different pictures. Because it is so much larger, it will have many examples of interactions that are not present in VisualGenome. We show that it is possible to improve the performance of a simple classifier on the SII task significantly by adding the satisfaction of a first-order logic (FOL) knowledge base to the supervised loss function. The computation of this satisfaction uses an unlabeled dataset as its domain.

For this purpose, we introduce a statistical relational learning framework called Differentiable Reasoning (DR) in Section 2, as our primary contribution. DR uses simple logical formulas to deduce new training examples in an unlabeled dataset. This is done by adding a differentiable loss term that evaluates the truth value of the formulas.

In the experimental analysis, we find that the gradient updates using the Modus Ponens (MP) and Modus Tollens (MT) rules are disproportionate. That is, MT often strongly dominates MP in the learning process. Such behavior suggests that our approach is highly sensitive to the Raven Paradox . It refers to the phenomenon that the observations obtained from “All ravens are black” are dominated by its logically equivalent “All non-black things are non-ravens”. Indeed, this is closely related to the material implication which caused a lot of discussion throughout the history of logic and philosophy . Our second main contribution relies on its investigation in Section 2.4, and our proposal to cope with it. Finally, we show results on a simple dataset in Section 3 and analyze the behavior of the Raven Paradox in Section 4. Related works and conclusion closes the paper.

Differentiable Reasoning

Next, we define a Bernouilli distribution function over worlds as follows

where ${\mathbf{w}_{i}(\mathsf{P}(\mathbf{o}))}$ (similarly, ${1-\mathbf{w}_{i}(\mathsf{P}(\mathbf{o}))}$) refers to the exponent. Given some world $\mathbf{w_{i}}$, the valuation function $v(\varphi,\mathbf{w_{i}})$ is 1 if $\varphi$ is true in that world, that is, $\mathbf{w}_{i}\models\varphi$, and 0 otherwise.

Next, we explain the domain we use in this article. We have a dataset $\mathcal{D}$ partitioned into two parts: a labeled dataset $\mathcal{D}_{l}=\langle\mathcal{O}_{l},\mathcal{W}_{l}\rangle$ and an unlabeled dataset $\mathcal{D}_{u}=\langle\mathcal{O}_{u},\emptyset\rangle$ where both $\mathcal{O}_{l}$ and $\mathcal{O}_{u}$ are sets of finite domains $D_{i}$, and $\mathcal{W}_{l}$ is a set containing the correct world $\mathbf{w}^{l*}_{i}$ for all pictures $i$.

In Figure 1 we illustrate the Bayesian network associated with this problem. The left plate denotes the usual supervised data likelihood $p(\mathcal{W}_{l}|\mathcal{O}_{l},\boldsymbol{\theta})$ and the right plates denote the probabilities of the truth values of the formulas $\varphi\in\mathcal{K}$ using $p(\mathcal{K}|\mathcal{O}_{u},\boldsymbol{\theta})$.

It is important to note that the true worlds $\mathbf{w}_{i}^{u*}$ of the unlabeled dataset are not known, that is, they are latent variables and they have to be marginalized over. The formulas in knowledge base $\mathcal{K}$ are all assumed to be true. We can now obtain the optimization problem that we can solve using gradient descent as

where in the last step we take the $\log$ and minimize with respect to the negative value. The optimization problem in Equation LABEL:eq:optim consists of two terms. The first is the cross-entropy loss for supervised labeled data. The second can be understood as follows: A world entails a (full) knowledge base (i.e., $\mathbf{w}\models\mathcal{K}$) if $\mathbf{w}\models\varphi$ holds for all $\varphi\in\mathcal{K}$ (that is, the product of their valuations is 1). For each domain $D_{i}$, we then find the sum of the probabilities of worlds that entail the knowledge base. This is an example of what we call the differentiable reasoning loss. The general differentiable reasoning objective is given as

2 Differentiable Reasoning Using Product Real Logic

The marginalization over all possible worlds $\mathbf{w}_{i}^{u}$ requires $2^{|\mathbf{A}_{i}|}$ combinations, so it is exponential in the size of the Herbrand base. Therefore, the problem of finding the sum of the probabilities $p(\mathbf{w}_{i}|\boldsymbol{\theta})$ for all worlds $\mathbf{w}_{i}$ that entail the knowledge base $\mathcal{K}$ is #P-complete Instead, we shall perform a much simpler computation defined over logical formulas and the parameters $\boldsymbol{\theta}$ as follows:

The loss term associated with the formula $\varphi=\forall x,y\ \textsf{chair}(x)\wedge\textsf{partOf}(y,x)\rightarrow\textsf{cushion}(y)\vee\textsf{armRest}(y)$ is computed as follows:

Say $\mathcal{O}_{u}$ contains the picture in Figure 2 whose domain is $\{a,b\}$ and the model predicts the following distribution over worlds:

The model returns high values for $f_{\textsf{chair}}^{\boldsymbol{\theta}}(a)$ and $f_{\textsf{partOf}}^{\boldsymbol{\theta}}(b,a)$ but it is not confident of $f_{\textsf{cushion}}^{\boldsymbol{\theta}}(b)$, even though it is clearly higher than $f_{\textsf{armRest}}^{\boldsymbol{\theta}}(b)$. We can decrease $\mathcal{L}(\boldsymbol{\theta};\varphi,\mathcal{O}_{u})=0.612$ simply by increasing $f_{\textsf{cushion}}^{\boldsymbol{\theta}}(b)$, since $f^{\boldsymbol{\theta}}_{\textsf{cushion}}$ is a differentiable function with respect to $\boldsymbol{\theta}$.

This example shows that we can find a new instance of the cushion predicate using reasoning on an unlabeled dataset. This process uses both statistical reasoning and symbolic rules. As more data improves generalization, those additional examples could help reducing the sparsity of the SII problem. Furthermore, showed that it is also possible to correct wrong labels due to noisy data when these do not satisfy the formulas.

Figure 3 shows the Bayesian Network for this formula on the picture from Figure 2, illustrating the computation path. We treat each subformula as a binary random variable of which the conditional probabilities are given by truth tables. Because the graph is not acyclic, we can use loopy belief propagation which is empirically shown to often be a good approximation of the correct probability . In fact, Product Real Logic can be seen as performing a single iteration of belief propagation. However, this can be problematic. For example, the degree of truth of the ground formula $\textsf{chair}(o)\wedge\textsf{chair}(o)$ would be computed using $f_{\textsf{chair}}^{\boldsymbol{\theta}}(o)^{2}$ instead of the probability of this statement, $f_{\textsf{chair}}^{\boldsymbol{\theta}}(o)$ . We show in Appendix A that Product Real Logic computes the correct probability $p(\mathcal{K}|\mathcal{O}_{u},\boldsymbol{\theta})$ for a corpus $\mathcal{K}$ under the strong assumption that, after grounding, each ground atom is used at most once.

An interesting and useful property of our approach is that it can perform multi-hop reasoning in an iterative, yet extremely noisy, manner. In one iteration it might, for instance, increase $f_{\textsf{cushion}}^{\boldsymbol{\theta}}(o)$. And since $f_{\textsf{cushion}}^{\boldsymbol{\theta}}(o)$ will return higher values in future iterations, it can be used to prove that the probability of other ground atoms that occur in formulas with $\textsf{cushion}(o)$ should also be increased or decreased.

A convenient property of the SII task is that we consider just binary relations between objects appearing on the same pictures. The Herbrand base then contains $O(|\mathcal{P}|\cdot|D_{i}|^{2})$ ground atoms, which is feasible as there are often not more than a few dozen objects on an image. This property also holds in natural language to some degree in the following way: only the words appearing in the same paragraph can be related. This is in contrast to the knowledge base completion task where we have a single graph with many objects and predicates .

3 Implementation

We optimize the negative logarithm of the likelihood function given in Equation LABEL:eq:optim. In particular, we use minibatch gradient descent to decrease the computation time both for the supervised part of the loss and the unsupervised part. We turn the unsupervised loss into minibatch gradient descent by approximating the computation of the $\forall$ quantifier: instead of summing over all $n$-tuples and all domains, we randomly sample from these $n$-tuples independently from the domain it belongs to.

4 The Material Implication

To provide a better understanding of the inner machinery of our approach, we will elaborate on some interesting partial derivatives. Say, we have a formula $\varphi$ of the form $\forall{\mathbf{x}}\phi(\mathbf{x})\rightarrow\psi(\mathbf{x})$, where $\phi(\mathbf{x})$ is the antecedent and $\psi(\mathbf{x})$ the consequent of $\varphi$. First, we write out the partial derivative of $\mathcal{L}(\boldsymbol{\theta};\varphi,\mathcal{O}_{u})$ with respect to the consequent, where we make use of the chain rule:

Next, we show how these quantities are used in the updating of the parameters $\boldsymbol{\theta}$ using backpropagation and act as mixing components on the gradient updates:

5 The Raven Paradox

In our experiments, we have found that this approach is very sensitive to the raven paradox . It is stated as follows: Assuming that observing an example of a statement is evidence for that statement (i.e., the degree of belief in that statement increases), and that evidence for a sentence also is evidence for all the other logically equivalent sentences, then our belief in “ravens are black” increases when we observe non-black non-raven, by the contrapositive “non-ravens are non-black”. Equation 17 shows however that the gradient is equally determined by positive evidence (observing black ravens) as by contrapositive evidence (observing non-black non-ravens). Because in the real world there are far more ravens than non-black objects, optimizing ${\rm Phys.~{}Rev.~{}Lett.}(\forall o\ \textsf{raven}(o)\rightarrow\textsf{black}(o)|\mathcal{O}_{u},\boldsymbol{\theta})$ amounts to recognizing that something is not a raven when it is not black. However, Machine Learning models tend to be biased when the class distribution is unbalanced during training .

We analyze a naive way of dealing with this phenomenon. We normalize the contribution to the total gradient of MP and MT reasoning by replacing the loss function $\mathcal{L}$ of rules of the form $\forall{\mathbf{x}}\phi(\mathbf{x})\rightarrow\psi(\mathbf{x})$ as follows:

where $\mu$ is a hyperparameter that assigns the relative importance of Modus Ponens with respect to Modus Tollens updates. We are then able to control how much either contributes to the training process. We experiment with different values of $\mu$ and report our findings in the next section.

Experiments

We carried out simple experiments on the PASCAL-Part dataset in which the task is to predict the type of the object in a bounding box and the partOf relation which expresses that some bounding box is a part of another. For example, a tail can be a part of a cat. Like in , the output softmax layer over the 64 object classes of a Fast R-CNN detector is used for the bounding box features. Note that this makes the problem of recognizing types very easy as the features correlate strongly with the true output types. Therefore, to get a more realistic estimate, we randomly split the dataset into only 7 labeled pictures for $\mathcal{D}_{l}$ and 2128 unlabeled pictures for $\mathcal{D}_{u}$. Additionally, we only consider 11 (related) types out of 64 due to computational constraints. As there is a large amount of variance associated with randomly splitting in this way, we do all our experiments on 20 random splits of the dataset. The results are evaluated on a held-out validation set of 200 images. We compare the accuracy of prediction of the type of the bounding box and the AUC (area under curve) for the partOf relationship.

We model $f_{\textsf{type}_{i}}^{\boldsymbol{\theta}}(o)$ using a single Logic Tensor Network (LTN) layer of width 10 followed by a softmax output layer to ensure mutual exclusivity of types. The term $f_{\textsf{partOf}}^{\boldsymbol{\theta}}(o_{1},o_{2})$ is modeled using an LTN layer of width 2 and a sigmoid output layer. The loss function is then optimized using RMSProp over 6000 iterations. We use the same relational background knowledge as which are rules like the following:

We compare three methods. In the first one we train without any rules, which forms the supervised baseline. In the second, unnormalized, we add the rules to the unlabeled data. This does not use any technique for dealing with the raven paradox. In the last one called normalized, we normalize MP and MT reasoning using Equation 18 for several different values of $\mu$. The results in Table 1 are statistically significant when using a paired t-test.

Analysis

Our experiments show that we can significantly improve on the classification of the types of objects for this problem. The normalized method in particular outperforms the unnormalized method, suggesting that explicitly dealing with the raven paradox is essential in this problem.

Related work

Our work follows the recent works on Real Logic , and the method we use is a special case of Real Logic with some additional changes. A particular difference is that the logic we employ has no function symbols, which was due to simplicity purposes. Injecting background knowledge into vector embeddings of entities and relations has been studied in . In particular, has some similarities with Real Logic and our method. However, this method is developed for regularizing vector embeddings instead of any parameterized model. In this sense, it can also be seen as a special case of Real Logic. Semantic Loss is a very similar semi-supervised learning method. This loss is essentially Equation LABEL:eq:optim, which makes it more accurate than Product Real Logic, but also exponential in runtime. To deal with this, they compile SDD’s to make the computation tractable. A recent direction is DeepProbLog , a probabilistic version of Prolog with neural predicates that also uses SDD’s. also injects rules into a general model with a framework that transfers the logic rules using a so-called teacher network. This model is significantly different from the aforementioned ones, as it does not add a loss for each rule.

2 Semi-Supervised Learning

There is a large body of literature on semi-supervised methods . In particular, recent research on graph-based semi-supervised learning relates unlabeled and labeled data through a graph structure. However, they do not use logically structured background knowledge. It is generally used for entity classification, although in it is also used on link prediction. introduced the surprisingly effective method Pseudo-Label that first trains a model using the labeled dataset, then labels the unlabeled dataset using this model and continues training on this newly labeled dataset. Our approach has a similar intuition in that we use the current model to get an estimation about the correct labels of the labeled dataset, and then use those labels to predict remaining labels, but the difference is that we use background knowledge to choose these labels.

Conclusion and Future Work

We proposed a novel semi-supervised learning technique and showed that it is possible to find labels for samples in an unlabeled dataset by evaluating them on relational background knowledge. Since implication is at the core of logical reasoning, we analyzed this by inspecting the gradients with respect to the antecedent and the consequent. Surprisingly, we discovered a strong imbalance between the contributions of updates from MP and MT in the induction process. It turned out that our approach is highly sensitive to the Raven paradox requiring us to handle positive and contrapositive reasoning separately. Normalizing these different types of reasoning yields the largest improvements to the supervised baseline. Since it is quite general, we suspect that issues with this imbalance could occur in many systems that perform inductive reasoning.

We would like to investigate this phenomenon with different background knowledge and different datasets such as VisualGenome and ImageNet. In particular, we are interested in other approaches for modelling the implication like different Fuzzy Implications or by taking inspiration from Bayesian treatments of the Raven paradox . Furthermore, it could be applied to natural language understanding tasks like semantic parsing.

References

Appendix A Conditional Optimality of Product Real Logic

For each formula $\varphi$, we have the set of ground atoms $\mathbf{A}_{\varphi}\subseteq\mathbf{A}$ appearing in the instantiations of $\varphi$. Likewise, the assignment of truth values of $\mathbf{A}_{\varphi}$ is $\mathbf{w}_{\varphi}$, which is a subset of the world $\mathbf{w}$. We can now express the joint probability, using Equation 1 and the valuation function defined in Section 2.1:

We will first show that Product Real Logic is equal to this probability with two strong assumptions. The first is that the sets of ground atoms $\mathbf{A}_{\varphi}$ are disjoint for all formulas in the corpus, i.e. if

The second is that the set of ground atoms used in two children (a direct subformula) of some subformula of a formula in $\mathcal{K}$ are disjoint. If $pa(\phi)$ returns the parent of $\phi$ and $r(\phi)$ returns the root of $\phi$ (the formula highest up the tree), then

First, we marginalize over the different possible worlds:

where we make use of Equation 22 to join the summations, the independence of the probabilities of atoms from Equation 1 and marginalization of the atoms other than those in $\mathbf{A}_{\varphi}$.

We denote the set of instantiations of $\varphi$ by $S_{\varphi}$, and a particular instance by $s$. $\mathbf{A}_{s}\subseteq\mathbf{A}_{\varphi}$ then is the set of ground atoms in $s$ (and respectively for $\mathbf{w}_{s}$. Next we show that $\sum_{\mathbf{w}_{\varphi}}p(\mathbf{w}_{\varphi}|\boldsymbol{\theta})\cdot v(\varphi,\mathbf{w}_{\varphi})=\prod_{s\in S_{\varphi}}{\rm Phys.~{}Rev.~{}Lett.}(\varphi|s,\boldsymbol{\theta})$. As the formulas are in prenex normal form, $\varphi=\forall x_{1},...,x_{\alpha}\phi$. We find that, using Equation 23 and the same procedure as in Equations 24-27

Then, it suffices to show that $\sum_{\mathbf{w}_{s}}p(\mathbf{w}_{s}|\boldsymbol{\theta})\cdot v(\phi,\mathbf{w}_{s})={\rm Phys.~{}Rev.~{}Lett.}(\phi|s,\boldsymbol{\theta})$. This is done using recursion. For brevity, we will only proof it for the $\neg$ and $\wedge$ connectives, as we can proof the others using those.

Assume that $\phi=\textsf{P}(x_{1},...,x_{n})$. Then if $w_{s}(\textsf{P}(x_{1},...,x_{n}))$ is the binary random variable of the ground atom $\textsf{P}(x_{1},...,x_{n})$ under the instantiation $s$,

Marginalize out all variables but $w_{s}(\textsf{P}(x_{1},...,x_{n}))$. $v(\textsf{P}(x_{1},...,x_{n}),\mathbf{w}_{s})$ is 1 if $w_{s}(\textsf{P}(x_{1},...,x_{n}))$ is, and 0 otherwise.

Finally, assume $\varphi=\phi\wedge\psi$. Then

Using this result and equations 27 and 29, we find that