The importance of sparsity for generalization

It is generally accepted that inferring a function given only a finite amount of data is only possible if one restricts the model of the data (descriptive approach) or the model of the dependencies (predictive approach) respectively. Over the last years sparse models have become very popular in the field of prediction. Sparse models are additive models f(x)=∑αi k(x,xi) - also referred to as kernel models - where at the solution for a finite amount of data only a few αi are unequal to zero. Surprisingly Bayesian schemes (like Gaussian Processes, Ridge Regression) which do not enforce such a sparsity show good generalization behaviour. We look for an explanation of this fact and finally for the usefulness of sparsity in Machine Learning.

References

• Thore Graepel, Ralf Herbrich, and John Shawe-Taylor. Generalisation Error Bounds for Sparse Linear Classifiers. . In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, pages 298-303, 2000. (Gzipped PostScript).
• Ralf Herbrich, Thore Graepel, and John Shawe-Taylor. Sparsity vs. Large Margins for Linear Classifiers. . In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, pages 304-308, 2000. in press. (Gzipped PostScript).
• Thore Graepel, Ralf Herbrich, and Robert C. Williamson. From Margin to Sparsity. . In Advances in Neural Information System Processing 13, 2001. in press. (Gzipped PostScript).
• Nick Littlestone, Manfred Warmuth. Relating Data Compression and Learnability. unpublished manuscript, June 10, 1986 (Postscript)