Any Two Learning Algorithms Are (Almost) Exactly Identical

This paper shows that if one is provided with a loss function, it can be used in a natural way to specify a distance measure quantifying the similarity of any two supervised learning algorithms, even non-parametric algorithms, indicating that any two learning algorithms are almost exactly identical for such scenarios.

Abstract

This paper shows that if one is provided with a loss function, it can be used in a natural way to specify a distance measure quantifying the similarityofany two supervised learning algorithms, even non-parametric algorithms. Intuitively, this measure gives the fraction of targets and training sets for which the expected performance of the two algorithms differs significantly. Bounds on the value of this distance are calculated for the case of binary outputs and 0-1 loss, indicating that anytwo learning algorithms are almost exactly identical for such scenarios. As an example, for any two algorithms B,even for small input spaces and training sets, for less than 2e of all targets will the difference between A's and B's generalization performance exceed 1%. In particular, this is true if B is bagging applied to A, or boosting applied to A. These bounds can be viewed alternatively as telling us, for example, that the simple English phrase "I expect that algorithm will generalize from the training set with an accuracy of at least 75% on the rest of the target" conveys 20,000 bytes of information concerning the target. The paper ends by discussing some of the subtleties of extending the distance measure to give a full (non-parametric) differential geometry of the manifold of learning algorithms.