Extracting structured information from user queries with semi-supervised conditional random fields

ABSTRACT

When search is against structured documents, it is beneficial to extract information from user queries in a format that is consistent with the backend data structure. As one step toward this goal, we study the problem of query tagging which is to assign each query term to a pre-defined category. Our problem could be approached by learning a conditional random field (CRF) model (or other statistical models) in a supervised fashion, but this would require substantial human-annotation effort. In this work, we focus on a semi-supervised learning method for CRFs that utilizes two data sources: (1) a small amount of manually-labeled queries, and (2) a large amount of queries in which some word tokens have derived labels, i.e., label information automatically obtained from additional resources. We present two principled ways of encoding derived label information in a CRF model. Such information is viewed as hard evidence in one setting and as soft evidence in the other. In addition to the general methodology of how to use derived labels in semi-supervised CRFs, we also present a practical method on how to obtain them by leveraging user click data and an in-domain database that contains structured documents. Evaluation on product search queries shows the effectiveness of our approach in improving tagging accuracies.

REFERENCES

• 1: Steven Abney, Understanding the Yarowsky Algorithm, Computational Linguistics, v.30 n.3, p.365-395, September 2004 [doi>10.1162/0891201041850876]
• 2: Arvind Arasu , Hector Garcia-Molina, Extracting structured data from Web pages, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872799]
• 3: Cory Barr , Rosie Jones , Moira Regelson, The linguistic structure of English web-search queries, Proceedings of the Conference on Empirical Methods in Natural Language Processing, October 25-27, 2008, Honolulu, Hawaii
• 4: J. Bilmes. On soft evidence in Bayesian networks. Technical Report UWEETR-2004-0016, University of Washington, 2004.
• 5: S. Canisius and C. Sporleder. Bootstrapping information extraction from field books. In Proceedings of the 2007 Conference on Empirical Methods in Natural Language Processing, pages 827--836, 2007.
• 6: Gregory Druck , Gideon Mann , Andrew McCallum, Learning from labeled features using generalized expectation criteria, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390436]
• 7: Y. Grandvalet and Y. Bengio. Semi-supervised learning by entropy minimization. In Advances in Neural Information Processing Systems, 2004.
• 8: Trond Grenager , Dan Klein , Christopher D. Manning, Unsupervised learning of field segmentation models for information extraction, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.371-378, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219886]
• 9: Feng Jiao , Shaojun Wang , Chi-Hoon Lee , Russell Greiner , Dale Schuurmans, Semi-supervised conditional random fields for improved sequence segmentation and labeling, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.209-216, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220202]
• 10: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 11: Xiao Li , Ye-Yi Wang , Alex Acero, Learning query intent from regularized click graphs, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390393]
• 12: G.S. Mann and A. McCallum. Generalized expectation criteria for semi-supervised learning of conditional random fields. In Proceedings of Association of Computational Linguistics, 2008.
• 13: David Pinto , Andrew McCallum , Xing Wei , W. Bruce Croft, Table extraction using conditional random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860479]
• 14: Ariadna Quattoni , Sybor Wang , Louis-Philippe Morency , Michael Collins , Trevor Darrell, Hidden Conditional Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.10, p.1848-1852, October 2007 [doi>10.1109/TPAMI.2007.1124]
• 15: J. Suzuki and H. Isozaki. Semi-supervised sequential labeling and segmentation using giga-word scale unlabeled data. In Proceedings of the 46th Annual Meeting of the ACL: Human Language Technologies, pages 665--673, 2008.
• 16: Paul Viola , Mukund Narasimhan, Learning to extract information from semi-structured text using a discriminative context free grammar, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076091]
• 17: Tak-Lam Wong , Wai Lam , Tik-Shun Wong, An unsupervised framework for extracting and normalizing product attributes from multiple web sites, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390343]
• 18: David Yarowsky, Unsupervised word sense disambiguation rivaling supervised methods, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.189-196, June 26-30, 1995, Cambridge, Massachusetts [doi>10.3115/981658.981684]
• 19: C. Zhao, J. Mahmud, and I. Ramakrishnan. Exploiting structured reference data for unsupervised text segmentation with conditional random fields. In Proceedings of the SIAM International Conference on Data Mining, 2008.
• 20: Jun Zhu , Bo Zhang , Zaiqing Nie , Ji-Rong Wen , Hsiao-Wuen Hon, Webpage understanding: an integrated approach, 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.1281288]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation

Keywords:
conditional random fields, information extraction, metadata, semi-supervised learning