Citing the confusing statements in the AI literature concerning the relationship between branch and bound (B&B) and heuristic search procedures were present a simple and general formulation of B&B which should help dispel much of the confusion. We illustrate the utility of the formulation by showing that through it some apparently very different algorithms for searching And/Or trees reveal the specific nature of their similarities and differences. In addition to giving new insights into the relationships among some AI search algorithms, the general formulation also provides suggestions on how existing search procedures may be varied to obtain new algorithms.

A new procedure is presented for growing min-max game trees. In large games, such as chess, decisions must be based on incomplete search trees. The new tree-growth procedure is based on “conspiracy numbers” as a measure of the accuracy of the root minimax value of an incomplete tree. Conspiracy numbers measure the number of leaf nodes whose value must change in order to change the minimax root value by a given amount. Trees are grown in a way that maximizes the conspiracy required to change the root value.

We argue that explanation-based generalisation as recently proposed in the machine learning literature is essentially equivalent to partial evaluation, a well-known technique in the functional and logic programming literature. We show this equivalence by analysing the definitions and underlying algorithms of both techniques, and by giving a PROLOG program which can be interpreted as doing either explanation-based generalisation or partial evaluation.

Despite their different perspectives, artificial intelligence (AI) and the disciplines of decision science have common roots and strive for similar goals. This paper surveys the potential for addressing problems in representation, inference, knowledge engineering, and explanation within the decision-theoretic framework. Recent analyses of the restrictions of several traditional AI reasoning techniques, coupled with the development of more tractable and expressive decision-theoretic representation and inference strategies, have stimulated renewed interest in decision theory and decision analysis. We describe early experience with simple probabilistic schemes for automated reasoning, review the dominant expert-system paradigm, and survey some recent research at the crossroads of AI and decision science. In particular, we present the belief network and influence diagram representations.

This article describes TEAM, a transportable natural-language interface system. TEAM was constructed to test the feasibility of building a natural-language system that could be adapted to interface with new databases by users who are not experts in natural-language processing. An overview of the system design is presented, emphasizing those choices that were imposed by the demands of transportability. Several general problems of natural-language processing that were faced in constructing the system are discussed, including quantifier scoping, various pragmatic issues, and verb acquisition. TEAM is compared with several other transportable systems; this comparison includes a discussion of the range of natural language handled by each as well as a description of the approach taken to achieving transportability in each system.

In order to solve problems effectively, a problem solver must be able to exploit domain-specific search control knowledge. Although previous research has demonstrated that explanation-based learning is a viable approach for acquiring such knowledge, in practice the control knowledge learned via EBL may not be useful. To be useful, the cumulative benefits of applying the knowledge must outweigh the cumulative costs of testing whether the knowledge is applicable. Unlike most previous systems that use EBL, the PRODIGY system evaluates the costs and benefits of the control knowledge it learns. Furthermore, the system produces useful control knowledge by actively searching for “good” explanations—explanations that can be profitably employed to control problem solving.

We show that the notion of inductive bias in concept learning can be quantified in a way that directly relates to learning performance in the framework recently introduced by Valiant. Our measure of bias is based on the growth function introduced by Vapnik and Chervonenkis, and on the Vapnik-Chervonenkis dimension. Using these bias measurements we analyze the performance of the classical learning algorithm for conjunctive concepts from the perspective of Valiant's learning framework. We then augment this algorithm with a hypothesis simplification routine that uses a greedy heuristic and show how this improves learning performance on simpler target concepts. Improved learning algorithms are also developed for conjunctive concepts with internal disjunction, k-DNF and k-CNF concepts.

Get Citation Alerts New Citation Alert added!

Did you know your Organization can subscribe to the ACM Digital Library?

In this paper, I consider a range of English expressions and show that their context-dependency can be characterized in terms of two properties:1. They specify entities in an evolving model of the discourse that the listener is constructing;2. The particular entity specified depends on another entity in that part of the evolving "discourse model" that the listener is currently attending to.Such expressions have been called anaphors. I show how tensed clauses share these characteristics, usually just attributed to anaphoric noun phrases. This not only allows us to capture in a simple way the oft-stated but difficult-to-prove intuition that tense is anaphoric, but also contributes to our knowledge of what is needed for understanding narrative text.