--- title: "A Recognition Method of Connected Spoken Words With Syntactical Constraints by Augmented Continuous DP Algorithm" authors: - "Sei-ichi Nakagawa" doi: "" url: "https://ijcai.org/proceedings/1983/152" pdf: "https://ijcai.org/proceedings/1983/0152.pdf" venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence" year: 1983 pages: "639-641" track: "Natural Language" keywords: --- # A Recognition Method of Connected Spoken Words With Syntactical Constraints by Augmented Continuous DP Algorithm Sei-ichi Nakagawa *Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 639-641. ## Abstract The technique of dy namic time warping by using dynamic programming is powerful for isolated word recognition. An augmented continuous dynamic programming algorithm is proposed for connected spoken word recognition with syntactical constraints, The algorithm is based on the same principle of two level DP and level building DP. Although our algorithm obtains a near optimal solution for the recognition principle based on pattern matching, it is computationaly more efficient than the conventional methods and also does not require many memory storages. Therefore it is useful for connected word recognition with syntactical constraints in a large vocabulary. The amount of computation is almost the same as that for isolated word recognition . ## Full text ## A RECOGNITION METHOD OF CONNECTED SPOKEN WORDS WITH SYNTACTICAL CONSTRAINTS ## BY AUGMENTED CONTINUOUS DP ALGORITHM ## Sei-ichi Nakagawa Dept. Informa. & Comp. Sci., Toyohashi University of Technology Toyohashi, 440 Japan of connected word recognition. Although t hi s method is an approximate solution for the recognition principle based on p~ttern matching, this requires less computat ion t hRn others. Therefore it is useful for connected word recognition with s yntactical constraints in a l arge vocabulary. ## II FOR¥..ALIZATION OF CONNECTED SPOKEN WORD RECOGNITION BY PATTE~~ MATCHING ## 2.1 Notation n n-th word N Number of words, vocabulary size. X Number of words in a test pattern. Jn Length (in frames) of the reference pattern for the n-th word . Reference pattern for the n-th word. n n n n R ; b 1 b 2 ·.· b 1 n I Length of a test pattern. T Test pattern, T; a 1 a 2 ··· ai Dx(i) Minimum cumulative distanc~, whenJa 1 a 2 ··· ai is matched with any concatenation of x reference patterns. dn(i,j) : Local distance between a. and b~ Last reference word in the concatenation of references to satisfy D (i). Beginning point in the ~est pattern for N (i) minus 1. X Minimum cumulative distance between a at agd the n-th reference pattern b~ ~~·:: ·· b 1 n min ( D ~(m) +minimum cumulative d m xd bn 1stance etween am+l ··· a. an 1 b~) 1 J ## 2.2 Formalization of Connected Word Recognition Principle Let us consider the connected spoken word recognition problem such that it is tgcffndnt2r se~uynce of reference patterns, R ; R R Rn x of length x which best matches (minimum cumulative distance) the test pattern T, over all possible concatenation of x reference patterns. If the number of words in the test pattern is not known, the minimization should be performed over all length x. The basic procedure for finding R is to solve a time alignment problem between T and R using a dynamic time warping method (DP matching). Therefore we should use an asynmetric DP pass to apply dynamic programming for connect ed word recognition[2]. Fig.l shows various types of asynmetric DP passes. In this paper, we use the type (a) to ## ABSTRACT The technique of dynamic time warping by using dynamic programming is powerful for isolated word recognition. An augmented continuous dynamic programming algorithm is proposed for connected spoken word recognition with syntactical constraints, The algorithm is based on the same principle of two level DP and level building DP. Although our algorithm obtains a near optimal solution for the recognition principle based on pattern matching, it is computationaly more efficient than the conventional methods and also does not require many memory storages. Therefore it is useful for connected word recognition with syntactical constraints in a large vocabulary. The amount of computation is almost the same as that for isolated word recognition . ## I INTRODUCTION The technique of dynamic time warping by using dynamic programming is powerful for isolated word recognition. Vintsyuk proposed a connected spoken word recognition method based on this principle in 1971 [1]. In 1975, Sakoe also proposed independently another algorithm from a . view point of pattern matching (called Two Level DP matching; TLD~)[2]. Recently, Myers and Rabiner have presented a new DTW-based connected word recognition algorithm, called Level Building DP matching (LB)[3]. This algorithm produces the same result as TLDP except for the difference of the matching window. This is less cpmputation , but not a real time oriented algorithm. Therefore, Sakoe and Watari led a new real time oriented algorithm by changing the computation order of LB ( called Clock-Wise DP matching; CWDP) [4]. T4is uses far less computation, but more memory storages. In last year, the author proposed two new algorithms based on the same principle as described above[S]. One is the Constant Time Delay DP matching (CTDP). This algorithm is the extention of TLDP, that is, executes the computation at every constant time delay (W frames) instead of every frame. Thus, the computation of local distance reduces a factor of 4 ~ 6. The another is O(n) DP matching. The total amount of computation is the same as that of isolated spoken word recognition by DP matching, that is, a factor of R (width of matching window) for TLDP, However, this O(n) DP matching cannot be applied to connected word recognition with. syntactical constraints. In this paper, He des<:ribe a new type method explain simply the algorithm. The princi~le described above is defined as follows. Let d (i,j) and u(i) represent the local distance between a. and j-th frame in R (concatenation of feferences) and a time warping function, respectively. The optimal concatenation of references is ~ such that test pattern ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000000_ef33409576350241ada5f01b2f5df2743de750427953239659e24459caaa0c50.png) Fig.l Asynmetric DP pass and weight ## 2.3 Recursive Formula for Solution The problem is solved equation by the following DP Dn(m+l:i) is calculated by the following equation. After repeating-DP equation (2) over l~i~I, the recognition result is decided by the flaw-in Fig.2. Fig.2 Decision process of recognition r esult (known length of string) ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000001_01dcf0c7841c046e93f3c26da150239e1f2e450e3fe90140650aae1f25b383bb.png) ## III FORMALIZATION OF CONNECTED SPOKEN WORD RECOGNITION WITH SYNTACTICAL CONSTRAINTS ## 3.1 Notation As a syntax control mechanism, the following finite state automaton a is introduced. - a = <S,Z::,ll,q 0 ,F> S A set of states, {q 0 , q 1 , ··· qlsl-l} - Z:: A set of input words, {n} - 1'1 A set of state transition rules, sxz::~s, that is,{ll (q. ,n)=q.} An initial st~te qo : F : A set of final states, FCS - D (i) q Minimum cumulative distance, when a 1 a 2 .·. a. is matched with any concatenation or v~rious reference patterns which reaches at state q. - N (i) q Last reference word in the concatenation of references to satisfy D (i). - B (i) q Beginning point in the ~est pattern for N ( i) minus 1. - Q (i) q S~ate which satisfies D (i) by state transition to q, that i~, li(Q (i), N (i)) = q q q ## 3. 2 Formalization of Connected l~ord Recognition Principle with Syntactical Constraints Let a test pattern T be a spoken sentence produced by the regular grammar equivalent to finite state automaton a . A syntax control is introduced into the minimization problem (equation (1)), so that the word sequence {n(l) n(2) ··· n(x} is accepted by automaton a .. A sentence {n(l) n(2) ··. n(x)} is said to be accepted by a if ll(q 0 ,n(l))=q.CS, ll (q.,n(2))=q.cS, ··. ll(qk,n(x-l))=q cS, ll(q ,n(x))=qfcF. In ori\er words, ~t is requi~ed thatgan over all state transition sequence caused by input word sequence {n(l), ··· n(x)} should start at an initial state q 0 and terminate at a final state in F. ## :: .· 3 Recursive Formula for Solution In order to realize this control, the DP equation (2) is modified as follows. The role of the index in the equation was no more than to count the word number in the word sequence. Equation (2) is searched for the optimal input word n and optimal time transition m+i along with coupting up the number x by one. Thus, if we reread (or rewrite) x to q, we can search for the optimal input word n and optimal time transitio m+i along optimal state transition qk~q. The formula are given in the following. Fig. 3 Decision process of recognition result. (with syntactic constraints) ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000002_263b71d0ee5c52ffa5fd04486f0f593de86321398f9216eaf4a643fe02a1be7b.png) After repeating DP equation (4) over l~i~I, the recognition result is decided by the flaw-in Fig.3 . ## IV AUGMENTED CONTINUOUS DYNAMIC PROGRAMMING ALGORITHM 4.1 Notation on(i,j) : min (minimum cumulative distance between a am+l ··· a. and b 1 b 2 ··· b.), where m n n n tWe base axis~for an asynmetricJDP pass is the reference' axis (see Fig.4). Br(i,j) : argmin (minimum cumulative distance between a am+l ··· a. and b 1 b 2 ··· b.) m n n m n DP(i,j,k): k-th-minm(m~n~mum cuffiulative d~stanceJ - between a amtl ··· a. and b 1 b 2 ··· b.) Br(i,j,k): arg-k-th-illin tminimum~cumulaEive J distance ~etween a am+~ ··· a. and bn n n m .~ 1 b 2 ··· b.). Where arg- -th-m~n f(m) means m ~uch that f(m) is th~ k-th minimum of f(m) for all m. n n n Let v(k) and Fig.4(a) be a time warping function and the DP pass, respectively. DP(i,j) is defined as follows ·. test pattern Fig.4 Asynmetric DP pass and weight ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000003_6c2584c2dc07cffb82a36d9d82e6b3a88d528e9d4527870031f84cdd48fb04cf.png) ## 4.2 Word Spotting Algorithm For speech understanding systems, the problem of detecting and locating a specific word in continuous speech has been considered by using a nonlinear time warping procedure (DP matching)[6,7]. This problem is referred to as the word spotting problem. If we can calculate D?(i,Jn) for any i-th frame in the test pattern and any n-th reference pattern, the word spotting problem would be solved. That is, if D?(i,Jn) satisfies the threshold for word detection, the location could be regarded as B?(i,Jn) - i in the test pattern. D?(i,Jn) and B?(i,Jn) are calculated as following DP equation. - 1) Initialize D?(.-l,j)=D?(O,j)= for n=l,2, ··· N; j=l,2, ·· Jn 2) Execute 3)4)5) for i=l,2, ··· I - 3) Execute 4)5) for n=l,2, ··· N - 4) D?(i,l)=dn(i,l) B?(i l)=i 3. . ' n 5) for J=2,3, ··· J i =i~2~~l~iD?(i',j-l) D?(i,j)=~(i,j-1) + dn(i,j) B? (i ,j) =B? (i ,j-1) ## 4.3 Application to Connected Word Recognition Oka has presented a connected word recognition algorithm based on a word spotting algorithm (called Continuous DP)[S]. However, his word spotting algorithm is incomplete on the application way of a dynamic programming technique and the word decision process is nondeterministic or heuristic. We propose a new connected word recognition algorithm based on our word spotting algorithm. Our method is based on the formalization of equations (2), (4), but gives an approximate solution for their equations. n In the equations (2), (4), we must calculate D (m+l:i) for m=O,l,2, ··· i-1. This cumulative distance depends on the matching length in the test pattern, that is, i-m. On the other hand, D?(i,Jn) depends on the length of reference that is Jn ' n , . There~re w~ can obtain approximately D (m+l:i) from D (i,J ) as follows. Although the location of B?(i,Jn)-i in the test pattern is the most reliable candidate location for the reference and i-th frame, m is fixed to B?(i,Jn) -1 ~n thisnmodification. Therefore we try to est~mate D (m+l:i) in some locations as follows. ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000004_535992458c33999683662b0953c68a267045ed157e1d98991b3f444fd21a7671.png) Where-r 1 -r 2 denotes the estimation range. If we would l~ke to calculate Dn(m+l:i) for more various locations, we should modify our word spotting algorithm as follows . - 4) for k=l,2, ·· · K D?(i,l,k)=dn(i,l) B?(i,l,k)=i - 5) Execute 5') for j=2,3, ··· Jn 3. 5 ') for k=l,2, ··· K i', R' =i~2~i~<ihi~~<KD?(i',j-l,k') ~(i,j ,k)=D'ff(i'T,J-l,R'T) + dn(i,j) B (i,j,k)=B?(i',j-l,R') Where the following condition should be satisfied: B?(i,j,k)~E?(i,j,h) for l~h<k. 4. Thus Dn(m+l:i) is obtained from: 6) for~=l,2n ··· K 5. m=B (i,J ,k)-1 Fig.~ illu~trates the difference for the calculation of D (m+l:~) between Two Level DP and Augmented Continuous DP. We find ACDP is an a?proximate method for calculating Dn(m+l:i), i-2Jn~m~i-Jn/2. We think, however, it is a fairly good approximation. Where r 1 corresponds to a skipped range between words and r 2 an overlapped range. ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000005_36603c688e7b25eee8c3f508a2b342417d87ff86a19143cfddee062bbb768773.png) (a) Tvo Level OP ![Image](https://ijcai.org/proceedings/1983/fulltext/152/image_000006_9d630e521a8feca5255208353953e51b7c708d67a63ee326d9e2b0eaf026fb0e.png) (b) Aug11ented Continuous DP (~=2) Fig.5 Range of m for the calculation of D"(m+l:i) ## 4.4 A Connected Spoken Word Recognition Algorithm by Augmented Continuous DP In this section , we present a connected spoken word recognition algorithm with syntactical constraints by Augmented Continuous DP. ## 1) Initialize ``` k=l,2, 2) Execute 3)-10) for i=l,2, ·.· I 3) E~c~te 4)-8b :or n=~2~ .·· N. 4) D (~,l,k)=d (~,1), B (~,l,k)=~, for k=l,2, 5) Execute 6) for j=2,3, ··. Jn 6) for k=l,2, ··· K .. , !('- "h · nne·· ·1k') ~ ' -i~2~i~J3il(i,j , h) +r 2 7) Execute 8) for k=l,2, ·.. K 8) for r'=-r 1 , -r 1 +1, 0,1, ·· r 2 m=J3il(i,Jn,k) - 1 n =n n i -m-r' D (m+r'+l:i)=D (i,J ,k)· ~ · · K 9) Execute 10) for q=q 1 , q 2 , ·.. qJs J-l 10) for m' = 1 ~~KJ3ll (i ,Jn, k) -r 1 -1 , .. '=n . n = = l~!KB (~,J ,k)+r 2 -l; n=l,2, ··· N; q '=ql' q2~ ~-- q l sl-1 m', n, q' = argmin(D ,(m') + Dn(m'+l :i)) Where, q=~(q',n) A q D (i)=DA,Cm') + Dn(m'+l:i) q q N Ci)=n B Ci)=m' Q Ci)=qA' q ' q ' q ``` - 11) Word decision process (refer to Fig . 3) ## V COMPARISON WITH OTHER ALGORITHMS Table 1 summarizes the amount of computation and memory storages for various algorithms. The amount of computation for phrase level (word decision l evel) is abbreviated. The amount of memory storages for r eference patterns and working area is also abbreviated. In general, .notice that the computation time of local distance (distance between frames ) consumes about as five or ten times as that of cumulat ive distance per one execution and that the value of J~l is several times of N (dependent on t ask) . Here we assumed that the window of DP matching viaS the ·slore of 1/':'. to 2 (for example , (h)-(e) in Fig . i and Fig . 4) . Augment ed Continuous DP (ACDP) matching algorithm is a better approximate algori thm of the solution for the equations (2) and (4). In other words, owing t o the approximate solution , uncertain parts in word boundaries might be skipped for matching, that is, this has a function of unconstrained endpoints DP matching. This was extended to emmit some (K) candidate locations and matching scores for every word and frame. The suitable value of K is about 2 from view point of computation, memory storage and accuracy. In this case, the value of K' becomes about 2 t o 4. We think that ACDP algorithm is a suitable algorithm for a task with large vocabulary or complex syntax . ## References 1. T.K.Vintsyuk,"El ement-wis e Recognitio!l of Continuous Speech Composed of Words from a Specified Dictionary" Kibernetika (Cybernetic s) No . 2 (1971) 133-143 2. H.Sakoe,"Two Level DP-matching -A Dynamic Programming Based Pattern Matching Algorithm for Connected Word Recognition" IEEE Trans. Vol . ASSP-27, No . 6 (1979) 588-595 3. C. S. Myers and L.R.Rabiner,"A Level Building Dynamic Time Warping Algorithm for Conn ec ted Word Recognition" IEEE Trans. Vol.ASSP-29 , No . 2 (1981) 284 -297 4. H.Sakoe and M. Watari, "Clockwise Propagation DP-matching Algorithm for Connected Word Recognition" ASJ, S81-65 (1981, in Japanese) 5. S.Nakagawa,"Continuous Speech Recognition Methods by Constant Time Delay DP Matching and O(n) DP Matching" ASJ , S82-17 (1982,in Japan ese) 6. T.Sakai and S.Nakagawa,"Speech Understanding System -LITHAN -and Some Applications, in Proc. 3rd IJCPR (1976) 621-625 7. R.W.Christiansen and C.K.Rushforth, "De t ecting and Locating Key Words in Continuous Speech Using Linear Predictive Coding" IEEE Trans. Vol .ASSP-25 , No.3 (1977) 361-367 8. R. Oka, "An Infinit e-Connected Words Recognition System for Male Speakers Using Time-Space Dynamic Programming" in Proc . 6th IJCAI (1979)