New ranking algorithms for parsing and tagging: kernels over discrete structures, and the voted perceptron

ABSTRACT

This paper introduces new learning algorithms for natural language processing based on the perceptron algorithm. We show how the algorithms can be efficiently applied to exponential sized representations of parse trees, such as the "all subtrees" (DOP) representation described by (Bod 1998), or a representation tracking all sub-fragments of a tagged sentence. We give experimental results showing significant improvements on two tasks: parsing Wall Street Journal text, and named-entity extraction from web data.

REFERENCES

• 1: Aizerman, M., Braverman, E., & Rozonoer, L. (1964). Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning. In Automation and Remote Control, 25:821--837.
• 2: Bod, R. (1998). Beyond Grammar: An Experience-Based Theory of Language. CSLI Publications/Cambridge University Press.
• 3: Rens Bod, What is the minimal set of fragments that achieves maximal parse accuracy?, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.66-73, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073022]
• 4: Borthwick, A., Sterling, J., Agichtein, E., and Grishman, R. (1998). Exploiting Diverse Knowledge Sources via Maximum Entropy in Named Entity Recognition. Proc. of the Sixth Workshop on Very Large Corpora.
• 5: Eugene Charniak, A maximum-entropy-inspired parser, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.132-139, April 29-May 04, 2000, Seattle, Washington
• 6: Michael John Collins , Mitchell P. Marcus, Head-driven statistical models for natural language parsing, 1999
• 7: Michael Collins, Discriminative Reranking for Natural Language Parsing, Proceedings of the Seventeenth International Conference on Machine Learning, p.175-182, June 29-July 02, 2000
• 8: Collins, M., and Duffy, N. (2001). Convolution Kernels for Natural Language. In Proceedings of Neural Information Processing Systems (NIPS 14).
• 9: Michael Collins, Ranking algorithms for named-entity extraction: boosting and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073165]
• 10: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 11: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 12: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062]
• 13: Yoav Freund , Raj D. Iyer , Robert E. Schapire , Yoram Singer, An Efficient Boosting Algorithm for Combining Preferences, Proceedings of the Fifteenth International Conference on Machine Learning, p.170-178, July 24-27, 1998
• 14: Goodman, J. (1996). Efficient algorithms for parsing the DOP model. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 143--152.
• 15: Haussler, D. (1999). Convolution Kernels on Discrete Structures. Technical report, University of Santa Cruz.
• 16: Mark Johnson , Stuart Geman , Stephen Canon , Zhiyi Chi , Stefan Riezler, Estimators for stochastic "Unification-Based" grammars, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.535-541, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034758]
• 17: Mark Johnson, Squibs and discussions: the DOP Estimation method is biased and inconsistent, Computational Linguistics, v.28 n.1, p.71-76, March 2002 [doi>10.1162/089120102317341783]
• 18: Lodhi, H., Christianini, N., Shawe-Taylor, J., & Watkins, C. (2001). Text Classification using String Kernels. In Advances in Neural Information Processing Systems 13, MIT Press.
• 19: Mitchell P. Marcus , Mary Ann Marcinkiewicz , Beatrice Santorini, Building a large annotated corpus of English: the penn treebank, Computational Linguistics, v.19 n.2, June 1993
• 20: Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In Proceedings of the empirical methods in natural language processing conference.
• 21: F. Rosenblatt, The perception: a probabilistic model for information storage and organization in the brain, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988