Guided Learning for Bidirectional Sequence Classification

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 760–767, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Guided Learning for Bidirectional Sequence Classification Libin Shen BBN Technologies Cambridge, MA 02138, USA lshen@bbn.com Giorgio Satta Dept. of Inf. Eng’g. University of Padua I-35131 Padova, Italy satta@dei.unipd.it Aravind K. Joshi Department of CIS University of Pennsylvania Philadelphia, PA 19104, USA joshi@seas.upenn.edu Abstract In this paper, we propose guided learning, a new learning framework for bidirectional sequence classification. The tasks of learn- ing the order of inference and training the local classifier are dynamically incorporated into a single Perceptron like learning algo- rithm. We apply this novel learning algo- rithm to POS tagging. It obtains an error rate of 2.67% on the standard PTB test set, which represents 3.3% relative error reduction over the previous best result on the same data set, while using fewer features. 1 Introduction Many NLP tasks can be modeled as a sequence clas- sification problem, such as POS tagging, chunking, and incremental parsing. A traditional method to solve this problem is to decompose the whole task into a set of individual tasks for each token in the in- put sequence, and solve these small tasks in a fixed order, usually from left to right. In this way, the out- put of the previous small tasks can be used as the input of the later tasks. HMM and MaxEnt Markov Model are examples of this method. Lafferty et al. (2001) showed that this approach suffered from the so called label bias problem (Bot- tou, 1991). They proposed Conditional Random Fields (CRF) as a general solution for sequence clas- sification. CRF models a sequence as an undirected graph, which means that all the individual tasks are solved simultaneously. Taskar et al. (2003) improved the CRF method by employing the large margin method to separate the gold standard sequence la- beling from incorrect labellings. However, the com- plexity of quadratic programming for the large mar- gin approach prevented it from being used in large scale NLP tasks. Collins (2002) proposed a Perceptron like learn- ing algorithm to solve sequence classification in the traditional left-to-right order. This solution does not suffer from the label bias problem. Compared to the undirected methods, the Perceptron like algorithm is faster in training. In this paper, we will improve upon Collins’ algorithm by introducing a bidirec- tional searching strategy, so as to effectively utilize more context information at little extra cost. When a bidirectional strategy is used, the main problem is how to select the order of inference. Tsu- ruoka and Tsujii (2005) proposed the easiest-first ap- proach which greatly reduced the computation com- plexity of inference while maintaining the accuracy on labeling. However, the easiest-first approach only serves as a heuristic rule. The order of inference is not incorporated into the training of the MaxEnt clas- sifier for individual labeling. Here, we will propose a novel learning frame- work, namely guided learning, to integrate classifi- cation of individual …

Content truncated to 500 words