Introduction
The integration of neural networks into safety-critical domains—such as autonomous driving and medical diagnostics—has highlighted a significant "black box" problem. While these models offer high performance, their complex nonlinearities make formal verification difficult. Traditional control theory requires guarantees of stability and safety that standard deep learning architectures cannot easily provide. This paper introduces Affine Multiplexing Networks (AMNs), a novel architecture designed to bridge the gap between the expressivity of neural networks and the rigorous requirements of formal methods.
The AMN Architecture
An AMN is constructed from two fundamental recursive building blocks:
- Affine Transformations ($\alpha$): These represent standard linear operations ($Ax + b$), capturing the weights and biases of a network.
- Multiplexers ($\mu$): A ternary operation that functions as an "if-then-else" logic gate. Given a "select" signal $z$, the output $w = \mu(x, y, z)$ is $x$ if $z \leq 0$ and $y$ if $z > 0$.
By interconnecting these blocks, complex nonlinear systems can be decomposed into a series of logical and linear statements. This structure allows the network's behavior to be encoded directly into Satisfiability Modulo Theory (SMT) and Mixed Integer Programming (MIP) solvers.
Expressivity and Encoding
A key strength of the AMN framework is its ability to exactly represent common neural network components. For instance, a Rectified Linear Unit (ReLU) is simply a multiplexer selecting between the input $x$ and zero based on the sign of $x$. Similarly, max-pooling and saturation functions can be represented as small AMN sub-networks.
Beyond standard activations, AMNs can model discontinuous "switched" systems and logical gates (AND, OR, NOT), making them more versatile than traditional continuous neural networks for modeling hybrid dynamical systems.
Formal Verification and Training
The structured nature of AMNs enables several powerful analytical capabilities:
- SMT-Based Verification: By translating the network into logical equations, researchers can use solvers like Z3 to find counterexamples or prove that a system remains within safe bounds.
- Adversarial Robustness: The framework can compute the exact minimal perturbation required to change a classification, providing a more rigorous measure of robustness than heuristic attacks.
- Lyapunov Stability: The authors propose a counterexample-guided loop to automatically synthesize Lyapunov functions, which serve as mathematical proofs of stability for dynamical systems with neural networks in the feedback loop.
- Consistency Training: In addition to gradient-based methods, AMNs allow for "formal" training where weights are synthesized to satisfy specific logical constraints or datasets using SMT solvers.
Experimental Results
The framework was validated across several benchmarks:
- MNIST Classification: To handle the complexity of SMT solving, images were reduced to 40 dimensions via PCA. The system successfully identified exact adversarial examples.
- Dynamical Systems: The framework proved stability for 2D switched systems and synthesized controllers for systems with nonconvex power constraints—problems typically intractable for standard convex optimization tools.
Conclusion and Future Work
Affine Multiplexing Networks provide a potent interface between machine learning and formal methods. By making the internal logic of a network transparent to automated solvers, AMNs allow for the design of systems that are both high-performing and provably safe. Future research will focus on improving the scalability of SMT/MIP solvers for larger models and extending the framework to handle continuous-time dynamics and vision-in-the-loop control systems.
Summary updated