Iterative Viterbi decoding: Difference between revisions

Revision as of 04:44, 3 December 2004

Latest revision as of 13:00, 1 December 2020

(23 intermediate revisions by 17 users not shown)

Line 1:

'''Iterative Viterbi Decodingdecoding''' is an [[algorithm]] that spots the subsequence ''S'' of an observation ''O'' = {''o''₁, ..., ''o''_''n''} having the highest average probability (i.e., probability scaled by the length of ''S'') of being generated by a given Hidden[[hidden Markov Modelmodel]] ''M'' with ''m'' states. The algorithm uses a modified [[Viterbi algorithm]] as an internal step.

The scaled probability measure was first proposed by [[John S. Bridle]]. An early algorithm to solve this problem, [[sliding window]], was proposed by [[Jay G. Wilpon]] et. al., 1989, with constant cost ''T'' = ''mn''²/2.

A faster algorithm was developed by Silaghi in 1989 (published 1999). It consists of an iteration of calls to the [[Viterbi algorithm]], reestimating a filler score until convergence.

== The Algorithmalgorithm ==

A basic (non-optimized) version, looksfinding likethe sequence ''s'' with the smallest normalized distance from some subsequence of ''t'' is:

<pre>

(int,// int,input int)is SilaghiBridleDistance(charplaced in observation s[1..n], chartemplate t[1..m], int d[1..n,1..m]) {

// and [[distance declare intmatrix]] d'[1..n,01..(m+1)] //

// remaining elements in matrices are solely for internal computations

declare int s'[0..(n+1)] // these structures replicate the parameters and

(int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {

declare int t'[0..(m+1)] // are not normally needed as such

declare int e, B, E // score, subsequence start, subsequence end

declare int e, B, E

for j := 1 to m // initialize data structure (can be optimized out)

t'[j] := t[j]

for i := 1 to n

d'[i,j] := d[i,j]

for i := 1 to n do s'[i] := s'[i] := e

t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'

e := random()

do

e' := e
for i := 1 to n do d'[i,0] := d'[i,m+1] := e

(e, B, E) := ViterbiDistance(s', t', d')/(E-B+1)

e := e/(E-B+1)

until (convergence)

until (e == e')

return (e, B, E)

Line 32 ⟶ 30:

</pre>

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.

== History ==

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''.

The algorithm is the result of an insomnia, a couple of nights prior to an exam in July 1998 for a "Speech Recognition" class attended at EPFL (taught by Herve Bourlard). The idea came by contemplating an imaginary 3-dimensional drawing of the matrix used by dynamic programming in the Viterbi algorithm.

An extension for NLP was discovered by Antoine Rozenknop, during a presentation given by Silaghi at LIA (EPFL) in 2000.

== References ==

* Silaghi, M., "Spotting Subsequences matching a HMM using the Average Observation Probability Criteria with application to Keyword Spotting", AAAI, 2005.

* RosenknopRozenknop, Antoine,A and Silaghi,M. Marius; "Algorithme de decodagedécodage de treillis selon le criterecritère de coutcoût moyen pour la reconnaissance de la parole", TALN 2001.

==Further reading==

*{{cite conference |title=An Efficient Code Structure of Block Coded Modulations with Iterative Viterbi Decoding Algorithm |last1=Li |first1=Huan-Bang |last2=Kohno |first2=Ryuji |date=2006 |publisher=IEEE |___location=Valencia, Spain |conference=3rd International Symposium on Wireless Communication Systems |isbn=978-1-4244-0397-4 |doi=10.1109/ISWCS.2006.4362391}}

*{{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 }}

[[Category:Error detection and correction]]

* Silaghi,M.; "Optimizing normalized costs with Iterating Dynamic Programming", submitted to EJOR, 2000.

[[Category:Markov models]]

* Silaghi,M. and Bourlard,H.; "A new Keyword Spotting approach based on iterative dynamic programming", ICASSP 2000.

* Silaghi,M. and Berinde,V.; "A new optimization algorithm", in Journal of North University at Baia Mare, Romania, 1999.

* Rosenknop,A and Silaghi,M.; "Algorithme de decodage de treillis selon le critere de cout moyen pour la reconnaissance de la parole", TALN 2001.