Bayesian Verification under Model Uncertainty

Lenz Belzner, Thomas Gabor

Introduction

As machine learning systems increasingly build and adapt models of their environment at runtime, they must grapple with "model uncertainty"—the fact that their learned models are only best guesses based on limited data. Traditional statistical model checking (SMC) usually assumes a single, fixed model of the environment. However, modern autonomous systems often use machine learning to build these models on the fly. Because runtime data is limited, there isn't just one "correct" model; instead, there is a whole space of possible models, some more likely than others. This creates gaps in defining success and quantifying risk when providing reliable verification results.

Methodology

The authors propose a new concept called Subjective Satisfaction. Instead of checking a property against one model, they calculate the expected probability of satisfaction across the entire distribution of possible models, weighted by how plausible each model is given the observed data. This is defined as the integral of the satisfaction function over the model parameters, allowing the system to consider all likely versions of reality.

To compute this, they introduce the Bayesian Verification (BV) Algorithm. The algorithm uses a "belief about a belief," maintaining a posterior distribution (using a Beta distribution) of the probability that the system is satisfied.

The Bayesian Verification (BV) algorithm pseudocode.

In each iteration, BV draws a sample model from the current model uncertainty distribution and runs a simulation to see if the requirement is met. The algorithm continues sampling and simulating until it has enough evidence to decide—with a user-specified level of confidence ($c_{req}$)—whether the system satisfies the requirement or violates it. By construction, the algorithm allows users to set stochastic bounds for Type I errors (false negatives) and Type II errors (false positives).

Experimental Evaluation

The paper evaluates the BV algorithm using a synthetic grid world experiment. A mobile agent in a 10x10 grid with randomly placed obstacles must execute a plan of 10 movements. The agent has a failure probability ($p_{fail}$) for its actions, which it must learn from limited observations. The requirement is that the agent must hit fewer than three obstacles during its 10-step plan.

Key Results

The primary finding is that BV successfully stayed within the required statistical error bounds. For example, it kept the error rate below 0.05 for a 95% confidence requirement.

Comparison of Type 1 and Type 2 error rates for BV and MLE against a 0.05 bound.

The authors compared BV against a Maximum Likelihood Estimation (MLE) approach, which selects only the single most likely model. While MLE performed adequately on Type I errors, it failed significantly on Type II errors (false accepts) because it ignored the "long tail" of possible models where the system might fail. BV proved capable of establishing statistical guarantees across various levels of environmental data, whereas non-Bayesian approaches became unreliable when data was scarce.

Discussion and Limitations

A key insight of this work is the separation of aleatoric uncertainty (inherent randomness) from epistemic uncertainty (lack of knowledge). BV’s error bounds are independent of the number of observations; whether the system has seen 10 or 10,000 data points, it respects user-defined confidence levels, though sparse data may require more simulations to reach a conclusion.

However, the BV algorithm has limitations. When the actual satisfaction probability is very close to the required threshold, it may require a very large number of iterations. Furthermore, the bounds are stochastic rather than absolute formal proofs. Future work could involve integrating satisfaction estimators to improve speed or studying the sensitivity of the algorithm to the choice of initial prior distributions.

Summary updated

Abstract

Machine learning enables systems to build and update domain models based on runtime observations. In this paper, we study statistical model checking and runtime verification for systems with this ability. Two challenges arise: (1) Models built from limited runtime data yield uncertainty to be dealt with. (2) There is no definition of satisfaction w.r.t. uncertain hypotheses. We propose such a definition of subjective satisfaction based on recently introduced satisfaction functions. We also propose the BV algorithm as a Bayesian solution to runtime verification of subjective satisfaction under model uncertainty. BV provides user-definable stochastic bounds for type I and II errors. We discuss empirical results of a toy experiment.
BibTeX
@inproceedings{belzner2017bayesian,
  author = {Lenz Belzner and Thomas Gabor},
  title = {{Bayesian Verification under Model Uncertainty}},
  booktitle = {SEsCPS@ICSE},
  year = {2017},
  url = {https://openreview.net/forum?id=PNq2lcKwgw},
}
Figure