Petsche T. et al., Computational Learning Theory and Natural Learning Systems, Vol. 3

Reducing the Small Disjuncts Problem by Learning Probabilistic Concept Descriptions

	Kamal M Ali	Michael J Pazzani
	
This paper presents a method for learning concept descriptions, where each concept description consists of a set of classification rules. Classifiers such as FOIL (Quinlan, 1990) learn a few accurate rules (disjuncts) but many inaccurate rules that are a major source of error on independent test examples. This problem, first identified by Holte et al. (1989), has been been referred to as the small disjuncts problem. We introduce the system HYDRA which learns concept descriptions consisting of rules with relational and attribute-value conditions. We provide empirical evidence that attachment of estimates of classification reliability reduces the contribution of error from small disjuncts. We demonstrate this effect on a number of relational and attribute-value domains from the UCI Machine Learning Repository of databases.