An Interpretable Knowledge Transfer Model for Knowledge Base Completion

Introduction

Knowledge bases (KB), such as WordNet (Fellbaum 1998), Freebase (Bollacker et al. 2008), YAGO (Suchanek et al. 2007) and DBpedia (Lehmann et al. 2015), are useful resources for many applications such as question answering (Berant et al. 2013; Yih et al. 2015; Dai et al. 2016) and information extraction (Mintz et al. 2009). However, knowledge bases suffer from incompleteness despite their formidable sizes (Socher et al. 2013; West et al. 2014), leading to a number of studies on automatic knowledge base completion (KBC) (Nickel et al. 2015) or link prediction.

The fundamental motivation behind these studies is that there exist some statistical regularities under the intertwined facts stored in the multi-relational knowledge base. By discovering generalizable regularities in known facts, missing ones may be recovered in a faithful way. Due to its excellent generalization capability, distributed representations, a.k.a. embeddings, have been popularized to address the KBC task (Nickel et al. 2011; Bordes et al. 2011; Bordes et al. 2014; Bordes et al. 2013; Socher et al. 2013; Wang et al. 2014; Guu et al. 2015; Nguyen et al. 2016b).

As a seminal work, Bordes et al. 2013 proposes the TransE, which models the statistical regularities with linear translations between entity embeddings operated by a relation embedding. Implicitly, TransE assumes both entity embeddings and relation embeddings dwell in the same vector space, posing an unnecessarily strong prior. To relax this requirement, a variety of models first project the entity embeddings to a relation-dependent space (Bordes et al. 2014; Ji et al. 2015; Lin et al. 2015b; Nguyen et al. 2016b), and then model the translation property in the projected space. Typically, these relation-dependent spaces are characterized by the projection matrices unique to each relation. As a benefit, different aspects of the same entity can be temporarily emphasized or depressed as an effect of the projection. For instance, STransE (Nguyen et al. 2016b) utilizes two projection matrices per relation, one for the head entity and the other for the tail entity.

Despite the superior performance of STransE compared to TransE, it is more prone to the data sparsity problem. Concretely, since the projection spaces are unique to each relation, projection matrices associated with rare relations can only be exposed to very few facts during training, resulting in poor generalization. For common relations, a similar issue exists. Without any restrictions on the number of projection matrices, logically related or conceptually similar relations may have distinct projection spaces, hindering the discovery, sharing, and generalization of statistical regularities.

Previously, a line of research makes use of external information such as textual relations from web-scale corpus or node features (Toutanova et al. 2015; Toutanova and Chen 2015; Nguyen et al. 2016a), alleviating the sparsity problem. In parallel, recent work has proposed to model regularities beyond local facts by considering multi-relation paths (García-Durán et al. 2015; Lin et al. 2015a; Shen et al. 2016). Since the number of paths grows exponentially with its length, as a side effect, path-based models enjoy much more training cases, suffering less from the problem.

In this paper, we propose an interpretable knowledge transfer model (ITransF), which encourages the sharing of statistic regularities between the projection matrices of relations and alleviates the data sparsity problem. At the core of ITransF is a sparse attention mechanism, which learns to compose shared concept matrices into relation-specific projection matrices, leading to a better generalization property. Without any external resources, ITransF improves mean rank and Hits@10 on two benchmark datasets, over all previous approaches of the same kind. In addition, the parameter sharing is clearly indicated by the learned sparse attention vectors, enabling us to interpret how knowledge transfer is carried out. To induce the desired sparsity during optimization, we further introduce a block iterative optimization algorithm.

In summary, the contributions of this work are: (i) proposing a novel knowledge embedding model which enables knowledge transfer by learning to discover shared regularities; (ii) introducing a learning algorithm to directly optimize a sparse representation from which the knowledge transferring procedure is interpretable; (iii) showing the effectiveness of our model by outperforming baselines on two benchmark datasets for knowledge base completion task.

Notation and Previous Models

Let $E$ denote the set of entities and $R$ denote the set of relations. In knowledge base completion, given a training set $P$ of triples $(h,r,t)$ where $h,t\in E$ are the head and tail entities having a relation $r\in R$, e.g., (Steve Jobs, FounderOf, Apple), we want to predict missing facts such as (Steve Jobs, Profession, Businessperson).

Most of the embedding models for knowledge base completion define an energy function $f_{r}(h,t)$ according to the fact’s plausibility (Bordes et al. 2011; Bordes et al. 2014; Bordes et al. 2013; Socher et al. 2013; Wang et al. 2014; Yang et al. 2015; Guu et al. 2015; Nguyen et al. 2016b). The models are learned to minimize energy $f_{r}(h,t)$ of a plausible triple $(h,r,t)$ and to maximize energy $f_{r}(h^{\prime},t^{\prime})$ of an implausible triple $(h^{\prime},r,t^{\prime})$.

To better model relation-specific aspects of the same entity, TransR (Lin et al. 2015b) uses projection matrices and projects the head entity and the tail entity to a relation-dependent space. STransE (Nguyen et al. 2016b) extends TransR by employing different matrices for mapping the head and the tail entity. The energy function is

However, not all relations have abundant data to estimate the relation specific matrices as most of the training samples are associated with only a few relations, leading to the data sparsity problem for rare relations.

Interpretable Knowledge Transfer

As discussed above, a fundamental weakness in TransR and STransE is that they equip each relation with a set of unique projection matrices, which not only introduces more parameters but also hinders knowledge sharing. Intuitively, many relations share some concepts with each other, although they are stored as independent symbols in KB. For example, the relation “(somebody) won award for (some work)” and “(somebody) was nominated for (some work)” both describe a person’s high-quality work which wins an award or a nomination respectively. This phenomenon suggests that one relation actually represents a collection of real-world concepts, and one concept can be shared by several relations. Inspired by the existence of such lower-level concepts, instead of defining a unique set of projection matrices for every relation, we can alternatively define a small set of concept projection matrices and then compose them into customized projection matrices. Effectively, the relation-dependent translation space is then reduced to the smaller concept spaces.

However, in general, we do not have prior knowledge about what concepts exist out there and how they are composed to form relations. Therefore, in ITransF, we propose to learn this information simultaneously from data, together with all knowledge embeddings. Following this idea, we first present the model details, then discuss the optimization techniques for training.

where $\boldsymbol{\alpha}_{r}^{H},\boldsymbol{\alpha}_{r}^{T}\in^{m}$, satisfying $\sum_{i}\boldsymbol{\alpha}_{r,i}^{H}=\sum_{i}\boldsymbol{\alpha}_{r,i}^{T}=1$, are normalized attention vectors used to compose all concept projection matrices in $\mathbf{D}$ by a convex combination. It is obvious that STransE can be expressed as a special case of our model when we use $m=2|R|$ concept matrices and set attention vectors to disjoint one-hot vectors. Hence our model space is a generalization of STransE. Note that we can safely use fewer concept matrices in ITransF and obtain better performance (see section 4.3), though STransE always requires $2|R|$ projection matrices.

We follow previous work to minimize the following hinge loss function:

where $P$ is the training set consisting of correct triples, $N$ is the distribution of corrupted triples defined in section 3.3, and $[\cdot]_{+}=\max(\cdot,0)$. Note that we have omitted the dependence of $N$ on $(h,r,t)$ to avoid clutter. We normalize the entity vectors $\mathbf{h},\mathbf{t}$, and the projected entity vectors $\boldsymbol{\alpha}_{r}^{H}\cdot\mathbf{D}\cdot\mathbf{h}$ and $\boldsymbol{\alpha}_{r}^{T}\cdot\mathbf{D}\cdot\mathbf{t}$ to have unit length after each update, which is an effective regularization method that benefits all models.

Sparse attention vectors

In Eq. (1), we have defined $\boldsymbol{\alpha}_{r}^{H},\boldsymbol{\alpha}_{r}^{T}$ to be some normalized vectors used for composition. With a dense attention vector, it is computationally expensive to perform the convex combination of $m$ matrices in each iteration. Moreover, a relation usually does not consist of all existing concepts in practice. Furthermore, when the attention vectors are sparse, it is often easier to interpret their behaviors and understand how concepts are shared by different relations.

with $\tau$ being the temperature of Softmax.

where $\mathcal{L}$ is the loss function defined in Eq. (2).

2 Block Iterative Optimization

For convenience, we refer to the parameters with and without the sparse constraints as the sparse partition and the dense partition, respectively. Based on this notion, the high-level idea of the approximated algorithm is to iteratively optimize one of the two partitions while holding the other one fixed. Since all parameters in the dense partition, including the embeddings, the projection matrices, and the pre-softmax scores, are fully differentiable with the sparse partition fixed, we can simply utilize SGD to optimize the dense partition. Then, the core difficulty lies in the step of optimizing the sparse partition (i.e. the sparse assignment vectors), during which we want the following two properties to hold

Satisfying the two criterion seems to highly resemble the original problem defined in Eq. (3). However, the dramatic difference here is that with parameters in the dense partition regarded as constant, the cost function is decoupled w.r.t. each relation $r$. In other words, the optimal choice of $\mathbf{I}_{r}^{H},\mathbf{I}_{r}^{T}$ is independent of $\mathbf{I}_{r^{\prime}}^{H},\mathbf{I}_{r^{\prime}}^{T}$ for any $r^{\prime}\neq r$. Therefore, we only need to consider the optimization for a single relation $r$, which is essentially an assignment problem. Note that, however, $\mathbf{I}_{r}^{H}$ and $\mathbf{I}_{r}^{T}$ are still coupled, without which we basically reach the situation in a backpack problem. In principle, one can explore combinatorial optimization techniques to optimize $\mathbf{I}_{r^{\prime}}^{H},\mathbf{I}_{r^{\prime}}^{T}$ jointly, which usually involve some iterative procedure. To avoid adding another inner loop to our algorithm, we turn to a simple but fast approximation method based on the following single-matrix cost.

Specifically, for each relation $r$, we consider the induced cost $\mathcal{L}_{r,i}^{H}$ where only a single projection matrix $i$ is used for the head entity:

Now, in order to choose the best $k$ matrices, we basically ignore the interaction among projection matrices, and update $\mathbf{I}_{r}^{H}$ in the following way:

Analogously, we can define the single-matrix cost $\mathcal{L}_{r,i}^{T}$ and the energy function $f_{r,i}^{T}(h,t)$ on the tail side in a symmetric way. Then, the update rule for $\mathbf{I}_{r}^{H}$ follows the same derivation. Admittedly, the approximation described here is relatively crude. But as we will show in section 4, the proposed algorithm yields good performance empirically. We leave the further improvement of the optimization method as future work.

3 Corrupted Sample Generating Method

Recall that we need to sample a negative triple $(h^{\prime},r,t^{\prime})$ to compute hinge loss shown in Eq. 2, given a positive triple $(h,r,t)\in P$. The distribution of negative triple is denoted by $N(h,r,t)$. Previous work (Bordes et al. 2013; Lin et al. 2015b; Yang et al. 2015; Nguyen et al. 2016b) generally constructs a set of corrupted triples by replacing the head entity or tail entity with a random entity uniformly sampled from the KB.

However, uniformly sampling corrupted entities may not be optimal. Often, the head and tail entities associated a relation can only belong to a specific domain. When the corrupted entity comes from other domains, it is very easy for the model to induce a large energy gap between true triple and corrupted one. As the energy gap exceeds $\gamma$, there will be no training signal from this corrupted triple. In comparison, if the corrupted entity comes from the same domain, the task becomes harder for the model, leading to more consistent training signal.

Motivated by this observation, we propose to sample corrupted head or tail from entities in the same domain with a probability $p_{r}$ and from the whole entity set with probability $1-p_{r}$. The choice of relation-dependent probability $p_{r}$ is specified in Appendix A.1. In the rest of the paper, we refer to the new proposed sampling method as ”domain sampling”.

Experiments

To evaluate link prediction, we conduct experiments on the WN18 (WordNet) and FB15k (Freebase) introduced by Bordes et al. 2013 and use the same training/validation/test split as in (Bordes et al. 2013). The information of the two datasets is given in Table 1.

In knowledge base completion task, we evaluate model’s performance of predicting the head entity or the tail entity given the relation and the other entity. For example, to predict head given relation $r$ and tail $t$ in triple $(h,r,t)$, we compute the energy function $f_{r}(h^{\prime},t)$ for each entity $h^{\prime}$ in the knowledge base and rank all the entities according to the energy. We follow Bordes et al. 2013 to report the filter results, i.e., removing all other correct candidates $h^{\prime}$ in ranking. The rank of the correct entity is then obtained and we report the mean rank (mean of the predicted ranks) and Hits@10 (top $10$ accuracy). Lower mean rank or higher Hits@10 mean better performance.

2 Implementation Details

We initialize the projection matrices with identity matrices added with a small noise sampled from normal distribution $\mathcal{N}(0,\,0.005^{2})$. The entity and relation vectors of ITransF are initialized by TransE (Bordes et al. 2013), following Lin et al. 2015b; Ji et al. 2015; García-Durán et al. 2016; García-Durán et al. 2015; Lin et al. 2015a. We ran mini-batch SGD until convergence. We employ the “Bernoulli” sampling method to generate incorrect triples as used in Wang et al. 2014, Lin et al. 2015b, He et al. 2015, Ji et al. 2015 and Lin et al. 2015a.

STransE (Nguyen et al. 2016b) is the most similar knowledge embedding model to ours except that they use distinct projection matrices for each relation. We use the same hyperparameters as used in STransE and no significant improvement is observed when we alter hyperparameters. We set the margin $\gamma$ to $5$ and dimension of embedding $n$ to $50$ for WN18, and $\gamma=1,n=100$ for FB15k. We set the batch size to $20$ for WN18 and $1000$ for FB15k. The learning rate is $0.01$ on WN18 and $0.1$ on FB15k. We use $30$ matrices on WN18 and $300$ matrices on FB15k. All the models are implemented with Theano (Bergstra et al. 2010). The Softmax temperature is set to $1/4$.

3 Results & Analysis

The overall link prediction results Note that although IRN (Shen et al. 2016) does not explicitly exploit path information, it performs multi-step inference through the multiple usages of external memory. When IRN is allowed to access memory once for each prediction, its Hits@10 is $80.7$, similar to models without path information. are reported in Table 2. Our model consistently outperforms previous models without external information on both the metrics of WN18 and FB15k. On WN18, we even achieve a much better mean rank with comparable Hits@10 than current state-of-the-art model IRN employing external information.

To provide a detailed understanding why the proposed model achieves better performance, we present some further analysis in the sequel.

In the proposed ITransF, we design an attention mechanism to encourage knowledge sharing across different relations. Naturally, facts associated with rare relations should benefit most from such sharing, boosting the overall performance. To verify this hypothesis, we investigate our model’s performance on relations with different frequency.

The overall distribution of relation frequencies resembles that of word frequencies, subject to the zipf’s law. Since the frequencies of relations approximately follow a power distribution, their log frequencies are linear. The statistics of relations on FB15k and WN18 are shown in Figure 1. We can clearly see that the distributions exhibit long tails, just like the Zipf’s law for word frequency.

In order to study the performance of relations with different frequencies, we sort all relations by their frequency in the training set, and split them into 3 buckets evenly so that each bucket has a similar interval length of log frequency.

Within each bucket, we compare our model with STransE, as shown in Figure 2. Domain sampling is not employed. As we can see, on WN18, ITransF outperforms STransE by a significant margin on rare relations. In particular, in the last bin (rarest relations), the average Hits@10 increases from $74.4$ to $92.0$, showing the great benefits of transferring statistical strength from common relations to rare ones. The comparison on each relation is shown in Appendix A.2 where we can observe tha. On FB15k, we can also observe a similar pattern, although the degree of improvement is less significant. We conjecture the difference roots in the fact that many rare relations on FB15k have disjoint domains, knowledge transfer through common concepts is harder.

Interpretability

In addition to the quantitative evidence supporting the effectiveness of knowledge sharing, we provide some intuitive examples to show how knowledge is shared in our model. As we mentioned earlier, the sparse attention vectors fully capture the association between relations and concepts and hence the knowledge transfer among relations. Thus, we visualize the attention vectors for several relations on both WN18 and FB15K in Figure 3.

For WN18, the words “hyponym” and “hypernym” refer to words with more specific or general meaning respectively. For example, PhD is a hyponym of student and student is a hypernym of PhD. As we can see, concepts associated with the head entities in one relation are also associated with the tail entities in its reverse relation. Further, “instance_hypernym” is a special hypernym with the head entity being an instance, and the tail entity being an abstract notion. A typical example is $(\textit{New York},\texttt{instance\_hypernym},\textit{city})$. This connection has also been discovered by our model, indicated by the fact that “instance_hypernym(T)” and “hypernym(T)” share a common concept matrix. Finally, for symmetric relations like “similar_to”, we see the head attention is identical to the tail attention, which well matches our intuition.

On FB15k, we also see the sharing between reverse relations, as in “(somebody) won_award_for (some work)” and “(some work) award_winning_work (somebody)”. What’s more, although relation “won_award_for” and “was_nominated_for” share the same concepts, their attention distributions are different, suggesting distinct emphasis. Finally, symmetric relations like spouse behave similarly as mentioned before.

Model Compression

A byproduct of parameter sharing mechanism employed by ITransF is a much more compact model with equal performance. Figure 5 plots the average performance of ITransF against the number of projection matrices $m$, together with two baseline models. On FB15k, when we reduce the number of matrices from $2200$ to $30$ ($\sim 90\times$ compression), our model performance decreases by only $0.09\%$ on Hits@10, still outperforming STransE. Similarly, on WN18, ITransF continues to achieve the best performance when we reduce the number of concept project matrices to $18$.

Analysis on Sparseness

Sparseness is desirable since it contribute to interpretability and computational efficiency of our model. We investigate whether enforcing sparseness would deteriorate the model performance and compare our method with another sparse encoding methods in this section.

Nonnegative Sparse Encoding

For completeness, we compare our model with the aforementioned approach We use the toolkit provided by (Faruqui et al. 2015).. The comparison is summarized in table 4. On both benchmarks, ITransF achieves significant improvement against sparse encoding on pretrained model. This performance gap should be expected since the objective function of sparse encoding methods is to minimize the reconstruction loss rather than optimize the criterion for link prediction.

Related Work

In KBC, CTransR (Lin et al. 2015b) enables relation embedding sharing across similar relations, but they cluster relations before training rather than learning it in a principled way. Further, they do not solve the data sparsity problem because there is no sharing of projection matrices which have a lot more parameters. Learning the association between semantic relations has been used in related problems such as relational similarity measurement (Turney 2012) and relation adaptation (Bollegala et al. 2015).

Data sparsity is a common problem in many fields. Transfer learning (Pan and Yang 2010) has been shown to be promising to transfer knowledge and statistical strengths across similar models or languages. For example, Bharadwaj et al. 2016 transfers models on resource-rich languages to low resource languages by parameter sharing through common phonological features in name entity recognition. Zoph et al. 2016 initialize from models trained by resource-rich languages to translate low-resource languages.

Several works on obtaining a sparse attention (Martins and Astudillo 2016; Makhzani and Frey 2014; Shazeer et al. 2017) share a similar idea of sorting the values before softmax and only keeping the $K$ largest values. However, the sorting operation in these works is not GPU-friendly.

The block iterative optimization algorithm in our work is inspired by LightRNN (Li et al. 2016). They allocate every word in the vocabulary in a table. A word is represented by a row vector and a column vector depending on its position in the table. They iteratively optimize embeddings and allocation of words in tables.

Conclusion and Future Work

In summary, we propose a knowledge embedding model which can discover shared hidden concepts, and design a learning algorithm to induce the interpretable sparse representation. Empirically, we show our model can improve the performance on two benchmark datasets without external resources, over all previous models of the same kind.

In the future, we plan to enable ITransF to perform multi-step inference, and extend the sharing mechanism to entity and relation embeddings, further enhancing the statistical binding across parameters. In addition, our framework can also be applied to multi-task learning, promoting a finer sharing among different tasks.

Acknowledgments

We thank anonymous reviewers and Graham Neubig for valuable comments. We thank Yulun Du, Paul Mitchell, Abhilasha Ravichander, Pengcheng Yin and Chunting Zhou for suggestions on the draft. We are also appreciative for the great working environment provided by staff in LTI.

This research was supported in part by DARPA grant FA8750-12-2-0342 funded under the DEFT program.

References

Appendix A Appendix

In this section, we define the probability $p_{r}$ to generate a negative sample from the same domain mentioned in Section 3.3. The probability cannot be too high to avoid generating negative samples that are actually correct, since there are generally a lot of facts missing in KBs.

We compare how different value of $\lambda$ would influence our model’s performance in Table. 5. With large $\lambda$ and higher domain sampling probability, our model’s Hits@10 increases while mean rank also increases. The rise of mean rank is due to higher probability of generating a valid triple as a negative sample causing the energy of a valid triple to increase, which leads to a higher overall rank of a correct entity. However, the reasoning capability is boosted with higher Hits@10 as shown in the table.

A.2 Performance on individual relations of WN18

We plot the performance of ITransF and STransE on each relation. We see that the improvement is greater on rare relations.