\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{(CISIM'2007 -- at Elk, Poland)}
\thispagestyle{empty}

\begin{document}
\begin{huge}

\clearpage  % (title) =========================================
\begin{center}
\color{blue}
{\bf Finding a Needle in a Haystack: \\ 
from  \\
Baldwin Effect \\ 
to \\
Quantum Computation}\\

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



\clearpage  % =========================================
\begin{figure}[bhtp]
\begin{center}
%%\includegraphics[width=8cm]{b19objects363.jpg}
%%\includegraphics[width=8.5cm]{usne6757.jpg}
%%\includegraphics[width=8.5cm]{ted-hay-24.3.jpg}
\includegraphics[width=8.5cm]{hay-1.eps}
\includegraphics[width=8.5cm]{hay-2.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Alora's proposition (2007)}\\
\color{black}

\begin{figure}[bhtp]
\begin{center}
  \includegraphics[width=1.5cm]{mozart.eps}
%%\includegraphics[width=1.5cm]{karajan-1.eps}
  \includegraphics[width=1.5cm]{karajan-2.eps}
\end{center}
\end{figure}

Brilliance = Ability to find a needle in a haystack.\\
\bigskip
{\LARGE
He said,\\
{\it ``Art is to create satisfying assignments to neural circuts \\
in our brain for an appreciation.''}
}
\end{center}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Could endlessly typing monky eventually create Shakespear by chance?}\\

\color{black}
\hspace*{1in}\\
Hopefully not! \\

\hspace*{1in}\\
Then what about {\it haiku}? \\

\hspace*{1in}\\
Might be more likely.
\end{center}


%% \clearpage
%% \begin{figure}[bhtp]
%% \begin{center}
%% \includegraphics[width=3cm,height=9cm]{1269.jpg}
%% \end{center}
%% \end{figure}


\clearpage
\vspace*{0.5in}
\hspace*{1in} 
�ӂ邢����\\
\hspace*{2in} 
���킸�Ƃт���\\
\hspace*{3in} �݂��̂���\\


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf How many possible different Haiku's?}

\color{black}
\begin{displaymath}
50^{17} \approx 10^{18}
\end{displaymath}

\hspace*{1in}\\
It's like a search for {\it a-needle-in-a-haystack} \\ 
for a mokey to create one of them.

\end{center}


%% by the way it's not difficult. Why don't we use magnet or metal detector?

%% start with haiku tategaki 
%% artist is a needle finder

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Computational analogue of needle-in-a-haystack}\\


\color{black}
\bigskip
deteting oil spil from satelite image \\
\color{red}
specific data
\color{black}
 from a  huge database\\
cryptography \\
...... \\
$\Downarrow$ \\
Such searches are very important for us.
\end{center}


\clearpage  % =========================================
%% I became interested in this topic for the first time when ...
\begin{center} \color{blue}
%%{\bf First motivated}
{\bf Associative memory by Spiking neurons}


\color{black}
\bigskip
Fitness landscape \\
$\Downarrow$ \\
Hopfield network ... many peaks in a rugded land \\
vs.\\
Spiking neurons ... like a flat island in a huge lake
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A standard initial distribution \\of fitness values}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-2p.eps}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-8p.eps}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-16p.eps}
\end{center}
\end{figure}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A fictitious 1-D fitness-landscape \\ of Hebbian-learning by spiking neurons}

\color{black}
\bigskip
\begin{figure}[bhtp]
\begin{center}
%% \includegraphics[width=9cm,height=3cm]{hebbian-ls.eps}   %% maybe delete this
\includegraphics[width=15cm,height=2.5cm]{spike-ls.eps}
\end{center}
\end{figure}

\end{center}



\clearpage  % =========================================
\begin{center}
\vspace*{1in}
{\bf It's not possible to hill climb\\ if not a hill to climb!}
\end{center}




\clearpage  % =========================================
\begin{center}
\color{blue}
{\bf Network intursion data \\ among normal transaction data}


\color{black}
\bigskip
E.g. $\Rightarrow$ 4 attack types in KDD-cup-99 dataset\\

\hspace*{1in}\\

The winner's result 
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=15cm,height=2.5cm]{table-1.eps}
\end{center}
\end{figure}

%% {\it
%% \begin{table}[h]
%% \begin{center}
%% \hspace*{1in}\\
%% \begin{tabular}{c c c c} \hline
%%                 Probe  & DoS  & U2R  &  R2L \\ \hline
%%                83.3\%   & 97.1\% & 13.2\% & 8.4\%  \\ \hline
%% \end{tabular} 
%% \end{center}
%% \end{table}
%% }

\clearpage  % =========================================
\begin{center}
\color{blue}
{\bf Detection rate by Sabhnani et al.~(2003)}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=18cm,height=8.5cm]{table-2.eps}
\end{center}
\end{figure}

%% \color{black}
%% {\it
%% \begin{table}[h]
%% \begin{center}
%% \begin{tabular}{l c c c c} \hline
%% \hspace*{.1in}                     & Probe  & DoS  & U2R  &  R2L \\ \hline
%% Multi-layer Perceptron             & 88.7   & 97.2 & 13.2 & 5.6  \\
%% Gaussian Classifier                & 90.2   & 82.4 & 22.8 & 9.6  \\
%% $K$-mean Clustering                & 87.6   & 97.3 & 29.8 & 6.4  \\
%% Nearest Cluster Algorithm          & 88.8   & 97.1 &  2.2 & 3.4  \\
%% Radial Basis Function              & 93.2   & 73.0 &  6.1 & 5.9  \\
%% Leader Algorithm                   & 83.8   & 97.2 &  6.6 & 1.0  \\
%% Hypersphere Algorithm              & 84.8   & 97.2 &  8.3 & 1.0  \\
%% Fuzzy Art Map                      & 77.2   & 97.0 &  6.1 & 3.7  \\
%% C4.5 Decision Tree                 & 80.8   & 97.0 &  1.8 & 4.6  \\ \hline
%% \end{tabular} 
%% \end{center}
%% \end{table}
%% }

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Some Intrusions \\
 are immune to be detected \\ 
by any Machine learning Techniques}\\

\color{black}
\hspace*{1in}\\
{\it ``If a class is very rare, e.g., 0.5\%
prediction of non-target will be 99.5\%.''} (Joshe et al. 2001)


however we have still many inocent reports of success
\end{center}




\clearpage   % =========================================
\color{blue}
\begin{center} \color{blue}
{\bf Let's study more in detail!}
\end{center}
\color{black}
\begin{itemize}
\item Hinton \& Nowlan's experiment
\item Reduced even-parity problem as a benchmark
\item Robot navigation
\item Quantum computation
\end{itemize}





\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's Needle (1987)}\\
\end{center}

\color{black}


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


\begin{itemize}
\item A-needle $\Rightarrow$ One configuration of 20-bit binary strings.
\item Haystack $\Rightarrow$ $2^{20}-1$ search points.
\end{itemize}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect --- Lifetime learning}\\
\color{black}
a genotype \\
(10901099011001001091)\\
$\Downarrow$\\
its phenotype\\
(10901099011001001091)\\
(10901099011001001091)\\
(10901099011001001091)\\
...

\end{center}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their GA implementation}\\
\color{black}
\bigskip
1000 genotypes \\
1000 lifetime learnings \\
25\% flexible genes \\ 
...... \\
\end{center}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect looks great!}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=10cm,height=6cm]{kauno-linear-2.eps}
\end{center}
\end{figure}










\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Descrepancies from their result}\\
\end{center}

\color{black}
\begin{itemize}
\item Why should we continue when lifetime-learning finds needle?
\begin{itemize}
\item not engineering but a biological interest (Turney 1987)
\end{itemize}
\item Is Learning gene decreasing?
\end{itemize}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf How many learning genes are necesarry?}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=5.5cm,height=4cm]{lifetime-success-1.eps}
\includegraphics[width=5.5cm,height=4cm]{lifetime-success-2.eps}
\end{center}
\end{figure}




\clearpage   % =========================================
\begin{center} \color{blue}
{\bf How many learning genes are necesarry?}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=8cm]{how-flexible-necessary.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf An extinction!}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=8cm]{baldwin-survived.eps}
\end{center}
\end{figure}



\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's Needle}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=8cm]{lamarck-number-of-9.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf What about Lamarckian Inheritance?}\\

\color{black}
\bigskip
Turney (1996)\\
{\it ``Lamarckian evolution requires an inverse mapping from phenotype and
environment to genotype ... We believe that computing this mapping is intractable in general,''}

\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf What about Lamarckian Inheritance?}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=8cm]{lamarck-avg-fit-2.eps}
\end{center}
\end{figure}







%% \clearpage
%% \hfill {\large (Cont'd)}



\clearpage   % =========================================
\color{black}
\begin{itemize}
\item Hinton \& Nowlan's experiment
\color{blue}
\item Reduced even-parity problem as a benchmark
\color{black}
\item Robot navigation
\item Quantum computation
\end{itemize}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A discussion}\\


{\Large
\hspace*{1in}\\
\color{black}
{\it ``Finding Needles in Haystacks Is Not Hard with Neutrality.'' }\\
(Yu \& Miller, 2002)\\
\hspace*{1in}\\
vs.\\
\hspace*{1in}\\
{\it ``Finding Needles in Haystacks is Harder with Neutrality.'' }\\
(Collins, 2005)\\
}
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-n-Parity Problem}\\
\end{center}



\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Fitness distribution}\\
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=2.5cm]{histgram-needle.eps}
\includegraphics[width=16cm,height=2.5cm]{histgram-parity.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-n-Parity Problem}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=2.4cm]{even-5-parity-1.eps}
\end{center}
\end{figure}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-n-Parity Problem}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=4cm]{even-5-parity-2.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-n-Parity Problem}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=4cm]{even-5-parity-3.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-n-Parity Problem}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=6cm]{even-5-parity-4.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\begin{center}
\hspace*{1in}\\
\hspace*{1in}\\
We human, on the other hand, \\
can create an even-$n$-parity for however large $n$.
\end{center}


\clearpage   % =========================================
\color{blue}
\begin{itemize}
\item Hinton \& Nowlan's experiment
\item Reduced even-parity problem as a benchmark
\item Robot navigation
\item Quantum computation
\end{itemize}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Can random-walker find a needle \\ in a 2-dimensional grid?}\\

\color{black}
\bigskip
A scale limit of search with random walk.

\end{center}


%% experimental result  when grid size becomes large


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A robot navigation}\\

\color{black}
\bigskip
Can a learning enhance efficiency?
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=6cm]{messy-quantum.eps}
\end{center}
\end{figure}


\clearpage   % =========================================
\color{blue}
\begin{itemize}
\item Hinton \& Nowlan's experiment
\item Reduced even-parity problem as a benchmark
\item Robot navigation
\item Quantum computation
\end{itemize}


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


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


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A quantum walk on the line}\\
\color{black}

%% When a particle goes from A to B, it takes all possible paths all at the same time.
%% The probability of observing the particle doing the quantum walk
%% at any given point $n$ at $t$  (Nayak \& Vishvanath)

\color{black}

\begin{Large}
\begin{displaymath}
p(n, t) = \| \psi_L (n, t) \|^2 + \| \psi_R (n, t) \|^2
\end{displaymath}
where
\begin{displaymath}
\psi_L = \frac{1+(-1)^{n+t}}{2} \int_{-\pi}^{\pi}{\frac{dk}{2 \pi}}
(1 + \frac{\cos k}{\sqrt{1 + \cos^2 k}}) \exp \{{-i(\omega_k t + kn)\}}
\end{displaymath}

\begin{displaymath}
\psi_R = \frac{1+(-1)^{n+t}}{2} \int_{-\pi}^{\pi}{\frac{dk}{2 \pi}}
\frac{\exp (i k)}{\sqrt{1 + \cos^2 k}}) \exp \{{-i(\omega_k t + kn)\}}
\end{displaymath}
\end{Large}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A quantum walk on the line}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-1.eps}
\end{center}
\end{figure}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-20.eps}
\end{center}
\end{figure}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-100.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Concluding Remarks}\\
\hspace*{1in}\\
\color{black}
$\bullet$ We have to avoid
an effect of \\ {\it like-to-hear-what-we-would-like-to-hear.}

\end{center}

\end{huge}
\end{document}



