Short context messages (like tweets and SMS's) are a potentially rich source of continuously and instantly updated information. Shortness and informality of such messages are challenges for Natural Language Processing tasks. Most efforts done in this direction rely on machine learning techniques which are expensive in terms of data collection and training. In this paper we present an unsupervised Semantic Web-driven approach to improve the extraction process by using clues from the disambiguation process. For extraction we used a simple Knowledge-Base matching technique combined with a clustering-based approach for disambiguation. Experimental results on a self-collected set of tweets (as an example of short context messages) show improvement in extraction results when using unsupervised feedback from the disambiguation process.
The rapid growth in IT in the last two decades has led to a growth in the amount of information available on the World Wide Web. A new style for exchanging and sharing information is short context. Examples for this style of text are tweets, social networks’ statuses, SMS’s, and chat messages.
In this paper we use twitter messages as a representative example of short informal
context. Twitter is an important source for continuously and instantly updated
information. The average number of tweets exceeds 140 million tweet per day sent by over
200 million users around the world. These numbers are growing exponentially [
Information Extraction (IE) is the research field which enables the use of such a vast amount of unstructured distributed information in a structured way. IE systems analyze human language text in order to extract information about pre-specified types of events, entities, or relationships. Named entity extraction (NEE) (a.k.a. named entity recognition) is a subtask of IE that seeks to locate and classify atomic elements (mentions) in text belonging to predefined categories such as the names of persons, locations, etc. While named entity disambiguation (NED) is the task of exploring which correct person, place, event, etc. is referred to by a mention.
NEE & NED processes on short messages are basic steps of many SMS services
such as [
Few research efforts studied NEE on tweets [
NEE and NED are highly dependent processes. In our previous work [
Contribution: In this paper we propose an unsupervised approach to prove the
validity of the reinforcement effect on short informal text. Our approach uses
KnowledgeBase (KB) lookup (here we use YAGO [
Furthermore, we propose an idea to solve the problem of lacking context needed for disambiguation by constructing profiles of messages with the same hashtag or messages sent by the same user. Figure 1 shows our approach on tweets as an example for short messages.
(1) We consider the KB-based NEE process as a basic predecessor step for NED. This means that we are only concerned with named entities that can be disambiguated. NED cannot be done without a KB to lookup possible candidates of the extracted mentions. Thus, we focus on public and famous named entities like players, companies, celebrities, locations, etc. (2) We assume the messages to be informative (i.e. contains some useful information about one or more named entities). Dealing with noisy messages is not within our scope. 2
In this work we use YAGO KB for extraction as well as disambiguation processes. YAGO is built on Wikipedia, WordNet, and GeoNames. It contains more than 447 million facts for 9.8 million entities. A fact is a tuple representing a relation between two entities. YAGO has about 100 relations, such as hasWonPrize, isKnownFor, isLocatedIn and hasInternalWikipediaLinkTo. Furthermore, it contains relations connecting mentions to entities such as hasPreferredName, means, and isCalled. The means relation represents the relation between the entity and all possible mention representations in wikipedia. For example the mentions {“Chris Ronaldo”, “Christiano”, “Golden Boy”, “Cristiano Ronaldo dos Santos Aveiro”} and many more are all related to the entity “Christiano Ronaldo” through the means relation. 2.1
The list lookup strategy is an old method of performing NEE by scanning all possible
n-grams of a document content against the mentions-entities table of a KB like YAGO
or DBpedia [
The advantages of this extraction method are:
(1) It prevents the imperfection of the standard extraction techniques (like POS) which
perform quite poorly when applied to Tweets [
On the other hand, the disadvantages of this method for NEE are: (1) Not retrieving correct NEs which are misspelled or don’t match any facts in the KB. (2) Retrieving many false positives (n-grams that match facts in the KB but do not represent a real NE).
This results in a high recall and low precision for the extraction process. In this paper we suggest a solution for the second disadvantage by using feedback from NED in an unsupervised manner for detecting false positives.
As we are concerned with NED, it is inefficient to annotate all the n-grams space as
named entities to achieve recall of 1. To do NED we still need a KB to lookup for the
named entities.
NED is the process of establishing mappings between extracted mentions and the actual
entities [
To prove the feasibility of using the disambiguation results to enhance extraction precision, we developed a simple disambiguation algorithm (see Algorithm 1). This algorithm assumes that the correct entities for mentions appearing in the same message should be related to each other in YAGO KB graph.
The input of the algorithm is the set of all candidate entities R(mi) for the extracted mentions mi. The algorithm finds all possible permutations of the entities. Each permutation includes one candidate entity for each mention. For each permutation pl we apply agglomerative clustering to obtain a set of clusters of related entities (Clusters(pl)) according to YAGO KB. We determine Clusters(pl) having minimum size.
The agglomerative clustering starts with each candidate in pl as a separate cluster. Then it merges clusters that contains related candidates. Clustering terminates when no more merging is possible. Tweet rcthu@rcbhreinakailnegxnaenwdrsi:a,eexgpylpots;iosenverreaplokritleldeda-tbbac.ccoopmtic owfpeompeirngioennc:ymioshitasmreedpreelsbsaerdaddeeim•oecgryapcyt’s real state Extracted mentions caolepxtaicndcrhiau,recxhp,locshiuornc,hreipno,rtkeidlled, egypt, bbc.com setlabtaeroafdeemi, erregpernescsye,de,gdyepmt,oocprainciyon, real, mohamed dGirdoautepsenoftirtieelsated can- {{{ASCClephoxaupacrtnecichdSerOhsiauro,tttfhEleoRgdyCoopmhxtae,l}CBle,h{BnKugCericlrNlhedediowsfiasns}Atea,lrce}txi,oa{nnR}de,rpiao,rted} {{ESRgtyeaaptlet}(oL,f’{AeRmrecpe-reregnse-snCecidye}l},,a{{lMDbueommh)oa}cmraecdyE(plBlaayr)a}d,ei,
Two candidates for two different mentions are considered related if there exists a direct or indirect path from one to the other in YAGO KB graph. Direct paths are defined as follows: candidate eij is related to candidate elk if there exists a fact of the form <eij , some relation, elk>. For indirect relations, candidate eij is related to candidate elk if there exist two facts of the form <eij , some relation, exy >and a fact <exy , some relation, elk>. We refer to the direct and the indirect relation in the experimental results section with ”relations of depth 1” and ”relations of depth 2”.
We didn’t go further than relations with length more than 2, because the time needed to build an entity graph grows exponentially with the increase in the number of levels. In addition, considering relations of a longer path is expected to group all the candidates in one cluster as they are likely to be related to each other through some intermediate entities.
Finding false positives: We select the winning Clusters(pl) as the one having minimum size. We expect to find one or more clusters that include almost all correct entities of all real mentions and other clusters each containing only one entity. Those clusters with size one contain most probably entities of false positive mentions.
Table 1 shows two examples for tweets along with the extracted mentions (using the KB lookup) and the clusters of related candidate entities. It can be observed that the correct candidate of real mentions are grouped in one cluster while false positives ended up alone in individual clusters.
Like the KB lookup extractor, this method of disambiguation can be applied on any language once the KB contains NE mentions for this language. 3
Here we present some experimental results to show the effectiveness of using the disambiguation results to improve the extraction precision by discovery of false positives. We also discuss the weak points of our approach and give some suggestions for how to overcome them.
input : M = {mi} set of extracted mentions, R(mi) = {eij 2 Knowledge base} set of candidate entities for mi output: Clusters(pl) = {cj} set of clusters of related candidate entities for permutation pl where |Clusters(pl)| is the minimum
Permutations = {{e1x, . . . , enx} | 8 1 i n9 !x : eix 2 R(mi)} end Find Clusters(pl) with minimum size; foreach Permutation pl 2 Permutations do
Clusters(pl) = Agglomerative Clustering{pl}; We selected and manually annotated a set of 162 tweets that are found to be rich with NEs. This set is collected by searching in an open collection of tweets1 for named entities that belong to topics like politics, sports, movie stars, etc. Messages are selected randomly from the search results. The set contains 3.23 NE/tweet on average.
Capitalization is a key orthographic feature for extracting NEs. Unfortunately in
informal short messages, capitalization is much less reliable than in edited texts [
The results are presented in table 2. The main observations are that the Stanford NER performs badly on our extraction task; and as expected the KB lookup extractor is able achieve high recall and low precision; and feedback from the disambiguation process improved overall extraction effectiveness (as indicated by the F1 measure) by improving precision at the expense of some recall. 3.3
KB lu extractor achieves a high recall with low precision due to many false positives. While KB lu + rod 1 achieves high precision as it looks only for direct related entities like ”Egypt” and ”Alexandria”.
By increasing the scope of finding related entities to depth 2, KB lu + rod 2 finds more related entities and hence fails to discover some false positives. This leads to a drop in the recall and an enhancement in both precision and F1 measure (compared with KB lu).
One major problem that harms recall is to have a message with an entity not related to any other NEs or to have only one NE within the message. Case 1 in table 3 shows a message with only one named entity (india) that ends up alone in a cluster and thus considered false positive. A suggestion to overcome such problem is to expand the context by also considering messages replied to this submission or messages having the same hashtag or messages sent by the same user. It is possible to get enough context needed for the disambiguation process using user or hashtag profiles. Figures 2(a), 2(b) and 2(c) show the word clouds generated for the hashtags “Egypt”, “Superbowl” and for the user “LizzieViolet” respectively. Word clouds for hashtags are generated from the TREC 2011 Microblog Track collection of tweets 2. This collection covers both the time period of the Egyptian revolution and the US Superbowl. The terms size in the 2 http://trec.nist.gov/data/tweets/ word cloud proportionates the probability that the term is being mentioned in the profile tweets.
Another problem that harms precision are entities like the “United States” that are related to many other entities. In case 2 of table 3, the mention “talks” is extracted as named entity. One of its entity candidates is “Camp David Accords” which is grouped with “Catherine Hardwicke” as they both are related to the entity “United States” (using KB lu + rod 2). Both entities are related to “United States” through relation of type “hasInternalWikipediaLinkTo”. A suggestion to overcome this problem is to incorporate a weight representing the strength of the relation between two entities. This weight should be inversely proportional to the degree of the intermediate entity node in the KB graph. In our example the relation weight between “Camp David Accords” and “Catherine Hardwicke” should be very low because they are related together through “United States” which has a very high number of edges connected to its node in the KB graph. 4
In this paper we introduced an approach for unsupervised improvement of Named Entity Extraction (NEE) in short context using clues from Named Entity Disambiguation (NED). To show its effectiveness experimentally, we chose an approach for NEE based on knowledge base lookup. This method of extraction achieves high recall and low precision. Feedback from the disambiguation process is used to discover false positives and thereby improve the precision and F1 measure.
In our future work, we aim to enhance our results by considering a wider context than a single message for NED, applying relation weights for reducing the impact of non-distinguishing highly-connected entities, and to study the portability of our approach across multiple languages. (a) #Egypt (b) #Superbowl (c) user LizzieViolet