Infinite Viterbi alignments in the two state hidden Markov models

zbMATH Open1166.62062arXiv0711.0928MaRDI QIDQ3626352FDOQ3626352

Authors: Alexey Koloydenko, J. Lember 

Publication date: 22 May 2009

Abstract: Since the early days of digital communication, Hidden Markov Models (HMMs) have now been routinely used in speech recognition, processing of natural languages, images, and in bioinformatics. An HMM $(X_i,Y_i{)}_{ige1}$ assumes observations $X_1,X_2,\mathrm{...}$ to be conditionally independent given an "explanotary" Markov process $Y_1,Y_2,\mathrm{...}$, 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} estimate $q_{1:n}=(q_1,q_2,\mathrm{...},q_n)$ of $Y_{1:n}$ given the observed data $x_{1:n}$. Maximum {em a posteriori} paths are also called Viterbi paths or alignments. Recently, attempts have been made to study the behavior of Viterbi alignments of HMMs with two hidden states when $n$ tends to infinity. It has indeed been shown that in some special cases a well-defined limiting Viterbi alignment exists. While innovative, these attempts have relied on rather strong assumptions. This work proves the existence of infinite Viterbi alignments for virtually any HMM with two hidden states.

Full work available at URL: https://arxiv.org/abs/0711.0928

Recommendations

• Existence of infinite Viterbi path for pairwise Markov models
• Asymptotic risks of Viterbi segmentation
• Properties of the maximum a posteriori path estimator in hidden Markov models
• scientific article; zbMATH DE number 1099037
• Robustifying the Viterbi algorithm

zbMATH Keywords

Viterbi extractionViterbi trainingmaximum a posteriori path

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Inference from stochastic processes (62M99)

Cited In (11)

• Viterbi sequences and polytopes
• On the Viterbi process with continuous state space
• The infinite viterbi alignment and decay-convexity
• A coarse-to-fine approach to computing the \(k\)-best Viterbi paths
• Regenerativity of Viterbi process for pairwise Markov models
• Viterbi algorithms for hidden Markov models with partially visible states
• Existence of infinite Viterbi path for pairwise Markov models
• On the accuracy of the MAP inference in HMMs
• Generalized Baum-Welch and Viterbi algorithms based on the direct dependency among observations
• Asymptotic risks of Viterbi segmentation
• The adjusted Viterbi training for hidden Markov models

This page was built for publication: Infinite Viterbi alignments in the two state hidden Markov models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3626352)