Average Case Analysis of k-CNF and k-DNF learning algorithms

Daniel S. Hirschberg, Michael J. Pazzani, Kamal M. Ali 
Department of Information and Computer Science 
University of California, Irvine 
Irvine, CA 92717, USA 
dan@ics.uci.edu pazzani@ics.uci.edu ali@ics.uci.edu
(714) 856-5888 

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.