Iterative Viterbi decoding

Iterative Viterbi Decoding is an algorithm that spots the subsequence S of an observation O={o1,...,on} 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.

The scaled probability measure was first proposed by Bridle. An early algorithm to solve this problem, sliding window, was proposed by Wilpon et.al., 1989, with constant cost T=mn^2/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 Algorithm

A basic (non-optimized) version looks like:

(int, int, int) SilaghiBridleDistance(char s[1..n], char t[1..m], int d[1..n,1..m]) {
    declare int d'[1..n,0..(m+1)]  //
    declare int s'[0..(n+1)]       // these structures replicate the parameters and
    declare int t'[0..(m+1)]       // are not normally needed as such
    declare int e, B, E  // score, subsequence start, subsequence end
    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
		for i := 1 to n	do	d'[i,0] := d'[i,m+1] := e
		(e, B, E)  := ViterbiDistance(s', t', d')/(E-B+1)
	until (convergence)

    return (e, B, E)
}

History

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.; "Optimizing normalized costs with Iterating Dynamic Programming", submitted to EJOR, 2000.
• 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.