Title: From algorithmic learning of languages to learning probability distributions (and back)

　Speaker: Georgios Barmpalias (Inst. of Software, CAS) (barmpalias.net)

　Time: 15:30 , June 26th, 2018

　Venue: Room 334, Building 5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

　Abstract:

　　Algorithmic learning theory traditionally studies the learnability of grammars given sufficiently long texts, while recent work adapted this framework to the study of learnability of probability distributions from random data. In this study, one is given a sufficiently long stream of random data and the task is to guess a probability distribution with respect to which the data is algorithmically random. We show certain equivalences between algorithmic learning of languages and probability distributions, that allow to transfer much of the classic theory to the study of algorithmic learning of probability distributions. In particular, we prove that for certain families of probability measures that are parametrized by reals (texts), learnability of a subclass of probability measures is equivalent to learnability of the class of the corresponding real parameters. Based on these equivalences, we present a number of applications, providing many new results regarding explanatory and behaviorally correct learnability of classes of measures, thus drawing parallels between the two learning theories. This talk is based on a recent paper written with Fang Nan and Frank Stephan: https://arxiv.org/abs/1801.02566

　Biography:

　　Georgios Barmpalias is in the State Key laboratory of the Institute of Software, in the Chinese Academy of Sciences. He has been with the institute since 2011, first as an international young scientist of the National Natural Science Foundation of China. He has a PhD in mathematics from the University of Leeds in 2004, and has accumulated an extensive publication record of 70+ articles in journals, conference proceedings and book chapters in mathematics, computer science, statistical physics and general science venues. His expertise lies from mathematical logic and computability theory, to aspects of information theory and Kolmogorov complexity, algorithmic learning, and more recently mathematical analysis of social networks and discrete dynamical systems that model real-life situations. Prior to joining the academy of sciences he held positions in the University of Leeds (U.K.), the University of Amsterdam (Netherlands) and Victoria University of Wellington (New Zealand), where he established various collaborations and supervised a number of student and postoc projects. George is a regular and often invited speaker in various international meetings and workshops, from the ASL meeting in Logic, various Dagstuhl and Oberwolfach meetings, to various annual computability, complexity and randomness conferences. George also has an extensive teaching record in various institutions in mathematics and computer science curricula, both in the graduate and theundergraduate levels.