Generic soft pattern models for definitional question answering

ABSTRACT

This paper explores probabilistic lexico-syntactic pattern matching, also known as soft pattern matching. While previous methods in soft pattern matching are ad hoc in computing the degree of match, we propose two formal matching models: one based on bigrams and the other on the Profile Hidden Markov Model (PHMM). Both models provide a theoretically sound method to model pattern matching as a probabilistic process that generates token sequences. We demonstrate the effectiveness of these models on definition sentence retrieval for definitional question answering. We show that both models significantly outperform state-of-the-art manually constructed patterns. A critical difference between the two models is that the PHMM technique handles language variations more effectively but requires more training data to converge. We believe that both models can be extended to other areas where lexico-syntactic pattern matching can be applied.

REFERENCES

• 1: S. Blair-Goldensohn, K.R. McKeown and A. Hazen Schlaikjer, A Hybrid Approach for QA Track Definitional Questions, Proc. of TREC 2003, 2003, pp. 336--343.
• 2: Hang Cui , Min-Yen Kan , Tat-Seng Chua, Unsupervised learning of soft patterns for generating definitions from online news, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988686]
• 3: H. Cui, M.-Y. Kan, T.-S. Chua and J. Xiao, A Comparative Study on Sentence Retrieval for Definitional Question Answering, SIGIR Workshop on Information Retrieval for Question Answering (IR4QA), Sheffield, U.K., 2004.
• 4: A.P. Dempster, N.M. Laird and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society, 39:1--38, 1977.
• 5: S. Harabagiu, D. Moldovan, C. Clark, M. Bowden, J. Williams and J. Bensley, Answer Mining by Combining Extraction Techniques with Abductive Reasoning, Proc. of TREC 2003, 2003.
• 6: W. Hildebrandt, B. Katz and J. Lin, Answering Definition Questions with Multiple Knowledge Sources, Proc. of HLT/NAACL 2004, Boston, MA, 2004, pp. 49--56.
• 7: F. Jelinek and R. L. Mercer, Interpolated estimation of markov source parameters from sparse data, Proc. of the Workshop Pattern Recognition in Practice, Amsterdam, Holland, 1980, pp. 381--397.
• 8: A. Krogh, M. Brown, I.S. Mian K. Sjolander and D. Haussler, Hidden Markov Models in Computational Biology - Applications to Protein Modeling, J. Mol. Biol. (1994) 235, pp. 1501--1531.
• 9: Chin-Yew Lin , Eduard Hovy, Automatic evaluation of summaries using N-gram co-occurrence statistics, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.71-78, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073465]
• 10: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 11: I. Muslea, Extraction patterns for information extraction tasks: A survey, Proc. of AAAI-99 Workshop on Machine Learning for Information Extraction, 1999, pp.1--6.
• 12: Deepak Ravichandran , Eduard Hovy, Learning surface text patterns for a Question Answering system, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073092]
• 13: Ellen Riloff , Janyce Wiebe, Learning extraction patterns for subjective expressions, Proceedings of the 2003 conference on Empirical methods in natural language processing, p.105-112, July 11, 2003 [doi>10.3115/1119355.1119369]
• 14: R. Rosenfeld, Two decades of statistical language modeling: Where do we go from here, Proc. of the IEEE, 88, August, 2000, pp. 1270--1278.
• 15: M. Skounakis, M. Craven, and S. Ray, Hierarchical hidden markov models for information extraction, Proc. of IJCAI '03, 2003.
• 16: E.M.Voorhees, Overview of the TREC 2003 question answering track, Proc. of TREC 2003, 2003.
• 17: E.M. Voorhees, Overview of the TREC 2004 question answering track, Proc. of TREC 2004, 2004.
• 18: J. Xiao, T.-S. Chua and H. Cui, Cascading Use of Soft and Hard Matching Pattern Rules for Weakly Supervised Information Extraction, Proc. of COLING '04, Geneva, Switzerland, 2004, pp.542--548.
• 19: Jinxi Xu , Ralph Weischedel , Ana Licuanan, Evaluation of an extraction-based approach to answering definitional questions, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009064]
• 20: H. Yang, H. Cui, M.-Y. Kan, M. Maslennikov, L. Qiu and T.-S. Chua, QUALIFIER in TREC 12 QA Main Task, Proc. of TREC 2003, 2003, pp. 54--63.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing

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

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
definitional question answering, probabilistic models, soft pattern