Nsv. Rao et Va. Protopopescu, ON PAC LEARNING OF FUNCTIONS WITH SMOOTHNESS PROPERTIES USING FEEDFORWARD SIGMOIDAL NETWORKS, Proceedings of the IEEE, 84(10), 1996, pp. 1562-1569
We consider the problem of learning functions based on finite samples
by using feedforward sigmoidal networks. The unknown function f is cho
sen from a family that has either bounded modulus of smoothness and/or
bounded capacity. The sample is given by (X(1), f(X(1))), (X(2), f(X(
2))), ..., (X(n), f(X(n))), where X(1), X(2), ..., X(n) are independen
tly and identically distributed (IID) according to an unknown distribu
tion P-X. General results guarantee the existence of a neural network,
f(w), that best approximates f in terms of expected error. However,
since both f and P-X are unknown, computing f(w) is impossible in gen
eral. Suitable neural network probability and approximately correct (P
AC) approximations to f(w) can be, in principle, computed based on fi
nite sample, but their computation is hard. Instead, we propose to com
pute PAC approximations to f(w) based on alternative estimators, name
ly: 1) nearest neighbor rule, 2) local averaging, and 3) Nadaraya-Wats
on estimators, all computed using the Haar system. We show that given
a sufficiently large sample, each of these estimators guarantees a per
formance as close as desired to that of f(w). The practical importanc
e of this result stems from the fact that, unlike neural networks, the
three estimators above are linear-time computable in terms of the sam
ple size.