Example: barber

Knowledge Graph Embedding via Dynamic Mapping Matrix

Knowledge Graph Embedding via Dynamic Mapping Matrix Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu and Jun Zhao National Laboratory of Pattern recognition (NLPR). Institute of Automation Chinese Academy of Sciences, Beijing, 100190, China Abstract completion is to predict relations between entities based on existing triplets in a Knowledge Graph . In Knowledge graphs are useful resources for the past decade, much work based on symbol and numerous AI applications, but they are far logic has been done for Knowledge Graph comple- from completeness. Previous work such as tion, but they are neither tractable nor enough con- TransE, TransH and TransR/CTransR re- vergence for large scale Knowledge graphs. Re- gard a relation as translation from head en- cently, a powerful approach for this task is to en- tity to tail entity and the CTransR achieves code every element (entities and relations) of a state-of-the-art performance.

National Laboratory of Pattern Recognition (NLPR) Institute of Automation Chinese Academy of Sciences, Beijing, 100190, China fguoliang.ji,shizhu.he,lhxu,kliu,jzhao g@nlpr.ia.ac.cn ... two vectors to represent a named sym-bol object (entity and relation). The rst one represents the meaning of a(n) entity (relation), the other one is used to con ...

Tags:

  Entity, Named, Recognition

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Knowledge Graph Embedding via Dynamic Mapping Matrix

1 Knowledge Graph Embedding via Dynamic Mapping Matrix Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu and Jun Zhao National Laboratory of Pattern recognition (NLPR). Institute of Automation Chinese Academy of Sciences, Beijing, 100190, China Abstract completion is to predict relations between entities based on existing triplets in a Knowledge Graph . In Knowledge graphs are useful resources for the past decade, much work based on symbol and numerous AI applications, but they are far logic has been done for Knowledge Graph comple- from completeness. Previous work such as tion, but they are neither tractable nor enough con- TransE, TransH and TransR/CTransR re- vergence for large scale Knowledge graphs. Re- gard a relation as translation from head en- cently, a powerful approach for this task is to en- tity to tail entity and the CTransR achieves code every element (entities and relations) of a state-of-the-art performance.

2 In this pa- Knowledge Graph into a low-dimensional embed- per, we propose a more fine-grained model ding vector space. These methods do reasoning named TransD, which is an improvement over Knowledge graphs through algebraic opera- of TransR/CTransR. In TransD, we use tions (see section Related Work ). two vectors to represent a named sym- bol object ( entity and relation). The first Among these methods, TransE (Bordes et al. one represents the meaning of a(n) entity 2013) is simple and effective, and also achieves (relation), the other one is used to con- state-of-the-art prediction performance. It learns struct Mapping Matrix dynamically. Com- low-dimensional embeddings for every entity and pared with TransR/CTransR, TransD not relation in Knowledge graphs. These vector em- only considers the diversity of relations, beddings are denoted by the same letter in bold- but also entities.

3 TransD has less param- face. The basic idea is that every relation is re- eters and has no Matrix -vector multipli- garded as translation in the Embedding space. For cation operations, which makes it can be a golden triplet (h, r, t), the Embedding h is close applied on large scale graphs. In Experi- to the Embedding t by adding the Embedding r, ments, we evaluate our model on two typ- that is h + r t. TransE is suitable for 1-to-1. ical tasks including triplets classification relations, but has flaws when dealing with 1-to- and link prediction. Evaluation results N, N-to-1 and N-to-N relations. TransH (Wang show that our approach outperforms state- et al. 2014) is proposed to solve these issues. of-the-art methods. TransH regards a relation as a translating oper- ation on a relation-specific hyperplane, which is 1 Introduction characterized by a norm vector wr and a trans- Knowledge Graphs such as WordNet (Miller lation vector dr.)

4 The embeddings h and t are 1995), Freebase (Bollacker et al. 2008) and Yago first projected to the hyperplane of relation r to (Suchanek et al. 2007) have been playing a piv- obtain vectors h = h wr> hwr and t =. otal role in many AI applications, such as relation t wr> twr , and then h + dr t . Both extraction(RE), question answering(Q&A), etc. in TransE and TransH, the embeddings of enti- They usually contain huge amounts of structured ties and relations are in the same space. How- data as the form of triplets (head entity , relation, ever, entities and relations are different types ob- tail entity )(denoted as (h, r, t)), where relation jects, it is insufficient to model them in the same models the relationship between the two entities. space. TransR/CTransR (Lin et al. 2015) set a As most Knowledge graphs have been built either Mapping Matrix Mr and a vector r for every re- collaboratively or (partly) automatically, they of- lation r.

5 In TransR, h and t are projected to the ten suffer from incompleteness. Knowledge Graph aspects that relation r focuses on through the ma- 687. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 687 696, Beijing, China, July 26-31, 2015. c 2015 Association for Computational Linguistics t1 . M rhi = rp hi p + I m n vectors operations. We evaluate TransD with the h1 h2 . M rti = rp t i p + I m n h1 r t1 task of triplets classification and link prediction. h3 t2. h 2 r t 2 The experimental results show that our method has h 3 . r t3. ( i = 1, 2,3). r r t 3 significant improvements compared with previous models. Relation Space Our contributions in this paper are: (1)We pro- entity Space pose a novel model TransD, which constructs a Figure 1: Simple illustration of TransD.

6 Each Dynamic Mapping Matrix for each entity -relation shape represents an entity pair appearing in a pair by considering the diversity of entities and re- triplet of relation r. Mrh and Mrt are Mapping lations simultaneously. It provides a flexible style matrices of h and t, respectively. hip , tip (i = to project entity representations to relation vec- 1, 2, 3), and rp are projection vectors. hi and tor space; (2) Compared with TransR/CTransR, ti (i = 1, 2, 3) are projected vectors of entities. TransD has fewer parameters and has no Matrix - The projected vectors satisfy hi + r ti (i = vector multiplication. It is easy to be applied 1, 2, 3). on large-scale Knowledge graphs like TransE and TransH; and (3) In experiments, our approach outperforms previous models including TransE, trix Mr and then Mr h + r Mr t. CTransR is TransH and TransR/CTransR in link prediction an extension of TransR by clustering diverse head- and triplets classification tasks.

7 Tail entity pairs into groups and learning distinct relation vectors for each group. TransR/CTransR 2 Related Work has significant improvements compared with pre- Before proceeding, we define our mathematical vious state-of-the-art models. However, it also has notations. We denote a triplet by (h, r, t) and their several flaws: (1) For a typical relation r, all en- column vectors by bold lower case letters h, r, t;. tities share the same Mapping Matrix Mr . How- matrices by bold upper case letters, such as M;. ever, the entities linked by a relation always con- tensors by bold upper case letters with a hat, such tains various types and attributes. For example, in c Score function is represented by fr (h, t). as M. triplet (friedrich burklein, nationality, germany), For a golden triplet (h, r, t) that corresponds to a friedrich burklein and germany are typical differ- true fact in real world, it always get a relatively ent types of entities.

8 These entities should be pro- higher score, and lower for an negative triplet. jected in different ways; (2) The projection oper- Other notations will be described in the appropri- ation is an interactive process between an entity ate sections. and a relation, it is unreasonable that the map- ping matrices are determined only by relations; TransE, TransH and TransR/CTransR. and (3) Matrix -vector multiplication makes it has As mentioned in Introduction section, TransE. large amount of calculation, and when relation (Bordes et al. 2013) regards the relation r as trans- number is large, it also has much more param- lation from h to t for a golden triplet (h, r, t). eters than TransE and TransH. As the complex- Hence, (h+r) is close to (t) and the score function ity, TransR/CTransR is difficult to apply on large- is scale Knowledge graphs.

9 In this paper, we propose a novel method named fr (h, t) = kh + r tk22 . (1). TransD to model Knowledge graphs. Figure 1. TransE is only suitable for 1-to-1 relations, there shows the basic idea of TransD. In TransD, we de- remain flaws for 1-to-N, N-to-1 and N-to-N rela- fine two vectors for each entity and relation. The tions. first vector represents the meaning of an entity or To solve these problems, TransH (Wang et al. a relation, the other one (called projection vector). 2014) proposes an improved model named trans- represents the way that how to project a entity em- lation on a hyperplane. On hyperplanes of differ- bedding into a relation vector space and it will ent relations, a given entity has different represen- be used to construct Mapping matrices. There- tations. Similar to TransE, TransH has the score fore, every entity -relation pair has an unique map- function as follows: ping Matrix .

10 In addition, TransD has no Matrix - by-vector operations which can be replaced by fr (h, t) = kh + r t k22 . (2). 688. Model #Parameters # Operations (Time complexity). Unstructured (Bordes et al. 2012; 2014) O(Ne m) O(Nt ). SE (Bordes et al. 2011) O(Ne m + 2Nr n2 )(m = n) O(2m2 Nt ). SME(linear) (Bordes et al. 2012; 2014) O(Ne m + Nr n + 4mk + 4k)(m = n) O(4mkNt ). SME (bilinear) (Bordes et al. 2012; 2014) O(Ne m + Nr n + 4mks + 4k)(m = n) O(4mksNt ). LFM (Jenatton et al. 2012; Sutskever et al. 2009) O(Ne m + Nr n2 )(m = n) O((m2 + m)Nt ). SLM (Socher et al. 2013) O(Ne m + Nr (2k + 2nk))(m = n) O((2mk + k)Nt ). NTN (Socher et al. 2013) O(Ne m + Nr (n2 s + 2ns + 2s))(m = n) O(((m2 + m)s + 2mk + k)Nt ). TransE (Bordes et al. 2013) O(Ne m + Nr n)(m = n) O(Nt ). TransH (Wang et al. 2014) O(Ne m + 2Nr n)(m = n) O(2mNt ). TransR (Lin et al.)


Related search queries