Off-line learning from clustered input examples

We analyze the generalization ability of a simple perceptron acting on a structured input distribution for the simple case of two clusters of input data and a linearly separable rule. The generalization ability computed for three learning scenarios: maximal stability, Gibbs, and optimal learning, is found to improve with the separation between the clusters, and is bounded from below by the result for the unstructured case, recovered as the separation between clusters vanishes. The asymptotic behavior for large training sets is the same for structured and unstructured input distributions. For small training sets, the generalization error of the maximally stable perceptron exhibits a nonmonotonic dependence on the number of examples for certain values of the model parameters.