Substantial Constructive Induction Using Layered Information Compression: Tractable Feature Formation in Search

Abstract

This paper addresses a problem of induction (generalization le a rning) which is more difficult than any comparable work in AI. The subject of the present research is a hard problem of new terms, a task of realistic constructive induction . While the approach is quite general, the system is analyzed and tested in an environment of heuristic search where noise management and incremental learning are necessary. Here constructive induction becomes feature formation from data repr esente d in elementary form . A high-level attribute or feature suc h as "piece advantage" in checkers is much more abstract than an elementary descriptor or primitive such as contents of a checkerboard square. Features have often been used in evaluation functions; primitives are usually too detailed for this. To create abst ract features from primitives (i.e. to restructure d ata descriptions), a new form of clustering is used which involves layering of know ledge and in variance of utility relationships r e lated to data primitives and task goals. The scheme, which is both model- and data-driven, requires little background, domain-specific knowledge, but rather constructs it. The method achieves considerable generality with superior noise management and low computational complexity. Although the domains addressed are difficult, initial experimental results are encouraging.