Some statistical bounds for the accuracy of distance-based pattern classification

摘要

Before implementing a pattern recognition algorithm, a rational step is to estimate its validity by bounding the probability of error. The ability to make such an estimate impacts crucially on the satisfactoriness of the particular features used, on the number of samples required to train and test the system and on the overall paradigm. This study develops statistical upper and lower bounds for estimating the probability of error, in the one-dimensional case. The bounds are distribution-free except for requiring the existence of the relevant statistics and can be evaluated easily by hand or by computer. Many of the results are also applicable to other problems involving the estimation of an arbitrary distribution of a random variable. Some multidimensional generalizations may be feasible.