Limits to classification performance by relating Kullback-Leibler
  divergence to Cohen's Kappa
L. Crow S. J. Watts
The performance of machine learning classification algorithms are evaluated
by estimating metrics, often from the confusion matrix, using training data and
cross-validation. However, these do not prove that the best possible
performance has been achieved. Fundamental limits to error rates can be
estimated using information distance measures. To this end, the confusion
matrix has been formulated to comply with the Chernoff-Stein Lemma. This links
the error rates to the Kullback-Leibler divergences between the probability
density functions describing the two classes. This leads to a key result that
relates Cohen's Kappa to the Resistor Average Distance which is the parallel
resistor combination of the two Kullback-Leibler divergences. The Resistor
Average Distance has units of bits and is estimated from the same training data
used by the classification algorithm, using kNN estimates of the
KullBack-Leibler divergences. The classification algorithm gives the confusion
matrix and Kappa. Theory and methods are discussed in detail and then applied
to Monte Carlo data and real datasets. Four very different real datasets -
Breast Cancer, Coronary Heart Disease, Bankruptcy, and Particle Identification
- are analysed, with both continuous and discrete values, and their
classification performance compared to the expected theoretical limit. In all
cases this analysis shows that the algorithms could not have performed any
better due to the underlying probability density functions for the two classes.
Important lessons are learnt on how to predict the performance of algorithms
for imbalanced data using training datasets that are approximately balanced.
Machine learning is very powerful but classification performance ultimately
depends on the quality of the data and the relevance of the variables to the
problem.