Learning Binary Perceptrons Perfectly Efficiently

摘要

The majority rule algorithm for learning binary weights for a perceptron is analysed under the uniform distribution on inputs. It is shown that even though the algorithm is demonstrably inconsistent on random samples for very small sample sizes, it nevertheless exhibits a curious and abrupt asymptotic transition to consistency at moderate sample sizes. Particular consequences are that the algorithm PAC-learns majority functions in linear time from small samples and that, while the general variant of binary integer programming embodied here is NP-complete, almost all instances of the problem are tractable given a sufficient number of inequalities to be satisfies