Reachable Set Estimation and Verification for Neural Network Models of Nonlinear Dynamic Systems

Weiming Xiang, Diego Manzanas Lopez, Patrick Musau, Taylor T. JohnsonarXiv 2018 · OpenReview

TL;DR

This paper tackles the critical challenge of ensuring safety in systems controlled by neural networks, specifically focusing on Nonlinear Autoregressive-Moving Average (NARMA) models. They propose a novel layer-by-layer method to estimate the "reachable set" of a neural network, which is then used to formally verify if the system will stay within safe operating bounds.

What Problem Does This Paper Address?

Neural networks are increasingly used to model complex, nonlinear dynamic systems, especially when traditional analytical models are difficult to derive. However, their "black box" nature makes it hard to guarantee their safety, a crucial requirement for applications in safety-critical domains like autonomous vehicles or industrial control. A key challenge is to formally verify that the system's outputs will always remain within acceptable, safe limits, even under various inputs and initial conditions. This paper addresses this by developing a method to estimate the set of all possible future states (the reachable set) of a system modeled by a neural network, and then using this estimation for safety verification.

Methods

The core of the paper's contribution lies in its approach to reachable set estimation for Multi-Layer Perceptrons (MLPs), which are used to model NARMA systems.

  • MLP Reachable Set Estimation: The authors propose a layer-by-layer computation. The input space of the MLP is partitioned into a finite number of "cells" (intervals). For each cell, they compute an over-approximation of the output reachable set. The union of these cell-wise over-approximations forms an overall over-approximation of the MLP's output reachable set. This process leverages the monotonic property of activation functions.
  • NARMA Reachable Set Estimation: Building on the MLP method, they develop an iterative algorithm to estimate the reachable set for NARMA models. This involves recursively applying the MLP reachable set estimation to predict future states based on past states and inputs.
  • Safety Verification: Once an over-approximation of the reachable set for the NARMA model is obtained, safety verification is performed by checking if this estimated reachable set intersects with any "unsafe" regions. If there's no intersection, the system is deemed safe.

Datasets

The paper does not explicitly mention training datasets for the neural networks. Instead, it focuses on the verification of pre-trained neural network models. The examples provided use specific weight matrices and bias vectors for the MLPs, implying these models are already trained.

Key Insights and Ideas

  • Bridging the Gap: The paper effectively bridges the gap between the powerful but opaque nature of neural networks and the stringent safety requirements of critical systems.
  • Partitioning for Tractability: By partitioning the input space of MLPs into manageable cells, they transform an intractable problem into a series of solvable sub-problems.
  • Layer-by-Layer Progress: The layer-by-layer computation for MLPs is a key insight, allowing the method to scale to deeper networks by building upon the results of preceding layers.
  • Over-approximation as a Safety Net: The use of over-approximations for reachable sets is a pragmatic approach. While it might lead to some conservatism, it provides a formal guarantee that the true reachable set is contained within the estimated one, thus ensuring safety.

Key Results

The paper demonstrates its approach through numerical examples, including a Maglev system.

  • Effective Reachable Set Estimation: Figures 1, 2, 3, and 4 visually show the estimated reachable sets for MLPs and NARMA models, illustrating how the method captures the range of possible system behaviors.
  • Impact of Partitioning: Figure 2 and Table 1 highlight that increasing the number of partitions (discretizing the input space more finely) leads to tighter, more accurate reachable set estimations, albeit at the cost of increased computation time.
  • Validation with Trajectories: In the Maglev example (Figure 3), 100 randomly generated state trajectories are shown to lie entirely within the estimated reachable set, validating the approach. Similarly, Figure 4 shows 200 random trajectories within the estimated reachable set.
  • Safety Verification Capability: The paper outlines how the computed reachable set can be used to verify safety specifications, as demonstrated in Example 2 where a safety region is defined and checked against the estimated reachable set.

Limitations and Future Work

  • Conservatism: The authors acknowledge that the estimation is an "over-approximation," meaning it might be more conservative than necessary. This conservatism can increase with the depth of the neural network.
  • Computational Cost: For deep neural networks with many layers, the computation effort required for fine discretization can become substantial.
  • Future Work: The authors explicitly state that reducing the conservativeness caused by an increasing number of layers and generalizing the approach to deeper neural networks will be their future focus. They also suggest extending the method to higher-dimensional systems.

Summary updated

Abstract

Neural networks have been widely used to solve complex real-world problems. Due to the complicate, nonlinear, non-convex nature of neural networks, formal safety guarantees for the behaviors of neural network systems will be crucial for their applications in safety-critical systems. In this paper, the reachable set estimation and verification problems for Nonlinear Autoregressive-Moving Average (NARMA) models in the forms of neural networks are addressed. The neural network involved in the model is a class of feed-forward neural networks called Multi-Layer Perceptron (MLP). By partitioning the input set of an MLP into a finite number of cells, a layer-by-layer computation algorithm is developed for reachable set estimation for each individual cell. The union of estimated reachable sets of all cells forms an over-approximation of reachable set of the MLP. Furthermore, an iterative reachable set estimation algorithm based on reachable set estimation for MLPs is developed for NARMA models. The safety verification can be performed by checking the existence of intersections of unsafe regions and estimated reachable set. Several numerical examples are provided to illustrate our approach.
BibTeX
@misc{xiang2018reachable,
  author = {Weiming Xiang and Diego Manzanas Lopez and Patrick Musau and Taylor T. Johnson},
  title = {{Reachable Set Estimation and Verification for Neural Network Models of Nonlinear Dynamic Systems}},
  year = {2018},
  eprint = {1802.03557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.03557},
}
Figure