First Steps Beyond the Bag-Of-Words Representation of Short Texts. (2011)

We address the problem of enhancing the classical bag-ofwords representation of texts by designing and engineering Tagme, the first system that performs an accurate and on-the-fly semantic annotation of short texts via Wikipedia as knowledge base. Several experiments show that Tagme outperforms state-of-the-art algorithms when they are adapted to work on short texts and it results fast and competitive on long ones. This leads us to argue favorably about Tagme’s application to clustering, classification and retrieval systems on challenging scenarios like web-snippets, tweets, news, ads, etc.. 1 Motivation and background The typical IR-approach to indexing, clustering, classification and retrieval, just to name a few, is that based on the bag-of-words paradigm. In recent years a good deal of work attempted to go beyond this paradigm with the goal of improving the search experience on (unstructured) textual data. In our work we are concerned with the task of adding structure to unstructured data, consisting of the identification of sequences of terms (aka spots) in the input text and their annotation with a Wikipedia page. This annotation process provides a stunning contextualization of the input text so that each subsequent IR-task could be improved by leveraging the huge semantic network provided by Wikipedia. Recently several works (see e.g. [4, 6] and refs therein) addressed the problem of annotating texts with hyper-links to Wikipedia pages. We add to this flow of work the specialty that the input texts to be annotated are short, namely, they are composed of few tens of terms. The context of use we have in mind is the annotation of either the snippets of search-engine results, or the tweets of a Twitter channel, or the items of a news feed, or the posts of a blog, or the advertisement messages, etc.. It is easy to argue that these poorly composed texts pose new challenges in terms of efficiency and effectiveness of the annotation process, which (1) should be very fast, because in those contexts data may be retrieved at query time and thus cannot be pre-processed, and (2) should be designed properly, because the input texts are so short that it is difficult to mine significant statistics that are rather available when texts are long. To address these issues, we have designed and implemented Tagme the first software system that, on-the-fly and with high precision/recall, annotates short texts with pertinent hyper-links to Wikipedia pages. As an example, let us consider the following news: “Diego Maradona won against Mexico”. Our goal is to detect “Diego Maradona” and “Mexico” as spots, and then hyper-link them with the Wikipedia pages which deal with the ex Argentina’s coach and the football team of Mexico. Tagme uses as spots (to be annotated) the sequences of terms composing the anchor texts which occur in the Wikipedia pages, and it uses as possible senses for each spot the (possibly many) pages pointed in Wikipedia by that spot/anchor. Tagme selects among the potentially many available mappings (spot-to-page) the most pertinent ones by finding a collective agreement among them via new scoring functions which are fast to be computed and accurate in the finally produced annotation. A preliminary description of Tagme has been published as poster in Procs ACM CIKM 2010. Tagme is available for test at http://tagme.di.unipi.it. What follows is a sketch of the main ideas and experimental results concerning with Tagme, the interested reader is invited to read [3] for details. 2 The anatomy of TAGME The annotation process of Tagme is composed by two main phases: Anchor disambiguation and Anchor pruning. Anchor disambiguation. This is the task that judiciously cross-references each anchor a ∈ AT found in the input text T with one pertinent page pa of Wikipedia. Tagme selects the best association a 7→ pa by computing a score for each possible page pa linked to a in Wikipedia (we call Pg(a) this set) that is based on a new notion of “collective agreement” between the page pa and the pages that can be associated to all other anchors detected in T , i.e. the anchors in AT . This agreement is evaluated by means of a voting scheme that computes for each other anchor b ∈ AT {a} its vote to the annotation a 7→ pa. Given that b may be linked to many pages in Wikipedia (i.e. |Pg(b)| > 1) we compute this vote as the average relatedness between each page pb, potentially linked to b, and the sense pa we wish to associate to a. However we argue that not all possible pages of b have the same (statistical) significance, so we weight each relatedness with the commonness of the page pb with respect to b (denoted as Pr(pb|b) and computed as the prior probability that b points to pb over all links of b in Wikipedia). Hence the voting given by anchor b to the annotation a 7→ pa is vb(pa) = 1 |Pg(b)| · ∑ pb∈Pg(b) rel(pb, pa) · Pr(pb|b) where the relatedness rel(pb, pa) between the two Wikipedia pages pa and pb is computed as suggested in [5] by exploiting the intersection over the incoming links to pa and pb. The overall score for the annotation a 7→ pa is computed as the sum of the votes given by all anchors b in T . This score is not enough to obtain an accurate disambiguation, so we first filter out candidate pages in Pg(a), via a properly set threshold, and then select the best page by deploying the commonness scores. Anchor pruning. This step detects and possibly prunes some of the candidate annotations produced by the Disambiguation phase, if they are considered to be not meaningful. These “bad annotations” are detected via a simple, yet effective, scoring function that takes into account only two features: (1) the link 1 “Diego Maradona” is the name of two persons and “Mexico” points to 154 different