\documentclass[10pt]{article}
\usepackage{graphicx}

\textheight 225mm
%\topmargin 5mm
\textwidth 175mm
\oddsidemargin -7mm

\newtheorem{algorithm}{Algorithm}

\title{{\bf {\large (Extended Abstract)} \\
Hinton \& Nowlan's computational Baldwin effect revisit. \\
Are we happy with it?}}

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

\date{}

\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}

\begin{abstract}
\noindent
In their seminal paper published in 1987, Hinton \& Nowlan showed us 
an elegant experiment which might be called  ``\it 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 {\it 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 {\it 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. 
\end{abstract}

\section{Introduction}
Searching for {\it 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 {\it 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 {\it a-needle-in-a-hay-stack}
problem and we propose a method to solve it.''
Let's name a few.  \\


\noindent
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 \cite{cram}.\\

\noindent
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 \cite{someone}. We postulate this is due to those attack is like
a needle in a haystack \cite{imad}.

\noindent
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

\section{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



\noindent
Mills \& Watson (2005) wrote
"In typical runs of the simulation after very few generations, the all 1�fs 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�fs in the genotype increases slowly towards the fittest genotype." => ???

\noindent
"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�fs and 1 otherwise." => ???

\noindent
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."

\subsubsection*{Flexible genes and lifetime learning}
\noindent
A key to understand the intention of their experiment is to make sure that 
an example of genotype is 
\begin{displaymath}
(1 1 0 1 0 9 0 9 1 0 9),
\end{displaymath}
and its possible {\it phenotype}
\begin{displaymath}
(1 1 0 1 0 1 0 1 1 0 0),
\end{displaymath}
or 
\begin{displaymath}
(1 1 0 1 0 0 0 1 1 0 1).
\end{displaymath}
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�fs model)."


\subsubsection*{Turney's doubts on computational Baldwin effect}
{\it ``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
{\it ``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.''}
\noindent
One of our proposal here is a model to which lamarkism is possible to be implement.



As Turney (1998) pointed out 
{\it ``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.




\subsubsection*[Effect of smoothing the fitness landscape]
{\it ``This makes it easier for evolution to climb to peaks in the landscape.''} (Turney 1998).

\subsubsection*{How does evolution look like in Hinton \& Nowlan's model}

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

\begin{quotation}
"In typical runs of the simulation after very few generations, the all 1�fs 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."
\end{quotation}

\subsubsection*{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 mutation-like 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�fs 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
non-plastic 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.

\subsubsection*{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)



\subsubsection*{Reference}
\begin{description}
\item
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.

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

\item
M. Sabhnani, and G. Serpen (2003) �gApplication of
Machine Learning Algorithms to KDD Intrusion Detection
Dataset within Misuse Detection Context.�h
Proceedings of the International Conference on Machine
Learning: Models, Technologies and Applications,
pp. 209--215.

\item
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.

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

\item 
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.


\item
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.

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


\end{description}
\end{document}





