Iterative Viterbi decoding

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.

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.

A faster algorithm was developed by 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 looks like:

(int, int, int) SilaghiBridleDistance(char s[1..n], char t[1..m], int d[1..n,1..m]) {
    // the following structures replicate the parameters and
    // are not normally needed in an optimized implementation
    declare 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
		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.