HOME

TheInfoList



OR:

Iterative Viterbi decoding is an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
that spots the subsequence ''S'' of an observation ''O'' = having the highest average probability (i.e., probability scaled by the length of ''S'') of being generated by a given
hidden Markov model A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or ''hidden'') Markov process (referred to as X). An HMM requires that there be an observable process Y whose outcomes depend on the outcomes of X ...
''M'' with ''m'' states. The algorithm uses a modified
Viterbi algorithm The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events. This i ...
as an internal step. The scaled probability measure was first proposed by John S. Bridle. An early algorithm to solve this problem,
sliding window A sliding window protocol is a feature of packet-based data transmission Protocol (computing), protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the data link layer (OSI model#Laye ...
, was proposed by
Jay G. Wilpon Jays are a paraphyletic grouping of passerine birds within the family (biology), family Corvidae. Although the term "jay" folk taxonomy, carries no taxonomic weight, most or all of the birds referred to as jays share a few similarities: they ar ...
et al., 1989, with constant cost ''T'' = ''mn''2/2. A faster algorithm consists of an iteration of calls to the
Viterbi algorithm The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events. This i ...
, reestimating a filler score until convergence.


The algorithm

A basic (non-optimized) version, finding the sequence ''s'' with the smallest normalized distance from some subsequence of ''t'' is:
// input is placed in observation s ..n template t ..m
// and 
distance matrix In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the ''dist ...
d ..n,1..m// remaining elements in matrices are solely for internal computations (int, int, int) AverageSubmatchDistance(char s ..(n+1) char t ..(m+1) int d ..n,0..(m+1)
The ViterbiDistance() procedure returns the tuple (''e'', ''B'', ''E''), i.e., the Viterbi score "''e''" for the match of ''t'' and the selected entry (''B'') and exit (''E'') points from it. "''B''" and "''E''" have to be recorded using a simple modification to Viterbi. A modification that can be applied to CYK tables, proposed by Antoine Rozenknop, consists in subtracting ''e'' from all elements of the initial matrix ''d''.


References

* Silaghi, M., "Spotting Subsequences matching a HMM using the Average Observation Probability Criteria with application to Keyword Spotting", AAAI, 2005. * Rozenknop, Antoine, and Silaghi, Marius; "Algorithme de décodage de treillis selon le critère de coût moyen pour la reconnaissance de la parole", TALN 2001.


Further reading

* *{{cite journal, last1=Wang , first1=Qi , last2=Wei , first2=Lei , last3=Kennedy , first3=R.A. , title=Iterative Viterbi decoding, trellis shaping, and multilevel structure for high-rate parity-concatenated TCM , journal=IEEE Transactions on Communications , volume=50 , number=1 , date=January 2002 , pages=48–55 , issn=0090-6778 , doi=10.1109/26.975743 Error detection and correction Markov models