Iterative Viterbi decoding: Difference between revisions

Revision as of 12:09, 15 September 2005

Latest revision as of 13:00, 1 December 2020

(17 intermediate revisions by 13 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 Markov model]] ''M'' with ''m'' states. The algorithm uses a modified [[Viterbi algorithm]] as an internal step.

{{cleanup-technical}}

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.

'''Iterative Viterbi Decoding''' 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 Markov model]] M with m states. The algorithm uses a modified [[Viterbi algorithm]] as an internal step.

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

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 [[Marius C. Silaghi]] in 1998 (published 1999). It consists of an iteration of calls to the [[Viterbi algorithm]], reestimating a filler score until convergence.

== The algorithm ==

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 matrix]] d[1..n,1..m]

// the following structures replicate the parameters and

// remaining elements in matrices are solely for internal computations

// are not normally needed in an optimized implementation

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

declare int s'[0..(n+1)]

declare int t'[0..(m+1)]

// score, subsequence start, subsequence end

declare int e, B, E

// initialize copies of parameters (can be optimized out)

for j := 1 to m

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]

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

// now the algorithm

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 := e/(E-B+1)

until (convergencee == e')

return (e, B, E)

Line 40 ⟶ 30:

</pre>

The ViterbiDistance() procedure returns the tuple (''e'', ''B'', ''E''), i.e., the Viterbi score "''e''" for the keywordmatch 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''.

== History ==

== References ==

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 [[Hervé Bourlard]]). The idea came by contemplating an imaginary 3-dimensional drawing of the matrix used by dynamic programming in the Viterbi algorithm.

* 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 decodagedécodage de treillis selon le criterecritère de coutcoût moyen pour la reconnaissance de la parole", TALN 2001.

==Further reading==

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

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

== References ==

[[Category:Error detection and correction]]

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

[[Category:Markov models]]

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

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

* Rozenknop, Antoine, and Silaghi, Marius; "Algorithme de decodage de treillis selon le critere de cout moyen pour la reconnaissance de la parole", TALN 2001.