ALCOMFT-TR-01-193 |
![]() |
Paul W. Goldberg
Estimating a Boolean Perceptron from its Average Satisfying Assignment: A Bound on the Precision Required
Warwick. Work package 4. December 2001.Abstract: A boolean perceptron is a linear threshold function over the discrete boolean domain {0,1}n. That is, it maps any binary vector to 0 or 1 depending on whether the vector's components satisfy some linear inequality. In 1961, Chow [chow] showed that any boolean perceptron is determined by the average or ``center of gravity'' of its ``true'' vectors (those that are mapped to 1). Moreover, this average distinguishes the function from any other boolean function, not just other boolean perceptrons.Postscript file: ALCOMFT-TR-01-193.ps.gz (91 kb).We address an associated statistical question of whether an empirical estimate of this average is likely to provide a good approximation to the perceptron. In this paper we show that an estimate that is accurate to within additive error (epsilon/n)O(log(1/epsilon)) determines a boolean perceptron that is accurate to within error epsilon (the fraction of misclassified vectors). This provides a mildly super-polynomial bound on the sample complexity of learning boolean perceptrons in the ``restricted focus of attention'' setting. In the process we also find some interesting geometrical properties of the vertices of the unit hypercube.