Empirical Risk Minimization Versus Maximum-Likelihood Estimation: a Case Study

We study the interaction between input distributions, learning algorithms and finite sample sizes in the case of learning classification tasks. Focusing on the case of normal input distributions, we use statistical mechanics techniques to calculate the empirical and expected (or generalization) errors for several well-known algorithms learning the weights of a singlelayer perceptron. In the case of spherically symmetric distributions within each class we find that the simple Hebb rule, corresponding to maximum-likelihood parameter estimation, outperforms the other more complex algorithms, based on error minimization. Moreover, we show that in the regime where the overlap between the classes is large, algorithms with low empirical error do worse in terms of generalization, a phenomenon known as over-training. 1 Introduction The problem of pattern recognition can formally be stated as follows (Vapnik 1982): in a certain environment which is characterized by a probability density P (~x),..