Learning Search Control Knowledge

The ability to learn from experience is a fundamental requirement for intelligence. One of the most basic characteristics of human intelligence is that people can learn from problem solving, so that they become more adept at solving problems in a given domain as they gain experience. This book investigates how computers may be programmed so that they too can learn from experience. Specifically, the aim is to take a very general, but inefficient, problem solving system and train it on a set of problems from a given domain, so that it can transform itself into a specialized, efficient problem solver for that domain. on a knowledge-intensive Recently there has been considerable progress made learning approach, explanation-based learning (EBL), that brings us closer to this possibility. As demonstrated in this book, EBL can be used to analyze a problem solving episode in order to acquire control knowledge. Control knowledge guides the problem solver's search by indicating the best alternatives to pursue at each choice point. An EBL system can produce domain specific control knowledge by explaining why the choices made during a problem solving episode were, or were not, appropriate.

This thesis presents an approach to learning good search guiding heuristics for the supposition-based theorom prover E in equational deductions. Search decisions from successful proof searches are represented as sets annotated clause patterns. Term Space Mapping, an alternative learning method for recursive structures is used to learn heuristic evaluation functions for the evaluation of potential new consequences. Experimental results with extended system E/TSM show the success of the approach. Additional contributions of the thesis are an extended superposition calculus and a description of both the proof procedure and the implementation of a state-of-the-art equational theorem prover.

learning correct rules. The overhead involved in learning is very low because this methodology needs only a small amount of data to learn from, namely, the goal stacks from the leaf nodes of a failure search tree, rather than the whole search tree. Empirical tests show that the rules derived by our system PAL, after sufficient learning, performs as well as, and in some cases better than, those derived by other systems such as PRODIGY/EBL and STATIC.

One of the most intriguing questions about the new computer technology that has appeared over the past few decades is whether we humans will ever be able to make computers learn. As is painfully obvious to even the most casual computer user, most current computers do not. Yet if we could devise learning techniques that enable computers to routinely improve their performance through experience, the impact would be enormous. The result would be an explosion of new computer applications that would suddenly become economically feasible (e. g. , personalized computer assistants that automatically tune themselves to the needs of individual users), and a dramatic improvement in the quality of current computer applications (e. g. , imagine an airline scheduling program that improves its scheduling method based on analyzing past delays). And while the potential economic impact ofsuccessful learning methods is sufficient reason to invest in research into machine learning, there is a second significant reason: studying machine learning helps us understand our own human learning abilities and disabilities, leading to the possibility of improved methods in education. While many open questions remain aboutthe methods by which machines and humans might learn, significant progress has been made.

"This book is a comprehensive and in-depth reference to the most recent developments in the field covering theoretical developments, techniques, technologies, among others"--Provided by publisher.

Machine Learning Proceedings 1989

Machine Learning