PAC learning using nadaraya-watson estimator based on orthonormal systems

Hongzhu Qiao; Nageswara S.V. Rao; V. Protopopescu

doi:10.1007/3-540-63577-7_41

PAC learning using nadaraya-watson estimator based on orthonormal systems

Hongzhu Qiao, Nageswara S.V. Rao, V. Protopopescu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Na~laraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.

Original language	English
Title of host publication	Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings
Editors	Ming Li, Akira Maruoka
Publisher	Springer Verlag
Pages	146-160
Number of pages	15
ISBN (Print)	3540635777, 9783540635772
DOIs	https://doi.org/10.1007/3-540-63577-7_41
State	Published - 1997
Event	8th International Workshop on Algorithmic Learning Theory, ALT 1997 - Sendai, Japan Duration: Oct 6 1997 → Oct 8 1997

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1316
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Workshop on Algorithmic Learning Theory, ALT 1997
Country/Territory	Japan
City	Sendai
Period	10/6/97 → 10/8/97

Access to Document

10.1007/3-540-63577-7_41

Cite this

Qiao, H., Rao, N. S. V., & Protopopescu, V. (1997). PAC learning using nadaraya-watson estimator based on orthonormal systems. In M. Li, & A. Maruoka (Eds.), Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings (pp. 146-160). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1316). Springer Verlag. https://doi.org/10.1007/3-540-63577-7_41

Qiao, Hongzhu ; Rao, Nageswara S.V. ; Protopopescu, V. / PAC learning using nadaraya-watson estimator based on orthonormal systems. Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings. editor / Ming Li ; Akira Maruoka. Springer Verlag, 1997. pp. 146-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{941094b41be94a0bb92f36c05bdbdbb7,

title = "PAC learning using nadaraya-watson estimator based on orthonormal systems",

abstract = "Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Na\textasciitilde{}laraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.",

author = "Hongzhu Qiao and Rao, \{Nageswara S.V.\} and V. Protopopescu",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 8th International Workshop on Algorithmic Learning Theory, ALT 1997 ; Conference date: 06-10-1997 Through 08-10-1997",

year = "1997",

doi = "10.1007/3-540-63577-7\_41",

language = "English",

isbn = "3540635777",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "146--160",

editor = "Ming Li and Akira Maruoka",

booktitle = "Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings",

}

Qiao, H, Rao, NSV & Protopopescu, V 1997, PAC learning using nadaraya-watson estimator based on orthonormal systems. in M Li & A Maruoka (eds), Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1316, Springer Verlag, pp. 146-160, 8th International Workshop on Algorithmic Learning Theory, ALT 1997, Sendai, Japan, 10/6/97. https://doi.org/10.1007/3-540-63577-7_41

PAC learning using nadaraya-watson estimator based on orthonormal systems. / Qiao, Hongzhu; Rao, Nageswara S.V.; Protopopescu, V.
Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings. ed. / Ming Li; Akira Maruoka. Springer Verlag, 1997. p. 146-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1316).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - PAC learning using nadaraya-watson estimator based on orthonormal systems

AU - Qiao, Hongzhu

AU - Rao, Nageswara S.V.

AU - Protopopescu, V.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1997.

PY - 1997

Y1 - 1997

N2 - Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Na~laraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.

AB - Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Na~laraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.

UR - https://www.scopus.com/pages/publications/84958040677

U2 - 10.1007/3-540-63577-7_41

DO - 10.1007/3-540-63577-7_41

M3 - Conference contribution

AN - SCOPUS:84958040677

SN - 3540635777

SN - 9783540635772

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 160

BT - Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings

A2 - Li, Ming

A2 - Maruoka, Akira

PB - Springer Verlag

T2 - 8th International Workshop on Algorithmic Learning Theory, ALT 1997

Y2 - 6 October 1997 through 8 October 1997

ER -

Qiao H, Rao NSV , Protopopescu V. PAC learning using nadaraya-watson estimator based on orthonormal systems. In Li M, Maruoka A, editors, Algorithmic Learning Theory - 8th International Workshop, ALT 1997, Proceedings. Springer Verlag. 1997. p. 146-160. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-63577-7_41

PAC learning using nadaraya-watson estimator based on orthonormal systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this