A polynomial algorithm for HMM decoding with long-distance dependencies

A polynomial algorithm for HMM decoding with long-distance dependencies

Place: Large Lecture Room

In this talk, dynamic programming is represented as a Max-Flow/Min-Cut problem, for which polynomial algorithm exists. For a linear HMM topology, the relation between dynamic programming and Viterbi decoding allows also the HMM decoding problem to be stated as a Max-Flow/Min-Cut problem. In the basic form, the graph cut formulation is computationally more expensive than Viterbi decoding. Nevertheless, long-term constraints to the Viterbi/decoding-path can be introduced by adding edges to the graph, while still finding the optimal path in polynomial time. An experimental evaluation shows the advantages of long-term decoding constraints for handwritten text recognition.