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

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

\newtheorem{algorithm}{Algorithm}

\title{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 the Baldwin effect in computers} which searches for only one object located in a huge search space. The object was called {\it a-needle-in-a-haystack}. Hinton \& Nowlan  evolved a population of candidates of the solution in the same way as a standard evolutionary search. What made it unique was an exploitation of individual's {\it lifetime-learning}. Since then we have had a fair amount of proposals of how we reach the needle more efficiently. The issue, however, is still open to debate. We try to repeat their experiment and take a consideration on it. 
\end{abstract}

\section{Introduction}
Let's start with a thought experiment. {\it ``(i) Suppose we have $N$ sea-shells on the table and a marble is hidden under one of those $N$ shells. Then, how much query on average will be necessary to locate where the marble is? (ii) If no such mable is hidden at all, how many queries are needed to know that?''} Or, we might imagine that we would try to break a $N$-digit PIN code (Personal Identification Number) by a {\it random-trial-and-error} or {\it exhaustive-one-by-one} search. Then what if $N$ is very huge?


\bigskip \noindent
{\bf Why we search for a needle?  --- Computational analogue.} The problem of looking for only one object hidden in a huge search space is sometimes called {\it a-needle-in-a-haystack} problem. It has long attracted and is still attracting many computer researchers. Let's name a few.\\

\noindent
Crammer \& Chechik (2004) defined the problem as, {\it ``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 ...''} Joshi et al.~(2001) pointed out yet another but a similar situation, writing, {\it ``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 predicting everything to be of non-target-class can also achieve very high accuracy level of 99.5\%.''} The technique proposed by Crammer \& Chechik to solve this problem exploits two {\it phases} called {\it positive} \& {\it negative}. Hence they call it {\it PN-rule}. Weiss (2004) summarized this method as, {\it ``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.''} Weiss also discusses about, {\it ``the role that rare classes and rare cases play in data mining,"} citing an interesting example of a {\it ``machine learning technique 
to detect oil spills from satellite images (Kubat et al.~1998).''}\\

\noindent
Sabhnani et al.~(2003) applied nine different machine learning techniques to the KDD-cup-1999 dataset (Stolfo et al.~1999) to know how these techniques detect network intrusions. In the dataset, data for four categories of intrusions are given, together with data for normal transactions. It was shown that the two out of four categories were all immune to all the nine methods more or less, while the other two were easy to be detected. We hypothesized that this is due to these two categories of attacks are like needles in a haystack of a normal and other categories of attacks (Imada, 2006).\\

\noindent
Among others, besides a specific data in a huge database, the most popular issue on this topic these days is probably a searching for needles in a huge hay of world-wide-web resources, and designing such search-engines. See, for example, (Makris et al.~2006). In software engineering community, this issue is also explored. See, for example, (Whitaker et al.~2004).


\bigskip \noindent
{\bf Hinnton \& Nowlan's model -- Computational Baldwin Effect.} In their seminal paper, Hinton \& Nowlan (1987) proposed a needle defining just as a unique configuration of 20-bit binary string, with all other configurations being a haystack. Then they tried an evolutionary search starting with a population of random candidates of the needle. A smart trick in their evolution is an inclusion of {\it flexible genes} in its {\it genotype}. Each of these flexible genes is replaced with either 1 or 0 in its {\it phenotype}. Then each of these phenotypes -- again a binary 20-bit stirng -- is checked if it matches the needle. Hence, this is calld a {\it lifetime-learning}. Each genotype can try its learning during their lifetime. Note that successful flexible genes in phenotype are not re-mapped into phenotype. This is a computational analogue of biological model of evolution called the {\it Baldwin effect} (Baldwin, 1896). Although we have had lots of reports concerning this apploach, such as (Mills \& Watson, 2006), the topic still includes open issues.\\

\noindent
Note that if we apply a standard genetic algorithm starting with a population of chromosomes with their genes being either 0 or 1 at random, then the fitness of each individual is always zero unless the individual is ultra lucky to be coincidentally identical to the needle. Hence the fitness landscape is everywhere flat land of altitude zero except for the only one point. See Figure~1. How could we hillclimb if not a hill to climb! Impossible to evolve.\\

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm,height=0.75cm]{a-needle-0.eps}
 \caption{A fictitious sketch of fitness landscape of {\it a needle in a haystack}.
The haystack here is drawn as a 2-dimensional flat plane of fitness zero.}
\end{center}
\end{figure}

\noindent
However, their choice of 20-bit is a good one. We tried a random search with a similar condition of Hinton \& Nowlan's experiment. The number of trials needed until the needle was found is plotted as a function of number of bits. Although the number explodes exponentially, as shown in Figure~2, 20-bits is just before the explosion. But in fact we never observed a needle longer than, say, 25 bits was reachd in a reasonable time.

\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=6cm]{random-search-needle-2-mono.eps}
\caption{Assuming only one configulation of  $n$-bit binary strings is a needle, the number of random trials needed until the needle was found is plotted against $n$. result is an average during 100 runs.}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=9cm,height=6cm]{kauno-linear-2-mono.eps}
\end{center}
\caption{Number of individuals necessary for the needle to be reached for the first time vs. the number of total search points. A result of random walks (blank circles) and search by 1000 learnings during individual's lifetime (filled circles).  The data are averaged after 100 runs. Complexity is both linear, but what a dramatic difference!}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=4cm]{lifetime-success-001-mono.eps}
\includegraphics[width=12cm,height=4cm]{lifetime-success-002-mono.eps}
\caption{Examples of Histogram of two genes of how many successes out of 1000 learnings of 1024 phenotypes. Genotype which reached the needle with 2 steps (top) and the other reached with 985 steps (bottom).}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{lamarck-avg-fit-2-mono.eps}
\caption{An evolution of genotypes including flexible genes by Lamarkian inheritance.}
\end{center}
\end{figure}


\section{Experiment, Results, and Discussion}
\noindent
Following Hinton \& Nowlan's experiment and a more clear specification of the experimental condition suggested by Mills \& Watson (2005), we tried to repeat their experiment. We create a population of 1024 chromosomes of 20-bit whose genes are either 0, 1, or 9. Genes are determined at random with a probability of 0.25 for 0's and 1's and 0.5 for 9's. A needle here is the 20-bit strigng of all 1, without a loss of generality. Each chromosome is given a chance of 1000 trials each time with its 9 being randomly replaced either with  0 or 1, and check if the result of replacement matches the needle or not, if it matches the needle at $n$-th trial, the fitness is given as $(1000 - n)$. Then we evolve this population from one generation to the next by {\it fitness-proportionate-selection}, {\it one-point-crossover} and {\it mutation} with the probability of 1/20.


\bigskip \noindent
{\bf Can we observe such an elegant result?} In Figure~3 we show the number of individuals needed to find the needle in two cases: (i) by simple random search (the same data as in Figure~2) and (ii) by search with lifetime learning. The plots here are against total search points $N$. Although the number is $O(N)$ in both cases, what a tremendously dramatic enhancement in efficiency it looks like!


\bigskip \noindent
{\bf Why should we continue when the lifetime learning already find the needle?} This is what we wondered when we read the original Hinton \& Nowlan's paper. A possible answer was given by Mills \& Watson (2005) in which they argued, {\it ``This model is not intended to show any engineering advantage but a biological interest.} Then they went on, {\it "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 recognize their own success (as is implicit in Hinton \& Nolan's model.)"}
We were not fully satisfied with this answer but let's acept it here. Then the next question arises.


\bigskip \noindent
{\bf The higher the fitness of a genotype, the better it performs?} Hinton \& Nowlan's assumption is that the closer the {\it genotype} to the needle, the faster the learning of {\it phenotype}, which makes the needle-like-peak smoother. To study this, we compared their lifetime results of two genotypes one reached the needle quickly (just 2 steps) and the other reached the needle but almost at the last chance (985 steps). We counted how many successes out of 1000 learnings of 1024 phenotypes. The histograms are shown in Figure~4. Although genotypes which reached the needle almost at the last chance sometimes reached the needle quickly, the higher fitness genotype by and large seems to perform better.


\bigskip \noindent
{\bf What is a fate of those flexible genes?} Then questions are, ``How many flexible genes are optimal?'' or ``Is the number of flexible genes decreasing as evolution proceeds?'' Let's see what happened our evolution of these genotypes. We observed 100 runs with 100 different random nubmer seeds, and what we saw in the 1st generation were only 4 successful genotypes at the luckiest case. The other 99 runs have only two, one or even zero sucessful genotypes. And in this luckiest case, the number of successful genes increased in an early stage of evolution to 300 -- 400, but all of a sudden at some point of evolution, an ectinction occured. That is, the nubmer of survival genotypes fell down to one or zero. Not possible for reproduction any more. (Figure to show this phenomenon is not in this paper.) Then, why don't we try another similar biological evolution model such as {\it Lamarckian inheritance} rather than sticking to the Baldwin Effect.


\bigskip \noindent
{\bf Is the Lamarckian inheritance computationally plausible?} Turney (1996) wrote, {\it ``Lamarckism requires an inverse mapping from phenotype and environment to genotype. This inverse mapping is biologically implausible.''} And further assumed by describing, {\it ``Perhaps Lamarckian evolution is superior to the Baldwin effect, when we are attempting to solve problems by evolutionary computation.''} and the went on to write {\it ``... (but) we believe that computing this mapping is intractable in general,''}\\

\noindent
Why not? Let's try! This reverse mapping is really easy in Hinton \& Nowlan's model. All we need is remap some of the successful 0's and 1's in the phenotype to the corresponding flexible genes in the genotype with a certain probability. Look at the typical sucess in its evolution shown in Figure~5. Though we still don't know this is {\it biologically} meaningful, this hypothesis once tried to be used to explain, ''Why giraffe has a long neck?''


\bigskip \noindent
{\bf Are we really happy with these models to find needle?} As already shown in Figure~2, exploiting the Baldwin effect seemed to tremendously enhance the efficiency of searching for the needle. But this is only under a comparison with the number of {\it individuals who tried to reach the needle}. If we comared with the number of {\it points which are visited}, we have almost similar result in those models. (Figure to show this is not included here.) Then how can we find a needle longer than, say, 25 bits? \\

\noindent
In addition, we have to admit that even if we found a really efficient needle-detector, the steps we need would be still $O(N)$ like in Figure~3.


\section{To Conclude}
We have tried a bird's eye view on the topic on {\it a-needle-in-a-haystack problem}, or equivalently, a {\it computational model of the Baldwin effect}. The topic was initially proposed by Hinton \& Nowlan two decades ago, but still this is a very important problem. Though we have had lots of proposals to approach to this problem, essentially we still have not find a truely efficient way of finding a needle in a really huge hay. Most techniques reported are still not sufficient when they are applied to a more scaled-up circumstance than when it was designed. A success in a small scale experiment is not necessarily a {\it royal road} to a success in a large scale situation in the real world. \\

\noindent
Let me take an example. We now assume a robot in a $ N \times N$ grid. A needle is hidden somewhere in the grid. Then the task of the robot is to look for the needle starting with somewhere in the grid. The robot has no idea of where is the needle. This is a two-dimensional version of a-needle-in-a-haystack problem. If $N$ is small enough, the robot can eventually reach the needle even with random walks. And a learning, whateve it might be, can reduce the number of steps to the needle. We have so many successful reports of experiments of robot navigation in a much more complicated simulated world than the above mentioned simple grid world. The fact is, however, if the grid size explodes then we actually don't know how we make robot navigate as we like, even in a very simple world without no constraint such as corridors, walls or obstacles. \\

\noindent
Yet another point we wanted to emphasize in this paper is that we have to avoid an effect of {\it like-to-hear-what-we-want-to-hear.} We had an interesting discussion between two papers: Yu \& Miller's (2002) {\it ``Finding needles in haystacks is not hard with neutrality''} vs. Collins' (2005) {\it ``Finding needles in haystacks is harder with neutrality.''}\\

\noindent
Anyway, as already mentioned, all approaches described in this paper require $O(N)$ steps to the needle. Let me conclude this paper with the claim of a real speed up from $O(N)$ to $O(\sqrt{N})$ by Grover (1997) by his quantum search, which was already mathematically proved. The problem in his context is to find the needle from no-structured huge database. That is, {\it ``Find $x$ such that $P(x) = 1$ when only $x$ from $N$ data fulfills $P(x)=1$ while all others do not.''} This is owing to a strange path of quantum computation. Namely, when a particle goes from A to B, it takes all possible paths at the same time. In reality, however, no one so far has seen a practical implementation of quantum computation. \\

\noindent
We hope this article would be a good {\it prelude} to the re-opening this issue.

\section*{Acknowledgment}
This topic was motivated by a comment from the floor when I talked in a seminar held in Vilnius in 2003 about evolutionary computations in general which included the topic of the computational Baldwin Effect. The comment insisted, {\it ``Such a search will never be plausible,''} mentioning the Baldwin Effect. Though still I could say, ``But it smoothes the fitness landscape, anyway,'' what he  pointed out was correct in a sence written in this article. I now thank you for his comment.

\section*{Reference}
\begin{description}
\setlength{\itemsep}{0pt}
\item 
Baldwin, J.~M.~(1896) 
``A New Factor in Evolution.''
American Naturalist, Vol. 30, pp. 441-457, 536-554.

\item
Collins, M.~(2005)
``Finding Needles in Haystacks is Harder with Neutrality.''
In Proceedings of Genetic and Evolutionary Computation Conference, pp. 1613--1618.

\item
Crammer, K., and G.~Chechik (2004)
``A Needle in a Haystack: Local One-Class Optimization.''
In Proceedings of International Conference on Machine Learning.
http://citeseer.ist.psu.edu/crammer04needle.html

\item
Grover, L.~(1997)
``Quantum Mechanics Helps in Searching for a Needle in a Haystack.'' 
Physical Review Letter, Vol. 79, pp. 325--328.

\item
Hinton, G.~E., and S.~J.~Nowlan (1987)
``How Learning can Guide Evolution: Adaptive Individuals in Evolving Populations.''
Models and Algorithms, Addison-Wesley Longman, pp. 447--454.

\item
Imada, A. (2006)
``How Many Parachutists will be Needed to Find a Needle in a Pastoral?''
In Proceedings of the International Conference on Neural Networks and Artificial Intelligence, 
pp. 53--60.

\item
Joshi, M.~V., R.~C.~Agarwal, and V.~Kumar (2001)
``Mining Needles in a Haystack: Classifying Rare Classes via Two-Phase Rule Induction.''
ACM SIGMOD (Special Interest Group on Management of Data) Record, Vol. 30 (2), pp. 91--102.

\item
Kubat, M., R.~C.~Holte, and S.~Matwin (1998)
``Machine Learning for the Detection of Oil Spills in Satellite Radar Images.''
Journal of Machine Learning Vol. 30, pp. 195--215.

\item
Makris, C., Y.~Panagis, E.~Sakkopoulos, and A.~K.~Tsakalidis (2006)
``Efficient and Adaptive Discovery Techniques of Web Services Handling Large Data Sets.'' 
Journal of Systems and Software, Vol. 79(4), pp. 480--495. 

\item 
Mills, R, and Watson R.~A.~(2005)
``Genetic Assimilation and Canalization in the Baldwin Effect.''
In Proceedings of the European Conference on Artificial Intelligence, pp. 353-362.

\item
Mills, R., and R.~A.~Watson (2006)
``On Crossing Fitness Valleys with the Baldwin Effect.''
In Proceedings of Artificial Life X, pp. 493--499.

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

\item
Stolfo, S.~J., F.~Wei, W.~Lee, A.~Prodromidis, and P.~K.~Chan (1999) 
``KDD Cup Knowledge Discovery and Data Mining Competition.''
http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

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

\item
Weiss, G.~M.~(2004)
``Mining with Rarity: A Unifying Framework.''
ACM SIGKDD (Special Interest Group on Knowledge Discovery and Data Mining) Explorations,
Vol. 6(1), pp. 7--19.

\item
Whitaker, A., R.~S.~Cox, and S.~D.~Gribble (2004)
"Configuration Debugging as Search: Finding the Needle in the Haystack."
Journal of Operating Systems Design and Implementation 2004, pp. 77--90.

\item
Yu, T., and J.~Miller (2002)
``Finding Needles in Haystacks is Not Hard with Neutrality.''
In Proceedings of EuroGP 2002, Lecture Notes in Computer Science Vol. 2278, Springer, pp. 13--25.

\end{description}
\end{document}

