Artificial intelligence

Steven Gillis, Walter Daelemans & Koenraad De Smedt


Handbook of Pragmatics Manual (1995)
© 2007 John Benjamins Publishing Company. Not to be reproduced in any form without written permission from the publisher.


1. Introduction

Artificial intelligence (AI) is a branch of computer science in which methods and techniques are developed that permit intelligent computer systems to be built.1 These systems allow the synthesis of different aspects of human and animal cognition: perception, action, communication, problem solving, and learning. We will not be concerned here with the question whether these systems are really intelligent; this is a controversial philosophical issue (see e.g. Copeland 1993; Searle 1984; Pylyshyn 1984; Harnad 1989; Hayes et al. 1992). The meaningful use of a natural language in order to communicate is considered to be a task requiring intelligence, even if the ability of people to speak and understand everyday language were not related to other cognitive abilities.

Mastering language has always been one of the primary goals of AI, not only because language is intimately tied to thought and is the principal means of conveying ideas, but also because of the sheer amount of knowledge it takes to understand language itself. AI therefore sees linguistic and other intelligent tasks as complex information processing problems. Consequently, the use of techniques for the aquisition, representation and application of knowledge is central in AI. The main research questions to be addressed in an AI approach are which knowledge sources are necessary, which problem solving strategies should be used, and how all of this can be represented, stored and processed on a digital computer. Much of the research in AI has led to theories of problem solving and knowledge representation in general. Language processing tasks such as production and interpretation are often seen as particular instances of more general problem classes. This has led to the use of powerful paradigms, e.g. parsing as deduction, parsing as search, language generation as planning, etc. (see Allen 1994, for a recent overview).

The aim of AI with respect to language is to develop computational models of the knowledge and the processes involved in executing linguistic tasks including speaking and writing, understanding, learning a language, and several more specific skills such as translating and correcting. The motivation can be to use these models as a basis for theories about human language processing (Dijkstra & De Smedt 1995), but it can also be to study the formal, mathematical properties of languages or the computational properties of language processes. The computational study of natural language is often referred to as natural language processing (NLP) or computational linguistics (CL), although not every computational linguist would see his/her work as belonging to AI. Computational linguists with a background in linguistics or theoretical computer science (in particular formal languages and automata), tend to concentrate on syntax and model-theoretic semantics. The applied wing of CL aims at solving practical problems, for instance by building and commercializing automatic translation aids or natural language interfaces to databases. This is often called language technology or linguistic engineering.

In this text, we will introduce only the central assumptions and methods of AI in general, and of CL in particular. There are several good textbooks and reference books that can be used to get a deeper knowledge about the concepts introduced in this chapter. Two recent textbooks on AI are Winston (1993) and Luger & Stubblefield (1993). They also include chapters on CL formalisms. The Encyclopaedia of AI (Shapiro 1992) and the Handbook of AI (Barr & Feigenbaum 1989) can be used to find brief introductions to all subfields and most concepts in AI and CL, and contain numerous references to the AI literature. Two excellent textbooks especially devoted to CL are Gazdar & Mellish (1989a, b) and Allen (1994).

Computer programming is an essential skill for anyone who wants to develop AI models. Languages like Lisp and Prolog are especially suited to implement the formalisms discussed in this chapter. Winston & Horn (1989) and Norvig (1992) are excellent textbooks to learn how to write AI programs in Lisp. Bratko (1990) and Flach (1994) do the same for Prolog. Gazdar & Mellish (1989a, b) introduce the most important CL formalisms together with their implement-ation, and exists in both a Prolog and a Lisp version. Pereira & Shieber (1987) is a classic introduction for learning how to implement CL formalisms in Prolog.

The remainder of the chapter is organized as follows. After a brief note on the history of natural language processing in the framework of AI, the central aims and methodology of AI will be introduced. We will then turn to the notion of knowledge in AI: its representation and use, and an overview of the principal formalisms of knowledge representation. Next we will discuss how knowledge representation is put to use in the various strata of the linguistic system, and we will devote special attention to pragmatics-related issues.


2. A brief historical note

In the early sixties, a number of computer programs were devised that enabled people to communicate with computers in natural language. For instance, Baseball (Green et al. 1963) enables a user to query the system about the dates, locations, teams and scores of baseball games. Baseball answers questions like Who beat the Yankees on July 4? The system is an example of a natural language interface to a database: the user enters natural language text which is transformed by the system into a formal query. On the output side, the retrieved data are presented to the user in the form of a natural language sentence. Other examples include Protosynthex1 (Simmons et al. 1964), a question-answering system that has as its domain the contents of a children’s encyclopedia, and Student (Bobrow 1968), a system that is able to find sets of equations in algebra story problems and solve them. Lunar (Woods et al. 1972) answers question about lunar rocks; it is one of the first systems using a sophisticated linguistic formalism, augmented transition networks (ATNs) to process natural language (Woods 1970).

One of the most famous examples is Eliza (Weizenbaum 1966), a program that converses with its user in English by accepting any input and responding more or less appropriately. A particularly popular ‘impersonation’ of the program is the simulation of a Rogerian psycho-therapist conducting an initial interview with a patient. The dialog between Eliza and its patients looks sophisticated at first sight, as can be seen in the following abstract:

Eliza: Earlier you said that you were having trouble with the computer.
Patient: That’s right and it hasn’t got any better.
Eliza: What does that suggest to you?
Patient: That computers are no use.
Eliza: How would you react if machines took over?
Patient: I think it would be a disaster.
Eliza: Does anyone else think it would be a disaster?
Patient: Yes quite a lot of people.

This dialog is taken from a mini-version of Eliza (McTear 1987). The program does not really understand the input: it scans the input for particular keywords and then generates an automatic response. For instance, the phrase I think triggers a response asking if also other people have the same opinion. It also uses particular phrases that are meant to show interest by simply reflecting the patient’s words or to prompt the patient for further input (as for instance, What does that suggest to you?). Of course, the particular communicative setting, where it is generally the patient who talks and the therapist prompts the patient, enables the program to carry on this superficial conversation strategy. However, the fact that even psychotherapists entertained the idea that a refined Eliza might be able to substitute a human psychotherapist (Weizenbaum 1984) suggests that artificial language users can ultimately pass the Turing test (Turing 1964), which would mean that humans are not able to distinguish a human from an artificial language user.

More importantly, Eliza illustrated some general purpose heuristics that can be used to model conversational behavior. Heuristics are strategies or guidelines for solving problems. This line of thinking has been pursued in later research on conversational computers and in intelligent interfaces to software programs.

The early attempts at having computers understand and produce natural language are fairly restricted in a number of respects. Only a very limited number of topics can be talked about using a restricted subset of the language. Furthermore, some of these systems look for keywords in the input that trigger particular responses, so that no serious linguistic analyses have to be performed. And finally, dialog is restricted to questions and answers, and no further transactions are possible. In this respect the early systems represent a result oriented approach to language processing, i.e. the main emphasis is on satisfying or impressing the user, rather than on cognitive simulation. Later approaches did in fact adopt a more cognitively and linguistically motivated perspective. Shrdlu (Winograd 1972) can be seen as one of the earliest examples of such an approach.

The domain of discourse of Shrdlu is a tiny model world of colored blocks, pyramids and a box, all of which can be manipulated by a simulated robot arm. (See the Blocks World model visually presented in Winograd 1972: 12.) On a screen, the system’s manipulations in the Blocks World are projected, and the robot is able to converse in writing with a person. The person can ask the robot to stack blocks, put them at different locations, etc., or ask the robot questions about its understanding of its world. For instance, a person can order the robot to Put the blue pyramid on the red block or ask How many things are on top of the green cube?

Clearly, the robot needs some nontrivial sense of language understanding to carry out such orders or describe the state of affairs. The system is able to detect the ambiguity in the sentence Put the green block on top of a red one; it would ask the person if by on top of she means directly on the surface or anywhere above (in case there was already another object on the red block). It also understands that a red block means no matter which one. Moreover, the system contains knowledge about how to intelligently stack blocks, for instance, that it is impossible to put a block on a pyramid, and that in order to put a block directly on another one, the second block has to be cleared first. In addition, the system could learn new words and their meaning, for example steeple.

One of the key innovations that Shrdlu embryonically established is the systematic representation and use of two interlocking kinds of knowledge: linguistic knowledge, pertaining to the syntax and the semantics of the language, and also world knowledge, encapsulated in a pragmatic component. It was made clear that understanding and producing natural language requires substantial amounts of knowledge about the domain of discourse, as well as reasoning about the structure of the discourse. It also became clear that handling the knowledge needed in a toy world is one thing, but designing a system for the real world is another. Scaling up a system is a formidable problem which involves gathering vast amounts of knowledge and finding out how it relates to the processes of language understanding and generation.

The importance of knowledge, especially background knowledge, and the ability of the language user to bring that knowledge to bear on the process of language comprehension and production, has been widely recognized in a number of approaches that have been traditionally labeled pragmatic, such as speech act theory, discourse processing and conversation analysis. The added value of an AI approach in this respect is the requirement that knowledge of whatever kind has to be dealt with explicitly in order to arrive at a working program. AI research provides a whole range of techniques to support the design of a knowledge base, its formal representation, and the implementation of the mechanisms to manipulate the knowledge. The whole can be tested by means of computer simulations, and shortcomings can be traced.

In conclusion, the introduction of specific language processing techniques in AI systems such as Shrdlu have resulted in a new type of human-computer interaction. Later systems generally incorporate knowledge about syntax and semantics for parsing and generation of sentences, discourse representation, text planning and dialog management facilities. Moreover, a detailed domain model and explicit models of the user are added. User models infer the user’s knowledge, goals and plans, which are needed to tailor the system’s interactions with the user. Knowledge about the domain provides the means for inferring connections between objects and events that are often left implicit in natural discourse. It also creates the basis for inferring new knowledge from known facts.


3. The physical symbol system hypothesis

Allen Newell received the 1975 Turing Award for showing that computers can be seen as general symbol manipulators and not just as number crunchers. With Herbert Simon, he formulated the physical symbol system hypothesis (PSSH; Newell 1980), a central hypothesis in both AI and cognitive science. According to the PSSH, concepts are mentally represented by physical symbols. The term physical means that the symbols should be implemented in some sense in physical reality, for example as electrical states in a computer memory. Relations between concepts are represented by structures of physical symbols. Mental processes are represented by physical processes that can be written as programs manipulating physical symbol structures (see Figure 1). Programs are also represented as symbol structures, so that they can be manipulated by other programs. Because of this recursion, learning can be explained within this framework: the mind can change itself in useful ways by manipulating its own mental structures and programs by means of a learning program. According to the PSSH, the manipulation of symbol structures is necessary and sufficient for intelligent behavior.

Figure 1. Mental functions are represented by processes operating on physical symbol structures.

A consequence of the PSSH is that intelligence is independent of the physical level, and can be described at an implementation-independent level. In other words, the hypothesis works regardless of whether physical symbols are located in the human brain as networks of neurons, or in a computer memory as electrical states.

The PSSH leads to a research methodology in AI in which a particular task or type of intelligent behavior is simulated by designing a computer program manipulating symbolic representations. A program translating English into French by manipulating symbols representing English and French words and using symbolic representations of the translator’s knowledge, is an instance of a program simulating intelligent linguistic behavior in a symbolic way.

The approach followed in designing an AI system is usually a variant of problem reduction: a task is decomposed into a number of simpler subtasks which can be further decomposed until subtasks are distinguished which can directly be implemented. Another design principle is modularity: the program achieving a task is divided into different modules, often corresponding to major subtasks, which are more or less autonomous, specialized information processors.

Within each module, the AI approach aims to put together the necessary knowledge and methods needed for that module to accomplish its task. This information needs to be captured in a formalism for the representation and manipulation of knowledge. At this point, it is useful to reflect on the role of formalisms in AI in general and in linguistic models in particular. A formalism is a description language that provides a bridge between theory and implementation. A formalism consists of two parts:

1. The data organization part contains a description of the domain entities, properties and relations involved. It provides the means with which the necessary knowledge is described. In a language processing model, this could be lexical information and grammar rules, among other things.
2. The inference part determines methods for how the data can be used to solve a problem. Specific methods include logical resolution, a production system interpeter, etc., which will be described below.

In recent research in CL, there has been a shift from procedural to declarative formalisms. A procedural formalism tightly integrates data and inference. This allows the model to use inferences which are local to specific instances of knowledge. But the directness and specificity of this approach is countered by severe problems in extending and updating such a system. For that reason, declarative models, which make a clean separation between knowledge representation and inference aspects of a problem, dominate the field.


4. Paradigms for the representation of knowledge

In this section, we will discuss some aspects of knowledge representation that have been used for the representation of knowledge in general, and linguistic knowledge in particular.


4.1 State-space search

A state-space is a tree structure consisting of nodes and arcs, as illustrated in Figure 2. Nodes describe states representing situations in the domain, e.g. the description of a chessboard with a number of pieces. Some nodes may describe goal states, e.g., a chessboard on which the white king is checkmate. Arcs in the tree describe the transition from one state to another by the application of an operator, e.g. an operator for moving a pawn. Arcs have an origin (the state to which the operator is applied), and a destination (the state which results from applying the operator). In CL, search is used e.g. in parsing sentences. Suppose we have a simple grammar with rewrite rules like the following:

S NP VP
NP N
NP Pro
VP V NP
VP Aux V
Pro they
N can | fish
Aux can
V fish

In the case of parsing a sentence with this grammar, states are partial derivations consistent with the grammar and the input sentence, and operators are the state changes that different applicable grammar rules may make. Figure 2 illustrates this in a simple way by showing a tree representing the state space of analyses, some of which lead to a successful analyses. In this case, the parsing proceeds top down, i.e. by expanding the left-hand side of rules to the right-hand side, working from the root node S down to the words.

Figure 2. State-space of a syntactic parsing.

Search methods are algorithms allowing a state space to be searched for solutions to a problem. Search methods can be blind, which means that all possible states are tried in the end by the search method, either in a depth first or a breadth first way, or they can be heuristically informed, in which case they make use of knowledge about the domain to traverse the state space (Pearl 1984).


4.2 Logic-based formalisms

In one view, logic is the standard knowledge representation formalism in AI, because it embodies basic principles of reasoning, such as modus ponens and modus tollens. It has been called by Sowa (1991) ‘the assembly language of knowledge representation’; it is indeed a low level formalism, in its complexity and verbosity far removed from the conciseness of natural language. Nevertheless, the formal properties of logical formalisms make them ideally suited as a language to which other formalisms can be translated in order to evaluate and compare them.

Data organization in predicate logic consists of a set of unambiguous constants representing entities in the domain, a set of unambiguous predicates representing relations between entities in the domain, a set of functions between sets, and furthermore variables, standing for any entity, quantifiers such as all and at least one, and logical connectives such as and and or. Inference in predicate logic is achieved by applying deductive principles such as resolution. In pure predicate logic, inference is not easy, i.e. it is not computationally tractable, but limited versions have been defined that make inference tractable, e.g. by the combination of Horn clauses and negation by failure in Prolog (Clocksin & Mellish 1984). Below is a very small Prolog program expressing the facts that Socrates and Plato are human, and the rule that if x is human, then x is mortal:

human(socrates).
human(plato).
mortal(X) :- human(X).

The choice of the right constants, predicates, functions and axioms for solving a particular task is the main problem in designing a logic-based solution to language processing problems. Predicate logic has some severe limitations as a tool for representing linguistic knowledge which is incomplete, inconsistent, dynamically changing, or relating to time, action and beliefs. For all these problems, special-purpose logics are being designed (Ramsay 1988). In this research, attention tends to shift from the domain to be represented (language knowledge and processes) to the formal properties of the representation formalism.

In the area of semantics and pragmatics, several logic-based approaches of reasoning and argumentation have been proposed. As one example, we mention the work of Lascarides and Oberlander (1992) on the nontemporal order of utterances with causal relationships, as in John fell of the cliff. The bitch pushed him. They explain this by linking the events by means of logical abduction.


4.3 Semantic network formalisms and frames

Semantic networks were introduced in AI in the sixties as a model for human semantic memory (Quillian 1968). A semantic network consists of named nodes representing concepts, and labeled links representing relations between concepts. Nodes can be used to represent both types and tokens. For example, the semantic network in Figure 3 expresses the knowledge that birds have skin, wings, and can fly. A special link, the is-a link allows inferences to be made via inheritance. In the network of Figure 3, sparrow is connected via an is-a link to bird, allowing the system to infer that sparrows have wings and skin and can fly without the necessity to explicitly represent this (see Sowa 1991 for an overview of recent research on semantic networks).

Figure 3. A semantic network.

In order to incorporate more structure into associative networks, frames were proposed as a representation formalism by Minsky (1975). Each frame can be viewed as one encapsulated chunk of a semantic network. Links in semantic networks correspond to roles in frames. When used to represent natural language semantics, roles may be used to represent thematic roles (case relations), among other things. For example, a frame for a kiss action may have an agent role and a recipient role. These roles are filled by fillers which are themselves frames, for example, the agent may be Susan and the recipient may be Jim. Frame systems may allow complex descriptions of roles by adding defaults for the filler of a role, constraints on the filler of a role, and attached procedures to compute the filler of a role. Consider the following frames:

KISS-ACTION
AGENT: Type = a PERSON
RECIPIENT: Type = a PERSON or OBJECT
KISS-1
ISA KISS-ACTION
AGENT: SUSAN
RECIPIENT: JIM
PERSON
AGE: Procedure = subtract BIRTH YEAR from CURRENT YEAR
BIRTH YEAR: Type = a NUMBER
NUMBER-OF-LEGS: Default = 2
JIM
ISA PERSON
BIRTH YEAR: 1970
SUSAN
ISA PERSON

In a frame-based system, an input activates one or more frames, which consequently allows inferences to be made on the basis of the input. Attached procedures (such as the one to compute the age of persons) enable local inferences. Other inferences are based on inheritance along is-a-links. Whether such inferences are interpreted as predictions, preferences, or defaults depends on the program using frames as a source of knowledge. In general, information that is inherited from other frames is default information, which means it is defeasible by more specific information. For an overview of the use of inheritance in CL, we refer to Daelemans, De Smedt & Gazdar (1992).


4.4 Rule-based formalisms

In a rule-based formalism, knowledge is cast in the form of if-then rules: if X then Y. For example, a rule for producing questions may be the following: if the intention is to query the truth of P, then produce a yes/no question about P. If-then rules, also called condition-action pairs or production rules, were developed during the seventies as a model for human problem solving (Newell & Simon 1972). The rules can only produce actual behavior with the help of an interpreter which performs a cyclical process where each cycle consists of three phases:

1. Identification. This phase determines for which rules the condition sides are currently satisfied in working memory.
2. Selection. It will often happen that more than one rule’s condition side will be satisfied. Since it is in general not desirable for all applicable rules to fire, one or more rules are selected using a criterion, e.g. the first rule found, or the most specific rule.
3. Execution. The actions of the chosen rule are executed. Although such actions can take many forms, the most typical ones involve the addition to or removal from working memory of certain facts. Some of the facts added may represent a solution to the given problem.

Production rule systems allow both forward chaining and backward chaining. In forward chaining, inference is data-driven, i.e. states in working memory activate rules when their left sides match the current state. Execution of these rules may in turn activate other rules or achieve goals. In backward chaining, inference is goal-driven, i.e. goals are asserted and conditions of rules achieving the goals are introduced as new goals when they are not present in working memory. In the latter case, the right-hand side of the rules is used to identify applicable rules.

The rule-base acts as a kind of long-term memory, whereas the working memory, which describes the conditions that are satisfied at some point during computation, acts as a short-term memory. Rule-based architectures have been further developed toward more sophisticated cognitive models e.g. Act* (Anderson 1983) and Soar (Newell, Rosenbloom & Laird 1989). The Act* system has a semantic network as part of its long-term memory. Soar contains special mechanisms for remembering the results of previous computations in long-term memory.


5. Linguistic symbol manipulation in semantics and pragmatics

Following the methodological principles of problem reduction and modularity, the task of generating or interpreting natural language is usually decomposed into subtasks so as to make the modeling of the task more manageable. Subtasks and modules in CL systems are usually more or less tied to the unit of processing, i.e. the phoneme, word, sentence, and discourse. On the side of language understanding, they often consist of speech recognition, morphological analysis, syntactic parsing, semantic analysis, and discourse analysis. On the side of language generation, they often include discourse planning, sentence generation, morphological generation and speech production. There are several possible architectures depending on how these modules interact.

One possible scheme for the interaction between those modules is a stratificational (or sequential) architecture. In this architecture, the different modules are accessed in sequence, and any output of one component is directly input to the next component. Clearly, other kinds of architecture are possible with more interaction between the different modules. In an interactive architecture, there is feedback between a module and the previous one. In blackboard architectures, modules communicate via a common channel called the blackboard; in object-oriented designs, objects representing parts of modules communicate via message passing. In localist connectionist systems there are weighted links that allow one symbol to directly activate other ones. Distributed connectionist systems, finally, allow several concepts to be implemented using the same set of units, depending on their activation pattern, making even the representation of symbols interactive (Murre & Goebel 1995).

Especially in the integration of syntax and semantics, several nonsequential architectures have been proposed. Syntactic ambiguities, which can run into the hundreds or thousands for normal sentences, can often be resolved as a natural side-effect of solving semantic ambiguities. Therefore, a stratificational ‘syntax first’ strategy, in which all possible syntactic parses are computed first and are then input to the semantic component, is impractical, and many AI researchers have tried to integrate these two modules (e.g. Waltz & Pollack 1985).

In the next two sections, we will give an overview of selected CL research in the framework of AI and we will focus on semantics and pragmatics. The modeling of phonology, morphology and syntax have traditionally been the realm of the more linguistically oriented researchers. We will not go into these issues here.


5.1 Semantics

Much of the early symbolic AI research on natural language understanding uses associative network formalisms to represent its theoretical insights. Schank (1972, 1975, 1980) and his students developed conceptual dependency theory as an associative network formalism for the description of the meaning of sentences and texts. These networks are somewhat related to semantic networks (see above), but they have severe restrictions on possible nodes and links. A limited number of node and link types are designated as conceptual primitives. Node types for actions include, for example, physical transfer, mental transfer, etc. These are seen as the basic elements in the language of thought, and expressions composed of these primitives are supposed to be necessary and sufficient as an interlingua to represent meaning in an unambiguous way. Any implicit information in the text is to be made explicit in the conceptual dependency representation. For example, the information in the sentence John gave the book to Mary is analysed in terms of a transfer (ATRANS) of the book (the object) from John (the donor) to Mary (the recipient), involving a change of ownership. John loaned the book to Mary has obviously an analogous underlying information structure, except that in the latter case possession but not ownership is involved. The conceptual dependency structures of both sentences are illustrated in the following graphs:

The general goal of conceptual dependency theory (viz. to capture meaning in language- independent knowledge structures) gave rise to the development of a large number of related data structures and inference mechanisms. Causal chains are data structures representing chains of states enabling or motivating actions which in turn result in or initiate other states; scripts are prepackaged sequences of causal chains. Other data structures include plans and goals, memory organization packages (Mops), and plot units (Schank & Abelson 1977; Schank 1982). These knowledge structures made possible directed and efficient inference mechanisms, based on following up causal connections and associations between representations at the same and at different levels of abstraction.

The work by Schank and his students also made clear that two sources of knowledge are indispensable for developing useful symbolic natural language understanding systems: (1) knowledge about the intentions, plans and goals of different agents in narratives or dialog, and (2) knowledge about preceding discourse. This work belongs to what is commonly understood as pragmatics. We will now go into some more detail about particular aspects of this research.


5.2 Knowledge and intentions

As to the speaker’s intentions, speech act theory has been an important source of inspiration. Cohen & Perrault (1979) and Allen & Perrault (1980) view linguistic behavior as goal-driven planning: the speaker plans an utterance in order to achieve a communicative goal, while the listener’s aim is to infer that goal from the linguistic form. Speech act theory articulates the specific goals and plans a speaker may have in using language. A specific example, adapted from Wilensky (1983), involves the goal and associated plan for asking, including the preconditions that need to be satisified for the plan to be successful:

Goal: X wants to find out P from Y
Act: Ask question to Y
Preconditions: 1. X is near to Y
2. Y knows P
3. Y wants to tell P to X
Result: Y tells P to X

The goal-directed and plan-based view of linguistic behavior has been widely adopted and is still a topic of current research in the AI community (e.g. Kobsa 1989; Carberry 1989; Cohen et al. 1990).

The underlying conceptual representation in a cognitive psychology approach is the source of further reasoning. In order to arrive at an answer to a question, it is often insufficient to convert the question directly into a database query, but frequently inferences have to be drawn. This is acknowledged by Lehnert (1978) in her discussion of Qualm, the reasoning component of a question-answering system using Schank’s conceptual dependency. Answering a question involves various manipulations of the conceptual structure underlying the question, such as inferring what entity or entities is/are actually referred to by a wh-word.

Consider for example the question Who wasn’t at the party? Probably a considerable part of the world’s population was not present, but a reasonable inference is that the question refers only to invitees who did not show up. Even in order to answer a fairly simple question such as Did John eat a steak? when he is sitting in a vegetarian restaurant or when he simply left after seeing a hopelessly burnt piece of meat, a lot of inferencing is needed. Besides a conceptualization of the events mentioned, knowledge is also needed about inferred events that probably occurred but were not mentioned, failed expectations, etc. These can be made on the basis of knowledge about stereotypical situations as well as general knowledge about how people achieve goals and what sorts of goals they try to achieve (Wilensky 1983).


5.3 Utterances in context

As a matter of course, many of the issues that are raised in discourse and conversation analysis also turn up in the computer processing of natural language. For a correct interpretation of an utterance, the hearer needs to take into account the context of the communication, including the situational context, the participants’ knowledge of the domain and their intentions, and the links between the current utterance and those that precede it. Questions in point relate to the identification of the referents of definite noun phrases, to anaphora resolution, etc. Much of the AI work on discourse processing has been restricted to fairly simple discourse types with a strong tie to a particular task. For instance, Grosz (1977) studies interactions in which an expert instructs an apprentice on how to assemble an air compressor. Grosz shows that it is possible to formulate focusing heuristics because the task restricts what is talked about: the structure of the task is mirrored in the dialog structure. Similarly, Carberry (1989) establishes focusing heuristics that rely on the expectations of possible shifts of focus constrained by the underlying task-related plan in an information-seeking dialog.

The cooperative nature of the discourse types studied also aids in establishing coherence relations. For instance, McKeown (1985a, b) expanded the focus rules designed by Sidner (1983, 1985) in her computational work on discourse generation. Her approach is based on the observation that people follow certain standard patterns or schemas of discourse generation (see below) for attaining discourse goals. These patterns are helpful for the listener or reader in establishing the thread of discourse and are thus an aid in understanding (Carberry 1989).

A number of computational models have been proposed for the comprehension of discourse, but they tend to ignore its complexities (Garnham 1995). Several AI systems tend to treat discourse as a product, for which stereotypical knowledge structures can be implemented. Reichman (1985), for instance, proposes a kind of grammar for discourse, consisting of formal discourse rules and an ATN formalism for analyzing discourse. This sharply contrasts with the approach taken in conversation analysis research, in which dialog is seen as an interactional achievement. The more or less stereotyped AI approach on the one hand and the dynamic approach advocated by conversation analysts on the other hand have been conceived as irreconcilable opponents, though a fruitful interaction that may enrich the flexibility of human-computer interaction is advocated by Luff et al. (1990).


5.4 Modeling the user

User models are specific components designed for a better understanding of the user of a computer system. They have been included in AI systems that perform various tasks. The Unix Consultant (UC), a natural language program assisting beginning Unix users, contains a component Knome which maintains a model of the user (Chin 1989; Wilensky et al. 1988). Some other systems which maintain user models are Grundy, which recommends novels to users in a library setting (Rich 1979), Ham-Ans, which assists a user in renting a room in a hotel (Morik 1989), and Xtra, which acts as a tax advisor assisting the user in filling out his/her income tax form (Kobsa et al. 1986). In all these systems, a model of the user is part of a dialog component. However, it can readily be seen that user modeling is an important aspect of other AI applications such as intelligent computer aided instruction, in which a teacher must monitor the knowledge of the student, and game playing, in which a system should take into account the perspective of its adversary in order to figure out what his/her plans and goals are.


5.4.1 User modeling and dialog systems

In the context of dialog systems, a user model can be defined as a knowledge source which contains explicit assumptions on all aspects of the user that may be relevant to the dialog behavior of the system. Allen (1994) argues that regardless of whether the dialog is cooperative or not, a user model is the basis for intelligent dialog behavior. Among other things, it is required for identifying the objects talked about, identifying and analyzing non-literal meanings or indirect speech acts, determining the effects of the planned contribution on the listener, etc. As such, a user model is a crucial component of a dialog system: it provides important information for understanding the dialog partner as well as for producing an appropriate response.

The assumptions gathered in a user model must be separable by the system from the rest of the system’s knowledge, and must be supplied to other components of the system which need them (Wahlster & Kobsa 1989). The intended separation between implicit and explicit models of the user stands in contrast to current practice in the field of human computer interaction (HCI, software ergonomics or cognitive engineering), where the designer of a software product has a typical user in mind, but the definition of that user is hidden in the system without being explicitly articulated; it can only be inferred from, e.g., the design of the user interface (Norman 1986; Helander 1988). In a dialog system, the concepts user model and discourse model are closely related. The exact relationship is still a matter of debate (see for instance the discussion of this topic in Computational Linguistics 14/3).


5.4.2 Dimensions of user models

There are various dimensions along which user models vary (Kass & Finin 1988). A first distinction is that between a canonical user model which accounts for all users and an individual user model which is specific for a single individual user. Canonical user models do not take into account the characteristics of individual users; once the latter come into play, a model must be explicitly maintained by the system and mechanisms must be provided for instantiating, updating and exploiting the model.

A second dimension concerns the long term versus short term user model. In the former, relatively stable or static characteristics of the user are represented, while in the latter specific interactional information (such as topics discussed, goals pursued, etc.) is stored. In this perspective the concept of a user model shows close correspondence with that of a dialog model: a short term user model actually overlaps with a dialog model in that it records the specifics of the interaction (Rich 1989; Kobsa 1989).


5.4.3 Construction of a user model

There are essentially two paths followed in constructing a model of the user. First of all, the actual input of the user is a prime source from which his/her knowledge of the domain, as well as his/her plans and goals can be inferred. Secondly, this method can be combined with an approach that assumes a priori knowledge present in the system about types of users which is used as a basis for drawing the profile of an individual user.

The notion of a stereotype is useful for initiating a user model. Rich (1989) observes that facts about people tend to be interdependent in that particular traits of people appear to be clustered, forming stereotypes which each stand for a class of users. Rosch & Mervis (1975) use the term prototype as the denotation of such cognitive reference points. Stereotypes or prototypes enable a system to infer a whole set of user characteristics on the basis of a relatively small number of observations. For instance, in the user modeling component Knome of the Unix Consultant (Chin 1989), users are characterized by four stereotypes: novice, beginner, intermediate, and expert, each of which represents an increasing mastery of the Unix operating system. An individual user is an instantiation of the stereotype and is assigned its default characteristics. In order to set up a model of an individual user, it is necessary to collect information from the user. This can be done in various ways:

An important feature of the use of stereotypes is that the system can infer what users are likely to know or not, which user characteristics are likely to hold or not, based on only partial information about the user. In other words, the inference that a user belongs to a particular class defined by a stereotype enables the system to make a set of default inferences, which are plausible but defeasible. In order for these to work properly, uncertainty measures are associated with inferences, either as numerical values or as symbolic ratings of uncertainty (Rich 1983, 1989; Chin 1989). Moreover, in order to recover from contradicted inferences, not only the assertions about users are recorded, but also the justification of these assertions are noted, so that some form of truth maintenance (Doyle 1979, 1983) can be assured. Truth maintenance guards the consistency of the model and is an important feature of user modeling attempts for specific domains as well as user modeling shells such as Gums (Finin & Drager 1986; Finin 1989) and Trump (Bonarini 1987).


5.4.4 Instantiating the user model: Collecting evidence in dialog

The context of user modeling in dialog behavior should be clarified before we can show how user models are instantiated, updated and exploited. Most of the systems that have been developed so far deal with user-system interactions in which the system is to assist the user in some way. For instance, the system provides information that the user asks for: How can I remove a file? is a possible query to the Unix Consultant (Chin 1989). A similar interaction arises in a natural language interface to a database: Which students got a grade of F in CS105 in Spring 1980? is a possible question envisaged by Co-op (Kaplan 1982), to which the system may respond: CS105 was not given in Spring 1980. Another communicative goal is explanation. The following is a sample question addressed to Quilici’s (1989) Unix Advisor: I tried to remove a file with the rm command. But the file was not removed and the error message was ‘permission denied’. I checked and I own the file. What’s wrong? To this, the system replies: To remove a file, you need to be able to write into the directory containing it. You do not need to own the file.

In the context of interchanges such as these, a system is supposed to draw a user profile. This includes a model of what the user knows, e.g. in the above example, the user knows which command to use to remove a file. It also includes the goals of the user, e.g. the user wants to remove a file; and how s/he plans to achieve that goal, e.g. to use the rm command to delete a file. At the same time, the system has to infer, among other things, what knowledge is lacking and hence has to be provided to the user, and also what the user’s misconceptions are that need to be corrected by means of an explanation; in the above example, the user misconceives the relation between deleting a file and owning it.

In the present case, the system faces the non-trivial task of determining why the user holds a particular belief or assumption, by trying to explain why the system itself does not hold that assumption (Quilici 1989). Hence, this example exemplifies a system that does not only construct a stereotype of the user, but also infers the causes of a user’s beliefs, for which the system has to go beyond a static stereotype in order to determine discrepancies between its own beliefs and assumptions and those apparently held by the user. Similar systems have been devised to detect user’s object-related misconceptions. Romper (McCoy 1989), for example, tries to explain to the user why a belief that a whale is a fish is actually wrong. Attention has also been paid to planning related misconceptions (Pollack 1986; Wilensky 1983; Wilensky et al. 1984; Chin 1989). The latter work stresses once again the importance of planning and plan recognition in natural language dialog systems (Carberry 1983, 1988, 1989; Grosz 1977; Robinson 1981; Allen, 1983a, 1983b; Allen & Perrault 1980; Sidner 1983, 1985; Litman 1986; Allen & Litman 1986).


5.5 Generating discourse

Generating an extended piece of discourse involves some careful amount of planning. This complex task has conveniently been divided into two subtasks: deciding what to say and deciding how to say. The former is sometimes called text planning or strategic generation (Thompson 1977), and involves choices regarding the selection and organization of information. The latter subtask is sometimes called linguistic realization or tactical generation, and involves lexical and syntactic choices for the computation of the linguistic form of the utterance. We will in this section be concerned only with the first subtask, text planning (or discourse planning). Overviews of AI research in natural language generation can be found in Kempen (1989) and McDonald (1992). For proceedings of workshops on computer models for natural language generation, we refer to volumes edited by Kempen (1987), Zock & Sabah (1988), Dale, Mellish & Zock (1990), Paris, Swartout & Mann (1991), Dale, Hovy, Rösner & Stock (1992), and Horacek & Zock (1993). Computational models of discourse planning are reviewed from a psycholinguistic perspective by Andriessen, De Smedt & Zock (1995).

Generating discourse is a multiple constrained process in which various knowledge sources should be taken into account: knowledge of the domain of discourse, the situational context and past discourse, as well as knowledge about the interlocutor or reader. As indicated in the previous section, user models are an important part of discourse understanding, but the user’s plans and goals also play an important role in discourse generation. Detecting and using the user’s goal to provide an appropriate response has been the object of extensive research (e.g. Appelt 1985; Carberry 1983; McKeown 1985a, 1985b). Even though the use of a specific user model in the generation process has recently been questioned (Sparck Jones 1991), tailoring discourse to the user’s level of expertise and taking the user’s misunderstandings and other input into account are obviously fundamental communicative abilities (Kaplan 1982; McCoy 1989; Quilici 1989; Reiter 1990; Cawsey 1990a, 1990b; McKeown et al. 1990; Paris 1988; Chin 1989; Moore & Swartout 1991; Moore 1989).

In discourse generation, two approaches can be distinguished. The first approach can be characterized as conceptualizing generation as a kind of planning in the AI sense of the word, driven by the communicative goals of the speaker (Appelt 1982, 1985; Cohen & Perrault 1979). This means that at the strategic level, text is planned by reasoning about both the system’s and the user’s knowledge and beliefs, and that speech acts are meant to have a particular impact on the user’s beliefs and knowledge structures. It has been argued that this approach does not incorporate an explicit notion of textual coherence and hence will face serious problems when transcending the sentence level (Dale et al. 1990; Moore & Swartout 1991).

The second approach emphasizes text structuring above the level of the sentence. To this end, McKeown (1985b) and Paris & McKeown (1987) propose schemas, i.e. representations of stereotypical discourse strategies. For instance, McKeown proposes four schemas for describing objects: identification, constituency, attributive and contrastive schemas. Schemas mandate the content and the order of the clauses in paragraphs. However, they do not allow the dynamic reassembly of the basic parts into new paragraphs. In order to fix this drawback, McKeown et al. (1990) envisage to generalize schemas into an hierarchy of increasingly more general schemas.

An alternative approach offering a more detailed and dynamic text structuring is rhetorical structure theory (RST; Mann & Thompson 1987, 1988). RST identifies basic rhetorical relations as the building blocks from which coherent paragraphs (and thus, ultimately also the schemas mentioned above) are composed. Using RST relations, text generation systems can dynamically put together paragraphs. Some examples of rhetorical relations between elements in texts are sequence, which is signaled by words like then, next, etc.; purpose, signaled by in order to; and alternative, signaled by or. Rhetorical relations are used at several levels of the text structure, down to the level of single clauses. Coherent discourse is attained if all parts of a text can be hierarchically structured by rhetorical relations. Thus, the relations in a stretch of discourse can be represented as a tree structure. The branches of the tree represent adjacent clauses and blocks of clauses between which a particular rhetorical relation holds.

Currently much generation research is devoted to implementations of RST, i.e. the design of planning algorithms that dynamically assemble the elements of a text using RST relations (Hovy 1988a, 1988b, 1990, 1991; Cawsey 1990b; Moore & Swartout 1991; Paris 1988, 1991; Scott & de Souza 1990). Other research deals with focus in discourse. Focusing refers to the way in which the writer guides the reader’s attention throughout a text. This, in turn, has consequences for the correct interpretation of referring expressions, for example pronouns and definite noun phrases. McCoy & Cheng (1991) investigate how a discourse focus tree can be built parallel to the discourse structure tree to track the focus of attention through the text.

An interesting new perspective is created by the introduction of technologies for multimodal human-computer interaction, i.e. using both the modalities of conversation and of graphic interaction. McKeown et al. (1990) describes a system in which text and graphics are used for explanations. Claassen (1992) proposes Edward, a multimodal dialog system where graphic interaction in a model world is combined with natural language commands and questions. An added feature of Edward is the continuous linguistic feedback generator (CLFG) which gives natural language feedback on the user’s actions.


6. Epilogue

Symbolic approaches that are based on rules, logic, frames, grammars, or on a combination of these representation techniques, are able to successfully perform complex natural language processing tasks. Thanks to the definition of formal operations as operating on the form of structures, irrespective of their content, symbolic systems achieve a high level of abstraction. Symbolic programming allows for flexibility and creativity. First, new symbols and structures can be created dynamically during program execution. Second, structures can be recursively defined and can thus represent a potentially infinite number of actual structures. And third, programs are also symbolic structures and can thus be created or manipulated by other programs.

However, precisely because of the high level of abstraction, symbolic systems are extremely complex in their handling of special conditions. Each exception requires additional rules and more processing. This is particularly problematic as the system is scaled up, even though the problem of scaling up can be somewhat alleviated by the use of powerful mechanisms such as default inheritance. The data and methods must generally be hand-coded by the system designer, because their complexity makes them hard to acquire automatically. This complexity makes symbolic systems vulnerable in the case of ill-formed or incomplete input and in the case of unforeseen interactions between rules. When a symbolic system goes wrong, it usually does not degrade gracefully, but breaks down completely. Machine learning of natural language from data like corpora or machine-readable dictionaries is therefore becoming an increasingly important topic in CL, as it may alleviate these knowledge acquisition and robustness problems.

While the PSSH goes a long way toward providing a framework for the study of knowledge-based intelligence, i.e. intelligence based on the construction and manipulation of models, this is less the case for behavior-based intelligence, i.e. intelligent behavior based on direct associations between sensory input and motor output without intermediate models. It is an open research question whether language processing is an instance of behavior-based or knowledge-based intelligence, or both. It also remains to be seen in how far language is a task much like other cognitive tasks, e.g. playing chess, solving algebra problems, or recognizing visual objects, or whether language is special in some ways, i.e. autonomous from other cognitive subsystems and requiring special cognitive mechanisms.


Note

1. Preparation of this paper was supported by a grant from the Fund for Joint Basic Research FKFO (contract number 2.0101.94) and by an interuniversity research program on linguistic pragmatics (IUAP-II, contract number 27).

References

ALLEN, J. (1983a) Recognizing intentions from natural language utterances. In M. Brady & R. Berwick (eds.): 107–166.

—— (1983b) ARGOT: A system overview. Computers and Mathematics with Applications 9: 97–109.

—— (1994) Understanding natural language. Addison-Wesley.

ALLEN, J. & D. LITMAN (1986) Plans, goals and language. Proceedings of the IEEE 74: 939–947.

ALLEN, J. & C. PERRAULT (1980) Analyzing intention in utterances. Artificial Intelligence 15: 143–178.

ANDERSON, J. R. (1983) The architecture of cognition. Harvard University Press.

ANDRIESSEN, J., K. DE SMEDT & M. ZOCK (1995) Computational models of discourse planning. In A. Dijkstra & K. De Smedt (eds.).

APPELT, D. E. (1982) Planning natural-language utterances. Proceedings AAAI-82: 59–62.

—— (1985) Planning English sentences. Cambridge University Press.

BARR, A. & E. A. FEIGENBAUM (1989) The handbook of artificial intelligence. Kaufmann.

BOBROW, D. (1968) Natural language input for a computer problem-solving system. In M. Minsky (ed.) Semantic information processing: 146–226. MIT Press.

BONARINI, A. (1987) User modeling in person-machine conversation. Proceedings of COGNITIVA-87: 377–382.

BRADY, M. & R. BERWICK (eds.) (1983) Computational models of discourse. MIT Press.

BRATKO, I. (1990) Prolog programming for artificial intelligence. Addison-Wesley.

CARBERRY, S. (1983) Tracking user goals in an information-seeking environment. Proceedings AAAI-83: 59–63.

—— (1988) Modeling the user’s plans and goals. Computational Linguistics 14: 23–37.

—— (1989) Plan recognition and its use in understanding dialog. In A. Kobsa & W. Wahlster (eds.): 133–162.

CAWSEY, A. (1990a) A computational model of explanatory discourse. In P. Luff, N. Gilbert & D. Frohlich (eds.): 221–234.

—— (1990b) Generating explanatory discourse. In R. Dale, C. Mellish & M. Zock (eds.): 75–101.

CHIGNELL, M. H. & P. A. HANCOCK (1988) Intelligent interface design. In M. Helander (ed.): 969–995.

CHIN, D. (1989) KNOME: Modeling what the user knows in UC. In A. Kobsa & W. Wahlster (eds.): 70–107.

CLAASSEN, W. (1992) Generating referring expressions in a multimodal environment. In R. Dale, E. Hovy, D. Roesner & O. Stock (eds.): 247–262.

CLOCKSIN, W. F. & C. S. MELLISH (1984) Programming in Prolog. Springer.

COHEN, P. & C. PERRAULT (1979) Elements of a plan-based theory of speech acts. Cognitive Science 3: 177–212.

COHEN, P., J. MORGAN & M. POLLACK (1990) Intentions in communication. MIT Press.

COPELAND, J. (1993) Artificial intelligence. Blackwell.

DAELEMANS, W., K. DE SMEDT & G. GAZDAR (1992) Inheritance in natural language processing. Computational Linguistics 18: 205–218.

DALE, R., E. HOVY, D. ROESNER & O. STOCK (eds.) (1992) Aspects of automated natural language generation. Springer.

DALE, R., C. MELLISH & M. ZOCK (1990) Introduction. In R. Dale, C. Mellish & M. Zock (eds.): 1–15.

DALE, R., C. MELLISH & M. ZOCK (eds.) (1990) Current research in natural language generation. Academic Press.

DIJKSTRA, A. & K. DE SMEDT (eds.) (1995) Computational psycholinguistics. Harvester Wheatsheaf.

DOYLE, J. (1979) A truth maintenance system. Artificial Intelligence 12: 231–272.

—— (1983) The ins and outs of reason maintenance. Proceedings IJCAI-83: 352–354.

FININ, T. (1989) GUMS: A general user modeling shell. In A. Kobsa & W. Wahlster (eds.): 411–430.

FININ, T. & D. DRAGER (1986) GUMS: A general user modeling system. Proceedings of the 6th Canadian Conference on Artificial Intelligence: 24–29.

FLACH, P. (1994) Simply logical. Wiley.

GAZDAR, G. & C. MELLISH (1989a) Natural language processing in Prolog. Addison-Wesley.

—— (1989b) Natural language processing in LISP. Addison-Wesley.

GARNHAM, A. (1995) Computational models of discourse comprehension. In A. Dijkstra & K. De Smedt (eds.).

GREEN, B., A. WOLF, C. CHOMSKY & K. LAUGHERY (1963) BASEBALL: An automatic question-answerer. In E. Feigenbaum & J. Feldman (eds.) Computers and thought: 207–216. McGraw-Hill.

GROSZ, B. (1977) The representation and use of focus in a system for understanding dialogs. Proceedings IJCAI-77: 67–76.

HARNAD, S. (1989) Minds, machines and Searle. Journal of Theoretical and Experimental Artificial Intelligence 1: 5–25.

HAYES, P., S. HARNAD, D. PERLIS & N. BLOCK (1992) Virtual symposium on the virtual mind. Minds and Machines 2: 217–238.

HELANDER, M. (ed.) (1988) Handbook of human-computer interaction. Elsevier Science.

HORACEK, H. & M. ZOCK (eds.) (1993) New concepts in natural language generation. Pinter.

HOVY, E. (1988a) Planning coherent multisentential text. Proceedings of the 26th ACL Conference: 163–169.

—— (1988b) On the study of text planning and realization. Proceedings of the AAAI Workshop on Text Planning and Realization: 17–29.

—— (1990) Unresolved problems in paragraph planning. In R. Dale, C. Mellish & M. Zock (eds.): 17–45.

—— (1991) Approaches to the planning of coherent text. In C. Paris, W. Swartout & W. Mann (eds.): 83–102.

KAPLAN, S. (1982) Cooperative responses from a portable natural language query system. Artificial Intelligence 19: 165–188.

KASS, R. & T. FININ (1988) Modeling the user in natural language systems. Computational Linguistics 14: 5–22.

KEMPEN, G. (1989) Language generation systems. In I. Bátori, W. Lenders & W. Putschke (eds.) Computational Linguistics: 471–480. de Gruyter.

—— (ed.) (1987) Natural language generation. Nijhoff.

KOBSA, A. (1989) A taxonomy of beliefs and goals for user models in dialog systems. In A. Kobsa & W. Wahlster (eds.): 52–68.

KOBSA, A., J. ALLGAYER, C. REDDIG, N. REITHINGER, D. SCHMAUKS, K. HARBIUSH & W. WAHLSTER (1986) Combining deictic gestures and natural language for referent identification. Proceedings of COLING-86: 356–361.

KOBSA, A. & W. WAHLSTER (eds.) (1989) User models in dialogue systems. Springer.

LASCARIDES, A. & J. OBERLANDER (1992) Abducing temporal discourse. In R. Dale, E. Hovy, D. Roesner & O. Stock (eds.): 176–182.

LEHNERT, W. (1978) The process of question answering. Erlbaum.

LITMAN, D. (1986) Linguistic coherence. Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics: 215–223.

LUFF, P., N. GILBERT & D. FROHLICH (eds.) (1990) Computers and conversation. Academic Press.

LUGER, G. F. & W. A. STUBBLEFIELD (1993) Artificial intelligence. Benjamin Cummings.

MANN, W. & S. THOMPSON (1988) Rhetorical structure theory. Text 8: 243–281.

McCOY, K. (1989) Highlighting a user model to respond to misconceptions. In A. Kobsa & W. Wahlster (eds.): 233–254.

McCOY, K. & J. CHENG (1991) Focus of attention. In C. Paris, W. Swartout & W. Mann (eds.): 103–124.

McDONALD, D. (1992) Natural language generation. In S. Shapiro (ed.): 983–997.

McKEOWN, K. R. (1985a) Discourse strategies and focus constraints to generate natural language text. Artificial Intelligence 27: 1–41.

—— (1985b) Text generation. Cambridge University Press.

McKEOWN, K. R., M. ELHADAD, Y. FUKUMOTO, J. LIM, C. LOMBARDI, J. ROBIN & F. SMADJA (1990) Natural language generation in COMET. In R. Dale, C. Mellish & M. Zock (eds.): 103–139.

McTEAR, M. (1987) The articulate computer. Blackwell.

MINSKY, M. (1975) A framework for representing knowledge. In P. Winston (ed.) The psychology of computer vision: 211–277. McGraw-Hill.

MOORE, J. D. (1989) Responding to ‘Huh’. Proceedings CHI-89: 91–91.

MOORE, J. D. & W. SWARTOUT (1991) A reactive approach to explanation. In C. L. Paris, W. Swartout & W. Mann (eds.): 3–48.

MORIK, K. (1989) User models and conversational settings. In A. Kobsa & W. Wahlster (eds.): 364–385.

MORIK, K. & C. ROLLINGER (1985) The real estate agent. AI Magazine 6: 44–52.

MURRE, J. & R. GOEBEL (1995) Computational modelling in connectionism. In A. Dijkstra & K. De Smedt (eds.).

NEWELL, A. (1980) Physical symbol systems. Cognitive Science 4: 135–183.

NEWELL, A. & H. SIMON (1972) Human problem solving. Prentice-Hall.

NEWELL, A., P. S. ROSENBLOOM & J. E. LAIRD (1989) Symbolic architectures for cognition. In M. I. Posner (ed.) Cognitive science: 93–131. Bradford/MIT Press.

NORMAN, D. A. (1986) Cognitive engineering. In D. A. Norman & S. Draper (eds.) User centered system design: 31–61. Erlbaum.

NORVIG, P. (1992) Paradigms of artificial intelligence programming. Morgan Kaufmann.

PARIS, C. (1988) Tailoring object descriptions to the user’s level of expertise. Computational Linguistics 14: 64–78.

—— (1991) Generation and explanation. In C. Paris, W. Swartout & W. Mann (eds.): 49–82.

PARIS, C. & K. McKEOWN (1987) Discourse strategies for describing complex physical objects. In G. Kempen (ed.): 97–115.

PARIS, C., W. SWARTOUT & W. MANN (eds.) (1991) Natural language generation in artificial intelligence and computational linguistics. Kluwer.

PEARL, J. (1984) Heuristics. Addison-Wesley.

PEREIRA, F. & S. SHIEBER (1987) Prolog and natural language analysis. CSLI Lecture Notes 10.

POLLACK, M. E. (1986) A model of plan inference that distinguishes between the beliefs of actors and observers. Proceedings of the 24th Annual Meeting of the Association of Computational Linguistics: 207–214.

PYLYSHYN, Z. (1984) Computation and cognition. Bradford Books.

QUILICI, A. (1989) Detecting and responding to plan-oriented misconceptions. In A. Kobsa & W. Wahlster (eds.): 108–132.

QUILLIAN, R. (1968) Semantic memory. In M. Minsky (ed.) Semantic information processing: 227–270. MIT Press.

RAMSAY, A. (1988) Formal methods in artificial intelligence. Cambridge University Press.

REICHMAN, R. (1985) Getting computers to talk like you and me. MIT Press.

REITER, E. (1990) Generating descriptions that exploit a user’s domain knowledge. In R. Dale, C. Mellish & M. Zock (eds.): 257–285.

RICH, E. (1979) User modelling via stereotypes. Cognitive Science 3: 329–354.

—— (1983) Users are individuals. International Journal of Man-Machine Studies 18: 188–214.

—— (1989) Stereotypes and user modeling. In A. Kobsa & W. Wahlster (eds.): 35–51.

ROBINSON, A. (1981) Determining verb phrase referents in dialogs. American Journal of Computational Linguistics 7: 1–18.

ROSCH, E. & C. MERVIS (1975) Family resemblances. Cognitive Psychology 7: 573–605.

SCHANK, R. (1972) Conceptual dependency. Cognitive Psychology 3: 552–630.

—— (1975) Conceptual information processing. North-Holland.

—— (1980) Language and memory. Cognitive Science 4: 243–284.

—— (1982) Dynamic memory. Cambridge University Press.

SCHANK, R. & R. ABELSON (1977) Scripts, plans, goals and understanding. Erlbaum.

SCOTT, D. & C. de SOUZA (1990) Getting the message across in RST-based text generation. In R. Dale, C. Mellish & M. Zock (eds.): 47–73.

SEARLE, J. R. (1984) Minds, brains and machines. Penguin.

SIDNER, C. (1983) What the speaker means. Computers and Mathematics with Applications 9: 71–82.

—— (1985) Plan parsing for intended response recognition of speaker’s plan in discourse. Computational Intelligence 1: 1–10.

SIMMONS, R., S. KLEIN & K. McCONLOGUE (1964) Indexing and dependency logic for answering English questions. American Documentation 15: 196–202.

SHAPIRO, S. (ed.) (1992) Encyclopedia of artificial intelligence. Wiley.

SOWA, J. F. (1991) Toward the expressive power of natural language. In J. F. Sowa (ed.) Principles of semantic networks: 157–190. Morgan Kaufmann.

SPARCK JONES, K. (1989) Realism about user modeling. In A. Kobsa & W. Wahlster (eds.): 341–363.

—— (1991) Tailoring the output to the user. In C. Paris, W. Swartout & W. Mann (eds.): 201–225.

THOMPSON, H. (1977) Strategy and tactics in language production. In W. Beach, S. Fox & S. Philosoph (eds.) Papers from the Thirteenth Regional Meeting of the Chicago Linguistic Society: 651–668.

TURING, A. (1964) Computing machinery and intelligence. In A. Andersen (ed.) Minds and machines: 4–30. Prentice Hall.

WAHLSTER, W. & A. KOBSA (1989) User models in dialog systems. In A. Kobsa & W. Wahlster (eds.): 4–33.

WALTZ, D. L. & J. B. POLLACK (1985) Massively parallel parsing. Cognitive Science 9: 51–79.

WEIZENBAUM, J. (1966) ELIZA: a computer program for the study of natural language communication between man and machine. CACM 9: 36–45.

—— (1984) Computer power and human reason. Penguin.

WILENSKY, R. (1983) Planning and understanding. Addison-Wesley.

WILENSKY, R., Y. ARENS & D. CHIN (1984) Talking to UNIX in English. CACM 27: 574–593.

WILENSKY, R., D. CHIN, M. LURIA, J. MARTIN, J. MAYFIELD & D. WU (1988) The Berkeley UNIX Consultant Project. Computational Linguistics 14: 35–84.

WINOGRAD, T. (1972) Understanding natural language. Academic Press.

WINSTON, P. H. (1993) Artificial intelligence (3rd ed.). Addison-Wesley.

WINSTON, P. H. & B. K. HORN (1989) LISP. Addison-Wesley.

WOODS, W. (1970) Transition network grammars for natural language analysis. Communications of the ACM 13: 591–606.

WOODS, W., B. NASH-WEBBER & R. KAPLAN (1972) The Lunar sciences natural language system final report. BBN report 3438. Bolt, Beranek and Newman.

ZOCK, M. & G. SABAH (eds.) (1988) Advances in natural language generation. Pinter.



Related articles: Communication, Computational linguistics, Cognitive psychology, Cognitive science, Connectionism, Context and contextualization, Frame analysis, Frame semantics, Speech act theory