Hirschberg, D. & Pazzani, M. (1992). Average case analysis of
 k-CNF learning algorithms.  Proceedings of the Tenth
 International Conference on Machine Learning  (pp. 206-211).
  Aberdeen, Scotland: Morgan Kaufmann.
 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 from a known distribution.  We extend the basic model
 to address issues that arise if the data contain attribute noise. We show how the analysis can lead to insight into the
 behavior of the algorithm and the factors that affect the error. We make certain independence assumptions during
 the derivation of the average case model and we demonstrate that the predictions of the model account for a large
 percentage of the variation in error when these assumptions are violated.