Abstract
We present a novel approach to efficiently compute tight non-convex enclosures of the image through neural networks with ReLU, sigmoid, or hyperbolic tangent activation functions. In particular, we abstract the input-output relation of each neuron by a polynomial approximation, which is evaluated in a set-based manner using polynomial zonotopes. While our approach can also can be beneficial for open-loop neural network verification, our main application is reachability analysis of neural network controlled systems, where polynomial zonotopes are able to capture the non-convexity caused by the neural network as well as the system dynamics. This results in a superior performance compared to other methods, as we demonstrate on various benchmarks.
Introduction
Verifying the safety of neural networks (NNs) is a critical challenge due to their inherent non-linearity. In open-loop verification, the goal is to ensure that for a specific range of inputs (e.g., an image with slight noise), the output remains within safe bounds. In closed-loop verification, where an NN acts as a controller for a physical system like an autonomous vehicle, we must prove the entire system never enters an unsafe state over time.
The primary obstacle in these tasks is "over-approximation." Traditional methods often rely on convex shapes like standard zonotopes or polytopes to bound NN outputs. However, the true output set of a neural network is frequently complex and non-convex. Using convex bounds often results in "loose" approximations, leading to false alarms where safe systems are flagged as unsafe because the mathematical representation was insufficiently precise.
Methodology: Polynomial Zonotopes and Quadratic Approximation
The proposed verification pipeline leverages Polynomial Zonotopes (PZs) to overcome the limitations of convex sets.
Non-Convex Set Representation
Unlike standard zonotopes, which are restricted to convex shapes, polynomial zonotopes can represent non-convex sets. A key advantage is that PZs are closed under polynomial maps. This means that passing a PZ through a polynomial function results in another PZ that exactly represents the transformed set, preserving complex dependencies and non-convexity.
Quadratic Neuron Approximation and Soundness
To handle non-linear activation functions such as ReLU, sigmoid, or tanh, the authors approximate each neuron's input-output relation with a quadratic polynomial ($ax^2 + bx + c$). To maintain mathematical soundness, the maximum possible error between the true activation function and the quadratic approximation is calculated. This error is then added back into the PZ as a "buffer," ensuring the resulting set is a guaranteed enclosure of the true image.
Key Insights
- The Polynomial Map Advantage: By approximating NNs with polynomials, complex non-convex shapes can be propagated through layers without the significant information loss typical of convex methods.
- Capturing Dependencies: PZs utilize "dependent factors" (scalars shared across generators). This allows the mathematical framework to track how different neurons relate to the original input, preventing the "wrapping effect" where error bounds explode over time.
- Efficiency vs. Precision: Using quadratic polynomials provides a "sweet spot"—offering enough precision for safety proofs while remaining computationally efficient for real-world benchmarks.
Evaluation and Results
The method was evaluated on several established benchmarks, including the ACAS Xu benchmark for open-loop aircraft collision avoidance and a suite of closed-loop reachability tests like TORA (translational oscillations/rotational actuator) and ACC (Adaptive Cruise Control).
Performance Highlights
- Tighter Enclosures: PZs produce significantly tighter bounds than standard zonotopes or Taylor models, particularly for Sigmoid and Tanh networks where non-convexity is prominent.
- Superior Speed in Closed-Loop: On reachability benchmarks, the PZ approach was often orders of magnitude faster than competitors. For instance, on the TORA benchmark with a Sigmoid NN, the PZ method completed in 1 second, compared to over 2,000 seconds for JuliaReach.
- Competitive Open-Loop Performance: The PZ-based verifier remained competitive with state-of-the-art specialized verifiers like
nnenumon the ACAS Xu benchmark.
Conclusion and Future Work
While highly effective, the approach faces challenges in complexity management as the number of "generators" defining the PZ's shape grows through network layers. Current research focuses on optimizing "order reduction" to balance precision and speed. Future work includes developing automated heuristics for choosing approximation degrees per layer and scaling the method to massive deep learning models.
Summary updated