Lecture 2: Encoding Information
Recap 2 nibbles in logic with carry
Carry-in serves to take in the overflow of a previous computation.
And: generates over-flow bit (G). XOR: ignores potential overflow. (P)
Normally summing is done serially (e.g. when done by hand), but this is not doable for larger circuits.
Plug in expression for C1 into C2, and so on to compute all operations in parallel without it depending on intermediary results.
ALU
Adds "S-lines"; they do not represent sums but selection lines.
Used to select addition, shift, subtraction; based on their values.
Specific instructions are received by setting the S-lines to different values.
G computes A AND B, the P part computes A XOR B.
M is a global bit, that determines whether carry-ins are ignored or not.
M=1 constitutes a full adder again that adds inputs; M=0 reduces the circuit to an XOR!
Storing information in memory (S-R Latch)
After computing we need to store the computed information somewhere. This can be done with a Set-Reset Latch.
- Set a state
- Reset a state
- Hold that state
- This is important! We do not want to have to give constant input to hold a value.
How do we hold information? With feedback in the logical circuit with an S/R latch, which consists of two NOR gates where their output feeds back into the other NOR gate.
In order to set the Q output, we need to set the SET input to 1. Input to RESET resets Q to 0. The other output is always the inverse, so can be expressed as "not Q".
The initial state, when both inputs are off, in arbitrary in a way. One of the two outputs will be slightly sooner than the other, fixing the initial latched state. This does not matter though. If S=1 and we already had Q=1, Q will still be 1.
Having both R=1 and S=1 is "illegal" input that leads to "unintelligent output" because Q and not Q are then both 0.
After switching a state with either R=1 or S=1, the state will be held in the absence of outputs. This is why R=S=0 "latches" the output to its previous value.
This allows us to hold bits.
But how do we encode real numbers, including fractions, using bits?
Storing real numbers digitally
When we are storing integers numbers, encoding in binary is straightforward. We can count "up" (2^0, 2^1, 2^2 etc.) and our bit strings will just get longer.
To represent fractions, we need to instead count "backwards". E.g. 2^-1=0.5, 2^-2=0.25 etc. But this approach using this binary expansion does not consistently result in exact representations of numbers. You cannot store 1/3 with a digital/binary expansion, but only approximate it.
Naive solution: let's say we have 64 bits, then we can extend the binary encoding also into the negative range. We can represent positive up until 2^31 = 2147483648 . In the negative range, we can have until 2^-31 = 1/2147483648 . This requires 32 bits, but we already included 2^0, so we need 31 extra bits. Now we have 63/64 bits in use and the last bit left as a sign bit to indicate whether we are dealing with a positive or negative number.
This encoding is of course very inflexible because now we cannot encode 2^32 anymore with 64 bits.
IEEE 754 definition of 64 float:
This float64 representation instead makes a distinction between the exponent 'e' and the so-called mantissa, or significand 'F'
E.g. 123.45 = 12345 x 10−2
Where F=12345 and -2 is the exponent.
11 bits (including sign) are used for encoding the exponent. The exponent is always an integer, not a fraction. 2^10=1024, so we can encode 0-1023 with 10 bits. The 11th bit is a sign bit. We then in principle can encode 2048 values, but in fact we can encode a few numbers less because there are some special signs.
- 011 1111 1111 = 0
- 100 0000 0000 = 1
- Notice this is what you get when you add 1 to 011 1111 1111
- 000 0000 0000 = zero either means this is an actual zero, or something smaller than we can express i.e. with leading zeros in the exponent
- So 000 0000 0001 is the least significant value that can be encoded
- 111 1111 1111 = inf with F=0 or NaN when F!=0
- So 011 111 111 is the most significant value that can encoded
64-11=53 bits left.
- 1 sign bit to allow for -0, +0, -inf, +inf
- 52 bits precision left.
- This means that we cannot exactly represent each number in the range.
Analog encodings
Current flow
An alternative is to have an analog continuous representation of a number, e.g. with a current flow, where the amount of energy/ampere is represents the value. Of course we need some convention, e.g. MAXFLOAT=20mA. And we can impose very small numbers as well; the limits are physics basically.
Neuromorphic chips use both digital and analog encodings.
Problems:
- Small numbers may not be able to be measured
- Measure errors introduce computation mistakes
Temporal encoding
The amount of time between two spikes can be considered a representation of a number. So we have a temporal representation
There is no upper bound to this in principle: this is as far as we know a necessary condition for spiking NNs to be Turing complete, but it may take then an age to finally encode a number if the pause is very long. So computing with this is not effective if delays can be arbitrarily long. So what you can really compute in practice (where waiting an age is not necessary) is a different question.
How can we encode a negative number?
Two neurons; one clock; one measures amount of time since clock. Reverse order to measure negative numbers. Meaning... measure time before clock? But this would be complicated, because you need to know about this clock signal in the future in order to synchronize with other computations. This is a very complicated story.
The general idea is the same. We can encode information temporally and this is especially handy when we discretize our temporal representation in small windows that each encode an integer, or an exponent.
Q: What could be an advantage to using such an analog encoding for a continuous number instead of using a 64-bit?
- No storage space
- Energy efficient: only two spikes needed to encode any number
- Independent of the size of the number
In general, we need one clock bit to start the timing, and then one spike per encoded value. So in general we need n+1 spikes needed to represent n numbers.
Information vs. redundancy
Any input-output relation can be computed in many different ways.
How much information is actually transmitted in the I/O function?
We are looking at a stimulus-response relation. Which encoded information goes in, and which information comes out?
We're consider a full adder network with a carry-out. This is one particular realization of a function. We ignore the particular realization and again, only ask about what information goes in and which information comes out.
Then we see that this function is not fully deterministic in the sense that from the output you cannot in the general case fully recover the inputs, because there is a 3-to-2 mapping; i.e. there is redundancy in the encoding as a result some information is lost in the process.
Sum 0 and Carry-out 1 and vice versa has multiple possible input configurations. (This is the redundancy).
We can compute the mutual information between stimulus and response to quantify information loss/how much information from the input signal is captured.
See slide.
$$I = \sum_{s} P(s) \sum_{r}P(r|s)log_2\frac{P(r|s)}{P(s)}$$
We can also look at the information of the response.
We care about that when we have a neuroscience perspective: information about the response can say something about the input signal.
$$I(r) = \sum_{s} P(s|r) P(s|r)log_2\frac{P(s|r)}{P(r)}$$
Encoding of information in the brain
- Local or distributed?
- Rate or place?
- Sparse or dense encoding?
In the brain we encounter all of these.
Local/distributed:
- Local encoding: the "grandmother cell" that fires only when shown a picture of their grandmother.
- Very rare; and not feasible for encoding all possible concepts
- Distributed: only a group of cells provide enough information about a single stimulus
- Analogy with two "neurons": The Sum and Overflow need to be taken together to understand the input
- Place: which neuron fires has meaning
- The sum and overflow neurons are also an example of a place encoding; because if you swap sum and overflow around the meaning completely changes.
-
Rate: only the probability of each neuron firing carrier meaning
-
Dense: 2^N potential information, if it's possible that all neurons fire at the same time
- But everything firing costs a lot of energy
- Sparse: N choose k bits, when only a fraction of the neurons can fire synchronously.
So why would be have rate or sparse encoding when it reduces the amount of information we can transfer?
- Robustness or "Graceful degradation" of rate encoding
- E.g. if we care about rate, then the loss of a single spike here or there does not matter much; it would only affect the overall rate very little.
- Whereas in place encoding the loss of a single neuron is more significant; each neuron has a specific "meaning" here, and changing a single spike could for example here change the most significant bit of the encoded information.
-
Sparse encoding for energy efficiency
-
Temporal encoding can encode a lot more information than rate encoding, but has larger potential for errors; so less robust.
- When frequencies are very high, the difference between rate based encoding and temporal encoding is less.
- Estimations are that in practice it would carry at most 10% extra information.
Let's assume a resolution of a millisecond. Then we could measure (and encode) 1000 spikes per second in a rate based encoding, because there are 1000 possible frequencies here.
But with temporal encoding the specific timing counts so we instead have 2^1000 possible things we can encode in that same second!
This is way too specific.
Solution/middle way: use rougher bins e.g. 10ms in your encoding, so that this allows for some more robustness against noise.
Exercise: encoding a binary probability distribution in a spiking neural network
1. rate coding
Idea 1: have a neuron, rate coded where the rate indicates the probability of heads.
Pro: very simple idea and robust.
Con: Let's say p(heads)=0.8, then that neuron would have a firing rate of 0.8. It would be more energy efficient to switch to representing tails then. Even for p=0.5 it would already be firing 50% of all time, which is a lot. (Another con: this neuron can only encode a single probability).
2: Temporal coding
Idea 2: have a single neuron temporally encoded. E.g. p=0.5 would be a single spike exactly in the middle of two clock signals; so in the middle of the measured time window.
Pro: you would only need one spike in a time frame, which is very energy inefficient.
Con: but you need to have access to a clock signal in order to interpret the spiking signal.
3: Two neurons rate coded
What if we use two neurons instead? Then we would be able to perhaps also encode the uncertainty of the encoded distribution.
Have one neuron fire with a frequency of 2 times per second, and the other at 4/s. They fire independently. How can you combine their information then?
If neuron fires twice as much as the other, this could mean the other one is twice as likely to fire. So their odds/relative frequency contains information. But then 4/2 and 8/4 would encode the same probability. As well would 40/20. However, there is a difference between 4/2 and 40/20 and this could also encode information, namely the certainty (or uncertainty) of the probability that it encodes.
Notice that adding one spike has a disproportionate effect on the computed odds. 5/2 becomes 2.5, 41/20 becomes 2.05 which is still very close to the encoded odds. So you could say that 41/20 encodes a situation where learning has converged and/or learning is not very effective anymore.
Matthijs makes an interesting point that perhaps we want to encode the most commonly needed representations using the least amount of spikes. Then the amount of spikes would then be inversely related to the uncertainty of the encoded probabilities. So less spikes: more certainty.
Additionally, it's perhaps more efficient from a learning perspective to prune spikes rather than to introduce them.
4: Two neurons temporally encoded
Again we can express a probability in terms of the relative frequency.
We can think of the spikes of two neurons switching between two states. So after neuron A fires it is in state Sa until neuron B fires. Neuron B is then in state Sb until neuron A fires.
For any fixed relative frequency, differences in timing between the spike of A and B can now encode hyperparameters in terms of how much time was spent in a particular state.
Where I guess we have maximum uncertainty when all spikes are evenly spaced?
Key takeaway: the more neurons you use, the more information you can encode with that. Information is not just in a single neuron, but there can also be information encoded in the activity of neurons relative to each other. We can potentially even combine rate and temporal encodings to mean different things.
However, the usefulness of temporal encoding is more obvious when we perhaps have deterministically spiking neurons in neuromorphic chips. With stochastis firing in biological systems it is difficult to be precise enough for elaborate temporal encodings to work.
Oscillation and synchronization: phase-of-fire coding
- Temporal synchronization of firing gives rises to wave forms of activity
- Frequency bands are associated with different mechanisms such as feature binding, or motor coordination
Phase-of-fire coding: we don't need an internal clock to set the pace. We can encode spikes relative to internal oscillations; firing out of fase, or in fase.
Oscillations seem to facilitate processing of stimuli. Stimuli coming in on certain frequencies can be anticipated and better processed (?); or then spikes are "interpreted" relative to those frequencies.
Interestingly, we see similar principles of synchronization at work in the use of very novel materials. See NMC-7a-Mentink-Computation_physics.md . Manipulation of quantum-nano spin resonances leads to synchronization as an emergent property. Is this desirable?
An obvious problem is that manipulation of one magnet influences others. In our traditional view of computing this is very bad. But what if this synchronization (that the brain apparently also uses) can itself be an algorithmic primitive to realize phase encoding?
Brain vs neuromorphic architectures
Where do we stop taking inspiring from the brain?
- Astrocytes are thought to allow modulation of signals and plasticity in online learning through calcium waves.
- Neurotransmitters play a role in neuronal signal modulation
Currently these two play no role, but perhaps they carry so much information in the brain that we need to take them into account (e.g. factors of global modulation).