#  PatchGame: Learning to Signal
Mid-level Patches in Referential Games

Kamal Gupta
<EMAIL_ADDRESS>
&Gowthami Somepalli
<EMAIL_ADDRESS>
&Anubhav Gupta
<EMAIL_ADDRESS>
Vinoj Jayasundara
<EMAIL_ADDRESS>
&Matthias Zwicker
<EMAIL_ADDRESS>
&Abhinav Shrivastava
<EMAIL_ADDRESS>
University of Maryland, College Park Code is available at
https://kampta.github.io/patch-game.

###### Abstract

We study a referential game (a type of signaling game) where two agents
communicate with each other via a discrete bottleneck to achieve a common
goal. In our referential game, the goal of the speaker is to compose a message
or a symbolic representation of “important” image patches, while the task for
the listener is to match the speaker’s message to a different view of the same
image. We show that it is indeed possible for the two agents to develop a
communication protocol without explicit or implicit supervision. We further
investigate the developed protocol and show the applications in speeding up
recent Vision Transformers by using only important patches, and as pre-
training for downstream recognition tasks (e.g., classification).

##  1 Introduction

The ability to communicate using language is a signature characteristic of
intelligence [60]. Language provides a structured platform for agents to not
only collaborate with each other and accomplish certain goals, but also to
represent and store information in a compressible manner. Most importantly,
language allows us to build infinitely many new concepts by the composition of
the known concepts. These qualities are shared by both the natural languages
used in human-human communication and programming languages used in human-
machine communication. The study of the evolution of language can hence give
us insights into intelligent machines that can communicate [54].

Our goal in this paper is to develop and understand an emergent language,
_i.e._ , a language that emerges when two neural network agents try to
communicate with each other. Clark [14] argued that supervised approaches that
consist of a single agent learning statistical relationships among symbols
don’t capture the functional relationships between the symbols _i.e._ , the
use of symbols leading to an action or an outcome. Krishna et al. [43] argued
the same viewpoint in the context of images. We, therefore, resort to the
recent works in emergent language [5, 42, 74, 45, 30, 46] which show that a
communication protocol can be developed or learned by two or more cooperative
agents trying to solve a task. The choice of the task is quintessential since
the language derives meaning from its use [78]. We choose a task where two
agents, a speaker, and a listener, play a referential game, a type of
signaling game first proposed by Lewis [48]. The speaker agent receives a
target image and sends a message to the listener. The message consists of
discrete symbols or words, capturing different parts of the image. The
listener receives another view of the target image, and one or more distractor
images. The goal of the speaker and the listener agents is to maximize the
agreement between the message and the target image. Fig. 1 illustrates the
overview of the proposed referential game.

In computer vision, a number of attempts have been made to represent images as
visual words [38], with a focus on low-level feature descriptors such as SIFT
[49], SURF [6], _etc._. Recent works in deep learning have attempted to
describe the entire image with a fixed number of discrete symbols [58, 59,
63], however, we postulate that large images contain a lot of redundant
information and a good visual representation should focus on only the
“interesting” parts of the image. To discover what constitutes the interesting
part of the image, we take inspiration from the works on mid-level patches
[70, 37, 18], the patches in the image that are both representative and
discriminative [70, 28]. This means they can be discovered in a large number
of images (and hence representative), but simultaneously they should also be
discriminative enough to set an image apart from the other images in the
dataset. Hence, the speaker agent in our paper focuses on computing a symbolic
representation in terms of these mid-level patches, as opposed to the entire
image.

To summarize, we propose PatchGame, a referential game formulation where given
an image, the speaker sends discrete signal in terms of mid-level patches, and
the listener embeds these symbols to match them with another view of the same
image in the presence of distractors. Compared to previous works [30, 45, 22],
we make the following key changes:

  * •

Agents in the some of the prior works [30, 45, 22] have access to a pre-
trained network, such as AlexNet [44] or VGG [69], for extracting features
from images. In this work, the agents rely on training on a large scale image
dataset, and invariance introduced by various image augmentations, to learn
the language in a self-supervised way [53].

  * •

We propose a novel patch-based architecture for the speaker agent, which
comprises of two modules: (1) PatchSymbol, a multi-layered perceptron (MLP)
that operates at the patch-level and converts a given image patch into a
sequence of discrete symbols, and (2) PatchRank, a ConvNet that looks at the
complete image and ranks the importance of patches in a differentiable manner.

  * •

We introduce a novel transformer-based architecture for the listener agent,
consisting of two modules: (1) a language module that projects the message
received from the speaker to a latent space, and (2) a vision module that
projects the image into the latent space. We use a contrastive loss in this
latent space to train both the speaker and the listener agents simultaneously.

  * •

We propose new protocols to evaluate each of the speaker and listeners’
modules.

We assess the success of PatchGame via qualitative and quantitative
evaluations of each of the proposed component, and by demonstrating some
practical applications. First, we show that the speaker’s PatchRank model does
indicate important patches in the image. We use the top patches indicated by
this model to classify ImageNet [16] images using a pre-trained Vision
Transformer [19] and show that we can retain over 60% top-1 accuracy with just
half of the image patches. Second, the listener’s vision model (ResNet-18) can
achieve upto 30.3% Top-1 accuracy just by using k-NN ($k=20$) classification.
This outperforms other state-of-the-art unsupervised approaches [63, 28] that
learn discrete representations of images by 9%. Finally, we also analyze the
symbols learned by our model and the impact of choosing several
hyperparameters used in our experiments.

Figure 1: Overview of the Referential Game. We generate two random views of
every image in the given batch of images. The speaker takes one of the views
as the input and generates a sequence of symbols (or message). The listener
takes the message sent by the speaker and the second view of the image, and
projects both into an embedding space. Both the speaker and listener agents
learn by minimizing the constrastive loss (see Eq. 3) between between the
views in this embedding space.

##  2 Related Work

Referential games. Prior to the advent of deep learning, significant research
in the field of emergent communications has shown that a communication
protocol can be developed or learned by agents by playing a language game [5,
42, 74, 77, 4, 3, 2, 39]. However, the agents employed in these works were
typically located in a synthetic world and made several assumptions about the
world such as the availability of disentangled representations of objects with
discrete properties. More recent works [36, 23, 15, 75, 47, 73, 45, 46] have
employed deep learning methods to develop a discrete language for
communication between the agents. Lazaridou et al. [45] used neural network
agents represented by a MLP to communicate concepts about real-world pictures.
They used a fixed-sized message composed of a large vocabulary for their
communication. Evtimova et al. [22], Bouchacourt and Baroni [9], Havrylov and
Titov [30] relax this assumption and allow communication via variable-length
sequences. Havrylov and Titov [30] allows the speaker agent to use an LSTM
[33] to construct a variable-length message. Lazaridou et al. [46], Havrylov
and Titov [30] show that even when we allow agents to use variable-length
sequences to represent a message, they tend to utilize the maximum possible
sequence to achieve the best performance (in terms of communication success).

The idea of using a Gumbel-softmax distribution [34, 51] with the straight-
through trick [7] for learning a language in multi-agent environment was
concurrently proposed by Mordatch and Abbeel [56] and Havrylov and Titov [30].
They show that we can achieve a more stable and faster training by using this
technique as compared to reinforcement learning used in several other
approaches.

Evaluating emergent communication. Evaluating the emergent language turns out
to be an equally challenging research problem. Existing approaches use the
successful completion of the task or the correlation between learned language
and semantic labels as evaluation metrics. Lowe et al. [50] and Keresztury and
Bruni [40] show that simple task success might not be a good or sufficient
metric for evaluating the success of a game. They discuss heuristics and
advocate measuring both positive signaling and positive listening
independently to evaluate agents’ communication. Andreas [1] provides a way of
evaluating compositional structure in learned representations.

Discrete Autoencoders. In parallel to the works on emergent communication,
there is a large body of research on learning discrete representations of
images using some form of autoencoding or reconstruction [28, 58, 65, 62, 20,
57, 29, 63] without labels. The focus of VQ-VAE [58] and VQ-VAE-2 [63] is to
learn a discrete bottleneck using vector quantization. Once we can represent
any image with these discrete symbols, a powerful generative model such as
PixelCNN [58, 66], or transformer [76, 61] is learned on top of these symbols
to sample new images. PatchVAE [28] achieves the same using Gumbel-Softmax and
imposes an additional structure in the bottleneck of VAEs. We argue that
because of mismatch in the objectives of reconstruction and visual recognition
tasks, each of these models trained using reconstruction-based losses do not
capture meaningful representations in the symbols.

Self-supervised learning in vision. Self-supervised learning (SSL) methods,
such as [11, 81, 12, 10, 13, 55, 32, 26] have shown impressive results in
recent years on downstream tasks of classification and object detection. Even
though the bottleneck in these methods is continuous (and not discrete
symbols), these methods have been shown to capture semantic and spatial
information of the contents of the image. Unlike SSL methods, neural networks
representing the two agents in our case, do not share any weights. Also, note
that the continuous nature of representations learned by SSL techniques is
fundamentally different from the symbolic representations used in language.
And indeed, we show that a k-Nearest Neighbor classifier obtained from the
continuous representations learned by SSL methods can perform better than the
one obtained using Bag of Words (or symbols). However, to the best of our
knowledge, our work is one of the first attempts to make representations
learned in a self-supervised way more communication- or language-oriented.

Comparison with Mihai and Hare [53, 52]. [52, 53] extends Havrylov and Titov
[30] by training a speaker and listener agents end-to-end without using pre-
trained networks. However, the prior works [52, 52, 30] use a top-down
approach to generate discrete representation (or a sentence) for an image,
i.e., they compute an overall continuous embedding of the image and then
proceed by generating one symbol of the sentence at a time using an LSTM. The
computational cost of LSTMs is prohibitive when length of a sentence is large,
which is needed to describe complex images. The transformers, on the other
hand, require constant time for variable length sentences at the cost of
increased memory (in the listener agent). However, generating the variable
length sentences with the speaker agent using transformers is non-trivial. To
solve this, we propose a bottom-up approach, _i.e._ , we first generate
symbols for image patches and combine them to form a sentence. This approach
allows for computationally efficient end-to-end training. Further, it allows
the speaker to compose symbols corresponding to different parts of the image,
instead of deducing it from a pooled 1D representation of the image.

##  3 PatchGame

We first introduce various notations and the referential game played by the
agents in our work. We provide further details of architectures of the
different neural network agents, as well as the loss function. We also
highlight the important differences between this work and prior literature.
Code and pre-trained models to reproduce the results are provided.

###  3.1 Referential Game Setup

Fig. 1 shows the overview of our referential game setup. Given a dataset of
$N$ images $\\{\operatorname{\mathbf{x}}_{i}\\}_{i=1}^{N}$, we formulate a
referential game [48] played between two agents, a speaker
$\operatorname{S_{\theta}}$ and a listener $\operatorname{L_{\phi}}$ as
follows: As in the setting of Grill et al. [26], we generate two “random
views” for every image. A random view is generated by taking a $224\times 224$
crop from a randomly resized image and adding one or more of these
augmentations - color jitter, horizontal flip, Gaussian blur and/or
solarization. This prevents the neural networks from learning a trivial
solution and encourages the emergent language to capture invariances induced
by the augmentations. Given a batch of $B$ images, we refer to the two views
as $\\{\operatorname{\mathbf{x}}_{i}\\}_{i=1}^{B}$ and
$\\{\operatorname{\mathbf{x}}^{\prime}_{i}\\}_{i=1}^{B}$. In each iteration
during training, one set of views is presented to the speaker agent and
another set of the views is shown to the listener agent.

The speaker $\operatorname{S_{\theta}}$ encodes each image
$\operatorname{\mathbf{x}}_{i}$ independently into a variable length message
$\operatorname{\mathbf{m}}_{i}$. Each message $\operatorname{\mathbf{m}}$ is
represented by a sequence of one-hot encoded symbols with a maximum possible
length $L$ and a fixed size vocabulary $V$. The space of all possible messages
sent by the speaker is of the order $|V|^{L}$. The input to the listener
$\operatorname{L_{\phi}}$ is the batch of messages
$\\{\operatorname{\mathbf{m}}_{i}\\}_{i=1}^{B}$ from the speaker, and the
second set of random views of the batch of images. The listener consists of a
language module $\operatorname{\phi_{\text{text}}}$ to encode messages and a
vision module $\operatorname{\phi_{\text{vision}}}$ to encode images. The goal
of the listener is to match each message to its corresponding image.

Specifically, for a batch of $B$ (message, image) pairs,
$\operatorname{S_{\theta}}$ and $\operatorname{L_{\phi}}$ are jointly trained
to maximize the cosine similarities of $B$ actual pairs while minimizing the
similarity of $(B^{2}-B)$ incorrect pairs. For a target message
$\operatorname{\mathbf{m}}_{j}$, the image
$\operatorname{\mathbf{x}}^{\prime}_{j}$ (augmented view of
$\operatorname{\mathbf{x}}_{j}$) acts as the target image while all the other
$(B-1)$ images act as distractors. And vice versa, for the image
$\operatorname{\mathbf{x}}^{\prime}_{k}$, the message
$\operatorname{\mathbf{m}}_{k}$ (encoded by the speaker
$\operatorname{S_{\theta}}(\operatorname{\mathbf{x}}_{k})$) acts as the target
message while all the other $(B-1)$ messages act as distractors. We use the
following symmetric and contrastive loss function, also sometimes referred to
as InfoNCE loss in previous metric-learning works [72, 59].

$\displaystyle\mathcal{L_{\text{text}}}$
$\displaystyle=-\sum_{j=1}^{B}{\log{\frac{\exp(\operatorname{\phi_{\text{text}}}(\operatorname{\mathbf{m}}_{j})\cdot\operatorname{\phi_{\text{vision}}}(\operatorname{\mathbf{x}}^{\prime}_{j})/\tau)}{\sum_{k=1}^{B}{\exp(\operatorname{\phi_{\text{text}}}(\operatorname{\mathbf{m}}_{j})\cdot\operatorname{\phi_{\text{vision}}}(\operatorname{\mathbf{x}}^{\prime}_{k})/\tau)}}}}$
(1) $\displaystyle\mathcal{L_{\text{vision}}}$
$\displaystyle=-\sum_{k=1}^{B}{\log{\frac{\exp(\operatorname{\phi_{\text{text}}}(\operatorname{\mathbf{m}}_{k})\cdot\operatorname{\phi_{\text{vision}}}(\operatorname{\mathbf{x}}^{\prime}_{k})/\tau)}{\sum_{j=1}^{B}{\exp(\operatorname{\phi_{\text{text}}}(\operatorname{\mathbf{m}}_{j})\cdot\operatorname{\phi_{\text{vision}}}(\operatorname{\mathbf{x}}^{\prime}_{k})/\tau)}}}}$
(2) $\displaystyle\mathcal{L}$
$\displaystyle=(\mathcal{L_{\text{text}}}+\mathcal{L_{\text{vision}}})/2$ (3)

where $\tau$ is a constant temperature hyperparameter.

The game setting used in our work is inspired from Lazaridou et al. [45] and
Havrylov and Titov [30], but there are important differences. Both our speaker
$\operatorname{S_{\theta}}$ and listener $\operatorname{L_{\phi}}$ agents are
trained from scratch. This makes the game setting more challenging, since
agents cannot use the pre-trained models which have been shown to encode
semantic and/or syntactic information present in natural language or images.
Our training paradigm, where we show different views of the same image to the
speaker and listener, is inspired by the recent success of self-supervised
learning in computer vision. Empirically, we observe that this leads to a more
stable training and prevents the neural networks from learning degenerate
solutions. However, in contrast with such self-supervised approaches, our goal
is to learn a discrete emergent language as opposed to continuous semantic
representations. We discuss the differences in the architecture of the two
agents in the following sections.

Figure 2: Speaker agent architecture. The upper branch represents the
PatchSymbol, $\operatorname{\theta_{\text{symb}}}$ module and the lower branch
represents PatchRank, $\operatorname{\theta_{\text{rank}}}$ module. Each of
the modules take the raw image as the input. PatchSymbol computes a message
for each patch of pre-defined size, using a fixed size vocabulary and message
length. PatchRank uses a ConvNet to compute weights or the importance of each
patch. Note that the symbols for a patch are context independent, however the
importance of a patch depends on the context. The speaker agent combines the
output of each of the models and sends a variable length message to the
listener.

###  3.2 Speaker agent architecture

A desirable characteristic of the speaker agent is that it should be able to
encode “important” components of images with a variable length sequence of
discrete symbols. Previous works [22, 9, 30] have achieved this by first
converting the image into a continuous deterministic latent vector and then
using an LSTM network [33] to generate a sequence of hidden states, and sample
from this sequence of hidden state until a special end of sequence token (or
maximum length) is reached. As observed by [46, 30], in order to achieve the
minimum loss, the model ends up always using the maximum allowable length. In
our experiments as well, we observed that having an LSTM makes the training
slow and does not achieve the objective of encoding images in variable length
sequences. We propose leverage two separate modules in the speaker agent
$\operatorname{S_{\theta}}$ to circumvent this problem - the first module
called PatchSymbol ($\operatorname{\theta_{\text{symb}}}$) is a 2-layer MLP
that computes patch-level embeddings for the image, the second module called
PatchRank ($\operatorname{\theta_{\text{rank}}}$) is a small ConvNet that
computes rank or importance of each patch in the image.

PatchSymbol, $\operatorname{\theta_{\text{symb}}}$. The idea of encoding an
image at the patch level is inspired by the works on discovering mid-level
patches [18, 37, 70] in images. We use a simple 2-hidden layer MLP, to encode
each $\mathbb{R}^{C\times S^{2}}$ dimensional image patch
$\operatorname{\mathbf{x}}_{\text{patch}}$ to $l$ vectors of log of
probabilities
$[\log{p^{1}_{1}},\dots,\log{p^{1}_{V}}],\dots,[\log{p^{l}_{1}},\dots,\log{p^{l}_{V}}]$.
Here $C$ is the number of (color) channels in the input image or patch, $S$ is
the spatial dimension of a square patch, $V$ is the size of the vocabulary
used to represent a single symbol, and $l$ is the number of symbols used to
encode each patch. Hence an image of size $\mathbb{R}^{C\times H\times W}$ can
be encoded using $K=\frac{HW}{S^{2}}$ patches, each consisting of $l$ symbols.
The vectors of log probabilities allow us to sample from a categorical
distribution of $V$ categories, with a continuous relaxation by using the
Gumbel-softmax trick [34, 51]. For a given vector
$[\log{p^{j}_{1}},\dots,\log{p^{j}_{V}}]$, we draw i.i.d samples $g^{j}_{i}$
from the $\mathsf{Gumbel}(0,1)$ distribution [27] and get a differentiable
approximation of $\operatorname*{arg\,max}$ as follows:

$\displaystyle\left[[\log{p^{1}_{1}},\dots,\log{p^{1}_{V}}],\dots,[\log{p^{l}_{1}},\dots,\log{p^{l}_{V}}]\right]$
$\displaystyle=\text{MLP}(\operatorname{\mathbf{x}}_{\text{patch}})$ (4)
$\displaystyle y^{j}=\mathsf{one\\_hot}(\operatorname*{arg\,max}_{i}[\log
p^{j}_{i}])$
$\displaystyle\sim\left\\{\frac{\exp((\log{p^{j}_{i}}+g^{j}_{i})/\tau_{s}))}{\sum_{k=1}^{V}\exp((\log{p^{j}_{k}}+g^{j}_{k})/\tau_{s})}\right\\}_{i=1}^{V},\forall
j$ (5)
$\displaystyle\operatorname{\theta_{\text{symb}}}(\operatorname{\mathbf{x}}_{\text{patch}})$
$\displaystyle=\operatorname{\mathbf{y}}=\left\\{y^{j}\right\\}_{j=1}^{l}$ (6)

where $\tau_{s}$ controls how close the approximation is to
$\operatorname*{arg\,max}$. The final output of the
$\operatorname{\theta_{\text{symb}}}$ network for the entire image
$\operatorname{\mathbf{x}}$ is $L$ one-hot encoded $V-$dimensional symbols,
where $L=l\times\frac{HW}{S^{2}}$. In all our experiments, we fix $V=128$ and
$l=1$.

PatchRank, $\operatorname{\theta_{\text{rank}}}$. An image might have a lot of
redundant patches encoded using the same symbols. The goal of the
$\operatorname{\theta_{\text{rank}}}$ network is to give an importance score
to each patch. Since importance of a patch depends on the context and not the
patch alone, we use a small ResNet-9 [31] to compute an importance weight for
each of the $K=\frac{HW}{S^{2}}$ patches. One possible way to use these
importance weights is to simply normalize them between $(0,1)$ and repeat the
Gumbel-Softmax trick to sample important patches. The listener network
$\operatorname{L_{\phi}}$ would see only the message consisting of “important”
patches. However, we empirically observed that a simple min-max or
L2-normalization allows the network to assign high weights to each patch and
effectively send the entire sequence of length $L$ to the listener. Instead,
we propose to use a differentiable ranking algorithm by Blondel et al. [8] to
convert the importance weights to soft-ranks $\\{1,\dots,K\\}$ in $O(K\log K)$
time. This method works by constructing differentiable operators as
projections onto the convex hull of permutations. Once we have the vector of
soft-ranks $\mathbf{r}\in\mathbb{R}^{K}$, we normalize the ranks and sample
binary values again using a special case of the Gumbel-softmax trick for
Bernoulli distributions [34, 51] as

$\displaystyle\mathbf{r}(\operatorname{\mathbf{x}})$
$\displaystyle=\operatorname*{arg\,max}_{\pi\in\Sigma}\langle\text{CNN}(\operatorname{\mathbf{x}}),\rho_{\pi}\rangle$
(7)
$\displaystyle\operatorname{\theta_{\text{rank}}}(\operatorname{\mathbf{x}})$
$\displaystyle\sim\operatorname{\operatorname{Bern}}\left(\frac{1}{K}\mathbf{r}(\operatorname{\mathbf{x}})\right)$
(8)

where $\text{CNN}(\operatorname{\mathbf{x}})$ are the importance weights
obtained by applying a ResNet-9 to the image $\operatorname{\mathbf{x}}$,
$\Sigma$ is the set of all $K!$ permutations, and $\rho_{\pi}$ are the ranks
corresponding to the permutation $\pi\in\Sigma$. We refer the reader to [8]
for a detailed description of the soft-sort algorithm. Therefore, the final
symbols encoded by the speaker agent, $\operatorname{S_{\theta}}$, is given
by:

$\displaystyle\operatorname{S_{\theta}}(\operatorname{\mathbf{x}})$
$\displaystyle=\operatorname{\mathbf{m}}=\operatorname{\theta_{\text{symb}}}(\operatorname{\mathbf{x}})\cdot\operatorname{\theta_{\text{rank}}}(\operatorname{\mathbf{x}})$
(9)

###  3.3 Listener agent architecture

As discussed in $\S$3.1, the listener agent $\operatorname{L_{\phi}}$ consists
of a language module $\operatorname{\phi_{\text{text}}}$ and a vision module
$\operatorname{\phi_{\text{vision}}}$. We implement
$\operatorname{\phi_{\text{text}}}$ using a small transformer encoder [76]. We
prepend a $\langle\text{CLS}\rangle$ token at the beginning of each message
sequence received from the speaker [17, 29], and use the final embedding of
$\langle\text{CLS}\rangle$ to compute the loss described in Eq. 3. We
implement $\operatorname{\phi_{\text{vision}}}$ using a small vision
transformer [19], and follow a similar procedure as in the text module to
obtain the final image embedding. Both the text and vision modules use a
similar transformer encoder architecture (no weight sharing) with $192$ hidden
size, $12$ layers and $3$ attention heads. Following [81, 11, 13], we add a
high dimensional projection at the end of the last layer before computing the
loss function.

###  3.4 Training

Each of the weights of the speaker and listener agents
$\\{\operatorname{\theta_{\text{symb}}},\operatorname{\theta_{\text{rank}}},\operatorname{\phi_{\text{vision}}},\operatorname{\phi_{\text{text}}}\\}$
are optimized jointly during the training. We use a 2-layer MLP for
$\operatorname{\theta_{\text{symb}}}$, ResNet-9 [31] for
$\operatorname{\theta_{\text{rank}}}$, a ResNet-18 [31] for
$\operatorname{\phi_{\text{vision}}}$, and a small transformer encoder (hidden
size $=192$, 3 heads, 12 layers) for $\operatorname{\phi_{\text{text}}}$. All
the experiments are conducted on the training set of ImageNet [16], which has
approximately 1.28 million images from 1000 classes. We create a training and
validation split from the training set by leaving aside 5% of the images for
validation. After obtaining the final set of hyper-parameters, we retrain on
the entire training set for 100 epochs. We use Stochastic Gradient Descent
(SGD) with momentum and cosine learning rate scheduling. In order to train the
stochastic component of the Speaker, we use the straight-through trick [7]. We
reiterate that the speaker and listener do not share weights, and the only
supervision used is the InfoNCE loss defined in Eq. 3. Please refer to the
appendix and code attached in the supplementary material for more details.

##  4 Experiments

We evaluate the success of communication in the referential game and impact of
various hyper-parameters on the success. Also, following the work of Lowe et
al. [50], we evaluate the emergent communication in two primary ways. In
section 4.1, we measure positive signaling, which means that
$\operatorname{S_{\theta}}$ sends messages relevant to the observation. In
section 4.2, we measure positive listening, which indicates that the messages
are influencing the $\operatorname{L_{\phi}}$ agent’s behavior.

###  4.1 Positive Signaling - Visualizing Patch Ranks from
$\operatorname{\theta_{\text{rank}}}$

We first visualize the output of PatchRank module as a heatmap overlayed on
the original image in Fig. 3. Most important patches are colored towards ‘red’
and the least important ones are colored towards ‘blue’. The figure shows that
our PatchRank can capture important and discriminative parts of the images. In
case of images of various animals and plants, the model assigns the highest
important to discriminative body parts. For the inanimate objects such as
abacus or revolver the model is able to distinguish between the foreground and
the background. Note that although approaches such as GradCam [67] can provide
pixel-level importance heatmaps, they require extensive supervision. Our
method on the other hand is self-supervised. We also show some of the failure
cases when discriminative patches in the image cover majority of the image on
the rightmost 2 columns of Fig. 3.

Figure 3: Heat maps based on Patch Importance. Red represents the most
important patches and Blue the least important. Labels are listed for better
understanding and are not used during training. We have used $224\times 224$
images and $32\times 32$ patches to get 49 non-overlapping patches per image.
Model successfully separates the primary object in an image - the “device” in
the “Abacus” image, “rabbit” in the “hare” image etc. (as shown by higher
concentration of yellow-to–red patches on these areas). Some failure cases are
shown as well on the right.

###  4.2 Positive Signaling - Image Classification with subset of patches
provided by $\operatorname{\theta_{\text{rank}}}$

Recently proposed Vision Transformers (ViT) by Dosovitskiy et al. [19] have
gained popularity because of their simplicity and performance. These models
treat an image as a sequence of $N\times N$ patches, use an MLP to convert the
patch into an embedding, and finally use these set of patches to perform
classification. We first note that both the inference time and memory
consumption of ViT depend largely on the length of sequence, because of the
$O(N^{2})$ self-attention operation. Secondly, the performance of the Vision
Transformers drops if instead of using all patches, we only use a subset of
patches during inference. This provides us a simple way to evaluate the
$\operatorname{\theta_{\text{rank}}}$ module. We artificially constrain the
number of patches available to ViT during inference. We measure the Top-1
Accuracy of ViT using only $k$ allowed patches. The selection of the patches
is done by the $\operatorname{\theta_{\text{rank}}}$ model.

We consider two different pre-trained ViT [19] models, one trained using
$32\times 32$ patches, on the images of size $384\times 384$ (so the number of
patches in an image is 144), while the second model is trained using $16\times
16$ patches on the images of size $224\times 224$ (196 patches per image). In
Fig. 4a and 4b, we show the Top-1 accuracy obtained by the pre-trained ViT
models using important patches predicted by
$\operatorname{\theta_{\text{rank}}}$ at different values of $k$. At the
$0^{\text{th}}$ epoch (with random weights), the performance of ViT drops
almost linearly as we lower the patch count $k$. At the $100^{\text{th}}$
epoch, at the end of the training, we observe that performance of the ViT does
not drop as drastically.

(a) $32\times 32$ patches

(b) $16\times 16$ patches

Figure 4: Impact of number of patches used during evaluation in a pre-trained
ViT [19]. The performance of a ViT drops if we provide fewer patches during
inference. However a PatchRank model (which is a small ResNet-9) can provide
important patches to ViT during inference with minimal loss in Top-1 accuracy.

###  4.3 Positive Signaling - Visualizing
$\operatorname{\theta_{\text{symb}}}$ symbols

As mentioned earlier, we are using a vocabulary $V=128$ and patch size $S=32$
in our base model. This means $\operatorname{\theta_{\text{symb}}}$ has to map
each $32\times 32$ patch to one of the $128$ available symbols. A natural way
to analyze what the symbols are encoding to see is to visualize their
corresponding patches. While $V=128$ is far too small a vocabulary to describe
all possible patches, we observe some interesting patterns in Fig. 5. Many of
the symbols seem to adhere to specific concepts repeatedly. We observed that
symbols have a lesser preference for color, but more preference for texture
and shape. We discovered several symbols corresponding to textures such as
grass, branches, and wood. We also noticed many symbols firing for the patches
corresponding to text, eyes, and even faces. There can be multiple symbols
representing single concept, _e.g._ , both symbol 91 and 123 both fire in case
of eyes.

Figure 5: Visualizing patches corresponding to various symbols. The number in
the top row corresponds to 1 of 128 vocabulary ids. 6 representative patches
corresponding to each patch are shown. The bottom row corresponds to our
interpretation of what concept that symbol might be capturing.

Table 1: Performance of Listener’s Vision module
$\operatorname{\phi_{\text{vision}}}$ \- Downstream classification accuracy
for ImageNet dataset using k-NN (k=20)

Method | Top-1 (%) | Top-5 (%)
---|---|---
MoCo-v2 [32] (R18) |  36.8 ($\pm$ 0.2) | 60.3
VQ-VAE2 [59] |  17.2 ($\pm$ 0.6) | 30.5
PatchVAE [28] (R18, $S=16$) |  16.4 ($\pm$ 0.6) | 28.5
PatchVAE [28] (R18, $S=32$) |  21.3 ($\pm$ 0.5) | 36.2
Ours (R18, $S=16$) |  27.6 ($\pm$ 0.6) | 46.2
Ours (R18, $S=32$) |  30.3 ($\pm$ 0.5) | 49.9

Table 2: Performance of Listener’s Vision module
$\operatorname{\phi_{\text{vision}}}$ \- Downstream mean Average Precision for
Pascal VOC

Method | mAP-50 (%)
---|---
MoCo-v2 [32] (R18) | 65.8
PatchVAE [28] ($S=16$) | 52.2
PatchVAE [28] ($S=32$) | 54.2
Ours ($S=16$) | 58.9
Ours ($S=32$) | 61.3

###  4.4 Positive Listening

Next, we evaluate the vision module, or $\operatorname{\phi_{\text{vision}}}$
of the listener. We follow the protocol employed by various approaches in
self-supervised learning literature. We consider the features obtained at the
final pooling layer of the $\operatorname{\phi_{\text{vision}}}$ (which is a
ResNet-18 in our case). Next, we run a k-NN classification with $k=20$ on the
validation dataset. Table 2 shows the Top-1 and Top-5 % accuracy obtained on
ImageNet using the listener’s vision module and the baselines approaches.
Although our method outperforms VQ-VAE-2 and PatchVAE (methods that learn a
discrete image representation) we observe that there is still a gap between
representations learned by these models as compared to the representations
learned by continuous latent models such as MoCo [32]. Note that, because of
the resource constraints, all results reported in the table are obtained by
training ResNet-18 for only 100 epochs. The results for both MoCo-v2 and our
approach continue to improve if we continue the training beyond 100 epochs (as
also noted by He et al. [32]). Further, we use the listener’s vision module as
a pre-trained network for Pascal VOC dataset [21]. Our results are shown in
the Table 2. Again, results are not competitive as compared to self-supervised
counterparts such as MoCo-v2 but we outperform models with discrete bottleneck
such as PatchVAE. We find that the convergence of models with discrete
bottlenecks (such as this work, and PatchVAE) is slow and hence, improving the
training efficiency of this class of models is an interesting future
direction.

(a) Learning rate

(b) Length of a single patch

(c) Vocabulary

Figure 6: Impact of various hyperparameters on the success of communication.
Top-1 accuracy denotes the percentage of messages in a batch that model was
able to match to the corresponding image. Having a higher message length and
vocabulary helps the model to learn faster.

###  4.5 Ablation study

A communication iteration is successful if the receiver is able to match the
message sent by the speaker to the correct target image. In our experiments,
we use an effective batch size of 512 (split over 4 GPUs), so the chance
accuracy of success of the speaker is $0.19\%$. We measure the Top-1 accuracy
for each image of the batch and average it over validation data at the end of
epoch. In Fig. 6a, we observe that too high or too low learning rates can be
detrimental to the success of communication. We fix the learning rate at
0.0001 which shows the best validation performance empirically. We train our
models at different vocabulary sizes, and different message lengths for 100
epochs. From Fig. 6b and 6c, we observe that having either a large vocabulary
or larger message length allows the model to reach high accuracy faster. This
is intuitive since the larger the space spanned by the messages is, the easier
it is for receiver to distinguish between the images. A large message length
increases the possible number of messages exponentially, at the cost of much
larger computation cost since self-attention [76, 17] is an $O(N^{2})$
operation. A large vocabulary also increases the both the span of messages and
computation cost linearly.

##  5 Discussion

Summary. In this work, we have shown that two cooperative neural network
agents can develop a variable length communication protocol to solve a given
task on a large scale image dataset with only self-supervision. To the best of
our knowledge, this is the first work to develop an emergent communication via
mid-level patches without using any pre-trained models or external labels. We
have introduced a novel mid-level-patch based architecture for the speaker
agent, in order to represent only the “interesting” parts of image with
discrete symbols. The listener agent learns to align the messages and images
using a language and image encoders to a common embedding space. The speaker
and listener agents are trained end-to-end jointly to capture invariances
induced by various data augmentations in order to solve a constrastive task.
We propose a number of quantitative and qualitative measures to analyse and
evaluate the emerged language. We also show two major applications of the
developed approach - (1) extract representative and discriminative parts of
the image (2) transfer learning in image classification tasks.

Limitations and Future Work. There are a few limitations of our approach.
Firstly, one of the applications discussed in Section 4.1 is using fewer
patches for inference in ViT. Although, using fewer patches reduces the memory
cost of ViT, the overhead of using another neural network for predicting the
important patches means our gain is minimal. In the future, we would like to
explore even faster architectures to have a bigger impact on classification
speed. Second, our method only works with fixed-size square patches.
Discovering arbitrary sized mid-level patches is a challenging task that we
would like to address in future work. Third, the language emerged from our
current model is not grounded in natural language and requires human
intervention for interpretation. Going forward, we would like to ground this
emerged language in the natural language.

Broader Impact. Like most self-supervised approaches, our approach is data
hungry and trained using a large amount of unlabeled data collected from the
Internet. Our model in its current form is prone to learning and amplifying
the biases present in the dataset, especially if the dataset in question is
not carefully curated. While the data collection and labeling has been
discussed in the original paper [16], the community has focused towards
imbalance and privacy violation in existing image datasets only recently [79].
A recent study [80] shows that 997 out of 1000 ImageNet categories are not
‘people’ categories. To compare against previous methods and allow future
benchmarking, we provide results on the 2012 version of the dataset with 1.28
million images in training set and 50000 images in the validation set.

Acknowledgements. We thank Matt Gwilliam, Max Ehrlich, and Pulkit Kumar for
reviewing early drafts of the paper and helpful comments. This project was
partially funded by DARPA SAIL-ON (W911NF2020009), and Amazon Research Award
to AS.

## References

  * Andreas [2019] Jacob Andreas.  Measuring compositionality in representation learning.  _arXiv preprint arXiv:1902.07181_ , 2019.
  * Andreas and Klein [2017] Jacob Andreas and Dan Klein.  Analogs of linguistic structure in deep representations.  _arXiv preprint arXiv:1707.08139_ , 2017.
  * Andreas et al. [2017] Jacob Andreas, Dan Klein, and Sergey Levine.  Learning with latent language.  _arXiv preprint arXiv:1711.00482_ , 2017.
  * Baronchelli et al. [2006] Andrea Baronchelli, Maddalena Felici, Vittorio Loreto, Emanuele Caglioti, and Luc Steels.  Sharp transition towards shared vocabularies in multi-agent systems.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2006(06):P06014, 2006.
  * Batali [1998] John Batali.  Computational simulations of the emergence of grammar.  _Approach to the Evolution of Language_ , pages 405–426, 1998.
  * Bay et al. [2006] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool.  Surf: Speeded up robust features.  In _European conference on computer vision_ , pages 404–417. Springer, 2006.
  * Bengio et al. [2013] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _arXiv preprint arXiv:1308.3432_ , 2013.
  * Blondel et al. [2020] Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga.  Fast differentiable sorting and ranking.  In _International Conference on Machine Learning_ , pages 950–959. PMLR, 2020.
  * Bouchacourt and Baroni [2019] Diane Bouchacourt and Marco Baroni.  Miss tools and mr fruit: Emergent communication in agents learning about object affordances.  _arXiv preprint arXiv:1905.11871_ , 2019.
  * Caron et al. [2020] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  _arXiv preprint arXiv:2006.09882_ , 2020.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers.  _arXiv preprint arXiv:2104.14294_ , 2021.
  * Chen et al. [2020] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pages 1597–1607. PMLR, 2020.
  * Chen and He [2020] Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  _arXiv preprint arXiv:2011.10566_ , 2020.
  * Clark [1996] Herbert H Clark.  _Using language_.  Cambridge university press, 1996.
  * Das et al. [2017] Abhishek Das, Satwik Kottur, José MF Moura, Stefan Lee, and Dhruv Batra.  Learning cooperative visual dialog agents with deep reinforcement learning.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2951–2960, 2017.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Doersch et al. [2012] Carl Doersch, Saurabh Singh, Abhinav Gupta, Josef Sivic, and Alexei Efros.  What makes paris look like paris?  _ACM Transactions on Graphics_ , 31(4), 2012.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Esser et al. [2020] Patrick Esser, Robin Rombach, and Björn Ommer.  Taming transformers for high-resolution image synthesis.  _arXiv preprint arXiv:2012.09841_ , 2020.
  * Everingham et al. [2015] M. Everingham, S. M. A. Eslami, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes challenge: A retrospective.  _International Journal of Computer Vision_ , 111(1):98–136, January 2015.
  * Evtimova et al. [2017] Katrina Evtimova, Andrew Drozdov, Douwe Kiela, and Kyunghyun Cho.  Emergent communication in a multi-modal, multi-step referential game.  _arXiv preprint arXiv:1705.10369_ , 2017.
  * Foerster et al. [2016] Jakob N Foerster, Yannis M Assael, Nando De Freitas, and Shimon Whiteson.  Learning to communicate with deep multi-agent reinforcement learning.  _arXiv preprint arXiv:1605.06676_ , 2016.
  * Fu et al. [2020] Ruigang Fu, Qingyong Hu, Xiaohu Dong, Yulan Guo, Yinghui Gao, and Biao Li.  Axiom-based grad-cam: Towards accurate visualization and explanation of cnns.  _arXiv preprint arXiv:2008.02312_ , 2020.
  * Goyal et al. [2017] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  _arXiv preprint arXiv:1706.02677_ , 2017.
  * Grill et al. [2020] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent: A new approach to self-supervised learning.  _arXiv preprint arXiv:2006.07733_ , 2020.
  * Gumbel [1954] Emil Julius Gumbel.  _Statistical theory of extreme values and some practical applications: a series of lectures_ , volume 33.  US Government Printing Office, 1954.
  * Gupta et al. [2020] Kamal Gupta, Saurabh Singh, and Abhinav Shrivastava.  Patchvae: Learning local latent codes for recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4746–4755, 2020.
  * Gupta et al. [2021] Kamal Gupta, Justin Lazarow, Alessandro Achille, Larry S Davis, Vijay Mahadevan, and Abhinav Shrivastava.  Layouttransformer: Layout generation and completion with self-attention.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1004–1014, 2021.
  * Havrylov and Titov [2017] Serhii Havrylov and Ivan Titov.  Emergence of language with multi-agent games: Learning to communicate with sequences of symbols.  _arXiv preprint arXiv:1705.11192_ , 2017.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9729–9738, 2020.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Jang et al. [2016] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ , 2016.
  * Jones [1972] Karen Sparck Jones.  A statistical interpretation of term specificity and its application in retrieval.  _Journal of documentation_ , 1972.
  * Jorge et al. [2016] Emilio Jorge, Mikael Kågebäck, Fredrik D Johansson, and Emil Gustavsson.  Learning to play guess who? and inventing a grounded language as a consequence.  _arXiv preprint arXiv:1611.03218_ , 2016.
  * Juneja et al. [2013] Mayank Juneja, Andrea Vedaldi, CV Jawahar, and Andrew Zisserman.  Blocks that shout: Distinctive parts for scene classification.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 923–930, 2013.
  * Jurie and Triggs [2005] Frederic Jurie and Bill Triggs.  Creating efficient codebooks for visual recognition.  In _Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1_ , volume 1, pages 604–610. IEEE, 2005.
  * Kazemzadeh et al. [2014] Sahar Kazemzadeh, Vicente Ordonez, Mark Matten, and Tamara Berg.  Referitgame: Referring to objects in photographs of natural scenes.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 787–798, 2014.
  * Keresztury and Bruni [2020] Bence Keresztury and Elia Bruni.  Compositional properties of emergent languages in deep learning.  _arXiv preprint arXiv:2001.08618_ , 2020.
  * Kingma and Welling [2013] Diederik P Kingma and Max Welling.  Auto-encoding variational bayes.  _arXiv preprint arXiv:1312.6114_ , 2013.
  * Kirby [2002] Simon Kirby.  Natural language from artificial life.  _Artificial life_ , 8(2):185–215, 2002.
  * Krishna et al. [2018] Ranjay Krishna, Ines Chami, Michael Bernstein, and Li Fei-Fei.  Referring relationships.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6867–6876, 2018.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25:1097–1105, 2012.
  * Lazaridou et al. [2016] Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni.  Multi-agent cooperation and the emergence of (natural) language.  _arXiv preprint arXiv:1612.07182_ , 2016.
  * Lazaridou et al. [2018] Angeliki Lazaridou, Karl Moritz Hermann, Karl Tuyls, and Stephen Clark.  Emergence of linguistic communication from referential games with symbolic and pixel input.  _arXiv preprint arXiv:1804.03984_ , 2018.
  * Lee et al. [2017] Jason Lee, Kyunghyun Cho, Jason Weston, and Douwe Kiela.  Emergent translation in multi-agent communication.  _arXiv preprint arXiv:1710.06922_ , 2017.
  * Lewis [1969] David Lewis.  _Convention: A philosophical study_.  John Wiley & Sons, 1969.
  * Lowe [2004] David G Lowe.  Distinctive image features from scale-invariant keypoints.  _International journal of computer vision_ , 60(2):91–110, 2004.
  * Lowe et al. [2019] Ryan Lowe, Jakob Foerster, Y-Lan Boureau, Joelle Pineau, and Yann Dauphin.  On the pitfalls of measuring emergent communication.  _arXiv preprint arXiv:1903.05168_ , 2019.
  * Maddison et al. [2016] Chris J Maddison, Andriy Mnih, and Yee Whye Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  _arXiv preprint arXiv:1611.00712_ , 2016.
  * Mihai and Hare [2019] Daniela Mihai and Jonathon Hare.  Avoiding hashing and encouraging visual semantics in referential emergent language games.  _arXiv preprint arXiv:1911.05546_ , 2019.
  * Mihai and Hare [2021] Daniela Mihai and Jonathon Hare.  The emergence of visual semantics through communication games.  _arXiv preprint arXiv:2101.10253_ , 2021.
  * Mikolov et al. [2016] Tomas Mikolov, Armand Joulin, and Marco Baroni.  A roadmap towards machine intelligence.  In _International Conference on Intelligent Text Processing and Computational Linguistics_ , pages 29–61. Springer, 2016.
  * Misra and Maaten [2020] Ishan Misra and Laurens van der Maaten.  Self-supervised learning of pretext-invariant representations.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6707–6717, 2020.
  * Mordatch and Abbeel [2018] Igor Mordatch and Pieter Abbeel.  Emergence of grounded compositional language in multi-agent populations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Nash et al. [2021] Charlie Nash, Jacob Menick, Sander Dieleman, and Peter W Battaglia.  Generating images with sparse representations.  _arXiv preprint arXiv:2103.03841_ , 2021.
  * Oord et al. [2017] Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu.  Neural discrete representation learning.  _arXiv preprint arXiv:1711.00937_ , 2017.
  * Oord et al. [2018] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Pinker [2003] Steven Pinker.  _The language instinct: How the mind creates language_.  Penguin UK, 2003.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  2018\.
  * Ramesh et al. [2021] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-shot text-to-image generation.  _arXiv preprint arXiv:2102.12092_ , 2021.
  * Razavi et al. [2019] Ali Razavi, Aaron van den Oord, and Oriol Vinyals.  Generating diverse high-fidelity images with vq-vae-2.  _arXiv preprint arXiv:1906.00446_ , 2019.
  * Rennie et al. [2003] Jason D Rennie, Lawrence Shih, Jaime Teevan, and David R Karger.  Tackling the poor assumptions of naive bayes text classifiers.  In _Proceedings of the 20th international conference on machine learning (ICML-03)_ , pages 616–623, 2003.
  * Rolfe [2016] Jason Tyler Rolfe.  Discrete variational autoencoders.  _arXiv preprint arXiv:1609.02200_ , 2016.
  * Salimans et al. [2017] Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma.  Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications.  _arXiv preprint arXiv:1701.05517_ , 2017.
  * Selvaraju et al. [2017] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , pages 618–626, 2017.
  * Seonghyeon [2019] Kim Seonghyeon.  vq-vae-2-pytorch.  https://github.com/rosinality/vq-vae-2-pytorch, 2019.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Singh et al. [2012] Saurabh Singh, Abhinav Gupta, and Alexei A Efros.  Unsupervised discovery of mid-level discriminative patches.  In _European Conference on Computer Vision_ , pages 73–86. Springer, 2012.
  * Sivic and Zisserman [2003] Josef Sivic and Andrew Zisserman.  Video google: A text retrieval approach to object matching in videos.  In _IEEE International Conference on Computer Vision_ , 2003.
  * Sohn [2016] Kihyuk Sohn.  Improved deep metric learning with multi-class n-pair loss objective.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , pages 1857–1865, 2016.
  * Spike et al. [2017] Matthew Spike, Kevin Stadler, Simon Kirby, and Kenny Smith.  Minimal requirements for the emergence of learned signaling.  _Cognitive science_ , 41(3):623–658, 2017.
  * Steels [2005] Luc Steels.  What triggers the emergence of grammar?  _Society for the Study of Artificial Intelligence and Simulation of Behaviour_ , 2005.
  * Sukhbaatar et al. [2016] Sainbayar Sukhbaatar, Arthur Szlam, and Rob Fergus.  Learning multiagent communication with backpropagation.  _arXiv preprint arXiv:1605.07736_ , 2016.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _arXiv preprint arXiv:1706.03762_ , 2017.
  * Wagner et al. [2003] Kyle Wagner, James A Reggia, Juan Uriagereka, and Gerald S Wilkinson.  Progress in the simulation of emergent communication and language.  _Adaptive Behavior_ , 11(1):37–69, 2003.
  * Wittgenstein [1953] Ludwig Wittgenstein.  _Philosophical investigations_.  John Wiley & Sons, 1953.
  * Yang et al. [2020] Kaiyu Yang, Klint Qinami, Li Fei-Fei, Jia Deng, and Olga Russakovsky.  Towards fairer datasets: Filtering and balancing the distribution of the people subtree in the imagenet hierarchy.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , pages 547–558, 2020.
  * Yang et al. [2021] Kaiyu Yang, Jacqueline Yau, Li Fei-Fei, Jia Deng, and Olga Russakovsky.  A study of face obfuscation in imagenet.  _arXiv preprint arXiv:2103.06191_ , 2021.
  * Zbontar et al. [2021] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  _arXiv preprint arXiv:2103.03230_ , 2021.
  * Zhang et al. [2018] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _CVPR_ , 2018.

##  Appendix A Training details

Both speaker and listener agents
$\\{\operatorname{\theta_{\text{symb}}},\operatorname{\theta_{\text{rank}}},\operatorname{\phi_{\text{vision}}},\operatorname{\phi_{\text{text}}}\\}$
are trained jointly during the training. All the experiments are conducted on
the training set of ImageNet [16], which has approximately 1.28 million images
from 1000 classes. We create a training and validation split from the training
set by leaving aside 5% of the images for validation. After obtaining the
final set of hyper-parameters, we retrain on the entire training set for 100
epochs. We use Stochastic Gradient Descent (SGD) with momentum and cosine
learning rate scheduling. In order to train the stochastic component of the
Speaker, we use the straight-through trick [7]. We use linear warmup for
learning rate for 30 epochs. We also use a cosine schedule for temperature
annealing for Gumbel Softmax, where we decrease the temperature from 5.0 to
1.0 in first 50 epochs and then fix the temperature to 1.0 for rest of the
epochs. Please find the code and model (see the README file) attached in the
supplementary material.

##  Appendix B More Ablations

#### Augmentations

We perform an additional ablation study where we train the model on ImageNet
for 20 epochs with different augmentations removed and observed which ones
have the most impact on downstream classification task with kNN. The results
are shown in the Table 4.

#### Batch Size

In our experiments, we observed that higher batch size leads to both stable
and improved downstream performance which is intuitive since it allows for
contrastive loss to be more accurate. In all our experiments, we use the
maximum batch size that could fit in 12GB GPU memory (128 images per GPU). The
contrastive loss is computed over the aggregate batch size over 4 GPUs (and
hence the effective batch size of 512 images). For larger batch sizes, we
scale the learning rate linearly [25]. Table 4 below shows the downstream
classification performance of the model at different batch sizes (trained for
20 epochs).

Table 3: Ablation study for augmentations

Augmentation | Top-1 (%)
---|---
Baseline | 26.3
Remove color jitter | 23.2
Remove random resized crops | 22.9

Table 4: Ablation study for batch sizes

Batch Size | Top-1 (%)
---|---
128 | 47.2
256 | 49.1
512 | 49.9

##  Appendix C Visualizing more symbols

Fig. 7 shows some additional examples of symbol ids and their possible
meaning. We observed that most symbol ids fire for consistent patterns. An
interesting observation is that model doesn’t focus a lot on the color but the
textures and shapes in the images. One of the limitations of our approach is
the fixed-size grid used in the architecture which restricts the patch size to
$32\times 32$ or $16\times 16$. This restriction is important for the
efficient training. However, it results in some symbols capturing only partial
concepts such as part of a face or text. In future works, we seek to address
this limitation.

Figure 7: Visualizing some more symbols. The number in the top row corresponds
to one of the 128 vocabulary ids (from 0-127). 6 representative patches
corresponding to each patch are shown. The bottom row corresponds to our
interpretation of what concept that symbol might be capturing.

##  Appendix D Topographic Similarity

We analyse the topographic similarity between the learned messages and images
from the validation dataset as following: We take 10 random images from each
category. Then we compute pairwise Jaccard Similarity (JS) between all
${10\choose 2}=45$ image pairs for that category. JS corresponds to a simple
intersection over union (IoU) of the set of symbols in the messages
corresponding to two images. This indicates how similar the images are with
respect to message generated by the Speaker (note that even though speaker
generates a sequence of symbol, we analyse it as a set for this analysis). For
each pair, we also compute Learned Perceptual Image Patch Similarity (LPIPS)
metric [82] using off-the-shelf VGG model. We draw a scatter plot between the
two similarity metrics as show in Fig. 8 We observe that some categories, such
as ‘toucan’, ‘filing cabinet’, and ‘crab’ have very high correlation, while
there are some categories with almost no correlation between LPIPS and Jaccard
similarity. The mean and median correlation across all categories is 0.25 and
0.21.

Figure 8: Topographic similarity computed as pairwise correlation between
Jaccard similarity of messages and LPIPS perceptual similarity of images [82].
The top row shows the 3 categories with highest topographic similarity and the
bottom row shows 3 categories with lowest topographic similarity. Note that
the slope coefficient is in the scientific notation $a\times 10^{b}$

##  Appendix E Variable length messages

We analyze the number of symbols and number of unique symbols appearing in
each message, as illustrated in Fig. 9. Fig. 9a shows that that all each
message has at least $7$ unique symbols, without any particular symbol
excessively recurring within a message. No image uses more than 16 unique
symbols even though maximum allowable symbols that can be used by an image is
49 (from the vocabulary of 128 symbols). Fig. 9b shows the distribution
obtained when we consider all symbols (and not just unique) for a message. The
distribution looks like a gaussian and this is because of the design choice we
made in our architecture. Since for a given image, we sample the patch ranks
from a normalized and sorted list of ranks, only about half of the symbols,
end up getting selected and hence the peak of the distribution is at 24-25
(half of 49).

(a) Unique symbols per message distribution

(b) All symbols per message distribution

Figure 9: Analysis of Patch Symbols. We investigate the number of unique
symbols appearing in an image (on the x-axis). y-axis shows the number of
images in the validation set with the corresponding number of unique symbols.
Most images use 13 unique symbols (maximum possible is 49) for representation.

##  Appendix F Relationship between length of messages and images

We try to analyze qualitatively the relationship between the images and the
length of message representation as generated by the speaker. We sort all the
images in the validation set by the length of the message and report some of
the images with very long and very short message lengths in Fig. 10. We
observe that, on an average, images with lengthier messages appear more
complex visually with a lot of clutter or variety of objects in the image.
Images with shorter message length usually have a single object.

Figure 10: Complex images require long messages while visually simple images
like the ones shown above can be represented with short messages.

##  Appendix G Visualizing saliency maps and PatchRank

We qualitatively compare the patch ranks generated by our method with the
corresponding saliency maps generated using a standard technique. Since the
saliency maps provide us with important regions of an image, the patches
deemed as important by our method should overlap with the said salient
regions. Note that the saliency method uses a supervised classification model
and class label to generate the pixelwise importance heatmap. Our method on
the other hand generates these plots in an unsupervised manner.

Following this hypothesis, we extract the saliency maps for the ImageNet
validation set with the XGradCAM [24] approach, using the ResNet-50 [31] model
with true category labels obtained from official code repository. Fig. 11
illustrates the saliency maps and the patch ranks obtained for a few such
random ImageNet validation images. We observe that important patches ranked by
our model has a high correspondence with the salient regions of the images.

Figure 11: Comparison of saliency maps and the patch rank heatmaps based on
importance for ImageNet validation images. Red represents the most important
patches and Blue the least important. For each set of three images, the first,
second and third sub-images correspond to the original image, saliency maps,
and patch heatmaps respectively. Note that the saliency method uses a
supervised classification model and class label to generate the pixelwise
importance heatmap. Our method on the other hand generates these plots in an
unsupervised manner.

##  Appendix H Analyzing the symbol distribution

We investigate the distribution of the patch symbols generated with our
method. For each image in the ImageNet validation set, we compute the list of
symbols generated by $\operatorname{\theta_{\text{symb}}}$. Then we calculate
the frequency that each symbol appear across the images in the validation set,
as illustrated in Fig. 12. Even though the distribution is not uniform, we
observe that all symbols recur often, suggesting that our generated symbols
are not redundant. This complements our observation in Section 4.3 (Fig. 5 of
the manuscript) where we observed that there are some symbols that correspond
some very common textures and patterns such as grass or lines, while some
symbols on the other hand capture more specific concepts such as faces, or
eyes.

Figure 12: Analysis of Patch Symbols. We investigate the distribution and
characteristics of symbols generated by our method for the ImageNet validation
set. x-axis shows symbol ids (between 0 and 127), while y-axis shows the
number of times that symbol appeared in the representation of images in
validation set. Symbols have non-uniform rate of appearance in the images.
However, most of the symbols are utilized by the model.

##  Appendix I Positive Signaling - Visual Bag of Words Classification with
$\operatorname{\theta_{\text{symb}}}$

Representing the image as visual bag of words is a well-known technique in
image retrieval works [71]. Since our task is to represent image with words as
well, we devise the following way to evaluate the PatchSymbol module or
$\operatorname{\theta_{\text{symb}}}$. For each image in the ImageNet training
and validation set, we compute the message or the list of symbols generated by
$\operatorname{\theta_{\text{symb}}}$ (and filtered according to
$\operatorname{\theta_{\text{rank}}}$). We then compute a feature for each
image using the weighted frequency of symbols in the image or tf-idf [35]. We
then train a simple complement naive bayes classifier [64] on top of these
feature vectors. For benchmarking, we choose two prior works that encode
images to symbols and have shown strong results in generative modeling. VQ-
VAE-2 or Vector Quantized Variational AutoEncoder was initially proposed by
Oord et al. [58] and later improved by Razavi et al. [63] for both conditional
and unconditional large scale image generation. We retrain the model for 100
epochs at $256\times 256$ resolution used in the paper using [68]’s
repository. PatchVAE by Gupta et al. [28] proposes a structured variant of
Variational AutoEncoders [41]. We use the authors’s code and retrain their
models for a $7\times 7$ bottleneck (corresponding to $S=32$ patch size), and
a $14\times 14$ bottleneck (corresponding to $S=16$ patch size), each for 100
epochs.

Table 5 shows the Top-1 and Top-5 % classification accuracies on ImageNet. The
patch symbols generated with our method outperform those generated by VQ-VAE-2
and PatchVAE in the downstream classification task by factors of 45% and 25%
respectively. Note that classification accuracy is far below the ones that can
be obtained using standard techniques, however the goal of this evaluation is
to demonstrate that the symbols do capture meaningful information.

Table 5: Performance of Speaker’s PatchSymbol module $\operatorname{\theta_{\text{symb}}}$ \- Downstream classification accuracy for ImageNet dataset using visual BoW method with Complement Naive Bayes Method | Top-1 (%) | Top-5(%)
---|---|---
VQ-VAE2 [58] |  0.88 ($\pm$ 0.03) | 5.02
PatchVAE [28] ($S=32$) |  1.02 ($\pm$ 0.07) | 4.48
PatchVAE [28] ($S=16$) |  1.00 ($\pm$ 0.08) | 5.04
Ours ($S=32$) |  1.28 ($\pm$ 0.06) | 6.10
Ours ($S=16$) |  1.20 ($\pm$ 0.06) | 5.94


# Efficient Graph-Friendly COCO Metric Computation for Train-Time Model
Evaluation

Luke Wood
Google
<EMAIL_ADDRESS>
https://lukewood.xyz François Chollet
Google
<EMAIL_ADDRESS>

###### Abstract

Evaluating the COCO mean average precision (MaP) and COCO recall metrics as
part of the static computation graph of modern deep learning frameworks poses
a unique set of challenges. These challenges include the need for maintaining
a dynamic-sized state to compute mean average precision, reliance on global
dataset-level statistics to compute the metrics, and managing differing
numbers of bounding boxes between images in a batch. As a consequence, it is
common practice for researchers and practitioners to evaluate COCO metrics as
a post training evaluation step. With a graph-friendly algorithm to compute
COCO Mean Average Precision and recall, these metrics could be evaluated at
training time, improving visibility into the evolution of the metrics through
training curve plots, and decreasing iteration time when prototyping new model
versions.

Our contributions include an accurate approximation algorithm for Mean Average
Precision, an open source implementation of both COCO mean average precision
and COCO recall, extensive numerical benchmarks to verify the accuracy of our
implementations, and an open-source training loop that include train-time
evaluation of mean average precision and recall.

##  I Introduction

COCO metrics, originally proposed alongside the COCO dataset, have become the
evaluation method of choice for object detection, segmentation map, and
keypoint detection models [1]. The process of computing COCO metrics is
complex and does not cleanly fit into the computation model used in popular
static graph-based deep learning frameworks such as TensorFlow [2] and JAX
[6]. For these reasons, researchers and practitioners alike most commonly
perform COCO metric evaluation as a post-training evaluation step using the
pycocotools package [1] 111 pyococotools is open source on GitHub at
https://github.com/cocodataset/cocoapi/tree/master/PythonAPI/pycocotools As a
consequence, model comparison is done using a table of single scalar metrics
rather than using learning curve plots. This decreases visibility into the
evolution of these metrics, greatly increases iteration time when prototyping,
and forces comparisons across models to be based on a single number (generally
without error bars), which decreases the reliability of these comparisons.

This work contributes an approach to compute recall and mean average precision
as defined in the Microsoft COCO challenge within the constraints of the
computation graphs of TensorFlow. Our contributions include an algorithm that
computes a close approximation to mean average precision, fine-grained
numerical accuracy benchmarks against existing COCO metric evaluation tools,
an open source Keras-native implementation of both mean average precision and
recall, and an open-source object detection pipeline leveraging these metrics.
Additionally, our algorithm and implementation support distributed metric
evaluation.

These innovations enable researchers to produce learning curves for MaP and
recall metrics throughout training, which in turn enables rapid iteration,
deeper understanding of the training process, and robust result reporting.

##  II Related Work

COCO metrics were first proposed in the Microsoft COCO challenge by Lin et al.
[1]. The metrics were used as the evaluation criteria for the challenge, and
have since been the standard evaluation criteria for object detection models.
COCO metrics have been used for model evaluation in numerous works
[3][4][11][10][8][9][5].

While COCO metrics remain the dominant object detection metrics, other object
detection evaluation metrics do exist. These include average IoU[7], F-Score,
and traditional recall and precision.

##  III Metric Overview

###  III-A Terminology

Intersection over Union (IoU). Intersection over Union, or IoU, is an area-
based metric used in Computer Vision to determine if two objects can be
considered to be the same. As the name suggests, the metric is computed by
dividing the area of the intersection of two objects by the area of their
union. The range of IoU is 0 to 1, with two identical objects having an IoU of
1 and objects with no intersection possessing an IoU of 0.

Ground Truth. Predicted boxes consist of six scalars. The first four represent
the boxes’ $left$, $top$, $right$ and $bottom$ coordinates, the fifth the
class of the predicted box, and the sixth the confidence score of the
predicted box.

Predicted Boxes. Predicted boxes contain the same information as ground-truth
boxes, along with an additional sixth value representing the confidence score
of the predicted box. Predicted boxes are typically produced by a bounding box
detection model.

True Positive and False Positive. To determine if a predicted box is a true
positive or false positive, first we define some IoU threshold $\theta$.

Next, we consider the predicted and true boxes present in a single image. We
compute the IoU scores for the predicted boxes and the true boxes, iterating
over the predicted boxes. If the predicted box has an IoU larger than $\theta$
for one or more ground truth box with the same class ID, the ground truth box
with the highest IoU to the predicted box is marked as matched. The matched
predicted box is then considered a true positive, and the process continues
until all predicted or ground truth boxes are exhausted. Any remaining
predicted boxes are considered false positives.

###  III-B Recall

An average of many recall scores is often used to represent a single value of
recall in object detection benchmarks. These various recall scores are
computed given a set of IoU thresholds, $\Theta$. A common choice for
$\Theta$, originally used in the Microsoft COCO challenge, is the range
$[0.5,0.55,...,0.9,0.95]$.

To compute each individual recall value, we compute true positives and false
positives in a given image with $IoU=\theta$ for all $\theta\in\Theta$.

To compute recall, the number of true positives computed for the given IoU
threshold is divided by the number of ground truth boxes. This process is
repeated for all $\theta\in\Theta$, and the average of all of these is
considered the final COCO recall score.

###  III-C Mean Average Precision

Precision is defined as the number of true positives divided by the sum of
true and false positives. While precision can be computed using the standard
precision formula, this is unfortunately not particularly useful in the object
detection domain, as models may make many predictions, some of which have low
confidence scores.

MaP is accounts for this fact and serves as a strong general purpose object
detection model evaluation metric. MaP is parameterized by a set of recall
thresholds $R$, and a set of IoU thresholds $\Theta$. While many metrics can
be computed on a per-image basis, MaP can only be computed on a global basis.

First, we construct the product of the sets $R$ and $\Theta$. We consider each
subset of these parameters, $\gamma_{j}\in R$ and $\theta_{i}\in\Theta$.

Next, the aforementioned process of determining whether or not each bounding
box is a true positive or false positive is followed with the selected value
$\theta_{i}$. The global set of predicted bounding boxes from the entire
evaluation dataset is sorted by confidence. The set of all ordered subsets of
boxes is constructed, starting from the empty set, moving to the set of only
the highest confidence box, then adding an additional box by confidence level
in descending order until the set of all predicted boxes is considered. For
each set the recall and precision scores $r_{zi},p_{zi}$ are both computed.

Following this, all pairs $r_{zi},p_{zi}$ are considered. A value
$m_{ji}=p_{ki}$ such that $k=min(z)$ such that $r_{zi}>=\gamma_{j}$. If no
value $r_{zi}>=\gamma_{j}$, $m_{ji}=0$. After computing all $m_{ji}$, a curve
is constructed such that $f_{i}(j)=m_{ji}$. A final value
$\tau_{i}=\int_{0}^{1}f_{i}(j)\,dj$ is computed.

The above process is repeated for all $\theta_{i}$. Finally, the result of MaP
is defined $MaP=avg_{i}(\tau_{i})$.

This process is complex, involves many edge cases, and relies on constructs
incompatible with the static graph-based computation model of the popular deep
learning frameworks TensorFlow. In practice, implementations must meticulously
consider efficiency and order of operations to achieve suitable runtime
performance.

##  IV Graph Implementation

Implementing COCO metrics in a graph deep learning framework poses numerous
challenges. This section describes each of the challenges faced in our
implementation, as well as the techniques and algorithms we implemented to
solve them.

###  IV-A Variable Size State.

The primary issue with computing MaP in the context of a computation graph is
that MaP requires a variable-size state representation. This is because in
order to compute MaP bounding box, predictions must be sorted on a global-
batch basis according to the detection confidence score. Whether or not a
detection was a true positive or false positive must be stored internally in
the metric, alongside the corresponding confidence score. The number of
predictions for any given dataset is unknown until the full dataset is
evaluated, therefore the internal state size of MaP is variable. Modern deep
learning frameworks lack strong support for variable size state in their
computation graphs.

MaP Approximation Algorithm.) In order to solve this issue we propose an
algorithm to closely approximate MaP. Instead of storing a list of detection
instances, whether or not they were true positives, and their corresponding
confidence score we initialize twos vector, $\beta_{p}$ and $\beta_{n}$, both
of shape $(buckets,)$. These vectors are initialized to contain all zeros.

Evaluation is performed on a mini-batch basis. During each mini-batch, we
first determine if the detection instances are true positives or false
positives. Following this, an index is computed for each bounding box using
$i=floor(c*(buckets-\delta))$, where $c=confidence$ and $\delta$ is an
infinitesimal. This yields a number in the range $[0,buckets)$. If the
bounding box is a true positive, $\beta_{p}[i]=\beta_{p}[i]+1$, otherwise
$\beta_{n}[i]=\beta_{n}[i]+1$.

Additionally, the number of ground truth boxes is also tracked in a Tensor,
$\Gamma$ in order to compute the recall scores as required during the AuC
interpolation step.

At the end of evaluation of all mini-batches, the final result is computed
using the following process.

First, a cumulative sum operation is performed over $\beta_{p}$ and
$\beta_{n}$. $\beta_{ps}$=$cumsum(\beta_{p})$,
$\beta_{ns}$=$cumsum(\beta_{n})$. $\beta_{ps}[i]$ can be interpreted as the
number of true positives the classifier has scored when only considering
bounding boxes with confidence score $i/buckets$.

Following this, recall scores for every bucket are computed:
$R=\beta_{ps}/\Gamma$. Precision scores for every bucket are also computed:
$P=\beta{ps}/(\beta_{fs}+\beta_{ps})$. These recall and precision values are
then used in the precision recall pair matching process described in the
original. The area under curve computation process is unchanged from the
original, as is the averaging and repetition of the process over each IoU
threshold.

It should be noted that an additional axis may be added to $\beta_{p}$,
$\beta_{n}$, and $\Gamma$ to support multi-class MaP computation. process.

While our algorithm Our algorithm exposes a parameter, $buckets$, to allow end
users to perform a trade off between accuracy and runtime performance. We
recommend a default setting of $buckets=10000$. In our benchmarks
$buckets=10000$ achieves strong accuracy, while maintaining tolerable runtime
performance.

###  IV-B Ragged Bounding Box Tensors.

The number of bounding boxes in an image may differ between training samples.
This makes the bounding box Tensor ragged. While an easily solvable problem,
this is an important design consideration when implementing COCO metrics in a
computation graph.

-1 Masking. In order to solve this, our implementation simply ignores samples with a class ID of $-1$. This allows us to keep Tensors dense, while still supporting a variable number of bounding boxes in each image. One major caveat of this approach is the additional memory use required to store the $-1$ values used to represent the masked out boxes. While this is far from ideal, all major deep learning frameworks are rapidly improving support for RaggedTensors. As such, our implementation will be updated to support them in the future.

##  V Numerical Accuracy Benchmarking

In order for our metrics to be useful to researchers and practitioners it is
important that the metrics be accurate to their predecessor: pycocotools.

It should be noted that deviation from pycocotools should not be thought of as
a deviation from the numerical value of the underlying metric itself.
pycocotools lacks precise testing and was primarily developed by one
individual contributor. But while pycocotools results should not be considered
the ground-truth value for MaP or recall, it is still the industry standard
for COCO metric evaluation. As such, we consider it prudent to benchmark the
error margins between our implementation and the pycocotools implementation.

###  V-A Mirroring Standard COCO Metric Evaluation

The standard pycocotools COCO evaluation suite contains several additional
parameterizations of the standard mean average precision and recall metrics.
These additional parameterizations include area range filtering, where only
bounding boxes inside of a specified area range are considered, and a max-
detection value, a limit on the number of detections a model may make per
image.

In order to evaluate the numerical accuracy of our implementation we have
implemented support for these parameters.

While implementing area range filtering and max detections on top of the
algorithm we have proposed in IV is trivial, there is no one-to-one perfectly
matching method. In the mini-batch update step all examples are simply
filtered based on their computed area before computing false positives, true
positives, and ground truths.

###  V-B Experimental Setup

Our benchmarking process covers each COCO metric configuration used in the
original Microsoft COCO challenge. The accuracy of each configuration is
evaluated for varying numbers of images and bounding boxes. Each test set is
generated based on the ground truth annotations provided in the COCO dataset
evaluation. Our process for producing a test dataset is as follows: First, we
sample $N$ random images from the COCO dataset. We select all of the bounding
boxes associated with that dataset and treat these as our ground truths. Next,
we modify the ground truth bounding boxes by shifting the $x$ coordinate up to
10% of the width of the box, and shifting the $y$ coordinate by up to 10% of
the height of the box. Following this, we randomly shift the width and height
of the predicted boxes by up to 10%. These mutated boxes are used as
predictions $y_{pred}$.

More formally:

$left=left+random(-0.2,0.2)*width\\\ right=right+random(-0.2,0.2)*height\\\
width=width*random(0.8,1.2)\\\ height=height*random(0.8,1.2)$

Test datasets are generated 10 times each, and each metric configuration is
evaluated independently. Every metric configuration from the COCO standard set
of metrics is evaluated, with both the pycocotools implementation and the
corresponding keras_cv implementation. The differences are compared, and the
error margin between each is disclosed in section VI.

##  VI Experimental Results

Figure 1 provides an overview of the error distributions of the runs of each
metric. Figure 2 and Figure 3 show the resulting error margin plots generated
from this experiment. The X axis shows the number of images used in the 10
runs making up that datapoint, and the Y axis represents the absolute error
from the pycocotools metric.

These figures show that when both implementations are used to evaluated the
same corpus of images, the results are near identical. However, there is
clearly a difference taken in the implementation of area range evaluation.

The error margins for both MaP and recall are <3% for cases that do not
involve area range filtering. Table I show the median, mean, and standard
deviation of each evaluation case. In cases that do not involve area range
filtering the error margins are likely caused by rounding differences between
the NumPy and TensorFlow, rounding errors induced by differing order of
operations between our implementation and the pycocotools implementation, and
the approximation algorithm used to compute MaP.

TABLE I: Numerical Results Across All runs Metric | Min Error | Max Error | Mean Error
---|---|---|---
Standard MaP | 0.000 | 0.046 | $0.015\pm 0.011$
MaP IoU=0.5 | 0.000 | 0.075 | $0.024\pm 0.019$
MaP IoU=0.75 | 0.001 | 0.079 | $0.025\pm 0.017$
MaP Small Objects | 0.000 | 0.202 | $0.054\pm 0.040$
MaP Medium Objects | 0.001 | 0.156 | $0.055\pm 0.036$
MaP Large Objects | 0.000 | 0.150 | $0.028\pm 0.030$
Recall 1 Detection | 0.000 | 0.029 | $0.009\pm 0.007$
Recall 10 Detections | 0.000 | 0.035 | $0.011\pm 0.007$
Standard Recall | 0.000 | 0.035 | $0.011\pm 0.007$
Recall Small Objects | 0.001 | 0.143 | $0.043\pm 0.031$
Recall Medium Objects | 0.000 | 0.172 | $0.047\pm 0.038$
Recall Large Objects | 0.000 | 0.150 | $0.013\pm 0.032$

###  VI-A Area Range Differences

The error margin for all cases involving area filtering is significantly
greater. This can be attributed to an implementation difference. pycocotools
filters the area of bounding boxes according to the area annotation of the
ground truth annotations included in the COCO dataset. It should be noted that
in the COCO dataset the area of each bounding box is actually computed using
the segmentation map included in the dataset. Additionally, no filtering is
done on the predicted bounding boxes.

On the other hand, KerasCV filters bounding boxes according to the specified
area range by computing the area of the bounding box itself. This is done for
both the ground truth bounding boxes and the detected bounding boxes.

While neither approach is perfect, we consider our approach to be
significantly more idiomatic than that of pycocotools. Segmentation maps are
significantly more expensive to produce. As such, most users performing
bounding box detection will likely not have segmentation maps for the data
they are evaluating their model on. This would prevent these users from
mirroring the approach taken in pycocotools. Additionally, it is a confusing
delegation of responsibilities to use a value computed using a segmentation
map to evaluate a metric for bounding box detection. Finally, tracking area of
a segmentation map is simply a pain to the end user. There is no general case
reason for this behavior, and as such we have chosen to deviate from it.

Figure 1: Error distribution for each metric configuration

Figure 2: Error margins for each COCO mean average precision challenge
configuration

Figure 3: Error margins for each COCO recall challenge configuration

##  VII Conclusions

We proposed and implemented an in-graph, mini-batch friendly approach to
compute the COCO recall metric, as well as closely approximating the COCO mean
average precision (MaP) metric. We released an open-source, easy-to-use
implementation of both algorithms as part of the KerasCV package. Our
numerical benchmarks confirm that our implementation produces results that
closely match the most commonly-used prior implementation of both metrics,
available in pycocotools. With our in-graph approach, it becomes easy and
efficient to implement train-time evaluation of object detection models. This
enables researchers and practitioners to leverage the full training curves for
these metric to more effectively compare two models or prototype new models.

## References

  * [1] Tsung-Yi Lin et al.  “Microsoft COCO: Common Objects in Context”  arXiv, 2014  DOI: 10.48550/ARXIV.1405.0312
  * [2] Martín Abadi et al.  “TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems” Software available from tensorflow.org, 2015  URL: https://www.tensorflow.org/
  * [3] Joseph Redmon, Santosh Divvala, Ross Girshick and Ali Farhadi  “You Only Look Once: Unified, Real-Time Object Detection”  arXiv, 2015  DOI: 10.48550/ARXIV.1506.02640
  * [4] Shaoqing Ren, Kaiming He, Ross Girshick and Jian Sun  “Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks”  arXiv, 2015  DOI: 10.48550/ARXIV.1506.01497
  * [5] Tsung-Yi Lin et al.  “Focal Loss for Dense Object Detection”  arXiv, 2017  DOI: 10.48550/ARXIV.1708.02002
  * [6] James Bradbury et al.  “JAX: composable transformations of Python+NumPy programs”, 2018  URL: http://github.com/google/jax
  * [7] Dingfu Zhou et al.  “Iou loss for 2d/3d object detection”  In _2019 International Conference on 3D Vision (3DV)_ , 2019, pp. 85–94  IEEE
  * [8] Alexey Bochkovskiy, Chien-Yao Wang and Hong-Yuan Mark Liao  “Yolov4: Optimal speed and accuracy of object detection”  In _arXiv preprint arXiv:2004.10934_ , 2020
  * [9] Zheng Ge et al.  “YOLOX: Exceeding YOLO Series in 2021”  arXiv, 2021  DOI: 10.48550/ARXIV.2107.08430
  * [10] Ze Liu et al.  “Swin Transformer V2: Scaling Up Capacity and Resolution”  arXiv, 2021  DOI: 10.48550/ARXIV.2111.09883
  * [11] Hao Zhang et al.  “DINO: DETR with Improved DeNoising Anchor Boxes for End-to-End Object Detection”  arXiv, 2022  DOI: 10.48550/ARXIV.2203.03605