Using meta-level inference to constrain search and to learn strategies in equation solving

Abstract

This thesis addresses two questions:- How can search be controlled in domains with a large search space?- How can this control information be learned?It is argued that both problems can be tackled with the aid of a technique called meta-level inference.In this technique, the control information is separated from the factual information. The control information is expressed declaratively, i.e. the control information is represented as explicit rules. These rules are axioms in the meta-theory of the domain. This gives rise to a two level program, the factual information forms the object-level and the control information forms the meta-level. Inference is performed at the meta-level. and this induces inference at the object-level. Search at the object-level is replaced by search at the meta-level. This has several advantages, one of the most important being that the meta-level search space is usually much smaller than the object-level space, so the search problem is greatly reduced.Two programs are presented in this thesis to support this claim. Both programs operate in the domain of symbolic equation solving. However, the techniques used can be applied to a wide variety of domains.The first program. PRESS, solves symbolic, transcendental, non-differential equations. PRESS makes extensive use of meta-level inference to control search. This overcomes problems experienced by other approaches. For example, systems that apply rewrite rules exhaustively usually only use the rules one way round, to avoid looping. However, this often makes the system incomplete, and the techniques for completing this set are not easily mechanized. PRESS is able to use rules in both directions, using inference to decide which direction is appropriate.The second program, LP is also an equation solving program, but, unlike PRESS, it is capable of learning new equation-solving techniques. It embodies a new learning method, called Precondition Analysis. Precondition Analysis combines meta-level inference with concepts from the field of planning, and allows the program to learn even from a single example. This learning technique seems particularly suitable in domains where the operators don't have precisely defined effects and preconditions. Equation solving is such a domain.