Merge branch 'dev'

[culture.git] / report / culture.tex

%% -*- mode: latex; mode: reftex; mode: flyspell; coding: utf-8; tex-command: "pdflatex.sh" -*-

%% Any copyright is dedicated to the Public Domain.
%% https://creativecommons.org/publicdomain/zero/1.0/
%% Written by Francois Fleuret <francois@fleuret.org>

\documentclass[11pt,a4paper,oneside]{article}
\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[pdftex]{graphicx}
\usepackage[colorlinks=true,linkcolor=blue,urlcolor=blue,citecolor=blue]{hyperref}
\urlstyle{same}
\usepackage{tikz}
\usetikzlibrary{arrows,arrows.meta,calc}
\usetikzlibrary{patterns,backgrounds}
\usetikzlibrary{positioning,fit}
\usetikzlibrary{shapes.geometric,shapes.multipart}
\usetikzlibrary{patterns.meta,decorations.pathreplacing,calligraphy}
\usetikzlibrary{tikzmark}
\usetikzlibrary{decorations.pathmorphing}
\usepackage[round]{natbib}
\usepackage[osf]{libertine}
\usepackage{microtype}

\usepackage{mleftright}

\usepackage{enumitem}
\setlist[itemize]{leftmargin=0pt,itemindent=1em,itemsep=2ex}
\setlist{nosep} % or \setlist{noitemsep} to leave space around whole list

\newcommand{\setmuskip}[2]{#1=#2\relax}
\setmuskip{\thinmuskip}{1.5mu} % by default it is equal to 3 mu
\setmuskip{\medmuskip}{2mu} % by default it is equal to 4 mu
\setmuskip{\thickmuskip}{3.5mu} % by default it is equal to 5 mu

\setlength{\parindent}{0cm}
\setlength{\parskip}{1ex}
%\renewcommand{\baselinestretch}{1.3}
%\setlength{\tabcolsep}{0pt}
%\renewcommand{\arraystretch}{1.0}

\def\argmax{\operatornamewithlimits{argmax}}
\def\argmin{\operatornamewithlimits{argmin}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\given{\,\middle\vert\,}
\def\proba{\operatorname{P}}
\newcommand{\seq}{{S}}
\newcommand{\expect}{\mathds{E}}
\newcommand{\variance}{\mathds{V}}
\newcommand{\empexpect}{\hat{\mathds{E}}}
\newcommand{\mutinf}{\mathds{I}}
\newcommand{\empmutinf}{\hat{\mathds{I}}}
\newcommand{\entropy}{\mathds{H}}
\newcommand{\empentropy}{\hat{\mathds{H}}}
\newcommand{\ganG}{\mathbf{G}}
\newcommand{\ganD}{\mathbf{D}}
\newcommand{\ganF}{\mathbf{F}}

\newcommand{\dkl}{\mathds{D}_{\mathsf{KL}}}
\newcommand{\djs}{\mathds{D}_{\mathsf{JS}}}

\newcommand*{\vertbar}{\rule[-1ex]{0.5pt}{2.5ex}}
\newcommand*{\horzbar}{\rule[.5ex]{2.5ex}{0.5pt}}

\def\positionalencoding{\operatorname{pos-enc}}
\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

\today

\vspace*{2ex}

\centerline{\color{red}(work in progress, to be updated)}

\medskip

\centerline{\url{https://fleuret.org/public/culture/culture.pdf}}

\end{center}

\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.

\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 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.

\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}

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.
%
\birdpic{pics/examples_train.png}{}
%

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.

\subsection{Culture quizzes}

This procedure results in the discovery of patterns which are not
present in the original quizzes:

\begin{example}

\birdpic{pics/4_birds_1.png}{}

\birdpic{pics/5_birds_1.png}{}

\birdpic{pics/6_birds_1.png}{}

More birds.

\end{example}

\separator

\begin{example}

\birdpic{pics/other_shapes_2.png}{}

\birdpic{pics/other_shapes_3.png}{}

New bird shapes.

\end{example}

\separator

\begin{example}

\birdpic{pics/other_shapes_1.png}{}

\birdpic{pics/occlusions_1.png}{}

Occlusions.

\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

\medskip

\centerline{\url{https://fleuret.org/git/culture}}

The experiments are done with a GTX 4090.

The GPT used has 37M parameters and the following structure:

\begin{center}
\begin{tabular}{lc}
    \texttt{dim\_model}  & 512  \\
    \texttt{dim\_keys}   & 64   \\
    \texttt{dim\_hidden} & 2048 \\
    \texttt{nb\_heads}   & 8    \\
    \texttt{nb\_blocks}  & 12
\end{tabular}
\end{center}

Adam, $\eta = 1e-4$, no scheduling.

There are $N_{\text{train}}=250'000$ original quizzes for training and
$N_{\text{test}} = 10'000$ for test.

At each epoch, for both train and test samples, we mix original
quizzes and the generated ones.

For training for instance, if there are less than $N_{\text{train}}/2$
new quizzes, we take all of them, otherwise we sample
$N_{\text{train}}/2$ of them without replacement, and then we sample
without replacement enough original quizzes to get $N_{\text{train}}$
samples in total.

We proceed similarly to get $N_{\text{test}}$ samples for test.

\end{document}