Moving Beyond Randomness in Probabilistic Modeling with Nondeterminism

What is it about?

Randomness has established itself as a ubiquitous way to model scenarios where the exact behaviour of systems is too complicated to describe precisely. For example, accurately describing the underlying mechanisms of measurement noise in a sensor is often downright impossible, whereas modelling the noise as random offers a simple and effective approximation. Over the past years, Probabilistic Programming Language (PPLs) have been developed as an easy and approachable way to make modelling probabilistic scenarios accessible to people without a background in probability theory. PPLs allow users to describe a scenario in the familiar language of standard programming languages, whereas a specialised inference engine automatically handles the mathematics to determine the probability distribution of the possible program outputs. In this context, many PPLs have been developed to infer output probabilities, and frequently they also support for Bayesian reasoning about conditional probabilities. However, not all forms of uncertainty are best modelled with randomness, and in these cases it might make more sense to consider Nondeterminism. Nondeterminism asks the user only to specify the set of possible actions, and the inference engine then automatically determines the optimal course of action, which would lead to highest possible probability for a given outcome. However, modern PPLs often do not support nondeterministic modelling in tandem with Bayesian conditioning, and so our work aims to close the gap with the introduction of a new and efficient inference algorithm.

Featured Image

Photo by Edge2Edge Media on Unsplash

Photo by Edge2Edge Media on Unsplash

Why is it important?

Extending Probabilistic Programming Languages with Nondeterminism significantly increases the expressiveness of these languages. In particular, it allows users of these languages to soundly reason about worst case probabilities and to find upper bounds for risks in scenarios where randomness might not be a good approach. As such, nondeterminism can be used to model mechanism which are not understood well enough to provide a reasonable probabilistic model, or when trying to model fully unknown systems like malicious actors.