# Cross Modal Retrieval with Querybank Normalisation

Simion-Vlad Bogolin1,2,* Ioana Croitoru1,2,*
Hailin Jin3 Yang Liu1,4,$\dagger$ Samuel Albanie1,5,$\dagger$
1Visual Geometry Group, University of Oxford 2Inst. of Mathematics of the
Romanian Academy 3Adobe Research
4Wangxuan Inst. of Computer Technology, Peking University 5Department of
Engineering, University Cambridge

###### Abstract

Profiting from large-scale training datasets, advances in neural architecture
design and efficient inference, joint embeddings have become the dominant
approach for tackling cross-modal retrieval. In this work we first show that,
despite their effectiveness, state-of-the-art joint embeddings suffer
significantly from the longstanding “hubness problem” in which a small number
of gallery embeddings form the nearest neighbours of many queries. Drawing
inspiration from the NLP literature, we formulate a simple but effective
framework called Querybank Normalisation (QB-Norm) that re-normalises query
similarities to account for hubs in the embedding space. QB-Norm improves
retrieval performance without requiring retraining. Differently from prior
work, we show that QB-Norm works effectively without concurrent access to any
test set queries. Within the QB-Norm framework, we also propose a novel
similarity normalisation method, the Dynamic Inverted Softmax, that is
significantly more robust than existing approaches. We showcase QB-Norm across
a range of cross modal retrieval models and benchmarks where it consistently
enhances strong baselines beyond the state of the art. Code is available at
https://vladbogo.github.io/QB-Norm/.

##  1 Introduction

00footnotetext:  *Equal contribution. $\dagger$Corresponding authors.

As the improving price-performance of hardware underpinning sensors, storage
and networking continues to enable the expansion of humanity’s digital
archives, the capacity to efficiently search data takes on greater commercial
and scientific importance. An appealing way to search such data is via natural
language queries, in which the user describes the target of their search
exactly as they would to another human, rather than employing specialised
database languages such as Structured Query Language (SQL).

Figure 1:  Left: The hubness problem. We consider the problem of cross modal
retrieval in which queries $q_{1}$ and $q_{2}$ are compared against a gallery
of samples, $x_{1}$ and $x_{2}$. As we show in Sec. 3.2, the high-dimensional
joint embeddings employed by modern methods for cross-modal retrieval suffer
from the “hubness problem” [93]. A hub (e.g. $x_{2}$) is the nearest neighbour
to multiple queries ($q_{1}$ and $q_{2}$), producing poor quality retrieval
results (bottom left). Right: Querybank Normalisation employs a querybank to
normalise similarities, reducing the similarity of hub $x_{2}$ to query
$q_{1}$, improving the retrieval results (bottom right).

Towards this goal, a rich body of research literature has studied the problem
of cross modal retrieval, the task of searching a gallery of samples in one
modality given a query in another. In particular, there has been significant
progress in recent years for systems that can efficiently search images [104],
audio [86] and videos [122] with natural language queries by employing cross
modal embeddings.

The dominant cross modal embedding paradigm employs deep neural networks that
project modality-specific samples into a high-dimensional, real-valued vector
space in which they can be directly compared via an appropriate distance
metric. A key challenge for such methods, intrinsic to such high-dimensional
spaces, is the emergence of “hubs” [93]—embedding vectors that appear amongst
the nearest neighbour sets of disproportionately many other embedding vectors
(Fig. 1, left). To illustrate this challenge, we show empirically in Sec. 3.2
and Fig. 2 that hubness is prevalent among a range of leading retrieval
methods. Hubs have consequences: if left unaddressed, they lead to a
significant degradation in the search ranking yielded by a retrieval system
[9]. The hubness problem has received considerable attention [9, 93, 75] and a
number of approaches have been proposed to address it [36], with notable
contributions in the NLP literature focusing on bilingual word translation
[28, 102, 25]. One contribution of our work is to show how each of these
methods can be interpreted within a single unifying conceptual framework
termed Querybank Normalisation (QB-Norm, Fig. 1, right), that employs a
querybank of samples during inference to reduce the influence of hubs in the
gallery. We observe that existing methods have two challenges: (1) To date,
these approaches have only been shown to work with concurrent access to
multiple test queries—an assumption that is impractical for real-world
retrieval systems; (2) They are sensitive to querybank selection, and indeed
actively harm performance for certain querybanks (Tab. 2). To address the
first challenge, we demonstrate through careful experiments (Tab. 1) that QB-
Norm does not require concurrent access to test queries to be effective. To
address the second challenge, we propose a new normalisation method, Dynamic
Inverted Softmax (DIS), that operates as a module within the QB-Norm
framework. We show that DIS provides effective normalisation, yet is more
robust than prior approaches [28, 102, 25].

We make the following contributions: (1) We motivate our study by
demonstrating that the longstanding problem of hubness remains a significant
concern in modern cross modal embeddings for retrieval; (2) We propose
Querybank Normalisation (QB-Norm), a simple non-parametric framework that
brings significant gains in retrieval performance without requiring model
fine-tuning; (3) We provide the first (to the best of our knowledge)
demonstration that Querybank Normalisation methods retain their effectiveness
for cross modal retrieval with no access to test queries beyond the current
query; (4) We propose the Dynamic Inverted Softmax, a novel normalisation
method for Querybank Normalisation that is more robust than prior literature;
(5) We show that QB-Norm is highly effective across a broad range of tasks,
models and benchmarks.

##  2 Related work

In this section, we summarise prior work from the literature that relates to
our approach, focusing on cross-modal retrieval, external memory banks and
hubness.

Cross-modal representations. Following initial studies in psychology [12],
early frameworks for cross-modal retrieval included Gaussian Mixture Models
[101] modelling translation via EM [32], Topic Models [10], CCA [94],
KCCA[103] and rank optimisation [117]. Motivated by the successes of deep
metric learning [22] and deep visual semantic embeddings [40], there has since
been a Cambrian explosion of cross-modal embedding methods for text-image
retrieval [65, 112, 61, 82, 34], text-video [4, 123, 29, 81, 125, 118, 27, 6]
text-audio [86], image-audio [62, 87, 2, 84, 131] and combinations of all the
above [5]. Recent research spanning these tasks has explored large-scale pre-
training [80, 91], domain adaptation [74, 83] and tight integration of
multiple sensory modalities into one side of the embedding space [79, 73, 41].

Similarity search for retrieval: Tricks of the trade. A plethora of techniques
have been developed to support and enhance similarity search for retrieval,
including k-d trees [8], re-ranking [90, 55], query expansion [24, 23], vector
compression schemes based on binary codes [44, 49] and quantization [54, 56]
that help address the curse of dimensionality [7]. Algorithms have been
developed for approximate k-nearest neighbour graph construction on CPUs [31]
and GPUs[58], with the latter drawing on product quantization techniques to
scale up to billion-scale searches.

Differently from the work on cross modal representations and improved
similarity search described above, we focus specifically on tackling the
problem of hubness in cross-modal embeddings, which we demonstrate (Sec. 3.2)
to be a widespread issue among leading cross-modal embedding frameworks.

Memory bank augmented architectures. Memory banks in various forms have been
studied as useful extensions to neural network architectures to facilitate
general problem-solving [45, 126, 46, 98], better image captioning [88, 120,
26] and summarisation [63, 67], enhance self-supervised training dynamics [48,
13, 72] and to provide a mechanism to deal with rare instances [60, 124]. Our
proposed Querybank Normalisation framework likewise stores embedding samples
in an external memory bank, but targets a very different problem to these
works, namely hubness mitigation.

The Hubness Problem. The hubness problem was formally characterised by
Radovanovic et al. [93], who observed that in points sampled from a
distribution with high intrinsic dimensionality, the distribution of
“k-occurrences” (the number of times a point appears in the k nearest
neighbours of other points) skews heavily to the right. Although there is
disagreement about the cause of hubness [75], it has been conceptually linked
[9] to distance concentration in high-dimensions (high-dimensional points lie
close to a hypersphere centred on the data mean, i.e., they all exhibit a
similar distance to the mean [39]). It is thought that hubs then result from
this phenomenon through the non-negligible variance in the distribution of
distances to the mean in finite dimensions [93].

Figure 2:  Hubness is pervasive in leading methods for text-video retrieval.
The charts depict the distribution of the number of times each gallery video
was retrieved by test set queries (x-axes video ids are ordered by decreasing
retrieval count). Top row (different models): We report retrieval
distributions for CE [73], TT-CE+ [27], MMT [41] and CLIP2Video [35] on the
MSR-VTT benchmark [121]. Bottom row (different datasets): We report retrieval
distributions for the TT-CE+ [27] method on four additional datasets, DiDeMo
[50], LSMDC [95], VaTeX [116], and ActivityNet-captions [66], In all
instances, we observe strong hubness, in which a small number of videos are
retrieved disproportionately often, damaging performance.

Hubness Mitigation. One paradigm has focused on rescaling the similarity space
to account for asymmetries in nearest neighbour relations [99]—a process that
can be achieved through both local [127, 57] and global [99] scaling schemes.
Another work has focused on addressing the hub-like tendency of centroids in
the data through Laplacian-based kernels [106] and centring [107, 47].
Fedbauer et al. provide a comprehensive empirical comparison of these families
of methods [36] and note that while effective, these approaches scale
quadratically, making their naive application unsuitable for large datasets.
One exception is the CENT method [107], however we did not find this approach
to be effective (experiments are provided in the supplementary). In the zero-
shot learning literature, works have sought to address hubness by mapping
(text) targets back into the (image) query space [100, 129], and by minimising
proxies for hubness [71] and skewness in the k-occurrences distribution [21]
to improve 3D few-shot learning performance. More closely related to our work,
[28] propose general retrieval schemes for which queries are matched with
targets for which they form the nearest neighbour. This work was built upon
the NLP literature by [25], who propose a cross-domain local scaling scheme
(which can be integrated into the loss [59]), and by [102], who introduce the
Inverted Softmax (IS) to mitigate hubness when translating between
dictionaries in different languages. We discuss the relationship of our
approach to [28, 25, 102] in more detail in Sec. 3 and compare these methods
with our proposed Dynamic Inverted Softmax in Sec. 4.

Also related to our work, [70, 18, 132] enforce a bipartite matching
constraint between queries and test set items by applying an IS over the full
set of test queries—a constraint that is unrealistic for practical retrieval
systems that experience continuous operation from users. One contribution of
this paper is to demonstrate that concurrent access to test queries is not
required. A second contribution of our work, not considered in prior work, is
to show that the techniques proposed above can actively damage retrieval
performance for particular querybank selections, an issue that we address with
our proposed Dynamic Inverted Softmax.

##  3 Method

We first define the task of retrieval with cross modal embeddings (Sec. 3.1),
before outlining the motivation for our work by examining the hubness problem
in the context of text-video retrieval (Sec. 3.2). Next, we introduce the
Querybank Normalisation framework (Sec. 3.3), generalising several existing
approaches to address this issue. Finally, we explore designs for framework
components and introduce the proposed Dynamic Inverted Softmax for robust
similarity normalisation (Sec. 3.4).

###  3.1 Task definition

Given a gallery, $\mathcal{G}$, of samples in one modality, $m_{g}$ and a
query, $q$, in another modality, $m_{q}$, the objective of cross modal
retrieval is to rank the gallery samples according to how well they match the
query. We study this problem within the framework of learning cross modal
embeddings [40]: specifically, we seek to learn a pair of encoders, $\phi_{q}$
and $\phi_{g}$, that map each query, $q$, and gallery sample, $g$, into a
shared real-embedding space, $\mathbb{R}^{C}$, such that $\phi_{q}(q)$ and
$\phi_{g}(g)$ are close if and only if $q$ is similar to $g$. We assume that
we are given access to a training set of $T$ corresponding query and gallery
samples $\\{(q_{i},g_{i})\\}_{i=1}^{T}$ for the purposes of learning the
embeddings. However, the queries and gallery used to evaluate retrieval
performance (i.e. the test set) are unseen during training.

The choice of similarity measure used to define a “good match” is determined
by the application domain. For instance, in the task of text-video retrieval
with natural language queries, the objective is to rank a gallery of videos
according to how well their content is described by a written free-form text
query [79], whereas in image-audio retrieval the objective is typically to
obtain audio samples from the gallery that share the same semantic category as
the image query [3]. In this work, we focus particularly on cross modal
retrieval tasks with natural language queries, for two reasons: (1) these
tasks have received limited attention in the hubness mitigation literature,
(2) hubness has been shown to be particularly prevalent in embeddings with
high intrinsic dimensionality [93]. Since natural language queries can express
more complex concepts than individual words (such as those considered in zero-
shot learning image labelling tasks [28]), we expect might expect natural
language queries to naturally induce cross modal embeddings with greater
intrinsic dimensionality, and thus may have greater potential to benefit from
hubness mitigation.

###  3.2 Motivation

It has long been observed that high-dimensional embedding spaces are prone to
hubness [93], in which a small proportion of samples appear disproportionately
frequently among the set of k-nearest neighbours of all embeddings. As noted
by Berenzweig [9], this property can have damaging consequences for retrieval
systems that employ nearest neighbour search to find the best gallery match
for a given query. To illustrate this issue, we consider the problem of video
retrieval with natural language queries. We plot the distribution of the
number of times each gallery video was retrieved on the MSR-VTT retrieval
benchmark [121] for an array of text-video retrieval methods, including CE
[73], TT-CE+ [27], MMT [41] and CLIP2Video [35], the latter of which
represents the current state of the art on this benchmark. In each case, we
see striking evidence of hubness—a small number of videos are retrieved
extremely often, while others are not retrieved at all. This phenomenon is not
limited to a particular retrieval model, suggesting that the issue is not
readily addressed by the use of multiple video modalities, attention
mechanisms and large-scale pretraining implemented in various combinations by
these approaches.

###  3.3 Querybank Normalisation

To address the hubness issues observed among cross modal embeddings for text-
video retrieval in the previous section, we first turn to the existing
literature on hubness mitigation. As noted in Sec. 2, hubness effects have
been studied in several problem domains, including Zero-Shot Learning [28,
100], NLP [102, 25], biomedical statistics [99] and music retrieval [99].
Among this literature, we are particularly interested in methods that can be
applied in a practical cross modal retrieval setting, namely, those methods
whose complexity scales at most linearly with the size of the gallery (rather
than quadratic complexity methods that seek to address hubness within a fixed
embedding space [36]). To clarify relationships between existing approaches,
we cast them into the Querybank Normalisation framework (Fig. 1), which
comprises two components, querybank construction and similarity normalisation,
described next:

Querybank construction. To mitigate hubness in the cross modal embedding
space, we seek to alter the similarities between embeddings in a way that
minimises the influence of hubs. To adjust similarities, we first construct a
querybank of $N$ samples, $\mathcal{B}=\\{b_{1},\dots,b_{N}\\}$ from the query
modality, $m_{q}$, which will serve as a probe to measure the hubness of
gallery samples.

Similarity normalisation. To normalise similarities to account for hubs, we
assume access to a query, $q$, trained encoders $\phi_{q}$ and $\phi_{g}$,
querybank $\\{b_{1},\dots,b_{N}\\}$, and a gallery $\mathcal{G}$. For each
$g_{j}\in\mathcal{G}$, we first compute a probe vector,
$p_{j}\in\mathbb{R}^{N}$,
$p_{j}(i)=\text{sim}(\phi_{q}(b_{i}),\phi_{g}(g_{j}))$ where
$\text{sim}(\cdot,\cdot)$ denotes similarities in the cross modal embedding
space (e.g. cosine similarity). The probe vectors are then stacked to form a
probe matrix $P\in\mathbb{R}^{|\mathcal{G}|\times N}$. Similarly, we compute
for each query a vector of unnormalised similarities,
$s_{q}\in\mathbb{R}^{|\mathcal{G}|}$,
$s_{q}(j)=\text{sim}(\phi_{q}(q),\phi_{g}(g_{j}))$. Here
$j\in\\{1,\dots,|\mathcal{G}|\\}$ indexes over all gallery elements. Finally,
we define a querybank normalisation function, $\textsc{QB-
Norm}:\mathbb{R}^{|\mathcal{G}|}\times\mathbb{R}^{|\mathcal{G}|\times
N}\to\mathbb{R}^{|\mathcal{G}|}$, which yields, for each query $q$ and gallery
$\mathcal{G}$, a vector of querybank normalised similarities,
$\eta_{q}=\textsc{QB-Norm}(s_{q},P)\in\mathbb{R}^{|\mathcal{G}|}$. Various
candidates for $\textsc{QB-Norm}(\cdot)$ are discussed in Sec. 3.4.

In practice, the probe matrix employed for similarity normalisation can be
precomputed and re-used across all queries (improving computational efficiency
at the cost of higher memory). An overview of the resulting QB-Norm algorithm,
and its application to ranking gallery samples for a collection of queries,
$\mathcal{Q}$, is summarised in Alg. 1.

Algorithm 1 Ranking with Querybank Normalisation

0: queries, $\mathcal{Q}\subset m_{q}$

0: gallery, $\mathcal{G}\subset m_{g}$

1: Querybank construction.

2: Construct querybank, $\mathcal{B}=\\{b_{1},\dots,b_{N}\\}\subset m_{q}$

3: Similarity normalisation:

4: Precompute querybank probe matrix

5: for gallery sample $g_{j}\in\mathcal{G}$ do

6: for querybank sample $b_{i}\in\mathcal{B}$ do

7: Compute probe matrix entry
$P(j,i)=\text{sim}(\phi_{q}(b_{i}),\phi_{g}(g_{j}))\in\mathbb{R}$

8: end for

9: end for

10: query computations: QB-Norm similarities

11: for query $q\in\mathcal{Q}$ do

12: for gallery sample $g_{j}\in\mathcal{G}$ do

13: Compute unnormalised similarity
$s_{q}(j)=\text{sim}(\phi_{q}(q),\phi_{g}(g_{j}))$

14: end for

15: $\eta_{q}=\textsc{QB-Norm}(s_{q},P)\in\mathbb{R}^{|\mathcal{G}|}$.

16: search ranking = argsort($\eta_{q}$)

17: end for

###  3.4 Design choices

The Querybank Normalisation framework admits a number of viable choices for
both querybank construction and similarity normalisation. To illustrate this
point, we first cast three techniques for hubness mitigation proposed in the
NLP literature into the framework. We then introduce our proposed alternative,
the Dynamic Inverted Softmax.

Globally-Corrected (GC) retrieval [28]. This approach, originally introduced
for the tasks of bilingual translation and zero-shot learning, can be
implemented by constructing the querybank from the full set of test queries,
$\mathcal{Q}$, (or all semantic labels, in the cross modal setting of zero-
shot image labelling). For their bilingual translation task, the authors
supplement their querybank by an additional randomly sampled collection of
instances from $m_{q}$, which improved performance. The normalised similarity
corresponding to $q$ and gallery vector $g_{j}$ is defined via
$\eta_{q}(j)=-(\text{Rank}(s_{q}(j),p_{j})-s_{q}(j))\in\mathbb{R}$, where
$\text{Rank}:\mathbb{R}\times\mathbb{R}^{N}\rightarrow\\{0,\dots,N\\}$ returns
the rank of the first argument with respect to the array of elements in the
second argument.

Cross-Domain Similarity Local Scaling (CSLS) [25]. Introduced for the task of
bilingual word translation, CSLS constructs an initial querybank comprising
all possible queries (corresponding to source vocabulary samples), then
employs a different subset of the querybank to normalise each gallery sample.
Let $\hat{p}_{j}\in\mathbb{R}^{K}$ denote the probe vector, $p_{j}$,
restricted to the $K$ querybank samples that are most similar to gallery
sample $g_{j}$. Similarly, let $\hat{s}_{q}\in\mathbb{R}^{K}$ denote the
unnormalised similarity vector, $s_{q}$, restricted to the $K$ gallery samples
that are most similar to query $q$. Then the normalised similarity is computed
via:
$\eta_{q}(j)=2s_{q}(j)-\frac{1}{K}\mathbf{1}^{T}\hat{s}_{q}-\frac{1}{K}\mathbf{1}^{T}\hat{p}_{j}\in\mathbb{R}$.

Inverted Softmax (IS) [102]. Targeting bilingual word translation, this method
constructs a querybank from the source vocabulary (corresponding to all
possible queries of interest). For practical implementations, the authors
recommend to uniformly randomly subsample a feasible number of queries.
Similarity normalisation is implemented via:

$\eta_{q}(j)=\frac{\exp(\beta\cdot s_{q}(j))}{\mathbf{1}^{T}\exp[\beta\cdot
p_{j}]}\in\mathbb{R}\vspace{-0.1cm}$ (1)

where $\exp[\cdot]$ denotes elementwise exponentiation and $\beta$ is a
hyperparameter referred to as the “inverse temperature”.

Dynamic Inverted Softmax (DIS). In experiments with the methods described
above (discussed in detail in Sec. 4) we observed an important practical
issue: if the querybank does not effectively cover the space containing the
gallery, performance is severely degraded such that it falls below the
performance of unnormalised similarities. This characteristic renders them
less desirable for a general-purpose solution: we would like something that
not only enhances performance in favourable conditions, but also “does no
harm” when curating a querybank to match the gallery closely is challenging.
To address this issue, in addition to the querybank probe matrix described in
Alg. 1, we also precompute a gallery activation set,
$\mathcal{A}=\\{j:j\in\stackrel{{\scriptstyle\mathclap{\scriptsize\mbox{k}}}}{{\operatorname*{argmax}}}_{l}s(b_{i},g_{l}),i\in\\{1,\dots,N\\}\\}$.
Here, the notation
$\stackrel{{\scriptstyle\mathclap{\scriptsize\mbox{k}}}}{{\operatorname*{argmax}}}_{l}f(l)$
denotes the $k$-max-select operator that returns the $k$ values of $l$ that
maximise $f(l)$ (like $j$, $l$ also runs over the gallery indices and $k$ is
set as a hyperparameter). Intuitively, this set contains the indices of
gallery vectors that our querybank probe has identified as potential hubs. We
create a Dynamic Inverted Softmax by activating the inverted softmax only for
nearest neighbour retrievals that fall within this set:

$\eta_{q}(j)=\begin{cases}\frac{\exp(\beta\cdot
s_{q}(j))}{\mathbf{1}^{T}\exp[\beta\cdot p_{j}]}&\text{if
}\operatorname*{argmax}_{l}s_{q}(l)\in\mathcal{A}\\\
s_{q}(j)&\text{otherwise}\end{cases}\vspace{-0.1cm}$ (2)

Since $s_{q}(j)$ is computed as an intermediate step in Eqn. 1, the only
additional cost incurred by the Dynamic Inverted Softmax over the standard
Inverted Softmax stems from the argmax operation in Eqn. 2. Fortunately, this
computation can be performed extremely efficiently with almost no loss in
precision, even at the scales of billions of gallery samples [58]. We show
through experiments in Sec. 4, the Dynamic Inverted Softmax is significantly
more robust than GC, CSLS and IS: crucially, it does not harm performance when
employed with suboptimal querybank selection.

##  4 Experiments

In this section, we first briefly describe the datasets and metrics used for
our experiments (Sec. 4.1). We then conduct a series of experiments that: (i)
demonstrate our claim that QB-Norm is effective without concurrent access to
more than one test query; (ii) investigate the influence of querybank size;
(iii) compare the Dynamic Inverted Softmax against prior methods; (iv) ablate
other QB-Norm components (Sec. 4.2). Finally, we demonstrate the generality of
Querybank Normalisation by applying it to a broad range of models, tasks and
datasets (Sec. 4.3).

###  4.1 Datasets and Evaluation Metrics

We conduct experiments on standard benchmarks for text-video retrieval: MSR-
VTT [121], MSVD [16], DiDeMo [50], LSMDC [95], VaTeX [116] and QueryYD [85].
We also investigate QB-Norm on text-image retrieval (MSCoCo [20]), text-audio
retrieval (AudioCaps [64]), and image-to-image retrieval (CUB-200-2011 [111],
Stanford Online Products [105]). Detailed descriptions of each dataset are
deferred to the supplementary. We report standard retrieval performance
metrics: R@K (recall at rank K, higher is better) and MdR (median rank, lower
is better). For each study, we report the mean and standard deviation over
three randomly seeded runs.

###  4.2 Querybank Normalisation

We conduct initial studies on the MSR-VTT benchmark for text-video retrieval
using TT-CE+ [27] to address a series of questions relating to Querybank
Normalisation.

Do we need access to more than one test query at a time to mitigate hubness?
Prior work has investigated the use of IS for image and video retrieval with
natural language queries, but only by assuming simultaneous access to the full
test set of queries to construct the querybank [70, 18, 132]. The motivation
for this approach [70] is to enforce a bipartite matching constraint that
encodes the prior knowledge that each test query maps to exactly one gallery
sample. Unfortunately, this approach is impractical to deploy for real world
systems that experience sequential user queries. Therefore, we first ask
whether we require concurrent access to all test set queries by constructing
an alternative querybank from the training set. We evaluate performance with
QB-Norm using DIS normalisation in which we construct querybanks from: (i) all
test set queries; (ii) all validation set queries: (iii) a randomly subsampled
subset of the training set matching the size of the test set (resampled once
for each trained model to estimate variance). The results are reported in Tab.
1. Remarkably, we observe that training set querybanks perform comparably to
test set querybanks. Given this finding, we conclude that test set querybanks
are not necessary to mitigate hubness. We therefore restrict all querybank
construction to use training set samples for all remaining experiments,
ensuring valid comparisons on standard retrieval benchmarks.

Querybank Source | Size | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---|---
No querybank | - | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
Training set | 60k | $17.3_{\pm 0.0}$ | $42.1_{\pm 0.1}$ | $54.9_{\pm 0.0}$ | $8.0_{\pm 0.0}$
Val set | 10k | $16.6_{\pm 0.1}$ | $40.8_{\pm 0.1}$ | $53.7_{\pm 0.1}$ | $9.0_{\pm 0.0}$
Test set | 60k | $17.5_{\pm 0.0}$ | $42.4_{\pm 0.1}$ | $55.1_{\pm 0.0}$ | $8.0_{\pm 0.0}$

Table 1: Effective querybanks can be constructed from the training set.
Performance is reported on MSR-VTT full split [121]. We observe that a
querybank of 60K samples from the training set performs comparably to a test
set querybank.

What is the influence of querybank size on performance? To address this, we
sample querybanks across a range of different scales, and report mean and
standard deviations across metrics for three samplings of each scale using DIS
normalisation. The results are shown in Fig. 3 (left), where we observe that
performance increases with querybank size, but strong results can be obtained
with a querybank of just a few thousand random training samples.

Figure 3: Retrieval results reported for a TT-CE+ [27] model on the MSR-VTT
[121] benchmark for text-video retrieval with QB-Norm DIS normalisation. Left:
The influence of querybank size on retrieval performance on the validation
split of MSR-VTT. We observe that performance grows steadily with increasing
querybank size, but saturates. Right: The influence of inverse temperature,
$\beta$, on the validation split of MSR-VTT. Performance varies smoothly with
inverse temperature, peaking at a value of 20.

What is the influence of the similarity normalisation strategy on QB-Norm? To
address this question, we first sample querybanks of 5,000 samples from the
MSR-VTT training split and compare the normalisation strategies described in
Sec. 3.4. Results are reported in the upper block (“In Domain”) of Tab. 2
where we observe that CSLS [25], IS [102] and the proposed DIS strategy
perform best, and that all querybank normalisation methods substantially
outperform the baseline without normalisation. Next, to evaluate the
robustness of the normalisation strategies to different querybank sampling
distributions, we sample additional querybanks of 5,000 samples from the
training splits of two different video retrieval datasets: MSVD [16] (whose
query domain closely matches MSR-VTT), and LSMDC [95] (a collection of movies
with audio descriptions, whose query domain is further away from MSR-VTT), and
evaluate retrieval performance on MSR-VTT test. We report results in the
middle blocks of Tab. 2 (“Close Domain” and “Far Domain”) where we observe
that sampling the querybank from a closely overlapping domain (MSVD) works
well for all methods (with DIS performing best), but that sampling from a
different domain (LSMDC) degrades performance below the baseline without
normalisation for all methods except GC [28] and DIS.

To understand why the LSMDC querybank could be actively harmful for methods
other than GC [28] and DIS, we studied the samples closely and observed that
LSMDC queries retrieve only a small subset of videos from the video gallery
(and thus were ineffectual at their primary purpose of probing for hubs). To
validate that this retrieval distribution was indeed the cause of the issue,
we constructed an “adversarial” querybank from MSR-VTT by selecting the 5,000
training queries that achieved the smallest coverage (i.e. retrieved the
lowest number of distinct videos) over the MSR-VTT test set. We report numbers
in the Adversarial block of Tab. 2. We observe that despite sampling from the
same dataset, all normalisation methods other than DIS are significantly
harmed. In the lower block, Overall, we present the overall performance
computed as geometric mean for all methods. Since DIS performs the best
overall (presented in bold in Tab. 2), we use it as our normalisation strategy
for QB-Norm for all remaining experiments.

QB Source Data | Normalisation | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---|---
No QB | - | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
In Domain |  |  |  |  |
MSR-VTT |  QB-Norm (GC [28]) | $15.8_{\pm 0.0}$ | $39.1_{\pm 0.0}$ | $51.8_{\pm 0.0}$ | $10.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (CSLS [25]) | $16.8_{\pm 0.1}$ | $41.5_{\pm 0.1}$ | $54.4_{\pm 0.1}$ | $8.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (IS [102]) | $17.1_{\pm 0.1}$ | $41.9_{\pm 0.2}$ | $54.7_{\pm 0.1}$ | $8.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (DIS) | $17.0_{\pm 0.1}$ | $41.3_{\pm 0.1}$ | $54.1_{\pm 0.1}$ | $8.6_{\pm 0.5}$
Close Domain |  |  |  |  |
MSVD |  QB-Norm (GC [28]) | $15.2_{\pm 0.1}$ | $38.8_{\pm 0.0}$ | $51.7_{\pm 0.0}$ | $10.0_{\pm 0.0}$
MSVD |  QB-Norm (CSLS [25]) | $16.5_{\pm 0.0}$ | $41.2_{\pm 0.0}$ | $54.1_{\pm 0.1}$ | $9.0_{\pm 0.0}$
MSVD |  QB-Norm (IS [102]) | $16.4_{\pm 0.2}$ | $40.9_{\pm 0.2}$ | $53.9_{\pm 0.1}$ | $9.0_{\pm 0.0}$
MSVD |  QB-Norm (DIS) | $16.7_{\pm 0.1}$ | $41.1_{\pm 0.1}$ | $54.0_{\pm 0.0}$ | $9.0_{\pm 0.0}$
Far Domain |  |  |  |  |
LSMDC |  QB-Norm (GC [28]) | $14.8_{\pm 0.1}$ | $38.2_{\pm 0.0}$ | $51.4_{\pm 0.0}$ | $10.0_{\pm 0.0}$
LSMDC |  QB-Norm (CSLS [25]) | $13.4_{\pm 0.0}$ | $35.9_{\pm 0.0}$ | $48.5_{\pm 0.0}$ | $11.0_{\pm 0.0}$
LSMDC |  QB-Norm (IS [102]) | $11.6_{\pm 0.0}$ | $32.5_{\pm 0.0}$ | $44.6_{\pm 0.0}$ | $14.0_{\pm 0.0}$
LSMDC |  QB-Norm (DIS) | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.2_{\pm 0.1}$ | $10.0_{\pm 0.0}$
Adversarial |  |  |  |  |
MSR-VTT |  QB-Norm (GC [28]) | $14.5_{\pm 0.0}$ | $38.1_{\pm 0.0}$ | $51.4_{\pm 0.0}$ | $10.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (CSLS [25]) | $14.4_{\pm 0.1}$ | $37.5_{\pm 0.1}$ | $50.4_{\pm 0.1}$ | $10.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (IS [102]) | $12.3_{\pm 0.1}$ | $32.9_{\pm 0.1}$ | $45.0_{\pm 0.0}$ | $14.0_{\pm 0.0}$
MSR-VTT |  QB-Norm (DIS) | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
Overall |  |  $GM$ $(R@1)$ |  $GM$ $(R@5)$ |  $GM$ $(R@10)$ |  $GM$ $(MdR)$
Summary |  QB-Norm (GC [28]) | $15.1_{\pm 0.6}$ | $38.5_{\pm 0.5}$ | $51.6_{\pm 0.2}$ | $10.0_{\pm 0.0}$
Summary |  QB-Norm (CSLS [25]) | $15.2_{\pm 1.6}$ | $39.0_{\pm 2.8}$ | $51.8_{\pm 2.9}$ | $\mathbf{9.4}_{\pm 1.3}$
Summary |  QB-Norm (IS [102]) | $14.1_{\pm 2.8}$ | $36.8_{\pm 5.0}$ | $49.3_{\pm 5.5}$ | $10.9_{\pm 3.2}$
Summary |  QB-Norm (DIS) | $\mathbf{15.8}_{\pm 1.1}$ | $\mathbf{39.7}_{\pm 1.7}$ | $\mathbf{52.7}_{\pm 1.6}$ | $\mathbf{9.4}_{\pm 0.7}$

Table 2:  The influence of normalisation strategies across querybank source
distributions. Performance is reported on MSR-VTT full split [121], while
querybanks of 5,000 samples are sampled from the training sets of different
datasets. In the last block, we presented the overall performance reported as
geometric mean (GM) for each method. We observe that DIS provides the best
overall trade-off: it matches the high performance of IS and CSLS with in
domain and close domain querybanks, and is more robust on far domain and
adversarial querybanks.

Figure 4: Qualitative results. We illustrate a sample query for which QB-Norm
leads to the retrieval of the correct target video (whose frames are
highlighted with a dashed green line). For further examples and more detailed
analysis, see supplementary.

Hyperparameter sensitivity. The IS [25] and DIS normalisation strategies
require the user to select an additional hyperparameter (the inverse
temperature) that is absent from other methods. We evaluate the sensitivity of
DIS to this hyperparameter in Fig. 3 (right), where we find that a value of 20
works best. In practice, we found that this value worked well consistently
across datasets, and therefore we use it for all remaining experiments (with
the exception of CLIP2Video [35] where we used $1.99^{-1}$, since the
similarities are already scaled by the method). DIS normalisation introduces
an additional hyperparameter (the $k$ maximum selection value described in
Sec. 3.4). We observed that choosing $k=1$ offers a good trade-off between
good performance and robustness, so we simply use this value for all
experiments.

Does QB-Norm mitigate hubness? The core motivation for QB-Norm is that
existing cross modal retrieval methods are heavily affected by hubness (Fig.
2). To investigate whether this has been addressed by QB-Norm, we report the
skewness of the k-occurrences distribution111A detailed description of this
calculation is given in the supplementary. (which indicates the hubness of an
embedding space [93]) for four datasets in Tab. 3 using a querybank consisting
from all the samples from the training set. We observe that in each case,
skewness (and hence hubness) is significantly reduced.

MSR-VTT | DiDeMo | LSMDC | MSCoCo
---|---|---|---
Before | After | Before | After | Before | After | Before | After
0.939 | 0.509 | 1.21 | 0.39 | 0.715 | 0.321 | 0.56 | 0.16

Table 3: Impact of QB-Norm on hubness on various datasets. We observe that QB-
Norm consistently reduces hubness (as measured by skewness in the k-occurences
distribution).

###  4.3 Comparison with other methods

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
CE[73] | $21.7_{\pm 1.3}$ | $51.8_{\pm 0.5}$ | $65.7_{\pm 0.6}$ | $5.0_{\pm 0.0}$
MMT[41] | $24.6_{\pm 0.4}$ | $54.0_{\pm 0.2}$ | $67.1_{\pm 0.5}$ | $4.0_{\pm 0.0}$
SSB[89] | $27.4$ | $56.3$ | $67.7$ | $3.0$
Frozen[6] | $31.0$ | $59.5$ | $70.5$ | $3.0$
CLIP4Clip [76] | $44.5$ | $71.4$ | $81.6$ | $\mathbf{2.0}$
TT-CE+[27] | $29.6_{\pm 0.3}$ | $61.6_{\pm 0.5}$ | $74.2_{\pm 0.3}$ | $3.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $33.3_{\pm 0.7}$ | $63.7_{\pm 0.1}$ | $76.3_{\pm 0.4}$ | $3.0_{\pm 0.0}$
CLIP2Video[35] | $45.6$ | $72.5$ | $81.7$ | $\mathbf{2.0}$
CLIP2Video (+QB-Norm) | $\mathbf{47.2}$ | $\mathbf{73.0}$ | $\mathbf{83.0}$ | $\mathbf{2.0}$

Table 4: MSR-VTT 1k-A split: Comparison to state of the art.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
VSE++[33] | $15.4$ | $39.6$ | $53.0$ | $9.0$
MoEE[79] | $21.1_{\pm 0.2}$ | $52.0_{\pm 0.7}$ | $66.7_{\pm 0.2}$ | $5.0_{\pm 0.0}$
CE[73] | $21.5_{\pm 0.5}$ | $52.3_{\pm 0.8}$ | $67.5_{\pm 0.7}$ | $5.0_{\pm 0.0}$
Frozen[6] | $33.7$ | $64.7$ | $76.3$ | $3.0$
CLIP4Clip [76] | $46.2$ | $76.1$ | $84.6$ | $\mathbf{2.0}$
TT-CE+[27] | $25.4_{\pm 0.3}$ | $56.9_{\pm 0.4}$ | $71.3_{\pm 0.2}$ | $4.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $26.6_{\pm 0.9}$ | $58.5_{\pm 1.3}$ | $71.8_{\pm 1.1}$ | $4.0_{\pm 0.0}$
CLIP2Video[35] | $47.0$ | $76.8$ | $85.9$ | $\mathbf{2.0}$
CLIP2Video (+QB-Norm) | $\mathbf{47.6}$ | $\mathbf{77.6}$ | $\mathbf{86.1}$ | $\mathbf{2.0}$

Table 5: MSVD: Comparison to state of the art methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $16.1_{\pm 1.0}$ | $41.2_{\pm 1.6}$ | $55.2_{\pm 1.6}$ | $8.3_{\pm 0.5}$
CE[73] | $17.1_{\pm 0.9}$ | $41.9_{\pm 0.2}$ | $56.0_{\pm 0.5}$ | $8.0_{\pm 0.0}$
TT-CE | $21.0_{\pm 0.6}$ | $47.5_{\pm 0.9}$ | $61.9_{\pm 0.5}$ | $6.0_{\pm 0.0}$
Frozen[6] | $31.0$ | $59.8$ | $72.4$ | $3.0$
CLIP4Clip [76] | $\mathbf{43.4}$ | $\mathbf{70.2}$ | $\mathbf{80.6}$ | $\mathbf{2.0}$
CE+[27] | $18.2_{\pm 0.2}$ | $43.9_{\pm 0.9}$ | $57.1_{\pm 0.8}$ | $7.9_{\pm 0.1}$
CE+ (+QB-Norm) | $20.7_{\pm 0.6}$ | $46.6_{\pm 0.2}$ | $59.8_{\pm 0.2}$ | $6.3_{\pm 0.5}$
TT-CE+[27] | $21.6_{\pm 0.7}$ | $48.6_{\pm 0.4}$ | $62.9_{\pm 0.6}$ | $6.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $24.2_{\pm 0.7}$ | $50.8_{\pm 0.7}$ | $64.4_{\pm 0.1}$ | $5.3_{\pm 0.5}$

Table 6: DiDeMo: Comparison to state of the art methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $12.1_{\pm 0.7}$ | $29.4_{\pm 0.8}$ | $37.7_{\pm 0.2}$ | $23.2_{\pm 0.8}$
CE[73] | $12.4_{\pm 0.7}$ | $28.5_{\pm 0.8}$ | $37.9_{\pm 0.6}$ | $21.7_{\pm 0.6}$
MMT[41] | $13.2_{\pm 0.4}$ | $29.2_{\pm 0.8}$ | $38.8_{\pm 0.9}$ | $21.0_{\pm 1.4}$
Frozen[6] | $15.0$ | $30.8$ | $39.8$ | $20.0$
CLIP4Clip [76] | $\mathbf{21.6}$ | $\mathbf{41.8}$ | $\mathbf{49.8}$ | $\mathbf{11.0}$
CE+[27] | $14.9_{\pm 0.6}$ | $33.7_{\pm 0.2}$ | $44.1_{\pm 0.6}$ | $15.3_{\pm 0.5}$
CE+ (QB-Norm) | $16.4_{\pm 0.8}$ | $34.8_{\pm 0.4}$ | $44.9_{\pm 0.9}$ | $14.5_{\pm 0.4}$
TT-CE+[27] | $17.2_{\pm 0.4}$ | $36.5_{\pm 0.6}$ | $46.3_{\pm 0.3}$ | $13.7_{\pm 0.5}$
TT-CE+ (QB-Norm) | $17.8_{\pm 0.4}$ | $37.7_{\pm 0.5}$ | $47.6_{\pm 0.6}$ | $12.7_{\pm 0.5}$

Table 7: LSMDC: Comparison to state of the art methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
HGR[19] | $35.1$ | $73.5$ | $83.5$ | $2.0$
SSB[89] | $44.6$ | $81.8$ | $89.5$ | $\mathbf{1.0}$
CE[73] | $47.9_{\pm 0.1}$ | $84.2_{\pm 0.1}$ | $91.3_{\pm 0.1}$ | $2.0_{\pm 0.0}$
Fast and Slow [78] | $50.5$ | $84.6$ | $91.7$ | -
TT-CE+[27] | $53.2_{\pm 0.2}$ | $87.4_{\pm 0.1}$ | $93.3_{\pm 0.0}$ | $\mathbf{1.0}_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $54.8_{\pm 0.1}$ | $88.2_{\pm 0.1}$ | $\mathbf{93.8}_{\pm 0.1}$ | $\mathbf{1.0}_{\pm 0.0}$
CLIP2Video[35] | $57.4$ | $87.9$ | $93.6$ | $\mathbf{1.0}$
CLIP2Video (+QB-Norm) | $\mathbf{58.8}$ | $\mathbf{88.3}$ | $\mathbf{93.8}$ | $\mathbf{1.0}$

Table 8: VaTeX: Comparison to state of the art methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $11.6_{\pm 1.3}$ | $30.2_{\pm 3.0}$ | $43.2_{\pm 3.1}$ | $14.2_{\pm 1.6}$
CE[73] | $13.9_{\pm 0.8}$ | $37.6_{\pm 1.2}$ | $48.3_{\pm 1.4}$ | $11.3_{\pm 0.6}$
CE+[27] | $13.2_{\pm 2.0}$ | $37.1_{\pm 2.9}$ | $50.5_{\pm 1.9}$ | $10.3_{\pm 1.2}$
CE+ (+QB-Norm) | $14.1_{\pm 1.8}$ | $\mathbf{38.6}_{\pm 1.3}$ | $51.1_{\pm 1.6}$ | $10.0_{\pm 0.8}$
TT-CE+[27] | $14.4_{\pm 0.5}$ | $37.7_{\pm 1.7}$ | $50.9_{\pm 1.6}$ | $\mathbf{9.8}_{\pm 1.0}$
TT-CE+ (+QB-Norm) | $\mathbf{15.1}_{\pm 1.6}$ | $38.3_{\pm 2.4}$ | $\mathbf{51.2}_{\pm 2.8}$ | $10.3_{\pm 1.7}$

Table 9: QuerYD: Comparison to state of the art methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
CLIP [91] | $37.8$ | $62.4$ | $72.2$ | -
VSE++ [33] | $43.9$ | $59.4$ | $72.4$ | -
OSCAR [69] | $54.0$ | $80.8$ | $88.5$ | -
VinVL [130] | $58.8$ | $83.5$ | $90.3$ | -
Fast and Slow [78] | $\mathbf{68.2}$ | $\mathbf{89.7}$ | $\mathbf{93.9}$ | -
CLIP[91]‡ | $30.3$ | $56.1$ | $67.1$ | $4.0$
CLIP‡ (+QB-Norm) | $34.8$ | $59.9$ | $70.4$ | $3.0$
MMT-OSCAR [42] | $52.2$ | $80.2$ | $88.0$ | $\mathbf{1.0}$
MMT-Oscar (+QB-Norm) | $53.9$ | $80.5$ | $88.1$ | $\mathbf{1.0}$

Table 10: Text-image retrieval - MSCoCo 5k split: Comparison to other methods.
‡ represents the results obtained using the official CLIP[91] ViT-B/32 model.

Model | $R@1\uparrow$ | $R@2\uparrow$ | $R@4\uparrow$ | $R@8\uparrow$
---|---|---|---|---
MS [113] | $57.4$ | $69.8$ | $80.0$ | -
EPS [68] | $64.4$ | $75.2$ | $\mathbf{84.3}$ | -
RDML[97] | $64.4$ | $75.3$ | $83.4$ | $90.0$
RDML[97] (+QB-Norm) | $\mathbf{64.8}$ | $\mathbf{75.6}$ | $84.0$ | $\mathbf{90.4}$

Table 11: Image to Image retrieval - CUB 200: Comparison to other methods.

Model | $R@1\uparrow$ | $R@10\uparrow$ | $R@100\uparrow$ | $R@1000\uparrow$
---|---|---|---|---
XBM [115] | $\mathbf{80.6}$ | $\mathbf{91.6}$ | $96.2$ | $98.7$
Smooth-AP[11] | $80.1$ | $91.5$ | $\mathbf{96.6}$ | $\mathbf{99.0}$
RDML[97] | $77.8$ | $89.5$ | $95.4$ | $98.4$
RDML[97] (+QB-Norm) | $78.1$ | $89.8$ | $95.6$ | $98.5$

Table 12: Image to Image retrieval - Online Products: Comparison to other
methods.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
AR [86]-MoEE | $22.5_{\pm 0.3}$ | $54.4_{\pm 0.6}$ | $69.5_{\pm 0.9}$ | $5.0_{\pm 0.0}$
AR [86]-CE | $23.1_{\pm 0.6}$ | $55.1_{\pm 0.7}$ | $70.7_{\pm 0.6}$ | $4.7_{\pm 0.5}$
AR [86]-CE (+QB-Norm) | $\mathbf{23.9}_{\pm 0.2}$ | $\mathbf{57.1}_{\pm 0.3}$ | $\mathbf{71.6}_{\pm 0.4}$ | $\mathbf{4.0}_{\pm 0.0}$

Table 13: Text-audio retrieval - AudioCaps: Comparison to other methods.

In this section, we conduct an extensive study to evaluate the effectiveness
and generality of QB-Norm on several well established benchmarks.

The influence of applying QB-Norm to cross modal embeddings for text-video
retrieval are reported in Tab. 4, 5, 17, 18, 8, 9. We provide further text-
video retrieval results in the supplementary. In Tab. 10 we report results for
the text-image retrieval task, while in Tab. 11, 12, we report results for the
image-image retrieval task. Finally, in Tab. 13, we report results for text-
audio retrieval. In Fig. 8 we also show a qualitative example. For the base
models that provide weights for different seeds we report mean and standard
deviation of QB-Norm applied on each seed. In each case, QB-Norm brings a
significant improvement over all tested methods, benchmarks and tasks. We show
in bold the best performing method.

##  5 Limitations and societal impact

Limitations All the normalisation techniques used with QB-Norm incur
additional pre-computation costs. The proposed normalisation technique, DIS,
adds a further small additional computational cost over other normalisation
approaches. For a full discussion on complexity, please refer to the
supplementary. We also show in Tab. 2 that adversarial querybank selection and
significant domain gaps can reduce the benefits of Querybank Normalisation.

Societal impact Cross modal retrieval is a powerful tool with both positive
applications and risks of harm. Cross modal search enables efficient content
discovery for researchers, musicians, artists and consumers. However, this
capability also lends itself to tools of political oppression: for example, it
could enable efficient searching of social media content to discover signs of
political dissent.

##  6 Conclusions

In this work, we introduced the Querybank Normalisation framework for hubness
mitigation. We also proposed the Dynamic Inverted Softmax for robust
similarity normalisation. We demonstrated its broad applicability across a
range of tasks, models and benchmarks.
Acknowledgements. This work was supported by Adobe, Google and Zhejiang Lab
(NO. 2022NB0AB05), and a G-Research travel grant. The authors thank Bruno
Korbar for useful suggestions, Andrew Zisserman and Jenny Hu for their
support, and Adam Berenzweig for kindly sharing a copy of his earlier work.
S.A. would like to acknowledge Z. Novak, N. Novak and S. Carlson in supporting
his contribution.

## References

  * [1] Lisa Anne Hendricks, Oliver Wang, Eli Shechtman, Josef Sivic, Trevor Darrell, and Bryan Russell.  Localizing moments in video with natural language.  In Proceedings of the IEEE international conference on computer vision, pages 5803–5812, 2017.
  * [2] Relja Arandjelovic and Andrew Zisserman.  Look, listen and learn.  In Proceedings of the IEEE International Conference on Computer Vision, pages 609–617, 2017.
  * [3] Relja Arandjelović and Andrew Zisserman.  Objects that sound.  In ECCV, 2018.
  * [4] Yusuf Aytar, Mubarak Shah, and Jiebo Luo.  Utilizing semantic word similarity measures for video retrieval.  In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2008.
  * [5] Yusuf Aytar, Carl Vondrick, and Antonio Torralba.  See, hear, and read: Deep aligned representations.  arXiv preprint arXiv:1706.00932, 2017.
  * [6] Max Bain, Arsha Nagrani, Gül Varol, and Andrew Zisserman.  Frozen in time: A joint video and image encoder for end-to-end retrieval.  2021\.
  * [7] Richard E. Bellman.  Adaptive control processes: A guided tour.  1961\.
  * [8] Jon Louis Bentley.  Multidimensional binary search trees used for associative searching.  Commun. ACM, 18:509–517, 1975.
  * [9] Adam Berenzweig.  Anchors and hubs in audio-based music similarity.  PhD thesis, Columbia University, NY, USA, 2007.
  * [10] David M Blei and Michael I Jordan.  Modeling annotated data.  In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 127–134, 2003.
  * [11] Andrew Brown, Weidi Xie, Vicky Kalogeiton, and Andrew Zisserman.  Smooth-ap: Smoothing the path towards large-scale image retrieval.  In European Conference on Computer Vision, pages 677–694. Springer, 2020.
  * [12] Vicki Bruce and Andy Young.  Understanding face recognition.  British journal of psychology, 77(3):305–327, 1986.
  * [13] Adrian Bulat, Enrique Sánchez-Lozano, and Georgios Tzimiropoulos.  Improving memory banks for unsupervised learning with large mini-batch, consistency and hard negative mining.  In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1695–1699. IEEE, 2021.
  * [14] Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem, and Juan Carlos Niebles.  Activitynet: A large-scale video benchmark for human activity understanding.  In Proceedings of the ieee conference on computer vision and pattern recognition, pages 961–970, 2015.
  * [15] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6299–6308, 2017.
  * [16] David L. Chen and William B. Dolan.  Collecting highly parallel data for paraphrase evaluation.  In ACL, 2011.
  * [17] David L Chen and William B Dolan.  Collecting highly parallel data for paraphrase evaluation.  In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 190–200. Association for Computational Linguistics, 2011.
  * [18] Shizhe Chen, Yida Zhao, and Qin Jin.  Team ruc ai.m3: Technical report in video pentathlon challenge 2020.
  * [19] Shizhe Chen, Yida Zhao, Qin Jin, and Qi Wu.  Fine-grained video-text retrieval with hierarchical graph reasoning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10638–10647, 2020.
  * [20] Xinlei Chen, Hao Fang, Tsung-Yi Lin, Ramakrishna Vedantam, Saurabh Gupta, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft coco captions: Data collection and evaluation server.  ArXiv, abs/1504.00325, 2015.
  * [21] Ali Cheraghian, Shafin Rahman, Dylan Campbell, and Lars Petersson.  Mitigating the hubness problem for zero-shot learning of 3d objects.  In BMVC, 2019.
  * [22] Sumit Chopra, Raia Hadsell, and Yann LeCun.  Learning a similarity metric discriminatively, with application to face verification.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 1, pages 539–546. IEEE, 2005.
  * [23] Ondřej Chum, Andrej Mikulík, Michal Perdoch, and Jiri Matas.  Total recall ii: Query expansion revisited.  CVPR 2011, pages 889–896, 2011.
  * [24] Ondřej Chum, James Philbin, Josef Sivic, Michael Isard, and Andrew Zisserman.  Total recall: Automatic query expansion with a generative feature model for object retrieval.  2007 IEEE 11th International Conference on Computer Vision, pages 1–8, 2007.
  * [25] Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou.  Word translation without parallel data.  In International Conference on Learning Representations, 2018.
  * [26] Marcella Cornia, Matteo Stefanini, Lorenzo Baraldi, and Rita Cucchiara.  Meshed-memory transformer for image captioning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10578–10587, 2020.
  * [27] Ioana Croitoru, Simion-Vlad Bogolin, Marius Leordeanu, Hailin Jin, Andrew Zisserman, Samuel Albanie, and Yang Liu.  Teachtext: Crossmodal generalized distillation for text-video retrieval.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11583–11593, 2021.
  * [28] Georgiana Dinu, Angeliki Lazaridou, and Marco Baroni.  Improving zero-shot learning by mitigating the hubness problem.  arXiv preprint arXiv:1412.6568, 2014.
  * [29] Jianfeng Dong, Xirong Li, and Cees GM Snoek.  Word2visualvec: Image and video to sentence matching by visual feature prediction.  arXiv preprint arXiv:1604.06838, 2016.
  * [30] Jianfeng Dong, Xirong Li, Chaoxi Xu, Shouling Ji, and Xun Wang.  Dual dense encoding for zero-example video retrieval.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
  * [31] Wei Dong, Moses Charikar, and K. Li.  Efficient k-nearest neighbor graph construction for generic similarity measures.  In WWW, 2011.
  * [32] Pinar Duygulu, Kobus Barnard, Joao FG de Freitas, and David A Forsyth.  Object recognition as machine translation: Learning a lexicon for a fixed image vocabulary.  In European conference on computer vision, pages 97–112. Springer, 2002.
  * [33] Fartash Faghri, David J Fleet, Jamie Ryan Kiros, and Sanja Fidler.  Vse++: Improving visual-semantic embeddings with hard negatives.  arXiv preprint arXiv:1707.05612, 2017.
  * [34] Fartash Faghri, David J. Fleet, Jamie Ryan Kiros, and Sanja Fidler.  Vse++: Improving visual-semantic embeddings with hard negatives.  In BMVC, 2018.
  * [35] Han Fang, Pengfei Xiong, Luhui Xu, and Yu Chen.  Clip2video: Mastering video-text retrieval via image clip.  arXiv preprint arXiv:2106.11097, 2021.
  * [36] Roman Feldbauer and Arthur Flexer.  A comprehensive empirical comparison of hubness reduction in high-dimensional spaces.  Knowledge and Information Systems, 59(1):137–166, 2019.
  * [37] Roman Feldbauer, Maximilian Leodolter, Claudia Plant, and Arthur Flexer.  Fast approximate hubness reduction for large high-dimensional data.  2018 IEEE International Conference on Big Knowledge (ICBK), pages 358–367, 2018.
  * [38] Roman Feldbauer, Thomas Rattei, and Arthur Flexer.  scikit-hubness: Hubness reduction and approximate neighbor search.  Journal of Open Source Software, 5(45):1957, 2020.
  * [39] Damien François, Vincent Wertz, and Michel Verleysen.  The concentration of fractional distances.  IEEE Transactions on Knowledge and Data Engineering, 19(7):873–886, 2007.
  * [40] Andrea Frome, Greg Corrado, Jonathon Shlens, Samy Bengio, Jeffrey Dean, Marc’Aurelio Ranzato, and Tomas Mikolov.  Devise: A deep visual-semantic embedding model.  2013\.
  * [41] Valentin Gabeur, Chen Sun, Karteek Alahari, and Cordelia Schmid.  Multi-modal transformer for video retrieval.  European Conference on Computer Vision, 2020.
  * [42] Gregor Geigle, Jonas Pfeiffer, Nils Reimers, Ivan Vulić, and Iryna Gurevych.  Retrieve fast, rerank smart: Cooperative and joint approaches for improved cross-modal retrieval.  arXiv preprint arXiv:2103.11920, 2021.
  * [43] Deepti Ghadiyaram, Du Tran, and Dhruv Mahajan.  Large-scale weakly-supervised pre-training for video action recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 12046–12055, 2019.
  * [44] Yunchao Gong and Svetlana Lazebnik.  Iterative quantization: A procrustean approach to learning binary codes.  CVPR 2011, pages 817–824, 2011.
  * [45] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  ArXiv, abs/1410.5401, 2014.
  * [46] Rasmus Boll Greve, Emil Juul Jacobsen, and Sebastian Risi.  Evolving neural turing machines for reward-based learning.  In Proceedings of the Genetic and Evolutionary Computation Conference 2016, pages 117–124, 2016.
  * [47] Kazuo Hara, Ikumi Suzuki, Masashi Shimbo, Kei Kobayashi, Kenji Fukumizu, and Milo _vs_. Radovanović.  Localized centering: Reducing hubness in large-sample data.  In AAAI, 2015.
  * [48] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick.  Momentum contrast for unsupervised visual representation learning.  2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9726–9735, 2020.
  * [49] Kaiming He, Fang Wen, and Jian Sun.  K-means hashing: An affinity-preserving quantization method for learning binary compact codes.  2013 IEEE Conference on Computer Vision and Pattern Recognition, pages 2938–2945, 2013.
  * [50] Lisa Anne Hendricks, Oliver Wang, Eli Shechtman, Josef Sivic, Trevor Darrell, and Bryan C. Russell.  Localizing moments in video with natural language.  2017 IEEE International Conference on Computer Vision (ICCV), pages 5804–5813, 2017.
  * [51] Shawn Hershey, Sourish Chaudhuri, Daniel P. W. Ellis, Jort F. Gemmeke, Aren Jansen, Channing Moore, Manoj Plakal, Devin Platt, Rif A. Saurous, Bryan Seybold, Malcolm Slaney, Ron Weiss, and Kevin Wilson.  Cnn architectures for large-scale audio classification.  In International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2017.
  * [52] Jie Hu, Li Shen, Samuel Albanie, Gang Sun, and Enhua Wu.  Squeeze-and-excitation networks.  IEEE transactions on pattern analysis and machine intelligence, 2019\.
  * [53] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [54] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In STOC ’98, 1998.
  * [55] Hervé Jégou, Matthijs Douze, and Cordelia Schmid.  Hamming embedding and weak geometric consistency for large scale image search.  In ECCV, 2008.
  * [56] Hervé Jégou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 33:117–128, 2011.
  * [57] Herve Jegou, Hedi Harzallah, and Cordelia Schmid.  A contextual dissimilarity measure for accurate and efficient image search.  In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2007.
  * [58] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  IEEE Transactions on Big Data, 2019.
  * [59] Armand Joulin, Piotr Bojanowski, Tomas Mikolov, Hervé Jégou, and Edouard Grave.  Loss in translation: Learning bilingual word mapping with a retrieval criterion.  In EMNLP, 2018.
  * [60] Lukasz Kaiser, Ofir Nachum, Aurko Roy, and Samy Bengio.  Learning to remember rare events.  ArXiv, abs/1703.03129, 2017.
  * [61] Andrej Karpathy and Li Fei-Fei.  Deep visual-semantic alignments for generating image descriptions.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39:664–676, 2017.
  * [62] Einat Kidron, Yoav Y Schechner, and Michael Elad.  Pixels that sound.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 1, pages 88–95. IEEE, 2005.
  * [63] Byeongchang Kim, Hyunwoo Kim, and Gunhee Kim.  Abstractive summarization of reddit posts with multi-level memory networks.  ArXiv, abs/1811.00783, 2019.
  * [64] Chris Dongjoo Kim, Byeongchang Kim, Hyunmin Lee, and Gunhee Kim.  Audiocaps: Generating captions for audios in the wild.  In NAACL, 2019.
  * [65] Ryan Kiros, Ruslan Salakhutdinov, and Richard S Zemel.  Unifying visual-semantic embeddings with multimodal neural language models.  arXiv preprint arXiv:1411.2539, 2014.
  * [66] Ranjay Krishna, Kenji Hata, Frederic Ren, Li Fei-Fei, and Juan Carlos Niebles.  Dense-captioning events in videos.  2017 IEEE International Conference on Computer Vision (ICCV), pages 706–715, 2017.
  * [67] Sangho Lee, Jinyoung Sung, Youngjae Yu, and Gunhee Kim.  A memory network approach for story-based temporal summarization of 360° videos.  2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1410–1419, 2018.
  * [68] Elad Levi, Tete Xiao, Xiaolong Wang, and Trevor Darrell.  Rethinking preventing class-collapsing in metric learning with margin-based losses.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10316–10325, 2021.
  * [69] Xiujun Li, Xi Yin, Chunyuan Li, Xiaowei Hu, Pengchuan Zhang, Lei Zhang, Lijuan Wang, Houdong Hu, Li Dong, Furu Wei, Yejin Choi, and Jianfeng Gao.  Oscar: Object-semantics aligned pre-training for vision-language tasks.  ECCV 2020, 2020.
  * [70] Fangyu Liu and Rongtian Ye.  A strong and robust baseline for text-image matching.  arXiv preprint arXiv:1906.01205, 2019.
  * [71] Fangyu Liu, Rongtian Ye, Xun Wang, and Shuaipeng Li.  Hal: Improved text-image matching by mitigating visual semantic hubs.  ArXiv, abs/1911.10097, 2020.
  * [72] Qun Liu and Supratik Mukhopadhyay.  Unsupervised learning using pretrained cnn and associative memory bank.  In 2018 International Joint Conference on Neural Networks (IJCNN), pages 01–08. IEEE, 2018.
  * [73] Yang Liu, Samuel Albanie, Arsha Nagrani, and Andrew Zisserman.  Use what you have: Video retrieval using representations from collaborative experts.  arXiv preprint arXiv:1907.13487, 2019.
  * [74] Yang Liu, Qingchao Chen, and Samuel Albanie.  Adaptive cross-modal prototypes for cross-domain visual-language retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14954–14964, 2021.
  * [75] Thomas Low, Christian Borgelt, Sebastian Stober, and Andreas Nürnberger.  The hubness phenomenon: Fact or artifact?  In Towards Advanced Data Analysis by Combining Soft Computing and Statistics, pages 267–278. Springer, 2013.
  * [76] Huaishao Luo, Lei Ji, Ming Zhong, Yang Chen, Wen Lei, Nan Duan, and Tianrui Li.  Clip4clip: An empirical study of clip for end to end video clip retrieval.  arXiv preprint arXiv:2104.08860, 2021.
  * [77] Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten.  Exploring the limits of weakly supervised pretraining.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 181–196, 2018.
  * [78] Antoine Miech, Jean-Baptiste Alayrac, Ivan Laptev, Josef Sivic, and Andrew Zisserman.  Thinking fast and slow: Efficient text-to-visual retrieval with transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9826–9836, 2021.
  * [79] Antoine Miech, Ivan Laptev, and Josef Sivic.  Learning a text-video embedding from incomplete and heterogeneous data.  arXiv preprint arXiv:1804.02516, 2018.
  * [80] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2630–2640, 2019.
  * [81] Niluthpol Chowdhury Mithun, Juncheng Li, Florian Metze, and Amit K Roy-Chowdhury.  Learning joint embedding with multimodal cues for cross-modal video-text retrieval.  In Proceedings of the 2018 ACM on International Conference on Multimedia Retrieval, pages 19–27, 2018.
  * [82] Niluthpol Chowdhury Mithun, Rameswar Panda, Evangelos E. Papalexakis, and Amit K. Roy-Chowdhury.  Webly supervised joint embedding for cross-modal image-text retrieval.  Proceedings of the 26th ACM international conference on Multimedia, 2018.
  * [83] Jonathan Munro, Michael Wray, Diane Larlus, Gabriela Csurka, and Dima Damen.  Domain adaptation in multi-view embedding for cross-modal video retrieval.  arXiv preprint arXiv:2110.12812, 2021.
  * [84] Arsha Nagrani, Samuel Albanie, and Andrew Zisserman.  Learnable pins: Cross-modal embeddings for person identity.  In ECCV, 2018.
  * [85] Andreea-Maria Oncescu, Joao F. Henriques, Yang Liu, Andrew Zisserman Zisserman, and Samuel Albanie.  Queryd: a video dataset with high-quality textual and audio narrations.  arXiv preprint arXiv:2011.11071, 2020.
  * [86] Andreea-Maria Oncescu, A Koepke, João F Henriques, Zeynep Akata, and Samuel Albanie.  Audio retrieval with natural language queries.  Interspeech, 2021.
  * [87] Andrew Owens, Jiajun Wu, Josh H McDermott, William T Freeman, and Antonio Torralba.  Ambient sound provides supervision for visual learning.  In European conference on computer vision, pages 801–816. Springer, 2016.
  * [88] Cesc Chunseong Park, Byeongchang Kim, and Gunhee Kim.  Attend to you: Personalized image captioning with context sequence memory networks.  2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6432–6440, 2017.
  * [89] Mandela Patrick, Po-Yao Huang, Yuki Asano, Florian Metze, Alexander Hauptmann, João Henriques, and Andrea Vedaldi.  Support-set bottlenecks for video-text representation learning.  arXiv preprint arXiv:2010.02824, 2020.
  * [90] James Philbin, Ondřej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman.  Object retrieval with large vocabularies and fast spatial matching.  2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, 2007.
  * [91] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  arXiv preprint arXiv:2103.00020, 2021.
  * [92] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  OpenAI Blog, 1(8):9, 2019.
  * [93] Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović.  Hubs in space: Popular nearest neighbors in high-dimensional data.  Journal of Machine Learning Research, 11(Sep):2487–2531, 2010.
  * [94] Nikhil Rasiwasia, Jose Costa Pereira, Emanuele Coviello, Gabriel Doyle, Gert RG Lanckriet, Roger Levy, and Nuno Vasconcelos.  A new approach to cross-modal multimedia retrieval.  In Proceedings of the 18th ACM international conference on Multimedia, pages 251–260, 2010.
  * [95] Anna Rohrbach, Marcus Rohrbach, Niket Tandon, and Bernt Schiele.  A dataset for movie description.  2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3202–3212, 2015.
  * [96] Anna Rohrbach, Atousa Torabi, Marcus Rohrbach, Niket Tandon, Christopher Pal, Hugo Larochelle, Aaron Courville, and Bernt Schiele.  Movie description.  International Journal of Computer Vision, 123(1):94–120, 2017.
  * [97] Karsten Roth, Timo Milbich, Samarth Sinha, Prateek Gupta, Bjorn Ommer, and Joseph Paul Cohen.  Revisiting training strategies and generalization performance in deep metric learning.  In International Conference on Machine Learning, pages 8242–8252. PMLR, 2020.
  * [98] Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.  Meta-learning with memory-augmented neural networks.  In International conference on machine learning, pages 1842–1850. PMLR, 2016.
  * [99] Dominik Schnitzer, Arthur Flexer, Markus Schedl, and Gerhard Widmer.  Local and global scaling reduce hubs in space.  Journal of Machine Learning Research, 13(10), 2012.
  * [100] Yutaro Shigeto, Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, and Yuji Matsumoto.  Ridge regression, hubness, and zero-shot learning.  In Joint European conference on machine learning and knowledge discovery in databases, pages 135–151. Springer, 2015.
  * [101] Malcolm Slaney.  Semantic-audio retrieval.  In 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 4, pages IV–4108. IEEE, 2002.
  * [102] Samuel L Smith, David HP Turban, Steven Hamblin, and Nils Y Hammerla.  Offline bilingual word vectors, orthogonal transformations and the inverted softmax.  arXiv preprint arXiv:1702.03859, 2017.
  * [103] Richard Socher and Li Fei-Fei.  Connecting modalities: Semi-supervised segmentation and annotation of images using unaligned text corpora.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 966–973. IEEE, 2010.
  * [104] Richard Socher, Andrej Karpathy, Quoc V. Le, Christopher D. Manning, and A. Ng.  Grounded compositional semantics for finding and describing images with sentences.  Transactions of the Association for Computational Linguistics, 2:207–218, 2014.
  * [105] Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese.  Deep metric learning via lifted structured feature embedding.  2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4004–4012, 2016.
  * [106] Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, Yuji Matsumoto, and Marco Saerens.  Investigating the effectiveness of laplacian-based kernels in hub reduction.  In AAAI, 2012.
  * [107] Ikumi Suzuki, Kazuo Hara, Masashi Shimbo, Marco Saerens, and Kenji Fukumizu.  Centering similarity measures to reduce hubs.  In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 613–623, 2013.
  * [108] Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li.  Yfcc100m: The new data in multimedia research.  Communications of the ACM, 59(2):64–73, 2016.
  * [109] Du Tran, Heng Wang, Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri.  A closer look at spatiotemporal convolutions for action recognition.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 6450–6459, 2018.
  * [110] Subhashini Venugopalan, Marcus Rohrbach, Jeffrey Donahue, Raymond Mooney, Trevor Darrell, and Kate Saenko.  Sequence to sequence-video to text.  In Proceedings of the IEEE international conference on computer vision, pages 4534–4542, 2015.
  * [111] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge J. Belongie.  The caltech-ucsd birds-200-2011 dataset.  2011\.
  * [112] Liwei Wang, Yin Li, and Svetlana Lazebnik.  Learning deep structure-preserving image-text embeddings.  2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5005–5013, 2016.
  * [113] Xun Wang, Xintong Han, Weilin Huang, Dengke Dong, and Matthew R Scott.  Multi-similarity loss with general pair weighting for deep metric learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5022–5030, 2019.
  * [114] Xin Wang, Jiawei Wu, Junkun Chen, Lei Li, Yuan-Fang Wang, and William Yang Wang.  Vatex: A large-scale, high-quality multilingual dataset for video-and-language research.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4581–4591, 2019.
  * [115] Xun Wang, Haozhi Zhang, Weilin Huang, and Matthew R Scott.  Cross-batch memory for embedding learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6388–6397, 2020.
  * [116] Xin Eric Wang, Jiawei Wu, Junkun Chen, Lei Li, Yuan fang Wang, and William Yang Wang.  Vatex: A large-scale, high-quality multilingual dataset for video-and-language research.  2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 4580–4590, 2019.
  * [117] Jason Weston, Samy Bengio, and Nicolas Usunier.  Wsabie: Scaling up to large vocabulary image annotation.  In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
  * [118] Michael Wray, Diane Larlus, Gabriela Csurka, and Dima Damen.  Fine-grained action retrieval through multiple parts-of-speech embeddings.  In Proceedings of the IEEE International Conference on Computer Vision, pages 450–459, 2019.
  * [119] Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492–1500, 2017.
  * [120] Chunpu Xu, Yu Li, Chengming Li, Xiang Ao, Min Yang, and Jinwen Tian.  Interactive key-value memory-augmented attention for image paragraph captioning.  In Proceedings of the 28th International Conference on Computational Linguistics, pages 3132–3142, 2020.
  * [121] Jun Xu, Tao Mei, Ting Yao, and Yong Rui.  Msr-vtt: A large video description dataset for bridging video and language.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5288–5296, 2016.
  * [122] Ran Xu, Caiming Xiong, Wei Chen, and Jason J. Corso.  Jointly modeling deep video and compositional text to bridge vision and language in a unified framework.  In AAAI, 2015.
  * [123] Ran Xu, Caiming Xiong, Wei Chen, and Jason J Corso.  Jointly modeling deep video and compositional text to bridge vision and language in a unified framework.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.
  * [124] Seungjoo Yoo, Hyojin Bahng, Sunghyo Chung, Junsoo Lee, Jaehyuk Chang, and Jaegul Choo.  Coloring with limited data: Few-shot colorization via memory augmented networks.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11275–11284, 2019.
  * [125] Youngjae Yu, Jongseok Kim, and Gunhee Kim.  A joint sequence fusion model for video question answering and retrieval.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 471–487, 2018.
  * [126] Wojciech Zaremba and Ilya Sutskever.  Reinforcement learning neural turing machines-revised.  arXiv preprint arXiv:1505.00521, 2015.
  * [127] Lihi Zelnik-Manor and Pietro Perona.  Self-tuning spectral clustering.  In NIPS, 2004.
  * [128] Bowen Zhang, Hexiang Hu, and Fei Sha.  Cross-modal and hierarchical modeling of video and text.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 374–390, 2018.
  * [129] Li Zhang, Tao Xiang, and Shaogang Gong.  Learning a deep embedding model for zero-shot learning.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2021–2030, 2017.
  * [130] Pengchuan Zhang, Xiujun Li, Xiaowei Hu, Jianwei Yang, Lei Zhang, Lijuan Wang, Yejin Choi, and Jianfeng Gao.  Vinvl: Making visual representations matter in vision-language models.  CVPR 2021, 2021.
  * [131] Hang Zhao, Chuang Gan, Andrew Rouditchenko, Carl Vondrick, Josh McDermott, and Antonio Torralba.  The sound of pixels.  In Proceedings of the European conference on computer vision (ECCV), pages 570–586, 2018.
  * [132] Yida Zhao, Yuqing Song, Shizhe Chen, and Qin Jin.  Ruc_aim3 at trecvid 2020: Ad-hoc video search & video to text description.  In TRECVID, 2020.
  * [133] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba.  Places: A 10 million image database for scene recognition.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017\.

Appendix

In this appendix, we provide additional information and ablation studies
relating to QB-Norm. We begin by providing more details about the datasets
used for each task (Sec. A). We then provide ablation studies that
investigate: (1) The influence of the $k$ hyperparameter on the proposed DIS
normalisation scheme (Sec. B); (2) Whether effective querybanks can also be
constructed from the training set using IS normalisation, rather than DIS
normalisation (Sec. C); (3) How embedding dimensionality influences the
effectiveness of QB-Norm (Sec. D). Next, we present comparisons on additional
datasets for the text-video retrieval task (Sec. E). In Sec. F we discuss the
complexity of each normalisation technique. In Sec. G we present a comparison
with CENT [107] normalisation. Then, we provide details on the skewness metric
reported in the submission (Sec. H), offer a more complete set of metrics
across ablations (Sec. I) and give more details about the text and video
experts used in this work (Sec. J). Finally, we report metrics indicating how
QB-Norm performs on video-text retrieval (Sec. K) and provide some additional
qualitative results (Sec. L).

##  Appendix A Dataset details

In this section, we describe the splits and datasets employed for all tasks
considered in this work.

###  A.1 Text-video retrieval

For the task of text-video retrieval we test our approach on seven current
benchmarks.

MSR-VTT [121] contains around 10k videos, each having 20 captions. For the
task of text-video retrieval, we follow prior works [73, 27] and we report
results on the official split (full) which contains 2,990 videos for testing
and 497 for validation. Since a number of recent works [73, 41, 89, 27] also
report results on the 1k-A split, we compare against these method on this
split as well. The 1k-A split contains 1,000 videos for testing and around
9,000 for training. We use the same videos and captions as defined in [73]
which are used by other works [125, 41, 89] for evaluation. We report the
results using models trained for 100 epochs.

MSVD [17] has 1,970 videos and around 80k captions. We report results on the
standard split using in prior works [110, 123, 73, 27] which consists of 1,200
videos for training, 100 for validation and 670 for testing.

DiDeMo [1] has 10,464 videos. They are collected from a large-scale creative
commons collection [108] and are varied in content (concerts, sports, pets
etc.). For each video, there are 3-5 pairs of descriptions. For the task of
text-video retrieval, we use the paragraph video retrieval protocol as defined
in prior works [128, 73, 27]. This means that we the split consisting of 8,392
for training, 1,065 validation and 1,004 test videos.

LSMDC [96] contains 118,081 short video clips extracted from 202 movies. Each
clip has a textual description which consist in a caption which is extracted
either from the movie script or transcribed from descriptive video services
(DVS) for the visually impaired. We use the official splits as defined in the
Large Scale Movie Description Challenge (LSMDC). The testing split contains
1,000 videos.

VaTeX [114] contains 3,4911 videos and has multilingual captions in Chinese
and English. Each video has 10 captions for each language. As for the other
datasets, we follow the same protocol as defined in prior works [19, 89, 27]
and use 1,500 videos for testing, while there are 1,500 videos for validation.
Please note that in this work, we use only the English annotations.

QuerYD [85] has 1,815 videos for training, 388 for validation and 390 for
testing. The videos are extracted from YouTube and are varied in content. The
dataset has 31,441 textual descriptions. 13,019 of these are precisely
localized in the video with start time and end time annotations while the
other 18,422 are coarsely localized. In this work, we do not use the
localization annotations and report results on the official splits following
prior work on text-video retrieval [27].

ActivityNet [14] contains 20k videos and has around 100K descriptive
sentences. The videos are extracted from YouTube. We use a paragraph video
retrieval as defined in prior works [128, 73, 27]. We report results on the
val1 split. The training split consists of 10,009 videos, while there are
4,917 videos for testing.

###  A.2 Text-image retrieval

For text image retrieval, we report results on the MSCoCo [20] dataset. It
consists of 123k images with 5 captions for each sentence. We report results
for the 5k test split.

###  A.3 Text-audio retrieval

For text audio retrieval, we report results on the AudioCaps [64] dataset
which comprises sounds with event descriptions. We use the same setup as prior
work [86] where 49,291 samples are used for training, 428 for validation and
816 for testing.

###  A.4 Image-to-image retrieval

CUB-200-2011 [111] contains 11,788 images with 200 classes. The training split
consist of the first 100 classes (5,863 images) while the testing split
contains the remaining classes (5,924 images). We use the same setup as used
in prior work [97].

Stanford Online Products [105] contains 120,053 images with products from
22,634 classes. We use the provided train and test splits containing 59,551
and 60,502 images respectively, as used in prior works [105, 97].

##  Appendix B The influence of the Top-k hyperparameter on DIS normalisation

Querybank Source Data | Topk | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---|---
No querybank | - | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
In Domain |  |  |  |  |
MSR-VTT | 1 | $17.0_{\pm 0.1}$ | $41.3_{\pm 0.1}$ | $54.1_{\pm 0.1}$ | $8.6_{\pm 0.5}$
MSR-VTT | 2 | $17.1_{\pm 0.1}$ | $41.7_{\pm 0.1}$ | $54.5_{\pm 0.1}$ | $8.0_{\pm 0.0}$
MSR-VTT | 3 | $17.1_{\pm 0.1}$ | $41.8_{\pm 0.1}$ | $54.6_{\pm 0.1}$ | $8.0_{\pm 0.0}$
MSR-VTT | 5 | $17.1_{\pm 0.1}$ | $41.9_{\pm 0.1}$ | $54.7_{\pm 0.1}$ | $8.0_{\pm 0.0}$
MSR-VTT | 10 | $17.1_{\pm 0.1}$ | $41.9_{\pm 0.1}$ | $54.7_{\pm 0.1}$ | $8.0_{\pm 0.0}$
Far Domain |  |  |  |  |
LSMDC | 1 | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.2_{\pm 0.1}$ | $10.0_{\pm 0.0}$
LSMDC | 2 | $14.8_{\pm 0.0}$ | $38.0_{\pm 0.0}$ | $51.0_{\pm 0.0}$ | $10.0_{\pm 0.0}$
LSMDC | 3 | $14.7_{\pm 0.0}$ | $37.9_{\pm 0.0}$ | $50.9_{\pm 0.0}$ | $10.0_{\pm 0.0}$
LSMDC | 5 | $14.6_{\pm 0.0}$ | $37.8_{\pm 0.0}$ | $50.8_{\pm 0.0}$ | $10.0_{\pm 0.0}$
LSMDC | 10 | $14.5_{\pm 0.0}$ | $37.5_{\pm 0.0}$ | $50.4_{\pm 0.0}$ | $10.0_{\pm 0.0}$

Table 14:  The influence of the $k$ hyperparameter on DIS normalisation.
Performance is reported on MSR-VTT full split [121], while querybanks of 5,000
samples are sampled from the training sets of different datasets. We observe
that for Far Domain querybanks, $k=1$ performs the best, while retaining good
performance for In Domain querybanks.

In Tab. 14 we show the influence of $k$ in the Top-k selection employed when
constructing the gallery activation set (introduced in Sec. 3.4 of the main
paper). We observe that choosing $k=1$ offers a good trade-off between good
performance when constructing In Domain querybanks and robustness when
constructing Far Domain querybanks. We therefore use $k=1$ for all reported
experiments.

##  Appendix C Can effective querybanks can be constructed from the training
set with IS normalisation?

Querybank Source | Size | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---|---
No querybank | - | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
Training set | 60k | $17.3_{\pm 0.1}$ | $42.1_{\pm 0.2}$ | $54.9_{\pm 0.1}$ | $8.0_{\pm 0.0}$
Val set | 10k | $16.7_{\pm 0.1}$ | $41.2_{\pm 0.1}$ | $54.0_{\pm 0.1}$ | $8.7_{\pm 0.5}$
Test set | 60k | $17.5_{\pm 0.0}$ | $42.4_{\pm 0.1}$ | $55.1_{\pm 0.0}$ | $8.0_{\pm 0.0}$

Table 15: Effective querybanks can be constructed from the training set.
Performance is reported on MSR-VTT full split [121] using IS normalisation. We
observe that a querybank of 60K samples from the training set performs
comparably to a test set querybank.

In the main submission, we showed that effective querybanks can be constructed
from the training set when employing DIS normalisation. Here, we show that
this property also applies to IS normalisation, supporting our hypothesis that
Querybank Normalisation has the general property of not requiring concurrent
access to multiple test queries for appropriate normalisation strategies. In
Tab. 15 we report the results of selecting queries from training, validation
or testing split to form the querybank when employing IS normalisation.
Similarly to DIS, we observe that training set querybanks perform comparably
to test set querybanks for IS normalisation.

##  Appendix D The influence of embedding dimensionality on the effectiveness
of QB-Norm

Figure 5:  (Left): The influence of embedding dimension on QB-Norm
effectiveness. We observe that QB-Norm brings a large increase in performance
in all cases (Right): The influence of number of used video embeddings on QB-
Norm effectiveness. We observe that our method is more effective with an
increased number of modalities.

Radovanovic et al. [93] posit that hubness is a phenomenon that is: (i)
inherent to high dimensional spaces; (ii) heavily influenced by the intrinsic
dimensionality of the data. To investigate these perspectives, we study the
improvement yielded by QB-Norm over embeddings of different dimensionality,
reporting results in Fig. 5 (left). We observe that QB-Norm brings around the
same gain when changing the embedding size. We can interpret this finding
within the framework of [93] as making the statement that changing the shared
embedding dimensionality does not influence intrinsic dimensionality. To
provide further analysis, we make a crude approximation to
increasing/decreasing intrinsic dimensionality by increasing/decreasing the
number of modalities employed in the video embedding. Intuitively, since audio
provides a different “view” of a sample to visual data, we expect a joint
embedding with access to more modalities to exhibit higher intrinsic
dimensionality than one with only visual cues. We plot the effect of these
changes in Fig. 5 (right). We observe a slight increase in performance gain
when applying QB-Norm with an increased number of modalities, which accords
with the Radovanovic [93] hypothesis.

Figure 6: Distribution of number of times each video is retrieved before and
after applying QB-Norm. We observe that QB-Norm reduces the maximum number of
retrievals for any individual video. Furthermore, we note that with QB-Norm,
previously unretrieved videos become possible to retrieve.

##  Appendix E Additional text-video retrieval results

In Tab. 16, 19 we report additional comparisons with state of the art on the
MSR-VTT full split as well as ActivityNet [14]. In both cases, we observe that
QB-Norm yields improvements. We also explore the use of QB-Norm with CLIP4Clip
[76]—for this, we train models using the code made available by the authors.
For CLIP4Clip experiments, we use a $\beta$ value of $0.45$ with the exception
of LSMDC where $\beta$ is $1.26^{-1}$.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
Dual[30] | $7.7$ | $22.0$ | $31.8$ | $32.0$
HGR[19] | $9.2$ | $26.2$ | $36.5$ | $24.0$
MoEE[79] | $11.1_{\pm 0.1}$ | $30.7_{\pm 0.1}$ | $42.9_{\pm 0.1}$ | $15.0_{\pm 0.0}$
CE[73] | $11.0_{\pm 0.0}$ | $30.8_{\pm 0.1}$ | $43.3_{\pm 0.3}$ | $15.0_{\pm 0.0}$
CE+[27] | $14.4_{\pm 0.1}$ | $37.4_{\pm 0.1}$ | $50.2_{\pm 0.1}$ | $10.0_{\pm 0.0}$
CE+ (+QB-Norm) | $16.4_{\pm 0.0}$ | $40.3_{\pm 0.1}$ | $53.0_{\pm 0.1}$ | $9.0_{\pm 0.0}$
TT-CE+[27] | $14.9_{\pm 0.1}$ | $38.3_{\pm 0.1}$ | $51.5_{\pm 0.1}$ | $10.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $17.3_{\pm 0.0}$ | $42.1_{\pm 0.1}$ | $54.9_{\pm 0.1}$ | $8.0_{\pm 0.0}$
CLIP4Clip[76]‡ | $27.9$ | $52.7$ | $63.6$ | $5.0$
CLIP4Clip (+QB-Norm) | $\mathbf{29.6}$ | $\mathbf{54.5}$ | $\mathbf{65.3}$ | $\mathbf{4.0}$

Table 16: MSR-VTT full split: comparison to state of the art.
‡ denotes results obtained training using the official code.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $16.1_{\pm 1.0}$ | $41.2_{\pm 1.6}$ | $55.2_{\pm 1.6}$ | $8.3_{\pm 0.5}$
CE[73] | $17.1_{\pm 0.9}$ | $41.9_{\pm 0.2}$ | $56.0_{\pm 0.5}$ | $8.0_{\pm 0.0}$
TT-CE | $21.0_{\pm 0.6}$ | $47.5_{\pm 0.9}$ | $61.9_{\pm 0.5}$ | $6.0_{\pm 0.0}$
Frozen[6] | $31.0$ | $59.8$ | $72.4$ | $3.0$
CLIP4Clip [76] | $\mathbf{43.4}$ | $70.2$ | $80.6$ | $\mathbf{2.0}$
CE+[27] | $18.2_{\pm 0.2}$ | $43.9_{\pm 0.9}$ | $57.1_{\pm 0.8}$ | $7.9_{\pm 0.1}$
CE+ (+QB-Norm) | $20.7_{\pm 0.6}$ | $46.6_{\pm 0.2}$ | $59.8_{\pm 0.2}$ | $6.3_{\pm 0.5}$
TT-CE+[27] | $21.6_{\pm 0.7}$ | $48.6_{\pm 0.4}$ | $62.9_{\pm 0.6}$ | $6.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $24.2_{\pm 0.7}$ | $50.8_{\pm 0.7}$ | $64.4_{\pm 0.1}$ | $5.3_{\pm 0.5}$
CLIP4Clip [76]‡ | $43.0$ | $70.5$ | $80.0$ | $\mathbf{2.0}$
CLIP4Clip (+QB-Norm) | $43.3$ | $\mathbf{71.4}$ | $\mathbf{80.8}$ | $\mathbf{2.0}$

Table 17: DiDeMo: Comparison to state of the art methods.
‡ denotes results obtained training using the official code.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $12.1_{\pm 0.7}$ | $29.4_{\pm 0.8}$ | $37.7_{\pm 0.2}$ | $23.2_{\pm 0.8}$
CE[73] | $12.4_{\pm 0.7}$ | $28.5_{\pm 0.8}$ | $37.9_{\pm 0.6}$ | $21.7_{\pm 0.6}$
MMT[41] | $13.2_{\pm 0.4}$ | $29.2_{\pm 0.8}$ | $38.8_{\pm 0.9}$ | $21.0_{\pm 1.4}$
Frozen[6] | $15.0$ | $30.8$ | $39.8$ | $20.0$
CLIP4Clip [76] | $21.6$ | $\mathbf{41.8}$ | $\mathbf{49.8}$ | $\mathbf{11.0}$
CE+[27] | $14.9_{\pm 0.6}$ | $33.7_{\pm 0.2}$ | $44.1_{\pm 0.6}$ | $15.3_{\pm 0.5}$
CE+ (QB-Norm) | $16.4_{\pm 0.8}$ | $34.8_{\pm 0.4}$ | $44.9_{\pm 0.9}$ | $14.5_{\pm 0.4}$
TT-CE+[27] | $17.2_{\pm 0.4}$ | $36.5_{\pm 0.6}$ | $46.3_{\pm 0.3}$ | $13.7_{\pm 0.5}$
TT-CE+ (QB-Norm) | $17.8_{\pm 0.4}$ | $37.7_{\pm 0.5}$ | $47.6_{\pm 0.6}$ | $12.7_{\pm 0.5}$
CLIP4Clip [76]‡ | $21.3$ | $40.0$ | $49.5$ | $\mathbf{11.0}$
CLIP4Clip (+QB-Norm) | $\mathbf{22.4}$ | $40.1$ | $49.5$ | $\mathbf{11.0}$

Table 18: LSMDC: Comparison to state of the art methods.
‡ denotes results obtained training using the official code.

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@50\uparrow$ | $MdR\downarrow$
---|---|---|---|---
MoEE[79] | $19.7_{\pm 0.3}$ | $50.0_{\pm 0.5}$ | $92.0_{\pm 0.2}$ | $5.3_{\pm 0.5}$
CE[73] | $19.9_{\pm 0.3}$ | $50.1_{\pm 0.7}$ | $92.2_{\pm 0.6}$ | $5.3_{\pm 0.5}$
HSE[128] | $20.5$ | $49.3$ | $-$ | $-$
MMT[41] | $22.7_{\pm 0.2}$ | $54.2_{\pm 1.0}$ | $93.2_{\pm 0.4}$ | $5.0_{\pm 0.0}$
SSB[89] | $26.8$ | $58.1$ | $93.5$ | $3.0$
CLIP4Clip[76] | $40.5$ | $\mathbf{72.4}$ | $\mathbf{98.1}$ | $\mathbf{2.0}$
TT-CE+[27] | $23.5_{\pm 0.2}$ | $57.2_{\pm 0.5}$ | $96.1_{\pm 0.1}$ | $4.0_{\pm 0.0}$
TT-CE+ (+QB-Norm) | $27.0_{\pm 0.2}$ | $60.6_{\pm 0.4}$ | $96.8_{\pm 0.0}$ | $4.0_{\pm 0.0}$
CLIP4Clip [76]‡ | $36.3$ | $65.9$ | $96.8$ | $3.0$
CLIP4Clip (+QB-Norm) | $\mathbf{41.4}$ | $71.4$ | $97.6$ | $\mathbf{2.0}$

Table 19: ActivityNet: Comparison to state of the art methods.
‡ denotes results obtained training using the official code.

##  Appendix F The computational complexity of normalisation strategies

As discussed in the main paper in Sec.3.4, we use various normalization
techniques in conjunction with QB-Norm. In this section, we describe the
computational cost of each technique in the context of its influence on
inference time. For clarity of exposition, we consider exact similarity
searches, but note that in practice approximate nearest neighbour
implementations are employed for large-scale deployments [58]. All strategies
incur an initial cost that corresponds to pre-computing the similarity between
a test query and all the videos from the gallery, $\mathcal{O}(N)$, where $N$
represents the number of videos in the gallery. We further assume that we have
pre-computed and stored all similarities between each query in the querybank
and videos from the gallery. This assumption incurs both computational and
storage costs of $\mathcal{O}(NM)$, where $M$ represents the number of queries
in the querybank.

Globally-Corrected (GC) retrieval [28] involves determining the rank of the
test query with respect to the querybank for each gallery item. Since we
assume that we have pre-computed similarities between the querybank and the
gallery, we also pre-compute an initial ranking over querybank elements for
each gallery item. For each test query, we establish its rank amongst the
querybank for every target item by performing a binary search over the sorted
list of pre-computed similarities. This incurs an inference time cost of
$\mathcal{O}(N\log M)$.

Cross-Domain Similarity Local Scaling (CSLS) [25] consists of finding the most
similar queries from the querybank for each gallery video and finding the $K$
gallery videos (here $K$ is a hyperparameter of CSLS) that are most similar to
the test query. For the former, we can pre-compute, for each video in the
gallery, the $K$ most similar queries from the querybank and store the average
similarity into a vector of size $N$. For the latter, we must compute (during
inference) the average similarity of the $K$ most similar items among the
gallery to our test query. Using quickselect, this can be done in
$\mathcal{O}(N)$ time on average (note that we do not require the top $K$
element similarities to be sorted, since they will be averaged).

Inverted Softmax (IS) [102] involves normalizing the final similarity by the
sum of the similarities given the querybank. However, the softmax denominator
can be pre-computed by summing the querybank similarities for each gallery
item and storing the results into a vector of size $N$. During inference the
similarities are divided by this pre-computed sum, which adds only constant-
time overhead. Pre-computing the sum in this manner also reduces the storage
cost associated with the querybank from $\mathcal{O}(NM)$ to $\mathcal{O}(N)$
(since we can discard the memory allocated to store the similarities between
each query in the querybank and each video in the gallery).

Dynamic Inverted Softmax (DIS). Since DIS involves applying IS dynamically,
the computation of the normalization for each test query is done in constant
time as described above for IS. The additional gallery activation set employed
by DIS can be pre-computed and stored for an additional $\mathcal{O}(N)$
storage cost. There is an additional cost during inference: the top-$1$ search
to determine the video originally retrieved by the test query (which
determines whether normalisation is performed). This can be done in linear
time ($\mathcal{O}(N)$).

##  Appendix G Comparison to CENT

Model | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---
Baseline | $15.0$ | $38.4$ | $51.5$ | $10.0$
CENT [107] | $14.4$ | $37.2$ | $50.2$ | $10.0$
DIS | $17.3$ | $42.1$ | $54.9$ | $8.0$

Table 20: MSR-VTT full split Comparison with CENT for a seed of TT-CE+[27]
model.

In Tab. 20 we show how CENT [107] normalisation performs in comparison to an
unnormalised baseline and Querybank Normalisation with DIS. Since we found
CENT to consistently harm performance for cross-modal retrieval, we did not
include it in all experiments in the main paper.

##  Appendix H Hubness and Skewness

We use the skewness metric as defined in [93] to measure hubness:

$S_{N_{k}}=\frac{E(N_{k}-\mu_{N_{k}})^{3}}{\sigma_{N_{k}}^{3}}$ (3)

where $\mu_{N_{k}}$ and $\sigma_{N_{k}}$ are the mean and standard deviation
of $N_{k}$. $N_{k}$ represents the k-occurrence distribution and is defined as
follows $N_{k}(\mathbf{x})=\sum_{i=1}^{n}p_{i,k}(\mathbf{x})$ where

$p_{i,k}(\mathbf{x})=\begin{cases}1,\text{if $\mathbf{x}$ is among the $k$
nearest neighbours of $q_{i}$}\\\ 0,\text{otherwise.}\end{cases}$ (4)

Here $\mathbf{x}$ represents a video embedding and $q_{i}\in Q$ a set of
queries. To compute these statistics, In practice, we use the we use $k=10$,
following [37] for the k-occurences distribution, employing the implementation
of [38].

As shown in Tab. 3 in the main paper, skewness and hence hubness is reduced
after applying QB-Norm. The same can be seen in Fig. 6 which depicts the
distribution of number of times each video is retrieved before and after using
QB-Norm. We observe that the maximum number of times a video is retrieved is
reduced, indicating a hubness reduction.

##  Appendix I Additional ablations on other metrics

In the main paper, to maintain conciseness we report ablation plots for the
influence of querybank size and inverse temperature using the geometric mean
of R1, R5 and R10. For completeness, in this section we show results on each
metric individually. As seen in Fig. 7, the individual metrics reflect the
trend shown for the geometric means, aligning with the results shown in the
main paper.

Figure 7: Retrieval results reported for a TT-CE+ [27] model on the MSR-VTT
[121] validation split in terms of R@1, R@5 and R@10. Left: The influence of
querybank size on retrieval performance. We observe that performance grows
steadily with increasing querybank size, but saturates. Right: The influence
of inverse temperature, $\beta$. Performance varies smoothly with inverse
temperature, peaking at a value of 20.

(a)

(b)

(c)

Figure 8: Qualitative results for the text video retrieval task. We show
queries and frames from the retrieved videos. For the first two example
queries, we observe that the use of QB-Norm leads to the retrieval of the
correct target video. The third query represents a failure case in which the
target video is not retrieved. However, we nevertheless observe qualitatively
that for this example, the video retrieved with QB-Norm is more related to the
query than the video retrieved without QB-Norm.

##  Appendix J Video and text embeddings (experts) description used for video
retrieval

For this work, we used the pretrained weights provided by TT-CE+ [27] and CE+
[73] (https://github.com/albanie/collaborative-experts). These models use a
set of pretrained experts. Below, we summarise how these experts were
extracted.

  * •

Two action experts are used: Action(KN) and Action(IG). Action(KN) is a
1024-dimensional embedding produced by an I3D architecture trained on Kinetics
[15]. The embeddings are extracted from frame clips at 25fps and center
cropped to 224 pixels. For Action(IG) the model is a 34-layer R(2+1)D [109],
trained on IG-65m [43]

  * •

Two forms of object experts: Obj(IN) and Obj(IG). For extracting Obj(IN) a
SENet-154 [52] model trained on ImageNet was used. For extracting Obj(IG) a
ResNext-101 [119] model trained on Instagram data with weakly labelled
hashtags [77] was used. Both of the embeddings are extracted at 25fps.

  * •

For producing an audio expert a VGGish model trained from audio classification
on the YouTube-8m dataset [51] was used.

  * •

For the scene expert a DenseNet-161 [53] pretrained on Places365 [133] was
used. The scene embedding has a 2208 dimension.

  * •

For the speech expert, the Google Cloud API (to transcribe the speech content)
is used.

  * •

For the text we use GPT2-xl [92] finetuned as provided by the authors. The
size of the final pre-trained embedding is 1600.

For CLIP2Video [35] we used the model as it is provided online
https://github.com/CryhanFang/CLIP2Video. The model receives as input the raw
frames and raw queries. For CLIP4Clip [76], we use the online code
https://github.com/ArrowLuo/CLIP4Clip and re-train the model for each dataset
where we present results since weights are not available online. For the other
tasks we followed the instructions given on the official repositories. For
MMT-Oscar [42] we used the pretrained weights and the features provided at
https://github.com/UKPLab/MMT-Retrieval. For RDML [97] we used the models
provided at https://github.com/Confusezius/Deep-Metric-Learning-Baselines. For
audio retrieval [86] we used the pretrained weights and models provided at
https://github.com/oncescuandreea/audio-retrieval.

##  Appendix K v2t performance metrics

Model | Task | $R@1\uparrow$ | $R@5\uparrow$ | $R@10\uparrow$ | $MdR\downarrow$
---|---|---|---|---|---
CE+[27] | v2t | $22.7_{\pm 0.5}$ | $52.6_{\pm 0.6}$ | $66.3_{\pm 0.2}$ | $5.0_{\pm 0.0}$
CE+ (+QB-Norm) | v2t | $28.6_{\pm 0.4}$ | $58.9_{\pm 0.5}$ | $71.4_{\pm 0.5}$ | $4.0_{\pm 0.0}$
TT-CE+[27] | v2t | $24.6_{\pm 0.3}$ | $54.1_{\pm 0.3}$ | $67.5_{\pm 0.5}$ | $4.7_{\pm 0.5}$
TT-CE+ (+QB-Norm) | v2t | $30.1_{\pm 0.4}$ | $61.4_{\pm 0.4}$ | $73.2_{\pm 0.4}$ | $3.0_{\pm 0.0}$

Table 21: MSR-VTT full split: Comparison to state of the art - v2t task.

In Tab. 21 we report metrics indicating the performance of QB-Norm on the
reverse task of video-text retrieval (in which videos are used as queries to
retrieve descriptions). We apply QB-Norm with DIS normalisation using all
videos from the training split to construct the querybank. We observe that QB-
Norm yields a striking boost in performance.

##  Appendix L Qualitative results

In Fig. 8 we provide some qualitative examples, illustrating cases for which
the QB-Norm model correctly retrieves videos that are not retrieved without
QB-Norm. Examining failure cases, we found qualitative examples for which the
retrieval ranking produced with QB-Norm was more “reasonable” (as shown in the
bottom set of Fig. 8). However, in line with prior work [93] suggesting that
hubness is a property of the distribution (rather than driven by individual
samples), we did not observe consistent, obvious qualitative trends among the
samples that were corrected, or remaining failure cases. As an example, we
observed gains for queries with both shorter and longer, highly descriptive
captions.