11institutetext:  Dept. of Comp. Sci. and Engg., Indian Institute of
Technology Kharagpur, India
22institutetext: Verimag, Univ. Grenoble Alpes, France

# Quantitative Corner Case Feature Analysis of Hybrid Automata with ForFETSMT

Antonio Anastasio Bruto da Costa 11 Pallab Dasgupta 11 Nikolaos Kekatos 22

###### Abstract

The analysis and verification of hybrid automata (HA) models against rich
formal properties can be a challenging task. Existing methods and tools can
mainly reason whether a given property is satisfied or violated. However, such
qualitative answers might not provide sufficient information about the model
behaviors. This paper presents the ForFETSMT tool which can be used to reason
quantitatively about such properties. It employs _feature automata_ and can
evaluate quantitative property corners of HA. ForFETSMT uses two third-party
formal verification tools as its backbone: the SpaceEx reachability tool and
the SMT solver dReach/dReal. Herein, we describe the design and implementation
of ForFETSMT and present its functionalities and modules. To improve the
usability of the tool for non-expert users, we also provide a list of
quantitative property templates.

##  1 Introduction

Formal verification techniques can provide guarantees of correctness and
performance for hybrid and cyber-physical systems. Nowadays, they are
supported by several robust verification tools, e.g. SpaceEx [11],
dReal/dReach [13]. A common modeling formalism for the design of such systems
is _hybrid automata_ [2] (HA). HA can exhibit non-deterministic behaviors and
have been used to model control systems and analog mixed-signal circuit
designs [4, 9]. Formalizing specifications of hybrid automata such that they
can be verified automatically is not an easy task, especially in an industrial
setting.

There is a semantic mismatch between industrial requirements and formal
specifications. Typically, industrial requirements are described in natural
language _"The caliper speed at contact must be below 2 mm/s"_ , while formal
specifications are expressed in a formal language, like temporal logic (TL),
e.g. $\square(q\rightarrow(\square p))$ with $p:=\\{speed<=2mm/s\\}$ and
$q:=\\{\text{caliper at contact}\\}$.

Standard analysis tools [11] can answer reachability questions and can verify
if given safety properties are satisfied. For more complex properties, one has
to construct a monitor automaton and take its product with the HA [12, 14]. In
practice, however, the resulting automaton can be large, resulting in long
analysis times and scalability issues. In addition, the answer provided by the
tool is qualitative, i.e. yes or no. It is not possible to support
quantitative measures, e.g. by what extent was the specification violated? In
addition, describing common system properties requires the ability to express
quantitative measures such as overshoot, settling time, or other timing and
value quantities.

There are two directions to address this limitation. On the one hand, it is
possible to use temporal logic. Much literature exists on TL, especially on
Linear Temporal Logic (LTL) [18]. Languages such as MITL [3], STL [15] and its
extensions such as xSTL [17] have been used for specifying specifications
involving continuous signals. Some TL languages support the use of robustness
metrics over properties [10]. Such metrics measure the distance of runs of the
system from unsafe regions defined by the property. However, these languages
are primarily designed to express specification correctness, and it can be
tedious to use them to express quantitative measures.

The other direction is to use features [1]. Unlike temporal logics like MITL
or STL, the language of features is designed to explicitly specify
quantitative measures. The quantity is expressed as a computation resulting
from matching a behaviour description. ForFET [6] is a tool for computing an
over-approximation for features, where the evaluation of a feature, written in
the Feature Indented Assertion (FIA) language, over runs of a HA is automated.

In a quantitative analysis, knowledge of the stimulus that produces the best
and worst-case quantity (minimum or maximum) provides insight into the system
and on how to modify the design to more robustly adhere to specifications. The
tool ForFETSMT addresses the needs described above, extending ForFET, with the
following:

  * •

Feature corner analysis using SMT. Using SMT has two advantages, it allows us
to refine the feature range beyond what ForFET produces, and also enables us
to generate a witness trace describing the stimulus and behaviour for best and
worst-case quantities.

  * •

Support for parameterized features and an extended language for features
having mixed urgent and non-urgent semantics.

  * •

Usability and support: i) two translators, written in Matlab and Octave, for
converting models from SpaceEx formalism to ForFET’s modeling language, ii)
support for custom paths for workspace, models, and third-party tools.

##  2 Design and Implementation

module buck(v,i,t) output v,i,t; parameter Vr = 12, ... , b1c = 0, T = 1e-05,
D = 0.51667; mode closed begin ddt t = 1; ddt v = (a10c*i + a11c*v + b1c*Vs);
ddt i = (a00c*i + a01c*v + b0c*Vs); end ... property inv closed mode==closed
|=> t<=D * T && t>=0; endproperty

property trans closed_open mode==closed && mode’==open && t>=D*T |=> i’==i &&
t’==0 && v’==v; endproperty ... initial begin set begin mode == closed; i ==
0; v == 0; t == 0; end end endmodule

feature settlingTime(Vr,E); begin var st; (v>=Vr+E) ##[0:$] @+(state==Open) &&
(v<=Vr+E), st=$time ##[0:$] @+(state==Open) && (v<=Vr+E) |-> settlingTime =
st; end

Figure 1: HA of the Buck Regulator, HASLAC Code-snippet of HA description,
Quantitative Specification of Settling Time as a feature.

We begin with a running example, as shown in Figure 1, to explain the inputs
to ForFET${}^{SMT}.$ The example is of a buck regulator taken from standard
benchmarks [16]. The regulator receives an input voltage, and in the event of
reasonably varying loads ensures that it provides an unchanging output
voltage.

###  2.0.1 Hybrid Automaton Description in HASLAC

An input to the tool is the HA description. The HA of the buck regulator has
two locations, open and closed, indicating the state of the switch that
charges the capacitor of the regulator.

The description of the HA is specified in the Hybrid Automaton Specification
Language for Analog Mixed-Signal (AMS) Circuits (HASLAC), as the model
description language for ForFET and ForFETSMT. HASLAC is specially designed to
mimic semiconductor circuit behavioural model description languages such as
Verilong-AMS, to make adoption of formal analysis in the semiconductor circuit
design flow less intimidating. HASLAC describes each location of the HA as a
mode, with each transition and invariant expressed as a property. In the model
description, v and i are aliases for the HA variables ${\tt x_{1}}$ and ${\tt
x_{2}}$.

###  2.0.2 Quantitative Specification using Features

A feature defines, formally, a quantitative specification, i.e. a measurement
over behaviours of the system. Unlike properties, which either match or fail,
having a Boolean outcome, the outcome of evaluating a feature is a real-valued
interval. The language of features is easier to use and understand for non-
experts, especially in the AMS domain, and it can be evaluated with the use of
reachability tools.

In our example, the intent to measure the time taken for the output voltage to
settle into a stable state can be expressed as the feature settlingTime. The
feature contains three core components: (i) a set of behaviours over which
measurements are made, (ii) variables, local to a feature, that may be
assigned values in the antecedent, as a matching behaviour is observed, and
(iii) the feature compute expression, over local variables, evaluated once the
behaviour has matched. The behaviour described by the feature in Figure 1
reads as follows, "(v<=Vr+E) is true and thereafter v settles below (Vr+E) for
two successive openings of the capacitor switch". The expressions (v>=Vr+E)
and (v<=Vr+E) are predicates over real-variables (PORVs). state is a special
variable allowing us to write predicates over the location labels of the HA.
The construct @+(P) represents an event, and is true only on the positive edge
of the predicate P. A behaviour in the feature expresses a sequence of Boolean
expressions over PORVs and events separated by time-delays. The statement "P
##[a:b] Q" is true whenever Q occurs within a time interval of a and b from
when P is true; $a,b\in\mathbb{R}^{+}$, $b\geq a$. The syntax ##[a:b]
represents a time-delay. The symbol $ represents the notion "anytime after a".
Observe that P can be true over a dense time interval, and for each point in
the interval where "P ##[a:b]" is true, Q can be true yielding an infinite
number of matches. A more complete description of the language for features is
available in [7].

###### Remark 1

A feature behaviour may match in one or multiple (potentially infinite) runs
of the HA, at one or multiple (potentially infinite) time-points. Each match
has the potential to yield a different feature value. Evaluating a feature
over runs of a HA, therefore, yields an interval
$[\mathcal{F}_{min},\mathcal{F}_{max}]$ of feature values. We call this a
feature range.

###  2.0.3 Algorithm

A functional overview of ForFETSMT is shown in Figure 2. The tool ForFET is
marked within a blue box. ForFETSMT extends ForFET by introducing an iterative
refinement step that refines the range provided by ForFET. It also introduces
a wrapper around the SMT solver dReal in order to correctly visualize a trace
that acts as a witness for each corner of the feature range.

The tool works as follows. The user provides two inputs (Step 1): a hybrid
automaton model $\mathcal{H}$ and a feature specification $\mathcal{F}$
(single or a set of features), ForFETSMT computes the product automaton (Step
2) according to [7]. Step 3 involves using SpaceEx [11] to compute reach-sets
for the transformed model $\mathcal{H}_{F}$. This results in a feature range
$[\mathcal{F}_{min},\mathcal{F}_{max}]$ computed as an evaluation of the
feature expression on the runs matching the feature sequence-expression (Step
4). The feature range is refined iteratively through a search using an SMT
solver (Steps 4 to 7).

(a) Functional Overview

(b) SMT Feature Refinement

(c) Computing the left corner

Figure 2: ForFETSMT: Corner Case Analysis

HyST [5] converter is used internally to translate the model $\mathcal{H}_{f}$
into an acceptable format for use with dReach. In each interaction, called a
query, between our tool and dReach, a goal statement is constructed to direct
dReach to prove the existence/non-existence of a feature value in a given
domain. Each query in Step 5 includes the model description for
$\mathcal{H}_{f}$, a goal statement, and a maximum transition hop count $K$,
which is translated by dReach into SMT clauses. The response of the SMT solver
(Step 6) is either unsatisfiable or satisfiable. In the latter case, a single
timed trace of the HA is made available. dReal generates a trace as a JSON
file with time-stamped valuations for the variables of the automaton, which is
parsed to identify the feature values for the trace. The search concludes in
Step 7 with a refined feature range
$[\mathcal{F}^{*}_{min},\mathcal{F}^{*}_{max}]$ as well as a trace
corresponding to each feature range corner value.

###  2.0.4 Implementation

ForFETSMT is implemented in C/C++. The parsers for features and the HASLAC
language are implemented in flex and bison, which are translated into C/C++.
The language was chosen due to its efficiency for handling complex operations
and data-structures involved in computing the product automaton of the HA and
feature monitor.

We represent the algorithm as a function which takes the HA and the feature as
inputs, and produces a range of feature values
$[\mathcal{F}^{*}_{min},\mathcal{F}^{*}_{max}]$ as output along with a trace
that acts as a witness for each extremal corner of the range. The algorithm is
guaranteed to terminate for bounded time traces [7]. As such, it constitutes a
procedure for computing feature ranges over bounded time horizons, which is
expected in practice.

###  2.0.5 Challenges using dReal

In general, HA use urgent locations to represent ordered discrete
transformations. In a trace, dReal provides a series of indexed time-ordered
tuples representing a trace satisfying the query. In our experience, when the
model $\mathcal{H}_{f}$ contains urgent locations, dReal generates a NULL
tuple representing a visit to an urgent location. Visualization tools provided
by the authors of dReal do not support drawing traces containing a NULL tuple.
To enable visualization for all traces generated by dReal, ForFETSMT post-
processes traces generated by dReal. It eliminates all NULL tuples and re-
indexes them to be consistent with the syntax expected by the visualization
tool.

###  2.0.6 Support for SpaceEx Models

The SpaceEx modeling language has become the quasi-standard interchange format
for defining and describing HA in the formal verification community [4]. It
offers a graphical user interface, respects the SX grammar [8] and the models
are written as XML files. ForFETSMT accepts HA models written in HASLAC. To
bridge this mismatch and facilitate the use of ForFETSMT with existing SpaceEx
models and HA benchmarks, we provide two translators, written in MATLAB and
Octave respectively. The translators require a SpaceEx model (necessary) and a
configuration file (optional). They come with an XML parser (partly written in
Java) and perform syntactic translation while also handling modeling
differences. Note that there exist other converters tailored to hybrid
automata and SpaceEx, e.g. HyST [5].

##  3 Installation and Usage

###  3.0.1 Installation

The ForFETSMT tool is available at a public GitHub repository. The repository
may be cloned in full using the following command:

git clone https://github.com/antoniobruto/ForFET2.git

The tool is written in C/C++. Before building the tool, one needs to have g++,
flex, bison, glib-2.0, json-glib-1.0 and C/C++ standard libraries for 32 bit
binaries (ia32-libs on Ubuntu 10.04 and later).

The tool can be compiled by running ./buildForFET.sh in the cloned directory.
One must also ensure that
SpaceEx111http://spaceex.imag.fr/sites/default/files/downloads/private/spaceex_exe-0.9.8f.tar.gz
and the SMT translator and solver
dReach222https://github.com/dreal/dreal3/releases and
dReal${}^{\ref{dRealLink}}$ are installed and executable in the user’s path.
The tool also uses the HA translator HyST (provided with ForFETSMT) which
requires a java run-time environment to be installed.

###  3.0.2 Usage

The compiled ForFETSMT tool can be interacted with through the command line.
Once compiled, the tool binary resides within the forFET directory as the
binary forFET. Standard invocation involves executing the binary with a
configuration file, by running ./forFET CONFIG-FILE-NAME. The configuration
file specifies where third party libraries may be found. An example
configuration file is provided in forFET/default.cfg.

##  4 Experimental Evaluation

In this Section, we present selected results on three models, provided with
ForFETSMT, i.e. a battery charger, a cruise control, and a buck regulator. We
tested a wide variety of features, capturing state-dependent, time-dependent,
sequential-properties and combinations of them. Some of these properties can
also be encoded as control specifications, e.g. overshoot or settling time.
More details about the models, specifications, features, and analysis results
can be found in the tool manual. For each model, the feature range is computed
first using SpaceEx and is then refined using SMT. Our observations show that,
except in one case, reachability analysis and SMT require similar time to
compute the expected feature range. The exception is when the model switches
location often, like the Buck Regulator. In these cases, SMT might be more
vulnerable to the state-space explosion. However, the additional computation
overhead leads to tighter feature ranges.

##  5 Concluding Remarks

In this paper, we have presented the tool, ForFETSMT, that is a formal feature
evaluation tool for hybrid automata (HA), emphasizing on its architecture and
utilities. Features form a promising and practical research direction as they
can be used on top of or alongside standard monitoring and hybrid reachability
tools to provide quantitative measures about HA behaviors. ForFETSMT makes use
of the HASLAC language for writing HA models and is linked to SpaceEx
reachability tool and dReal/dReach SMT solver. Using such an SMT solver to
compute features can produce concrete traces for feature corner points and
lead to the generation of tighter feature ranges. The traces for corners of
the feature range can provide insights that guide experts to refine their
designs.

## References

  * [1] A. Ain, A. Bruto da Costa, and P. Dasgupta.  Feature indented assertions for analog and mixed-signal validation.  IEEE TCAD, PP(99):1–1, 2016.
  * [2] R. Alur et al.  The algorithmic analysis of hybrid systems.  Theoretical Computer Science, 138:3–34, 1995.
  * [3] R. Alur, T. Feder, and T. A. Henzinger.  The benefits of relaxing punctuality.  J. ACM, 43(1):116–146, Jan. 1996.
  * [4] A. ARCH.  Benchmarks for continuous and hybrid system verification, 2015.
  * [5] S. Bak et al.  HyST: A source transformation and translation tool for hybrid automaton models.  In HSCC, Seattle, Washington, Apr. 2015. ACM.
  * [6] A. A. Bruto da Costa and P. Dasgupta.  ForFET: A Formal Feature Evaluation Tool for Hybrid Systems.  In Proc. of ATVA, pages 437–445, 2017.
  * [7] A. A. Bruto da Costa, G. Frehse, and P. Dasgupta.  Formal feature interpretation of hybrid systems.  IEEE TCAD, 37(11):2474–2484, 2018.
  * [8] S. Cotton, G. Frehse, and O. Lebeltel.  The spaceex modeling language, 2010.
  * [9] T. Dang et al.  Verification of analog and mixed-signal circuits using hybrid system techniques.  In FMCAD, pages 21–36. 2004.
  * [10] J. V. Deshmukh et al.  Robust online monitoring of signal temporal logic.  Formal Methods in System Design, 51(1):5–30, 2017.
  * [11] G. Frehse et al.  SpaceEx: Scalable Verification of Hybrid Systems.  In CAV, 2011.
  * [12] G. Frehse et al.  A toolchain for verifying safety properties of hybrid automata via pattern templates.  In ACC, pages 2384–2391, June 2018.
  * [13] S. Gao et al.  dreal: An SMT solver for nonlinear theories over the reals.  In CADE, pages 208–214, 2013.
  * [14] N. Kekatos.  Formal Verification of Cyber-Physical Systems in the Industrial Model-Based Design Process.  PhD thesis, 2018.
  * [15] O. Maler and D. Nickovic.  Monitoring temporal properties of continuous signals.  In FORMATS-FTRTFT, pages 152–166. Springer, 2004.
  * [16] L. V. Nguyen and T. T. Johnson.  Benchmark: DC-to-DC Switched-Mode Power Converters.  In ARCH14-15, volume 34, pages 19–24, 2015.
  * [17] D. Nickovic et al.  AMT 2.0: Qualitative and quantitative trace analysis with extended signal temporal logic.  In TACAS, pages 303–319, 2018.
  * [18] A. Pnueli.  The temporal logic of programs.  In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77, pages 46–57, Washington, DC, USA, 1977. IEEE Computer Society.


# Domain Adaptation in Multi-View Embedding
for Cross-Modal Video Retrieval

Jonathan Munro
University of Bristol &Michael Wray
University of Bristol &Diane Larlus
NAVER LABS Europe Gabriela Csurka
NAVER LABS Europe &Dima Damen
University of Bristol

###### Abstract

Given a gallery of uncaptioned video sequences, this paper considers the task
of retrieving videos based on their relevance to an unseen text query. To
compensate for the lack of annotations, we rely instead on a related video
gallery composed of video-caption pairs, termed the source gallery, albeit
with a domain gap between its videos and those in the target gallery. We thus
introduce the problem of Unsupervised Domain Adaptation for Cross-modal Video
Retrieval, along with a new benchmark on fine-grained actions. We propose a
novel iterative domain alignment method by means of pseudo-labelling target
videos and cross-domain (_i.e_. source-target) ranking. Our approach adapts
the embedding space to the target gallery, consistently outperforming source-
only as well as marginal and conditional alignment methods.

Figure 1: Given video-text pairs (respectively denoted by circles and stars)
from the  source (blue), and a video-only target set (purple), we propose an
alignment method to reduce the domain gap between the source videos and the
target videos using pseudo-labels (Section C) and cross-domain ranking
(Section 3.2). The learnt and aligned space can then be used for retrieving a
ranked list of target videos using previously unseen text queries.

##  1 Introduction

Using natural language queries to search for video sequences is the most
intuitive interface for video search engines. Example applications include
finding short and precise action sequences in long instructional videos,
_e.g_. for educational purposes. Cross-modal retrieval is typically approached
by training a joint video-text embedding following a learning-to-rank
objective. Thanks to this, retrieval comprises of computing distances between
representations of textual queries and representations of videos in a gallery.
Building a reliable joint embedding space requires large amounts of accurately
annotated video-caption pairs [9, 21, 26, 32, 37, 39, 41, 57], where captions
come from manual annotations, query logs or transcribed audio. These works
assume the training set allows for learning a robust representation that
generalises to the test/target videos. However, the appearance of certain
actions can change due to new environments or recording equipment. This
introduces a visual domain gap between the captioned video sequences and the
gallery of videos we wish to retrieve from, rendering the trained joint
embedding space sub-optimal.

In this paper we address the challenge of a visual domain gap in the context
of cross-modal action retrieval, assuming that no captions are available for
the target gallery. For this, we choose the EPIC-KITCHENS-100 dataset [13]
which is composed of two distinct sets of videos featuring fine-grained
actions. It has been shown to exhibit a significant domain shift which alters
performance when tested for action recognition [42, 45, 49]. Instead, we offer
the first attempt to use this dataset for domain alignment in action
retrieval.

We first show that the marginal alignment of the distribution over videos [34,
50], independent of the text, is insufficient to fix the domain gap. Instead,
we propose to leverage pseudo-labels for the target videos in a unified
learning-to-rank approach which effectively combines _captioned source_ video
sequences and _uncaptioned target_ videos (see illustration in Figure 1).
Given the domain gap, pseudo-labelling is noisy. Therefore, we propose a
robust confidence measure to determine the reliability of pseudo-labels,
combined with a sampling strategy that ensures all actions are aligned, rather
than only the most confident or common actions. For better adaptation, we
align multi-view embeddings, where each embedding specialises in one part-of-
speech (_i.e_. verbs and nouns) within the caption.

To summarise, our contribution is threefold. First, we introduce the problem
of Unsupervised Domain Adaptation (UDA) for text-to-video retrieval. In this
setup, training only has access to i) a source domain composed of video-
caption pairs and to ii) videos (without captions) from the target gallery
set. Second, we propose a cross-domain learning-to-rank strategy which mixes
samples from the source and the target domains thanks to iterative pseudo-
labelling and robust sampling strategy. Third, we conduct extensive
experiments on the EPIC-KITCHENS-100 dataset which validate our approach. Our
method outperforms state-of-the-art UDA approaches [29, 43, 59] which we
adapted for action retrieval.

##  2 Related Work

#### Supervised Cross-modal Video Retrieval.

Learning a joint embedding space is a common approach to perform text-to-video
retrieval [9, 18, 21, 26, 31, 32, 37, 38, 41, 55, 57, 63]. Features from pre-
trained models have been used as a mixture of experts [21, 32, 38, 55]. Other
methods have instead focused on decomposing text captions into events, actions
and entities [9], creating a concept space [18], or disentangling captions
into their constituent parts of speech (PoS) [57]. Additional gains can be
achieved by distilling knowledge from vision-text transformers as in [36]. In
all these works, no domain gap is expected between the training and test sets.

#### Unsupervised Domain Adaptation.

Domain adaptation between pairs of domains (one source and one target), or
multiple domains (multi-source), has been proposed for various problems.
Earlier works acted in the pre-extracted feature space and considered data re-
weighting, metric learning, subspace representations or distribution matching.
Recent methods instead rely on deep architectures, trained end-to-end, where
the domain discrepancy is minimised jointly with the task error to learn
domain invariance [14, 34, 51]. Alternatives to discrepancy minimisation
include domain discriminative models with adversarial losses [53] or gradient
reversal layers [22].

Aligning the marginal statistics fails to consider the multi-modal structure
of input data, ignoring the boundaries between classes and the class imbalance
across domains. Therefore, methods consider the conditional or joint
distributions [35, 62]. To approximate target label information, soft
predictions or pseudo-labels are inferred by a transductive learning paradigm.
Relying on pseudo-labels, [47] designs an asymmetric strategy to learn
discriminative representations for the target domain, [5] minimises the
difference between the class centroids of each domain, while [15] enforces a
similarity-preserving constraint to maintain class-level relations among the
source and target. To minimise the impact of noisy pseudo-labels during
alignment, curriculum learning has been explored [5, 12, 44, 52], where
approaches first consider the most confident target samples for alignment,
then include the less confident ones at a later stage of the training.
Confidence scores are determined from classifiers [44, 60], similarity to
neighbours [48, 52] or to class prototypes [5, 12]. To improve the confidence
estimation of pseudo-labels, [46] relies on the consensus of image
transformations, whereas [47] considers the agreement between multiple
classifiers.

#### Domain Adaptation for Videos.

Prior works for video domain adaptation (DA) have focused on classification
[6, 11, 28, 42], segmentation [7, 8] and localisation [2]. They use
adversarial training to align the marginal distributions [28], an auxiliary
self-supervised task [8, 11, 42], or attending to relevant frames alignment
[6, 7, 8].

#### Domain Adaptation for Retrieval.

Most DA works for retrieval were proposed for person re-identification where,
to overcome the domain shift, generative models with similarity preserving
constraints learn to transfer the style between domains [4, 10, 16, 24]. Some
methods exploit pseudo-labels obtained by joint source and target clustering
[19, 20, 23], while others use curriculum learning to progressively adapt the
retrieval space [58, 61].

In contrast to the above literature, where the retrieval task is performed
within a single modality (namely images), only few DA works have considered
cross-modal retrieval [33, 44]. Initial work [44] learns correlations between
captions and images using a scene graph and Maximum Mean Discrepancy (MMD) for
domain alignment. Concurrent work [33] also attempts DA for text-to-video
retrieval. They train two prototypical classifiers in the cross-modal
embedding space, one for the source and one for the target, where labels are
found by respectively clustering the source text and target video
representations. To align domains, they maximise the mutual information
between the prototype assignments of both modalities. Departing from this
approach which uses prototypes for the alignment itself, ours builds on source
prototypes to sample a reliable subset of pseudo-labelled target videos for
cross-domain learning to rank. We additionally show the benefit of performing
alignment in multiple embedding spaces.

Figure 2: Proposed alignment strategy for the multi-view embedding of verbs.
(a) Domain gap between target videos (grey) and video-caption source pairs
(coloured according to their verb—wash/green, cut/orange, peel/purple) (b)
Target videos inherit pseudo-labels from their nearest source video, with a
confidence defined by the verb prototypes. Over epochs, pseudo-labelling is
updated. We show one video pseudo-labelled as cut in epoch $n$, and wash in
$n+1$ with increased confidence. (c) Cross-modal losses ($L_{s}$) are jointly
trained with cross-domain losses $L^{\times}_{s\rightarrow t}$,
$L^{\times}_{t\rightarrow s}$. Relevant (green arrow) and irrelevant (red
arrow) relations are used to train the embedding space with only the most
confidently pseudo-labelled target videos.

##  3 Method

In this work, we tackle text-to-video retrieval, where the goal is to retrieve
relevant videos from a _target_ gallery of videos $V^{t}$, given any text
query $w^{t}$. To achieve this, we leverage a _source_ gallery of paired
videos $V^{s}$ with their captions $W^{s}$. We consider the case where a
domain shift is known to exist between $V^{s}$ and $V^{t}$. Our aim is thus to
leverage the paired _source_ set, and the single-modality _target_ set (_i.e_.
videos only), for training a text-to-video retrieval model which will be
applied to the _target_ set.

An overview of our approach is presented in Fig. 2. In this section, we first
describe a multi-view text-to-video retrieval approach which performs well
when aligned video-caption pairs are available for training, _e.g_. as in our
source domain (Sec. 3.1). Second, we build on this baseline, and present our
domain alignment approach (Sec. 3.2) which learns a cross-domain cross-modal
embedding, and uses unsupervised conditional alignment of the source and
target videos along with a robust pseudo-labelling strategy applied to the
target gallery, which relies on prototype-based confidence estimation (Sec.
C).

###  3.1 Training for text-to-video retrieval with captioned videos

Given a set of videos $V^{s}$ and their corresponding captions $W^{s}$, one
can learn a joint video-text embedding space, following a learning-to-rank
approach with the hinge-based triplet ranking loss. Two embedding functions
$f:V^{s}\rightarrow\Omega$ and $g:W^{s}\rightarrow\Omega$ which respectively
produce representations for videos and text in the embedding space $\Omega$
are learned. The triplet ranking loss is defined as:
$H(a,b^{+},b^{-})=max(\gamma+d\big{(}h(a),h(b^{+})\big{)}-d\big{(}h(a),h(b^{-})\big{)},0)$
where $a$ is the anchor, $b^{+}$ and $b^{-}$ are relevant and irrelevant
samples for that anchor, $\gamma$ is a constant margin, $d(\cdot,\cdot)$ is
the distance function and $h\in\\{f,g\\}$ is the appropriate embedding
function, $f$ or $g$, depending on the modality.

Classical text-to-video retrieval approaches [9, 21, 32, 37] sample triplets
within video-caption pairs from $(V^{s},W^{s})$ and optimize $L(\theta)=\sum
H(v_{i},w_{i},w_{j})+\sum H(w_{i},v_{i},v_{k})$, where $v_{i},v_{k}\in V^{S}$
and $w_{i},w_{j},\in W^{S}$ and $\theta$ represents the parameters of the
embedding functions $h$. While these approaches typically already perform
well, videos/captions of similar actions are not explicitly encouraged to be
close in the embedding space. Inspired by [54, 57], we use both cross-modal
and within-modal losses between sets of relevant items. When the anchor is a
video, combining the cross-modal and within-modal losses produces:

$\begin{split}L^{v\rightarrow w}_{s}(\theta)=\sum H(v_{i},w_{j},w_{k})+\sum
H(v_{i},v_{l},v_{m})\\\ \text{with}~{}w_{j}\in W^{s}_{i+},w_{k}\in
W^{s}_{i-},v_{l}\in V^{s}_{i+},v_{m}\in V^{s}_{i-}\end{split}$ (1)

where $V^{s}_{i+}$ are all videos relevant to the query video $v_{i}$ and
$V^{s}_{i-}$ are irrelevant ones. Similarly, $W^{s}_{i+}$/$W^{s}_{i-}$ is the
set of all captions relevant/irrelevant111We generalise from the case where
only a single caption is considered relevant, to a set of relevant captions,
in line with recent works [25, 56, 64]. Finding these sets of relevant
videos/captions requires additional knowledge, such as visual clustering [20],
attributes [3], or semantic similarity between captions [25, 56, 64].  to the
query video $v_{i}$.

Analogous to Eq. 1, text-to-video cross-modal and within-modal losses are
defined, where the anchor is a caption, as $L^{w\rightarrow v}_{s}$. The
training is then defined as $L_{s}=L^{v\rightarrow w}_{s}+L^{w\rightarrow
v}_{s}$.

#### Multi-view Embeddings.

Recent works in text-to-video retrieval have shown that learning multiple
embedding spaces (or multi-view embeddings) could be beneficial [21, 32, 38,
57]. This can be achieved by disentangling the visual input into multiple
modalities [32, 38] or the caption into individual parts of speech [57]. Due
to our focus on fine-grained actions, we follow the JPoSE architecture [57]:
We parse captions into parts of speech (PoS) and we train a separate embedding
for each. The embedding vectors in the various views are then concatenated,
and considered as input to a final action embedding, where text-to-video
retrieval can be performed. Each embedding is trained using its own set of
triplets involving embedding-specific relevance relations. In the ‘verb’
embedding, all captions involving the verb (_e.g_. ‘cut’) are considered
relevant to one another, regardless of the object. Conversely, in the ‘noun’
embedding, all captions involving the same noun are considered relevant.

In the following, we show how a joint multi-view embedding space trained on
the source domain ${S=(V^{s},W^{s})}$ can be adapted for the target video
gallery $V^{t}$. The proposed adaptation method is applied to _each_ of the
multi-view embeddings, trained jointly.

###  3.2 Cross-domain Cross-modal Embedding

Reducing the domain shift by aligning marginal distributions of the source and
the target video sequences often leads to sub-optimal solutions as it does not
consider the alignment of local distributions between the two galleries. We
propose a cross-domain cross-modal approach instead. To overcome the lack of
captions in the target gallery $V^{t}$ we instead propose using pseudo-labels
to model cross-modal relevance.

For simplicity, we refer to source video $v^{s}_{i}\in V^{s}$ as $s_{i}$, and
to target video $v^{t}_{i}\in V^{t}$ as $t_{i}$. We define the source-to-
target and target-to-source cross-domain ranking objectives as:

$\begin{split}L^{\times}_{s\rightarrow t}(\theta)=\sum
H(s_{i},t_{j},t_{k})|~{}t_{j}\in V^{t}_{s_{i}+},t_{k}\in V^{t}_{s_{i}-}\\\
L^{\times}_{t\rightarrow s}(\theta)=\sum H(t_{i},s_{j},s_{k})|~{}s_{j}\in
V^{s}_{t_{i}+},s_{k}\in V^{s}_{t_{i}-}\end{split}$ (2)

where $V^{t}_{s_{i}+}/V^{t}_{s_{i}-}$ are relevant/irrelevant sets of target
videos for the source video $s_{i}$ and $V^{s}_{t_{i}+}/V^{s}_{t_{i}-}$ are
the relevant/irrelevant sets of source videos for the target video $t_{i}$.
These relevant sets are defined by the pseudo-labelling strategy described in
Sec C.

We then train the source embedding objectives (see Section 3.1) along with the
cross-domain ranking objectives, _i.e_.
$L=L_{s}+\lambda_{1}L^{\times}_{s\rightarrow
t}+\lambda_{2}L^{\times}_{t\rightarrow s}$ where $\lambda_{1}$ and
$\lambda_{2}$ are weights to balance the corresponding cross-domain losses.

Importantly, note that this is an iterative process during training. As the
joint embedding space is trained, target videos are pseudo-labelled, and are
used to generate triplets for cross-domain ranking. Target videos can
potentially be assigned to different pseudo-labels at each iteration. For
robust learning, we adjust the assignments to the relevance sets at the end of
each training epoch.

As mentioned in the previous section, we learn a separate embedding space for
each part of speech together with a final action embedding. We apply Eq. (2)
to each PoS embedding (_i.e_. view embedding) as well as to the overall action
embedding.

###  3.3 Pseudo-labelling and Prototype-based Sampling

In order to sample triplets for the cross-domain losses in Eq. (2), we need
pairs of relevant videos between the source and the target sets. Therefore, we
propose: i) a pseudo-labelling strategy to determine relevant video pairs
across domains, and ii) an associated prototype-based confidence measure to
select which target videos to use for training.

In standard DA, which often assumes a single modality and a classification
task, typical approaches use the softmax scores of the source classifier to
produce pseudo-labels [47, 17], or label propagation on the nearest neighbour
graph built with the joint source and target sets [48, 27]. Taking inspiration
from these strategies, and replacing pseudo-labelling with the process of
assigning to each target video a relevant set of source videos, we proceed as
follows. As in classical label propagation, the target video inherits the
relevance property of the closest source video, _i.e_. a relevant/irrelevant
query to the nearest source video is considered relevant/irrelevant to the
target video. Formally, if $s_{\hat{n}}$ is the nearest source video to the
target video, $t_{i}$, _i.e_. ${\hat{n}=\arg\min_{n}d(f(t_{i}),f(s_{n}))}$, we
assign
$V^{s}_{t_{i}+}=\\{V_{s_{\hat{n}}+}^{s}\cup\\{s_{\hat{n}}\\}\\};V^{s}_{t_{i}-}=V_{s_{{\hat{n}}-}}^{s}.$
Similarly, the target video is considered relevant to each source video in its
relevant set. However, this process which associates videos across the source
and the target domains might be error prone, and relying on too many erroneous
relevance pairs would degrade the model. On the other hand, trusting too few
would not be sufficient to align the domains. Consequently, to handle such a
trade-off, we propose to robustly measure the confidence of the labelling
process and to use these confidence scores to select target videos.

#### Prototype Confidence (PC).

We propose to calculate confidence scores based on the distance between the
target videos and the _source prototypes_ of their closest source video
$s_{\hat{n}}$ in the embedding space. A source prototype is defined as the
barycentre of the sets of relevant videos as described in Sec. 3.2. All videos
within one set $V^{s}_{s_{i}+}$ are relevant to each other and share the same
relevance properties, _e.g_. they show the same action/PoS. We calculate the
prototype for this set $V^{s}_{p}$ by $\mu_{p}=\sum_{s_{i}\in
V^{s}_{p}}f(s_{i})$.

Let $\mu_{\hat{p}}$ be the prototype corresponding to the source video
$s_{\hat{n}}$, _i.e_. $s_{\hat{n}}\in V^{s}_{\hat{p}}$, and therefore
$V^{s}_{s_{\hat{n}}+}=V^{s}_{\hat{p}}$. Then, the confidence measure for
pseudo-labelling the target video, $t_{i}$, is calculated as a function of the
distance to the prototype $\mu_{\hat{p}}$, more precisely
$\alpha_{t_{i}}=e^{-d(f(t_{i}),\mu_{\hat{p}})}$.

Note that we propose to calculate the distance between the target video and
the closest prototype $\mu_{\hat{p}}$, rather than the closest source video
$s_{\hat{n}}$, so we increase robustness by avoiding outliers and considering
the distance of the target video to all relevant source videos.

Importantly, the embeddings $f(t_{i})$, $f(s_{\hat{n}})$ and prototypes
$\mu_{\hat{p}}$ depend on the learnt embedding function $f$, and hence they
continuously change over training iterations. Subsequently, the pseudo-
labelling and the confidence scores are also continuously changing, but it
would be extremely costly to update them for all target videos after every
model update. Fortunately, this change is progressive and updating them at the
end of every epoch is sufficient.

#### Prototype Based Sampling (PBS).

Using the proposed prototype confidence scores, we can sample the most
reliable target videos, and use them for training our cross-domain losses (Eq.
2). However, selected target videos do not only need to be reliable, they also
need to widely cover the different actions. Without sufficient coverage, some
actions can be poorly aligned. As training progresses, the variety of selected
actions may decrease as the labelling gets biased towards actions that are
already aligned.

To avoid only aligning a few confident actions, and ignoring the others during
domain alignment, we leverage the source prototypes. Let us consider the set
of all target videos that are pseudo-labelled using the source prototype $p$,
_i.e_. their relevant source videos are $V^{s}_{p}$. We would like to select
the most confident of these, per prototype, to maintain coverage. We thus
propose to sample the top $x\%$ most confident target videos assigned to each
prototype, _i.e_. we rank the videos assigned to $V^{t}_{p}$ based on the
confidence scores $\alpha_{t_{i}}$ and take the top $x\%$ of the list, for
each prototype. Our proposal thus can deal with imbalanced sets, maintaining
the distribution of pseudo-labels, when sampling the most confident ones.

To summarise, we align each multi-view embedding (Sec 3.1) by pseudo-
labelling, sampling the most confident target videos per prototype, and
iterating. Importantly, the multi-view embeddings are trained jointly, with
one loss $L$ per embedding.

##  4 Experimental Evaluation

#### Dataset.

We evaluate our approach on EPIC-KITCHENS-100 [13], which provides videos
associated with free-form narrated captions of egocentric actions. The
Source/Target split has only been evaluated in the context of action
recognition [42], using class labels but not the captions.

We observe a similar visual domain gap to that in action recognition (see test
performances in Fig. 1). We consider all videos from the TRAIN/VAL UDA action
recognition challenge, as these contain released captions222The Test split in
the challenge does not have released captions publicly available. They are
collected from 16 participants, with videos recorded with a two-year gap [13],
totalling 55K action videos (21K Source and 34K Target). The domain gap in
this dataset results from recording footage in different environments and
recording periods.

Split | Domain | Participants | Video Gallery | Text Queries
---|---|---|---|---
TRAIN | Source / Target | 12 / 12 | 16115 / 26115 | 4756 / [5907†]
VAL | Source / Target | 4 / 4 | 5002 /7906 | 1805 / [2822∗]
Table 1: Proposed EPIC-KITCHENS benchmark. Note that target text queries are
never used for training. $\dagger$: only used for evaluation *: only used for
optimising hyper-parameters.

#### Proposed Benchmark.

We propose the first benchmark for domain alignment in fine-grained text-to-
video retrieval (see Table 1). We use the VAL split of the UDA challenge [13]
only to select the hyperparameters. Once hyperparameters are decided, we train
the model on the TRAIN split. The model is trained with Source videos and
their captions but only Target videos are used (with no captions). At test
time, the model is evaluated by ranking the Target videos for each Target text
query. For evaluation, we report mAP and nDCG, both of which measure ranking
quality, as proposed in the supervised retrieval challenge [13]. We follow the
same approach to define ground-truth retrieval results, considering retrieved
videos depicting the same actions as described by the textual query as
relevant.

#### Model and Pretraining.

For our experiments we use the public implementation of JPoSE [57] as our base
network and modify it for domain adaptation as described in Sec. 3.2 and C. To
train the model, we first pre-train our network only on Source and use it to
initialise the proposed domain alignment network. See supplementary for
further details.

#### Alignment Baselines.

As a lower bound, we include the non adapted Source-Only results.
Additionally, we implement per-domain standardisation PDS which is a simple
alignment technique where the input distribution of each domain is
standardised separately. PDS decreases the domain shift. All methods—including
ours—are trained with these standardised features. We compare our method to
classification-based (_i.e_. typical) domain alignment methods, that we
modified for the task of cross-modal video retrieval. All methods were hence
trained and tested with the exact same protocol. We list them below.

From shallow models we test CORAL [50], which aligns second order statistics,
and from deep models we consider MMD [34], which minimises the discrepancy
between source and target embeddings, and GRL [22], which optimizes a domain
discrimination loss in an adversarial manner. We also compare to more recent
conditional alignment approaches, adapting these by replacing the notion of
classes with groups of relevant videos that share the same prototype. In
particular, we evaluate MSTN [59] which minimizes the Euclidean distance
between the source and target prototypes, TPN [43] which minimises the MMD
between the source and target examples per prototype and CDD [29] where the
MMD is minimised within each prototype while maximised across examples
belonging to differing prototypes. For fairness, all conditional alignment
methods use the same pseudo-labelling strategy as our method and, to make sure
conditional alignment baselines have a sufficient number of instances per
prototype, we compare alignment of the Part of Speech (PoS) embeddings.

| Method | Alignment Space |  | Val (Target VAL) | Test (Target TRAIN)
---|---|---|---|---|---
|  | PoS | Action | M | C | nDCG | mAP | nDCG | mAP
(a) | Source-Only | $\times$ | $\times$ | $\times$ | $\times$ | $40.45$ | 7.32 | $35.25$ | 5.05
PDS | $\checkmark$ | $\times$ | $\checkmark$ | $\times$ | $40.78$ | 7.65 | $35.92$ | 5.42
CORAL [50] | $\checkmark$ | $\times$ | $\checkmark$ | $\times$ | $40.70$ | 7.79 | $36.32$ | 5.38
MMD [34] | $\checkmark$ | $\times$ | $\checkmark$ | $\times$ | $40.60$ | 7.49 | $36.26$ | 5.43
GRL [22] | $\checkmark$ | $\times$ | $\checkmark$ | $\times$ | $42.45$ | 5.20 | $36.64$ | 5.61
TPN [43] | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | $42.19$ | 8.27 | $36.86$ | 5.73
CDD [29] | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | $42.00$ | 8.48 | $36.48$ | 5.80
MSTN [59] | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | $42.85$ | 8.63 | $37.62$ | 5.87
| Ours-PoS | $\checkmark$ | $\times$ | $\checkmark$ | $\checkmark$ | 43.14 | 8.59 | 38.01 | 6.21
(b) | Ours-Action | $\times$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | 43.07 | 8.85 | 37.74 | 6.20
Ours | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | 44.00 | 9.10 | 38.21 | 6.34

Table 2: (a) Comparison with alignment baselines (M: Marginal alignment, C:
Conditional alignment). TPN, CDD, MSTN use our sampling strategy for fair
comparison. (b) Which space(s) to use for alignment: Part-of-Speech or Action
(see sec. 3.1).

#### Comparison to SOTA.

Table 2(a) shows how the proposed method performs against models trained
solely on source (Source-Only) and both marginal and conditional alignment
baselines. We report retrieval results on Target VAL (referred as Val) and on
Target TRAIN (referred as Test333We report the best Val epoch based on nDCG
and use it as early stopping criteria when testing on Target TRAIN.).
Surprisingly, the simpler marginal alignment methods (PDS and CORAL) yield
better performance than the deep models (MMD) for our benchmark, but overall
they provide marginal improvements over the Source-Only model. Adversarial
training (GRL) provides a larger improvement, however, we find this to be
highly unstable as training progresses. The conditional alignment approaches
(TPN, CDD, MSTN) perform better than marginal alignment, with MSTN performing
the best. Our approach (Ours-PoS), using cross-domain alignment, outperforms
all baselines on Test.

In Table 2(b) we show two alternatives of the proposed model, Ours-Action
where we align the domains in the Action embedding space. Even with single-
view domain alignment (only Action embedding), our approach outperforms all
baselines. Finally, by aligning all embeddings (PoS and Action) jointly, we
observe further improvements over Ours-PoS.

To verify the design choices of our proposed model (see Sec. C) we answer the
following three questions in Table 4 (further details in the supplementary):

#### How to pseudo-label?

Table LABEL:subtab:labelling shows that inheriting from the nearest source
video performs better than using the nearest prototype’s label (Proto) because
it makes fewer assumptions on the target distribution.

#### How to assign confidence?

Table LABEL:subtab:confidence shows that the proposed confidence measure
$\alpha$—based on the distance to the prototype—is more robust than using a
confidence based on the distance to the closest source video instead
(Neighbour).

Figure 3: Performance as we train for different proportions of target sampled.

#### How to sample videos?

In Table LABEL:subtab:sampling we compare the proposed sampling strategy to
uniform sampling.

By sampling confident examples per prototype, we ensure that they cover a
variety of actions, thus improving the domain alignment. Without our sampling
strategy, target videos are sampled from fewer actions as training progresses.

#### How many relevant?

Figure 3 shows the impact of different proportions used to sample target
examples. The results are shown on Val. We observe that removing the least
confident examples significantly improves target performance and that $60\%$
performs best. Also, we see that, as expected, using all target instances
(100%), which would include erroneous pseudo-labels, leads to a substantial
drop in performance. This validates our sampling proposal.

(a) Labelling Method Method | Test
---|---
Proto | $37.92\pm 0.12$
Ours | $38.21\pm 0.08$

(b) Confidence Method Method | Test
---|---
Neighbour | $37.64\pm 0.30$
Ours | $38.21\pm 0.08$

(c) Video Sampling Method Method | Test
---|---
Uniform $(60\%)$ | $37.88\pm 0.08$
Ours $(60\%)$ | $38.21\pm 0.08$

Table 3: Ablation Studies on the Test set (nDCG). Mean and standard deviation
over 3 runs.

##  5 Conclusion

In this work, we have introduced the problem of unsupervised domain adaption
for text-to-video retrieval. Given a source dataset of captioned videos for
training, the goal is to perform retrieval on a distinct target set of
uncaptioned videos. At the heart of our proposed approach lies an iterative
pseudo-labelling process, which associates source and target samples at train
time. These pseudo-labelled samples fuel our cross-domain cross-modal
learning-to-rank approach which aligns the source and the target video
galleries. Our experiments validate this strategy and highlight the importance
of selecting confident target examples, using source prototypes, during
alignment.

## Appendix

In this appendix we provide additional analysis and further implementation
details. We show qualitative results of text-video retrieval using target text
queries in Appendix A followed by feature visualisations in Appendix B. Next
we show the accuracy of pseudo-label assignments in Appendix C, and the
variety of pseudo-labels assigned to target videos in Appendix D. Finally, we
report the Mean Average Precision metric for the ablation in the main paper
(Table 4) in Appendix E, and discuss the implementation details in more depth
in Appendix F.

##  Appendix A Qualitative Results

Figure 4 shows how the rank of the first relevant video to specified text
queries changes from the Source-Only model and Ours. Ours results in more
relevant videos retrieved higher in the ranking, however, some failure cases
exist. The video of ”put rolling pin in drawer” is retrieved lower in the
ranking, with videos depicting actions of moving utensils retrieved higher in
the ranking.

Figure 4: Qualitative results of text-to-video retrieval. We show the query
caption and the corresponding video along with the change in rank,
$A\leftarrow B$, of the proposed method (A) and Source-Only baseline (B).

##  Appendix B Feature Visualisations

Fig 5 shows the UMAP visualisation of the action, noun and verb embedding
spaces for Source-Only (LEFT) and Ours (RIGHT). Ours not only shows greater
alignment of source (BLUE) and target (ORANGE) videos but more distinct
clusters of videos depicting the same action/part-of-speech.

Fig 6 shows the UMAP visualisation of the target videos (ORANGE) and target
text (other colours). Target-text were used as queries to evaluate text-video
retrieval, but were not present during training. For clarity, we only show the
text embeddings from the 20 verb/noun prototypes with the most videos. Target
text is aligned with target video clusters.

Analysis of the alignment of source and target videos in the action and part-
of-speech embeddings (a) Action Embedding (b) Verb Embedding (c) Noun
Embedding

Figure 5: UMAP visualisation of the part-of-speech and action embeddings,
Target in ORANGE and Source in BLUE. LEFT: Source-only, RIGHT: Ours

Analysis of the alignment of target text queries with target videos (a) Noun
embedding (b) Verb embedding

Figure 6: UMAP visualisation of chosen target text queries and all target
videos. Visualising text queries from 20 part-of-speech prototypes which have
the most videos. Target videos are shown in ORANGE.

##  Appendix C Pseudo-label Accuracy for Alignment losses

Figure 7 shows the pseudo-label accuracy over training epochs. Note that
pseudo-label accuracy improves over training iterations as the domains are
better aligned. Ours, with the robust prototype-based confidence measure,
outperforms using the distance to the nearest source video as the confidence
measure (Neighbour). Pseudo-labelling based on the nearest source prototype
(Proto) incorrectly labels more target examples as it is affected by outliers.

Analysis of the accuracy of the pseudo-labels assigned to target videos
(a) Action (b) Verb (c) Noun

Figure 7: Pseudo-label accuracy for target videos in the action, verb and noun
embedding as training progresses. Ours (BLUE) produces more accurate labels as
training progresses compared to: Neighbour (ORANGE) which uses the distance to
the nearest source video to determine confidence, and Proto (GREEN) which uses
the nearest source prototype to propagate labels onto target videos. These
different approaches are compared in Table 4 from the main paper.

##  Appendix D Analysis of the diversity of target video pseudo-labels

Analysis of the diversity of target video pseudo-labels
(a) Action (b) Verb (c) Noun

Figure 8: The percentage of prototypes (pseudo-labels) assigned to target
videos in the action, verb and noun embedding as training progresses. We see
that Ours (BLUE) maintains a greater variety of labels than uniform sampling
(ORANGE).

Figure 8 shows the percentage of prototypes assigned to all target examples as
pseudo-labels. Our proposed sampling strategy ensures that the target videos
are assigned to a large variety of action/pos prototypes, while using uniform
sampling favors assignments to prototypes corresponding to large clusters
introducing an increasing bias towards them.

##  Appendix E mAP performance

Tables 4 shows the Mean Average Precision metric for the different pseudo-
labelling and sampling strategies. In order to produce a binary relevancy,
videos are only considered relevant to a query text if the original relevancy
is strictly greater than 0.5. Similar to nDCG, Ours outperforms the
alternative pseudo-labelling strategies.

(a) Labelling Method Method | Test
---|---
Proto | $6.21\pm 0.02$
Ours | $6.34\pm 0.05$

(b) Confidence Method Method | Test
---|---
Neighbour | $6.09\pm 0.05$
Ours | $6.34\pm 0.05$

(c) Video Sampling Method Method | Test
---|---
Uniform $(60\%)$ | $6.28\pm 0.02$
Ours $(60\%)$ | $6.34\pm 0.05$

Table 4: Ablation Studies on Train (mAP). Mean and standard deviation over 3
runs. We report comparable nDCG results in the main paper.

##  Appendix F Additional Implementation Details

#### Architecture and Input Features.

Video input features, $V$, are extracted from a TBN [30] model pre-trained on
the source domain videos from Train and Val splits. The 3072 dimensional
feature vector is a concatenation of RGB, Flow and Audio features—where audio
is the natural sound recorded with the video. The text features are a Word2Vec
[40] descriptor of length 200, trained on the Wikipedia corpus [1].

The base architecture is defined in JPOSE [57] where $f(v_{i})$ and $g(w_{i})$
are multi-layer perceptrons with hidden layer sizes of 228 and 1664,
respectively. The output video and text embeddings are vectors of length 256.
The action descriptor is of length 512, which is the concatenation of the
video and text embeddings.

For optimisation, weights are optimised by SGD with a learning rate of 0.01
and momentum of 0.9. We also adopt a hard-negative mining strategy for the
source-domain losses. This considers only negative examples from the nearest
$30\%$ of action prototypes to the action prototype of the query. This
decreased the number of epochs required for training the Source-Only model, in
addition to a small gain in text-video retrieval performance.

#### Hyper-parameter Selection.

The weights for the alignment losses,
$\lambda^{\times}_{s,t}=\lambda^{\times}_{t,s}=0.1$ were found best when
tuning on Val with values
$\lambda^{\times}_{s,t},\lambda^{\times}_{t,s}\in\\{0.01,0.1,1.0\\}$. The
weights of the source losses $\lambda_{s}$ were those defined in JPOSE [57].
The distance metric $d$ used for pseudo-labelling and confidence measures was
the cosine distance.

As often in DA, we first pre-train our network on source and use it to
initialise the proposed domain alignment network. Then we train the proposed
model with cross-modal and cross-domain ranking losses, where the source-
target associations are obtained with the proposed target video pseudo-
labelling and sampling strategy. At the end of each epoch we update the
relevance sets.

To obtain results on the test set (Train Target), we follow the same
procedure, i.e. we initialise our network with the model pre-trained on Train
Source (note that we have different source sets for Val and Train). The
network is then trained with all losses using the hyper-parameters selected
from the Val set. The network is trained for $n$ epochs, where $n$ indicates
the number of epochs used to train the best performing model on the Val set.

#### Baselines.

The shallow method, PDS, is applied as a pre-processing step to align $V^{s}$
and $V^{t}$. This is done only once at the beginning of the training process.
In spite of its simplicity, PDS allows initial pseudo-labelling to be
improved, when compared to Source-Only.

CORAL is also applied as a pre-processing, transforming the source input
features to have the same covarience as the target.

Deep alignment methods, MMD and GRL, are optimised jointly with the source
cross-modal embedding. The weighting of the MMD loss, $\lambda_{mmd}=0.01$,
and GRL, $\lambda_{GRL}=0.0001$ were found using a grid-search in the range of
$[0.0001,0.001,0.01,0.1,1.0]$.

The conditional alignment approaches (MSTN, TPN and CDD) utilise our proposed
pseudo-labelling strategy. First the networks are trained on source, similarly
to Ours. For these baselines, we implement class-aware sampling [29] which
ensures sufficient number of examples for each prototype. This samples 30
instances from 32 different classes each mini-batch. For classes containing
less than 30 instances all instances of the class are used and classes
containing less than 3 samples are not sampled. The weighting for each loss is
$\lambda_{MSTN}=0.1$, $\lambda_{TPN}=0.1$, $\lambda_{CDD}=0.005$ for MSTN, TPN
and CDD, repsectively. These were found using a grid-search in the range of
$[0.0001,0.001,0.005,0.01,0.1,1.0]$.

## References

  * [1] The wikipedia corpus.  Accessed:2020-11-11.
  * [2] N. Agarwal, Y.-T. Chen, B. Dariush, and M.-H. Yang.  Unsupervised domain adaptation for spatio-temporal action localization.  Brit. Mach. Vis. Conf., 2020.
  * [3] K. E. Ak, A. A. Kassim, J. H. Lim, and J. Y. Tham.  Learning attribute representations with localization for flexible fashion search.  In IEEE Conf. Comput. Vis. Pattern Recog., 2018.
  * [4] S. Bak, P. Carr, and J.-F. Lalonde.  Domain adaptation through synthesis for unsupervised person re-identification.  In Eur. Conf. Comput. Vis., 2018.
  * [5] C. Chen, W. Xie, W. Huang, Y. Rong, X. Ding, Y. Huang, T. Xu, and J. Huang.  Progressive feature alignment for unsupervised domain adaptation.  In IEEE Conf. Comput. Vis. Pattern Recog., 2019.
  * [6] M.-H. Chen, Z. Kira, G. AlRegib, J. Woo, R. Chen, and J. Zheng.  Temporal attentive alignment for large-scale video domain adaptation.  In Int. Conf. Comput. Vis., 2019.
  * [7] M.-H. Chen, B. Li, Y. Bao, and G. AlRegib.  Action segmentation with mixed temporal domain adaptation.  In IEEE Winter Conf. on App. of Comput. Vis, 2020.
  * [8] M.-H. Chen, B. Li, Y. Bao, G. AlRegib, and Z. Kira.  Action segmentation with joint self-supervised temporal domain adaptation.  In IEEE Conf. Comput. Vis. Pattern Recog., 2020.
  * [9] S. Chen, Y. Zhao, Q. Jin, and Q. Wu.  Fine-grained video-text retrieval with hierarchical graph reasoning.  In IEEE Conf. Comput. Vis. Pattern Recog., 2020.
  * [10] Y. Chen, X. Zhu, and S. Gong.  Instance-Guided Context Rendering for Cross-Domain Person Re-Identification.  In Int. Conf. Comput. Vis., 2019.
  * [11] J. Choi, G. Sharma, S. Schulter, and J.-B. Huang.  Shuffle and attend: Video domain adaptation.  In Eur. Conf. Comput. Vis., 2020.
  * [12] G. Csurka, B. Chidlovskii, and F. Perronnin.  Domain Adaptation with a Domain Specific Class Means Classifier.  In Eur. Conf. Comput. Vis. Worksh., 2014.
  * [13] D. Damen, H. Doughty, G. M. Farinella, A. Furnari, J. Ma, E. Kazakos, D. Moltisanti, J. Munro, T. Perrett, W. Price, and M. Wray.  Rescaling egocentric vision.  CoRR, 2020.
  * [14] B. B. Damodaran, B. Kellenberger, R. Flamary, D. Tuia, and N. Courty.  DeepJDOT: Deep Joint Distribution Optimal Transport for Unsupervised Domain Adaptation.  In Eur. Conf. Comput. Vis., 2018.
  * [15] W. Deng, L. Zheng, Y. Sun, and J. Jiao.  Rethinking triplet loss for domain adaptation.  IEEE Trans. Circuit Syst. Video Technol., 2020.
  * [16] W. Deng, L. Zheng, Q. Ye, G. Kang, Y. Yang, and J. Jiao.  Image-Image Domain Adaptation with Preserved Self-Similarity and Domain-Dissimilarity for Person Re-identification.  In IEEE Conf. Comput. Vis. Pattern Recog., 2018.
  * [17] Z. Deng, Y. Luo, and J. Zhu.  Cluster Alignment with a Teacher for Unsupervised Domain Adaptation.  In Int. Conf. Comput. Vis., 2019.
  * [18] J. Dong, X. Li, C. Xu, X. Yang, G. Yang, X. Wang, and M. Wang.  Dual encoding for video retrieval by text.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [19] H. Fan, L. Zheng, C. Yan, and Y. Yang.  Unsupervised Person Re-identification: Clustering and Fine-tuning.  ACM Trans. Multimedia Comput. Commun. Appl., 2018.
  * [20] Y. Fu, Y. Wei, G. Wang, Y. Zhou, H. Shi, and T. S. Huang.  Self-similarity Grouping: A Simple Unsupervised Cross Domain Adaptation Approach for Person Re-identification.  In Int. Conf. Comput. Vis., 2019.
  * [21] V. Gabeur, C. Sun, K. Alahari, and C. Schmid.  Multi-modal transformer for video retrieval.  In Eur. Conf. Comput. Vis., 2020.
  * [22] Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky.  Domain-Adversarial Training of Neural Networks.  Advances in Computer Vision and Pattern Recognition, 2016.
  * [23] Y. Ge, D. Chen, and H. Li.  Mutual mean-teaching: Pseudo label refinery for unsupervised domain adaptation on person re-identification.  In Int. Conf. Learn. Represent., 2020.
  * [24] Y. Ge, F. Zhu, R. Zhao, and H. Li.  Structured domain adaptation for unsupervised person re-identification.  arXiv, 2020.
  * [25] A. Gordo and D. Larlus.  Beyond instance-level image retrieval: Leveraging captions to learn a global visual representation for semantic retrieval.  In IEEE Conf. Comput. Vis. Pattern Recog., 2017.
  * [26] M. Hahn, A. Silva, and J. M. Rehg.  Action2vec: A crossmodal embedding approach to action learning.  In Brit. Mach. Vis. Conf., 2019.
  * [27] A. Iscen, G. Tolias, Y. Avrithis, and O. Chum.  Label propagation for deep semi-supervised learning.  In IEEE Conf. Comput. Vis. Pattern Recog., 2019.
  * [28] A. Jamal, V. P. Namboodiri, D. Deodhare, and K. Venkatesh.  Deep domain adaptation in action space.  In Brit. Mach. Vis. Conf., 2018.
  * [29] G. Kang, L. Jiang, Y. Yang, and A. G. Hauptmann.  Contrastive adaptation network for unsupervised domain adaptation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4893–4902, 2019.
  * [30] E. Kazakos, A. Nagrani, A. Zisserman, and D. Damen.  Epic-fusion: Audio-visual temporal binding for egocentric action recognition.  In Int. Conf. Comput. Vis., 2019.
  * [31] J. Lei, L. Li, L. Zhou, Z. Gan, T. L. Berg, M. Bansal, and J. Liu.  Less is more: Clipbert for video-and-language learning via sparse sampling.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 7331–7341, 2021\.
  * [32] Y. Liu, S. Albanie, A. Nagrani, and A. Zisserman.  Use what you have: Video retrieval using representations from collaborative experts.  arXiv, 2019.
  * [33] Y. Liu, Q. Chen, and S. Albanie.  Adaptive cross-modal prototypes for cross-domain visual-language retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 14954–14964, June 2021.
  * [34] M. Long, Y. Cao, J. Wang, and M. Jordan.  Learning Transferable Features with Deep Adaptation Networks.  In Int. Conf. on Mach. Learn., 2015.
  * [35] M. Long, Z. Cao, J. Wang, and M. Jordan.  Conditional Adversarial Domain Adaptation.  In Adv. Neural Inform. Process. Syst., 2018.
  * [36] A. Miech, J.-B. Alayrac, I. Laptev, J. Sivic, and A. Zisserman.  Thinking fast and slow: Efficient text-to-visual retrieval with transformers.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June.
  * [37] A. Miech, J.-B. Alayrac, L. Smaira, I. Laptev, J. Sivic, and A. Zisserman.  End-to-end learning of visual representations from uncurated instructional videos.  In IEEE Conf. Comput. Vis. Pattern Recog., 2020.
  * [38] A. Miech, I. Laptev, and J. Sivic.  Learning a text-video embedding from incomplete and heterogeneous data.  arXiv, 2018.
  * [39] 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 Int. Conf. Comput. Vis., 2019.
  * [40] T. Mikolov, K. Chen, G. Corrado, and J. Dean.  Efficient estimation of word representations in vector space.  Int. Conf. Learn. Represent., 2013.
  * [41] N. C. Mithun, J. Li, F. Metze, and A. K. Roy-Chowdhury.  Learning joint embedding with multimodal cues for cross-modal video-text retrieval.  In Int. Conf. on Multimedia Retrieval, 2018.
  * [42] J. Munro and D. Damen.  Multi-modal domain adaptation for fine-grained action recognition.  In IEEE Conf. Comput. Vis. Pattern Recog., 2020.
  * [43] Y. Pan, T. Yao, Y. Li, Y. Wang, C.-W. Ngo, and T. Mei.  Transferrable prototypical networks for unsupervised domain adaptation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2239–2247, 2019.
  * [44] Y. Peng and J. Chi.  Unsupervised cross-media retrieval using domain adaptation with scene graph.  IEEE Trans. Circuit Syst. Video Technol., 2019.
  * [45] M. Planamente, C. Plizzari, E. Alberti, and B. Caputo.  Cross-domain first person audio-visual action recognition through relative norm alignment.  ArXiv, 2021.
  * [46] S. Roy, A. Siarohin, E. Sangineto, S. R. Bulo, N. Sebe, and E. Ricci.  Unsupervised domain adaptation using feature-whitening and consensus loss.  In IEEE Conf. Comput. Vis. Pattern Recog., 2019.
  * [47] K. Saito, Y. Ushiku, and T. Harada.  Asymmetric tri-training for unsupervised domain adaptation.  In Proc. Mach. Learn. Res, 2017.
  * [48] O. Sener, H. Song, A. Saxena, and S. Savarese.  Learning Transferrable Representations for Unsupervised Domain Adaptation.  In Adv. Neural Inform. Process. Syst., 2016.
  * [49] X. Song, S. Zhao, J. Yang, H. Yue, P. Xu, R. Hu, and H. Chai.  Spatio-temporal contrastive domain adaptation for action recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June.
  * [50] B. Sun, J. Feng, and K. Saenko.  Return of frustratingly easy domain adaptation.  In AAAI, 2016.
  * [51] B. Sun and K. Saenko.  Deep CORAL: Correlation Alignment for Deep Domain Adaptation.  In TASK-CV Workshop, 2016.
  * [52] T. Tommasi and B. Caputo.  Frustratingly Easy NBNN Domain Adaptation.  In Int. Conf. Comput. Vis., 2013.
  * [53] E. Tzeng, J. Hoffman, K. Saenko, and T. Darrell.  Adversarial Discriminative Domain Adaptation.  In IEEE Conf. Comput. Vis. Pattern Recog., 2017.
  * [54] L. Wang, Y. Li, and S. Lazebnik.  Learning deep structure-preserving image-text embeddings.  In IEEE Conf. Comput. Vis. Pattern Recog., 2016.
  * [55] X. Wang, L. Zhu, and Y. Yang.  T2vlad: global-local sequence alignment for text-video retrieval.  In IEEE Conf. Comput. Vis. Pattern Recog., pages 5079–5088, 2021\.
  * [56] M. Wray, H. Doughty, and D. Damen.  On semantic similarity in video retrieval.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
  * [57] M. Wray, D. Larlus, G. Csurka, and D. Damen.  Fine-grained action retrieval through multiple parts-of-speech embeddings.  In Int. Conf. Comput. Vis., 2019.
  * [58] Y. Wu, Y. Lin, X. Dong, Y. Yan, W. Ouyang, and Y. Yang.  Exploit the Unknown Gradually: One-Shot Video-Based Person Re-Identification by Stepwise Learning.  In IEEE Conf. Comput. Vis. Pattern Recog., 2018.
  * [59] S. Xie, Z. Zheng, L. Chen, and C. Chen.  Learning semantic representations for unsupervised domain adaptation.  In International conference on machine learning, pages 5423–5432. PMLR, 2018.
  * [60] W. Zhang, W. Ouyang, W. Li, and D. Xu.  Collaborative and Adversarial Network for Unsupervised Domain Adaptation.  In IEEE Conf. Comput. Vis. Pattern Recog., 2018.
  * [61] X. Zhang, J. Cao, C. Shen, and M. You.  Self-Training with Progressive Augmentation for Unsupervised Cross-Domain Person Re-Identification.  In Int. Conf. Comput. Vis., 2019.
  * [62] Y. Zhang, T. Liu, M. Long, and M. Jordan.  Bridging Theory and Algorithm for Domain Adaptation.  In Int. Conf. on Mach. Learn., 2019.
  * [63] Z. Zhang and V. Saligrama.  Zero-shot learning via semantic similarity embedding.  In Int. Conf. Comput. Vis., 2015.
  * [64] M. Zhou, Z. Niu, L. Wang, Z. Gao, Q. Zhang, and G. Hua.  Ladder loss for coherent visual-semantic embedding.  In AAAI, 2020.


fish1     fish2     8     73.57     64410     58215     3.07     2.07     149.62     179.76     55     16     2.10     2.09     0.16     0.12     0.969±0.0872     0.969±0.0763
glass1     glass2     13     12.83     30921     13439     7.28     7.81     273.30     283.75     24     0     1.85     1.33     0.22     0.10     0.918±0.122     0.89±0.107
gorilla1     gorilla5     26     30.52     37417     59375     1.26     1.24     33.04     58.37     1     4     4.05     2.76     0.09     0.10     0.988±0.0326     0.978±0.0448
horse0     horse5     16     20.55     31507     34978     0.23     0.21     31.10     35.11     0     1     2.16     2.37     0.05     0.06     0.989±0.0414     0.99±0.027
Cow_t     Horse_t     21     20.09     31694     32515     0.58     1.16     117.74     129.02     17     18     2.25     3.43     0.13     0.23     0.978±0.0515     0.969±0.0641
human1     human2     21     42.27     56550     82581     0.57     0.87     58.34     60.89     0     33     1.67     2.09     0.06     0.10     0.988±0.0267     0.985±0.0428
michael0     michael7     20     19.53     19445     30014     0.40     0.35     21.62     27.28     1     4     1.75     1.46     0.06     0.07     0.992±0.0221     0.991±0.0269
seahorse2     seahorse4     22     8.24     13720     15667     0.09     0.11     16.89     17.14     1     1     1.10     1.91     0.04     0.04     0.993±0.0227     0.993±0.0213
toy1     toy2     12     31.54     75236     62880     0.43     0.47     47.36     53.13     5     3     4.74     3.66     0.08     0.07     0.987±0.0345     0.979±0.05

\begin{equation}
\label{eq:opt-problem}
\begin{aligned}
\argmin_{\phi} \quad &      E_f[\phi] + E_{d}[\phi] + \mathrm{Reg}[\phi]\\
\textrm{subject to} \quad & \phi \in \mathcal{P}.\\
\end{aligned}
\end{equation}

Quantitative results on all mesh pairs in our dataset. Our maps closely match the target boundaries while producing low distortion and few tetrahedron inversions. Here, $\ell$ denotes the number of landmarks. Time is measured in minutes.

2|l|Names      $\ell$     2c|$|\mathcal{T}_i|$     Time     2c|num inversions     2c|${\hat d}_{\max}  (\times 10^{-3})$     2c|${\hat d}_{\mathrm{avg}} (\times 10^{-3})$     2c|$|\det \hat J|$
scan_011     scan_019     23     36420     43527     29.2     3	     11      14.7     0.0782     0436     0491     0.958±0.108     0.95±0.118
scan_011     scan_030     19     36420     37588     23.2     1.06     0.564     1.04     0.564     0.0554     0.0705     0433     0493     0.964±0.0828     0.968±0.0683
scan_019     scan_039     16     43527     50713     35.5     1.08     1.39     1.05     1.29     0.0518     0.0622     0429     0459     0.955±0.107     0.952±0.116

B313 placenta_1

B313 placenta_2     7     151522     158977     105     0.066     0.703     0.0601     0.626     0.108     0.112     0887     0963     0.98±0.032     0.974±0.0732

C307 placenta (p.1)

C307 placenta (p.2)
5     64837     105693     187     0.273     1.29     0.23     1.06     0.0782     0.0844     0782     0751     0.964±0.0507     0.951±0.094
G308 placenta_100     G308 placenta_1     12     162762     177523     187     1.63     5.08     1.53     4.35     0.0719     0.0717     0549     0557     0.96±0.109     0.962±0.0976
airplane1     airplane2     7     24894     30700     40.6     0.245     1.92     0.233     1.83     0.0375     0.0522     0262     031     0.958±0.0891     0.909±0.186
armadillo     def. armadillo     21     81114     113794     69.2     0.0616     0.611     0.0616     0.606     0.0968     0.0969     0351     0345     0.98±0.0365     0.975±0.0476
bird_1     bird_2     12     30361     90810     27.2     0.0527     0.268     0.0527     0.255     0.0464     0.0402     0405     0408     0.982±0.0344     0.964±0.0649
cat0     cat1     17     17867     22988     18.7     0.509     0.761     0.504     0.713     0.0734     0.0665     0485     0435     0.976±0.0613     0.971±0.066
cat4     cat5     18     25985     22710     28.5     1.37     0.387     1.24     0.374     0.0719     0.0747     0526     0544     0.966±0.0826     0.971±0.0619
centaur0     centaur1     37     30357     26954     22.7     0.135     1.14     0.135     1.05     0.0679     0.0731     0417     0456     0.983±0.0353     0.978±0.0551
dancer     dancer2     13     58535     36902     86.9     2.56     1.52     2.28     1.49     0.0228     0.0244     0197     0231     0.864±0.236     0.916±0.166
dog4     dog5     27     31469     30160     29.7     1.03     1.1     0.963     1.05     0.0634     0.0647     0413     0425     0.962±0.0975     0.967±0.0844
dog6     dog7     24     26739     43771     60.3     1.75     3.18     1.7     3     0.0856     0.0652     0509     0418     0.945±0.111     0.923±0.161
dog7     dog8     25     81145     85128     92.8     0.535     1.17     0.531     1.11     0.0865     0.0893     0405     0427     0.985±0.0371     0.982±0.0573
dolphin_t     shark_t     9     129443     55440     59.6     5.77     10.1     3.63     7.86     0.0481     0.0785     0798     0.0149     0.732±0.363     0.718±0.413
dragon_stand     dragonstand2     28     109823     194651     30.8     0728     0.878     0455     0.87     0.0809     0.0824     0359     0364     0.993±0.0145     0.987±0.0317
fish1     fish2     8     64410     58215     167     4.33     1.5     4.06     1.41     0.0844     0.0728     0431     0394     0.916±0.211     0.95±0.124
glass1     glass2     13     30921     13439     25.9     3.95     2.21     3.84     2.21     0.02     0.0203     0273     0185     0.813±0.269     0.843±0.169
gorilla1     gorilla5     26     37417     59375     66.5     1.49     1.03     1.43     0.979     0.0812     0.0607     0579     0435     0.978±0.0535     0.963±0.0781
horse0     horse5     16     31507     34978     38.1     0.181     0.469     0.181     0.386     0.0863     0.0895     0439     0485     0.981±0.0603     0.979±0.0455
cow_t     horse_t     21     31694     32515     35.9     1.26     3.42     1.09     2.61     0.0869     0.114     0568     0614     0.954±0.111     0.951±0.107
human1     human2     21     56550     82581     81.8     0.401     2.09     0.394     2.04     0.0499     0.0628     0294     0352     0.973±0.0599     0.971±0.0709
michael0     michael7     20     19445     30014     30.7     0.453     1.65     0.453     1.6     0.0499     0.0399     0365     0289     0.985±0.0399     0.98±0.0526
seahorse2     seahorse4     22     13720     15667     13.9     0.19     0.702     0.19     0.702     0.0699     0.06     0365     031     0.986±0.0419     0.984±0.0359
toy1     toy2     12     75236     62880     49.1     0.106     0.398     0.102     0.347     0.127     0.131     0554     0553     0.975±0.0524     0.966±0.0788

Quantitative results on all mesh pairs in our dataset. Our maps closely match the target boundaries while producing low distortion and few tetrahedron inversions. Here, $\ell$ denotes the number of landmarks. Time is measured in minutes.

2|l|Names      $\ell$     2c|$|\mathcal{T}_i|$     Time     2c|$n_{inv}$     2c|${\hat d}_{\max}  (\times 10^{-2})$     2c|${\hat d}_{\mathrm{avg}} (\times 10^{-2})$     2c|$|\det \hat J|$
scan_011       scan_019       23     36420     43527     29.23     3     11     0.120     0.240     1.472     7.817     0.98±0.05      0.974±0.0545
scan_011       scan_030       19     36420     37588     11.39     2     0     0.099     0.116     1.828     2.520     0.981±0.0372      0.984±0.0275
scan_019       scan_039       16     43527     50713     17.57     0     2     0.124     0.143     1.574     1.996     0.976±0.0503      0.979±0.0456
airplane1       airplane2       7     24894     30700     28     8     12     0.097     0.117     2.333     2.344     0.968±0.0773      0.954±0.0979
armadillo       deformed_armadillo       21     81114     113794     75.89     2     3     0.049     0.056     1.146     1.390     0.99±0.0244      0.988±0.0259
244.1.ele     248.1.ele     12     30361     90810     19.55     0     7     0.055     0.077     1.231     1.154     0.987±0.0278      0.984±0.0318
cat0       cat1       17     17867     22988     9.86     0     1     0.081     0.081     1.984     1.732     0.984±0.0479      0.981±0.0467
cat4       cat5       18     25985     22710     14.05     5     5     0.129     0.111     3.919     2.892     0.98±0.0498      0.98±0.0496
centaur0       centaur1       37     30357     26954     13.70     1     3     0.052     0.073     1.037     1.423     0.993±0.0212      0.988±0.0299
dancer       dancer2       13     58535     36902     43.11     41     17     0.117     0.106     1.324     2.182     0.934±0.131      0.951±0.0909
dog4       dog5       27     31469     30160     17.04     7     3     0.090     0.102     2.287     2.266     0.979±0.0527      0.98±0.0538
dog6       dog7       24     26739     43771     33.92     3     14     0.196     0.168     76     2.380     0.961±0.0754      0.958±0.0863
dog7_VOL       dog8_VOL       25     81145     85128     71.15     4     9     0.082     0.121     2.858     4.784     0.992±0.031      0.992±0.0286
Dolphin_t       Shark_t       9     129443     55440     39.75     11     13     0.139     0.161     3.964     5.319     0.981±0.0576      0.981±0.0592
dragon_stand       dragonstand2       28     109823     194651     70.37     0     0     0.019     0.025     0.755     0.953     1±0218      1±0333
fish1       fish2       8     64410     58215     73.57     55     16     0.155     0.120     2.098     2.087     0.969±0.0872      0.969±0.0763
glass1       glass2       13     30921     13439     12.83     24     0     0.222     0.099     1.848     1.328     0.918±0.122      0.89±0.107
gorilla1       gorilla5       26     37417     59375     30.52     1     4     0.089     0.103     4.048     2.762     0.988±0.0326      0.978±0.0448
horse0       horse5       16     31507     34978     20.55     0     1     0.048     0.060     2.163     2.375     0.989±0.0414      0.99±0.027
Cow_t       Horse_t       21     31694     32515     20.09     17     18     0.134     0.228     2.247     3.426     0.978±0.0515      0.969±0.0641
human1       human2       21     56550     82581     42.27     0     33     0.062     0.097     1.670     2.091     0.988±0.0267      0.985±0.0428
michael0       michael7       20     19445     30014     19.53     1     4     0.055     0.070     1.746     1.463     0.992±0.0221      0.991±0.0269
seahorse2       seahorse4       22     13720     15667     8.24     1     1     0.041     0.037     1.099     1.906     0.993±0.0227      0.993±0.0213
toy1       toy2       12     75236     62880     31.54     5     3     0.075     0.075     4.737     3.661     0.987±0.0345      0.979±0.05