ALBERT

Notes: Abstract:  The utilization of a fuzzy aspect within data analysis attempts to move from a quantitative to a more qualitative investigative environment. As such, this may allow the more non-quantitative researchers results they can use, based on sets of linguistic terms. In this paper an inductive fuzzy decision tree approach is utilized to construct a fuzzy-rule-based system for the first time in a biological setting. The specific biological problem considered attempts to identify the antecedents (conditions in the fuzzy decision rules) which characterize the length of song flight of the male sedge warbler when attempting to attract a mate. Hence, for a non-quantitative investigator the resultant set of fuzzy rules allows an insight into the linguistic interpretation on the relationship between associated characteristics and the respective song flight duration.

Notes: Abstract: Expert systems can be used to determine some objects or consequences from uncertain knowledge by hierarchical categorization. Categorical representation is psychologically motivated and also offers an explanation of how to deal with uncertain knowledge based on counting during approximate reasoning. It is an alternative to other well-known uncertainty calculi. A knowledge base which is used during approximate reasoning is represented by a taxonomical arrangement of verbal categories. Priming eases the formation of the final hypothesis, as more exact possible hypotheses are formed. The approximate reasoning is demonstrated on an expert system ‘Jurassic’ from the field of paleontology for the determination of a dinosaur species. It helps the paleontologist to determine creatures from uncertain knowledge. The system is composed of 423 rules arranged in a directed acyclic graph with a depth of 5. This knowledge is represented by a taxonomical arrangement of verbal categories represented by associative memories.

Notes: Abstract: Information technology and the Internet have been major drivers for changes in all aspects of business processes and activities. They have brought major changes to the financial statements audit environment as well, which in turn has required modifications in audit procedures. There exist certain difficulties, however, with current audit procedures especially for the assessment of the level of control risk. This assessment is primarily based on the auditors' professional judgment and experiences, not on objective rules or criteria.To overcome these difficulties, we propose a prototype decision support model named CRAS-CBR using case-based reasoning to support auditors in making their professional judgment on the assessment of the level of control risk of the general accounting system in the manufacturing industry.To validate the performance, we compare our proposed model with benchmark performances in terms of classification accuracy for the level of control risk. Our experimental results show that CRAS-CBR outperforms a statistical model and staff auditor performance in average hit ratio.

Notes: Abstract: Machine learning can extract desired knowledge from training examples and ease the development bottleneck in building expert systems. Most learning approaches derive rules from complete and incomplete data sets. If attribute values are known as possibility distributions on the domain of the attributes, the system is called an incomplete fuzzy information system. Learning from incomplete fuzzy data sets is usually more difficult than learning from complete data sets and incomplete data sets. In this paper, we deal with the problem of producing a set of certain and possible rules from incomplete fuzzy data sets based on rough sets. The notions of lower and upper generalized fuzzy rough approximations are introduced. By using the fuzzy rough upper approximation operator, we transform each fuzzy subset of the domain of every attribute in an incomplete fuzzy information system into a fuzzy subset of the universe, from which fuzzy similarity neighbourhoods of objects in the system are derived. The fuzzy lower and upper approximations for any subset of the universe are then calculated and the knowledge hidden in the information system is unravelled and expressed in the form of decision rules.

Notes: Abstract: Probabilistic approaches to rough sets in granulation, approximation and rule induction are reviewed. The Shannon entropy function is used to quantitatively characterize partitions of a universe. Both algebraic and probabilistic rough set approximations are studied. The probabilistic approximations are defined in a decision-theoretic framework. The problem of rule induction, a major application of rough set theory, is studied in probabilistic and information-theoretic terms. Two types of rules are analyzed: the local, low order rules, and the global, high order rules.

Notes: Abstract: The theory of rough sets is an extension of set theory for studying intelligent systems characterized by insufficient and incomplete information. We discuss the basic concept and properties of knowledge reduction based on inclusion degree and evidence reasoning theory, and propose a knowledge discovery approach based on inclusion degree and evidence reasoning theory.

Notes: Abstract: The paper is concerned with the creation of predictive models from data within the framework of the variable precision rough set model. It is focused on two aspects of the model derivation: computation of uncertain, in general, rules from information contained in probabilistic decision tables and forming hierarchies of decision tables with the objective of reduction or elimination of decision boundaries in the resulting classifiers. A new technique of creation of a linearly structured hierarchy of decision tables is introduced and compared to tree-structured hierarchy. It is argued that the linearly structured hierarchy has significant advantages over tree-structured hierarchy.

Notes: In today's competitive business environment, it is important that customers are able to obtain their preferred items in the shops they visit, particularly for convenience store chains such as 7–Eleven where popular items are expected to be readily available on the shelves of the stores for buyers. To minimize the cost of running such store chains, it is essential that stocks be kept to a minimum and at the same time large varieties of popular items are available for customers. In this respect, the replenishment system needs to be able to cope with the taxing demands of minimal inventory but at the same time keeping large varieties of needed items. This paper proposes a replenishment system which is able to respond to the fluctuating demands of customers and provide a timely supply of needed items in a cost–effective way. The proposed system embraces the principle of fuzzy logic which is able to deal with uncertainties by virtue of its fuzzy rules reasoning mechanism, thereby leveraging the responsiveness of the entire replenishment system for the chain stores. To validate the feasibility of the approach, a case study has been conducted in an emulated environment with promising results.

Notes: A formidable synergy can be obtained by putting expert system technology into the Internet. The modern trend of embedding expert systems into Websites turns out to be very promising, in particular for the field of marketing via the Web. The last two years have seen a growing interest in providing Websites with suitable embedded expert systems for one–to–one marketing. One–to– one marketing means marketing in a personalized way, i.e. marketing in a way that is adaptive to the personal needs of the user. A basic feature of this marketing framework consists in personalized prioritizing of news, i.e. presenting information in an order that is relevant to the specific needs of the current user. If the personalized prioritizing of news is a very useful feature in wired Web, it becomes essential in wireless Web, the promising next generation of the Web.The paper presents a general methodology for personalized prioritizing of news. The methodology integrates decision theory with a deep–knowledge–based user model (i.e. causal knowledge linking user preferences to user goals). The deep–knowledge model of the user is a source of power of the methodology because it allows the system to know (and possibly explain) why the user acts the way he/she acts. Another relevant aspect of the methodology is that the burden of personalization is not placed on the user, and in fact the user does not have to declare his/her needs or interests or goals: they are automatically inferred from his/her profile data. In order to investigate the ideas underlying the proposal, a methodology example has been implemented in a prototype and then tested on real cases in the context of a supercomputing portal.

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: This article deals with the problem of providing Kowalski and Sergot's event calculus, extended with context dependency, with an efficient implementation in a logic programming framework. Despite a widespread recognition that a positive solution to efficiency issues is necessary to guarantee the computational feasibility of existing approaches to temporal reasoning, the problem of analyzing the complexity of temporal reasoning programs has been largely overlooked. This article provides a mathematical analysis of the efficiency of query and update processing in the event calculus and defines a cached version of the calculus that (i) moves computational complexity from query to update processing and (ii) features an absolute improvement of performance, because query processing in the event calculus costs much more than update processing in the proposed cached version.

Notes: This article presents a formal theory of concurrent actions that handles the qualification, ramification, and frame problems. The theory is capable of temporal explanation, i.e., reasoning forward and backward. The approach uses the modal logic Z to extend the work of Lifschitz and Rabinov on miracle-based temporal reasoning. The advantages of miracles for describing unknown actions are augmented with the ability to handle concurrent actions that can provide for the most economical explanation of state changes. For temporal explanation problems restricted to finite domains, it has a worst-case exponential decision procedure. The theory is as general as first-order logic in what it can express as preconditions and consequences of actions.

Notes: The game of Nine Men's Morris is a draw. We obtained this result using a combination of endgame databases (1010 states) and search. Our improved algorithm for computing endgame databases allowed the game to be solved on a personal computer. Other games have been solved using knowledge-based methods to dramatically prune the search tree. Nine Men's Morris does not seem to profit from such methods, making it the first nontrivial game solved in which almost the entire state space has to be considered.

Notes: It is believed that chess masters use pattern-based knowledge to analyze a position, followed by a pattern-based controlled search to verify or correct the analysis. This paper describes a first-order system called PAL that can learn patterns in the form of Horn clauses from simple example descriptions and general purpose knowledge. It is shown how PAL can leam chess patterns that are beyond the learning capabilities of current inductive systems. The patterns learned by PAL can be used for analysis of positions and for the construction of playing strategies. By taking the learned patterns as attributes for describing examples, a set of rules which decide whether a Pawn can safely be promoted without moving the King in a King and Pawn vs King endgame, is automatically constructed with a similarity-based learning algorithm. Similarly, a playing strategy for the King and Rook vs King endgame is automatically constructed with a simple learning algorithm by following traces of games and using the patterns learned by PAL. Limitations of first-order systems, PAL imparticularly, are exposed in domains where a large number of background definitions may be required for induction. Conclusions and future research directions are given.

Notes: Games with imperfect information are an interesting and important class of games. They include most card games (e.g., bridge and poker) as well as many economic and political models. Here we investigate algorithms for findi ng the simplest form of a solution (a pure-strategy equilibrium point) to imperfect information games expressed in their extensive (game tree) form. We introduce to the artificial intelligence community a classic algorithm, due to Wilson, that solves one-player games with perfect recall. Wilson's algorithm, which we call iMP-minimax, runs in time linear in the size of the game-tree searched. In contrast to Wilson's result, Koller and Meggido have shown that finding a pure-strategy equilibrium point in one-player games without perfect recall is NP-hard. Here, we provide another contrast to Wilson's result–we show that in games with perfect recall but more than one player, finding a pure-strategy equilibrium point, given that such an equilibrium point exists, is NP-hard.Our second contribution is to present a pruning technique for Wilson's IMP-minimax algorithm to make the latter more tractable. We call this new algorithm IMP-alpha-beta. We provide a theoretical framework (model) and analyze IMP-alpha-beta in that model. IMP-alpha-beta is of direct value for one-player, perfect-recall games. It also has strong potential for other imperfect information games, as it is a natural (but as yet untested) heuristic in those cases.

Notes: Allen's interval algebra has been shown to be useful for representing plans. We present a strengthened algorithm for temporal reasoning about plans, which improves on straightforward applications of the existing reasoning algorithms for the algebra. This is made possible by viewing plans as both temporal networks and hierarchical structures. The temporal network view allows us to check for inconsistencies as well as propagate the effects of new temporal constraints, whereas the hierarchical view helps us to get the strengthened results by taking into account the dependency relationships between actions.We further apply our algorithm to the process of plan recognition through the analysis of natural language input. We show that such an application has two useful effects: the temporal relations derived from the natural language input can be used as constraints to reduce the number of candidate plans, and the derived constraints can be made more specific by combining them with the prestored constraints in the plans being recognized.

Notes: Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions. However, all such methods are sensitive to the feature set chosen to represent the examples. If the features do not capture aspects of the examples significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are carefully handcrafted and a great deal of time and effort goes into refining and tuning them. This paper presents an automatic knowledge-based method for generating features for evaluation functions. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further.This method has been applied to two problem-solving domains: the Othello board game and the domain of telecommunications network management. Empirical results show that the method is able to generate many known features and several novel features and to improve concept accuracy in both domains.

Notes: Although game-tree search works well in perfect-information games, it is less suitable for imperfect-information games such as contract bridge. The lack of knowledge about the opponents’ possible moves gives the game tree a very large branching factor, making it impossible to search a significant portion of this tree in a reasonable amount of time.This paper describes our approach for overcoming this problem. We represent information about bridge in a task network extended to represent multi-agency and uncertainty. Our game-playing procedure uses this task network to generate game trees in which the set of alternative choices is determined not by the set of possible actions, but by the set of available tactical and strategic schemes.We have tested this approach on declarer play in the game of bridge, in an implementation called Tignum 2. On 5000 randomly generated notrump deals, Tignum 2 beat the strongest commercially available program by 1394 to 1302, with 2304 ties. These results are statistically significant at the α= 0.05 level. Tignum 2 searched an average of only 8745.6 moves per deal in an average time of only 27.5 seconds per deal on a Sun SPARCstation 10. Further enhancements to Tignum 2 are currently underway.

Notes: This paper introduces METAGAMER, the first program designed within the paradigm of Metagame-playing (Metagame). This program plays games in the class of symmetric chess-like games, which includes chess, Chinese chess, checkers, draughts, and Shogi. METAGAMER takes as input the rules of a specific game and analyzes those rules to construct an efficient representation and an evaluation function for that game; they are used by a generic search engine. The strategic analysis performed by METAGAMER relates a set of general knowledge sources to the details of the particular game. Among other properties, this analysis determines the relative value of the different pieces in a given game. Although METAGAMER does not learn from experience, the values resulting from its analysis are qualitatively similar to values used by experts on known games and are sufficient to produce competitive performance the first time METAGAMER plays a new game. Besides being the first Metagame-playing program, this is the first program to have derived useful piece values directly from analysis of the rules of different games. This paper describes the knowledge implemented in METAGAMER, illustrates the piece values METAGAMER derives for chess and checkers, and discusses experiments with METAGAMER on both existing and newly generated games.

Notes: The Allen and Koomen planner is intractable in two ways: the Allen interval algebra is an intractable temporal reasoner, and the collapsing problem introduces a large branching factor in the search space for a solution plan. We define independence and dependence for networks to address both problems. Independence is used to find a decomposition of an interval network, and dependence is used to focus search when faced with the collapsing problem.

Notes: We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O(max(n3, n2 m)) time (for n points and m ≠-relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.

Notes: As influence diagrams become a popular representational tool for decision analysis, influence diagram evaluation attracts more and more research interests. In this article, we present a new, two-phase method for influence diagram evaluation. In our method, an influence diagram is first mapped onto a decision graph and then the analysis is carried out by evaluating the decision graph. Our method is more efficient than Howard and Matheson's because, among other reasons, our method generates a much smaller decision graph for the same influence diagram. Like those most recent algorithms reported in the literature, our method also provides a clean interface between influence diagram evaluation and Bayesian net evaluation. Consequently, various well-established algorithms for Bayesian net evaluation can be used in influence diagram evaluation. Furthermore, our method has a few unique merits. First, it takes advantage of asymmetry in influence diagrams to avoid unnecessary computation. Second, by using heuristic search techniques, it provides an explicit mechanism for using heuristic information that may be available in a domain-specific form. These additional merits make our method more efficient than the current algorithms in general. Finally, by using decision graphs as an intermediate representation, the value of perfect information can be computed in a more efficient way.

Notes: Vagueness and uncertainty have attracted the attention of philosophers and logicians for many years. Recently, AI researchers contributed essentially to this area of research. Fuzzy set theory and the theory of evidence are seemingly the most appealing topics. On this note we present a new approach, based on the rough set theory, for looking to these problems. The theory of rough sets seems a suitable mathematical tool for dealing with problems of vagueness and uncertainty. This paper is a modified version of the author's lecture titled “An inquiry into vagueness and uncertainty,” which was delivered at the AI Conference in Wigry (Poland), 1994.

Notes: This paper presents results of experiments showing how machine learning methods arc useful for rule induction in the process of knowledge acquisition for expert systems. Four machine learning methods were used: ID3, ID3 with dropping conditions, and two options of the system LERS (Learning from Examples based on Rough Sets): LEM1 and LEM2. Two knowledge acquisition options of LERS were used as well. All six methods were used for rule induction from six real-life data sets. The main objective was to lest how an expert system, supplied with these rule sets, performs without information on a few attributes. Thus an expert system attempts to classify examples with all missing values of some attributes. As a result of experiments, it is clear that all machine learning methods performed much worse than knowledge acquisition options of LERS. Thus, machine learning methods used for knowledge acquisition should be replaced by other methods of rule induction that will generate complete sets of rules. Knowledge acquisition options of LERS are examples of such appropriate ways of inducing rules for building knowledge bases.

Notes: Knowledge discovery in databases, or dala mining, is an important direction in the development of data and knowledge-based systems. Because of the huge amount of data stored in large numbers of existing databases, and because the amount of data generated in electronic forms is growing rapidly, it is necessary to develop efficient methods to extract knowledge from databases. An attribute-oriented rough set approach has been developed for knowledge discovery in databases. The method integrates machine-learning paradigm, especially learning-from-examples techniques, with rough set techniques. An attribute-oriented concept tree ascension technique is first applied in generalization, which substantially reduces the computational complexity of database learning processes. Then the cause-effect relationship among the attributes in the database is analyzed using rough set techniques, and the unimportant or irrelevant attributes are eliminated. Thus concise and strong rules with little or no redundant information can be learned efficiently. Our study shows that attribute-oriented induction combined with rough set theory provide an efficient and effective mechanism for knowledge discovery in database systems.

Notes: This paper presents an empirical study of the use of the rough set approach to reduction of data for a neural network classifying objects described by quantitative and qualitative attributes. Two kinds of reduction are considered: reduction of the set of attributes and reduction of the domains of attributes. Computational tests were performed with five data sets having different character, for original and two reduced representations of data. The learning time acceleration due to data reduction is up to 4.72 times. The resulting increase of misclassification error does not exceed 11.06%. These promising results let us claim that the rough set approach is a useful tool for preprocessing of data for neural networks.

Notes: In this paper, we introduce the notion of interval structures in an attempt to establish a unified framework for representing uncertain information. Two views are suggested for the interpretation of an interval structure. A typical example using the compatibility view is the rough set model in which the lower and upper approximations form an interval structure. Incidence calculus adopts the allocation view in which an interval structure is defined by the tightest lower and upper incidence bounds. The relationship between interval structures and interval-based numeric belief and plausibility functions is also examined. As an application of the proposed model, an algorithm is developed for computing the tightest incidence bounds.

Notes: “Simpson's paradox,” first described nearly a century ago, is an anomaly that sometimes arises from pooling data. Dramatic instances of the paradox have occurred in real life in the domains of epidemiology and admissions policies. Many writers have recently described hypothetical examples of the paradox arising in other areas of life and it seems possible that the paradox may occur frequently in mundane domains but with less serious implications. Thus, it is not surprising that the paradox should arise in commonsense reasoning, that subarea of artificial intelligence that seeks to axiomatize reasoning in such mundane domains. It arises as the problem “approximate proof by cases” and the question of whether to accept it may well depend on whether we wish to construct performance or competence models of reasoning. This article gives a brief history of the paradox and discusses its occurrence in our own discipline. It argues that if the paradox occurs frequently but undramatically in real life, every uncertain reasoning system will have to deal with the problem in some way.

Notes: We present the syntax and proof theory of a logic of argumentation, LA. We also outline the development of a category theoretic semantics for LA. LA is the core of a proof theoretic model for reasoning under uncertainty. In this logic, propositions are labeled with a representation of the arguments which support their validity. Arguments may then be aggregated to collect more information about the potential validity of the propositions of interest. We make the notion of aggregation primitive to the logic, and then define strength mappings from sets of arguments to one of a number of possible dictionaries. This provides a uniform framework which incorporates a number of numerical and symbolic techniques for assigning subjective confidences to propositions on the basis of their supporting arguments. These aggregation techniques are also described with examples.

Notes: In this paper we focus on the temporal constraints between causes and effects of causal relations, and, to deal correctly with such relations, we stress the importance of analyzing the action-types (aspectual category) of causes and effects. In particular, we propose a domain-independent ontology in which the distinctions between action-types (e.g., the distinction between durative and punctual situations) are dealt with, and different types of causal relations are distinguished, on the basis of (i) the temporal constraints they impose between causes and effects (these constraints are expressed in a temporal formalism that extends Vilain's point interval algebra) and (ii) the action-types of their causes and effects. Our ontology allows one to capture precisely the temporal constraints imposed by causation and the action-types of the related situations. Moreover, in case the user has no accurate knowledge about the action-types of some situations and/or the types of some causal connections to be dealt with, our formalism allows the user to leave the descriptions underspecified, and more specific pieces of information may be inferred. Inferences provide a flow of information about action-types to information about temporal constraints in causation and vice versa, and demonstrate that a deep integration of time and causation is provided also at the inferential level.

Notes: The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst-case analysis of the algorithm also shows linear growth with respect to the number of instances.

Notes: We propose a procedure for estimating DBLEARN's potential for knowledge discovery, given a relational database and concept hierarchies. This procedure is most useful for evaluating alternative concept hierarchies for the same database. The DBLEARN knowledge discovery program uses an attribute-oriented inductive-inference method to discover potentially significant high-level relationships in a database. A concept forest, with at most one concept hierarchy for each attribute, defines the possible generalizations that DBLEARN can make for a database. The potential for discovery in a database is estimated by examining the complexity of the corresponding concept forest. Two heuristic measures are defined based on the number, depth, and height of the interior nodes. Higher values for these measures indicate more complex concept forests and arguably more potential for discovery. Experimental results using a variety of concept forests and four commercial databases show that in practice both measures permit quite reliable decisions to be made; thus, the simplest may be most appropriate.

Notes: The inverted pendulum poses serious problems for qualitative modeling methods, so it is a good benchmark to lest their performance. This paper shows how a new data analysis method known as rough set theory can be utilized to swing up and stabilize the pendulum. Our approach to this task consists of deriving control rules from the actions of a human operator stabilizing the pendulum and subsequently using them for automatic control. Rule derivation is based on the “learning from examples” principle and does not require knowledge of a quantitative model of the system.

Notes: We present some methods, based on the rough set and Boolean reasoning approaches, for extracting laws from decision tables. First we discuss several procedures for decision rules synthesis from decision tables. Next we show how to apply some near-to-functional relations between data to data filtration. Two methods of searching for new classifiers (features) are described: searching for new classifiers in a given set of logical formulas, and searching for some functions approximating near-to-functional relations.

Notes: We apply rough set constructs to inductive learning from a database. A design guideline is suggested, which provides users the option to choose appropriate attributes, for the construction of data classification rules. Error probabilities for the resultant rule are derived. A classification rule can be further generalized using concept hierarchies. The condition for preventing overgeneralization is derived. Moreover, given a constraint, an algorithm for generating a rule with minimal error probability is proposed.

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.