Hinton & Nowlan’s

Computational Baldwin Effect Revisit:

Are we happy with it?

Akira Imada Brest State Technical University

Belarus

(13th International Scientific Conference – at Panevezys, Lithuania) 2

Looking for “a-needle-in-a-haystack”

(13th International Scientific Conference – at Panevezys, Lithuania) 3

To break an unknown 4 digit decimal PIN

Only one out of 10,000 is correct (a-needle-in-a-haystack)

⇓

How many random/exhaustive trials

will be necessary to break?

⇓

An average of 5,000 trials.

A needle hidden in a huge grid world.

Can a navigation robot reach it?

⇓

A 2-D version of a-needle-in-a-haystack.

(13th International Scientific Conference – at Panevezys, Lithuania) 5

What is a-needle-in-a-haystack

Assume we have an ORACLE for needle F (x) “Find x (among N items) such that F (x) = 1”

when

only x fulfills F (x) = 1 while F (x) = 0 for all others.

(We might call F (x) a fitness function of this problem.)

(13th International Scientific Conference – at Panevezys, Lithuania) 6

O(N) steps are necessary!

(13th International Scientific Conference – at Panevezys, Lithuania) 7

Can we look for a needle more efficiently?

Hinton & Nowlan’s Needle (1987)

• A-needle ⇒ Just one configuration of 20-bit binary strings.

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

Their choice of 20-bit was a good one!

Hence, their experiment was not a very difficult one.

How we evolve all-fitness-0 chromosomes?

• What about in the case of “All-one-problem?” (9 × 14 ⇒ 16 ⇒ 17 vs. 0 × 0 ⇒ 0 ⇒ 0)

Hinton & Nowlan’s brilliant trick

Evolution under Baldwin effect

— Lifetime learning of phenotype

A genotype:

(10901099011001001091)

Its phenotype:

(10101001011001001001) (10001011011001001011)

...

(13th International Scientific Conference – at Panevezys, Lithuania) 12

Their assumption

The closer the genotype to the needle,

the faster the learning of phenotype.

⇓

This makes the sharp-fitness-peak a more smooth one.

(13th International Scientific Conference – at Panevezys, Lithuania) 13

Baldwin effect looks great!

(13th International Scientific Conference – at Panevezys, Lithuania) 14

Are we really happy with this?

Why should we continue evolution when lifetime-learning already has found the needle?

⇓ (Turney 1987)

“Not from an engineering but a biological interest.”

(13th International Scientific Conference – at Panevezys, Lithuania) 15

Their GA implementation

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

under Roulette wheel selection; One-point crossover; Mutation; ......

(13th International Scientific Conference – at Panevezys, Lithuania) 16

Is a high fitness gene always a good gene?

Assume the needle is (1111111111111111111) without a loss of generality

(13th International Scientific Conference – at Panevezys, Lithuania) 17

Goodness depends on number of 9?

How many 9’s are optimal? or Is the number of 9’s decreasing?

Which will be a better one?

Assuming (11111111111111111111) is the needle

(99999999919999999999)

or

(11111111191111111111)

(13th International Scientific Conference – at Panevezys, Lithuania) 20

An extinction!

Only 4 successful genotypes are found in the 1st generation, at the luckiest case (in 100 runs).

(13th International Scientific Conference – at Panevezys, Lithuania) 21

Genotypes survived at the start

Let’s increase the population.

(13th International Scientific Conference – at Panevezys, Lithuania) 22

Why we failed?

No fitness correlation between parents & offspring

(13th International Scientific Conference – at Panevezys, Lithuania) 23

We need more 9’s to be successful, but...

(13th International Scientific Conference – at Panevezys, Lithuania) 24

A dilemma.

Assuming (11111111111111111111) is the needle,

e.g. (11919910999199119199) has no chance to reach the needle,

while e.g. (99999991999999999999) has 1000 chances.

⇓

What if e.g. (99999991999999999999) dominates the population?

(13th International Scientific Conference – at Panevezys, Lithuania) 25

Our evolution is not so successful under Baldwin effect!

(13th International Scientific Conference – at Panevezys, Lithuania) 26

What about Lamarckian Inheritance?

An inverse mapping from phenotype to genotype is necessary.

Turney (1996)

“We believe that computing this mapping is intractable,”

With Lamarckian Inheritance

Let’s re-map a few of successful 9’s in phenotype to its genotype.

Eventually, all 9’s disappeared to converge to the needle itself.

(13th International Scientific Conference – at Panevezys, Lithuania) 28

Why giraffe has a long neck?

(13th International Scientific Conference – at Panevezys, Lithuania) 29

Still we are not so happy.

The number of total points searched (not the number of individuals,) is almost similar as a random search.

(13th International Scientific Conference – at Panevezys, Lithuania) 30

“Alas! Where is the needle longer than 25-bit?”

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.

(13th International Scientific Conference – at Panevezys, Lithuania) 32

Grover’s quantum search (1997) A speed up from O(N) to O(\sqrt{N}).

(13th International Scientific Conference – at Panevezys, Lithuania) 33

A strange path of quantum computation

When a particle goes from A to B, it takes all possible paths at the same time.

Concluding Remarks

• Searching for a needle in a hay is open & important issue.

• We need real efficient approaches.

• Not yet so far a real efficient one.

• We have to be careful about an effect of like-to-hear-what-we-would-like-to-hear.

Success at a small scale is not a royal road to a real success.