20th Estonian Winter School in Computer Science (EWSCS)
XX Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2015

Prakash Panangaden

School of Computer Science
McGill University
Montreal, Qc.

Probabilistic programming languages and semantics


Probabilistic reasoning has long been a part of computer science, however, probabilistic programming languages have recently emerged as a vital and growing area of interest to the programming languages community. As far back as 1997 the probabilistic variant of concurrent constraint programming languages was proposed and in 1999 a POPL paper on the semantics of probabilistic ccp appeared. The recent reemergence of probabilistic ideas has been driven by an exciting new interaction between the machine learning community and the programming languages community.

Central to this interaction is the notion of conditional probability which is the analogue of implication, the fundamental logical counterpart to functional abstraction. Important topics that need to be understood are: (a) what are the probabilistic analogues of basic concepts like binary relations? (b) how does one describe behavioural similarity probabilistically? and (c) how does one capture probabilistic semantics?

Course plan

The target audience is people with some background in programming language theory: operational semantics and denotational semantics. Knowing a very tiny bit of category theory, just the basic vocabulary, will help. The objective is to cover basic topics from a logical and semantical perspective rather than from the algorithmic or complexity theory perspective.

  1. Lecture I: Probability as logic:
    1. Conditional probability.
    2. A dash of measure and integration.
    3. Markov kernels as analogues of binary relations.
  2. Lecture II: Probabilistic bisimulation:
    1. Basic ideas.
    2. Logical characterization of bisimulation.
  3. Lecture III: Metrics for probabilistic similarity:
    1. From relations to metrics.
    2. Metrics from fixed-point theory.
    3. Metrics from modal logic.
  4. Lecture IV: Languages and semantics for probabilistic programming:
    1. Languages for capturing conditioning.
    2. State transformer and wp semantics of a language of while loops.

Course materials


Prof. Panangaden has worked on probabilistic transition systems, bisimulation and probabilistic semantics for nearly 20 years. Along with Josée Desharnais and Abbas Edalat he proved a striking logical characterization theorem for bisimulation. He is the author of the book Labelled Markov Processes (Imperial College Press, 2009) and several papers on probabilistic bisimulation, approximation of Markov processes, metrics for Markov processes, probabilistic semantics and applications to machine learning. He was elected a Fellow of the Royal Society of Canada in 2013.

Valid CSS! Valid XHTML 1.0 Strict Last changed April 17, 2016 21:57 Europe/Helsinki (GMT +03:00) by local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/