(Extended Abstract)

Hinton & Nowlan’s computational Baldwin effect revisit. Are we happy with it?

Brest State Technical University Moskowskaja 267, Brest 224017 Republic of Belarus akira@bsty.by

Abstract

In their seminal paper published in 1987, Hinton & Nowlan showed us an elegant experiment which might be called “an evolution with Baldwin effect in computers.” The purpose was to show a new method to search for a unique object located in a huge search space, and thus, it is called a-needle-in-a-hay-stack problem. The method is by evolving a population of candidates of the solution like a usual evolutionary search, but what was proposed was to exploiting individuals lifetime-learning. Hence this is the first suggesiton of a computational Baldwin Effect. We have fair amount of application proposal of this technicque even these days. The topic still includes open issues and some of them are explored here.

1 Introduction

Searching for a-needle-in-a-haystack problem has long attracted and still is attracting many of us in computer science/technology communities. Since Hinton & Nowlan (1987) show us an elegant way using the concept of the Baldwin Effect borrowing a metaphore form a biological evolution, we have had so many reports which claime, “This and that problem we are facing in real world is searching for a-needle-in-a-hay-stack problem and we propose a method to solve it.” Let’s name a few.

In data-mining, The problem of finding a small and coherent subset of points in a given data which sometimes referred to as one-class or set covering, requires to find a small-radius ball that covers as many data points as possible [?].

Sabhnani et al. applied nine different machine learning techniques to the KDDcup-99 data to know how these techniques detect intrusions. In the dataset, data for four types of intrusions are given as well as the data for normal transactions.

network intrusion d. =¿ immune to all the ten methods while others are easy to be detect [?]. We postulate this is due to those attack is like a needle in a haystack [?]. Joshi, The traditional evaluation metric of accuracy is not adequate when the target-class is rare. If the class is very rare, say 0.5 %, then precdicting everything to be of non-target-class can also achieve very high accuracy level of 99.5

which Weis simply summarise as “this approach identifies regions likely to contain needles in the first phase and then learns to discard the strands of hay within these regions in the second phase.

data-mining web-search satellite software-engineering

2 Hinnton & Nowlan’s Model

Hinton & and Nowlan’s model (1987) has attracted and is still attracting ...

To make us easy to imagin what, just image 20 bit binary PIN instead of usual decimal PIN.

As Watson & Pollack wrote “”Hinton and Nowlan choose the population size, number of lifetime trials, and number of variables in the problem carefully so as to make it most unlikely that genetic variation alone will find the solution but very likely that lifetime variation will.””

Anyway, try to find one unique hidden, say, 30-bit, binary string in a reasonable time with our most recent PC. Mills & Watson (2005) ”Here we present a simplified model that is used to reveal the essential mechanisms and

highlight several conceptual issues that have not been clearly defined in prior literature.”

yet not very clear defiend rather still open Mills & Watson (2005) wrote ”In typical runs of the simulation after very few generations, the all 1 ’ s phenotype is found by lifetime learning, and the average num-ber of 1’s in the genotype increases rapidly. In subsequent generations the average number of 1 ’ s in the genotype increases slowly towards the fittest genotype.” =¿ ??? ”The fitness of each individual is the average fitness of the phenotypes it produces during its lifetime and the fitness of each phenotype is Fmax if it is all 1 ’ s and 1 otherwise.” =¿ ??? Mills & Watson (2006) wrote ”We find the extent of modifications to this landscape provided by plasticity, by calculating the expected fitness of individuals as a function of their location with respect to the two peaks.”

Flexible genes and lifetime learning

A key to understand the intention of their experiment is to make sure that an example of genotype is

(11010909109),

and its possible phenotype

(11010101100),

or

(11010001101).

etc.

Yet another key is

to paraphrase Mills & Watson (2005) ”To remove the assumption of learning phenotypes, we evaluate fitness as the mean fitness of the lifetime phenotypes, rather than the number of trials remaining after the phenotypic solution is first found. This means that the organisms do not have to recognise their own success (as is implicit in H&N ’ s model).”

Turney’s doubts on computational Baldwin effect

“The genotype is ... In a living organism, this is typically the organism’s DNA. In evolutionary computation, it is typically a string of bits. The phenotype is the set of observable characteristics of an organism, as determined by the organism’s genotype and environment.” Further “The distinction between genotype and phenotype is clear in biological evolution, but the distinction does not exist in many of the simpler examples of evolutionary computation.” One of our proposal here is a model to which lamarkism is possible to be implement.

As Turney (1998) pointed out “Learning has benefits but it also has costs. The Baldwin effect is concerned with the costs and benefits of lifetime learning in an evolving population.”

“Learning can accelerate evolution under certain circumstances, but it can also slow evolution under other circumstances.” (Turney)

It’s easy to see this with a simple experiment.

[

Effect of smoothing the fitness landscape] “This makes it easier for evolution to climb to peaks in the landscape.” (Turney 1998).

How does evolution look like in Hinton & Nowlan’s model

Mills & Watoson revisted the experiment with the same condition as described earlier and concluded.

”In typical runs of the simulation after very few generations, the all 1’s phenotype is found by lifetime learning, and the average number of 1’s in the genotype increases rapidly. In subsequent generations the average number of 1’s in the genotype increases slowly towards the fittest genotype. ... reduction in lifetime plasticity, is facilitated by means of reduction in numbers of ?’s – the allele representing that plasticity.”

Yet another closely related model

”In our constant plasticity model there is no designation of particular traits that are phenotypically plastic, i.e. we do not use ? alleles. Instead lifetime plasticity varies any trait with equal probability, using non-heritable mutationlike variations applied to the genotypic trait specifications in each lifetime trial. This models a constant plasticity level which separates the effects of lifetime plasticity from canalisation.”

”Specifically, this new model does not use canalisation, individuals do not have to recognise their own success (i.e. cognitive learning is not required, only some form of phenotypic plasticity),”

”To remove the assumption of learning phenotypes, we evaluate fitness as the mean fitness of the lifetime phenotypes, rather than the number of trials remaining after the phenotypic solution is first found. This means that the organisms do not have to recognise their own success (as is implicit in H&N ’ s model).”

Well, what we are wandreing if we apply this to the very original Hinton & Nowlan’s model, most likely scenario is fitness of the lifetime phenotypes are all zero, and as such mean fitness of them.

Mills & Watson argued: ”1 To consider performance from an engineering perspective, we find the learning population takes approx. 13.3*200*1024 = 2,723,840 evaluations, which is significantly more than for the nonplastic case (approx. 2382*200 = 476,400 evaluations). However, this model is not intended to show any engineering advantage; from a biological viewpoint, generation time is approximately fixed. Thus the important comparison to make is upon the number of generations required.”

Then why don’t we expect more to Lamarkian rather than Baldwin.

Lamarckian Inheritance in Computation

“Lamarckism requires an inverse mapping from phenotype and environment to genotype. This inverse mapping is biologically implausible.” (Turney)

”The hypothesis appears very similar to Lamarck’s disproved beliefs that an acquired trait is directly inherited by offspring.” (Mills & Watson 2005)

Reference

Hinton, G. E., amd Nowlan S. J. (1987) “How learning can guide evolution, Adaptive individuals in evolving populations: models and algorithms, Addison-Wesley Longman. pp. 447–454.

K. Crammer, and G. Chechik (2004) ”A Needle in a Haystack: Local One-Class Optimization.”

M. Sabhnani, and G. Serpen (2003) “ Application of Machine Learning Algorithms to KDD Intrusion Detection Dataset within Misuse Detection Context.”Proceedings of the International Conference on Machine Learning: Models, Technologies and Applications, pp. 209–215.

A. Imada (2006) “How Many Parachutists will be Needed to Find a Needle in a Pastoral?” Proceedings of the International Conference on Neural Networks and Artificial Intelligence, pp.53–60.

Baldwin, J. M. (1896) ”A New Factor In Evolution.” American Naturalist Vol. 30, pp. 441-457, 536-554.

Mills, R, and Watson R. A. (2005) ”Genetic assimilation and canalisation in the Baldwin effect.” In Proceedings of the European Conference on Artificial Intelligence, pp. 353-362, Springer-Verlag.

Mills R., and R. A. Watson R. A. (2006) ”On Crossing fitness Valleys with the Baldwin Effect.” In Proceedings of Artificial Life X, pp. 493–499.

Turney P, (1996) ”Myths and Legends of the Baldwin Effect” In Proceedings of the 13th International Conference on Machine Learning, pp. 135–142.