# Solving Visual Analogies using Neural Algorithmic Reasoning

Atharv Sonwane111corresponding author at<EMAIL_ADDRESS>
Work done as part of an internship at TCS Research 1, Gautam Shroff 2,
Lovekesh Vig 2,
Ashwin Srinivasan 1, Tirtharaj Dash 1
1 APPCAIR, BITS Pilani, K.K. Birla Goa Campus
2 TCS Research, New Delhi

###### Abstract

We consider a class of visual analogical reasoning problems that involve
discovering the sequence of transformations by which pairs of input/output
images are related, so as to analogously transform future inputs. This program
synthesis task can be easily solved via symbolic search. Using a variation of
the ‘neural analogical reasoning’ approach of [1], we instead search for a
sequence of elementary neural network transformations that manipulate
distributed representations derived from a symbolic space, to which input
images are directly encoded. We evaluate the extent to which our ‘neural
reasoning’ approach generalizes for images with unseen shapes and positions.

This document contains (1) the extended abstract for our work accepted at the
AAAI-22 Student Abstract and Poster Program; (2) relevant supplementary
material. In particular, the supplementary material describes details of the
methodology adopted as well as additional results and observations. Note that
while notation in the extended abstract has been simplified for brevity, the
supplementary material makes use of much more extended formalism.

###### Contents

  1. 1 Extended Abstract
    1. 1.1 Introduction
    2. 1.2 Methodology
    3. 1.3 Results and Discussion
  2. 2 Detailed Methodology
    1. 2.1 Definitions
    2. 2.2 Algorithm
    3. 2.3 Latent Space
      1. 2.3.1 Encoder Decoder Architecture
      2. 2.3.2 Learning a Combined Representation Space
      3. 2.3.3 Image Setting
      4. 2.3.4 Handling Unseen Shapes
    4. 2.4 Transforms
    5. 2.5 Search
      1. 2.5.1 Classical Search
      2. 2.5.2 Guided Search
      3. 2.5.3 Rule Based Guidance
    6. 2.6 Data Generation
  3. 3 Further Results
    1. 3.1 Evaluation of Latent Space
    2. 3.2 Evaluation of Transform Correctness
      1. 3.2.1 Image to multi-hot setting
      2. 3.2.2 Image to Image setting
    3. 3.3 Evaluation of Latent Space Generalisation
    4. 3.4 Evaluation of Transform Generalisation
    5. 3.5 Evaluation of Search Performance

##  1 Extended Abstract

###  1.1 Introduction

We consider a class of simple visual reasoning tasks specified by pairs of
(input, output) images, all of which are related by the same unknown
transformation procedure. Given a new image, the task is to generate the
correct output in an analogous manner to the examples provided. We model this
task as a program synthesis problem, where the mapping between input and
output is represented by a composition of elementary transformations. Building
on previous program synthesis approaches which construct complex programs from
simpler primitives, we employ a variation on the neural algorithmic reasoning
[1] framework to replace elementary symbolic transformations with equivalent
neural networks, and examine if this leads to the generalisation which is the
basis of analogical reasoning.

We decouple representation learning from transform learning, first learning a
latent representation that captures key information from the input followed by
learning transforms inside this representation space for which input-output
examples have been given. Fig 1 provides an overview of our approach wherein
we search over possible combinations of primitives until one is found that
satisfies all the example pairs. This solution is thus a neural algorithm,
i.e., a composition of elementary neural networks, rather than a symbolic
program, corresponding to the unknown analogical relation, which we can then
apply to any query image to obtain an analogous result (output image).

###  1.2 Methodology

The images considered consist of simple shapes (from a 20 member set of
alphabets and polygons) placed on a $3\times 3$ grid while positional shifts
and shape conversions make up the elementary transforms with which to compose
our solutions.

Figure 1: Overview

##### Representation Learning

Let a latent space be characterised by an encoder $E$ that maps natural inputs
(e.g. images) to their latent representations (real-valued vectors). Since we
are interested in spaces that are rich enough to represent a wide variety of
shapes and sparse enough to represent concepts distinctly, we first construct
a space based on symbolic descriptions of the input images containing
information on the shapes and their positions in the 2D grid. For this, we
train an autoencoder $(\text{Encoder: }E_{s},\text{Decoder: }D_{s}$ on the
multi-hot (Boolean) vector representations of symbolic descriptions by
minimising the negative log-likelihood loss between the inputs and the
reconstructed vectors.

To be able to handle image inputs (denoted by $x$s), we train a CNN based
encoder $E_{x}$ to fit to the outputs of $E_{s}$ (with frozen weights) by
minimising the mean-squared-error over the encodings of images
$E_{x}(x^{(i)})$ and encodings of the corresponding symbolic vectors
$E_{s}(s^{(i)})$: $\text{MSE}\left(E_{x}(x^{(i)}),E_{s}(s^{(i)})\right)$.

To be able to handle shapes at test time that were not seen during training,
we also include an additional shape-label called unseen. We then train $E_{x}$
to map some set of shapes to the latent vectors generated by $E_{s}$
corresponding to the unseen labels.

##### Transform Training

We use single hidden layer MLPs as the neural transform networks
${\mathcal{T}_{i}}$s that manipulate the latent representations of the input
images where a transform refers to some spatial transformations on the
original space (images). For our experiments, we consider positional shifts in
the ordinal directions (e.g. shift-right moves each shape in the image one
grid-position to the right) and shape conversions (e.g. to-square converts
each shape in the image to a square). We construct a separate transform
network ${\cal T}_{i}$ for each such spatial transformation, and learn its
weights by minimising the negative log-likelihood between $D_{s}({\cal
T}(E_{s}(s^{(i)}))$ and the multi-hot vector corresponding to the symbolic
description of the transformed image, while keeping the encoder and decoder
weights frozen.

##### Program Evaluation

Figure 2: Pipeline

We define primitives as transforms or special operations (reset and out);
programs are sequences of such primitives. As shown in Fig. 2, the input image
is preprocessed to extract individual shapes by identifying the connected
components. Each isolated image is converted into a latent vector using the
encoder $E_{x}$ and stored in the input buffer. Algorithm 1 is applied and the
resultant latent vectors in the output buffer are converted to their symbolic
descriptions using $D_{s}$. The final image is constructed by drawing the
corresponding shapes and combining them into a single image. (In the case of
shapes marked as unseen in the symbolic description, we keep track of the
original shape from the input and use it to generate the output.)

1 Input: Set of latent vectors $z_{k}$s for input, program $P$

2 Output: Set of latent vectors for output

1: Let input = $\\{z_{k}\\}$, memory = $\emptyset$, output = $\emptyset$

2: for $i=1:\text{length}(P)$ do

3: if $P[i]$ = out then

4: output $\leftarrow$ output $\cup$ memory

5: else if $P[i]$ = reset then

6: memory $\leftarrow$ input

7: else

8: memory $\leftarrow\\{P[i](z_{k}),\forall z_{k}\in\text{memory}\\}$

9: return output

Algorithm 1 Program Execution

##### Searching for Solution

Given an (input, output) pair of images, we find the program that maps each
input shape to the corresponding shape in the output by performing an
exhaustive search over sequences of primitives. Various pruning measures are
built into the search to make it tractable.

###  1.3 Results and Discussion

We evaluate our proposed system using ratio of (input, output) pairs for which
a valid program is found. These pairs are generated from a dataset of 16743
programs (1000 programs for each length up to 20 with redundant programs
removed). Fig. 3 suggests that our system is able to find the correct
solutions for the complete dataset as well as all programs containing direct
compositions of transforms up to length 5, demonstrating that conceptual
integrity is maintained throughout successive transform application. This is
not the case when using a latent space based on an autoencoder trained on
images as opposed to multi-hot vectors, suggesting a well-structured embedding
space is particularly important in this setting.

Figure 3: Generalisation Experiments

We evaluate how well transforms $\mathcal{T}_{i}$s and image encoder $E_{x}$
can generalise by withholding shapes during training and including them during
evaluation. Note that when evaluating transforms with varying number of seen
shapes, the encoder and decoder have seen all 20 shapes during training. When
evaluating the encoder, the unseen label is used in addition to the labels
corresponding to images seen during transform training; for this experiment,
of the 20 shapes available, 4 have labels included in the symbolic
descriptions while the rest are considered to have the label unseen. From Fig.
3, we see that performance improves with more shapes seen during training (as
expected). However, the system is able to generalise since it finds a valid
programs a significant portion of the time even when observing very few shapes
during training. We observe similar results when evaluating generalisation to
unseen grid-positions occupied by the shapes.

While our approach is limited by the use of classical algorithms for shape
extraction as well as the mechanism for handling unseen shapes within a fixed
symbolic code, we demonstrate within-domain generalisation capabilities
(shapes seen during training the encoder but not transforms). Our approach,
based on manipulating latent space representations, is, we submit, a step
towards fully neural analogical reasoning with out-of-domain generalisation.

Supplementary Materials

##  2 Detailed Methodology

The ability to recognize and make analogies is often used as a measure of or
to even test human intelligence [2]. We consider a simplified representative
problem wherein the system need to identify and apply visual analogies from
input output pairs of images related by some spatial transformation.

We are given some $k$ (input, output) image pairs as examples of a spatial
transformation. Here the images consist of simple shapes (from 20 member set
of alphabets and polygons) placed on a $3\times 3$ grid while the spatial
transformation are composed of simpler elementary transformations consisting
of grid position shifts (e.g. `shift-right`) and shape conversions (e.g. `to-
circle`). We are also given a query image, on which we must apply the spatial
transformation of which the preceding pairs are examples and generate the
output.

We model this as a program synthesis problem where the analogous relationships
(spatial transformations) are modeled as compositions of elementary
primitives. We employ a variation on the neural algorithmic reasoning [1]
framework to replace elementary symbolic transformations with equivalent
learned neural network transforms which manipulate latent representations of
the input data. While [1] propose learning a representation together with
neural algorithms acting on abstract data, we decouple representation learning
from transform learning, first learning a latent representation that captures
key information from the input followed by learning transforms inside this
representation space for which input-output examples have been given.

###  2.1 Definitions

We consider two domains, $S$ denoting the space of symbolic descriptions of
individual shapes in the image and $X$ denoting the space of images. Since
images we are considering consist of some number of shapes placed on cells in
an implicit grid, symbolic descriptions for each shape consist of the shape
label and its position. We will be using the following variants of the above
domains to describe images. $\mathbf{S}=\mathcal{P}(S)$ to denote the space of
sets of symbolic descriptors (since an image may have more than one shape) and
$\mathbf{X}=\mathcal{P}(X)$ where
$\forall\mathbf{x}\in\mathbf{X},|\mathbf{x}|=1$ to denote the set of single
element sets of images (this is necessary to maintain consistency in notation
that an image is described by a set).

Let the space of board states be defined as $B=\mathbf{S}\times\mathbf{X}$ so
that a board state $b\in B$ is a two-tuple $b=(\\{s_{k}\\},\\{x\\})$ composed
of a set of symbolic descriptors $s_{k}\in S\ \forall k$ for each shape in the
given board and the image representation $x\in X$ of the board (given as a the
only image in a set).

Let a latent space be defined as a 2-tuple $L(Z)=(E^{Z},D^{Z})$ where
$E^{Z}:Z\rightarrow\mathcal{P}(R^{n})$, $D_{L}:\mathcal{P}(R^{n})\rightarrow
Z$ such that $\forall z\in Z,D^{L}(E^{L}(z))=z$. We will consider two such
latent spaces, $L(\mathbf{X})$ over the space of single element images sets
$\mathbf{X}$ and $L(\mathbf{S})$ over the space of sets of symbolic
descriptions $\mathbf{S}$. Note that the encoders and decoders work over sets
since we are defining our board state as a set of objects.

The symbolic encoder and decoder will work element-wise over the input set to
produce the output set. The image encoder will take the only element of the
input set and generate as output a set of encoding for all shapes present in
the image and the decoder will do the reverse.

Let a program state be defined as 3-tuple $PS(Z)=(I,M,O)\in Z\times Z\times Z$
where $I$, $M$, $O$ denote the input, memory and output set respectively and
$Z$ can be any space such as $B$ or the internal representations from latent
spaces such as $L(\mathbf{X})$ or $L(\mathbf{S})$.

We define primitives as mappings between programs states $T:PS(Z)\rightarrow
PS(Z)$. Transforms are defined as a special type of primitive which only
modify the contents of the memory $M$ and leave the input $I$ and output $O$
unchanged. Apart from transforms, the only two primitives currently considered
are: out to denote copying all elements of memory $M$ to the output $O$ and
reset to denote resetting of contents of memory $M$ with the input $I$.

A program $P$ is defined as a composition of primitives $P=T_{1}\circ
T_{2}\circ\ldots\circ T_{n}$ such that $P(a)=T_{n}(...(T_{2}(T_{1}(a))))\
\forall a\in PS(Z)$. The procedure for applying a program to an input board
state is given in Algorithm 3.

An example $\lambda$ is defined as a 2-tuple $\lambda=(b_{i},b_{o})$ composed
of the input and output board states. A task $\omega$ is defined as a 2-tuple
$\omega=(\\{\lambda_{i}\\},q)$ composed of a set of examples of a program $P$
and $q\in B$ being the query board state for which we need to be find the
result on applying $P$.

Note that both the image and symbolic representations are included in board
states so that algorithms can be written in a general manner independent of
underlying domain. Which representation is to be used is selected according to
the latent space in consideration. If this is known before hand (as in the
case of final evaluation), during the creation of the tuples, the irrelevant
representation can be kept empty since we know it will not be selected.

###  2.2 Algorithm

The formalised algorithm corresponding to the procedure demonstrated in Figure
1 is shown below

Input: Search procedure: search, Max Depth: $d$, Latent Space:
$L=(E^{Z},D^{Z})$ Transforms : $T^{Z}=\\{T^{Z}_{i}\\}$, Dataset of Tasks:
$D_{T}=\\{\omega_{k}\\}$ where $\omega=(\\{\lambda_{i}\\},q)$

Output: Solutions

1 solutions $\leftarrow$ [ ];

2 for  _$(\\{\lambda_{i}\\},q)_{k}\in D_{T}$_ do

3 P $\leftarrow$ search($d$, $L(Z)$, $T^{Z}$, $\\{\lambda_{i}\\}$)

4 if  _P is not None_ then

5 g $\leftarrow$ apply_program(P, $q$, $L(Z)$);

6 solutions.add(g);

7

8 else

9 solutions.add(None);

10

11 end if

12

13 end for

return solutions;

Algorithm 2 General Algorithm for Solving Analogical Reasoning Tasks

Input: Program: $P=[T_{1},T_{2},\ldots,T_{n}]$, Input Board State:
$q=(\\{s^{q}_{k}\\},\\{x^{q}\\})$, Latent Space: $L(Z)=(E^{Z},D^{Z})$

Output: Board State $g=(\\{s^{g}_{k}\\},\\{x^{g}\\})\in B$ obtained after
applying $P$ to $q$

1 encodings $=\\{e_{j}\\}$ $\leftarrow$ $E^{Z}($filter$(q,L(Z))$

2 for  _$e_{j}\in encodings$_ do

3 decodings $\leftarrow\emptyset$ ;

4 memory $\leftarrow e_{j}$;

5 for  _$i=1:\text{length}(P)$_ do

6 $T_{k}=P[i]$

7 if  _$T_{k}=$ out_ then

8 decodings $\leftarrow$ decodings $\cup$ memory;

9 else if  _$T_{k}=$ reset_ then

10 memory $\leftarrow e_{j}$;

11 else

12 memory $\leftarrow$ $T_{k}$(memory) // implied that $T_{k}$ is working on
complete program state;

13 end if

14

15 end for

16

17 end for

18output $=(\\{s^{g}_{k}\\},\\{x^{g}\\})$ $\leftarrow$
unfilter($D^{Z}$(decodings), $L(Z)$)

return output;

Algorithm 3 apply_program

filter is used to choose which (out of symbolic or image) representation to
use out of a board state and unfilter is used to construct a board state given
only either symbolic or image representation.

###  2.3 Latent Space

####  2.3.1 Encoder Decoder Architecture

To obtain a latent space over some representation $Z$, we need to learn an
Encoder and Decoder of the form $E^{Z}:Z\rightarrow\mathcal{P}(R^{n})$ and
$D^{Z}:\mathcal{P}(R^{n})\rightarrow Z$ respectively. Since Z is either
$\mathbf{S}$ or $\mathbf{X}$, elements of which are sets, the encoder and
decoder need to work with sets as their inputs and outputs. In the symbolic
case, we assume that the encoder and decoder neural networks act elementwise
on the input sets to produce the output set. In the image setting, elements of
$\mathbf{X}$ contain an image as their only element. There are three ways that
this can be tackled -

  1. 1.

Splitting up an image containing multiple shapes into multiple images
containing single shapes using connected-component based image processing
methods.

  2. 2.

Using an encoder architecture (such as RNN) which can take the image as input
and output a set of latent embedding (each corresponding to one of the shapes
in the image).

  3. 3.

Using only a single latent embedding for the complete image.

Currently we are making use of the first method.

####  2.3.2 Learning a Combined Representation Space

##### Symbolic to Symbolic Setting

Figure 4: Multi-hot vector representation of symbolic descriptions

We obtain a latent space derived from an auto-encoder trained on the symbolic
space $\mathbf{S}$ as
$L(\mathbf{S})=(E^{\mathbf{S}}_{\psi},D^{\mathbf{S}}_{\phi})$ where
$E^{\mathbf{S}}_{\psi}:\mathbf{S}\rightarrow\mathcal{P}(R^{n}$) and
$D^{S}_{\phi}:\mathcal{P}(R^{n})\rightarrow\mathbf{S}$ apply neural networks
parameterised by $\psi$ and $\phi$ to the input set in element-wise manner to
generate the output set. To be able to input the symbolic descriptions into
the Neural Networks, we first convert them into a multi-hot vector of length
$|N|+2*S$ where $N$ is the set of shapes and $S$ is the size of the board. The
multi-hot vector is made up of 3 concatenated one-hot vectors, one for
denoting shape, one for x-coordinate and another for y-coordinate as seen in
Figure 4

In this setting, $\psi$ and $\phi$ are obtained via gradient descent on a
combination of negative-log-likelihood loss functions as follows -

$\mathcal{L}_{S}(g,t)=\Sigma_{k\in\\{\text{shape},\text{x},\text{y}\\}}-\log(\dfrac{e^{g^{k}_{\text{argmax}(t)}}}{\Sigma_{i}e^{g^{k}_{i}}})$
(1)

$\psi,\phi=\operatorname*{argmin}_{\psi,\phi}\Sigma_{s\in
S}\mathcal{L}_{S}(\hat{s},s)\text{ where
}\\{\hat{s}\\}=(D^{S}_{\phi}(E^{S}_{\psi}(\\{s\\}))$ (2)

####  2.3.3 Image Setting

There are two ways to learn the Latent Space in the case of the Image Setting.
Either to base it off the Latent Space from the symbolic setting
$L(\mathbf{S})$ or to obtain a completely new Latent Space for the Image
setting in the same way as subsubsection 2.3.2 (by training an autoencoder
followed by the transforms).

Training Encoder to Target $L(S)$

Figure 5: Procedure for obtaining image encoder using latent representation
space based on symbolic descriptions

We can make use of $L(\mathbf{S})$ when inputs and outputs are images by
learning $E^{\mathbf{X}}_{\psi}:\mathbf{X}\rightarrow\mathcal{P}(R^{n})$ which
applies a CNN based Neural Network to the only element image of the input set
to fit to the outputs of the symbolic setting encoder $E^{\mathbf{S}}_{\psi}$
from subsubsection 2.3.2 as follows -

$\psi=\operatorname*{argmin}_{\psi}\Sigma_{(\\{s_{k}\\},\\{x\\})\in
B}\dfrac{1}{2}(E^{\mathbf{X}}_{\psi}(\mathit{\\{x\\}})-E^{\mathbf{S}}_{\psi_{\mathbf{S}}}(\\{s_{k}\\}))^{2}$
(3)

This is demonstrated in Figure 5. Note the subscript to $\psi_{\mathbf{S}}$ to
denote that these weights are from the symbolic space encoder and are distinct
from the $\psi$ used to parameters $E^{\mathbf{X}}_{\psi}$. Using this image
encoder and the decoder from $L(\mathbf{S}$), we construct a latent space
$L^{S_{1/2}}(\mathbf{X})=(E^{\mathbf{X}}_{\psi},D^{\mathbf{S}}_{\phi})$.

The decoder $D^{\mathbf{X}}_{\phi}:\mathcal{P}(R^{n})\rightarrow\mathbf{X}$ in
this setting can be trained in multiple ways. One being via a reconstruction
loss while keeping encoder weights fixed which gives the latent space
$L^{\mathbf{S}_{r}}(\mathbf{X})=(E^{\mathbf{X}}_{\psi},D^{\mathbf{X}}_{\phi})$
where the parameters obtained are -

$\phi=\operatorname*{argmin}_{\phi}\Sigma_{(\\{s_{k}\\},\\{x\\})\in
B}\dfrac{1}{2}(D^{\mathbf{X}}_{\phi}(E^{\mathbf{X}}_{\psi}(\\{x\\}))-\\{x\\})^{2}$
(4)

Another being via the sandwich loss approach which gives the Latent Space
$L^{\mathbf{S}_{s}}(\mathbf{X})=(E^{\mathbf{X}}_{\psi},D^{\mathbf{X}}_{\phi})$
with parameters learnt as -

$\phi=\operatorname*{argmin}_{\phi}\Sigma_{(\\{s_{k}\\},\\{x\\})\in
B}\dfrac{1}{2}(E^{\mathbf{X}}_{\psi}(D^{\mathbf{X}}_{\phi}(\tilde{h}_{i}))-\\{\tilde{h}_{i}\\})^{2}$
(5) $\\{\tilde{h}_{i}\\}=E^{\mathbf{X}}_{\psi}(\\{x\\})$ (6)

While in the proposed system, we reconstruct images from latent embeddings by
first decoding to symbolic descriptions using $D^{\mathbf{S}}_{\phi})$ and
then redraw those images according to these descriptions, the above approaches
demonstrate that a end to end neural system is possible.

Obtaining a new Latent Space based on Image Setting
Here we obtain a new Latent Space
$L^{a}(\mathbf{X})=(E^{\mathbf{X}}_{\psi},D^{\mathbf{X}}_{\phi})$ by training
an autoencoder as given below and then training transforms in a similar
fashion to Equation 2

$\psi,\phi=\operatorname*{argmin}_{\psi,\phi}\Sigma_{\mathbf{x}\in\mathbf{X}}\dfrac{1}{2}(D^{\mathbf{X}}_{\phi}(E^{\mathbf{X}}_{\psi}(\mathbf{x}))-\mathbf{x})^{2}$
(7)

####  2.3.4 Handling Unseen Shapes

To be able to handle unseen shapes in the $L^{S_{1/2}}(\mathbf{X})$ setting,
some additional measures need are taken. Since a multi-hot vector is used to
represent symbolic descriptions of board elements while training the
$E^{\mathbf{S}}$ and $D^{\mathbf{S}}$ in $L^{S_{1/2}}(\mathbf{X})$, it can
only accommodate a finite set of shapes. To be able to handle any number of
shapes, we add another shape class to the multi-hot vector for unseen shapes.
This can be further generalised by removing the shape part from the the multi-
hot completely. The issue then becomes, if there are multiple different shapes
on the board, how do we tell them apart when the encoding contains no
information about shape classes but only point positions. To handle this we
keep track of which image corresponds to which latent embedding in the memory
and output buffers. When trying to match if the multi-hot generated as output
matches the targets, we make use of a distance metric between the image of the
shapes corresponding to the generated and target multi-hots as described in
subsection 2.5.

###  2.4 Transforms

Independent NNs for Transforms

Figure 6: Procedure for training transforms

As shown in Figure 6, we obtain a set of transforms
$T^{\mathbf{S}}_{\theta}=\\{T^{\mathbf{S}}_{i,\theta_{i}}\\}$ over the latent
space $L(\mathbf{S})=(E^{\mathbf{S}}_{\psi},D^{\mathbf{S}}_{\phi})$ where each
$T^{\mathbf{S}}_{i,\theta_{i}}:\mathcal{P}(R^{n})\rightarrow\mathcal{P}(R^{n})$
applies a neural network parameterised by $\theta_{i}$ in an element-wise
manner to input set to generate output set. The parameters $\theta_{i}$ are
obtained via gradient descent on some loss function (either from Equation 1 or
MSE) while keeping weights of the encoder and decoder frozen.

$\theta_{i}=\operatorname*{argmin}_{\theta}\Sigma_{b\in B}\\\
\mathcal{L}(D^{\mathbf{S}}_{\phi}({\tt
apply_{p}rogram}([T^{\mathbf{S}}_{i,\theta},{\tt out}],b,L(\mathbf{S}))),{\tt
filter}(\bar{T}_{i}(b),L(\mathbf{S})))$ (8)

Vectors for Transforms
An alternative to training separate sets of weights for each transforms is
learning a vector $v_{i}\in R^{k}$ for each $T^{\mathbf{S}}_{i}$ along with a
main transform network $T^{\mathbf{S}}_{\theta}:\mathcal{P}(R^{n})\times
R^{k}\rightarrow\mathcal{P}(R^{n})$ which takes as input both the transform
vector $v_{i}$ and the input set and generates the output set via element-wise
application.

The apply_program procedure can be modified for this setting into
apply_program_vectors by taking $T^{\mathbf{S}}_{\theta}$ as an additional
input $T$ and changing all instances of $T_{k}(memory)$ to $T(memory,v_{k})$.
The parameters $\theta$ and the transform vectors $\\{v_{i}\\}$ can be learnt
via -

$\theta_{i},\\{v_{i}\\}=\operatorname*{argmin}_{\theta,\\{v_{i}\\}}\sum_{b\in
B}\mathcal{L}(D^{\mathbf{S}}_{\phi}({\tt
apply_{p}rogram_{v}ectors}([v_{i},{\tt
out}],T^{\mathbf{S}}_{\theta},b,L(\mathbf{S}))),\ {\tt
filter}(\bar{T}_{i}(b),L(\mathbf{S})))$ (9)

We use the Independent NNs for Transforms method in our proposed approach but
experimented with the above as an alternative.

###  2.5 Search

Algorithm 4 is used to check whether a program using a certain latent space
satisfies all examples in a given set.

Input: List of Examples: $\\{\lambda_{i}\\}$ Program: $P$, Latent Space:
$L(Z)=(E^{Z},D^{Z})$

Output: Whether $P$ satisfies all the examples in $B$

1 found $\leftarrow$ True;

2 for  _$(b_{i},b_{o})\in\\{\lambda_{i}\\}$_ do

3 if  _$b_{o}$ $\neq$ apply_program(P, $b_{i}$, $L(Z)$)_ then

4 found $\leftarrow$ False;

5 break;

6

7 end if

8

9 end for

return found;

Algorithm 4 satisfies

Note that the equality check here is non-trivial. Since the input output pairs
can be given in any format (including natural representations such as images),
there may not be a straightforward way to check if the generated output
matches target output. In the case of images, we can make use of some
continuous distance function and set some threshold below which two images can
be considered equal. Options for the distance function includes -

  * •

Pixel based matching - two images are the same if their pixel values are
exactly equal. While this works when using a symbolic system such as
$L^{S_{1/2}}(\mathbf{X})$ described in subsubsection 2.3.4 since output is
constructed from shapes in the input, it will not work when images are
generated by a decoder.

  * •

Mean squared distance. This was tried in practice and seemed to work for
simple shapes (squares, triangles etc…) but required careful tuning of the
threshold each time the autoencoder was retrained.

  * •

$||H-I||$ where $H$ is the homography [3] between the detected and matching
keypoints for two images which computes the amount of scaling, shearing and
translation required to transform one image into another. This is a more
appropriate metric since it explicitly takes into account the amount of
spatial difference between individual shapes rather than just the difference
in pixel values. (This is the method currently used for images).

  * •

Learned distance function which could be trained in the style of a Siamese
network.

We make use of the homography based option in our approach.

####  2.5.1 Classical Search

The simplest search procedure that can be used in Algorithm 2 to find a
program that satisfies a given set of examples would be a exhaustive breadth
first search upto some depth is given in Algorithm 5.

Input: Max Depth: $d$, Latent Space: $L(Z)=(E^{Z},D^{Z})$ Transforms:
$T^{Z}={T^{Z}_{i}}$, List of Examples: $\\{\lambda_{i}\\}$

Output: Program that satisfies all given examples

1 q $\leftarrow$ LIFO(); q.push([ ])

2 while  _True_ do

3 program $\leftarrow$ q.pop();

4 if  _length(program) = $d$_ then

5 return None;

6 end if

7 for  _$t_{i}\in T^{Z}$_ do

8 new_program $\leftarrow$ program + $t_{i}$;

9 found $\leftarrow$ satisfies($\\{\lambda_{i}\\}$, new_program, $L(Z)$);

10 if  _found_ then

11 return new_program;

12 end if

13 q.push(new_program);

14

15 end for

16

17 end while

Algorithm 5 Limited Depth Exhaustive BFS

The naive implementation of BFS evaluates every possible sequence of
transforms. With a branching factor of 8 (4 shift operations, 4 change shape
operations), this implementation becomes intractable on our systems for
searching for programs of length greater than 5. However, since we have both
the final board as well as the initial board available during search,
extensive pruning of the search tree is possible to reduce the effective
branching factor significantly. The following measures were taken for pruning
-

  * •

If the current output buffer contains an element not present in target output,
prune the current branch.

  * •

Keeping track of the maximum number of matches with the target output so far
by any branch. If a new branch has fewer matches than the maximum, it is
pruned.

Along with this, we reduce the constant factor involved at each step by
keeping track of the program state after partial execution. This creates a
significant reduction in time taken since the majority of it is the neural
network forward passes. This means that transforms are only applied when a new
transform is added to the program. We do the same for output decoding - only
applying output decoder whenever the `out` primitive is called and keeping
track of output buffer in subsequent nodes. The pruned version is described in
Algorithm 6

Input: Max Depth: $d$, Latent Space: $L(Z)=(E^{Z},D^{Z})$ Transforms:
$T^{Z}={T^{Z}_{i}}$, List of Examples: $\\{\lambda_{i}\\}$

Output: Program that satisfies all given examples

1 q $\leftarrow$ LIFO(); q.push([ ])

2 while  _True_ do

3 program $\leftarrow$ q.pop();

4 if  _length(program) = $d$_ then

5 return None;

6 end if

7 for  _$t_{i}\in T^{Z}$_ do

8 new_program $\leftarrow$ program + $t_{i}$;

9 found $\leftarrow$ satisfies($\\{\lambda_{i}\\}$, new_program, $L(Z)$);

10 if  _found_ then

11 return new_program;

12 end if

13 q.push(new_program);

14

15 end for

16

17 end while

Algorithm 6 Pruned BFS

####  2.5.2 Guided Search

While an exhaustive search is guaranteed to find the solution program (if it
exists), it makes no use of the given set of examples $\\{\lambda_{i}\\}$
during search apart from end checking and can become intractable for more
complex settings (even with pruning). With our transforms being primarily
based on spatial concepts, the input, output pair together contain information
about the solution program which may be used to guide the search.

Formally, we want to model the distribution over programs given a set of
examples as $P(T_{1},T_{2},...,T_{n}|\\{\lambda_{i}\\})$. We can factorise
this distribution over the complete sequence into one made up of distributions
over next step -

$P(T_{1},T_{2},...,T_{n}|\\{\lambda_{i}\\})=P(T_{1}|\\{\lambda_{i}\\})\Pi_{i=2}^{n}P(T_{i}|\\{\lambda_{i}\\},T_{1},...,T_{i-1})$
(10)

This model can them be used to score program in a beam search as follows -

Input: Max Depth: $d$, Latent Space: $L(Z)=(E^{Z},D^{Z})$ Transforms:
$T^{Z}=\\{T^{Z}_{i}\\}$, List of Examples: $\\{\lambda_{i}\\}$, Program
Likelihood Model: $P$ Beam width: $k$

Output: Program that satisfies list of examples

1 beam $\leftarrow$ [$\phi$]; i $\leftarrow$ 0;

2 while  _i ¡ d_ do

3 for  _program in beam_ do

4 for  _$t$ in $T$_ do

5 new_program $\leftarrow$ program + $t$;

6 found $\leftarrow$ satisfies($\\{\lambda_{i}\\}$, new_program, $L(Z)$);

7 if  _found_ then

8 return new_program;

9 end if

10 beam.add(new_program);

11

12 end for

13

14 end for

15 beam $\leftarrow$ select_top_k(beam, $P$, $k$, $\\{\lambda_{i}\\}$); i++;

16

17 end while

return None;

Algorithm 7 Guided Beam Search

One way to formulate the `select_top_k` procedure is by simply choosing
programs with highest likelihoods.

####  2.5.3 Rule Based Guidance

As an initial step, we consider using hardcoded rules to build the
distribution $P(T_{1},T_{2},...,T_{n}|\\{\lambda_{i}\\})$. Since our input and
output consists of a set of shapes, the simplest strategy is to score each
program according to the number of matches between its output set and the
target output. This is very similar to the pruning strategy used for making
exhaustive search more tractable. Additionally, programs with shape conversion
to a shape present in the target output are given higher scores.

###  2.6 Data Generation

Random examples can be generated by applying a randomly generated program to a
randomly selected board. During generation of the program, constraints are
applied (no consecutive shape conversion transforms, no consecutive `out` or
`reset` operations, all programs must end with an `out` operation, `reset`
operations must follow an `out` operation) to minimise the generation of any
redundant programs. When generating a set of random examples, it is also
ensured that all examples generated are unique.

In this manner, we prepare two main datasets of programs. `R20ALL` refers to a
dataset of 16743 randomly generated programs containing 1000 programs of
length 5 to length 20, 1 of length 1, 9 of length 2, 74 of length 3 and 659 of
length 4 (total number of possible sequences under given constraints for those
lengths). `R20SHIFT` refers to a similar dataset as above but where programs
contain only the shift operations along with `out` and `reset`. This contains
a total of 15620 programs. During evaluation, we generate a dataset of
examples by pairing randomly selected board with randomly selected programs
from the above datasets.

##  3 Further Results

We consider the following factors with regards to our system in both the image
to multi-hot ($L^{S_{1/2}}(\mathbf{X})$) and image-to-image
($L^{a}(\mathbf{X})$) settings -

  * •

How well are the transforms manipulating the latent space correctly?

  * •

How well are the transforms generalising to unseen shapes and positions?

  * •

How well is the latent space (encoder and decoder) generalising to unseen
shapes and positions?

  * •

Performance of the search procedures

###  3.1 Evaluation of Latent Space

(a) Image autoencoder

(b) Image autoencoder with smaller CNN

(a) Ohe-hot autoencoder

(b) Ohe-hot autoencoder with mean-squared distance loss

Figure 8: TSNE Plots for Latent Embedding. Each point represents an embedding
for a specific board element consisting of a single shape in a grid position
on the board. The left hand plots have points coloured according to position
and right hand plots according to grid position.  Figure 9: Reconstruction
Examples using $L(S)$

In our system, the elements on which computation is to be done are latent
embeddings in some vector space $R^{k}$ of the actual inputs (images or
symbolic descriptions). Such a space is obtained by learning an autoencoder
described in subsubsection 2.3.2. It is important that this space is amenable
to this computations. We utilise t-SNE to visualise and compare the
distribution of latent embeddings in different cases in Figure 8.

For the plot we can see that embeddings in the multi-hot space are much more
structured than in the image space. This could be due to the difference in
loss function (negative log-likelihood in the case of the multi-hots and mean-
squared-distance in the case of the images). When using mean-squared distance
loss for training the $L(S)$, we can see that the clusters for each position
are much more tightly grouped, thus while it is clear on how to distinguish
between positions, different shapes become indistinguishable. Another
interesting phenomenon however is that while the space when using the smaller
CNN is more structured, it also performs much worse in reconstruction only
producing vague black shapes in the correct positions as compared to the
almost perfect reconstructions of the larger autoencoder as seen in Figure 9.

###  3.2 Evaluation of Transform Correctness

####  3.2.1 Image to multi-hot setting

To evaluate to what degree the transforms manipulate the latent space in the
correct way, we apply Algorithm 5 with transforms trained according to
Equation 2 on the dataset of examples (as described in subsection 2.6). The
hit-ratio is defined as the ratio of examples for which a program was found
that gave the correct output from the given input. Note that the generated
program may be different from the program used to create the example since
multiple programs may be possible for a give input and output pair.

Evaluating transforms trained in $L(\mathbf{S})$ on programs with upto 6
consecutive shift transformations gives a perfect hit-ratio of 1.0. This
indicates that these transforms can manipulate the latent embeddings
accurately upto a length of 6. Similar evaluation was done on the transforms
as vector (described in subsubsection 2.3.2) setting. The results are
displayed in Table 1

Length of Sequence | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
Single Object Independent Transform | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
Single Object Vector as Transform | 1.0 | 0.85 | 0.725 | 0.64 | 0.52
Table 1: Accuracy of transforms trained in symbolic (multi-hot) setting with
frozen latent space trained as autoencoder

####  3.2.2 Image to Image setting

Figure 10: Reconstruction Example for image-to-image autoencoder

Training transforms in $L^{a}(\mathbf{X})$ with a loss similar to Equation 2
resulted in poorly performing transforms. For example, when two consecutive
shift-left transforms are applied to an latent embeddings of image with a
single square in the middle row and left column and the result is decoder, we
obtain the image in Figure 10. It is observed in general when using
$L^{a}(\mathbf{X})$ that consecutive application of transforms leads to loss
of conceptual information and the resultant image being incomprehensible. This
highlights the importance of sparse and structured latent spaces as obtained
by training on symbolic descriptions.

###  3.3 Evaluation of Latent Space Generalisation

To test how well the latent space (encoder and decoder) generalises to unseen
situations, we utilise a similar scheme as follows. Let us formally define it
as a tuple $(M,N,R,T)\in\mathcal{P}(Q)^{4}$ where $Q$ is the set of all shapes
that can be present on a board, $M$ denotes the shapes present in the training
data for the latent space (here $|M|+1+6$ denotes the size of the multi-hot
vector, here 6 is for the positional encoding and 1 is for a slot of unseen
shape), $N$ denotes the shapes present in the training data for transforms,
$R$ denotes the shapes present in the training data for the encoder and $T$
denotes the shapes present in the examples on which the latent space is being
evaluated.

We perform 4 experiments based on this evaluation scheme to test the
generalisation capabilities of the latent space $L^{S_{1/2}}(\mathbf{X})$
where the decoder is from $L(\mathbf{S})$ and the encoder is a CNN based
network trained to fit to the encoder from $E(\mathbf{S})$ as per Equation 3.
The results are given in Figure 11. Note that the total number of shapes
possible $|Q|=20$.
-

  1. 1.

For $M=N=\phi$ (all shapes considered unseen in the multi-hot) and $T=Q$ (all
shapes included in test examples), we vary the shapes shown to the CNN encoder
during training from $|R|=1$ (just one shape being included in training data)
$R=Q$ (all shapes included) and record the evaluation performance.

  2. 2.

For $M=N=\phi$ (all shapes considered unseen in the multi-hot), we vary the
shapes shown to the CNN encoder during training from $|R|=1$ (just one shape
being included in training data) $R=Q$ (all shapes included) and record the
evaluation performance of with this encoder on $T=R^{\prime}$ (test only
including shapes not present in train for encoder).

  3. 3.

For $M=N=\\{\text{square},\text{triangle},\text{circle},\text{delta}\\}$ (four
shapes + unseen in the multi-hot) and $T=Q$ (all shapes included in test
examples), we vary the shapes shown to the CNN encoder during training from
$|R|=1$ (just one shape being included in training data) $R=Q$ (all shapes
included) and record the evaluation performance.

  4. 4.

For $M=N=\\{\text{square},\text{triangle},\text{circle},\text{delta}\\}$ (four
shapes + unseen in the multi-hot), we vary the shapes shown to the CNN encoder
during training from $|R|=1$ (just one shape being included in training data)
$R=Q$ (all shapes included) and record the evaluation performance of with this
encoder on $T=R^{\prime}$ (test only including shapes not present in train for
encoder).

Figure 11: Generalisation of Latent Space to Unseen Shapes

###  3.4 Evaluation of Transform Generalisation

To test how well the learned transforms generalise to unseen situations in
$L^{S_{1/2}}(\mathbf{X})$, we train the autoencoder with all the data, then
train the transforms only on input, output pairs which have only a subset of
shapes (or input positions). Then during testing of the transforms on a
dataset of example programs, we include all shapes (or positions). This can be
thought of as keeping $M=R=T=Q$ while $N$ is varied from $Q$ to $\phi$. If the
transforms give similar performance to those trained with all the data, we can
say that they, together with the latent space, are generalising well. The
results for $L(\mathbf{S})$ are given in Figure 12.

Figure 12: Generalisation of Transforms to Unseen Positions and Shapes

###  3.5 Evaluation of Search Performance

Figure 13: Search Performance

The comparison between the running time performance of naive and pruned BFS
(both discussed in subsection 2.5) for program search is shown in Figure 13.
We an clearly see the difference in performance and that pruning makes
exhaustive search tractable when searching for longer programs.

Our simple rule based guidance was sufficient to make beam search with beam
width of 500 perform well (80%) upto search lengths of upto 15. Various other
rules could be tried here however the high performance with the above simple
rules gives sufficient evidence that a guidance system that understands the
examples and the programs will be able perform well with beam search.

## References

  * [1] Petar Veličković and Charles Blundell.  Neural algorithmic reasoning.  Patterns, 2(7):100273, 2021.
  * [2] Douglas R Hofstadter.  Fluid concepts and creative analogies: Computer models of the fundamental mechanisms of thought. Basic books, 1995.
  * [3] O. Chum, T. Pajdla, and P. Sturm.  The geometric error for homographies.  Comput. Vis. Image Underst., 97:86–102, 2005.