%% 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}
\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}
+
{\Large Self-Generated Culture}
Fran\c cois Fleuret
\vspace*{2ex}
-\centerline{\color{red}(work in progress, to be updated)}\\[3ex]
+\centerline{\color{red}(work in progress, to be updated)}
+
+\medskip
\centerline{\url{https://fleuret.org/public/culture/culture.pdf}}
\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.
-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}
+
+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.
+
+\end{example}
+
+\separator
+
+\begin{example}
-The experiments starts with a set of quizzes, that is going to be
-progressively enriched.
+\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}
+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.
%
-\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.
-\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}
+
+\begin{itemize}
+
+\item The whole process can be envisioned as natural selection of
+ quizzes in the representation landscape of GPTs. There probably is a
+ subtle relation between the temperature (mutation rate) and the
+ number of models used to validate with the ``all but one'' criterion
+ (survival criterion).
+
+\item The ``all but one'' could be ``all but K'', and there may be
+ some information-theoretical thing, where the goal is to maximize
+ mutual information, with $K=N$ being total randomness, so high
+ entropy but no structure, and $K=0$ is total determinism, so no
+ information to share.
+
+\item The setup does not push toward any specific invariance or
+ property in the generated quizzes, their consistency is entirely due
+ to the statistics of the ``world quizzes'' that remain in the
+ training set, and to the GPTs' inductive biased.
+
+\item The GPTs obviously get a sense of objectness and 2d topology
+ early on, since they rapidly increase the number of birds and
+ ``discover'' occlusion even though they never was in the world
+ quizzes.
+
+\item There may not be so many problems that can be cast as pairs of
+ patterns that are each a deterministic function of the other, which
+ is probably critical here.
+
+\item This overall process probably fight the ``simplicity bias'': If
+ a model is lacking a ``cue'' that the others have, there will
+ rapidly be quizzes that require this cue, they will be added to the
+ training data, and that model will catch up.
+
+\item The randomness of the process probably allow to even go beyond
+ just synchronizing the abilities of the models. There may be some
+ additional complexification of quizzes that get accepted by chance.
+
+\item It can be parallelized by dispatching the GPTs across multiples
+ nodes, and avoiding a quadratic cost by limiting the validation of
+ the quizzes to a subset of them.
+
+\item The current process to generate new quizzes, which simply
+ samples them at random is very rudimentary and probably not
+ sufficient in a real-data setup. It can probably be supplemented
+ with a MCTS-type search.
+
+\item There may be already in the generated quizzes some structure
+ that \emph{we} do not pick up (e.g. certain color or motion
+ patterns).
+
+\end{itemize}
\section*{Appendix}
-The code is available at\\[-2ex]
+The code is available at
+
+\medskip
\centerline{\url{https://fleuret.org/git/culture}}