Carl M. Kadie
Microsoft Research, Bldg 9S
Redmond 98052-6399, WA
Author Email: carlk@microsoft.com
Many learning systems implicitly use the fitandsplit learning method to create a comprehensive hypothesis from a set of partial hypotheses. At the core of the fitandsplit method is the assignment of examples to partial hypotheses. To date, however, this core has been neglected. This paper provides the first definition and model of the fitandsplit assignment problem. Extant systems perform assignment nearly arbitrarily, implicitly using, for example, greedy set covering. This paper also presents Conceptual Set Covering (CSC), a new assignment algorithm. An extensive empirical evaluation over a wide range of learning problems suggests that CSC can improve any fitandsplit learning system.
Proceedings of the Seventh International Conference on Machine Learning, Austin, Texas, June 1990. (postscript)