Seminar - Theoretical perspectives on probabilistic reasoning from labeled data

School of Mathematics and Statistics Research Seminar

Speaker: Karen Seidel
Time: Wednesday 2nd May 2018 at 12:00 PM - 01:00 PM
Location: Cotton Club, Cotton 350
Groups: "Mathematics" "Statistics and Operations Research"

Add to Calendar Add to your calendar

Abstract

Vitanyi and Chater suggested to study the fundamental problem in statistics, how to infer a probability distribution according to observed data, in the set- ting of algorithmic learning theory. Building on essential terminology and first observations by Bienvenu, Figueira, Monin and Shen, the recently revealed equiv- alences between learning formal languages and learning probability distributions by Barmpalias, Fang and Stephan are reviewed.

On the other hand, Aschenbach, Kötzing and the speaker investigated how imposing different restrictions on the learning process effects the learnability of formal languages from labeled data. They observed that learners can be assumed to never guess incorrectly once they found a correct description of the language to be learned (such learners are called non-U-shaped).

After proving this claim, the talk addresses the natural question how the require- ment of non-U-shapedness effects the learnability of probability distributions. For this, we discuss in which sense de Brecht’s framework may be helpful to character- ize learnability by structural properties from topology and descriptive set-th.

Go backGo back to the seminar list