Deep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths
Authors: Ming Xu
Sourav Garg
Michael Milford
Stephen Gould
Venue: ICLR 2023 poster (2023)
Keywords: implicit differentiation
sequence matching
time series
visual localization
music

Abstract: This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW). Existing approaches to differentiable DTW either differentiate through a fixed warping path or apply a differentiable relaxation to the min operator found in the recursive steps used to solve the DTW problem. We instead propose a DTW layer based around bi-level optimisation and deep declarative networks, which we name DecDTW. By formulating DTW as a continuous, inequality constrained optimisation problem, we can compute gradients for the solution of the optimal alignment (with respect to the underlying time series) using implicit differentiation. An interesting byproduct of this formulation is that DecDTW outputs the optimal warping path between two time series as opposed to a soft approximation, recoverable from Soft-DTW. We show that this property is particularly useful for applications where downstream loss functions are defined on the optimal alignment path itself. This naturally occurs, for instance, when learning to improve the accuracy of predicted alignments against ground truth alignments. We evaluate DecDTW on two such applications, namely the audio-to-score alignment task in music information retrieval and the visual place recognition task in robotics, demonstrating state-of-the-art results in both.

Published as a conference paper at ICLR 2023
DEEP DECLARATIVE DYNAMIC TIME WARPING FOR END-TO-ENT LEARNING OF ALIGNMENT PATHS
Ming Xu Sourav Garg'
Michael Milford
Stephen Gould
"Queensland University of Technology AAustallian National University {mingda. xu, stephen. gould]@anu. edu. adu {s garg, qut edu
ABSTRACT
This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW). Existing approaches to differentiable DTW either differentiate through a fixed warping path or apply differentiable relaxation to the min operator found in the recursive steps used to solve the DTW problem. We instead propose a DTW layer based around bi- level optimisation and deep declarative networks, which name DecDTW. By formulating DTW as a continuous, incquality constrained optimisation problem, we can compute gradients for the solution of the optimal alignment (with respect the underlying time series) using implicit differentiation. An interesting byproduct of this formulation that DecDTW outputs the optimal warping path between two time series as opposed to soft approximation, recoverable from Soft-DTW. We show that this property is particularly useful for applications where downstream loss functions are defined on the optimal alignment path itself. This naturally occurs, for instance, when learning to improve the accuracy of predicted alignments against ground truth alignments. We evaluate DecDTW on two such applications, namely the -odioe alignment task in music information retrieval and the visual place recognition task in robotics, demonstrating state-of-the-an art results in both.
INTRODUCTION
The dynamic time warping (DTW) algorithm computes a discrepancy measure between two temporal sequences, which is invariant to shifting and non-lincar scaling time. Because of this desirable invariance, DTW is ubiquitous in fields that analyze temporal sequences such as speech recognition, motion capture, time series classification and bioinformatics (Kovar & Gleicher 2003) Zhu & Shasha 2003] Sakoe & Chiba 1978 Bagnall et al., 2017)) Petitjean et al.) 2014 Needleman & Wunsch] 1970). The original formulation of DTW computes the minimum cost matching between elements of the two sequences, called an alignment (or warping) path, subject to temporal constraints imposed on the matches. For two sequences of length m and n., this be computed by first constructing an m-by-n pairwise cost matrix between sequence elements and subsequently solving dynamic program (DP) using Bellman's recursion in (mn) time. Figure illustrates the mechanics of the DTW algorithm.
a) Classic DTW Alignment
Classic
Warping Path
Alignment
Warp
x.yl
x:y(f)
00-
62
11.25
1.00
240
0.00
0.5
Figure 1: Classic DTW (a) is discrete optimisation problem which finds the minimum cost warping path through a pairwise cost matrix (b). DecDTW uses continuous time variant of classic DTW (GDTW) (c) and finds optimal time warp function between continuous time signals (d).

---

Published as a conference paper at ICLR 2023
There has been interest in recent years around embedding DTW within deep learning models (Cuturi & Blondel 2017 Cai et al., 2019; Lohit et al.) 2019: Chang et al., 2019 202I), with applications spread across a variety of learning tasks utilising audio and video data (Garreau et al. 2014 Dvornik
et al. 2021] Haresh et al.
2021 Chang et al. 2019; 2021). especially where an explicit alignment step desired. There are several distinct approaches in the literature for differentiable DTW layers:
Cuturi & Blondell (017) (Soft-DTW) and Chang et al. (2019) use differentiable relaxation of min
the DP recursion, Cai et al. (2019) and Chang et al. (202I) observe that differentiation is possible after fixing the warping path, and others (Lohit et al. 22099; Shapira Weber et al. 2019 Grabocka & Schmidt- 2018 Kazlauskaite et 20191 Abid & Zou| 2018) regress warping paths directly from sequence elements without explicitly aligning. Note, methods based on DTW differ from methods such as CTC for speech recognition (Graves & Jaitly 2014), where word-level transcription is more important than frame-level alignment, and an explicit alignment step is not required.
We propose a novel approach to differentiable DTW, which we name DecDTTW, based on deep implicit layers. By adapting continuous time formulation of the DTW problem proposed by Deriso & Boyd (2019), called GDTW, as an inequality constrained non-linear program (NLP), we can use the deep declarative networks (DDN) framework (Gould al., 2021) to define the forward and backward passes in our DTW layer. The forward pass involves solving for the optimal (continuous time) warping path; we achieve this using a custom dynamic programming approach similar the original DTTW algorithm. The backward pass uses the identities in Gould et al. (2021) to derive gradients using implicit differentiation through the solution computed in the forward pass.
We will show that DecDTW has benefits compared to existing approaches based on Soft-DTW (Cuturi & Blondel 2017 Le Guen & Thome 2019 Blondel al. 202I);: the most important of which is that DecDTW W is more effective and efficient at utilising alignment path information in an end-to-end learning setting. This is particularly useful for applications where the objective of learning is to improve the accuracy of the aligmment itself, and furthermore, ground truth alignments between time series pairs are provided. We show that using DecDTW yields both considerable performance gains and efficiency gains (during training) over Soft-DTWW (Le Guen & Thome, 2019) in challenging real-world alignment tasks. An overview of our proposed DecDTW layer is illustrated in Figure 2
First, propose novel, inequality constrained NLP formulation of the DTW problem, building on the approach in Deriso & Boyd (019)). Second, we use this NLP formulation to specify our novel DecDTW layer, where gradients in the backward pass computed implicitly as in the DDN framework (Gould et al., 2021). Third, we show how the aligmment path produced by DecDTW can be used to minimise discrepancies to ground truth alignments. Last, we use our method to attain -fae--of-the-are performance on challenging real-world alignment tasks.
Our Contributions
2 RELATED WORKS
Differentiable DTW Layers Earlier approaches to learning with DTW involve for each iteration, alternating between first, computing the optimal alignment using DTW and then given the fixed alignment, optimising the underlying features input into DTW. Zhou & De la Torre 2009); Su & Wu (2019); (hou & De la Torre (012) analytically solve for a linear transformation of raw observations. More recent work such as DT Wett (Cai et al. 2019) and DP-DTW (Chang et al. (221 instead take a single gradient step at each iteration to optimise a non-linear feature extractor. All aforementioned methods are not able to directly use path information within downstream loss function.
Differentiable Temporal Alignment Paths Soft-DTWW (Cuturi & Blondel| 2017) is a differentiable relaxation of the classic DTW problem, achieved by replacing the min step in the DP recursion with a differentiable soft-min. The Soft-DTW discrepancy is the expected alignment cost under a Gibbs distribution over alignments, induced by the pairwise cost matrix A and smoothing parameter
0. Path information is encoded through the expected alignment matrix, A = [.[[A]
Vadtw, (X. Y) (Cuturi& & Blondel 2017). While A;, is recovered during the -oft-DTW backward
pass, differentiating through At, involves computing Hessian V dtw,, (X,,, Y). Le Guen & Thome (2019) proposed an efficient custom backward pass to achieve this. A loss can be specified over paths through penalty matrix Ωt which for instance, can encode the error between the expected predicted path and ground truth. Note, at inference time, the original DTW problem (i.e., y = 0) is solved to generate predicted alignments, leaving disconnect between the training loss and inference task.
2

---

Published as a conference paper at ICLR 2023
Soft-DTW
DecDTW
Train
Inference
Train
Inference
M
Lass
RM Optinal
Expecied path 4 Br(A
2(4)) m (At.0)
Dxo'<
loss ng. sels
Sxl--
GOTW
4
P 2
Dvge*
Ragulariaat and corerra - g gthe brwn, brnne)
ot ER
FFovvo 2001
Det
Figure 2: Learning with path information. Left: Using Soft-DTW, one can define a loss between the soft, (i.c., >> 0) expected alignment path against a penalty matrix S2. During inference, DTW (i.c., 7 = 0) must be used produce a predicted alignment. Right: Our DecDTW outputs the optimal warping path & using GDTW at both train and inference time, removing the disconnect present in Soft-DTW. DecDTW also allows the regularisation and constraint values to be learnable parameters.
In contrast, DecDTW deviates from the original DTW problem formulation entirely, and uses a continuous-time DTW variant adapted from GDTW (Deriso & computes a minimum cost, continuou ali alignment path between two continuous time signals. We will provide detailed explanation of GDTW in Section 3 DecDTW allows the optimal alignment path 6 to be differentiable (w.rt. layer inputs), as opposed to a soft approximation from Soft-DTW. As result, the gap between training loss and inference task found in Soft-DTW is not present under DecDTW. In our experiments, we show that using DecDTT to train deep networks to reduce alignment error using ground truth path information greatly improves compares Soft-DTW and DecDTW for learning with path information.
The GDTW problem
Soft-ITWW. Figure)
Deep Declarative Networks The declarative framework that allows us incorporate differentiable optimisation algorithms into a deep network is described in Gould et al. (022)). They present theoretical results and analyses on how differentiate constrained optimization problems via implicit differentiation. Differentiable convex problems have also been studied recently, including quadratic programs (Amos& Kolter 2017) and cone programs (Agrawal et al. 2019a b). This technique has been applied to various application domains including oprimisation-baseee control (Amos et al. 2018 video classification (Fernando Gould 2016 2017). action recognition (Cherian et al.] 2017). visual attribute ranking (Santa Cruz et al. 2019), few-shot learning for visual recognition (Lee et al. 2019 and camera pose estimation (Campbell et al., 2020 Chen et al. 2020). To the best of our knowledge
this is the first embedding of inequality constramed NLP within declarative layer.
CONTINUOUS TIME FORMULATION FOR DTW (GDTW)
In this section, we introduce a continuous time version of the DTW problem which is heavily inspired by GDTWW (Deriso & Boyd, 2019). The GDTW problem is used derive the NLP formulation for our DecDTTW layer. We will describe how the results in this section can be used to derive a corresponding NLP in Section
3.1 PRELIMINARIES
Signal A time-van varyingrying signal x [0, 1] Rd vector-valued function of time. Signals are assumed to be differentiable (at least piecewise smooth) and can be constructed from a time series comprised observation times t E [0, 1| where
i < l2 < <... < IN < and associated observations features given by X = {xi,.... ...,.... .N E R xx by interpolating between observations (e.g., linear, cubic splines). Without loss generality, we rescale time for all signals to [o, 1].
Time warp function A time warp function o [0, 1] + [0, 1] defines correspondences from times in one signal to another, and is similarly assumed to be piecewise smooth. Warp functions typically come with constraints; common constraint requires that warp functions are non-decreasing, ie., ø'(t (t) 2 0 for all t. We interpret x o 6 to be the time warped version of x.
Dynamic time warping The GDTW problem can be formulated as follows. Given two signals and y, find a warp function & such that y ó zs x in some sense over the time series features. In other words, wish to bring signals and y together by warping time in y. Figure TigureeTillusraate iillustrates
3

---

Published as a conference paper at ICLR 2023
a]
Underlying Signals
b) Effect Regularisation
c) Effect Constraints
1.0
x/yr(t)
68
64-
6.-
glcbal
local
0.
010
8
Figure Regularisation (b) and constraints (c) can applied to prevent pathological warps, e.g., À O in (b). Global and local constraints bound warp function values and derivatives, respectively.
how GDTW differs from classic DTW for an example sequence pair. We found our experiments that GDTW outperformed DTW generally for real-world alignment tasks. We attribute this to the former's 's ability to align in between observations, thus enabling a more accurate alignment.
3.2 OPTIMISATION PROBLEM FORMULATION FOR GDTW
GDTW can be specified constrained optimisation problem where the decision variable is the time warp function & and input parameters are signals x and y. Concretely, the problem given by
minimise
f(x. y, A. Φ) - L(x,y, y, Φ) XR( S
subject to
b(t) min S o(t)) S b(t)
Vt.
(I)
constraints
global
The objective function f can be decomposed into the signal loss L relating to feature error and warp regularisation term R, where 0 is a hyperparameter controlling the strength of regularisation. Since Φ, and y are functions, our objective function f is a functional, revealing the variational nature of the optimisation problem. We will see in Section 4 that restricting to the space of piecewise linear functions will allow us to easily solve Equation while still allowing for expressive warps.
Furthermore, number of potentially time-varying constraints usually imposed on 6. We partition these constraints into local and global constraints as in Morel et al. (2018). Local constraints bound the time derivatives of the warp function and can be used to enforce the typical nondecreasing warp assumption. Global constraints bound the warp function values directly. with prominent examples being the R-K (Ratanamahatana & Keogh 2004) and commonly used Sakoe-Chiba (Sakoe) & Chiba 1978) bands. Furthermore, global constraints are used to enforce boundary constraints, i.e., ((t) [0, for all and endpoint constraints, i... ((0) = 0, ((1)
Not including endpoint constraints allows for subsequence GDTW, where a subsequence is aligned to only a portion of x. Figure illustrates how constraints can be used change the resultant warps returned by GDTW.
Signal Loss
The signal loss functional L in Equation is defined as
C(x,y, 6) L x((()))(
where Rd + a twice-differentiable (a.e.) penalty function defined over features. our experiments we use L(-) & - 112. however other penalty functions (c.g., the 1-norm, Huber loss) can be used. The signal loss (Equation]) 2 measures the separation of features between and time- wareed y and is analogous to the classic DTW discrepancy given by the cost along the optimal warping path.
Warp Regularisation
The warp regularisation functional R in Equation is defined
R(Ø) J. R(0'(t) 1)ddt
where R: R is a penalty function on deviations from the identity warp. i.e. ('(t) 1. We use quadratic penalty R((u) x² in this work, consistent with Deriso & Boyd 2019). This regularisation term penalises warp functions with large jumps and a sufficiently high brings ø close to the identity. Regularisation is crucial for preventing noisy and/or pathological warps (Zhang et al. 2017 Wang (tt al. (0166) from being produced from GDTW (and DTW, more generally), and can greatly affect alignment accuracy. We select optimally using cross-validation (Deriso & Boyd 2019
4

---

Published as a conference paper at ICLR 2023
4 SIMPLIFIED NLP FORMULATION FOR GDTW
While Section B provides a high-level overview of the GDTW problem, we did not specify a concrete parameterisation for d, which dictates how the optimisation problem in Equation 3 will be solved. In this section, we provide simplifying assumptions on é, which allows us to solve Equation 3 We follow the approach in Deriso & Boyd (2019) to reduce the infinite dimensional variational problem in Equation[] to a finite dimensional NLP. This is achieved by first assuming that Φ is piecewise linear, allowing it to be fully defined by its value m knot points 0-
l2 < .... Lm 1. Knot points can be uniformly spaced or just be the observation times used to parameterise
Formally,
piecewise linearity allows us represent & as Φ (01...... pm) E F where Φ; = ((t,). The other crucial assumption involved in reducing Equation to an NLP is replacing the continuous integrals in the signal loss and warp regularisation in Section 3 with numerical approximations given by the trapezoidal rule. These assumptions yield an alternative optimisation problem given by
minimise
f(x, y, X, Φ)) y Φ) + XR(Φ)
(4)
subject to s..in I 91+1-0:
Al. I s.
bmin S 0i S 1/Tax
Vi,
where At, = ti+1 - -t. The new signal loss L is given by
.b) Σ Lisi Li Ali, 1 L(x(t)) y
((x,y,
(5)
2
which follows from applying the definition of and the trapezoidal approximation Equation Note, the non-convexity of objective (even when assuming convex L and R) caused by the x(o:) terms for arbitrary signal x. The new regularisation term is given by
2
R(6) = Σ R 1=1
m1
10+1- - di 1) Ali,
(6)
Al;
noting that since ø' is assumed to be piecewise constant, we can simply use Riemann integration to evaluate the continuous integral R exactly. The simplified problem in Equation 4 is actually a continuous non-linear program with decision variable & R" and linear constraints. However, the objective function is non-convex (Deriso & Boyd, 2019)) and we will now describe the method used to find good solutions Equation 4 Juing approximate dynamic programming.
5 DECLARATIVE DTW FORWARD PASS
Our DecDTW layer encodes an implicit function o- DecDTW(x: A, s, smaax, bin bmxx), which yields the optimal warp given input signals x, y, regularisation À and constraints min {smin) 1= max = {s! /==1 min [bmin) 1e max [b!nax ) The warp Ø² can be used in a downstream loss J(Ø'), e.g. the error between predicted warp 6* and ground truth warp da
The GDTW discrepancy is recovered by setting J = f. Compared to Soft-DTW (Ctturi & Blondel 2017), which produces soft alignments, DecDTW outputs the optimal, continuous time warp. The DecDTW forward pass solves the GDTW problem given by Equation 4 given the input parameters.
We solve Equation 4
Jusing a dynamic programming (DP) approach as proposed in Deriso & Boyd (2019) instead of calling general- -prepos NLP solver; this is to minimise computation time.
The DP approach uses the fact that & lies on compact subset of I defined by the global bounds, allowing for efficient discretisation. Finding the globally optimal solution to the discretised version of Equation 4 can be done using DP. The resultant solution Ø* an approximation the solution of the continuous NLP, with the approximation error dependent on the resolution of discretisation. We can reduce the error given a fixed resolution M using multiple iterations of refinement. tighter discretisation is generated around the previous solution and the new discrete problem solved. A detailed description of the solver can be found in Deriso & Boyd (2019) and the Appendix.
each iteration,
Note, for the purpose of computing gradients in the backward pass, detailed in Section 6 it is important that the approximation 6² is suitably close to the (true) solution of Equation 4 Otherwise, the gradients computed in the backward pass may diverge from the true gradient, causing training to be unstable. The accuracy of Ø² is highly dependent on the resolution of discretisation and number of refinement iterations. We discuss how to set DP solver parameters in the Appendix.
5

---

Published as a conference paper at ICLR 2023
6 DECLARATIVE DTW BACKWARD PASS
We now derive the analytical solution of the gradients of o recovered in the forward pass w.r.t inputs fx, y, X, smin, smax bmin bmax) IR" using Proposition 4.6 in Gould et al. (0221) (note that gradients w.r.t. signals x, y are w.r.t. the underlying observations X, Y). Unlike existing approaches for differentiable DTW, DecDTW allows the regularisation weight À and constraints to be learnable parameters in deep network. Let h [h1,- 1ppl, where each h; IR x IR - R corresponds to an active constraint from the full set of inequality constraints described in Equation [ rearranged in standard form, i.c., (-)-) S For instance, an active local constraint relating time łj can be expressed as (z, Φ) = 0j+1 63- - Stj < O. Assuming non-singular И (note, this always holds for norm-squared and R) and rank (z, x)) = p. the backward pass gradient is given by
DΦ(z)= - A (AHI (AH B C) H
(7)
where DØ(z) E Rmxx is the Jacobian of estimated warp Φ w.r.t. inputs z and
A Dæh(z, Φ)) RRxm
B= D 2 f (z, 12, () Rmx
(8)
C Dzh(z, Φ) E R H = 04. f (z. Φ) E Rm
Observe that the objective f as defined in Equation [ only depends on subset of z corresponding to v, À and similarly, constraints h only depend on s!iin s b max While Proposition 4.6 in Gould et al. (202I) has additional terms in B and H involving Lagrange multipliers, we note that since á is at most first order w.r.t. {z, 6). these terms evaluate to be zero and can be ignored. We discuss how to evaluate Equation? 7 [siing vector-Jacobian products efficiently in the Appendix.
7 EXPERIMENTS
Our experiments involve two distinct application areas and utilise real-world datasets. For both appli- cations, the goal is to use learning to improve the accuracy predicted temporal aligmments using a training set of labelled ground truth alignments. We will show that DecDTW yields state-of-the-art per- formance on these tasks. We have implemented DecDTW in PyTorch (Paszke et al. 2019) with open source code available to reproduce all experiments at https://github httppp://giiaubooo//mmmnuddddddd wwtp:///wimmmi.dddddoatttteeee..
7.1 LEARNING FEATURES FOR AUDIO-TO-SCORE ALIGNMENT
Problem Formulation Our first experiment relates to audio-to tiddio-to-ccon -o-eetor--eeeeeeee alignment, which is a fun- damental problem in music information retrieval (Thcckstun et al., 2020; [wwert et al., 2009; Orio Øt al. 2001: Shalev-Shwarte et al. 2004), with applications ranging from score following to music transcription (Thickstun al. 2020). The goal of this task is to align audio recording of music performance to its corresponding musical score/sheet music. We use the mathematical formulation proposed in Thickstun al.) (2020) for evaluating predicted audio-to-score alignments against ground truth alignment, which we will now summarise. An alignment is monotonic function score (measured in beats) to a corresponding position
6: (0, S) + [0, 7' which maps positions in the performance recording (measured in seconds). Two evaluation metrics between predicted alignment & and a ground truth alignment de are proposed, namely the temporal average error (TimeErr) and temporal standard deviation (TimeDev), given formally by
1 S TimeErr(ó, det) 1 (o(s) 00t0 (s)lds, TimeDev (8
1 S V J (6(s) (s)
Thickstun et al. (2000) assumes alignments are piecewise linear in between changepoints (where the set of notes being played changes) within the score, allowing Equation 9
to be analytically tractable.
Methodology Thickstun et al. (2020) provide a method for generating candidate alignments between performance recording and a musical score as follows: First, synthesize the musical score (using a MIDI file) to an audio recording. Second, extract audio features from the raw audio for both the synthesised score and performance. Third, use DTW to align the two sets of features. Last, use Equation to evaluate the predicted alignment. In these experiments, we learn a feature extractor on top of the base audio features with the goal of improving the alignment accuracy from DTW.

---

Published as a conference paper at ICLR 2023
Mckipes Bag (G) (TineEr 336ms)
Query
Basa (G)
DecDTW
DecTTW TTmmerr
(we)
(a)
(b)
Figure (a) Example audio-to sostoo-t--coreeeeee alignment. Red (resp. yellow) identifies notes indicated by audio feature (resp. ground truth) alignments, but not by the ground truth (resp. audio features). DecDTW training yields dramatic improvements for melspec features, even surpassing highly optimised CQT features (38ms TimeErr). (b) Example VPR alignment. Query images are aligned sequence using learned image embeddings. Magenta (resp. green) illustrates where the pre-trained (resp. fine-tuned) system estimates the query poses using database geotags. The max (resp. mean) error reduced from 7.8m to 2.7m (resp. 4.6m to 1.5m) after fine-tuning.
database
We use the dataset in Thickstun et al. (2020), which is comprised of 193 piano performances of 64 scores with ground truth alignments taken from a subset of the MAE- STRO (Hawthorne et al. 2019) and Kernscores (Sapp, 2005) datasets. We extract three types of base frequency-dome doquunncy-domain features from the raw audio: constant- transform (CQT), Jog-mmamrmma (chroma) and (log-)mel spectrogram (melspec). The CQT and chroma features are already highly optimised for pitch compared to melspec features. However, melspec features retain more information from the raw audio compared to CQT and chroma. We evaluated six different methods, described as follows: 1-2) use base features (no learning) and both DTW (D) and GDTW (G) for alignments. For the remaining methods (3-6), each learns feature extractor given by Gated Recurrent Unit (GRU) (Cho et al. 2014), on top of the base fcatures. The learned features are then used to compute the corresponding loss, described follows: 3) Soft-DTWW (Cuturi & Blondel 2017) discrepancy loss; 4) feature matching cost along ground truth alignment path (Along GT); 3) DILATE Le Guen & Thome (2019), which uses path information through the soft expected alignment under Soft-DTW; and 6) TimeErr loss training (DecDTW only). For DILATE, we encode the deviation from the ground truth alignment in the path penalty matrix Q. The full set of hyperparameters. including dataset generation and further information on comparison methods are provided in the Appendix.
Experimental Setup
Table I: Summary of results for the audio-to-score alignment experiments
Reported metrics TimeFrr / TimeDev (ms)
Feature Type
Base (D)
Base (G)
Soft-DDTW
Along GT
DILATE
DecDTTW
CQT
/0
19/30
49 130
49 130
29/45
17/ 27
Chroma
50 115
24/39
59 142
59 / 142
28 /1
19 19/31
Melspec
122 / 235
81
55 153
52 145
26/40 40
16 27
Results A summary of results is presented in Table DTW is used for alignments in Base (D), Soft-DTW, Along GT and DILATE, while GDTW used for alignments for Base (G) and DecDTW. Training using Soft-DTW fails to improve alignment performance over the yalidation set, measured by TimeErr, because the ground truth alignment is not used during training"] Similarly, minimising the feature matching cost along the ground truth alignment path fails to improve alignment accuracy, since the predicted alignment is not used during training. DILATE, however, significantly improves on Base (D) since it incorporates predicted and ground truth path information during training.
Similarly to DILATE, training using the TimcErr loss with DecDTW significantly improves the alignment accuracy compared to Base (G), effectively utilising both predicted and ground truth path information. DecDTW yields state-of-the-art results overall for all base feature types by a large margin. Note the already the strong performance of Base (G) over both Base (D) and even DILATE
'Tee randomly initialised GRU feature extractor also degrades alignment accuracy compared hase features.

---

Published as a conference paper at ICLR 2023
(for CQT and chroma); this demonstrates the benefit of using continuous time GDTW alignments. Finally, it is interesting to note that both DILATE and DecDTW are able to utilise the more expressive (versus CQT and chroma) melspec features to surpass the performance of base CQT and chroma. Figure illlstrras an example test alignment, with more examples provided in the Appendix.
7.2 TRANSFER LEARNING FOR SEQUENCE-BASED VISUAL PLACE RECOGNITION
Our second experiment relates the Visual Place Recognition (VPR) problem, which is an active area of research in computer vision (Berton et al. 2022 Arandjelovic et al. 2016) and robotics (Garg et al. 2021 Lowry et al., 2015 Cummins & Newman 2011) and is often an important component of the navigation systems found in mobile robots and autonomous cars. The VPR task involves recognising the approximate geographic location where an image is captured, typically
tolerance of a few meters (Zaffar et al. 2021: Berton et al. (022) and is commonly formulated as image retrieval, where a query image is compared to a database of geo-tagged reference images. VPR using image sequences has been shown to improve retrieval performance over single image methods (Garg & Milford [02T]] Xu et al. 2020 Stenborg et al., (020). In this experiment we first formulate sequence-based VPR as a temporal alignment problem and then fine-tune a deep feature extractor for this alignment task.
Problem formulation Let (T)) t" E R.N and [x]][_] be a reference image sequence, as- sociated (sorted) timestamps and geotags, respectively. Similarly, let [i to R and X === be the equivalent for query sequence, noting that query geotags are used only for training and evaluation. Furthermore, when using deep networks for VPR, we have feature extractor fo with weights 9 that is used extract embeddings Z = {[,)) E E Nxd and z {fo(4)) IR M from reference and query images, respectively. Finally, x", x², z", z be continuous time signals built from geotags and image embeddings using associated timestamps.
We can formulate sequence-based VPR as temporal alignment problem, where the objective is to minimise the discrepancy between the predicted alignment derived from the query and reference image embeddings and the optimal alignment derived from the geotags. Concretely, the goal of our learning problem is to minimise w.r.t. network weights 0, measure of localisation error G (Φ), X9), where :2:0) () defined as Φ; = (t(?)) the estimated alignment which maps query images to positions in the reference sequence and x" (Ø) maximum error over the queries, given by G(X X²) max
& = (TW(z", 2";
( We select G as the (squared)
x² = =ii=,... M.}.
Experimental setup We source images and geotags from the Oxford RobotCar dataset (Maddemn et al. 2017), commonly used as benchmark to evaluate VPR methods. This dataset is comprised of autonomous vehicle traverses of the same route captured over two years across varying times of day and environmental conditions. We use a subset of ~ 1M images captured across 50+ traverses provided by Thoma et al. (020)) with geotags taken from RTK GPS (Maddern et al., 2020 where available, accurate to 15cm. These images are split into training, validation and test sets, which are methods. The train and validation sets are captured in the same geographic areas on distinct dates whereas the test set is captured in an area geographically disjoint from validation and training.
used to train a base network for single image retrieval as well as our sequence
Paired sequences are generated using the GPS ground truth; reference sequences have 25 images spaced ~55m apart and query sequences have 10 images sampled at 1z. This setup is close to a deployment scenario where geotags are available for the reference images and query images exhibit large changes in velocity compared to the reference. Subsequence GDTW is used to align queries to the reference sequence. In total, we use 222, 44k 1.7k sequence pairs for training, validation and testing, respectively. Our test set contains a diverse set of sequences over large geographic area, and exhibits lighting, seasonal and structural change between reference and query. We provide our paired sequence dataset in the supplementary material. Finally, for feature extraction, we use a VGG backbone with NetVLAD aggregation layer (Arandjelovic et al. 2016) (yields 32k-dim embeddings) and train the single image network using triplet margin loss. We fine-tune the conv5 and NetVLAD layers for sequence training. See the Appendix for a detailed description of the training setup.
Results We evaluate all methods by measuring the proportion of test sequences where the maximum error is below predefined distance thresholds; these metrics are commonly used for single image methods (Garg et al. 2021 Berton et al. 2022p. Results are split into three different environmental conditions including overcast, sunny and snow. We present results for two methods using the base single image network (1-2) and four methods which perform fine-tuning of the base network for
8

---

Published as a conference paper at ICLR 2023
sequence VPR (3-6): 1-2) Base features (no sequence fine-tuning) with DTW (D) and GDTW (G) alignment, 3) OTAM Cao et al. (2020) (Soft-DTW w/subsequence alignment) discrepancy. 4) Feature cost along the ATE minimising alignment (Along GT), 5) DILATE loss and 6) max enror loss (DecDTW). Similar to the audio experiments, DTW was used to produce alignments for methods (3-5) and GDTW was used for (6). For DILATE, we again modified the path penalty matrix Ω to encode the deviation from the ground truth path. Table summarises the results.
Table 2: VPR experiment results (maximum error): Test Accuracy @ @2/3/5/10m
Method
Overcast
Sunny
Snow
Base (D)
0.7/12.3/44.3/73. 10.2/31.7/65.6/9003 9,0/33.2/55.1/993
1.6/11.1/44.//6..3
Base (G)
6.2/25.7/73.2/1000
OTAM/Along GT
0.7/12.3/44.3/73.8
0.5/8.7/40.2/62.2
1.6/11.1/44.3/2.33
DILATE
0.7/14.5/54.5/80.0
1.5/11.//40.9699.
1.3/12.2/44.6/68.
DecDTW
25.4/45.0068.3/9011
22.8/50.4/84.3/98.3
13.5/44.8/88.0/1000
We found that fine-tuning with the OTAM and Along GT losses is not able to reduce localisation error over the validation set compared to using base features. This because the OTAM loss does not use GPS ground truth and the Along GT loss does not use the predicted alignment. DILATE, which utilises path information, improves over Base (D), especially for the 5-10m error tolerances. However, training with DecDTW to directly reduce the maximum GPS error between predicted and ground truth yields significant improvements compared to Base (G) across tighter (S 5m) error tolerances. Similar to the audio experiments,
see the benefit of using GDTW alignments over DTW when comparing Base (G) to Base (D) and DILATE. However, DecDTW improves over Base (G) substantially more compared DILATE over Base (D) when compared the audio experiments. We provide more results and ynil for the VPR task in the Appendix. Figure 4b illustrates an example of a test sequence before and after fine-tuning, with more examples provided in the Appendix.
7.3 SCALABILITY
Figure 5 illustrates how inference test time scales with time series length n for GDTW (required for DecDTW) compared to evaluated on Nvidia GeForce GTX 1080Ti
10
DTW. Timings
Computation time (s)
11Gb GDTW is between 15-50 times slower than DTW, with the gap increasing with length n. The additional computation due
10%
in large part to the additional discretisation required to solve for the finer-grained continuous time problem defined in Section [ DTW solves DP with (mm) nodes and O(mn) edges, whereas GDTW solves a DP with (mM) edges and O(m 22) edges (we
10-1
GDTW
10-2
GDTW approx.
set M n)) However, by removing iterations of warp refinement, we can reduce this gap to a 4-12x slowdown with an mean accuracy loss of only 0.5%. Further discussion and comparison of train- time scalability is provided in the Appendix.
200
800
T Time series length
Figure 5: Test time scalability
8 CONCLUSION AND FUTURE WORKS
We present a novel formulation for a differentiable DTW layer that can be embedded into a deep network, based on continuous time warping and implicit deep layers. Unlike existing approaches, DecDTW yields the optimal alignment path as a differentiable function of layer inputs. We demon- strate the effectiveness of DecDTW in utilising path information challenging, real-world alignment tasks compared to existing methods. One promising direction for future work is in exploring more compact, alternative parameterisations of the warp function to improve scalability, inspired by Zhou & De la Torre (2012). Another direction would be to integrate more sophisticated DTW variants such as JTW Fremmery et al. 2010). which allows for repeats and discontinuities in the warp, into the GDTW (and De)DTW) formulation. Finally, we presented methodology for allowing regulari- sation and constraints to be learnalle parameters in a deep network but did not explore this in our experiments. Future work will also explore this capability in more detail.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
S. Garg and M. Milford are with the QUT Centre for Robotics, School of Electrical Engineering and Robotics at the Queensland University of Technology. M. Xu and S. Gould are with the School of Computing. College of Engineering, Computing and Cybernetics at the Australian National University. The majority of the work was completed while M. Xu was at the QUT Centre for Robotics. M. Xu was supported by an Australian Government Research Training Program (RTP) Scholarship as well as by the QUT Centre for Robotics. M. Milford is supported by funding from ARC Laureate Fellowship (FL210100156) funded by the Australian Government. S. Gould is the recipient of an ARC Future Fellowship (FT200100421) funded by the Australian Govermment. Finally, we thank the reviewers and the area chair for their insightful and constructive comments during the discussion period.
REPRODUCIBILITY STATEMENT
To facilitate reproducibility, we provide a reference implementation for our method, including code to reproduce all results across both of the experiments presented in the paper. Our code provides the full training and evaluation pipeline for all methods. In addition, we provide detailed instructions for setting up the datasets for training and evaluation, again for both experiments, per the descriptions provided in the Appendix. Furthermore, we make publicly available the model checkpoint for the pre-trained single-image baseline network used for sequence fine-tuning in the VPR experiments.
REFERENCES
Abubakar Abid and James Y Zou. Learning Warping Distance from Unlabeled Time Series Using Sequence Autoencoders. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and Z. Kolter. Differentiable Convex Optimization Layers. Advances in Neural Information Processing Systems (NeurIPS), 2019a.
A. Agrawal, S. Barratt, Boyd, E. Busseti, and W. Moursi. Differentiating through a Cone Program. Journal of Applied and Numerical Optimization, 1(2):107-115, 2019b.
Brandon Amos and J. Zico Kolter. OptNet: Differentiable Optimization a Layer in Neural Networks. In Proc. of the International Conference on Machine Learning (ICML), 2017.
Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and J. Zico Kolter. Differentiable MPC for End-to-end Planning and Control. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Relja Arandjelovic, Petr Gronat, Akihiko Torii, Tomas Pajdla, and Josef Sivic. NetVLAD: CNN architecture for weakly supervised place recognition. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Anthony Bagnall, Jason Lines, Aaron Bostrom, James Large, and Eamonn Keogh. The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances. Data Mining and Knowledge Discovery, 31, 2017.
Gabriele Berton, Riccardo Mereu, Gabriele Trivigno, Carlo Masone, Gabriela Csurka, Torsten Sattler, and Barbara Caputo. Deep Visual Geo-localization Benchmark. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Mathieu Blondel, Arthur Mensch, and Jean-Philippe Vert. Differentiable Divergences Between Time Series. In Proc. of International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Xingyu Cai, Tingyang Xu, Jinfeng Yi, Junzhou Huang, and Sanguthevar Rajasekaran. DeWNet: Dynamic Time Warping Network. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Dylan Campbell, Liu Liu, and Stephen Gould. Solving the Blind Perspective- Pointt Problem End- To-End With Robust Differentiable Geometric Optimization. In Proc. of the European Conference on Computer Vision (ECCV), 2020.
10

---

Published as a conference paper at ICLR 2023
Kaidi Cao, Jingwei Ji, Zhangjie Cao, Chien-Y. Yi Chang, and Juan Carlos Niebles. Few-Shot Video Classification via Temporal Alignment. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Chien-Yi Chang, De-An Huang, Yanan Sui, Li Fei-Fei, and Juan Carlos Niebles. D3TW: Dis- criminative Differentiable Dynamic Time Warping for Weakly Supervised Action Alignment and Segmentation. In Proc. of the IEEF/CVF Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
Xiaobin Chang, Frederick Tung, and Greg Mori. Learning Discriminative Prototypes with Dynamic Time Warping. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Bo Chen, Alvaro Parra, Jiewei Cao, Nan Li, and Tat-Jun Chin. End-to-End Learnable Geometric Vision by Backpropagating PnP Optimization. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Anoop Cherian, Basura Fernando, Mehrtash Harandi, and Stephen Gould. Generalized Rank Pooling for Activity Recognition. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Kyunghyun Cho, Bart van Merrienboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. In Proc. of the Workshop on Syntux, Semantics and Structure in Statistical Translation (SSST-8), 2014.
Mark Cummins and Paul Newman. Appearance-only SLAM at large scale with PAB-MAP2.1 2.0. The International Journal of Robotics Research, 30, 2011.
Marco Cuturi and Mathieu Blondel. Soft-DTW: a Differentiable Loss Function for Time-Series, In Proc. of the International Conference on Machine Learning (ICML), 2017.
Dave Deriso and Stephen Boyd. A general optimization framework for dynamic time warping. arXiv preprint ar
2019.
Mikita Dvomik, Isma Hadji, Konstantinos G Derpanis, Animesh Garg, and Allan Jepson. Drop-DTW: Aligning Common Signal Between Sequences While Dropping Outliers. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Sebastian Ewert, Meinard Muller, and Peter Grosche. High resolution audio synchronization using chroma onset features. In Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2009.
Basura Fernando and Stephen Gould. Learning End-to-end Video Classification with Rank-Pooling. In Proc. of the International Conference on Machine Learning (ICML), 2016.
Basura Fernando and Stephen Gould. Discriminatively Learned Hierarchical Rank Pooling Networks. International Journal of Computer Vision, 2017.
Christian Fremerey, Meinard Müller, and Michael Clausenr. Handling Repeats and Jumps in Score- Performance Synchronisation. In International Society for Music Information Retrieval Conference (ISMIR). 2010.
Sourav Garg and Michael Milford. SeqNet: Learning descriptors for sequence-based hierarchical place recognition. IEEE Robotics and Automation Letters, 6, 2021.
Sourav Garg, Tobias Fischer, and Michael Milford. Where Is Your Place, Visual Place Recognition? In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), 2021.
Damien Garreau, Rémi Lajugic, Sylvain Arlot, and Francis Bach. Metric Learning for Temporal Sequence Alignment. In Advances in Neural Information Processing Systems, 2014.
Stephen Gould, Richard Hartley, and Dylan Campbell. Deep Declarative Networks. IEEE Transac- fions Pattern Analysis and Machine Intelligence (TPAMI), 2021.

---

Published as a conference paper at ICLR 2023
Josif Grabocka and Lars Schmidt- Thieme. Neuralwarp: Time-series similarity with warping networks. arXiv preprint 1rX.v:812.008366, 2018.
Alex Graves and Navdeep Jaitly. Towards end-to-end speech recognition with recurrent neural networks. In Proc. of the International Conference on Machine Learning (ICML), 2014.
Sanjay Haresh, Sateesh Kumar, Huseyin Coskun, Shahram N. Syed, Andrey Konin, Zeeshan Zia, and Quoc-Huy Tran. Learning by Aligning Videos in Time. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Curtis Hawthorne, Andriy Stasyuk, Adam Roberts, Ian Simon, Cheng-Zhi Anna Huang, Sander Dieleman, Erich Elsen, Jesse Engel, and Douglas Eck. Enabling Factorized Piano Music Modeling and Generation with the MAESTRO Dataset. In Proc. the International Conference on Learning Representations (ICLR), 2019.
leva Kazlauskaite, Carl Henrik Ek, and Neill Camphell. Gaussian Process Latent Variable Align- ment Learning. In Proc. of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. of the International Conference on Learning Representations (ICIR), 2015.
Lucas Kovar and Michael Gleicher. Flexible Automatic Motion Blending with Registration Curves. In Proc. of the 2003 ACM SIGGRAPH/EEungrrahhics Symposium on Computer Animation, 2003.
Vincent Le Guen and Nicolas Thome. Shape and time distortion loss for training deep time series forecasting models. In Advances in Neural Information Processing Systems (NeurlPS), 2019.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-Learning With Differentiable Convex Optimization. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Suhas Lohit, Qiao Wang, and Pavan Turaga. Temporal Transformer Networks: Joint Learning of Invariant and Discriminative Time Warping. In Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Stephanie Lowry, Niko Sünderhauf, Paul Newman, John J Leonard, David Cox, Peter Corke, and Michael Milford. Visual place recognition: A survey, IEEE Transactions Robotics, 32, 2015.
Will Maddern, Geoffrey Pascoe, Chris Linegar, and Paul Newman. year, 1000 km: The Oxford RobotCar dataset. The International Journal of Robotics Research, 36, 2017.
Will Maddern, Geoffrey Pascoe, Matthew Gadd, Dan Barnes, Brian Yeomans, and Paul Newman. Real-tima time kinematic ground truth for the oxford robotcar dataset. arXiv preprint 101152000..01552 2020.
Marion Morel, Catherine Achard, Richard Kulpa, and Séverine Dubuisson. Time-series averaging using constrained dynamic time warping with tolerance. Pattern Recognition, 74, 2018
Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48, 1970.
Nicola Orio, Diemo Schwarz, and Iream Pompidou. Alignment of monophonic and polyphonic music to a score. In International Computer Music Conference (ICMC), 2001.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetoto, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Perfo-peeo Deep Learning Library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
François Petitjean, Germain Forestier, Geoffrey I. Webb, Ann E. Nicholson, Yanping Chen, and Eamonn Keogh. Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification. In Proc. of the IEEE International Conference Data Mining, 2014.
12

---

Published as a conference paper at ICLR 2023
Chotirat Ratanamahatana and Eamonn Keogh. Making time-series classification more accurate using learned constraints. In Proc. of the Fourth SIAM International Conference on Data Mining, 2004.
H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition.
IEEE Transactions Acoustics, Speech, and Signal Processing. 26, 1978.
Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Visual Permutation Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2019.
Craig Sapp. Online database of scores in the humdrum file format. In Proc. of the International Conference on Music Information Retrieval (ISMIR), 2005.
Proc. of the International Conference on Music Information Reirieval (ISMIR), 10 2004. Shai Shalev-Shwartz, Joseph Keshet, and Yoram Singer. Learning to align polyphonic music. In
Ron A Shapira Weber, Matan Eyal, Nicki Skafte, Oren Shriki, and Oren Freifeld. Diffeomorphic Temporal Alignment Nets. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Erik Stenborg, Torsten Sattler, and Lars Hammarstrand. Using Image Sequences for Long- Term Visual Localization, In Proc. of the International Conference on 3D Vision (3DV), 2020.
Bing Su and Ying Wu. Learning distance for sequences by learning ground metric. In Proc. of the International Conference Machine Learning (ICML), 2019.
John Thickstun, Jennifer Brennan, and Harsh Verma. Rethinking evaluation methodology for audio- to-score alignment. arXiv preprint arXiv:2009. 14374, 2020.
Janine Thoma, Danda Pani Paudel, and Luc Gool, Soft Contrastive Learning for Visual Localization. In Advances in Neural Information Processing Systems, 2020.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17, 2020.
Yizhi Wang, David J Miller, Kira Poskanzer, Yue Wang, Lin Tian, and Guoqiang Yu. Graphical time warping for joint alignment of multiple curves. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Ming Xu, Niko Snderhauf, and Michael Milford. Probabilistic visual place recognition for hicrarchical localization, IEEE Robotics and Automation Letters, 6, 2020.
Mubariz Zaffar, Sourav Garg, Michael Milford, Julian Kooij. David Flynn. Klaus McDonald -aierr and Shoaib Fhsan. VPR-Bench: An Open-Source Visual Place Recognition Evaluation Framework with Quantifiable Viewpoint and Appearance Change. International Journal of Computer Vision, 129, 2021.
Zheng Zhang, Romain Tavenard, Adeline Bailly, Xiaotong Tang, Ping Tang, and Thomas Corpetti. Dynamic Time Warping under limited warping path length. Information Sciences, 393, 2017.
Feng Zhou and Fernando De Torre Canonical Time Warping for Alignment of Human Behavior. In Advances in Neural Information Processing Systems (Neurips), 2009.
Feng Zhou and Fernando De la Torre. Generalized Time Warping for Multi-modal Alignment of Human Motion. In Proc. of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), 2012.
Yunyue Zhu and Dennis Shasha. Warping Indexes with Envelope Transforms for Query by Humming. In Proc. of the ACM SIGMOD International Conference on Management of Data 2003.
13

---

Published as a conference paper at ICLR 2023
A APPENDIX
We provide additional implementation details for DecDTT,, well as additional qualitative examples for both experiments in this section.
A.1 DYNAMIC PROGRAMMING SOLVER FOR GDTW
The mechanics of the solver are described follows. For each we can discretise Φ; into M values { uniformly between global bounds liti, 1itax, This forms graph where each of the mM values correspond to nodes and furthermore, temporally adjacent nodes, i.c., Φi-1,j. Pi,6 for all j, k are connected with edges, for total of (m 1) M2 edges. Node costs correspond to signal loss values in Equation and edge costs correspond to warp regularisation values Equation 6 Edges which violate the local constraints sqt su are given cost of co. The global minima of this new discrete optimisation problem corresponds to the minimum cost path through the graph and is solved using dynamic programming in (mmM2 time complexity. Iterative refinement of the discretisation and solution is performed as described in Deriso & Boyd (2019). We use three iterations of discretisation with discretisation factor 0.125 in all of our experiments. Furthermore, we set M = max(50, n.. where n is the length of time series X. Figure illustrates the mechanics of the DP solver for subsequence alignment problem and shows that the solution after refinement is comparable to calling an SLSQP solver (Virtanen et al. 2020) directly.
In general, one can set 17 and M using hyperparameter optimisation over a validation dataset. Assume we have a validation dataset where each observation is comprised of a time series pair. For any given 17 and M and number of refinement iterations r, we can use GDTW to compute the optimal alignment o using the DP solver. Furthermore, we can use o to initialise an NLP solver such as in Virtanen et al. (2020) to find a refined solution L which will be closer to the true solution of Equation 4. The goal of the hyperparameter optimisation is to find the least computationally expensive solver configuration (measured by computation time) subject to constraints on approximation error (measured w.r.t. objective function f or warp Φ).
Iteration f(o"): 0.02906
Iteration 2: f(d"): 0,02367
Iteration 3: f(d'); 0.02328
lteration 4: f(0'): 0.02325
1.0
10
0.6
0.6
06.
0.5
0.2
SLSOP
SLSQP DP
0.2
SLSQP
SLSQP
DP
DP
DP
0.0
0.6
8/3
6/
0.5
0.6
0.2
3-
3-
X/yre)
x/v(e)
0.20
0.23
5.51
5:70
3.00
11.0
1422
14.00
1173
1.20
2300
0.20
0.20
11775
110
1603
0.25
0.30
0.70
Figure 6: Illustration of the DP solver mechanics on subsequence alignment problem, where maps times in the shorter sequence y longer sequence x. A uniform discretisation is generated between global constraints the first iteration. Subsequent discretisations are made between tighter bounds around the previous solution. The objective function value decreases at each iteration until convergence after iterations. The objective value f from the SLSQP solver (Virtanen al. 2020) is 0.02325, close to the DP solver at the final iteration and furthermore, we can see qualitatively that the solved warps are indistinguishable between the DP and SLSQP approach.
14

---

Published as a conference paper at ICLR 2023
A.2 EFFICIENT COMPUTATION OF BACKWARD PASS
We do not construct the full Jacobian Dø(z) from Equation E explicitlyy instead directly computing the vector-Jacobian products required for automatic differentiation libraries. Let ( be downstream loss function defined over the estimated alignment (e.g., MSE to ground truth alignment )a)). Our goal for the end-to-end model to compute Dz(z) v (z)z), where e = ( E R To do this, we evaluate v DØ(z) from left to right, pre-computing and caching H A beforehand. In addition, note that H is tridiagonal from the definition of f, where off off-diagonal elements correspond only to the warp regu larisatiiooonn component R. This allows us solve v H- in ((m) time. Finally, observe that B and C' are in a sense complementary to each other. Specifically, columns of B relating to sminn s b b are zero since the objective function f only depends on x, A. Conversely, columns of C relating to x.y. À are zero since the constraint functions only depend on Φ and s s b b b This allows efficient evaluation of Equation 7 w.r.t the two blocks {x, y, )} and (smin, smmax bimnn mmxx separately by setting C (resp. B) to zero. Our full, efficient backward pass implementation as decribed is provided in our code at
A.3 TRAIN TIME SCALABILITY ANALYSIS
We present results for train time scalability in this section using the same experimental setup as the test time scalability analyisis presented in Section Unlike at test time, we aren't able to trade-off warp estimation accuracy for computation time during training. This is because the backward pass computation given by Equation 7 assumes the estimated warp o* satisfies the first-order optimality conditions for the NLP defined in Equation 4 To ensure this assumption holds, we need to ensure our solver discretises & finely enough such that o' is sufficiently close to optimal point (up suitable numerical tolerance). In practice, this can be achieved with multiple rounds of iterative refinement (we use three in our experiments, described in Section 6 and sufficiently large discretistion level M (again, we set M- = n in this analysis).
Figure 7 illlustrates the results of our train time scalability analysis. Note, the computation times presented include the total time taken for a training iteration, including the forward and backward pass. We observe that a training iteration of DecDTW is 4-20x (resp. 15-50x) slower than Soft-DTW (resp. DTWNet),, due to the iterative warp re- finement required for fine-grained warp estimation in the
10
Computation time (s)
10
DeDDWW
DILATE
SohDTW
10-2
DecDTW forward pass. However, we observe that DI-
DTWNet
LATE is in fact slower for training compared to DecDTW; this is attributed to the relevant efficiency of our back- ward pass being explicitly computed rather than computed through unrolling the DP recursion.
200
400
600
800
Time series length
Figure 7: Train time scalability
A.4 EXPERIMENTAL SETUP FOR AUDIO-TO- -OO-RR ALIGNMENT
Dataset Description Ground truth alignments were generated between the 193 piano performances to their associated scores using the methodology proposed in Thickstun et (2220) We used the authors' default hyperparameters for ground truth generation. These 193 performances are divided into train (94), validation (49) and test (50) splits. Furthermore, scores are not shared across splits. Audio is sampled at 22.1kHz with a hop size of 1024 for generating uniformly spaced time series of base features for each performance and synthesised score. Furthermore, each performance is split into uniform, non-overlapping slices of length 256, which corresponds to 12 seconds of audio per slice. There were a total of 995, 565 and 541 slices, across the train, validation and test splits, respectively. The hyperparameters used to generate constant-Q transform (48-dim) and chromagram (12-dim) features are identical to the ones used in Thickstun et al. (2020). For the mel spectrogram features, we used 128 mel bands, yielding 128-dim feature. We provide the full dataset generation procedure in our code.
Learning Task For learned methods (3-6), we apply a feature extractor comprised of single layer bi-directional Ghu et al. (2014) (with random initialisation) on top of base audio features. This feature extractor operates sequennceto--sqquence model. Specifically, the GRU layer takes as input
15

---

Published as a conference paper at ICLR 2023
length N sequence of base audio features of shape RNxd and outputs learned features of shape RNxd, where the output dimension of the GRU layer is set as d1 = 128 in our experiments. The learned features
then L2- 12-normalised before being used to compute both downstream alignment and training loss for each learned comparison method. Alignments in Table are generated using DTW for Base (D), Soft-DTW, Along GT, DILATE and using GDTW for Base (G) and DecDTT..
Comparison Methods The training losses for (3-6) are described as follows: The Soft-DTW (Cuturi Blondel 2017) method (3) computes the Soft-DTW discrepancy between two feature sets and utilises no path information. Along GT (4) computes the discrepancy between features along the path given by ground truth alignments. DILATE (Le Guen & Thome, 2019) (5) is a hybrid loss which consists of a shape loss (equivalent to the Soft-DTW discrepancy) and temporal loss, which penalises deviations from the predicted and ground truth paths. The relative weighting between both losses is given by hyperparameter 0 S a S 1. Ground truth path information in DILATE is given by penalty matrix Ω. Elements within each row (corresponding to a single point in time in the score) of 52 (where ground truth alignments are defined) is given penalty term based on the absolute alignment error. DecDTW (6) is able to train on the TimeErr loss directly. Full implementation for DecDTW and all comparison methods for this experiment are provided in our code.
Training Hyperparameters We use the Adam (Kingma & Ba 2015 optimiser with a learning rate 0.0001 and batch size of 5 for all methods. We trained for 300 epochs for DILATE and 20 epochs for all remaining methods and selected the model which yielded minimum TimeErr over the validation set. For DecDTW and Base (G), we set GDTW the regularisation hyperparameter A= 0.1, 0.7, 0.9 for CQT, chroma and melspec features, respectively. These regularisation weight values were selected using grid search over the average TimeFrr across the validation set for the base features. For the Soft-DTTW (Cuturi & Blondel| 2017) comparison method we used y noting that results do not meaningfully change for different For DILATE, a = 0 and 7 = 0.1 yielded the best results. We found that a low learning rate and high number of epochs were required for stable training under DILATE, in contrast to DecDTW..
A.5 EXPERIMENTAL SETUP FOR VISUAL PLACE RECOGNITION
Construction of Paired Sequences Dataset The single-imag dataset used to train the baseline VPR retrieval network is used to bootstrap the paired sequences dataset used for sequence- based fine- tuning. Within each train/val/test split, GPS data is used to produce sequence pairs. We designated a fixed set of reference traverses (6 for training. 1 each for validation and test), with each traverse having an associated full data collection run with a given date/time identifier (e.g.. 2015-08-17-13-30-11
Each reference traverse is split into geographically overlapping but distinct reference sequences of length 25, with images spaced 5 meters apart within each reference sequence. Adjacent reference sequences within the same traverse have 20 meters overlap between them for training and 12 meters overlap for validation and test splits. For each reference sequence, five query sequences are sampled. Query sequences are randomly selected from the pool of available remaining (i.e. non-reference) traverses within each split. The starting location of each query sequence is chosen randomly such that the query sequence is geographically contained by the reference sequences.
Our resultant dataset, comprised of ~22k, ~4k, ~1.3k sequence pairs for training, validation and testing, respectively, full covers the geographic region and a large set of conditions encompassed by the RobotCar dataset. A large variety of sequence pairs spanning different locations and condition pairs between query and reference enables features learned by sequence fine-tuning to generalise between training and the unseen (both in geographic location and date) test set. We also ensure that the large number of and uniformly spaced test sequences allow for a comprehensive and challenging evaluation. While we can arbitrarily increase the size of this dataset, we find the variety present in our bootstrapped dataset is enough to yield significant gains for sequence fine-tuning Full dataset lists for the paired sequence datasets are provided in the supplementary material.
Comparison Methods Similar to the audio experiments, all learned sequence fine-tuning methods apply a loss on top of sequences of extracted image embeddings. The OTAM (Cao et al. 2020) loss is the Soft-DTW discrepancy loss with minor modification to allow for subsequence alignment. Along GT computes the discrepancy between features along the path given by ground truth alignments. For DILATE (Le Guen & Thome 2019), similar to the audio experiments, needed parameterise
16

---

Published as a conference paper at ICLR 2023
the penalty matrix Ω. The value for element i.j is given by the (squared) GPS enror (in meters) between the geotages of query image and reference image j. Finally, DecDTW is able to use the task loss, ie. the maximum (or mean) GPS error along the optimal alignment to improve localisation performance. DILATE is not able to learn directly on the task loss due to the path heing encoded as a soft alignment path matrix.
Hyperparameetrs for Single Image VPR We train single image NetVLAD representations with VGG-16 backbone pretrained on ImageNet. NetVLAD layer uses 64 clusters, leading to a 32,768 dimensional time series embedding. Images are resized to 240 x 180 (width x height), consistent Thoma al. (2020). Triplet loss margin set to 0.1 and 10 negatives per anchor-positive pair are used. The model is trained using the Adam optimizer with learning rate of le-5 and a batch size of Our training setup is based on the recently released visual geolocalization benchmark (Berton et al.) 2022) and its associated codebase") We provide training and dataset setup code in the supplementary materials.
Hyperparameters for Sequence-based VPR For the sequence fine-tuning experiments, we use learning rate of 0.0001, batch size for a maximum of 10 epochs across all methods. In contrast to the audio experiments, query and reference images are both fed through a shared feature extractor comprised of a VGG-16 backbone, followed by a NetVLAD aggregation layer. We checkpoint models during training based the average maximum GPS error over the full validation set five times per epoch. We selected a fixed regularisation weight of À = 0.1 for DecDTW using the validation set and embeddings from the single-image model. For OTAM Cao al. (2020), we selected 7 = similar to the audio experiments, noting results were insensitive to this parameter. For DILATE Le Guen & Thome ) we used y 0.1 and similar to the audio experiments, we set a and y 1.
A.6 ADDITIONAL RESULTS FOR AUDIO-TO-SCORE ALIGNMENT EXPERIMENTS
In this section, we investigate if features learned using each comparison method presented in Sec- tion 7. generalises across both DTW and GDTW aligmments at test time. Table we present results for each comparison method using only DTW alignments at test time. Notably, the main difference to Table [ is the DecDTW column; the features output by the GRU(S) trained using TimeErr loss are placed into DTW alignment layer (as opposed to GDTW) during testing.
We can see in Table 3 that features learned with DecDTW produce poor alignment accuracy using DTW for both CQT and chroma features when compared to both base features (no learning) and DILATE. In addition, test alignment performance using DTW is significantly poorer compared to using GDTW (see last column in Table
Table 3: Results for the audio-to-son scoor alignment experiments (DTW alignment)
Reported metrics are Time / TemeDev (ms)
Feature Type
Base (D)
Soft-DTW
Along GT
DILATE
DecDTW
CQT
35/ 90
49 / 130
49 / 130
29 / 45
100 210
Chroma
50 / 115
59 / 142
59 142
28 /41
45 / 117
Melspec
122 235
55 153
52/ 145
26 40
31 /76
We also present results in Table which evaluate features learned under each comparison method time. Features learned with methods based on DTW (i.e. Soft-
using only GDTW alignments DTW, Along GT, DILATE) perform worse than base features for GDTW alignment. This holds for especially true for DILATE,, which yielded accuracy gains when evaluating with DTW alignments compared to base features but significantly degraded accuracy for GDTW alignment. DecDTW as expected, yielded gains compared to base features when evaluated using GDTW alignments.
Overall, we conclude that features trained with an underlying alignment method (either DTW or GDTW) tends to specialise to the particular alignment method used in training. Note that the continuous time formulation of GDTW, which allows for interpolation of alignments, and the availability regularisation X, cause GDTW alignments to outperform DTW overall at test time across most combinations of methods and features.
17

---

Published as a conference paper at ICLR 2023
Table Results for the audio-to-score alignment experiments (GDTW alignment)
Reported metrics TimeFrr Tem (ms)
Feature Type
Base (G)
Soft-DDTW
Along GT
DILATE
DecDTT
CQT
19
23/
23
43/69
17/27
Chroma Melspec
24 / 39
34/51
34//5
70/ 112
19/31
56 81
155 219
147
43/68 68
16/ 27
A.7 ADDITIONAL RESULTS FOR VISUAL PLACE RECOGNITION EXPERIMENTS
In this section, we provide additional results to the ones presented Table 2 in Table First, we add results for the independent retrieval task. The independent retrieval task involves finding the most visually similar reference image for each query using nearest neighbours, independently, using image embeddings (no DTW optimisation). Interestingly, fine-tuning network trained using contrastive learning on single images (this loss is designed to maximise single image retrieval performance) using sequence- based loss tends to overall improve independent retrieval performance at finer error thresholds (S 5m). However, performance reduced at the looser tolerances (> 5m). This holds uniformly and significantly for DecDTW and DILATE across all test conditions. We hypothesise that the embeddings of networks fine-tumed on the alignment task are trained to better differentiate between more nuanced visual details between nearby reference images.
Table 5: VPR experiment results (maximum error): Test Accuracy 2//3/5/10m
Method
Overcast
Sunny
Snow
Base (DTW)
0.7/12.3/44.3/73.8
0.5/8.7/40.2/62.1
1.6/11.1/44.//22.
Base (GDTW)
10.2/31.7765.6/90.
9.0/33.2/75.1/99.1
6.2/25../73.2/100000
OTAM/Along GT
0.7/12.3/44.3/73.8
0.5/8.7/40.2/622
DILATE
0.7/14.5/54.5/8000
1.511..//4099/66
1.3/12.2/44.6/688
DecDTW
25.4/45.0/68.3/90.1 22.8/50.4/84.31
1.5/44.8/88.0/1000
Base (Indep.)
0.0/11.6/47.9//
5.0/7.5/40.4//8
66/10.0/50.1/87
DILATE (Indep.)
0.2/11.1158.4/8477 0.2/14.5/50.1/6555
0.2/17.2/61.7/93.0
1./113.7/6..3/6.2
DecDTW (Indep.)
0.2/9.9/35.8/56.7
0.9/11.1/57.7855.
We additionally present results for the pose across the sequence (as opposed to the maximum in Table 5) in Table 6 This measure of positioning error commonly referred to as the absolute trajectory error (ATE). The conclusions equivalent to the maximum error case; fine-tuning on the GPS eтror directly using our DecDTW layer yields considerable performance improvements sub 5m tolerances the comparison methods.
Table 6: Additional VPR experiment results (mean error): Test Accuracy @2/3/5/10m
Method
Overcast
Sunny
Snow
Base (DTW)
16.9/48. 16.9/48.9/70.0/994
16.2/42.9/622.0/91.8
16.2/42.9/62.0//1.
Base (GDTW)
44.8/70. 1/98.1
8/99//9999
OTAM/Along GT
16.9/48 011.4/.97700094...
22/42.9/62.0//1..
16.2/42.9/62.000
11114/../62.//1111 1.8
DILATE
22.5/57.9/77 1/7.0/99977.//96.111 1
19. 1/43, 1/69. 5/93.2
15.1/40.4/6 .0/96.5
DecDTW
52.1/80.2/91.8999
25.99/9.8//88880 8/99.8
Base (Indep.)
(8.6/55.7/80../99
16.9/50.8/88 4/85,4/9.8
17.0/58.5/90.
DILATE (Indep.)
26.9/69. 7/900.9//9.1.......
32.9/69 0/9.9///94.//99.8
22.8/68.5PP 5/96..55/7.... 1/99.3
DecDTW (Indep.)
22.5/55.9/72.4885.7
26.2/59.8872.6685.7
19.3/61.4/86.0999 4/86.0/2//
A.8 ADDITIONAL QUALITATIVE EXAMPLES FOR AUDIO-TO-SCORE ALIGNMENT EXPERIMENTS
In Figure we present additional visualisations of example alignments for the audio to score alignment task. All features types (CQT, chroma, melspec) and before/after learning are presented in the figures.
18

---

Published as a conference paper at ICLR 2023
Example alignments randomly sampled from the test set. The visualisations way proposed by Thickstun et al. (2020) to visually compare two alignments (e.g., an estimated and ground truth alignment) by plotting performance aligned scores, where performance aligned score is generated by mapping the score through warping function.
We generate a performance aligned score using both the ground truth alignment and the estimated alignments using audio features. Red identifies notes indicated by audio feature alignments, but not by the ground truth, and yellow identifies notes indicated by the ground truth, but not by the audio features. Note, even if predicted alignment is close to the ground truth (in TrmeErr sense), mistakes made by the performer may yield significant looking errors (orange and red) in the visualisations.
A.9 ADDITIONAL QUALITATIVE EXAMPLES FOR VISUAL PLACE RECOGNITION EXPERIMENTS
We provide additional qualitative examples for the VPR experiments Figure 9
These figures
illustrate the effect of DecDTW fine-tuning on resultant positioning accuracy for a set of test sequence pairs. addition, Figure 9 provides example test images to illustrate the amount of appearance change observed between reference and query images.
19

---

Published as a conference paper at ICLR 2023
Fugue C-sharp minor, WTC
CQT/Base (TimeErr 35ms)
Chroma/Base (D) (TimeErr 30ms)
Melspec/Base (TimeErr 36ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DILATE (TimeErr 37ms)
Chroma/DILATE (TimeErr 38ms)
Melspec/DILATE (TimeErr 35ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/Base (TimeErr 19ms)
Chroma/Base (G) (TimeErr 22ms)
Melspec/Base (TimeErr 14ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DecDTW (TimeErr 19ms)
Chroma/DecDTW (TimeErr 16ms)
Melspec/DecDTW (TimeErr 15ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
Fugue 18 in G-sharp minor, WTC
CQT/Base (D) (TimeErr 53ms)
Chroma/Base (D) (TimeErr 82ms)
Melspec/Base (D) (TimeErr 47ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
COT/DILATE (TimeErr 38ms)
Chroma/DILATE (TimeErr 43ms)
Melspec/DILATE (TimeErr 33ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/Base (G) (TimeErr 26ms)
Chroma/Base (G) (TimeErr 21ms)
Melspec/Base (G) (TimeErr 17ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DecDTW (TimeErr 23ms)
Chroma/DecDTW (TimeErr 21ms)
Melspec/DecDTW (TimeErr 20ms)
Pitch
Pitch
Pitch
1
Time (sec)
Time (sec)
(scC)
20

---

Published as a conference paper at ICLR 2023
Fugue 12 in minor, WTC
CQT/Base (D) (TimeErr 24ms)
Chroma/Base (TimeErr 68ms)
Melspec/Base (D) (TimeErr
Pitch
Pitch
Pitch
Time (sec)
Time (SCC)
Time (SeC)
COT/DILATE (TimeErr 16ms)
Chroma/DILATE (TimeErr 17ms)
Melspec/DILATE (TimeErr 15ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/Base (G) (TimeErr 13ms)
Chroma/Base (TimeErr 20ms)
Melspec/Base (G) (TimeErr 22ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DecDTW (TimeEm 12ms)
Chroma/DecDTW (TimeErr 17ms)
Melspec/DecDTW (TimeEm 14
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
Prelude C-sharp Major, WTC
CQT/Base (D) (TimeErr 52ms)
Chroma/Base (D) (TimeErr 27ms)
Melspec/Base (D) (TimeErr 16ms)
Pltch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DILATE (TimeErr 25ms)
Chroma/DILATE (TimeErr 21ms)
Melspec/DILATE (TimeErr 42ms)
Pitch
Pitch
Pitch
10
Time (sec)
Time (sec)
Time (sec)
CQT/Base (G) (TimeErr 24ms)
Chroma/Base (TimeErr 15ms)
Melspec/Base (TimeEr 13ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
CQT/DecDTW (TimeErr 14ms)
Chroma/DecDTW (TimeErr 15ms)
Melspec/DeccDTV (TimeErr 10ms)
Pitch
Pitch
Pitch
Time (sec)
Time (sec)
Time (sec)
Figure 8: Example four randomly selected test set alignments for the audio-to-scon sc-oor alignment experiments. All recordings are performances of segments from Bach's The Well Tempered Clavier. Each column represents a particular feature type and each row represents a particular training loss.
21

---

Published as a conference paper at ICLR 2023
Overcast Query Max Error: Base (G) 5.26m, DecDTW 2.22m, Base (D) 23.35m, DILATE 7.85m
Ref
Query
(G)
Dec
Base (D)
DILATE
Snow Query Max Error: Base (G) 5.77m, DecDTW 3.86m, Base (D) 10.40m,
DILATE 6. 6.14m
Oalard Proce
Ref
Query
Oeengh
Base (G)
DecDTW
Base (D)
Carnyed Cayleeer
DILATE
Wesdde
Wondoy Way
de'y ply
Sunny Query Max Error: Base (G) 4.33m, DecDTW 3.52m, Base (D) 21.29m,
DILATE 15.48m
Ref
Query
Base (G)
Base (D)
DILATE
Overcast Query Max Error: Base (G) 2.31m, DecDTW 7.56m, Base (D) 10.22m,
DILATE 4.66m
Query
Base (G)
PRSS
DecDTW
Base (D)
DILATE
Figure 9; Additional example localisation output for the VPR experiments selected from the set. Example query images from the sequence are provided in the top row and example database images are provided in the bottom row. Query poses are offset from the database for visualisation purposes only. The substantial intra-sequence velocity change in the last (bottom) example, combined with warp regularisation causes DecDTW training to perform worse than Base (G) and DILATE.
22


Reviews:
[{"review_id": "ZV2iVh50aJi", "reviewer": "Reviewer_Z1je", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel DTW layer that combines non-linear programing based generalized DTW (Deriso & Boyd) with declarative network (Gould et al.), to not only output the DTW discrepancy value, but also the alignment. More importantly, the output alignment could be compared against ground truth alignment and the difference could be backpropogated to train the network. Experiments on audio-to-score alignment and image query datasets, both show improvement over SOTA methods. Scalability is also discussed in the end.", "summary_of_the_review": "Overall, the method is novel but lack some motivation behind it. The applications are interesting to the community.", "strength_and_weaknesses": "Pros:\n1. The idea is novel that is very different from existing differentiable DTW methods (e.g. DTWnet or soft-DTW). This is the first attempt of using declarative network in DTW problem.\n2. The experiments are conducted on some interesting and very practical tasks, the audio-to-score and visual query.\n3. The paper is clearly written and easy to follow. Additional details are provided in appendix.\n\nCons:\n1. The motivation of applying declarative network is vague. If just for incorporating alignment path error, simple modifications can be done on DTWNet or SoftDTW to obtain the DTW path as a byproduct, and adding the path into the loss is achievable by defining a proper distance between hypothesis path and gold alignment.\n2. Lack of comparison with other methods that regularize the alignment paths, e.g. Graphical Time Warping (GTW) and following literatures on this method.\n3. The method is not scalable, 2 orders of magnitude slower than other methods. This significantly limit the usage of the method. This is due to the complexity in declarative network.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WM-ZZZll3-", "reviewer": "Reviewer_EEJt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "**Update 11-16-22** I acknowledge the revisions made by the authors. I believe the proposed revisions further improve this already-strong submission. I am holding my score at 8 Accept and am willing to further champion this paper's acceptance if needed.\n\nThis paper proposes an algorithm for improving temporal alignments between related pairs of time series data, applicable in applications like audio-to-score alignment in music information retrieval. Unlike past efforts, the proposed algorithm can leverage ground truth alignment information during training if available, leading to improved performance on several real-world alignment tasks.", "summary_of_the_review": "Overall, I think this paper presents a well-motivated method w/ strong empirical results on an important task. The scope of the exploration is somewhat limited to aligning (as opposed to _transcribing_ as in tasks like speech recognition), but this is an important task for which there are certainly useful real-world applications. Overall, I think the ICLR community will benefit from this paper’s inclusion and the ensuing discussion.", "strength_and_weaknesses": "A primary strength of this paper is the combination of the theoretical elegance of the proposed method alongside its impressive performance on real-world alignment tasks. Additionally, this paper is well-written and contains precise notation. One weakness is that, while the proposed method is continuous and can be combined w/ neural networks, it does not address the problem of jointly learning to align and _transcribe_, unlike other methods like CTC which can learn alignments without designing an explicit cost function between input and output sequences (e.g., in speech recognition).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JVoE9Y-cy9", "reviewer": "Reviewer_UgzC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel differentiable dynamic time-warping algorithm. The approach is advantageous over existing variants as it outputs a learnable warping path between the time series representations.\n\nThe authors test their approach on two distinct tasks: audio-score alignment and visual place recognition, and achieve results comparable to or better than the existing state-of-the-art.", "summary_of_the_review": "The authors improve over DTW, a commonly used tool for sequential alignment tasks. Their formulation directly outputs the alignment path, which could be further used to improve the alignment. The paper is well written with minor corrections or clarifications required. \n\nGiven the above, I would like to recommend this paper to be presented at the conference.\n\nBelow I will list some minor/specific comments:\n\n- Problem formulation & methodology: The text reads a bit like Thickstun is the first person to formalise audio-score alignment. I understand the authors refer to the wording in the cited paper. On the other hand, they also cite much earlier work (e.g. Ewert et al.) which has made similar definitions. It might be good to re-word; e.g. stating the pepper adopts the framework described in Thickstun et al.\n- I think the setup needs more elaboration for both experiments. In both experiments, the authors use a subset of the data available, but they do not explain why. Moreover, in the audio-score alignment experiments, it is not explained if the scores could be present in multiple training/validation/test sets, potentially causing leakage.\n- A7: It would also be good to include worse alignment results and discuss why such failures occur.\n- Future work: it would be very interesting to extend the work on \"subsequence alignment with jumps,\" see JumpDTW.", "strength_and_weaknesses": "Strengths:\n\n- Directly outputs the alignment path\n- Tested on two completely different domains\n- Typically better results on both tasks compared to existing DTW variants\n\nWeaknesses:\n\n- Not compared to anything else but DTW-variants\n- The experimental setup, in particular, the train/validation/test divisions are not explained in detail. See the specific comment below.\n- Nit: The figures aren't colour-blind friendly\n- For camera ready, adding a companion with audio and video examples could be good.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0-jcju2SgW", "reviewer": "Reviewer_yA9i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper suggest the use of Generalized Dynamic Time Warping as a way to get differentiable alignments.\nIt then showcases the utility of this method on experiments on which the loss to be optimized depends directly on the obtained path.", "summary_of_the_review": "Overall, this paper introduces interesting ideas, but the lack of comparison to an important baseline (SoftDTW with regularization on the path [1]) makes it impossible to assess whether the proposed approach outperforms the said baseline.", "strength_and_weaknesses": "* Strengths\n    * Using the path information from DTW alignments in gradient-based optimization is an interesting track of research\n    * Relying on the Generalized DTW formulation to do so makes a lot of sense\n* Weaknesses\n    * The major weakness in this paper is that it misses an important related work [1] that also relies on integrating the path information (from SoftDTW this time) for gradient-based optimization with a DTW-derived loss.\n    \n        1. Shape and Time Distortion Loss for Training Deep Time Series Forecasting Models. Le Guen & Thome, NeurIPS 2019\n\n    * Another weakness of the paper is that the presentation of the experiments is too brief, which makes it hard to get what each competing method does in practice.\n\nIn more details:\n\n* At several places, authors suggest that when using SoftDTW, one cannot differentiate through the path information, which is not true (it is discussed in the original SoftDTW paper and done in [1]). Below are a few occurrences of this claim in the paper:\n    > DTWNet and SoftDTW only allow the DTW discrepancy between two time series to be differentiable wrt its inputs (Legend of Fig 1)\n\n    > This enables for the first time the use of the alignment path itself in a downstream loss (page 2)\n\n    * Comparison to [1] is of prime importance given that the computation for DecDTW is said to be \"between 4-20 times slower than SoftDTW\"\n* The description of the experiments is sometimes hard to follow. As an example, I do not understand Table 1. More specifically, I do not understand what the subparts (left and right) of the Table are, since we have a first subpart dedicated to \"Classic DTW\" in which there is still a DecDTW entry and similarly a second subpart named \"GDTW\" in which there are DTWNet and SoftDTW entries.\nI guess there is something like one can use a different alignment algorithm to train the network and predict a path, but if this is the explanation, things should be made much clearer in the text in my opinion.\n* Here are other remarks related to the experiments:\n    > Interestingly, fine-tuning using DecDTW dramatically reduces independent retrieval performance (p. 9)\n       * This would be worth a discussion\n    * Also, I do not get why \"DTW (Base)\", \"Fine-tune Along GT\" and \"Fine-tune OTAM\" reach the exact same level of performance here. Is there a rational explanation for this fact?\n* Finally, this is a minor remark, but I feel that, when presenting GDTW, authors should not use sentences such as:\n    > This more general description of the DTW problem\n\n    > The dynamic time warping problem can be formulated as follows (page 3)\n\n    since the GDTW problem is not the DTW problem (yet it is an interesting formulation anyway)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster