A concept is either a categorical or an uncertain classification rule-a binary or probabilistic class membership function over an ‘instance space’ defined by a set of attributes or features. Given the range of attribute values and the range of function values, the correct concept can be expressed as one of many candidates or hypotheses. Over ‘hypothesis space’ another function can be defined that measures the objective-the accuracy, credibility, or performance of the candidate concept. Hence, concept learning can be viewed as optimization. Jaxtaposing these two problems and studying the methods used in each may benefit both areas of research. In real-world domains a concept 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 biased. These difficulties arise when learning evaluation functions, which can be considered as concepts. A representative (but unimodal) problem, the fifteen puzzle, is used to test six different learning systems: some that fit, count, or partition data in instance space, some that optimize measures derived from data in hypothesis space, and some that perform combinations of such procedures. These six systems are described, tested, and analyzed. Through several experiments, we extract specific properties. By combining two or three kinds of techniques, the extent to which they complement each other is gauged. Combinations of strengths can overcome difficulties in domains that are simultaneously probabilistic, dynamic, noisy, and biased.
