Upper limits on complexity in spiking neural network computations
Upper bounds on the number of causal pieces in spiking neural networks
Neural and Evolutionary ComputingArtificial IntelligenceMachine Learning
Summary
Spiking neural networks process information by dividing possible inputs into different regions called causal pieces. This paper finds upper limits on how many such pieces these networks can create, which helps understand their complexity and error bounds when approximating functions. The researchers provide two types of mathematical bounds: one general bound applying to many neuron types, and a second more specific one for certain neuron models, using geometric and combinatorial techniques. These bounds clarify how network depth, width, and input size affect the number of causal pieces.
What this means in practice
- •For neural network engineers: Estimate the maximum complexity of spiking neural network architectures during design to guide resource allocation and model capacity.
- •For machine learning theoreticians: Rule out unattainable expressiveness levels in spiking neural networks, focusing research on feasible function approximation capabilities.
A theory result. No direct application yet.
Authors
Dominik Dold, Dennis Elbrächter, Philipp Petersen
Abstract
The input space of single-spike neural networks decomposes into causal pieces, and the number of causal pieces has been shown to provide a lower bound on the approximation error for some spiking neural networks. While this decomposition is applicable to a wide range of spiking neuron models, the limits of how many causal pieces can be realised by spiking neural networks are still unknown. In this work, we derive two complementary upper bounds on the number of causal pieces in feedforward single-spike neural networks. First, we establish a combinatorial bound given by the poly-Bernoulli numbers, which applies to a broad class of spiking neuron models. The bound is of order $e^{2(L-1)N\log N+\mathcal{O}(N)}$, with network depth $L$ and maximum layer width $N$. Second, for a specific set of neuron models, we derive a bound based on hyperplane arrangements. Applying the latter framework, we obtain bounds of order $\mathcal{O}\!\left(N^{(4L-3)(N_0-1)}\right)$ for the non-leaky integrate-and-fire model with exponential synapses and the ReLU-type spike response model, and $\mathcal{O}\!\left(N^{L(N_0-1)}\right)$ for the leaky integrate-and-fire model with Dirac-$δ$ synapses, where $N_0$ is the input dimension. For the non-leaky integrate-and-fire model with Dirac-$δ$ synapses, additional temporal structure allows us to sharpen the general combinatorial bound to one that depends only on $N_0$, independently of the network depth and widths.