Convergence Rates for Empirical Estimation of Binary Classification
  Bounds
  Bounding the best achievable error probability for binary classification
problems is relevant to many applications including machine learning, signal
processing, and information theory. Many bounds on the Bayes binary
classification error rate depend on information divergences between the pair of
class distributions. Recently, the Henze-Penrose (HP) divergence has been
proposed for bounding classification error probability. We consider the problem
of empirically estimating the HP-divergence from random samples. We derive a
bound on the convergence rate for the Friedman-Rafsky (FR) estimator of the
HP-divergence, which is related to a multivariate runs statistic for testing
between two distributions. The FR estimator is derived from a multicolored
Euclidean minimal spanning tree (MST) that spans the merged samples. We obtain
a concentration inequality for the Friedman-Rafsky estimator of the
Henze-Penrose divergence. We validate our results experimentally and illustrate
their application to real datasets.
