On PAC learning of functions with smoothness properties using feedforward sigmoidal networks
Nageswara S. V. Rao, Vladimir A. Protopopescu · Proceedings of the IEEE · 1996
We consider the problem of learning functions based on finite samples by using feedforward sigmoidal networks. The unknown function f is chosen from a family that has either bounded modulus of smoothness and/or bounded capacity. The sample is given by (X/sub 1/, f(X/sub 1/)), (X/sub 2/, f(X/sub 2/)), ...(X/sub n/, f(X/sub n/)). Where X/sub 1/, X/sub 2/, ..., X/sub n/, are independently and identically distributed according to an unknown distribution P/sub X/. General results guarantee the existence of a neural network, f/sub w/*, that best approximates f in terms of expected error. However, since both f and P/sub X/ are unknown, computing f/sub w/* is impossible in general. We propose to compute probability and approximately correct (PAC) approximations to f/sub w/*, based on alternative estimators, namely: 1) the nearest neighbor rule, 2) local averaging, and 3) Nadaraya-Watson estimators, all computed using the Haar system. We show that given a sufficiently large sample, each of these estimators guarantees a performance as close as desired to that of f/sub w/*. The practical importance of this result sterns from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.