## Open Theses

### Type Inference for Tractable Probabilistic Programming

Functional Programming for Probabilistic Programming

Master Thesis

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 :) .)"

**Examiner**: Prof. Dr.-Ing. Mira Mezini**Supervisor**: David Richter, M.Sc.Bachelor Thesis, Master Thesis

OPAL is a comprehensive library for static analyses that is developed in Scala to facilitate the writing of a wide range of different kinds of analyses. OPAL supports the development of analyses ranging from bug/bug pattern detection up to full-scale data-flow analyses.

In the context of this project we are always searching for students who are interested in static analysis and want to implement them using Scala. Topics of interest are, e.g., to develop needed base static analyses such as Call Graph Algorithm, analyses to find security issues or to visualize software.

If you are interested in OPAL, do not hesitate to contact Dominik Helm. For further information, you can also go to The OPAL Project

**Examiner**: Prof. Dr.-Ing. Mira Mezini**Supervisors**: Julius Näumann, M.Sc., Dr.-Ing. Dominik Helm