Merge branch 'dev'
[culture.git] / report / culture.tex
index 59899c0..d9f39e3 100644 (file)
@@ -5,7 +5,7 @@
 %% Written by Francois Fleuret <francois@fleuret.org>
 
 \documentclass[11pt,a4paper,oneside]{article}
 %% Written by Francois Fleuret <francois@fleuret.org>
 
 \documentclass[11pt,a4paper,oneside]{article}
-\usepackage[paperheight=15cm,paperwidth=8cm,top=2mm,bottom=15mm,right=2mm,left=2mm]{geometry}
+\usepackage[paperheight=15cm,paperwidth=8cm,top=2mm,bottom=15mm,right=5mm,left=5mm]{geometry}
 %\usepackage[a4paper,top=2.5cm,bottom=2cm,left=2.5cm,right=2.5cm]{geometry}
 \usepackage[utf8]{inputenc}
 \usepackage{amsmath,amssymb,dsfont}
 %\usepackage[a4paper,top=2.5cm,bottom=2cm,left=2.5cm,right=2.5cm]{geometry}
 \usepackage[utf8]{inputenc}
 \usepackage{amsmath,amssymb,dsfont}
 \def\concat{\operatorname{concat}}
 \def\crossentropy{\LL_{\operatorname{ce}}}
 
 \def\concat{\operatorname{concat}}
 \def\crossentropy{\LL_{\operatorname{ce}}}
 
+\newcommand{\separator}{\begin{center}
+*
+\end{center}}
+
+\newcommand{\pic}[2]{%
+\hspace*{\stretch{1}}
+%
+\includegraphics[scale=0.25]{#1}
+%
+\hspace*{\stretch{1}}%
+}
+
+\newcommand{\birdpic}[2]{%
+\hspace*{\stretch{1}}
+%
+\includegraphics[scale=0.35]{#1}
+%
+\hspace*{\stretch{1}}%
+}
+
+\newenvironment{example}{%
+
+\vspace*{2ex}
+
+\begin{minipage}{\textwidth}
+
+\setlength{\parindent}{0cm}
+\setlength{\parskip}{1ex}
+}{%
+\end{minipage}
+}
+
 \begin{document}
 
 \vspace*{-3ex}
 
 \begin{center}
 \begin{document}
 
 \vspace*{-3ex}
 
 \begin{center}
+
 {\Large Self-Generated Culture}
 
 Fran\c cois Fleuret
 {\Large Self-Generated Culture}
 
 Fran\c cois Fleuret
@@ -94,101 +127,379 @@ Fran\c cois Fleuret
 \section{Introduction}
 
 The hypothesis behind this experiment is that high-level abstract
 \section{Introduction}
 
 The hypothesis behind this experiment is that high-level abstract
-thinking is fueled by social competition. A group of communicating
-agents that try to demonstrate their cognitive superiority would end
-up developing a rich and consistent culture.
+thinking is fueled by social competition.
+
+A group of communicating agents that try to demonstrate their
+cognitive superiority would end up developing a rich and consistent
+culture.
+
+\subsection{Setup}
 
 The experiment is designed with a group of GPTs that alternatively
 learn to solve quizzes and generate new ones.
 
 
 The experiment is designed with a group of GPTs that alternatively
 learn to solve quizzes and generate new ones.
 
-A ``quiz'' is a triplet of the form $(A, d, B)$ where $A$ and $B$ are
-two sequences and $d$ is a token indicating if the direction is
-forward or backward. Given $(A, d)$, the challenge is to generate $B$.
+A ``quiz'' is a pair composed of a prompt and a solution, both being
+sequence of tokens.
+
+We differentiate \textbf{world quizzes} that follow pre-defined and
+fixed regularities, and mimic the world's physical and environmental
+patterns that an organism has to grasp to survive, and \textbf{culture
+  quizzes} that are generated by the GPTs, and mimic the knowledge one
+has to master to perform socially.
+
+
+We train five GPTs on a a very large set of ``world quizzes''
+generated randomly. These models are trained to generate both the
+solution given the prompt, and the prompt given the solution.
+
+This is achieved by using for training both ``forward sequences'',
+composed of a token \texttt{[fwd]}, followed by the prompt's tokens,
+followed by another token \texttt{[fwd]}, followed by the solution's
+tokens, or ``backward sequences'' composed of a token \texttt{[bck]},
+followed by the solution's tokens, followed by another token
+\texttt{[bck]}, followed by the prompt's tokens,
+
+\subsection{Generating Culture Quizzes}
+
+When their accuracy get above $95\%$ we generate new quizzes as follows:
+%
+\begin{enumerate}
+
+\item generate a solution (without conditioning) at temperature $T=2$,
+  then generate a prompt for that solution at temperature $T=1/2$, and
+  then generate a solution for that prompt at temperature $T=1/2$.
+
+\item generate one solution for that prompt with each of the $5$ GPTs
+  at temperature $T=1$, if $4$ of them generate the correct solution,
+  validate that quiz and include it in the training data.
+
+\end{enumerate}
+
+This criterion assures that the new quizzes are both solvable and
+sophisticated, and incrementally complexify the culture. Imposing both
+direction prevents the generation of quizzes which are not trivial
+only because the prompt has been randomly degraded.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\pagebreak
+
+\section{Grid Quizzes}
+
+\subsection{World Quizzes}
+
+We define several types of quizzes and implement algorithmic
+procedures to generate randomly as many examples from each that we
+need.
+
+In these quizzes, the prompt is made of three grids $A, f(A), B$ and
+the solution is a single grid $f(B)$.
+
+\subsubsection{Half Fill}
+
+\pic{pics/task_color_grow.png}{``half fill''}
+
+The first grid contains three rectangles, each with a vertical or an
+horizontal line of another color in its middle. The second grid is
+identical with one of the rectangle having one half filled. The third
+grid contains three rectangles of identical colors as the firs grid,
+of different size and locations. The solution is obtained by filling
+similarly one of the half of a rectangle of the third image.
+
+\subsubsection{Detect}
+
+\pic{pics/task_detect.png}{``detect''}
+
+The first grid contains three rectangles, the second has two pixels of
+same colors located in the top-left corner of two of them. The
+solution is obtained by marking in the fourth image the top-left
+corners of the rectangles of same colors in the third.
+
+\subsubsection{Frame}
+
+\pic{pics/task_frame.png}{``frame''}
+
+The first grid contains three rectangles, and the second is identical
+except that one rectangle has been replaced by its frame. The same
+should be done to the similarly colored rectangles of the third grid
+to obtain the solution.
+
+\subsubsection{Grow}
+
+\pic{pics/task_grow.png}{``grow''}
+
+The first grid contains three rectangles, one of them getting one
+pixel thicker or thinner in the second. The same should be done to the
+similarly colored rectangles of the third grid to get the solution.
+
+\subsubsection{Replace color}
+
+\pic{pics/task_replace_color.png}{``replace color''}
+
+The first grid contains three rectangles, the second is obtained by
+changing one of the colors. The same should be done to the third grid
+to obtain the solution.
+
+\subsubsection{Translate}
+
+\pic{pics/task_translate.png}{``translate''}
+
+The first grid contains three rectangles. The second is obtained by
+displacing one of them by one pixel in both direction. The solution is
+obtained by applying the same motion to the similarly colored
+rectangle in the third grid.
+
+%% \subsubsection{Bounce}
+
+%% \pic{pics/task_bounce.png}{``bounce''}
+
+%% The solution should join the two pixels of same color, with a path of
+%% another color, starting in the direction indicated by a pixel of that
+%% color, and changing direction only when colliding with a pixel of a
+%% third color or one of the lattice border.
+
+%% \subsubsection{count}
+
+%% \pic{pics/task_count.png}{``count''}
+
+%% \subsubsection{scale}
+
+%% \pic{pics/task_scale.png}{``scale''}
+
+%% \subsubsection{trajectory}
+
+%% \pic{pics/task_trajectory.png}{``trajectory''}
+
+\subsection{Culture Quizzes}
+
+We list here some generated quizzes that exhibit features that were not present in the ``world quizzes'' used for training.
+
+\bigskip
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0110_N4_validated/quiz_63.png}{0110/63}
+
+\pic{pics/culture_c_quiz_0115_N4_validated/quiz_37.png}{0115/37}
+
+The quizzes ``frame'' and ``half fill'' have been combined in a single
+quiz.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0120_N4_validated/quiz_05.png}{0110/05}
+
+The ``frame'' quiz has been generalized to non-rectangular shapes.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_01.png}{0078/01}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_02.png}{0078/02}
+
+More rectangles were added as distractors.
 
 
-The experiments starts with a set of quizzes, that is going to be
-progressively enriched.
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0087_N4_validated/quiz_62.png}{0087/62}
+
+\pic{pics/culture_c_quiz_0102_N4_validated/quiz_04.png}{0102/04}
+
+\pic{pics/culture_c_quiz_0102_N4_validated/quiz_11.png}{0102/11}
+
+\pic{pics/culture_c_quiz_0108_N4_validated/quiz_31.png}{0108/31}
+
+Variation of ``Detect'' with location markers colored according to the
+color of the rectangle they mark.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_16.png}{0078/16}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_21.png}{0084/21}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_42.png}{0078/42}
+
+\pic{pics/culture_c_quiz_0089_N4_validated/quiz_28.png}{0089/28}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_00.png}{0084/00}
+
+Variations of ``Half Fill'', ``Detect'', ``Translate'', ``Grow'', and
+``Frame'' with a number of rectangles not equal to three.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_27.png}{0078/27}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_18.png}{0078/18}
+
+\pic{pics/culture_c_quiz_0086_N4_validated/quiz_45.png}{0086/45}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_37.png}{0078/37}
+
+Variations of ``Half Fill'' where the shapes to change have more
+complex coloring.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_30.png}{0078/30}
+
+Variation of ``Translate'' where the moving part is occluded, which
+was never the case.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_31.png}{0078/31}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_10.png}{0084/10}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_12.png}{0084/12}
+
+\pic{pics/culture_c_quiz_0086_N4_validated/quiz_23.png}{0086/23}
+
+\pic{pics/culture_c_quiz_0086_N4_validated/quiz_28.png}{0086/28}
+
+Variations of ``Half Fill'' with non-rectangular shapes.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0078_N4_validated/quiz_60.png}{0078/60}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_41.png}{0084/41}
+
+\pic{pics/culture_c_quiz_0084_N4_validated/quiz_49.png}{0084/49}
+
+\pic{pics/culture_c_quiz_0086_N4_validated/quiz_04.png}{0086/04}
+
+Variations of ``Half Fill'' with two colors or two rectangles have to
+be modified.
+
+\end{example}
+
+\separator
+
+\begin{example}
+
+\pic{pics/culture_c_quiz_0111_N4_validated/quiz_23.png}{0111/23}
+
+Variation of ``Frame'' with no rectangle of adequate size to be
+modified.
+
+\end{example}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\pagebreak
 
 \section{Bird World}
 
 
 \section{Bird World}
 
+These results were obtained with a slightly different procedure. In
+particular the quizzes were validated if the models could predict both
+the solution from the prompt and the prompt from the solution. We
+report them since they exhibit the same patterns of generalization
+although they are quite different.
+
+\subsection{World Quizzes}
+
 The initial set of quizzes consist of predicting the dynamics of a
 very simple world: A $6 \times 8$ grid with three colored ``birds'' moving in
 a straight line, possibly bouncing on the grid's borders. There are
 ten different colors.
 %
 The initial set of quizzes consist of predicting the dynamics of a
 very simple world: A $6 \times 8$ grid with three colored ``birds'' moving in
 a straight line, possibly bouncing on the grid's borders. There are
 ten different colors.
 %
-\begin{center}
-\includegraphics[scale=0.35]{pics/examples_train.png}
-\end{center}
+\birdpic{pics/examples_train.png}{}
 %
 
 %
 
-\vspace*{-2ex}
-
 In each on these quizzes, $A$ is the left image serialized in
 raster-scan order as a sequence of $6 \times 8 = 48$ tokens, $d$ is
 either the token ``forward'' or the token ``backward'', and $B$ is the
 right image, also serialized. The direction of prediction is chosen at
 random.
 
 In each on these quizzes, $A$ is the left image serialized in
 raster-scan order as a sequence of $6 \times 8 = 48$ tokens, $d$ is
 either the token ``forward'' or the token ``backward'', and $B$ is the
 right image, also serialized. The direction of prediction is chosen at
 random.
 
-\section{Generating Quizzes}
+\subsection{Culture quizzes}
 
 
-Given a set of $N$ GPTs, we can generate new quizzes as follows:
-Select one of the models, and use it to generate the $97$ tokens of a
-triplet $(A, d, B)$.
+This procedure results in the discovery of patterns which are not
+present in the original quizzes:
 
 
-Then with each one of the $N-1$ other models, predict $B$ from $(A,
-d)$, and $A$ from $(B, d')$ where $d'$ is the direction token opposite
-of $d$.
+\begin{example}
 
 
-A quiz is validated if \textbf{all the other GPTs but one predict it
-  deterministically correctly in both directions.}
+\birdpic{pics/4_birds_1.png}{}
 
 
-This criterion assures that the new quizzes are both solvable and
-sophisticated, and incrementally complexify the culture. Imposing both
-direction prevents the generation of quizzes which are not trivial
-only because the prompt has been randomly degraded.
+\birdpic{pics/5_birds_1.png}{}
 
 
-\section{Overall Process}
+\birdpic{pics/6_birds_1.png}{}
 
 
-The overall process consists of training the GPTs from scratch by
-iterating the following steps:
-%
-\begin{itemize}
+More birds.
 
 
-\item select the GPT with the lowest recorded test accuracy, train it through one epoch,
+\end{example}
 
 
-\item if its test accuracy gets above $97.5\%$, generate $1'000$ new
-  quizzes, add them to the training set, re-compute the accuracy of
-  all the models
+\separator
 
 
-\end{itemize}
+\begin{example}
 
 
-\section{Results}
+\birdpic{pics/other_shapes_2.png}{}
 
 
-This procedure results in the discovery of patterns which are not
-present in the original quizzes:
+\birdpic{pics/other_shapes_3.png}{}
 
 
-\textbf{More birds}
+New bird shapes.
 
 
-\begin{center}
-\includegraphics[scale=0.35]{pics/4_birds_1.png}
-\includegraphics[scale=0.35]{pics/5_birds_1.png}
+\end{example}
 
 
-\includegraphics[scale=0.35]{pics/6_birds_1.png}
-\end{center}
+\separator
 
 
-\textbf{New bird shapes}
+\begin{example}
 
 
-\begin{center}
+\birdpic{pics/other_shapes_1.png}{}
 
 
-\includegraphics[scale=0.35]{pics/other_shapes_2.png}
-\includegraphics[scale=0.35]{pics/other_shapes_3.png}
-\end{center}
+\birdpic{pics/occlusions_1.png}{}
 
 
-\textbf{Occlusions}
+Occlusions.
 
 
-\begin{center}
-\includegraphics[scale=0.35]{pics/other_shapes_1.png}
-\includegraphics[scale=0.35]{pics/occlusions_1.png}
-\end{center}
+\end{example}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\pagebreak
 
 \section{Various thoughts}
 
 
 \section{Various thoughts}