PaperlayerView exact revision on arXiv

Source-linked AI summary

Expressivity of Spiking Neural Networks

Manjot Singh, Adalbert Fono, Gitta Kutyniok

arXiv:2308.08218v2cs.NE

TL;DR

The paper asks how expressive spiking networks are when information is encoded in firing times. Using a linear-response Spike Response Model, it compares LSNNs with ReLU networks and derives expressivity and complexity results. LSNNs can realize continuous and discontinuous piecewise-linear mappings, emulate ReLU networks with complexity overhead, and achieve exponentially many linear regions in one layer.

  • Problem

    The paper addresses the limited understanding of SNN expressive power and its comparison with ANN and ReLU-network expressivity under temporal coding.

  • Method

    The authors analyze LSNNs under a noise-free Spike Response Model with linear responses, single spikes, and firing-time encoding.

  • Results

    LSNNs realize piecewise-linear mappings, can be continuous or discontinuous unlike ReLU networks, emulate multi-layer ReLU ANNs, and generate exponentially many linear regions in one layer.

  • Takeaways & Limitations

    Temporal spiking networks can match ReLU-network approximation capabilities while offering distinct discontinuous mappings and shallow expressivity for some continuous piecewise-linear functions.

  • Takeaways & Limitations

    The complexity analysis leaves extensions of the bounds to multi-layer LSNNs for future work and shows encoding-scheme dependence in some realizations.

Abstract

from arXiv · show

The synergy between spiking neural networks and neuromorphic hardware holds promise for the development of energy-efficient AI applications. Inspired by this potential, we revisit the foundational aspects to study the capabilities of spiking neural networks where information is encoded in the firing time of neurons. Under the Spike Response Model as a mathematical model of a spiking neuron with a linear response function, we compare the expressive power of artificial and spiking neural networks, where we initially show that they realize piecewise linear mappings. In contrast to ReLU networks, we prove that spiking neural networks can realize both continuous and discontinuous functions. Moreover, we provide complexity bounds on the size of spiking neural networks to emulate multi-layer (ReLU) neural networks. Restricting to the continuous setting, we also establish complexity bounds in the reverse direction for one-layer spiking neural networks.

1. Introduction

The paper studies SNN expressivity when information is encoded by precise firing times, comparing linear-response spiking networks with ANNs and ReLU networks. It shows similarities in piecewise-linear computation alongside distinctive discontinuity and complexity properties.

  • Motivation: Temporal coding is motivated by sparse, event-driven information transmission and its potential relevance to energy-efficient neuromorphic computation.
  • Research focus: The paper analyzes SNN expressivity using the noise-free Spike Response Model with linear responses and single-spike temporal coding.
  • Function classes: LSNN mappings are piecewise linear and, under suitable conditions, can be continuous, concave, and increasing.
  • Similarities with ANNs: LSNNs can emulate ReLU nonlinearities and, by extension, multi-layer ReLU ANNs with explicit construction complexity bounds.
  • Differences from ReLU networks: LSNNs may realize discontinuous mappings, unlike ReLU-ANNs, which produce continuous piecewise-linear mappings.
  • Complexity and expressivity: A one-layer LSNN can generate a number of linear regions that scales exponentially with input dimension, matching a key expressivity feature of deep ReLU networks for some functions.

2. Spiking neural networks

The paper formalizes spiking neural networks under the Spike Response Model and specializes them to LSNNs with linear response functions, single spikes, and layered parameterizations. It then defines firing-time mappings and the corresponding artificial-neural-network framework used for expressivity comparisons.

  • Spiking-neuron model: The Spike Response Model represents each neuron through synaptic weights, delays, response functions, thresholds, and membrane potentials, with firing times defined by threshold crossings.Under the single-spike assumption, each presynaptic contribution reduces to w_uv ε_uv(t − t_u), while refractoriness is absorbed into a constant threshold.
  • Linear spiking neural networks: LSNNs restrict the response function to a linear segment, allowing signed effective weights that encode excitatory and inhibitory synaptic effects.The sign parameter distinguishes excitatory from inhibitory synapses, and the synaptic delay determines when a spike can influence its postsynaptic neuron.
  • Firing-time computation: A neuron’s firing time is determined by the presynaptic spikes that arrive before it fires, so the active presynaptic subset can change with weights, delays, thresholds, and input firing times.A spike arriving after the postsynaptic neuron has already fired does not contribute to its firing time.
  • Layered representations: Both artificial networks and LSNNs are represented layerwise, with artificial networks using weight-bias tuples and LSNNs using weight-delay-threshold tuples.Network size is defined as the total number of neurons, and depth is the number of layers in each parameterized representation.
  • Analytical assumptions: The analysis assumes a large or infinite linear-response segment and positive incoming-weight sums, ensuring well-defined firing mappings and, under the stated condition, spike emission.The large-segment assumption makes synaptic effects constant over time; removing the positive-weight condition permits nonsparking neurons but increases model flexibility and complexity.

3. Main results

The paper characterizes linear-response spiking networks (LSNNs) as piecewise-linear models whose continuity depends on weight conditions, then compares their expressivity and emulation complexity with ReLU networks.

  • 3.1. Characterization of functions expressed by LSNNs: LSNN firing mappings are piecewise linear; with a sufficient weight condition they are continuous, while negative weights can produce firing-time discontinuities.The sufficient condition requires each incoming positive weight to exceed the absolute sum of incoming negative weights; without it, plateaus or delayed firing can create jumps.
  • 3.1. Characterization of functions expressed by LSNNs: With positive weights, LSNN firing mappings are increasing and concave, but these properties generally fail when the positivity assumption is removed.The stated positivity properties concern the firing mapping before encoding; corresponding realization properties also depend on the encoding scheme.
  • 3.1. Characterization of functions expressed by LSNNs: Encoding choices materially affect realizability: one encoding pair realizes the target activation with two LSNN layers, another fails there, and inconsistent input-output encodings enable a one-layer construction.The result generalizes to varying widths and arbitrary piecewise-linear activation functions.
  • 3.2. Bounds on the complexity of ReLU-ANNs for expressing LSNNs: A one-layer LSNN with d inputs partitions its domain into at most 2d−1 linear regions, attaining the maximum exactly when all synaptic weights are positive.Each region corresponds to a subset of input neurons that contributes to the output spike, and positive weights make every nonempty subset effective.
  • 3.2. Bounds on the complexity of ReLU-ANNs for expressing LSNNs: For a one-layer positive-weight LSNN, a ReLU network can realize the same firing map with depth ℓ = ⌈log2(d + 1)⌉ + 1 and N(Ψ) ∈ O(ℓ · 22d3+3d2+d).The broader complexity comparison gives O(d) depth and O(8d) units in the alternative construction, while extending these bounds to multi-layer LSNNs remains open.
  • 3.2. Bounds on the complexity of ReLU-ANNs for expressing LSNNs: The two emulation directions yield upper bounds, but they are not optimal: ReLU networks emulating one-layer LSNNs can require exponential dependence on input dimension, whereas LSNNs emulating L-layer ReLU networks scale linearly in that dimension.The authors identify lower bounds and sharper understanding of which functions each model realizes efficiently as open needs.

4. Discussion

The discussion positions LSNNs as theoretically as expressive as ReLU ANNs while emphasizing unresolved practical and modeling limitations. It also identifies intrinsic LSNN constructions and richer neuron models as directions beyond direct ReLU emulation.

  • 4. Discussion: Intrinsic LSNN capabilities could yield more complex, potentially better approximation architectures than directly emulating known ReLU constructions in some circumstances.Finding optimal architectures for different function classes is explicitly outside the paper’s focus.
  • 4. Discussion: Allowing multiple spikes per neuron may improve approximation results but would make the analysis more elaborate because response and threshold effects become coupled.The paper also leaves the influence of response-function choice and firing frequency for future work.
  • 4. Discussion: LSNNs can be as expressive as ReLU-ANNs in the paper’s theoretical, noise-free analysis.The result concerns similarities and differences in computational structure rather than practical implementation performance.
  • 4. Discussion: Theoretical expressivity results may depend in practice on effective training algorithms for programmable weights, delays, and thresholds.Implementing efficient learning algorithms for these parameters is left for future work.
  • 4. Discussion: The analysis uses a noise-free model, whereas extending it to noisy spiking neurons is identified as important for noisy environments.The authors note that real spiking activity is not deterministic because of ubiquitous noise sources.

Appendix A. Proofs

The appendix develops the proof framework by characterizing LSNN firing maps and constructing LSNN realizations of ReLU networks. It uses these results to establish the stated expressivity and complexity claims.

  • Appendix A. Proofs: LSNN firing maps are characterized as piecewise linear, and under stronger assumptions as continuous, increasing, and concave.This characterization provides the structural basis for the subsequent constructions and proofs.
  • Appendix A. Proofs: The appendix constructs an LSNN that emulates the ReLU non-linearity and extends the construction to realize outputs of arbitrary ReLU networks.The construction supports the paper’s comparison between LSNN and ReLU-network expressivity.

A.1. Spiking neural network calculus

The spiking-network calculus provides operations for composing and parallelizing LSNN architectures. Unified input-output encoding makes these operations suitable for building larger network realizations.

  • A.1. Spiking neural network calculus: Unified input and output encoding enables concatenation and parallelization of spiking network architectures.These operations support compositions of network realizations.
  • A.1. Spiking neural network calculus: Concatenation combines two networks when the input dimension of the first matches the output dimension of the second.Under the stated reference-time assumptions, the concatenated network has N(Φ1)+N(Φ2)−d1 computational units.
  • A.1. Spiking neural network calculus: Both concatenation and parallelization can be recursively extended to finitely many networks, although the paper’s constructions require only the introduced forms.More general variants, including different-depth parallelization, can also be established.
  • A.1. Spiking neural network calculus: Parallelization combines two networks with the same depth and input dimension into one network.Its computational-unit count is N(Φ1)+N(Φ2)−d, under the stated shared-input assumptions.

A.2.1. SPIKING NEURON WITH TWO INPUTS

A two-input LSNN neuron partitions its input space according to which incoming spikes determine firing, with each region governed by an affine-linear firing-time rule. The resulting number and geometry of regions depend on the neuron’s weights and on the finite-duration response assumption.

  • A.2.1. SPIKING NEURON WITH TWO INPUTS: A two-input LSNN neuron has separate firing cases for the first input, the second input, or both inputs jointly, each defining a linear region.The toy example analyzes these cases under the assumption that the response duration δ is arbitrarily large.
  • A.2.1. SPIKING NEURON WITH TWO INPUTS: The output firing time is a CPWL mapping over three input regions, with each region associated with an affine-linear mapping.Figure 2 depicts both the partition of the two-dimensional input space and its affine rules.
  • A.2.1. SPIKING NEURON WITH TWO INPUTS: The maximum of three linear regions occurs only when both input weights are positive, while non-positive weights prevent firing altogether.The exact region count depends on the signs and magnitudes of the weights.
  • A.2.1. SPIKING NEURON WITH TWO INPUTS: Thresholds, delays, and weights mainly shift linear-region boundaries through an additive constant determined by the active firing configuration.Their effect on the boundary is limited beyond this shift.
  • A.2.1. SPIKING NEURON WITH TWO INPUTS: Using a finite response duration δ makes spike timing and parameter choices more consequential because some combined delayed inputs may no longer trigger a spike.The paper leaves an in-depth analysis of δ’s influence for future work and continues under the arbitrarily large-δ assumption.

A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS

An LSNN neuron's firing time is piecewise linear in its input firing times, with continuity determined by weight constraints. Under positive weights, the map is additionally increasing and concave.

  • A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS: In two dimensions, the firing-time map is continuous across breakpoints because the changing neuron's effective contribution is zero there.The affine pieces therefore agree at the boundary between linear regions.
  • A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS: For dimensions greater than two, continuity does not automatically follow from piecewise linearity and can fail when weights violate the required constraints.Negative weights of sufficiently large magnitude can produce discontinuous behavior.
  • A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS: An LSNN neuron's firing-time map is piecewise linear, and it is continuous when condition (13) on the weights holds.The condition is necessary and sufficient for continuity of a single neuron's firing time.
  • A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS: The number of linear regions is at most 2^d − 1 for d inputs and reaches this bound when all weights are positive.The actual region count depends on the synaptic weights.
  • A.2.2. SPIKING NEURON WITH ARBITRARILY MANY INPUTS: With positive weights, the firing-time map is increasing and concave.These properties rely on positive synaptic weights and the corresponding characterization of the firing time.

A.2.3. NETWORKS OF SPIKING NEURONS

The piecewise-linear and continuity properties of individual LSNN neurons extend layer by layer to LSNN networks. Under condition (9), the whole network has a continuous piecewise-linear firing map.

  • A.2.3. NETWORKS OF SPIKING NEURONS: A layered LSNN network has a piecewise-linear firing map because each layer composes piecewise-linear neuron maps.Continuity also propagates through the layers when condition (9) holds for every neuron.
  • A.2.3. NETWORKS OF SPIKING NEURONS: Condition (9) guarantees that the network firing map is continuous, making it a CPWL mapping.The condition is sufficient but not necessary for network continuity.
  • A.2.3. NETWORKS OF SPIKING NEURONS: A constructed two-input network remains CPWL despite containing a negative weight that violates condition (9).Its hidden-neuron firing times depend separately on the two input firing times, and the resulting output map is continuous.

Evaluating the firing time of the output neuron at the breakpoints gives

The breakpoint construction shows that network continuity can persist beyond the sufficient weight condition, while negative weights can also produce locally decreasing or non-concave firing maps.

  • Evaluating the firing time of the output neuron at the breakpoints gives: Positive-weight composition preserves increasing and concave firing maps across LSNN layers.The result follows by composing strictly increasing maps and non-decreasing concave functions.
  • Evaluating the firing time of the output neuron at the breakpoints gives: Negative weights can yield an LSNN firing map that is not increasing or concave.The paper constructs examples where increasing inputs produce a lower firing time and where concavity fails.

A.3. Realizing ReLU with LSNNs

The section characterizes which piecewise functions a one-layer LSNN can realize and uses these results to construct ReLU networks under different encoding schemes. A single LSNN neuron cannot realize ReLU with consistent encoding, but a two-layer LSNN can, while one-layer realization of a discontinuous piecewise function requires specific parameter conditions.

  • One-layer impossibility: A one-layer LSNN neuron cannot realize any of the functions f1, −f1, or f2 from Proposition 24.The proof derives contradictions from the required firing-map behavior on intervals around the breakpoint.
  • Firing-map analysis: The firing-map analysis shows that certain positive and negative piecewise behaviors are incompatible with the timing contributions of incoming spikes.For f2, the proof rules out the required constant interval after the breakpoint; for −f2, a suitable one-layer construction is possible under the Proposition 25 conditions.
  • One-layer constructions: A one-layer LSNN neuron realizes the discontinuous piecewise function in Proposition 25 if and only if c1 − c3 = c2 and c1 ≥ 2c3.The value at the breakpoint x = c3 is not fixed, and the construction uses an auxiliary input neuron with constant firing time.
  • Encoding schemes: A single LSNN neuron cannot realize ReLU with consistent encoding, whereas inconsistent encoding permits one-neuron realization.The impossibility follows from the preceding analyses of the firing maps that can be produced under consistent encoding.
  • Consistent encoding: A two-layer LSNN realizes ReLU on a bounded domain with a consistent encoding scheme.The construction introduces an auxiliary input neuron and specifies the network parameters to emulate the desired function.

A.4. Realizing ReLU networks by LSNNs

The paper constructs LSNNs that realize affine maps, ReLU compositions, and complete multilayer ReLU networks by coordinating reference times, auxiliary neurons, concatenation, and parallelization.

  • A.4. Realizing ReLU networks by LSNNs: Any multilayer ReLU ANN can be emulated by composing LSNNs that realize affine maps and ReLU, with the resulting realization matching the ANN.The construction alternates affine-linear and ReLU subnetworks, then extends them through concatenation and parallelization.
  • A.4. Realizing ReLU networks by LSNNs: The affine subnetwork realizes f(x) exactly on [a, b]^d when thresholds and reference times are chosen so the output spike occurs after all input spikes arrive.The reference time can depend only on parameter bounds, allowing the same timing configuration to support different affine functions within those bounds.
  • A.4. Realizing ReLU networks by LSNNs: A three-layer LSNN realizes σ∘f on [a, b]^d using d + 6 computational units, including auxiliary neurons needed to match concatenated subnetworks.The construction first realizes a one-dimensional affine map, then concatenates it with the ReLU network while aligning reference times and input-output dimensions.
  • A.4. Realizing ReLU networks by LSNNs: Parallelizing subnetworks and removing redundant auxiliary neurons yields an intermediate-layer count of 4d + 3 computational units.The construction uses shared auxiliary neurons when identical subnetworks are parallelized.
  • A.4. Realizing ReLU networks by LSNNs: The composed LSNN realizes the complete ANN mapping through layer-wise composition, with its overall size determined by the number of ANN layers and neurons.The paper gives an explicit complexity expression after concatenating the constructed subnetworks.
  • A.4. Realizing ReLU networks by LSNNs: The proof establishes existence of an accurate LSNN emulation, while the specific functional role of delays remains open for further investigation.Delays can alter spike timing and outputs but are not essential to the proof.
Loading 2308.08218v2…