A Study of Empirical Learning for an Involved Problem

Abstract

In real-world domains a concept to be learned may be unwieldy and the environment may be less than ideal. One combination of difficulties occurs if the concept is probabilistic and the learning situation is dynamic. In this case, the data may be noisy and biaaed. These difficulties arise when learning evaluation functions, which can be considered as concepts. A representative problem, the fifteen puzzle, is used to test six different learning systems: some that fit, count, or partition data in inatanee space; some that optimize measures derived from data in hypothesi& space; and some that perform eombinationa of such procedures. These six systems are described, tested, and analyzed. From quantitative differences in several experiments, we extract specific properties. By combining two or three kinds of techniques, we gauge the extent to which they complement each other. Combinations of strengths can overcome difficulties in domains that are simultaneously probabilistic, dynamic, noisy, and biased.