ABSTRACT

'AMAZING' UNIVERSAL DISTRIBUTIONS AND THE COST OF LEARNING

Allan Erskine Department of Computer Science, UCL

The word 'amazing' is often found used in conjunction with universal probability distributions; this talk continues in that tradition, and offers further justification for it, explaining that such distributions can be thought of as perfect learners. It can be argued though that the "original" universal distribution, Levin's universal semimeasure, is a little bit too amazing --- it assigns probability to data regardless of how computationally expensive the data was to produce. A review is offered of Schmidhuber's speed-prior, a slightly less universal (but still amazing!) distribution which explicitly addresses this cost problem; other "economic" distributions will also be introduced sharing the same construction as the speed-prior. The talk concludes with a discussion of different notions of cost associated with learning in relation to these distributions.

Maintained by rbennett@cs.ucl.ac.uk