Iterative Viterbi A* Algorithm for K-Best Sequential Decoding
Zhiheng Huang, Yi Chang, Bo Long, Jean-François Crespo, Anlei Dong, Sathiya Keerthi, Su-Lin Wu · 2012
Sequential modeling has been widely used in a variety of important applications including named entity recognition and shallow parsing. However, as more and more real time large-scale tagging applications arise, decoding speed has become a bottleneck for existing sequential tagging algorithms. 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. We show the efficiency of these proposed algorithms for five NLP tagging tasks. 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. This algorithm makes real-time large-scale tagging applications with thousands of labels feasible.