A nonparametric bound for the bayes error

This paper presents a nonparametric upper bound on the Bayes wrror with a built-in statistical test and can be considered as an extension of the Kolmogorov-Smirnov test.

Abstract

The exact computation of the Bayes Error Probability is not possible in most recognition situations. The mathematical form of the class-conditional probability density functions of real world features is usually unknown. We can only compute certain approximations from finite training sets. This paper presents a nonparametric upper bound on the Bayes wrror with a built-in statistical test. First, the Bayes Error of a feature is expressed in terms of the relative extremes of the absolute value of the difference between the class-conditional cumulative distributions. Then, from the sampled distributions obtained from the training examples, we can establish confidence bands for the true distributions. Finally, an upper bound on the Bayes Error can be easily obtained from the confidence bands. The bound has a definite statistical meaning: it is as tight as allowed by a chosen confidence level. It can be considered as an extension of the Kolmogorov-Smirnov test. An efficient algorithm for the bound in the univariate case is experimentally compared with other typical estimators and shown to be a practical and accurate feature celection criterion in a wide range of applications.