Learning DNF via Probabilistic Evidence Combination

Abstract

One approach to learning DNF expressions from examples is to use a conjunctive learner to separately form each of the disjuncts. This paper describes a learning algorithm that follows this approach, extending our earlier work on learning conjunctive classifiers from noisy data to learning DNF classifiers from noisy data. Because every disjunct does not cover every positive example, such learners must decide which positive examples to cover with each disjunct being learned. The central idea here is to model as representational noise the uncertainty as to whether a positive example should be treated as positive for a particular disjunct, in addition to whatever other noise may be imposed on the data by the environment. In experiments with synthetic data our learning method exhibits statistically significantly lower error rates during early learning when compared to the C4.5 algorithm, and on seven out of eight real-world datasets the error rates of classifiers learned by the new algorithm meet or exceed those of the classifiers learned by C4.5.