ALBERT

Notes: The Coach system, a computer simulation of a human tutor, was constructed with the goal of obtaining a better understanding of how a tutor interprets the student's behavior, diagnoses difficulties, and gives advice. Coach gives advice to a student who is learning a simple computer programming language. Its intelligence is based on a hierarchy of active schemas that represent the tutor's general concepts and on more specific information represented in a semantic network. The coordination of conceptually guided and data-driven processing enables the Coach system to interpret student behavior, recognize errors, and give advice to the student.

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: The input to the described program, in learning mode, consists of examples of starting graph and result graph pairs. The starting graph is transformable into the result graph by adding or deleting certain edges and vertices. The essential common features of the starting graphs are stored together with specifications of the edges and vertices to be deleted or added. This latter information is obtained by mapping each starting graph onto the corresponding result graph. On subsequent input of similar starting graphs without a result graph, the program, in performance mode, recognizes the characterizing set of features in the starting graph and can perform the proper transformation on the starting graph to obtain the corresponding result graph. The program also adds the production to its source code so that after recompilation it is permanently endowed with the new production. If any feature which lacks the property “ordinary” is discovered in the starting graph and only one example has been given, then there is feedback to the user including a request for more examples to ascertain whether the extraordinary property is a necessary part of the situation.

Notes: The ability to reuse existing plans to solve new planning problems can enable a domain-independent planner to improve its average case efficiency by exploiting the problem distribution and avoiding repetition of planning effort. The pay-off from plan reuse, however, crucially depends on finding effective solutions to two important underlying control problems: (i) controlling the retrieval of an appropriate plan and mapping to be reused in a new situation, and (ii) controlling the modification (refitting) of the retrieved plan so as to minimize perturbation to the applicable parts of the plan. This paper is concerned with the development of efficient domain-independent solutions to these two problems. For the retrieval, it provides a domain independent similarity metric that utilizes the plan causal dependency structure to estimate the utility of reusing a given plan in a new problem situation. For the refitting, it presents a minimum-conflict heuristic, again based on the causal dependency structure of the plan, to conservatively control the modification. The paper also discusses the implementation and evaluation of these strategies within the PRIAR plan modification framework.

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: To plan means reasoning about possible actions, but a robot must also reason about actual events. This paper proposes a formal theory about actual and possible events. It presents a new modal logic as a notation for this theory and a technique for planning in the modal logic using a first-order theorem prover augmented with simple modal reasoning. This avoids the need for a general modal-logic theorem prover. Adding beliefs to this theory raises an interesting problem for which the paper offers a tentative solution.

Notes: Several computational theories of early visual processing, such as Marr's zero-crossing theory, are biologically motivated and based largely on the well-known difference of Gaussians (DOG) receptive-field model of retinal processing. We examine the physiological relevance of the DOG, particularly in the light of evidence indicating significant spatiotemporal inseparability in the behaviour of retinal cell types. From the form of the inseparability we find that commonly accepted functional interpretations of retinal processing based on the DOG, such as the Laplacian of a Gaussian and zero crossings, are not valid for time-varying images. In contrast to current machine-vision approaches, which attempt to separate form and motion information at an early stage, it appears that this is not the case in biological systems. It is further shown that the qualitative form of this inseparability provides a convenient precursor to the extraction of both form and motion information. We show the construction of efficient mechanisms for the extraction of orientation and two-dimensional normal velocity through the use of a hierarchical computational framework. The resultant mechanisms are well localized in space-time and can be easily tuned to various degrees of orientation and speed specificity.

Notes: The use of a single grammar in natural language parsing and generation is most desirable for a variety of reasons, including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. These characteristics have been noted before by several researchers, but it was only recently that more serious attention started to be paid to the problem of creating a bidirectional system for natural language processing. In this paper we discuss a somewhat more radical version of the problem: given a parser for a language, can we reverse it so that it becomes an efficient generator for the same language? Furthermore, since both the parser and the generator are based upon the same grammar, are there any normalization conditions upon the form of the grammar that must be met in order to assure the maximum efficiency of the reversed program? Can other grammars be transformed into the normal form? We describe the results of an experiment with PROLOG-based logic grammar which has been derived from a substantial-coverage string grammar for English. We present an alogorithm for automated inversion of a unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments for predicates. We discuss the scope of the present version of the algorithm and then point out several possible avenues for extension. We also outline a preliminary solution to the question of grammar's “normal form” and suggest a handful of normalizing transformations that can be used to enhance the efficiency of the generator. This research interacts closely with a Japanese-English machine translation project at New York University, for which the first implementation of the inversion algorithm has been prepared.

Notes: Halperri argues for alternative non-Bayesian approaches to uncertainty based on problems he perceives in the Bayesian approach. In particular, he argues for a distinction between degrees of belief and statistical statements (based on the concept of random sampling). In this response I show that there is no difference between these two concepts in the Bayesian framework, and that the replacement of variables by constants in probabilistic predicate calculus expressions is valid, despite Halpern's objections. The main reason for his rejection of the simpler approach is that he does not condition his belief statements on the evidence used to form these beliefs, and so gets into trouble when new evidence is received. This failure to properly take evidence into account invalidates most of his other criticisms. While I approve of his call for more formal rigor in representing Bayesian practice, his claim to have provided a semantics is misleading – what he has provided is not operational.

Notes: A hierarchical planning system achieves efficiency by planning with the most important conditions first, and considering details later in the planning process. Few attempts have been made to formalize the structure of the planning knowledge for hierarchical planning. For a given domain, there is usually more than one way to define its planning knowledge. Some of the definitions can lead to efficient planning, while others may not. In this paper, we provide a set of restrictions which defines the relationships between a non-primitive action and its set of subactions. When satisfied, these restrictions guarantee improved efficiency for hierarchical planning. One important feature of these restrictions is that they are syntactic and therefore do not depend on the particular structure of any plan. Along with these restrictions, we also provide algorithms for preprocessing the planning knowledge of a hierarchical planner. When used during planning, the preprocessed operator hierarchies can enable a planner to significantly reduce its search space.

Notes: During incremental concept learning from examples, tentative hypotheses are formed and then modified to form new hypotheses. When there is a choice among hypotheses, bias is used to express a preference. Bias may be expressed by the choice of hypothesis language, it may be implemented as an evaluation function for selecting among hypotheses already generated, or it may consist of screening potential hypotheses prior to hypothesis generation. This paper describes the use of the third method. Bias is represented explicitly both as assumptions that reduce the space of potential hypotheses and as procedures for testing these assumptions. There are advantages gained by using explicit assumptions. One advantage is that the assumptions are meta-level hypotheses that are used to generate future, as well as to select between current, inductive hypotheses. By testing these meta-level hypotheses, a system gains the power to anticipate the form of future hypotheses. Furthermore, rigorous testing of these meta-level hypotheses before using them to generate inductive hypotheses avoids consistency checks of the inductive hypotheses. A second advantage of using explicit assumptions is that bias can be tested using a variety of learning methods.

Notes: This paper describes LEW (learning by watching), an implementation of a novel learning technique, and discusses its application to the learning of plans. LEW is a domain-independent learning system with user-limited autonomy that is designed to provide robust performance in realistic knowledge acquisition tasks in a variety of domains. It partly automates the knowledge acquisition process for different knowledge types, such as concepts, rules, and plans. The inputs to the system, which we call cues, consist of an environmental component and of pairs containing a problem and its solution. Unlike traditional forms of “learning from examples”, in which the system uses the teacher's answer to improve the result of a prior generalization of an example, LEW treats the problem-solution or question-answer instances, i. e., the cues themselves, as the basic units for generalization.

Notes: Although there are many arguments that logic is an appropriate tool for artificial intelligence, there has been a perceived problem with the monotonicity of classical logic. This paper elaborates on the idea that reasoning should be viewed as theory formation where logic tells us the consequences of our assumptions. The two activities of predicting what is expected to be true and explaining observations are considered in a simple theory formation framework. Properties of each activity are discussed, along with a number of proposals as to what should be predicted or accepted as reasonable explanations. An architecture is proposed to combine explanation and prediction into one coherent framework. Algorithms used to implement the system as well as examples from a running implementation are given.

Notes: In the past, Kripke structures have been used to specify the semantic theory of various modal logics. More recently, modal structures have been developed as an alternative to Kripke structures for providing the semantics of such logics. While these approaches are equivalent in a certain sense, it has been argued that modal structures provide a more appropriate basis for representing the modal notions of knowledge and belief. Since these notions, rather than the traditional notions of necessity and possibility, are of particular interest to artificial intelligence, it is of interest to examine the applicability and versatility of these structures. This paper presents an investigation of modal structures by examining how they may be extended to account for generalizations of Kripke structures. To begin with, we present an alternative formulation of modal structures in terms of trees; this formulation emphasizes the relation between Kripke structures and modal structures, by showing how the latter may be obtained from the former by means of a three-step transformation. Following this, we show how modal structures may be extended to represent generalizations of possible worlds, and to represent generalizations of accessibility between possible worlds. Lastly, we show how modal structures may be used in the case of a full first-order system. In all cases, the extensions are shown to be equivalent to the corresponding extension of Kripke structures.

Notes: A definition of extended definite clause grammars and their relationship to unrestricted grammars are presented. A method for translating extended definite clause grammars describing unrestricted grammars into executable prolog programs is given. Three different parsing techniques are presented, and for each a complete presentation of how to incorporate unrestricted grammars in the actual formalism is done. Extended definite clause grammar is a powerful formalism usable for specifying grammars in natural language processing systems.

Notes: This paper describes a qualitative technique for interpreting graphical data. Given a set of numerical observations regarding the behaviour of a system, its attributes can be determined by plotting the data and qualitatively comparing the shape of the resulting graph with graphs of system behaviour models. Qualitative data modeling incorporates techniques from pattern recognition and qualitative reasoning to characterize observed data, generate hypothetical interpretations, and select models that best fit the shape of the data. Domain-specific knowledge may be used to substantiate or refute the likelihood of hypothesized interpretations. The basic data modeling technique is domain independent and is applicable to a wide range of problems. It is illustrated here in the context of a knowledge-based system for well test interpretation.

Notes: Most shape-from-shading methods assume that surface reflectance is constant within large image regions. This assumption is violated in natural scenes with objects made from different materials. We present a more general method for recovering shape from shading, assuming that surfaces are smooth and albedo is piecewise constant, as would be the case if a Mondrian image was painted on a smooth curved surface. Our method is based on combining Brooks and Horn's method for shape recovery with the recovery of albedo using stochastic relaxation.

Notes: Artificial neural networks capable of doing hard learning offer a new way to undertake automatic speech recognition. The Boltzmann machine algorithm and the error back-propagation algorithm have been used to perform speaker normalization. Spectral segments are represented by spectral lines. Speaker-independent recognition of place of articulation for vowels is performed on lines. Performance of the networks is shown to depend on the coding of the input data. Samples were extracted from continuous speech of 38 speakers. The error rate obtained (4.2% error on test set of 72 samples with the Boltzmann machine and 6.9% error with error back-propagation) is better than that of previous experiments, using the same data, with continuous Hidden Markov Models (7.3% error on test set and 3% error on training set). These experiments are part of an attempt to construct a data-driven speech recognition system with multiple neural networks specialized to different tasks. Results are also reported on the recognition performance of other trained networks, such as one trained on the E-set consonants.

Notes: The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.

Notes: Reasoning about change requires predicting how long a proposition, having become true, will continue to be so. Lacking perfect knowledge, an agent may be constrained to believe that a proposition persists indefinitely simply because there is no way for the agent to infer a contravening proposition with certainty. In this paper, we describe a model of causal reasoning that accounts for knowledge concerning cause-and-effect relationships and knowledge concerning the tendency for propositions to persist or not as a function of time passing. Our model has a natural encoding in the form of a network representation for probabilistic models. We consider the computational properties of our model by reviewing recent advances in computing the consequences of models encoded in this network representation. Finally, we discuss how our probabilistic model addresses certain classical problems in temporal reasoning (e. g., the frame and qualification problems).

Notes: It is commonplace in artificial intelligence to divide an agent's explicit beliefs into two parts: the beliefs explicitly represented or manifest in memory, and the implicitly represented or constructive beliefs that are repeatedly reconstructed when needed rather than memorized. Many theories of knowledge view the relation between manifest and constructive beliefs as a logical relation, with the manifest beliefs representing the constructive beliefs through a logic of belief. This view, however, limits the ability of a theory to treat incomplete or inconsistent sets of beliefs in useful ways. We argue that a more illuminating view is that belief is the result of rational representation. In this theory, the agent obtains its constructive beliefs by using its manifest beliefs and preferences to rationally (in the sense of decision theory) choose the most useful conclusions indicated by the manifest beliefs.

Notes: We realize a computer simulation of children's reasoning in arithmetic word problem solving. The model parses the terms provided to the system in natural language and, while it performs this task, it tries to build its representation of the described situation by the way that the child elaborates a mental problem representation. This image results from three components: semantic knowledge, text comprehension process, and problem-solving strategies.We emphasize the adequacy, on one hand, between the knowledge representation and manipulation by an object formalism and, on the other hand, between the structure and the use of knowledge interacting in this application.The specific aspect of our model is that the internal representation is realized in an object-oriented language whose main properties are accurately exploited. This choice allows one to combine the descriptive characteristics of each piece of knowledge with its implication in the progress of the process.The program is supported by the analysis of individual protocols of some children: they allow us to hypothesize on the way the children modify their problem representation during the solving task.We describe the main objects of the model. Then we simulate on the terms of a problem, the way that the process is driven by expectations of contextually relevant information.

Notes: It is currently thought in the knowledge-based systems (KBS) domain that sophisticated tools are necessary for helping an expert with the difficult task of knowledge acquisition. The problem of detecting inconsistencies is especially crucial. The risk of inconsistencies increases with the size of the knowledge base; for large knowledge bases, detecting inconsistencies “by hand” or even by a superficial survey of the knowledge base is impossible. Indeed, most inconsistencies are due to the interaction between several rules via often deep deductions. In this paper, we first state the problem and define our approach in the framework of classical logic. We then describe a complete method to prove the consistency (or the inconsistency) of knowledge bases that we have implemented in the COVADIS system.

Notes: This paper provides a systematic treatment of possibly imprecisely or vaguely specified numerical quantifiers in default syllogisms, following an approach initiated by Zadeh. The obtained propagation rules are derived from simple properties of relative cardinality or, equivalently, conditional probability. Uncertainty in the description of numerical quantifiers is handled using possibility theory and, particularly, fuzzy arithmetic. The advantages of this default reasoning method are its ability to model any kind of quantifier and to build new defaults by chaining existing ones, in a rigorous manner. This approach also emphasizes the difference between two types of uncertain pieces of knowledge, i.e., conjectures versus general rules.

Notes: GETA (Groupe d'études pour la traduction automatique) is a research team working basically in the domain of machine translation. GETA's software system, ARIANE-78, has been tested over various pairs of relatively unrelated languages. Being a product of the late seventies, the system misses out on some of the artificial intelligence technology, particularly that of the eighties. Nevertheless, GETA carries out some research related to artificial intelligence within a general effort to bring improvements to the current system. This paper reports on an effort to embed such work within the framework of an entirely new system based on ideas from expert systems, significantly departing from the methodology of the current system (and that of other currently implemented machine translation systems). The proposed architecture aims for total modularity and flexibility and some degree of intelligence.

Notes: This paper describes a dialogue-based system which is intended as an intelligent natural language interface to the French Yellow Pages. We do not assume that the user knows how the Yellow Pages are organized, and we paraphrase his request, if necessary, so as to better search for the desired information. We do, however, assume that the reason the user is on line is to find an address and phone number for some supplier.There are three basic modules used in our system: parser, dialogue manager, and generator. The first two exist (and are constantly being extended); the generation module is still only a set of functional specifications which will be outlined later in this article.

Notes: Logical omniscience may be described (roughly) as the state of affairs in which an agent explicitly believes anything which is logically entailed by that agent's beliefs. It is widely agreed that humans are not logically omniscient, and that an adequate formal model of belief, coupled with a correct semantic theory, would not entail logical omniscience. Recently, two prominent models of belief have emerged which purport both to avoid logical omniscience and to provide an intuitively appealing semantics. The first of these models is due to Levesque (1984b); the second to Fagin and Halpem (1985). It is argued herein that each of these models faces serious difficulties. Detailed criticisms are presented for each model, and a computationally oriented theory of intensions is presented which provides the foundation for a new formal model of belief. This formal model is presented in a decidable subset of first-order logic and is shown to provide a solution to the general problem of logical omniscience. The model provides for the possibility of belief revision and places no a priori restrictions upon an agent's representation language.

Notes: The relative expressive power of a sentential operator □α is compared to that of a syntactical predicate L(‘α’) in the setting of first-order logics. Despite well-known results by Montague and by Thomason that claim otherwise, any of the so-called “modal” logics of knowledge and belief can be compiled into classical first-order logics that have a corresponding predicate on sentences. Moreover, through the use of a partial truth predicate, the standard modal axiom schemata can be translated into single sentences, making it possible to use conventional first-order logic theorem provers to directly derive results in a wide class of modal logics.

Notes: The Graph Theorist, GT, is a system that performs mathematical research in graph theory. From the definitions in its input knowledge base, GT constructs examples of mathematical concepts, conjectures and proves mathematical theorems about concepts, and discovers new concepts. Discovery is driven both by examples and by definitional form. The discovery processes construct a semantic net that links all of GT's concepts together.Each definition is an algebraic expression whose semantic interpretation is a stylized algorithm to generate a class of graphs correctly and completely. From a knowledge base of these concept definitions, GT is able to conjecture and prove such theorems as “The set of acyclic, connected graphs is precisely the set of trees” and “There is no odd-regular graph on an odd number of vertices.” GT explores new concepts either to develop an area of knowledge or to link a newly acquired concept into a pre-existing knowledge base. New concepts arise from the specialization of an existing concept, the generalization of an existing concept, and the merger of two or more existing concepts. From an initial knowledge base containing only the definition of “graph,” GT discovers such concepts as acyclic graphs, connected graphs, and bipartite graphs.

Notes: Program debugging is an important part of the domain expertise required for intelligent tutoring systems that teach programming languages. This article explores the process by which student programs can be automatically debugged in order to increase the instructional capabilities of these systems. The research presented provides a methodology and implementation for the diagnosis and correction of nontrivial recursive programs. In this approach, recursive programs are debugged by repairing induction proofs in the Boyer-Moore logic. The induction proofs constructed and debugged assert the computational équivalence of student programs to correct exemplar solutions. Exemplar solutions not only specify correct implementations but also provide correct code to replace buggy student code. Bugs in student code are repaired with heuristics that attempt to minimize the scope of repair.The automated debugging of student code is greatly complicated by the tremendous variability that arises in student solutions to nontrivial tasks. This variability can be coped with, and debugging performance improved, by explicit reasoning about computational semantics during the debugging process. This article supports these claims by discussing the design, implementation, and evaluation of Talus, an automatic debugger for LISP programs, and by examining related work in automated program debugging.Talus relies on its abilities to reason about computational semantics to perform algorithm recognition, infer code teleology, and to automatically detect and correct nonsyntactic errors in student programs written in a restricted, but nontrivial, subset of LISP. Solutions can vary significantly in algorithm, functional decomposition, role of variables, data flow, control flow, values returned by functions, LISP primitives used, and identifiers used. Solutions can consist of multiple functions, each containing multiple bugs. Empiricial evaluation demonstrates that Talus achieves high performance in debugging widely varying student solutions to challenging tasks.

Notes: Machine instructional planners use changing and uncertain data to incrementally configure plans and control the execution and dynamic refinement of these plans. Current instructional planners cannot adequately plan, replan, and monitor the delivery of instruction. This is due in part to the fact that current instructional planners are incapable of planning in a global context, developing competing plans in parallel, monitoring their planning behavior, and dynamically adapting their control behavior. In response to these and other deficiencies of instructional planners a generic system architecture based on the blackboard model was implemented. This self-improving instructional planner (SUP) dynamically creates instructional plans, requests execution of these plans, replans, and improves its planning behavior based on a student's responses to tutoring. Global planning was facilitated by explicitly representing decisions about past, current, and future plans on a global data structure called the plan blackboard. Planning in multiple worlds is facilitated by labeling plan decisions by the context in which they were generated. Plan monitoring was implemented as a set of monitoring knowledge sources. The flexible control capability for instructional planner was adapted from the blackboard architecture BB1. The explicit control structure of SUP enabled complex and flexible planning behavior while maintaining a simple planning architecture.

Notes: This paper compares certain aspects of situation semantics and Montague grammar and points out some issues related to natural language programming. It provides and introduction to certain basic concepts of situation semantics and makes some tentative claims about possible advantages of situation semantics.

Notes: This paper synthesizes a number of approaches to concept representation and learning in a multilayered model. The paper emphasizes what has been called similarity-based learning (SBL) from examples, although this review is extended to address wider issues. The paper pays particular attention to requirements for incremental and uncertain environments, and to interrelationships among concept purpose, concept representation, and concept learning.One goal of the paper is to unite some of the notions underlying recent research, in an attempt to construct a more complete and extensible framework. This framework is designed to capture representations and methods such as those based on hypothesis search and bias selection, and to extend the ideas for greater system capability. This leads to a specific perspective for multilayered learning which has several advantages, such as greater clarity, more uniform learning, and more powerful induction.The approach clarifies and unifies various aspects of the problem of concept learning. Some results'are (1) Various concept representations (such as logic, prototypes, and decision trees) are subsumed by a standard form which is well suited to learning, particularly in incremental and uncertain environments; (2) Concept learning may be enhanced by exploiting a particular phenomenon in many spaces-this phenomenon is a certain kind of smoothness or regularity, one instance of which underlies the similarity in SBL systems; (3) The paper treats the phenomenon in a general way and applies it hierarchically. This has various advantages of uniformity. For example the model allows layered learning algorithms for concept learning all to be instantiations of one basic algorithm. A single kind of representation (an instantiation of the standard form) is prominent at each level. The combination of representation and algorithm allows fast, accurate, concise, and robust concept learning.

Notes: This paper presents an approach to learning to control a dynamic physical system. The approach has been implemented in a program named CART, and applied to a simple physical system studied previously by several researchers. Experiments illustrate that a control method is learned in about 16 trials, an improvement over previous learning programs.

Notes: A formal, foundational approach to autonomous knowledge acquisition is presented. In particular, “learning from examples” and “learning from being told” and the relation of these approaches to first-order representation systems are investigated. It is assumed initially that the only information available for acquisition is a stream of facts, or ground atomic formulae, describing a domain. On the basis of this information, hypotheses expressed in set-theoretic terms and concerning the application domain may be proposed. As further instances are received, the hypothesized relations may be modified or discarded, and new relations formed. The intent though is to characterize those hypotheses that may potentially be formed, rather than to specify the subset of the hypotheses that, for whatever reason, should be held.Formal systems are derived by means of which the set of potential hypotheses is precisely specified, and a procedure is derived for restoring the consistency of a set of hypotheses after conflicting evidence is encountered. In addition, this work is extended to where a learning system may be “told” arbitrary sentences concerning a domain. Included in this is an investigation of the relation between acquiring knowledge and reasoning deductively. However, the interaction of these approaches leads to immediate difficulties which likely require informal, pragmatic techniques for their resolution. The overall framework is intended both as a foundation for investigating autonomous approaches to learning and as a basis for the development of such autonomous systems.

Notes: In this paper we present a computational theory of human motor performance and learning. The theory is implemented as a running AI system called MAGGIE. Given a description of a desired movement as input, the system generates simulated motor behavior as output. The theory states mat skills are encoded as motor schemas, which specify the positions and velocities of a limb at selected points in time. Moreover, there exist two natural representations for such knowledge; viewer-centered schemas describe visually perceived behavior, arid joint-centered schemas are used to generate behavior. When the model acts upon these two representational formats, they exhibit quite different behavioral characteristics. MAGGIE performs the desired movement within a feedback control paradigm, monitoring for errors and correcting them when it detects them. Learning involves improving the joint-centered schema over many practice trials; this reduces the need for monitoring. The model accounts for a number of well-documented motor phenomena, including the speed-accuracy trade-off and the gradual improvement in performance with practice. It also makes several testable predictions. We close with a discussion of the theory's strengths and weaknesses, along with directions for future research.

Notes: This paper describes a novel approach to machine learning, based on the principle of learning by reasoning. Current learning systems have significant limitations such as brittleness, i.e., the deterioration of performance on a different domain or problem and lack of power required for handling real-world learning problems. The goal of our research was to develop an approach in which many of these limitations are overcome in a unified, coherent and general framework. Our learning approach is based on principles of reasoning, such as the discovery of the underlying principle and the recognition of the deeper basis of similarity, which is somewhat akin to human learning. In this paper, we argue the importance of these principles and tie the limitations of current systems to the lack of application of these principles. We then present the technique developed and illustrate it on a learning problem not directly solvable by previous approaches.

Notes: In this paper, we introduce and initiate a formalism to represent syntactic and semantic features in logic-based grammars. We also introduce technical devices to express feature-checking and feature-inheritance mechanisms. This leads us to propose some extensions to the basic unification mechanism of PROLOG. Finally, we consider the problem of long-distance dependency relations between constituents in gapping grammars rules from the point of view of morphosyntactic features that may change depending on the position occupied by the moved constituents. What we propose is not a new linguistic theory about features, but rather a formalism and a set of tools that we think will be useful to grammar writers to describe features and their relations in grammar rules.

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: A mechanism for tracing the utilization of rules in expert systems during periods of practical usage is proposed. Statistics related to the utilization of each rule help the designer to re-evaluate the appropriateness of each rule, so that over-utilized rules may be expanded and unnecessary ones deleted. By incorporating such a mechanism, the efficiency of maintaining and updating expert systems is improved.

Notes: Abstract: Expert system shells are discussed as very-high-level programming languages for knowledge engineering. Based on a category/domain distinction for expert systems the concept of expert system shells is explained using seven classifications. A proposal for a shell-development policy is sketched. The conclusions express concern about current over-emphasis on graphical interfaces.

Notes: Abstract: This article describes the development of a knowledge-based system (KBS) for guiding both technical and non-technical managers in estimating the risks inherent in proposed KBS development projects. The work described here is part of an ongoing research project studying the use of KBS both to teach and to do KBS development. So far, as part of this research project, over the past two years close to 150 non-technical and technical full-time business managers have developed some 75 KBS prototypes in conjunction with an MBA course in strategic planning. Based on replies to a survey of this test group, 17% of the KBS developed were reportedly used at work, 14% led to promotions, pay raises, or new jobs, and 14% led to participation in other KBS development projects at work. All but two of the survey respondents reported that their work on the KBS development project led to a substantial increase in their job knowledge or performance. The KBS work described here extends research work described by Cullen and Bryman [1988], Slagle and Wick [1988], Cohen and Howe [1988], Dologite [1988, 1989], and Mockler [1989(A) and (B)].

Notes: Abstract: The sophisticated nature of new production facilities means more complex maintenance units and costly breakdowns. For users of high tech machinery, the efficiency of their maintenance services is becoming an increasingly important factor, and for manufacturers, the maintainability of their equipment they sell is an element that has to be taken into account in their battle for market share. Troubleshooting Expert Systems (TES) are one possible means of improving maintenance capability and maintenance units. Surveying cases of success or failure that the authors have witnessed themselves or come across in the literature, they propose a checklist of seven questions to be considered at the outset of TES development, which deal with the human, managerial and organisational aspects of TES.

Notes: Abstract: Robust design is an efficient method for designing high quality products at low cost. The method examines the effect of a large number of design factors on the variability of a product's response due to various sources of disturbance. This effect can be observed efficiently by studying a large number of variables simultaneously through balanced, orthogonal array experiments, and by analyzing the resulting data using variance decomposition methods. In this paper we describe an expert system prototype for designing efficient experiments. Given the information on various parameters and their levels, the system designs an experiment using orthogonal arrays. This expert system is implemented in Prolog, which is a logic programming language for artificial intelligence research and expert systems development. The system was implemented under the P-Shell knowledge programming environment on UNIX.

Notes: Abstract: This paper deals with the issue of knowledge elicitation for expert systems. Specifically, it looks at the requirements of the knowledge elicitation process and the suitability of structured methods from systems analysis to carry out part of the elicitation task. The techniques of data flow analysis, entity-relationship analysis and entity-life cycle analysis are used to structure the data associated with the expert task. The methods proposed lay emphasis on the definition of limited data sets at the boundary of the explicit knowledge base and the identification of status attributes to model the control of activation of ‘processes’ within the knowledge base. Attention is also paid to the relationship between the resulting logical model, and two popular methods of knowledge representation, namely, Production Systems and Frames.

Notes: Abstract: Despite their potential advantages, robots are not used much by industry andlor services. One of the major reasons for this situation is the limitations of robots, especially their lack of ‘intelligence”. Artificial intelligence and expert systems technologies can help in this case. This paper describes the potential contribution of expert systems to the decision making capabilities of robots and to decisions regarding robots. The major potential contribution of expert systems is in the automation of the error recovery process. Specifically, when something is going wrong in the robot itself or in its work environment, an automated corrective action is needed. Today's technology is capable of economically handling some of the activities in the process (e.g. interpretation of signals from sensors, diagnosis of what is wrong and suggestions for remedies). The AI technology is still not capable in most cases (at least in an economical manner) of actually restoring the robot's operations. The paper also gives examples of several experimental expert systems in the robotic field.

Notes: Knowledge-Based Systems: Markets, Suppliers and Products, Tim Johnson et al.The European Market for Expert Systems, Artificial Intelligence Systems and Expert Systems Used in Medical Laboratory Applications