In Lemmer, J. F. and Kanal, L. N. (Eds.), UAI 2, pp. 149–163. Elsevier/North-Holland.

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 proposal, I describe a. method for formulating plans from