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

%%\usepackage{rsfs}

%%\usepackage[pdftex,dvipsnames]{color}
%%\usepackage[pdftex]{color}
%%\usepackage{epstopdf} 
%%\DeclareGraphicsExtensions{.pdf,.eps,.png,.jpg,.mps}

\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{color}

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

\pagestyle{myheadings}
\markright{(Congress of Young IT Scientist 2012)}
\thispagestyle{empty}
\begin{document}
\begin{huge}

\clearpage  % (title) =========================================
\color{blue}
\begin{center}
{\bf How can we compare intelligence of\\ two machines?}
\hspace*{,5in}\\
\color{black}
\bigskip
\hspace*{1in}\\
\begin{Large}
Akira Imada  \\
\bigskip
Brest State Technical University (Belarus)
\end{Large}
\end{center}

%% The topic is machine intelligence but somehow a very basic one

\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf The term 'Intelligence' is everywhere!}\\
\hspace*{1in}\\
\color{black}
{\LARGE
Lots of papers claim an intelligence}\
\end{center}



%% The topic is not my very specially but I'm always wondering
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf How intelligent?\\ \bigskip Which agent is more intelligent?}\\
\end{center}




%% Let's name a few
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf E.g. Intelligent decision in stock market}\\
\color{black}
\hspace*{1in}\\
{\large
Sewell "The Application of \color{red}intelligent 
\color{black} systems to financial time series analysis."\\
\bigskip
Tsang "Forecasting - where computational \color{red}intelligence 
\color{black} meets the stock market." \\
\bigskip
Kuoa "An \color{red}intelligent 
\color{black} stock trading decision support system."}\\
\end{center}

%% a Nobel lowriate economist
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Or, would it be better to ask monkey\\ to throw darts?}\\
\hspace*{1in}\\
\color{black}
{\Large
Malkiel "A Random Walk Down Wall Street"\\
\hspace*{1in}\\
{\it "A monkey throwing darts at the WSJ to select a portfolio\\
might be better than the one carefully selected by experts."}\\
$\Downarrow$\\
Those machines would be less intelligent than a monkey}
\end{center}


%% early march this year in Brooklyn 
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\LARGE
{\bf Other examples we want to know its intelligence}}\\
\bigskip
\bigskip
\color{black}
{\Large
From \\
\color{red}Deep Blue\color{black}: beat Kasparov \\
to\\
\color{red}Watson\color{black}: won Jeopardy\\ 
\color{red}Dr. Fill\color{black}: joined the human crossword tournament\\
\color{red}Siri\color{black}: incorpolated in i-Phone 4\\
\color{red}Essay-scoring software\color{black}}
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\LARGE
{\bf A degree to how a machine is intelligent}}\\
\bigskip
\bigskip
\color{black}
{\Large
Gregory Chaitin (1987), Warren Smith (2006)\\ tried to answer it 
using \color{red} complexity \color{black} theory.\\
%% \bigskip
%% Time: "{\it intelligent peoples are more difficult to learn to know.} (2012)\\
$\Downarrow$\\
Now we have a fair amount of such definitions.}
\end{center}

%% attracts a lot of interest, recently
%% Gregory J. Chaitin, Warren D. Smith
%% last year skip detail but this time ...

\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Legg \& Hutter's definition}\\
\color{black}
\bigskip
\bigskip
{\Large
From informal\\
``An \color{red}agent\color{black}'s ability to achieve \color{red}goals \color{black} in a wide range of \color{red}environments\color{black}.''\\
\bigskip
$\Downarrow$\\
to formal
\color{red}
\begin{displaymath}
\gamma(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} \cdot V_{\mu}^{\pi}
\end{displaymath}
\color{black}
}\\
\end{center}


%% Agents we concerns usually interact SOME environment
%% Let me represent i-th obserbation, action, and reward as o_i, a_i and r_i
%% or
%% Let me denote ith repetion as  o_i, a_i and r_i

\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Agent interacts with environment}\\
\color{black}
{\Large
\bigskip
Observation $o_i$ $\Rightarrow$ Action $a_i$ $\Rightarrow$ Reward $r_i$
\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=18cm,height=6cm]{env.jpg}
\end{center}
\end{figure}
%% an exploration of the agent in the environment yields a series of sequences of ... called history
}
\end{center}



%% indeterministic simulation
%% let's call it a pi/mu
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Definition of agent}\\
\bigskip
\color{black}
{\Large Function that takes the current history as input\\ and \\produces an action as output\\ 
\bigskip \color{red}
%% $\pi(a_3 \vert o_1r_1a_1o_2r_2)$\\
$\pi(a_k \vert o_1r_1a_1o_2r_2a_2\cdots o_{k-1}r_{k-1})$\\
\color {black} or probability function for indeterministic.
} 
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Definition of environment}\\
\bigskip
\color{black}
{\Large
Function  which produces output $o_kr_k$ given the current history\\
\bigskip \color{red}
$\mu(o_kr_k\vert o_1r_1a_1o_2r_2a_2\cdots o_{k-1}r_{k-1}a_{k-1})$\\
\color{black} or probability function for indeterministic.
}\end{center}


\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Expected value of sum of rewards}\\
\color{red}
{\Large
\begin{displaymath}
V_{\mu}^{\pi} = E (\sum_{i=1}^{\infty} r_i)
\end{displaymath}
\color{black}
after each repetion of\\ $o_i \rightarrow a_i \rightarrow r_i$.}
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Definition of intelligence} \\
\color{black}
\bigskip
{\Large
Weighted sum of \\
expected value of sum of rewards over infinite environments\\
\color{red}
\begin{displaymath}
\gamma(\pi) = \sum_{\mu \in E} w_{\mu} \cdot V_{\mu}^{\pi}
\end{displaymath}}
\end{center}
%% Summation if for infinite environments



%% So that we can calculete Kolmogorov ...
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf How will those weights be specified?} \\
\bigskip
\color{black}
{\Large
Translate the environment into a binary string $x$ by Turing Machine $U$\\
%%\bigskip
$\Downarrow$\\
Calculate Kolmogorov complexity $K$ of $x$ \\
(length of the shortest program that computes $x$)\\ 
%% \bigskip
%% $\Downarrow$\\
$K(x)=\min_p\{l(p) \vert U(p)=x\}$\\
\bigskip
$\Downarrow$\\
\color{red}$w_{\mu}=2^{-K(\mu)}$ \color{black}\\
The smaller the complexity the larger the weight $\Rightarrow$ Occam's razor}
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Universal Machine Intelligence} \\
\color{black}
{\Large
by Legg and Hutter \\
\begin{displaymath}
\gamma(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} \cdot V_{\mu}^{\pi}
\end{displaymath}
``An \color{red}agent\color{black}'s ability to achieve \color{red}goals \color{black} in a wide range of \color{red}environments\color{black}.''}
\end{center}


\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Too conceptual or too theoretical} \\
\bigskip
\color{black}
{\Large
Goertzel:\\
"Universal but not practical."}
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Goertzel} \\
\color{black}
{\Large 
pragmatic intelligence\\
\color{red}
\begin{displaymath}
\Pi(\pi) = \sum_{\mu \in E, g \in G, T} \nu(\mu)\gamma(g,\mu)\tau_{g,\mu}(T) V^{\pi}_{\mu,g,T}
\end{displaymath}
\color{black}
\bigskip
$\Downarrow$\\
It's not very practical yet, isn't it?}
\end{center}


\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Problem is, translation of environment \\by Turing machine} \\
\bigskip
{\Large 
\color{black}
$\Downarrow$\\
Are there easier alternatives to the Turing machine?}
\end{center}

%% purpose is to generate ...
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Hern\'andes-Orallo} \\ 
{\Large
\color{red}
\bigskip
The other representations of environment \\
\color{black}
%% Apart from Turing machines many other Turing complete models of computation, such as: \\
$\Downarrow$ \\
%%\bigskip
(i) $\lambda$-calculus, (ii) combinatory logic, (iii) abstract state machines, \\
(iv) register machines, (v) Markov algorithms,\\ (vi) term-rewriting systems, ... \\
\bigskip
%% also Finite state machine (not Turing complete though) 
\color{red}
to generate environments and calculate complexity \color{red}automatically\color{black}.\\
\bigskip
{\it "still Turing-complete, but\\ \color{red}more natural and easy 
\color{black} to work with than the Turing machine."}\\
}
\end{center}


%% his target was strings like this
%% for some strings of different difficulty such as these strings
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Hernandes's example}\\
\bigskip
\color{black}
{\Large
tests measures the ability of finding the shortest explanation\\ 
for some strings of different difficulty in a fixed time”\\
e.g.\\
{\it 
x = aaaaaaabaaaaaaaaaaaaaabaaa\\
x = aabbbccdddeefffgghhhiijjj\\
x = 1,2,3,5,7,11,13,17,19,23}\\

$\Downarrow$\\
Still not so practical for our purpose.}
\end{center}


%% In order to proceed
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\Large {\bf To proceed further (1)}}\\
{\LARGE {\bf First, let's be more practical!}}\\
\bigskip
\color{black}
{\Large
Let's look for yet another way to measure complexity.}
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf The other ways to measure complexity}\\
\color{black}
{\Large
although these are not Turing complete any more.\\
\hspace*{1in}\\
Crutchfield et al.: Comment on "Simple Measure for Complexity"\\
\color{red}
$\Gamma_{\alpha \beta} = (S/S_{max})^{\alpha}(1-(S/S_{max}))^{\beta}$\\
\color{black}
\bigskip
Fioretti: A subjective measure of complexity
\color{red} \begin{displaymath}
C_{O}(S) = \sum_{q=0}^{Q} \frac{q+1}{s_q}
\end{displaymath} \color{black}
%% \bigskip
%% Calbet: A statistical measure of complexity\\
%% \bigskip
%% Lee: Problem complexity:\\ A measure of problem difficulty in algebra by using computer\\
\bigskip
Lloyd: A survey - Measures of complexity a non-exhaustive list}
\end{center}




%% at least at this moment we need to be specific but not universal
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\Large {\bf To proceed further (2)}}\\
{\bf Second, let's be specific not universal!}\\
\color{black}
\bigskip
{\Large
$\star$ "She is an \color{red} intelligent \color{black} dancer," \\ while we know she is not good at Mathematics,\\
which we don't care.\\
\bigskip
$\star$ This conductor always makes an \color{red}intelligent \color{black} interpretation of symphony, but very bad at football.\\
\bigskip
$\star$ Would Einstein play tennis \color{red} intelligently?\\
\color{black} $\Downarrow$\\
\color{red}
Intelligence doesn't need to be universal!}
\end{center}

%% What about this one?
%% Which route, do you think, ...
%% this is somewhat extreme but
%% our concern is only route
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf E.g. which route is more intelligent?}\\
\bigskip
\color{black}
{\Large
%% What we want, at least currently, is an intelligence in a specific domain, not a universal one.\\
%% E.g., Which route is more intelligent, and why?\\
A business person \& a philosopher going for a walk in Manhattan}
\end{center}

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=4cm,height=4cm]{trace-96-start-val-1.jpg}
   \includegraphics[width=4cm,height=4cm]{trace-96-end-new-val-1.jpg}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} 
\color{blue}
{\Large {\bf To proceed further (3)}}\\
{\bf Third, let's be more unpredictable!}\\
\end{center}



\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf What is human-like intelligence?}\\
\color{black}
{\Large 
%%$\Downarrow$ \\
\bigskip
\bigskip
Human-intelligence is
\color{red}
spontaneous\color{black}, \color{red}flexible\color{black}, 
and/or \color{red} unpredictable\color{black},\\ 
\color{black}more or less.\\
Or even \color{red} erroneous \color{black} sometimes.}
\end{center}

%% 

%% \clearpage  % =========================================
%% \begin{center} 
%% \color{blue}
%% {\bf Can we tell it's a computer, not a human?}\\
%% \color{black}
%% \bigskip
%% $\Downarrow$\\
%% \bigskip
%% {\Large If we can, it's because of \color{red}too precise \color{black} reaction,\\
%% \bigskip
%% Is computer intelligent enough to pretend to be a little foolish?}
%% \end{center}


\clearpage  % =========================================
\bigskip
\begin{center} 
\color{blue}
{\bf A possible trick to the Turing Test}\\
\bigskip
\color{black}
{\Large
might be \\
to give a \color{red} same question repeatedly.}
\end{center}

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=6cm,height=5cm]{turing.jpg}
\end{center}
\end{figure}




\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf To mimic a human}\\
\color{black}
\bigskip
$\Downarrow$\\
\bigskip
{\Large
\color{red}Do not always exactly the same action even in a same situation\color{black}.}
\end{center}


%% I like this metaphor
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf ``I beg your pardon?''}\\
\hspace*{1in}\\
\color{black}
{\Large 
Intelligent people try a \color{red}different 
\color{black}explanation for an easier understanding\\
\bigskip
while \\
others just repeat the \color{red}same \color{black}expression, maybe louder.}
\end{center}


%% come accross a sushi bar with a sushi robot
\clearpage  % =========================================
\bigskip
\begin{center} 
\color{blue}
{\bf I couldn't enjoy sushi by a sushi robot!}\\
{\LARGE
\color{black}
\bigskip
because it tastes \color{red} always the same.}
\end{center}



%% \clearpage  % =========================================
%% \begin{center} 
%% \color{blue}
%% {\bf Excellent but always slightly different}\\
%% \color{black}
%% {\Large (One of the reason I like this.)}
%% \end{center}
%% 
%% \begin{figure}[bhtp]
%% \begin{center}
%%    \includegraphics[width=5cm]{gyoza-0.jpg}
%%    \includegraphics[width=5cm]{gyoza-1.jpg}
%%    \includegraphics[width=5cm]{gyoza-2.jpg}
%% \end{center}
%% \end{figure}



%% \clearpage  % =========================================
%% \begin{center} 
%% \color{blue}
%% {\LARGE
%% {\bf 
%% Does intelligence imply \\preciseness, efficiency, or effectiveness?}}\\
%% \bigskip
%% {\Large
%% \color{black}
%% If so\\
%% We have already lots of intelligent machines}
%% \end{center}



\clearpage  % ========================================= negative
\begin{center} 
\color{blue}
{\bf Why spontaneous?}\\
%% \begin{figure}[h]
%% \begin{center}
%% \rotatebox[origin=c]{270}koko{
%% \includegraphics[width=2.5cm,height=5cm]{aibo.eps}}
%% \includegraphics[width=4cm,height=3cm]{sony_aibo_entertainment_robot.jpg}
%% }
%% \end{center}
%% \end{figure}
%% \bigskip
\hspace*{1in}\\
\color{black}
{\Large We sometimes need \color{red} spontaneous \color{black} and \color{red} unpredictable \color{black} intelligence rather than \color{red} efficiency \color{black} or \color{red}effectiveness \color{black} like in case of SONY's AIBO.\\
\bigskip
It learns excellently and acts \color{red} differently in different situation \color{black}
but repeats \color{red} the same action in a same situation\color{black}.\\
\bigskip
Sooner or later the owners lose their interest
}
\end{center}



\clearpage  % ========================================= negative
\begin{center} 
\color{blue}
{\bf Our modification}\\
\color{black}
\bigskip
{\Large
Legg \& Hutter's\\
``an ability to achieve goal\color{red}s \color{black} in a wide range of environment\color{red}s\color{black}'' \\
$\Downarrow$\\
``ability to achieve \color{red} a \color{black} goal in \color{red} an \color{black} environment''\\
{\LARGE +}\\
\color{red}``an ability to act differently even in a similar situation''\color{black}\\
%% $\Downarrow$ \\
%% We could evaluate so-far-proposed machine intelligence!!
}
\end{center}

%% First of all, we tried to modify the definition by Legg & Hutter

\clearpage  % ========================================= negative
\begin{center} 
\color{blue}
{\bf A measure of similarity}\\
\end{center}


%% In order to be specific
%% repeat a run in a same condition to see similarity
%% similarity of each result 
%% Instead of Kolmogorov we use a more realistic definition of complexity

\clearpage  % ========================================= negative
\begin{center} 
\color{blue}
{\bf Intelligence in a specific domain}
\color{black}
{\Large
\begin{displaymath}
\gamma(\pi) = \sum_{\mu \in E} 2^{-K(\mu)} \cdot V_{\mu}^{\pi} \hspace{.4in} \Rightarrow \hspace{.4in} \gamma(\pi) = 2^{-K(\mu)} \cdot V_{\mu}^{\pi} 
\end{displaymath}
%% $\Downarrow$
%% \begin{displaymath}
%% \gamma(\pi) = 2^{-K(\mu)} \cdot V_{\mu}^{\pi}
%% \end{displaymath}
$\Rightarrow$ repeat a run in a same condition to see similarity
\hspace*{1in}\\
\color{red}
\begin{displaymath}%% \gamma(\pi) = \sum_i \frac{2^{-\{\mbox{\small COMPLEXITY}\}_{i}}\cdot \{\mbox{\small REWARD}\}_{i}}{\{\mbox{\small SIMILARITY}\}_{i}}
\gamma(\pi) = \sum_i \frac{2^{-\{\mbox{\small COMPLEXITY}\}_{i}}\cdot \{\mbox{\small EXPECTED REWARD}\}_{i}}{\{\mbox{\small SIMILARITY}\}_{i}}
\end{displaymath}
}
\end{center}


%% this is what we have completed so far
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Let's summarize}\\
\bigskip
\color{black}
{\Large 
based on Legg \& Hutter's definition \\
$\Downarrow$\\
but specific, not universal \\
$\Downarrow$\\
more reallistic complexity measure, not by Turing Machine.\\
$\Downarrow$\\
expect a different action in a same situation.\\}
\end{center}


%% and not intelligent individuals looks simple, which is opposit of our definition
%% and still on going
\clearpage  % =========================================
\begin{center} 
\color{blue}
{\bf Is Occam's razor principle\\ really necessary?}\\
\hspace*{1in}\\
\color{black}
{\Large
Occam's razor plays an inportant role but at the same time we doubt it\\
\hspace*{1in}\\
Once Kluger wrote in the TIME Magazine\\
{\it "intelligent individuals are more difficult to learn to know." }\\
$\Downarrow$\\
Artificial agents sometimes must pretend to be complex.\\
$\Downarrow$\\
The issue is still open and many things await to be done.\\
$\Downarrow$\\
Let's cooperate!}
\end{center}

%% this conclude my talk, thank you!

\clearpage  % ========================================= negative
\vspace*{0.7in}
\begin{center} 
\color{blue}
{\bf Dzi\c{e}kuj\c{e}!}
\end{center}

\end{huge}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



