Efficient Staggered Decoding for Sequence Labeling

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 485–494, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Efficient Staggered Decoding for Sequence Labeling Nobuhiro Kaji Yasuhiro Fujiwara Naoki Yoshinaga Masaru Kitsuregawa Institute of Industrial Science, The University of Tokyo, 4-6-1, Komaba, Meguro-ku, Tokyo, 153-8505 Japan {kaji,fujiwara,ynaga,kisture}@tkl.iis.u-tokyo.ac.jp Abstract The Viterbi algorithm is the conventional decoding algorithm most widely adopted for sequence labeling. Viterbi decoding is, however, prohibitively slow when the label set is large, because its time com- plexity is quadratic in the number of la- bels. This paper proposes an exact decod- ing algorithm that overcomes this prob- lem. A novel property of our algorithm is that it efficiently reduces the labels to be decoded, while still allowing us to check the optimality of the solution. Experi- ments on three tasks (POS tagging, joint POS tagging and chunking, and supertag- ging) show that the new algorithm is sev- eral orders of magnitude faster than the basic Viterbi and a state-of-the-art algo- rithm, CARPEDIEM (Esposito and Radi- cioni, 2009). 1 Introduction In the past decade, sequence labeling algorithms such as HMMs, CRFs, and Collins’ perceptrons have been extensively studied in the field of NLP (Rabiner, 1989; Lafferty et al., 2001; Collins, 2002). Now they are indispensable in a wide range of NLP tasks including chunking, POS tagging, NER and so on (Sha and Pereira, 2003; Tsuruoka and Tsujii, 2005; Lin and Wu, 2009). One important task in sequence labeling is how to find the most probable label sequence from among all possible ones. This task, referred to as decoding, is usually carried out using the Viterbi algorithm (Viterbi, 1967). The Viterbi algorithm has O(NL2) time complexity,1 where N is the input size and L is the number of labels. Al- though the Viterbi algorithm is generally efficient, 1The first-order Markov assumption is made throughout this paper, although our algorithm is applicable to higher- order Markov models as well. it becomes prohibitively slow when dealing with a large number of labels, since its computational cost is quadratic in L (Dietterich et al., 2008). Unfortunately, several sequence-labeling prob- lems in NLP involve a large number of labels. For example, there are more than 40 and 2000 labels in POS tagging and supertagging, respectively (Brants, 2000; Matsuzaki et al., 2007). These tasks incur much higher computational costs than simpler tasks like NP chunking. What is worse, the number of labels grows drastically if we jointly perform multiple tasks. As we shall see later, we need over 300 labels to reduce joint POS tag- ging and chunking into the single sequence label- ing problem. Although joint learning has attracted much attention in recent years, how to perform de- coding efficiently still remains an open problem. In this paper, we present a new decoding algo- rithm that overcomes this problem. The proposed algorithm has three distinguishing properties: (1) It is much more efficient than the Viterbi algorithm when dealing with a large number of labels. (2) It is an …

Content truncated to 500 words