26.04.15 - 30.04.15, Seminar 15181

Challenges and Trends in Probabilistic Programming

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

In this Dagstuhl Seminar, we bring together researchers working in the fields of machine learning, quantitative security, quantum computing, and (probabilistic) program analysis.

Probabilistic programming is at the heart of machine learning for describing distribution functions; Bayesian inference is pivotal in their analysis. Based on probabilistic programs describing the prior and sampling distributions, a compiler generates code to perform inference and make predictions. Programs are often given as a probabilistic graphical model allowing for the specification of dependencies between random variables via generative models and the conditioning of random variables using phenomena or data observed in the real world. A variety of inference algorithms have been developed to analyse and query such models, e.g., Gibbs sampling methods, Metropolis-Hastings and belief propagation. The probabilistic programming approach within AI has the potential to fundamentally change how the community understands, designs, builds, tests and deploys probabilistic systems.

Virtually all cryptographic algorithms are randomized and have probabilistic security guarantees. Similarly, perturbing outputs with probabilistic noise is a standard tool for achieving privacy in computations; e.g., differential privacy achieves privacy-preserving data-mining using probabilistic noise. Cryptographic algorithms and differentially private algorithms are implemented as probabilistic programs. More singularly, one common approach for reasoning about these algorithms is to use the code- and game-based approach proposed by Bellare and Rogaway, in which not only the algorithms, but also their security properties and the hardness properties upon which their security relies, are expressed as probabilistic programs. Quantitative information flow is another important field in security where probabilistic programs and models play an important role. Here, the key question is to obtain quantitative statements about the leakage of certain information from a given program.

Quantum programs are used to describe quantum algorithms and typically are quantum extensions of classical while-programs. According to a basic postulate of quantum mechanics, the unique way to acquire information about a quantum system is to measure it. Therefore, the essential ingredient in a quantum program is the ability to perform measurements of quantum registers, i.e., finite sequences of distinct quantum variables. As the outcome of a measurement is probabilistic, quantum programs are inherently probabilistic.

On the other hand, one recent rapidly growing trend in research on probabilistic programs is more in line with traditional programming languages. It focuses on such topics as efficient compilation, static analysis, program transformations, and program verification using model checking and theorem proving.

Given the diversity of the different communities currently working on probabilistic programs, there is an urgent need to bring these communities together in order to exploit synergies and cross-fertilize. This Dagstuhl Seminar aims to do that. The seminar will offer technically-focused tutorial talks on each of the different topics, but first and foremost will focus on discussions of prime research questions.