summaries: This paper provides a very simple approach to the problem of knowledge base completion. The idea is this - given a query (subject, relation), you find other entities similar to subject, see which other paths they can take to their corresponding object if they express the relation, and check if the subject express those paths. Object reached this way are candidate answers. The one with most paths reached is marked correct.

summaries: This paper proposes a non-parametric reasoning method for reasoning on incomplete knowledge bases. Specifically, for the task of finding a target entity given a source entity and a relation, since this specific relation might be missing for the source entity, multi-hop reasoning is required to get the answer. To get the reasoning paths, this paper proposes to first retrieve similar entities from the knowledge base that have the same outgoing relation, and then gather all possible reasoning paths from these retrieved entities. Finally, these reasoning paths extracted from other entities can be applied to the source entity in the query and get the answer.

abstractText: We present a surprisingly simple yet accurate approach to reasoning in knowledge graphs (KGs) that requires no training, and is reminiscent of case-based reasoning in classical artificial intelligence (AI). Consider the task of finding a target entity given a source entity and a binary relation. Our non-parametric approach derives crisp logical rules for each query by finding multiple graph path patterns that connect similar source entities through the given relation. Using our method, we obtain new state-of-the-art accuracy, outperforming all previous models, on NELL-995 and FB-122. We also demonstrate that our model is robust in low data settings, outperforming recently proposed meta-learning approaches1.

authors:
Agnar Aamodt
Enric Plaza

title: Case-based reasoning: Foundational issues, methodological variations, and system approaches

venue: AI communications,

authors:
Edoardo M Airoldi
David M Blei
Stephen E Fienberg
Eric P Xing

title: Mixed membership stochastic blockmodels

authors:
Kurt Bollacker
Colin Evans
Praveen Paritosh
Tim Sturge
Jamie Taylor

title: Freebase: A collaboratively created graph database for structuring human knowledge

venue: In ICDM,

authors:
Antoine Bordes
Nicolas Usunier
Alberto Garcia-Duran
Jason Weston
Oksana Yakhnenko

title: Translating embeddings for modeling multi-relational data

venue: In NeurIPS,

authors:
Antal van den Bosch
Bertjan Busser
Sander Canisius
Walter Daelemans

title: An efficient memorybased morphosyntactic tagger and parser for dutch

venue: LOT Occasional Series,

authors:
Matthias Broecheler
Lilyana Mihalkova
Lise Getoor

title: Probabilistic similarity logic

venue: In UAI,

authors:
Ziqiang Cao
Wenjie Li
Sujian Li
Furu Wei

title: Retrieve, rerank and rewrite: Soft template based neural summarization

venue: In ACL,

authors:
Andrew Carlson
Justin Betteridge
Bryan Kisiel
Burr Settles
Estevam R. Hruschka
Jr.
Tom M. Mitchell

title: Toward an Architecture for Never-ending Language Learning

venue: In AAAI,

authors:
Walter Daelemans
Jakub Zavrel
Peter Berck
Steven Gillis

title: Mbt: A memory-based part of speech tagger-generator

venue: In WVLC,

authors:
Rajarshi Das
Arvind Neelakantan
David Belanger
Andrew McCallum

title: Chains of reasoning over entities, relations, and text using recurrent neural networks

authors:
Rajarshi Das
Shehzaad Dhuliawala
Manzil Zaheer
Luke Vilnis
Ishan Durugkar
Akshay Krishnamurthy
Alex Smola
Andrew McCallum

title: Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning

venue: In ICLR,

authors:
Tim Dettmers
Pasquale Minervini
Pontus Stenetorp
Sebastian Riedel

title: Convolutional 2d knowledge graph embeddings

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In ICML,

authors:
Lise Getoor
Ben Taskar

title: Introduction to statistical relational learning

venue: MIT press,

authors:
Shu Guo
Quan Wang
Lihong Wang
Bin Wang
Li Guo

title: Jointly embedding knowledge graphs and logical rules

venue: In EMNLP,

authors:
Kelvin Guu
Tatsunori B. Hashimoto
Yonatan Oren
Percy Liang

title: Generating sentences by editing prototypes

venue: In TACL,

authors:
Tatsunori B Hashimoto
Kelvin Guu
Yonatan Oren
Percy S Liang

title: A retrieve-and-edit framework for predicting structured outputs

authors:
Charles Kemp
Joshua B Tenenbaum
Thomas L Griffiths
Takeshi Yamada
Naonori Ueda

title: Learning systems of concepts with an infinite relational model

authors:
Urvashi Khandelwal
Omer Levy
Dan Jurafsky
Luke Zettlemoyer
Mike Lewis

title: Generalization through memorization: Nearest neighbor language models

authors:
Stanley Kok
Pedro Domingos

title: Statistical predicate invention

title: Maintaining organization in a dynamic long-term memory

venue: Cognitive science,

authors:
Juliana S Lancaster
Janet L Kolodner

title: Problem solving in a natural task as a function of experience

venue: Technical report, Georgia Tech CS Department,

title: Cbr in context: The present and future. Case-based reasoning: Experiences, lessons, and future

authors:
Xi Victoria Lin
Richard Socher
Caiming Xiong

title: Multi-hop knowledge graph reasoning with reward shaping

authors:
Xin Lv
Yuxian Gu
Xu Han
Lei Hou
Juanzi Li
Zhiyuan Liu

title: Adapting meta knowledge graph information for multi-hop reasoning over few-shot relations

authors:
Kurt Miller
Michael I Jordan
Thomas L Griffiths

title: Nonparametric latent feature models for link prediction

venue: In Neurips,

authors:
Bonan Min
Ralph Grishman
Li Wan
Chang Wang
David Gondek

title: Distant supervision for relation extraction with an incomplete knowledge base

venue: In HLT-NAACL,

authors:
Pasquale Minervini
Thomas Demeester
Tim Rocktäschel
Sebastian Riedel

title: Adversarial sets for regularising neural link predictors

venue: arXiv preprint arXiv:1707.07596,

authors:
Pasquale Minervini
Matko Bošnjak
Tim Rocktäschel
Sebastian Riedel
Edward Grefenstette

title: Differentiable reasoning on large knowledge bases and natural language

title: Inverse entailment and progol

venue: New generation computing,

authors:
Stephen Muggleton
Ramon Otero
Alireza Tamaddoni-Nezhad

title: Inductive logic programming

authors:
Stephen Mussmann
Stefano Ermon

title: Learning and inference via maximum inner product search

authors:
Gaurav Pandey
Danish Contractor
Vineet Kumar
Sachindra Joshi

title: Exemplar encoder-decoder for neural conversation generation

authors:
Hao Peng
Ankur Parikh
Manaal Faruqui
Bhuwan Dhingra
Dipanjan Das

title: Text generation with exemplar-based adaptive decoding

venue: In NAACL,

title: Learning logical definitions from relations

venue: Machine learning,

title: Examples in legal reasoning: Legal hypotheticals

venue: In IJCAI,

authors:
Tim Rocktäschel
Sebastian Riedel

title: End-to-end differentiable proving

title: Remindings and their effects in learning a cognitive skill

venue: Cognitive psychology,

title: Dynamic memory: A theory of reminding and learning in computers and people

venue: cambridge university press,

authors:
Henk Schmidt
Geoffrey Norman
Henny Boshuizen

title: A cognitive perspective on medical expertise: theory and implications

venue: Academic medicine,

authors:
Stefan Schoenmackers
Oren Etzioni
Daniel S Weld
Jesse Davis

title: Learning first-order horn clauses from web text

authors:
Fabian Suchanek
Gjergji Kasneci
Gerhard Weikum

title: Yago: A core of semantic knowledge

venue: In WWW,

authors:
Zhiqing Sun
Zhi-Hong Deng
Jian-Yun Nie
Jian Tang

title: Rotate: Knowledge graph embedding by relational rotation in complex space

authors:
Ilya Sutskever
Joshua B Tenenbaum
Russ R Salakhutdinov

title: Modelling relational data using bayesian clustered tensor factorization

authors:
Théo Trouillon
Johannes Welbl
Sebastian Riedel
Éric Gaussier
Guillaume Bouchard

title: Complex embeddings for simple link prediction

authors:
Patrick Verga
David Belanger
Emma Strubell
Benjamin Roth
Andrew McCallum

title: Multilingual relation extraction using compositional universal schema

authors:
William Yang Wang
Kathryn Mazaitis
William W Cohen

title: Programming with personalized pagerank: a locally groundable first-order probabilistic logic

venue: In CIKM,

authors:
Jason Weston
Emily Dinan
Alexander Miller

title: Retrieve and refine: Improved sequence generation models for dialogue

venue: In ConvAI Workshop EMNLP,

authors:
Sam Wiseman
Karl Stratos

title: Label-agnostic sequence labeling by copying nearest neighbors

authors:
Wenhan Xiong
Thien Hoang
William Yang Wang

title: Deeppath: A reinforcement learning method for knowledge graph reasoning

authors:
Zhao Xu
Volker Tresp
Kai Yu
Hans-Peter Kriegel

title: Infinite hidden relational models

authors:
Bishan Yang
Wen-tau Yih
Xiaodong He
Jianfeng Gao
Li Deng

title: Embedding entities and relations for learning and inference in knowledge bases

authors:
Fan Yang
Zhilin Yang
William W Cohen

title: Differentiable learning of logical rules for knowledge base reasoning

authors:
Daojian Zeng
Kang Liu
Siwei Lai
Guangyou Zhou
Jun Zhao

title: Relation classification via convolutional deep neural network

venue: In COLING,

authors:
Jun Zhu
Jiaming Song
Bei Chen

title: Max-margin nonparametric latent feature models for link prediction

heading: 1. Introduction

text:
Given a new problem, humans possess the innate ability to ‘retrieve’ and ‘adapt’ solutions to similar problems from the past. For example, an automobile mechanic might fix a car engine by recalling previous experiences where cars exhibited similar symptoms of damage. This model of reasoning has been widely studied and verified in cognitive psychology for various applications such as mathematical problem solving [Ross, 1984], diagnosis by physicians [Schmidt et al., 1990], automobile mechanics [Lancaster and Kolodner, 1987] etc. A lot of classical work in artificial intelligence (AI), particularly in the field of case-based reasoning (CBR) has focused on incorporating such kind of reasoning in AI systems [Schank, 1982, Kolodner, 1983, Rissland, 1983, Aamodt and Plaza, 1994, Leake, 1996, inter-alia].
At a high level, a case-based reasoning system is comprised of four steps [Aamodt and Plaza, 1994] — (a) ‘retrieve’, in which given a new problem, ‘cases’ that are similar to the given problem are retrieved. A ‘case’ is usually associated with a problem description (used for matching it to a new problem) and its corresponding solution. After the initial retrieval step, the previous solutions are (b) ‘reused’ for the problem in hand. Often times, however, the retrieved solutions cannot be directly used, and hence the solutions needs to be (c) ‘revised’. Lastly, if the revised solution is useful for solving the given problem, they are (d) ‘retained’ in a memory so that they can be used in the future.
Knowledge graphs (KGs) [Suchanek et al., 2007, Bollacker et al., 2008, Carlson et al., 2010] contain rich facts about entities and capture relations with diverse semantics between those entities. However, KGs can be highly incomplete [Min et al., 2013], missing important edges (relations)
1Code available at https://github.com/rajarshd/CBR-AKBC
between entities. For example, consider the small fragment of the KG around the entity MELINDA GATES in figure 1. Even though a lot of facts about MELINDA is captured, it is missing the edge corresponding to works in city. A recent series of work address this problem by modeling multi-hop paths between entities in the KG, thereby able to reason along the path MELINDA→ ceo→ GATES FOUNDATION→ headquartered→ SEATTLE. However, the number of paths starting from an entity increases exponentially w.r.t the path length and therefore past work used parametric models to do approximate search using reinforcement learning (RL) [Xiong et al., 2017, Das et al., 2018, Lin et al., 2018]. Using RL-based methods have their own shortcomings, like hard to train and high computational requirements. Moreover, these models try to encode all the rules for reasoning into the parameters of the model which makes learning even harder.
In this paper, we propose a simple non-parametric approach for reasoning in KGs (Figure 1). Given an entity and a query relation (eq,rq), we first retrieve k entities in the KG that are similar to eq and for which we observe the query relation edge rq. The retrieved entities could be present anywhere in the KG and are not just restricted in the immediate neighborhood of eq. Similarity between entities is measured based on the observed relations that the entities participate in. This ensures that the retrieved entities have similar observed properties as eq (e.g., if eq is a CEO, then the retrieved entities are also CEO’s or business person). Next, for each of the retrieved entities, our
method finds a set of reasoning paths that connect the retrieved entities to the entities that they are connected with via the query relation rq. In this way, our method removes the burden of storing the reasoning rules in the parameters of the model and rather extract it from entities similar to the query entity. Next, our method checks if similar reasoning paths exists starting from the query entity eq. If similar paths exists, then the answer to the original query is found by starting from eq and traversing the KG by following the reasoning path. In practice, we find multiple reasoning paths which end at different entities and we rank the entities based on the number of reasoning paths that lead to them, with the intuition that an entity supported by multiple reasoning paths is likely to be a better answer to the given query.
Apart from being non-parametric, our proposed method has many other desirable properties. Our method is generic and even though we find very simple and symbolic methods to work very well for many KG datasets, every component of our model can be augmented by plugging in sophisticated neural models. For example, currently we use simple symbolic string matching to find if a relation path exists for the query entity. However, this component can be replaced with a neural model that matches paths which are semantically similar to each other [Das et al., 2017]. Similarly, we currently use a very simple inner product to compute similarities between entity embeddings. But that can be replaced with more sophisticated maximum inner product search [Mussmann and Ermon, 2016].
The contributions of the paper are as follows — (a) We present a non-parametric approach for reasoning over KGs, that uses multiple paths of evidence to derive an answer. These paths are gathered from entities in different parts of the KG that are similar to the query entity. (b) Our approach requires no training and can be readily applied to any new KGs. (c) Our method achieves state-of-the-art performance on NELL-995 and the harder subset of FB-122 outperforming sophisticated neural approaches and other tensor factorization methods. We also perform competitively on the WN18RR dataset. (d) Lastly, we provide detailed analysis about why our method outperforms parametric rule learning approaches like MINERVA [Das et al., 2018].

heading: 2. Method

heading: 2.1 Notation and Task Description

text:
Let E denote the set of entities and R denote the set of binary relations. A knowledge base (KB) is a collection of facts stored as triplets (e1, r,e2) where e1,e2 ∈ E and r ∈ R . From the KB, a knowledge graph G can be constructed where the entities e1,e2 are represented as the nodes and relation r as labeled edge between them. Formally, a KG is a directed labeled multigraph G = (V,E,R ), where V and E denote the vertices and edges of the graph respectively. Note that V = E and E ⊆V ×R ×V . Also, following previous approaches [Bordes et al., 2013, Xiong et al., 2017], we add the inverse relation of every edge, i.e. for an edge (e1, r,e2) ∈ E, we add the edge (e2, r−1,e1) to the graph. (If the set of binary relations R does not contain the inverse relation r−1, it is added to R as well). A path in a KG between two entities es, et is defined as a sequence of alternating entity and relations that connect es and et. A length of a path is the number of relation (edges) in the path. Formally, let a path p = (e1, r1,e2, . . . , rn,en+1) with st(p) = e1, en(p) = en+1 and len(p) = n. Let P denote the set of all paths and Pn denote the set of all paths with length up to n, i.e. Pn ⊆ P = {p ∈ P | len(p)≤n}.
We consider the task of query answering on KGs. Query answering seeks to answer questions of the form ( e1q,rq,? ) (e.g. Melinda, works in city, ?), where the answer is an entity in the KG.

heading: 2.2 Case-based Reasoning on Knowledge Graphs

text:
This section describes how we apply case-based reasoning (CBR) in a KG. In CBR, given a new problem, similar cases are retrieved from memory [Aamodt and Plaza, 1994]. In our setting, a problem is a query ( e1q,rq,? ) for a missing edge in the KG. A case is defined as an observed fact (e1, r,e2) in a KG along with a set of paths up to length n that connect e1 and e2. Formally, a case c = (e1, r,e2,P) ⊆ V ×R ×V × Pn is a 4 tuple where (e1, r,e2) ∈ G and P ⊆ P(e1,e2) = {p ∈ Pn | st(p) = e1,en(p) = e2}. In practice, it is intractable to store all paths between e1 and e2 (P(e1,e2)) and therefore we only store a random sample. Note, that we have a case for every observed triple in the KG and we denote the set of all such cases as C . We also assume access to a pre-computed similarity matrix S ∈ RV×V which stores the similarity between any two given entities in a KG. Intuitively, two entities which exhibit the same relations should have a high similarity (e.g., an athlete should have a high similarity score with another athlete). Lastly, we define a memory M that serves as the store for all the cases present in a KG and also the similarity matrix, i.e. M = (C ,S).
As explained earlier, CBR broadly comprises of four steps, which we explain briefly for our setup on a KG.
• Retrieve: In this step, given a query ( e1q,rq,? ) , our method first retrieves a set of k similar
entities w.r.t e1q using the pre-computed similarity matrix S, such that for each entity e′ in the retrieved set, we observe at least one fact of the form (e′,rq,e′′) in G . In other words, each retrieved entity should have at least one outgoing edge in G with the edge label as rq. Next, we gather all such facts (e′,rq,e′′) in G for each of the retrieved e′. Note, that there could be more than one fact for a given entity and query relation (e.g. USA, has city, New York City and USA, has city, Boston, for the entity ‘USA’ and query relation ‘has city’). Finally for all the gathered facts from the k-nearest neighbors, we retrieve all the cases from the memory store M . As noted before, in our formulation, a case is a fact augmented with a sample of KG paths that connect the entities of the fact. As we will see later (§ 3), the KG paths often represent reasoning rules that determine why the fact (e′,rq,e′′) hold true. The goal of CBR is to reuse these rules for the new query.
• Reuse: The reasoning paths that were gathered in the retrieve step are re-used for the query entity. As described before, a path in a KG is an alternating sequence of entities and relations. The path gathered from the nearest neighbors have entities which are in the immediate neighborhood of the nearest neighbor entities. To reuse these paths, we first replace the entities from the paths with un-instantiated variables and only extract the sequence of relations in them [Schoenmackers et al., 2010]. For example, if we have a retrieved case (a fact with a set of paths) such as ((USA,has city,Boston) ,{(USA,has state,Massachusetts,city in state,Boston)}), we remove the entities from the path and extract rules such as: has state(x,y),city in state(y,z) =⇒ has city(x,z). We gather all such paths from all the cases retrieved for a query. Since the same path type can occur in different cases, we maintain a list of paths sorted w.r.t the counts (in descending order).
• Revise: After the paths have been gathered, we look if those paths exists for the query entity e1q. In our approach we find that simple symbolic exact-string matching for the relations works quite well. However, neural relation extraction systems [Zeng et al., 2014, Verga et al., 2016] can be incorporated to map a relation to other similar relations to improve recall. We keep this direction as a part of our future work. Instead if we find an exact match for the sequence of
relations, we revise the rules by instantiating the variables with the entities which lie along the path in the neighborhood of e1q.
• Retain: Finally, a case including the query fact and the paths that lead to the correct answer for the query can be added to the memory store M .
Computing the similarity matrix: CBR approaches need access to a similarity matrix S to retrieve similar cases to the query entity. Intuitively, the similarity between entities that have similar relations should be higher (e.g. similarity between two athletes should be higher than the similarity between an athlete and a country). To model this, we parameterize each entity with an m-hot vector e ∈ RR . That is, each entity is a m-hot vector with the dimension equal to the size of the number of binary relations in the KB. An entry in the vector is set to 1, if an entity has at least one edge with that relation type, otherwise is set to 0. Even though, this is a really simple way of parameterizing an entity, we found this to work extremely well in practice. However, as previously mentioned we propose a generic method and one could replace the entity embeddings with any pre-trained vectors from any model. As an example, we present experiments by replacing our m-hot representation with pre-trained embeddings obtained from the state-of-the-art RotatE model [Sun et al., 2019]. Lastly, the similarity between two entities is calculated by a simple inner product between the normalized embeddings.
Caching ‘cases’ in the memory store: CBR also needs access to store containing cases. As mentioned before, in our setup a ‘case’ is a KG triple, along with a sample of paths that connect the two entities of the triple. Since the number of paths between entities grow exponentially w.r.t path length, it is intractable to store all paths between an entity pair. We instead consider a small subgraph around each entity in the KG spanned by 1000 randomly sampled paths of length up to 3. Next, for each triple (e1, r,e2) in the KG, we exhaustively search the subgraph around e1, collected in the previous step to find paths up to length 3 which lead to e2. These paths along with the fact form a case. This process is repeated for all the triples and each case is added to the case store C .
Both the similarity matrix S and the case store C are pre-computed offline and is stored in the memory M . Once that is done, our method requires no further training and can be readily used for any query in the KG.

heading: 3. Experiments

heading: 3.1 Data and Evaluation Protocols

text:
We test our CBR based approach on three datasets that are often used in the community for benchmarking models — FB122 [Guo et al., 2016], NELL-995 [Xiong et al., 2017], and WN18RR [Dettmers et al., 2018]. FB122 comes with a set of KB rules that can be used to infer missing triples in the dataset. We do not use the rules in the dataset and even show that our model is able to recover the rules from similar entities to the query. WN18RR was created by Dettmers et al. [2018] from the original WN18 dataset by removing various sources of test leakage, making the datasets more realistic and challenging. We compare our CBR based approach with various state-of-the-art models using standard ranking metrics such as HITS@N and mean reciprocal rank (MRR). For fair comparison to baselines, after a fact is predicted we do not add the new case (inferred fact and paths) in the memory (retain step in § 2.2), as that would mean we would use more information than our baselines to predict the followup queries. Hyper-parameters: The various hyper-parameters for our method are the number of nearest neighbor retrieved for a query entity (k), the number of paths that are gathered from the retrieved entity (l) and
the maximum path length considered (n). For all our experiments, we set n = 3. We tune k and l for each dataset w.r.t the given validation set.

heading: 3.2 Results on Query Answering

text:
We first present results on query answering (link prediction) on the three datasets and compare to various state-of-the-art baseline models. It is quite common in literature [Bordes et al., 2013, Yang et al., 2015, Dettmers et al., 2018, Sun et al., 2019] to report aggregate results on both tail prediction (e1, r,?) and head prediction (?, r−1,e2). To be exactly comparable to baselines, we report results on tail prediction for NELL-995 and for other datasets, we report average of head and tail predictions.
NELL-995: Table 2 reports the query answering performance on the NELL-995 dataset. We compare to several strong baselines. In particular, we compare to various embedding based models such as DistMult [Yang et al., 2015], ComplEx [Trouillon et al., 2016] and ConvE [Dettmers et al., 2018]. We also wanted to compare to various neural models for learning logical rules such as neuraltheorem-provers [Rocktäschel and Riedel, 2017], NeuralLP [Yang et al., 2017] and MINERVA [Das et al., 2018]. However, only MINERVA scaled to the size of NELL-995 dataset and others did not. As it is clear from table 2, CBR outperforms all the baselines by a large margin with gains of over 4% on the strict HITS@1 metric. We further discuss and analyze the results in sec (3.4).
FB122: Next we consider the FB122 dataset by Guo et al. [2016]. Comparing results on FB122 is attractive for a couple of reasons — (a) Firstly, this dataset comes with a set of logical rules hand coded by the authors that can be used for logical inference. It would be interesting to see if our CBR approach is able to automatically uncover the rules from the data. (b) Secondly, there is a recent work on a neural model for logical inference (GNTPs) [Minervini et al., 2020] that scales neural-theorem-provers [Rocktäschel and Riedel, 2017] to this dataset and hence we can directly compare with them. Table 1 reports the results. We compare with several baselines. CBR significantly outperforms GNTPs and even outperforms most models which have access to the hand-coded rules
during training. We also find that CBR is able to uncover correct rules for 27 out of 31 (87%) query relations.
WN18RR: Finally, we report results of WN18RR in table 3. CBR performs competitively with GNTPs and most embedding based methods except RotatE [Sun et al., 2019]. Upon further analysis, we find that for 210 triples in the test set, the entity was not present in the graph and hence no answers were returned for those query entities.

heading: 3.3 Experiments with limited data

text: As mentioned before, our CBR based approach needs no training and gathers reasoning patterns from few similar entities. Therefore, it should ideally perform well for query relations for which we do not have a lot of data. Recently, Lv et al. [2019] studied this problem and propose a meta-learning [Finn et al., 2017] based solution (Meta-KGR) for few-shot relations. We compare with their model to see if CBR based approach will be able to generalize for such few-shot relations. Table 4 reports the results and quite encouragingly we find that we outperform all sophisticated meta-learning approaches by a large margin.

heading: 3.4 Analysis: CBR is capable of doing contextualized reasoning

text:
In this section, we analyze the performance of our non-parametric approach and try to understand why it works better than existing parametric rule learning models like MINERVA. Lets consider the relation ‘agent belongs to organization’ in the NELL-995 dataset. Here the query entity can belong to a wide varity of types. For example, these are all triples for the query relation in NELL995— (George Bush, agent belongs to organization, House of Republicans), (Vancouver Canucks, agent belongs to organization, NHL), (Chevrolet, agent belongs to organization, General Motors). As can be seen, the query entity for a relation can belong to many different types and hence the logical rules that needs to be learned would be different. An advantage of CBR based approach is
that, for each query entity it retrieves similar contexts and then gather rules from them. One the other hand, models like MINERVA has to encode all rules into its parameters which makes learning harder. In other words, CBR is capable of doing better fine-grained contextual reasoning for a given query. To further confirm this hypothesis, we count the number of paths that CBR finds that lead to the correct answer and compare it with MINERVA. CBR learns a total of 306.4 unique paths that lead to answer compared to 176.83 of MINERVA. Figure 2 plots the counts for each query relation which further shows that CBR finds more varied paths than MINERVA.

heading: 3.5 Results with RotatE embeddings

text: As mentioned before, the CBR approach is generic and one can incorporate sophisticated models into each of the step. We run experiments where the m-hot representation of entities is replaced with pretrained embeddings obtained from a trained RotatE [Sun et al., 2019] model for building the similarity matrix. On the WN18RR dataset, we get a MRR of 0.425 as compared to 0.423 with our original approach.

heading: 3.6 Limitations of our Current Work

text:
A key limitation of our current work is the symbolic matching of reasoning paths. Different symbolic sequence of relation can have similar semantics (e.g. works in org, org located in and studies in,
college located in are similar paths for inferring lives in relation), but in our current work, these paths would be treated differently. This limitation can be alleviated by learning a similarity kernel for paths using distributed representation of relations.
On error analysis, we found that a major source of error occurs in our ranking of entities. Currently, ranking of predicted entities is done via number of paths that lead to it. Even though, this simple technique works well, we noticed that, if we had access to an oracle ranker, our performance would improve significantly. For example, in FB122 dataset, CBR retrieves a total of 241 entities out of more than 9.5K entities. An oracle ranking of these entities would increase the accuracy (HITS@1) from 0.28 to 0.74. This indicates that a substantial gain could be obtained if we train a model to rank the retrieved entities, a direction we leave as future work.
3.7 Inference time Dataset MINERVA CBR
WN18RR 63s 69s
NELL-995 35s 68s
Table 5: Inference time (in seconds) on two datasets.
Table 5 report the inference times of our model on the entire evaluation set of WN18RR (6268 queries) and NELL-995 (2825 queries) and compares it with MINERVA. Since our approach first retrieves similar entities and then gathers reasoning paths from them, it is slower than MINERVA. However, given the empirical improvements in accuracy, we believe this is not a significant tradeoff.

heading: 4. Related Work

text:
Bayesian non-parametric approaches for link prediction: There is a rich body of work which employs bayesian non-parametric approaches to automatically learn the latent dimension of entities. The infinite relational model (IRM) [Kemp et al., 2006] and its extensions [Xu et al., 2006] learns a possibly unbounded number of latent clusters from the graph and an entity is represented by its cluster membership. Later Airoldi et al. [2008] proposed the mixed membership stochastic block models that allows entities to have mixed membership over the clusters. Instead of cluster membership, Miller et al. [2009] propose a model that learn features of entities and the non-parametric approach allows learning unbounded number of dimensions. Sutskever et al. [2009] combine bayesian nonparametric and tensor factorization approaches and Zhu et al. [2012] allows non-parametric learning in a max-margin framework. Our method does not learn latent dimension and features of entities using a bayesian approach. Instead we propose a framework for doing non-parametric reasoning by learning patterns from k-nearest neighbors of the query entity. Also, the bayesian models have only been applied to very small knowledge graphs (containing few hundred entities and few relations). Rule induction in knowledge graphs is a very rich field with lots of seminal works. Inductive Logic Programming (ILP) [Muggleton et al., 1992] learns general purpose predicate rules from examples and background knowledge. Early work in ILP such as FOIL [Quinlan, 1990], PROGOL [Muggleton, 1995] are either rule-based or require negative examples which is often hard to find in KBs (by design, KBs store true facts). Statistical relational learning methods [Getoor and Taskar, 2007, Kok and Domingos, 2007, Schoenmackers et al., 2010] along with probabilistic logic [Richardson and Domingos, 2006, Broecheler et al., 2010, Wang et al., 2013] combine machine learning and logic but these approaches operate on symbols rather than vectors and hence do not enjoy the generalization properties of embedding based approaches. Moreover, unlike our approach, these methods do not learn rules from entities similar to the query entity. Recent work in rule induction, as discussed before
[Yang et al., 2017, Rocktäschel and Riedel, 2017, Das et al., 2018, Minervini et al., 2020] try to encode rules in the parameters of the model. In contrast, we propose a non-parametric approach for doing so. Moreover our model outperforms them on several datasets. K-NN based approach in other NLP applications: Nearest neighbor models have been applied to a number of NLP applications in the past such as parts-of-speech tagging [Daelemans et al., 1996] and morphological analysis [Bosch et al., 2007]. There has also been several recent work which leverages k-nearest neighbors for various NLP tasks, which is a step towards case based reasoning. Retrieve-and-edit based approaches are gaining popularity for various structured prediction tasks [Guu et al., 2018, Hashimoto et al., 2018]. Accurate sequence labeling by explicitly and only copying labels from retrieved neighbors have been achieved by Wiseman and Stratos [2019]. Another recent line of work use training examples at test time to improve language generation [Weston et al., 2018, Pandey et al., 2018, Cao et al., 2018, Peng et al., 2019]. Improvements in language model have been also observed by Khandelwal et al. [2020] by utilizing explicit examples from past training data obtained from nearest neighbor search in the encoded space. However, unlike us these work do not extract explicit reasoning patterns (or solutions in cases) from nearest neighbors.

heading: 5. Conclusion

text: We propose a very simple non-parametric approach for reasoning in KGs that is similar to case-based reasoning approaches in classical AI. Our proposed model requires no training and can be readily applied to any knowledge graphs. It achieves new state-of-the-art performance in NELL-995 and FB122 datasets. Also we show that, our approach is robust in low-data settings. Overall, our nonparametric approach is capable of deriving crisp logical rules for each query by extracting reasoning patterns from other entities and entirely removes the burden of storing logical rules in the model parameters.

heading: Acknowledgements

text: This work is funded in part by the Center for Data Science and the Center for Intelligent Information Retrieval, and in part by the National Science Foundation under Grant No. IIS-1514053 and in part by the International Business Machines Corporation Cognitive Horizons Network agreement number W1668553 and in part by the Chan Zuckerberg Initiative under the project Scientific Knowledge Base Construction. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.

title: A Simple Approach to Case-Based Reasoning in Knowledge Bases


summaries: The paper describes an evaluation of several pre-training strategies for the task of entity linking, using the AIDA and TAC-KBP baselines. In particular, the authors look at the impact of entity candidate selection strategies, adding noise during pre-training, and context selection methods. The model employed for entity disambiguation is a 4-layer transformer for the language representation, with an MLP final layer to perform disambiguation. The analysis of the pre-training strategies is detailed, and could be interesting for others using the transformer architecture to perform entity linking. Minor issue, but the paper is missing a conclusion section - this could be used to discuss how these results can generalize to other methods for entity linking.

summaries: This paper investigates the use of a simple architecture for entity disambiguation: encode the mention and its context with BERT, use an MLP over the mention's fenceposts to compute an embedding, then compare that embedding with embeddings of entity candidates and take the one with the highest dot product. Notably, it uses a transformer pre-trained on Wikipedia to do entity resolution, but does *not* use the BERT model or its pre-trained parameters directly.  The paper deals with several design decisions along the way: how to pre-train this model on Wikipedia, how to generate candidates at train and test time, whether or not to mask the input as in BERT, and other hyperparameters. Results show state-of-the-art performance on CoNLL (with a good candidate set) and TAC-KBP, as well as good performance on end-to-end entity linking (detecting and linking mentions).

abstractText: In this work, we present an entity linking model which combines a Transformer architecture with large scale pretraining from Wikipedia links. Our model achieves the stateof-the-art on two commonly used entity linking datasets: 96.7% on CoNLL and 94.9% on TAC-KBP. We present detailed analyses to understand what design choices are important for entity linking, including choices of negative entity candidates, Transformer architecture, and input perturbations. Lastly, we present promising results on more challenging settings such as end-to-end entity linking and entity linking without in-domain training data.

title: Investigating entity knowledge in bert with simple neural end-to-end entity linking

authors:
Razvan Bunescu
Marius Pasca

title: Using encyclopedic knowledge for named entity disambiguation

venue: EACL,

authors:
Xiao Cheng
Dan Roth

title: Relational inference for wikification

venue: In EMNLP,

authors:
Andrew Chisholm
Ben Hachey

title: Entity disambiguation with web

venue: links. TACL,

authors:
Joachim Daiber
Max Jakob
Chris Hokamp
Pablo N Mendes

title: Improving efficiency and accuracy in multilingual entity extraction

venue: In ICSS,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint 1810.04805,

authors:
Thibault Févry
Livio Baldini Soares
Nicholas FitzGerald
Eunsol Choi
Tom Kwiatkowski

title: Entities as experts: Sparse memory access with entity supervision

venue: arXiv preprint arXiv:2004.07202,

authors:
Octavian-Eugen Ganea
Marina Ganea
Aurelien Lucchi
Carsten Eickhoff
Thomas Hofmann

title: Probabilistic bag-of-hyperlinks model for entity linking

authors:
Daniel Gillick
Sayali Kulkarni
Larry Lansing
Alessandro Presta
Jason Baldridge
Eugene Ie
Diego Garcia-Olano

title: Learning dense representations for entity retrieval

authors:
Amir Globerson
Nevena Lazic
Soumen Chakrabarti
Amarnag Subramanya
Michael Ringaard
Fernando Pereira

title: Collective entity resolution with multi-focal attention

authors:
Nitish Gupta
Sameer Singh
Dan Roth

title: Entity linking via joint encoding of types, descriptions, and context

authors:
Michael U Gutmann
Aapo Hyvärinen

title: Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics

authors:
Johannes Hoffart
Mohamed Amir Yosef
Ilaria Bordino
Hagen Fürstenau
Manfred Pinkal
Marc Spaniol
Bilyana Taneva
Stefan Thater
Gerhard Weikum

title: Robust disambiguation of named entities in text

authors:
Heng Ji
Ralph Grishman
Hoa Trang Dang
Kira Griffitt
Joe Ellis

title: Overview of the tac 2010 knowledge base population track

venue: TAC

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint 1412.6980,

authors:
Nikolaos Kolitsas
Octavian-Eugen Ganea
Thomas Hofmann

title: End-to-End neural entity linking

venue: In CoNLL,

authors:
Kenton Lee
Shimi Salant
Tom Kwiatkowski
Ankur Parikh
Dipanjan Das
Jonathan Berant

title: Learning recurrent span representations for extractive question answering

venue: arXiv preprint 1611.01436,

authors:
Jeffrey Ling
Nicholas FitzGerald
Zifei Shan
Livio Baldini Soares
Thibault Févry
David Weiss
Tom Kwiatkowski

title: Learning cross-context entity representations from text

authors:
Lajanugen Logeswaran
Ming-Wei Chang
Kenton Lee
Kristina Toutanova
Jacob Devlin
Honglak Lee

title: Zero-shot entity linking by reading entity descriptions

authors:
Gang Luo
Xiaojiang Huang
Chin-Yew Lin
Zaiqing Nie

title: Joint entity recognition and disambiguation

authors:
Rada Mihalcea
Andras Csomai

title: Wikify! linking documents to encyclopedic knowledge

venue: IKM,

authors:
Andriy Mnih
Koray Kavukcuoglu

title: Learning word embeddings efficiently with noisecontrastive estimation

venue: In NeurIPS,

authors:
Maria Pershina
Yifan He
Ralph Grishman

title: Personalized page rank for named entity disambiguation

authors:
Matthew E Peters
Mark Neumann
IV Logan
L Robert
Roy Schwartz
Vidur Joshi
Sameer Singh
Noah A Smith

title: Knowledge enhanced contextual word representations

authors:
Francesco Piccinno
Paolo Ferragina

title: From tagme to wat: a new entity annotator

venue: In Proceedings of the First International Workshop on Entity Recognition & Disambiguation,

authors:
Priya Radhakrishnan
Partha Talukdar
Vasudeva Varma

title: Elden: Improved entity linking using densified knowledge graphs

venue: In ACL-HLT,

authors:
Jonathan Raphael Raiman
Olivier Michel Raiman

title: Deeptype: multilingual entity linking by neural type system evolution

venue: In AAAI,

authors:
Michael Ringgaard
Rahul Gupta
Fernando CN Pereira

title: Sling: A framework for frame semantic parsing

venue: arXiv preprint 1710.07032,

authors:
Avirup Sil
Alexander Yates

title: Re-ranking for joint named-entity recognition and linking

authors:
Avirup Sil
Gourab Kundu
Radu Florian
Wael Hamza

title: Neural cross-lingual entity linking

authors:
Chen-Tse Tsai
Dan Roth

title: Cross-lingual wikification using multilingual embeddings

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: NeurIPS,

authors:
Ledell Wu
Fabio Petroni
Martin Josifoski
Sebastian Riedel
Luke Zettlemoyer

title: Zeroshot entity linking with dense entity retrieval

authors:
Ikuya Yamada
Hiroyuki Shindo
Hideaki Takeda
Yoshiyasu Takefuji

title: Joint learning of the embedding of words and entities for named entity disambiguation

title: Learning distributed representations of texts and entities from knowledge

venue: base. TACL,

heading: 1. Introduction

text:
Traditionally, entity linking approaches have relied on knowledge bases, complicated modelling and task-specific hand-engineered features to achieve high performance. More recently, Broscheit 2019, Ling et al. 2020 and Wu et al. 2019 show that using large-scale pretrained language models like BERT [Devlin et al., 2018], pretraining on Wikipedia entity links, and fine-tuning on a specific entity linking corpus leads to state-of-the-art performance without relying on such features. However, Ling et al. 2020 focused mainly on constructing general-purpose entity representations, Wu et al. 2019 on building strong zero-shot entity linking systems, and Broscheit 2019 on end-to-end linking, so that the limits of pretraining for entity disambiguation have not been fully explored.
In this paper we present a thorough study of pretraining strategies for supervised entity linking. We establish new upper bounds for performance on the widely studied CoNLL and TAC-KBP 2010 entity linking tasks. We also show that our pretraining approach yields a very competitive entity linking system without any further domain specific tuning. We present a detailed analysis of significant design choices including the choice of negative candidates used during training, and the document context encoded for each mention. We find that the optimal choice of negative candidates is dependent on whether or not the final linking system has access to an alias table. For a system that will use an alias table at inference, it is helpful to pretrain the models with lexically similar candidates. However, when no alias table is used for the downstream task, ensuring candidates are random improves the model ability to distinguish the right entity among all possible entities.
∗. Denotes equal contribution. †. Work conducted during Google AI Residency.
In our studies we found two surprising results: (1) it is possible to achieve optimal entity linking results with a four layer transformer, which is one third of the size of BERT-base, and (2) given the abundance of supervision from Wikipedia links, we did not get any gains in performance from training with an auxiliary language modeling loss. However, we did find that the input perturbations introduced by [Devlin et al., 2018] themselves increase the quality of our pretraining approach and we present an analysis of how these perturbations add robustness to the model.
Finally, to demonstrate the generality of our model, we present results on the end-toend entity linking task in which both mention location and identity are predicted. On this task, our model outperforms all but the tailored methods introduced by Kolitsas et al. 2018, Broscheit 2019. We argue that our model is more practical, and easier to integrate, than heavily engineered existing approaches, and we believe that downstream tasks such as information extraction and question answering can benefit from this robust standalone end-to-end entity linker (e.g. [Févry et al., 2020]).

heading: 2. Related Work

text:
Early entity linking systems [Bunescu and Pasca, 2006, Mihalcea and Csomai, 2007] focused on matching the context of the mention with that of the entity page. In addition to context features, systems have relied on P(e|m), the prior probability that mention m refers to entity e, computed from Wikipedia mention counts. The set of entities in a document should be globally coherent, and several approaches have introduced sophisticated global disambiguation methods [Globerson et al., 2016, Cheng and Roth, 2013, Sil and Yates, 2013] that consider all mentions in a document to make predictions. In contrast, we do not model document-level disambiguation explicitly. However, our long context windows contain several mentions which should allow such disambiguation. Other approaches have also sought to incorporate types and knowledge base information in their modelling, such as Radhakrishnan et al. 2018, Raiman and Raiman 2018.
We pretrain our model by learning distributed representation of entities directly from Wikipedia text, similarly to Yamada et al. 2016, 2017, Gillick et al. 2019, Ling et al. 2020. Unlike Wu et al. 2019, Gupta et al. 2017, our embeddings are learned directly rather than generated through entity descriptions. In contrast with Yamada et al. 2016, 2017, we do not use additional features, such as prior probabilities or string match features. Our method is therefore most similar to Ling et al. 2020 and Broscheit 2019 who also use a transformer. We differ from Ling et al. 2020 by simultaneously considering all mentions and entities in a context and, in contrast to both, only use a four layer, randomly-initialized transformer instead of twelve layers initialized from large scale language modelling pretraining.
In addition, we experiment with end-to-end entity linking [Sil and Yates, 2013, Luo et al., 2015, Kolitsas et al., 2018], where instead of predicting the entity for gold spans, a system must both predict the span and its label. A closely related task is multilingual entity linking. Approaches have used multilingual embeddings to link text in several languages [Sil et al., 2018, Tsai and Roth, 2016]. Zero-shot entity linking [Logeswaran et al., 2019, Wu et al., 2019] is another relevant task. In that setting, entities predicted at test time are not seen in training. Instead, the system relies on the entity name and description.

heading: 3. Model

heading: 3.1 Task Definition

text:
Let E = {e1 . . . eN} be a predefined set of entities, and let V = {[mask], w1 . . . wM} be a vocabulary of words. A context x = [x0 . . . xt] is a sequence of words xi ∈ V. A span s = (sstart, send), is a tuple with 0 ≤ sstart, send < t which defines a contiguous sequence of tokens in a given context. A mention label l = (sk, ek) consists of a span si and an entity label, ei ∈ E ∪ ∅. We use l to denote a set of such mention labels. The NULL-symbol ∅ indicates a span that is labeled as a mention, but without an entity linking label.
Our training data, D = {(x0, l0) . . . (xN , lN )}, is a corpus of contexts, each paired with a set of mention labels, one for each mention in the context. Given an input context xi, our goal is to predict the set of entity mentions li. In Entity Disambiguation, we are given the set of spans, and predict the entity linked by each span. In End-to-End Entity Linking, we must predict both the set of mention spans, and their linked entities.

heading: 3.2 Contextual Language Representation

text:
Our model is built using the now-standard Transformer-based architecture [Vaswani et al., 2017]. The model computes a matrix representation Ĥ ∈ Rt×d of a text sequence through successive application of a Transformer block to the output of the previous layer:
Hi = TransformerBlock(Hi−1)
= MLP(MultiHeadAttention(Hi−1,Hi−1,Hi−1))
H0 is a sequence of context-independent token embeddings and Ĥ = Hn, where n is the number of Transformer layers.

heading: 3.3 Entity Disambiguation

text:
Each entity e ∈ E is mapped directly onto a dedicated vector in Rd via a |E|×d dimensional embedding matrix. In our experiments, we have a distinct embedding for every concept that has an English Wikipedia page, resulting in approximately 5.7m entity embeddings.
In order to perform entity linking for a particular span with word-piece token indices (i, j), we (following Lee et al. 2016) first obtain a representation of the span by concatenating the representation at the span start and end, and pass this through a multi-layer perceptron which projects the span representation into the same space as the entity embeddings.
ŝsi = MLP([Hn,sstart ,Hn,send ]) (1)
Our model scores each span-entity pair by taking the dot-product between the projected span representation and the embedding of ec. Thus, the conditional probability that the span si refers to entity ec is defined as:
P(ec|si) = exp(ŝsi · ec)∑
c′∈E exp(ŝsi · ec′) (2)
In practice, this is expensive to compute for large |E|. Therefore, for every l we select a set Cl of k candidates, which contains the entity labels for all l ∈ l as well as a set of negative candidates. We do not have an entity linking loss on mentions that do not have a label. Therefore, our per-example entity linking loss is:
llinking(l) = ∑ li∈l exp(ŝsi · ei)1ei!=∅∑ c∈Cl exp(ŝsi · ec) (3)
We will discuss further how we select Cl in Section 4.1.

heading: 3.4 Mention Detection

text: For many entity linking tasks, the target spans are provided. In order to be able to do endto-end entity linking, we additionally train our model to predict mentions, independently of entity linking. One way to do this would be to score every possible span-entity pair, and either use a score threshold to filter spans where no entity link achieves a sufficiently high score, or to additionally score a special NULL-link embedding. However, enumerating all spans for the long contexts we use in our model would be prohibitively expensive. We take the approach of encoding mentions as a BIO sequence, and train an MLP on the context representation to predict this sequence with a standard cross-entropy loss. Our final loss sums the mention detection loss and the linking loss.

heading: 4. Experimental Setup

heading: 4.1 Wikipedia Pretraining

text:
We build a training corpus of contexts paired with entity mention labels from the 2019-04- 14 dump of English Wikipedia. We first divide each article into chunks of 1000 unicode characters, resulting in a corpus of over 17.5 million contexts with over 17 million entity mentions covering over 5.7 million entities. These are processed with the BERT tokenizer, limited to 256 word-piece tokens. In addition to the Wikipedia links, we annotate each sentence with unlinked mention spans using a state-of-the-art named entity recognizer. These are used as additional signal for our mention detection component.
Entity Candidates Selection Training the model with a full softmax over all 5.7 million entities for every mention is computationally expensive. A common solution is to use a noise contrastive loss [Gutmann and Hyvärinen, 2012, Mnih and Kavukcuoglu, 2013] and sample candidates according to their relative frequency, as in Ling et al. [2020]. In this work, we experiment with other approaches to candidate generation that might provide better negatives in training. In addition to negatives selected uniformly at random from the entire entity vocabulary, we define two types of hard negatives:
1. Page candidates, which is the set of all entities linked to in the article from which the given context was taken. This is meant to capture semantically related concepts.
2. Phrase table candidates, the set of lexically related entities for each mention candidate, obtained from the Phrase Table provided by SLING [Ringgaard et al., 2017].
Throughout the paper, we will use |Cl| = 768. In our base setup, we use up to 256 page candidates, and 384 phrase table candidates, equally divided between each mention in the example. Any remaining room in the set of 768 is filled with random candidates sampled uniformly from the entity vocabulary (meaning a minimum of 128 random candidates per example). We will study the impact of different candidate selection methods in Section 6.2. In addition to those candidates, for every example in a batch, we use the candidates of other examples as additional negatives.
Input Noising We also add noise to the input data. We apply the same noise function as is used in Devlin et al. 2018: 15% of the tokens are chosen to be modified. 80% of those tokens are changed to the [mask] token, 10% are changed to a random token and 10% are left unmodified.
Pretraining hyperparameters We use Adam [Kingma and Ba, 2014] with a learning rate of 1e-4 to optimize our model. We use a linear warmup schedule for the first 10% of training, decay the learning rate afterwards and use gradient clipping with a norm of 1.0. We train from scratch for up to a million steps and use a large batch size of 8192 for pretraining. We follow BERT [Devlin et al., 2018] base for many of our model parameters, though we do not use large-scale language-modeling pretraining and only use four layers, as we did not find more to layers to further improve performance. We use the same wordpiece vocabulary as the lowercase version of BERT. We use entity embeddings of size 256 unless mentioned otherwise. We weight both the entity disambiguation loss and the mention detection loss to 1. We use a context window of 256 tokens.

heading: 4.2 Entity Linking Datasets

text: We evaluate our model on two popular entity linking benchmarks: AIDA CoNLL YAGO [Hoffart et al., 2011] and TAC-KBP 2010 [Ji et al., 2010]. The first is comprehensively annotated with approximately 34,000 mentions on 1,393 newswire document on the full Wikipedia vocabulary, while the second is sparsely annotated for target entities only on a smaller entity vocabulary.

heading: 4.2.1 AIDA CoNLL-YAGO Dataset

text:
Textual Context Most CoNLL documents do not fit in our limit of 256 tokens. Therefore, we split the document into “sentences” at each newline in the document. We experiment with three methods to add document context to these sentences: (i) taking the sentence as-is, (ii) adding the title of the document to the sentence, (iii) adding the title of the document as well as the first two sentences to the sentence. Throughout our experiments we will use (iii), though we show the impact of this choice in Section 6.4.
Entity Candidates Selection Our candidates for CoNLL come from alias tables - resources which provide a list of possible strings for a given entity. A key challenge with evaluating entity linking systems on the CoNLL dataset is inconsistent use of alias tables. Globerson et al. 2016 describe the difficulty of resolving older resources due to changes in Wikipedia links and unicode, and provide statistics for two commonly-used alias tables: The YAGO extended “means” mapping of Hoffart et al. 2011, and the “PPRforNED” mapping of Pershina et al. 2015.
We find that through careful resolution of unicode and Wikipedia redirects, we achieve a slightly higher conversion rate than reported by Globerson et al. 2016 (statistics provided in Table 1). This leads to a higher gold recall, but also a larger number of candidate for each mention, meaning our system must distinguish between more candidates. We report results using both alias tables.
Finetuning We finetune our model – including the entity embeddings – on the CoNLL training set, using the alias table candidates for each mention. We used a batch size of 256, a learning rate of 1e-6, and train for 2000 steps.

heading: 4.2.2 TAC-KBP 2010 dataset

text:
TAC-KBP 2010 is another widely used dataset for evaluating entity disambiguation systems. In contrast with CoNLL, the mentions are sparsely annotated among documents. It contains 1074 annotated entities in the training set and 1020 in the evaluation set. The entities for this dataset are part of the TAC Knowledge Base, containing 818,741 entities. Due to the reduced entity vocabulary, we can fine-tune without resorting to an alias table and we adopt this setting throughout our results. This is consistent with the prior state-of-the-art approach of Wu et al. 2019. To select the context for a mention, we take the 256 bytes before and after the first occurrence of the mention in the document.
We select the fine-tuning parameters on training by doing cross-validation on the training set. We used a batch size of 32, trained for 1,000 steps and found it was best to freeze the entity embeddings. Our final model is trained on all the training data with the parameters selected in cross-validation. However, we report the result on the evaluation (test) set number in all tables, including ablations. Indeed, we found that this was more reflective of task performance, as the training set is significantly easier.

heading: 4.3 End-to-end entity linking

text:
We also experiment with end-to-end entity linking on CoNLL (TAC-KBP is not suitable due to its sparse annotations). In this case, we do not use an alias table. In this setting, we follow the hyperparameters of Section 6.1. Instead of using candidates, we train our model to predict BIO-tagged mention boundaries and to disambiguate among all entities. At training and fine-tuning time, gold spans are used for the disambiguation task. At
inference, we use the BIO-tagged predictions as our spans and predict entities for each span among all possible entities. We use the standard strong matching micro-F1 score.

heading: 5. Evaluation

heading: 5.1 Entity Linking

text: Table 1 shows that our approach outperforms all prior approaches on CoNLL and TACKBP 2010. On CoNLL, we outperform methods in both alias-table settings. Additionally, we note that unlike many previous systems, we do not use alias priors, knowledge-base features, or other entity features.

heading: 5.2 End-to-end entity linking

text:
For end-to-end entity linking, we do not use the alias table. Instead of using candidates, we predict BIO-tagged mention boundaries and disambiguate mentions among all entities. At training and fine-tuning time, gold spans are used for the disambiguation task. At inference, we use the BIO predictions as our spans and predict entities for all these spans.
Table 2 shows our model fares well against other models, with the exception of Broscheit 2019 and Kolitsas et al. 2018. The former use a much larger Transformer model, and also initialize from BERT-base model, which is pretrained on a corpus of unlabeled text much larger than our training data. Kolitsas et al. 2018 relies on an alias table to generate candidate mentions at both training and inference time. In addition, it introduces a clever mechanism to jointly optimize and select mention boundaries and entity candidates, whereas we use a simpler pipelined approach. Finally, they also introduce a document-level disambiguation coherence penalty and a coreference resolution heuristic. We believe the use of an alias
.
table as well as the aforementioned differences explain the gap between our method and Kolitsas et al. 2018, and we will look to bridge this gap in future work. Nevertheless, our model stands as a strong baseline of what can be achieved with simple modelling and low inference cost.

heading: 6. Analysis

heading: 6.1 Classifying all entities or classifying candidates

text: We trained our model to distinguish the correct linked entity among candidates. An alternative approach is to predict among all entities. This is computationally more expensive as it requires doing a softmax over 5.7 million entities for every mention in the batch. Thus we use a batch size to 2048 and set the entity embedding dimension to 64 for both this model and the one trained with candidates. Table 3 shows impressive accuracy without an alias table for the system classifying among all entities. However, it does not fare better than the model trained with candidates when using one. Given the considerable cost of doing the full sofmax for every mention, we use candidates for our other experiments. Note that our model gets 88.4% accuracy when trained only on the CoNLL data.

heading: 6.2 Impact of candidate selection

text:
In Table 4, we show the impact of different candidate selection pretraining strategies. On CoNLL, where we do use an alias table for evaluation, we find that our candidate selection heuristic seems to help the model in pre-training, achieving better performance than any of our ablations. Training with lexically related (phrase table) candidates is particularly important, as this is similar to the disambiguation task the model has to perform. Page candidates are semantically related but generally not lexically related and thus do not bring the same benefits. In fact, they might even distort the distribution of negative candidates as the model performs worse in this setting than with random candidates. After fine-tuning, all models fare similarly, which we believe is due to CoNLL having enough fine-tuning data so that all our models approach the performance upper-bound on this task (see Section 6.5).
For TAC-KBP 2010, where we do not use an alias table at fine-tuning or inference time, the results are markedly different. After pre-training, ours which has less random candidates performs worse than all other alternatives. This is likely because having more random candidates is closer to the full classification setup used in TAC-KBP 2010. Given TAC-KBP’s small training set, these differences carry over in fine-tuning performance.

heading: 6.3 Impact of adding noise during pretraining

text:
Table 5 shows adding noise in pretraining helps both pre-training and fine-tuning performance. We hypothesize that input noise implicitly trains the model to generalize to alternative aliases: for instance, given the mention “Yuri Gagarin”, the model might have to learn to recognize “Yuri [MASK]” or “[MASK] Gagarin”.
Encouraged by the success of Devlin et al. 2018, we experimented with also pretraining our model with a masked-language modelling objective, with the expectation that such pretraining would help our model learn better representations of language. We tried different architectures and loss weights (including a 4 layer transformer with both objectives at layer 4, a 12 layer with the entity linking loss at layer 4, etc.) but overall found this to not improve further on simply adding noise in pretraining.

heading: 6.4 Impact of context selection methods on CoNLL

text: Table 6 shows the impact of varying CoNLL’s context type in pre-training and fine-tuning. We find that larger contexts, especially those that include the beginning of the document, considerably boost performance before fine-tuning. However, similarly to our observations in Sections 6.2 and 6.3, we find that improvements are less marked after fine-tuning, likely because our performance is already very high.

heading: 6.5 Error analysis

text: Figure 2 shows three sample errors on the CoNLL development set. Most errors are due to varying levels of specificity in the CoNLL labels. Some errors are due to changes in Wikipedia. For instance, in text A, the Bulgaria U21 soccer team Wikipedia page was built in 2013, after CoNLL. Also, in text C, our model correctly disambiguates between Austin, Michaella and Richard Krajicek, which are all three tennis players (only Richard is a dutch).

heading: 7. Conclusion

text: In this paper we present a thorough study of pretraining strategies for supervised entity linking, achieving state-of-the-art performance on both CoNLL and TAC-KBP 2010 with a four-layer Transformer-based model. Given the limited headroom remaining in these datasets, and the strong impact of alias tables in simplifying the problem, we believe the creation of new datasets, and more difficult entity linking settings, such as zero-shot and low resource domains, are crucial areas for future work.

heading: Acknowledgments

text: The authors wish to thank Dan Bikel and Eunsol Choi for their helpful comments in the preparation of this paper, as well as the anonymous reviewers.

title: Empirical Evaluation of Pretraining Strategies for Supervised Entity Linking