Rethinking Generalisation
This work addresses a foundational issue in machine learning theory for researchers, but it appears incremental as it builds on existing risk distribution concepts.
The paper tackles the problem of predicting generalization performance in machine learning by assuming a known distribution of risks, computing expected error for classification and regression, and identifying attunement as a key factor. It presents analyses for Boolean functions and perceptrons, with corrections for chance correlations in training data.
In this paper, a new approach to computing the generalisation performance is presented that assumes the distribution of risks, $ρ(r)$, for a learning scenario is known. From this, the expected error of a learning machine using empirical risk minimisation is computed for both classification and regression problems. A critical quantity in determining the generalisation performance is the power-law behaviour of $ρ(r)$ around its minimum value---a quantity we call attunement. The distribution $ρ(r)$ is computed for the case of all Boolean functions and for the perceptron used in two different problem settings. Initially a simplified analysis is presented where an independence assumption about the losses is made. A more accurate analysis is carried out taking into account chance correlations in the training set. This leads to corrections in the typical behaviour that is observed.