Complete Identification of Deep ReLU Neural Networks by Many-Valued Logic
This addresses the issue of functional symmetries in deep ReLU networks for researchers in neural network theory and logic, though it is incremental as it builds on existing ideas from switching circuit design.
The paper tackles the problem of identifying all possible ReLU neural network architectures and parameters that produce the same function, by translating networks into Lukasiewicz logic formulae and using algebraic rewrites based on logic axioms to connect equivalent networks. They show that all networks in a functional equivalence class are linked by a finite set of symmetries derived from these axioms.
Deep ReLU neural networks admit nontrivial functional symmetries: vastly different architectures and parameters (weights and biases) can realize the same function. We address the complete identification problem -- given a function f, deriving the architecture and parameters of all feedforward ReLU networks giving rise to f. We translate ReLU networks into Lukasiewicz logic formulae, and effect functional equivalent network transformations through algebraic rewrites governed by the logic axioms. A compositional norm form is proposed to facilitate the mapping from Lukasiewicz logic formulae back to ReLU networks. Using Chang's completeness theorem, we show that for every functional equivalence class, all ReLU networks in that class are connected by a finite set of symmetries corresponding to the finite set of axioms of Lukasiewicz logic. This idea is reminiscent of Shannon's seminal work on switching circuit design, where the circuits are translated into Boolean formulae, and synthesis is effected by algebraic rewriting governed by Boolean logic axioms.