Knowledge Base Completion Using Embeddings and Rules

1 Introduction

Knowledge bases (KBs), e.g., WordNet [Miller, 1995], Freebase [Bollacker et al., 2008], and YAGO [Suchanek et al., 2007], are extremely useful resources for many AI related applications. KBs contain rich information of entities and their relations, stored in triples of the form (head entity, relation, tail entity), called facts. Although typical KBs may contain millions or even billions of facts, they are still greatly incomplete [West et al., 2014]. KB completion, i.e., automatically inferring missing facts from existing ones, has thus become an increasingly important task.

A promising approach to KB completion is to embed KBs into low-dimensional vector spaces [Bordes et al., 2011;

2013; 2014; Nickel et al., 2011; Socher et al., 2013]. Specifically, given a KB, entities and relations are first represented in a low-dimensional vector space, and for each triple, a scoring function is defined to measure its plausibility. Then, the representations of entities and relations (i.e. embeddings) are learned by maximizing the total plausibility of existing facts. For any missing fact, its plausibility can be predicted by using the learned embeddings. By learning and operating on latent representations, such embedding models are able to capture some unobservable but intrinsic properties of entities and relations [Jenatton et al., 2012].

The main drawback of KB embedding models is their purely data-driven fashion. Most of the previous embedding models make inferences based solely on existing facts, utilizing neither physical nor logical rules. Here, logical rules are those involving logic and deduction (e.g., entities linked by the relation HasWife should also be linked by the relation HasSpouse); physical rules refer to those non-logical ones enforcing physical restraints (e.g., both arguments of the relation HasSpouse need to be Person entities). Rules have been demonstrated to play a pivotal role in inference [Jiang et al., 2012; Pujara et al., 2013], and hence are of critical importance to KB completion.

In this paper, we propose a novel KB completion approach that infers missing facts using both embeddings and rules. The new approach formulates inference as a constrained maximization problem, or more specifically, an integer linear programming (ILP) problem. The objective function is the aggregated plausibility of all candidate facts, predicted by a specific KB embedding model; and the constraints are translated from physical and logical rules. Solving the optimization problem results in a set of facts which 1) have the highest plausibility predicted by the embedding model, and 2) comply with all the rules and hence are physically and logically favourable. Figure 1 sketches the approach.

The advantages of our approach are three-fold: 1) The use

enhances inference accuracy; 2) It naturally preserves the benefits of embedding models, capable of capturing intrinsic properties of data; 3) It is a general framework, applicable to a wide variety of embedding models and rules.

Moreover, given that KBs (especially those constructed by information extraction techniques) can be very noisy, we provide a simple, yet effective slacking technique to deal with the noise. The key idea is to explicitly model the noise with slack variables, allowing the observed triples to be false.

We evaluate our approach on publicly available data created using NELL [Carlson et al., 2010]. Experimental results show that by incorporating rules, our approach significantly and consistently outperforms state-of-the-art KB embedding models. Furthermore, the slacking technique is effective in identifying erroneous facts and ambiguous entities, with a precision higher than 90%.

2 RelatedWork

KB completion is to automatically infer missing facts based on existing ones in a KB. The literature falls into three major categories: 1) methods based on embedding strategies that model connections in a KB as resulting from latent factors (e.g. [Nickel et al., 2011; Bordes et al., 2013]); 2) methods based on Markov random fields (MRFs) that make inferences via first-order logic (e.g. [Jiang et al., 2012]) or probabilistic soft logic (e.g. [Pujara et al., 2013]); 3) methods based on path ranking algorithms that search entity connections using random walks (e.g. [Lao et al., 2011; Dong et al., 2014]). This paper focuses on the first category.

The key idea of embedding-based KB completion is to represent entities and relations in latent spaces and model candidate facts as resulting from latent factors. RESCAL [Nickel et al., 2011] and TransE [Bordes et al., 2013] are two typical methods, learning latent representations by minimizing a reconstruction loss or a margin-based ranking loss respectively. Other approaches include [Bordes et al., 2011; 2014; Socher et al., 2013; Wang et al., 2014; Lin et al., 2015; Guo et al., 2015]. During learning and inference, these embedding models only exploit existing facts, and do not make use of rules. TRESCAL [Chang et al., 2014] tries to encode rules into RESCAL. However, it focuses solely on a single rule (i.e., arguments of a relation should be entities of certain types). Rockt¨aschel et al. [2014] recently proposed to embed first-order logic into low-dimensional vector spaces. But in their work rules are not imposed directly for inference and cannot explicitly reduce the solution space. Our work differs in that we provide a general framework oriented towards inference, capable of incorporating various types of rules.

Rules, particularly logical rules, have been studied extensively in MRF-based KB completion approaches, represented in first-order logic [Richardson and Domingos, 2006] or probabilistic soft logic [Br¨ocheler et al., 2010]. This paper incorporates rules into embedding models, represented as constraints of a maximization problem. Moreover, besides logical rules, physical rules are also investigated in our approach.

Integer linear programming (ILP) refers to constrained optimization where both the objective and the constraints are linear equations with integer variables. It has been widely applied in many different areas, e.g., AI planning [Vossen et al., 1999; Do et al., 2007], natural language processing [Roth and Yih, 2004; Riedel and Clarke, 2006], and computational biology [Dittrich et al., 2008; Wang and Xu, 2013]. This paper employs ILP to integrate embedding models and rules in a unified framework for KB completion.

3 Our Approach

As illustrated in Figure 1, our approach consists of three key components: 1) We employ KB embedding models to predict the plausibility of each candidate fact; 2) We introduce physical and logical rules to impose restraints on candidate facts; 3) We integrate the first two components by ILP, with the objective function generated from the embedding models and the constraints translated from the rules. Facts inferred in this way will have the highest plausibility predicted by KB embedding, and at the same time comply with all the rules.

3.1 Embedding Knowledge Bases

Suppose we are given a KB consisting of n entities and m relations. The facts observed are stored as a set of triples O = {(ei, rk, ej)}. A triple (ei, rk, ej) indicates that entity ei and entity ej are connected by relation rk. KB embedding aims to 1) embed the entities and relations into a latent space, and 2) model and predict the plausibility of each candidate fact in that space. We employ three KB embedding models: RESCAL [Nickel et al., 2011], TRESCAL [Chang et al., 2014], and TransE [Bordes et al., 2013].

RESCAL represents each entity ei as a vector ei ∈ Rd and each relation rk as a matrix Rk ∈ Rd×d in the latent space. Given a triple (ei, rk, ej), a bilinear scoring function

is used to model the plausibility of the triple. {ei} and {Rk} are learned by minimizing a reconstruction loss, i.e.,

where y(k) ij equals one if the triple (ei, rk, ej) ∈ O and zero otherwise, and R = ∑i ‖ei‖22 + ∑k ‖Rk‖2F is a regularization term. An alternating least squares algorithm is adopted to solve the optimization problem.

TRESCAL is an extension of RESCAL, requiring the arguments of a relation to be entities of certain types. Given a relation rk, let Hk and Tk be the sets of entities with compatible types (e.g., for the relation CityLocatedInCountry, Hk contains City entities and Tk Country entities). Learning is then conducted by reconstructing legitimate triples, i.e.,

solved again by an alternating least squares algorithm. 1

1 Both RESCAL and TRESCAL are originally presented in matrix forms.

TransE represents both entities and relations as vectors in the latent space. Given a triple (ei, rk, ej) and the associated embeddings ei, ej , rk ∈ Rd , TransE uses the following scoring function to measure the plausibility of the triple:

{ei} and {rk} are learned by minimizing a margin-based ranking loss, enforcing positive (i.e. observed) triples to have higher plausibility than negative ones, i.e.,

where t+ = (ei, rk, ej) is a positive triple; Nt+ contains negative triples constructed by replacing the entities in t+; t- = (e′i , rk, e′j ) ∈ Nt+; and γ > 0 is a margin separating positive and negative triples. 2 Stochastic gradient descent is adopted to solve the optimization problem.

After we obtain the embeddings, for any missing triple, its plausibility can be predicted by using the scoring functions. Triples with higher plausibility are more likely to be true.

3.2 Imposing Physical &Logical Rules

We introduce three physical rules (Rule 1, 2, and 3) and a logical rule (Rule 4) to impose restraints on candidate facts.

Rule 1 (noisy observation). Facts that already exist are very likely, but not necessarily to be true. KBs, especially those constructed by information extraction techniques, can be very noisy. This rule is crucial in handling noisy KBs.

Rule 2 (argument type expectation). Arguments of a relation should be entities of certain types. For example, both arguments of the relation HasSpouse need to be Person entities. This rule is the same as considered in TRESCAL.

Rule 3 (at-most-one restraint). For 1-To-Many/Many-To-1 relations, the first/second argument can take at most one entity; for 1-To-1 relations, both arguments can take at most one entity. For example, CityLocatedInCountry is a Many-To-1 relation. Given any City entity, there exists at most one Country entity for which the resultant triple is true (i.e., a city locates in at most one country in the KB).

Rule 4 (simple implication). Suppose relation r1 implicates relation r2, denoted as r1 ↦→ r2. Then, any two entities linked by r1 should also be linked by r2. For example, HasWife ↦→ HasSpouse.

These rules contain rich prior knowledge, and can greatly reduce the solution space during inference.

3.3 Integrating by Integer Linear Programming

We aggregate the above two components and formulate inference as an ILP problem. For each candidate fact (ei, rk, ej), we use w(k) ij = f (ei, rk, ej) to represent the plausibility predicted by an embedding model, and introduce a Boolean decision variable x(k) ij to indicate whether the fact is true or false.

2 Bordes et al. [2013] referred to the scoring function as an energy function, and required positive triples to have lower energies. The two formulations are equivalent.

Figure 2: The associated ILP problem.

Our aim is then to find the best assignment to the decision variables, maximizing the overall plausibility and complying with all the rules. The ILP problem is given in Figure 2. 3 Here, t+ is a fact already observed; R1-M/RM-1/R1-1 refers to the set of 1-To-Many/Many-To-1/1-To-1 relations; and the ID before each constraint indicates the corresponding rule (e.g., constraint R1 is translated from Rule 1).

The most notable constraint is the first one, i.e., the noisy observation rule. We introduce a Boolean slack variable ϵ for each observed fact to explicitly model the noise: if ϵ = 1, the observed fact ought to be false (x = 0). And we penalize the objective function with the noise, encouraging the observed facts to be true (but not necessarily).

Our approach has the following advantages: 1) By incorporating rules, it significantly improves the inference accuracy of existing KB embedding models; 2) The noisy observation rule (more specifically the slack variables) can automatically identify noise in KBs; 3) It is a general framework, applicable to a wide variety of embedding models, and capable of incorporating various types of rules.

4 Experiments

We conduct experiments to test the performance of our approach in 1) retrieving head/tail entities and 2) predicting new facts. We further investigate the effectiveness of the slack variables in 3) automatic noise detection.

4.1 Data Sets

We create two data sets Location and Sport using NELL, both containing five relations (listed in Table 1) and the associated triples. On the Sport data set, for the last two relations, only those triples related to "sport" are included. On both data sets, entities appearing only once are further removed, resulting in 195 entities and 231 triples on Location, and 477 entities and 710 triples on Sport. In NELL, the entity type information is encoded in a specific relation called Generalization. From this information, we obtain the argument type expectation for each relation, as suggested in [Chang et al., 2014].

3 Constraint R4 might also be written as x(k1) ij ≤ x(k2) ji .

To identify the relation type (i.e., 1-To-Many, Many-To-1, or 1-To-1), we follow the strategy proposed in [Bordes et al., 2013]. For each relation, we compute the averaged number of heads ei (tails ej) appearing in the data set, given a tail ej (head ei). If the averaged number is smaller than 1.2, we label the argument as "1" and "Many" otherwise. We further create several simple implication rules on each data set. The argument types, relation types, and implication rules are given in Table 1. We will release the data upon request.

4.2 Retrieving Head/Tail Entities

This task is to complete a triple (ei, rk, ej) with ei or ej missing, i.e., predict ei given (rk, ej) or ej given (ei, rk). It is called link prediction in previous work [Bordes et al., 2011; 2013]. We test RESCAL, TRESCAL, and TransE in this task, before and after incorporating rules. A model with rules incorporated is denoted as r-RESCAL for example.

Evaluation protocol. To evaluate, for each data set, we split the triples into a training set and a test set, with the ratio of 4:1. The former is used for model training, and the latter for evaluation. 4 For each test triple, we replace the head/tail entity by each of the entities with compatible types, and rank the resultant corrupted triples in descending order, according to the plausibility (before incorporating rules) or the decision variables (after incorporating rules). Then we check whether the original correct triple ranks first. We corrupt head entities for 1-To-Many relations, tail entities for Many-To-1 relations, and both entities for 1-To-1 relations. Since these corrupted arguments are supposed to have only one correct answer, our protocol actually evaluates whether that answer could be retrieved. Aggregating all the test triples, we report the overall Hits@1, i.e., the proportion of cases in which the correct answer ranks first. The relation-specific Hits@1 is also reported, aggregated over the test triples with a specific relation.

The protocol is slightly different with that used in previous work [Bordes et al., 2011; 2013]. First, instead of iterating through all the entities, we corrupt a test triple using only those entities with compatible types. Chang et al. [2014] have demonstrated that removing triples with incompatible types during test time leads to better results. Second, we choose to report Hits@1 rather than Hits@10 (i.e. the proportion of correct answers ranked in the top ten). Since in our case each corrupted argument has only one correct answer, we believe it is more substantive to evaluate whether that answer ranks first, as opposed to just in the top ten.

4 Since we only have a small number of triples, it is difficult to hold out a validation set with meaningful size.

Implementation details. We implement RESCAL and TRESCAL in Java, and use the code released by Bordes et al. [2013] for TransE 5 . In RESCAL and TRESCAL, we fix the regularization parameter λ to 0.1, and the maximal number of iterations to 10, as suggested by Chang et al. [2014]. In TransE, we fix the margin to 1, the learning rate to 10, the batch number to 5, and the maximal number of iterations again to 10, which we found empirically to be enough to give the best performance. For each of the three models, we tune the the latent dimension d in the range of {10, 20, 30, 40, 50} and select the optimal parameter setting.

We then incorporate rules into the three models with optimal parameter settings using ILP. To generate the objective, plausibility predicted by RESCAL or TRESCAL is normalized by w′ij = wij/MAX, and plausibility predicted by TransE is normalized by w′ij = (wij -AVG) / (MAX -AVG). The ILP problems on Location data finally get 21,540 variables and 18,192 constraints, and the ILP problems on Sport data 241,268 variables and 194,788 constraints. We use the lp solve package 6 to solve the ILP problems. It takes about 1 minute on Location data and 2 hours on Sport data.

We repeat all experiments 10 times by drawing new training/test splits in each round. We report Hits@1 values averaged over the 10 rounds.

Quantitative results. Table 2 and Table 3 report the results on the test sets of the two data sets, where "H"/"T" indicates predicting head/tail entities for a relation. On Location data, the relation StateHasCapital gets a Hits@1 value of zero for all the methods, no matter predicting heads or tails. We remove that relation from Table 2. From the results, we can see that 1) The incorporation of rules significantly improves the performance of all the three embedding models on both data sets, with the Hits@1 values drastically enhanced. This observation demonstrates the superiority and generality of our approach. 2) RESCAL and TRESCAL perform better than TransE after incorporating rules, indicating that compared to margin-based ranking losses, embedding models based on reconstruction errors might be more preferred by the ILP framework. 3) The performance of TRESCAL is just comparable with that of RESCAL, showing that imposing the argument type expectation rule alone is not enough to bring better results. We need multiple rules, and our approach is definitely a proper choice for incorporating various rules.

5 https://github.com/glorotxa/SME

6 http://lpsolve.sourceforge.net/5.5/

Qualitative analysis. Figure 3 further provides a case study on the Location data set, to show how the rules can help an embedding model (i.e. RESCAL) in the entity retrieval task. Consider the test triple (City:Andorra La Vella, CityCapitalOfCountry, Country:Andorra) with the head corrupted. Without incorporating rules, RESCAL ranks the correct answer sixth, and the Hits@1 value associated with this case is zero. However, our training data tells that the answers ranked in the top five are capitals of other countries. By imposing the at-most-one restraint (i.e. a city can be the capital of at most one country), r-RESCAL rules out the top five answers and ranks the correct answer first. The Hits@1 value hence increases to one. This example indicates that rules are extremely useful in reducing the solution space during inference, and thus can greatly improve the performance of embedding models.

Consider this example again. Given the same test triple with the head corrupted, using the rules listed in Table 1 alone is not enough to retrieve the correct answer. Actually, based on the rules and the training data, only 75 among the total 94 cities which locate in or are capitals of other countries can be ruled out. The other 19 cities are all accepted by the rules. However, if we further consider the plausibility predicted by RESCAL, the correct answer will be promoted to the first. This example demonstrates the benefits of embedding models, resulted from learning and operating on latent variables. Our approach naturally preserves such benefits by integrating embedding models into the objective function.

4.3 Predicting New Facts

This task is to predict entire triples, rather than just heads or tails. We test RESCAL and TRESCAL in this task, before and after incorporating rules. 7

On each data set, we use all the observed triples for model training, and ask human annotators to judge the correctness of the top N triples predicted by each of the methods. For RESCAL and TRESCAL, we rank all candidate triples (i.e. unobserved ones with compatible entity types) in descending order according to their plausibility, and return those ranked in the top N. For r-RESCAL and r-TRESCAL, we use an additional constraint ∑k,i,j x(k) ij ≤ N ′ to conduct prediction. In all the methods, parameters are set to the optimal settings determined in Section 4.2. Note that in our data a same entity name can refer to different real-world entities (will be detailed in Section 4.4). Given a triple with an ambiguous entity name, we label it true as long as it holds for one real-world entity associated with the name. We report precision at the positions of 10, 20, 30, and 50.

Figure 4 reports the results on Location data. The results show that 1) r-RESCAL/r-TRESCAL consistently outperforms RESCAL/TRESCAL at all the positions. 2) The improvements are particularly significant for the topmost predictions. These observations again demonstrate the advantages of incorporating rules. We have conducted the same experiments on Sport data and observed similar phenomena.

7 We have also tested TransE, but it does not perform well on this task, particularly before incorporating rules.

4.4 Automatic Noise Detection

This task is to automatically detect noise in KBs. We test rRESCAL and r-TRESCAL in this task on Location data, with the optimal parameter settings determined in Section 4.2. In both methods, all the observed triples are used for model training, and those getting ϵ = 1 after solving the ILP problem are returned as noise. We then ask human annotators to judge the precision of the detection.

r-RESCAL identifies 22 suspicious triples, among which 21 are confirmed to be noise, with a detection precision higher than 95%. Table 4 lists the 21 triples, roughly categorized into three groups: factual errors, polysemy errors, and synonym errors. Factual errors refer to triples that are essentially false, e.g., the one stating that City:Los Angeles locates in State:Nevada. 8 Polysemy errors are caused by the phenomenon that a same entity name can refer to different real-world entities. City:Austin is such an ambiguous entity. We observe two triples related to it, stating that it locates in State:Colorado and State:Texas. And as a matter of fact, there do exist two different cities named Austin, located in the two states respectively. Synonym errors are caused by the phenomenon that a same real-world entity may have different names. For instance, State:Illinois and State:IL refer to the same entity, with the latter being an abbreviation of the former. Ambiguous entities are marked by stars in Table 4. r-TRESCAL performs similarly to r-RESCAL, with 22 suspicious triples identified and 20 of them confirmed to be noise, getting a precision higher than 90%. The results demonstrate the effectiveness of the slack variables in detecting erroneous facts and ambiguous entities.

4.5 Discussions

Although powerful in the tasks described above, our approach gets two limitations. First, it can only cope with 1-To-Many, Many-To-1, or 1-To-1 relations, but cannot handle Many-ToMany relations. The reason is that without introducing the atmost-one constraints, the ILP problem given in Figure 2 tends to predict all triples with positive plausibility (w(k) ij > 0) to be true, leading to poor inference accuracy. Statistics show that in some KBs, only a small faction (lower than 25%) of the relations are Many-To-Many relations [Bordes et al., 2013], making our approach still appealing for most cases.

8 Los Angeles is actually a city located in California.

Second, solving the ILP problem given in Figure 2 is timeconsuming, which limits the efficiency and scalability of our approach. A possible solution is to decompose the ILP problem into multiple small-scale sub-problems for large KBs. Specifically, given that the objective function, the constraints R1, R2, and R3 are decomposable by different relations, we can simply decompose the ILP problem according to constraint R4. That is, two relations are assigned to a same group if one implicates the other. In this way, each of the resultant sub-problems corresponds to a small number of relations that implicate each other. Such a divide-and-conquer strategy is almost always practical for different KBs, and to some extent addresses the scalability issue.

5 Conclusion and FutureWork

In this paper, we propose a novel KB completion approach which integrates embedding models and rules in a unified framework. It formulates inference as solving an ILP problem, where the objective function is generated from embedding models and the constraints are translated from rules. Facts inferred in this way are the most preferred by the embedding models, and at the same time comply with all the rules. The incorporation of rules significantly reduces the solution space and enhances the inference accuracy. To handle noise in KBs, a slacking technique is further proposed. We empirically evaluate our approach in entity retrieval and new fact prediction. Experimental results show significant and consistent improvements over state-of-the-art embedding models. Moreover, the slacking technique is demonstrated to be effective in automatic noise detection.

As future work, we plan to 1) Make our approach more efficient by acceleration or approximation, so as to handle larger KBs and more complicated rules such as r1(ei, ej) ∧

r2(ei, ej) ⇒ r3(ei, ej). 2) Investigate the possibility of incorporating rules during embedding rather than after embedding. It might result in more accurate embeddings, and benefit various tasks besides KB completion, e.g., relation extraction and entity resolution.

Acknowledgments

We would like to thank the anonymous reviewers for their valuable comments and suggestions. This work is supported by the National Natural Science Foundation of China (grant No. 61402465), the Strategic Priority Research Program of the Chinese Academy of Sciences (grant No. XDA06030200), and the National Key Technology R&D Program (grant No. 2012BAH46B03).