Source-linked AI summary
Fast and accurate annotation of short texts with Wikipedia pages
Paolo Ferragina, Ugo Scaiella
TL;DR
The paper addresses accurate, efficient cross-referencing of short text fragments with Wikipedia pages despite synonymy, polysemy, sparse context, and on-the-fly processing needs. TAGME combines fast collective disambiguation with pruning, and reports superior short-text performance plus competitive accuracy and faster processing on long texts. The authors also note scope boundaries inherited from short-text context and tested design choices.
Problem
Annotating short, poorly composed texts requires on-the-fly spot detection and sense disambiguation despite sparse statistics and many possible Wikipedia mappings.
Method
TAGME detects Wikipedia anchors, collectively scores candidate senses with a fast voting scheme, and prunes non-pertinent annotations using link probability and coherence.
Results
78% F-measure versus 69% for Milne&Witten is reported on short texts, while TAGME remains competitive in long-text accuracy with less than 2ms per anchor.
Takeaways & Limitations
TAGME supports accurate, on-the-fly annotation of short text fragments and remains fast and competitive when applied to long texts.
Takeaways & Limitations
Previous systems were unsuitable for short, poorly composed texts because they relied on many focused spots or slow scoring functions.
Abstract
from arXiv · showhide
We address the problem of cross-referencing text fragments with Wikipedia pages, in a way that synonymy and polysemy issues are resolved accurately and efficiently. We take inspiration from a recent flow of work [Cucerzan 2007, Mihalcea and Csomai 2007, Milne and Witten 2008, Chakrabarti et al 2009], and extend their scenario from the annotation of long documents to the annotation of short texts, such as snippets of search-engine results, tweets, news, blogs, etc.. These short and poorly composed texts pose new challenges in terms of efficiency and effectiveness of the annotation process, that we address by designing and engineering TAGME, the first system that performs an accurate and on-the-fly annotation of these short textual fragments. A large set of experiments shows 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 texts.
1. INTRODUCTION
TAGME targets accurate, efficient Wikipedia annotation for very short, poorly composed texts, where spot detection and sense disambiguation are difficult. It uses fast scoring and pruning to annotate short texts on-the-fly while remaining competitive on long texts.
- Resource: Wikipedia offers more than 3 million English pages and over 500K pages in each major European language, balancing broad coverage with structured pages.This motivates using Wikipedia rather than either small structured catalogs or noisy, unstructured Web collections.
- Problem: Short texts such as search snippets, tweets, news items, and blog posts require on-the-fly detection of meaningful spots and their pertinent Wikipedia senses.The example “Diego Maradona won against Mexico” illustrates both polysemy and the need to prune non-meaningful anchors.
- Challenges: Short inputs limit the statistics available for disambiguation, while retrieval-time processing prevents preprocessing.Existing systems target longer texts, relying on many focused spots or computationally expensive scoring functions.
- TAGME: TAGME resolves synonymy and polysemy by combining fast scoring functions with collective agreement among candidate spot-to-page mappings.It uses Wikipedia anchor texts as spots and linked pages as possible senses.
- Results: TAGME outperforms adapted state-of-the-art systems on short texts in accuracy or speed, or both, and remains competitive in accuracy on long texts.The paper evaluates TAGME against two established systems on both short and long texts.
2. NOTATION AND TERMINOLOGY
The paper defines Wikipedia anchors as texts linking to pages and uses them interchangeably with spots. Polysemy creates multiple candidate pages, while a dummy page represents annotations that should be pruned.
- Anchors: An anchor is text used in one Wikipedia page to point to another page, including titles, synonyms, acronyms, redirects, or longer phrases.The examples include “nds,” “Gameboy ds,” and “Nintendo Dual Screen” for “Nintendo DS.”
- Anchors: Wikipedia provides about 8M distinct English anchors after redirect-page titles are added, and the paper uses “anchor” and “spot” interchangeably.
- Notation: For an anchor a, Pg(a) is its set of candidate pages, while freq(a), link(a), lp(a), and Pr(p|a) describe occurrence, linking, link-probability, and page-prior statistics.
- Disambiguation and pruning: Disambiguation selects one page from Pg(a), whereas the dummy mapping a 7→na prunes occurrences that are not meaningful annotations.
3. RELATED WORKS
Earlier systems enriched text using external knowledge and global coherence, but their assumptions or computational costs fit long texts better than short, poorly composed inputs. TAGME addresses this with fast collective voting, pruning schemes, and broad experiments.
- Prior approaches: Knowledge-base annotation can add concept dimensions to vector-space models, while salient-fragment annotation links meaningful text sequences to catalog senses.
- Prior approaches: Wikipedia-based systems provide millions of candidate senses and relations, but short texts offer sparse context for reliable disambiguation.
- Prior approaches: Milne&Witten’s approach uses unambiguous context pages, in-link overlap relatedness, and coherence to classify candidate senses.
- Prior approaches: Chakrabarti et al. combine local and global scores and formulate annotation as a quadratic assignment problem, making the process sophisticated and slow.
- TAGME contributions: TAGME uses a simple voting scheme over all candidate annotated senses to find collective agreement while accounting for sparse anchors in short texts.
- TAGME contributions: TAGME’s pruning schemes combine anchor link probability with coherence against other candidate annotations, selecting a simple and fast final pruner.
- Evaluation: The experiments test alternative algorithms and compare TAGME with Chakrabarti’s and Milne&Witten’s systems on short and long texts.
- Results: 78% F-measure versus 69% for Milne&Witten is reported on short texts, with precision up to 90%, recall up to 80%, and similar speed.
4. THE ANATOMY OF TAGME
TAGME combines Wikipedia-derived resources with fast parsing, disambiguation, and pruning procedures tailored to short texts. Its design uses collective agreement and commonness to resolve senses, then retains meaningful annotations while avoiding costly or poorly supported computations.
- Data structures: TAGME indexes an anchor dictionary, a 2.7M-page catalog, and an in-link graph containing about 147M edges.The dictionary is built from Wikipedia anchors, redirects, and title variants; unsuitable low-frequency anchors and unsuitable page types are removed.
- Pipeline: The annotation pipeline parses anchors, disambiguates each against a pertinent Wikipedia sense, and prunes annotations judged irrelevant to the input text.Parsing searches for multi-word anchor sequences, disambiguation selects page senses, and pruning removes possibly meaningless mappings.
- Anchor parsing: TAGME detects anchor sequences of up to six words and simplifies overlapping-boundary handling to avoid processing redundant shorter anchors.For example, when “jaguar” is contained in “jaguar cars,” discarding the shorter anchor reduces unnecessary sense processing and speeds disambiguation.
- Anchor disambiguation: Disambiguation scores each candidate sense by collective agreement with senses of other anchors, weighted by sense commonness and combined with the candidate’s own commonness.The approach exploits unambiguous anchors when available, while its simpler scores account for sparse anchors and missing unambiguous context in short texts.
- Anchor disambiguation: A commonness threshold discards low-probability senses to improve speed, but overly aggressive filtering can reduce precision by removing pertinent senses.The threshold trades off computational speed and recall against preservation of candidate senses.
- Comparison with prior work: Compared with prior disambiguation approaches, TAGME reports +6.5% absolute recall, −0.8% absolute precision, about +3% absolute F-measure, and more than one order-of-magnitude better speed on the stated comparisons.The passage attributes the speed advantage to TAGME’s use of few short vectors rather than vectors over terms and all involved senses.
- Design choice: TAGME drops surrounding-anchor text features because testing them produced either worse accuracy or slower annotation, while leaving their application value for future investigation.The paper notes that these features were used by earlier systems but are excluded from TAGME’s final design.
- Anchor pruning: Pruning combines anchor link probability with coherence among assigned senses, and TAGME selects ρAVG because it is simple, fast, and requires no training.The pruning stage extends coherence beyond unambiguous anchors and compares each pruning score with a threshold to decide whether to discard an annotation.
5. EXPERIMENTAL EVALUATION
The evaluation tests Wikipedia-anchor coverage, disambiguation and pruning choices, and Tagme’s accuracy and speed against established annotators on short and long texts. Tagme improves short-text performance substantially and remains competitive on long texts, while its speed advantage is especially pronounced against Chakrabarti’s system.
- Coverage: More than 93.9% of tweets and 98.5% of web snippets contain at least three Wikipedia anchors.For at least 95% of both short-text types, the top link-probability exceeds 6.5%.
- Evaluation setup: The evaluation measures disambiguation with precision and recall, and overall annotation with exact-match annotation precision and recall.The annotation measures require matching the ground-truth anchors exactly, whereas topic identification can tolerate different pages for the same topic.
- Short-text disambiguation: +6.5% absolute Recall and about +3% absolute F-measure versus Milne&Witten’s disambiguator were achieved on short texts, despite -0.8% absolute Precision.The improvement comes from voting over relatedness among senses associated with all anchors, including ambiguous ones.
- Short-text annotation: About 8–9% absolute gains in both precision and recall over Milne&Witten were observed for overall annotation on short texts.Tagme also improves the other approach clearly across almost all ρna values; coherence features outperform link-probability alone in pruning.
- Long-text annotation: On long texts, Tagme improves Milne&Witten uniformly across the reported precision/recall curves, but its performance approaches 72% F-measure as anchor counts grow, versus about 74% for Milne&Witten.Tagme’s settings were not retrained for long texts, and the authors plan a length-adaptive variant.
- Speed: Tagme is competitive with Chakrabarti’s system on precision/recall while being more than one order of magnitude faster on the iitb dataset.The comparison is limited by the shift-based approach used for this experiment.
- Efficiency: Tagme’s annotation complexity is O(din × (n × s)^2), and runtime is roughly quadratic for inputs with fewer than 10 anchors.As the number of anchors grows, runtime tends toward linear behavior in the reported measurements.
6. CONCLUSION AND FUTURE WORKS
Tagme is positioned as a basis for applications beyond explanatory links, including on-the-fly clustering and Web advertising. Future work investigates these applications and expands real-world evaluation.
- Future evaluation: A larger Mechanical Turk user study is being prepared to create a manually annotated dataset and extend Tagme’s evaluation.
- Applications: Tagme’s annotations may improve on-the-fly labeled clustering of search-engine results by adding knowledge beyond syntactic and statistical features.The authors are investigating its impact on SnakeT and related systems.
- Applications: The authors plan to study Tagme for Web advertising, where structured knowledge could help resolve ambiguity and polysemy when matching keywords to page content.