On Multi-Level Machines for Continuous Speech Recognition

ON MULTI-LEVEL MACHINES FOR CONTINUOOS SPEECH RECOGNITION

Joseph di Martino

ONIVERSITE DE NANCY I - CENTRE DE RECHERCHE EN INFORMATIQOE DE NANCY

In this piper we introduce the ocncepts of nulti-lev<>l madrines arrl of nul ti -level dynamic programni.rY,J. 'nlese madrines are well suited for the difficult ccntinlnJS speech recognitioo I='blan because firstly, they pennit the integratioo of several lanlled;Je sources, sea:rrlly, they allCM an cptimal search based oo dynamic pro;Jramnin:J arrl thirdly, they can deal with sanantic ooostraints. F\lrthenrore these sanantic ooostraints have the interest:in; prqlerty to be dynamic, i.e. they can be m:xii.fied easily by the speech recognitioo systan itself. '!he .inp::lrtant ~ of this prqlerty is that the nulti-level machines x:resented in this pap& have a potential self-learJ'lin1 tab:il.ity.

In this pap& we x:resent the cx:rx:epts of nulti- level madrines arrl nulti -level dynamic pro:Jra!llllirg. 'nlese nulti -level madrines, oo ooe harrl, pennit the integratioo of several lanlled;Je sources such as pxn:uogy, syntax, sanantic etc, arrl oo the ot:her-han:l can take into aoount local sanantic coostraints. 1\s it will be &n.n these sanantic ooostraints are "dynamic", in the sense that the speech recognitioo systan can m:xii.fy them easily.

In sectioo 2 we begin by slx:Jwi.n;J mw a !-level machine can be b.lilt f:ron sinpl.e finite-state autaratoos. 'nlese autaratoos are called oells because the entire machine is b.rilt f:ron these elementary madrines. '!he descriptioo is OO!le in such a way that the iterative p:ocess to generate a general n-level machine can be i.ndooed easily. '!he sanantic links are also describes arrl we p.Jt in evidence the fact that firstly, they can be m:xii.fied easily, arrl seccrrll y that such m:xii.ficatioos can be realized by the speech recognitioo systan itself. nus interestilq prop&ty ccnfer to the systEm a self-learnin;J hahility.

In sectioo 3 we introduce the fonmlisrn necessary to explain mw an cptimal seauch can be realized in an n-level machine. Fran this mathEmatical discussioo we slxJw that the solutioo foorxl. is cptimal for all the levels of the machine. '!his other interstirg property ccnfims the~ of the n-level machines.

'!he basic of the machine is a sinpl.e fini~tate machine as illustrated by figure 1 (1) ·

F.IGR 1. '!he basic oell of a nulti -level machine a sinpl.e finite state autaratoo.

'!he basic oell is characterized by a set of start.in:J states ES, a set of erxlin:J states FS, arrl a set of tenninal synilols T. Fbr exmple, in the case of figure 1, ES = (s 1 , s 2 ), FS = (s 6 , s 7 ) arrl T = (a,b,c;d). An element of the st:art:ing state set arrl an element of the erxlin:J state set are particularized : they are called respectively the entry-state of the machine arrl the exit-state of the machine. 'nlese notioos of entry-state arrl exit-state will be used later en 1oh!n the notioo of ccntext of a machine is defined.

Nc:M in order to a::rmect these basic cells ~oe Use a finite-state fcmnalisn in ..nich the syrrtx>ls are the l::asic cells ~oe just described. Figure 2 sh::7.1s a nachine h.ti.lt fran the a::rmectioo of basic cells.

Iet ec ani fc designate respectively the entry-state arrl the exit-state of an elanentary cell c.

let n ani m two n::x'les of the finite-state nachine in which c c are eni:e:Xled the elanentary cells, def.i.nin:J a transi tioo l..arelled ~ syntx:ll. c.

ret t 11 · (n 1 e 1 , C 1 ,f 1 ,m 1 ) the a::ntext of another nachine c , c c c C 1 · '!hen we say that nachine C is a::rmected to nachine C' if the cx:ntexts of the two nachines are tied ~ the relatioo of JBrtia1 order defined ~ relatioo (2) :

Relatioo (2) defines the a::rmectioo of two nachines. art:, in fact this link is stren]thened by a special link ..nich ties the exit-state of Clll! nachine with the entry-state of the other Clll!, we call su::h a link a senantic link because ~ specifyirq a · Bin]le rode of the target nachine a lot of plths­ senantically incxlrrect- are ~· F\Jrt:henrt:lre as these senantic links can be m:xiified dynamically in a straighfon.w:d manner ~ the speech reoognitioo system, we claim that the I!Ulti-level. IIII!IC:hines have a eelf-leamin;J hability. Figure 3 illustrates su::h a senantic link.

• FJill!E 3. An illustratioo of a sanantic link in a !-level nachine.

At this stage of the develq:pement ~oe can give the fall~ definitioos :

• 'lhe basic cell is called a o-level. DBchine. Stx:h a nachine can be used for exanple to represent the ac:x:>UStical, fh:xlological variatioos of a lexical entity. Interesting stu:iies oo this subject can be found in 5 arrl 6.
• A machine h.ti.lt fran basic cells is called a 1-level nachine.

Figure 2 is an example of a !-level DBchine.

N:M, it is clear that cor procedure for h.ti.l.dinJ a !-level nachine fran o-level nachines can be iterated. we get in this case a general u-level. DBchine ; SUch rtachines are interesting because of the fall~ proferties :

• 1 they can tackle the different degrees of abstractioo of the language ; in other words the structure of the language can be dealt with ~ these nachines. 'Ihi.s property is a very desirable ce1e, because the lan3uages represented in not a structural way -i.e. for exanple o-level finite-state languages-beccme rapidly intractable \~ben the m.rrber of words of the vocal::olary g:J beya1d ~tively one or two hurxired.
• 2 their m::del is ext:ranely ooherent ;
• 3 they can take into acamt sanantic Cx:ru;traints ;
• 4 an qtinal search l::ased oo dynamic prograrrmin:J - lP - is p:lSSihl.e in these nachines 2.

'lhe next ,actioo is interrled to prove the last p:>int.

III - AN <FRIMAL SFA!Oi s::vJriCN BI>SED CN lP IN MLTI-LEVEL Ml'tNINES

At the deepest level of the I!Ult,i-level nachine, i.e. the o-level, the autanatoos are coostituted ooly of terminal syntx:ll.s which characterize the a=ti.c properties of the speec:h signal. A syntx:ll. c in a o-level autanatoo is defined ~ its a::ntext t 0 :

S}'rttx>l II neans that the entry-state arrl the exit-state of a

'Ihe o-level autaratoo inclt.rlin;J syrrb::>l c in context t 0 is itself in context t 1 in the !-level stage of the rrulti-level machine ...tri.ch itself is in context t 2 in the 2-level stage ... ...tri.ch is itself in context tn in the n-level stage of the rrulti-level machine. Coosequently to syrrb::>l c in context t 0 can be associated the list :

wch characterizes oarpletely such a o-level syrrb::>l in an n-level machine. NcM such a syrrb::>l nust be p.~t in rorresp:nlance with the i ' th acx:ustical feature of the l.ll1lax7.ln senterx::e. '!his rorresp:nlance can be realized in a matching space of dirrensicnelity (n+2) where to each .(Dint

is attached the folla.rin;J sarantic interpretation the aooostical entity is p.1t in rorresp::o:lance with a synbol in context t 0 in a machine in context t 1 in a machine in context t 2 ·· .···· in a machine in context tn.

In order to fin:l the best ~ of w:>rds that best matches the 1.ll'lkn:::wl utterance we need to define the neiglll:a.u:h::lods of each .(Dint of the matching Spice 4.

ret define l·i k.=l, .. , 5 be the primitive projectioos on contexts t i at the i 'th level stage of the rrulti -level machine givin] the k'th coordinate of these contects.

As in the connected speech recognition proolem, tw:> kin:ls of neighbc:mh:x:ds nust be defined :

a) Inter-m:del neiglli:nlrh:xx)

this neighlx:m"h::xld nust be defined if i· 0 (t 0 ) is not the entry-state of the o-level machine i· 1 (t 1 ) in context t 1 . In this case the neigl'lt:alrh::xxl of .(Dint (tn, tn-\ tn- 2 , t 0 , i) can be expressed by the folla.rin;J relation

b) Inter-m:xiel. nei.gtp:urtxxxl this ne:i.lx:url'xlcd nust be defined if tlere existes an integer 1 such that :

If tn+l designates the context of the overall machine then by definition : i,n+l(tn+l) = i'n(tn) \<ohatever context tn.

In this case the inter-m::rlel neighl::a.u:h::xxi of p::)int (tn, tn-l, t 1 , i) can be expressed by the folla.rin;J relation

and the general neighl::a.u:h::xxi of .(Dint (t n, t n-l, t 0 , i)

In order to express the DP recursive relation we need the folla.rin;J definitions :

L'EF.INl'l'I(N 1 : If for a particular .(Dint of the matching space (tn,tn-1, tn- 2 , ... , 0 ,i) with i=l relatioos (6) are verified for l=n and if i'n(tn) is a start of then-level machine, then this .(Dint is called a gate-.(:Dint of the matching space.

L'EF.INl'l'I(N 2

assiciated with the partial optimal path goilq thrt:uJh .(Dint (tn,tn- 1 , tn- 2 , ... , t 0 ,i).

- d(tn,tn-l,tn- 2 , ... , .t 0 ,i) is a local rreasure of dissimilarity between the i 'th acx:ustical feature of the l.ll1lax7.ln utterance and the acx:ustical representation of a o-level synbol characte­ rized by the list of contexts (tn,tn- 1 , tn- 2 , .·· ,to).

~ to these definitioos we are able to give the IP relatioos IF V(tn,tn- 1 , .·. ,t 0 ,iJ = o 'IHEN

END IF

It is :inp::>rtant to rerrark that as the lP relatioos take into aco.Jilt all the levels of the nulti-level rradrine, the solutioo d:ltained is c¢irta1 for all these levels.

Fran these lP recursive relatioos it is pJSSible to el.alxlrate an alcprithn that can deal with any nulti-level m::rlel.ed .l.an;juage. Ellt its expl.icetatioo is beyaxl the sa:p! of this piper (3).

N - a:H:UlS1I:H

In this piper we have p:esented the cxn:::epts of nulti-level rrachil)es and of nulti-level dynamic~- 'lhese rradrines are well suited to the diffic.ul.t prd:>lem of coot.inl.nls speech recognitioo because :

• l they ~ the lirr:Juistic strix:ture of the .l.an;juage
• 2 they pennit the introduct:.i.oo of semantic constraints
• 3 they al.l.cM an c¢irtal search l:.ased oo IP.

Aoother interest.in] p:ri.nt of sudl rrachi.nes and perhaps the Il'CSt :inp::>rtant ooe is due to the fact that the semantic links can be m::rlified in an easy rranner 1::1f the speech reao9nitioo itself. ~tly wr nadrines have a p;:>tential hability of self-learnin:J.

• 1 J. E l:l:KKFr, J. E Uiil1I\N : "Fonral laiY:JUageS and '!heir Relatioo to Autarata", ktissoo wesley, Reaclirx;J M:lssaclrussetts, 1969.
• 2 R.BELIMAN : "Dynamic Pro;Jrannrin:J". Princetoo University Press 1957.
• 3 J. di MARl'JN) : "A r-t.llti -Level Li.n;Juistic M:xl.el for O:ntinLOJS Speech Recooitioo", ClUN rep:lrt.
• 4 H. I'm : '"!he use of A Qle-stahe Algoritirn for O:nnected W:lrd Rec:x:qnitioo", IEEE Trans., J'oc:aJSt., Speech, Signal Processin3, VCL. ASSP-32, ];p.263-271, April 1984.
• 5 A.M. CDLIA, D. · OCIARRA : "Autaratic Generatioo of Li.n;Juistic, Ftxnetic and AaJustic l<ll:::lwledhe for a Difh:t'le-Based O:ntinLOJS Speech Rec:x:qnitioo ·System", in Nato Asi Series, Vol. Fl6, New Systans and Architectures for Autanatic Speech Rec:x:qnitioo and synthesis, F. 16, New Systans and Architectures for Autaratic Speech Rec:x:qnitioo and synthesis, R. DE . M:IU and C. Y. SUEN atitors, 5Prinher-Verlag Heidelberg, 1985.
• 6 Kai-FU Lee "Incranental Netw:>rk Generaticn in Rec:x:qnitioo" , CMJ-<::S-85-181, Deputment of O::lrplter Science, Cctrneqie-Meltoo University.