Evaluating Relaxations of Logic for Neural Networks: A Comprehensive Study

1 Introduction

Neural networks are remarkably effective across many domains and tasks; but their usefulness is limited by their data hungriness. A promising direction towards alleviating this concern involves augmenting learning with rules written in first-order logic [Rockt¨aschel et al., 2015; Li and Srikumar, 2019; Li et al., 2019; Fischer et al., 2019, inter alia]. To make rules amenable with gradient-based learning, this approach calls for relaxing the logical operators to define subdifferentiable loss terms. A systematic method to perform this relaxation uses a well-studied family of binary operators, namely triangular norms or t-norms [Klement et al., 2013]. Different t-norms define different [0, 1]-valued interpretations of the Boolean operators.

There are infinitely many such t-norm logics, but the most commonly used ones are: Product [Rockt¨aschel et al., 2015; Li et al., 2019; Asai and Hajishirzi, 2020], G¨odel [Minervini et al., 2017] and Łukasiewicz [Bach et al., 2017]. While the usefulness of such relaxations is well established, the questions of how they compare against each other, and even how such a comparison should be defined remain open.

This paper is a first step towards answering these important questions by analyzing the three t-norm relaxations and their variants. To do so, we define the criteria for quantifying the goodness of a t-norm based relaxation. On the theoretical side, we rank logic relaxations by their consistency, i.e., their ability to preserve the truth of tautologies. On the empirical side, we use a principled approach to construct loss functions using t-norms that subsume traditional loss functions like cross-entropy, and study how well different relaxations compare with standard gradient-based learning. We report the results of experiments on two tasks: jointly recognizing digits and predicting the results of arithmetic operators, and text chunking. Both the theoretical and empirical criteria concur in the recommendation that a variant of the Product t-norm (R-Product) is most suitable for introducing logical rules into neural networks.

In summary, the main contributions of this work are:

• We define theoretical and empirical properties that any relaxation of logic should have to be useful for learning.
• We define the consistency of relaxations to rank them in terms of their ability to preserve tautologies.
• We present empirical comparisons of logic relaxations on two tasks where labeled examples and declaratively stated knowledge together inform neural models.

2 Problem Statement and Notation

Several recent efforts have shown the usefulness of declarative knowledge to guide neural network learning towards improving model quality. While different approaches exist for incorporating such rules into neural models [Xu et al., 2018, for example], a prominent strategy involves relaxing logic to the real regime using the well-studied t-norm relaxations.

Triangular norms (t-norms) arose in the context of probabilistic metric spaces [Menger, 1942], and for our purposes, represent a relaxation of the Boolean conjunction which agrees with the definition of conjunctions for {0, 1}- inputs. Given such a relaxation and a relaxation of ¬X as 1 - x, we have two axiomatic approaches for defining implications. The first (called S-logics) treats implications as disjunctions (i.e., X → Y = ¬X ∨ Y ), while the second (called R-logics) defines implications axiomatically. We refer the reader to Klement et al. [2013] for a detailed treatment of t-norms.

Table 1 shows the set of t-norms we consider here; these have been used in recent literature to inject knowledge into neural networks. However, despite their increasing prevalence, there is no consensus on which t-norm to employ. A survey of recent papers reveals the use of SProduct [Rockt¨aschel et al., 2015], R-Product [Li et al., 2019; Asai and Hajishirzi, 2020], Łukasiewicz [Bach et al., 2017], S-G¨odel [Minervini et al., 2017] and even a mixture of the S-G¨odel and R-Product [Li et al., 2020] t-norms.

How do these relaxations of logic compare against each other? In this work, we answer this question from both theoretical and empirical perspectives.

2.1 Learning FromLogic: The Setup

To compare the different relaxations of logic on an even footing, let us first see a general recipe for converting logic rules to loss functions for a given relaxation 1 . We will use the task of recognizing handwritten digits as a running example.

Given a labeling task, we can represent the fact that the label for an instance x is y as a predicate, say Label(x, y). In our running example, we could define a predicate Digit(x, y) to denote that an image x represents the digit y. We could also define a predicate Sum(x1, x2, y) to denote the fact that the digits in two images x1 and x2 add up to the digit y (mod10). From this perspective, we can treat classifiers as predicting probabilities that the predicates hold.

To train such classifiers, we typically have a training set D of labeled examples (x, y). In our notation, each such example can be represented as the predicate Label(x, y) and the training set is a conjunction of such predicates

Sometimes, instead of a labeled dataset, we may have a constraint written in logic. In our running example, from the definition of the Digit and Sum predicates, we know that

Note that such a constraint need not depend on labeled examples, and should hold irrespective of what labels the examples should be assigned. In general, given a large unlabeled set of examples denoted by x ∈ U, we can write constraints

These constraints may be composite formulas constructed with predicates as shown in our running example above.

From this standpoint, we can envision the goal of learning as that of ensuring that the formulas representing labeled examples ( equation 1) and constraints ( equation 3) hold. Since we are treating classifiers as predicting probabilities that the atomic predicates hold, we can equivalently state the learning problem as that of finding model parameters that maximize the value of a relaxation of the conjunction of the formulas representing the data and constraints. In other words, we can use logic to define loss functions.

1 The setup described here is implicitly present in Rockt¨aschel et al. [2015], Li et al. [2019], and others.

In this declarative learning setting, we have the choice of using any models (e.g., CNNs) for our predicates, and any relaxation of logic. If we only have labeled examples, and we use one of the Product relaxations, we recover the widely used cross-entropy loss [Li et al., 2019; Giannini et al., 2019].

Notation. We use upper case letters (e.g., P, Digit) to represent Booleans, and lower cased letters (e.g., p, digit) to represent their relaxations. In some places, for clarity, we use square brackets to denote the relaxation of a Boolean formula A (i.e., [A]=a).

3 Validity of Relaxed Logic

In this section, we propose three criteria that a logic relaxation should satisfy to be useful for learning.

Consistency. The language of logic can declaratively introduce domain knowledge, invariants, or even reasoning skills into neural networks. However, to admit reasoning, tautologies should always hold. That is, the truth value of any tautology should be 1 irrespective of the value of its constituent atomic predicates. Equivalently, the integral of the relaxation of a tautology over the domain of its atomic predicates should be 1. We can formalize this intuition.

Definition 1. Let T be a tautology in predicate logic formed with a set of atomic predicates T , and let L be a logic relaxation. The consistency of T in L, denoted as κL(T), is defined as

If the consistency κL(T) = 1, we will say that the tautology T is consistent under the relaxation L.

Self-consistency. Every Boolean statement implies itself. That is, the statement P ↔ P is a tautology for any P. This observation gives us the definition of self-consistency of a formula under a given relaxation.

Definition 2. Let P be any Boolean formula in predicate logic with a set of atomic predicates P , and let L be a logic relaxation. The self-consistency of P in the logic L, denoted as

κLS (P), is defined as

If κLS (P) ̸= 1 we will say that formula P is not selfconsistent under a relaxation L. Since we consider a dataset to be a conjunction of facts ( equation 1), the self-consistency of large conjunctions allows us to judge whether a dataset implies itself under a relaxation.

Sub-differentiability. Since our eventual goal is to relax declaratively stated knowledge to train neural networks, the relaxations should admit training via backpropagation. As a result, the functions defining the relaxed logical operators should at least be sub-differentiable.

In sum, we consider a logic relaxation to be valid if the following properties hold:

• (P1) It must be sub-differentiable over the interval [0, 1].
• (P2) It must be consistent for any tautology.
• (P3) It must be self-consistent for any Boolean formula.

All the relaxations we study here satisfy property P1 2 . Even among sub-differentiable relaxations, some may be easier than others to learn using gradient-based approaches. We consider this empirical question in §5. Properties P2 and P3 do not always hold, and we will prefer relaxations that have higher values of consistency and self-consistency.

4 Truth Preservation of Relaxations

In this section, we will assess the relaxations from Table 1 with respect to properties P2 and P3.

4.1 Consistency

Property P2 expects every tautology to be consistent under a valid logic relaxation. Since predicate logic admits infinitely many tautologies, we will use a representative set of tautologies for our evaluation. This set contains the Axiom Schemata of the Hilbert proof system for predicate logic 3 , the primitive propositions, and a set of elementary properties defined by Russell and Whitehead [1910].

Table 2 shows the consistency for each tautology for our tnorm relaxations. Comparing results across the columns, we see that Łukasiewicz and R-Product t-norm logics preserve truth the most across our representative set. In general, we find R logics to be better at preserving truth than S logics.

Example 1. Consistency of the tautology A → A using SProduct.

By the definition of consistency ( equation 4), we have

2 This is not always the case. In R-G¨odel logics, for instance, implications are not sub-differentiable: [X → Y], takes value 1 if y ≥ x, and y otherwise.

3 This choice is motivated because, loosely speaking, every tautology is generated using the Axiom Schemata with the modus ponens proof rule.

4.2 Self-consistency

The validity property P3 states that every well-formed Boolean formula should be self-consistent for a relaxation of the logic to be valid. It turns out that the definition of implications for any R logic (including Łukasiewicz) guarantees the self-consistency of every formula.

Proposition 1. Every formula is self-consistent under any Rlogic relaxation.

This follows directly from the definition of the t-norm and the properties of residua.

However, the same is not true for S-logics. For example, for the conjunction P = A ∧ B, the self-consistency under the G¨odel relaxation κS-G¨odel S (P) = 0.75 and under the Product relaxation, we have κS-Prod S (P) ≈ 0.74. These results suggest that the R-Product and Łukasiewicz relaxations are preferable from the perspective of property P3 as well.

Intriguingly, we find that the S-Product logic is eventually self-consistent for large monotone conjunctions.

Proposition 2. Let A = ∧ni=1 Ai be a conjunction consisting of n atomic predicates A1, A2, . . . , An. The self-consistency of A is given by κS-Prod S (A) = 1 - 2 2n + 3 3n - 2 4n + 1 5n .

Proof. By induction over the size of the conjunction n.

We see that, as n → ∞, the self-consistency of a monotone conjunction approaches 1. In other words, large conjunctions (e.g., representing large datasets) are essentially selfconsistent under the S-Product relaxation.

5 Empirical Comparisons of Relaxed Logic

In this section, we empirically study the differences between the different logic relaxations using two tasks: recognizing digits and arithmetic operations, and text chunking. In both tasks, we set up the learning problem in terms of logic, and compare models learned via different logic relaxations. 4

5.1 Recognizing Digits and Arithmetic Operations

These experiments build upon our running example from §2. We seek to categorize handwritten digits; i.e., we learn the predicate Digit. In addition, we also seek to predict the sum and product (modulo 10) of two handwritten digit images. These correspond to the predicate Sum we have seen, and a new analogous predicate Product.

We use the popular MNIST dataset [LeCun, 1998] for our experiments, but only to supervise the Digit classifier. Rather than directly supervising the other two classifiers, we use coherence constraints over unlabeled image pairs that connect them to the Digit model. The constraint for the Sum classifier is shown in equation 2, and the one for the Product classifier is similarly defined.

We set up the learning problem as defined in §2 and compare performance across different relaxations.

Data and Setup

We partition the 60k MNIST training images into TRAIN and DEV sets, with 50k and 10k images respectively. To supervise the Digit model, we sample 1k, 5k and 25k labeled images from TRAIN to form three DIGIT sets. The coherence constraints are grounded in 5k unlabeled image pairs consisting of images from TRAIN that are not in any DIGIT set, giving us the PAIR dataset.

For evaluating the Digit model, we use the original 10k TEST examples fromMNIST. For the development and evaluation of the operator models, we sample random image pairs from DEV and TEST to create the PairDEV and PairTEST sets respectively. The ground truth Sum and Product labels for these image pairs can be computed by the sum and product modulo 10 of the image labels.

We use CNNs as the Digit, Sum and Product models. For the operator models, we concatenated the two images to get CNN inputs. To jointly train these models using the labeled DIGIT data and the unlabeled PAIR datasets, we define a loss function by relaxing the conjunction of Digit predicates over the DIGIT examples and the coherence constraints over the PAIR examples. That is, learning requires minimizing:

-

4 Our PyTorch [Paszke et al., 2019] code is archived at https:// github.com/utahnlp/neural- logic

In practice, we found that it is important to use a hyperparameter λ that weights the relaxed coherence constraints in the loss. We used the DEV sets for hyperparameter tuning using the average of the accuracy of the Digit classifier and the coherences of the other two.

Results

Table 3 reports accuracies for the Digit classifier trained with different sizes of DIGIT, and the coherence constraints instantiated over the 5k PAIR examples. We observe that the R-Prod relaxation dominates across all settings, with higher gains when there are fewer labeled examples. (The bold entries in this and other tables are statistically significantly better than the other relaxations at p < 0.05. The accuracies are averages from three runs with different seeds along with the standard deviation.) Table 4 reports the average of Sum, and Prod accuracies for the same settings, and Table 5 shows the fraction of PairTEST examples where the coherence constraints are satisfied. From these results, we see that the RProduct and S-G¨odel relaxations offer the best accuracies.

Interestingly, Łukasiewicz is the least accurate relaxation. However, the losses compiled using Łukasiewicz and SG¨odel t-norms were unstable, and the results shown here were achieved with additional assumptions. We defer this technical discussion to §5.3, and conclude that the stability and accuracy of the R-Product relaxation suggest that it is the most suitable relaxation for this class of problems.

Joint Learning vs. Pipelines

In the coherence constraints in equation 2, if we knew both the Digit terms, we can deterministically compute the value of Sum. This suggests a pipeline strategy for training, where we can train the Digit classifier alone, and use it to assign (noisy) labels to the unlabeled PAIR data. Subsequently, we can train the Sum and Product models independently. How does the joint training strategy compare to this pipeline?

Importantly, we should note that both the joint and the pipeline strategies instantiate the declarative learning approach outlined in §2 where logical facts are compiled into an optimization learning problem via the logic relaxations. However, in the pipeline, the coherence constraints are not explicitly involved in the loss, because the noisy labels already satisfy them. Since conjunctions are identical for the S and R relaxations, they give the same results.

Tables 6, 7, and 8 show the results of these pipelined experiments. We observe the same trends as in the joint learning experiments: R-Product achieves the highest performance.

Comparing the joint learning and the pipeline results, we observe that the latter are slightly better across relaxations and data settings. As mentioned above, however, pipelining is only viable here because of the special form of our constraint.

5.2 Text Chunking

Our second set of experiments use the NLP task of text chunking using the CoNLL 2000 dataset [Sang and Buchholz, 2000]. This task illustrates how relaxed logic can be used to derive loss functions for sequential inputs and outputs.

Text chunking is a sequence tagging problem, where each word of a sentence is assigned a phrase type. For example, in the sentence 'John is playing in the park.', the word 'John' is labeled as B-NP, indicating that it starts a noun phrase (NP). We use the standard BIO labeling scheme: B-X indicates the start of a new phrase labeled X, I-X indicates the continuation of a phrase labeled X, and O marks words that do not belong to any of the predefined phrase types.

In the case of text chunking, the input x is a sequence of words and correspondingly, output y is a sequence of labels (phrase types). Consequently, each position in the sequence is associated with a predicate. For an input x with n words, we have n predicates, one per word.

Using our notation from §2 we define the predicate, Tag(xi, yi), to denote that ith word in input x is assigned the label yi. For our preceding example, John being assigned the label B-NP corresponds to the predicate Tag(John, B-NP).

Constraints

For each position in the sequence, we have constraints defining pairwise label dependencies. If a word in a sentence has a B/I label of a certain phrase type, then the next word cannot have a I label of a different phrase type. For example, we have

In general, given a labeled dataset D, and a set C of k constraints for each word position, we can write the conjunction of all constraints as:

We can now use this Boolean formula to state the goal of learning as finding the model parameters of a neural network that maximizes the value of the relaxation derived for each t-norm. We used a bidirectional LSTM over GloVe embeddings [Pennington et al., 2014] to instantiate Tag.

Experiments and Results

We compare the four t-norms on two settings. First, in purely supervised learning, the model only learns from labeled examples. Second, we augment the labeled dataset with the constraints described above to study the effectiveness of incorporating simple constraints on outputs. For both of these settings, we also study the models in a low data regime with training data restricted to 10%. Following previous work [Sang and Buchholz, 2000], we use the F1 score as our evaluation metric.

We report performances of the models trained with different t-norms in Table 9. We observe that for supervised learning (top rows), both variants of product t-norm outperform the other two t-norms by a significant margin. We again observe that for purely supervised learning, both R-Product and S-Product produce identical results since no implication constraints are used. Further, S-G¨odel performs the worst among the four t-norms. Note that this observation is consistent with our analysis from Table 2 where S-G¨odel was found to be least consistent with tautologies.

Let us now look at the results of augmenting supervised learning with simple output constraints (Table 9, bottom rows). First, we observe that incorporating simple constraints into neural models, using the framework discussed in this work, can indeed improve their performance in all cases. Particularly, this improvement is more pronounced in low data regimes, since models need to rely more on external background knowledge when training data is small.

We also find that both variants of product t-norms outperform S-G¨odel and Łukasiewicz. However, in both data regimes, R-Product outperforms S-Product when incorporating constraints into the neural model. We observe that these results are consistent with the ones obtained in §5.1.

5.3 Theory vs. Experiments

From our analysis of t-norms in §4, we found that Łukasiewicz and R-Product are the most preferable. Empirically, R-Product outperforms the other relaxations.

The consistency analysis suggests that since S-G¨odel is least consistent, we should also expect S-G¨odel to empirically perform the worst. This argument is reinforced by the results across all tasks and settings, if we naively applied the G¨odel t-norm to define the loss. The S-G¨odel results shown in this work were obtained by warm starting the learning using the R-Product relaxation. Without the warm start, we found that not only is learning unstable, the resulting accuracies were also low.

One other discrepancy bears attention: although Łukasiewicz is most preferable in terms of consistency on tautologies, the experiments suggest otherwise. From an empirical perspective, a valid relaxation of logic should provide a sufficient gradient signal to make learning feasible. We discovered that loss functions defined by the Łukasiewicz t-norm are not amenable to gradient-based learning. Here, we briefly explain this phenomenon.

Consider the Łukasiewicz conjunction over n atoms:

For this operation to provide a non-zero output, we need ∑ni ai > (n - 1), or on average, each of the conjuncts ai should exceed n-1 n .

That is, to provide a useful signal, Łukasiewicz t-norm requires the model to assign high probabilities to correct labels. This, of course, is not true for a randomly initialized model when learning starts, contributing to near-zero gradients, and no model updates at all.

To make learning feasible with Łukasiewicz t-norm, we implemented a less strict definition of conjunction inspired by the MAX-SAT relaxation of Bach et al. [2017]. This transforms our learning objective to the form maxθ (∑ni ai). An important consequence of this approach is that Łukasiewicz t-norm in our experiments is merely an approximation of the original Łukasiewicz t-norm.

6 RelatedWork and Discussion

The use of t-norm relaxations to encode knowledge into learning is increasingly prevalent in recent years [Wang et al., 2020; Minervini et al., 2017; Donadello et al., 2017, for example]. Additionally, Grefenstette [2013], and Nandwani et al. [2019] also implicitly use t-norms to similar ends. These works do not frame the learning problem as a declarative statement encoded using a single predefined logical language, as in the case of [Sikka et al., 2020] and [Giannini et al., 2019].

Our framework is closer to Li et al. [2019], Asai and Hajishirzi [2020], and Wang et al. [2020] where both data and background knowledge are declaratively stated and encoded in one single t-norm relaxation that defines the loss. Our experiments for the extended MNIST digit classification are inspired by Manhaeve et al. [2018], who employ constraints similar to our coherence constraints. Of course, the goal of this work is to theoretically, and empirically investigate which relaxation is best suited for use in such problems. To our knowledge, none of the previously mentioned works analyze the choice of the relaxation they use.

Similar studies to this paper are that of Evans and Grefenstette [2018], and van Krieken et al. [2020]. The former, includes comparison in performance of Łukasiewicz, Product, and G¨odel t-norm operators used to induce differentiable functions from definitive clauses in neural program synthesis. The latter, perhaps closer to our approach, provides a general theoretical and empirical analysis for different t-norm relaxations. However, there are two key differences with our work: (a) they do not treat labeled data as part of the declarative problem specification, and the constraints are added into a standard cross entropy loss, (b) their analysis involves the derivatives of the losses and does not discuss the consistency and self-consistency properties. We also studied the importance of the loss gradient signal in gradient-based learning, and hypothesise that a less consistent t-norm would perform worse at characterizing the truth of a Boolean statement than a more consistent one, and as a result, would correspond to poorer empirical performance.

7 Conclusions

In this work, we studied the question of how best to relax declarative knowledge to define loss functions. To this end, we define a set of criteria that characterizes which relaxations of logic would be most amenable for preserving tautologies and offer support for gradient-based learning. We also present empirical studies on two tasks using the paradigm of formulating entire learning problems via logic. All our analyzes concur that the R-Product relaxation is best suited for learning in this paradigm.