Average Case Analysis of k-CNF and k-DNF Learning Algorithms
Daniel S. Hirschberg, Michael J. Pazzani, Kamal Ali · The MIT Press eBooks · 1994
We present average case models of algorithms for learning Conjunctive Normal Form (CNF, i.e., conjunctions of disjunctions) and Disjunctive Normal Form (DNF, i.e., disjunctions of conjunctions). Our goal is to predict the expected error of the learning algorithm as a function of the number n of training examples, averaging over all sequences of n training examples. We show that our average case models accurately predict the expected error and demonstrate that the analysis can lead to insight into the behavior of the algorithm and the factors that affect the error. 1 Introduction A goal of research in machine learning is to gain an understanding of the capabilities of learning algorithms. Pazzani & Sarrett (1990) introduced a framework for average case Petsche T. et al. Computational Learning Theory and Natural Learning Systems, Vol. 2. 2 analysis of machine learning algorithms. Here, we show how this framework can be applied to create average case models of an algorithm for learning...