Understanding Spoken Natural Language with Omni-Directional Information Flow

1 Introduction

Flexible intelligent behavior must involve very diverse information flows, which vary drastically from one con­ text to another and encompass heterogeneous sorts of information. The methods proposed so far in AI are generally based on procedures concerning specific sorts of information such as syntax and semantics, and spe­ cific tasks such as speech recognition and parsing. An attempt to coordinate these methods faces fatal difficul­ ties concerning scalability, because procedures stipulate encapsulated ways of information flow, which require a great deal of revision and annotation when they are put them together.

To overcome this difficulty, we consider an architec­ ture consisting of modules of constraint and a general method for controlling context-dependent information flow among heterogeneous types of constraint. . By con­ straint we mean a design orthogonal to information flow, so that there should be no special prescription of infor­ mation flow for pattern recognition, planning, language

Koiti Hasida

Electrotechnical Laboratory 1-1-4 Umezono, Tukuba 305, Japan hasida@etl.go.jp

Takashi Miyata

University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan mya-u@is.s.u-tokyo.ac.jp

comprehension, and so on. Coordination· among mod­ ules is, therefore, a far simpler issue with constraints than with procedures.

Dynamiwl semantics [Hasida, 1992] enables us to de­ sign context-sensitive complex behaviors under declara­ tive semantics within tractable computational complex­ ity. Constraints are represented in a clausal-form logic program, and a fine-grained declarative semantics is de­ fined over the constraints by measuring the degree of vi­ olation in terms of real-valued potential energy. A field of force arises along the gradient of this energy, and in­ ferences are controlled on the ba.<>is of the dynamics. As the potential energy reflects the context, so too does the control of information processing. The computational resources arc concentrated on dynamic focal points in the huge hypothesis space. Also, the system is robust in the sense that it is free from hard failure of constraint satisfaction.

In the rest of the paper, we consider spoken language understanding. Since the constraint-based architecture implements omni-directional information flow between speech and natural language processing, we are able to resolve several tough problems in understanding spoken language, such as treatment of ambiguous or ill-formed speech, prediction of subsequent utterances, revision of previous interpretation, and some speech-specific issues including phoneme insertion/ deletion and word bound­ ary recognition. While most conventional spoken lan­ guage systems first construct phonological hypotheses, then apply higher level knowledge and generate seman­ tic interpretations, our system simultaneously applies all types of constraint, from acoustic to pragmatic. We dis­ cuss some constraints concerning spoken language un­ derstanding, but, of course, there is nothing in princi­ ple which prevents integration of any other sort of con­ straint.

Some research has managed to integrate linguistic in­ formation into speech understanding, such a.'> that by Erman et a!. [1980], Hayes et a!. [1986], Young et al. [1989], Kitano [1991], and Chung et al. [1992], the meth­ ods they propot;e, however, are specific combinations of specific types of knowledge sources with rather fixed in­ formation flows, and with flexible interactions disallowed among them. Our method can flexibly control omni­ directional information flow in a very context-sensitive fashion. The details of the relationship to these work are discussed in Section 4.

2 Interaction across Heterogeneous Information

Section 2 of Hasida et al. [1993] accounts for the com­ putational architecture employed in our study. The rest of this paper employs the notation and terminology dis­ cussed there.

We consider the computational processes along with an example in which the following Japanese sentence is understood from an acoustic input .

tegami kaita letter wrote '(I) wrote a/the letter.'

Since phoneme /k/ and /h/ are similar to each other, kaita might sound like haita (vomited}. In addition, kaita might also sound like kaite (write-IMPERATIVE} due to the similarity between /a/ and jej. The former confu­ sion is resolved by selectional restrictions, and the latter by the semantic and pragmatic context. As shown be­ low, these processes involve omni-directional information flow among acoustic, phonetic, morphological , syntactic, semantic, and pragmatic constraints.

In this example, we consider the following clauses.

• (1} true -sentence(S,X,_) -speechO{X,Y) -sounds(Y) .
• (2} np(S,XO,X6) -letter(S) -t(XO,X1) -e(X1,X2)
• -g(X2,X3) -a(X3,X4} -m(X4,X5) -i{X5,X6) .
• (3} vp(S,XO,X5} -write(S) -past(S) -k{XO,X1)
• -a(Xl,X2) -i(X2,X3) -t(X3,X4) -a(X4,X5).
• sentence(Event,X,Z) -np(lndex,X,Y) -vp(Event,Y,Z) -sbjobj(Event, Index).
• sbjobj(Event,lndex) -agent(Event,lndex) .
• -agent(_,X) +animate(X}.
• -animate(X) -letter(X) .
• -letter(X} +document(X).
• sbjobj(Event,lndex) -patient(Event,lndex) .
• -patient(Event,lndex} -write(Event) +document(lndex).

The details will be accounted for in the following discus­ sion.

2.1 Acoustics and Phonetics

It is theoretically possible for our computational ar­ chitecture to incorporate traditional methods of speech recognition, such as Hidden Markov Models (HMM) [Itou et al., 1992], DP matching, and Time-Delay Neu­ ral Networks [Waibel et al., 1989]. For instance, HMM consists of a finite state automaton and stochastic in­ formation, which are encoded straightforwardly in logic program and dynamics, respectively. In the current im­ plementation, however, phoneme recognition is an ex­ ternal procedure call, because this involves sequential simulation and, hence, cannot accommodate the mas­ sive computation required for speech recognition in our computation-demanding architecture.

Although this excludes acoustic information from dy­ namical interaction, the phonological information can still interact dynamically with syntactic, semantic, and other types of information within the uniform computa­ tional architecture. That is, the scores for the phonemes are not determined once and for all, but vary over time depending upon the global context, including various other types of information, as discussed later.

Figure 1 shows an example of a phoneme lattice that is

constructed in the traditional speech recognition phase. In this figure, /t/, jej, and /d/ represent phonemes. This phoneme lattice is encoded in the constraint net­ work in Figure 2. The output of the HMM procedure

augments such a network. In this figure, sound1( ·.·} and sound2{ ·.·) represent acoustic signals introduced over time. They may be regarded as sequences of vector quan­ tization codes, for example. speechO( ·.· ), speech1( ·.· ), and speech2( ·.·) represent phoneme boundaries, which correspond to nodes in the phoneme lattice shown in Figure 1. Also t( ·.· ), e( ·.· ), and d( ·.·} correspond to the recognized phonemes /t/, fe/, and / dj. Currently, when a new phoneme (say /t/) comes in, a new literal -soundi(·.·) is introduced into the top clause (1). The scores of speech recognition are reflected in the relevant parameters of energy functions.

As mentioned above, such structures are made by an external procedure in the current implementation, but this process is designed to fit into our main architecture in the following two senses. First, these procedure calls are eventually subject to dynamical control. That is, the procedure is called when a phoneme on the right edge of the lattice is linked to another through a lexical entry. The creation of such a link is controlled on a dynamical basis, as described in the next subsection. Second, we can make the structure in Figure 2 without recourse to external procedures, if a speech recognition method such as HMM is really encoded in con~traints as mentioned before.

2.2 Phonetics and Morphology

Next, we explain interaction between recognized input phonemes and phonemes in the lexicon. Clauses (2) and ( 3) are lexical entries.

For the sake of simplicity, we first show exact matches between inputs and the lexicon. Figure 3 illustrates how an input phoneme sequence ft ef (t( ·,·) and e( ·,·) in the figure) and phonemes in the lexicon tegarni (letter) are connected to each other by unification links.

There is a local potential energy which captures the transitivity of equality. Due to this energy, an equation tends to be highly activated when it belongs to a cy­ cle of equations. Symbolic operations to create cycles of equations are hence preferred in most cases. In Figure 3, consider the initial situation where the links between the two t( ·,· )s and those between the two e( ·.· )s are not yet created. The first argument of speechO( ·,·) and the sec-

ond argument of np( ·.·.·) are connected through equa­ tion path a. (a runs across the syntactic constraint, as shown in Figure 7.) If the two t( ·.· )s are linked, then equation b together with equation path a will constitute a cycle of equations as indicated by the thick curve. So, the operation to create the links between the two t( ·.· )s is preferred here. Namely, l¥al is large now, where sis parameter of the energy function associated with links b and c. Similarly, if the two e( ·.· )s are linked as well, then equation c together with equation d will constitute a cycle of equations. Thus, the operation to create links between the two e( ·.· )s is preferred once the two t( ·.· )s are linked. Consequently, the recognized phoneme se­ quence /t e/ is likely to be matched against the initial part of the phonological form of the word tegarni (letter).

Figure 4 illustrates a deviation from exact matching, including one insertion/deletion and one substitution. The leftmost pair of the figure exhibits a substitution of ft/ with /k/ or vice versa. The atomic formulas and equations in the thick cycle have lower activation values than when that matching was exact. This is because mutual excitation between different phonemes (t(·.·) and k(·.·) in this case) is weaker than that be­ tween the same phonemes. Here, we omit the details of how to encode this in the potential energy. Insertion and deletion also reduce the activation values of the neigh· boring part of the con~traint network because they break cycles of equations. In Figure 4, no cycle of equations involves /gf. Note that, in general, a cycle of equations is created only by consecutive matching of phonemes. Approximate matching i;; an emergent phenomenon of this computational architecture, because the dynamics allows us to compare the adequacy of inexact matchings.

2.3 Morphology and Syntax

Syntax is also considered entirely as a constraint con· sisting of clauses such as ( 4). Phoneme sequences across word boundaries are encoded as a part of the syntac· tic constraint. So, consecutive matching of phonemes is preferred due to equation cycles, just a.o;; in the matching within a single word discussed above.

In Figure 5, the word tegarni has been totally covered

by the input phoneme lattice. Now, the most preferred operation is to establish a link from the input phoneme /k/ to its counterpart in the word kaita, because that will create a cycle of equations as shown by the thick curve.

As noted earlier, we do not employ any domain/task· specific prescription on information flow. Algorithmic behavior is just an epiphenomenon of the dynamics. For instance, an efficient parsing process similar to chart parsing has been shown to emerge out of general hem·is­ tics similar to our dynamical control [Hasida, 1991]. In contrast, the disadvantage of procedures like Ear­ ley's algorithm [Earley, 1970] and generalized LR parser [Tomita, 1987] is that they are less sensitive to context because they stipulate a specific information flow. It is difficult to extend them to incorporate semantic infor­ mation in the course of syntactic parsing, for instance, because that requires you to further stipulate when to use which semantic information. Generally speaking, procedure-based systems tend to become complex, thus reflecting the diversity of the information flow to be im­ plemented. The information flow in the human cognitive process appears diverse enough to render such systems intractable.

2.4 Plus Semantics, Pragmatics, and Whatever

Now, we explain a semantic process using clauses (5, 6, 7, 8, 9, 10). The process is roughly logic-based, and uses deduction and abduction, whose applications are also controlled by the dynamics. ( 5) means that if Index is Event's agent, then Index is Event's subject or object. Similarly, (9) means that if Index is Event's patient , then Index is Event's subject or object. Due to completion, to make sbjobj(V,N) true in (4) requires that Index be an agent or patient of Event. From (6), if Index is agent, then Index should be animate. From (7) , however, if Index is letter, then Index cannot be animate. Thus, link gin Figure 6 causes a contradiction. Then, the cycle

involving g becomes less activated than the cycle involv­ ing J, which does not contain contradictions. In general, an interpretation with more contradiction-free cycles is preferable. This heuristics emerges from the dynam­ ics of constraints. In this example, the interpretation tegami kaita ('(I) wrote a/the letter') is the most prefer­ able, because it involves more contradiction-free cycles than other interpretations such as tegami haita ('(I) vom­ ited a/the letter'), which has no cycle, and tegami kaite

('please write a letter'). which involves two cycles corre­ sponding to the ones involving c and f.

If past( ·) does not exist in the top clause and, in­ stead. we have some pragmatic information indicating that. the speaker is requesting something, then the first interpretation will have only two cycles while the third interpretation will have three or more cycles. Thus, the third interpretation (i.e., the imperative interpretation) will be preferred. The semantic/pragmatic constraints can, thus, contribute to prediction/activation of the in­ terpretation of utterances.

A more global view of the constraint involved in the current example is given in Fignre 7, which shows a. snap-

shot of recognition of phoneme sequence /t e gam i k/ . As suggested by this figure, all the different types of constraints dynamically interact with each other, due to omni-directional information flow across this picture.

3 Experiment

In this section, we show some snapshots of execution of the program implementing the above theory.

Figure 8 represents the state of the constraint network where the first phoneme of the tegami kaita. example has just been accepted. The buttons at the top of the window are used to execute actions such as spreading activation and backpropaga.tion. In the right near the bottom of Figure 8 is a small window entitled 'DP.info' to communicate some information about parameters and activation values. The other squares are clauses. The top clause is near the upper right corner, and the clauses to its left correspond to those in Figure 6. In the lower half of the left hand side are lexical entries for tegami and kaita. The clause to the right of them contains the first phoneme /t/. The four links connected to the phoneme literal indicate tentative matching of that phoneme with ones in lexical entries.

Figure 9 shows how a phoneme lattice is created after some phonemes are accepted. The pyramid of clauses in the center of the window encodes the lattice shown in Figure 10. An insertion of a phoneme takes place in Figure 11. In this case, the input phoneme sequence is It e i g a m il, where the first Iii is regarded as noise. In the figure, this Iii is matched against I el and I gl in the lexical entry of tegam.i.

The current implementation is in 14,000 lines of C code, and runs on standard UNIX workstations. This program is registered a.<> !COT Free Software, and the source is publicly available free of charge for noncom­ mercial purposes. In this sequential implementation, the computational complexity in average cases appears to be linear to the size of the constraint network, which means that the average time complexity is expected to be con­ stant on an appropriate ma.<>sively parallel machine.

4 Discussion

Some previous studies have addressed how to combine different knowledge sources for spoken language under­ standing. HEARSAY-II [Erman et al., 1980] employs blackboard architecture to coordinate several types of information relevant to spoken language. Hayes et al. [1986] employ semantic case frames to analyze spoken language. Young et al. [1989] use dialogue knowledge to predict subsequent utterance. Since they use specific procedures to incorporate specific sorts of knowledge, however, extension to include other sorts of knowledge into the tight interaction is hopelessly cumbersome, be­ cause procedures are basically encapsulated prescription of information flow. Although blackboard architecture is an attempt to reduce such difficulty, the attempt is not successful as far as it is domain/task-specific proce­ dures that operate on the blackboard. Genearlly speak­ ing, prescriptions of information flow give rise to encap­ sulated patterns of information processing, and hence domain/task-specific procedures prevent tight interac­ tions among diverse sorts of information.

Kitano [1991] and Chung et al. [1992] have developed a method of parallel marker passing to support both top-down prediction and bottom-up activation. Their approach is more flexible than the traditional ones, be­ cause marker passing is a weak method and thus does not pose so large chunks of encapsulated information flow as in the traditional approaches. However, they prescribe the routes of marker passing, restricting the diversity of information flow so as to exclude revision of previous phonological interpretation, among others. Also, their approach does not naturally extend to incorporate the acoustic process into the tight feedback loops involving also linguistic and other information.

After all, a major advantage of our method over the previous ones is that it implements more fine-grained and diverse feedback loops integrating heterogeneous sorts of information, rather than constructing phoneme-level hy­ potheses in advance and then going on to the linguistic level as in most of the other approaches. So our system can for instance pick up an alleged phoneme depending upon linguistic or extralinguistic context, even if that phoneme looks so implausible on the acoustic ground alone that traditional bottom-up architecture would fil­ ter it out before entering the linguistic mode. Note that such diverse information flow does not cause com­ putational intractability, because information processs­ ing at each context is centered around dynamically de­ termined focal points or the focus of attention in the constraint network. This cont rol mechanism gives rise to spoken language understanding without any specific procedures for specific tasks, such as matching between phonemes, parsing, and semantic and pragmatic infer­ ences. The computation emergent from this control is highly context-sensitive, since there is no prescription of encapsulated information flow specific to any individual domain or task.

5 Concluding Remarks

We have proposed a computational architecture which supports omni-directional information flow among hetergeneous knowledge sources, from acoustics to pragmat­ ics, and demonstrated that problems in spoken language understanding are naturally resolved in this architecture without any domain/task dependent prescription of in­ formation flow. Although the current implementation handles the acoustic information by an external proce­ dure of the traditional type, it is possible to absorb it into the general architecture, provided with appropriate massively parallel, communication-intensive hardware.

In fact, we are planning to implement the present the­ ory on a massively parallel machine and include the acoustic computation into the constraint-based archi­ tecture, so as to directly incorporate it into the tight feedback loops realized by the constraints. This will ne­ cessitate a learning algorithm to acquire the dynamical properties of the constraint on the linguistic sounds. Our conjecture is that such parameter learning is possible by using the generalized backpropagation method we have already implemented to control computation.

Acknowledgements

The authors would like to thank HAYAMIZU Satoru and ITOU Katunobu at Electrotechnical Laboratory for their help in preparation of the reported experiment.