Question classification using support vector machines

ABSTRACT

Question classification is very important for question answering. This paper presents our research work on automatic question classification through machine learning approaches. We have experimented with five machine learning algorithms: Nearest Neighbors (NN), Naive Bayes (NB), Decision Tree (DT), Sparse Network of Winnows (SNoW), and Support Vector Machines (SVM) using two kinds of features: bag-of-words and bag-of-ngrams. The experiment results show that with only surface text features the SVM outperforms the other four methods for this task. Further, we propose to use a special kernel function called the tree kernel to enable the SVM to take advantage of the syntactic structures of questions. We describe how the tree kernel can be computed efficiently by dynamic programming. The performance of our approach is promising, when tested on the questions from the TREC QA track.

REFERENCES

• 1: M. Collins and N. Duffy. Convolution Kernels for Natural Language. In Proceedings of Neural Information Processing Systems (NIPS14), 2001.
• 2: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 3: Andrew J. Carlson , Chad M. Cumby , Jeff L. Rosen , Dan Roth, SNoW User Guide, University of Illinois at Urbana-Champaign, Champaign, IL, 1999
• 4: Eugene Charniak, A Maximum-Entropy-Inspired Parser, Brown University, Providence, RI, 1999
• 5: Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 6: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 7: T. Gaertner, J. Lloyd, and P. Flach. Kernels for Structured Data. In Proceedings of the 12th International Conference on Inductive Logic Programming (ILP), July 2002.
• 8: D. Haussler. Convolution Kernels on Discrete Structures. Technical Report, University of Santa Cruz. 1999.
• 9: U. Hermjakob. Parsing and Question Classification for Question Answering. In Proceedings of the ACL Workshop on Open-Domain Question Answering, Toulouse, France, 2001.
• 10: E. Hovy, L. Gerber, U. Hermjakob, C. Lin, and D. Ravichandran. Towards Semantics-based Answer Pinpointing. In Proceedings of the DARPA Human Language Technology conference (HLT), San Diego, CA, 1999.
• 11: C. W. Hsu and C. J. Lin. A Comparison of Methods for Multi-class Support Vector Machines, IEEE Transactions on Neural Networks, 13, pp. 415--425, 2002.
• 12: Xin Li , Dan Roth, Learning question classifiers, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072378]
• 13: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 14: A. McCallum and K. Nigam. A Comparison of Event Models for Naive Bayes Text Classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 16: Dan Roth, Learning to resolve natural language ambiguities: a unified approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.806-813, July 1998, Madison, Wisconsin, United States
• 17: Dan Roth, Learning to resolve natural language ambiguities: a unified approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.806-813, July 1998, Madison, Wisconsin, United States
• 18: E. Voorhees. The TREC-8 Question Answering Track Report. In Proceedings of the 8th Text Retrieval Conference (TREC8), pp. 77--82, NIST, Gaithersburg, MD, 1999.
• 19: E. Voorhees. Overview of the TREC-9 Question Answering Track. In Proceedings of the 9th Text Retrieval Conference (TREC9), pp. 71--80, NIST, Gaithersburg, MD, 2000.
• 20: E. Voorhees. Overview of the TREC 2001 Question Answering Track. In Proceedings of the 10th Text Retrieval Conference (TREC10), pp. 157--165, NIST, Gaithersburg, MD, 2001.
• 21: C. Watkins. Dynamic Alignment Kernels. In A. J. Smola, P. L. Bartlett, B. Schlkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pp. 39--50, MIT Press, 2000.
• 22: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

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

General Terms:
Algorithms, Experimentation

Keywords:
kernel method, machine learning, question answering, support vector machine, text classification