Learning unlearnable problems with perceptrons

Abstract

We study how well perceptrons learn to solve problems for which there is no perfect answer (the usual case), taking as examples a rule with a threshold, a rule in which the answer is not a monotonic function of the overlap between question and teacher, and a rule with many teachers (a ``hard'' unlearnable problem). In general there is a tendency for first-order transitions, even using spherical perceptrons, as networks compromise between conflicting requirements. Some existing learning schemes fail completely--occasionally even finding the worst possible solution; others are more successful. High-temperature learning seems more satisfactory than zero-temperature algorithms and avoids ``overlearning'' and ``overfitting,'' but care must be taken to avoid ``trapping'' in spurious free-energy minima. For some rules examples alone are not enough to learn from, and some prior information is required.