Automatic Pattern Recognition A Study Of The Probability Of Error英文电子书.pdf

530 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. IO, NO. 4. JULY 1988 Automatic Pattern Recognition: A Study of the Probability of Error LUC DEVROYE Abstract-A test sequence is used to select the best rule from a rich 2) The closeness of the actual element picked from D class of discrimination rules defined in terms of the training sequence. to the best element in D . The Vapnik-Chervonenkis and related inequalities are used to obtain The former issue is related to the consistency of the distribution-free bounds on the difference between the probability of error of the selected rule and the probability of error of the best rule estimators in D, and will only be dealt with briefly. Our in the given class. The hounds are used to prove the consistency and main concern is with the second problem: to what extent asymptotic optimality for several popular classes, including linear dis- can we let the data select the discriminator, and how much criminators, nearest neighbor rules, kernel-based rules, histogram are we paying for this luxury? The paper is an exercise in rules, binary tree classifiers, and Fourier series classifiers. In partic- compromises: on the one hand, D should be rich enough ular, 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 so that every Bayes rule can be asymptotically approached choose between parametric and nonparametric rules. by a sequence of rules picked from a sequence of D’s,