Paper: Bidirectional Inference With The Easiest-First Strategy For Tagging Sequence Data

ACL ID H05-1059
Title Bidirectional Inference With The Easiest-First Strategy For Tagging Sequence Data
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2005
Authors
  • Yoshimasa Tsuruoka (CREST Japan Science and Technology Corporation, Saitama Japan; University of Tokyo, Tokyo Japan)
  • Jun'ichi Tsujii (University of Tokyo, Tokyo Japan; University of Manchester, Manchester UK; CREST Japan Science and Technology Corporation, Saitama Japan)

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 tha...