Induction as Knowledge Integration.
Abstract
Accuracy and efficiency are the two main evaluation criteria for induction algorithms. One of the most powerful ways to improve performance along these dimensions is by integrating additional knowledge into the induction process. However, integrating knowledge that differs significantly from the knowledge already used by the algorithm usually requires rewriting the algorithm. This dissertation presents Kil, a Knowledge Integration framework for Induction, that provides a straightforward method for integrating knowledge into induction, and provides new insights into the effects of knowledge on the accuracy and complexity of induction. The idea behind Kil is to express all knowledge uniformly as constraints and preferences on hypotheses. Knowledge is integrated by conjoining constraints and disjoining preferences. A hypothesis is induced from the integrated knowledge by finding a hypothesis consistent with all of the constraints and maximally preferred by the preferences. Theoretically, just about any knowledge can be expressed in this manner. In practice, the constraint and preference languages determine both the knowledge that can be expressed and the complexity of identifying a consistent hypothesis. RS-KII, an instantiation of Kll based on a very expressive set representation, is described. RS-Kll can utilize the knowledge of at least two disparate induction algorithms-AQ-ll and CEA ('version spaces') in addition to knowledge neither algorithm can utilize. It seems likely that RS-NII can utilize knowledge from other induction algorithms, as well as novel kinds of knowledge, but this is left for future work. RS-Kll's complexity is comparable to these algorithms when using only the knowledge of a given algorithm, and in some cases RS-Kll's complexity is dramatically superior.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1995
- Accession Number
- ADA309542
Entities
People
- Benjamin D. Smith
Organizations
- University of Southern California