Collective annotation of Wikipedia entities in web text

ABSTRACT

To take the first step beyond keyword-based search toward entity-based search, suitable token spans ("spots") on documents must be identified as references to real-world entities from an entity catalog. Several systems have been proposed to link spots on Web pages to entities in Wikipedia. They are largely based on local compatibility between the text around the spot and textual metadata associated with the entity. Two recent systems exploit inter-label dependencies, but in limited ways. We propose a general collective disambiguation approach. Our premise is that coherent documents refer to entities from one or a few related topics or domains. We give formulations for the trade-off between local spot-to-entity compatibility and measures of global coherence between entities. Optimizing the overall entity assignment is NP-hard. We investigate practical solutions based on local hill-climbing, rounding integer linear programs, and pre-clustering entities followed by local optimization within clusters. In experiments involving over a hundred manually-annotated Web pages and tens of thousands of spots, our approaches significantly outperform recently-proposed algorithms.

REFERENCES

• 1: Eneko Agirre , German Rigau, Word sense disambiguation using Conceptual Density, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark [doi>10.3115/992628.992635]
• 2: Sanjay Agrawal , Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Arnd Christian Konig , Dong Xin, Exploiting web search engines to search structured databases, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526777]
• 3: R. Bunescu and M. Pasca. Using encyclopedic knowledge for named entity disambiguation. In EACL, pages 9--16, 2006.
• 4: S. Cucerzan. Large-scale named entity disambiguation based on Wikipedia data. In EMNLP Conference, pages 708--716, 2007.
• 5: Stephen Dill , Nadav Eiron , David Gibson , Daniel Gruhl , R. Guha , Anant Jhingran , Tapas Kanungo , Sridhar Rajagopalan , Andrew Tomkins , John A. Tomlin , Jason Y. Zien, SemTag and seeker: bootstrapping the semantic web via automated semantic annotation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775178]
• 6: U. Feige, D. Peleg, and G. Kortsaz. The dense k-subgraph problem. Algorithmica, 29(3):410--421, Dec. 2001.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: R. V. Guha and R. McCool. TAP: A semantic web test-bed. Journal of Web Semantics, 1(1):81--87, 2003.
• 9: Michael I. Jordan, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: Subhash Khot, Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.136-145, October 17-19, 2004 [doi>10.1109/FOCS.2004.59]
• 11: R. Larson. Bibliometrics of the world wide web: An exploratory analysis of the intellectual structure of cyberspace. In Annual Meeting of the American Society for Information Science, 1996. Online at http://sherlock.berkeley.edu/asis96/asis96.html.
• 12: Douglas B. Lenat, CYC: a large-scale investment in knowledge infrastructure, Communications of the ACM, v.38 n.11, p.33-38, Nov. 1995 [doi>10.1145/219717.219745]
• 13: Rada Mihalcea , Andras Csomai, Wikify!: linking documents to encyclopedic knowledge, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321475]
• 14: G. Miller, R. Beckwith, C. FellBaum, D. Gross, K. Miller, and R. Tengi. Five papers on WordNet. Princeton University, Aug. 1993.
• 15: David Milne , Ian H. Witten, Learning to link with wikipedia, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458150]
• 16: Viswanath Nagarajan , Maxim Sviridenko, On the maximum quadratic assignment problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.516-524, January 04-06, 2009, New York, New York
• 17: Sunita Sarawagi, Information Extraction, Foundations and Trends in Databases, v.1 n.3, p.261-377, March 2008 [doi>10.1561/1900000003]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation

Keywords:
Wikipedia, collective inference, entity annotation/disambiguation