An Interactive Program for Conversational Elecitation of Decision Structures

AN INTERACTIVE PROGRAM FOR CONVERSATIONAL ELICITATION OF DECISION STRUCTURES

Antonio Leal* and

Judea Pearl

School of Engineering and Applied Science University of California, Los Angeles

An interactive computer program has been designed and implemented that elicits a decision tree from a decision maker in an English-like conversational mode. It emulates a decision analyst who guides the decision maker in structur­ ing and organizing his knowledge about a particular problem domain.

Decision analysts are often called upon to assist in the solution of planning problems ranging over a large variety of domains. In most such cases the decision analysts possess less specific knowledge about the problem domain than their customers, and their contributions are confined primarily to the phases of formalization and optimization. While optimization is usually performed on electronic computers, the formaliza­ tion phase invariably has been accomplished manually, using lengthy interviews with persons intimately familiar with the problem domain.

The major drawback of manual interviews is their length and cost. Since real-time analysis of decision trees is beyond the limitation of human computational capability, it invariably happens that many hours of interviews are spent on eliciting portions of the decision tree which do not have decisive bearing on the problem(s) at hand. This fact can only be discovered at a later stage once the problem structure is formal­ ized, and a sensitivity analysis has been conducted on an electronic computer. During the interview itself, however, it is impossible for the analyst to process the entire information obtained by him up to that point, and to select the optimum course for conducting future inquiries.

This paper describes an initial attempt to automate the formarization phase using an inter­ active computer system which guides the decision maker through a structured English-like dialogue and constructs a decision tree from his responses . The objectives of this work are threefold: (1) to provide the decision analysis industry with a practical automated tool for eliciting decision trees in cases where manual elicitation techniques are either infeasible or non-economical, (2) to cast the decision analysts' behavior into a formal framework in order to examine the principles

* Portions of this work are contained in Antonio Leal's Ph.D. dissertation in the School of Engineering ~nd Applied Science at UCLA, June, 1976. He is currently a Research Scientist at Perceptronics, Inc., Woodland Hills, Calif. Work reported herein was supported in part by NSF Grant GJ-42732.

governing the elicitation procedure and gain a deeper understanding of the analysis process itself, and (3) to provide experimental psycholo­ gists with an automated research tool for coding subjects' perception of problem situations into a standard and formal representation.

The approach centers on the realization that the process of conducting an elicitation dialogue is structurally identical to conducting a heuristic search on game trees, as is commonly practiced in Artificial Intelligence programs. Heuristic search techniques, when applied to tree elicitation, permit real-time rollback and sensitivity analysis as the tree is being formulated. Thus, it is possible to concentrate effort on expanding those parts of the tree which are crucial for the resolution of the solution plan. The program requires the decision maker to provide provisional values at each intermediate stage in the tree construction, that estimate the promise of future opportunities open to him from that stage. These ~rovisional values then serve a role identical to a heuristic evalu­ ation function in selecting the next node (scenario) to be explored in more detail. The difference is only that the heuristic function is supplied initially by the programmer and it is defined over the entire state space, while the utility values are supplied by the decision maker interactively with the elicitation program.(FIG. 1)

The program is domain independent, as it assumes no prior knowledge specific to any problem environment, and can therefore be used as a universal decision-aiding tool. Although the program makes almost no effort toward language understanding, the conversation seems to follow a natural discourse. This is due to the simplicity of the structure underlying decision trees. The user's verbal responses are mapped directly into one of the following data types: events, actions, likelihood relations, value estimates, or experiment descriptions. The final result of the computer interview is a "solution plan" that recommends an action for all anticipated contingencies.

• 0 SECOND PLAYER'S TURN TO MOVE

HEURISTIC SEARCH ON GAM£ TAUS

DECISION TAU ELICITATION

• OBJIECT 1$ TO FINO THE PATM I'L.AN) 'MTH THE HIGHEST HEURISTtC VALUE Hill WITH THE MINIMUM NUMaf.A Of NODE EXP~IONS.
• 08JECT II TO FIND THE P'ATH (PLAN) WITH THE HIGHEST UTILITY U(l) WnH THE MINIMUM NUMifR OF QUUTIONS.
• COM"-ETE TRE£ UNAVAILABlE EXPliCITLY. IIMI"l.ICITL Y CONTAINED IN GAME RULES.)
• COMPlETE TAU UNKNOWN TO THE ANALYST. IREIID£1 IN THE DECISION MAKER'S KNOWLEDGE.)
• EXP~ON FOt.LOWIITATE TftANIITION RULES (LEGAL MOV£1 ).
• EXPAHIION FOlLOWS THE DECISK>N MAKER'S 'ERCEI'TION Of EVENT/ACTION RELATIONSHII'S.
• HEUIUmc fUNCTtON I'AOVID£0 IY ANALYST.
• "'OYIIIONAL VALUES MOYIDED BY DECIStON MAKER.
• HEURimC FUNCTtON GUIDES SIARCH.
• ~IIIONAL VALUES D£TERMIN£ NEXT QUESTION.
• MINI.auJC ROLLBACK.
• ExnCTI.fiiiAX ROLLBACK.
• Tf.ftMINAL NOOU OETEAMINIEO BY RULES. (WIN/LOIS. I
• TIERMINAL NOOIES DIETIERMINIED BY DECISION MAKER.