How a Peak on a Completely-flatland-elsewhere

can be Searched for?

A Fitness Landscape of Associative Memory by Spiking Neurons

Akira Imada Brest State Technical University Belarus

We came accross

an extremely difficult

PEAK to be searched for

in a

FITNESS LANDSCAPE

explored by an

EVOLUTIONARY COMPUTATION

(ACS & CISM – 2004 at Elk, Poland) 3

□ A reason for the title — A tiny-flat-island in a huge-lake

(ACS & CISM – 2004 at Elk, Poland) 4

To realize an ASSOCIATIVE MEMORY

we use SPIKING NEURONS whose learning is by

EVOLUTIONARY COMPUTATIONS.

(ACS & CISM – 2004 at Elk, Poland) 5

□ Contents

1. What is Associative Memory?

· Traditional Model by Hopfield.

vs.

· A Model using Spiking Neurons.

2. Can we evolve Spiking Neurons? · We study it by observing Fitness Landscape.

(ACS & CISM – 2004 at Elk, Poland) 6

(cont’d)

3. Results of our Experiments.

· A downhill walk from Hebb’s peak! · How difficult to find other peaks!

4. A proposition of Test-function.

5. Summary & Concluding Remarks.

(ACS & CISM – 2004 at Elk, Poland) 7

□Associative Memory:

• stores patterns – in a distributed way (among neurons),

• recalls patterns – from noisy and/or partial input.

⇓ i.e.

• gives us – perfect recollection from imperfect information □The Associative Memory can be realized with:

• Fully-connected Neural Network Model (Hopfield type)

• Artificial Immune System Model

• Spiking Neurons (To be more biologically plausible)

• etc.

(ACS & CISM – 2004 at Elk, Poland) 9 (ACS & CISM – 2004 at Elk, Poland) 10 (ACS & CISM – 2004 at Elk, Poland) 11

□ A Schematic Diagram of the Hopfield Model

(ACS & CISM – 2004 at Elk, Poland) 12

□ State Transition of the Hopfield Model

s_{i}(t + 1) = sgn(N ; ∑ ; j w_{ij}s_{j}(t))

(ACS & CISM – 2004 at Elk, Poland) 13

□ Hebbian Weights

w_{ij} = \frac{1}{N} p ; ∑ ; μ=1 ξ_{i}^{ν}ξ_{j}^{ν}, (i ≠ j), w_{ij} = 0.

(To store p patterns: x^{μ} = (ξ_{1}^{μ}, ξ_{2}^{μ}, ⋯ ξ_{N}^{μ}) μ = 1, 2, ⋯, p)

(ACS & CISM – 2004 at Elk, Poland) 14

□ Hopfield Model has a Crucial Drawback.

• N neurons store only 2N patterns at most (Gardner). p < 2N.

□ From the Hopfield Model to Spiking Neuron Model

Influence from other neurons via ELECTRIC CURRENTS

⇓

changes MEMBRANE VOLTAGE of the neuron.

(ACS & CISM – 2004 at Elk, Poland) 16

(cont’d)

⇓

If it exceeds a threshold

⇓ the neuron emits

a SPIKE.

(ACS & CISM – 2004 at Elk, Poland) 17

□ Pyramidal Cells & Interneurons

(ACS & CISM – 2004 at Elk, Poland) 18

PYRAMIDAL CELL

∥ (positive current)

⇓

PYRAMIDAL CELL

⇑ (negative current)

∥

INTERNEURON

□ Response of a Single Neuron to an External Stimulus: • Spike rate vs stimuli (Naka-Rushton function)

S(P) = \{ \begin{matrix}MP^{n}/(σ^{n} + P^{n}) & if P ≥ 0 \\ 0 & if P < 0 \end{matrix}

(cont’d)

• Spike rate under time-variant stimulus:

\frac{dr(t)}{dt} = \frac{1}{τ}(−r(t) + S(P))

□ Response of Multiple Neurons • Stimulus to a Pyramidal Cell

P_{i} in the previous Eq. S(P_{i}) = MP_{i}^{n}/(σ^{n} + P_{i}^{n})

is now expressed as

P_{i} = ( N ; ∑ ; j=1 w_{ij} · R_{j} − g · G)_{+}^{2}

(ACS & CISM – 2004 at Elk, Poland) 22

(cont’d)

• Spiking Ratio of a Pyramidal Cell

And

\frac{dr}{dt} = \frac{1}{τ}(−r + MP^{n}/(σ^{n} + P^{n}))

becomes

τ_{R} \frac{dR_{i}}{dt} = −R_{i} + \frac{100( N ; ∑ ; j=1 w_{ij}R_{j} − 0.1G)_{+}^{2}}{100 + ( N ; ∑ ; j=1 w_{ij}R_{j} − 0.1G)_{+}^{2}}

(ACS & CISM – 2004 at Elk, Poland) 23

(cont’d)

• Spiking Ratio of Interneuron

τ_{G} \frac{dG}{dt} = −G − 0.07 N ; ∑ ; j=1 R_{i}

(ACS & CISM – 2004 at Elk, Poland) 24

□ How to encode patterns?

For the pattern

(ξ_{1}, ξ_{2}, ⋯, ξ_{N})

we encode as

ξ_{i} = \{ \begin{matrix}1 & if R_{i} ≥ M/2 \\ 0 & if R_{i} < M/2 \end{matrix}

⇒Rate Coding □ GA Implementation:

1. Represent a series of w_{ij} as a population of strings (chromosome).

2. Evaluate fitness by “How good is each individual?”

3. Generate an initial population at random.

(ACS & CISM – 2004 at Elk, Poland) 26

(cont’d)

4. Evolve them with – Selection

– Crossover

– Mutation

5. Better Solutions from generation to generation.

(ACS & CISM – 2004 at Elk, Poland) 27

□ A Conceptual Illustration of Fitness Landscape □ One specific solution were already known — Hebbian peak.

“When fire then wire” principle ⇓ w_{ij} = sgn(R_{i} − M/2) · sgn(R_{j} − M/2)

(ACS & CISM – 2004 at Elk, Poland) 29

• A Downhill Walk by Flipping zero to one:

(ACS & CISM – 2004 at Elk, Poland) 30

□ Search for an island □ Hinton & Nowlan’s Search for A-needle-in-haystack

• A-needle ⇒ Only one configuration of 20 bits of binary string.

• Haystack ⇒ 2^{20} − 1 search points.

· say, (11111111110000000000) is assigned fitness one, while others are fitness zero.

(ACS & CISM – 2004 at Elk, Poland) 32

□ Black box to detect a needle

(ACS & CISM – 2004 at Elk, Poland) 33

(cont’d)

• lifetime learning of each individual (Baldwin Effect). · about 25% are “1”, 25% are “0”, and the rest of the 50% are “?” . · They are evaluated with all the “?” position being assigned “1” or “0” at random ⇒ learning · Each individual repeats the learning up to 1000 times · If it reaches the point of fitness one at the n-th trial, then the degree to which learning succeeded is calculated as

1 + 19 · (1000 − n)/1000.

(ACS & CISM – 2004 at Elk, Poland) 34

□ Search for a needle

(ACS & CISM – 2004 at Elk, Poland) 35

Test Function — A Tiny Flat Island in a Huge Lake:

Assuming a n-dimensional hypercube all of whose coordinate x_{i} are

−1 ≤ x_{i} ≤ 1 (i = 1, ⋯, n),

find an algorithm to locate a point in the region A

A : {(x_{1}, x_{2}, ⋯, x_{n}) | 0 ≤ x_{i} ≤ a (i = 1, ⋯, n)},

where all the points in A are assigned fitness = 1 and elsewhere 0.

□ How can AIS search for a needle, if any? Function-optimization, pattern-classification, anomaly-detection, or ...?

• Cronal Selection?

• Negative Selection?

• ⋯

• With what and how?

(ACS & CISM – 2004 at Elk, Poland) 37

□ Conclusion • Can Artificial Immune System search for a needle?

• Otherwise, what method would be?

— Call for Challanges!