Bounds on the Number of Units for Computing Arbitrary Dichotomies by Multilayer Perceptrons

AbstractMultilayer perceptrons can compute arbitrary dichotomies of a set of N points of [0, 1]d. The minimal size of such networks was studied by Baum (1988, J. Complexity4, 193-215) using the parameter N. In this paper, we show that this question can be addressed using another parameter, the minimum distance δ between the two classes. We derive related upper and lower bounds on the size of nets capable of computing arbitrary dichotomies