Optimal unsupervised learning

Abstract

We introduce an inferential approach to unsupervised learning which allows us to define an optimal learning strategy. Applying these ideas to a simple, previously studied model, we show that it is impossible to detect structure in data until a critical number of examples have been presented -- an effect which will be observed in all problems with certain underlying symmetries. Thereafter the advantage of optimal learning over previously studied learning algorithms depends critically upon the distribution of patterns; optimal learning may be exponentially faster. Models with more subtle correlations are harder to analyse, but in a simple limit of one such problem we calculate exactly the efficacy of an algorithm similar to some used in practice, and compare it to that of the optimal prescription. PACS. 87.10 - PACS. 02.50 - PACS. 64.60C Published in J. Phys. A: Math. and Gen. * Laboratoire associ'e au C.N.R.S. (U.R.A. 1306), `a l'E.N.S. et aux Universit'es Paris VI et Paris VII. 1 I...