Learning unlearnable problems with perceptrons

Publisher Website
Google Scholar
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.