{'fraction_non_alphanumeric': 0.03890321068666511, 'fraction_numerical': 0.02035973752050621, 'mean_word_length': 4.409126921248614, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Typed Tensor Decomposition of Knowledge Bases for Relation Extraction

While relation extraction has traditionally been viewed as a task relying solely on textual data, recent work has shown that by taking as input existing facts in the form of entity-relation triples from both knowledge bases and textual data, the performance of relation extraction can be improved significantly. Following this new paradigm, we propose a tensor decomposition approach for knowledge base embedding that is highly scalable, and is especially suitable for relation extraction. By leveraging relational domain knowledge about entity type information, our learning algorithm is significantly faster than previous approaches and is better able to discover new relations missing from the database. In addition, when applied to a relation extraction task, our approach alone is comparable to several existing systems, and improves the weighted mean average precision of a state-of-theart method by 10 points when used as a subcomponent.


Introduction
Identifying the relationship between entities from free text, relation extraction is a key task for acquiring new facts to increase the coverage of a structured knowledge base. Given a pre-defined database schema, traditional relation extraction approaches focus on learning a classifier using textual data alone, such as patterns between the occurrences of two entities in documents, to determine whether the entities have a particular relation. Other than using the existing known facts to label the text corpora in a distant supervision setting (Bunescu and Mooney, 2007;Mintz et al., * Work conducted while interning at Microsoft Research. 2009; Riedel et al., 2010;Ritter et al., 2013), an existing knowledge base is typically not involved in the process of relation extraction.
However, this paradigm has started to shift recently, as researchers showed that by taking existing facts of a knowledge base as an integral part of relation extraction, the model can leverage richer information and thus yields better performance. For instance, Riedel et al. (2013) borrowed the idea of collective filtering and constructed a matrix where each row is a pair of entities and each column is a particular relation. For a true entityrelation triple (e 1 , r, e 2 ), either from the text corpus or from the knowledge base, the corresponding entry in the matrix is 1. A previously unknown fact (i.e., triple) can be discovered through matrix decomposition. This approach can be viewed as creating vector representations of each relation and candidate pair of entities. Because each entity does not have its own representation, relationships of any unpaired entities cannot be discovered. Alternatively, Weston et al. (2013) created two types of embedding -one based on textual similarity and the other based on knowledge base, where the latter maps each entity and relation to the same ddimensional vector space using a model proposed by Bordes et al. (2013a). They also showed that combining these two models results in a significant improvement over the model trained using only textual data.
To make such an integrated strategy work, it is important to capture all existing entities and relations, as well as the known facts, from both textual data and large databases. In this paper, we propose a new knowledge base embedding model, TRESCAL, that is highly efficient and scalable, with relation extraction as our target application. Our work is built on top of RESCAL (Nickel et al., 2011), which is a tensor decomposition method that has proven its scalability by factoring YAGO (Biega et al., 2013) with 3 million entities and 41 million triples (Nickel et al., 2012). We improve the tensor decomposition model with two technical innovations. First, we exclude the triples that do not satisfy the relational constraints (e.g., both arguments of the relation spouse-of need to be person entities) from the loss, which is done by selecting sub-matrices of each slice of the tensor during training. Second, we introduce a mathematical technique that significantly reduces the computational complexity in both time and space when the loss function contains a regularization term. As a consequence, our method is more than four times faster than RESCAL, and is also more accurate in discovering unseen triples.
Our contributions are twofold. First, compared to other knowledge base embedding methods developed more recently, it is much more efficient to train our model. As will be seen in Sec. 5, when applied to a large knowledge base created using NELL (Carlson et al., 2010) that has 1.8M entity-relation triples, our method finishes training in 4 to 5 hours, while an alternative method (Bordes et al., 2013a) needs almost 3 days. Moreover, the prediction accuracy of our model is competitive to others, if not higher. Second, to validate its value to relation extraction, we apply TRESCAL to extracting relations from a free text corpus along with a knowledge base, using the data provided in (Riedel et al., 2013). We show that TRESCAL is complementary to existing systems and significantly improves their performance when using it as a subcomponent. For instance, this strategy improves the weighted mean average precision of the best approach in (Riedel et al., 2013) by 10 points (47% to 57%).
The remainder of this paper is organized as follows. We survey most related work in Sec. 2 and provide the technical background of our approach in Sec. 3. Our approach is detailed in Sec. 4, followed by the experimental validation in Sec. 5. Finally, Sec. 6 concludes the paper.

Related Work
Our approach of creating knowledge base embedding is based on tensor decomposition, which is a well-developed mathematical tool for data analysis. Existing tensor decomposition models can be categorized into two main families: the CP and Tucker decompositions. The CP (CAN-DECOMP/PARAFAC) decomposition (Kruskal, 1977;Kiers, 2000) approximates a tensor by a sum of rank-one tensors, while the Tucker decomposition (Tucker, 1966), also known as high-order SVD (De Lathauwer et al., 2000), factorizes a tensor into a core tensor multiplied by a matrix along each dimension. A highly scalable distributional algorithm using the Map-Reduce architecture has been proposed recently for computing CP (Kang et al., 2012), but not for the Tucker decomposition, probably due to its inherently more complicated model form.
Matrix and tensor decomposition methods have been applied to modeling multi-relational data. For instance, Speer et al. (2008) aimed to create vectors of latent components for representing concepts in a common sense knowledge base using SVD. Franz et al. (2009) proposed TripleRank to model the subject-predicate-object RDF triples in a tensor, and then applied the CP decomposition to identify hidden triples. Following the same tensor encoding, Nickel et al. (2011) proposed RESCAL, a restricted form of Tucker decomposition for discovering previously unknown triples in a knowledge base, and later demonstrated its scalability by applying it to YAGO, which was encoded in a 3M × 3M × 38 tensor with 41M triples (Nickel et al., 2012).
Methods that revise the objective function based on additional domain information have been proposed, such as MrWTD, a multi-relational weighted tensor decomposition method (London et al., 2013), coupled matrix and tensor factorization (Papalexakis et al., 2014), and collective matrix factorization (Singh and Gordon, 2008). Alternatively, instead of optimizing for the least-squares reconduction loss, a non-parametric Bayesian approach for 3-way tensor decomposition for modeling relational data has also been proposed (Sutskever et al., 2009). Despite the existence of a wide variety of tensor decomposition models, most methods do not scale well and have only been tested on datasets that are much smaller than the size of real-world knowledge bases.
Multi-relational data can be modeled by neuralnetwork methods as well. For instance, Bordes et al. (2013b) proposed the Semantic Matching Energy model (SME), which aims to have the same d-dimensional vector representations for both entities and relations. Given the vectors of entities e 1 , e 2 and relation r. They first learn the latent representations of (e 1 , r) and (e 2 , r). The score of (e 1 , r, e 2 ) is determined by the inner product of the vectors of (e 1 , r) and (e 2 , r). Later, they proposed a more scalable method called translating embeddings (TransE) (Bordes et al., 2013a). While both entities and relations are still represented by vectors, the score of (e 1 , r, e 2 ) becomes the negative dissimilarity measure of the corresponding vectors − e i + r k − e j , motivated by the work in (Mikolov et al., 2013b;Mikolov et al., 2013a). Alternatively, Socher et al. (2013) proposed a Neural Tensor Network (NTN) that represents entities in d-dimensional vectors created separately by averaging pre-trained word vectors, and then learns a d × d × m tensor describing the interactions between these latent components in each of the m relations. All these methods optimize for loss functions that are more directly related to the true objective -the prediction accuracy of correct entity-relation triples, compared to the meansquared reconstruction error in our method. Nevertheless, they typically require much longer training time.

Background
In this section, we first describe how entityrelation triples are encoded in a tensor. We then introduce the recently proposed tensor decomposition method, RESCAL (Nickel et al., 2011) and explain how it adopts an alternating least-squares method, ASALSAN (Bader et al., 2007), to compute the factorization.

Encoding Binary Relations in a Tensor
Suppose we are given a knowledge base with n entities and m relation types, and the facts in the knowledge base are denoted as a set of entity-relation triples T = {(e i , r k , e j )}, where i, j ∈ {1, 2, · · · n} and k ∈ {1, 2, · · · m}. A triple (e i , r k , e j ) simply means that the i-th entity and the j-th entity have the k-th relation. Following (Franz et al., 2009), these triples can naturally be encoded in a 3-way tensor X ∈ {0, 1} n×n×m , such that X i,j,k = 1 if and only if the triple (e i , r k , e j ) ∈ T 1 . The tensor can be viewed as consisting of m slices, where each slice is an n×n square matrix, denoting the interactions of the entities of a particular relation type. In the remainder of this paper, we will use X k to refer to the k-th slice of the tensor X . Fig. 1 Figure 1: A tensor encoding of m binary relation types and n entities. A slice X k denotes the entities having the k-th relation.

RESCAL
In order to identify latent components in a tensor for collective learning, Nickel et al. (2011) proposed RESCAL, which is a tensor decomposition approach specifically designed for the multirelational data described in Sec. 3.1. Given a tensor X n×n×m , RESCAL aims to have a rank-r approximation, where each slice X k is factorized as (1) A is an n × r matrix, where the i-th row denotes the r latent components of the i-th entity. R k is an asymmetric r × r matrix that describes the interactions of the latent components according to the k-th relation. Notice that while R k differs in each slice, A remains the same.
A and R k are derived by minimizing the loss function below.
is the mean-squared reconstruction error and RESCAL is a special form of Tucker decomposition (Tucker, 1966) operating on a 3-way tensor. Its model form (Eq. (1)) can also be regarded as a relaxed form of DEDICOM (Bader et al., 2007), which derives the low-rank approximation as: X k ≈ AD k RD k A T . To compare RESCAL to other tensor decomposition methods, interested readers can refer to (Kolda and Bader, 2009).
The optimization problem in Eq. (2) can be solved using the efficient alternating least-squares (ALS) method. This approach alternatively fixes R k to solve for A and then fixes A to solve R k . The whole procedure stops until f (A,R k ) X 2 F converges to some small threshold or the maximum number of iterations has been reached.
By finding the solutions where the gradients are 0, we can derive the update rules of A and R k as below.
Complexity Analysis Following the analysis in (Nickel et al., 2012), we assume that each X k is a sparse matrix, and let p be the number of non-zero entries 2 . The complexity of computing X k AR T k and X T k AR k is O(pr + nr 2 ). Evaluating B k and C k requires O(nr 2 ) and the matrix inversion requires O(r 3 ). Therefore, the complexity of updating A is O(pr+nr 2 ) assuming n r. The updating rule of R k involves inverting an r 2 × r 2 matrix. Therefore, directly computing the inversion requires time complexity O(r 6 ) and space complexity O(r 4 ). Although Nickel et al. (2012) considered using QR decomposition to simplify the updates, it is still time consuming with the time complexity O(r 6 + pr 2 ). Therefore, the total time complexity is O(r 6 +pr 2 ) and the step of updating R k is the bottleneck in the optimization process. We will describe how to reduce the time complexity of this step to O(nr 2 + pr) in Section 4.2.

Approach
We describe how we leverage the relational domain knowledge in this section. By removing the incompatible entity-relation triples from the loss function, training can be done much more efficiently and results in a model with higher prediction accuracy. In addition, we also introduce a mathematical technique to reduce the computational complexity of the tensor decomposition methods when taking into account the regularization term.

Applying Relational Domain Knowledge
In the domain of knowledge bases, the notion of entity types is the side information that commonly exists and dictates whether some entities can be legitimate arguments of a given predicate. For instance, suppose the relation of interest is bornin, which denotes the birth location of a person. When asked whether an incompatible pair of entities, such as two person entities like Abraham Lincoln and John Henry, having this relation, we can immediately reject the possibility. Although the type information and the constraints are readily available, it is overlooked in the previous work on matrix and tensor decomposition models for knowledge bases (Riedel et al., 2013;Nickel et al., 2012). Ignoring the type information has two implications. Incompatible entity-relation triples still participate in the loss function of the optimization problem, which incurs unnecessary computation. Moreover, by choosing values for these incompatible entries we introduce errors in training the model that can reduce the quality of the model.
Based on this observation, we propose Typed-RESCAL, or TRESCAL, which leverages the entity type information to improve both the efficiency of model training and the quality of the model in term of prediction accuracy. We employ a direct and simple approach by excluding the triples of the incompatible entity types from the loss in Eq. (2). For each relation, let L k and R k be the set of entities with a compatible type to the k-th relation. That is, (e i , r k , e j ) is a feasible triple if and only if e i ∈ L k and e j ∈ R k . For notational convenience, we use A k l , A kr to denote the sub-matrices of A that consists of rows associated with L k and R k , respectively. Analogously, let X k lr be the sub-matrix of X k that consists of only the entity pairs compatible to the k-th relation. The rows and columns of X k lr map to the entities in A k l and A kr , respectively. In other words, entries of X k but not in X k lr do not satisfy the type constraint and are ignored from the computation. Figure 2: The construction of TRESCAL. Suppose the k-th relation is born-in. L k is then a set of person entities and R k is a set of location entities.
Only the sub-matrix corresponds to the compatible entity pairs (i.e., X k lr ) and the sub-matrices of the associated entities (i.e., A k l and A T kr ) will be included in the loss. TRESCAL solves the following optimization problem: where F . Similarly, A and R k can be solved using the alternating least-squares method. The update rule of A is Complexity Analysis Letn be the average number of entities with a compatible type to a relation. Follow a similar derivation in Sec. 3.2, the time complexity of updating A is O(pr +nr 2 ) and the time complexity of updating R k remains to be O(r 6 + pr 2 ).

Handling Regularization Efficiently
Examining the update rules of both RESCAL and TRESCAL, we can see that the most timeconsuming part is the matrix inversions. For RESCAL, this is the term (Z T Z+λI) −1 in Eq. (3), where Z = A ⊗ A. Nickel et al. (2011) made the observation that if λ = 0, the matrix inversion can be calculated by Then, it only involves an inversion of an r × r matrix, namely A T A. However, if λ > 0, directly calculating Eq.
(3) requires to invert an r 2 × r 2 matrix and thus becomes a bottleneck in solving Eq. (2).
To reduce the computational complexity of the update rules of R k , we compute the inversion Z T Z + λI −1 by applying singular value decomposition (SVD) to A, such that A = UΣV T , where U and V are orthogonal matrices and Σ is a diagonal matrix. Then by using properties of the Kronecker product we have: The last equality holds because V ⊗ V is also an orthogonal matrix. We leave the detailed derivations in Appendix A. Notice that λI + Σ 2 ⊗ Σ 2 −1 is a diagonal matrix. Therefore, the inversion calculation is trivial.
This technique can be applied to TRESCAL as well.
By applying SVD to both A k l and A kr , we have of Eq. (5) thus becomes: The procedure of updating R is depicted in Algorithm 1.
Complexity Analysis For RESCAL, V and Σ can be computed by finding eigenvectors of A T A. Therefore, computing SVD of A costs O(nr 2 + r 3 ) = O(nr 2 ). Computing Step 4 in Algorithm 1 takes O(nr 2 + pr).
Step 5 and Step 6 require Algorithm 1 Updating R in TRESCAL Require: X , A, and entity sets R k , L k , ∀k Ensure: R k , ∀k.
1: for k = 1 . . . m do 2: (1 is a matrix of all ones. Function diag converts the diagonal entries of a matrix to a vector. ) 6: kr . (The operator "./" is element-wise division.) 7: end for O(r 2 ) and O(r 3 ), respectively. The overall time complexity of updating R k becomes O(nr 2 +pr).
Using a similar derivation, the time complexity of updating R k in TRESCAL is O(nr 2 + pr). Therefore, the total complexity of each iteration is O(nr 2 + pr).

Experiments
We conduct two sets of experiments. The first evaluates the proposed TRESCAL algorithm on inferring unknown facts using existing relationentity triples, while the second demonstrates its application to relation extraction when a text corpus is available.

Knowledge Base Completion
We evaluate our approach on a knowledge base generated by the CMU Never Ending Language Learning (NELL) project (Carlson et al., 2010). NELL collects human knowledge from the web and has generated millions of entity-relation triples. We use the data generated from version 165 for training 3 , and collect the new triples generated between NELL versions 166 and 533 as the development set and those generated between version 534 and 745 as the test set 4 . The data statistics of the training set are summarized in Table 1. The numbers of triples in the development and test sets are 19,665 and 117,889, respectively. Notice that this dataset is substantially larger than the datasets used in recent work. For example, the Freebase data used in (Socher et al., 2013) and ( al., 2013a) have 316k and 483k 5 triples, respectively, compared to 1.8M in this dataset.
In the NELL dataset, the entity type information is encoded in a specific relation, called Generalization. Each entity in the knowledge base is assigned to at least one category presented by the Generalization relationship. Based on this information, the compatible entity type constraint of each relation can be easily identified. Specifically, we examined the entities and relations that occur in the triples of the training data, and counted all the types appearing in these instances of a given relation legitimate.
We implement RESCAL and TRESCAL in MATLAB with the Matlab tensor Toolbox (Bader et al., 2012). With the efficient implementation described in Section 4.2, all experiments can be conducted on a commodity PC with 16 GB memory. We set the maximal number of iterations of both RESCAL and TRESCAL to be 10, which we found empirically to be enough to generate a stable model. Note that Eq. (4) is non-convex, and the optimization process does not guarantee to converge to a global minimum. Therefore, initializing the model properly might be important for the performance. Following the implementation of RESCAL, we initialize A by performing singular value decomposition overX = k (X k + X T k ), such thatX = UΣV T and set A = U. Then, we apply the update rule of R k to initialize {R k }. RESCAL and TRESCAL have two types of parameters: (1) the rank r of the decomposed tensor and (2) the regularization parameter λ. We tune the rank parameter on development set in a range of {100, 200, 300, 400} and the regularization parameter in a range of {0.01, 0.05, 0.1, 0.5, 1}.
For comparison, we also use the code released by Bordes et al. (2013a), which is implemented using Python and the Theano library (Bergstra et al., 2010), to train a TransE model using the  Table 2: Model performance in mean average precision (MAP) on entity retrieval and relation retrieval. † and ‡ indicate the comparison to TRESCAL in the same setting is statistically significant using a pairedt test on average precision of each query, with p < 0.01 and p < 0.05, respectively. Enforcing type constraints during test time improves entity retrieval substantially, but does not help in relation retrieval.
same NELL dataset. We reserved randomly 1% of the training triples for the code to evaluate the model performance in each iteration. As suggested in their paper, we experiment with several hyper-parameters, including learning rate of {0.01, 0.001}, the latent dimension of {50, 100} and the similarity measure of {L1, L2}. In addition, we also adjust the number of batches of {50, 100, 1000}. Of all the configurations, we keep the models picked by the method, as well as the final model after 500 training iterations. The final model is chosen by the performance on our development set.

Training Time Reduction
We first present experimental results demonstrating that TRESCAL indeed reduces the time required to factorize a knowledge database, compared to RESCAL. The experiment is conducted on NELL with r = 300 and λ = 0.1. When λ = 0, the original RESCAL algorithm described in (Nickel et al., 2011;Nickel et al., 2012) cannot handle a large r, because updating matrices {R k } requires O(r 4 ) memory. Later in this section, we will show that in some situation a large rank r is necessary for achieving good testing performance. Comparing TRESCAL with RESCAL, each iteration of TRESCAL takes 1,608 seconds, while that of RESCAL takes 7,415 seconds. In other words, by inducing the entity type information and constraints, TRESCAL enjoys around 4.6 times speed-up, compared to an improved regularized version of RESCAL. When updating A and {R k } TRESCAL only requires operating on sub-matrices of A, {R k } and {X k }, which reduces the computation substantially. In average, TRESCAL filters 96% of entity triples that have incompatible types.
In contrast, it takes TransE at least 2 days and 19 hours to finish training the model (the default 500 iterations) 6 , while TRESCAL finishes the training 6 It took almost 4 days to train the best TransE model that in roughly 4 to 5 hours 7 .

Test Performance Improvement
We consider two different types of tasks to evaluate the prediction accuracy of different modelsentity retrieval and relation retrieval.
Entity Retrieval In the first task, we collect a set of entity-relation pairs {(e i , r k )} and aim at predicting e j such that the tuple (e i , r k , e j ) is a recorded triple in the NELL knowledge base. For each pair (e i , r k ), we collect triples {(e i , r k , e * j )} from the NELL test corpus as positive samples and randomly pick 100 entries e j to form negative samples {e i , r k , e j }. Given A and R k from the factorization generated by RESCAL or TRESCAL, the score assigned to a triple {e i , r k , e j } is computed by a T i R k a j where a i and a j are the i-th and j-th rows of A. In TransE, the score is determined by the negative dissimilarity measures of the learned embeddings: −d(e i , r k , e j ) = − e i + r k − e j 2 2 . We evaluate the performance using mean average precision (MAP), which is a robust and stable metric (Manning et al., 2008). As can be observed in Table 2 (left), TRESCAL achieves 54.79%, which outperforms 51.59% of RESCAL and 51.41% of TransE. Adding constraints during test time by assigning the lowest score to the entity triples with incompatible types improves results of all models -TRESCAL still performs the best (69.26%), compared to TransE (67.56%) and RESCAL (62.91%).
Relation Retrieval In the second task, given a relation type r k , we are looking for the entity pairs (e i , e j ) that have this specific relationship. To generate test data, for each relation type, we collect is included in Table 2. 7 We also tested the released code from (Socher et al., 2013) for training a neural tensor network model. However, we are not able to finish the experiments as each iteration of this method takes almost 5 hours. gold entity pairs from the NELL knowledge base as positive samples and randomly pick a set of entity pairs as negative samples such that the number of positive samples are the same as negative ones.
Results presented in Table 2 (right) show that TRESCAL achieves 76.12%, while RESCAL and TransE are 73.15% and 75.88%, respectively. Therefore, incorporating the type information in training seems to help in this task as well. Enforcing the type constraints during test time does not help as in entity retrieval. By removing incompatible entity pairs, the performance of TRESCAL, RESCAL and TransE drop slightly to 75.70%, 73.08% and 70.71% respectively. One possible explanation is that the task of relation retrieval is easier than entity retrieval. The incorrect type information of some entities ends up filtering out a small number of entity pairs that were retrieved correctly by the model.
Notice that TRESCAL achieves different levels of performance on various relations. For example, it performs well on predicting AthletePlaysSport (81%) and CoachesInLeague (88%), but achieves suboptimal performance on predicting Works-For (49%) and BuildingLocatedInCity (35%). We hypothesize that it is easier to generalize entity-relation triples when the relation has several related relations. For examples, AthletePlaysForTeam and TeamPlaysSport may help discover entity-relation triples of Ath-letePlaysSport.

Sensitivity to Parameters
We also study if TRESCAL is sensitive to the rank parameter r and the regularization parameter λ, where the detailed results can be found in Appendix B. In short, we found that increasing the rank r generally leads to better models. Also, while the model is not very sensitive to the value of the regularization parameter λ, tuning λ is still necessary for achieving the best performance.

Relation Extraction
Next, we apply TRESCAL to the task of extracting relations between entities, jointly from a text corpus and a structured knowledge base. We use a corpus from (Riedel et al., 2013) that is created by aligning the entities in NYTimes and Freebase. The corpus consists of a training set and a test set. In the training set, a list of entity pairs are provided, along with surface patterns extracted from NYTimes and known relations obtained from Freebase. In the test set, only the surface patterns are given. By jointly factoring a matrix consisting of the surface patterns and relations, Riedel et al. (2013) show that their model is able to capture the mapping between the surface patterns and the structured relations and hence is able to extract the entity relations from free text. In the following, we show that TRESCAL can be applied to this task.
We focus on the 19 relations listed in Table 1 of (Riedel et al., 2013) and only consider the surface patterns that co-occur with these 19 relations. We prune the surface patterns that occur less than 5 times and remove the entities that are not involved in any relation and surface pattern. Based on the training and test sets, we build a 80,698×80,698×1,652 tensor, where each slice captures a particular structured relation or a surface pattern between two entities. There are 72 fine types extracted from Freebase assigned to 53,836 entities that are recorded in Freebase. In addition, special types, PER, LOC, ORG and MISC, are assigned to the remaining 26,862 entities based on the predicted NER tags provided by the corpus. A type is considered incompatible to a relation or a surface pattern if in the training data, none of the argument entities of the relation belongs to the type. We use r = 400 and λ = 0.1 in TRESCAL to factorize the tensor.
We compare the proposed TRESCAL model to RI13 (Riedel et al., 2013), YA11 (Yao et al., 2011), MI09 (Mintz et al., 2009) and SU12 (Surdeanu et al., 2012) 8 . We follow the protocol used in (Riedel et al., 2013) to evaluate the results. Given a relation as query, the top 1,000 entity pairs output by each system are collected and the top 100 ones are judged manually. Besides comparing individual models, we also report the results of combined models. To combine the scores from two models, we simply normalize the scores of entity-relation tuples to zero mean and unit variance and take the average. The results are summarized in Table 3.
As can been seen in the table, using TRESCAL alone is not very effective and its performance is only compatible to MI09 and YA11, and is significantly inferior to RI13. This is understandable because the problem setting favors RI13 as only entity pairs that have occurred in the text or the database will be considered in RI13, both during model training and testing. In contrast, TRESCAL  predicts all the possible combinations between entities and relations, which makes the model less fit to the task. However, when combining TRESCAL with a pure text-based method, such as SU12, we can clearly see TRESCAL is complementary to SU12 (0.39 to 0.44 in weighted MAP score), which makes the results competitive to RI13. Interestingly, although both TRESCAL and RI13 leverage information from the knowledge base, we find that by combining them, the performance is improved quite substantially (0.47 to 0.57). We suspect that the reason is that in our construction, each entity has its own vector representation, which is lacked in RI13. As a result, the new triples that TRESCAL finds are very different from those found by RI13. Nevertheless, combining more methods do not always yield an improvement. For example, combining TR, RI13 and SU12 together (not included in Table 3) achieves almost the same performance as TR+RI13.

Conclusions
In this paper we developed TRESCAL, a tensor decomposition method that leverages relational domain knowledge. We use relational domain knowledge to capture which triples are potentially valid and found that, by excluding the triples that are incompatible when performing tensor decomposition, we can significantly reduce the training time and improve the prediction performance as compared with RESCAL and TransE. More-over, we demonstrated its effectiveness in the application of relation extraction. Evaluated on the dataset provided in (Riedel et al., 2013), the performance of TRESCAL alone is comparable to several existing systems that leverage the idea of distant supervision. When combined with the stateof-the-art systems, we found that the results can be further improved. For instance, the weighted mean average precision of the previous best approach in (Riedel et al., 2013) has been increased by 10 points (47% to 57%).
There are a number of interesting potential extensions of our work. First, while the experiments in this paper are on traditional knowledge bases and textual data, the idea of leveraging relational domain knowledge is likely to be of value to other linguistic databases as well. For instance, part-ofspeech tags can be viewed as the "types" of words. Incorporating such information in other tensor decomposition methods (e.g., (Chang et al., 2013)) may help lexical semantic representations. Second, relational domain knowledge goes beyond entity types and their compatibility with specific relations. For instance, the entity-relation triple (e 1 , child-of, e 2 ) can be valid only if e 1 .type = person ∧ e 2 .type = person ∧ e 1 .age < e 2 .age. It would be interesting to explore the possibility of developing efficient methods to leverage other types of relational domain knowledge. Finally, we would like to create more sophisticated models of knowledge base embedding, targeting complex in-ference tasks to better support semantic parsing and question answering.

Appendix B Hyper-parameter Sensitivity
We study if TRESCAL is sensitive to the rank parameter r and the regularization parameter λ. We use the task of relation retrieval and present the model performance on the development set. Fig. 3 shows the performance of TRESCAL and RESCAL with different rank (r) values while fixing λ = 0.01. Results show that both TRESCAL and RESCAL achieve better performance when r is reasonably large. TRESCAL obtains a better model with smaller r than RESCAL, because TRESCAL only needs to fit the triples of the compatible entity types. Therefore, it allows to use smaller number of latent variables to fit the training data.
Fixing r = 400, Fig. 4 shows the performance of TRESCAL at different values of the regularization parameter λ, including no regularization at all (λ = 0). While the results suggest that the method is not very sensitive to λ, tuning λ is still necessary for achieving the best performance.