Efficient learning beyond saturation by single-layered neural networks

We present two distinct learning rules that can be applied to the problem of constructing a dichotomy of an arbitrary pattern set. Both rules are given in a closed form and are discussed, within the context of a single layered network of N nodes storing P patterns. For P less than or equal to N both rules realize dichotomies of a pattern set and can quarantee perfect storage up to a maximal capacity of P=N. Beyond this maximal capacity the rules can be used to give efficient solutions with a small number of errors. Their efficiency for learning beyond saturation and the simple closed form of these solutions make them ideal for use in constructive algorithms. Generalization performance and the issue of pattern stability in the regime of perfect storage are also examined and theoretical predictions are compared with simulations