In this paper we propose 1-best A*, 1-best iterative A*, k-best A* and k-best iterative Viterbi A* algorithms for sequential decoding.

In particular, we show that iterative Viterbi A* decoding can be several times or orders of magnitude faster than the state-of-the-art algorithm for tagging tasks with a large number of labels.

3.1 l-Best Viterbi

The Viterbi algorithm is a classic dynamic programming based decoding algorithm.

Traditionally, the Viterbi algorithm ( Viterbi , 1967) is used.

Unfortunately, due to its 0(TL2) time complexity, where T is the input token size and L is the label size, the Viterbi decoding can become prohibitively slow when the label size is large (say, larger than 200).

The Viterbi algorithm cannot find the best sequences in tolerable

For tagging, learned constraints are directly used to constrain Viterbi decoding.

Dynamic programming techniques based on Markov assumptions, such as Viterbi decoding, cannot handle those ’nonlocal’ constraints as discussed above.

However, it is possible to constrain Viterbi

It can be learned from gold-segmented data, generally applies to languages with bound morphemes, and does not require a hand-compiled lexicon.3 Moreover, it has only four labels, so Viterbi decoding is very fast.

Incremental Greedy Decoding Decoding with the CRF—based tagger model in this setting requires some slight modifications to the Viterbi algorithm.

This forces the Viterbi path to go through If.