Joint Utterance: Intrasentential Speaker/Hearer Switch as an Emergent Phenomenon

1 Introduction

The traditional design of AI systems based on procedural programming does not look feasible , because it stipulates information flow so that the complexity of the design heavily reflects the diversity of information flow requisite for intelligent behaviors. This diversity is very likely to be large enough to render such a system too complex and non-modular to extend or maintain.

This paper proposes a totally constraint-based compu­ tational architecture and applies it to natural language processing. Here constraint means a design which is or­ thogonal to information flow, so as to capture diverse patterns of computation in intelligent systems. This notion of constraint is very different from the ordinary one under which a constraint is a declarative knowledge to narrow down the search space. In our architecture, declarative semantics is defined by measuring the degree of violation of a constraint in terms of real valued poten­ tial energy, and context-sensitive control of computation emerges from the dynamics defined thereof.

Our concern here is what kind of mechanism might un­ derlie joint utterance involving role switching between a speaker and hearer in the midst of one sentence. For in-

NAGAO, Katashi

MIYATA, Takashi

Sony Computer Science Lab. Inc. 3-14-13 Higashi-gotanda, Shinagawa-ku, Tokyo 141, Japan nagao@csl.sony.co.jp University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan my a-u@is.s. u-tokyo.ac.jp

stance, it might be the case that one person opens up a sentence by saying Kim. and another person succeeds the utterance and completes the sentence by saying sneezed. A standard way to explain such phenomena would be to postulate a procedure for sentence comprehension and another for sentence production, and finally to account for how to switch back and forth between them. One will then end up with a very cumbersome theory about how the two procedures could communicate, if they are dif­ ferent from each other as is the case with the procedural approach.

The constraint-based approach addresses quite an­ other explanation. First of all, no specific procedures are postulated for the relevant tasks such as sentence pars­ ing, generation, plan recognition, role switching, and so forth , since constraint is orthogonal to information flow. Moreover, joint utterance is accounted for as a corol­ lary of constraint-based architecture. Since constraint does not refer to information flow, input and output are tightly coupled within a constraint module which is em­ bodied as a feedback loop coupling the system and its environment. Joint utterance emerges when the dynam­ ical field around that constraint changes and flips it from input and output or vice versa, the computation on the other relevant constraints such as syntax remaining on the previous tracks.

2 Computational Architecture

A quick overview of our computational framework is in order here. The subsequent sections contain further de­ tails just enough to account for the examples. See Hasida [1992] for a more comprehensive and general discussion.

We consider a clausal-form first order logic program, and treat it totally as constraint, in the sense that there is no predetermined direction of information flow such as top-down or left-to-right. Computation is controlled by a dynamics in the sense of physics. Dynamical in­ teraction across the whole constraint implements omni­ directional information flow among various types of in­ formation, syntactic, semantic, pragmatic and so on.

2.1 Constraint Network

A constraint is a set of clauses. A clause is basically a disjunction of literals. A literal is an atomic constraint preceded by a sign. An atomic constraint is an atomic formula such as p(X,Y,Z), a binding such as X=f(Y), a feature .~pecification such as agent(X,Y), or an equation· such as X= Y. A sign is '+'. '-' or nil. For any atomic constraint a, literal +a stands for just a, and -a stands for -,a. Names beginning with capital letters represent variables, and the others predicates. A clause is written as a sequence of the included literals followed by a period. The order among literals is not significant. So (1) and (2) represent the same clause, which means (3) in a rough, crisp approximation.

1. -p(U,Y) +q(Z) -U=f(X) -X=Z.
2. +q(Z) -p(f(Z),Y).
3. VU, X, Y { -.p(U, Y) V q(X) V U -1- f(X)}

A literal with a null sign is called the head of the clause; A clause with a head is called a definition clause of the predicate of the head. In a crisp approximation, the meaning of this predicate is defined in terms of a neces­ sary and sufficient condition tailored from its definition clauses. For instance, if predicate p has the definition clauses in (4), then pis roughly defined by (5).

Predicates having definition clauses are called defined predicates, and the other predicates free predicates.

A definition clause of true is called a top clause. A top clause corresponds to the query in Prolog. That is, top clause (6) represents top-level hypothesis (7) .

Clause +true. forces the head true of some top clause to be true, so that the negation of the body of that top clause is hypothesized. The computation is to tailor the best hypothesis to explain the top-level one, in the spirit of Hobbs et al. [1990]. The top clause transforms as computation proceeds, when the information boundary between the system and its environment changes, or in particular when interactions with the external world take place.

A constraint is regarded as a network. For instance, the constraint in Figure 1 may be graphically repre-

• (a) true -s{SEM,WO,Wl) -speech{WO).
• (b) s(VSEM,X,Z) -agent(VSEM,NSEM) -np(NSEM,X,Y) -vp(VSEM,Y,Z).
• (c) np(kim,A,B) -"Kim"(A,B).
• (d) vp(SNEEZE,C,D) -sneeze(SNEEZE) -"sneezed" (C,D ).
• (e) vp(VSEMl,E,G) -patient(VSEMl,NSEM 1) -v(VSEM1,E,F) -np(NSEM1,F,G).

Figure 1: A Constraint in Symbolic Form

sented as in Figure 2. 1 In such a graphical represen­ tation, a clause is a closed domain containing the atomic constraints constituting that clause. Atomic constraints without such indication are referred to as negative liter­ als in clauses. An argument of an atomic constraint is depicted as a '·'. A term appearing as several arguments of atomic constraints in a clause is regarded as a hyper­ link whose endpoints are those arguments. For instance, term (variable) VSEM in clause (b) is a hyperlink with three endpoints. Constants such as kim in Figure 2 are also hyperlinks because they are terms. Only constants are hyperlinks running outside of clauses. Equations are links between arguments. For simplicity, we assume that no equation belongs to any clause.

1 Tense is neglected in the semantics of sneeze here.

We regard each part of constraint network as a set of instances, and consider that the unifiability of a and f3 implies that an {3 = 0 is not known, for terms or atomic constraints a and {3. We say a subsumes {3 to mean a 2 {3. We assume two atomic constraints are unifiable if and only if their corresponding arguments are directly connected through an equation, and that every equation connects two corresponding arguments of two unifiable atomic constraints. No equations are unifiable with each other.

We assume that initially all the atomic constraints with the same predicate are unifiable with each other, except that head atomic constraints are not unifiable with each other and non-head atomic constraints shar­ ing the same defined predicate are not unifiable with each other. For example, the vp( ·.·.· )s in (d) and (e) are not unifiable. Neither are the np(·,·.·)s in (b) and (e).

Not every equation is made explicit in a graphical representation. Normally only strong equations are dis­ played, but not weak ones, unless stated otherwise. Here a strong (weak) equation is one which supports a strong (weak) dynamical interaction between the two atomic constraints it links up. At the outset, the equations between atomic constraints with defined predicates are strong and the other equations are weak.

2.2 Dynamics and Computation

Each atomic constraint a has an activation value x0 , which is a real number such that 0 < Xa < 1 and may be regarded as the truth value (or a subjective proba­ bility of the truth) of a, zero and one corresponding to absolute falsity and absolute truth, respectively. The ac­ tivation values of literals are defined so that X+a = X0 and x -a = ( 1 - x 0 ) for any atomic constraint a. The potential energy U of the entire constraint network is a function of the activation values, and represents the degree of violation of the constraint. U gives rise to a field of force to change the state of the constraint network so as to decrease U.

Suppose there are n distinct atomic constraints in the given constraint, and hence n activation values, x1 through Xn. Then the current state of the system is regarded as a point (8) in the n-dimensional Euclidean space, and the global potential energy U defines a field of force (9).

F causes spreading activation. When F =f 0, a change of Xi so as to reduce U influences the neighboring parts of the constraint network, which causes further changes of activation values there, and thus state transition propa­ gates across the network. In the long run, the assignment of the activation values will settle upon a stable equilib­ rium with F = 0. The resulting state gives a minimal value of U. That is, the resultant x suboptimally satisfies the entire constraint.

The declarative semantics of the entire constraint is decomposed into several aspects. U is the sum of the local energies each representing one such aspect, so that U captures the global declarative semantics. The types of energy are disjunction energy, exclusion energy, com­ pletion energy, assimilation energy, dependency energy, transitivity energy, binding energy, and normalization energy. We discuss a few of them just below and some more afterwards.

The disjunction energy of a clause captures the dis­ junction of the literals: at least one literal should be true in a clause. Consider the following clause.

The disjunctive meaning of this clause is that either - p or +q should be true. The below disjunction energy represents the degree of violation of this meaning.

D is a positive constant associated with clause (10). Note that (11) is small if and only if either xp or 1- xq is small; keep in mind that the activation values are be­ tween 0 and 1. In dynamical terms, q is excited by p to the extent that p is excited, and p is inhibited by q to the extent that q is inhibited. In Figure 2, vp( ·,·,·) is excited by sneeze( ·) and "sneezed" ( ·.·) together in (d), due to the disjunction energy.

Exclusion energy represents the mutual exclusion of the literals in a clause, by which we mean that at most one literal should be true. So in (10), for example, only one of -p and +q may be true. This supports abduc­ tive inferences, to assume p when given q, and assume -q when given -p. The exclusion energy of (10) is the following formula.

Eisa constant associated with clause (10). In Figure 2, true excites both s( ·.·.·) and speech( ·) due to the exclu­ sion energy of the top clause, for example.

The assimilation energy between two unifiable atomic constraints captures the axiom of equality in a relaxed fashion: the activation values of two unifiable atomic constraints should be both close to zero or both close to one to the extent that the equations between them are excited. So for instance p(X,Y) and p(U,V) tend to be both excited or both inhibited when the equa­ tion between X and U and that between Y and V are both strongly excited. Then the assimilation energy of the pair of two unifiable atomic constraints a and {3 is defined by the following.

A~ is a positive constant associated with predicate 71' shared by a and {3. 8 ranges over the equations connect­ ing the corresponding arguments of a and {3. sa~ is a non-negative constant called the subsumption coefficient between a and {3. When n and {3 are unifiable, sa~ = 1 if n is known to subsume {3 or vice versa, and otherwise Safi = so for a constant so such that 0 < so < 1. So a and f3 strongly influence each other when they are in subsumption relation. When a and (3 are not unifiable, Sa~= 0.

A transitive cycle is a cycle of equations in which any two adjacent equations are connected with different ar­ guments filled by the same term. The transitivity energy of a transitive cycle tl. is defined as follows, which cap­ tures the axiom of equality, excluding the cases where just one equation in tl. is false.

8 ranges over the equations in tl., and S6 is again the sub­ sumption coefficient of the two atomic constraints con­ nected by 8. 9 is a. constant such that 0 < 9 < 1. t is a positive constant. So the transitivity energy is large when just one 8 has an activation value smaller than 9. Due to this energy, the equations in a transitive cycle very often tend to excite each other.

Symbolic operations encompass not only internal com­ putation including subsumption operation (a generaliza­ tion of unification to create subsumption relation instead of equality) and deletion (of links and clauses) but also input (perception) and output (action). Some of these operations are accounted for along the examples dis­ cussed in the subsequent sections. The preference for a symbolic operation depends on the expected degree to which the accompanying local change may dynamically influence some central part of the constraint. This degree is approximated by '*'· where penalty function P is the disjunction energy o¥' clause +true. at the equilib­ rium of spreading activation, and s is some parameter of the potential energy which is altered by the opera­ tion in question. I* I is regarded as the importance of parameter s. This ~alue is computed by a generalized backpropagation.

Input and output are handled by constraints on the phenomena directly perceivable (in the sense of Gibson [1979]) in the environment, such as speech( ·) in Figure 2. Such constraints extend over both the cognitive system and the world. Namely, they implement feedback loops connecting the system and the world, whereas the other constraints implement feedback loops within the system. Any constraint cannot be just for input or just for out­ put, because input and output are ways of information flow and hence abstracted away from the level of con­ straint. Since information flow is determined accord­ ing to dynamical context in om architecture, whether speech(·) serves input or output also varies from one con­ text to another. Generally speaking, such a perceptual constraint, when fired, introduces a novel piece of infor­ mation about the external world. For instance, speech( ·) unfolds the linear structure of speech. The difference be­ tween input and output is just that in the case of output the introduced information is attributed to the system's own action.

Here it is important that input and output are so tightly coupled for each sensorimotor feedback loop, because this is the source of intrasentcntial switch of speaker and hearer. That is, joint utterance is almost a corollary of constraint-based design, as exemplified in the subsequent sections.

This architecture is omni-directional and holistic for the following reasons. First, the spreading activation based on potential energy implements isotropic informa­ tion flow, because any two activation values influence each other through dynamical interactions. Second, in this connection, backpropagation is also bidirectional in the same sense, the importance of any two parameters affecting each other to the extent that those parameters are related. Third, symbolic operations do not follow any prescribed order or direction, but controlled on the basis of such dynamical properties. Each symbolic oper­ ation is affected by the local dynamical context, which reflects the global context due to backpropagation.

3 From Comprehension to Production

In this section we discuss how the initial hearer may start speaking in accordance with the previous context. The scenario is that a sentence begins with an utterance of one word but the rest of the sentence is taken over by the initial hearer, when, for instance, the initial speaker cannot recall the right word to follow.

Figure 3 shows a part of the constraint when sentence

comprehension is to start. The clauses are the same as in Figure 2 except that the top clause (a) has incorpo­ rated new literal -"Kim" ( ·.· ), which corresponds to the observation of an utterance of word "Kim" in the exter­ nal environment. Clause (e) is omitted because it does not play any important role in the rest of the story.

As indicated by the thick curve, the first arguments of the two "Kim" ( ·.· )s are connected through a dependency path, by which we mean a path of strong equations which implies that the terms on both ends are unifiable. In general, when two terms are connected through a de­ pendency path and fill the first arguments of two unifi­ able bindings or two unifiable feature specifications, sub­ sumption operations are triggered so that one of those terms should subsume a copy of the other. Those sub­ sumption operations start from the term which is in the more important binding or feature specification, and pro­ ceed along the dependency path. The importance of an atomic constraint n is measured by I qfs I· s is the pa­ rameter of dummy (in the sense that s is always zero) energy sx0., which corresponds to an external input to a. In general, a subsumption concerns a pair of unifiable atomic constraints, as is the case with unification, and the preference for a subsumpt.ion along a dependency path is given by I* I again, where s is the subsumption coefficient of the pair of the relevant atomic constraints.

In the current example, the first argument of the up­ per "Kim" ( ·.·) is going to subsume that of the lower "Kim" ( ·.· ), because the former "Kim" ( ·.·) is in the top clause and thus is more important. So the first subsump­ tion is the one indicated by the arrow in Figure 3. This gives rise to the next state shown in Figure 4. Now clause

(b) in the previous state has been duplicated to be {b) and {b'). (b') is the copy whose s( · .· .·) is the original s(·.·.·)'s maximum subset subsumed by the s(·.·.·) in (a). So the s( · ,· ,·) in (b) is not unifiable with that in (a) any more now.

The subsumption along the thick dependency path proceeds further down, as indicated by the arrow in Fig­ ure 4. The result is given in Figure 5. Here the first argument of the "Kim" ( ·.·) in {a) subsumes that of the "Kim"(·.·) in (c'). So the former "Kim"(·.·) subsumes the latter, because "Kim" is a partial function, in the sense that if "Kim"(a,,B) and "Kim"(a.'Y) are both true then !3 and 'Y must be identical. In general, equations be­ tween two atomic constraints are rendered strong when one of these atomic constraints subsumes the other. This is why the equations between the two "Kim" ( ·.· )s are shown Figure 5.

Now we consider how the initial hearer could take over for the rest of the sentence by saying sneezed. Let us investigate how that may happen under the assumption that the top clause (a) contains a literal sneeze( · ), which means that the initial hearer believes that somebody sneezed. She does not have to know from the outset that it is Kim that sneezed, because she can abductively guess it as shown later. Let us also postulate the fol­ lowing clause, which means that a sneezing event should have an agent.

(f) -sneeze(U) +agent(U,V).

Then the sneeze(·) in (a) may excite that in (f) due to ~he assimilation ene~gr- Tl~at would excite the agent( ·.·) m (f) due to the disJunction energy of (f) , which will further excite agent( ·.·) in (b') due to the a.<;similation energy again. On the contrary, the agent( ·.·) in (b') ex­ cites agent(·.·) in (f), it excites sneeze(·) in (f), and it excites sneeze( ·) in (a). This motivates the two indicated subsumptions from (a) and (b') to (f), 2 because that will ~ore strongly excite the sneeze( ·) in (a) and agent( ·.·) m (b') and thus reduce the penalty function P. That is, their mutual activation through (the instance of) (f) will become stronger because the relevant links will be strong due to the subsumptions. This is predicted because -¥a is large for the subsumption coefficient s between th 8 e two sneeze( · }s and also the two agent( ·.· )s. The indi­ cated subsumptions amount to an abductive inference to the effect that it is Kim that sneezed. Note that this process captures marker passing [Charniak, 1986; Norvig, 1989] as an emergent phenomenon of the dy­ namics, markers corresponding to high activation val­ ues. On the other hand, the subsumption operation from sneeze( ·) in (a) to that in (d) could also happen, because that will decrease P, too. Note that the three subsumptions indicated in Figure 5 are all along the cy­ cle of equations depicted as the thick closed curve. This cycle increases the preferences of these subsumptions, because the equations on it tend to have relatively high activation values due to the transitivity energy.

Now suppose (f') is the resulting instance of (f) linked w~th (a) and (b') and (d') is the instance of (d) linked w1th (a) . Then the current configuration is as shown in Figure 6, where unimportant clauses are omitted.

2 The lower subsumption might be in the opposite direc­ tion if it took place after the upper one.

Here let us assume that speech( ·) produces a word. This happens when the phonological form of a word con­ nected with speech{ ·) through a dependency path is suf­ ficiently important in the sense described before. All the perceptual constraints behave essentially the same way. In Figure 6, the phonological form "sneezed" ( ·.·) is con­ nected via the thick dependency path with speech{ · ), and also important because (d') is linked with (a) and hence this "sneezed" ( ·,·) has stronger interactions with the top clause than the other phonological word forms.

If speech( ·) is thus fired and transformed while intro­ ducing a new piece of exterual information about the utterance of "sneezed," then the resulting structure of the relevant part of the constraint will be as shown in Figure 7. Now arises the thick dependency path, which

triggers the subsumption operations indicated by the arrows. As a result, the copy of "sneezed" ( ·.·) in an in­ stance of ( d') is subsumed by the "sneezed" ( · ,·) in (a), so that the equations between the two "sneezed" ( ·, · )s are rendered strong. So the sentence is done.

4 From Production to Comprehension

Here we consider the initial speaker, who becomes the hearer from midst of the sentence. Let us suppose that she begins with the constraint shown in Figure 8. Here

the semantic content to be verbalized is in the top clause. Two thick cycles of equations are shown here, each con­ sisting of two external equations, one weak and the other strong. The weak equations are those between the two agent( ·.· )s. The subsumption operation indicated by the arrow is preferred here because that would increase the mutual excitation of the two agent( ·.· )s, which con­ tributes to the reduction of the penalty function. Al­ though not explicitly shown, another cycle of equations runs through the two sneeze( · )s in (a) and (d), and thus a subsumption operation between them is also motivated here. However, the rest of the discussion assumes the former subsumption.

Here the reader might want to compare this with semantic-head-driven generation (SHDG) [Shieber et al., 1989]. The two subsumptions mentioned above both cor­ respond to retrieval of the semantic head (the minimal grammatical category with the same semantics as the root category to be generated) in SHDG. Our method is more general and flexible, however, because its computa­ tion follows the emergent control derived from dynamics, whereas SHDG is a procedure prescribing information flow. For instance, the above subsumptions are not pre­ scribed at all but motivated on a very general ground depending on the dynamical context.

As indicated by the thick dependency path between speech( ·) and "Kim" ( · .· ), the word "Kim" ( ·.·) is now focused on as a promising candidate for the first word, because the equation between the first arguments of the two np( · .· .· )s is particularly excited due to the cycle of equations running through kim.

Let us assume that the subsumption takes place be­ fore the utterance of Kim. This amounts to hypothes1zmg that the speaker is relatively deli berate rather than reactive, in the sense that internal inferences are preferred to actions. Of course we can encode different ratio of deliberation and reactivity in terms of dynamical parameters which control symbolic operations including actions, in a way similar to Maes [1991].

The subsumption in question results in Fi7ure 10. Since the feature specification agent( ·.·) in (b ) is the

maximum subset of the 01iginal subsumed by agent(·.·) in (a), agent( ·.·) in (b) is not unifiable with the other two. So the dependency between the first arguments of the two agent( ·.· )s in (a) and (b) indicates a contra­ diction, because if these arguments are identical then these feature specifications must unify since a feature is a partial function. In general, a local energy called the dependency energy is defined for each dependency path connecting two terms not unifiable. This energy engen­ ders mutual inhibition among the atomic constraints on both ends of the dependency path and the equations in the path. In Figure 9, therefore, the two agent( ·.· )s in (a) and (b) and the equation connecting their first ar­ guments inhibit each other. Here the agent( ·.·) in (a) will defeat the others because it is in the top clause and hence receives the strongest excitation. So the agent( ·.·) in (b) or the equation connecting the first argument of the twos( ·.·.· )sis inhibited, which renders (b) unimpor­ tant in the rest of the current task. We will thus neglect (b) henceforth.

The subsumption indicated in Figure 9 is motivated because of the dependency path connecting kim with it­ self. After this subsumption, we arrive at the situation in Figure 10. Now let us suppose that for some reason or another the hearer happens to say sneezed before the speaker does. After the input of sneezed, the top clause (a) incorporates a new atomic formula "sneezed" ( ·.· ). Now the first arguments of the two "sneezed" ( · .· )s are connected through a dependency path, which is the same as the one indicated in Figure 7. So subsumptions are triggered also as shown in Figure 7, and the sentence is completed.

5 Concluding Remarks

Joint utterance has been accounted for as a corollary of constraint-based design. The essence of the account is that input and output are tightly coupled as parts of feedback loops constituting a constraint. Transfer of conversational roles in the middle of a sentence hence naturally emerges without recourse to any special mech­ anism. It is simply that the dynamical context around that constraint flips it between input and output. The reported work has been fully implemented. The pro­ gram is written in C and runs in UNIX with X window interface. 3

The present work is related to several other studies in such a way that it integrates and generalizes some aspects of them. First, it is based on the work on reversible natural language processing [Hasida, 1990; Shieber, 1988]. Since our framework is constraint-based, it should fit in the picture of reversible NLP in a strongest sense that sentence comprehension and pro­ duction are based on the same linguistic and extralin­ guistic constraints and the same general procedure to deal with constraints. The cuiTent study is an exten­ sion of Hasida [1991], which is the only work along this strongest sense. Second, our work may be com­ pared with connectionist NLP [Kalita and Shastri, 1987; Waltz and Pollack, 1985]. In this respect, our approach is distinguished in that it captures declarative semantics of logic programs in dynamics and derives control of com­ putation thereof. In the connectionist approaches, either network structure is fixed or control of symbolic compu­ tation is programmed more arbitrarily and less systemat­ ically. Finally, as mentioned before, the above example on intrasentential role switching has a lot in common with reactive planning [Maes, 1991] and time-dependent planning [Boddy and Dean, 1989]. The unique charac­ teristic of our work in this connection is the integration of declarative semantics and computation control again, and practically full first-order descriptive capacity.

Future work includes applications to wider range of problems and extension of the computational architecture. An ultimate goal into the former direction is to implement a full NLP system in the constraint-based architecture as a huge bunch of feedback loops running both the inside and on tside of the system. Regarding the latter direction, we want to tailor a learning algorithm for at least parameters of the potential energy. Also, it is definitely necessary to implement the architecture on massively parallel hardware.

3Its source code is available as a part of ICOT Free Soft­ ware. Please contact the first author for the newest version.