In this work we present NeuralLog+MIL, a structure learning system based on Meta-Interpretive Learning. NeuralLog+MIL applies the idea of Metagol to learn theories in the NeuralLog language. Metagol is a system that uses a set of higher-order clauses to de ne a hypotheses space of rst-order logic theories and applies those clauses in order to derive rst-order theories from examples. Then, NeuralLog transforms a rst-order logic program into a neural network. It receives as input a set of rst-order clauses that are used to de ne the neural network models, and a set of facts that becomes weights in the neural network. We show that our approach has competitive results for the link prediction task when compared with Neural-LP in three di erent datasets. Achieving comparable values for the hit at top 10 entities and the mean rank metric in the UMLS and WordNet datasets; and outperforming Neural-LP in the UWCSE dataset in those metrics.
NeuralLog is a system developed to transform a rst-order logic program into a
neural network. It receives as input a set of rst-order clauses that are used to
de ne the neural network models, and a set of facts that becomes weights in the
neural network. Then, those weights are ne-tuned in order to better describe a
set of examples [
In this paper, we propose NeuralLog+MIL, a structure learning system
that nds rst-order logic program for NeuralLog [
Copyright© 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
NeuralLog+MIL contributes to the extensive line of research that is being
developed on combining the advantages of high-level knowledge representations,
quite often based on logic, and the impressive performance of neural networks.
Often, e ort relied on pre-existing theories, or on theories learned by di erent
learners, that might not be the best t for these learners. In fact, previous
work on theory learning for Statistical Relational Programs showed progress in
this area to be constrained by the need to perform combined inference and by
explosive growth in the search space. Thus, most work in this area assumes the
existence of an underlying theory. One important exception is Neural-LP [
While neural network has been achieving great performance in a range of
tasks [
The combination of logic based approaches with neural network can bene t from the strengths of both methods. On one hand, neural networks can bring to rst-order logic the capability to deal with uncertainty and noise. On the other hand, rst-order logic can improve the performance of neural network models by incorporating background knowledge. This background knowledge might contain expert knowledge that can be used to guide the neural network toward a better model representation. Nevertheless, neural network models based on rst-order logic might be easier to interpret and explain, since rst-order logic is easier to understand, from a human perspective; and the inference of neural networks based on it is, to some extent, based on the underlying logic structure.
We show that NeuralLog+MIL has comparable results with Neural-LP in
the UMLS [
The remainder of the paper is organized as follows: in Section 2 we give the background knowledge in order to understand this work; in Section 3 we present our structure learning algorithm for NeuralLog using MIL; in Section 4 we present the performed experiments and obtained results; in Section 5 we present the works related to ours; and we conclude and propose directions for future work in Section 6. 2
First-order logic programs are basically composed of two parts: (1) a set of logic
facts, that represents relations between logic entities; and (2) a set of rules that
reason over those facts. In this work, we are concerned about a speci c type of
rules called a Horn clause [
A Horn clause has the form of b(:) p1(:) ^ : : : ^ pn(:): (1) where b(:) is called the head of the clause and the set of pi is called the body and represents a conjunction. The Horn clause states that whenever the body is true, the head must also be true. b and pi are called predicates. In the parentheses, there might be constants, that represent logic entities and starts with a lower case letter; or variables, which are substituted by a constant in order to prove the rule, and starts with an upper case letter. Constants and variables are generically called term. A predicate name, followed by its terms is called an atom. Each predicate has a xed number of terms it accepts, which is called arity, and a predicate p of arity n is represented as p=n. Finally, a fact is represented by Horn clauses with empty body and no variables.
There are several algorithms that nd the proves of a logic rule. We refer
the reader to [
NeuralLog receives as input a set of facts weighted F with arity at most 2 and a set of rules R, both containing a set of entities E. For each distinct predicate p=2 of the set of facts, NeuralLog creates a matrix P 2 IRjEj jEj, in such a way that Pi;j = w, if there is a fact p(ei; ej ) with weight w in F ; otherwise, Pi;j = 0. Analogously, it represents facts of arity 1 as vectors and facts of arity 0 as scalars. A constant e is represented as an one-hot vector, whose value is 1 for the entry corresponding to the index of e and 0 anywhere else.
Finally, inference of rules are computed by mathematical operations on those matrices, given the numeric representation of the constant for the rst term in the head of the rule, and the result is a vector representation of the last term in the head of the rule, in such way that the values di erent from 0 correspond to logic proved constants. The result values of di erent rules with the same predicate in the head are summed, in order to obtain the nal result for the inference of the predicate.
NeuralLog also allows the de nition of numeric functions as predicates, that are applied to the vector representation of the variable of the predicate in the rule. We use this feature to apply activation and output functions to rules.
A neural network is a list of di erentiable operations that is applied into an
input in order to compute the output. These operations often include internal
parameters that are learned by the neural network through a gradient descent
algorithm [
The concern of this work is to nd a suited set of Horn clauses that creates a neural network in order to predict the examples of the task, given the background knowledge, where the examples are pairs of entities that are connected through a speci c relation. Given a relation and an (input) entity, we would like to predict all the (output) entities connected to it, through the given relation; this task is called link prediction.
NeuralLog creates a neural network for the relation, based on the set of rules, in order to predict the output entities, given the input entity. In addition, the weight of some predicates are speci ed to be learned by the neural network, through the gradient descent algorithm. 3
In this section we introduce NeuralLog+MIL, a structure learning algorithm
based on the Meta-Interpretive Learning (MIL) system Metagol [
MIL is a method that learns rst-order logic theories by the use of a
higherorder logic theory that will de ne the hypotheses space and guide the search of
the hypothesis in this space [
In rst-order logic, the predicate names in the rules, which represent the relations between the logic entities, are constant. In higher-order logic, those predicate names might be variable, and the logic inference system should nd the substitution of the name in order to prove the rule.
Metagol uses a modi ed Prolog meta-interpreter that generates a rst-order
logic theory that proves the positive examples, without proving the negative
ones, given the background knowledge. It does it by traversing a higher-order
theory in a similar way a SLD-Resolution algorithm would do [
NeuralLog+MIL takes a slightly di erent approach: instead of adding rules to the rst-order theory as needed, it creates a rst-order theory by adding all possible rules that satis es the higher-order program, given a pre-de ned depth. Each rule will then receive an associated weight and an activation function.
This approach is better suited to be integrated with NeuralLog, since a single neural network is created and the task to nd the weight of the rules is passed to the neural network optimization process. If we had followed Metagol's approach, we would have to create and evaluate several intermediary neural networks, which would be more computationally expensive.
Given a higher-order theory and a target predicate p, NeuralLog+MIL creates a \meta" SLD-Resolution tree, starting with a list of goals [q], replacing its terms by distinct variables, as the root node. Then, for each node in the tree, a child node is created by applying a meta-clause that uni es with one of the goals in the node; in the same way a conventional SLD-Resolution method would. The new child node is created with the list of goals from the parent node, with the goal, whose rule was applied, replaced by the body of the uni ed meta-clause.
We grow this tree, breadth- rst, by applying all possible meta-clauses to all goals in all nodes until we reach the maximum depth. Each edge represents the application of a meta-clause whose head was uni ed to the used goal in the parent node. For each path from the root to a leaf, we have a meta-program with variable predicates to be instantiated.
Finally, for each meta-program we generate a rst-order program by replacing the set of variable predicates for each possible predicate in the knowledge base. The nal program is the concatenation of all generated clauses in all the programs.
For instance, consider the higher-order theory in Table 1 and a target predicate p=2. The tree would start with the root node containing the goal [p(X; Y )], referred here as level 0. By applying each clause to the goal of the root node, we would end up with two nodes at level 1: the node [Q(X; Y )], generated by the uni ed clauses p(X; Y ) Q(X; Y ):; and the node [Q(X; Z); R(Z; Y )], generated by the uni ed clause p(X; Y ) Q(X; Z) ^ R(Z; Y ): After the addition of both nodes, the level 1 would be complete.
If we would like to go further in the resolution, we could apply the metaclause to each goal in the nodes and keep adding new nodes until a pre-de ned depth. Figure 1 shows an example of part of a tree until depth 3; where some nodes were omitted for clarity.
Q(X; Y ) Q0(X; Y ):
[Q0(X; Y )] Q0(X; Z) Q00(X; Z0) ^ R0(Z0; Z): [Q00(X; Y 0); R0(Y 0; Z); R(Z; Y )] p(X; Y ) Q(X; Y ):
p(X; Y ) Q(X; Z) ^ R(Z; Y ): [Q(X; Y )]
[Q(X; Z); R(Z; Y )] [p(X; Y )] Q(X; Y ) Q0(X; Z) ^ R(Z; Y ): [Q0(X; Z); R(Z; Y )]
R(Z; Y ) Q0(Z; Z0) ^ R0(Z0; Y ):
[Q0(X; Z); Q00(Z; Z0); R0(Z0; Y )]
In order to demonstrate the capabilities of NeuralLog to learn neural network
structure using MIL, we compared NeuralLog+MIL with Neural-LP [
We use these rank metrics to reproduce the experiments from Neural-LP [
UMLS. It is a dataset consisting of 46 relations between biomedical concepts. We
selected the most frequent relation (A ects) as target relation and applied the
system to predict this relation from the remaining ones. We randomly selected
90% of the facts from the target relation as training examples and the other 10%
as test. Following the procedure used in [
WordNet. It is a dataset consisting of 18 relations between words and it is already split into train, development and test sets. We ran each system once, holding out one relation at a time, and reported the mean results of the relations. UWCSE. It is already split into 5-folds for the Advised by relation. We run the system once for each fold and reported the mean results.
The used meta-theory was the one shown in Table 2, with the depth of 1. It means that each meta-clause is applied directly to the example. For instance, applying the rst clause to the example advisedby(X; Y ) would generate the clause advisedby(X; Y ) Q(X; Y ):, where Q is replaced for each valid predicate in the knowledge base (KB). If the depth were 2, in addition to replacing Q for each example in the KB, we would also have tried to prove it with another metaclause; for instance, the last one, which would result in an invented predicate f (X; Y ) Q(X; Z) ^ R(Z; Y ):
The head of each generated rule is changed from the target predicate p=2 to a predicate p0=2 and a rule of the form p0(X; Y ) p(X; Y ); output f unction(Y ): is added to the theory. Also, each generated rule has two atoms appended to it. The rst one is the atom activation f unction(Y ), where Y is the output of the rule, and it serves to applying an activation function to the output result of the rule. The second one is an atom of the form w(id), where id is an unique constant for each rule and w is a predicate whose weight will be learned by the network and will multiply the nal result of the rule. Finally, we add a rule of the form p(X; Y ) b: to the theory. Since this rule does not depend on the input, it will be true for any input and its value will be b, which will be added to the output of the other rules with the predicate p=2 in the head, acting as a bias. The value of the predicate b will also be learned by the network.
We used sigmoid as activation function and softmax as output function; and adagrad to minimize the binary cross-entropy with L2 regularization for 50 epochs in the case of the UMLS and UWCSE datasets, and 10 epochs for the WordNet dataset.
We used the default parameters for Neural-LP, which achieved good results in two of the three datasets. 4.2
Results Table 3 shows the results for each dataset. The lower the mean rank, the better; for the other metrics, the higher, the better. The best value of each metric, for each dataset is bold-faced. Pair of underlined values, of the same metric, in the same dataset, means that the di erence between the values has statistical signi cance according to the two-tailed paired t-test with p < 0:05.
As can be seen from the table, NeuralLog+MIL shows a competitive result with Neural-LP in both the UMLS and WordNet datasets; and is considerably better in the UWCSE dataset, for the hit at top 10 entities and the mean rank.
WordNet is composed of 18 relations with a di erent number of examples for each relation. If we take the average of the metrics, weighted by the number of examples of each relation, the di erence between NeuralLog+MIL and NeuralLP is even smaller, being 0:9280 against 0:9544, for the hit at top 10 entities; and 4:1480 against 6:1228, for the mean rank; for the NeuralLog+MIL and NeuralLP, respectively. In this scenario, the mean rank of NeuralLog+MIL is better than the one of Neural-LP.
Finally, from these results, we show that NeuralLog+MIL can learn the structure of NeuralLog models for link prediction tasks, a rmatively stating that NeuralLog+MIL can learn structure representations of NeuralLog models for link prediction tasks. 5
A strong feature of NeuralLog is that it can be used together with any other
neural network structure. In order to achieve this, the remaining of the neural
network must be de ned in the logic theory. TensorLog [
DeepProbLog also combines neural networks with rst-order logic. However,
its semantic is di erent from NeuralLog [
Traditional Inductive Logic Programming (ILP) systems try to nd logic
theories to prove a set of examples, given background knowledge in a pure logic
fashion [
Furthermore, the higher-order theory may also be used to nd the logic part that integrates with the neural network part, by specifying a constant predicate that will pose as a connection point between the logic part and the neural network. However, we left this for a future work.
The idea of applying MIL to systems based on rst-order logic is not novel.
A system that does that is the Iterated Structural Gradient (ISG) [
In this paper we presented NeuralLog+MIL, a structure learning system for the
NeuralLog language [
We showed that our approach has competitive results in the rank metrics for
the UMLS [
Furthermore, NeuralLog+MIL is suited to learn logic theories alongside other neural network de nitions in the NeuralLog language, while Neural-LP can only learn the entire logic theory from scratch. However, we left the analysis of models that combine logic parts with other neural network structures for future works.
We would also like to apply NeuralLog+MIL in relational tasks where (partially correct) theories are available in order to analyse if NeuralLog+MIL is able to improve the quality of the existing theory by appending clauses built by the higher-order theory.
In addition, we would also like to experiment learning with a deeper
metatheory in future works, which could take advantage of MIL capability of inventing
new predicates [
Acknowledgment Victor Guimar~aes was nanced by the Portuguese funding agency, FCT | Fundac~ao para a Ci^encia e a Tecnologia through Ph.D. scholarships 2020.05718.BD.