Donald Bren School of Information and Computer Sciences

This paper presents a method for learning relational and attribute-value concepts based on maximum-likelihood estimation. Greedy hill-climbing classifiers like FOIL and FOCL build a few reliable clauses but many unreliable clauses, referred to as small disjuncts. Small disjuncts are a major source of error on independent test examples. We introduce the system HYDRA which learns probabilistic relational concepts and reduces contribution of error from small disjuncts. We demonstrate the reduction of the small disjuncts problem on various relational and attribute-value domains.