Algorithmic theory on brain network

The algorithm behind the brain network is inspired by the tasks that are solved by human brain.The tasks that are presented to this network are abstract in nature. Algorithms are designed to solve these problems and also analyze these algorithms in terms of static costs such as number of neurons and dynamic costs such as the time to converge to a solution. Lower bound on size of the network affects convergence time of the network. Cost measures are quite tricky when algorithms are in action.

These are isomorphic to the situation of designing a distributed system with some distributed algorithm built on the top of that which concerns with communication between wire and wireless networks, network organization, distributed data management. Also Concurrent system theory is concerned with proving theorems and modeling system. Biologically systems behave like distributed systems, for example brain cells organise themselves into meaningful patterns, insect colonies die off to solve problems of cooperative exploration, task allocation, consensus and neuron cooperate to do focus, learning and memory. Biological features are Spiking neurons, noisy firing thresholds, excitation and inhibition, restricted connectivity, synapse weights, synchronization.

Network Model

The model is called Stochastic Spiking Neural Networks. It is a kind of neuron network where the spike/activation of a neuron at a particular time is probabilistic and depends upon weights value between connected neurons. Mathematically, v↑t=1 iff neuron v at time t spikes, where v↑t means state of neuron v at time t.

Spiking neuron model

pot(v, t)=∑u↑(t-1)w(u↑(t-1), v)-b(v) where pot(v, t)=Potentional function, u↑(t-1)=Previous state neuron at time (t-1), w(u↑(t-1), v)=weight of the connected neuron b(v)=bias of neuron v. Pr[v↑t=1]=1/(1+e↑(-pot(v, t))) where Pr[v↑t=1] probability at time t.

All neurons can be strictly inhibitory or strictly excitatory, i.e., w(u, v)≥ 0 for all v or w(u, v)≤ 0 for all v. Here we ignore some of other biological features: Refractory period, spike propagation delay, history, noise on synapses. A weight of the connected directed graph, nodes represent neurons, edges represent synapses, weights indicate synaptic strength. Regard weight = 0 as absence of edge, weight > 0 as excitatory, weight < 0 as inhibitory. There are three type of neurons: Input neuron, Hidden neuron and output neuron. Input and output neurons must be excitatory. Auxiliary neurons may be either excitatory or inhibitory.

Network Terminology

Configuration(C): Firing/spiking state is either 0 or 1 depending on value C(u) where 'C' defines the Configuration of neurons and C(u) be Configuration of neuron 'u'. Execution(α): α=C↑0,C↑1,......C↑(t-1) set of 't' configuration at different time unit from 0 to (t-1). C↑t=C↑t(u) denotes Configuration of neuron 'u'.

Basic Considerations

Input firing patterns may be arbitrary. For auxiliary and output neurons firing pattern are determined by network definitions. For every infinite input execution, the network produces a probability distribution on infinite executions, by applying the stochastic firing dynamics for all non-input neurons at a different time unit.

Computational Problems

There is function f:{0,1}↑n→{0,1}↑m where n is number of input neuron whether if firing or not and m is output neuron. The issue is to design a compact function that converges to Y∈f(X) with high probability. With that tradeoff among number of input neurons, weight assigned to connected neurons, number of hidden layer, maximum weight used.

• 

Brain Algorithm

This algorithm is called Winner-Take-All Problem which is developed by Nancy Lynch, Cameron Musco, Merav Parter. It is a kind of neural network which is self-stabilizing.
With high probality >= (1-δ) the network converge within short time t↓c which corresponds to single firing output for firing input and remain in the stable state for long t↓s time.

• 

It is denoted by WTA(n, t↓c, t↓s,δ), where n is number of input layers and here number of output layer is equal to number of number of input layer,t↓c is convergence time,t↓s is stability time and δ is any small constant between 0 and 1. This can be achieved by introducing two inhibitors which are convergence inhibitor and stability inhibitor.
Stability inhibitor(a↓s): This neuron activate with high probability whenever one or more output neuron fires and restrict the neuron to fire in next round which are currently inactive.
Convergence inhibitor(a↓c): This neuron fires with high probability whenever two or more outputs fire and any active output neuron at time t has probability of 0.5 to fire in next time unit.
On a half of the currently-firing outputs stop firing at each step and so with constant high probability at time t↓c <= logn such that network produces desired one output neuron activated and remain in this state for long t↓s time. Meanwhile, the stability inhabitor stop other neuron to be activated. To increase t↓s we need to multiply the weights and biases by γ which is relatively larger w.r.t n and t↓s. A linear increase in network parameters implies exponential increase in t↑s. Convergence time of the network is O(logn).
Theorem 1: Assume γ ≥ clog(n t↓s  /δ). Then starting from any state, with probability ≥1 − δ, the network converges, within time t↓c=clog(nlog(1/δ)) , to a single firing output corresponding to a firing input, and remains stable for time t↓s.

Proof of correctness: The convergence and stability can be proved with similar logic that are used in distributed algorithm. That is stability can be proved using invariant property and convergence by showing progress over multiple iteration through the network with high probability.
Stability Proof: Consider a configuration C leading to new configuration C¹
stochastically with high probability. The with high probality No output corresponding to a non-firing input fires in C¹
. If a↓s  is the only inhibitor that fires in C, then the same outputs fire in C¹
as in C. If there is exactly one firing output in C then a↓s  fires in C¹
and a↓c  does not.
Convergence Proof: It is proved by progressing through multistep behaviour and step happens with high probability. There is a chance that it converges to a undesirable state, i.e., no firing output neuron. Because of two different inhabitors there is a chance of race condition during a↓c duration. To get high probability network have to be reset and run again.
Lemma(Convergence): From any configuration C, the probability of reaching a valid configuration within time =nlogn is ≥ 1/18.
Theorem: If γ ≥ clog(n(t↓s)/δ), then the network solves WTA(n, t↓c , t↓s , δ) , with t↓c =nlognlog(1/δ). To get the faster convergence it is required to add extra inhibitor(both stability and convergence inhibitor) with exponentially growing biases.
Theorem: With one stability inhibitor plus k convergence inhibitors, then from any state, with prob ≥1 − δ, the network converges, within time t↓c=cklog↑(1/k)nlog(1/δ), to a single firing output corresponding to a firing input, and remains stable for time t↓s.
Theorem: No stochastic neural network with only one auxiliary neuron can solve Winner-Take-All Problem(WTA) in t↓c for t↓s time.
Proof: The inhibitor(auxiliary neuron) can either activate or inactivate. Let a be the inhibitor.
Claim 1: If a activate so it is highly probable that corresponding output neuron will fire, so this guerantees that at least one output neuron will fire in convergence time of t↓c.
calim 2: If a activate then any output which was active will stop firing, so this ensure that at most one output neuron fire in convergence time of t↓c.
By both claim it proves the theorem.

Similarity testing

Given two input firing patterns C↓1 and C↓2 , distinguish the case where C↓1 = C↓2 from the case where they are far from being equal, e.g., d(C↓1 , C↓2)≥ εn, where C↓i is notation of ith firing pattern.
After convergence, the output neuron should fire continuously if the inputs are equal, and not fire if they are far from equal.
Simple (non-neural) sublinear time algorithm: Sample O(logn/ε)) random positions and check whether C↓1 and C↓2 match at those positions.
For sampling random positions, we use an Indexing Module(Neuro-RAM): given an index encoded by the firing pattern of a set of neurons, select the appropriate value of C↓1 or C↓2. After convergence, the output neuron should fire continuously if and only if C(Z) is firing. To get the output y, it is required to used C(Z), since it is connected.

Indexing

Indexing used to access information from large data set. This seems important for similarity testing, word triggering of a memory.
Algorithmic Results:
Theorem 1: For any t≤√n , there is an SNN solving the indexing problem with O(n/t) auxiliary neurons that converges by time t (With High Probability).
Sublinear-sized circuit running for similarity testing with O(√nlog(n/ε)) running in O(√n) time. This lower bound shows that our two-inhibitor network's convergence time cannot be improved by more than a log↑2n  factor. This separates feed forward stochastic NN from feed forward circuits composed of sigmoidal gates with real-valued outputs; these can implement indexing with O(√n) neurons, in O(√n) time.
Theorem 2: Any circuit that solves the indexing problem and converges by t time with high probability, requires Ω(n/tlog↑2n) auxiliary neurons.

References

This article "Algorithmic theory on brain network" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Algorithmic theory on brain network. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---