ALBERT

Notes: In this paper, I present an architecture for generating extended text. This architecture is implemented in a system, Salix, which incrementally generates natural language texts whose structure is derived from the domain structure of the subject matter. The architecture is composed of data-driven, domain-independent strategies for producing increments of text. The strategies include metastrategies that combine or choose among all strategies that are applicable at each increment or decide what to do if no strategy applies. Salix's capabilities are demonstrated in generating texts, in the domains of houses and families, that are comparable to descriptions elicited from human speakers. Salix has also been utilized to generate texts about text style (Germain 1991). The approach to text generation presented here is compared to others in the literature along the dimensions of local organization, coherence, focusing, and domain independence. An argument is made for the approach presented here that locally organizes and incrementally generates coherent text.

Notes: A story generation system based on dynamics of the mind is presented. Semantic theories until now avoided discussing a linkage of language with encyclopedic human knowledge. This paper attacks the problem of how to make clear the complicated, wide-ranging dynamics of the mind and how to connect it to language.First, the background of this study is shown, in which our model of the mind, with both five levels along the concept formation process and eight domains according to the contents of mental activities, is surveyed.Based on this model, then, the dynamics of mind are discussed, along an Aesop fable. A unit of data processing in the mind is called a “module,” and the mental dynamics are considered as a chain activation of those modules, represented by a dynamic network. Next, a method for story generation is discussed. Propositional information of a sentence is embedded in a slot of activated, frame-structured modules, and the discourse structure of a generated story basically depends on the dynamic network. Both the chain activation and the generation processes are verified by experiments.Lastly, residual problems of our research, a comparison with related research, and its applications are discussed.This case study would be expected to give a basis to integrated systems for problem solving, natural language and image understandings, their generations, and intelligent robots.

Notes: Looking to the future, generators will have more knowledge of language and will have to deal with inputs that are very rich in information. As a result, several problems will become more acute, including selecting what to say at the subproposition level and dealing with interaction among goals and dependencies among choices. This paper explains how these problems arise and why they are hard to handle within traditional architectures for generation. It also discusses why these issues have not been well addressed, including the current lack of demanding applications, excessive emphasis on linguistic traditions, the use of reverse engineering to determine generator inputs, and the tendency to research only one issue at a time.

Notes: Common sense sometimes predicts events to be likely or unlikely rather than merely possible. We extend methods of qualitative reasoning to predict the relative likelihoods of possible qualitative behaviors by viewing the dynamics of a system as a Markov chain over its transition graph. This involves adding qualitative or quantitative estimates of transition probabilities to each of the transitions and applying the standard theory of Markov chains to distinguish persistent states from transient states and to calculate recurrence times, settling times, and probabilities for ending up in each state. Much of the analysis depends solely on qualitative estimates of transition probabilities, which follow directly from theoretical considerations and which lead to qualitative predictions about entire classes of systems. Quantitative estimates for specific systems are derived empirically and lead to qualitative and quantitative conclusions, most of which are insensitive to small perturbations in the estimated transition probabilities. The algorithms are straightforward and efficient.

Notes: When Horn clause theories are combined with integrity constraints to produce potentially refutable theories, Seki and Takeuchi have shown how crucial literals can be used to discriminate two mutually incompatible theories. A literal is crucial with respect to two theories if only one of the two theories supports the derivation of that literal. In other words, actually determining the truth value of the crucial literal will refute one of the two incompatible theories.This paper presents an integration of the idea of crucial literal with Theorist, a logic-based system for hypothetical reasoning. Theorist is a goal-directed nonmonotonic reasoning system that classifies logical formulas as possible hypotheses, facts, and observations. As Theorist uses full clausal logic, it does not require Seki and Takeuchi's notion of integrity constraint to define refutable theories. In attempting to deduce observation sentences, Theorist identifies instances of possible hypotheses as nomological explanations: consistent sets of hypothesis instances required to deduce observations. As multiple and mutually incompatible explanations are possible, the notion of crucial literal provides the basis for proposing experiments that distinguish competing explanations.We attempt to make three contributions. First, we adapt Seki and Takeuchi's method for Theorist. To do so, we incrementally use crucial literals as experiments, whose results are used to reduce the total number of explanations generated for a given set of observations. Next, we specify an extension which incrementally constructs a table of all possible crucial literals for any pair of theories. This extension is more efficient and provides the user with greater opportunity to conduct experiments to eliminate falsifiable theories. A prototype is implemented in CProlog, and several examples of diagnosis are considered to show its empirical efficiency. Finally, we point out that assumption-based truth maintenance systems (ATMS), as used in the multiple fault diagnosis system of de Kleer and Williams, are interesting special cases of this more general method of distinguishing explanatory theories.

Notes: When trying to understand a speaker's argument, it is necessary to determine what her claim is and what evidence she provides for it. It is necessary, therefore, to be able to recognize evidence relations in terms of the speaker's beliefs. This paper describes an implementation of an evidence oracle, which tests for evidence between statements and builds a model of the speaker based on the evidence relations found. This implementation is intended to be an advance in the development of practical discourse analysis systems, proposing a basis for verifying certain relationships between utterances. Another contribution of the work is a stratified speaker model which allows for varying levels of acceptance of beliefs attributed to the speaker. Integration of the implemented evidence oracle into a full discourse analyser is presented, together with output illustrating the analysis for several sample arguments. Some extensions of this approach for plan inference are also discussed.Lorsque l'on essaie de comprendre l'argument d'un locuteur, il importe de déterminer la nature de sa prétention et le type d'évidence qui l'accompagne. Par conséquent, il est nécessaire de pouvoir distinguer des relations d'évidence les croyances du locuteur. Cet article décrit la mise en oeuvre d'un oracle qui recherche l'évidence entre des énoncés et construit un modèle du locuteur en fonction des relations d'évidence constatées. Cette mise en oeuvre propose une base pour vérifier certaines relations entre des énoncés; elle se veut une contribution au développement d'un système pratique d'analyse du discours. Une autre contribution de cette recherche est l'élaboration d'un modèle de locuteur stratifyé qui tient compte de niveaux variables d'acceptation des croyances attributeés au locuteur. l'intégration de l'oracle d'évidence sous forme d'analyseur de discours est présentée, ainsi que des illustrations de l' analyse de plusieurs arguments types. Une extension de cette approche à l'inférence de plans est également discutée.

Notes: The ability of a biological organism to visually track a perceptually significant feature in its environment has been argued to be an important feedback mechanism guiding locomotion. This paper analyzes the constraints available from the visual motion stimuli in the context of tracking. Our aim is to show that the act of tracking simplifies the decoding of egomotion parameters from motion stimuli. The constraints obtainable under tracking are utilized to analyze a possible egomotion decoding strategy for a binocular robot eye system, modeled after the human ocular tracking (smooth pursuit) mechanism. The main result of the paper is in the derivation of a closed-form solution of the egomotion parameters using feedback information concerning the movement of the tracking motors over time. The theoretical results are verified by experiments. We believe that the active tracking approach presented here is a more simple, practical, and manageable technique in a robot navigation setting, compared to passive methods.

Notes: This paper considers computer programs that purport to do inference. It finds the essence of their reasoning ability to reside in a particular relationship which exists between the computations described by the texts of those programs and machine-independent formal representations of the theories in which they are said to reason. The principal novelties in the treatment of this question are the use of explicit “abstraction functions” between states of a computation and sets of sentences of a theory, and the notion of global “inference relations” which characterize the set of all inferences of which a system is capable. The central result of the paper is an “arrow-theoretic” characterization of the concept of a knowledge representation, along with the related concept of a knowledge representation realization. The notions of equivalence and subsumption for knowledge representations are defined, as well as equivalence of knowledge representation realizations. Finally, important issues of expression evaluation and control are addressed. The paper concludes with a slogan: “The AI is in the arrows.”Cet article traite des programmes informatiques qui prétendent faire de ľinférence. Ľauteur constate que ľessentiel de leur capacityé de raisonnement réside dans la relation particulière qui existe entre les calculs décrits par les textes de ces programmes et les représentations formelles non liées à un type de machine des théories dans le cadre desquelles ils sont supposés raisonner. Les principales nouveautés dans le traitement de cette question sont ľutilisation de fonctions ?abstraction explicites éntre les etats ?un calcul et les ensembles de phrases ?une théorie, et la notion de relations ?inférence globales qui caractérisent ľensemble de toutes les inférences dont un système est capable. Le principal résultat de cet article est une caractérisation du concept de la représentation des connaissances, ainsi que du concept connexe de la réalisation de la représentation des connaissances. Les notions ?équivalence et de sous-somption pour la représentation des connaissances sont définies, ainsi que ľéquivalence des réalisations de la représentation des connaissances. Enfin, des questions importantes comme ľanalyse et le contrǒle ?expressions sont traitées.

Notes: Abstract: Many organizations today have an interest in communications networks, either as users of public networks or as operators of their own private networks. Thus, the management of communications networks has become an important issue in the communications industry. The network design task is fundamental to the whole notion of network management; however, with the rapid rate of change in network technology and the emergence of highly sophisticated network users, network design has become an increasingly complex problem.The purpose of this paper is to describe a development effort which incorporates expert systems techniques to treat one aspect of the network design problem—the initial planning and design of a network prior to implementation. The research effort was concerned with developing an expert system for Amdahl Communications Products which could be used by sales engineers in designing wide area networks to meet specified customer requirements. The system treats both the topological design problem and the component configuration problem.

Notes: Abstract: The rapid growth in the use of expert systems has led to widespread interest in techniques for their evaluation, which includes verification and validation. Evaluation techniques in the software engineering community are well established but there are different opinions about the effectiveness of transferring software engineering methodologies to expert systems. This paper outlines some of the issues involved in evaluating expert systems and cites almost 200 significant papers on the topic. We present it with the expectation that it will help both new and established researchers become acquainted with the literature of an important and growing field.

Notes: Abstract: This paper describes some of the problems encountered in developing a user interface for a commercial expert system. The emphasis is on the practical side of interface implementation while attempting to follow the many guidelines presented in the literature.

Notes: Abstract: The need to integrate knowledge-based systems (KBS) with mainstream data processing (DP) systems is increasingly recognised. It is also recognised that there is no ideal mode of KBS integration: different types of problem call for different modes of integration. Many large organisations are now facing a serious problem in the operation of their existing DP systems. This paper focuses on the problem of providing intelligent support to the (often inexperienced) terminal users of complex mainframe systems—but without initiating any significant changes to the existing DP environment. Over the past few years we have been attempting to evolve a solution to this type of problem that is satisfactory from both a human and a software engineering perspective. This paper outlines the previous work and considerations underlying our current approach. Starting from a purely mainframe-based mode of integration, this has entailed locating an increasing number of an integrated KBS-DP system's components onto a front-end workstation. In our current solution, both user interface and KBS modules reside on a workstation linked to the (unchanged) mainframe environment. The key element of this approach is terminal operator emulation: a KBS-controlled 'script’ facility on a workstation which emulates the flexible keyboard behaviour of an experienced mainframe terminal user interacting with an existing DP system. The software tools and techniques employed in implementing this solution are discussed and details of a large operational system are presented as an example application.

Notes: Abstract: The aim of this paper is to describe a system whereby an intensive care unit patient's condition can be monitored and assessed over time using mostly blood gas analysis data. The first six sections analyse some major temporal reasoning approaches (with limited examples from other related areas) with the aim of selecting one for the task at hand. The last sections describe the PONJIP temporal blood gas analysis expert system with its main components, including user interfaces customised to the doctor's requirements. Since the overall aim of this paper is to describe an expert system used for the evaluation of the possible contribution of temporal medical reasoning from blood gas data, research specific to other application areas or data will not be covered here.

Notes: Abstract: Solving the customer's LAN/WAN interconnect problem is difficult because of the need to explore many possible configurations (e.g. bridging/routing, packet/channels) and then to choose the best configuration using economic, performance and other criteria. The rapid introduction of new standards, protocols and products to the networking field brings additional complications to the solution and can cause confusion when configuring a network. ALCA is intended to generate all feasible LAN/WAN configuration possibilities automatically and to pick the most appropriate solution to solve the customer's problem, while specifically addressing open systems interconnection (OSI) standards. Matching communications protocols while searching all possible configurations is notoriously slow even on a computer. We show how the search speed can be significantly improved by using expert system knowledge compilation, a computer-aided software engineering (CASE) technique. ALCA is based on a centrally updated knowledge base of various local area networking products and their interconnect possibilities. ALCA also allows querying to find out protocol interfaces supported by a particular product/service. Finally, it includes a graphic user interface and context-sensitive menus to reduce user information load. ALCA is intended to be used by the field personnel involved in pre-sales support, by the data communication product managers, and as an educational tool for novice communication product managers.

Notes: Abstract: Artificial intelligence has emerged from the toy problem world and is being applied to real domains in a more general way, the existence of several large application systems supporting the belief that a generation of smarter and more general systems will be developed. However, a new problem, sometimes referred to as the fusion problem, has been identified, which acts to restrict the development of such systems. This paper explains the nature of the problem, and by examining a proposed expert system in economics (ESE), discussing three approaches to a prototype ESE and the problems associated with them, draws some conclusions with regard to data fusion and expert co-operation.

Notes: Abstract: This paper presents work undertaken as part of a project concerned with the development of a fully automated industrial radiographic inspection system, based on both conventional image-processing techniques for the detection and analysis of defects in the radiographic image, and intelligent knowledge-based (1KB) techniques for the classification and evaluation of defect data against the quality assurance requirements of the inspection process. In this paper the 1KB defect classification system is presented. This system is based on a hierarchical frame-based knowledge representation and a backward-chaining production rule system. Examples of the frame structures, frame taxonomies and the data-driven procedures, which maintain the knowledge base are given, along with an outline of the defect classification rules and the inference mechanism for dealing with uncertainty by means of confidence factors.

Notes: Abstract: The excessive time devoted to the development, testing and maintenance of expert systems (ESs) needs to be reduced radically. What is needed is general-purpose software that can interlace the extracting, structuring, testing, and encoding of knowledge gained from debriefing the expert in any field. LAPS (Logic Aids for Problem Solving) is just such a program and has been successfully used to produce an ES in the domain of submarine diving officers. This automatically-encoded ES was produced by each expert entering his responses to the LAPS series of strategic-induction, AI-jargon-free queries. Currently, the LAPS prototype has four core sessions or functions: (1) the initial or sample-solution session; (2) the dechunking or hidden-knowledge session; (3) the alternatives or completeness-testing session; and (4) the automatic rule-production session. After any session the interviewee can use the fourth function of LAPS to produce frame-laden rules (in M.I, for now; later, in CLIPS). These rules can of course be used to carry out consultation sessions, though fewer of these are needed. LAPS has itself been translated from M.I to C to provide a very fast program on an almost universally available platform — the microcomputer. In accord with the overall technical approach to this project, other successful offline rigorous interviewing functions are being added to LAPS. Other code additions pertain to (a) graphical and other user-friendly reasoning-aid enhancements; (b) a series of simpler follow-up queries; and (c) the fleshing out of many stubs, or functions having intermediate results but as yet no processing.

Notes: Abstract: This paper describes a shell for cooperating expert systems that has been developed at the University of Porto. The main goal of this shell is two-fold: to generate a community of cooperative knowledge-based systems and to develop several special reasoning techniques which can be used under a distributed and cooperative paradigm. UPShell is able to convert a set of generated intelligent systems (ISs) into a community of cooperative ISs. In this first version it is already possible to generate different intelligent systems which are able to run ‘simultaneously’ as separate Unix processes and, using a message-passing mechanism, to communicate among themselves. They can be set to pursue an overall goal in a cooperative way. Moreover, several tasks can be given to each IS to be solved simultaneously, and the IS can switch from task to task according to dynamic priorities reflecting the urgency attached to the specific sub-tasks that emerge. The shell described here may also be used to test, within a distributed environment, some time-bounded reasoning techniques that are presently being developed. The paper has three main parts: a general overview of the UPShell (Section 1); a tutorial explaining, by means of examples, how to use the package (Section 2); and, finally, some considerations on the reasoning techniques used and future improvements (Sections 3–5).

Notes: Book reviewd in this article:Expert Systems in Production and Services II: From Assessment to Action?Thomas Bernold, Ulrich Hillenkamp (Eds.)Expert Systems: Human Issues. D. Berry, A. Hart.Prolog and its Applications: A Japanese Perspective. Fumio Mizuguchi (Ed.)

Notes: Abstract: There has been a growing desire for methodological support for the development of knowledge-based systems, and the KADS methodology is probably the most widely known methodology in Europe. However, KADS has been criticised for the overhead which it places on small and medium-sized KBS projects where the risks of KBS development becoming unmanageable are relatively low. This paper describes the use of ‘pragmatic KADS’, an attempt to extract the most useful elements from the KADS methodology, in the development of the COURSE SELECTOR KBS, which assists undergraduate students to choose courses which comply with University regulations and timetabling restrictions. This KBS was built in six man-weeks. The paper describes the three major phases of a KBS project, giving a brief outline of the KADS approach to each of these stages, and then discusses the techniques which were actually used for COURSE SELECTOR. It concludes with a recommendation of techniques for future small KBS projects.

Notes: Abstract: FDAS (Fabric Defects Analysis System) is a knowledge-based system (KBS) for diagnosing defects in woven textile structures. The following major issues were considered in the design of FDAS: (1) range of applications; (2) user profiles; (3) response time requirements; (4) modularity and (5) ease of system modification and enhancements. Knowledge about defects is represented in FDAS using a hierarchy of classes, with the slots representing defect attributes, and forward chaining rules. The inferencing process is controlled by slots of another distinct class hierarchy. Inference is made more efficient by hierarchical classification of the defects with pruning. The agenda (i.e. ordered set of hypotheses) is dynamically reset using actions attached to rules. The diagnosis information—information about the causes of the defects and remedial actions to be taken—is kept separate from the rules in the knowledge base. The user interface part of the system is also independent of the knowledge base, which facilitates easier tailoring of the system to meet the needs of different users. The user interaction with FDAS is menu-based and has been designed to minimize cognitive load on the user. FDAS has been extensively evaluated by in-house individuals who are experts in the task of fabric defects analysis. It has also been demonstrated to experts from the industry and is ready for field tests.

Notes: Abstract: This paper describes the use of the explanation-based learning (EBL) machine learning technique in the practical domain of knowledge acquisition for expert systems. A knowledge acquisition tool, EBKAT (Explanation-Based Knowledge Acquisition Tool), is described, which may be used in the development of knowledge bases for diagnostic expert systems. The functioning of EBKAT attempts to combine the full potential of a domain expert's skills and the power of explanation-based machine learning techniques. The EBL component is not employed in the acquisition of the knowledge base rules but is used to justify the knowledge entered and to relate it to the knowledge already in the system. It is suggested that the EBKAT tool goes some way towards overcoming the knowledge acquisition bottleneck and results in the acquisition of knowledge which is rich in contextual information.

Notes: Abstract: Knowledge-based systems have previously been restricted to capturing the knowledge of living human experts and, in the medical domain, to delaying the onset of death in living patients. The system described in this paper overcomes both these restrictions by providing knowledge-based support for the reanimation of dead patients, who may also be domain experts.There is a well-established literature on raising the dead to life and an extensive literature on counselling patients who have undergone traumatic experiences. Examination of this literature suggests that the actual reanimation process is a relatively simple process, so the system concentrates on the counselling and care aspects. Results so far are encouraging.The next version of the system is intended to include a natural language interface to handle the English-Aramaic interpretation which is expected to be necessary for the actual reanimation process: this version will require further funding and clearance from the appropriate ethical committees. Both of these are expected to present few difficulties.The success of this system demonstrates that application of proven KBS techniques to a domain previously considered intractable can produce surprisingly fast and impressive results; to date, over 90% of system modules have been successfully tested. It is likely that this success could be replicated in other areas and this is currently the subject of further study by the authors (Rugg & Phibes 1993b).

Notes: Abstract: In this paper we present a new approach to evaluating expert systems. Our conceptual framework is based on a socio-technical model that spawned some 39 technical and contextual evaluation criteria. These socio-technical dimensions of quality are identified, defined and supported. We suggest that the approach presented here is an alternative to the restrictive verification and validation techniques that seem to be prevalent.

Notes: Book reviewed in this article:Understanding Expert Systems Using Crystal, Mary Jackson

Notes: Abstract: Knowledge engineers often find that experts’ estimates of uncertainty change from one day to the next and therefore often seem unreliable. This article explores the unreliability of probability estimates. Forty undergraduates answered 31 questions concerning the probability of daily events at two separate times. Three answer modalities were available: probability, chances and percent of the time. This paper finds that reliability decreases when answer modalities change from one time to the next. It is hypothesized that problem-solving approaches changed along with the modalities. The subjects represented a wide range in reliability, with the most reliable subjects changing answer modalities less than the unreliable subjects. These results suggest that knowledge engineers should endeavor to have experts express their uncertainty estimates using consistent modalities.

Notes: Abstract: Developing a prototype can be crucial to the eventual success of an expert system. This paper describes an evaluation of four expert system tools that can be used for prototyping. It outlines the evaluation method used and details findings, considering hardware and software requirements, tool features, support for development and consultation, and overall suitability for prototyping an expert system application.

Notes: Book reviewed in this article:The Craft of Prolog, Richard A. O'KeefeObject-Oriented Programming with Smat It al k/V, Dusko Savíc

Notes: Abstract: This article describes the integration of an expert system shell (AllRound Expert System, AR/XPS) with a Unix-based 4GL application generator (Task Flow Management, TFM). TFM supports the client-server architecture of distributed applications and provides access to several relational databases, including Informix and Oracle. A short overview of the major features of TFM is given, with special regard to characteristics relevant for the integration of an expert system. The main focus lies in the architecture of AR/XPS, which contains rule-based and frame-based knowledge representation methods and which was implemented in Prolog; the user interface is totally unified with that of TFM, so that the user sees only one system and need not be aware that an expert system is present. AR/XPS has access to all features of TFM and to any databases present, so that an expert system can take decisions according to the current status of the database. At the end of this article a description of the Knowledge Base Creator is given and some remarks are made regarding our experience with pilot applications.

Notes: Abstract: Instigating the selection of a methodological approach for the development of a knowledge-based system (KBS) should not be trivialised. This paper sets out to enlighten the reader about the needs and difficulties in comparing methodologies. In doing so, a descriptive framework is presented which allows the depiction of essential features of a methodology. This is intended to simplify the comparative study of KBSs that a knowledge engineer might be involved in.

Notes: ProKappa is an expert system tool kit developed by IntelliCorp in C using X-Windows for graphical interface. The SUN 3 or 4 version costs $9995/£7000 and $2595/£1800 for the interactive C environment. This review covers ProKappa version 1.1, installed on a colour SUN SPARC Station 1 with the minimum recommended values of 12 Mb of memory and 30 Mb of swap space. IntelliCorp can be contacted in the USA at 1975 El Camino Real West, Mountain View, CA 94040-2216 (+1 (415) 965-5500) and in the UK at 10 Jewry Street, Winchester, Hampshire SO23 8RZ (+44 (0)962 735348).

Notes: Book reviewed in this article:Integrating knowledge-based and database management systems, Ruth KerryNonmonotonic reasoning: logical foundations of commonsense Gerhard BrewkaBuilding knowledge-based systems: towards a methodology John S. EdwardsThe Rise of the Expert Company—How Visionary Companies are Using Artificial ntellig ence to Achieve Higher Productivity and Prof its, Edward Feigenbaum

Notes: Abstract: The purpose of this paper is to draw attention to some important barriers to the practical application of expert systems to management problems. By drawing attention to these barriers, we show two findings: (a) that certain types of knowledge found in management situations are more likely to lead to the successful adoption of management expert systems (MESs) than others; (b) that a potential exists for an alternative form of MES application. The first finding has implications for knowledge elicitation. We propose that MESs developed from academic knowledge, which we define in specific terms, are more likely to succeed than those developed from working with managers in the field. Alternatively, feasibility studies should include an analysis of the type of knowledge which a manager is capable of providing to ensure that suitable knowledge is available for knowledge elicitation purposes. The second finding has implications for the developers of MESs at both research and commercial levels. We suggest the need for a check-list MES application, capable of converting responses to strategic and operational questions into managerial actions.

Notes: Artificial Intelligence Terminology: A Reference Guide Colin BeardonExpert Systems: A Decision Support Approach - With Applications in Management and Finance M. Klein and L. B. Methlie, AddisonThe Logical Basis for Computer Programming, Vol. 2: Deductive Systems Zohar Manna and RichardProlog Programming for Artificial Intelligence Ivan Bratko

Notes: Prolog III is available from PrologIA Luminy, Case 919 13288, Marseille Cedex 09, France. Tel: +33 91 26 86 36. Prices (French francs): Sun 3, 70 000; Sparc 100 000; Mac Plus/SE 30 000; Mac SE 30/II38 000; IBM PC 386 38 000. Prices exclude VAT. Universities are entitled to a 60% discount and research centres to 30%. Systems are also available for HP9000 (series 300 and series 800), VAX and DECstation.

Notes: Abstract: In this article we describe how two popular AI representation techniques—frames and production systems— can be usefully combined under a general AI object-oriented approach to problems which arise in the domain of hardware fault diagnosis. One of the main advantages of such a combination is that causal reasoning— crucial to the domain under consideration — can also be naturally and effectively represented. In order to put the combination of frames and production systems on a sound methodological footing, we first provide a knowledge engineering methodology which is an object-oriented re-interpretation of ontological analysis.

Notes: Book reviewd in this article:Developing Expert Systems A Knowledge Engineer's Handbook for Rules and Objects, Edmund C. Payne, Robert C. McArthurBuilding Large Knowledge-Based Systems. Douglas B. Lenat, R. V. Guha.Designing Systems A Guide to Selecting Implementation Techniques. Paul J. Kline and Steven B. Dolins.

Notes: There have been many proposals for adding sound implementations of numeric processing to Prolog. This paper describes an approach to numeric constraint processing which has been implemented in Echidna, a new constraint logic programming (CLP) language. Echidna uses consistency algorithms which can actively process a wider variety of numeric constraints than most other CLP systems, including constraints containing some common nonlinear functions. A unique feature of Echidna is that it implements domains for real-valued variables with hierarchical data structures and exploits this structure using a hierarchical arc consistency algorithm specialized for numeric constraints. This gives Echidna two advantages over other systems. First, the union of disjoint intervals can be represented directly. Other approaches require trying each disjoint interval in turn during backtrack search. Second, the hierarchical structure facilitates varying the precision of constraint processing. Consequently, it is possible to implement more effective constraint processing control algorithms which avoid unnecessary detailed domain analysis. These advantages distinguish Echidna from other CLP systems for numeric constraint processing.

Notes: We describe a representation and set of inference techniques for the dynamic construction of probabilistic and decision-theoretic models expressed as networks. In contrast to probabilistic reasoning schemes that rely on fixed models, we develop a representation that implicitly encodes a large number of possible model structures. Based on a particular query and state of information, the system constructs a customized belief net for that particular situation. We develop an interpretation of the network construction process in terms of the implicit networks encoded in the database. A companion method for constructing belief networks with decisions and values (decision networks) is also developed that uses sensitivity analysis to focus the model building process. Finally, we discuss some issues of control of model construction and describe examples of constructing networks.

Notes: Generating action sequences to achieve a set of goals is a computationally difficult task. When multiple goals are present, the problem is even worse. Although many solutions to this problem have been discussed in the literature, practical solutions focus on the use of restricted mechanisms for planning or the application of domain dependent heuristics for providing rapid solutions (i.e., domain-dependent planning). One previously proposed technique for handling multiple goals efficiently is to design a planner or even a set of planners (usually domain-dependent) that can be used to generate separate plans for each goal. The outputs are typically either restricted to be independent and then concatenated into a single global plan, or else they are merged together using complex heuristic techniques. In this paper we explore a set of limitations, less restrictive than the assumption of independence, that still allow for the efficient merging of separate plans using straightforward algorithmic techniques.In particular, we demonstrate that for cases where separate plans can be individually generated, we can define a set of limitations on the allowable interactions between goals that allow efficient plan merging to occur. We propose a set of restrictions that are satisfied across a significant class of planning domains. We present algorithms that are efficient for special cases of multiple plan merging, propose a heuristic search algorithm that performs well in a more general case (where alternative partially ordered plans have been generated for each goal), and describe an empirical study that demonstrates the efficiency of this search algorithm.

Notes: Based on psychological studies which show that metaphors and other non-literal constructions are comprehended in the same amount of time as comparable literal constructions, some researchers have concluded that literal meaning is not computed during comprehension of non-literal constructions. In this paper, we suggest that the empirical evidence does not rule out the possibility that literal meaning is constructed. We present a computational model of comprehension of non-literal expressions which is consistent with the data, but in which literal meaning is computed. This model has been implemented as part of a unification-based natural language processing system, called LINK.

Notes: There are two pertinent themes in the study of idioms in the area of natural language processing. Firstly, idioms should be defined and located in the space of non-literal expressions. This will be the first aim of this paper. Secondly, a processing model should be developed. In this paper, the application of knowledge representation techniques in three different models for the representation and processing of idioms are discussed. The first, a symbolic procedural model extends the two-level model which was originally developed in computational morphology. The second is a simple localist connectionist model. The third, a symbolic hierarchical model, represents idioms as part of a lexicon conceived as an inheritance hierarchy. A comparison between the models is made in which the focus lies on the resolution of the ambiguity of idioms, the relation between the literal and non-literal interpretation and the syntactic flexibility of idiomatic expressions.

Notes: Metallel is a program that incorporates marker passing techniques within a preference/collative semantics framework. This allows for the simultaneous generation of literal and non-literal meaning representations, while allowing for a much greater degree of parallelism during processing. In addition, we have integrated metonymic and metaphoric inferencing into one procedure, arguing that at least some types of metaphor can be represented as parallel metonymies. A number of examples are presented which show that metallel's output is roughly equivalent to conventional, rule-based approaches to metonymy.

Notes: Once viewed as a rhetorical and superficial language phenomenon, metaphor is now recognized to serve a fundamental role in our conceptual structuring and language comprehension processes. In particular, it is argued that certain experiential metaphors based upon intuitions of spatial relations are inherent in the conceptual organization of our most abstract thoughts. In this paper we present a two-stage computational model of metaphor interpretation which employs a spatially founded semantics to broadly characterize the meaning carried by a metaphor in terms of a conceptual scaffolding, an interim meaning structure around which a fuller interpretation is fleshed out over time. We then present a semantics for the construction of conceptual scaffolding which is based upon core metaphors of collocation, containment and orientation. The goal of this scaffolding is to maintain the intended association of ideas even in contexts in which system knowledge is insufficient for a complete interpretation. This two-stage system of scaffolding and elaboration also models the common time lapse between initial metaphor comprehension and full metaphor appreciation. Several mechanisms for deriving elaborative inference from scaffolding structures, particularly in cases of novel or creative metaphor, are also presented. While the system developed in this paper has significant practical application, it also demonstrates that core spatial metaphors clearly play a central role in metaphor comprehension.

Notes: PAU is an all-paths chart-based unification parser that uses the same uniform representation for regular syntax, irregular syntax such as idioms, and semantics. PAU's representation has very little redundancy, simplifying the task of adding new semantics and syntax fo PAU's knowledge base. PAU uses relations between the syntax and semantics to avoid the proliferation of rules found in semantic grammars. By encoding semantics at the same level of representation as syntax, PAU is able to use semantic constraints early in the parse to eliminate semantically anomalous syntactic interpretations. Examples are given to show how PAU can handle the many eccentricities of different idioms using the same mechanisms as are used to handle regular syntax and semantics. These include the ability of some idioms, but not other idioms of the same syntactic form to undergo passivization, particle movement, action nominalization, indirect object movement, modification by adjectives, gerundive nominalization, prepositional phrase preposing, and topicalization. PAU's representation is bidirectional and is also used by a companion generator. PAU is designed to be efficient, runs in real time on typical workstations, and is being used in a number of natural language systems.

Notes: Evidence from real discourse suggests that beliefs and other mental states (propositional attitudes) are often viewed by speakers and other agents in a metaphorical way. Typical metaphors are MIND-AS-CONTAINER—the view of the mind as a container, with thoughts being physical objects inside it—or IDEAS-AS-INTERNAL-UTTERANCES—the view of thoughts as natural language utterances inside an agent's head. It is therefore necessary for AI systems for mental-state representation/reasoning to reason within such views. This approach contrasts with the highly abstract logical stance adopted in most propositional attitude research. A formal representation scheme based on the various metaphors has been partially developed. In this paper, it is mainly the MIND-AS-CONTAINER segment of the formal representation scheme that is detailed. Inference processes operating over the scheme are also presented. The crucial distinguishing feature of the representation scheme is that the description of mental states is directly based on physical predicates, objects and so on, as opposed to abstract, tailor-made, mental ones. That is, the representation scheme is itself explicitly metaphor-imbued.

Notes: Theories and computational models of metaphor comprehension generally circumvent the question of metaphor versus “anomaly” in favor of a treatment of metaphor versus literal language. Making the distinction between metaphoric and “anomalous” expressions is subject to wide variation in judgment, yet humans agree that some potentially metaphoric expressions are much more comprehensible than others. In the context of a program which interprets simple isolated sentences that are potential instances of cross-modal and other verbal metaphor, I consider some possible coherence criteria which must be satisfied for an expression to be “conceivable” metaphorically. Metaphoric constraints on object nominals are represented as abstracted or extended along with the invariant structural components of the verb meaning in a metaphor. This approach distinguishes what is preserved in metaphoric extension from that which is “violated”, thus referring to both “similarity” and “dissimilarity” views of metaphor. The role and potential limits of represented abstracted properties and constraints is discussed as they relate to the recognition of incoherent semantic combinations and the rejection or adjustment of metaphoric interpretations.

Notes: A linguistic form's compositional, timeless meaning can be surrounded or even contradicted by various social, aesthetic, or analogistic companion meanings. This paper addresses a series of problems in the structure of spoken language discourse, including turn-taking and grounding. It views these processes as composed of fine-grained actions, which resemble speech acts both in resulting from a computational mechanism of planning and in having a rich relationship to the specific linguistic features which serve to indicate their presence. The resulting notion of Conversation Acts is more general than speech act theory, encompassing not only the traditional speech acts but turn-taking, grounding, and higher-level argumentation acts as well. Furthermore, the traditional speech acts in this scheme become fully joint actions, whose successful performance requires full listener participation. This paper presents a detailed analysis of spoken language dialogue. It shows the role of each class of conversation acts in discourse structure, and discusses how each class can be processed and recognized. Conversation acts, it will be seen, better account for the success of conversation than speech act theory alone. They also provide a pragmatic view of meaning in which the literal/non-literal distinction is simply irrelevant.

Notes: We evaluate the success of the qualitative physics enterprise in automating expert reasoning about physical systems. The field has agreed, in essentials, upon a modeling language for dynamical systems, a representation for behavior, and an analysis method. The modeling language consists of generalized ordinary differential equations containing unspecified constants and monotonic functions; the behavioral representation decomposes the state space described by the equations into discrete cells; and the analysis method traces the transitory response using sign arithmetic and calculus. The field has developed several reasoners based on these choices over some 15 years. We demonstrate that these reasoners exhibit severe limitations in comparison with experts and can analyze only a handful of simple systems. We trace the limitations to inappropriate assumptions about expert needs and methods. Experts ordinarily seek to determine asymptotic behavior rather than transient response, and use extensive mathematical knowledge and numerical analysis to derive this information. Standard mathematics provides complete qualitative understanding of many systems, including those addressed so far in qualitative physics. Preliminary evidence suggests that expert knowledge and reasoning methods can be automated directly, without restriction to the accepted language, representation, and algorithm. We conclude that expert knowledge and methods provide the most promising basis for automating qualitative reasoning about physical systems.

Notes: The paper by Sacks and Doyle that is the focus of this debate resembles previous papers by Cheeseman and McDermott, leaping from the observation that a specific application of some AI technology is unable to solve a problem to the conclusion that the technology itself is of limited value. We argue that claims such as this should be made more cautiously in the future, and make constructive suggestions about future qualitative physics research based on Sacks and Doyle's results.

Notes: The starting point for this commentary is Sacks’ and Doyle's conclusion that a central problem for qualitative physics is automating mathematical model formulation. We believe that model formulation is also a central problem for operations research, and although we have focused on models for production planning rather than for engineering systems analysis, our experience confirms that of Sacks and Doyle, that at least parts of model formulation are amenable to automation. In terms of their recommendations for future research, their strategy seems to emphasize the formalization of mathematical knowledge. We wish to stress that understanding the design or analysis context, the problem domain, and resource constraints on the modeling process is equally important. Methods used in cognitive psychology for understanding human problem solving, such as protocol analysis, can complement mathematical study by helping us understanding the processing that human modelers use to bring mathematical knowledge to bear. We have been using the results of such analyses to guide the creation of a model formulation system (MFS) within the Soar architecture. The use of cognitive studies and computer models in tandem seems to represent a viable strategy for making progress in this area.

Notes: Sacks & Doyle provide an excellent overview of the fundamental limitations of the SPQR representations for reasoning about the qualitative properties of dynamic systems. We take this opportunity to outline some new directions for qualitative reasoning. In this paper, we provide a rigorous mathematical characterization for the term “qualitative property” in the context of static and dynamic systems. Based on these characterizations, we show that interval representations are well suited for reasoning about the qualitative properties of static systems such as qualitative comparative statics and qualitative stability. Moreover, we also show that symbolic computations help in the derivation of useful global properties of dynamic systems which can be used to guide numerical sampling of differential equations. The integration of symbolic and numeric methods provides a powerful approach for automating the qualitative analysis of differential equations.

Notes: The economic theory of rationality promises to equal mathematical logic in its importance for the mechanization of reasoning. We survey the growing literature on how the basic notions of probability, utility, and rational choice, coupled with practical limitations on information and resources, influence the design and analysis of reasoning and representation systems.

Notes: A formal description is given of a connectionist implementation of discrete relaxation for labelled graph matching. The network is shown to converge. The desired behavior of the algorithm is formally specified; then it is proved that the result of the relaxation meets the formal goal. The network is limited by complexity considerations to the detection and propagation of unary and binary consistency constraints. The application is fast parallel indexing into a memory of object models, based on a visually derived junction/link structure description. Implementation experiments are presented, and explicit and exact space and time requirements are developed.

Notes: A truth maintenance system is a subsystem that manages the utilization of assumptions in the reasoning process of a problem solver. Doyle's original motivation for creating a truth maintenance system was to augment a reasoning system with a control strategy for activities concerning its nonmonotonic state of beliefs. Hitherto, much effort has been invested in designing and implementing the concept of truth maintenance, and little effort has been dedicated to the formalization that is essential to understanding it. This paper provides a complete formalization of the principle of truth maintenance. Motivated by Reiter and de Kleer's preliminary report on the same subject, this paper extends their study and gives a formal account of the concept of truth maintenance under the general title of assumption-based reasoning. The concept of assumption-based theory is defined, and the notions of explanation and direct consequence are presented as forms of plausible conclusions with respect to this theory. Additionally, the concepts of extension and irrefutable sentences are discussed together with other variations of explanation and direct consequence. A set of algorithms for computing these conclusions for a given theory are presented using the notion of prime implicates. Finally, an extended example on Boolean circuit diagnosis is shown to exemplify these ideas.

Notes: Much research in machine learning has been focused on the problem of symbol-level learning (SLL), or learning to improve the performance of a program given examples of its behavior on typical inputs. A common approach to symbol-level learning is to use some sort of mechanism for saving and later reusing the solution paths used to solve previous search problems. Examples of such mechanisms are macro-operator learning, explanation-based learning, and chunking. However, experimental evidence that these mechanisms actually improve performance is inconclusive. This paper presents a formal framework for analysis of symbol-level learning programs, and then uses this framework to investigate a series of solution-path caching mechanisms which provably improve performance. The analysis of these mechanisms is illuminating in many respects; in particular, in order to obtain positive results, it is necessary to use a novel representation for a set of solution paths, and also to apply certain unusual optimizations to a set of solution paths. Several of the predictions made by the model have been confirmed by recently published experiments.