August 27, 2024


capbtabboxtable[][]

# Semi-supervised Multimodal Coreference Resolution in Image Narrations

Arushi Goel1, Basura Fernando2, Frank Keller1, and Hakan Bilen1 1School of
Informatics, University of Edinburgh, UK 2CFAR, IHPC, A*STAR, Singapore

###### Abstract

In this paper, we study multimodal coreference resolution, specifically where
a longer descriptive text, i.e., a narration is paired with an image. This
poses significant challenges due to fine-grained image-text alignment,
inherent ambiguity present in narrative language, and unavailability of large
annotated training sets. To tackle these challenges, we present a data
efficient semi-supervised approach that utilizes image-narration pairs to
resolve coreferences and narrative grounding in a multimodal context. Our
approach incorporates losses for both labeled and unlabeled data within a
cross-modal framework. Our evaluation shows that the proposed approach
outperforms strong baselines both quantitatively and qualitatively, for the
tasks of coreference resolution and narrative grounding.

##  1 Introduction

In linguistic processing, coreference resolution is a standard task that aims
to identify referring expressions such as noun phrases and pronouns that refer
to the same entity. It is fundamental to many standard problems including
question answering Kwiatkowski et al. (2019); Das et al. (2017), sentiment
analysis Cambria et al. (2017); Medhat et al. (2014), summarization Gupta and
Lehal (2010); Shi et al. (2021) and machine translation Lopez (2008); Bahdanau
et al. (2014); Wu et al. (2016). In this work, we focus on a multimodal
coreference resolution (MCR) scenario where the coreferences occur in a
narration paired with an image and also link to an image region as shown in
Figure 1. Here resolving coreferences is challenging, as mentions referring to
different entities can be very similar when encoded by a language model, e.g.,
one boy, the other boy, the boy. Hence it demands a fine-grained understanding
of each modality and as well as across them. In particular, it requires
simultaneously grounding instances by identifying fine-grained visual details
(e.g., disambiguating them by recognizing the action ‘crying’, spotting ‘white
color t-shirt and cream color short’ or ‘a white color sticker on the head’),
and capturing long-range dependency across sentences (e.g., two small boys and
their).

Figure 1: Example image-narration pair from the Coreferenced Image Narratives
dataset Goel et al. (2022). Phrases marked in the same color corefer to the
same entity which are also grounded in the image. We do not show singletons
for brevity.

MCR has recently gained increasing attention, with several notable studies
Ramanathan et al. (2014); Huang et al. (2018); Cui et al. (2021); Parcalabescu
et al. (2021); Das et al. (2017); Guo et al. (2022); Goel et al. (2022); Hong
et al. (2023). However, many of them focus on images with simple short
sentences, such as ‘A woman is driving a motorcycle. Is she wearing a helmet?’
Das et al. (2017); Parcalabescu et al. (2021), or are limited to identifying
movie characters or people Ramanathan et al. (2014); Cui et al. (2021). More
recently, Goel et al. (2022) introduced a challenging and unconstrained MCR
problem (see Figure 1) including a dataset, Coreferenced Image Narratives
(CIN), with both people and objects as referents with long textual
descriptions (narrations). As manually annotating a large dataset with
coreferencing and grounding labels is expensive, the authors provide
annotations only for evaluation purposes. They also propose a weakly
supervised method that learns to jointly ground mentions in images and use
them as anchors along with prior linguistic rules Lee et al. (2011) to group
coreferring mentions from only image and narration pairs without the
annotations. The method has multiple shortcomings: (1) weakly supervised
grounding fails to disambiguate multiple instances of the same object class,
boy (one boy, the other boy), (2) language rules such as exact match of
phrases are either too strict or too generic, e.g., pronoun match, linking
pronouns to one antecedent (one boy, he, he, his) and, (3) they require an
additional modality, mouse traces to learn coreferences which can be expensive
to obtain.

Motivated by these limitations, we argue that it difficult to successfully
resolve coreferences from only image-narration pairs in cases where multiple
instances of the same object category are present; this situation is common
coincides with a mention in the narration. Since full manual annotations of
coreference chains and bounding boxes is expensive, we propose to resolve
coreferences and ground mentions in a semi-supervised setting where only a few
data samples are labeled. Our approach involves a customized multi-modal
fusion model that combines image region features and mention features from
narrations through cross-attention Vaswani et al. (2017); Li et al. (2021). We
investigate different task-specific losses for training on labeled and
unlabeled data, and show that naively combining training on the labeled and
pseudo-labeled data suffers from severe overfitting Arazo et al. (2020).
Hence, we propose a robust loss function and thresholding-based training
scheme to effectively learn from the unlabeled set. This novel approach
results in consistent performance improvements with the inclusion of unlabeled
data during training.

Our main contributions are (1) a vision-language framework for MCR trained on
a small labeled and an unlabeled dataset, (2) novel task-specific losses (on
both labeled and pseudo-labeled data) for learning joint multi-modal
embeddings for coreference resolution while simultaneously improving narrative
grounding, (3) extensive evaluation of our proposed method on the CIN dataset
and ablation studies to validate our design choices, showing consistent
performance gains compared to baselines on coreference resolution and
narrative grounding.

##  2 Related work

Multimodal coreference resolution. MCR involves comprehending the contextual
information in language and establishing connections with specific regions in
an image. Recently, considerable efforts have been dedicated to developing
datasets that can effectively address this intricate task. Parcalabescu et al.
(2021) introduced the VALSE dataset, which encompasses various coreference
scenarios. However, this dataset focuses on the downstream task of visual
question answering without evaluating coreference resolution or grounding.
Hence, we evaluate our method on CIN dataset Goel et al. (2022) that contains
coreference chains and grounding annotations. Another approach to MCR datasets
involves linking people’s names mentioned in the text to corresponding images
and resolving pronouns that connect to those specific names Ramanathan et al.
(2014); Cui et al. (2021); Hong et al. (2023). However, our main focus is to
resolve coreferences in a generic scenario (with visual complexity) unlike the
others that are either limited to only people names/characters Ramanathan et
al. (2014); Cui et al. (2021); Hong et al. (2023) or have simple sentences Das
et al. (2017); Parcalabescu et al. (2021).

Vision-language learning. Existing work on vision and language understanding
employs either pre-trained object detector features He et al. (2017); Ren et
al. (2015) as an image encoder, ViT Dosovitskiy et al. (2020) or a CNN
Simonyan and Zisserman (2014) combined with a transformer-based text encoder
Devlin et al. (2018). To model cross-modal interaction between the image and
text encoders, UNITER Chen et al. (2020), ALBEF Li et al. (2021) and VinVL
Zhang et al. (2021b) employ a multimodal encoder. They are pre-trained on
large-scale image-caption pairs such as COCO Lin et al. (2014), Conceptual
captions Sharma et al. (2018); Changpinyo et al. (2021), Visual Genome Krishna
et al. (2017). The pre-training objectives are implemented with image-text
contrastive loss, masked language modeling, and image-text matching loss. Our
method is inspired by these architectures and is trained using a set of self-
supervised and task-based objectives in a semi-supervised learning fashion.

Semi-supervised learning. There is a large body of work in semi-supervised
learning Zhai et al. (2019); Van Engelen and Hoos (2020); Ouali et al. (2020).
These methods typically exploit unlabeled data via either pseudo-labeling with
small amounts of labeled data Lee et al. (2013); Arazo et al. (2020); Rizve et
al. (2021); Sohn et al. (2020); Zhang et al. (2021a) or by enforcing
consistency regularization Berthelot et al. (2019); Abuduweili et al. (2021)
on the unlabeled data to produce consistent predictions over various
perturbations of the same input by applying several augmentation strategies
Zhang et al. (2017); Cubuk et al. (2018, 2020). Our method draws inspiration
from pseudo-labeling literature and uses a robust loss function and
thresholding to counter overfitting to pseudo-labels.

##  3 Method

###  3.1 Task Overview

Our goal is (1) to group mentions (i.e., referential words or phrases) in the
narration that corefer to the same entity and, (2) to ground each mention to a
region in an image. Formally, let $N=\\{m_{1},m_{2},\dots,m_{|N|}\\}$ denote a
narration with $|N|$ mentions for an image $I$ with $|I|$ regions where
$I=\\{r_{1},r_{2},\dots,r_{|I|}\\}$. We wish to learn an embedding function
$f$ that takes in an image $I$ and its narration $N$, parsed to contain a set
of mentions, and outputs a score for a mention pair $(m,m^{\prime})$:

$\frac{f(m)\cdot f(m^{\prime})}{|f(m)||f(m^{\prime})|}$ (1)

The mention pair $m$ and $m^{\prime}$ corefers if the score in Equation 1 is
high, otherwise they do not.

For grounding of the mention $m$ on the image region $r$, we also learn
another function $g$ that outputs a score for the mention $m$ being located at
region $r$ in image $I$. Next, we describe in detail our methodology to learn
the two functions $f$ and $g$.

Figure 2: Illustration of our model architecture and training methodology. The
pre-extracted image regions are fed into the visual encoder, the narrations
are fed into the text encoder and both modalities are fused using a multimodal
encoder. The model is optimized using self-supervised objectives (in grey) and
specialized task-based losses on both the labeled data (in yellow boxes) and
the pseudo-labeled data (in green boxes).

###  3.2 Model Architecture

In Figure 2, we illustrate our model architecture. Each image is parsed into a
set of regions through a pre-trained object detector Ren et al. (2015), where
each region $r$ is represented by a $d$-dimensional joint embedding
$\bm{v}_{r}\in\mathbb{R}^{d}$ including its visual, semantic and spatial
features. In particular, the visual encoder $f_{v}$ is instantiated as a
transformer block that takes in a joint feature embedding $\bm{v}_{r}$ for the
object region $r$ and outputs a $D$ dimensional embedding, i.e.,
$f_{v}(\bm{v}_{r}):\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}$.

Furthermore, we encode the words in each narration $N$ using a tokenizer
Devlin et al. (2018) to get a set of tokens for the words $w\in\mathbb{R}^{V}$
where $V$ is the vocabulary size. The text encoder $f_{t}$ which is also a
transformer block that takes in the word token $w$ and outputs a $D$
dimensional embedding, i.e.,
$f_{t}(w):\mathbb{R}^{V}\rightarrow\mathbb{R}^{D}$. The mention embeddings are
computed by averaging its corresponding word representations as:
$f_{t}(m)=\frac{1}{|m|}\sum_{w\in m}f_{t}(w)$ where, $|m|$ indicates the
mention length in words, and the embeddings $f_{t}(m)$ have the same
dimensionality as the visual features.

Next, the multi-modal encoder $f$ fuses the visual features from the visual
encoder $f_{v}(\bm{v}_{r})$ with the mention features from the text encoder
$f_{t}(m)$. Similar to the cross-modal architectures Li et al. (2021); Zhang
et al. (2021b), the embeddings from the text encoder are first encoded using
self-attention layers Vaswani et al. (2017). Then, a multi-head cross
attention module integrates the textual and visual features. In the cross-
attention module, the self-attended mention embeddings $f_{t}(m)$ are treated
as the query, while the image representations $f_{v}(\bm{v}_{r})$ are treated
as keys and values. The attention weights between the mention $m$ and the
region $r$ are given as:

$\begin{split}g(m,r)=\frac{\exp(\frac{f_{t}(m)^{T}.f_{v}(\bm{v}_{r})}{\sqrt{d}})}{\sum_{r^{\prime}\in
I}\exp(\frac{f_{t}(m)^{T}.f_{v}(\bm{v}_{r^{\prime}})}{\sqrt{d}})}\end{split}$
(2)

where the softmax is computed over the image regions for each mention. This
attention matrix (or the grounding function) $g$ from the multi-head cross
attention learns fine-grained mention to region alignment scores. Finally, the
vision-aware mention embedding is represented as:

$f(m)=g(m,r).{f_{v}({\bm{v}_{r}})}$ (3)

where, $f(m)\in\mathbb{R}^{D}$. This weighted embedding is then passed to a
feed-forward module Li et al. (2021) with an MLP and layer normalization. All
the transformer encoders/blocks are based on the architecture proposed by Li
et al. (2021). It is important to note that compared to Goel et al. (2022),
our model fuses vision and text features with a multimodal encoder, unlike
theirs.

###  3.3 Semi-supervised Learning

Concretely, we aim to learn the parameters of the modules $f_{v}$, $f_{t}$ and
$f$ given a training dataset $\mathcal{D}$ with $|\mathcal{D}|$ samples of
image-narration pairs. Specifically, we use a small labeled set
$\mathcal{D}_{s}=\\{x_{i},y_{i}\\}_{i=1}^{{|\mathcal{D}_{s}|}}$ where
$x_{i}=\\{I,N\\}$ is the image-narration input pair and $y_{i}=\forall_{m\in
N}\\{P(m),A(m),b_{m}\\}$ is the label for the input pair. In particular, the
label for each mention $m$ in the narration is given as: $P(m)$ and $A(m)$,
the set of positive and negative mentions respectively for the mention $m$ and
$b_{m}$, the bounding-box coordinates of the region corresponding to the
mention $m$.

Due to the unavailability of a large labeled training set, we leverage the
unlabeled data $\mathcal{D}_{u}$ = $\mathcal{D}\setminus\mathcal{D}_{s}$
where, $\mathcal{D}_{u}=\\{x_{i}\\}_{i=1}^{{|\mathcal{D}_{u}|}}$ with only
image-narration pairs as inputs. Our overall training objective is the joint
loss function as follows:

$\sum_{(x,y)\in\mathcal{D}_{s}}\frac{1}{|\mathcal{D}_{s}|}\mathcal{L}_{s}(x,y)+\sum_{x\in\mathcal{D}_{u}}\frac{1}{|\mathcal{D}_{u}|}\mathcal{L}_{u}(x)$
(4)

where, $\mathcal{L}_{s}$ is the supervised loss and $\mathcal{L}_{u}$ is the
unsupervised loss. First, we discuss how to formulate task-based supervised
losses on the dataset $\mathcal{D}_{s}$.

(S1) Coreference loss (CR) Specifically, we propose to learn the similarity
between the mention embeddings using a supervised contrastive loss Khosla et
al. (2020) which is defined as:

$\begin{split}\mathcal{L}_{cr}=\sum_{m\in N}\frac{-1}{|P(m)|}\sum_{p\in
P(m)}\\\ \text{log}\frac{exp(f(m).f(p)/\tau)}{\sum_{a\in
A(m)}exp(f(m).f(a)/\tau)}\end{split}$ (5)

where $\tau$ is the temperature. This loss helps to cluster embeddings for
coreferring mentions together and push the embeddings of non-referrants away
from each other.

(S2) Grounding loss (GD) To align the mention $m$ and region $r$, we use the
grounding function $g$ defined in Equation 2. In particular, we first define
the ground-truth binary alignment on the labeled training set
$\mathcal{D}_{s}$. For the ground-truth bounding box $b_{m}$ for a mention $m$
we compute the intersection over union (IoU) between this bounding-box and the
$R$ pre-extracted image regions. This is crucial because we don’t have the
exact region-mention match for the detections from the object detector.
Following this, we get the binary alignment function $h(m,r)$, which is 1 for
the mention $m$ and the detected image region $r$ if the region $r$ has the
maximum IoU overlap with the ground-truth bounding box $b_{m}$, and 0
otherwise. Once we have the ground-truth alignment $h(m,r)$, we compute the
cross-entropy loss as:

$\mathcal{L}_{gd}=-\sum_{m\in N}\sum_{r\in I}h(m,r)\text{log}(g(m,r))$ (6)

(S3) Bounding box regression loss (BBR) We further propose to add additional
supervision to refine the object proposals from the detector for a mention.
For each mention $m$, the ground-truth bounding box localization is
represented as $b_{m}=(x,y,w,h)$. To learn refinements, we predict the box
deltas from the model as
$\delta_{m}=(\delta_{x},\delta_{y},\delta_{w},\delta_{h})$ for each mention
$m$. We then take the highest scoring region for a given mention $m$ as:

$r_{m}=\operatorname*{arg\,max}_{r\in I}g(m,r).$ (7)

Our goal is to learn a transformation that maps a proposed box $r_{m}$ to a
ground-truth box $b_{m}$. We then apply the smooth-L1 loss following Ren et
al. (2015), denoted as $\mathcal{L}_{bbr}$. Further details about this loss
are given in the appendix.

Next, we discuss how to train on the unlabeled subset of the dataset by
generating pseudo-labels for the coreference and grounding tasks.

(U1) Pseudo coreference loss (PCR) Given the unlabeled dataset
$\mathcal{D}_{u}$, we compute the pseudo coreferring pairs for the mentions in
$N$. More specifically, we compute pseudo-positives $\hat{P}(m)$ and pseudo-
negatives $\hat{A}(m)$ for a mention $m$ by computing the cosine similarity
between the embeddings as in Equation 1. For each mention $m$, if the
similarity with another mention $m^{\prime}$ is greater than a threshold then
we label it as a positive otherwise a negative. Finally, we compute the
triplet loss as:

$\begin{split}\mathcal{L}_{pcr}=\\\ \sum_{m\in
N}\text{max}(||f(m)-\frac{1}{|\hat{P}(m)|}\sum_{p\in\hat{P}(m)}f(p)||^{2}\\\
-||f(m)-\frac{1}{|\hat{A}(m)|}\sum_{a\in\hat{A}(m)}f(a)||^{2}+\alpha,0)\end{split}$
(8)

where $\alpha$ is the margin, $f(m)$ is the embeddings for the query mention
$m$, $\frac{1}{|\hat{P}(m)|}\sum_{p\in\hat{P}(m)}f(p)$ is the mean of
embeddings of the pseudo-positive labels $\hat{P}(m)$ and
$\frac{1}{|\hat{A}(m)|}\sum_{a\in\hat{A}(m)}f(a)$ is the mean of embeddings of
the pseudo-negative labels $\hat{A}(m)$.

The key intuition behind using the mean in a triplet loss formulation is to
reduce overfitting to the noise in the pseudo labels. This works better in
practice compared to the contrastive loss formulation in Equation 5 or mining
a random positive/negative label for the standard triplet loss, especially
when dealing with pseudo labels.

(U2) Pseudo grounding loss (PGD) Furthermore, we compute the pseudo grounding
loss on the unlabeled training dataset. Specifically, we impute the pseudo-
labels from the grounding function, $g(m,r)$. We only consider samples whose
grounding score is greater than a confidence threshold $t$, which is set to
0.9 in our experiments. The high threshold value ensures that we consider only
confident samples in the unlabeled set and eliminates learning from noisy
samples. We denote this label after binary thresholding as $\hat{h}(m,r)$. The
pseudo grounding alignment loss is:

$\mathcal{L}_{pgd}=\sum_{m\in N}\sum_{r\in I}-\hat{h}(m,r)\text{log}(g(m,r))$
(9)

Apart from the above mentioned task-based losses, we combine the standard
image-text pretraining losses Vaswani et al. (2017); Li et al. (2021). These
losses help to learn better unimodal representations before fusion.

(U3) Image-Text contrastive loss (ITC) Following Goel et al. (2022), we
incorporate the contrastive loss to align the image and narration pairs to
learn better representations before fusion. This loss is defined as:

$\mathcal{L}_{itc}=\sum_{m\in
N}-\log\big{(}\frac{\exp(f_{v}(\bm{v}_{r})f_{t}(m))}{\sum_{r^{\prime}\in
I}\exp(f_{v}(\bm{v}_{r^{\prime}})f_{t}(m)))}\big{)}$ (10)

where $f_{v}(\bm{v}_{r})f_{t}(m)$ is the mention-region matching score from
the visual and text representations before fusing in the multi-modal encoder
and $\bm{v}_{r}$ are the raw features for the highest scoring region for a
mention $m$.

(U4) Masked language modeling loss (MLM) To fine-tune the pretrained BERT
model Devlin et al. (2018) on the image-narration data, we also use the pre-
trained task of masked language modeling. In particular, the input word tokens
are randomly masked and are replaced by a special masking token. The model
needs to predict the mask token based on the unmasked words. This task is
trained with a cross-entropy loss, $\mathcal{L}_{mlm}$.

Hence, our overall training objective in Equation 4 is a combination of
specialized task losses on the labeled training set $\mathcal{D}_{s}$
($\mathcal{L}_{cr}$, $\mathcal{L}_{gd}$ and $\mathcal{L}_{bbr}$) and the
unlabeled training set $\mathcal{D}_{u}$ ($\mathcal{L}_{pcr}$ and
$\mathcal{L}_{pgd}$) and global pre-training objectives on the entire training
dataset $\mathcal{D}$ ($\mathcal{L}_{itc}$ and $\mathcal{L}_{mlm}$).

###  3.4 Inference

To obtain the coreference scores, we form chains by measuring the cosine
similarity between the mentions as described in Equation 1, considering the
pairs with similarity higher than a predefined threshold as positives. When
evaluating narrative grounding, we extract the cross-attention scores from the
last layer of the multimodal encoder. For each mention, we identify the region
with the highest softmax score as the positively referred region.

##  4 Experiments

Method | Modality | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---|---
Text | Image | R | P | F1 | R | P | F1 | R | P | F1 | F1
Neural Coref Lee et al. (2017)†∗ | ✓ | ✗ | 0.11 | 0.17 | 0.13 | - | - | - | - | - | - | -
longdoc Toshniwal et al. (2021)∗ | ✓ | ✗ | 7.79 | 8.43 | 7.24 | 62.27 | 76.10 | 67.69 | 48.77 | 84.95 | 61.02 | 45.31
VisualBERT Su et al. (2019)∗ | ✓ | ✓ | 18.17 | 6.08 | 8.06 | 69.01 | 36.08 | 41.03 | 21.25 | 57.10 | 28.67 | 25.92
UNITER Chen et al. (2020)∗ | ✓ | ✓ | 16.92 | 7.15 | 8.83 | 68.34 | 44.29 | 50.22 | 28.12 | 72.78 | 38.91 | 32.65
VinVL Zhang et al. (2021b)∗ | ✓ | ✓ | 16.76 | 8.60 | 9.75 | 68.49 | 62.32 | 61.30 | 42.88 | 80.81 | 53.69 | 41.58
MAF Wang et al. (2020) | ✓ | ✓ | 19.07 | 15.62 | 15.65 | - | - | - | - | - | - | -
WS-MCR Goel et al. (2022) | ✓ | ✓ | 24.87 | 18.34 | 19.19 | - | - | - | - | - | - | -
Ours | ✓ | ✗ | 13.30 | 14.12 | 12.55 | 67.91 | 79.48 | 72.41 | 56.05 | 86.20 | 67.05 | 50.67
✓ | ✓ | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 1: Coreference resolution results on the CIN dataset Goel et al. (2022)
from our proposed method and other state-of-the-art unimodal and multi-modal
baselines. $\dagger$ indicates the use of predicted mentions, while the other
results rely on ground-truth mentions during inference. $*$ means zero-shot
performance.

Datasets.  We evaluate our proposed method on the CIN dataset Goel et al.
(2022) that consists of 1000 test and 880 validation image-narration pairs
from the Flickr30k split of the Localized Narratives dataset Pont-Tuset et al.
(2020) annotated with coreference chains and bounding boxes. We use the test
split of the CIN dataset to report the performance on CR and narrative
grounding. The annotations from the validation split are used as the small
labeled set during training. The unlabeled dataset is the Flickr30k training
subset of the Localized Narratives dataset, which consists of 50k image-
narration pairs but is not annotated with bounding boxes or coreference
chains.

Implementation details. For the image regions, we extract bounding box
regions, visual features and object class labels using the Faster-RCNN object
detector Ren et al. (2015) as in Goel et al. (2022). We use a 4-layer
transformer architecture for the text encoder and the multi-modal encoder
similar to the ALBEF Li et al. (2021) framework. The weights of the
transformer encoders are initialized with the first four layers of BERT Devlin
et al. (2018). The visual encoder is a stack of two transformer encoder
layers. Each transformer encoder layer includes a multi-head self-attention
layer and an FFN. There are two heads in the multi-head attention layer, and
two FC layers followed by ReLU activation layers in the FFN. Training details
are in the appendix.

Evaluation. We report results for coreference resolution and narrative
grounding. For the former, we use the standard CoNLL F1 score which is the
average of three coreference-based metrics: MUC, B3 and CEAFϕ4. For the
latter, we follow Goel et al. (2022) and report the grounding accuracy for
both noun phrases and pronouns. More precisely, if the overlap between the
ground-truth box and the predicted box is greater than 0.5, then it is
considered to be a correct prediction.

##  5 Results and Discussion

###  5.1 Coreference Resolution

Table 1 reports the coreference resolution performance on the CIN dataset Goel
et al. (2022) for our method and the baselines. Further details about the
baselines are given in the appendix. The text-based baselines Neural Coref Lee
et al. (2017) and longdoc Toshniwal et al. (2021) are evaluated in a zero-shot
way on the task. Their low CoNLL F1 scores indicate the incapability of the
model to generalize to new domains which is in line with what has been
evaluated extensively in the coreference literature Toshniwal et al. (2021);
Xia and Van Durme (2021); Gandhi et al. (2023).

We further compare to strong multi-modal baselines by directly evaluating the
VLMs in a zero-shot way on the CIN dataset. Interestingly, all three methods:
VisualBERT Su et al. (2019), UNITER Chen et al. (2020) and VinVL Zhang et al.
(2021b) perform better in MUC and B3 compared to the text-based baseline,
longdoc Toshniwal et al. (2021), but drop in performance on the average CoNLL
F1 scores. These results show the inability of these models to effectively
find singletons, hence leading to poor performance in the precision scores.
Moreover, we can conclude that the vision and language pre-trained models fail
to generalize for MCR.

We also compare to two weakly supervised methods that are trained on the CIN
dataset, MAF Wang et al. (2020) and WS-MCR Goel et al. (2022). Goel et al.
(2022) present results on the MAF model as a baseline and their proposed
method, WS-MCR. MAF is a weakly supervised grounding method trained with ITC
that is evaluated for CR and WS-MCR Goel et al. (2022) learns weakly-
supervised grounding and CR combining the ITC loss and prior linguistic rules.
Both of these methods improve significantly in MUC scores compared to other
zero-shot unimodal and multi-modal baselines.

Finally, we compare with the text-only variant (without any images) of our
method. This method improves over the baselines on the CoNLL F1 scores. The
significant gains in performance of our final method, with both text and
image, combined with label supervision shows the importance of carefully
tuning the model with a small amount of labeled data and large amounts of
pseudo-labeled data.

###  5.2 Narrative Grounding

In Table 2, we present a comprehensive comparison between the baselines and
our proposed approach on the task of narrative grounding. This task is both
challenging and crucial, as it evaluates the precise alignment between image
regions and phrases in textual data. Notably, our proposed method goes beyond
the traditional alignment of noun phrases and also addresses the grounding
pronouns, which is vital for multimodal coreference resolution. We measure
noun phrase grounding, pronoun grounding, and overall accuracy to measure
performance Goel et al. (2022).

Remarkably, our proposed method exhibits superior performance compared to
weakly supervised baselines, showing a margin of improvement if approximately
2% and 2.5% in noun phrase and pronoun grounding accuracy, respectively.
Furthermore, when compared to our unsupervised baseline, namely “Ours (ITC \+
MLM)”, the inclusion of labeled and pseudo-labeled data yields a significant
performance boost of approximately 6%. These results demonstrate the
significance of training with both grounding alignment and coreference
resolution loss, highlighting the mutual benefits derived from this approach.

Method | Noun Phrases | Pronouns | Overall
---|---|---|---
MAF Wang et al. (2020) | 21.60 | 18.31 | 20.91
WS-MCR Goel et al. (2022) | 30.27 | 25.96 | 29.36
Ours (ITC \+ MLM) | 27.44 | 22.77 | 26.45
Ours (Full) | 32.58 | 28.45 | 31.71

Table 2: Comparison of narrative grounding performance on the CIN dataset Goel
et al. (2022).

###  5.3 Ablation Study

Varying labeled and unlabeled data. We study the impact of labeled data on the
learning process, allowing us to showcase the strengths of our approach. In
Table 3, we measure the model’s performance on CoNLL F1 scores at different
proportions of labeled data (20% and 50%). Remarkably, despite the limited
amount of labeled data samples, the model demonstrates consistently high
performance without any significant drop. This highlights the exceptional
ability of our model to effectively learn from a small labeled set, without
relying on a large number of annotated training samples.

Data type | % Samples | CoNLL F1
---|---|---
Labeled | 20% | 60.04
50% | 61.24
Unlabeled | 20% | 56.82
50% | 59.11

Table 3: CR performance by changing the amount of labeled and unlabeled data
during training.

Furthermore, to validate the efficacy of our proposed method, we also
investigate the influence of unlabeled data samples during training. Following
the same data split as in the supervised experiments, we observe the changes
in performance indicated by row 2 in Table 3. As the quantity of unlabeled
samples increases, the model exhibits enhanced coreference resolution
performance. This result reinforces the ability of our proposed method to
leverage and effectively learn from pseudo-labeled data. Detailed results are
in the appendix.

Losses | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
PCR(U1) |  PGD(U2) |  ITC(U3) |  MLM (U4) |  CR (S1) |  GD (S2) |  BBR (S3) | R | P | F1 | R | P | F1 | R | P | F1 | F1
✗ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | 23.81 | 25.83 | 23.12 | 69.32 | 85.87 | 76.41 | 61.00 | 89.69 | 72.05 | 57.19
✗ | ✗ | ✓ | ✓ | ✓ | ✗ | ✗ | 22.70 | 21.40 | 20.23 | 69.05 | 80.03 | 73.66 | 55.52 | 87.09 | 67.20 | 53.70
✓ | ✗ | ✓ | 23.86 | 24.52 | 22.31 | 69.31 | 84.15 | 75.67 | 59.50 | 89.15 | 70.80 | 56.26
✓ | ✓ | ✓ | 27.68 | 29.04 | 26.66 | 69.93 | 85.43 | 76.61 | 60.92 | 90.61 | 72.26 | 58.51
✓ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | 30.66 | 32.82 | 30.31 | 70.70 | 86.09 | 77.33 | 62.64 | 92.92 | 74.27 | 60.64
✓ | ✓ | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 4: Ablation study on our proposed method with the combination of the
proposed losses.

CR Loss | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
on $\mathcal{D}_{s}$ | on $\mathcal{D}_{u}$ | R | P | F1 | R | P | F1 | R | P | F1 | F1
BCE | BCE | 23.63 | 23.55 | 21.57 | 69.50 | 81.94 | 74.47 | 57.68 | 88.01 | 68.95 | 55.00
CR | CR | 28.20 | 22.47 | 23.08 | 70.10 | 76.29 | 72.40 | 52.32 | 87.22 | 64.71 | 53.40
CR | RTC | 29.24 | 32.41 | 29.46 | 70.37 | 86.71 | 77.45 | 63.14 | 92.59 | 74.55 | 60.49
CR | PCR | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 5: Performance comparison with the choice of coreference resolution loss
on the labeled dataset $\mathcal{D}_{s}$ and the unlabeled dataset
$\mathcal{D}_{u}$.

Impact of different loss functions. In Table 4, we assess the performance of
coreference resolution by incorporating various losses proposed in Section 3.
Throughout the training process, the model consistently integrates the self-
supervised objectives of ITC and MLM, see first row of Table 4.

Integrating the supervised contrastive coreference resolution loss, CR, in
addition to ITC and MLM, results in a significant performance drop. Due to the
limited availability of labeled data, the model struggles to effectively
generalize for coreference resolution, leading to overfitting and consequently
lower F1 scores. However, by progressively incorporating the bounding box
regression loss, BBR, and the grounding alignment loss GD, we get a much
stronger training signal even with a small labeled set. This multi-task
training objective contributes to an improvement of approximately 1.5% in the
CoNLL F1 score.

Subsequently, we investigate the impact of incorporating loss on pseudo-
labeled data. By introducing the pseudo coreference loss, denoted as PCR, we
observe a remarkable improvement of approximately 2% in the CoNLL F1 scores.
This result highlights the significance of leveraging pseudo clusters and
underscores the effectiveness of our proposed robust triplet loss, which
computes the triplet loss using the mean of positive and negative embeddings.
Notably, this approach successfully incorporates pseudo-labeled data without
leading to overfitting while achieving substantial performance gains.
Consequently, our final proposed method, which integrates the pseudo grounding
loss, PGD, exhibits the most superior overall performance, validating the
potency of pseudo-labels for both coreference resolution and grounding.

Choice of coreference resolution loss. In Table 5, we examine the impact of
different types of coreference resolution losses. We present a comparison of
the following loss combinations: (1) Binary cross-entropy loss (BCE) applied
to both $\mathcal{D}_{s}$ and $\mathcal{D}_{u}$, (2) Supervised contrastive
loss (CR) applied to both $\mathcal{D}_{s}$ and $\mathcal{D}_{u}$, and (3)
Supervised contrastive loss (CR) on $\mathcal{D}_{s}$ and random triplet
mining loss (RTC) on $\mathcal{D}_{u}$.

We observed a significant performance drop when training with the BCE loss,
compared to utilizing the supervised contrastive loss. We hypothesize that the
supervised contrastive loss provides a better clustering of mentions by
contrasting them in the embedding space directly than the binary cross-entropy
loss. Consequently, the embeddings become more robust for CR, contributing to
improved performance.

Interestingly, when applying the supervised contrastive loss to
$\mathcal{D}_{u}$ (row 2), we observed a drop in performance. Our hypothesis
is that the contrastive loss tends to overfit in the presence of noisy pseudo
labels, leading to a degradation in performance. In contrast, our pseudo
triplet loss formulation PCR is softer in penalizing noisy pseudo labels. This
allows the model to gradually adapt and become more resilient to such noise,
resulting in more efficient clustering of mentions. We also compare to another
ablation where instead of taking the mean of the embeddings for pseudo-
positive labels and pseudo-negative labels, we sample a random positive and
negative label (results in row 3) abbreviated as RTC. Randomly sampling the
labels generalizes better than the other ablations but the mean cluster
embeddings outperforms than randomly selecting samples.

Figure 3: Visualization for grounding and coreference resolution. The colored
boxes in image correspond to the mentions with the same color in the sentence.

###  5.4 Qualitative Results

In Figure 3, we qualitatively visualize the performance of our method and
compare it with the weakly supervised baseline from Goel et al. (2022). Our
model correctly separates the mentions the front man and the the man both
during CR and grounding, whereas the WS-MCR Goel et al. (2022) method
incorrectly assigns the mention the man to the the front man and grounds it
incorrectly too (denoted by the blue dotted line). Hence, our method can
effectively learn to disambiguate the instances based on the visual details
which is also helpful for coreference resolution.

##  6 Conclusion

In conclusion, this paper addresses the challenging task of multimodal
coreference resolution where an image is accompanied by a longer descriptive
text. We propose a data efficient semi-supervised approach that incorporates
task-based losses for both labeled and unlabeled data, operating within a
cross-modal framework. Our method achieves remarkable results for CR and
narrative grounding tasks on the CIN dataset, showcasing its effectiveness in
handling the complexities of MCR. In the future, we plan to investigate how
the power of pre-training combined with semi-supervised fine-tuning can be
fully utilized for the task of MCR.

## Limitations

Here, we outline limitations that are important considerations for future
work.

First, the current model’s performance in coreference resolution and grounding
is limited by the use of a pre-trained object detector. The detectors
pretrained for object detection task have a limited object category vocabulary
and lack in fine-grained properties including adjectives, human actions and
the open vocabulary found in narrations. This forces the model to rely on a
predetermined set of regions and object classes, preventing it from directly
learning region coordinates for a mention on an image. To improve performance,
we envision the development of an end-to-end approach that eliminates this
reliance on pre-defined regions.

Second, our model currently depends on ground-truth mentions to resolve
coreferences and ground them. In the future, one promising direction would be
to detect mentions simultaneously with coreference resolution and grounding.
This would significantly improve the applicability of our proposed method and
reduce dependence on off-the-shelf mention detectors or ground-truth
annotations.

## Ethics Statement

All datasets used in this work have been previously released. The use of the
CIN dataset Goel et al. (2022) in our paper is consistent with their intended
use. The detail of the dataset is describied in Goel et al. (2022). Multimodal
datasets frequently include social biases, and we expect the models trained on
them to reflect the biases in these datasets. It is important to note that
multimodal models have both beneficial and harmful applications. Beneficial
applications include advanced image and video retrieval, visual description
systems to assist the visually impaired, and user interfaces that enhance
interaction with smart home devices. However, harmful applications, such as
non-consensual surveillance or fine-tuning models to retrieve inappropriate
content, must be carefully addressed and mitigated.

## Acknowledgements

AG is supported by the Armeane Choksi Scholarship and HB is supported by the
EPSRC programme grant Visual AI EP/T028572/1 and HB and FK are supported by
Edinburgh Laboratory for Integrated Artificial Intelligence (ELIAI). This
research/project is supported by the National Research Foundation, Singapore,
under its NRF Fellowship (Award NRF-NRFF14-2022-0001). Thanks to Nikita Moghe
and Matt Grenander for discussions and constructive feedback.

## References

  * Abuduweili et al. (2021) Abulikemu Abuduweili, Xingjian Li, Humphrey Shi, Cheng-Zhong Xu, and Dejing Dou. 2021.  Adaptive consistency regularization for semi-supervised transfer learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6923–6932.
  * Arazo et al. (2020) Eric Arazo, Diego Ortego, Paul Albert, Noel E O’Connor, and Kevin McGuinness. 2020\.  Pseudo-labeling and confirmation bias in deep semi-supervised learning.  In _2020 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_.
  * Berthelot et al. (2019) David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. 2019.  Mixmatch: A holistic approach to semi-supervised learning.  _Advances in neural information processing systems_ , 32.
  * Cambria et al. (2017) Erik Cambria, Dipankar Das, Sivaji Bandyopadhyay, Antonio Feraco, et al. 2017.  A practical guide to sentiment analysis.
  * Changpinyo et al. (2021) Soravit Changpinyo, Piyush Sharma, Nan Ding, and Radu Soricut. 2021.  Conceptual 12m: Pushing web-scale image-text pre-training to recognize long-tail visual concepts.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3558–3568.
  * Chen et al. (2020) Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. 2020.  Uniter: Universal image-text representation learning.  In _European conference on computer vision_ , pages 104–120. Springer.
  * Cubuk et al. (2018) Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. 2018\.  Autoaugment: Learning augmentation policies from data.  _arXiv preprint arXiv:1805.09501_.
  * Cubuk et al. (2020) Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. 2020.  Randaugment: Practical automated data augmentation with a reduced search space.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops_ , pages 702–703.
  * Cui et al. (2021) Yuqing Cui, Apoorv Khandelwal, Yoav Artzi, Noah Snavely, and Hadar Averbuch-Elor. 2021.  Who’s waldo? linking people across text and images.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1374–1384.
  * Das et al. (2017) Abhishek Das, Satwik Kottur, Khushi Gupta, Avi Singh, Deshraj Yadav, José MF Moura, Devi Parikh, and Dhruv Batra. 2017.  Visual dialog.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 326–335.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * 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. 2020.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_.
  * Gandhi et al. (2023) Nupoor Gandhi, Anjalie Field, and Emma Strubell. 2023.  Annotating mentions alone enables efficient domain adaptation for coreference resolution.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 10543–10558, Toronto, Canada. Association for Computational Linguistics.
  * Girshick (2015) Ross Girshick. 2015.  Fast r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 1440–1448.
  * Goel et al. (2022) Arushi Goel, Basura Fernando, Frank Keller, and Hakan Bilen. 2022.  Who are you referring to? weakly supervised coreference resolution with multimodal grounding.  _arXiv preprint arXiv:2211.14563_.
  * Guo et al. (2022) Danfeng Guo, Arpit Gupta, Sanchit Agarwal, Jiun-Yu Kao, Shuyang Gao, Arijit Biswas, Chien-Wei Lin, Tagyoung Chung, and Mohit Bansal. 2022.  Gravl-bert: Graphical visual-linguistic representations for multimodal coreference resolution.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 285–297.
  * Gupta and Lehal (2010) Vishal Gupta and Gurpreet Singh Lehal. 2010.  A survey of text summarization extractive techniques.  _Journal of emerging technologies in web intelligence_ , 2(3):258–268.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. 2017.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2961–2969.
  * Hong et al. (2023) Xudong Hong, Asad Sayeed, Khushboo Mehra, Vera Demberg, and Bernt Schiele. 2023\.  Visual writing prompts: Character-grounded story generation with curated image sequences.  _arXiv preprint arXiv:2301.08571_.
  * Huang et al. (2018) De-An Huang, Shyamal Buch, Lucio Dery, Animesh Garg, Li Fei-Fei, and Juan Carlos Niebles. 2018.  Finding" it": Weakly-supervised reference-aware visual grounding in instructional videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5948–5957.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. 2020.  Supervised contrastive learning.  _Advances in neural information processing systems_ , 33:18661–18673.
  * Krishna et al. (2017) Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al. 2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  _International journal of computer vision_ , 123(1):32–73.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. 2019.  Natural questions: a benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:453–466.
  * Lee et al. (2013) Dong-Hyun Lee et al. 2013.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.  In _Workshop on challenges in representation learning, ICML_ , volume 3, page 896.
  * Lee et al. (2011) Heeyoung Lee, Yves Peirsman, Angel Chang, Nathanael Chambers, Mihai Surdeanu, and Dan Jurafsky. 2011.  Stanford’s multi-pass sieve coreference resolution system at the conll-2011 shared task.  In _Proceedings of the fifteenth conference on computational natural language learning: Shared task_ , pages 28–34.
  * Lee et al. (2017) Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. 2017.  End-to-end neural coreference resolution.  _arXiv preprint arXiv:1707.07045_.
  * Li et al. (2021) Junnan Li, Ramprasaath R. Selvaraju, Akhilesh Deepak Gotmare, Shafiq Joty, Caiming Xiong, and Steven Hoi. 2021.  Align before fuse: Vision and language representation learning with momentum distillation.  In _NeurIPS_.
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context.  In _European conference on computer vision_ , pages 740–755. Springer.
  * Lopez (2008) Adam Lopez. 2008.  Statistical machine translation.  _ACM Computing Surveys (CSUR)_ , 40(3):1–49.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_.
  * Medhat et al. (2014) Walaa Medhat, Ahmed Hassan, and Hoda Korashy. 2014.  Sentiment analysis algorithms and applications: A survey.  _Ain Shams engineering journal_ , 5(4):1093–1113.
  * Ouali et al. (2020) Yassine Ouali, Céline Hudelot, and Myriam Tami. 2020.  An overview of deep semi-supervised learning.  _arXiv preprint arXiv:2006.05278_.
  * Parcalabescu et al. (2021) Letitia Parcalabescu, Michele Cafagna, Lilitta Muradjan, Anette Frank, Iacer Calixto, and Albert Gatt. 2021.  Valse: A task-independent benchmark for vision and language models centered on linguistic phenomena.  _arXiv preprint arXiv:2112.07566_.
  * Plummer et al. (2015) Bryan A Plummer, Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svetlana Lazebnik. 2015.  Flickr30k entities: Collecting region-to-phrase correspondences for richer image-to-sentence models.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2641–2649.
  * Pont-Tuset et al. (2020) Jordi Pont-Tuset, Jasper Uijlings, Soravit Changpinyo, Radu Soricut, and Vittorio Ferrari. 2020.  Connecting vision and language with localized narratives.  In _European conference on computer vision_ , pages 647–664. Springer.
  * Ramanathan et al. (2014) Vignesh Ramanathan, Armand Joulin, Percy Liang, and Li Fei-Fei. 2014.  Linking people in videos with “their” names using coreference resolution.  In _European conference on computer vision_ , pages 95–110. Springer.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. 2015.  Faster r-cnn: Towards real-time object detection with region proposal networks.  _Advances in neural information processing systems_ , 28.
  * Rizve et al. (2021) Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. 2021.  In defense of pseudo-labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning.  _arXiv preprint arXiv:2101.06329_.
  * Sharma et al. (2018) Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. 2018.  Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2556–2565.
  * Shi et al. (2021) Tian Shi, Yaser Keneshloo, Naren Ramakrishnan, and Chandan K Reddy. 2021.  Neural abstractive text summarization with sequence-to-sequence models.  _ACM Transactions on Data Science_ , 2(1):1–37.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_.
  * Sohn et al. (2020) Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. 2020.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  _Advances in neural information processing systems_ , 33:596–608.
  * Su et al. (2019) Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. 2019\.  Vl-bert: Pre-training of generic visual-linguistic representations.  _arXiv preprint arXiv:1908.08530_.
  * Toshniwal et al. (2021) Shubham Toshniwal, Patrick Xia, Sam Wiseman, Karen Livescu, and Kevin Gimpel. 2021\.  On generalization in coreference resolution.  _arXiv preprint arXiv:2109.09667_.
  * Van Engelen and Hoos (2020) Jesper E Van Engelen and Holger H Hoos. 2020.  A survey on semi-supervised learning.  _Machine learning_ , 109(2):373–440.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Wang et al. (2020) Qinxin Wang, Hao Tan, Sheng Shen, Michael W Mahoney, and Zhewei Yao. 2020.  Maf: Multimodal alignment framework for weakly-supervised phrase grounding.  _arXiv preprint arXiv:2010.05379_.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_.
  * Xia and Van Durme (2021) Patrick Xia and Benjamin Van Durme. 2021.  Moving on from OntoNotes: Coreference resolution model transfer.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 5241–5256, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Zhai et al. (2019) Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. 2019.  S4l: Self-supervised semi-supervised learning.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 1476–1485.
  * Zhang et al. (2021a) Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. 2021a.  Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling.  _Advances in Neural Information Processing Systems_ , 34:18408–18419.
  * Zhang et al. (2017) Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. 2017.  mixup: Beyond empirical risk minimization.  _arXiv preprint arXiv:1710.09412_.
  * Zhang et al. (2021b) Pengchuan Zhang, Xiujun Li, Xiaowei Hu, Jianwei Yang, Lei Zhang, Lijuan Wang, Yejin Choi, and Jianfeng Gao. 2021b.  Vinvl: Revisiting visual representations in vision-language models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5579–5588.

## Appendix

##  Appendix A Baselines

Method | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
| R | P | F1 | R | P | F1 | R | P | F1 | F1
Weights from ALBEF Li et al. (2021) | 31.70 | 25.97 | 26.47 | 70.78 | 78.35 | 73.77 | 54.58 | 89.02 | 66.94 | 55.73
Ours (Weights from BERT Devlin et al. (2018)) | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 6: CR performance with ALBEF Li et al. (2021) as pre-trained weights.

Grounding | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
threshold | R | P | F1 | R | P | F1 | R | P | F1 | F1
0.0 | 28.20 | 22.47 | 23.08 | 70.10 | 76.29 | 72.40 | 52.32 | 87.22 | 64.71 | 53.40
0.5 | 31.18 | 30.04 | 28.92 | 70.80 | 82.67 | 75.76 | 59.68 | 92.18 | 71.77 | 58.82
0.7 | 30.48 | 33.34 | 30.58 | 70.63 | 86.74 | 77.58 | 63.30 | 93.22 | 74.85 | 61.01
0.9 | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 7: Performance of our proposed method by varying the grounding threshold
$t$ to include samples above this threshold in Equation 9.

We consider the following baselines to fairly compare and evaluate our
proposed method:

(a) Text-only CR: For all these methods, we directly evaluate the coreference
chains using the narration only without the image. (1) Neural-Coref Lee et al.
(2017): This method is trained end-to-end using a neural network on a large
corpus of wikipedia data to detect mentions and coreferences. For this
baseline, we use the predicted mentions instead of the gold mentions. (2)
longdoc Toshniwal et al. (2021): This is a strong transformer based method
using Longformer-Large as the backbone for coreference resolution, trained on
multiple datasets. We use the gold mentions to predict coreference chains for
this model.

(b) Multi-modal CR:  We evaluate strong vision and langauge models for the
task on coreference resolution on the CIN dataset. (1) VisualBERT Su et al.
(2019), UNITER Chen et al. (2020), VinVL Zhang et al. (2021b): All these three
baselines are strong vision language models trained on image-caption data and
shows improvements on a variety of downstream tasks such as VQA, NLVR etc. To
test it for CR, we compute the cosine similarity for the multi-modal mention
embeddings in a zero-shot way. (2) MAF Wang et al. (2020): MAF is a weakly
supervised phrase grounding method, originally trained on the
Flickr30k-Entities Plummer et al. (2015). Goel et al. (2022) train this model
on narrations data and evaluate it for CR. (3) WS-MCR Goel et al. (2022): This
is a strong weakly supervised method for multimodal coreference resolution on
the CIN dataset Goel et al. (2022). In this method, they train a vision and
text encoder with an image-text contrastive loss and weak prior linguistic
rules as a regularizer.

##  Appendix B Bounding box regression loss (BBR)

We define the smmoth-L1 loss Ren et al. (2015) for the bounding box
transformation as follows:

$\mathcal{L}_{bbr}=\begin{cases}0.5(b_{m}-b^{\prime}_{m})^{2}/\beta,&\text{if
$|b_{m}-b^{\prime}_{m}|<\beta$}\\\
|b_{m}-b^{\prime}_{m}|-0.5*\beta,&\text{otherwise}\end{cases}$ (11)

where $\beta$ is set to 1 following previous work Girshick (2015); Ren et al.
(2015), $b^{\prime}_{m}$ are the transformed bounding box coordinates after
applying the delta transformation $\delta_{m}$ on the maximum region proposal
$r_{m}$ similar to Girshick (2015).

##  Appendix C Training details

The whole architecture is trained end-to-end with the AdamW Loshchilov and
Hutter (2017) optimizer. The initial learning rate of the model is 1e-5. The
learning rate is gradually warmed up for 2 epochs with a unit multiplier and
then decayed following a step scheduler with step size of 10 epochs and gamma
of 0.95. We use a batch size of eight and weight decay of 0.01. The model is
trained for 30 epochs and we choose the best performing model based on the
test set. The model is trained on 4 V100 GPUs with data parallelism. All code
and models will be made available at https://github.com/VICO-UoE/CIN-SSL.

##  Appendix D Further Ablations

Pre-trained weights from ALBEF Li et al. (2021). In Table 6, we show CR
results by replacing the text-encoder and the multi-modal encoder in our model
from the ALBEF Li et al. (2021) framework with 6 transformer blocks in each
encoders. Moreover, we use the pre-traiend weights from ALBEF Li et al. (2021)
and then fine-tune using our semi-supervised training strategies. Despite
strong pre-training from ALBEF, the model does not fine-tune and transfer well
to the task of MCR compared to our method which is initialized with BERT
weights.

Varying the threshold for pseudo-grounding loss. In Table 7, we compare the
results with different grounding thresholds for the pseudo grounding loss.
Including all the pseudo predictions (threshold of 0.0) leads to a significant
drop in performance showing the importance of thresholding-based training
strategy. Furthermore, as presented in the results the threshold of 0.9 works
the best compared to 0.5 and 0.7.

Varying the amount of labeled and unlabeled data. In Table 8 and Table 9, we
present detailed results from the discussion in Section 5.3 on different CR
metrics by varying the amount of labeled and unlabeled data.

% $\mathcal{D}_{s}$ | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
R | P | F1 | R | P | F1 | R | P | F1 | F1
20% | 26.40 | 31.18 | 27.26 | 69.83 | 88.26 | 77.75 | 64.25 | 92.02 | 75.11 | 60.04
50% | 28.65 | 34.13 | 29.91 | 70.26 | 88.83 | 78.27 | 64.55 | 92.56 | 75.53 | 61.24
100% | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 8: CR performance by varying the number of labels in the labeled
dataset.

% $\mathcal{D}_{u}$ | MUC | B3 | CEAFϕ4 | CoNLL
---|---|---|---|---
R | P | F1 | R | P | F1 | R | P | F1 | F1
20% | 30.96 | 27.09 | 27.20 | 70.84 | 79.36 | 74.23 | 56.49 | 90.79 | 69.04 | 56.82
50% | 30.87 | 29.97 | 28.83 | 70.75 | 83.58 | 76.23 | 60.24 | 92.02 | 72.27 | 59.11
100% | 31.11 | 35.25 | 31.86 | 70.63 | 87.85 | 78.06 | 63.99 | 93.44 | 75.47 | 61.79

Table 9: CR performance by varying the number of labels in the unlabeled
dataset.

##  Appendix E Qualitative Results

In Figure 4 and Figure 5, we present detailed qualitative visualizations.
Figure 4 shows the coreference chains predicted by our proposed method and the
baseline, WS-MCR Goel et al. (2022). The baseline model misses the instances
of his to relate it to the the man (row 2, column 2) which is correctly
clustered by our method. Moreover, WS-MCR Goel et al. (2022) cannot relate big
orange color building to the building (row2, column 4) unlike our method. This
highlights that our method is able to learn fine-grained correlations between
the image regions and text to effectively resolve such ambiguities. Despite
significant advantages, our method still fails to resolve cases like some
other people by clustering them into the same chain. We believe that the model
needs more complex visual understanding (localize different instance of some
other people) and contextual knowledge from text (people standing on road vs
people standing on footpath) for these specific cases.

In Figure 5, we show grounding of the corresponding mentions on the image from
our proposed method and the baseline WS-MCR Goel et al. (2022). Compared to
the baseline, our method successfully grounds entrance door, some other people
and two women. Hence our method clearly exhibits strong coreference resolution
and grounding capabilities compared to previous work.

Figure 4: Coreference resolution for an image-narration pair. We break down
the full narration as individual sentences in the columns for simplicity. The
rows from top to bottom show ground-truth annotations, predictions from the
WS-MCR method Goel et al. (2022) and Ours. The mentions in the same color form
a part of the coreference chain.

Figure 5: Visualization of Grounding and CR performance. Zoom in for better
visualization of bounding boxes.


# MAGNet: Multi-agent Graph Network for Deep Multi-agent Reinforcement
Learning

Aleksandra Malysheva  JetBrains Research
National Research University
Higher School of Economics
St Petersburg, Russia
<EMAIL_ADDRESS>Daniel Kudenko  JetBrains Research
L3S Research Center
Leibniz University Hannover
Hannover, Germany
<EMAIL_ADDRESS>Aleksei Shpilman  JetBrains Research
National Research University
Higher School of Economics
St Petersburg, Russia
<EMAIL_ADDRESS>
###### Abstract

Over recent years, deep reinforcement learning has shown strong successes in
complex single-agent tasks, and more recently this approach has also been
applied to multi-agent domains. In this paper, we propose a novel approach,
called MAGNet, to multi-agent reinforcement learning that utilizes a relevance
graph representation of the environment obtained by a self-attention
mechanism, and a message-generation technique. We applied our MAGnet approach
to the synthetic predator-prey multi-agent environment and the Pommerman game
and the results show that it significantly outperforms state-of-the-art MARL
solutions, including Multi-agent Deep Q-Networks (MADQN), Multi-agent Deep
Deterministic Policy Gradient (MADDPG), and QMIX.

###### Index Terms:

multi-agent system, relevance graphs, deep-learning

##  I Introduction

A common difficulty of reinforcement learning in a multi-agent environment
(MARL) is that in order to achieve successful coordination, agents require
information about the relevance of environment objects to themselves and other
agents. For example, in the game of Pommerman [1] it is important to know how
relevant bombs placed in the environment are for teammates, e.g. whether or
not the bombs can threaten them. While such information can be hand-crafted
into the state representation for well-understood environments, in lesser-
known environments it is preferable to derive it as part of the learning
process.

In this paper, we propose a novel method, named MAGNet (Multi-Agent Graph
Network), to learn such relevance information in form of a relevance graph and
incorporate this into the reinforcement learning process. The method works in
two stages. In the first stage, a relevance graph is learned. In the second
stage, this graph together with state information is fed to an actor-critic
reinforcement learning network that is responsible for the decision making of
the agent and incorporates message passing techniques along the relevance
graph.

The contribution of this work is a novel technique to learn object and agent
relevance information in a multi-agent environment, and incorporate this
information in deep multi-agent reinforcement learning.

We applied MAGNet to the synthetic predator-prey game, commonly used to
evaluate multi-agent systems [2], and the popular Pommerman [1] multi-agent
environment. We achieved significantly better performance than state-of-the-
art MARL techniques including MADQN [3], MADDPG [4] and QMIX [5].
Additionally, we empirically demonstrate the effectiveness of utilized self-
attention [6], graph sharing and message passing system.

##  II Deep Multi-Agent Reinforcement Learning

In this section we describe the state-of-the-art deep reinforcement learning
techniques that were applied to multi-agent domains. The algorithms introduced
below (MADQN, MADDPG, and QMIX) were also used as evaluation baselines in our
experiments.

###  II-A Multi-agent Deep Q-Networks

Deep Q-learning utilizes a neural network to predict Q-values of state-action
pairs [7]. This so-called deep Q-network is trained to minimize the following
loss function:

$L(\theta)=\mathbb{E}_{s,a\sim\rho(s)}[y-Q(s,a|\theta)]^{2}$ (1)

$y=r+\gamma\max_{a^{\prime}}Q^{past}(s^{\prime},a^{\prime})$ (2)

where $s^{\prime}$ is the state we transition into by taking action $a$ in
state $s$ and $r$ is the reward of that action, $\theta$ is the parameter
vector of the current Q-function approximation. $a\sim\rho(s)$ denotes all
actions that are permitted in state $s$.

The Multi-agent Deep Q-Networks (MADQN, [3]) approach modifies this process
for multi-agent systems by performing training in two repeated steps. First,
they train agents one at a time, while keeping the policies of other agents
fixed. When the agent is finished training, it distributes its policy to all
of its allies as an additional environmental variable.

###  II-B Multi-agent Deep Deterministic Policy Gradient

When dealing with continuous action spaces, the MADQN method described above
can not be applied. To overcome this limitation, the actor-critic approach to
reinforcement learning was proposed [8]. In this approach an actor algorithm
tries to output the best action vector and a critic tries to predict the value
function for this action.

Specifically, in the Deep Deterministic Policy Gradient (DDPG [9]) algorithm
two neural networks are used: $\mu(s)$ is the actor network that returns the
action vector. $Q(s,a)$ is the critic network, that returns the $Q$ value,
i.e. the value estimate of the action of $a$ in state $s$.

The gradient for the critic network can be calculated in the same way as the
gradient for Deep Q-Networks described above (Equation 1). Knowing the critic
gradient $\nabla_{a}Q$ we can then compute the gradient for the actor as
follows:

$\nabla_{\theta^{\mu}}J=\mathbb{E}_{s}[\nabla_{a}Q(s,a|\theta^{q})|s=s_{t},a=\mu(s|\theta^{\mu})]$
(3)

where $\theta^{q}$ and $\theta^{\mu}$ are parameters of critic and actor
neural networks respectively, and $\rho^{\pi}(s)$ is the probability of
reaching state $s$ with policy $\pi$.

The authors of [10] proposed an extension of this method by creating multiple
actors, each with its own critic, where each critic takes in the respective
agent’s observations and actions of all agents. This then constitutes the
following value function for actor $i$:

$\nabla_{\theta_{i}}J=E_{s,a\sim\pi^{\theta}}[\nabla_{\theta_{i}}log\pi_{i}(a_{i}|o_{i})Q^{\pi}_{i}(o_{i},a_{1},\dots,a_{N})]$
(4)

This Multi-agent Deep Deterministic Policy Gradient method showed the best
results among widely used deep reinforcement learning techniques in continuous
state and action space.

###  II-C QMIX

Another recent promising approach to deep multi-agent reinforcement learning
is the QMIX [5] method. It utilizes individual Q-functions for every agent and
joint Q-function for a team of agents. The QMIX architecture consists of three
types of neural networks. Agent networks evaluate individual Q-functions for
agents taking in the current observation and the previous action. Mixing
network takes as input individual Q-functions from agent networks and a
current state and then calculates a joint Q-function for all agents. Hyper
networks add an additional layer of complexity to the mixing network. Instead
of passing the current state to the mixing network directly, hyper networks
use it as input and calculate weight multipliers at each level of the mixing
network. We refer the reader to the original paper for a more complete
explanation [5].

The authors empirically demonstrated on a number of RL domains that this
approach outperforms both MADQN and MADDPG methods.

##  III MAGnet approach and architecture

Figure 1: The overall network architecture of MAGNet. Left section shows the
graph generation stage. Right part shows the decision making stage. $X(t)$
denotes the state of the environment at step $t$. $a(t)$ denotes the action
taken by the agent at step $t$. GGN refers to Graph Generation Network.

Figure 1 shows the overall network architecture of our MAGNet approach. The
whole process can be divided into a relevance graph generation stage (shown in
the left part) and a decision making stages (shown in the right part). In this
architecture, the concatenation of the current state and the previous action
forms the input of the model, and the output is the next action. The details
of the two processes are described below.

###  III-A Relevance graph generation stage

In the first part of our MAGNet approach, a neural network is trained to
produce a relevance graph, which is represented as a numerical matrix
$|A|\times(|A|+|O|)$, where $|A|$ is the number of agents and $|O|$ is a given
maximum number of environment objects, e.g., bombs and walls in Pommerman.
Weights for objects that are not present at the current time are set to 0. The
relevance graph represents the relationship between agents and between agents
and environment objects. The higher the absolute weight of an edge between an
agent $a$ and another agent $b$ or object $o$ is, the more important $b$ or
$o$ are for the achievement of agent $a$’s task. Every vertex $v$ of the graph
has a type $b(v)$, defined by the user. Example types are ”wall”, ”bomb”, and
”agent”. Types are user-defined and are used in the message generation step
(see below). The graph is generated by MAGNet from the current and previous
state together with the respective actions.

##  IV Relevance graph visualization

To generate this relevance graph, we train a neural network via back-
propagation to output a graph representation matrix. The input to the network
are the current and the two previous states (denoted by $X(t)$, $X(t-1)$, and
$X(t-2)$ in Figure 1), the two previous actions (denoted by $a(t-1)$ and
$a(t-2)$), and the relevance graph produced at the previous time step (denoted
by $graph(t-1)$). For the first learning step (i.e. $t=0$), the input consists
out of three copies of the initial state, no actions, and a random relevance
graph. The inputs are passed into a convolution and pooling layer, followed by
a padding layer, and then concatenated and passed into fully connected layer
and finally into the graph generation network (GGN). In this work we implement
GGN as either a multilayer perceptron (MLP) or a self-attention network, which
uses an attention mechanism to catch long and short term time-dependencies. We
present the results of both implementations in Table I. The self-attention
network is an analogue to a recurrent network, such as an LSTM, but takes much
less time to compute [6]. The result of the GGN is fed into a two-layer fully
connected network with dropout, which produces the relevance graph matrix.

The loss function for the back-propagation training is defines as follows:

$L=||W^{t}-W^{t-1}||_{2}^{2}$ (5)

The loss function is based on the squared difference between weights of edges
in the current graph $W^{t}$ and the one generated in the previous state
$W^{t-1}$. We could train the graph without this loss function, and instead
with just the loss function of the decision making stage backpropagated to the
graph generation stage. However, we found that this lowers the performance
(see Figure 3). Both Pommerman and predator-prey environments have these
default agents. However, we found out that the better way to train MAGNet is
to first pre-train the graph generation and then add the agent networks (see
also Section V-E). There are two alternatives for training relevance graphs:
(1) train individual relevance graphs for every agent, or (2) train one shared
graph (GS) that is the same for all agents on the team. We performed
experiments to determine which way is better (see Table I).

###  IV-A Decision making stage

The agent AI responsible for decision making is represented as a neural
network whose inputs are accumulated messages and the current state of the
environment. The output of the network is an action to be executed. This
action is computed in 4 steps through a message passing system.

In the first step, individual (i.e. location-specific) observations of agents
and objects are pre-processed by a neural network into an information vector
(represented as a numerical vector). This neural network is initialized
randomly and trained during the overall learning process using the same global
loss function.

In the second step, a neural network (also trained) is taking the information
vector of an agent, and maps it into a message (also a numerical vector), one
for each connected vertex type in the relevance graph. This message is
multiplied by the weight of the corresponding edge and passed to the
respective vertices.

In the third step, each agent or object in the relevance graph updates its
information vector, also using a trained network, based on the incoming
messages and the previous information vector. Steps 2 and 3 are repeated a
given number of times, in our experiments five times. Finally, in the last
step, the final message received by the agent, together with the current state
information is mapped by a trained decision making network into an action.

Since the message passing system outputs an action, we view it as an actor in
the DDPG actor-critic approach [9], and train it accordingly. A more formal
description of this decision making stage is as follows.

  1. 1.

Initialization of information vector. Each vertex $v$ has an initialization
network $\textit{MLP}^{b(v)}_{init}$ associated with it according to its type
$b(v)$ that takes as input the current individual observation $O_{v}$ and
outputs initial information vector $\mu^{0}_{v}$ for each vertex.

$\mu^{0}_{v}=\textit{MLP}^{b(v)}_{init}(O_{v})$ (6)

  2. 2.

Message generation. Message generation performs in iterative steps. At message
generation step $\tau+1$ (not to be confused with environmental time $t$) the
message networks $\textit{MLP}^{c{(v,u)}}_{msg}$ compute output messages for
every edge $(v,u)\in E$ based on the type of the edge $c(v,u)$, which are then
multiplied by the weight of the corresponding edge in the relevant graph.

$\textit{msg}^{\tau}_{(v,u)}=w_{(v,u)}\textit{MLP}^{c{(v,u)}}_{msg}(\mu^{\tau}_{v})$
(7)

  3. 3.

Message processing. The information vector $\mu^{\tau+1}_{v}$ at the message
propagation step $\tau$ is updated by an associated update network
$\textit{LSTM}^{b(v)}_{up}$, according to its type $b(v)$. The network takes
as input a sum of all incoming message vectors and the information vector
$\mu^{\tau}_{v}$ at the previous step.

$\mu^{\tau+1}_{v}=\textit{LSTM}^{b(v)}_{up}(\mu^{\tau}_{v},\sum{msg^{\tau}_{(*,v)}})$
(8)

  4. 4.

Choice of action. All vertices that are associated with agents have a decision
network $\textit{MLP}^{b(v)}_{\textit{choice}}$ which takes as an input its
final information vector $\mu^{T}_{v}$ and computes the mean of the action of
the Gaussian policy.

$a_{v}=\textit{MLP}_{\textit{choice}}(\mu^{T}_{v})$ (9)

##  V Experiments

###  V-A Environments

In this paper, we use two popular multi-agent benchmark environments for
testing, the synthetic multi-agent predator-prey game [2], and the Pommerman
game [1].

In the predator-prey environment, the aim of the predators is to kill faster
moving prey in 500 iterations. The predator agents must learn to cooperate in
order to surround and kill the prey. Every prey has a health of 10. A predator
moving within a given range of the prey lowers the prey’s health by 1 point
per time step. Lowering the prey health to 0 kills the prey. If even one prey
survives after 500 iterations, the prey team wins. Random obstacles are placed
in the environment at the start of the game.

The Pommerman game is a popular environment which can be played by up to 4
players. The multi-agent variant has 2 teams of 2 players each. This game has
been used in recent competitions for multi-agent algorithms, and therefore is
especially suitable for a comparison to state-of-the-art techniques.

In Pommerman, the environment is a grid-world where each agent can move in one
of four directions, place a bomb, or do nothing. A grid square is either empty
(which means that an agent can enter it), wooden, or rigid. Wooden grid
squares can not be entered, but can be destroyed by a bomb (i.e. turned into
clear squares). Rigid squares are indestructible and impassable. When a wooden
square is destroyed, there is a probability of items appearing, e.g., an extra
bomb, a bomb range increase, or a kick ability. Once a bomb has been placed in
a grid square it explodes after 10 time steps. The explosion destroys any
wooden square within range 1 and kills any agent within range 4. If both
agents of one team die, the team loses the game and the opposing team wins.
The map of the environment is randomly generated for every episode.

The game has two different modes: free for all and team match. Our experiments
were carried out in the team match mode in order to evaluate the ability of
MAGnet to exploit the discovered relationships between agents (e.g. being on
the same team).

We represent states in both environments as a $D\times D\times M$ tensor $S$,
where $D\times D$ are the dimensions of the field and $M$ is the maximum
possible number of objects. $S[i,j,k]=1$ if object $k$ is present in the
$[i,j]$ space and is 0 otherwise. The predator-prey state is a $64\times
64\times 20$ tensor, and the Pommerman state is $11\times 11\times 30$.

Figure 2: The synthetic predator-prey (left) and the Pommerman game
environment (right).

Figure 2 shows both test environments.

###  V-B Evaluation Baselines

Figure 3: MAGNet variants compared to state-of-the-art MARL techniques in the
predator-prey (left) and Pommerman (right) environments. MAGNet-DSH refers to
MAGNet with domain specific heuristics (Section V-F). MAGNet-NoGL refers to
MAGNet trained without the graph generation loss function (Equation 5), but
only with the final loss function of the decision making stage. MAGNet-NO-PT
refers to MAGNet with no pre-training for the graph generating network
(Section V-E ). Every algorithm trained by playing against a default
environment agent for a number of games (episodes) and a respective win
percentage is shown. Default agents are provided by the environments. Shaded
areas show the 95% confidence interval from 20 runs.

In our experiments, we compare the proposed method with state-of-the-art
reinforcement learning algorithms in the two environments described above.
Figure 3 shows a comparison with the MADQN [3], MADDPG [4] and QMIX [5]
algorithms. Each of these algorithms were trained by playing a number of games
(i.e. episodes) against the default AI provided with the games, and the
respective win rates are shown. All graphs display a 95% confidence interval
over 20 runs to show statistical significance.

The parameters for the MADQN the baselines were set as follows through
parameter exploration. The network for the predator-prey environment consists
of seven convolutional layers with 64 5x5 filters in each layer followed by
five fully connected layers with 512 neurons each with residual connections
[11] and batch normalization [12] that takes an input an 128x128x6 environment
state tensor and one-hot encoded action vector (a padded 1x5 vector) and
outputs a Q-function for that state-action pair. Since the output of a DQN is
discrete, but the predator-prey environment requires a continuous action, the
agents employ only two speeds and 10 directions. The network for Pommerman
consists of five convolutional layers with 64 3x3 filters in each layer
followed by three fully connected layers with 128 neurons each with residual
connections and batch normalization that takes an input an 11x11x4 environment
state tensor and one-hot encoded action vector (a padded 1x6 vector) that are
provided by the Pommerman environment and outputs a Q-function for that state-
action pair.

For our implementation of MADDPG we used a multilayer perceptron (MLP) with 3
fully connected layers with 512-128-64 neurons for both the actor and critic
for the predator-prey game, and 5 fully connected layer with 128 neurons in
each layer for the critic and a 3 layer network with 128 neurons in each layer
for the actor in Pommerman.

Parameter exploration for QMIX led to the following settings for both
environments. All agent networks are DQNs with a recurrent layer of a Gated
Recurrent Unit (GRU [13]) with a 64-dimensional hidden state. The mixing
network consists of a single hidden layer of 32 neurons. Since the output of
MADDPG and QMIX is continuous, but Pommerman expects a discrete action, we
discretized it.

As in the original QMIX paper [5], we decrease learning rate linearly from 1.0
to 0.05 over the first 50k time steps and than keep it constant. As can be
seen from Figure 3, our MAGnet approach significantly outperforms current
state-of-the-art algorithms.

###  V-C MagNet network training

In both environments we first trained the graph generating network on 50,000
episodes with the same parameters and with the default AI as the decision
making agents. Both predator-prey and Pommerman environments provide these
default agents. After this initial training, the default AI was replaced with
the learning decision making AI described in section III. All learning graphs
show the training episodes starting after this replacement.

Table I shows results for different MAGNet variants in terms of achieved win
percentage against a default agent after 600,000 episodes in the predator-prey
game and a 1,000,000 episodes in the game of Pommerman. The MAGNet variants
are differing in the complexity of the approach, starting from the simplest
version which takes the learned relevance graph as a direct addition to the
input, to the version incorporating message generation, graph sharing, and
self-attention. The table clearly shows the benefit of each extension.

TABLE I: Influence of different modules on the performance of the MAGnet model. MAGnet modules |  Win % PP |  Win % PM
---|---|---
SA |  GS |  MG |  |
+ |  + |  + |  $74.2\pm 1.2$ |  $76.3\pm 0.7$
+ |  + |  - |  $61.3\pm 0.9$ |  $56.7\pm 1.8$
+ |  - |  + |  $63.2\pm 1.3$ |  $62.4\pm 1.7$
+ |  - |  - |  $43.3\pm 1.5$ |  $54.5\pm 2.6$
- |  + |  + |  $69.3\pm 1.5$ |  $67.1\pm 1.9$
- |  + |  - |  $39.3\pm 2.0$ |  $52.0\pm 1.7$
- |  - |  + |  $41.5\pm 1.4$ |  $45.2\pm 3.6$
- |  - |  - |  $25.1\pm 2.3$ |  $32.7\pm 5.9$

Each of the three extensions with their hyper-parameters are described below:

  * •

Self-attention (SA). We can train the Graph Generating Network (GGN) as a
simple multi-layer perceptron (number of layers and neurons was varied, and a
network with 3 fully connected layers 512-128-128 neurons achieved the best
result). Alternatively, we can train it as a self-attention encoder part of
the Transformer network (SA) layer [6] with default parameters.

  * •

Graph Sharing (GS): relevance graphs were trained individually for agents, or
in form of a shared graph for all agents on one team.

  * •

Message Generation (MG): the message generation module was implemented as
either an MLP or a message generation (MG) architecture, as described in
Section IV-A.

###  V-D MAGNet parameters

We define vertex types $b(v)$ and edge types $c(e)$ in relevance graph as
follows:

$b(v)\in\\{0,1,2,3\\}$ in case of predator-prey game that corresponds to:
”predator on team 1 (1, 2, 3)”, ”predator on team 2 (4, 5, 6)”, ”prey”,
”wall”. Every edge has a type as well: $c(e)\in\\{0,1,2\\}$, that corresponds
to “edge between predators within one team”, “edge between predators from
different teams” and “edge between the predator and the object in the
environment or prey”.

$b(v)\in\\{0,1,2,3,4,5,6\\}$ in case of Pommerman game that corresponds to:
”ally”, ”enemy”, ”placed bomb” (about to explode), ”increase kick ability”,
”increase blast power”, ”extra bomb” (can be picked up). Every edge has a type
as well: $c(e)\in\\{0,1\\}$, that corresponds to “edge between the agents” and
“edge between the agent and the object in the environment”.

We tested the MLP and message generation network with a range of hyper-
parameters, choosing the best one. In the predator-prey game, the MLP has 3
fully connected layers with 512-512-128 neurons, while the message generation
network has 5 layers with 512-512-128-128-32 neurons. For the Pommerman
environment, the MLP has 3 fully connected layers 1024-256-64 neurons, while
the message generation network has 2 layers with 128-32 neurons. In both
domains 5 message passing iterations showed the best result.

Dropout layers were individually optimized by grid search in the [0, 0.2, 0.4]
space. We tested two convolution sizes: [3x3] and [5x5]. [5x5] convolutions
showed the best result. A Rectified Linear Unit (ReLU) transformation was used
for all connections.

###  V-E No pre-training

With regards to pre-training of the graph generating network we need to answer
the following questions. First, we need to determine whether or not it is
feasible to train the network without an external agent for pre-training. In
other words, can we simultaneously train both the graph generating network and
the decision making networks from the start. Second, we need to demonstrate
whether pre-training of a graph network improves the result.

To answer this question, we performed experiments without the pre-training of
the graph network. Figure 3 shows the results of those experiments (MAGNet-NO-
PT). As can be seen, the network indeed can learn without pre-training, but
pre-training significantly improves the results. This may be due to decision
making error influencing the graph generator network in a negative way.

###  V-F Domain specific heuristics

We also performed experiments to see whether or not additional knowledge about
the environment can improve the results of our method. To incorporate this
knowledge, we change the loss function for graph generation in the following
manner.

$L=||W^{t}-W^{t-1}||_{2}^{2}+\sum_{\xi_{(v,u)}\in\Xi^{t}}(w^{t}_{(v,u)}-s(\xi_{(v,u)}))^{2}$
(10)

The first component is the same: it is based on the squared difference between
weights of edges in the current graph $W^{t}$ and the one generated in the
previous state $W^{t-1}$. The second iterates through events $\Xi^{t}$ at time
$t$ and calculates the square difference between the weight of edge $(v,u)$
that is involved in event $\xi_{(v,u)}$ and the event weight $s(\xi_{(v,u)})$.

For example, in the Pommerman environment we set $s(\xi)$ corresponding to our
team agent killing an agent from the opposite team to 100, and the $s(\xi)$
corresponding to an agent picking up a bomb to 25. In the predator-prey
environment, if a predator kills a prey, we set the event’s weight to 100. If
a predator only wounds the prey, the weight for that event is set to 50.

As can be seen in Figure 3 (line MAGNet-DSH), the model that uses this domain
knowledge about the environment trains faster and performs better. It is
however important to note that the MAGNet network without any heuristics still
outperforms current state-of-the-art methods. For future research we consider
creating a method for automatic assignment of the event weights.

##  VI Conclusion

In this paper we presented a novel method, MAGNet, for deep multi-agent
reinforcement learning incorporating information on the relevance of other
agents and environment objects to the RL agent. We also extended this basic
approach with various optimizations, namely self-attention, shared relevance
graphs, and message generation. The MAGNet variants were evaluated on the
popular predator-prey and Pommerman game environments, and compared to state-
of-the-art MARL techniques. Our results show that MAGNet significantly
outperforms all competitors.

## References

  * [1] Tambet Matiisen.  Pommerman baselines, 2018.
  * [2] Igor Mordatch and Pieter Abbeel.  Emergence of grounded compositional language in multi-agent populations.  In AAAI Conference on Artificial Intelligence, 2018.
  * [3] Maxim Egorov.  Multi-agent deep reinforcement learning, 2016.
  * [4] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in Neural Information Processing Systems, pages 6379–6390, 2017.
  * [5] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson.  Qmix: monotonic value function factorisation for deep multi-agent reinforcement learning.  arXiv preprint arXiv:1803.11485, 2018.
  * [6] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems, pages 5998–6008, 2017.
  * [7] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602, 2013.
  * [8] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In Advances in neural information processing systems, pages 1057–1063, 2000.
  * [9] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  arXiv preprint arXiv:1509.02971, 2015.
  * [10] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In Advances in Neural Information Processing Systems, pages 6379–6390, 2017.
  * [11] 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.
  * [12] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  arXiv preprint arXiv:1502.03167, 2015.
  * [13] Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio.  Gated feedback recurrent neural networks.  In International Conference on Machine Learning, pages 2067–2075, 2015.