Discrete perceptrons
share
Perceptrons have been known for a long time as a promising tool within the neural networks theory. The analytical treatment for a special class of perceptrons started in seminal work of Gardner Gar88. Techniques initially employed to characterize perceptrons relied on a statistical mechanics approach. Many of such predictions obtained in Gar88 (and in a follow-up GarDer88) were later on established rigorously as mathematical facts (see, e.g. SchTir02,SchTir03,TalBook,StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13). These typically related to spherical perceptrons. A lot of work has been done related to various other types of perceptrons. Among the most challenging ones are what we will refer to as the discrete perceptrons. An introductory statistical mechanics treatment of such perceptrons was given in GutSte90. Relying on results of Gar88, GutSte90 characterized many of the features of several types of discrete perceptrons. We in this paper, consider a similar subclass of discrete perceptrons and provide a mathematically rigorous set of results related to their performance. As it will turn out, many of the statistical mechanics predictions obtained for discrete predictions will in fact appear as mathematically provable bounds. This will in a way emulate a similar type of behavior we observed in StojnicGardGen13,StojnicGardSphNeg13,StojnicGardSphErr13 when studying spherical perceptrons.
READ FULL TEXT