THE REPRESENTATION AND USE OF FOCUS IN A SYSTEM FOR UNDERSTANDING DIALOGS Barbara J. Grosz Artificial Intelligence Center SRI International, Menlo Park, California 94025 ABSTRACT As a dialog progresses the objects and actions that are most relevant to the conversation, and hence in the focus of attention of the dialog participants, change. This paper describes a representation of focus for language understanding systems, emphasizing its use in understanding taskoriented dialogs. The representation highlights that part of the knowledge base relevant at a given point in a dialog. A model of the task is used both to structure the focus representation and to provide an index into potentially relevant concepts in the knowledge base The use of the focus representation to make retrieval of items from the knowledge base more efficient is described. I INTRODUCTION To understand the sentences in a discourse, a computer system, like a person, must have knowledge about the domain of the discourse. However, the knowledge required to understand even simple, reallife domains is so extensive that it will overwhelm a system that does not apply it selectively. This means that the ability to focus on the subset of knowledge relevant to a particular situation is crucial. This paper addresses the problem of focus from the perspective of building a computer system that can participate in a task-oriented dialog. A representation for focus is presented; its use is illustrated by showing how the referents of definite noun phrases are identified. A combination of contextual factors influences the interpretation of an utterance. In fact, what is usually meant by "the context of an utterance" is precisely that set of constraints which together direct attention to the concepts of interest in the discourse in which the utterance occurs. Both the preceding discourse context - - the utterances that have already occurred -- and the situational context -- the environment in which an utterance occurs -- affect the interpretation of the utterance. For a dialog, the situational context includes the physical environment, the social setting, and the relationship between the participants in the dialog. This paper shows how the task and dialog contexts combine to provide a focus on those concepts relevant to the interpretation of utterances in task-oriented dialogs.

Abstract: It has been claimed that production systems have several advantages over other representational schemes. These include the potential for general self-augmentation (i.e., learning of new behavior) and the ability to function in complex environments. The production system language, OPS, was implemented to test these claims. In this paper we explore some of the issues that bear on the design of production system languages and try to show the adequacy of OPS for its intended purpose. I. INTRODUCTION Much of the work that has been done with production systems during the past few years has had as its primary goal the development of systems that are expert in some particular task. The tasks so far addressed include: chemical inference [Buchanan and Lederberg, J 971], medical diagnosis [Davis, Buchanan, and Shortliffe, 1975], discovery in mathematics [Lenat, 1976], speech recognition [Erman and Lesser, 1975; McCracken, 1977], and automatic programming [Barstow, 1977]. Although many of these systems have shown impressive power in the particular task for which they were designed, there remains a question of how suitable the production system representation is for large general problem solving programs. The Instructable Production System (IPS) project at CMU [Rychener and Newell, 1977] is attempting to answer this question. It has been claimed that production systems are capable of learning in a nontrivial way. If this is true, a production system should be able to learn not only facts, but also new behaviors.

A range of different encoding techniques have been developed, along with a number of approaches to applying knowledge. Most of the effort to date, however, has concentrated on representing and manipulating knowledge about a specific domain of application, like game-playing ([14]), natural language understanding ([15], [19]), speech understanding ([8], [11]), chemistry ([7]), etc. This paper explores a number of issues involving representation and use of what we term meta-level knowledge, or knowledge about knowledge. It begins by defining the term, then exploring a few of its varieties and considering the range of capabilities it makes possible. Four specific examples of meta-level knowledge are described, and a demonstration given of their application to a number of problems, including interactive transfer of expertise and guiding the use of knowledge. Finally, we consider the long term implications of the concept and its likely impact on the design of large programs.

Traditional scheduling algorithms (using the techniques of PERT charts, decision analysis or operations rrsrarrh) require well-defined, quantitative, complete sets of constrainls*. They are insufficient for scheduling situations where the problem description is ill-defined, involving incomplete, possibly inconsistent and generally qualitative constraints. The NUDGE program uses an extensive knowledge base to debug scheduling requests by supplying typical values for qualitative constraints, supplying missing details and resolving minor inconsistencies. The result is that an informal request is converted to a complete description suitable for a traditional scheduler. To implement the NUDGE program, a knowledge representation language -- FRL-0 -- based on a few powerful generalizations of the traditional property list representation has been developed.

The Platonic assumption that the world is made up entirely of objects with flat surfaces obviously does not hold; and yet, as with so many other simplifications of reality for the sake of tractability, it has been immensely productive in establishing a paradigm for scene analysis. There is a coherent evolving body of research based on the notion that a polyhedral world is the simplest we can consider without eliminating any of the essential aspects of scene analysis, namely, the picture-taking process, models, lighting, support, occlusion, and so on. The thesis is that once we achieve ways of dealing intelligently with those aspects for a simple, but nonetheless real, world we could then consider the fuzzy world of teddy bears (Michie, 1974) and the like. This should not be taken as suggesting that each of those aspects presents simply a separate, independent subproblem to be solved. The most important question to be faced was how to write programs that coordinate the use of these separate, but interrelated, knowledge systems to achieve sensible picture interpretations. Roberts (Roberts, 1965) was the first to give an answer to this question. We shall examine his answer in some detail, because he exposed in it the issues that became themes of the first decade of scene analysis.

The Open Mind Common Sense project is an attempt to construct a database of commonsense knowledge through the collaboration of a distributed community of thousands of non-expert netizens. We give an overview of the project, describe our knowledge acquisition and representation strategy of using natural language rather than formal logic, and demonstrate this strategy with a search engine application that employs simple commonsense reasoning to reformulate problem queries into more effective solution queries.

Many of the recent expert rule-based systems [Dendral, Mycin, AM, Pecos] have architectures that differ significantly from the simple domainindependent architectures of "pure" production systems. The purpose of this paper is to explore, somewhat more systematically than has been done before, the various ways in which the simplicity constraints can be relaxed, and the benefits of doing so. The most significant benefits arise from three sources: (i) the grain size of a typical rule can be increased until it captures a unit of advice which is meaningful in that system's task domain, (ii) the interpreter can become accessible to the rules and thus become dynamically modifiable, and (iii) meaningful permanent Knowledge can be stored in data memories, not just within productions. Although there are costs associated with relaxing the simplicity constraints, for many task domains the benefits outweigh the costs.

Further progress in the application of computers to many practical fields seems to depend heavily on the success in implementing learning and inductive processes within machines. For example, to develop a consultation system for medical or plant disease diagnosis, prognosis and decision making in general, it is very desirable, perhaps even necessary, to be able to'teach' the system through examples of correct and/or incorrect decisions, rather than by precisely describing the decision process in its full generality and then transforming this description into a computer program. A similar situation exists in computer chess. The development of computer programs playing at the master level (especially the end games) seems to be a formidable task if the programs are not eventually able to learn and improve on their decision making rules through the specific examples of games, rather than by being explicitly told all the rules. Due to easy access to human knowledge about chess and the relative simplicity of testing the results, chess is one of the most attractive testing domains for inductive inference programs.

Programs in the artificial intelligence domain impose unusual requirements on control structures. Production systems are a control structure with promising attributes for building, generally intelligent systems with large knowledge bases. This paper presents examples to illustrate the unusual position taken by production systems on a number of control and pattern-matching issues. Examples are chosen to illustrate certain powerful features and to provide critical tests which might be used to evaluate the effectiveness of new designs.

See also: Stanford Heuristic Programming Project Memo HPP-77-25Proc. IJCAI-77: Fifth International Joint Conference on Artificial Intelligence, pp 1014-1029