Learning with Lookahead: Can History-Based Models Rival Globally Optimized Models?

Proceedings of the Fifteenth Conference on Computational Natural Language Learning, pages 238–246, Portland, Oregon, USA, 23–24 June 2011. c⃝2011 Association for Computational Linguistics Learning with Lookahead: Can History-Based Models Rival Globally Optimized Models? Yoshimasa Tsuruoka†∗ Yusuke Miyao‡∗ Jun’ichi Kazama∗ † Japan Advanced Institute of Science and Technology (JAIST), Japan ‡ National Institute of Informatics (NII), Japan ∗ National Institute of Information and Communications Technology (NICT), Japan tsuruoka@jaist.ac.jp yusuke@nii.ac.jp kazama@nict.go.jp Abstract This paper shows that the performance of history-based models can be significantly im- proved by performing lookahead in the state space when making each classification deci- sion. Instead of simply using the best ac- tion output by the classifier, we determine the best action by looking into possible se- quences of future actions and evaluating the final states realized by those action sequences. We present a perceptron-based parameter op- timization method for this learning frame- work and show its convergence properties. The proposed framework is evaluated on part- of-speech tagging, chunking, named entity recognition and dependency parsing, using standard data sets and features. Experimental results demonstrate that history-based models with lookahead are as competitive as globally optimized models including conditional ran- dom fields (CRFs) and structured perceptrons. 1 Introduction History-based models have been a popular ap- proach in a variety of natural language process- ing (NLP) tasks including part-of-speech (POS) tag- ging, named entity recognition, and syntactic pars- ing (Ratnaparkhi, 1996; McCallum et al., 2000; Ya- mada and Matsumoto, 2003; Nivre et al., 2004). The idea is to decompose the complex structured prediction problem into a series of simple classifi- cation problems and use a machine learning-based classifier to make each decision using the informa- tion about the past decisions and partially completed structures as features. Although history-based models have many prac- tical merits, their accuracy is often surpassed by globally optimized models such as CRFs (Lafferty et al., 2001) and structured perceptrons (Collins, 2002), mainly due to the label bias problem. To- day, vanilla history-based models such as maximum entropy Markov models (MEMMs) are probably not the first choice for those who are looking for a ma- chine learning model that can deliver the state-of- the-art accuracy for their NLP task. Globally opti- mized models, by contrast, are gaining popularity in the community despite their relatively high compu- tational cost. In this paper, we argue that history-based mod- els are not something that should be left behind in research history, by demonstrating that their ac- curacy can be significantly improved by incorpo- rating a lookahead mechanism into their decision- making process. It should be emphasized that we use the word “lookahead” differently from some lit- erature on syntactic parsing in which lookahead sim- ply means looking at the succeeding words to choose the right parsing actions. In this paper, we use the word to refer to the process of choosing the best ac- tion by considering different sequences of future ac- tions and evaluating the structures realized by those sequences. In other words, we introduce a looka- head mechanism …

Content truncated to 500 words