Lecture 5a: Analysing Spiking Nets

The assignment more or less failed.

An answer to this question is still missing: "What can we do with constrained resources that we cannot do with regular computational devices?"

Given the landscape of known complexity classes etc, where do neuromorphic chips fit in?

The main potential advantage of neuro-chips is energy efficiency, but this is usually not taken into account.

To really assess neuromorphic chips, we therefore need a complexity analysis that does not only take time and space, but also energy into account.

Computational Complexity for SNNs

What kind of problems can we solve efficiently on neuromorphic chips? Which are not? What's the difference with Von Neumann architecture?

We should also take energy into account, not only time! Our current model of computation only takes space and time into account; this is a clear limitation!

Short review Turing machine. They are relatively stable and generic and are sufficient for analyzing the behavior of traditional computers. Adding another tape can also be simulated in polynomial time.

The main point is that space and time are part of this model, but energy is not.

Fun detail; the notion of computation was designed in a time without computers.

Question Matthijs: Is there a concept of energy complexity?

A: Yes and no. It's in its infancy. Mostly, you have constructive proofs by giving upper bounds on the amount of spikes needed to solve a problem. But to assess the inherent energy usage, with a dedicated class, not yet afaik.

Which resources to take into account?

No cheating: constructing/configuring/training the network should be part of the computational model and count towards resource usage.

Cheating would be: hey we have this big lookup table with the answers; the problem is tractable yay! Or updated to NNs: let's say we trained an artificial neural network for years and now it can solve extremely hard problems in the blink of an eye. It would be misguided to ignore the training and testing process in evaluating the performance and resource usage of that network.

When do we take resources like training time into account for the computation resources?

  • Amortized resources: cost can be divided over multiple-uses if an algorithm is generic
  • Case-based resources: if the resulting network configuration is case-specific, then the costs cannot be amortized.

Relatively speaking, the cost of building a network is higher if we only use the network once, vs. when we have a generic problem that can be re-used on many problems.

Machine-learning view

So in a machine learning workflow we should take into account training, learning, testing and configuring as well. Because you can re-use the same network for different things, you can however take into account "amortized" resources. ("Afschrijving" ) You can amortize the resources needed for learning and some involved computations if we for example build a classifier that will be applied many times. We cannot amortize if instead we build a network to play a single game of Go. Some of the resources will be case-based and cannot be amortized.

Configuration view

Instead of training a network, we sometimes construct a network that we can then configure in many ways.

Imagine we construct a generic network that can be used in a network flow problem. The network is a general structure with capacities and "pipes" i.e. connections. We can configure it in many ways and test different flows, with different specific inputs.

This configuration is a case-based resource and cannot be amortized.

The construction of such a generic network that handles a particular input type can however be amortized because the general structure will be re-used in all these runs.

Programming view

Let's say we want to use a chip to compute a result a single time, e.g. we use a neuromorphic chip as a co-processor to find the shortest path for a particular graph problem. As opposed to the "configuration view", the network construction is no longer generic but specifically suited for this single problem. After we've computed the result, we're done. For the next computation, we need to reconstruct the network.

Recall: to solve the shortest-path problem we designed a network with the path weights/vertices encoded as delays between neurons. This is 100% case specific. As a result, none of the resources here can be amortized; all resources are case-based.

A new complexity branch is needed

DoE 2016 workshop report, p. 29:

entirely new computational theory paradigm will need to be defined in order to encompass ...

Goal: describe problems that can be solved energy-efficiently on neuromorphic chips.

Of course, time and space remain relevant. But the main promise and goal of neuromorphic chips is to make computation more efficient.

To describe which problems we can solve energy-efficiently we need a new branch of complexity theory:

  • New formal notion of computation
  • Complexity classes with resource constraints
  • New hardness criteria
    • Potential for translating problems into each other while keeping the same resources constant
    • Basically what is used in NP-hard proofs as well; showing that a problem can be translated into another in polynomial time; so not increasing the complexity class.
  • Algorithm to decide in which class a problem in

Beyond Turing

  • Turing Machine
  • Family of Boolean Circuits
    • Extension when we want to take multiple inputs at the same time

The Turing Machine is a general framework that can recognize a particular language L {0,1}* The complexity question here is: does a Turing machine for language L accept a particular phrase in that language (a binary string) using at most R resources (time/space). The used state machine is the same for any input, independent of the lenght of the input.

The complexity question is slightly different for Boolean circuits. Here we allow we have a different algorithm for differently sized inputs.

For differently sized inputs we can have multiple algorithms/circuits. Then the question instead is: does the circuit that matches input size |I| accept the input given resource constraints R, for all inputs I?

So the main difference between TM and boolean circuits is that in TM we have a fixed single state machine, wheres in boolean circuits we take different algorithms/circuits into account

This is why we speak of a family of boolean circuits for language L, so $C_{L,|I|}$.

Notice that the family is defined over input sizes and not just all inputs.

Extension to SNNs

In Boolean circuits we have different circuits for different input sizes. In a way, this is pushed to the extreme in SNNs because there the input I and algorithm A are co-located!

There is no strict distinction between input tape and machine. There is not necessarily an input that is fed into the network. We generalize to the situation where the input is encoded in the network itself. E.g. when arrays are encoded as delays in the network, the input is part of the network. Another example is the encoding of path lengths as delays in the shortest-path problem. Things can be encoded in threshold values, delays, or other parameter values.

As a result, the Collection of SNNs $S_{L,I}$ (cf. $S_{L,|I|}$) allows one network per input. So the difference with Boolean circuits is that the family is no longer defined on input sizes but on each unique possible input.

The acceptance/rejection criterion is redefined in terms of special neurons firing.

That means we do not have a strict distinction between input tape and the computations. In this case, complexity is not simply expressed relative to input size. The question becomes more how long it takes to construct such a network. We need to include this into our complexity assessment. This is the main point here.

Otherwise you can pre-design networks that supposedly "efficiently" solve a problem; but in SSNs precisely the construction, due to co-location, is the essential matter at hand.

The question then is:

"Is there a resource-bounded Turing machine Ml that, given I, generates $S_{L,I}$ which decided I using resources at most $R{_s}$?"

Abstraction: Note that this abstracts away from either the programmer view or the machine learning view; in all cases the underlying question is whether a resource-bounded Turing machine can generate the SNN that decides on input I.

This formalization is very general in the sense that there is no external input assumed at all; but of course, this input may be there, for example to train the parameters of network.

Questions:

Q: "You mentioned that the input could be a set of training data. For non-trivial datasets, how would complexity be analyzed? Training gradually improves performance, but how this could be analyzed in terms of complexity is unclear to me"

Long story short; factoring in the training data in complexity analysis is still vague, also in the traditional machine learning view. The main take-away from this lecture is that at least the network construction should be factorized in.

Q: "Why would encoding the input in the structure, and thus causing a huge |S_L,I| be more desirable than creating a SNN that works on any input?"

There's a trade-off between the resources need to create a general algorithm vs those for a specific network. E.g. if the specific network is very easy to make, it may still me easier to define it on the fly, even if it's a single use network. Constructing general networks also takes more resources.

For example, we've seen in a previous lecture three possible encodings to solve the question whether a number i is in array A. In one case, the inputs where completely encoded in the network itself (delays from a single programmed neuron), which resulted in a small network. In another case, the inputs were completely external. But to allow for that generality we needed more neurons.

Two models for SNN computation

  1. "TM-preprocessing-then_SNN-computation-model" [M o S] (M "before" S)

Sequential process.

Generate SNN based on constraints of traditional Turing bitstring input.

After network construction, we still have the computation itself until the acceptance node is reached.

We can then define a whole hierarchy of complexity classes based on things like: how many synapses are required for the conversion? How many neurons? And then take time, space etc. into account.

This approach is not super powerful (why?).

  1. TM-using-SNN-oracle-model [M^S]

The idea here is to use a neuromorphic chip as a co-processor.

This is a more powerful alternative according to Kwisthout.o It's not entirely clear to me yet why.

If you have a problem (e.g. network flow), you could outsource the shortest path computation to an SNN. In this case the network SNN serves as an oracle to the Turing Machine.

I think the second approach is considered more powerful because now the result is used by the TM, whereas in the first approach the output is just "there" somewhere in the network. (This expression is still too vague)

Some first theoretical results

Kwisthout & Donselaar.

Quite complex concepts; does not seem to be exam material, but great illustration.

Example: network flow problem from theory to Loihi

Note that the theoretical work makes some assumptions that may not hold on the actual hardware chip, in this case the Loihi.

E.g. the theoretical proof assumes we can read out a single neuron. In the Loihi this is not the case: we read out the whole network at once.

See slides for details.