Strachey Lecture: From probabilistic bisimulation to representation learning via metrics
Abstract: Bisimulation is a fundamental equivalence relation in process theory invented by Robin Milner and with an elegant fixed-point definition due to David Park. In this talk, I will review the concept of bisimulation and then discuss its probabilistic analogue. This was extended to systems with continuous state spaces. Despite its origin in theoretical work, it has proved to be useful in fields like machine learning, especially reinforcement learning. Surprisingly, it turned out that one could prove a striking theorem: a theorem that pins down exactly what differences one can "see" in process behaviours when two systems are not bisimilar.
However, it is questionable whether a concept like equivalence is the right one for quantitative systems. If two systems are almost, but not quite, the same, bisimulation would just say that they are not equivalent. One would like to say in some way that they are 'almost' the same. Metric analogues of bisimulation were developed to capture a notion of behavioral similarity rather than outright equivalence. These ideas have been adopted by the machine learning community and a bisimulation-style metric was developed for Markov decision processes. Recent work has shown that variants of these bisimulation metrics can be useful in representation learning. I will tell the tale of this arc of ideas in as accessible a way as possible.
Speaker Bio: Prakash Panangaden is a founding member of the Reasoning and Learning Lab and a Professor Emeritus in the School of Computer Science at McGill University. Prakash is a world leader in the theory of probabilistic processes: approximation, metrics and logics. He and his collaborators have developed quantitative equational logic as a way of reasoning about probabilistic systems, vastly extended the scope of probabilistic bisimulation and invented probabilistic bisimulation metrics which has served as a fundamental tool in the approximation of Markov processes and have had significant impact on reinforcement learning. In the past he has worked on quantum field theory, semantics of concurrent computation, type theory, knowledge in distributed systems, and semantics of programming languages.
Prakash is a Core Member of the Montreal Institute of Learning Algorithms (MILA). He twice, in 2017 and 2022, won the Test-of-Time Prize from the ACM-IEEE Symposium on Logic in Computer Science for papers that had a significant impact over a 20-year span. He was elected a Fellow of the Royal Society of Canada in 2013 and a Fellow of the Association for Computing Machinery in 2021. He was the founding chair of the ACM Special Interest Group on Logic and Computation (SIGLOG).
He obtained his MSc from IIT Kanpur, an MS from the University of Chicago on radiation from black holes, a PhD from the University of Wisconsin-Milwaukee on quantum field theory in curved spacetimes and an MS computer science from the University of Utah on the semantics of dataflow programming. He has been an assistant professor in computer science at Cornell University before taking his current position at McGill.
The Strachey Lectures are generously supported by OxFORD Asset Management