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.
