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?
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.
- Lecture I: Probability as logic:
- Conditional probability.
- A dash of measure and integration.
- Markov kernels as analogues of binary relations.
- Lecture II: Probabilistic bisimulation:
- Basic ideas.
- Logical characterization of bisimulation.
- Lecture III: Metrics for probabilistic similarity:
- From relations to metrics.
- Metrics from fixed-point theory.
- Metrics from modal logic.
- Lecture IV: Languages and semantics for probabilistic programming:
- Languages for capturing conditioning.
- State transformer and wp semantics of a language of while loops.
- P. Panangaden. Probabilistic programming languages and semantics. Slides from the EWSCS 2015 course.
- Part 1. Probability as logic. [pdf] (UPDATED 3 March)
- Part 2. Probabilistic systems and bisimulation. [pdf] (UPDATED 3 March)
- Part 3. Probabilistic bisimulation metrics. [pdf]
- Part 4. Languages and semantics for probabilistic programming. [pdf]
- Part 4bis. Concurrent constraint programming. [pdf]
- P. Panangaden. Exercises to accompany the EWSCS 2015 course. [pdf]
- Videos from the lectures.
- P. Panangaden. Labelled Markov Processes. Imperial College Press, 2009.
- P. Panangaden. Measure and probability for concurrency theorists. Theor. Comput. Sci., v. 253, n. 2, pp. 287-309, 2001. [doi link]
- J. Desharnais, A. Edalat, P. Panangaden. A logical characterization of bisimulation for labelled Markov processes. In Proc. of 13th Ann. IEEE Symp. on Logic in Computer Science, LICS '98, pp. 478-487. IEEE, 1998. [doi link]
- V. Gupta, R. Jagadeesan, P. Panangaden. Stochastic processes as concurrent constraint programs. In Proc. of 26th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL 99, pp. 189-202. ACM, 1999. [doi link]
- J. Desharnais, V. Gupta, R. Jagadeesan, P. Panangaden. Metrics for labelled Markov processes. Theor. Comput. Sci., v. 318, n. 3, pp. 323-354, 2004. [doi link]
- J. Desharnais, V. Gupta, R. Jagadeesan, P. Panangaden. Approximating labelled Markov processes. Inf. and Comput., v. 184, n. 1, pp. 160-200, 2003. [doi link]
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.
April 17, 2016 21:57 Europe/Helsinki (GMT +03:00)
local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/