Rate-optimal Meta Learning of Classification Error
This provides a method for meta-learning classification error rates, which is incremental as it improves upon existing estimators by achieving optimal convergence rates.
The paper tackles the problem of estimating the Bayes classification error without needing to estimate the optimal classifier, by proposing a weighted nearest neighbor graph estimator for the Henze-Penrose divergence. The result is a rate-optimal estimator with mean squared error decaying at the fastest possible rate of O(1/M+1/N), demonstrated on simulated and real datasets.
Meta learning of optimal classifier error rates allows an experimenter to empirically estimate the intrinsic ability of any estimator to discriminate between two populations, circumventing the difficult problem of estimating the optimal Bayes classifier. To this end we propose a weighted nearest neighbor (WNN) graph estimator for a tight bound on the Bayes classification error; the Henze-Penrose (HP) divergence. Similar to recently proposed HP estimators [berisha2016], the proposed estimator is non-parametric and does not require density estimation. However, unlike previous approaches the proposed estimator is rate-optimal, i.e., its mean squared estimation error (MSEE) decays to zero at the fastest possible rate of $O(1/M+1/N)$ where $M,N$ are the sample sizes of the respective populations. We illustrate the proposed WNN meta estimator for several simulated and real data sets.