|
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<sup>2</sup>/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)
</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 ==
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.
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
* Silaghi, Marius; "Optimizing normalized costs with Iterating Dynamic Programming", submitted to EJOR, 2000.
* 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.
| 