#  $\mathbb{VD}$-$\mathbb{GR}$: Boosting ${\mathbb{V}}$isual
${\mathbb{D}}$ialog with Cascaded Spatial-Temporal
Multi-Modal ${\mathbb{GR}}$aphs

Adnen Abdessaied Lei Shi Andreas Bulling
University of Stuttgart
{adnen.abdessaied, lei.shi<EMAIL_ADDRESS>
###### Abstract

We propose $\mathbb{VD}$-$\mathbb{GR}$†† Our project web-page is accessible
here. – a novel visual dialog model that combines pre-trained language models
(LMs) with graph neural networks (GNNs). Prior works mainly focused on one
class of models at the expense of the other, thus missing out on the
opportunity of combining their respective benefits. At the core of
$\mathbb{VD}$-$\mathbb{GR}$ is a novel integration mechanism that alternates
between spatial-temporal multi-modal GNNs and BERT layers, and that covers
three distinct contributions: First, we use multi-modal GNNs to process the
features of each modality (image, question, and dialog history) and exploit
their local structures before performing BERT global attention. Second, we
propose hub-nodes that link to all other nodes within one modality graph,
allowing the model to propagate information from one GNN (modality) to the
other in a cascaded manner. Third, we augment the BERT hidden states with
fine-grained multi-modal GNN features before passing them to the next
$\mathbb{VD}$-$\mathbb{GR}$ layer. Evaluations on VisDial v1.0, VisDial v0.9,
VisDialConv, and VisPro show that $\mathbb{VD}$-$\mathbb{GR}$ achieves new
state-of-the-art results across all four datasets.

Figure 1: $\mathbb{VD}$-$\mathbb{GR}$ outperforms strong baselines and
achieves new state-of-the-art results on VisDial v1.0, VisDial v0.9,
VisDialConv, and VisPro. $\uparrow$ indicates higher is better and
$\downarrow$ indicates lower is better. ($\clubsuit=$ Fine-tuning on dense
annotations, $\diamondsuit=$ Ensemble model).

##  1 Introduction

Visual dialog is a multi-modal task to assess how well an artificial agent can
hold a conversation with a human on a visual content using natural language
[9]. Visual dialog differs from other tasks, such as visual [3] or video
question answering [55], in that it requires the agent to answer a series of
temporally dependent questions. That is, the agent not only has to reason
about the visual input but also has to leverage the context of previous rounds
to be able to answer the current question correctly. Although other datasets
have been proposed for this task [45, 27], VisDial [9] has established itself
as the de-facto standard because of its challenging, open-ended, and real-
world nature.

Early visual dialog models on this dataset were based on recurrent networks
[18] within deep neural architectures ranging from vanilla LSTMs [17] over
memory nets [54] to hierarchical structures [46]. More recently, graph neural
networks (GNNs) have been proposed and have been shown to produce more fine-
grained features based on the local structures of each modality [6, 15, 19,
30, 20]. Other works have focused on attention models and pre-trained language
models (LM) [9, 44, 38, 1], fine-tuned for the visual dialog task [37, 32, 52,
61]. However, both methodological approaches have so far remained separate
despite their complementary strengths and weaknesses: While GNNs are effective
at exploiting local structure, they struggle to capture the global inter-modal
context, especially in a rich multi-modal task like visual dialog. In
contrast, transformer-based models [50] (e.g. BERT [10]) excel at learning the
global context using self and global attention but often fail to exploit local
intra-modal structures within each modality and suffer from the lack of
inductive bias [56].

We posit that it is essential to exploit both local intra-modal structures and
the global inter-modal context: Each modality is composed of smaller entities
whose relationships have to be separately captured and understood by the model
(i.e. the objects in the image, the words that constitute the question, and
the rounds that form the history). At the same time, the inter-dependency of
the modalities and the global context are equally important for a model to be
able to answer the current question efficiently. Implementing this idea, we
propose $\mathbb{VD}$-$\mathbb{GR}$ – the first visual dialog model to combine
transformer-based LMs and GNNs. Each of our proposed layers alternates between
GNNs that use hub-nodes to propagate information from one modality graph to
another to alleviate the lack of inter-modal context, as well as BERT layers
to learn the global intra-model context. The contributions of our work are
threefold:

  * •

A novel integration method of GNNs into transformer-based models that
alternates between multi-modal graph aggregation and BERT layers. The GNNs
exploit the local structure of each modality to augment the BERT hidden states
with their fine-grained features before passing them to the next
$\mathbb{VD}$-$\mathbb{GR}$ layer in an attempt to mitigate their lack of
inductive bias.

  * •

A novel feature propagation technique for multi-modal GNNs that relies on hub-
nodes that link to all other nodes of the other modality in a cascaded manner,
thus alleviating the lack of inter-modal context within the multi-modal
graphs.

  * •

Our model achieves new state-of-the-art results on VisDial v1.0, VisDial v0.9,
VisDialConv, and VisPro datasets, thereby outperforming strong baselines on
all four datasets.

Figure 2:  $\mathbb{VD}$-$\mathbb{GR}$ takes an image, a question, and a
history consisting of the previous turns as input together with their
respective graph structures. Each $\mathbb{VD}$-$\mathbb{GR}$-layer is
composed of cascaded multi-modal graphs and a vanilla BERT layer.

##  2 Related Work

###  2.1 GNNs for Visual Dialog

GNN-EM [65] was one of the earliest models to deploy GNNs for visual dialog.
It relied on building graphically structured neural networks to approximate
the learning and inference processes of graphical models [34, 48, 33, 12]. FGA
[44] developed a general attention mechanism that borrowed from the core idea
of GNN message passing, and that was able to combine representations of any
number of utilities. CAG [15] proposed representing the image as a fully-
connected graph of objects whose adjacency matrices could be dynamically
updated using a question-based attention mechanism. GOG [6] proposed
representing each modality as a graph before processing them by a light-weight
fusion module [38] to rank the candidate answers. Similarly to CAG [15],
DualVD [21] proposed representing the image as a graph consisting of connected
objects. They argued that the visual view helped to capture the appearance-
level information, including objects and their relationships, while the
semantic view enabled the agent to understand high-level visual semantics from
the whole image to the local regions [21].

Our model differs from the aforementioned works in two major aspects: (1)
Instead of concatenating the GNN node features, we propose using hub-nodes
that link to all remaining nodes within a given modality. We argue that this
improves the feature fusion on a local scale given that GNNs can freely learn
how to integrate information extracted from previous modalities. (2) We marry
GNNs with pre-trained LMs (BERT) in a novel way to benefit from the advantages
of both worlds. Contrarily to [57, 59] where simple integration approaches for
plain uni-modal tasks were introduced, we propose a sophisticated integration
method for the complex and rich multi-modal visual dialog task: We first
exploit the local multi-modal structures through GNNs before propagating
inter-modal information in a cascaded manner via hub-nodes to finally enhance
the hidden states of each BERT layer. To the best of our knowledge, we are the
first to propose this for the visual dialog task.

###  2.2 Language Models for Visual Dialog

ViLBERT [35] and XLMERT [49] were among the first attempts to leverage pre-
trained LMs for vision-language tasks (e.g. VQA [3], VCR [64], and image
retrieval [60]). Concretely, they used a transformer encoder as a backbone and
deployed a two-stream architecture to separately encode text and visual input.
VisDial-BERT [37] built on top of ViLBERT and specifically adapted it to the
visual dialog task, achieving new state-of-the-art performance on VisDial, and
thus becoming the standard baseline for this dataset. More recently, UTC [5]
was introduced as an improvement of VisDial-BERT and used two inter-task
contrastive losses to improve training. Another class of models used a single
stream to encode the multi-modal input such as B2T2 [2], VisualBERT [31], VL-
BERT [47], and UNITER [8]. VD-BERT [52] adapted a single stream VQA model [66]
to the visual dialog task and managed to achieve good performance without
relying on external datasets.

Contrarily to the aforementioned works, our model relies on the power of
cascaded GNNs to exploit local structures within each modality and, thus
produce more fine-grained representations for subsequent BERT layers. To the
best of our knowledge, this combination of GNNs and pre-trained LMs has not
been explored before for visual dialog.

##  3 Method

As shown in Figure 2, $\mathbb{VD}$-$\mathbb{GR}$ consists of four main
components: a) a graph construction and pruning module, (b) a backbone
operating on alternating cascaded multi-modal graphs and BERT layers, (c)
multiple loss heads (next sentence prediction $\mathcal{L}_{nsp}$, masked
language modelling $\mathcal{L}_{mlm}$, masked region modelling
$\mathcal{L}_{mrm}$, and multi-modal graph edge masking
($\mathcal{L}^{\mathcal{I}}_{gem}$, $\mathcal{L}^{\mathcal{Q}}_{gem}$,
$\mathcal{L}^{\mathcal{H}}_{gem}$)) , and (d) a prediction module to rank a
set of candidate answers.

###  3.1 Problem Formulation

Given a question $\texttt{Q}_{\texttt{t}}$ grounded on an image I at $t$-th
turn, as well as its dialog history
$\texttt{H}_{\texttt{t}}=\\{\texttt{C},\texttt{(Q}_{\texttt{1}},\texttt{A}_{\texttt{1}}\texttt{)},...,\texttt{(Q}_{\texttt{t-1}},\texttt{A}_{\texttt{t-1}}\texttt{)}\\}$
(where C denotes the image caption), the model is tasked to predict its answer
$\texttt{A}_{\texttt{t}}$ by ranking a list of $N=100$ answer candidates
$\\{\hat{\texttt{A}}_{\texttt{t}}^{\texttt{1}},\hat{\texttt{A}}_{\texttt{t}}^{\texttt{2}},...,\hat{\texttt{A}}_{\texttt{t}}^{\texttt{100}}\\}$.

###  3.2 Graph Construction and Pruning

Image Modality.  The image graph constructor $\mathcal{G_{I}}(.)$ treats each
object in the image as a node and relies on spatial relationships to construct
the graph topology, i.e. the adjacency matrix, where each edge represents a
relationship between two objects in the image. The objects
$\mathbf{I}=\\{\mathbf{v}_{1},...,\mathbf{v}_{N_{i}}\\}$ are obtained using
Faster R-CNN [43] pre-trained on Visual Genome [28] where each object feature
$\mathbf{v}_{i}$ is a $2048$ dimensional vector and $N_{i}=36$. Similar to
[58], we distinguish between $11$ relations based on the
$(x_{1},y_{1},x_{2},y_{2})$ object coordinates. Specifically, the overlapping
region and spatial coordinates of two regions are used to judge whether an
edge exists between them or not.

Question Modality. The question graph constructor $\mathcal{G_{Q}}(.)$ treats
each word in the question as a node and relies on dependency relations to
construct the graph topology, i.e. the adjacency matrix, where each edge
represents a relationship between two words in the question. To extract these
relationships, we use the neural dependency parser of Stanza [42] that yields
$47$ relations.

History Modality. The history graph constructor $\mathcal{G_{Q}}(.)$ treats
each dialog round as a node and relies on coreference relations to construct
the graph topology, i.e. the adjacency matrix, where each edge represents a
relationship between two rounds in the history.

As can be seen in Figure 2, the topology of all multi-modal graphs is computed
once during a pre-processing stage and is always kept constant over time. We
refer to the supplementary material for additional details.

###  3.3 Proposed Layer

####  3.3.1 Transformer Features

Inline with previous works, we use VisDial-BERT [37] layers within our novel
GNN-enhanced approach. For a given image-question pair at round $t$, we first
concatenate the caption C, the previous dialog rounds
$\texttt{H}_{\texttt{t}}$, the current question $\texttt{Q}_{\texttt{t}}$, and
a candidate answer $\tilde{\texttt{A}}_{\texttt{t}}$ to form the textual input

$\mathbf{T}=\\{\texttt{[CLS]}\,\texttt{C}\,\texttt{[SEP]}\,\texttt{Q}_{\texttt{1}}\texttt{[SEP]}\texttt{A}_{\texttt{1}},..,\texttt{Q}_{\texttt{t}}\,\texttt{[SEP]}\,\tilde{\texttt{A}}_{\texttt{t}}\\},$
(1)

where [CLS] and [SEP] are the special classification and separation tokens,
respectively. As in [37, 52, 61, 5], we use a special learnable token [IMG],
and initialise it using mean pooling of the object sequence. The hidden
features of the [IMG] token are used in conjunction with those of [CLS] by
means of element-wise multiplication to produce the final input features of
the NSP head.

Finally, the two sequences are used as input for the language and vision
streams of the VisDial-BERT layer to obtain the hidden states
$\mathbf{T}_{h}^{(l)}$ and $\mathbf{I}_{h}^{(l)}$, where $l$ is the
$\mathbb{VD}$-$\mathbb{GR}$ layer index.

Method | VisPro | VisDialConv
---|---|---
NDCG$\uparrow$ | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$ | NDCG$\uparrow$ | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$
MCA-I [1] | $59.80$ | $57.88$ | $45.39$ | $72.24$ | $82.76$ | $5.84$ | $52.07$ | $55.55$ | $41.65$ | $72.47$ | $83.81$ | $5.92$
MCA-I-HConcQ [1] | $61.08$ | $61.79$ | $48.95$ | $77.50$ | $86.58$ | $4.72$ | $54.84$ | $62.06$ | $47.42$ | $80.10$ | $88.87$ | $4.37$
MCA-I-HGuidedQ [1] | $61.35$ | $60.13$ | $47.11$ | $75.26$ | $86.18$ | $5.23$ | $53.81$ | $62.29$ | $48.35$ | $80.10$ | $88.76$ | $4.42$
MCA-I-VGH [1] | $61.68$ | $59.33$ | $46.18$ | $75.53$ | $86.71$ | $5.07$ | $55.48$ | $58.48$ | $44.54$ | $74.95$ | $86.19$ | $5.18$
MCA-I-H [1] | $61.72$ | $59.62$ | $45.92$ | $77.11$ | $86.45$ | $4.85$ | $53.01$ | $61.24$ | $47.63$ | $79.07$ | $87.94$ | $4.77$
Student [22] | $-$ | $-$ | $-$ | $-$ | $-$ | $-$ | $59.30$ | $-$ | $-$ | $-$ | $-$ | $-$
$\mathbb{VD}$-$\mathbb{GR}$ | $\mathbf{67.09}$ | $\mathbf{66.82}$ | $\mathbf{54.47}$ | $\mathbf{81.71}$ | $\mathbf{91.44}$ | $\mathbf{3.54}$ | $\mathbf{60.35}$ | $\mathbf{69.89}$ | $\mathbf{57.21}$ | $\mathbf{85.97}$ | $\mathbf{92.68}$ | $\mathbf{3.15}$

Table 1: Performance comparison on VisPro. The best and second-best results
are in bold and underlined, respectively. $\uparrow$ indicates higher is
better and $\downarrow$ indicates lower is better.

####  3.3.2 Spatial-Temporal GNN Features

##### Node Features.

As illustrated in Figure 2, the multi-modal GNNs of the $l$-th
$\mathbb{VD}$-$\mathbb{GR}$ layer get their node features from the hidden
states of the previous VisDial-BERT layer (or from the embedding layers in the
first step). It is worth noting that the special tokens [IMG] and [CLS] are
not included in the graph features. The nodes of the image and question graphs
are gathered from the image and question token embeddings of the $(l-1)$-th
layer, i.e. $\\{\mathbf{I}_{h,i}^{(l-1)}\\}_{i=1}^{N_{i}}$ and
$\\{\mathbf{T}_{h,i}^{(l-1)}\\}_{i=s_{q}}^{s_{q}+N_{q}}$, where $s_{q}$ and
$N_{q}$ denote the index of the first question token and the length of the
question, respectively. We use the special [SEP] tokens to represent each
dialog round in the history and gather their hidden states from
$\mathbf{T}_{h}^{(l-1)}$ to get the node features of the history graph. The
node features of the question and history graphs have to be extracted
carefully since the textual input, i.e. where the question starts and ends and
where the [SEP] tokens are located, varies within $\mathbf{T}_{h}^{(l-1)}$ for
each dialog and round.

##### Hub-node Features.

To make each modality aware of the other in a cascaded manner, we introduce
hub-nodes as illustrated in Figure 2. As a result, the history becomes aware
of the image, the question becomes aware of the history, and finally the image
becomes aware of the question. The hub-node within each graph links to all
other nodes using a special edge feature to propagate information on a local
scale from one modality to the other before applying self- and cross-
attention. To obtain the hub-node features, we train attention-based graph
embeddings for each modality, i.e. $f_{\theta_{\mathcal{I}}}(.)$,
$f_{\theta_{\mathcal{Q}}}(.)$, and $f_{\theta_{\mathcal{H}}}(.)$, which take
the node features of the corresponding graph and output a single vector
representing it. For example, the image hub-node $\mathcal{I}$, is computed
from the image graph node features $\mathbf{I}_{{G}}$ of the $l$-th layer as
follows:

$\displaystyle\mathcal{I}$
$\displaystyle=f_{\theta_{\mathcal{I}}}(\mathbf{I}_{{G}})=\sum_{i}\alpha_{i}\mathbf{v}_{i}\,\,\mathrm{for}\,\,\mathbf{v}_{i}\in\mathbf{I}_{{G}},$
(2) $\displaystyle\alpha$
$\displaystyle=\\{\alpha\\}_{i}=\mathrm{MLP}(\mathbf{I}_{{G}}),$ (3)

where MLP is a multi-layer perceptron that maps from the node features’ vector
space to $\mathbb{R}$ and $\theta_{\mathcal{I}}$ is the set of learnable
parameters of the embedding. The question hub-node $\mathcal{Q}$ and history
hub-node $\mathcal{H}$ are obtained in the same manner.

####  3.3.3 Graph Aggregation

Our multi-modal graphs are a variant of graph attention networks [51],
although other types of GNNs can be used within each
$\mathbb{VD}$-$\mathbb{GR}$ layer. Each multi-modal graph uses $K$ layers
(purple boxes in Figure 2) to propagate information between the nodes. For
example, the $k$-th image graph layer receives the node features from the
previous graph layer and updates them as follows:

$\displaystyle\mathbf{I}^{(k)}_{G}=\\{\mathbf{v}_{1}^{(k)},..,\mathbf{v}_{N_{i}}^{(k)},\underbrace{\mathbf{v}_{N_{i}+1}^{(k)}}_{=\mathcal{Q}}\\}=\mathrm{GNN}_{\mathcal{I}}(\mathbf{I}^{(k-1)}_{G}),$
(4)
$\displaystyle\mathbf{v}_{i}^{(k)}=\mathrm{GeLU}\left(\displaystyle\mathrel{\mathop{\parallel}_{h=1}^{H}}\tilde{\mathbf{v}}_{i}^{(k,h)}+\mathbf{v}_{i}^{(k-1)}\right),$
(5)
$\displaystyle\tilde{\mathbf{v}}_{i}^{(k,h)}=f(\sum_{v_{s}\in\mathcal{N}_{v_{t}}}\alpha_{s\rightarrow
t}^{(k,h)}\mathbf{m}_{s\rightarrow t}^{(k,h)})\,\,\forall 1\leq h\leq H,$ (6)

where $\parallel$ and $H$ are the concatenation operation and the number of
GNN attention heads, respectively. $\mathcal{N}_{v_{t}}$ represents the
neighbourhood of node $v_{t}$, $\alpha_{s\rightarrow t}$ denotes the attention
weight that scales the message $\mathbf{m}_{s\rightarrow t}^{(k,h)}$ between a
source node $\mathbf{v}_{s}$ and a target node $\mathbf{v}_{t}$, and $f$ is a
linear layer. The messages $\mathbf{m}_{s\rightarrow t}^{(k,h)}$ between the
nodes are computed following:

$\mathbf{m}_{s\rightarrow
t}^{(k,h)}=g_{h}(\mathbf{v}_{s}^{(k-1)},\mathbf{e}_{s\rightarrow t}),$ (7)

where $g_{h}$ is a linear layer and $\mathbf{e}_{s\rightarrow t}$ is the edge
feature between the nodes $\mathbf{v}_{s}$ and $\mathbf{v}_{t}$. We omitted
the $l$ index of the $\mathbb{VD}$-$\mathbb{GR}$ layer in the previous
equations for brevity. The $k$-th question and history graph layers update
their node features $\mathbf{Q}_{G}^{(k)}$ and $\mathbf{H}_{G}^{(k)}$ in the
same manner.

####  3.3.4 Hidden States Enhancement

The outputs of the multi-modal graphs of the last $K$-th layer, i.e.
$\mathbf{I}_{G}^{(l,K)}$, $\mathbf{Q}_{G}^{(l,K)}$ and
$\mathbf{H}_{G}^{(l,K)}$, are used to enhance the hidden states of the
following BERT layer. First, the GNN features are scattered back to their
corresponding places within the VisDial-BERT hidden states. Then, we apply a
fusion operation inspired by the idea of residual connections [16] as
illustrated in Figure 2. Our experiments show that this step is crucial and
leads to significant improvements in performance. These operations can be
summarised as follows:

$\displaystyle\tilde{\mathbf{I}}_{h}^{l}=\mathbf{I}_{h}^{l}\oslash(\mathbf{I}_{G}^{(l,K)},\mathrm{Idx}_{v}),\,\,\hat{\mathbf{I}}_{h}^{l}=\lambda\mathbf{I}_{h}+(1-\lambda)\tilde{\mathbf{I}}_{h}^{l},$
(8)
$\displaystyle\tilde{\mathbf{T}}_{h}^{l}=\big{(}\mathbf{T}_{h}^{l}\oslash(\mathbf{Q}_{G}^{(l,K)},\mathrm{Idx}_{q})\big{)}\oslash\big{(}\mathbf{H}_{G}^{(l,K)},\mathrm{Idx}_{h}\big{)},$
(9)
$\displaystyle\hat{\mathbf{T}}_{h}^{l}=\lambda\mathbf{T}_{h}+(1-\lambda)\tilde{\mathbf{T}}_{h}^{l}\quad\mathrm{for}\,\,\lambda\in[0,1],$
(10)

where $\oslash$ denote the scatter operation and $\mathrm{Idx}_{*}$ the
indices of the graph nodes features with respect to the BERT hidden states.
The final enhanced features $\hat{\mathbf{I}}_{h}^{l}$ and
$\hat{\mathbf{T}}_{h}^{l}$ are passed to the next BERT layer.

###  3.4 Loss Heads

We complement the traditional losses used for the visual dialog task (masked
language modelling $\mathcal{L}_{\textrm{mlm}}$, masked region modelling
$\mathcal{L}_{\textrm{mrm}}$, and next sentence prediction
$\mathcal{L}_{\textrm{nsp}}$) with graph edge masking
$\mathcal{L}_{\textrm{gem}}$ to improve learning of the local structure of
each modality, and thus to enhance the feature representation of our multi-
modal graphs.

##### Masked Language and Region Modelling.

Similar to masked language modelling introduced in [10], we randomly masked
$10\%$ of the text tokens and image objects with the special token [MASK] and
the model had to recover them based on the surrounding tokens and cross-modal
clues:

$\displaystyle\mathcal{L}_{\textrm{mlm}}$
$\displaystyle=-\mathbb{E}_{(\mathbf{w},\mathbf{I})\sim
S_{tr}}\left[logP(w_{m}|\mathbf{w}_{\backslash
m},\mathbf{h}_{\texttt{[IMG]}})\right],$ (11)
$\displaystyle\mathcal{L}_{\textrm{mrm}}$
$\displaystyle=-\mathbb{E}_{(\mathbf{w},\mathbf{I})\sim
S_{tr}}\left[logP(\mathbf{v}_{m}|\mathbf{I}_{\backslash
m},\mathbf{h}_{\texttt{[CLS]}})\right],$ (12)

where $w_{m}$, $\mathbf{v}_{m}$, and $S_{tr}$ denote the masked words, the
masked regions, and the training set, respectively.

##### Next Sentence Prediction.

The aim of next sentence prediction (NSP) is to identify whether the appended
answer $\tilde{\texttt{A}}_{\texttt{t}}$ is correct or not, i.e.

$\mathcal{L}_{\textrm{nsp}}=-\mathbb{E}_{(\mathbf{w},\mathbf{I})\sim
S_{tr}}\left[logP(y|\aleph(\mathbf{w},\mathbf{I}))\right],$ (13)

where $y\in\\{0,1\\}$ is a ground-truth binary label, and $\aleph(.,.)$ is the
binary answer prediction head operating on the element-wise product of the
[IMG] and [CLS] token representations.

Figure 3:  Only edges connecting two unmasked node features are eligible for
masking with a $15\%$ probability.

##### Graph Edge Masking.

We introduce the multi-modal graph edge masking to alleviate the potential
problem of having well-trained BERT layers but not sufficiently trained GNNs.
Given that, by design, our GNNs receive their features from the previous BERT
layer, they inherit some masked node representations. In order to make the
edge prediction task stable, we only masked $15\%$ of the edges connecting two
unmasked node features as illustrated in Figure 3. The representations of
these nodes were then used to predict the masked edges. For the example of the
image graph, this results in the following loss:

$\mathcal{L}^{\mathcal{I}}_{\textrm{gem}}=-\mathbb{E}_{(\mathbf{w},\mathbf{I})\sim
S_{tr}}\left[logP(y_{m}^{(i,j)}|\mathbf{h}_{\mathbf{v}_{i}},\mathbf{h}_{\mathbf{v}_{j}})\right],$
(14)

where $y_{m}^{(i,j)}$ is the ground-truth edge type between the nodes
$\mathbf{v}_{i}$ and $\mathbf{v}_{j}$. The question and history edge graph
masking losses $\mathcal{L}^{\mathcal{Q}}_{\textrm{gem}}$ and
$\mathcal{L}^{\mathcal{H}}_{\textrm{gem}}$ are obtained in a similar manner.

##### Total Loss.

We adopt a two-stage approach to train our model. First, we train it on a
warm-up task of masked token and graph edge prediction, i.e. using the total
loss $\mathcal{L}_{\textrm{warm}}$:

$\displaystyle\mathcal{L}_{\textrm{warm}}=\alpha_{1}(\mathcal{L}_{\textrm{mlm}}+\mathcal{L}_{\textrm{mrm}})+\alpha_{2}\mathcal{L}_{\textrm{GEM}},$
(15)
$\displaystyle\mathcal{L}_{\textrm{GEM}}=\mathcal{L}_{\textrm{GEM}}^{\mathcal{I}}+\mathcal{L}_{\textrm{GEM}}^{\mathcal{Q}}+\mathcal{L}_{\textrm{GEM}}^{\mathcal{H}}.$
(16)

Then, we only train the model based on the visual dialog loss

$\mathcal{L}_{\textrm{VD}}=\mathcal{L}_{\textrm{mlm}}+\mathcal{L}_{\textrm{mrm}}+\mathcal{L}_{\textrm{nsp}}.$
(17)

##  4 Experiments

###  4.1 Datasets

We evaluated $\mathbb{VD}$-$\mathbb{GR}$ on the challenging VisDial v0.9 and
VisDial v1.0 datasets. VisDial v0.9 has circa $83$k training and $40$k
validation dialogs. The more recent v1.0 version consists of about $123$k,
$2$k, and $8$k images for training, validation, and testing, respectively.
Each image comes with a caption and $10$ question-answer pairs; each question
turn is associated with $100$ candidate answers. The validation data and part
of the training data of VisDial v1.0 provide dense annotations for the
candidate answers. Furthermore, we evaluated our model on two additional
datasets, i.e. VisPro [62] and VisDialConv [1].

###  4.2 Quantitative Results

Method | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$
---|---|---|---|---|---
MN [9] | $59.65$ | $45.55$ | $76.22$ | $85.37$ | $5.46$
CoAtt [63] | $63.98$ | $50.29$ | $80.71$ | $88.81$ | $4.47$
HCIAE [36] | $62.22$ | $48.48$ | $78.75$ | $87.59$ | $4.81$
CorefNMN [26] | $64.10$ | $50.92$ | $80.18$ | $88.81$ | $4.45$
RvA [39] | $66.34$ | $52.71$ | $82.97$ | $90.73$ | $3.93$
Student [22] | $60.03$ | $50.40$ | $70.74$ | $77.15$ | $12.13$
DVAN [14] | $66.67$ | $53.62$ | $82.85$ | $90.72$ | $3.93$
VD-BERT [52] | $70.04$ | $57.79$ | $85.34$ | $92.68$ | $4.04$
VisDial-BERT [37] | $71.99$ | $59.41$ | $87.92$ | $94.59$ | $2.87$
$\mathbb{VD}$-$\mathbb{GR}$ | $\mathbf{74.50}$ | $\mathbf{62.10}$ | $\mathbf{90.49}$ | $\mathbf{96.37}$ | $\mathbf{2.45}$

Table 2: Performance comparison on the val split of VisDial v0.9 dataset. NDCG
is not supported in this version of the dataset.

##### VisDialConv & VisPro.

First, we evaluated our model on VisPro 111Same subset as in [1]. and
VisDialConv which were introduced to verify the role of dialog history in
answering the current question $\texttt{Q}_{\texttt{t}}$. We compared
$\mathbb{VD}$-$\mathbb{GR}$ to the baselines introduced in [1] as well as the
most recent Student model [22]. As can be seen from Table 1,
$\mathbb{VD}$-$\mathbb{GR}$ significantly outperformed all MCA variants across
all metrics on both datasets. Specifically, it increased the performance of
the baselines by over $5$ absolute points on NDCG and MRR on VisPro. On
VisDialConv, $\mathbb{VD}$-$\mathbb{GR}$ increased the top performance by over
$4$ absolute points on the same metrics. Table 1 also shows that our model
managed to surpass the Student model by over $1$ NDCG absolute point although
it was trained on circa $13$M additional images.

Method | NDCG$\uparrow$ | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$
---|---|---|---|---|---|---
LTMI [38] | $62.72$ | $62.32$ | $48.94$ | $78.65$ | $87.88$ | $4.86$
VD-BERT [52] | $63.22$ | $67.44$ | $54.02$ | $83.96$ | $92.33$ | $3.53$
VisDial-BERT [37] | $60.96$ | $67.17$ | $53.42$ | $84.41$ | $92.62$ | $3.41$
MCA [1] | $60.27$ | $64.33$ | $51.12$ | $80.91$ | $89.65$ | $4.24$
UniMM-UL [53] | $62.86$ | $53.49$ | $42.70$ | $65.03$ | $74.58$ | $10.65$
UTC [5] | $63.22$ | $68.58$ | $55.48$ | $85.38$ | $93.20$ | $3.28$
Student [22] | $\mathbf{65.47}$ | $53.19$ | $43.08$ | $64.09$ | $71.51$ | $14.34$
VD-PCR [61] | $64.16$ | ${69.71}$ | ${56.79}$ | ${85.82}$ | ${93.64}$ | ${3.15}$
$\mathbb{VD}$-$\mathbb{GR}$ | ${64.32}$ | $\mathbf{69.91}$ | $\mathbf{57.01}$ | $\mathbf{86.14}$ | $\mathbf{93.74}$ | $\mathbf{3.13}$

Table 3:  Performance comparison on the val split of VisDial v1.0 dataset.

##### VisDial v0.9.

Second, we compared $\mathbb{VD}$-$\mathbb{GR}$ with the state of the art on
the val split of VisDial v0.9. As can be seen from Table 2, our model
significantly outperformed all previous models and achieved new state-of-the-
art results across all metrics. Specifically, it outperformed pre-training
methods such as VisDial-BERT and VD-BERT by a large margin. Even more
importantly, it managed to also surpass more recent models such as Student.
Specifically, $\mathbb{VD}$-$\mathbb{GR}$ improved the MRR and R@1 scores by
over $2.5$ absolute points compared to the second best model.

##### VisDial v1.0 val.

We then compared $\mathbb{VD}$-$\mathbb{GR}$ with the state of the art on the
val split of VisDial v1.0. As can be seen from Table 3, our model outperformed
all previous models across all five sparse metrics. Specifically, it
outperformed pre-training methods, such as VisDial-BERT and VD-BERT by a
significant margin. Even more importantly, it managed to also surpass more
recent models such as UniMM-UL, VD-PCR, UTC, and Student.
$\mathbb{VD}$-$\mathbb{GR}$ improved MRR, R@1, and R@5 by over $0.2$ absolute
points compared to the second best VD-PCR model. Furthermore, we compared
their performance on individual dialog rounds using the sparse metrics (MRR,
R@1, R@5, and R@10). As can be seen from Figure 4, $\mathbb{VD}$-$\mathbb{GR}$
managed to outperform VD-PCR on almost all rounds of the dataset.

##### VisDial v1.0 test-std.

Finally, we compared our model with state-of-the-art published baselines on
the test-std split of the VisDial v1.0 dataset.

$\bullet$ State-of-the-art Results on Sparse Metrics: As can be seen from the
first section of Table 4, $\mathbb{VD}$-$\mathbb{GR}$ lifted the state-of-the-
art R@5, R@10, and Mean scores from $85.38$, $93.53$, and $3.21$ achieved by
VD-PCR to $85.58$, $93.85$, and $3.20$, respectively. On the remaining
metrics, our models performed on par with the state of the art. Specifically,
it reached respective scores of $68.65$ and $55.33$ on MRR and R@1, only third
to UTC and VD-PCR.

$\bullet$ Fine-tuning on Dense Annotations: As in previous works, we fine-
tuned our model on the dense annotations released by [37] in order to improve
the NDCG score. As illustrated in the second section of Table 4, the NDCG
score sharply increased from $63.49$ to $75.95$, outperforming all previous
models in the single-model setting. However, by fine-tuning on dense
annotations, we decreased the performance on the sparse metrics (MRR, R@1,
R@5, R@10, and Mean). This well-known phenomenon of the dataset is due to the
misalignment of the dense and sparse annotations as previously observed by
[37, 52]. In contrast to other baselines, $\mathbb{VD}$-$\mathbb{GR}$ managed
to keep relatively high sparse scores (4/5 metrics are the new state of the
art) after fine-tuning.

Figure 4:  Performance comparison on different dialog rounds of the VisDial
v1.0 val split. We only considered sparse metrics since the dense annotations
used to compute the NDCG score are not defined on all 10 rounds of the
validation dialogs.

Figure 5:  Performance comparison with different number of GNN layers $K$ on
the val split of VisDial v1.0. Results are shown for the val split of VisDial
v1.0.

$\bullet$ Ensemble Setting: As it is common practice, we fine-tuned an
ensemble comprised of eight pre-trained $\mathbb{VD}$-$\mathbb{GR}$ models to
further improve the NDCG score. One set of four models was fine-tuned with
Cross Entropy (CE) and with a varying number for GNN layers $K$, i.e.
$K=\\{1,2,3,4\\}$. Each model of the second set was trained using the ListNet
[4] ranking optimisation method. As can be seen in the last section of Table
4, our ensemble model reached an NDCG score of $76.43$ outperforming the
closest competitor UniMM-UL with only 76.17 and, thus setting a new state of
the art in the ensemble setting.

Method | NDCG$\uparrow$ | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$
---|---|---|---|---|---|---
MN [9] | $47.50$ | $55.49$ | $46.98$ | $72.30$ | $83.30$ | $5.92$
CorefNMN [26] | $54.70$ | $61.50$ | $47.55$ | $78.10$ | $88.80$ | $4.40$
FGA [44] | $56.90$ | $66.20$ | $52.75$ | $82.92$ | $91.07$ | $3.80$
DAN [23] | $57.59$ | $63.20$ | $49.63$ | $79.75$ | $89.35$ | $4.30$
LTMI [38] | $59.03$ | $64.08$ | $50.20$ | $80.68$ | $90.35$ | $4.05$
CAG [15] | $56.64$ | $63.49$ | $49.85$ | $80.63$ | $90.15$ | $4.11$
GOG [6] | $61.04$ | $63.52$ | $50.01$ | $80.13$ | $89.28$ | $4.31$
VD-BERT [52] | $59.96$ | $65.44$ | $51.63$ | $82.23$ | $90.68$ | $3.90$
VisDial-BERT [37] | $63.87$ | $67.50$ | $53.85$ | $84.68$ | $93.25$ | $3.32$
UTC [5] | ${64.60}$ | ${68.70}$ | $\mathbf{55.73}$ | $84.93$ | $93.08$ | $3.32$
VD-PCR [61] | $63.55$ | $\mathbf{68.73}$ | ${55.45}$ | ${85.38}$ | ${93.53}$ | ${3.21}$
UniMM-UL [53] | $63.90$ | $68.14$ | $54.57$ | $85.15$ | $93.13$ | $3.27$
‡Student [22] | $\mathbf{64.91}$ | $68.44$ | $55.05$ | $85.18$ | $93.35$ | $3.23$
$\mathbb{VD}$-$\mathbb{GR}$ | $63.49$ | $68.65$ | $55.33$ | $\mathbf{85.58}$ | $\mathbf{93.85}$ | $\mathbf{3.20}$
♣MCA [1] | $72.47$ | $37.68$ | $20.67$ | $56.67$ | $72.12$ | $8.89$
♣VD-BERT [52] | $74.54$ | $50.74$ | $33.15$ | $61.58$ | $77.15$ | $7.18$
♣VisDial-BERT [37] | $74.47$ | $50.74$ | $37.95$ | $64.13$ | $80.00$ | $6.28$
♣UTC [5] | $74.32$ | $50.24$ | $37.12$ | $63.98$ | $79.88$ | $6.48$
♣VD-PCR [61] | $75.30$ | $56.17$ | ${45.32}$ | $68.05$ | $80.98$ | $6.15$
♣UniMM-UL [53] | ${75.92}$ | ${56.18}$ | $43.70$ | ${71.03}$ | $\mathbf{84.80}$ | ${5.42}$
♣$\mathbb{VD}$-$\mathbb{GR}$ | $\mathbf{75.95}$ | $\mathbf{58.30}$ | $\mathbf{46.55}$ | $\mathbf{71.45}$ | $84.52$ | $\mathbf{5.32}$
♢♣P1+P2 [41] | $74.91$ | $49.13$ | $36.68$ | $62.96$ | $78.55$ | $7.03$
♢♣VD-BERT [52] | $75.35$ | $51.17$ | $38.90$ | $62.82$ | $77.98$ | $6.69$
♢♣VD-PCR [61] | $76.14$ | $56.05$ | ${44.75}$ | ${68.40}$ | ${82.75}$ | ${5.72}$
♢♣UniMM-UL [53] | ${76.17}$ | $\mathbf{56.42}$ | $44.32$ | $\mathbf{70.23}$ | $\mathbf{84.52}$ | $\mathbf{5.47}$
♢♣$\mathbb{VD}$-$\mathbb{GR}$ | $\mathbf{76.43}$ | ${56.35}$ | $\mathbf{45.18}$ | $68.13$ | $82.18$ | $5.79$

Table 4: Performance comparison on the test-std split of VisDial v1.0 dataset.
$\clubsuit$ indicates fine-tuning on dense annotations and $\diamondsuit$
denotes ensemble model. ${\ddagger}$ denotes the use of extra large datasets
for training.

Methods | NDCG$\uparrow$ | MRR$\uparrow$ | R@1$\uparrow$ | R@5$\uparrow$ | R@10$\uparrow$ | Mean$\downarrow$
---|---|---|---|---|---|---
$\mathbb{VD}$-$\mathbb{GR}$ w/ $\lambda=0$ | $56.69$ | $67.71$ | $54.07$ | $85.03$ | $92.84$ | $3.33$
$\mathbb{VD}$-$\mathbb{GR}$ w/o $\mathcal{L}_{\mathrm{warm}}$ | $63.76$ | $69.83$ | $56.84$ | ${86.05}$ | ${93.70}$ | $3.15$
$\mathbb{VD}$-$\mathbb{GR}$ w/o sharing | ${64.15}$ | $69.79$ | $56.73$ | $86.02$ | $93.68$ | $3.15$
$\mathbb{VD}$-$\mathbb{GR}$ w/o HN | $64.11$ | ${69.86}$ | ${56.88}$ | ${85.97}$ | ${93.67}$ | ${3.14}$
$\mathbb{VD}$-$\mathbb{GR}$ (Full) | $\mathbf{64.32}$ | $\mathbf{69.91}$ | $\mathbf{57.01}$ | $\mathbf{86.14}$ | $\mathbf{93.74}$ | $\mathbf{3.13}$

Table 5: Performance comparison of ablated versions of our model on the val
split of VisDial v1.0.

Figure 6:  Qualitative samples from the VisDial v1.0 val split. The attention
weights correspond to the $K$-th GNN of the first and last
$\mathbb{VD}$-$\mathbb{GR}$ layers. We first average them across all $H$
attention heads before re-normalising them for each node using a softmax
function. For clarity, we only show a subset of the image graph nodes.

###  4.3 Ablation Study

##### Number of GNN layers $K$.

This is an important hyper-parameter of our model: If $K$ is too small, then
the expressive power of the GNNs will be hampered. Contrarily, if $K$ is too
large, the GNNs will suffer from over-smoothing [29]. To this end, we
increased $K$ incrementally from one to four and used the sparse metrics of
the task (MRR, R@1, R@5, R@10) for validation. As illustrated in Figure 5, the
performance of our model peaked at $K=2$ for all four metrics. Thus, we kept
this value fixed in all previous experiments unless explicitly stated
otherwise.

##### Model Ablations.

In addition to the full model, we evaluated the following ablated versions:
$\bullet$ $\mathbb{VD}$-$\mathbb{GR}$ w/ $\mathbf{\lambda=0}$: This variant
did not apply the proposed residual connection of Equation 10 while augmenting
the BERT hidden states.
$\bullet$ $\mathbb{VD}$-$\mathbb{GR}$ w/o
$\mathbf{\mathcal{L}_{\textrm{warm}}}$: This variant was not trained on the
warm-up task of edge prediction as discussed in Sec. 3.4.
$\bullet$$\mathbb{VD}$-$\mathbb{GR}$ w/o sharing: This variant did not share
the weights of the GNNs in each layer of our model.
$\bullet$ $\mathbb{VD}$-$\mathbb{GR}$ w/o HN: This variant did not use hub-
nodes to propagate the information between the multi-modal GNNs.

As can be seen from Table 5, the residual connections are essential for high
performance. Without them, $\mathbb{VD}$-$\mathbb{GR}$ achieved the lowest
performance across all metrics. The same applies to the warm-up training
stage: Although the performance of this ablated version improved over the
previous one, it still performed significantly worse than our best model. The
results also underline the importance of sharing the GNN weights within the
different $\mathbb{VD}$-$\mathbb{GR}$ layers: Although this version has more
weights, it still performed worse than our best model on all metrics. This
finding was to be expected given that the local structure of each modality
does not change from one $\mathbb{VD}$-$\mathbb{GR}$ layer to another.
Finally, the importance of the inter-modal feature propagation using hub-nodes
is highlighted by the two last rows of Table 5: The hub-nodes enabled our
model to achieve the best performance across all metrics of the val split of
the VisDial v1.0 dataset.

###  4.4 Qualitative Results

Finally, in Figure 6 we show selected qualitative samples (with more in the
supplementary material) from the val split of VisDial v1.0 alongside the
ground truth answers, as well as the top-$1$ predictions of our
$\mathbb{VD}$-$\mathbb{GR}$ model and VD-PCR for comparison since it achieved
the second best results on this split. We make two interesting observations:
(1) Our model deals better with questions that require exploiting local
structure within modalities. For example, it managed to correctly answer
$\texttt{Q}_{\texttt{2}}=\texttt{How many skiers can you see?}$ in the first
dialog sample (see Figure 6a) by predicting 11 whereas VD-PCR predicted I can
only see two. We hypothesise that this is due to the fact that our model
exploits the spatial structure of the visual input more effectively using the
image graph compared to VD-PCR, although the latter has access to the same
visual features. (2) $\mathbb{VD}$-$\mathbb{GR}$ has more accurate semantic
understanding of the question. This is highlighted in answering
$\texttt{Q}_{\texttt{2}}=\texttt{How old does she seem to be?}$ (referring to
the woman) in the second dialog sample (see Figure 6b). Whereas our model
correctly predicted Early 20’s, VD-PCR failed by answering Grey, which is not
a semantically-sound response. We posit that this advantage of our model is
related to the fine-grained features of the question graph.

##  5 Conclusion

In this work we proposed $\mathbb{VD}$-$\mathbb{GR}$ – a novel visual dialog
model that combines pre-trained language models and GNNs. Specifically,
$\mathbb{VD}$-$\mathbb{GR}$ alternates between multi-modal graphs and BERT
layers, and augments the hidden states of the latter with the fine-grained
features obtained by the former. $\mathbb{VD}$-$\mathbb{GR}$ propagates
information from one modality graph to another in a cascaded manner using hub-
nodes that link to all other nodes within each modality, thereby effectively
alleviating the lack of inter-modal context. Extensive analyses underlined its
effectiveness, while experiments on four challenging visual dialog datasets
(VisDial v1.0, VisDial v0.9, VisDialConv, and VisPro) demonstrated its
superior performance over existing methods.

## Acknowledgment

A. Bulling was funded by the European Research Council (ERC; grant agreement
801708) and L. Shi was funded by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy - EXC
2075–390740016.

## Appendix

##  Appendix A Limitations

Although our model managed to outperform previous models on four challenging
datasets, it is important to acknowledge some of its limitations: First,
$\mathbb{VD}$-$\mathbb{GR}$ leverages extra data in the form of adjacency
matrices of the multi-modal GNNs and relies on external models to acquire
them. Although inferring these models on the VisDial data is cheap, this
approach can lead to inaccurate predictions of adjacency matrices, especially
for the question and history modalities. Thus, by keeping the graph structures
constant, our model’s performance might be limited by this introduced noise.
This could be remedied in future work by jointly learning the graphs’
parameters as well as refining their structures over time [13, 7, 11]. Second,
similar to almost all previous methods on this task, we did not manage to
achieve new state-of-the-art performance across all metrics of this
challenging dataset (see different sections of Table 4). Finally, inline with
previous works [37, 52, 24, 5, 61, 53], fine-tuning our model (both in the
single model as well as the ensemble setting) on dense annotations improved
the most relevant metric of the dataset, i.e. the NDCG score, at the expense
of the other (sparse) ones. Although our model’s performance dropped with
respect to the sparse metrics, we managed to outperform previous works by
achieving an NDCG score of 76.43, which is the main objective of dense
annotation fine-tuning.

##  Appendix B Graph Construction and Pruning

##### Image Modality.

Given two object features $\mathbf{v}_{i}$ and $\mathbf{v}_{j}$, their
bounding boxes and centre coordinates $(x_{i},y_{i})$ and $(x_{j},y_{j})$, we
computed the value of their intersection over unions $\mathrm{IoU}_{ij}$ and
relative angle $\phi_{ij}$. As shown in Figure 10, there are two spacial
cases: The first occurs when the bounding box of $\mathbf{v}_{i}$ completely
includes the bounding box of $\mathbf{v}_{j}$ and this class is denoted as
inside with index $i=1$. The second occurs when the bounding box of
$\mathbf{v}_{i}$ is entirely covered by the bounding box of $\mathbf{v}_{j}$.
This class is denoted as cover with index $i=2$. The remaining classes are
solely determined by the value of $\mathrm{IoU}_{ij}$. If
$\mathrm{IoU}_{ij}\geq 0.5$, then the relationship between the objects is
denoted as overlap and has the index $i=3$. Finally, if
$\mathrm{IoU}_{ij}<0.5$, the class index is computed as

$i=\lceil\frac{\phi_{ij}}{0.25\pi}\rceil+3.$

By construction, all classes of index $i\neq 3$ are pairwise symmetric as can
be seen from Figure 7a where we plotted the distribution of the different
image graph relationship classes over the training split of VisDial v1.0.

##### Question Modality.

The question graph relationship classes were determined by the dependency
between the question words. To this end, we input each question to the Stanza
dependency parser that output the classes between the different word pairs
resulting in a total of $47$ classes. As shown in Figure 7b, the distribution
of these classes within the VisDial v1.0 training split is not uniform with
det and nsubj being the most frequent. We illustrate a qualitative sample in
Figure 8.

##### History Modality.

We relied in coreference resolution to construct the history graph.
Specifically, an edge exists between two rounds i and j (i $>$ j) if and only
if a word in round j was used to reference another word in round i. The only
exception is the caption C that links to all upcoming rounds in the history
even if there is no explicit coreference between them. We posit that the
caption is complementary to the visual input and helps the model better
understand the scene. We illustrate a qualitative sample in Figure 9.

Method | VisDialBERT [37] | VD-BERT [52] | VD-PCR [61] |  $\mathbb{VD}$-$\mathbb{GR}$
---|---|---|---|---
# Parameters | 250M | 250M | 255M | 260M
Tr. time / epoch | 0.6h | 0.6h | 1.00h | 1.05h

Table 6: Model complexity and runtime comparison with respect to VisDial v1.0
on our hardware setup.

##  Appendix C Model Complexity

The overhead for constructing the multi-modal graphs only incurs once during a
cheap offline pre-processing stage and therefore does not lead to crucial
increase in compute complexity, i.e. number of trainable parameters and epoch
training time, compared with previous seminal models, e.g. VisDial-BERT [37],
VD-BERT [52], and VD-PCR [61], as can be seen in Table 6.

Figure 7:  Right: The distribution of the image graph relationship classes
within the training split of VisDial v1.0. Left: The distribution of the
question graph relationship classes within the training split of VisDial v1.0.

Figure 8:  A qualitative sample of the dependency relationships between
question word pairs.

Figure 9:  A qualitative sample of the coreference relationships between
different dialog rounds. The hub-node was not visualised for clarity.

Figure 10:  The different spatial relationships (without the hub-node
relationship) used in constructing the image graph. The orange and green
rectangles correspond to the bonding boxes of two objects within the scene.

Hyper-parameter | Training Stage
---|---
Warm-up | Sparse fine-tuning | Dense fine-tuning
Number of GNN layers $K$ | $2$ | $2$ | $2$
Number of GNN heads $H$ | $4$ | $4$ | $4$
Residual connection coefficient $\lambda$ | $0.5$ | $0.5$ | $0.5$
Dimension of $\textrm{GNN}_{\mathcal{I}}$ node features | $1024$ | $1024$ | $1024$
Dimension of $\textrm{GNN}_{\mathcal{Q}}$ node features | $768$ | $768$ | $768$
Dimension of $\textrm{GNN}_{\mathcal{H}}$ node features | $768$ | $768$ | $768$
Dimension of $\textrm{GNN}_{\mathcal{I}}$ edge features | $12$ | $12$ | $12$
Dimension of $\textrm{GNN}_{\mathcal{Q}}$ edge features | $48$ | $48$ | $48$
Dimension of $\textrm{GNN}_{\mathcal{H}}$ edge features | $2$ | $2$ | $2$
Dimension of $\mathrm{Linear}_{\mathcal{I}\rightarrow\mathcal{H}}(.)$ | $(1024,768)$ | $(1024,768)$ | $(1024,768)$
Dimension of $\mathrm{Linear}_{\mathcal{Q}\rightarrow\mathcal{I}}(.)$ | $(768,1024)$ | $(768,1024)$ | $(768,1024)$
Maximum number of text tokens | $256$ | $256$ | $256$
Maximum number of image regions | $37$ | $37$ | $37$
Text token mask probability | $0.1$ | $0.1$ | $-$
Image region mask probability | $0.1$ | $0.1$ | $-$
Graph edge mask probability | $0.15$ | $-$ | $-$
Optimiser | Adam | Adam | Adam
Minimum learning rate of BERT parameters | $0$ | $0$ | $1\times 10^{-5}$
Minimum learning rate of GNN parameters | $0$ | $0$ | $1\times 10^{-5}$
Maximum learning rate of BERT parameters | $5\times 10^{-6}$ | $5\times 10^{-6}$ | $2\times 10^{-5}$
Maximum learning rate of GNN parameters | $5\times 10^{-4}$ | $5\times 10^{-4}$ | $1\times 10^{-4}$
Learning rate warm-up of BERT parameters | True | True | True
Learning rate warm-up of GNN parameters | True | True | True
Learning rate schedule of BERT parameters | Linear | Linear | Linear
Learning rate schedule of GNN parameters | Linear | Linear | Linear
Training Loss | $\mathcal{L}_{\mathrm{warm}}$ | $\mathcal{L}_{\mathrm{VD}}$ |  $\mathcal{L}_{\mathrm{CE}}$ / $\mathcal{L}_{\mathrm{ListNet}}$
Number of epochs | $5$ | $20$ | $3$
Effective batch size | $64$ | $64$ | $100$
GPU Model | Tesla V100-32GB | Tesla V100-32GB | Tesla V100-32GB
Number of GPUs | $8$ | $8$ | $8$
Distributed training | Apex | Apex | PyTorch DP

Table 7: Hyper-parameter settings of $\mathbb{VD}$-$\mathbb{GR}$ for the
different stages of training.
$\mathrm{Linear}_{\mathcal{I}\rightarrow\mathcal{H}}(.)$ and
$\mathrm{Linear}_{\mathcal{Q}\rightarrow\mathcal{I}}(.)$ denote the linear
layers that produce the history and image hub-node features, respectively.

##  Appendix D Training Details

We implemented our model using PyTorch [40] and trained it on a server with 8
NVIDIA Tesla V100 GPUs using an effective batch size of $64$ and Adam
optimiser [25] with a linear decay learning rate schedule with warm-up. We set
the initial learning rates of the BERT and GNN weights to $5\times 10^{-6}$
and $5\times 10^{-4}$, respectively. Furthermore, we set the loss coefficients
$\alpha_{1}=\alpha_{2}=1$ and the residual connection coefficient
$\lambda=0.5$. We refer to Table 7 for a complete overview of our experimental
setup.

##  Appendix E Additional Qualitative Results

We present additional qualitative examples from the val split of VisDial v1.0
in Figure 11 and Figure 12. As in the main text, we compared the top-$1$
predictions of $\mathbb{VD}$-$\mathbb{GR}$ with the ground-truth and the
predictions of VD-PCR since it achieved the second best performance on this
split.

Figure 11:  Qualitative samples from the val split of the VisDial v1.0
dataset. We compared the predictions of $\mathbb{VD}$-$\mathbb{GR}$ (orange)
with the ground truth answers (blue) and the predictions of VD-PCR (pink). The
answers of both models correspond to the top-$1$ predictions.

Figure 12:  Qualitative samples from the val split of the VisDial v1.0
dataset. We compared the predictions of $\mathbb{VD}$-$\mathbb{GR}$ (orange)
with the ground truth answers (blue) and the predictions of VD-PCR (pink). The
answers of both models correspond to the top-$1$ predictions.

## References

  * [1] Shubham Agarwal, Trung Bui, Joon-Young Lee, Ioannis Konstas, and Verena Rieser.  History for Visual Dialog: Do we really need it?  In ACL, 2020.
  * [2] Chris Alberti, Jeffrey Ling, Michael Collins, and David Reitter.  Fusion of Detected Objects in Text for Visual Question Answering.  In EMNLP, 2019.
  * [3] Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh.  VQA: Visual Question Answering.  In ICCV, 2015.
  * [4] Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li.  Learning to Rank: From Pairwise Approach to Listwise Approach.  In ICML, 2007.
  * [5] Cheng Chen, Yudong Zhu, Zhenshan Tan, Qingrong Cheng, Xin Jiang, Qun Liu, and Xiaodong Gu.  UTC: A Unified Transformer with Inter-Task Contrastive Learning for Visual Dialog.  In CVPR, 2022.
  * [6] Feilong Chen, Xiuyi Chen, Fandong Meng, Peng Li, and Jie Zhou.  GoG: Relation-aware graph-over-graph network for visual dialog.  In Findings of ACL, 2021.
  * [7] Yu Chen, Lingfei Wu, and Mohammed J. Zaki.  Iterative deep graph learning for graph neural networks: Better and robust node embeddings.  In NeurIPS, 2020.
  * [8] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.  Uniter: Universal image-text representation learning.  In ECCV, 2020.
  * [9] Abhishek Das, Satwik Kottur, Khushi Gupta, Avi Singh, Deshraj Yadav, José M.F. Moura, Devi Parikh, and Dhruv Batra.  Visual Dialog.  In CVPR, 2017.
  * [10] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In NAACL, 2019.
  * [11] Pantelis Elinas, Edwin V. Bonilla, and Louis C. Tiao.  Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.  In NeurIPS, 2020.
  * [12] Haoshu Fang, Yuanlu Xu, Wenguan Wang, Xiaobai Liu, and Song-Chun Zhu.  Learning Pose Grammar to Encode Human Body Configuration for 3D Pose Estimation.  In AAAI, 2017.
  * [13] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He.  Learning discrete structures for graph neural networks.  In ICML, 2019.
  * [14] Dan Guo, Hui Wang, and Meng Wang.  Dual visual attention network for visual dialog.  In IJCAI, 2019.
  * [15] Dan Guo, Hui Wang, Hanwang Zhang, Zheng Jun Zha, and Meng Wang.  Iterative Context-Aware Graph Inference for Visual Dialog.  In CVPR, 2020.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [17] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 1997.
  * [18] J J Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  Proceedings of the National Academy of Sciences, 1982.
  * [19] Tianling Jiang, Yi Ji, Chunping Liu, and Hailin Shao.  Visual-textual alignment for graph inference in visual dialog.  In COLING, 2020.
  * [20] Xiaoze Jiang, Siyi Du, Zengchang Qin, Yajing Sun, and Jing Yu.  KBGN: Knowledge-Bridge Graph Network for Adaptive Vision-Text Reasoning in Visual Dialogue.  In ACM MM, 2020.
  * [21] Xiaoze Jiang, Jing Yu, Zengchang Qin, Yingying Zhuang, Xingxing Zhang, Yue Hu, and Qi Wu.  DualVD: An Adaptive Dual Encoding Model for Deep Visual Understanding in Visual Dialogue.  In AAAI, 2020.
  * [22] Gi-Cheon Kang, Sungdong Kim, Jin-Hwa Kim, Donghyun Kwak, and Byoung-Tak Zhang.  The Dialog Must Go On: Improving Visual Dialog via Generative Self-Training.  In CVPR, 2023.
  * [23] Gi-Cheon Kang, Jaeseo Lim, and Byoung-Tak Zhang.  Dual attention networks for visual reference resolution in visual dialog.  In EMNLP, 2019.
  * [24] Gi-Cheon Kang, Junseok Park, Hwaran Lee, Byoung-Tak Zhang, and Jin-Hwa Kim.  Reasoning visual dialog with sparse graph learning and knowledge transfer.  In Findings of EMNLP, 2021.
  * [25] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In ICLR, 2015.
  * [26] Satwik Kottur, José MF Moura, Devi Parikh, Dhruv Batra, and Marcus Rohrbach.  Visual coreference resolution in visual dialog using neural module networks.  In ECCV, 2018.
  * [27] Satwik Kottur, José M.F. Moura, Devi Parikh, Dhruv Batra, and Marcus Rohrbach.  Clevr-dialog: A diagnostic dataset for multi-round reasoning in visual dialog.  In NAACL, 2019.
  * [28] Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David A Shamma, et al.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  IJCV, 2017.
  * [29] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem.  DeepGCNs: Can GCNs Go As Deep As CNNs?  In ICCV, 2019.
  * [30] Linjie Li, Zhe Gan, Yu Cheng, and Jingjing Liu.  Relation-aware Graph Attention Network for Visual Question Answering.  In ICCV, 2019.
  * [31] Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang.  VisualBERT: A Simple and Performant Baseline for Vision and Language.  In arXiv:1908.03557, 2019.
  * [32] Mingxiao Li and Marie-Francine Moens.  Modeling coreference relations in visual dialog.  In EACL, 2021.
  * [33] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated Graph Sequence Neural Networks.  In ICLR, 2015.
  * [34] Guosheng Lin, Chunhua Shen, Ian Reid, and Anton van den Hengel.  Deeply Learning the Messages in Message Passing Inference.  In NeurIPS, 2015.
  * [35] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks.  In NeurIPS, 2019.
  * [36] Jiasen Lu, Anitha Kannan, , Jianwei Yang, Devi Parikh, and Dhruv Batra.  Best of Both Worlds: Transferring Knowledge from Discriminative Learning to a Generative Visual Dialog Model.  In NeurIPS, 2017.
  * [37] Vishvak Murahari, Dhruv Batra, Devi Parikh, and Abhishek Das.  Large-scale pretraining for visual dialog: A simple state-of-the-art baseline.  In ECCV, 2020.
  * [38] Van Quang Nguyen, Masanori Suganuma, and Takayuki Okatani.  Efficient Attention Mechanism for Visual Dialog that Can Handle All the Interactions Between Multiple Inputs.  In ECCV, 2020.
  * [39] Yulei Niu, Hanwang Zhang, Manli Zhang, Jianhong Zhang, Zhiwu Lu, and Ji-Rong Wen.  Recursive Visual Attention in Visual Dialog.  In CVPR, 2019.
  * [40] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In NeurIPS, 2019.
  * [41] Jiaxin Qi, Yulei Niu, Jianqiang Huang, and Hanwang Zhang.  Two causal principles for improving visual dialog.  In CVPR, 2020.
  * [42] Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning.  Stanza: A Python natural language processing toolkit for many human languages.  In ACL, 2020.
  * [43] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks.  In NeurIPS, 2015.
  * [44] Idan Schwartz, Seunghak Yu, Tamir Hazan, and Alexander G. Schwing.  Factor Graph Attention.  In CVPR, 2019.
  * [45] Paul Hongsuck Seo, Andreas Lehrmann, Bohyung Han, and Leonid Sigal.  Visual Reference Resolution using Attention Memory for Visual Dialog.  In NeurIPS, 2017.
  * [46] Iulian Serban, Alessandro Sordoni, Ryan Lowe, Laurent Charlin, Joelle Pineau, Aaron Courville, and Yoshua Bengio.  A Hierarchical Latent Variable Encoder-Decoder Model for Generating Dialogues.  In AAAI, 2017.
  * [47] Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai.  VL-BERT: Pre-training of Generic Visual-Linguistic Representations.  In ICLR, 2020.
  * [48] Sainbayar Sukhbaatar, Rob Fergus, et al.  Learning multiagent communication with backpropagation.  In NeurIPS, 2016.
  * [49] Hao Tan and Mohit Bansal.  LXMERT: Learning Cross-Modality Encoder Representations from Transformers.  In EMNLP, 2019.
  * [50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is All you Need.  In NeurIPS, 2017.
  * [51] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  In ICLR, 2018.
  * [52] Yue Wang, Shafiq Joty, Michael R. Lyu, Irwin King, Caiming Xiong, and Steven C.H. Hoi.  VD-BERT: A unified vision and dialog transformer with BERT.  In EMNLP, 2020.
  * [53] Zihao Wang, Junli Wang, and Changjun Jiang.  Unified multimodal model with unlikelihood training for visual dialog.  In ACM MM, 2022.
  * [54] Jason Weston, Sumit Chopra, and Antoine Bordes.  Memory Networks.  In NeurIPS, 2014.
  * [55] Jun Xu, Tao Mei, Ting Yao, and Yong Rui.  MSR-VTT: A Large Video Description Dataset for Bridging Video and Language.  In CVPR, 2016.
  * [56] Yufei Xu, Qiming Zhang, Jing Zhang, and Dacheng Tao.  Vitae: Vision transformer advanced by exploring intrinsic inductive bias.  In NeurIPS, 2021.
  * [57] Junhan Yang, Zheng Liu, Shitao Xiao, Chaozhuo Li, Defu Lian, Sanjay Agrawal, Amit Singh, Guangzhong Sun, and Xing Xie.  GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph.  In NeurIPS, 2021.
  * [58] Ting Yao, Yingwei Pan, Yehao Li, and Tao Mei.  Exploring visual relationship for image captioning.  In ECCV, 2018.
  * [59] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  In NeurIPS, 2021.
  * [60] Peter Young, Alice Lai, Micah Hodosh, and Julia Hockenmaier.  From image descriptions to visual denotations: New similarity metrics for semantic inference over event descriptions.  TACL, 2014.
  * [61] Xintong Yu, Hongming Zhang, Ruixin Hong, Yangqiu Song, and Changshui Zhang.  VD-PCR: Improving visual dialog with pronoun coreference resolution.  Pattern Recognition, 2022.
  * [62] Xintong Yu, Hongming Zhang, Yangqiu Song, Yan Song, and Changshui Zhang.  What You See is What You Get: Visual Pronoun Coreference Resolution in Dialogues.  In EMNLP-IJCNLP, 2019.
  * [63] Zhou Yu, Jun Yu, Jianping Fan, and Dacheng Tao.  Multi-modal factorized bilinear pooling with co-attention learning for visual question answering.  In ICCV, 2017.
  * [64] Rowan Zellers, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  From Recognition to Cognition: Visual Commonsense Reasoning.  In CVPR, June 2019.
  * [65] Zilong Zheng, Wenguan Wang, Siyuan Qi, and Song-Chun Zhu.  Reasoning Visual Dialogs with Structural and Partial Observations.  In CVPR, 2019.
  * [66] Luowei Zhou, Hamid Palangi, Lei Zhang, Houdong Hu, Jason Corso, and Jianfeng Gao.  Unified Vision-Language Pre-Training for Image Captioning and VQA.  In AAAI, 2020.


# Entropy and forecasting complexity of hidden Markov models, matrix product
states, and observable operator models

Peter Grassberger  JSC, FZ Jülich, D-52425 Jülich, Germany

###### Abstract

In a series of three papers, Jurgens and Crutchfield recently proposed a
supposedly novel method to compute entropies of hidden Markov models (HMMs),
discussed in detail its relationship to iterated function systems, and applied
it to compute their “ambiguity rates”, a concept supposedly introduced by
Claude Shannon. We point out that the basic formalism is not new (it is the
well known “forward algorithm” for HMMs), and that all three papers have also
serious other faults.

Hidden Markov models (HMMs) Bengio ; Ephraim ; Zucchini  are a standard tool
in data analysis, with a vast number of applications covering among others
finance, medicine, chemistry, bioinformatics, speech analysis, meteorology,
and physics. It is repeatedly claimed in the literature that no good
algorithms exit for estimating their (Shannon) entropy Jacquet ; Ordentlich ,
but this is not true: both the “forward” and the Baum-Welch algorithms
Zucchini  do just this. It is true that in their treatments entropy is often
not mentioned, but likelihoods are, and entropy is just the average negative
log-likelihood.

In Jurgens1 , a supposedly new algorithm based on “mixed states” was proposed.
But this algorithm is exactly the forward algorithm, and the “mixed states”
become precisely the causal states introduced in Grass86 , when their set is
minimized. This minimization is, in general, anyhow necessary for an efficient
application. Indeed, the forward algorithm was independently (re-)discovered
for a special class of HMMs in Zambella , where it was used to present precise
entropy estimates for a number of non-trivial models, and where it was also
used to compute forecasting complexities (FCs Grass86 ; later called
‘stochastic complexities’ in Young ). The fact that the algorithm proposed in
Zambella  is much more general was stressed in arXiv , where also a number of
other points were clarified.

More precisely, we consider a finite stationary ergodic irreducible first
order Markov process $M$. Here, “finite” means that it has a finite number $N$
of states, in the following called $s_{t}$ with values numbered simply by
$``i",\;i=1\ldots N$. The restriction to first order is trivial, as any higher
order Markov chain can be re-written as a first order process by re-labelling
the states. Irreducibility is essential since it implies (by the Frobenius-
Perron-theorem) that there is a unique stationary state. The probability to be
in state $i$ at (discrete) time $t$ is denoted as $P_{i,t}$. The stationary
state is characterized by the probabilities $P_{i,\infty}$. The transition
matrix is $T_{ji}={\rm prob}\\{s_{t+1}=j|s_{t}=i\\}$. The time evolution of
the probabilities is

$P_{j,t+1}=\sum_{i}T_{ji}P_{i,t}.$ (1)

In a more compact vector notation, we denote the state at time $t$ by a vector
${\bf P}_{t}\in\mathbb{R}^{N}$, so that the time evolution can be written as
${\bf P}_{t+1}={\bf T}{\bf P}_{t}$.

This Markov process is “hidden”, i.e. its states cannot be observed. What is
observed instead is the chain of discrete symbols $x_{t}$ which are emitted
one-by-one during each transition. These emitted symbols are chosen from an
alphabet $A$ (with cardinality $|A|$), and

$T^{(x)}_{ji}\equiv({\bf T}^{(x)})_{ji}={\rm
prob}\\{s_{t+1}=j,x_{t}=x|s_{t}=i\\}.$ (2)

For consistency, we have

${\bf T}=\sum_{x\in A}{\bf T}^{(x)}.$ (3)

Notice that we consider thus “edge-emitting” HMMs. The more widely discussed
“node-emitting” HMMs Zucchini  are obtained simply by assuming that the
emitted symbol does depend only on state $i$ and not on $j$, so that
$T^{(x)}_{ji}=T_{ji}q(x|i)$.

We now assume that the process has been going on for a long time, but no
emitted symbols have been observed for any time $t\leq 0$, so that ${\bf
P}_{0}={\bf P}_{\infty}$. Thus the observer/forecaster has at time $t=1$ no
clue about the internal state of $M$, and cannot make any non-trivial forecast
beyond that based on stationarity. This changes, however, when observations
are made at times $t=1,2,\ldots$. From these, the observer can make inferences
about the internal states, which will then lead to improved forecasts.
Comparing these forecasts with the actually emitted symbols will lead to
improved inferences, and so on. In general, this ‘observation process’ is not
stationary (even if the HMM is). It will in the limit $t\to\infty$ lead to a
situation where the non-predicted amount of information per symbol is a.s. the
entropy.

The optimally inferred states of the hidden dynamics based on the observation
process were called ‘mixed states’ in Jurgens1 ; Jurgens2 ; Jurgens3 , and
will be denoted here as $\hat{\bf P}_{t}(x_{1}x_{2}\ldots x_{t})$. Based on
them, the optimal forecast of the observed process is
$\hat{p}_{t+1}(x|x_{1}x_{2}\ldots x_{t})=\hat{p}_{t+1}(x_{1}x_{2}\ldots
x_{t},x)/\hat{p}_{t}(x_{1}x_{2}\ldots x_{t})$ with

$\displaystyle\hat{p}_{t+1}(x_{1}x_{2}\ldots x_{t},x)$ $\displaystyle=$
$\displaystyle\sum_{i,j}T^{(x)}_{ji}\hat{P}_{i,t}(x_{1}x_{2}\ldots x_{t})$
$\displaystyle=$ $\displaystyle{\bf 1}\cdot{\bf T}^{(x)}\hat{\bf
P}_{t}(x_{1}x_{2}\ldots x_{t})$

with ${\bf 1}=(1\ldots 1)^{T}$. On the other hand, an unbiased hidden state
inferred from a new observation $x_{t+1}$ is

$\hat{\bf P}_{t+1}(x_{1}x_{2}\ldots x_{t+1})=c\cdot{\bf T}^{(x_{t+1})}\hat{\bf
P}_{t}(x_{1}x_{2}\ldots x_{t}),$ (5)

where the constant $c$ is determined by the normalization ${\bf
1}\cdot\hat{\bf P}_{t+1}(x_{1}x_{2}\ldots x_{t+1})=1$, which gives finally

$\hat{\bf P}_{t+1}(x_{1}x_{2}\ldots x_{t+1})=\frac{{\bf T}^{(x_{t+1})}\hat{\bf
P}_{t}(x_{1}x_{2}\ldots x_{t})}{\hat{p}_{t+1}(x_{t+1}|x_{1}x_{2}\ldots
x_{t})}.$ (6)

The complete observation / forecasting process is thus a cyclic chain between
inferences, forecasts, and updates due to observations.

Equations (4) and (6) are essentially the same as Eq.(3.4) in Zambella , and
are today well known as ‘forward algorithm’ Zucchini . They hold also for
‘observable operator models’ (OOMs) Jaeger ; Spanczer  (in which the
positivity requirements made for HMMs are dropped), and even for ‘matrix
product states’ in statistical physics Derrida ; Klumper ) with discrete time
and discrete values.

While the Baum-Welch algorithm is often considered as superior to the forward
algorithm, it is shown in Zucchini  that both have their advantages. Indeed,
the entropy estimates of simple but non-trivial models made in Zambella  were
of unprecedented accuracy, and no brute-force estimates would have been
possible at that time with the same accuracy. Using the estimator of arXiv2003
, we now checked that all entropies quoted in Table 1 of Zambella  agreed
perfectly with brute-force estimations, with one single exception: For rules
25 and 61, the correct value of the entropy is 0.88955 bits, while 0.88947
bits was quoted in Zambella .

As shown in Zambella  (see also arXiv ), the set of ‘mixed states’ becomes
precisely the set of causal states introduced in Grass86  when minimized.
Minimization means that two vectors $\hat{\bf P}_{t}(x_{1}\ldots x_{t})$ and
$\hat{\bf P}_{t}(x^{\prime}_{1}\ldots x^{\prime}_{t})$ are identified if they
lead, via Eq.(4), to the same $\hat{p}_{t+k}(x)\;\forall k\geq 1$. No such
minimization was done in Jurgens1 , which is why no FCs were estimated there
and no precise estimates of entropy. It was also shown in Zambella  that
causal states do in general not correspond to elements of a partitioning of
phase space (in contrast to what was claimed in Young ), at least when
transient parts of the “$\epsilon$-machine” are not cut off. Cutting them off
(as proposed in most recent papers by Crutchfield et al.) is not a viable
alternative, as in some cases (called ‘totally recurrent graphs’ in arXiv )
none of the nodes of the “$\epsilon$-machine” correspond to elements of a
phase space partitioning Zambella ; arXiv . An example of the latter is e.g.
‘rule 22’ Zambella ; arXiv .

A main point in Jurgens1 ; Jurgens2  was that no such minimization can in
general be expected (and FCs are infinite), if the HMM depends on irrational
real valued parameters, such that all different observed sequences lead to
different optimal forecasts. It was already pointed out in Grass-Helv ; Grass-
Nat  that even rather simple systems can lead to infinite FC. On the other
hand, symmetries of the ${\bf T}^{(x)}$ can lead to non-trivial minimizations,
even if the ${\bf T}^{(x)}$ depend on irrational parameters (an instance where
some optimal forecasts do not depend on the history at all, but FC is infinite
nevertheless, will be be discussed below). No entropy estimates with precision
close to these in Zambella  were made in Jurgens1 , and no estimates of FCs at
all. The main reason is that no minimizations of the set of ‘mixed states’
were performed.

It is claimed in Jurgens1 ; Jurgens2 ; Jurgens3  that the set of mixed states
is in general not countable, if irrational parameters are involved, but this
is wrong. It is always countable by construction. What is correct, however, is
that the closure of the set of mixed states is in such cases uncountable, just
as the triadic Cantor set is countable, while its closure is not (a non-
countable set could be obtained by using any arbitrary starting vector ${\bf
P}_{0}$ instead of ${\bf P}_{0}={\bf P}_{\infty}$, but the resulting forecasts
would not be optimal). This non-countability of the closure is, however, not
restricted to HMMs with real-valued parameters (as claimed in Jurgens1 ;
Jurgens2 ; Jurgens3 ), but holds also for many of the HMMs studied in Zambella
. The difference between these two groups of models is not in the cardinality
of the sets of inferences, but in the Hausdorff dimension of the invariant
measure (the Blackwell measure Blackwell ) supported by it. It was zero in all
models studied in Zambella , although the box-counting dimensions were non-
zero in many cases.

The failure of distinguishing sets from their closures is also responsible for
most of Jurgens2  being obsolete. As remarked already in Zambella , the set of
mixed (=causal) states is very similar to an iterated function system (IFS),
with a difference largely overlooked in Jurgens1 ; Jurgens2 ; Jurgens3 : While
the maps ${\bf T}^{(x)}$ are chosen randomly (maybe with non-uniform
probabilities) in an IFS, their choice is in the present case constrained by
the (in general non-trivial) grammar of the sequence $\\{x_{t}\\}$. Thus
theorems about IFSs cannot be taken over blindly 111Non-trivial grammatical
restrictions do not seem to be responsible for the ‘resetting strings’ found
in some of the models studied in Zambella , which are finite strings
$R=x_{1}\ldots x_{n}$ of observed symbols for which ${\bf T}^{(R)}\equiv{\bf
T}^{(x_{n})}\ldots{\bf T}^{(x_{1})}$ maps any ${\bf P}$ onto ${\bf
P}_{\infty}$. They correspond to catastrophic forgettings of the internal
state and are then responsible for the finite Hausdorff dimension of the
Blackwell measure; in a systematic search, we now found that this phenomenon
occurs in 108 of the 256 models studied in Zambella . For the model called
‘rule 22’ in Zambella . the shortest resetting string is e.g. ‘01000010000’
(the string given in Zambella  is an extension of this).. Nevertheless, the
open set condition (OSC) Moran ; Peres-Rams  should hold in many cases. But
its application is much less trivial than assumed in Jurgens2 , where the
(non-)overlapping of the sets was confused with the (non-)overlapping of their
closures. That such a confusion can be fatal is maybe best illustrated by the
‘fat baker’s transformation’ Alexander .

If minimization of the set of mixed states had been used, the study of the
Hausdorff dimension of the set of causal states in Jurgens2  (called
‘statistical complexity dimension’ there), would have been very useful. Both
were obviously motivated by the calculations of Hausdorff dimensions and by
similar studies of the convergence of entropy and forecasting complexity in
Zambella , although that paper was not cited. But although this minimization
was alluded to repeatedly in Jurgens1 ; Jurgens2 ; Jurgens3 , it was never
actually done.

But even more natural and interesting would seem anyhow what we might call the
‘FC divergence rate’ $\alpha$, in which we replace the dependence of the FC on
the precision of the hidden state inferences (as in the statistical complexity
dimension Jurgens2 ) by its dependence on the achieved values of the Shannon
entropy. Assume we have a stochastic process with finite entropy $h$ and
infinite true FC, and assume that we have an approximate forecasting scheme
with a finite FC $C$ and an approximate entropy $h_{C}>h$. Then we might
expect generically

$C\sim\delta h^{-\alpha}\qquad{\rm with}\;\;\;\delta h=h_{C}-h.$ (7)

Indeed, this can be defined for general stationary ergodic processes, not only
for HMM. All what is needed is that one can define a sequence of approximate
HMMs or OOMs, to which one can apply Eqs. (4,6). Minimizing $h_{C}-h$ can be
used for model (or parameter) inference Zucchini , but minimizing both
$h_{C}-h$ and $C$ at fixed $\alpha$ could be useful for finding models /
parameters / approximations that are both accurate and relatively easy to
forecast.

Finally, Ref. Jurgens3  is devoted to the calculation of the ‘ambiguity rate’
$h_{a}$ of a process, a notion supposedly introduced by Shannon in Shannon  as
a quantity opposed to ‘equivocation’. In fact, ‘ambiguity’ is mentioned
exactly once in Shannon , but as a synonym for equivocation. The concept as
defined in Jurgens3  is the rate at which information about the past can be
discarded, and yet prediction of the future is optimal. If $h_{a}<h$, this
would mean that less information is dismissed than new information is
obtained, i.e. that FC (the information stored in an optimal forecasting
scheme) diverges with time. In the opposite case, i.e. when $h_{a}=h$, it was
claimed that “the associated $\epsilon$-machine’s internal causal-state
process is stationary.” Jurgens3 . This is wrong, as demonstrated by the
counter-examples given in Zambella . There it was shown that FC is finite in
all considered cases (i.e., $h_{a}=h$), but yet the forecasting process is not
stationary in cases like ‘rule 22’, because of the slow convergence of FC.

When each observed sequence leads to a different forecast, it is clear that no
information can be dismissed in an optimal forecast, and thus $h_{a}=0$. In
some cases, the situation is a bit more subtle. Consider, e.g., the example in
Sec. 7B of Jurgens3  for control parameter values $x=0.25,\alpha=0.5$, which
was treated in detail in appendix B of Jurgens3 . In this model, there are
three emitted symbols $\triangle,\Box,\circ$. One finds that always
$\hat{p}_{t}(\Box)=1/4$, while $\hat{p}_{t}(\triangle)$ and
$\hat{p}_{t}(\circ)$ depend non-trivially on the observations at times
$1,\ldots t-1$. Indeed, no two different histories lead to the same
$\hat{p}_{t}(\triangle)$ and $\hat{p}_{t}(\circ)$ (at least for $t<12$; for
larger $t$ one would need extended precision arithmetic to avoid numerical
problems), so that no information can be dismissed if all forecasts are to be
optimal, and thus $h_{a}=0$ — while $h_{a}=0.4499$ bits is quoted in Jurgens3
. Obviously, this wrong value was obtained because $h_{a}$ was calculated in
Jurgens3  using the open set condition, and overlaps between sets were
confused with overlaps between their closures. Since this error was made in
all calculations of $h_{a}$, all numerical results of Jurgens3  are either
trivial or obsolete.

In summary, we have shown that most results of Jurgens1 ; Jurgens2 ; Jurgens3
are either wrong or were well known for a long time. In particular, many of
them were first obtained in Zambella  (which was not cited), a fact pointed
out already several times to Dr. Crutchfield (see also arXiv ; arXiv2 ).

## References

  * (1) Y. Bengio, “Markovian models for sequential data”, Neural Computing Surveys, 2, 129, (1999).
  * (2) Y. Ephraim and N. Merhav, “Hidden markov processes”, IEEE Trans. Informat. Theory 48, 1518 (2002)
  * (3) W. Zucchini, I.L. MacDonald, and R. Langrock, “Hidden Markov Models for Time Series. An Introduction using R” (CRC Press, Boca Raton, 2016).
  * (4) P. Jacquet, G. Seroussi, W. Szpankowski, “On the entropy of a hidden Markov process”, Theoretical Computer Science 395, 203 (2008).
  * (5) E. Ordentlich and T. Weissman, “New bounds on the entropy rate of hidden Markov processes”, Information Theory Workshop, IEEE (2004).
  * (6) A.M. Jurgens and J.P. Crutchfield, “Shannon Entropy Rate of Hidden Markov Processes J. Stat. Phys. 183, 32 (2021).
  * (7) P. Grassberger, Int. J. Theor. Phys. 25, 907 (1986).
  * (8) D. Zambella and P. Grassberger, “Complexity of Forecasting in a Class of Simple Models”, Complex Systems 2, 269 (1988).
  * (9) J.P. Crutchfield and K. Young, “Inferring statistical complexity”, Phys. Rev. Lett. 63, 105 (1989).
  * (10) A.M. Jurgens and J.P. Crutchfield, “Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes”, Chaos 31, 083114 (2021).
  * (11) A.M. Jurgens and J.P. Crutchfield, “Ambiguity Rate of Hidden Markov Processes”, Phys. Rev. E 104, 064107 (2021).
  * (12) H. Jaeger, “Discrete-time, discrete-valued observable operator models: a tutorial”, url =
https://www.ai.rug.nl/minds/uploads/oom-tutorial.pdf (accessed Nov. 20, 2023).

  * (13) I. Spanczér, Observable operator models”, Austrian Journal of Statistics 36, 41 (2007).
  * (14) B. Derrida, M. R. Evans, V. Hakim and V. Pasquier, “Exact solution of a 1D asymmetric exclusion model using a matrix formulation”, J. Phys. A: Math. & General 26, 1493 (1993).
  * (15) A. Klümper, A. Schadschneider and J. Zittartz, “Matrix Product Ground States for One-Dimensional Spin-1 Quantum Antiferromagnets”, Europhys. Lett. 24, 293 (1993).
  * (16) P. Grassberger, “Entropy Estimates from Insufficient Samplings”, arXiv preprint arXiv:physics/0307138 (2003).
  * (17) P. Grassberger, “Some comments on computational mechanics, complexity measures, and all that”, arXiv preprint arXiv:1708.03197 (2017).
  * (18) P. Grassberger, “Problems in quantifying self-generated complexity”, Helv. Phys. Acta 62, 489 (1989).
  * (19) P. Grassberger, Z. Naturforsch. 43a, 671 (1988).
  * (20) D. Blackwell, “The entropy of functions of finite-state Markov chains”, Matematika 3, 143 (1959).
  * (21) P.A.P. Moran, “Additive functions of intervals and Hausdorff measure”, Math. Proc. Cambridge Philos. Soc. 42, 15 (1946).
  * (22) Y. Peres, M. Rams, K. Simon, and B. Solomyak, “Equivalence of positive Hausdorff measure and the open set condition for self-conformal sets”, Proc. Amer. Math. Society 129, 2689 (2001).
  * (23) J.C. Alexander and J.A. Yorke, “Fat baker’s transformations”, Ergod. Th. & Dynam. Sys. 4, 1 (1984).
  * (24) C.E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379, 623 (1948).
  * (25) P. Grassberger, “Comment on ‘Inferring Statistical Complexity’ ”, arXiv preprint arXiv:1708.04190 (2017).