Automatic pattern recognition: a study of the probability of error
- 1 July 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 10 (4) , 530-543
- https://doi.org/10.1109/34.3915
Abstract
A test sequence is used to select the best rule from a class of discrimination rules defined in terms of the training sequence. The Vapnik-Chervonenkis and related inequalities are used to obtain distribution-free bounds on the difference between the probability of error of the selected rule and the probability of error of the best rule in the given class. The bounds are used to prove the consistency and asymptotic optimality for several popular classes, including linear discriminators, nearest-neighbor rules, kernel-based rules, histogram rules, binary tree classifiers, and Fourier series classifiers. In particular, the method can be used to choose the smoothing parameter in kernel-based rules, to choose k in the k-nearest neighbor rule, and to choose between parametric and nonparametric rules.Keywords
This publication has 96 references indexed in Scilit:
- Bounds for the uniform deviation of empirical measuresJournal of Multivariate Analysis, 1982
- Distribution-Free Consistency Results in Nonparametric Discrimination and Regression Function EstimationThe Annals of Statistics, 1980
- On the L 1 convergence of kernel estimators of regression functions with applications in discriminationProbability Theory and Related Fields, 1980
- Distribution-free performance bounds for potential function rulesIEEE Transactions on Information Theory, 1979
- Distribution-free inequalities for the deleted and holdout error estimatesIEEE Transactions on Information Theory, 1979
- Distribution-free performance bounds with the resubstitution error estimate (Corresp.)IEEE Transactions on Information Theory, 1979
- Bootstrap Methods: Another Look at the JackknifeThe Annals of Statistics, 1979
- Central Limit Theorems for Empirical MeasuresThe Annals of Probability, 1978
- LEARNING IN PATTERN RECOGNITIONPublished by Elsevier ,1969
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967