Nonparametric Bayes error estimation using unclassified samples

IEEE Transactions on Information TheoryPublished 1 July 1973

Keinosuke Fukunaga, David Kessell

DOI10.1109/tit.1973.1055049

Source URL

Citations88

SJR quartileQ1

SJR score1.46

SNIP1.76

TL;DR

A pattern recognition system may be viewed as a decision rule which transforms measurements into class assignments and the Bayes error is the minimum achievable error, where the minimization is with respect to all decision rules.

Abstract

A new nonparametric method of estimating the Bayes risk using an unclassified test sample set as well as a classified design sample set is introduced. The classified design set is used to obtain nonparametric estimates of the conditional Bayes risk of classification at each point of the unclassified test set. The average of these risk estimates is the error estimate. For large numbers of design samples the new error estimate has less variance than does an error-count estimate for classified test samples using the optimum Bayes classifier. The first application of the nonparametric method uses k -nearest neighbor ( k -NN) estimates of the posterior probabilities to form the risk estimate. A large-sample analysis is made of this estimate. The expected value of this estimate is shown to be a lower bound on the Bayes error. A simple modification provides unbiased estimates of the k -NN classification error, thus providing an upper bound on the Bayes error. The second application of the method uses Parzen approximation of the density functions to obtain estimates of the risk and subsequently the Bayes error. Results of experiments on simulated data illustrate the small-sample behavior.

Keywords

MathematicsDecision Sciences

IEEE Transactions on Information TheoryNearest neighbor pattern classification

16,134 Citations1967Thomas M. Cover, Peter E. Hart

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.

The Annals of Mathematical StatisticsOn Estimation of a Probability Density Function and Mode

10,504 Citations1962Emanuel Parzen

View PDF

IEEE Transactions on Information TheoryOn optimum recognition error and reject tradeoff

826 Citations1970Chee Lap Chow

An optimum rejection rule is described and a general relation between the error and reject probabilities and some simple properties of the tradeoff in the optimum recognition system are presented.

IEEE Transactions on Systems Science and CyberneticsThe Nearest Neighbor Classification Rule with a Reject Option

214 Citations1970Martin E. Hellman

Here the (k,k?) nearest neighbor rule with a reject option is examined, which looks at the k nearest neighbors and rejects if less than k? of these are from the same class; if k? or more are from one class, a decision is made in favor of that class.

IEEE Transactions on Information TheoryConvergence of the nearest neighbor rule

87 Citations1971T. Wagner

It is shown that when the samples lie in n-dimensional Euclidean space, the probability of error for the nearest nearest neighbor rule conditioned on the n known samples converges to R with probability 1 for mild continuity and moment assumptions on the class densities.

Elsevier eBooksLEARNING IN PATTERN RECOGNITION

77 Citations1969Thomas M. Cover

A discussion is made of some nonparametric approaches to the problem of the classification of an unknown pattern when the only information on the underlying distributions associated with the various categories is that which can be obtained from a finite number of samples.

IEEE Transactions on ComputersEstimation of Classification Error

70 Citations1971Keinosuke Fukunaga, David Kessell

Methods of estimating the probability of error for the Bayes' classifier which must be designed and tested with a finite number of classified samples are discussed and the expected difference between estimates is discussed.

IEEE Transactions on Information TheoryApplication of optimum error-reject functions (Corresp.)

33 Citations1972Keinosuke Fukunaga, David Kessell

In an optimum pattern-recognition system the error rate is determined by the reject function and this correspondence describes how this property may be exploited to provide quantitative tests of model validity using unclassified test samples, basically goodness-of-fit tests for a function of the observations.

TechnometricsSeries Estimation of a Probability Density Function

22 Citations1971Donald F. Specht

IEEE Transactions on Information TheoryNonparametric Bayes-risk estimation

20 Citations1971S. Fralick, Rodney J. Scott

Two nonparametric methods to estimate the Bayes risk using classified sample sets are described and compared and it is shown that both have acceptable small- sample properties; however, small-sample convergence of both estimators depends strongly on the choice of metric and local area or window size in the measurement space.