Approximation and generalization properties of the random projection classification method
This work addresses generalization issues in machine learning classification, offering a potentially more efficient approach for problems with large Rashomon ratios, though it appears incremental as it builds on existing random projection and complexity theory.
The paper tackles the problem of generalization gaps in classifiers by studying a low-complexity method that thresholds random one-dimensional projections of data embedded in higher-dimensional spaces, showing that under ideal conditions, its error converges to the optimal Bayes error as parameters increase, and bounding its generalization gap to be smaller than that of linear classifiers for certain problems.
The generalization gap of a classifier is related to the complexity of the set of functions among which the classifier is chosen. We study a family of low-complexity classifiers consisting of thresholding a random one-dimensional feature. The feature is obtained by projecting the data on a random line after embedding it into a higher-dimensional space parametrized by monomials of order up to k. More specifically, the extended data is projected n-times and the best classifier among those n, based on its performance on training data, is chosen. We show that this type of classifier is extremely flexible as, given full knowledge of the class conditional densities, under mild conditions, the error of these classifiers would converge to the optimal (Bayes) error as k and n go to infinity. We also bound the generalization gap of the random classifiers. In general, these bounds are better than those for any classifier with VC dimension greater than O(ln n). In particular, the bounds imply that, unless the number of projections n is extremely large, the generalization gap of the random projection approach is significantly smaller than that of a linear classifier in the extended space. Thus, for certain classification problems (e.g., those with a large Rashomon ratio), there is a potntially large gain in generalization properties by selecting parameters at random, rather than selecting the best one amongst the class.