\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\usepackage{graphicx}
\usepackage{color}

\textheight 260mm
\topmargin 5mm
\textwidth 180mm
\oddsidemargin -7mm

\newtheorem{algorithm}{Algorithm}

\pagestyle{myheadings}
\markright{(13th International Scientific Conference  -- at Panevezys, Lithuania)}
\thispagestyle{empty}

\begin{document}
\begin{huge}


%% The topic is hinton & nowlan's computational baldwin effect which we doubt more or less
%% as we will see it later more in detail.

%% I'm not an evangelist of this topic. Rather opposite.

\clearpage  % (title) =========================================
\begin{center}
\color{blue}
{\bf Hinton \& Nowlan's \\ Computational Baldwin Effect Revisit: \\ 
\bigskip
Are we happy with it?}

\color{black}
\hspace*{1in}\\ 
\begin{Large}
Akira Imada  \\
\bigskip
Brest State Technical University \\ 
Belarus
\end{Large}
\end{center}



%% a metephor to express an extrimly diificult search
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Looking for ``a-needle-in-a-haystack''}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=10cm]{hay-2.eps}
\end{center}
\end{figure}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf To break an unknown 4 digit decimal PIN} \\

\hspace*{1in}\\
\color{black}
{\LARGE
Only one out of 10,000 is correct (a-needle-in-a-haystack)\\
$\Downarrow$ \\
How many random/exhaustive trials \\
will be necessary to break? \\
$\Downarrow$ \\
An average of 5,000 trials.
}
\end{center}


%% as far as we know this simple looking task is still an open issue 
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A needle hidden in a huge grid world.}\\
\bigskip
\color{black}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=4cm,height=4cm]{grid.eps}
\end{center}
\end{figure}
{\LARGE
Can a navigation robot reach it? \\
$\Downarrow$ \\
A 2-D version of a-needle-in-a-haystack.
}
\end{center}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf What is a-needle-in-a-haystack} \\

\color{black}
\bigskip
{\LARGE
%% Assume we have a needle detector $F(x)$\\
Assume we have an {\it ORACLE} for  needle $F(x)$\\
\bigskip
\color{red}
``Find $x$ 
\color{black}
(among $N$ items)
\color{red} 
such that $F(x) = 1$'' \\
\color{black}
\bigskip
when \\
only $x$ 
%% from $N$ data 
fulfills $F(x)=1$ while $F(x)=0$ for all others.} \\
\bigskip
{\Large (We might call $F(x)$ a fitness function of this problem.)}


\end{center}


\clearpage  % =========================================
\begin{center}   
\hspace*{1in}\\
\hspace*{1in}\\

\color{red} $O(N)$  \color{black} steps are necessary!
\end{center}


\clearpage  % =========================================
\hspace*{1in}\\
\hspace*{1in}\\

\begin{center} \color{blue}
{\bf Can we look for a needle more efficiently?} \\
\end{center}


%% they shoed us an ELEGANT experiment
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's Needle (1987)}\\
\end{center}

%% approximately one million points
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm,height=1.5cm]{a-needle-0.eps}
\end{center}
\end{figure}

\color{black}
\noindent
{\LARGE
$\bullet$ A-needle $\Rightarrow$ Just one configuration of 20-bit binary strings.
$\bullet$ Haystack $\Rightarrow$ $2^{20}-1$ search points.}



%% We tried a random search with a same condition as Hinton & Nowlan's
%% I have never observed the needle more than 26bits by ANY search

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their choice of 20-bit was a good one!}\\
\end{center}
\begin{LARGE}
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{random-search-needle-2.eps}
\end{center}
\end{figure}
\hspace*{.5in}
Hence, their experiment was not a very difficult one.
\end{LARGE}

%% if we are not ultralucky
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf How we evolve all-fitness-0 chromosomes?}\\

\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=5cm]{ga-baldwin.eps}
\end{center}
\end{figure}

\color{black}
{\Large $\bullet$ What about in the case of ``All-one-problem?''\\
(9 $\times$ 14 $\Rightarrow$ 16 $\Rightarrow$ 17
vs.
0 $\times$ 0 $\Rightarrow$ 0 $\Rightarrow$ 0)}
\end{center}

% their smart trick is an inclusion of flexible genes which is expressed with red 9 here
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's brilliant trick}\\
\end{center}
\bigskip
\color{black}
{\LARGE Evolution under Baldwin effect \\
\hspace*{2.5in} --- Lifetime learning of phenotype} \\
{\Large
\color{black}
\hspace*{1in}A genotype:
\begin{center}
(10\color{red}9\color{black}010\color{red}99\color{black}0110010010\color{red}9\color{black}1)\\
\end{center}
\hspace*{.85in} Its phenotype:
\begin{center}
(10\color{red}1\color{black}010\color{red}01\color{black}0110010010\color{red}0\color{black}1)\\
(10\color{red}0\color{black}010\color{red}11\color{black}0110010010\color{red}1\color{black}1)\\
...
\end{center}
}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Their assumption}\\

\bigskip
{\LARGE
\color{black}
The closer the {\it genotype} to the needle,\hfill\\
\hfill the faster the learning of {\it phenotype.} \\
$\Downarrow$ \\
This makes the sharp-fitness-peak a more smooth one.}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=4cm]{make-it-smooth.eps}
\end{center}
\end{figure}
\end{center}

%% random search is the same as before but this time against number of search points instead of 
%% number of bits
%% we may see a tremendous improvement
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect looks great!}\\
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=8.5cm]{kauno-linear-2.eps}
\end{center}
\end{figure}

%% are we REALLY happy ...
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Are we really happy with this?}\\ %% Baldwin effect?}\\

\bigskip
\color{black}
{\LARGE
Why should we continue evolution\\
when lifetime-learning already has found the needle? \\

$\Downarrow$ \\

(Turney 1987)\\
{\it ``Not from an engineering  but a biological interest.''}
}
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their GA implementation}\\
\color{black}
{\LARGE
\bigskip
\color{red} 1024 \color{black} 
genotypes with 
\color{red} 25\% \color{black} 
flexible genes, \\
each allowed 
\color{red} 1000 \color{black} 
lifetime learnings; \\
\bigskip
under \\
\bigskip
Roulette wheel selection; \\
One-point crossover;\\
Mutation; \\
......} \\
\end{center}




%% we tried histgrams ...
%% by and large
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Is a high fitness gene always a good gene?}\\
\bigskip
\color{black}
{\Large Assume the needle is (1111111111111111111) without a loss of generality}
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=7cm]{lifetime-success-001.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Goodness depends on number of 9?}
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=7cm]{lifetime-success-002.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\hspace*{1in}\\
\begin{center}   
\color{blue}
{\bf How many 9's are optimal?}\\
\color{black}
or \\
\color{blue}
{\bf Is the number of 9's decreasing?}\\
\end{center}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Which will be a better one?}\\
\hspace*{1in}\\
\color{black}
{\LARGE
Assuming $(11111111111111111111)$ is the needle\\
\hspace*{1in}\\
\hspace*{1in}\\
$(999999999
\color{red}1\color{black}
9999999999)$ \\
or \\
$(111111111
\color{red}9\color{black}
1111111111)$}
\end{center}

%% we experiment with 200 different random seeds
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf An extinction!}\\
\bigskip
\color{black}
{\Large 
Only 4 successful genotypes are found in the 1st generation,\\ 
at the luckiest case (in 100 runs).}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=5cm]{baldwin-survived-2.eps}
\end{center}
\end{figure}
\color{black}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Genotypes survived at the start}\\
\bigskip
\color{black}
{\LARGE Let's increase the population.}
\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=7cm]{genotype-survived.eps}
\end{center}
\end{figure}
\end{center}



\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Why we failed?}\\
\bigskip
\color{black}
{\LARGE No fitness correlation between parents \& offspring}
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=6cm]{fit-parents-child.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf We need more 9's to be successful, but...}\\
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=7cm]{how-efficient-baldwin-2-1.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A dilemma.}\\
\hspace*{1in}\\
\color{black}
{\LARGE Assuming} {\Large $(11111111111111111111)$} {\LARGE is the needle,}\\
\bigskip
{\LARGE e.g.} {\Large $(1191991\color{red}0\color{black}999199119199)$}
{\LARGE has no chance to reach the needle,\\
while e.g.} {\Large $(9999999\color{red}1\color{black}999999999999)$} 
{\LARGE has 1000 chances.} \\
$\Downarrow$ \\
{\LARGE What if e.g.} {\Large $(9999999\color{red}1\color{black}999999999999)$} 
{\LARGE dominates the population?}
\end{center}

\clearpage   % =========================================
\hspace*{1in}\\
\begin{center} \color{blue}
{\bf Our evolution is not so successful \\under Baldwin effect!}\\
\end{center}


%% this is believed to be intractable
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf What about Lamarckian Inheritance?}\\

\color{black}
\bigskip
{\LARGE
An inverse mapping from phenotype to genotype  is necessary.\\
\hspace*{1in}\\
Turney (1996)\\
{\it ``We believe that computing this mapping is intractable,''}
}
\end{center}




%% I don't know this computational lamarkian model is meaningful in a biological sence...
%% but this hypothesis used to try to explain why girrafe has a long neck
%% nowadays now one believe this happen in nature
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf With Lamarckian Inheritance}\\

\bigskip
{\Large
\color{black}
Let's re-map a few of successful 9's in phenotype to its genotype. \\
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=5cm]{lamarck-avg-fit-2.eps}
\end{center}
\end{figure}
Eventually, all 9's disappeared to converge to the needle itself.
}
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Why giraffe has a long neck?}\\
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=5cm,height=5cm]{giraffe.eps}
\end{center}
\end{figure}


%% Inspite of a superficial improvement ... 
%% all of these 2 cases ...
\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Still we are not so happy.}\\
\bigskip
\color{black}
{\Large 
The number of total points searched (not the number of individuals,) \\
 is almost similar as a random search.}\\

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=4.5cm]{kauno-exponential-2.eps}
\includegraphics[width=8cm,height=4.5cm]{baldwin-1.eps}
\end{center}
\end{figure}

\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}  
\hspace*{1in}\\
\hspace*{1in}\\
``Alas! Where is the needle longer than 25-bit?''
\end{center}




%% ... are typical nowaday's needle-in-a-haystack
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Computational analogue of a-needle-in-a-haystack}\\
\bigskip
{\LARGE
\color{red}
A specific rare cases 
\color{black}
in a  huge database;\\
\color{red}
A real necessary information 
\color{black}
from world-wide-web; \\
\color{red}
Oil spills in the ocean  
\color{black}
from satellite image; \\
\color{red}
A cause of failures  
\color{black}
in diagnosing a huge code; \\   %% from software-engineering
\color{red}
A collision 
\color{black}
of a hash function; \\  
%% cryptography \\
etc...... \\
$\Downarrow$ \\
Such searches are very important for us.
}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Grover's quantum search (1997)}\\
\color{black}
\bigskip
A speed up from 
\color{red}
$O(N)$ 
\color{black}
to 
\color{red}
$O(\sqrt{N})$.
\end{center}


\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{fictitious-classics.eps}
\includegraphics[width=7.5cm,height=4cm]{fictitious-quantum.eps}
\end{center}
\end{figure}



%% Owing
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A strange path of quantum computation}\\
\color{black}
\bigskip
\begin{Large}
When a particle goes from A to B, \\ it takes all possible paths at the same time.
\end{Large}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{quantum-path.eps}
\end{center}
\end{figure}



%% I think we are running out of time and hope this conlulde the tolk, thank you
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Concluding Remarks}\\
\end{center}

\color{black}
{\LARGE
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Searching for a needle in a hay is open \& important issue.
\item We need real efficient approaches.
\item Not yet so far a real efficient one.
\bigskip
\item We have to be careful about an effect of \\
\hspace*{0.6in}{\it like-to-hear-what-we-would-like-to-hear.} \\
Success at a small scale is not a royal road to a real success.

\end{itemize}
}


\end{huge}
\end{document}


