Algorithmic Randomness and Learning
The leading thread of this talk will be the relationship between algorithmic randomness and inductive learning. Depending on the learning problem at hand, randomness can be either beneficial or detrimental to learning. Numerous learning tasks can be described as the process of extrapolating patterns from empirical data. One of the driving intuitions behind the theory of algorithmic randomness is that randomness amounts to the absence of any effectively detectable patterns: it is thus natural to regard randomness as being antithetical to learning. On the other hand, there are several learning scenarios where observing a random data stream might instead be conducive to learning—for instance, when the goal is inferring a probabilistic model from a sample generated by some underlying probability distribution. Zaffora Blando will begin by illustrating the broader project of exploring the interplay between randomness and learning in a computability-theoretic setting. She will then focus on the antagonistic side of this relationship and explain how learning-theoretic notions can be used to provide an alternative framework—first introduced by Osherson and Weinstein —for modelling algorithmic randomness, which relies on the identification of randomness with unlearnability. Zaffora Blando will present novel, learning-theoretic characterisations of Martin-Löf randomness and other standard algorithmic randomness notions, and will then discuss the expressivity of this framework.