Data-Defined Kernels for Parse Reranking Derived from Probabilistic Models

Proceedings of the 43rd Annual Meeting of the ACL, pages 181–188, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Data-Defined Kernels for Parse Reranking Derived from Probabilistic Models James Henderson School of Informatics University of Edinburgh 2 Buccleuch Place Edinburgh EH8 9LW, United Kingdom james.henderson@ed.ac.uk Ivan Titov Department of Computer Science University of Geneva 24, rue G´en´eral Dufour CH-1211 Gen`eve 4, Switzerland ivan.titov@cui.unige.ch Abstract Previous research applying kernel meth- ods to natural language parsing have fo- cussed on proposing kernels over parse trees, which are hand-crafted based on do- main knowledge and computational con- siderations. In this paper we propose a method for defining kernels in terms of a probabilistic model of parsing. This model is then trained, so that the param- eters of the probabilistic model reflect the generalizations in the training data. The method we propose then uses these trained parameters to define a kernel for rerank- ing parse trees. In experiments, we use a neural network based statistical parser as the probabilistic model, and use the resulting kernel with the Voted Percep- tron algorithm to rerank the top 20 parses from the probabilistic model. This method achieves a significant improvement over the accuracy of the probabilistic model. 1 Introduction Kernel methods have been shown to be very ef- fective in many machine learning problems. They have the advantage that learning can try to optimize measures related directly to expected testing perfor- mance (i.e. “large margin” methods), rather than the probabilistic measures used in statistical models, which are only indirectly related to expected test- ing performance. Work on kernel methods in natural language has focussed on the definition of appropri- ate kernels for natural language tasks. In particu- lar, most of the work on parsing with kernel meth- ods has focussed on kernels over parse trees (Collins and Duffy, 2002; Shen and Joshi, 2003; Shen et al., 2003; Collins and Roark, 2004). These kernels have all been hand-crafted to try reflect properties of parse trees which are relevant to discriminating correct parse trees from incorrect ones, while at the same time maintaining the tractability of learning. Some work in machine learning has taken an al- ternative approach to defining kernels, where the kernel is derived from a probabilistic model of the task (Jaakkola and Haussler, 1998; Tsuda et al., 2002). This way of defining kernels has two ad- vantages. First, linguistic knowledge about parsing is reflected in the design of the probabilistic model, not directly in the kernel. Designing probabilistic models to reflect linguistic knowledge is a process which is currently well understood, both in terms of reflecting generalizations and controlling computa- tional cost. Because many NLP problems are un- bounded in size and complexity, it is hard to specify all possible relevant kernel features without having so many features that the computations become in- tractable and/or the data becomes too sparse.1 Sec- ond, the kernel is defined using the trained param- eters of the probabilistic model. Thus the kernel is in part determined by the training …

Content truncated to 500 words