Over the past years, state-of-the-art information extraction (IE) systems such as NELL [5] and ReVerb [9] have achieved impressive results by producing very large knowledge resources at web scale with minimal supervision. However, these resources lack the schema information, exhibit a high degree of ambiguity, and are di cult even for humans to interpret. Working with such resources becomes easier if there is a structured information base to which the resources can be linked. In this paper, we introduce the integration of open information extraction projects with Wikipedia-based IE projects that maintain a logical schema, as an important challenge for the NLP, semantic web, and machine learning communities. We describe the problem, present a gold-standard benchmark, and take the rst steps towards a data-driven solution to the problem. This is especially promising, since NELL and ReVerb typically achieve a very large coverage, but still still lack a fulledged clean ontological structure which, on the other hand, could be provided by large-scale ontologies like DBpedia [2] or YAGO [13].
Research on information extraction (IE) systems has experienced a strong
momentum in recent years. While Wikipedia-based information extraction projects
such as DBpedia [
agentcollaborateswithagent(royals, mlb) In this triple, royals and mlb are two terms which are linked by some relation agentcollaborateswithagent. Interpreting these terms is di cult since they can have several meanings, including very infrequent and highly specialized ones, which are sometimes di cult to interpret even for humans. Here, royals refers to the baseball team Kansas City Royals and mlb to Major League Baseball.
In general, due to the fact that information on the Web is highly heterogeneous, there can be a fair amount of ambiguity in the extracted facts. The problem becomes even more obvious when we encounter triples like: bankbankincountry(royal, ireland) Here, royal refers to a di erent real-world entity, namely the Royal Bank of Scotland. Hence, it is important to uniquely identify the terms in accordance with the contextual information provided by the entire triple. In this paper, we aim at aligning such polysemous terms from open IE systems to instances from a closed IE system, while focusing on NELL and DBpedia in particular.
The remainder of the paper is organized as follows, in Section 2 we introduce the information extraction projects relevant to our work. We present our baseline algorithm for nding the best matching candidates for a term in Section 3 and in Section 4 introduce a gold standard for evaluating its performance. In Section 5 we report performance results of the proposed approach. In Section 6 we discuss related work on information extraction and entity linking. Finally, we conclude the paper in Section 7. 2
The Never Ending Language Learning [
extract novel instances. This process is repeated inde nitely with each re-training and extraction phase called an iteration. Since numerous extraction components work in parallel and extract facts with di erent degrees of con dence in their correctness, one of the most important aspects of Nell is its ability to combine these di erent extraction algorithms into one coherent model. This is also accomplished with relatively simple linear machine learning algorithms that weigh the di erent components based on their past accuracy.
Nell has been running since 2010, initially fully automated and without any human supervision. Since it has experienced concepts drift for some of its relations and classes, that is, an increasingly worse extraction performance over time, Nell now is given some corrections by humans to avoid this long-term behavior. Nell does not adhere to any of the semantic web standards such as RDF or description logic.
DBpedia [
DBpedia represents its data in accordance with the best-practices of
publishing linked open data. The term linked data describes an assortment of best
practices for publishing, sharing, and connecting structured data and knowledge
over the web [
royals ) http://dbpedia.org/resource/Kansas City Royals royal ) http://dbpedia.org/resource/The Royal Bank of Scotland 3
Wikipedia is an exhaustive source of unstructured data which has been
extensively used to enrich machines with knowledge [
In this work we accordingly ex- anchor Article Link count plore the idea of using Wikipedia to jaguar Jaguar Cars 1842 nd out the most probable article for jaguar Jaguar Racing 440 a given term. Wikipedia provides reg- jaguar Jaguar 414 ular data dumps and there are o - . . . . . . . . . the-shelf preprocessing tools to parse those dumps. We used WikiPrep [11, lincoln Lincoln, England 1844 10] for our purpose. WikiPrep re- lincoln Lincoln, Nebraska 920 moves redundant information from lincoln Lincoln (2012 lm) 496 the original dumps and creates more . . . . . . . . . relevant XML dumps with additional information like the number of pages uTsainbgleth1e. Sannicphpoertjaogfutharosaenadrtliicnlceosllnin.ked to in each category, incoming links to each Wikipedia article and their anchor text, and a lot more2. In our work, we are primarily interested in the link counts, namely the frequency of anchor text labels pointing to the same Wikipedia page. Table 1 shows some of the articles the anchors jaguar or lincoln are referring to. Intuitively, out of all the outgoing links from the anchor term jaguar, 1842 links pointed to the article Jaguar Cars and so on. Essentially, these anchors are analogous to the NELL terms. Based on these counts, we create a ranked list of articles for a given anchor3.
As seen in Table 1, the output from WikiPrep can often be a long list of
anchor-article pairs and some of them having as low as just one link count.
Accordingly, we adopt a probabilistic approach in selecting the best possible
DBpedia instance. For any given anchor in Wikipedia, the fraction of articles
the links points to is proportional to the probability that the anchor term refers
to the particular article [
Nell provides regular data dumps4 consisting of facts learned from the Web.
Based on this data we create a frequency distribution over the predicates. To this
end, we rst clean up the data from the dumps (since these contain additional
2 http://www.cs.technion.ac.il/~gabr/resources/code/wikiprep/
3 Note that, while there are alternative data sets such as the Crosswiki data [
Top predicates generalizations
proxyfor agentcreated subpartof atlocation mutualproxyfor locationlocatedwithinlocation athleteplayssport citylocatedinstate professionistypeofprofession subpartoforganization
bookwriter furniturefoundinroom agentcollaborateswithagent animalistypeofanimal
agentactsinlocation teamplaysagainstteam athleteplaysinleague
worksfor chemicalistypeofchemical
Random predicates personleads-organization countrylocatedingeopoliticallocation actorstarredinmovie athleteledsportsteam
personbornincity bankbankincountry weaponmadeincountry
athletebeatathlete companyalsoknownas lakeinstate information, such as, for instance, iteration of promotion, best literal strings, and so on5, which are irrelevant to our task). In Table 2, we list the 30 most frequent predicates. Since the gold standard should not be biased towards predicates with many assertions we randomly sampled 12 predicates from the set of predicates with at least 100 assertions (highlighted in bold in the table). In this paper, we focus on this smaller set of predicates due to the time consuming nature of the manual annotations we needed to perform. However, we plan to continuously extend the gold standard with additional predicates in the future.
For each Nell predicate we randomly sampled 100 triples. We assigned each predicate and the corresponding list of triples to an annotator. Since we wanted to annotate a large number of triples within an acceptable time frame, we rst applied the method described in Section 3 to generate possible mapping candidates for the Nell subject and object of each triple. In particular, we generated the top-3 mappings, thereby avoiding generation of too many possible candidates, and presented those candidates to the annotator. Note that in some cases (see Table 3), our method could not determine a possible mapping candidate for a Nell instance. In this case, the triple had to be annotated without presenting a matching candidate for subject or object or both. In our setting, each annotation instance falls under one of the following three cases: (i) One of the mapping candidates is chosen as the correct mapping, i.e., the simplest case. (ii) The correct mapping is not among the presented candidates (or no candidates have been generated). However, the annotator can nd the correct
stranger gospel riddle master king john Nell-Object albert-camus 1st cand. 2nd cand. 3rd cand. henry james 1st cand. 2nd cand.
3rd cand. patricia a mckillip 1st cand. 2nd cand. 3rd cand. shakespeare 1st cand. 2nd cand. 3rd cand.
The Stranger (novel)
Stranger (comics) Stranger (Hilary Du song) Characters of Myst
? Gospel music
Gospel Urban contemporary gospel The Riddle-Master of Hed
King John (play) John, King of England
King John (play) King John (1899 lm)
Albert Camus Albert Camus Henry James
Henry James Henry James (basketball) Henry James, 1st Baron...
Patricia A. McKillip Patricia A. McKillip William Shakespeare
William Shakespeare Shakespeare quadrangle Shakespeare, Ontario
mapping after a combined search in DBpedia, Wikipedia or other resources available on the Web. (iii) The annotator cannot determine a DBpedia entity to which the given Nell instance should be mapped. This was the case when the term was too ambiguous, underspeci ed, or not represented in DBpedia. In this case the annotator marked the instance as unmatchable (`?').
Evaluation Measures In the following, we brie y re-visit the de nitions of precision and recall and explain their application in our evaluation scenario. Let A refer to the mappings generated by our algorithm, and G refer to mappings in the gold standard. Precision is de ned as prec(A; G) = jA \ Gj=jAj and recall as rec(A; G) = jA \ Gj=jGj. The F1 measure is the equally weighted harmonic mean of both values, i.e., F1(A; G) = 2 prec(A; G) rec(A; G)=(prec(A; G) + rec(A; G)).
If an annotator assigned a question mark, then the corresponding Nell term could not be mapped and it does not appear in the gold standard G. This can again be seen in Table 3, where we present the mappings generated by
Predicate agentcollaborateswithagent
lakeinstate personleadsorganization
bookwriter animalistypeofanimal teamplaysagainstteam companyasloknownas weaponmadeincountry actorstarredinmovie bankbankincountry citylocatedinstate athleteledsportsteam our algorithm for four triples, as well as the corresponding gold-standard annotations. If the mapping A consists of top-k possible candidates, computing precision and recall on the examples, we have the precision value for k = 1 as prec@1 = 4=7 57% and rec@1 = 4=7 57%. Note that precision and recall are not the same in general, because jAj 6= jGj in most cases. More generally, we are interested in prec@k, the fraction of top-k candidates that are correctly mapped and rec@k, the fraction of correct mappings that are in the top-k candidates. For k = 3, we have prec@3 = 5=17 29% and rec@3 = 5=7 71%.
It can be expected that prec@1 will have the highest score and rec@1 will have the lowest score. When we analyze A with k > 1, we focus mainly on the increase in recall. Here we are in particular interested in the value of k for which the number of additionally generated correct mappings in A is negligibly small compared to the mappings generated in A for k + 1.
When generating the gold standard, we realized that nding the correct mappings is often a hard task and sometimes even di cult for a human annotator. We had also observed that the problem of determining the gold standard varies strongly across the properties we analyzed. For some of the properties we could match all (or nearly all) subjects and objects in the chosen triples, while for other properties up to 15% of the instances could not be matched. In this case, the mapping for subject and object was annotated with a question mark. We also observed cases in which an uncommon description was chosen that had no counterpart in DBpedia. Some examples from the predicate animalistypeofanimal are the labels furbearers or small mammals. 0 lla ..081 0.810.82 0.820.86 0.860.88 0.890.86 0.820.78 c e /R .06 n o iisc .40 e rP .2 0 0 . actor0staargreednitncmoloavbieorateswithaagneinmtalistypeofanaitmhlaelteledsportsteabmankbankincountrcyitylocatedinstate 0.8 0.81 0.820.83 5.2
Results and Discussion We run our algorithm against the gold standard6, and report the precision and recall values. In Figure 1, we show the precision and recall values obtained on the set of Nell predicates. These values are for top-1 matches. Precision and recall vary across the predicates with lakeinstate having the highest precision. Using micro-average method, for the top-1 matches we achieved a precision of 82.78% and an average recall of 81.31% across all the predicates. In the case of macro-averaging, instead, we achieved precision of 82.61% and recall of 81.42%.
In Figure 2, we show the values for rec@2, rec@5 and rec@10 compared to rec@1, the recall values reported in Figure 1. By considering more possible candidates with increasing k, every term gets a better chance of being matched correctly, thus explaining the increases in rec@k with k. However, it must be noted, that for most of the predicates the values tend to saturate after rec@5. This re ects that after a certain k any further increase in k does not alter the correct mappings, since our algorithm already provided a match within top-1 or top-2 candidates. Still, for some we observe an increase even at rec@10 because there can be still a possibility of one correct matching candidate lying at a much lower rank in the top-k list of candidates.
In Figure 3, we plot the micro-average values of the precision, recall and F1 scores over varying k. We attain the best F1 score of 0.82 for k = 1 and the recall values tend to saturate after k = 5.
This raises an important question regarding the upper bound of recall of our algorithm. In practice, we cannot achieve a recall of 1.0 because we are limited from factors like: { the matching candidate being never referred to by the terms. For example, gs refers to the company Goldmann Sachs, but it never appeared even in all the possible candidates, since Goldmann Sachs is never referred to with gs in Wikipedia. 6 The data are freely available at http://web.informatik.uni-mannheim.de/data/ nell-dbpedia/NellGoldStandard.tar. 0 . 1 8 .
0 l 6 la .0 c e R .40 2 . 0 0 a.0ctorstarraegdeinnmtcoovliaeborateswithageanntimalistypeofanimatahlleteledsportsteambankbankincountrycitylocatedinstate
NELL Pbroeodkcwiocrmitaepratneysasloknpoewrsnoansleadsorganization teamplaysagainstweeaamponmadeincountry lakeinstate { persons being often referred to by the combination of their middle and last name. For e.g. hussein obama. It is actually talking about President Barack Obama, but with our approach we cannot nd a good match.
{ misspelled words. We have entities like missle instead of missile. However, there are ways to further improve the recall of our method like, for instance, by means of string similarity techniques { e.g., Levenshtein edit distance. A similarity threshold (say, as high as 95%) could then be tuned to consider entities which only partially match a given term. Another alternative would be to look for sub-string matches for the terms with middle and last names of persons. For instance, hussein obama can have a possible match if terms like barrack hussein obama has a candidate match. In addition, a similarity threshold can be introduced in order to avoid matching by arbitrary longer terms.
In general, thanks to the annotation task and our experiments we were able to acquire some useful insights about the .01 data set and the proposed task. 0.89 0.89 { Predicates with polysemous entities, like companyalso knownas, usually have lower precision. The triples for this predicate had a wide usage of abbreviated terms (the stock exchange codes for the companies) and that accounts for a lower precision value. { The Nell data is skewed towards a particular region or type. The triples involving persons and sports primarily refer to basketball or baseball. Similarly, for lakeinstate, nearly all the triples refer to lakes in United States. 6
Key contributions in information extraction have concentrated on minimizing
the amount of human supervision required in the knowledge harvesting process.
To this end, much work has explored unsupervised bootstrapping for a variety
of tasks, including the acquisition of binary relations [
There has been some work on instance matching in the recent past.
Researchers have transformed the task into a binary classi cation problem and
solved it with machine learning techniques [
In this paper, we introduced a most-frequent-entity baseline algorithm in order to link entities from an open domain system to a closed one. We introduced a gold standard for this task and compared our baseline against it. In the near future, we plan to extend this work with more complex and robust methods, as well as extending our methodology to cover other open IE projects like ReVerb.