On PAC learning of functions with smoothness properties using feedforward sigmoidal networks

Nageswara S.V. Rao; Vladimir A. Protopopescu

doi:10.1109/5.537119

On PAC learning of functions with smoothness properties using feedforward sigmoidal networks

Nageswara S.V. Rao, Vladimir A. Protopopescu

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

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₁, f (X₁)), (X₂, f (X₂)), ⋯ (X_n, f (X_n)). where X₁, X₂,⋯, X_n are independently and identically distributed (HD) according to an unknown distribution 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 general. Suitable neural network probability and approximately correct (PAC) approximations to f*_w can be, in principle, computed based on finite sample, but their computation is hard. Instead, we propose to compute PAC approximations to f*_w based on alternative estimators, namely: 1) 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*_w. The practical importance of this result stems from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.

Original language	English
Pages (from-to)	1562-1568
Number of pages	7
Journal	Proceedings of the IEEE
Volume	84
Issue number	10
DOIs	https://doi.org/10.1109/5.537119
State	Published - 1996

Funding

Manuscript received October 1. 1995, revised February 1, 1996 This work was supported by the Engineering Research Program of the Office of Basic Energy Sciences, of the U S Department of Energy, under Contract DE-AC05-960R22464 with Lockheed Martin Energy Research Corp The authors are with the Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TN 37831-6364 USA. Publisher Item Identifier S 0018-9219(96)07174-5 ’A preliminary version of these results has been presented at the International Conference on ArtlficcaE Intelligence and Mathematics, Ft. Lauderdale, FL, January 3-5, 1996

Funders	Funder number
U.S. Department of Energy	DE-AC05-960R22464
Basic Energy Sciences

Access to Document

10.1109/5.537119

Cite this

@article{364c370d32c04333a509e28c7625996a,

title = "On PAC learning of functions with smoothness properties using feedforward sigmoidal networks",

abstract = "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 (X1, f (X1)), (X2, f (X2)), ⋯ (Xn, f (Xn)). where X1, X2,⋯, Xn are independently and identically distributed (HD) according to an unknown distribution Px. 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 Px are unknown, computing f*w is impossible in general. Suitable neural network probability and approximately correct (PAC) approximations to f*w can be, in principle, computed based on finite sample, but their computation is hard. Instead, we propose to compute PAC approximations to f*w based on alternative estimators, namely: 1) 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*w. The practical importance of this result stems from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.",

author = "Rao, {Nageswara S.V.} and Protopopescu, {Vladimir A.}",

year = "1996",

doi = "10.1109/5.537119",

language = "English",

volume = "84",

pages = "1562--1568",

journal = "Proceedings of the IEEE",

issn = "0018-9219",

publisher = "Institute of Electrical and Electronics Engineers",

number = "10",

}

TY - JOUR

T1 - On PAC learning of functions with smoothness properties using feedforward sigmoidal networks

AU - Rao, Nageswara S.V.

AU - Protopopescu, Vladimir A.

PY - 1996

Y1 - 1996

N2 - 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 (X1, f (X1)), (X2, f (X2)), ⋯ (Xn, f (Xn)). where X1, X2,⋯, Xn are independently and identically distributed (HD) according to an unknown distribution Px. 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 Px are unknown, computing f*w is impossible in general. Suitable neural network probability and approximately correct (PAC) approximations to f*w can be, in principle, computed based on finite sample, but their computation is hard. Instead, we propose to compute PAC approximations to f*w based on alternative estimators, namely: 1) 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*w. The practical importance of this result stems from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.

AB - 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 (X1, f (X1)), (X2, f (X2)), ⋯ (Xn, f (Xn)). where X1, X2,⋯, Xn are independently and identically distributed (HD) according to an unknown distribution Px. 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 Px are unknown, computing f*w is impossible in general. Suitable neural network probability and approximately correct (PAC) approximations to f*w can be, in principle, computed based on finite sample, but their computation is hard. Instead, we propose to compute PAC approximations to f*w based on alternative estimators, namely: 1) 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*w. The practical importance of this result stems from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.

UR - http://www.scopus.com/inward/record.url?scp=0030270407&partnerID=8YFLogxK

U2 - 10.1109/5.537119

DO - 10.1109/5.537119

M3 - Article

AN - SCOPUS:0030270407

SN - 0018-9219

VL - 84

SP - 1562

EP - 1568

JO - Proceedings of the IEEE

JF - Proceedings of the IEEE

IS - 10

ER -

On PAC learning of functions with smoothness properties using feedforward sigmoidal networks

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this