Finding a Needle in a Haystack:

from Baldwin Effect to Quantum Computation

Akira Imada

Brest State Technical University, Belarus

(CISIM’2007 – at Elk, Poland) 2

Alora’s proposition (2007)

Brilliance = Ability to find a needle

in a haystack.

“Art is to create a rarely possible appreciation somewhere in a huge universe of our brain.”

(CISIM’2007 – at Elk, Poland) 4

(Cont’d)

(Artificial) INTELLIGENCE can search, classify and recognize normal objects

while only BRILLIANCE

can search for a needle in a hay.

Could an endlessly typing monkey eventually create Shakespeare by chance?

Hopefully not!

Then what about haiku?

Is there really a chance it would happen at all?

うぐいすの

かさおとしたるつばきかな U-Gu-I-Su-No

Ka-Sa-O-To-Shi-Ta-Ru Tsu-Ba-Ki-Ka-Na

(CISIM’2007 – at Elk, Poland) 8

How many possible different candidates

76^{17} ≈ 10^{31}

It’s still like a search for a-needle-in-a-haystack for a monkey to create a meaningful one.

Computational analogue of a-needle-in-a-haystack

A specific rare cases in a huge database; A real necessary information from world-wide-web;

Oil spills in the ocean from satellite image; A cause of failures in diagnosing a huge code;

A collision of a hash function; etc...... ⇓

Such searches are very important for us.

(CISIM’2007 – at Elk, Poland) 10

Associative memory by Spiking neurons

Fitness landscape ⇓

Hopfield network ... many peaks in a rugged land

vs.

Spiking neurons ... like a flat island in a huge lake

(CISIM’2007 – at Elk, Poland) 11

A standard initial distribution of fitness values

(CISIM’2007 – at Elk, Poland) 12

A-tiny-flat-island-in-a-huge-lake

A fictitious 1-D fitness-landscape of Hebbian-learning by spiking neurons

(CISIM’2007 – at Elk, Poland) 13

Then, fitness distribution is ...

(CISIM’2007 – at Elk, Poland) 14

It’s not possible to hillclimb if not a hill to climb!

(CISIM’2007 – at Elk, Poland) 15

Network intrusion data among normal transaction data

E.g. ⇒ 4 attack types in KDD-cup-99 dataset

The winner’s result

(CISIM’2007 – at Elk, Poland) 16

Detection rate by Sabhnani et al. (2003)

(CISIM’2007 – at Elk, Poland) 17

Some Intrusions are immune to

any detectors

Probably because they are like needles in a huge hay.

(Joshi et al. 2001) “If a class is very rare, e.g., 0.5%, prediction of non-target will be 99.5%.”

(Nevertheless, we have still many innocent optimistic reports of success.)

(CISIM’2007 – at Elk, Poland) 18

We now look at the other 4 cases more in detail!

I. Hinton & Nowlan’s experiment II. Reduced even-parity problem as a benchmark III. A robot navigation IV. Quantum computation

< I >

Hinton & Nowlan’s Simplest Needle in a Hay.

Hinton & Nowlan’s Needle (1987)

• A-needle ⇒ A configuration of 20-bit binary strings • Haystack ⇒ 2^{20} − 1 search points

(CISIM’2007 – at Elk, Poland) 21

Their choice of 20-bit was a good one!

(CISIM’2007 – at Elk, Poland) 22

Evolution under Baldwin effect – Lifetime learning of phenotype

A genotype:

(10901099011001001091)

⇓

Its phenotype: (10101001011001001001) (10001011011001001011)

...

(Cont’d)

(Their assumption) The closer the genotype to the needle,

the faster the learning of phenotype.

⇓

This makes the needle-like-peak smoother.

(CISIM’2007 – at Elk, Poland) 24

Their GA implementation

1000 genotypes with 25% flexible genes, each allowed 1000 lifetime learnings;

Roulette wheel selection; One-point cross over; Mutation; ......

(CISIM’2007 – at Elk, Poland) 25

Baldwin effect looks great!

Note, anyway, in both cases, O(N) steps are necessary!

(CISIM’2007 – at Elk, Poland) 27

Are we happy with this Baldwin effect?

Why should we continue

when lifetime-learning already has found the needle?

⇓ (Turney 1987)

“Not from an engineering but a biological interest.”

(CISIM’2007 – at Elk, Poland) 28

Is a high fitness gene a good gene?

(How many successes out of 1000 learnings of 1000 phenotypes)

(CISIM’2007 – at Elk, Poland) 29

Goodness depends on number of 9?

How many 9’s are optimal?

or

Is the number of 9’s decreasing?

(CISIM’2007 – at Elk, Poland) 31

An extinction!

In the 1st generation,

only 4 successful genotypes are found at the luckiest case.

Evolution was not successful.

(CISIM’2007 – at Elk, Poland) 32

What about Lamarckian Inheritance?

An inverse mapping from phenotype to genotype is necessary.

Turney (1996)

“We believe that computing this mapping is intractable,”