Iterative Viterbi decoding

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[1..n], template t[1..m], // and distance matrix d[1..n,1..m] // remaining elements in matrices are solely for internal computations (int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) { // score, subsequence start, subsequence end declare int e, B, 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 := e/(E-B+1) until (e == e')

return (e, B, E) }

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.