Dynamic time warping applied to detection of confusable word pairs in automatic speech recognition

DYNAMIC TIME WARPING APPLIED TO DETECTION OF CONFUSABLE WORD PAIRS IN AUTOMATIC SPEECH RECOGNITION Jan Anguita Ortega, Francisco Javier Hernando Pericás {jan,javier}@talp.upc.es (TALP Research Center) Universitat Politecnica de Catalunya, Barcelona, Spain ABSTRACT In this paper we present a rnethod to predict if two words are likely to be confused by an Autornatic SpeechRecognition (ASR) systern. This method is based on the c1assical Dynamic Time Warping (DTW) technique. This technique, which is usually used in ASR to measure the distance between two speech signals, is usedhere to calculate the distance between two words. With this distance the words are c1assified as confusable or not confusable using a threshold. We have tested the methodin ac1assicalfalse acceptance/false rejection framework and the Equal Error Rate (EER) was measured to be less than 3%. 1. INTRODUCTION U sing speech to communicate with the machines is a greatimprovernent since ithas a lot of advantages: speech is the natural way of communicationfor humans, speaking is fasterthan typing, while speaking hands and eyes are free for other tasks, sorne channels (Phone) are made for speech, etc. Unfortunately, a1though Automatic Speech Recognition (ASR) technology is already mature enough for sorne consumer products, in order to obtain acceptable performance s the vocabulary and the structure of the sentences that the systemis able to recognizemust be limited. Even so, the systems make errors. These errors are sometimes caused by the words of the vocabulary that are phonetically similar. Therefore, the error rate can be reduced by designing the vocabulary with words as less similar as possible. The aim ofthis study is to design a method to predict if two words are likely to be confused by an ASR system. A tool .. RAMA DE ESTUDIANTES DEL IEEE DE BARCELONA like this can help to design the vocabulary of a speech recognition system since it can wam the designeriftwo words are too similar, and sometimes one ofthem can be changedfor anotherone with the samemeaning butless similar. For example, suppose that we want a speech recognition systemfor amail application, where the user will be able to control all the options by his voice. First of all, we have to define the vocabulary that the systern will be able to recognize. For example, suppose that we chose the following words: Supprirner: to delete amessage. Imprimer: toprintamessage. Envoyer: to send amessage. Lire: toreadamessage. Ecrire: to write a message. Suivant: to go to the nextmessage. Précédent: to go to the previous message. We have chosenFrench words because in this project we have worked in French. Once the vocabulary is chosen we have to define the syntax, i.e. the structure of the sentences the systern will recognize. In this case isolated words is enough. This means that the usercan only say one word each time, preceded and followed by a silence. He cannot say supprirner suivant for example. This application may seem very simple but, as we have already said, we must do these simplifications because, nowadays, the ASR technology is not good enough to let the user say whathe wants and how he wants. Even if this systern is very simple it will rnake errors. Sometimes the userwill say one word and the system will recognize another one. This is very dangerous because, imagine that the 45 usersays lireand the system understands supprimer. The message is lostforever. Therefore, these errors must be reduced as much as possible. Imagine that, when the system is already in use, we realize that it ofien confuses two words, for example supprimer andimprimer. If we wouldhave known this when we were designingthe vocabulary ofthe system, we could have changed one word by a synonym, for example supprimer by effacer. In this case the application wouldhave been exactlythe same and we would have avoided the confusions between supprimerandimprimer. In this projectwehavedevelopedamethod to predictif two words are likely to be confused by an ASR system if they are both in its vocabulary. We will use the terms confusable and not confusable to referto the pairs of words thatare ofien confused by an ASR system and the ones that are not confused respectively. The developed method is based on a technique called Dynamic Time Warping (DTW) [1], which is usuall y used in ASR to measure the distance between two speech signals. Here, we use it to calculate a measure of distance between the phonetic transcriptions of the words to compare [2,3] and, after, we classify the pair of words as confusableornotconfusable using a threshold. This method can help to design the vocabulary of an ASR system, because it will wam the designerifhe chose confusable words so, he can change them if it is possible. The principIe of this measure is to do an alignment between the phonetic transcriptions of the two words and calculate the distance as the sum of the distance between the phones that are in correspondence according to the alignment. Although the developedmethod can be used in any language, the used language in this work is French. The organization of this paperis as follows. In section 2 we explain the DTW distance. The first step of this technique is to align the phonetic transcriptions to compare. Therefore, first of all we explain the notation used to describe an alignment. After, the formulation ofDTW andits algorithmare presented. In section 3 we present the distaIíce measure between phones that we have used to calculate the distance between phonetic transcriptions. In section 4 we describe the experiments performed to test the method and the 46 obtainedresults. Finally, in section 5 we presentthe conclusions of this work. 2. DYNAMIC TIME WARPING 2.1. Alignment between Pbonetic Transcriptions Let Wj={Pj) and W2={P2 ), with i=l, .. .J and j= 1, ... ,J, be the phonetic transcriptions of the two words to compare. The values 1 andJ are the lengthsofthephonetictranscriptionsandp .andp . • h ~ are therrphones. Let us consider an i-j grid, shown in Fig. 1, where Wj and W2 are developed along the i-axis and the j-axisrespectively. A path through the grid is written as F={c(l),c(2) ... c(K)}, and it represents an alignment between the two transcriptions. The generalisedelementofthe path is c( k) and it consists of a pair of coordinates in the i and j directions. The i and j coordinates of the kth pathelement are i(k) andj(k) respectively. c(k)=(i(k),j(k» (1) The pathFfulfIIs the following conditions [1]: 1) Monotonic conditions: i(k-l) s i(k) andj(k-1) sj(k) (2) 2) Continuity conditions: i(k)-i(k-1)sl andj(k)-j(k-1)sl (3) 3) Boundary conditions: i(K)=I and j(K)=J (4) The alignment is defined by the path F as follows: -ifi(k)=i(k-l)+l andj(k)=j(k-l)+l thenp . d· j«~ an p 2j(k) are ahgned. -ifi(k)=i(k-l)+l andj(k)=j(k-l)thenp. is a1i ed . 1z(k) gn wlththenullcharacter(symbolofaninsertion or an omission) - ifi(k)=i(k-l) andj(k)=j(k-l)+l thenp. is ali ed ·th ~ gn WI thenullcharacter. BURAN N"22 SEPTIEMBRE 2005 Pll p12 P13 (0,0) c(l)==(l,l) c(2 )==(1,2) c(3 )==(2,3) c(4 )==(3,4) Fig. l. Example ofapath F in the grid, and the steps c(k). For example, the alignment associated to the path ofFig. 1 is the following one: P2¡ p22 p23 p24 P11 P12 p13 2.2. DISTAN CE BETWEEN TWO PHONETIC TRANSCRIPTIONS The proposed application of this work is to predictiftwo words are likely to be confused by an ASR system, i.e, if they are confusable or not. In orderto do this, a distance is calculated between the two words and, if the distance is lower than a threshold, the word pair is considered confusable: { if D DTW (W¡ , W2 ) s Threshold => Confusable if D DTW (W¡, W2 ) > Threshold => Not Confusable whereD DrJ W} , W) is adistance between the phonetic transcriptions of the words W} and W2• Dynamic Time Warping (DTW) [1] is a technique that was used in speech recognition to ca1culate a distance measure between two speech signals. In this work we apply this technique to ca1culate the distance between the phonetic transcriptions of two words: (5) K 6 d(c(k ))w(k) K 6W (k) RAMA DE ESTUDIANTES DEL IEEE DE BARCELONA where w(k) is a weightingfunctionintroduced to normalise by the path length and d(c(k)) is a distance measure between the elements that are aligned according to c(k). For example d( c( 1)) in Fig. 1 is the distance between the phones and p 11. How to obtain the distance d( c(k)) is explained in the following section. In this work we have used the followingweightingfunction [1]: w(k)=i(k)-i(k-1)+j(k)-j(k-1) (6) Thisimplies that: Then, the denominator of (5) is constant and, therefore, independent of the path F. The DTW distance is the minimum weighted surnmation ofthe distances between the aligned phones, for all the possible alignments between the phonetic transcriptions of the words. Since the denominator N(w)=I+J is a constant, in order to solve (5) we only have to minimize the numerator and after, divide by 1+ J. Recall thatthe points that can lead to the point (i(k),j(k)) are (i(k)-l ,j(k)), (i(k)-l ,j(k)- 1) and (i(k),j(k)-l) (monotonic and continuity conditions). Therefore, the weights associated to each step are (using (6)): 47 (i(k)-l,j(k)) --;. (i(k),j(k)): w(k) = i(k)-i(k-l)+j(k)- j(k-l) = i(k)-(i(k)-l)+j(k)-j(k) = 1 (i(k)-l,j(k)-l) --;. (i(k),j(k)): w(k) = i(k)-i(kl)+j(k)-j(k-l) = i(k)-(i(k)-l)+j(k)-(j(k)-l) = 2 (i(k)-l,j(k)) --;. (i(k),j(k)): w(k) = i(k)-i(k-l)+j(k)- j(k-l) = i(k)-i(k)+j(k)-(j(k)-l) = 1 The solution, i.e DDTW(Wl,W2), can be found using the variable s(i,j) defmed as follows: (8) 1 s(i-l,j)+d(i,j) s(i,j)= min s(i -1, j -1)+ 2d(i, j) s(i, j -1)+ d(i, j) where s(i,j) is the accumulated distance of the optimal path that goes from the point (0,0) to the point(i,j). Therefore, (9) D (W W )= s(I,J) D1W l' 2 I+J When all the values s(i,j) have been calculated overalli,jDDTW(Wl,W2)canbecalculatedusing (9). Below we present the algorithm to find the solution [4]. s(O,O) = ° for(j= 1 ;j J ;j++ ) s(O,j)= for(i=l ;iI;i++){ s(i,O)= for(i=l ;iI;i++){ } D (W W )= s(I,J) D1W l' 2 I+J } 3.DISTANCE BETWEEN PHONES In the previous section we have explained the DTW technique, whichis used tocalculate adistance measure between twophonetic transcriptions. Since this technique depends on a distance between the phones of the phonetic transcriptions, in this section we explain how to obtain this distance. In modem ASR systems the acoustic units are usually modeled 48 by HiddenMarkov Models (HMM) [5]. Therefore, it is possible to obtain a distance measure between two phones by ca1culating the distance between their HMMs. In this paperwe propose the following distance between two HMMs: (10) if PI" P2 if PI = Pz where Q is an alignment between the states of the HMMs of the phones p 1 and p 2' P( Q) is the probability of Q, L is the length of the alignment, q 1i and q2i are states of the models that are aligned according to Q, N q¡; and N q2i are the Gaussian distributions associated to the states q 1i and q 2i' and DJ) is a measure of distance between the two Gaussian distributions. The numeratoris a weighted sum of the average distance between the Gaussians ofthe aligned states foreach alignmentQ. In [6], this average distance between Gaussians is ca1culated foreach Q and the mínimum one is chosen. On the other hand, we sum all these average Gaussian distances weighted by the probability of the alignment. Since only a subset of the possible alignments is used, the denominatoris introducedin order to normalise by the probability of the subset of alignments. In this work, we used the alignments associated to the possiblepaths ina gridof dimension M1 xM 2 ' where M1 andM 2 are the number of states ofthemodels. Fig. 2 shows anexamplewithM 1 = M2 = 3.This subset avoids the alignments where there are loops in states of the two models at the sametime. (q 11>q21) = (1,1) (q 12,q 22) = (2,2) (q 13>q 2~ = (2,3) (q 14,q 24) = (3,3) Fig. 2: Subset of alignments used to calculate the inter-HMM distance. The bold Une shows one ofthese alignments. The values of ql i and q2i are the aligned states according to the path in boldo BURAN N°22 SEPTIEMBRE 2005 The models used to obtain a distance value between the phones with the proposed measure have one Gaussian per state. This does not imply that therealASRsystems musthaveone Gaussian per state. We considered several monomodal GaussiandistancessuchasEuclidean,Mahalanobis, Kullback -Leibler, Bhattacharyya and J effreys- Matusita [7,8]: Euclidean distance: (11) Bhattacharyyadistance: (12) DBH/N¡,N) = (118) (~2 - ~lY «L 1+LY2)'1 (~2 - ~l) + 1/2 log (I(Ll+L2)/2I)/(ILlIIL21)(1/2) Jeffreys-Matusitadistance: (13) DJM (NI' N2 )= -fi(l-exp(D BHA (NI'N 2 )))1/2 Kullback -Leibler distance: (14) DK lN¡,N 2) = 1/2 (~2 - ~lY (1IL1 +1IL 2) (~2 - ~l) + 112 tr«1!L1 )L 2 + (1ILz>Ll -21) Mahalanobis distance: (15) DMAH(NJ'N 2) = (~2 - ~y (LILz>-1(~2 - ~l) where 11, and ~, are the mean vector and r', I the covariance matrix of the Gaussian Ni respectively. This distance has to be extended to cover pairs consisting of a phone and the null character, which corresponds to the operation of insertion or omission. Theextendedinter-phonedistance, which • RAMA DE ESTUDIANTES DEL IEEE DE BARCELONA is the one used to ca1culate the DTW distance measureis: where d_is the distance between a phone and the null characterThis value was set atthe arithmetic mean of the distances between all the phones: (17) where P is the total number of phones. 4.EXPERIMENTS AND RESULTS 4.1.ExperimentalSetup In order to test our method we need to determine which pairsof words are usualiy confused by ASR systems tocomparethem with the prediction of ourmethod. We constructed two kinds of ASR systems: one to detect the confusable word pairs, and the other to detect the not confusable word parrs. -NCDSystems(NoConfusabilityDetection): 223 systems, each one with only one word in its vocabulary and a garbage model to reject out -of- vocabulary data. Each system was tested with the 223 words. -CD System (Confusability Detection): One system with 841 words and a garbage model, tested with the 841 words. lfoneoftheNCDsystems, withonlytheword A in its vocabulary, is tested with another word B and they are never confused, it means that they are very differentand, therefore, they arenotconfusable. On the other hand, if they are sometimes confused, it only means that Bis more similarto A than to the garbage model, not necessarily that A and B are similar. Therefore, with this kind of systems we can only determine if two words are not confusable in general . 49 If we test the CD system with several pronunciations of a word A, and a word B is never recognized, we cannot say that A and B are not confusable, we can only say that A is more similar to sorne of the other words of the vocabulary than to B. On the other hand, if they are sometimes confused, we can assure that they are quite confusable. Therefore, with this system we can detect confusable word pairs. The vocabulary ofthe CD andNCD systems consisted ofFrench isolated words such as numbers, cities, cornmands, etc. Each word was pronounced by 700 speakers in average. The speech signal was sampled at 8 kHz and parameterized usingMFCCs. The feature vectors consisted of27 coefficients: the frame energy, 8 MFCCs, and the first and second time derivatives. The models of the words were constructed by concatenating context dependent HMMs ofthe phones with one Gaussian per state. By testing these systems the following three groups of word pairs are obtained: "Low Probability ofConfusion (LPC): 21506 word pairs which were never confused when the NCD systems were tested. "Medium Probability of Confusion (MPC): 150 word pairs which had a confusion rate lower than5% andhigher than 0% whentheCDsystem wastested. "High Probability of Confusion (HPC): 189 word pairs which had a confusion rate higher than 5 % when the CD system was tested. We consider a False Rejection to c1assify as confusable a LPC word pair, and a False Acceptance to c1assify as not confusable a HPC word pairo The MPC word pairs were not taken into accountin theevaluation because weconsidered that is not a severe error neither to c1assify them as confusable nor as not confusable. The HMMs used to calculate the inter -phone distances are not the models usedin recognition. In the first case we used models without context with 3 states and 1 Gaussian per state. 4.2. RESULTS In order to test our method we measure the False Rejection Rate (FRR) and the False 50 Acceptance Rate (F AR). The FRRis the errorrate when c1assifying the pairs of words that are not confusable, i.e., the percentage of pairs words belongingto the group LPCc1assifiedas confusable. The F ARis the errorrate when c1assifying the pairs of words that are confusable. That is to say, the percentage of word pairs belonging to the group HPCc1assifiedasnotconfusable.Ourobjectiveis to minimize both FRR and F AR, and both values depend on the chosen threshold. If we decrease the threshold theFRR decreases and theF ARincreases and vice versa. In order to compare the different methods with only one value we use the EqualError Rate (EER). TheEERis the False AcceptanceRate and the False Rejection Rate obtained with the threshold thatmakes them equal as shownin Fig. 3. FRR Fig. 3: FRR and FAR in terms ofthe threshold. The EER is the point where the two Unes intersect. Table 1 shows the EER for each Gaussian distance in (10). We can see that the betterresults are obtained when using the Mahalanobis Gaussian distance to calculate the distances between the phones. With the Euc1idean and the Kullback- Leibler distances also low errorrates are obtained. On theother hand, the Battacharyyaand theJeffreys- Matusitadistances give highEERs and therefore are not useful to ourpurpose. We can conc1ude that the developed method can be used useful to predict if two words are likely to be confused by an ASR systembecausewehaveobtainedanEERof2.6%. 5.CONCLUSIONS In this paper we have presented a method to predict if two words will be confused by an ASR system. This methodis based on the c1assicalDTW technique, which is used to calculate a distance BURAN N°22 SEPTIEMBRE 2005 between two phonetic transcriptions. We also have described how to obtain the data to test. We have tested the method in a classical false acceptanee / false rejeetion framework and the EER was measured to be les s than 3%. DTW EUC 3,1 % KL 3,2% MAH 2,6% JM 7,5% BHA 8,9% Table 1: EER obtained with each Gaussian distance in ( 10 ) 6.ACKNOWLEDGMENTS This paper reports the work performed during an intemship at Telisma R&D, Lannion, Franee. The authors would like to thank all the members of Telisma speeially Stephane Peillon and Alexandre Bramoulle. 7.REFERENCES [1] lfuoaki Sakoe and Seibi Chiba, "Dynamic Programming algorithm optimization for spoken word recognition". In IEEE Tran s. on ASSP, vol. ASSP-26, N°1, 1978. [2] Beng T. Tan, Yong Gu, Trevor Thomas, "Word Confusability Measures for Vocabulary Selection in Speech Recognition", Proceedings of the ASRU, Keystone, December 1999. [3] Sandrine Pouységur, "Etude du taux de confusion de mots pour la reconnaissance de mots isolés". 4e Rencontres jeunes chercheurs en parole, 200 l. [4] Calliope, La Parole et son Traitement Automatique, Masson, París, 1989. [5] Rabiner L. "A tutorial on Hidden Markov Models and Selected Application s in Speech Recognition". Proceedings ofthe IEEE, 77(2):257-286, Feb. 1989 . • RAMA DE ESTUDIANTES DEL IEEE DE BAR CELONA [6] Bahlmann C. and Burkhardt H. "Measuring HMM similarity with the Bayes probability of error and its application to online handwriting recognition ", Proceedings ofthe ICDAR, pp406 -4 11 , 2001. [7] Bas sevi lle M. "Dis tance Measures for Signal Processing and Patter Recognition ", Signa! Process in g, Vol. 18(4),pp. 349-369,1989. [8] Sooful J ., Botha E. "An Acoustic Distance Measure for Automatic Cross-Ianguage Phoneme Mappin g". Proceedings of the PRASA , 2001 . 8.AUTHORS Jan Anguita Ortega receive dhi sdegree in telecommunicarion engineering and the European master in speech and language from the Universitat P olitecnica de Catalunya (U PC) in 2003. He is currently a PhD student in the department ofsignal theory and communications at UPC. His interests are speech processin g, robust speech and speaker recog nition and speech perception. Francisco Javier Hernando Pericás received his degree and PhD degree in telecommunication engineeringfrom the Universitat Politecnica de Catalunya (UPC) in 1988 and 1993 respec ti vely. He is presently an associate professor in the department of signal theory and co mmuni cations at UPC. His main interests ar e speech processing and robust speech and speaker recognition. He has publishedpapers in internationaljournals and co nf erences and he is member ofbot h national and international associations. He works in projects supported by Spanish and European institutions. 51