A constructive proof of the existence of Viterbi processes

2008/04/14 by J. Lember, A. Koloydenko
Mathematics · Computer Science · #math.ST #cs.IT #math.IT #math.PR #stat.CO #stat.ML #stat.TH

paper · pdf · doi:10.1109/tit.2010.2040897

published as IEEE Transactions on Information Theory, volume 56, issue 4, 2010, pages 2017 - 2033 · Submitted to the IEEE Transactions on Information Theory, focuses on the proofs of the results presented in arXiv:0709.2317, and arXiv:0803.2394

arxiv created 2008/04/14 · arxiv updated 2012/07/24

Abstract

Since the early days of digital communication, hidden Markov models (HMMs) have now been also routinely used in speech recognition, processing of natural languages, images, and in bioinformatics. In an HMM (X_i,Y_i)_{i≥ 1}, observations X₁,X₂,... are assumed to be conditionally independent given an ``explanatory'' Markov process Y₁,Y₂,..., which itself is not observed; moreover, the conditional distribution of X_i depends solely on Y_i. Central to the theory and applications of HMM is the Viterbi algorithm to find \em a maximum a posteriori (MAP) estimate q_1:n=(q₁,q₂,...,q_n) of Y_1:n given observed data x_1:n. Maximum \em a posteriori paths are also known as Viterbi paths or alignments. Recently, attempts have been made to study the behavior of Viterbi alignments when n→ ∞. Thus, it has been shown that in some special cases a well-defined limiting Viterbi alignment exists. While innovative, these attempts have relied on rather strong assumptions and involved proofs which are existential. This work proves the existence of infinite Viterbi alignments in a more constructive manner and for a very general class of HMMs.

Citations

• Adjusted Viterbi training for hidden Markov models
• The adjusted Viterbi training for hidden Markov models