Be Brief, Be to the Point, ... Be Seated or Relevant Responses in Man/Machine Conversation

I. Introduction.

Artificial Inte lligence systems developed during the 70's were based on Knowledge Representation. The applications were supposed to showcase the different types of representation, such as frames, scripts, scenarios, or expert-systems. The dialogue problern was partly neglected . Some programs (6) were then related to written dialogues; their primary purpose was to really understand the attitudes of botb parti­ cipants, but they didn't mind engaging in dialogue. At the same time, theoretical research has been pur­ sued on this point, but has not always given rise to practical applications (5), (2), .··

Following this path, we have tried to determine the t ypes of knowledge implicated in human conversa­ tion. Even if they arenot always well defined, the­ re are some rules which govern the elaboration of the sentences uttered in conversation. In this paper we will focus on the knowledge a program needs to cooperate in a dialogue . After abrief overview ot the works that have influenced our research, the pa­ per presents examples of possible dialogues. We then describe how the different kinds of knowledge repre­ sentat ions are built and used.

II. The role of the machine in a dialogue.

Most studies in the theory of Speech Acts (Ii), (!) agree on Grice's cooperation principle for ana­ lysis of human dialogues (4). A conversation is a relational act in which each participant is required to take an active part : else it would be a monolo­ gue or a dictatorial lecture! Each interlocutor must take into account the other's goal . No one can be engaged in a dialogue if he can't explain his own ut­ t erances, or cannot specify what he couldn't under­ s tand in someone else 's previous statements.

To detail his principle, Grice proposes some axioms that must be respected, otherwise, as your interlocutor assumes your stat.~ment was intentional, he will make incorrect inferences.

We have established that to be considered as a help, a question-answering system must respect the three following principles :

• be able to participate in a real dialogue, with more than just "one question- one response",
• be able to restart the dialogue when some pro­ blern prevents the successful operation of the system
• be able to justify itself,i.e. the chain of rea­ soning it used to produce a previous answer.

III. Examples of dialogues.

In this paper, we describe dialogues where both participants are involved; the user expects from the machine a well-formed answer (i.e. not in some jar­ gon) , aud the machine doesn' t limi t the user' s part to a choice among a set of predefined questions. We are currently working on an application in which a program takes the place of the"yellow pages" of the french telephone directory (the professional listings : suppliers of goods and services).

This system assumes that the user's goal is to obtain a phone number; when a problern is posed, it searches for someone who might solve it. The system has a deterministic parser (7) which analyzes the user's utterances; it uses a semantic network with different kinds of links. Each listing is represen­ ted by its name, i.e. a .concept and a list of sen­ tences describing the activity of the supplier (8).

Example EI (illustrates the explanation process)

Ul I would like to move my safe.

SI I suggest an art mover or a piano mover.

U2 Why a piano mover ?

S2 Because, both your safe and a piano are very heavy.

U3 Why an art mover ?

S3 Because your safe may contain valuable objects, and an art mover handles things of value.

In Ul, the topic recognized is "to move a safe". Then, the reasoning process (REASON) looks for an answer to this request : first it chooses the lis­ tings whose name contains the concept "move" or the concept "safe", then it searches the list of senten­ ces describing the activity of the supplier. Here it finds nothing, so i t uses the "synonym" reasoning process (it examines the links between the concepts in the semantic network, and their possible combina­ tions, e .g. "sort of" and "part of" give "part of"). REASON finds that safe is the "approximate synonym"

of "piano" (both heavy) and "valuables" (safe roay contain objects of value). Then it verifies that the listing "piano mover" and the listing "art roover" contain inforroation which agrees with the question the user asks, and generates SI. The user suprised (and he has reason to be!) questions in U2. The irr­ temal representation of this question is passed to the dialogue process (DIALOG). It recognizes a cau­ sal question, concerning a prior topic : to roove a piano. Then it roust find the path that led it to this result and it roust constitute an explanation which is, as rouc~ as possible, tailored for the user. In order to carry on the dialogue with good results, the systero roust incorporate the following three re­ presentations : the topics that have already be~n roentioned, the different chains of reasoning the systero has used, and th~ knowledge level we suppose the user has . We will develop below the roethods used to build these representations. Using thero, the systero can give coherent explanations. When it is asked about the piano roover, it uses its topic knowledge to selection only the relevant inforroa­ tion froro the reasoning (52), and the saroe process with S3. In building these answers, the systero roust take into account the knowledge we suppose thE user to have, . so as to avoid an overly detailed explana­ tion.

Example E2 (underlines the capacities to follow the changes of subject, and restart the dialo­ gue) .

• Ul I would like the phone nurober of an oriental restaurant.
• SI Would you prefer a vietnaroese, a japanese or a chinese one?
• U2 I don't care .

S2 In which part of town?

• U3 First give roe a phone nurober for a radio taxi
• S3 You have the following listings unde r Taxi : Hello Taxi (111 - 11-1 1), Night Taxi(222-22-22).
• U4 In that case, I would like a restauraut in the 5th district.
• S4 You have :

chinese restauraut :"The Mandarin" 333-33-33 japanese restauraut :"The rising sun"444-44-44

After analysis, we know that Ul is an "object"· deroand for an oriental restaurant. REASON works only on the couple (predicate, object): dine at a restau­ rant. Thus, it finds the following listings : chi­ nese, russian, japanese restaurant, fast food, ... DIALOG obtains this list . To roake a selection, it begins by looking for a roodifying criterion in the user's request. It finds : oriental, which qualifies the type of restaurant . There reroain the chinese, vietnamese restaurants, which are proposed to the user (SI) . As he refuses to roake a choice, another question roust be constituted. First, we try to use the criteria (topics) which allowed us to deterroine the current listin~s . Then we make a search on the information known about the listings. But these pro­ cedures fail. If the systero contained the fact that vietnamese food was "spicy'' and japanese food was "non-spicy" ,. the system would have been able to of­ fer a further choice. In this ~ase, the criteria were " richer" than the first choices presented; but not in our exarople E2 . fhe last solution we have foreseen is to ask a question about the restauraut location (S2). In U3, the user changes the topic, he asks for a radio taxi. After a new search , REASON finds the listing taxi. DIALOG verifies that it ope­ rates by radio call, and proposes S3. The user may then answer S2, and asks for a restauraut in the 5th district. The system then recognizes a topic already discussed, it doesn't make a new search, but makes a selection among three types of r estauraut chosen before. It is possible to compose S4.

IV. The representations built by the sys t em.

The first representation we show here is the chronological record (CR). It connects all the others which we present below. It es tablishes the link bet­ ween the different utterances and indicates "who" says "what", and in whi ch con text an utterance has been said.

In this structure, we find, for each utterance

1. who said it, the user or the syste~.
2. the topics developed in this utterance . By topic, we roean the subject of the dialogue, what we are spea­ king about. In this part, we used the results obtained by Grau's system (3). In he r work, the topic is repre­ sented by a set of schemas which are connec ted by different kinds of links (hierarchical, descriptive, .. ) Her systero offers the possibility of integrating a sentence in its context, that is to relate it to the topics which have already been discussed. During the dialogue, the jifferent topics are developed both by the user, when he introduces a request or further specifies it, and by the system when REASON makes approximations. Among these topics, we estab lish a hierarchy, which underlines the fact that some "de­ tours" roay appear after a user reques t without a com­ plete change of subject. This hierarchy leads us to build a tree whose root is the user's initial request. Wehave considered that REASON can't introducc a com­ pletely new topic; it cau only produce different kinds of "detours". The topi cs developed during the dialogue constitute a list of trees (cf Fig 1). Each entry of CR points to a node inside one of these trees.

3) the system's chain of reasoning. In the examples we dernarrstrate the necessity of different levels of detail in the chain of reasoning so as to present a "good" justification. ln an order to obtain those levels, we have represented the reasoning as a tree . The sets of procedures which form REASON constitute an implicit hierarchy; this hierarchy is reflected in the structure of the "reasoning tree" we produce. As a one-time procedure (for each version of REASON) we build a tree which represents all the possibili­ ties of REASON ( the image of the algorithm : IMAL­ GO). Each time REASON is called, a new sub-tree is extracted, corresponding to the particular execution (the image of the execution : IMEXEC). IMEXEC is the trace of the reasoning used to solve a certain pro­ blem. It will be used by the explanation process (EXPLAIN) .

4) the user's representation. In CR, we score a pointer towards a representation of the user as we currently define it (it is dynamic). It is composed of two e lements : the knowledge level the system at­ tributes to the user, and our current definition of the us er's problem. The knowledge level is used to avoid to drown the user in details when the system explains its reasoning. It is based on IMALGO. The r epresentation of the user's problern is composed of the couple (predicate, object) which was used to call REASON. Joined to this is a list of concepts which modify one of the couple's two elements. We see in E2 that it ~s used to solve some cases of ambiguity.

It is the set of all these representations inter­ connected byCR which allow us to manage a dialogue, t aking into account as best we can the three points unde rlined above :

• parti cipation in more than "one question - one answer" dialogue,
• restart the dialogue,
• self-justification.

V. The use of these .cpresentations for the dialogue

To enable us to accept questions regarding the whole dialogue, the CR is updated at each utterance, A new entry is created showing who spoke, the topic developed, the user's representation as it is current­ l y pe r ceived and the chain of reasoning.

Le t us examine what happens when a user's utter­ ance is addressed to the system. It is firsc analy­ zed. Then DIALOG acts in different ways, depending on the kind of question and the topic developed If the question contains a topic change, REASON is called to search the knowledge base (in E2 : Ul and U3). If it is a question concerning a prior topic, EXPLAIN is called (in EI : U2). Otherwise it is trea­ t ed as information to resolve an ambiguous point (in E2 : U4). At the end of the reasoning process, a good answe r either has or has not been found.DIALOG will then transmit the good answer to the generation pro­ cess, otherwise it tries to determine a question, in order to pursue the dialogue (see E2).

When EXPLAIN is called, it first decideey, by .re­ ferring to topi c and CR,where this problern has been solved. Then it retrieves the part of IMEXEC concer­ ned by the question, and taking into account the knowledge we assumes the user has, it builds an ex­ planation. After that, the user's representation is modified so if he asks again for an explanation we may give him more details.

We find in the following diagram a resume of this process.

VI. Conclusion

Our goal is to give control of the dialogue back to the user, to permit him to change the subject, to backpedal, and to question the system's responses. In any_ case, if the system can't solve the whole pro­ blem, ~t must be able to efficiently aid the user to modify the request. To this end, the system's ques­ tions take into account the work already accomplished and indicate to the user the various paths possible to arrive at their goal.

During a conversation, each participant assumes an enormaus amount of knowledge an the part of the other(s). This is what is shown in Grices's maxims. He points out that the violation of any of the axioms d~rived from the cooperation principle is given signi­ f~cance equal to that of the actual contents of the utterance. This is why our system is constructed to act in accordance with the~~ principles. The s~stem's utterance must be clear so that the user doesn t have to search for hidden meanings.