Donald Bren School of Information and Computer Sciences

We present an approach to modeling the average case behavior of an algorithm for learning Conjunctive Normal Form (CNF, i.e., conjunctions of disjunctions). Our motivation is to predict the expected error of the learning algorithm as a function of the number of training examples. We evaluate the average case model by comparing the error predicted by the model to the actual error obtained by running the leaming algorithm, and show how the analysis can lead to insight into the behavior of the algorithm and the factors that affect the error.