Event-threading calculation algorithm complexity estimation

Event-threading algorithm

Algorithm handles input data using new principles and methods based on parallel algorithms, event-driven model [4] and new approaches of ANN training and synthesis of trained network. Using allows decreasing the number of operations from O(n) (classical models) down to O(ln n) (etANN mode). Posterior synthesis of trained decreases the number of connections between neurons by deleting insignificant relations, leading to a simpler system.

Nowadays there exist several models of ANN and their realizations. Classical ANN models were defined by Hoff [1] and Hopfield [2] and modifications of ANN were described by Nell Dale [3]. It is known that ANN solve many classes of problems such as patterns classification, clustering, categorization, functions approximation, predicting, forecasting, optimization, associative memory and so on.

In the case of event-threading algorithm on each step there occur operations only in significant neurons and connections. Classical algorithms recalculate all ANN weights on each step, where the number of operations is up to O(n) [5]. Complexity of algorithm is O(ln n), and after the training is finished, all insignificant weights are removed and complexity becomes much less than at the start-up.

Mathematical Model of Alternative ANN

Artificial neural network is a directional graph with weighted connections and artificial neurons in its nodes. By architecture ANN connections can be grouped in two classes - direct propagation networks with graph without loops and recurrent or back-propagation networks.

Contingencies of the classical ANN:

1. Calculation of neuron output is intended to be instant and without delays. It is not possible to simulate the dynamic systems with internal state with the help of these neurons [8].
2. Absence of neural impulses. There is no modulation of the signal level by density of impulses like in neural system [3].
3. Absence of precise algorithms in activation function selection [9].
4. Absence of mechanisms of network functioning integral control [9].
5. Excessive formalization of threshold and weights concepts. In living neurons numerical threshold  does not exist. It dynamically changes depending on the activity of neurons. Living synapses possess plasticity and stability: weights are configured depending on the signals passing through synapses [10].
6. Variability of natural synapses types which differ by localization and functions. Inhibitory and excitatory synapses in this model are implemented in the form of opposite sign weights [7].
7. Difference between graded potentials and nervous impulses in ANN model cannot be traced [10].

For more faithful modeling of natural neural networks (BNN) there were used literary sources from the domain of biology. Chemical and electrical reactions in human brain in abstract terms can be treated as processes, merging in dynamical system (DS), as brain is a giant dynamical system [3].

Analogous signal is transmitted only via axons where neuron’s perikaryon is charged by sufficient impulse for emission of neurotransmitters in consideration of adiaphoria (temporary lock of the neuron after signal transmission). Size, perikaryon form, length and dendrites form, axon length, form and dendrites tree length, type and volume of neurotransmitters define inner parameters of DS. Density of neurons per volume unit also depends on myelin sheath thickness. Speed of signal transmission depends on the length and diameter of axon: wider axon  faster speed  [7].

Neurons emit activating and inhibitory signals, which decrease the activity of dendrite-connected neurons. Neuron accumulates activating and abscopal signals from dendrite-connected neurons and forms post-synaptic signal. Input signals transformations into output signal occur when summary charge of neuron exceeds certain specific threshold [3].

Neurons interconnections have inner structure different from classical ANN models. Classical ANN models generally are presented in the form n-partite graph K (n1, ..., nm), where ni - size of layer (part); each neuron from layer i is connected with each neuron from layer i+1, where  from [1,m] in case of direct propagation networks, or is connected with each neuron from layer j in general case (back-propagation).

Neuron’s excitation power is coded by speed of signals emission. Higher level of activation or higher post synaptic potential defines faster speed of signals emission. Signals transmission uses impulse-coded modulation, and cells from different brain zones use the same coding method.

Alternative ANN realization is adequate to BNN functionality:

1. Delays in BNN occur when neuron waits neural signals from connected neurons and output signal is emitted when neuron accumulates necessary impulse. Each neuron has its own independent inner state and current charge.
2. Alternative model provides analogue - artificial neural impulse (signal). Event-threading technology allows possibility of synchronous and asynchronous computations execution so far as input signals are incoming.
3. Artificial neuron possesses its own  activation function.
4. Artificial neuron represents an integral unit which depends on its own inner parameters: training speed, threshold function, etc.
5. Neural signal is transmitted deep into neural network after checking on threshold value for a specific neuron by all input signals summation from connected layers.
6. Alternative mathematical model allows possibilities to organize all the types of synaptic connections; methods of event  type can be overridden more than once (multicasting) in domain of the given model or system.
7. Signals (artificial neural impulses) represent an analogical class with a set of values and methods of self-organization and auto-configuration.

Algorithm Complexity Estimation 

Complexity calculation of classical ANN algorithm [5] realization in case of 3-layered network structure depends on the following parameters: ni size of input layer (number of analyzed parameters), nh - hidden layer size (sum of all possible values of analyzed parameters in ni) and no - size of output layer (predicted parameters). The following relations are correct

no < ni << nh,                        (1)

Number of operations in this case Wcls = no * ni * nh. Being based on the inequality (1) complexity is equal to

O(ni * nh + no * nh) = c * O(nh),                      (2)

where c = ni + no having very small value, can be ignored. Then complexity is O(n) for all epochs on training, testing and data-handling stage.

Number of output signals Sout in etANN from layer ai to aj is between ln ai and ln aj when on training stage it is used th(s) or (1+exp(-s))^(-1) as threshold function. Value ln ai in represents frequency of threshold exceeding.

In alternative case number of operations is equal to Wet = ni * ln nh + ln (ln no) * ln nh and depends on current training value of the analyzed parameters. Number ln nh represents operations quantity which are executed when threshold value exceeds and etANN complexity is estimated by O( ln n ).

Conclusion 

Essential modification of classical ANN structure consists in elimination of all unessential connections (threads) after handling by etANN calculation algorithm and introduced dynamics considerably reduces delays in calculations because all operations take place in real-time.

New theoretical mechanism for data handling on testing and application stage of ANN development, being based on asynchronous threads in networks and developed tools, solves formulated problems more effectively and much faster.

Performance increase is reached by parallel work of all neurons and software architecture based on alternative model. etANN is oriented to eliminate three classical problems related to parallelism support in software applications. Classical problems in parallel (multithreading) programming are double blocks, lack of blocks elimination, incorrect blocks order and execution of block operations in critical important sections of the application. Errors of this kind lead to serious and unpredictable performance degradation. In the developed software this problems are solved with the aid of integrated operating system (32bit) technologies [4].

References 

1.  B. Widrow, M. Hoff, Adaptive switching circuits. New York: Institute of Radio Engineers, 1960.
2. J. Hopfield, Cooperative and Competitive Neural Networks. USA, Japan, 1982.
3. P. Dayan, L.F. Abbott, Theoretical Neuroscience - Computational and Mathematical Modeling of Neural Systems. MIT Press, 2000.
4. A. Troelsen, Programmers workshop: C# and .NET platform. Moscow, C.Petersburg: PITER, 2003.
5. V.A. Nosov, Fundamentals of algorithms and their complexity analysis theory. Moscow, 1992.
6. A. Loscutov, A. Mikhailov, Sinergetics. M., Science, 1990.
7. S. Bresler, Advances of physical sciences: Biophysics problems, 4-th Ed., L., Science Academy UdSSR, Institute of High-molecular compounds, 1969.
8. V. Zhukov, E. Ponomaryov, Anatomy of neural system: Tutorial. University of Kaliningrad, Kaliningrad, 1998.
9. G. Hacken, Principles of human brain working. Moscow, PERSE, 2001.
10. I. Zaentsev, Neural networks: Basic models. State University ov Voronezh, 1999.