Figuring Out What the User Wants: Steps Toward an Automatic Yellow Pages Assistant

FIGURING OUT WHAT THE USER WANTS - STEPS TOWARD AN AUTOMATIC YELLOW PAGES ASSISTANT

Anatole Gershman·

Schlumherger-Doll Research Ridgefield, Ct. 08877

1. AI Dubin Auto & Plate Glass Works: 1171
2. Stuyvesant Av.: 373-2555
3. Allstate Glass Co. : 400 Hamilton Blvd.: 757-5036

Let us analyze the kinds of "intelligence" A YPA must have in order to produce the above behavior. First , it has to extract from the user's request that the user has a car, and that the windshield in this car is broken . Second, A YPA must infer that the user wants to replace the windshield. We call this kind of processing request analysis. Request analysis requires: ( 1) an ability to extract information out of natural language input and express it in some language independent representational system; (2) knowledge about objects and actions and their relationship (e.g., the knowledge that windshields are car parts made out of glass, that glass parts are not repaired but replaced , etc.); (3) knowledge about the intentions of Yellow Pages users (e.g., if the user informs the system that he has a damaged item, he probably wants to repair it), and finally, (4) the inferential capabilities to reason about the user's intentions.

At the second stage of request processing (which we call requt·st answering) the system must be able to find the relevant entries in the Yellow Pages and select some that are in the vicinity of the user.

II THE KNOWLEDGE BASE

A YPA uses the New York Telephone Manhattan Yellow Pages data base in which entries for individual businesses are grouped into categories such as : "Automobile Dealers.-New Cars", or "Glass­ Automobile, Plate, Window, Etc.-Dealers." Each entry contains the name of the business establishment, its address and its phone number. Each category has an identifying number (e.g, A V480 is "Automobile Dealers.-New Cars".)

A YPA 's semantic and pragmatic knowledge is stored in the form of a hierarchical associative network which we call YPNET. A fragment of this net is shown on fig. I .

The core of the net consists of nodes which represent aeneric concepts such as ·cAR, ·PERSON, ·REPAIR, etc., and links which define the relationship

ABSTRACT

An experimental system, A YPA. for automatic Yellow Pages assistance is described. The system, which operates in the domain of automobiles, automobile parts , and related objects, reads the user's request in simple English, analyzes it and represents it in terms of the system's conceptual primitives. From this, the system tries to figure out the intent of the request and formulate a Yellow Pages query. It paraphrases the request back to the user in English and searches its data base for the relevant Yellow Pages categories. The system serves as a research vehicle for experiments with its various components and user interfaces.

I. INTRODUCTION

This paper describes an experimental system, A YPA, for automatic Yellow Pages assistance. The system, which operates in the domain of automobiles, automobile parts, and related objects, reads the user's request in simple English, analyzes it and represents it in terms of the system's conceptual primitives. From this, the system attempts to infer the intent of the request . and formulate a Yellow Pages query. It paraphrases the request back to the user in English and searches its data base for the relevant Yellow Pages categories.

We view this work as a research in natural language access to databases (1 I. (2), (3). In order to provide nat ural language access to a database we have to create an extensive structure, external to the database, which can serve as a bridge between the concepts used by people in talking about the items in the database and the database organization.

The program aims at performing the following type of interaction with the user:

USER: My windshield is broken, help.

A YPA: I understand that you want to replace the windshield in your car. Where are you located '!

USER: Hamilton and Stuyvesant in Springfield.

• A YPA: llere are some establishments ncar you that might be able to help you:
• The work dcs.:ril'>ed in this d<X·umcnt w;as t>crformcd while the author was at Uc:ll Laboratories. Murruy llill , N.J. 07974.

among concepts in A YPA 's world. There are two major kinds of links in YPNET: vertical (hierarchical) and horizontal (associative). Vertical links represent the hierarchical organization of the nodes in the net. The vertical links are the usual ones: ISA (is a) which goes from a more specific concept to its generalizations, and REF (refinement) link which goes from a general concept to its refinements [4) .

Every node in YPNET is considered to be a frame with various attributes. For example, *REPAIR has attributes ACTOR and OBJECT. The ACTOR of *REPAIR must be a *PERSON and is called a repairman with a corresponding node *REPAIRMAN. Horizontal links in YPNET link frames and their attributes.

Information contained in the network is used by A YP A in four ways:

• Retrieval of an item from the net (e.g., ACTOR of *REPAIR) .
• Verificati'on of a predicate (e.g., "is a mechanic a person?", i.e., (JSA *MECHANIC *PERSON) = True or False).
• Finding a concept which relates two given concepts (e.g., *CARREPAIR relates *CAR and *REPAIR) . This is used heavily in the language analysis.
• Finding the nearest concept with a given property. For example, finding the nearest concept which corresponds to a Yellow Pages category.

III REQUEST ANALYSIS

Request analysis begins with a process which takes a natural language sentence and produces an expression representing its meaning. We call it Conc·eptual Analysis [5]. We use a modified version of Conceptual l>ependem:y (('J)I notation 161 as our n:prcsentational system, using primitives from A YPA 's knowledge base.

The conceptual analyzer used in A YPA is written in the general fmmcwork described in [7). It is a dictionary-based production-like system. This is essentially a rule-based system with rules dynamically assembled from information contained in the dictionary, syni<Kiic fmmcs. and most importantly, YPNET, which is the repository of the system's semantic and pragmatic knowledge.

A. Immediate Inferences

Consider the following example:

My windshield is broken. I have a 1979 Ford.

Having analyzed a sentence. A YPA activates all the inference rules indexed by the head of the conceptual expression. There arc two rules stored under the conl·ept *DAMAGE whil·h underlies such verbs as "to break". "to dent". "to smash". etc. Their content can be paraphrased in English as:

Rule Ia: IF I) the physical state value of an object is equal to -I (damaged) and 2) the user's goal has not been asserted

THEN assert the user's goal to repair the object.

Rule I b: IF I) the physical state value of an object

is equal to -2 (destroyed) and 2) the user's goal has not been asserted

THEN assert the user's goal to replace the object.

Thus. A YPA tentatively asserts that the user wants to repair his broken glass-autopart. <This goal will later be changed to "replace".) If a different goal is explicitly mentioned later. it will replace this one.

B. Goal Finding and Sharpening.

When all of the user's request has been read, A YP A goes to the next stage which we call goal./inclin~:. At this stage, the system checks if the user's goal has been asserted at the input stage and if it hasn't, A YPA tries to infer it using its general rules for inferring the user's goal. There are several such rules and here is one example:

Rule 2: IF I) there is a physical object in the short term memory not controlled by the user

THEN assert the user 's goal to buy the object.

Controlled in the above rule means either owned. rented. or occupied. If the user simply says: "car". A YPA. using Rule 2. will assume that he wants to buy a car. If the user says: "My car", A YPA will not assume that he wants to buy a car since he already has it.

After the goal-finding stage, the system has a conceptual expression representing the system's idea of the user's goal. This expression may still be too general by comparison with the user's real goal. For example, when the user says: "I want a car" the system asserts that the user's goal is to control (buy or rent) a car. If the user says: "I need a garage" the system asserts that his goal is to control a garage. In reality, the first request usually means buying while the second renting. We could ask the user for clarifications at this point, but this may be annoying especially when the circumstances and the object strongly imply a preferred way of controlling it. Thus, we need another stage of request processing which we call xoa/-sharpening. This 1s done by activating the goal-sharpening rules stored under the conceptualization heads.

C. Goal-Elaboration.

Having found and sharpened the conceptual expression that represents the system's idea of the user's goal, A YPA goes into the last stage of request analysis which we call goal 1.'/abvrativn. At this stage, A YP A goes through all the concepts in the goal conceptualization and tries to fill the remaining gaps in them. Consider, for example, the following request :

My carburetor is broken . I have a 1979 Ford Fairmont.

The system decides that the user wants to repair a broken carburetor but, before the goal-elaboration stage , it did not associate the carburetor and the user's Fairmont. Since there were no other cars mentioned, A YPA assumes that the broken carburetor is a part of the user's Fairmont.

Goal elaboration ends the request analysis stage . Now the system expresses in English what it thinks the 'Jser's goal is and goes into the request answering stage

IV REQUEST ANSWERING

Answering a user's request may be a complicated process which requires both specific knowledge about information organization of the Yellow Pages, and "normal" pragmatic inferences, for example: "if you want to find an object part and do not find it, try to find the whole object." The Yellow Pages categories cover the world in a patchy and inconsistent way . For example, the Yellow Pages user who wants to repair a carburetor should know that the category associated with a car part is relevant io both buying and repairing of the part and look under "Carburetors". This information is implicit in the assumed model of interaction between the user and the Yellow Pages and must be made explicit if we want to usc it. This is not limited to l'ar parts. Implicit assumptions arc made about nearly every Yell ow Pages category . Businesses and professionals arc assumed to perform actions usually associated with them. physil·al objects are ass.umed to be repaired, bought. sold, or rented . We have made these assumptions explicit by attaching specitlc search rules to the concept nodes and to the user's goals.

V SOME FACTS AND CONJECTURES

The work described in this document was an experiment in trying to identify the knowledge needed for an intelligent Yellow Pages assistant. The program was used as a vehicle for experiments with various algorithms of conceptual analysis . associative network organization and searches, and user interfaces. The network consists of 85 concept nodes, 46 of which have Yellow Pages pointers. The total number of links is 223. The natural language part has a vocabulary of about 150 words. This is a long way from a full-scale Yellow Pages assistance system which would require 4500 catego ri es. However, although we have experimented with a very small fraction of the Yellow Pages (about 1%), we have almost completely covered the area of auto buying and repairing. There is no reason to think that other parts of the Yellow Pages would give a significantly greater branching factor for the network .

"(he natural language part is by far the most difficult and critical in the whole project. However, its development crucially depends on the development of the associative network since the language analyzer takes most of its information from there . In fact , we have experimented with an interface which knows next to nothing about English syntax but combines the meanings of the words in the user 's requests directly using the network. This produced an imperfect but very usable interface which we used for testing the network itself.