Capacity and error estimates for boolean classifiers with limited complexity

This paper extends the notions of capacity and distribution-free error estimation to nonlinear Boolean classifiers on patterns with binary-valued features. We establish quantitative relationships between the dimensionality of the feature vectors (d), the combinational complexity of the decision rule (c), the number of samples in the training set (n), and the classification performance of the resulting classifier. Our results state that the discriminating capacity of Boolean classifiers is given by the product dc, and the probability of ambiguous generalization is asymptotically given by (n/dc 1)-i 0(1Og d)/d) for large d, and n = O(dc). In addition we show that if a fraction v of the training samples is misclassified then the probability of error (r) in subsequent samples satisfies P(17r - vl > e) : 2.773 exp (dc - e2n/8) for all distributions, regardless of how the classifier was discovered.