AAAI Conference 1991 Conference Paper
It is well-known that inductive learning algorithms are sensitive to the way in which examples of a concept are represented. Constructive induction reduces this sensitivity by enabling the inductive algorithm to create new terms with which to describe examples. However, new terms are usually created as functions of existing terms, so an extremely poor initial representation makes the search for new terms intractable. This work considers inductive learning within a problem-solving environment. It shows that information about the problem-solving task can be used to create terms that are suitable for learning search control knowledge. The resulting terms describe the problem-solver’ s progress in achieving its goals. Experimental evidence from two domains is presented in support of the approach. ‘ by hand’ can take a long time, because it is essentially a manual search of the space of possible vocabularies. One solution, known as constructive induction, is to enable the learning program to construct new terms for its vocabulary. Most constructive induction algorithms define new terms as Boolean or arithmetic functions of previously known terms. There are infinitely many such functions, so attention must be restricted to a small subset. Most systems search the space of possible vocabularies heuristically, using either the structure of the evolving concept (e. g. CITRE [Matheus & Rendell, 19891) or the behavior of the learning algorithm (e. g. STAGGER [Schlimmer & Granger, 19861) to guide search. In both cases, an extremely poor initial vocabulary makes the search intractable.