Affine Multiplexing Networks: System Analysis, Learning, and Computation

Ivan Papusha, Ufuk Topcu, Steven Carr, Niklas LaufferarXiv 2018 · DOI · arXiv

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:

  1. Affine Transformations ($\alpha$): These represent standard linear operations ($Ax + b$), capturing the weights and biases of a network.
  2. 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$.
Fundamental building blocks of an AMN: the multiplexer ($\mu$) and the affine transformation ($\alpha$).

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.

Common nonlinearities like Maximum, Rectifier (ReLU), and Saturation represented as AMN structures.

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

Abstract

We introduce a novel architecture and computational framework for formal, automated analysis of systems with a broad set of nonlinearities in the feedback loop, such as neural networks, vision controllers, switched systems, and even simple programs. We call this computational structure an affine multiplexing network (AMN). The architecture is based on interconnections of two basic conceptual building blocks: multiplexers ($μ$), and affine transformations ($α$). When attached together appropriately, these building blocks translate to conjunctions and disjunctions of affine statements, resulting in an encoding of the network into satisfiability modulo theory (SMT), mixed integer programming, and sequential convex optimization solvers. We show how to formulate and verify system properties like stability and robustness, how to compute margins, and how to verify performance through a sequence of SMT queries. As illustration, we use the framework to verify closed loop, possibly nonlinear dynamical systems that contain neural networks in the loop, and hint at a number of extensions that can make AMNs a potent playground for interfacing between machine learning, control, convex and nonconvex optimization, and formal methods.
BibTeX
@misc{papusha2018affine,
  author = {Ivan Papusha and Ufuk Topcu and Steven Carr and Niklas Lauffer},
  title = {{Affine Multiplexing Networks: System Analysis, Learning, and Computation}},
  year = {2018},
  eprint = {1805.00164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.00164},
}
Figure