We present ways of incorporating logical rules into the construction of embedding based Knowledge Base Completion (KBC) systems. Enforcing “logical consistency” in the predictions of a KBC system guarantees that the predictions comply with logical rules such as symmetry, implication and generalized transitivity. Our method encodes logical rules about entities and relations as convex constraints in the embedding space to enforce the condition that the score of a logically entailed fact must never be less than the minimum score of an antecedent fact. Such constraints provide a weak guarantee that the predictions made by our KBC model will match the output of a logical knowledge base for many types of logical inferences. We validate our method via experiments on a knowledge graph derived from WordNet.
t = [eT ;e0T ]T . We will use the semicolon symbol ; as an infix operator to denote vector concatenation, i.e. (x;y) = [xT ;yT ]T . Finally, x y denotes that the vector x is elementwise larger than y and B(x;r) denotes the L2 ball centered at x with radius r.
Score Function: A majority of the existing work on embedding based KBC measures the correctness of a fact via a scoring function, score: R E E!R, with the property that when score(f ) > score(f 0), fact f is more likely to be correct than f 0. The two major classes of score functions are: score(f ) = hr;ti (1) score(f ) = jjr tjj2 (2) In Equations (1–2), r and t are vector representations of r and t = (e;e0), respectively, that are constituents of f = (r;(e;e0)). For brevity, we will omit this expansion from here onwards.
Unconstrained Objectives for Learning Score Function Rendle et al. 2009 proposed the Bayesian Personalized Ranking
(BPR) objective as a way of tuning recommendation systems when a user can only observe positive training data, such as correct
facts, but the facts that are absent may be either correct or incorrect. In this paper we will focus on the BPR objective since this
objective has been used for learning the parameters of a KBC system by various researchers
BPR posits that the training data is a single joint sample of U(U 1) bernoulli random variables fbff0 j f 2 U ;f 0 2 U ;f 0 =6 f g. bff0 equals 1 when f is in F and f 0 is in F c and 0 otherwise. bff0 is parameterized by its probability pff0 and all bff0 are conditionally independent given the probabilities pff0 . The probability values must obey the reasonable condition that pff0 = 1 pf0f . A natural way to satisfy this condition is to parameterize pff0 as (score(f ) score(f 0)) where is the sigmoid function.2 The BPR estimator is simply the L2 regularized MLE estimator of this probabilistic model, with regularization strength . Table 1 lists instances of the BPR objective that arise with different score functions.
Model A j t = (e;e0) R j t = e
B t = (e;e0;eT e0) C j t = (e;e0) e0 e0 T j t = e
D t = (e;e0jje e0jj) (1) (1) (2) (2) score
X log (f;f)2F Fc
(f;f)2F Fc r2R t2E
X log( (hr1;ei+hr2;e0i+he;e0i (f;f)2F Fc
X log( (jjr tjj2 jjr tjj2))+ (Xjjrjj2+Xjjejj2) (f;f)2F Fc r2R t2E jjr1 ejj2+jjr2 e0jj2+jje e0jj2! jjr1 ejj2 jjr2 e0jj2
jje e0jj2 hr1;ei hr2;e0i he;e0i))+ (Xjjrjj2 +Xjjejj2) r2R t2E +
Logical Consistency of Embeddings through Constraints Our general scheme for incorporating logical relations into embeddings is to ensure that during the learning of the vector representation of entities and relations, the score of a consequent fact will be greater than the score of any of its antecedents. In other words if f1;:::;fn 1 =) fn then score(fn) mini2[1;n 1](score(fi)). If this does not hold true, then it will be possible for our KB to assign a low score to a logically entailed fact even though all of its antecedents have a high score.
We analyze common logical rules found in large scale KBs and for different combinations of a logical rule and scoring function we devise inequalities that the score function should satisfy. We translate those inequalities into constraints that restrict the entity and relation representations in a KB. We use the projected subgradient descent algorithm for learning the parameters of our KBS system. Algorithm 1 shows a specific instance, for Model A and batch size 1, of our parameter learning algorithm with a general set of rules L. We now show how to construct convex constraints from logical rules. 2.1
Constraints for Logical Consistency: Relational Implication We now present the constraints for guaranteeing that the predictions from embeddings based KBC systems are consistent with logical rules starting with implication rules. An implication rule of the form, RELIMP(r;r0), specifies that if a fact f = (r;t) is correct, then (r0;t) must also be correct. For example, the rule RELIMP(Husband Of, Spouse Of) enforces that if our KB predicts the fact, (HusbandOf,(Don, Mel)), then it will also predict (SpouseOf,(Don, Mel)). As explained above we can enforce such a rule by ensuring that score(r0;t) score(r;t) 8t 2 T . 3
When we use the inner product score function (1) then this inequality can be enforced by ensuring that hr0 r;ti 0 for all t 2 T . We constrain t to lie in a subset of Rd, say T, then the implication rule can be enforced by constraining r0 r to lie in the dual cone of T, denoted T . A very convenient special case arises when we chose T to be a “self dual cone” for which T = T . The set of positive real vectors Rd+ is one example of such a self dual cone. 4
When we use the L2 distance score function (2) then the restriction on the score function translates into the following constraints on the vector representations: jjr tjj2 jjr0 tjj2 0 =) hr r0;r0 + r 2ti 0 =) hr r0;r0 + ri=2 hT(r r0). Here hT(x) is the value of the support function of T at x which is defined as hT(x) = supt2Thx;ti. It is necessary and sufficient for the feasibility of this constraint that the hT function should be finite for at least one value of x = r r0. Once we have fixed r r0 then r+r0 can be easily chosen from the halfspace H (r0 r;2hT(r r0)). Note that if hT is difficult to compute then implementing this constraint will also be difficult, therefore we must chose T wisely.
One example of a good choice of T is Rd+. hRd+ (r r0) is finite and zero iff r r0 0 therefore, the value of r+r0 must lie in the halfspace hr r0;r0 +ri 0. Unfortunately, the problem of finding r and r0 vectors that satisfy this constraint is non-convex and it is not possible to project on to this set given a pair of vectors that violate the constraints. We remedy this situation by adding an additional constraint that r + r0 must also lie in the negative orthant, i.e. r + r0 0. Table 2 presents all the derived constraints. Unfortunately, since the T model defines t = e e0, therefore it is not possible to set T = Rd+. In the case of the T model if we constrain e to lie in B(0; ) then t must lie in B(0;2 ) and hT(r r0) = 2 (r r0) =) hr r0;r0+ri 4 . One way to make this constraint amenable to efficient projection is to enforce that r+r0 = 4 (r r0) and jjr r0jj2 jjr1 =r0)jj jjr0jj2 j2 :5j. This constraint becomes trivial if = 0:25 2.1.1
Reverse Relational Implication and Symmetry A reverse relational implication rule denoted by REVIMP(r;r0) specifies that if (r;(x;y)) is correct, then (r0;(y;x)) is also correct for all (x;y) 2 T . This rule can be enforced through the inequality that score(r0;y;x) score(r;x;y). Depending on the model let r = (r1;r2) or (r1;r2;1 or 0) as shown in Table 1, and similarly decompose r0. We will omit this detail in later sections. Under models A and B, this inequality translates to the following constraint hy;r01i+hx;r02i hx;r1i+hy;r2i and under models C and D, the necessary constraints are hr1 r02;r1 + r02 2xi hr01 r2;r01 + r2 2yi. Stronger versions of these constraints, which are more efficient to enforce, are shown in Table 2.
A symmetry rule denoted as SYMM(r) specifies that if the fact (r;(e;e0)) is known to be correct then (r;(e0;e)) is also correct. We can only comply with this logical rule in an embedding base KB by ensuring that score(r;e;e0) = score(r;e0;e). Under all 4 score models this rule can be enforced only by ensuring that r1 = r2. 2.1.2
Entailment A type A entailment logical rule denoted as ENTAILA(r;e;r0;e0) specifies that (r;(e;x)) implies (r0;(e0;x)) for all x in E.5 A Type B entailment rule, ENTAILB(r;e;r0;e0) specifies that (r;(x;e)) implies (r0;(x;e0)). r and r0 may denote the same relation. For example, the rule ENTAILB(IsA,Man,IsA,Mortal) can be used to enforce that if (IsA,(Socrates,Man)) then the KB must also predict that (IsA, (Socrates,Mortal)). The final constraints required to implement a type B entailment rule are shown in Table 3.6 2.1.3
Property Transitivity A property transitivity rule denoted PROTRANS(r;r0;e0;r00;e00) specifies that if (r;(x;y)) and (r0;(y;e0)) are true then (r00;(x;e00)) is also true. For example, the rule PROTRANS(Partner,Convicted,Criminal,Suspected,Criminal) can be used to incorporate the common sense rule that if an entity is the partner of a convicted criminal then it will be suspected of being a criminal into the embeddings based KB. Note that the score of the hypothesis fact (r00;(x;e00)) should be high if the antecedent facts have high 3We abuse notation in saying that score(r;(x;y))=score(r;x;y).
4Other self-dual cones, distinct from Rd+ also exist such as the Lorentz cone fx 2 Rd j xd details on the geometry of closed convex cones and their polar and dual sets.
5We use the term, entailment, in the sense of entailment of properties. Note that this is different from implication.
6Details: To implement a type B entailment rule we need to ensure that score(r0;x;e0) score(r;x;e) for all x2E. Under model A this inequality translates to, hr01 r1;xi hr2;ei hr02;e0i. Model B requires hr01 r1 +e0 e;xi hr2;ei hr02;e0i. Model C requires hr1 r01;r1 +r01 2xi hr02 e0 +r2 e;r02 e0 r2 +ei, and finally the constraints over model D’s score functions are hr1 r01;r1 +r01i+he e0;e+e0i hr02 e0 r2 +e;r02 e0 +r2 ei 2hr1 r01 e e0;xi.
qPid=11xi2g. We refer the reader to
hy; r2 +(1 score for any possible entity y. A natural way in which we can incorporate such a rule into score based KBC models is by ensuring that score(r00;x;e00) maxy2E min(score(r;x;y);score(r0;y;e0)). In order to derive efficient constraints that can enforce this inequality we strengthen the constraint imposed on the score function by replacing the min function in the lower bound to a convex combination of the scores, i.e. let 2 (0;1), we enforce the inequality that score(r00;x;e00) maxy2E score(r;x;y)+(1 )score(r0;y;e0) .
Since a convex combination of two values is greater than their minimum, this stronger inequality translates to the following con(1 r1+e00 , b = (1 )(r01+e0)+ r1 ,
)r01i. Let a = r010 )hr02;e0i , and let E contain the set fe j e 2 Eg. For Model B, the above inequality on the score function leads to the the constraint: 8x;y 2 E; hx;yi hx;ai + hy;bi + c. Remember that our goal is to devise a set E, and constraints on relation embeddings such that it is efficient to project onto it and for which the above inequality can be guaranteed. The following proposition – proof ommitted for lack of space – shows how to construct such a set:
d Proposition 1. Let x;y be members of R+ \B(a;jjajj) and a 0 then hx;yi hx+y;ai.
The above proposition shows that if a = b and c d 0 then by setting E = R+ \B(a;jjajj) we can satisfy the above constraints.
Alg. 1 Projected SGD for Model A, Batch Size=1
ProjL (t;t) 2.1.4
Type Implication
C, D
R
Constraints r r0 r r0 r r02 r1, r01 r1 r02 matrix(r0)
r2 r1, r2 r01 matrix(r)
r2.
A type implication rule, denoted as TYPEIMP(r;e;r0), specifies that if the fact (r;(x;y)) is correct then (r0;(x;e)) is also correct 8(x;y) 2 T . In other words, this rule enforces that positional arguments of a relation possess certain properties. For example, the rule TYPEIMP(Husbandof,Man,Gender) can enforce that if our KB predicts the fact that (Husbandof,(Don,Mel)) then it also predicts that (Gender,(Don,Man)).
Under model A the TYPEIMP(r; e; r0) rule translates to the following inequality for the parameters hx; r01i hx; r1i
hy;r2i he;r02i8(x;y) 2 T . Let a = e+ r01 r1, b = r2 and c = hr02;ei. Under model B, the restriction on the score function
translates to: hx;yi ha;xi + hb;xi + c. The analysis for this case again relies on Propostion 1 and the analysis for models C
and D is yet out of reach. See Table 3.
The problem of enforcing consistency between the predictions made by a machine learning system and a first order logic system,
which is what our work attempts to do, has a large history of research but we will only be able to review recent work on learning
representations of entities and relations of a knowledge graph and refer the reader to reviews of neural-symbolic systems
Our method for training embeddings based KBC systems allows for a very interesting application of solving logical puzzles using an embeddings based KBC system without using an external logical-symbolic subsystem. We perform a controlled experiment where we compare the performance of an embedding based KBC system trained with the constraints versus a system that has been trained without those constraints.
Data Consider the logical deduction problem shown in Table 5. This is a simplified version of a logical puzzle presented in
Rules RELIMP(TradeWith,TransactWith) ENTAILB(Possess,WMD,Considered,Enemy) PROTRANS(TransactWith,Enemy, Considered,Criminal,Considered)
Facts (Possess,(Nono,WMD)) (TradeWith,(Benedict,Nono))
Query ? (Considered,(Benedict,Criminal))
Evaluation We train two versions of two KBC systems, Models A and B, with batch size= 1, = 0:001; = 0:1;S = 200;d = 50, and d~ = 25 using Algorithm 1. Both KBs were trained in one pass using the two training facts. The only difference was that the baseline system did not constrain the embeddings to obey logically derived geometric constraints. After training we queried the KBs for the scores of all possible facts. We ranked all the facts based on their scores, excluding the training facts, and marked all facts that could be logically entailed from the two training facts as correct results and the rest of them as incorrect. We performed 10 runs and in each run we computed the MRR, P@10, MAP for the two models. Finally we averaged these quantities over 10 runs.
Results Table 6 shows that our method was able to rank logically entailed facts with much higher precision and recall than the baseline systems. This validates our intuition that logical rules can be usefully incorporated into the parameter learning mechanism of a KBC system via simple geometric constraints even for low dimensional embeddings. The reason for the large improvement in performance by the ELKB system in comparison to the baseline is that the ELKB model makes the score of entailed facts higher than the score of non-entailed facts because of the constraints during learning. E.g. the scores of entailed facts such as (Considered,(Nono, Enemy)), and (TransactWith,(Benedict, Nono)) are forced to be high in comparison to non-entailed facts such as (Trade With,(Benedict,WMD)). In comparison the baseline method does not have this systematic advantage and its scores remain unchanged. 4.1
Link Prediction on WordNet
In the link prediction task, the KBC system is given incomplete facts, with either a missing head entity or tail entity, i.e. given
either (r;( ;e0)), or (r;(e; )) the system has to predict e or e0 respectively. We evaluated the utility of proposed constraints by
comparing the performance of model A and model B trained with and without the constraints. We now present the results of
our experiments on the WN18 knowledge graph,7 derived from WordNet, and released by
Data The WN18 dataset comes with standard train, development and test splits. These three splits of the data contain 141442,
5000, and 5000 facts respectively. The total number of relations in the WN18 dataset is 18 and the number of entities is 40,943.
Recently
For all the models we fixed batch size= 10, = 0:001; = 0:125;S = 200;d~ = 100, for model T , d = 100 and otherwise d = 200. Following existing work we measured the MRR, HITS@3 and Hits@10 metrics and report their average over the two tasks of head entity prediction and tail entity prediction. Instead of training in a single pass we trained our models for 50 epochs on the WN18 dataset and chose the best parameters using early stopping on the validation set. In other words, we used the parameters from that epoch which performed the best on the validation set in terms of the HITS@10 metric. Finally, we combined the predictions of the best performing T model and the best performing system based on model B. In order to combine the two ranking systems we trained a logistic regression classifier using the default settings in vowpal webbit9 to first predict whether model T or model B will produce a better ranking and then output that system’s ranking over entities for evaluation. Our logistic regression classifier had 73% accuracy on the training data and 70% accuracy over the test data. By using this third system we were able to create a single ranking system that performed better than model T which is very similar to the TransE model.10
Results Table 7 shows that both the constrained and unconstrained versions of model A perform quite poorly. This is to be expected since model A scores a triplet (r;(e;e0)) as hr;ei+hr;e0i. Regardless of e0, the ranking produced by the model will remain the same. Therefore model A is clearly unsuitable for this task, for similar reason model C is also an unsuitable model. However the drastic improvement in the performance of model B when it is trained according to the Table 7: MRR, HITS@3 and HITS@10 of the constrained and constraints corresponding to the REVIMP rules demonstrates unconstrained versions of models A, B and unconstrained T. B+T the utility of our proposed constraints. After adding the con- reports the results of combining models B and model T. straints, the MRR increased almost 3 times and the value of HITS@10 by 4 times from 0:137. Recall that at test / inference time the constraints do not play any role so the only role of the constraints is as a form of regularization on the parameters of the model. 7We found that the performance of models C;D and R was too low therefore we do not report their results. 8aclweb.org/anthology/attachments/D/D16/D16-1019.Attachment.zip 9https://github.com/JohnLangford/vowpal_wabbit 10The main differences between model T and TransE are that TransE used hinge loss versus the BPR objective. TransE does not regularize the relation embeddings and forces the entity embeddings to lie on the unit sphere, instead in model T we add a quadratic regularization term to regularize the embeddings.