Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 467–474, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Bidirectional Inference with the Easiest-First Strategy for Tagging Sequence Data Yoshimasa Tsuruoka12 and Jun’ichi Tsujii231 1 CREST, JST (Japan Science and Technology Corporation) Honcho 4-1-8, Kawaguchi-shi, Saitama 332-0012 Japan 2 Department of Computer Science, University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033 Japan 3 School of Informatics, University of Manchester POBox 88, Sackville St, MANCHESTER M60 1QD, UK {tsuruoka,tsujii}@is.s.u-tokyo.ac.jp Abstract This paper presents a bidirectional in- ference algorithm for sequence label- ing problems such as part-of-speech tag- ging, named entity recognition and text chunking. The algorithm can enumerate all possible decomposition structures and find the highest probability sequence to- gether with the corresponding decomposi- tion structure in polynomial time. We also present an efficient decoding algorithm based on the easiest-first strategy, which gives comparably good performance to full bidirectional inference with signifi- cantly lower computational cost. Exper- imental results of part-of-speech tagging and text chunking show that the proposed bidirectional inference methods consis- tently outperform unidirectional inference methods and bidirectional MEMMs give comparable performance to that achieved by state-of-the-art learning algorithms in- cluding kernel support vector machines. 1 Introduction The task of labeling sequence data such as part-of- speech (POS) tagging, chunking (shallow parsing) and named entity recognition is one of the most im- portant tasks in natural language processing. Conditional random fields (CRFs) (Lafferty et al., 2001) have recently attracted much attention be- cause they are free from so-called label bias prob- lems which reportedly degrade the performance of sequential classification approaches like maximum entropy markov models (MEMMs). Although sequential classification approaches could suffer from label bias problems, they have sev- eral advantages over CRFs. One is the efficiency of training. CRFs need to perform dynamic pro- gramming over the whole sentence in order to com- pute feature expectations in each iteration of numer- ical optimization. Training, for instance, second- order CRFs using a rich set of features can require prohibitive computational resources. Max-margin methods for structured data share problems of com- putational cost (Altun et al., 2003). Another advantage is that one can employ a vari- ety of machine learning algorithms as the local clas- sifier. There is huge amount of work about devel- oping classification algorithms that have high gener- alization performance in the machine learning com- munity. Being able to incorporate such state-of-the- art machine learning algorithms is important. In- deed, sequential classification approaches with ker- nel support vector machines offer competitive per- formance in POS tagging and chunking (Gimenez and Marquez, 2003; Kudo and Matsumoto, 2001). One obvious way to improve the performance of sequential classification approaches is to enrich the information that the local classifiers can use. In stan- dard decomposition techniques, the local classifiers cannot use the information about future tags (e.g. the right-side tags in left-to-right decoding), which would be helpful in predicting the tag of the target word. To make use of the information about …

Content truncated to 500 words