Functional Programming for Probabilistic Programming

A probabilistic program is any program making use of randomness, usually a core part of machine learning algorithms. Probabilistic inference is the art of answering queries over such programs, such as 'what is the probability that the result of running the program is equal to x'. Usually, such a query is answered using monte-carlo methods, e.g., after running the programming a thousand or more times, the histogram over the results gives a numeric approximations of the probability of the result of the program landing in any histogram bin. For example throwing a coin a thousand times would produce a histogram of roughly equal head and tail results such as: {head: 476, tail: 524}, which approximates the true probability numerically.

Instead of numeric approximations we are interested in exact inference, where probabilistic inference is implemented as a interpreter or a compiler that takes a probabilistic program as an input and produces a new program that calculates the probability (density) of any result. In the case of the simple coin flip, the corresponding exact probability function would be “fun c => if c == head then 0.5 else 0.5”, as both results should occur with equal probability. In principle a exact answer is much faster to generate because the program needs to run only once, compared to numeric methods that need to run the program very many times and only slowly converge to the true probability.

For simple cases, like a single coin throw, exact inference is easy to explain and implement, however we want to apply and look for insights from functional programming and type system research, to write experiments or proof-of-concepts to explore advances regarding program expressivity, try out compiler optimization for efficiency, or design type-systems to forbid annoying errors in using probabilistic programming languages.

The specific content of the thesis changes with regard to your ability and what we are currently working on. Given there are not many courses on functional programming, experience in functional programming is very welcome but not necessary, yet a curiosity and general interest in learning and using functional programming is required.

( Next to interest in functional programming, if you are curious about your first steps into programming with dependent types, or remember some stuff from math from probability theory, we can probably also make use of that here :) .)"

This thesis will be co-supervised by the AIML group.