Soft pattern matching models for definitional question answering

ABSTRACT

We explore probabilistic lexico-syntactic pattern matching, also known as soft pattern matching, in a definitional question answering system. Most current systems use regular expression-based hard matching patterns to identify definition sentences. Such rigid surface matching often fares poorly when faced with language variations. We propose two soft matching models to address this problem: 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 the models on definition sentence retrieval for definitional question answering. We show that both models significantly outperform the state-of-the-art manually constructed hard matching patterns on recent TREC data.

A critical difference between the two models is that the PHMM has a more complex topology. We experimentally show that the PHMM can handle language variations more effectively but requires more training data to converge.

While we evaluate soft pattern models only on definitional question answering, we believe that both models are generic and can be extended to other areas where lexico-syntactic pattern matching can be applied.

REFERENCES

• 1: Eugene Agichtein , Luis Gravano, Snowball: extracting relations from large plain-text collections, Proceedings of the fifth ACM conference on Digital libraries, p.85-94, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336644]
• 2: Ahn, D., Jijkoun, V., Mishne, G., &Muml;uller, K., de Rijke, M., and Schlobach, S. 2004. Using Wikipedia at the TREC QA Track. In Proceedings of TREC.
• 3: Blair-Goldensohn, S., McKeown, K., and Schlaikjer, A. H. 2003. A hybrid approach for QA track definitional questions. In Proceedings of TREC. 185--192.
• 4: Blair-Goldensohn, S., McKeown, K., and Schlaikjer, A. H. 2004. Answering definitional questions: A hybrid approach. In New Directions in Question Answering. 47--58.
• 5: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, ACM SIGMOD Record, v.30 n.2, p.175-186, June 2001
• 6: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 7: Chu-Carroll, J., Czuba, K., Prager, J., Ittycheriah, A., and Blair-Goldensohn, S. 2004. IBM's PIQUANT II in TREC 2004. In Proceedings of TREC.
• 8: 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]
• 9: Hang Cui , Min-Yen Kan , Tat-Seng Chua, Generic soft pattern models for definitional question answering, 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.1076101]
• 10: Cui, H., Kan, M.-Y., Chua, T.-S., and Xiao, J. 2004b. A comparative study on sentence retrieval for definitional question answering. In Proceedings of SIGIR 2005 Workshop IR4QA: Information Retrieval for Question Answering.
• 11: Dempster, A., Laird, N., and Rubin, D. 1977. Maximum likelihood from incomplete data via the EM algorithm (with discussion). J. Roy. Statist. Soc. 39, 1--38.
• 12: Oren Etzioni , Michael Cafarella , Doug Downey , Stanley Kok , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988687]
• 13: Gaizauskas, R., Greenwood, M. A., Hepple, M., Roberts, I., and Saggion, H. 2004. The University of Sheffields TREC 2004 Q&A experiments. In Proceedings of TREC.
• 14: Han, K.-S., Chung, H., Kim, S.-B., Song, Y.-I., Lee, J.-Y., and Rim, H.-C. 2004. Korea University Question Answering System at TREC 2004. In Proceedings of TREC.
• 15: Harabagiu, S. M., Moldovan, D. I., Clark, C., Bowden, M., Hickl, A., and Wang, P. 2005. Employing two question answering systems in TREC-2005. In Proceedings of TREC.
• 16: Harabagiu, S. M., Moldovan, D. I., Clark, C., Bowden, M., Williams, J., and Bensley, J. 2003. Answer mining by combining extraction techniques with abductive reasoning. In Proceedings of TREC. 375--382.
• 17: Harabagiu, S. M., Moldovan, D. I., Pasca, M., Mihalcea, R., Surdeanu, M., Bunescu, R. C., Girju, R., Rus, V., and Morarescu, P. 2000. FALCON: Boosting knowledge for answer engines. In Proceedings of TREC.
• 18: Hildebrandt, W., Katz, B., and Lin, J. J. 2004. Answering definition questions with multiple knowledge sources. In Proceedings of HLT-NAACL. 49--56.
• 19: Hongyan Jing, Sentence reduction for automatic text summarization, Proceedings of the sixth conference on Applied natural language processing, p.310-315, April 29-May 04, 2000, Seattle, Washington [doi>10.3115/974147.974190]
• 20: Katz, B., Bilotti, M., Felshin, S., Fernandes, A., Hildebrandt, W., Katzir, R., Lin, J., Loreto, D., Marton, G., Mora, F., and Uzuner, O. 2004. Answering multiple questions on a topic from heterogeneous resources. In Proceedings of TREC.
• 21: Judith L. Klavans , Smaranda Muresan, Evaluation of DEFINDER: a system to mine definitions from consumer-oriented medical text, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.201-202, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379488]
• 22: Lannon, J. M. 1991. Technical Writing. HarperCollins, New York, NY.
• 23: 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]
• 24: Jimmy Lin , Dina Demner-Fushman, Automatically evaluating answers to definition questions, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.931-938, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220692]
• 25: Jimmy Lin , Dina Demner-Fushman, Will pyramids built of nuggets topple over?, Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, p.383-390, June 04-09, 2006, New York, New York [doi>10.3115/1220835.1220884]
• 26: Bing Liu , Chee Wee Chin , Hwee Tou Ng, Mining topic-specific concepts and definitions on the web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775188]
• 27: Inderjeet Mani , James Pustejovsky , Beth Sundheim, Introduction to the special issue on temporal information processing, ACM Transactions on Asian Language Information Processing (TALIP), v.3 n.1, p.1-10, March 2004 [doi>10.1145/1017068.1017069]
• 28: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 29: McCallum, A. 2003. Efficiently inducing features of conditional random fields. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI03).
• 30: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 31: Smaranda Muresan , Samuel D. Popper , Peter T. Davis , Judith L. Klavans, Building a terminological database from heterogeneous definitional sources, Proceedings of the 2003 annual national conference on Digital government research, p.1-4, May 18-21, 2003, Boston, MA
• 32: Muslea, I. 1999. Extraction patterns for information extraction tasks: A survey. In Proceedings of the AAAI-99 Workshop on Machine Learning for Information Extraction. 1--6.
• 33: Fuchun Peng , Ralph Weischedel , Ana Licuanan , Jinxi Xu, Combining deep linguistics analysis and surface pattern learning: a hybrid approach to Chinese definitional question answering, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.307-314, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220614]
• 34: John Prager , Dragomir Radev , Krzysztof Czuba, Answering what-is questions by Virtual Annotation, Proceedings of the first international conference on Human language technology research, p.1-5, March 18-21, 2001, San Diego [doi>10.3115/1072133.1072139]
• 35: Prager, J. M., Chu-Carroll, J., Czuba, K., Welty, C. A., Ittycheriah, A., and Mahindru, R. 2003. IBM's PIQUANT in TREC2003. In Proceedings of TREC. 283--292.
• 36: Dragomir R. Radev , Hongyan Jing , Małgorzata Styś , Daniel Tam, Centroid-based summarization of multiple documents, Information Processing and Management: an International Journal, v.40 n.6, p.919-938, November 2004 [doi>10.1016/j.ipm.2003.10.006]
• 37: 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]
• 38: 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]
• 39: Rosenfeld, R. 2000. Two decades of statistical language modeling: Where do we go from here. Proc. the IEEE 88, 8.
• 40: Barry Schiffman , Inderjeet Mani , Kristian J. Concepcion, Producing biographical summaries: combining linguistic knowledge with corpus statistics, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.458-465, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073071]
• 41: Schwartz, A. S. and Hearst, M. A. 2003. A simple algorithm for identifying abbreviation definitions in biomedical text. In Proceedings of Pacific Symposium on Biocomputing. 451--462.
• 42: Skounakis, M., Craven, M., and Ray, S. 2003. Hierarchical Hidden Markov Models for information extraction. In Proceedings of 18th International Joint Conference on Artificial Intelligence. 427--433.
• 43: Kiyoshi Sudo , Satoshi Sekine , Ralph Grishman, An improved extraction pattern representation model for automatic IE pattern acquisition, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.224-231, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075096.1075125]
• 44: Voorhees, E. M. 2001. Overview of the TREC 2001 Question Answering Track. In Proceedings of TREC.
• 45: Ellen M. Voorhees, Evaluating answers to definition questions, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology: companion volume of the Proceedings of HLT-NAACL 2003--short papers, p.109-111, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073483.1073520]
• 46: Voorhees, E. M. 2003b. Overview of the TREC 2003 Question Answering Track. In Proceedings of TREC. 54--68.
• 47: Voorhees, E. M. 2004. Overview of the TREC 2004 Question Answering Track. In Proceedings of TREC.
• 48: Jing Xiao , Tat-Seng Chua , Hang Cui, Cascading use of soft and hard matching pattern rules for weakly supervised information extraction, Proceedings of the 20th international conference on Computational Linguistics, p.542-es, August 23-27, 2004, Geneva, Switzerland [doi>10.3115/1220355.1220433]
• 49: Xu, J., Licuanan, A., and Weischedel, R. M. 2003. TREC 2003 QA at BBN: Answering definitional questions. In Proceedings of TREC. 98--106.
• 50: 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]
• 51: Yang, H., Cui, H., Maslennikov, M., Qiu, L., Kan, M.-Y., and Chua, T.-S. 2003. QUALIFIER In TREC-12 QA main task. In Proceedings of TREC. 480--488.
• 52: Zahariev, M. 2003. Efficient acronym-expansion matching for automatic acronym acquisition. In Proceedings of IKE. 32--37.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Experimentation

Keywords:
Soft patterns, definitional question answering