Bisimulations for Neural Network Reduction
summary
Defines a neural-network bisimulation based on a pre-sum operator that merges nodes within layers and yields a quotient network with identical input–output semantics; provides a partition-refinement algorithm that computes the coarsest bisimulation (analogous to classical bisimulation minimization). Recognizes exact reductions are limited, introduces delta-approximate bisimulation with a proven epsilon bound on output deviation as a function of delta, network structure and partition. No layer-count reduction and no empirical evaluation yet; verification remains NP‑complete so scalability gains are the goal.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:11Broad Goal
- 1:08Neural Network NN
- 1:44Neural Networks Semantics
- 3:56Neural Networks in Autonomous Systems
- 5:50Output Range Analysis Problem
- 6:10Constraint Solving Approach
- 8:09Bisimulations
- 9:10NN Bisimulaitons using Presum
- 15:16NN Bisimulation Algorithm
- 19:55Approximate NN Bisimulation Quotient
- 21:20Closeness of reduced system
- 22:20Conclusion
related talks
27mProof Minimization in Neural Network Verification
59mDifferential Verification of Deep Neural Networks
19mAbstract Neural Networks
20mIncremental Verification of Neural Networks
15mReduced Products of Abstract Domains for Fairness Certification of Neural Networks
01h 01mTensor Networks and Quantum Algorithms
19mInterval Universal Approximation for Neural Networks
49mAn Algorithmic Theory of Brain Networks