Named entity mining from click-through data using weakly supervised latent dirichlet allocation

ABSTRACT

This paper addresses Named Entity Mining (NEM), in which we mine knowledge about named entities such as movies, games, and books from a huge amount of data. NEM is potentially useful in many applications including web search, online advertisement, and recommender system. There are three challenges for the task: finding suitable data source, coping with the ambiguities of named entity classes, and incorporating necessary human supervision into the mining process. This paper proposes conducting NEM by using click-through data collected at a web search engine, employing a topic model that generates the click-through data, and learning the topic model by weak supervision from humans. Specifically, it characterizes each named entity by its associated queries and URLs in the click-through data. It uses the topic model to resolve ambiguities of named entity classes by representing the classes as topics. It employs a method, referred to as Weakly Supervised Latent Dirichlet Allocation (WS-LDA), to accurately learn the topic model with partially labeled named entities. Experiments on a large scale click-through data containing over 1.5 billion query-URL pairs show that the proposed approach can conduct very accurate NEM and significantly outperforms the baseline.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 2: Daniel M. Bikel , Scott Miller , Richard Schwartz , Ralph Weischedel, Nymble: a high-performance learning name-finder, Proceedings of the fifth conference on Applied natural language processing, p.194-201, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974586]
• 3: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 4: D. Blei and J. McAulie. Supervised topic models. In Advances in Neural Information Processing Systems 21(NIPS'07), MIT Press, 2007.
• 5: Andrew Eliot Borthwick , Ralph Grishman, A maximum entropy approach to named entity recognition, New York University, New York, NY, 1999
• 6: Huanhuan Cao , Daxin Jiang , Jian Pei , Qi He , Zhen Liao , Enhong Chen , Hang Li, Context-aware query suggestion by mining click-through and session data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401995]
• 7: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Probabilistic query expansion using query logs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511489]
• 8: Laura Dietz , Steffen Bickel , Tobias Scheffer, Unsupervised prediction of citation influences, Proceedings of the 24th international conference on Machine learning, p.233-240, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273526]
• 9: Oren Etzioni , Michael Cafarella , Doug Downey , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Unsupervised named-entity extraction from the web: an experimental study, Artificial Intelligence, v.165 n.1, p.91-134, June 2005 [doi>10.1016/j.artint.2005.03.001]
• 10: R. Gaizauskas , K. Humphreys , H. Cunningham , Y. Wilks, University of Sheffield: description of the LaSIE system as used for MUC-6, Proceedings of the 6th conference on Message understanding, November 06-08, 1995, Columbia, Maryland [doi>10.3115/1072399.1072418]
• 11: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 12: Chien-Kang Huang , Lee-Feng Chien , Yen-Jen Oyang, Relevant term suggestion in interactive web search based on contextual information in query session logs, Journal of the American Society for Information Science and Technology, v.54 n.7, p.638-649, May 2003 [doi>10.1002/asi.10256]
• 13: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 14: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 15: Bing Liu , Yang Dai , Xiaoli Li , Wee Sun Lee , Philip S. Yu, Building Text Classifiers Using Positive and Unlabeled Examples, Proceedings of the Third IEEE International Conference on Data Mining, p.179, November 19-22, 2003
• 16: Andrew McCallum , Wei Li, Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.188-191, May 31, 2003, Edmonton, Canada [doi>10.3115/1119176.1119206]
• 17: Qiaozhu Mei , Deng Cai , Duo Zhang , ChengXiang Zhai, Topic modeling with network regularization, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367512]
• 18: Marius Paşca, Organizing and searching the world wide web of facts -- step two: harnessing the wisdom of the crowds, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242587]
• 19: Marius Paşca, Weakly-supervised discovery of named entities using web search queries, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321536]
• 20: Issei Sato , Hiroshi Nakagawa, Knowledge discovery of multiple-topic document using parametric mixture model with dirichlet prior, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281256]
• 21: N. Ueda and K. Saito. Parametric mixture models for multi-labeled text. In Advances in Neural Information Processing Systems 15 (NIPS'03), pp.721--728. MIT Press, 2003.
• 22: Xing Wei , W. Bruce Croft, LDA-based document models for ad-hoc retrieval, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148204]
• 23: Hwanjo Yu , Jiawei Han , Kevin Chen-Chuan Chang, PEBL: positive example based learning for Web page classification using SVM, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775083]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Experimentation

Keywords:
named entity recognition, search log mining, topic model, web mining