# SEA: Sentence Encoder Assembly for Video Retrieval by Textual Queries

Xirong Li, , Fangming Zhou, Chaoxi Xu, Jiaqi Ji, Gang Yang Manuscript received
August 14, 2020; revised November 05, 2020; accepted November 22, 2020.This
work was supported in part by NSFC (No. 61672523), Beijing Natural Science
Foundation (No. 4202033), the Fundamental Research Funds for the Central
Universities and the Research Funds of Renmin University of China (No.
18XNLG19). The associate editor coordinating the review of this manuscript and
approving it for publication was Prof. Raouf Hamzaoui.The authors are with the
Key Lab of Data Engineering and Knowledge Engineering, Renmin University of
China, and the AI & Media Computing Lab, School of Information, Renmin
University of China, Beijing 100872, China (e-mail<EMAIL_ADDRESS>
###### Abstract

Retrieving unlabeled videos by textual queries, known as Ad-hoc Video Search
(AVS), is a core theme in multimedia data management and retrieval. The
success of AVS counts on cross-modal representation learning that encodes both
query sentences and videos into common spaces for semantic similarity
computation. Inspired by the initial success of previously few works in
combining multiple sentence encoders, this paper takes a step forward by
developing a new and general method for effectively exploiting diverse
sentence encoders. The novelty of the proposed method, which we term _Sentence
Encoder Assembly_ (SEA), is two-fold. First, different from prior art that use
only a single common space, SEA supports text-video matching in multiple
encoder-specific common spaces. Such a property prevents the matching from
being dominated by a specific encoder that produces an encoding vector much
longer than other encoders. Second, in order to explore complementarities
among the individual common spaces, we propose multi-space multi-loss
learning. As extensive experiments on four benchmarks (MSR-VTT, TRECVID AVS
2016-2019, TGIF and MSVD) show, SEA surpasses the state-of-the-art. In
addition, SEA is extremely ease to implement. All this makes SEA an appealing
solution for AVS and promising for continuously advancing the task by
harvesting new sentence encoders.

###### Index Terms:

Ad-hoc video search, cross-modal representation learning, sentence encoder
assembly, multiple space learning

##  I Introduction

Video is arguably the most engaging type of digital content in our society.
Research related to video content understanding and retrieval is essential for
multimedia data management and retrieval. On one hand, common users have been
well educated by web search giants such as Google and Baidu to express their
information need in textual queries. While on the other hand, there is an
increasing amount of videos lacking reliable annotations or even completely
unlabeled. This paper targets at the challenging problem of ad-hoc video
search (AVS), which is to search on many unlabeled videos for user queries
expressed exclusively by a phrase or a natural-language sentence and provided
on the fly. The complexity of queries varies, ranging from specific objects,
_e.g.,_ “a sewing machine”, to multi-object events occurred in specific
scenes, _e.g.,_ “one or more people eating food at a table indoors”, see Fig.
1. A cross-modal similarity model that effectively computes the semantic
relevance of the unlabeled videos with respect to a given query is crucial.
Also, due to the ad-hoc nature of the query, the model has to be generalizable
to handle novel queries unseen when the model is built.

Figure 1: Top-5 videos per query sentence retrieved from V3C1 [1], a large
collection of one million _unlabeled_ web video clips, by the proposed SEA
model. Queries are from the TRECVID Ad-hoc Video Search benchmarks [2, 3, 4,
5].

For building such a model, both queries and videos have to be encoded into
real-valued vectors via cross-modal representation learning. Earlier efforts
struggle to detect semantic concepts from the two modalities and use the
detected concepts as an intermediate representation [6, 7, 8, 9, 10, 11]. Now,
it is becoming increasingly evident that learning cross-modal representations
in an end-to-end and concept-free manner is preferred, as manifested via major
benchmarks for the AVS task including TRECVID [12, 13, 14] and MSR-VTT [15,
16, 17].

We concentrate on end-to-end query representation learning, an essential
component for AVS. Typically, the component is composed of a sentence encoder
that vectorizes a textual query into a constant-sized vector and a feed-
forward neural network that projects the vector into a common latent space
[18, 19, 15, 12]. Varied types of sentence encoders have been investigated in
the growing literature. The vanilla Bag-of-Words (BoW) model is employed by
[20, 12, 14], with word2vec (w2v) in [12, 21], GRU / bi-GRU in [15, 12, 14,
22], NetVLAD in [16, 13], and BERT in [17, 23]. While the existing works
mainly count on a single sentence encoder, the importance of exploiting
multiple sentence encoders for addressing ad-hoc queries has been recognized
by few recent works [12, 14, 13]. The W2VV++ model proposed by Li _et al._
[12] processes a given query by three encoders, _i.e.,_ BoW, w2v and GRU, in
parallel, and then merges the three encoding results by vector concatenation.
Dong _et al._ [14] and their follow-up [13, 24] develop multi-level encoding,
where specific sentence encoders are selectively used at distinct levels.
Again, vector concatenation is used to combine encodings from the multiple
levels. Despite their state-of-the-art performance, we argue that such a
concatenation-based method is suboptimal due to the following two reasons.
First, the overall encoding could be easily dominated by a specific encoder
that produces an encoding vector much longer than the others. For instance,
the size of a BoW vector goes up to ten thousand with ease, while encodings of
word2vec, GRU or BERT are more compact, with a typical size of a few hundreds.
Second, varied encodings by distinct encoders are fed as a whole into the
subsequent feed-forward network, meaning the exploration of complementarities
among the encoders is limited to a single common space.

In this paper we advance AVS with the following contributions:

  * •

We propose _Sentence Encoder Assembly_ (SEA), a new and general method for
effectively exploiting varied sentence encoders. SEA bypasses the issues of
vector concatenation by learning common spaces per encoder.

  * •

To derive a cross-modal similarity from multiple common spaces, we propose
multi-space multi-loss learning, an effective mechanism to explore
complementarities among the individual common spaces.

  * •

Our solution surpasses the state-of-the-art on four benchmarks, _i.e.,_ MSR-
VTT, TRECVID AVS 2016–2019, TGIF and MSVD. Moreover, our solution is easy to
implement. With its generality, effectiveness and simplicity, SEA has opened
up a promising avenue for harnessing novel sentence encoders for continuous
performance improvement of AVS. Code and data are available at
https://github.com/li-xirong/sea.

Figure 2: Proposed Sentence Encoder Assembly (SEA) method for exploiting
multiple sentence encoders $\\{e_{t,1},\ldots,e_{t,k}\\}$ for computing cross-
modal similarities between a given query sentence $s$ and a specific unlabeled
video $v$. Instead of concatenating the output of the individual sentence
encoders as in previous works [14, 12, 13], our SEA model simultaneously
learns $k$ common spaces for the $k$ encoders. Rather than minimizing a single
loss computed based on the combined similarity $\sum_{i=1}^{k}cms_{i}(s,v)$,
SEA is trained to minimize a combine loss $\sum_{i=1}^{k}loss_{i}(s)$. Such a
multi-space multi-loss learning mechanism is novel and crucial for AVS,
meanwhile easy to implement.

##  II Related Work

Earlier methods for AVS follow a concept-based approach [8, 9, 25, 26, 27, 28,
29], with both queries and videos represented in a pre-defined concept space.
An intrinsic drawback of the concept-based approach is that concepts in use
have to be specified in advance, typically according to their occurrence in
training data. Such a hand-crafted common space is suboptimal for cross-modal
similarity computation [12]. In order to overcome the drawback, end-to-end
learning of concept-free and cross-modal representations has been the
mainstream [15, 14, 16, 30, 31]. As we target at query representation
learning, in what follows we discuss recent progress in this direction.

The classical Bag-of-Words (BoW) representation is commonly used for its
simplicity. In [20], for instance, a query is first encoded as a BoW vector,
and then projected into a latent space through a fully connected layer.
However, the BoW encoder has two intrinsic issues. First, it cannot handle
semantic relatedness between words. In a BoW feature space, the distance of “a
beagle is running” to “a dog is running” is the same as to “a person is
running”, even though the former pair is visually and semantically more close.
Second, it fully ignores word order. To resolve the first issue, Dong _et
al._[32] employ a pre-trained word2vec model to encode each word in a given
query into a dense vector and consequently obtain the query vector by mean
pooling over the word-level vectors. Later in Liu _et al._ [16], NetVLAD [33]
is adopted to exploit second-order statistics of the word-level vectors. To
overcome the limit of BoW in sequential modeling, varied forms of sequence-
aware deep neural networks are investigated. For instance, GRU is used in
[15], bi-LSTM in [34], relational GCN in [30], and more recently BERT in [17,
23].

While more advanced sentence encoders are being actively exploited for AVS, it
appears to us that no specific encoder is ready to rule them all. We attribute
this to the variety and complexity of AVS queries, which can be short phrases
or detailed descriptions of multiple-object actions in specific scenes. For
the former case, a BoW encoder will suffice, while the latter case requires a
complicated encoder to effectively capture fine-grained information. In the
context of image/video caption retrieval, Dong _et al._[32] make an initial
endeavor to combine multiple encoders including BoW, w2v and GRU for query
representation. In particular, they concatenate the output of the individual
encoders into a lengthy vector. Based on [32], Li _et al._[12] develop W2VV++,
the winning entry for the TRECVID AVS 2018 evaluation [35]. Contemporarily,
Dong _et al._[14] propose the Dual Encoding network, wherein three encoders,
_i.e.,_ BoW, bi-GRU and 1-d CNN, are employed to build a multi-level query
representation. Follow-ups of [14], _e.g.,_[13, 31, 24] also leverage multiple
encoders, and again merge the output of the encoders in advance to cross-modal
representation learning. By contrast, our multi-space learning mechanism makes
our model more flexible to harness the complementarities between distinct
sentence encoders. Consequently, even with common 2D-CNN features as video
representation, our proposed model compares favorably against the state-of-
the-art.

Note that at a high level, the idea of sentence encoder assembly is similar to
the conventional ensemble methods [36]. However, ensemble learning is a very
general idea, typically studied in the context of a classification task.
Therefore, a gap naturally exists between the idea itself and putting it to
work on AVS. This paper is an initial attempt to bridge the gap.

##  III Proposed Method

###  III-A Problem Formalization

We formalize an ad-hoc video search process as follows. We denote a specific
video clip as $v$ and a large collection of $n$ _unlabeled_ video clips as
$\mathcal{V}=\\{v_{1},\ldots,v_{n}\\}$. For an ad-hoc query in the form of a
sentence $s$, let $cms(s,v)$ be a cross-modal similarity function that
measures the semantic relevance between the query and a specific video.
Accordingly, the search process boils down to sorting $\mathcal{V}$ in
descending order in terms of $cms(s,v)$ and returning the top ranked items for
the given query. The computation of $cms(s,v)$ requires proper embeddings of
both $s$ and $v$ into a common cross-modal space. While visual CNNs are
prerequisites for video embedding, sentence encoders are required for query
embedding. Let $e_{t}$ be a specific sentence encoder, which encodes the given
query into a $d_{t}$-dimensional real-valued vector, _i.e.,_ $e_{t}(s)\in
R^{d_{t}}$. Having $k$ distinct sentence encoders
$\\{e_{t,1},\ldots,e_{t_{k}}\\}$ shall give us $k$ vectors of varied
dimensions $\\{d_{t,1},\ldots,d_{t,k}\\}$. We aim for a model that effectively
exploit the multiple sentence encoders for computing $cms(s,v)$.

Next, we describe in brief sentence encoders investigated in this work in
Section III-B, followed by the proposed sentence encoder assembly (SEA) model
in Section III-C.

###  III-B Sentence Encoders in Use

We consider five present-day sentence encoders, _i.e.,_ Bag-of-Words (BoW),
word2vec (w2v), GRU, bi-GRU and BERT. Among them, the first two are unigram,
while the others are sequential models. Their main properties are summarized
in Table I.

TABLE I: Five sentence encoders used in this paper. The specific value of the
vocabulary size $m$ is dataset-dependent, which is 7,676 for MSR-VTT, 3,981
for TGIF and 2,917 for MSVD. The notation $m$\+ means the vocabulary of GRU
and bi-GRU is slightly bigger than $m$ due to the inclusion of stopwords and
special tokens for sequential modeling.

Encoder | Vocabulary |  Dim. $d_{t}$ | Training | Prior work
---|---|---|---|---
BoW | $m$ | $m$ | Not trainable | [20, 32, 12, 14]
w2v | 1.7 millions | 500 |  | pre-trained1
---
and fixed
[32, 12, 21, 13]
GRU |  $m$+ | 1,024 |  | trained from
---
scratch
[32, 12, 15]
bi-GRU |  $m$+ | 2,048 |  | trained from
---
scratch
[14, 13]
BERT | 30,000 | 768 |  | pre-trained2
---
and fixed
[17, 23]

1) BoW. As a classical text encoder, BoW simply quantizes a given sentence $s$
of $l$ words with respect to a pre-specified vocabulary of $m$ words. Let
$c(s,j)$ be a function that counts the occurrence of the $j$-th word in the
sentence. Accordingly, we have the BoW encoding $e_{BoW}(s)$ as

$e_{BoW}(s):=(c(s,1),\ldots,c(s,m)).$ (1)

Note that an AVS query is relatively short, often containing less than 10
words. Meanwhile, the vocabulary size is much larger, with a typical order of
$10^{4}$. As a consequence, $e_{BoW}(s)$ is a long and sparse vector.

2) w2v. The w2v model [37] learns to produce word-level dense and semantic
vectors by training a two-layer neural network on a large text corpus, with
the goal to reconstruct linguistic contexts of words in the training text. As
computing the reconstruction loss requires no extra manual annotation, w2v
encodes millions of words with ease. We adopt a 500-dimensional w2v
model111https://github.com/danieljf24/w2vv Note that while [32] performs
image-to-text matching experiments on Flickr30k, its w2v model was trained on
English tags of 30 million Flickr images, using the skip-gram algorithm. from
[32]. We also tried alternatives such as GloVe [38], and found it less
effective in our preliminary experiments. Let $w2v(s[i])$ be a lookup function
that returns the embedding vector for the $i$-th word of $s$, we obtain w2v
based sentence encoding by mean pooling, _i.e.,_

$e_{w2v}(s):=\frac{1}{l}\sum_{i=1}^{l}w2v(s[i]).$ (2)

3) GRU. The Gated Recurrent Unit (GRU) network [39] models the sequential
information within a sentence by iteratively generating a sequence of
recurrent hidden state vectors $\\{\vec{h}_{1},\ldots,\vec{h}_{l}\\}$. In
particular, the hidden state vector at time-step $i$, $\vec{h}_{i}$, is
jointly determined by the word embedding of the current word $s[i]$ and
$\vec{h}_{i-1}$, the hidden state vector at the previous time-step. Similar to
LSTM [40], the GRU network effectively prevents the vanishing gradient problem
by introducing a gating mechanism to modulate the flow of information inside
the unit. Meanwhile, as GRU has no separate memory cell, it has a simplified
architecture and thus with less parameters to be trained. Following [12], we
obtain the GRU-based sentence encoding by mean pooling over the hidden vector
sequence, _i.e.,_

$e_{gru}(s):=\frac{1}{l}\sum_{i=1}^{l}\vec{h}_{i}.$ (3)

4) bi-GRU. The bi-directional GRU (bi-GRU) network extends the forward GRU by
including a backward GRU that encodes the sequence in a reverse order. Given
$\\{\reflectbox{$\vec{\reflectbox{$h$}}$}_{1},\ldots,\reflectbox{$\vec{\reflectbox{$h$}}$}_{l}\\}$
as hidden state vectors of the backward GRU, our bi-GRU based sentence
encoding is obtained by

$e_{bigru}(s):=\frac{1}{l}\sum_{i=1}^{l}\vec{h}_{i}\oplus\reflectbox{$\vec{\reflectbox{$h$}}$}_{i},$
(4)

where $\oplus$ denotes vector concatenation. Note that given forward and
backward hidden vectors of the same size, $e_{bigru}$ provides a richer
representation than $e_{gru}$ at the cost of doubled parameters. Hence, we
shall use either $e_{gru}$ or $e_{bigru}$, but not both.

5) BERT. The BERT model, built by stacking a number of $L$ bi-directional
Transformer blocks [41], generates word embeddings for a given sentence by
progressively passing encodings through the multiple blocks. A Transformer
block consists of a self-attention network and a feed-forward network [42].
The self-attention network accepts encodings of individual tokens from the
previous Transformer block, weighs their importance to each other by a self-
attention mechanism, and accordingly generates new encodings. These encodings
are then fed in parallel into the feed-forward network to produce the output
encodings of this block. In this work, we adopt the base version of BERT
containing $L=12$ blocks, which has been pre-trained on English Wikipedia and
book corpora for masked language modeling and next sentence
prediction222https://github.com/google-research/bert. We obtain the BERT-based
sentence encoding by mean pooling as

$e_{bert}(s)=\frac{1}{l}\sum_{i=1}^{l}\mbox{token-emb}(s[i],L-1),$ (5)

where $\mbox{token-emb}(s[i],L-1)$ denotes the embedding of the $i$-th word
produced by the second-last block. Note that we tried max pooling or using the
embedding of the first / last token, and found these alternatives less
effective than mean pooling.

With the sentence encoders introduced, we proceed to describe how to
effectively combine them in an end-to-end framework.

###  III-C Sentence Encoder Assembly

We propose to combine $k$ distinct sentence encoders
$\\{e_{t,i}|i=1,\ldots,k\\}$ in a generic multi-space multi-loss learning
framework.

Multiple common spaces. Our framework consists of $k$ cross-modal matching
subnetworks, each corresponding to a specific sentence encoder and learning
its own common space. Each subnetwork, indexed by $i$, consists of two fully
connected (FC) layers, one on the text side to transform $e_{t,i}(s)$ into a
$d_{c,i}$-dimensional vector, and the other on the video side that transforms
the video feature vector $f(v)$ into another $d_{c,i}$-dimensional vector.
Consequently, the sentence-video semantic relevance, denoted as
$cms_{i}(s,v)$, is computed as the cosine similarity between the two
embedding:

$cms_{i}(s,v):=\mbox{cosine-sim}(\underbrace{FC_{t,i}(e_{t,i}(s))}_{\mbox{text
embedding}},\underbrace{FC_{v,i}(f(v))}_{\mbox{video embedding}}),$ (6)

where $FC_{t,i}$ and $FC_{v,i}$ indicate the two FC layers, each followed by a
tanh function to increase their learning capacity. We choose the cosine
similarity as it is a widely used similarity metric for cross-modal matching
[43, 16, 14, 18, 44]. We also tried a Euclidean distance based similarity,
which is however less effective333For SEA ({BoW,w2v}) trained with the
Euclidean distance based similarity, its infAP scores on TV16/17/18/19 are
12.8/18.9/11.8/10.4, clearly lower than the cosine similarity counterpart
(15.7/23.4/12.8/16.6)..

By simply averaging the similarities computed in the individual common spaces,
we have the overall cross-modal similarity as

$cms(s,q):=\frac{1}{k}\sum_{i=1}^{k}cms_{i}(s,v).$ (7)

Note that we do not go for more complicated alternatives, _e.g.,_ weighing the
individual similarities by self-attention mechanisms. Rather, we opt for this
simple combination strategy, not only for preventing the risk of over-fitting.
Such a strategy also encourages the individual common spaces to be good enough
to be combined, as they are set to be equally important.

Multi-loss learning. We develop our loss function based on the improved
triplet ranking loss (ITRL) by Faghri _et al._[43]. While originally proposed
for image-text matching, ITRL is now found to be effective for text-video
matching [15, 12, 14, 16, 13]. Unlike the classical triplet ranking loss that
selects negative training examples by random, ITRL considers the negative that
violates the ranking constraint the most (within a mini-batch) and thus deemed
to be the most informative for improving the model being trained. Given a
training sentence $s$ with $v^{+}$ as a video relevant w.r.t $s$ and $v^{-}$
as irrelevant, we express ITRL as

$\left\\{\begin{array}[]{ll}v^{-*}&=\operatornamewithlimits{argmax}_{v^{-}\in
batch}(cms(s,v^{-})-cms(s,v^{+}))\\\
ITRL(s)&=\max(0,\alpha+cms(s,v^{-*})-cms(s,v^{+})),\end{array}\right.$ (8)

where $\alpha$ is a positive hyper-parameter concerning the margin.

We argue that such a single loss is suboptimal for multi-space learning. Given
a specific mini-batch, hard negative examples selected in terms of the
combined similarity are not necessarily the most effective for learning the
individual common spaces. Therefore, we choose to compute $ITRL_{i}(s)$ per
space, and accordingly learn to minimize their combined loss, _i.e.,_

$\sum_{i=1}^{k}ITRL_{i}(s).$ (9)

In a similar spirit to similarity combination, we again treat all the sub
losses equally. As exemplified in Fig. 3, the combined loss lets the model be
exposed to more diverse hard negatives. We empirically find that compared to
the single loss, the combined loss provides around 30% extra hard negatives
per training epoch.

Figure 3: Examples of hard negative videos automatically selected for specific
sentences during training. The first column (a) is selection based on the
combined similarity in a single common space. The other columns indicate
selections made based on individual similarities w.r.t (b) $e_{BoW}$, (c)
$e_{w2v}$, and (d) $e_{gru}$ within the proposed multi-space and multi-loss
framework. Using the combined loss allows the model to be exposed to more
diverse hard negatives in a given batch.

To sum up, the multi-space strategy provides a more flexible mechanism to
exploit complementarities among the distinct sentence encoders. Meanwhile,
given a specific mini-batch during training, the multi-loss strategy allows
each common space to select its own hard negative example. More flexibility in
encoder ensemble and more effectiveness for training together contributes to
the superior performance of the proposed SEA method against the state-of-the-
art.

##  IV Evaluation

We first conduct experiments on two major benchmarks, MSR-VTT [45] and TRECVID
AVS [2]. While originally developed for video captioning, MSR-VTT has been
adopted by recent works for text-based video retrieval [15, 34, 14, 16, 18,
30, 17]. TRECVID AVS is a leading benchmark for ad-hoc video search at large-
scale since 2016 [2, 3, 4, 5]. The two benchmarks have their own
characteristics. As shown in Table II, while MSR-VTT has a relatively small
amount of 2,990 test videos, it has over 59k query sentences. As for TRECVID,
it has a much larger number of test videos, over 335k in the 2016 / 2017 /
2018 editions and over one million in the 2019 edition. Hence, a joint
evaluation on the two benchmarks provides a comprehensive assessment of the
state-of-the-art. In addition, we report performance on TGIF [46] and MSVD
[47].

###  IV-A Experimental Setup

We first describe experimental setups unique to MSR-VTT and TRECVID, and then
introduce common implementations.

####  IV-A1 Setup for MSR-VTT

TABLE II: Datasets used in our evaluation. For all experiments we train models
on the specified training set and use the corresponding validation set for
model selection.

Data split | Data sources | Video clips | Frames | Queries
---|---|---|---|---
MSR-VTT experiments:
train set | MSR-VTT [45] | 6,513 | 197,648 | –
val. set | 497 | 15,347 | 9,940
test-full | 2,990 | 92,467 | 59,800
test-1k [34] | 1,000 | 30,932 | 1,000
TRECVID experiments:
train set | MSR-VTT [45] | 10,000 | 305,462 | –
TGIF [46] | 100,855 | 1,045,268 | –
val. set | TV16-VTT-dev [2] | 200 | 5,941 | 200
|  test set for
---
TV16/17/18
IACC.3 [2] | 335,944 | 3,845,221 | 90
|  test set for
---
TV19
V3C1 [1] | 1,082,649 | 7,839,450 | 30
TGIF experiments:
train set | TGIF [46] | 78,799 | 818,140 | –
val. set | 10,705 | 110,252 | 10,828
test set | 11,351 | 116,876 | 34,074
MSVD experiments:
train set | MSVD [47] | 1,200 | 23,313 | –
val. set | 100 | 2,415 | 4,291
test set | 670 | 15,429 | 27,767

We follow the official data split, which divides MSR-VTT into three disjoint
subsets used for training, validation and test, respectively. Note that in
[34] and its follow-ups [16, 18, 17], a smaller test set of 1,000 videos
randomly sampled from the full test set is used, which we refer to as test-1k.

Performance metrics. Following the previous works, we report _R@k_ ,
$k=1,5,10$, the percentage of test queries that have at least one relevant
video covered in the top $k$ returned items, and Median rank (_Med r_), the
median rank of the first relevant video in the search results. Mean Average
Precision (_mAP_) is also reported to assess the overall ranking quality.

####  IV-A2 Setup for TRECVID

We evaluate on the TRECVID AVS testbed from the last four years. The test
video collection for TV16 / TV17 / TV18 is IACC.3 [2], containing 335,944 web
video clips. The test collection for TV19 is V3C1 [48], which contains
1,082,649 web video clips, with even more diverse content, no predominant
characteristics and low self-similarity [1]. As no training data is provided
by the organizers, we adopt the setup of the winning entry of TV18 [35], using
MSR-VTT and TGIF [46] for training and the development set of the TV16 video-
to-text matching task [2] for validation.

Performance metric. The official metric, _i.e.,_ inferred average precision
(infAP) [49], is used.

####  IV-A3 Common Implementations

We use public feature data444https://github.com/li-xirong/avs, where each
video is represented by a 4,096-d feature vector, obtained by using two pre-
trained CNNs, _i.e.,_ ResNet-152 and ResNeXt-101, to extract 2,048-d features
from video frames. Frame-level features are concatenated and aggregated to
video-level features by mean pooling. We refer to [12] for details.

Training. The margin parameter $\alpha$ in the loss is set to $0.2$ according
to [43]. The dimensionality of all the common spaces $d_{c,i}$ is set to
2,048, which achieves a good balance between model performance and model
complexity. In fact, our model is highly robust to the choice of the common
space dimensionality, see the Appendix. We perform SGD based training, with a
mini-batch size of 128 and RMSProp as the optimizer. The learning rate is
initially set to $10^{-4}$, decayed by a factor of $0.99$ per epoch. Following
[50], we half the learning rate if the validation performance does not
increase in three consecutive epochs. Early stop occurs when no validation
performance increase is achieved in ten consecutive epochs. For each model
with specific configurations of sentence encoders, we repeat training three
times and pick the version that maximizes the validation performance. All
experiments were done with PyTorch (1.2.0) [51] on an Nvidia GEFORCE GTX
1080Ti GPU.

TABLE III: Joint evaluation of sentence encoders and their assembly models,
_i.e.,_ W2VV++ [12] and the proposed _SEA_ , on MSR-VTT and TRECVID. Numbers
are shown in percentages, with best scores shown in bold font. For a given
setup of sentence encoders, relative improvement of SEA over its W2VV++
counterpart is given in parentheses. SEA is consistently better.

Sentence encoders | Model |  MSR-VTT (the full test set) |  TRECVID (metric: infAP)
---|---|---|---
R@1 | R@5 | R@10 | Med r | mAP | TV16 | TV17 | TV18 | TV19 | MEAN
{BoW, w2v} | W2VV++ | 10.9 | 29.1 | 39.9 | 19 | 20.2 | 14.4 | 21.8 | 11.1 | 14.3 | 15.4
SEA | 11.6 | 30.6 | 41.6 | 17 | 21.3 ($\uparrow$5.4%) | 15.7 | 23.4 | 12.8 | 16.6 |  17.1 ($\uparrow$11.2%)
{BoW, w2v, GRU} | W2VV++ | 11.1 | 29.6 | 40.5 | 18 | 20.6 | 16.2 | 22.3 | 10.1 | 13.9 | 15.6
SEA | 12.2 | 31.9 | 43.1 | 15 | 22.1 ($\uparrow$7.3%) | 15.0 | 23.4 | 12.2 | 16.6 | 16.8 ($\uparrow$7.5%)
{BoW, w2v, bi-GRU} | W2VV++ | 11.3 | 29.9 | 40.6 | 18 | 20.8 | 16.1 | 21.7 | 10.4 | 13.5 | 15.4
SEA | 12.4 | 32.1 | 43.3 | 15 | 22.3 ($\uparrow$7.2%) | 16.4 | 22.8 | 12.5 | 16.7 |  17.1 ($\uparrow$10.9%)
{BoW, w2v, BERT} | W2VV++ | 12.3 | 31.8 | 43.0 | 15 | 22.2 | 15.1 | 22.5 | 10.2 | 12.8 | 15.2
SEA | 12.8 | 33.1 | 44.6 | 14 | 23.0 ($\uparrow$3.6%) | 15.3 | 22.8 | 12.1 | 14.8 | 16.3 ($\uparrow$7.3%)
{BoW, w2v, GRU, BERT} | W2VV++ | 12.1 | 31.7 | 42.7 | 16 | 22.0 | 14.3 | 19.3 | 9.3 | 10.1 | 13.3
SEA | 13.0 | 33.6 | 44.9 | 14 |  23.3 ($\uparrow$5.9%) | 16.0 | 23.1 | 12.1 | 15.4 | 16.7 ($\uparrow$25.7%)
{BoW, w2v, bi-GRU, BERT} | W2VV++ | 12.0 | 31.3 | 42.3 | 16 | 21.8 | 15.8 | 20.6 | 9.0 | 10.5 | 14.0
SEA | 13.1 | 33.4 | 45.0 | 14 |  23.3 ($\uparrow$6.9%) | 15.9 | 22.9 | 11.7 | 15.5 | 16.5 ($\uparrow$18.1%)

###  IV-B Experiment 1. Which Sentence Encoders to Use?

We compare with the state-of-the-art W2VV++ [12], which combines multiple
sentence encoders by concatenating their output into a long feature vector and
then embeds the concatenated vector into a common space by an FC layer. While
originally developed for automated search, W2VV++ has been used with success
by Kratochvíl _et al._ [52] and Lokoć _et al._ [23] in the Video Browser
Showdown, a leading benchmark for interactive video retrieval [53, 54]. For a
fair comparison, we use author-provided source code555https://github.com/li-
xirong/w2vvpp with the same setup as described in Section IV-A3.

The performance of W2VV++ and the proposed SEA model is presented in Table
III. For all configurations of sentence encoders, SEA consistently outperforms
its W2VV++ counterpart. Specifically, on MSR-VTT our model obtains a relative
improvement ranging from 3.6% to 7.3% in terms of mAP. While on TRECVID, the
relative improvement w.r.t the overall performance ranges from 7.3% to 25.7%.
The advantage becomes even more clear when four sentence encoders are
combined, see the last two rows in Table III. These results justify the
effectiveness of the multi-space mechanism.

As more sentence encoders are included, we observe different phenomenons on
the two benchmarks. For MSR-VTT, adding sequential encoders is helpful.
Compared to SEA ({BoW, w2v}), SEA ({BoW, w2v, GRU}) improves mAP from 21.3 to
22.1, while substituting BERT for GRU obtains higher mAP of 23.0. The peak
performance, mAP of 23.3, is reached by SEA ({BoW, w2v, GRU, BERT}) and SEA
({BoW, w2v, bi-GRU, BERT}). By contrast, the inclusion of GRU and BERT has a
negative impact on TRECVID. Compared to SEA ({BoW, w2v}) which has the best
overall infAP of 17.1, adding GRU results in an overall infAP of 16.8, while
adding BERT results in a lower value of 16.3. By analyzing the query sentences
of the two benchmarks, we find that an MSR-VTT sentence tend to be longer,
containing 9.3 words on average, while the corresponding number of TRECVID is
7.1. We attribute this difference to the fact that MSR-VTT was originally
meant for video captioning, so its sentences are more detailed. This is
furthered confirmed by part-of-speech statistics, where we find that an MSR-
VTT query has 3.3 nouns, 1.8 verbs and 0.6 adjective on average, while a
TRECVID query has 2.7 nouns, 1.0 verb and 0.4 adjective. TRECVID queries are
more keyword-oriented, _e.g.,_ “a newspaper”, “people shopping”, and “a blond
female indoors”. Hence, for answering keyword-oriented queries, SEA ({BoW,
w2v}) is most suited, while a full setup, _e.g.,_ SEA ({BoW, w2v, bi-GRU,
BERT}), is preferred for addressing description-oriented queries.

TABLE IV: Evaluating different methods for fusing multiple sentence encoders,
_i.e.,_{BoW, w2v, GRU}. The most effective method is to train the SEA model
with the combined loss.

Fusion method | TV16 | TV17 | TV18 | TV19 | MEAN
---|---|---|---|---|---
W2VV++ | 16.2 | 22.3 | 10.1 | 13.9 | 15.6
Transformed W2VV++ | 13.9 | 20.2 | 10.2 | 13.5 | 14.5
Model averaging | 14.9 | 21.9 | 11.6 | 15.4 | 16.0
SEA single loss | 14.7 | 21.8 | 11.2 | 14.7 | 15.6
SEA combined loss | 15.0 | 23.4 | 12.2 | 16.6 | 16.8

We further analyze the complementarity between the distinct sentence encoders
by inspecting how they behave when used individually. To that end, we train a
cross-modal matching network per encoder on MSR-VTT. To obtain an intuitive
understanding of what each network has learned as its common space, we perform
sentence-to-sentence retrieval, using all the 200k captions in MSR-VTT as a
sentence pool. As w2v and BERT are pre-trained on large-scale corpora with a
large vocabulary, they better handle subjects of low occurrence (‘beagle’) or
zero occurrence (‘rottweiler’) in the training data, see Fig. 4.
Interestingly, for the query ‘a is running on lawn’ where we have
intentionally remove the subject, BoW returns sentences describing person
running, while some of the top-ranked sentences by BERT are still related to
dogs. Moreover, we perform a per-query comparison between the matching
networks for video retrieval. Among all the 59,800 test queries, the network
with BoW is better than the others for 15.2% of the test queries, while the
numbers corresponding to w2v, GRU, bi-GRU and BERT are 14.5%, 12.9%, 14.0% and
19.6%, respectively. The results clearly show the complementarity between the
encoders.

Figure 4: Visualization of sentence-to-sentence retrieval results. Given a
query sentence, _e.g.,_ “a dog is running on lawn”, we retrieve top-20
sentences from MSR-VTT (which has 200k sentences in total), using common
spaces learned by cross-modal matching networks with respect to specific
sentence encoders. A yellow grid indicates sentences related to dogs. For the
last query, we intentionally remove the subject. Encoders pre-trained on
large-scale corpora, _i.e.,_ w2v and BERT, better handle subjects of low
occurrence (‘beagle’) or zero occurrence (‘rottweiler’) in the training data.

###  IV-C Experiment 2. Other Alternatives for Encoder Assembly?

As the output size of the individual sentence encoders ranges from 500
($e_{w2v}$) up to over 10k ($e_{BoW}$), one might naturally challenge the
deficiency of the concatenation operation used by W2VV++. For a more
comprehensive comparison, we further implement two more alternatives:
$\bullet$ Transformed W2VV++. We modify W2VV++ by adding an FC layer after
each encoder to transform all encodings into 2,048-d vectors in advance to
concatenation. This allows the size of the concatenated vector to be invariant
with respect to the encodings. The new variant is also end-to-end trained.
$\bullet$ Model averaging. The cross-modal subnetworks w.r.t the individual
encoders are trained separately. Cross-modal similarities computed by the
subnetworks are equally combined.

Table IV shows the results of these alternatives on TRECVID. The lower
performance of Transformed W2VV++ suggests that adjusting the encodings causes
loss in the original information produced by the individual encoders. Model
averaging outperforms W2VV++, again suggesting the benefit of using multiple
common spaces against a single common space. The result that model averaging
is less effective than SEA verifies the necessity of learning multiple common
spaces in a unified framework.

###  IV-D Experiment 3. Combined loss versus Single loss

We have qualitatively illustrate the benefit of the combined loss against the
single loss in Fig. 3. Now we provide more quantitative evidence. As Table IV
shows, SEA trained with the single loss does not outperform W2VV++. We can
also observe similar results from the learning curves in Fig. 5. For both
W2VV++ and _SEA_ , we use {BoW, w2v, GRU} as their sentence encoders. Note
that the number of epochs each model takes is not pre-specified. Due to the
early stop strategy, the number of training epochs actually took varies among
the models. As shown in Fig. 5, SEA with the single loss (the blue curve)
quickly converged to a suboptimal state. These results proof the importance of
the combined loss for training the multi-space network.

Figure 5: Learning curves of distinct models in the TRECVID experiments.
Validation is performed after each epoch. The number of epochs a model takes
is not pre-specified. After a model reaches its peak performance, as indicated
by yellow markers, early stopping occurs in ten epochs. So the number of
training epochs actually took varies among the models. Both W2VV++ and SEA use
{BoW, w2v, GRU} as their sentence encoders. For training the multi-space
network, the combined loss is preferred over the single loss.

###  IV-E Comparison to the State-of-the-Art

####  IV-E1 On MSR-VTT

We compare with 11 recent models as follows, which have been evaluated on the
test-1k set [34, 18, 17], the _full_ set [55, 30, 31] or both [43, 16, 14, 12,
44]. We highlight their choices of sentence encoders:
$\bullet$ JSFusion [34]: Use bi-LSTM as its sentence encoder.
$\bullet$ VSE++ [43]: Use GRU as its sentence encoder.
$\bullet$ Mithun _et al._ [55]: Use GRU as its sentence encoder.
$\bullet$ Miech _et al._ [18]: Use a 1D-CNN as its sentence encoder.
$\bullet$ Dual Encoding [14]: Hierarchical encoding that combines BoW, bi-GRU
and 1D-CNN.
$\bullet$ W2VV++ [12]: Concatenate encodings of BoW, w2v and GRU
$\bullet$ CE [16]: Use NetVLAD as its sentence encoder.
$\bullet$ TCE [44]: Use a latent semantic tree for query representation
learning.
$\bullet$ HGR [30]: Encode by hierarchical semantic graph including three
levels of events, actions, entities and relationships across levels.
$\bullet$ CF-GNN [31]: Graph neural network based search result reranking,
with Dual Encoding as its sentence encoder.
$\bullet$ UniViLM [17]: BERT as its sentence encoder.

Note that all the models were trained on the official training set of MSR-VTT
except for [18, 17], where the authors pre-trained their model on 100 million
narrated video clips and then fine-tuned on MSR-VTT.

TABLE V: State-of-the-art on MSR-VTT for text-based video retrieval. Best
scores from the cited papers are used, where applicable. On both the test-1k
set and the full test set, our proposed SEA({BoW, w2v,bi-GRU, BERT}) is the
best.

| Test
---
set
Model | R@1 | R@5 | R@10 |  | Med
---
r
mAP
1k [34] | JSFusion [34] | 10.2 | 31.2 | 43.2 | 13 | n.a.
VSE++ [43] | 15.2 | 37.7 | 50.1 | 10 | 26.0
TCE [44] | 16.1 | 38.0 | 51.5 | 10 | n.a.
Miech _et al._ [18] | 14.9 | 40.2 | 52.8 | 9 | n.a.
| UniViLM [17] | 15.4 | 39.5 | 52.3 | 9 | n.a.
| Dual Encoding [14] | 18.8 | 44.4 | 57.2 | 7 | 31.6
| W2VV++ [12] | 18.9 | 45.3 | 57.5 | 8 | 31.6
| CE [16] | 20.9 | 48.8 | 62.4 | 6 | n.a.
| SEA | 23.8 | 50.3 | 63.8 | 5 | 36.6
Full | Mithun _et al._ [55] | 7.3 | 21.7 | 30.9 | 34 | n.a.
TCE | 7.7 | 22.5 | 32.1 | 30 | n.a.
CF-GNN [31] | 8.0 | 23.2 | 32.6 | 31 | 16.0
VSE++ | 8.7 | 24.3 | 34.1 | 28 | 16.9
HGR [30] | 9.2 | 26.2 | 36.5 | 24 | n.a
| CE | 10.0 | 29.0 | 41.2 | 16 | n.a.
| Dual Encoding | 11.1 | 29.4 | 40.3 | 19 | 20.5
| W2VV++ | 11.1 | 29.6 | 40.5 | 18 | 20.6
| SEA | 13.1 | 33.4 | 45.0 | 14 | 23.3

Results. Table V shows the performance of the distinct models on the MSR-VTT
full test set and test-1k. For the ease of comparison, the performance of the
baselines is directly cited from the original papers except for W2VV++5,
VSE++666https://github.com/fartashf/vsepp and Dual
Encoding777https://github.com/danieljf24/dual_encoding, which we have re-
trained using their public code with the same video feature as used in this
work. Among the baselines, CE is the best on test-1k, while W2VV++ is the best
on the full test set. On both sets, the proposed SEA model is the top
performer. Notice that the good performance of CE is obtained by representing
videos with many features including appearance, scene, motion, face, OCR,
speech and audio. Given the simplicity of our video feature, the advantage of
the new model is clearly justified.

####  IV-E2 On TRECVID AVS 2016–2019

TABLE VI: State-of-the-art on TRECVID AVS. SEA surpasses the prior art. Late
average fusion of two SEA models or SEA ({BoW,w2v}) and Dual Encoding boosts
the performance.

Model | TV16 | TV17 | TV18 | TV19 | MEAN
---|---|---|---|---|---
Top-3 TRECVID finalists
Rank 1 |  05.4[25] | 20.6 [26] | 12.1 [35] | 16.3 [13] | n.a.
Rank 2 |  05.1 [27] | 15.9 [28] |  08.7 [56] | 16.0 [57] | n.a.
Rank 3 |  04.0 [58] | 12.0 [29] |  08.2 [59] | 12.3 [60] | n.a.
VideoStory [20, 61] |  08.7 | 15.0 | n.a. | n.a. | n.a.
VSE++ [43] | 13.5 | 16.3 | 10.6 |  09.8 | 12.6
W2VV++ [12] | 16.2 | 22.3 | 10.1 | 13.9 | 15.6
Dual Encoding [14] | 16.5 | 22.8 | 11.7 | 15.2 | 16.6
| Extended Dual
---
Encoding [24]
15.9 | 24.4 | 12.6 | n.a. | n.a.
SEA({BoW,w2v}) | 15.7 | 23.4 | 12.8 | 16.6 | 17.1
SEA({BoW,w2v,bi-GRU}) | 16.4 | 22.8 | 12.5 | 16.7 | 17.1
|  SEA({BoW,w2v}) +
---
SEA({BoW,w2v,bi-GRU})
16.6 | 23.5 | 12.6 | 17.2 | 17.5
|  SEA({BoW,w2v}) +
---
Dual Encoding
17.3 | 25.0 | 12.8 | 17.1 | 18.1

Figure 6: Performance of varied models in the TRECVID 2019 (TV19) AVS task,
which is to find amidst a set of one million unlabeled videos those relevant
with respect to 30 test queries. For result analysis, each query is preceded
by the TRECVID-specified query type, _e.g.,_[person + object] or [person +
action + location], and ID. The queries are sorted in descending order in
terms of their infAP scores by SEA ({BoW,w2v,bi-GRU}). As the key difference
of the varied models is whether multiple sentence encoders are used and how
they are combined, the leading performance of the SEA series verifies the
effectiveness of the proposed method, namely multi-space network plus multi-
loss training.

We compare with the top-3 finalist of the TRECVID AVS evaluation each year,
which naturally reflects the state-of-the-art. We again compare with W2VV++,
VSE++ and Dual Encoding, re-training them using the TRECVID setup as described
in Section IV-A2. We also include VideoStory [20] which uses BoW as its
sentence encoder, and Extended Dual Encoding [24], a very recent work which
makes use of more than one encodings of the visual and textual content and two
distinct attention mechanisms.

Results. The performance on the TRECVID test data is shown in Table VI. The
proposed SEA model surpasses the prior art. While the Extended Dual Encoding
network [24] appears to be on par with the SEA models, [24] has factually used
the ground truth of the test set, which shall be unavailable in real
applications, to select the best performing models. By contrast, our model
selection is performed exclusively based on an independent validation set (see
Table II), and thus more practical.

Late average fusion of Dual Encoding and SEA boosts the performance further,
see the last row. Note that previous top-performing submissions boost their
performance by late (average) fusion of a handful of models [26, 35, 13] or
nearly hundred models [60]. In this context, the capability of SEA to advance
the state-of-the-art with a single model is a big advantage for AVS at large-
scale.

Fig. 6 shows how each model performs on the individual queries from the TV19
task, by searching over the one-million V3C1 collection. Each query is
preceded by a TRECVID-specified query type that reflects the query complexity
to some extent [5]. A query comprised of person, action, object and location
tends to be more complex and thus more difficult to address than a query of
person. While such a pattern can largely be observed from Fig. 6, exceptions
are not uncommon. Consider query #639, for instance. Although the top-ranked
videos show small airplane flying, they are mostly “external view”, rather
than “inside view” as required. Such a geometric property has not been
effectively captured by the current sentence encoders that are fully data-
driven. We consider the SEA model, with its flexibility to harvest new
encoders, promising to attack the deficiency.

####  IV-E3 On TGIF and MSVD

For both datasets, we follow the data partition specified by their developers.
That is, training / validation / test is 78,799 / 10,705 / 11,351 for TGIF and
1,200 / 100 / 670 for MSVD. All captions are used. The state-of-the-art
following such a setting is HGR [30] and CF-GNN [31] on TGIF and CF-GNN on
MSVD. Therefore, we compare with these two models. Dual Encoding and W2VV++
are also included.

Results. As shown in Table VII and Table VIII, our SEA model is again the
best. Given that the amount of the training data in MSVD is substantially less
than that of TGIF, the peak performance of SEA on MSVD is reached with less
sentence encoders.

TABLE VII: State-of-the-art on TGIF for text-based video retrieval.

Model | R@1 | R@5 | R@10 |  | Med
---
r
mAP
HGR [30] | 4.5 | 12.4 | 17.8 | 160 | n.a.
Dual Encoding [14] | 9.1 | 21.3 | 28.6 | 50 | 15.7
W2VV++ [12] | 9.4 | 22.3 | 29.8 | 48 | 16.2
CF-GNN [31] | 10.2 | 23.0 | 30.7 | 44 | n.a.
SEA ({BoW,w2v,GRU}) | 10.2 | 23.6 | 31.3 | 41 | 17.2
SEA ({BoW,w2v,BERT}) | 10.7 | 24.4 | 31.9 | 37 | 17.9
SEA ({BoW,w2v,GRU,BERT}) | 11.1 | 25.2 | 32.7 | 36 | 18.4
SEA ({BoW,w2v,bi-GRU,BERT}) | 11.1 | 25.2 | 32.8 | 35 | 18.5

TABLE VIII: State-of-the-art on MSVD for text-based video retrieval.

Model | R@1 | R@5 | R@10 |  | Med
---
r
mAP
Dual Encoding [14] | 20.3 | 46.8 | 59.7 | 6 | 32.9
CF-GNN [31] | 22.8 | 50.9 | 63.6 | 6 | n.a.
W2VV++ [12] | 22.4 | 51.6 | 64.8 | 5 | 36.1
SEA ({BoW,w2v,GRU}) | 23.2 | 52.9 | 66.2 | 5 | 37.2
SEA ({BoW,w2v,BERT}) | 24.6 | 55.0 | 67.9 | 4 | 38.7
SEA ({BoW,w2v,GRU,BERT}) | 24.4 | 54.1 | 67.6 | 5 | 38.3
SEA ({BoW,w2v,bi-GRU,BERT}) | 23.9 | 53.9 | 67.3 | 5 | 38.0

###  IV-F Efficiency Analysis

We report in Table IX the amount of trainable parameters, training time and
inference time of the SEA models with varied setups on MSR-VTT, TGIF and MSVD.
Two state-of-the-art methods, _i.e.,_ Dual Encoding [14] and W2VV++ [12], are
included as well. For a fair comparison, all models use the same size of 2,048
for their common spaces. For all models, the computational cost of video
embedding is excluded from the inference time as this step is done once in an
offline mode. Concerning the training time, Dual Encoding is slower than
W2VV++ and SEA on MSR-VTT and MSVD, while faster on TGIF. In particular, SEA
({BoW,w2v,biGRU,BERT}) requires the longest training time of 4.9 hours on
TGIF, as we find that the model needs more training epochs to trigger the
early stop mechanism on this dataset.

For each model, its inference time to answer a given query consists of two
parts: 1) query embedding that projects the query into a common space (for
Dual Encoding and W2VV++) or multiple common spaces (for the SEA models), and
2) ranking that performs cross-modal matching between the query and all videos
in a test set and sorting the videos accordingly. The main computational
overhead is due to the online inference of the BERT encoder. Still, query
embedding can be done within 19 milliseconds. As the cross-modal matching is
executed in parallel on GPU, the ranking is extremely fast, costing around one
millisecond. The inference time per query is around 20 milliseconds. Hence,
our model is sufficiently fast to support real-time interactive video
retrieval.

TABLE IX: Training and inference time of Dual Encoding, W2VV++ and our
proposed SEA models on distinct datasets. The dimensionality of the common
space for all models is 2,048. Experiments are done with PyTorch (1.2.0) on an
Nvidia 1080Ti GPU.

Model | MSR-VTT | TGIF | MSVD
---|---|---|---
| #parameters
---
(million)
| training
---
time (hr)
| query
---
embedding
(ms)
| ranking
---
(ms)
| #parameters
---
(million)
| training
---
time (hr)
| query
---
embedding
(ms)
| ranking
---
(ms)
| #parameters
---
(million)
| training
---
time (hr)
| query
---
embedding
(ms)
| ranking
---
(ms)
Dual Encoding [14] | 95.9 | 2.9 | 14.8 | 0.5 | 86.5 | 2.2 | 16.6 | 0.9 | 83.7 | 0.7 | 13.7 | 0.4
W2VV++ [12] | 35.8 | 1.2 | 2.1 | 0.5 | 26.4 | 2.4 | 2.2 | 0.9 | 23.7 | 0.3 | 1.8 | 0.4
SEA(BoW,w2v) | 33.5 | 0.9 | 1.2 | 0.6 | 26.0 | 3.1 | 1.0 | 1.0 | 23.8 | 0.1 | 0.9 | 0.6
SEA(BoW,w2v,GRU) | 52.6 | 2.7 | 2.4 | 0.8 | 43.2 | 4.4 | 2.4 | 1.1 | 40.5 | 0.2 | 2.2 | 0.8
SEA(BoW,w2v,bi-GRU) | 59.4 | 2.4 | 2.8 | 0.8 | 50.0 | 4.9 | 3.0 | 1.1 | 47.3 | 0.4 | 2.6 | 0.8
SEA(BoW,w2v,BERT) | 43.5 | 1.0 | 15.8 | 0.8 | 35.9 | 3.6 | 15.9 | 1.1 | 33.8 | 0.2 | 15.5 | 0.8
SEA(BoW,w2v,GRU,BERT) | 62.6 | 2.0 | 17.4 | 0.9 | 53.2 | 4.4 | 17.1 | 1.2 | 50.4 | 0.3 | 17.1 | 1.0
SEA(BoW,w2v,bi-GRU,BERT) | 69.4 | 2.5 | 18.4 | 0.9 | 59.9 | 4.9 | 18.2 | 1.2 | 57.2 | 0.3 | 17.4 | 0.9

##  V Conclusions

We have described a method for exploiting diverse sentence encoders for ad-hoc
video search. Our experiments show the importance of building a query
representation learning network that supports text-video matching in multiple
encoder-specific common spaces. Nonetheless, the multi-space network
architecture alone is inadequate. In order to effectively utilize
complementaries among the individual common spaces, the network has to be end-
to-end trained with a combined loss. On four benchmark datasets including MSR-
VTT, TRECVID AVS 2016–2019, TGIF and MSVD, our proposed SEA model with multi-
space multi-loss learning surpasses the prior art.

The impact of the common space dimensionality. As shown in Table X, except for
using a relatively small value of 256, the dimensionality of the common space
has a marginal impact on the performance of the proposed method. We recommend
to use 2,048 to strikes a proper balance between performance and model
complexity.

TABLE X: The influence of the common space dimensionality $d_{c,i}$ on the
model performance. We evaluate SEA ({BoW,w2v,GRU}) on MSR-VTT.

$d_{c,i}$ | R@1 | R@5 | R@10 | Med r | mAP
---|---|---|---|---|---
256 | 11.0 | 29.5 | 40.4 | 18 | 20.4
512 | 12.0 | 31.5 | 42.7 | 16 | 21.9
1,024 | 12.1 | 31.6 | 42.9 | 15 | 22.0
2,048 | 12.2 | 31.9 | 43.1 | 15 | 22.1
4,096 | 12.2 | 31.8 | 43.1 | 15 | 22.1
8,192 | 12.1 | 31.4 | 42.6 | 16 | 21.8

The role of pretraining corpus. As noted in Section III-B, we use w2v and BERT
which were pre-trained on Flickr tags [32] and web documents [41],
respectively. To investigate if better performance can be obtained by pre-
training the two encoders on the same corpus, we have re-trained w2v on
Wikipedia dumps and book corpus as used for BERT. We do not try the opposite
direction, _i.e.,_ re-training BERT on the Flickr data, since Flickr tags are
not natural-language text and thus unsuited for training BERT. As shown in
Table XI, the Flickr version of w2v is slightly better.

TABLE XI: Performance of SEA with w2v pre-trained on distinct corpus. We
evaluate SEA ({BoW,w2v,bi-GRU,BERT}) on MSR-VTT.

Corpus for w2v | R@1 | R@5 | R@10 | Med r | mAP
---|---|---|---|---|---
Flickr tags | 13.1 | 33.4 | 45.0 | 14 | 23.3
Wiki & book corpus | 13.0 | 33.4 | 44.9 | 14 | 23.3

## References

  * [1] F. Berns, L. Rossetto, K. Schoeffmann, C. Beecks, and G. Awad, “V3C1 dataset: An evaluation of content characteristics,” in _ICMR_ , 2019.
  * [2] G. Awad, J. Fiscus, D. Joy, M. Michel, A. Smeaton, W. Kraaij, G. Quénot, M. Eskevich, R. Aly, R. Ordelman, G. Jones, B. Huet, and M. Larson, “Trecvid 2016: Evaluating video search, video event detection, localization, and hyperlinking,” in _TRECVID Workshop_ , 2016.
  * [3] G. Awad, A. Butt, J. Fiscus, D. Joy, A. Delgado, M. Michel, A. Smeaton, Y. Graham, G. J. F. Jones, W. Kraaij, G. Quénot, M. Eskevich, R. Ordelman, and B. Huet, “Trecvid 2017: Evaluating ad-hoc and instance video search, events detection, video captioning and hyperlinking,” in _TRECVID Workshop_ , 2017.
  * [4] G. Awad, A. Butt, K. Curtis, Y. Lee, J. Fiscus, A. Godil, D. Joy, A. Delgado, A. F. Smeaton, Y. Graham, W. Kraaij, G. Quénot, J. Magalhaes, D. Semedo, and S. Blasi, “Trecvid 2018: Benchmarking video activity detection, video captioning and matching, video storytelling linking and video search,” in _TRECVID Workshop_ , 2018.
  * [5] G. Awad, A. Butt, K. Curtis, Y. Lee, J. Fiscus, A. Godil, A. Delgado, A. F. Smeaton, Y. Graham, W. Kraaij, and G. Quénot, “Trecvid 2019: An evaluation campaign to benchmark video activity detection, video captioning and matching, and video search & retrieval,” in _TRECVID Workshop_ , 2019\.
  * [6] M. Naphade, J. Smith, J. Tešić, S.-F. Chang, W. Hsu, L. Kennedy, A. Hauptmann, and J. Curtis, “Large-scale concept ontology for multimedia,” _IEEE Multimedia_ , vol. 13, no. 3, pp. 86–91, 2006.
  * [7] A. Hauptmann, R. Yan, W.-H. Lin, M. Christel, and H. Wactlar, “Can high-level concepts fill the semantic gap in video retrieval? a case study with broadcast news,” _T-MM_ , vol. 9, no. 5, pp. 958–966, 2007.
  * [8] C. G. M. Snoek and M. Worring, “Concept-based video retrieval,” _Foundations and Trends in Information Retrieval_ , vol. 2, no. 4, pp. 215–322, 2009.
  * [9] Y.-J. Lu, H. Zhang, M. de Boer, and C.-W. Ngo, “Event detection with zero example: Select the right and suppress the wrong concepts,” in _ICMR_ , 2016\.
  * [10] F. Markatopoulou, D. Galanopoulos, V. Mezaris, and I. Patras, “Query and keyframe representations for ad-hoc video search,” in _ICMR_ , 2017.
  * [11] G. Awad, D.-D. Le, C.-W. Ngo, V.-T. Nguyen, G. Quénot, C. Snoek, and S. Satoh, “Video indexing, search, detection, and description with focus on trecvid,” in _ICMR_ , 2017.
  * [12] X. Li, C. Xu, G. Yang, Z. Chen, and J. Dong, “W2VV++: Fully deep learning for ad-hoc video search,” in _ACMMM_ , 2019.
  * [13] X. Wu, D. Chen, Y. He, H. Xue, M. Song, and F. Mao, “Hybrid sequence encoder for text based video retrieval,” in _TRECVID Workshop_ , 2019.
  * [14] J. Dong, X. Li, C. Xu, S. Ji, Y. He, G. Yang, and X. Wang, “Dual encoding for zero-example video retrieval,” in _CVPR_ , 2019.
  * [15] N. Mithun, J. Li, F. Metze, and A. K. Roy-Chowdhury, “Learning joint embedding with multimodal cues for cross-modal video-text retrieval,” in _ICMR_ , 2018\.
  * [16] Y. Liu, S. Albanie, A. Nagrani, and A. Zisserman, “Use what you have: Video retrieval using representations from collaborative experts,” in _BMVC_ , 2019\.
  * [17] H. Luo, L. Ji, B. Shi, H. Huang, N. Duan, T. Li, X. Chen, and M. Zhou, “UniViLM: A unified video and language pre-training model for multimodal understanding and generation,” _arXiv preprint arXiv:2002.06353_ , 2020.
  * [18] A. Miech, D. Zhukov, J.-B. Alayrac, M. Tapaswi, I. Laptev, and J. Sivic, “Howto100M: Learning a text-video embedding by watching hundred million narrated video clips,” in _ICCV_ , 2019.
  * [19] Y. Pan, T. Mei, T. Yao, . Li, and Y. Rui, “Jointly modeling embedding and translation to bridge video and language,” in _CVPR_ , 2016.
  * [20] A. Habibian, T. Mensink, and C. G. M. Snoek, “Video2vec embeddings recognize events when examples are scarce,” _T-PAMI_ , vol. 39, no. 10, pp. 2089–2103, 2017.
  * [21] M. Wray, D. Larlus, G. Csurka, and D. Damen, “Fine-grained action retrieval through multiple parts-of-speech embeddings,” in _ICCV_ , 2019.
  * [22] B. Zhang, H. Hu, and F. Sha, “Cross-modal and hierarchical modeling of video and text,” in _ECCV_ , 2018.
  * [23] J. Lokoć, T. Soućek, P. Veselý, F. Mejzlík, J. Ji, C. Xu, and X. Li, “A W2VV++ case study with automated and interactive text-to-video retrieval,” in _ACMMM_ , 2020.
  * [24] D. Galanopoulos and V. Mezaris, “Attention mechanisms, signal encodings and fusion strategies for improved ad-hoc video search with dual encoding networks,” in _ICMR_ , 2020.
  * [25] D.-D. Le, S. Phan, V.-T. Nguyen, B. Renoust, T. Nguyen, V.-N. Hoang, T. Ngo, M.-T. Tran, Y. Watanabe, M. Klinkigt _et al._ , “NII-HITACHI-UIT at TRECVID 2016,” in _TRECVID Workshop_ , 2016.
  * [26] C. G. M. Snoek, X. Li, C. Xu, and D. C. Koelma, “University of Amsterdam and Renmin university at TRECVID 2017: Searching video, detecting events and describing video,” in _TRECVID Workshop_ , 2017.
  * [27] F. Markatopoulou, A. Moumtzidou, D. Galanopoulos, T. Mironidis, V. Kaltsa, A. Ioannidou, S. Symeonidis, K. Avgerinakis, S. Andreadis _et al._ , “ITI-CERTH participation in TRECVID 2016,” in _TRECVID Workshop_ , 2016\.
  * [28] K. Ueki, K. Hirakawa, K. Kikuchi, T. Ogawa, and T. Kobayashi, “Waseda_Meisei at TRECVID 2017: Ad-hoc video search,” in _TRECVID Workshop_ , 2017.
  * [29] P. Nguyen, Q. Li, Z.-Q. Cheng, Y.-J. Lu, H. Zhang, X. Wu, and C.-W. Ngo, “VIREO@TRECVID 2017: Video-to-text, ad-hoc video search and video hyperlinking,” in _TRECVID Workshop_ , 2017.
  * [30] S. Chen, Y. Zhao, Q. Jin, and Q. Wu, “Fine-grained video-text retrieval with hierarchical graph reasoning,” in _CVPR_ , 2020.
  * [31] W. Wang, J. Gao, X. Yang, and C. Xu, “Learning coarse-to-fine graph neural networks for video-text retrieval,” _T-MM_ , 2020, in press.
  * [32] J. Dong, X. Li, and C. G. M. Snoek, “Predicting visual features from text for image and video caption retrieval,” _T-MM_ , vol. 20, no. 12, pp. 3377–3388, 2018.
  * [33] R. Arandjelović, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “NetVLAD: CNN architecture for weakly supervised place recognition,” _T-PAMI_ , vol. 40, no. 6, pp. 1437–1451, 2018.
  * [34] Y. Yu, J. Kim, and G. Kim, “A joint sequence fusion model for video question answering and retrieval,” in _ECCV_ , 2018.
  * [35] X. Li, J. Dong, C. Xu, J. Cao, X. Wang, and G. Yang, “Renmin University of China and Zhejiang Gongshang University at TRECVID 2018: Deep Cross-Modal Embeddings for Video-Text Retrieval,” in _TRECVID Workshop_ , 2018.
  * [36] C. M. Bishop, _Pattern Recognition and Machine Learning_. Berlin, Heidelberg: Springer-Verlag, 2006.
  * [37] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” in _ICLR_ , 2013.
  * [38] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in _EMNLP_ , 2014.
  * [39] K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using rnn encoder-decoder for statistical machine translation,” in _EMNLP_ , 2014.
  * [40] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” _Neural Computation_ , vol. 9, no. 8, pp. 1735–1780, 1997.
  * [41] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: pre-training of deep bidirectional transformers for language understanding,” in _NAACL-HLT_ , 2019\.
  * [42] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NIPS_ , 2017.
  * [43] F. Faghri, D. J. Fleet, J. R. Kiros, and S. Fidler, “VSE++: Improving visual-semantic embeddings with hard negatives,” in _BMVC_ , 2018.
  * [44] X. Yang, J. Dong, Y. Cao, X. Wang, M. Wang, and T.-S. Chua, “Tree-augmented cross-modal encoding for complex-query video retrieval,” in _SIGIR_ , 2020\.
  * [45] J. Xu, T. Mei, T. Yao, and Y. Rui, “MSR-VTT: A large video description dataset for bridging video and language,” in _CVPR_ , 2016.
  * [46] Y. Li, Y. Song, L. Cao, J. Tetreault, L. Goldberg, A. Jaimes, and J. Luo, “TGIF: A new dataset and benchmark on animated GIF description,” in _CVPR_ , 2016.
  * [47] D. L. Chen and W. B. Dolan, “Collecting highly parallel data for paraphrase evaluation,” in _ACL_ , 2011.
  * [48] L. Rossetto, H. Schuldt, G. Awad, and A. A. Butt, “V3c – a research video collection,” in _MMM_ , 2019.
  * [49] E. Yilmaz and J. A. Aslam, “Estimating average precision with incomplete and imperfect judgments,” in _CIKM_ , 2006.
  * [50] A. Joulin, L. van der Maaten, A. Jabri, and N. Vasilache, “Learning visual features from large weakly supervised data,” in _ECCV_ , 2016.
  * [51] A. Paszke _et al._ , “PyTorch: An imperative style, high-performance deep learning library,” in _NeurIPS_ , 2019.
  * [52] M. Kratochvíl, P. Veselý, F. Mejzlík, and J. Lokoč, “SOM-Hunter: Video browsing with relevance-to-som feedback loop,” in _MMM_ , 2020.
  * [53] J. Lokoč, W. Bailer, K. Schoeffmann, B. Muenzer, and G. Awad, “On influential trends in interactive video retrieval: Video browser showdown 2015–2017,” _T-MM_ , vol. 20, no. 12, pp. 3361–3376, 2018.
  * [54] L. Rossetto, R. Gasser, J. Lokoc, W. Bailer, K. Schoeffmann, B. Muenzer, T. Soucek, P. A. Nguyen, P. Bolettieri, A. Leibetseder, and S. Vrochidis, “Interactive video retrieval in the age of deep learning \- detailed evaluation of VBS 2019,” _T-MM_ , 2020, in press.
  * [55] N. Mithun, J. Li, F. Metze, and A. K. Roy-Chowdhury, “Joint embeddings with multimodal cues for video-text retrieval,” _International Journal of Multimedia Information Retrieval_ , vol. 8, no. 1, pp. 3–18, 2019.
  * [56] P.-Y. Huang, J. Liang, V. Vaibhav, X. Chang, and A. Hauptmann, “Informedia@TRECVID 2018: Ad-hoc video search with discrete and continuous representations,” in _TRECVID Workshop_ , 2018.
  * [57] X. Li, J. Ye, C. Xu, S. Yun, L. Zhang, X. Wang, R. Qian, and J. Dong, “Renmin University of China and Zhejiang Gongshang University at TRECVID 2019: Learn to search and describe videos,” in _TRECVID Workshop_ , 2019\.
  * [58] J. Liang, J. Chen, P. Huang, X. Li, L. Jiang, Z. Lan, P. Pan, H. Fan, Q. Jin, J. Sun _et al._ , “Informedia @ Trecvid 2016,” in _TRECVID Workshop_ , 2016.
  * [59] M. Bastan, X. Shi, J. Gu, Z. Heng, C. Zhuo, D. Sng, and A. Kot, “NTU ROSE lab at TRECVID 2018: Ad-hoc video search and video to text,” in _TRECVID Workshop_ , 2018.
  * [60] K. Ueki, T. Hori, and T. Kobayashi, “Waseda_Meisei_SoftBank at TRECVID 2019: Ad-hoc video search,” in _TRECVID Workshop_ , 2019.
  * [61] D. C. Koelma and C. G. M. Snoek, “Query understanding is key for zero-example video search,” in _TRECVID Workshop_ , 2017.

|  Xirong Li received the B.S. and M.E. degrees from Tsinghua University,
Beijing, China, in 2005 and 2007, respectively, and the Ph.D. degree from the
University of Amsterdam, Amsterdam, The Netherlands, in 2012, all in computer
science. He is currently an Associate Professor with the Key Lab of Data
Engineering and Knowledge Engineering, Renmin University of China, Beijing,
China. His research is multimedia intelligence. Dr. Li was recipient of the
ACMMM 2016 Grand Challenge Award, the ACM SIGMM Best Ph.D. Thesis Award 2013,
the IEEE TRANSACTIONS ON MULTIMEDIA Prize Paper Award 2012, and the Best Paper
Award of ACM CIVR 2010. He served as program co-chair of Multimedia Modeling
2021. He is associate editor of ACM TOMM and the Multimedia Systems journal.
---|---
|  Fangming Zhou received his B.S. degree in Nano Materials in Nanjing
University of Science and Technology, Nanjing, China in 2019. He is currently
a graduate student at School of Information, Renmin University of China,
pursuing his master degree on multimedia retrieval.
---|---
|  Chaoxi Xu received his B.S. and M.E. degrees in Computer Science from
Renmin University of China, Beijing, China, in 2017 and 2020, respectively. He
is currently an assistant engineer at the Institute of Computing Technology,
Chinese Academy of Sciences, Beijing, China.
---|---
|  Jiaqi Ji received his B.S degree in Software Engineering from Taiyuan
University of Technology, Taiyuan, China in 2019. He is currently a graduate
student at the School of Information, Renmin University of china, pursuing his
master degree on video retrieval.
---|---
|  Gang Yang received his Ph.D. degree in Innovative Life Science from
University of Toyama, Toyama, Japan in 2009. He is currently an Associate
Professor at School of Information, Renmin University of China, Beijing,
China. His research interests include computational intelligence, multimedia
computing and machine learning.
---|---


# Diffusion Maps : Using the Semigroup Property for Parameter Tuning

Shan Shan and Ingrid Daubechies

###### Abstract

Diffusion maps (DM) constitute a classic dimension reduction technique, for
data lying on or close to a (relatively) low-dimensional manifold embedded in
a much larger dimensional space. The DM procedure consists in constructing a
spectral parametrization for the manifold from simulated random walks or
diffusion paths on the data set. However, DM is hard to tune in practice. In
particular, the task to set a diffusion time $t$ when constructing the
diffusion kernel matrix is critical. We address this problem by using the
semigroup property of the diffusion operator. We propose a semigroup criterion
for picking the “right” value for $t$. Experiments show that this principled
approach is effective and robust.

Keywords Diffusion maps Diffusion operator Semigroup properties Manifold
learning Dimension reduction.

##  1 Introduction

Diffusion maps (DM) [4] are used in machine-learning to achieve dimension
reduction for data that are assumed to be sampled from a lower-dimensional
manifold within a higher-dimensional setting; they are related to other kernel
eigenmap methods such as Laplacian eigenmaps [1], local linear embedding [10],
Hessian eigenmaps [6] and local tangent space alignment [12].

The basic idea is simple: diffusion on a manifold is governed by the semigroup
generated by the manifold’s Laplace-Beltrami operator; the spectral analysis
of the diffusion operator thus provides information about the manifold that
can be used to provide a lower-dimensional parametrization for the data that
also removes “noise” from the data inconsistent with the manifold hypothesis.
One can (approximately) simulate a random walk or diffusion process on the
(unknown) manifold by taking small steps within the data set according to
probabilities estimated from the distances between data points. Indeed, if the
data points provide a sufficiently dense sampling of the manifold, then their
distances (measured in the high-dimensional ambient space) within a close
neighborhood of a fixed data point $P$ are close approximations to the
distances between the corresponding points within the pull-back of the
neighborhood to the tangent plane at $P$; the diffusion kernel on the manifold
can be likewise approximated (near $P$) by that on the tangent plane at $P$.
Since the diffusion kernel in a Euclidean space takes the same form (up to
normalization) regardless of the dimension, one can thus simply use the
distances in the ambient large-dimensional Euclidean space to generate a
reasonable approximation to the manifold diffusion kernel for short diffusion
times.

More precisely, suppose we are given a set of points
$\mathcal{D}=\\{y_{1},\dots,y_{N}\\}$ residing in high-dimensional Euclidean
space $\mathbb{R}^{K}$. To compute a low-dimensional representation of the
data with DM, we first construct a diffusion kernel matrix $W^{(t)}$,

$\displaystyle W^{(t)}_{ij}=\exp\left(-\frac{d^{2}(y_{i},y_{j})}{t}\right).$
(1)

Here, $d(\cdot,\cdot)$ is a distance metric on $\mathcal{D}$, for example as
defined by the $L_{2}$ norm $||\cdot||_{2}$ on $\mathbb{R}^{K}$, and $t$ is a
diffusion time parameter chosen by the user. (This parameter is the “short
time” from the hand-waving argument in the preceding paragraph.) Further
operations are typically carried out (see below) to correct for possible local
differences in e.g. sampling density within the data set. The resulting
discrete matrix is interpreted as an approximation to the diffusion kernel
(i.e. the kernel of the semigroup generated by the Laplace-Beltrami operator)
on the manifold assumed to underlie the data. The entries
$\left(\Psi_{\ell}\right)_{i};\,\ell=1,\ldots,L,\,i=1,\ldots N$ (with $L\ll
K$) of this matrix’s first few eigenvectors $\Psi_{\ell}$, sometimes suitably
weighted according to the eigenvalues $\lambda_{\ell}^{t}$, then provide an
$L$-dimensional parametrization for the data points $y_{i},\,i=1,\ldots N$.

This article is organized as follows. Section 2 gives a brief capsule
description of the algorithm for computing diffusion maps and its mathematical
interpretation. Section 3 discusses the sensitivity of the method to the
choice for $t$, illustrates the difficulty in guesstimating the “right” $t$,
and introduces the semigroup test as a criterion for determining a useful
value for $t$; we also give examples of using the semigroup test to the
problems of finding optimal data embedding on synthetic data and real image
data. Experiments show that this principled approach is effective and robust.

##  2 Diffusion operator and Diffusion maps: a brief recap

We present a very condensed summary; readers interested in more extensive
discussion of Riemannian manifolds can consult e.g. [3]; the basics of
Diffusion Maps can be found in [5].

###  2.1 Laplace Beltrami operator

We begin by defining the Laplace-Beltrami operator applied to a scalar
function $f:\mathcal{M}\rightarrow\mathbb{R}$ on a Riemannian manifold
$\mathcal{M}$; for simplicity we shall assume $\mathcal{M}$ to be compact,
without boundary.

Definition (Laplace-Beltrami) Let $\mathcal{M}$ be a Riemannian manifold with
a metric $g$. The Laplace-Beltrami operator on $\mathcal{M}$ is defined by

$\displaystyle\Delta_{\mathcal{M}}f(x)=-\text{Trace}\nabla^{\mathcal{M}}\nabla
f(x),$ (2)

where $\nabla^{\mathcal{M}}$ denotes the canonical Levi-Civita connection on
${\mathcal{M}}$ associated with $g$.

(In the case where $\mathcal{M}$ is a compact manifold with a smooth boundary,
one has to consider appropriate boundary conditions in order to define
$\nabla_{\mathcal{M}}$ as a self-adjoint operator.)

The spectrum of $\Delta_{\mathcal{M}}$ on a compact manifold $\mathcal{M}$ is
discrete. Let the eigenvalues be
$0=\gamma_{0}\leq\gamma_{1}\leq\gamma_{2}\leq\dots$ and let $f_{i}$ be the
eigenfunction corresponding to eigenvalue $\gamma_{i}$. Then the
eigenfunctions of the Laplace-Beltrami operator give rise to an embedding
operation with certain optimality properties.

An important observation (see e.g. [2]), is that $||\nabla f||$ provides us
with an estimate of how far apart $f$ maps nearby points. Let
$y_{i},y_{j}\in\mathcal{M}$; then

$\displaystyle|f(y_{i})-f(y_{j})|\leq\mbox{dist}_{\mathcal{M}}(y_{i},y_{j})||\nabla
f||+o(\mbox{dist}_{\mathcal{M}}(y_{i},y_{j})),$ (3)

indicating that points close together on the manifold are mapped by $f$ to
values close together in $\mathbb{R}$. The extent to which $f$ “preserves”
locality can be measured by e.g.

$\displaystyle\int_{\mathcal{M}}||\nabla f(y)||^{2}d_{vol_{\mathcal{M}}}y;$
(4)

minimizing this objective function is equivalent to finding eigenfunctions of
the Laplace Beltrami operator $\Delta_{\mathcal{M}}$, in the following sense.
The eigenfunction $f_{0}$ of $\Delta_{\mathcal{M}}$ with the lowest value for
(4) is a constant function on $\Delta_{\mathcal{M}}$ (for which $\nabla
f(y)=0$ for all $y$), which is completely uninformative concerning
localization of manifold points w.r.t. each other, since it maps all points to
the same value in $\mathbb{R}$. The next eigenfunction $f_{1}$ provides an
optimal embedding map to the real line (in the sense that it minimizes the
integral over $\mathcal{M}$ of the averaged distortion bound (4)); similarly,
the optimal embedding of the manifold in $\mathbb{R}^{L}$ is defined by

$\displaystyle\mathbf{g}:=\left(f_{1}(y),\dots,f_{L}(y)\right).$ (5)

###  2.2 Diffusion operator

Although the first $L$ eigenvectors of the Laplace-Beltrami operator provide
an informative embedding of $\mathcal{M}$ in $\mathbb{R}^{L}$, it can be
difficult to identify these eigenvectors with a reasonable degree of accuracy,
starting from noisy samples of $\mathcal{M}$. For this reason, it may be
useful, in order to determine (approximations to) these eigenvectors, to work
instead with the semigroup of operators
$\\{e^{-t\Delta_{\mathcal{M}}}\\}_{t\geq 0}$. The Laplace-Beltrami operator
$\Delta_{\mathcal{M}}$ is the infinitesimal generator of
$e^{-t\Delta_{\mathcal{M}}}$, i.e.,

$\displaystyle\lim_{t\rightarrow
0}\frac{I-e^{-t\Delta_{\mathcal{M}}}}{t}f=-\Delta_{\mathcal{M}}f,$ (6)

whenever $f$ belongs to a suitable dense subset of $C({\mathcal{M}})$. The
diffusion operators $\\{e^{-t\Delta_{\mathcal{M}}}\\}_{t>0}$ share the same
eigenfunctions as $\Delta_{\mathcal{M}}$, and the eigenvalues of
$e^{-t\Delta_{\mathcal{M}}}$ are exactly the $e^{-\gamma_{\ell}t}$; in
particular, they are bounded: $1=e^{-\gamma_{0}t}\geq e^{-\gamma_{1}t}\geq
e^{-\gamma_{2}t}\geq\dots>0.$

The Laplace-Beltrami operator $\Delta_{\mathcal{M}}$ and the diffusion
operator $e^{-t\Delta_{\mathcal{M}}}$ are also related through the heat (or
diffusion) equation on the manifold.

Definition (Heat Equation). Let $f:\mathcal{M}\rightarrow\mathbb{R}$ be the
initial temperature distribution on a manifold $\mathcal{M}$ embedded in
$\mathbb{R}^{K}$. The heat equation is the partial differential equation

$\displaystyle\begin{split}&\frac{\partial u}{\partial
t}+\Delta_{\mathcal{M}}u=0,\\\ &u(x,0)=f(x).\end{split}$ (7)

The solution of the heat equation is given by the diffusion operator
$e^{-t\Delta_{\mathcal{M}}}$,

$\displaystyle u(x,t)$ $\displaystyle=e^{-t\Delta_{\mathcal{M}}}f(x)$ (8)
$\displaystyle=\int_{\mathcal{M}}h_{t}(x,y)f(y)d_{vol_{\mathcal{M}}}y.$ (9)

In the integral from (9), $h_{t}$ is called the heat kernel. When $x,y$ are
close to each other and $t$ is small, $h_{t}$ can be approximated by the
Gaussian

$\displaystyle h_{t}(x,y)=(4\pi t)^{-\frac{d}{2}}e^{-\frac{||x-y||^{2}}{4t}},$
(10)

where $d$ is the dimension of $\mathcal{M}$.

###  2.3 Approximating the diffusion operator on a discrete dataset

On discrete data samples of $N$ data objects in $K$ dimensions, interpreted as
points of an unknown Riemannian manifold $\mathcal{M}$ embedded in
$\mathbb{R}^{K}$, an approximation of the diffusion operator
$e^{-t\Delta_{\mathcal{M}}}$ is built as follows. First, define the $N$ by $N$
matrix $W$,

$\displaystyle
W_{ij}=\begin{cases}e^{-\frac{||y_{i}-y_{j}||^{2}}{4t}}~{}~{}&\mbox{if}~{}||y_{i}-y_{j}||<\epsilon\\\
0~{}~{}&\mbox{otherwise}\end{cases}$ (11)

where $\epsilon$ is picked in concordance with $t$; typically $\epsilon$ is
proportional to $(Ct)^{1/2}$ for some $C$ significantly larger than 1; the
$W_{ij}$ set to zero thus correspond to entries that would otherwise be so
small that they would not contribute much to the overall matrix, while setting
them to zero alleviates the complexity of the algorithm. The action of the
true diffusion kernel, acting as an integral operator on the constant function
1 on ${\mathcal{M}}$, would produce the function 1 again; the discrete
approximation $W$ typically does not have the same effect on the all-ones
vector approximating the function 1. Many of the approximation ingredients
contribute to this shortcoming, such as setting some of the $W$-entries to
zero, or (more importantly) local variations in the data manifold sampling,
which result in some data points having more and/or closer neighbors than
others and which also cause the summing (rather than integration) procedure to
deviate from an optimal quadrature. To remedy the total effect of these
shortcomings to some extent, one defines a diagonal matrix
$D=[D_{ii}]_{i=1}^{N}$, with entries given by $D_{ii}=\sum_{j}W_{ij}$; the
matrix $D^{-1}W$ then does indeed map the all-ones vector to itself. (Note
that this also neatly sidesteps the problem that we had no estimate for the
dimension $d$ of $\mathcal{M}$, which would, in principle, have been necessary
for the normalization of the gaussian approximation to $h_{t}$.) We then
compute eigenvalues and eigenvectors for $D^{-1}W$, i.e.

$\displaystyle D^{-1}W\mathbf{f_{\ell}=\lambda_{\ell}\mathbf{f}_{\ell}},$ (12)

where we order the eigenvalues and eigenvectors so that
$1=\lambda_{0}\geq\lambda_{1}\geq\lambda_{2}\geq\ldots~{}$. The
$k$-dimensional embedding is then defined by

$\displaystyle\mathbf{g}_{i}=(\mathbf{f}^{[i]}_{1},\dots,\mathbf{f}^{[i]}_{L}),$
(13)

where $\mathbf{f}^{[i]}_{\ell}$ is the $i$-th entry in the $N$-dimensional
$\ell$-th eigenvector.

Figure 1 illustrates this embedding on a simple example. The dataset consists
of points residing on a helix wrapped around a torus, and shows the 2D
embeddings obtained by Laplacian eigenmaps and diffusion maps, comparing them
with those from PCA and MDS; Laplacian-based methods clearly do the better job
recovering the intrinsic data structure – in this example, PCA and MDS
essentially give results similar to a linear projection onto a 2D-plane.

Figure 1: (a) Original data points, uniformly sampled (with some noise added)
from a helicoidal curve wrapped around a torus in 3D. (We note that although
we show the data embedded in a low-dimensional space in all our examples, the
size of the ambient dimension has no impact on these methods, since they
depend only on the distances between data points.)
Smaller panels: 2D embeddings of these data obtained via (b) PCA, (c) MDS, (d)
Laplacian eigenmaps, and (e) Diffusion eigenmaps

In a second example the data are sampled uniformly (without added noise) from
a 2D “Swiss roll” surface (a rectangle rolled up so that it forms a spiral –
see Fig. 2(a)) embedded in 3D. Figure 2 compares the embeddings produced by
Laplacian eigenmaps and by Diffusion maps, showing that Diffusion maps
introduce fewer deformations.

Figure 2: Left: orginal Swiss roll data; Middle and Right: 2D Embeddings
obtained via Laplacian eigenmaps and Diffusion maps, respectively.

Remarks
1\. The same “normalization by left-multiplication by a diagonal matrix”
approach can be (and has been) used for the Laplace-Beltrami operator
$\Delta_{\mathcal{M}}$ rather than $e^{-t\Delta_{\mathcal{M}}}$; approximating
the differential operator by a matrix $L$ expressing a second-order
difference, and then “normalizing” it by setting $D^{-1}L$, leads to the
Laplacian eigenmaps proposed in [2].

2\. Although the matrix $W$ is symmetric, the “normalized” version $D^{-1}W$
typically isn’t. One can also consider instead the symmetrized version
$D^{-1/2}WD^{-1/2}$, which has the same eigenvalues as $D^{-1}W$; its
eigenvectors are the vectors $D^{1/2}\mathbf{f}_{\ell}$.

3\. In case the sampling density is known to be systematically not uniform
over the manifold, it can be useful to introduce a correction for this in the
matrix construction. The paper [4] describes in detail how one can modify the
construction to incorporate (an approximation to) the sampling density.
Depending on the value assigned to a tuning parameter $\alpha$, the
modification introduced in [4] can be interpreted (when $\alpha=1$) as
introducing a Jacobian-like factor (so that, in the limit for finer and finer
sampling, one recovers again the standard diffusion semi-group and its
Laplace-Beltrami generator), or (when $\alpha\neq 1$) as an adjustment of the
diffusion process itself, with a non-constant diffusivity; in the latter case,
the approximation is linked to a different semigroup, the eigenvectors and
eigenvalues of which encode again significant geometric information about the
manifold, and can therefore again be used for a lower-dimensional
parametrization of the manifold.

##  3 Setting the diffusion time $t$

###  3.1 Sensitivity to the choice of $t$

It is intuitively clear that the algorithm described earlier can work only in
some window for $t$: if $t$ is chosen very large, then $W_{ij}$ will be
different from zero even for pairs $i,\,j$ for which the data points $y_{i}$
and $y_{j}$ are far from each other in the ambient space, although we expect
that their Euclidean distance is not at all informative about their relative
roles on the manifold $\mathcal{M}$. We argued in Section 2 that the
construction of $\left(W_{t}\right)_{ij}$ (where we now explicitly denote the
dependence of $W$ on $t$) was reasonable for $i,\,j$ where the distance
$\|y_{i}-y_{j}\|$ was sufficiently small that $y_{j}$ could be viewed as close
to the tangent plane to $\mathcal{M}$ at $y_{i}$; this means we should expect
the method to work well only for $t$ below some threshold. This is also
consistent with the proofs in [5] and [4]: since those are proofs holding for
$t\longrightarrow 0$, the similarity of the eigendecompositions of $W_{t}$ and
the true diffusion operator $e^{-t\Delta_{\mathcal{M}}}$ on $\mathcal{M}$ can
be expected only in the regime of small $t$.

When $t$ is too small, the method faces a different problem: for
$t<\min_{i\neq j}\|y_{i}-y_{j}\|^{2}$, $W$ reduces to the identity operator,
and no useful embedding can be constructed. The problem persists for slightly
larger values of $t$, where only a few $(i,j)$ emerge above the threshold. In
a certain sense, the diffusion time is then too short for the diffusion
process to consistently bridge the distance between sample points on
$\mathcal{M}$. Ideally, one would like that for each $i$,
$\left(W_{t}\right)_{ij}\neq 0$ for several $j\neq i$. (One would also like
the number of such “useful” neighbors not to vary by orders of magnitude over
the dataset. This is possible only if the sampling is fairly uniform. It is
when the spatial distribution of the points in the dataset varies so much that
no single parameter setting in the definition of $W_{t}$ allows for the number
$\\#\\{j\neq i;\,\left(W_{t}\right)_{ij}\neq 0\\}$ to be at least (say) 10 for
all $i$ without getting into the several 100s for other $i$, that it is
necessary to adapt the simple diffusion operator $W_{t}$, e.g. using the
methods in [4].)

Finding the “right” choice for $t$, in the happy medium between the two
extreme regimes, can be tricky: as illustrated in Figures 3 and 4 below,
different choices for $t$ can lead to very different outcomes for the same
data.

Figure 3: Three embeddings of the helicoidal data from Figure 1 obtained via
Diffusion maps, for different choices for the parameter $t$: $t_{1}$ (left),
$t_{2}$ (middle) and $t_{3}$ (right). The choice $t=t_{2}$ was adopted for
Fig.1(e); the choices $t=t_{1}=t_{2}/16$ and $t=t_{3}=4t_{2}$ are clearly
suboptimal. Figure 4: Several embeddings of the Swiss roll data from Fig. 2
obtained by the Diffusion map procedure of Section 2; the only difference lies
in the choice of the parameter $t$, increasing from left to right in the
figure by a factor 2 each time.

###  3.2 Semigroup test

In practical applications of Diffusion maps, it can take quite a bit of trial
and error to find a “right” value for $t$. Our goal here is to describe a
simple robust guiding strategy to reduce this guesswork, which finds a near-
optimal value for $t$ in many situations in which we have tested it.

The diffusion operators $\\{e^{-t\Delta_{\mathcal{M}}}\\}_{t>0}$ form a
strongly continuous semigroup; i.e. the $T_{t}:=e^{-t\Delta_{\mathcal{M}}}$
satisfy

$\displaystyle T_{t_{1}+t_{2}}=T_{t_{1}}T_{t_{2}}\,,~{}\mbox{ and
}s\mbox{-}\\!\lim_{t\rightarrow 0}T_{t}=\mbox{Id}~{}.$ (14)

It follows that the matrices $D_{t}^{-1}W_{t}$, used to define diffusion maps,
or their symmetrized versions $K_{t}:=D_{t}^{-1/2}W_{t}D_{t}^{-1/2}$, can be
approximate, discretized versions of the diffusion operators on $\mathcal{M}$
only when they likewise (approximately) satisfy the semigroup property.

We use this insight to formulate a criterion to pick an “optimal” $t$. In the
regime where the $K_{t}$-operators are reasonable approximations of the
semigroup $\\{e^{-t\Delta_{\mathcal{M}}}\\}_{t\geq 0}$,
$\left(K_{t}\right)^{2}$ should be close to $K_{2t}$. This motivates the
definition of the semi-group error $\mbox{(SGE)}(t)$,

$\displaystyle\text{SGE}(t):=\|\left(K_{t}\right)^{2}-K_{2t}\|.$ (15)

The norm used here is the operator norm; the operators we consider are
(expected to be) positive, with eigenvalues between 0 and 1, and the range for
SGE$(t)$ is between 0 and 1.

In practice, we begin with initializing a wide range of discrete values for
$t$, i.e. we pick a set $T:=\\{t_{m}\,;\,m=1,\ldots M\\}$. For each $t_{m}$ in
$T$, we construct the diffusion matrices $\left(K_{t_{m}}\right)^{2}$ and
$K_{2t_{m}}$, and we compute $\mbox{(SGE)}({t_{m}})$.

Figure 5 below plots the semi-group error SGE$(t)$ for different values of $t$
for the Swiss roll example of Figures 2 and 4; SGE$(t)$ reaches its lowest
value for the choice of $t$ where the 2D-embedding is closest to a rectangle,
which we know to be the ground truth in this case.

Figure 5: Semi-group error SGE for the Swiss roll data, for the values of $t$
illustrated in Figure 3. The red dot is the optimal value of $t$, and
corresponds to the embedding that visually best reflects the ground truth. The
scale for $t$ is logarithmic; each of the successive $t_{m}$ (at the tick
marks) is larger by factor 2 than the previous one, $t_{m+1}=2\,t_{m}$.

In Figure 6, below, we revisit the three embeddings shown in Figure 3, next to
the semi-group error plot for this dataset, and we observe that the visually
optimal embedding (which is also the most accurate version of the ground truth
for this manifold $\mathcal{M}$) corresponds again to the value of $t$ with
the smallest SGE in the regime of small diffusion times.

Figure 6: Semi-group error plot for a wide range of candidate values for $t$ –
the ratio $t_{\max}/t_{\min}$ equals $2^{20}$ ! – for the dataset illustrated
in Figures 1 and 3. Note that for very large $t$, the SGE estimate becomes
small again – see discussion in the text.

As shown in Figure 6, the values of SGE$(t)$ behave qualitatively as we would
have expected, based on the intuition explained at the start of this section:
when $t$ is very small, the semigroup behavior of the $K_{t}$ hasn’t “kicked
in” yet, because the numerical diffusion’s range is too short, and this is
reflected by larger values for SGE$(t)$. (We recall that the range of SGE
values is between 0 and 1; values exceeding .3 are indeed “large”.) As $t$
increases, SGE$(t)$ drops to lower values, to start increasing again after a
minimum SGE-value not too far above 0. (These small values are maintained in
an interval for $t$, as may not be evident from Figure 6, in which the
successive values of $t$ increase by a factor 4, $t_{m+1}=4\,t_{m}$; detailed
behavior in the neighborhood of each $t_{m}$ is not apparent from this
figure.) We interpret this increase as the influence of ambient-space geometry
(such as the toroidal winding in this example), once the numerical diffusion
is no longer “following” the manifold $\mathcal{M}$; because even noisy
sampling from $\mathcal{M}$ translates to very non-uniform sampling in the
higher-dimensional ambient space, the $K_{t}$ are less close to following a
semi-group behavior. When $t$ increases further, the value of SGE$(t)$ starts
decreasing again: once the reach of the numerical diffusion is sufficiently
large that the “sources” on or near $\mathcal{M}$ all “act” as one diffuse
blob, and the geometry of $\mathcal{M}$ has been obscured, the semigroup
nature of the ambient-space diffusion takes over. Although SGE$(t)$ is small
again, one cannot use these diffusion maps to generate an informative low-
dimensional embedding of $\mathcal{M}$ for $t$ in this range.

We next turn to a few examples with non-uniform sampling. In this case we
compensate for the change in sampling density by using the techniques
described in [4], using an integral kernel $A_{t,\alpha}$ obtained by a
“renormalization” of $W_{t}$. Regardless of the parameter setting for $\alpha$
that gives the best results (which depends on the type of non-uniformity), the
basic intuition underlying the method remains the same: the spectral analysis,
used to construct a low-dimensional embedding of $\mathcal{M}$, is predicated
on the $A_{t,\alpha}$ approximating the kernels of a semigroup of operators.
One can thus again use the SGE to determine optimal choices of $t$. Figure 7
shows the results for a non-uniformly sampled circle.

Figure 7: Left: 512 non-uniformly sampled points on a circle; Middle: SGE$(t)$
for a wide range of $t$ values, with the useful-range optimal $t$ marked in
red; Upper right inset: the embeddings obtained for the optimal $t=1/4$ and
for $t=1/16$ (left) and $t=1$ (right). In this example, we set $\alpha=2$ to
determine the adapted kernels $A_{t,\alpha}$. (In this case, there is hardly
any dimension reduction, since both the original and final circle are depicted
on a 2D plane; this is a toy example, after all. It may be worth noting that
the parametrization by Diffusion maps would have been identical had the data
been embedded in a random not-coordinate-aligned plane in a much higher
dimensional space.) Figure 8: Left: 512 non-uniformly sampled points on a
circle, now with noise added; Middle: SGE$(t)$ for a wide range of $t$ values,
with the useful-range optimal $t$ marked in red; Upper right inset: the
embeddings obtained for the optimal $t=1/4$, as well as for $t=1/16$ (left)
and $t=1$ (right). In this case, we have again set $\alpha=2$ to determine the
adapted kernels $A_{t,\alpha}$.

To illustrate the robustness of our the SGE test, we examine this dataset
again after noise has been added. The results are shown in Figure 8.

After the simulated toy data examples, we conclude with one example of real
data.

The dataset is part of the extended Yale Face Database B [7]; it consists of
64 images (192 pixels by 168 pixels) of the same human face, in the same pose,
under different illumination conditions: the light source is moved around in
two different directions. The intrinsic dimensionality of this collection of
images is therefore expected to be 2, although the images themselves are
objects in a much higher-dimensional space. We applied Diffusion maps, coupled
with the semigroup-error tuning strategy described above, to this collection;
the results are shown in Figure 9. By its very nature, the dataset in this
example is noisy, since all photographs (as opposed to images generated by
computer graphics) are inherently noisy, but we don’t have an explicit
chracterization of this noise. To illustrate robustness of our analysis and
semigroup criterion to noise, we resort to a common strategy in image
analysis: we revisit the dataset in Figure 10, after extra noise has been
added independently to each of the 64 images.

To add noise to the datapoints, from Figure 9 to Figure 10, we proceeded as
follows. For each of the $192\times 168$ pixels in each of the 64 images, we
generated a random integer $I$ uniformly in $[-100,100]$; we then replaced the
pixel value $P$ by $P+I$ if $0<P+I<255$, by 0 if $P+I<0$ or by 255 if
$P+I>255$. An example of one of the face photographs, before and after adding
noise, is shown in Figure 11 below.

Despite the severity of the noise, we observe that the Diffusion Map analysis,
combined with the semigroup tuning strategy, is remarkably robust: the same
$t_{\mbox{\tiny{opt}}}$ is selected in both cases, and the corresponding 2D
embeddings are very similar (up to an inversion of the axis in one of the 2
variables), as illustrated by Figure 12 below.

Figure 9: DM with the semigroup tuning strategy applied to the Yale Face
dataset, in which each data point is an image of $192\times 168$ pixels. Top
left: SGE$(t)$ for a wide range of $t$. The colored boxes above show the
embeddings using the first 3 non-trivial eigenvectors for the optimal choice
$t_{\mbox{\tiny{opt}}}=1/4$ and its two SGE-plot neighbors
$t_{-4}=t_{\mbox{\tiny{opt}}}/4$ and $t_{0}=4\,t_{\mbox{\tiny{opt}}}$.
Although the embedding for $t_{-4}$ looks comparable to that for
$t_{\mbox{\tiny{opt}}}$ at first sight, the embedding shows that one data
point is not integrated well with the rest (boxed green datapoint near one of
the axes); for $t_{0}$ the structure of the dataset is much less well-defined
than for $t_{\mbox{\tiny{opt}}}$. Left: 2-dimensional DM embedding for
$t_{\mbox{\tiny{opt}}}$, with the datapoints indicated by thumbprints of the
images, indicating that the DM parametrization captured the illumination
degrees of freedom in the dataset. (In this case, we set $\alpha=1.5$ to
determine the adapted kernels.) Figure 10: DM with the semigroup tuning
strategy applied to the same Yale Face dataset as in Figure 9, after
additional noise was added to each image of $192\times 168$ pixels, i.e. to
each data point. (The nature of the noise is explained below and illustrated
in Figure 11.) Top left: SGE$(t)$ for a wide range of $t$. The colored boxes
above show the embeddings using the first 3 non-trivial eigenvectors for the
optimal choice $t_{\mbox{\tiny{opt}}}=1/4$ and its two SGE-plot neighbors
$t_{-4}=t_{\mbox{\tiny{opt}}}/4$ and $t_{0}=4\,t_{\mbox{\tiny{opt}}}$. Left:
2-dimensional DM embedding for $t_{\mbox{\tiny{opt}}}$, with the datapoints
indicated by thumbprints of the images. (We again set $\alpha=1.5$ to
determine the adapted kernels.) Figure 11: Left: one of the 64 images from the
Yale Face dataset used in the analysis in Figure 9; Right: the noisy version
of this image obtained by adding, pixelwise, random integers picked uniformly
and independently in [-100,100] to the gray value of the pixel, and rounding
so the result is in [0,225]. Figure 12: Left and Middle: the 2D embeddings
from Figures 9 and 10, respectively, for the 64-face Yale Face dataset without
and with the added noise illustrated in Figure 11. Up to a change of sign in
the horizontal axis, the two embeddings are remarkably similar, as illustrated
by the figure on the Right, which superimposes onto the Middle embedding a
“skeleton” of the other embedding, indicating with a green rectangle the
mirrored position of each thumbprint from the Left embedding. Closer scrutiny
shows that thumbprints in close geometric proximity in this comparison picture
do indeed correspond to the same face picture.

##  4 Conclusion

Although Diffusion maps have shown to be a powerful tool to explore datasets
embedded in high dimensions that are suspected to have interesting geometric
structure on a much lower-dimensional scale [8][11][9], determining the
“right” value for the diffusion parameter $t$ has been found to be tricky.
Picking $t$ so that it minimizes the Semi-Group Error is computationally easy,
makes sense from a theoretical point of view, and gives good results in
practice.

## References

  * [1] M. Belkin and P. Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  Neural computation, 15(6):1373–1396, 2003.
  * [2] M. Belkin and P. Niyogi.  Towards a theoretical foundation for laplacian-based manifold methods.  Journal of Computer and System Sciences, 74(8):1289–1308, 2008\.
  * [3] W. M. Boothby and W. M. Boothby.  An introduction to differentiable manifolds and Riemannian geometry, Revised, volume 120.  Gulf Professional Publishing, 2003.
  * [4] R. R. Coifman and S. Lafon.  Diffusion maps.  Applied and computational harmonic analysis, 21(1):5–30, 2006.
  * [5] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker.  Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps.  Proceedings of the national academy of sciences, 102(21):7426–7431, 2005.
  * [6] D. L. Donoho and C. Grimes.  Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data.  Proceedings of the National Academy of Sciences, 100(10):5591–5596, 2003.
  * [7] A. S. Georghiades, P. N. Belhumeur, and D. J. Kriegman.  From few to many: Illumination cone models for face recognition under variable lighting and pose.  IEEE transactions on pattern analysis and machine intelligence, 23(6):643–660, 2001.
  * [8] J. Liu, Y. Yang, and M. Shah.  Learning semantic visual vocabularies using diffusion distance.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 461–468. IEEE, 2009.
  * [9] K. R. Moon, D. van Dijk, Z. Wang, S. Gigante, D. B. Burkhardt, W. S. Chen, K. Yim, A. v. d. Elzen, M. J. Hirn, R. R. Coifman, et al.  Visualizing structure and transitions in high-dimensional biological data.  Nature biotechnology, 37(12):1482–1492, 2019.
  * [10] S. T. Roweis and L. K. Saul.  Nonlinear dimensionality reduction by locally linear embedding.  Science, 290(5500):2323–2326, 2000.
  * [11] D. Van Dijk, R. Sharma, J. Nainys, K. Yim, P. Kathail, A. J. Carr, C. Burdziak, K. R. Moon, C. L. Chaffer, D. Pattabiraman, et al.  Recovering gene interactions from single-cell data using data diffusion.  Cell, 174(3):716–729, 2018.
  * [12] T. Zhang, J. Yang, D. Zhao, and X. Ge.  Linear local tangent space alignment and application to face recognition.  Neurocomputing, 70(7-9):1547–1553, 2007.