Time Series Alignment with Global Invariances
Authors: Titouan Vayer
Romain Tavenard
Laetitia Chapel
Rémi Flamary
Nicolas Courty
Yann Soullard
Venue: Accepted by TMLR ()

Abstract: Multivariate time series are ubiquitous objects in signal processing. Measuring a distance or similarity between two such objects is of prime interest in a variety of applications, including machine learning, but can be very difficult as soon as the temporal dynamics and the representation of the time series, i.e. the nature of the observed quantities, differ from one another. In this work, we propose a novel distance accounting both feature space and temporal variabilities by learning a latent global transformation of the feature space together with a temporal alignment, cast as a joint optimization problem. The versatility of our framework allows for several variants depending on the invariance class at stake. Among other contributions, we define a differentiable loss for time series and present two algorithms for the computation of time series barycenters under this new geometry. We illustrate the interest of our approach on both simulated and real world data and show the robustness of our approach compared to state-of-the-art methods.


Published in Transactions on Machine Learning Research (10/2022)
Time Series Alignment with Global Invariances
Titouan Vayer
bilouan.vayerrrnniia
Université Lyon, INRIA, CNRS, ENS de Lyon, UCB Lyon 1, LIP, Lyon, France
Romain Tavenard
Université de Rennes, CNRS, LETG, IRISA, Rennes, France
Lactitia Chapel
lactikiia.chapell@rriss...
Université Bretagne-Sud, CNRS, IRISA, Vonnes, Prance
Rémi Flamary
CMAP, Ecole Polytechnique, IP Paris, Fronce
Nicolas Courty
Niccolas.courtyy@iiisse
Université Bretagne-Sude CNRS, IRISA, Vonnes, Pronce
Yann Soullard
yam..soulaardBbmiieernnee...
Université de Rennes, CNRS, LETG, IRISA, Rennes, France
Reviewed OpenReview: https: openreview. net/ ptt/form?? id= UXC
Abstract
Multivariate time series ubiquitous objects in signal processing. Measuring distance or similarity between two such objects is of prime interest in a varicty of applications, including machine learning, but can be very difficult as soon as the temporal dynamics and the representation the time series, i.e. the nature of the observed quantities, differ from one another. In this work, we propose a novel distance accounting both feature space and temporal variabilities by learning a latent global transformation of the feature space together with temporal alignment, cast joint optimization problem. The versatility of our framework allows for several variants depending the invariance class at stake. Among other contributions, we define differentiable loss for time series and present two algorithus for the computation of time series barycenters under this new geometry. We illustrate the interest of our approach on both simulated and real world data and show the robustness of our approach compared to state-of-the-art methods.
1 Introduction
Time series are subject to a number variabilities that make their processing difficult in practice. One the most well-known example the temporal shift, usually handled using the celebrated Dynamic Time Warping (DTW, Sakoe & Chiba 1978) that aligns, time, two time series and is invariant to any monotonically increasing temporal map. It has been initially introduced for speech processing applications and is now widely used in variety of contexts such human activity recognition (Chang et al.] 2019), satellite image analysis Wegner Maus et al. 2019) or medical applications (Huang & Lu 2020 Janati et al. 2020
Another source of variability in time series is feature space alterations, that may occur due to a permutation of sensors, changes in sensor properties or even different number of sensors. This problem of heterogeneous representations, also called distribution shifts machine learning, has boen studied mostly on non-structured data. It has been shown that algorithms are notoriously weak (Ben-David al. 2010)) when it comes generalizing to out-o--distrilaution samples, as they rely the correlations that are found in the training

---

Published in Transactions on Machine Learning Research (10/2022)
f (y)
J V2,3
DTW path xt
Registration
min DTW-GI(X.y) /EF /EF,TEA(x.)) (L,))E
Σ (()))
Figure 1: DTW-GI aligns time series by optimizing on temporal alignment x (through Dynamic Time Warping) and feature space transformation f (c.g. here in the Stiefel manifold V2.3). In the figure x², f denole the solutions of the optimization problem DTW-GI. Time series represented here are color-coded trajectories, whose starting (resp. end) point is depicted in blue (resp. yellow).
data AArjovsyy et al. 2019). Consequently, dedicated paradigms such as domain adaptation (Kouw & Loog 2019) directly take into account this problem in the learning process. Another approach is to learn with respect to some invariance classes (based on some prior knowledge) in order to be more robust to irrelevant feature transformations (Battaglia et al., 2018; Goodfellow et al.] 2009). In this work, we aim at tackling this problem in the time series context through the definition of similarity measures that naturally encode desirable invariances. More preciscly, we introduce similarity mcasures that are able to deal with both temporal and feature space transformations.
There exist many frameworks to register different spaces under some classes of invariance. In the shape analysis community. matching objects under rigid transformations is widely studied problem. Iterative Closest. Point (ICP, Chen & Medioni 1992) is a standard algorithm for such a task. It acts by alternating two simple steps: (i) matching points using nearest neighbor search and (ii) registering shapes together based on the obtained matches, which is known as the orthogonal Procrustes problem that has a closed form solution (Goodall) 1991). This idea further explored in Cohen Guibas
[1999] Alvarez- Alvaise--Melis et al.] (2019). where optimal transport is used to match points in the first step, and a recent extension to objects with hicrarchical structure has been introduced in Alvarez-Melis et al. 2020) that considers dedicated invariance class for the registration step.
This heterogeneous setting has also been investigated in the time series context, where the goal is to align series of features lying in different spaces. One of the most salient track of rescarch in this setting is the Canonical Time Warping (CTW) method. CTW (Zhou & Torre, 2009) has been introduced for human motion alignment under rigid space transformations. transformed time series, using Canonical Correlation Analysis (CCA) to define the fcature space transform. Few extensions to CTW have been proposed. GTW (Zhou & De la Torre 2012) parametrizes CTW temporal alignments in continuous time instead of relying on DTW. Deep CTW (Trigeorgis et al., 2016) extends CTW by learning a feature space embedding (in the form of a neural network) before performing CTW. Finally, Canonical soft Time Warping applics the CTW methodology to soft alignments (see Section 2 for more details on soft alignments). In the same vein as CTW, Deng et al. (2020) learns an invariant subspace based on DTW alignments. More rocently, GromovDTW (Cohen et al. 2021 has been introduecd as an extension of the Cromov-Wasserslees distance measure between heterogeneous distributions to the time series context. GrWmovDTW relies on time series self-simin self-similarities as way cireumvent the need to compute distances across feature spaces. Compared to these approaches, our method works by optimizing map between feature spaces, hence allowing one to (i) add prior information in the form of constraints on the set of allowed maps and (ii) use the computed map for downstream application, as illustrated in our experiments on MoCap data (as described in Section
consists of temporal alignment (using DTW) of
In more detail, we aim at tackling both temporal and feature space invariances. To do so, we state the problem a joint optimization over temporal alignments and feature space transformations, as depicted in
2

---

Published in Transactions on Machine Learning Research (10/2022)
Figure [ Our general framework allows the use of either DTW or its smoothed counterpart softDTW as alignment procedure. Similarly, though rigid transformations of the leature space seem reasonable invariance class, we show that our method can be used in conjunction with other families of transformations. Such a framework allows considering the case when time scries differ both in length and feature space dimensionality. We introduce two different optimization procedures that could be used to lackle this problem and show experimentally that they lead effectively invariant similarity measures. Our method can also be used compute meaningful barycenters even when time series at stake do not lie in the same feature space. Finally, showcase the versatility of our method and the importance of jointly learning feature space transformations and temporal alignments on two real-world applications that are time series forecasting for human motion and cover song identification.
2 Dynamic Time Warping (DTW)
Dynamic Time Warping (DTW, Sakoe & Chiba 1978) is an algorithm used to assess similarity between time series, with extensions to multivariate time series proposed in Ten Holt al. (2007 Wöllmer et al. (2009) In its standard form, given two multivariate time series x IR Txxp and y R of the same dimensionality P, DTW is defined as:
DTW(x,y) = min Σ d(x;,;;)
(1)
TEA((x)) (1.))E
where A(x, y) is the set of all admissible aliguments between x and y and d is a ground metric. most cases, the squared Euclidean distance, i.e. dyx;, ||x - y; 112.
An alignment æ is a sequence of pairs of time frames which is considered be admissible iff it matches first (and respectively last) indexes of time series x and y together, (ii) it is monotonically increasing and (iii) it is connected (i.e. every index from one time series must be matched with at least one index from the other time scries). Efficient computation of the above-defined similarity measure can be performed in quadratic time using dynamic programming, relying on the following recurrence formula:
DTW + ( N DTW X -1-
DTW 8-ro) = ((Xt,,Se)) + min
(2)
where we denole by x_y the time series x observed up to time L. Many variants of this similarity measure have been introduced. For example, the set of admissible alignment paths can be restricted to those lying close to the diagonal using the so-called Itakura parallelogram or Sakoe-Chiba band, or a maximum path length can be enforced (Zhang al.) (017). Most notably, differentiable variant of DTW, coined softDTW. has been introduced in Cuturi & Blondel (2017) and is based on previous works alignment. kernels (Cuturi et al. 2007). It replaces the min operation in Equation 2 by soft-min operator min whose smoothness is controlled by a parameter 7 > 0, resulting in the DTW, distance:
(x,,( min *EA(xxy) (FJ)ET
Σ d(x;, -7 log
Σ
- -mese d(x.y,)/7
(EA(xx.)
In the limit case 7 min? reduces to hard min operator and DTW, is equivalent to the DTW algorithm.
3 DTW with Global Invariances
Despite their widespread use, DTW and sofDDTW are not able to deal with time series of different dimension- alities or to encode feature transformations that may arise between time series. the following, we introduce new similarity measure aiming at aligning time series in this complex sotting and provide ways compute associated alignments. We also derive Fréchet mean formulation that allows computing barycenters under this new geometry.
3

---

Published in Transactions on Machine Learning Research (10/2022)
DTW
DTW-GI
Figure 2: Example alignments between 2D time scries (trajectorics in the planc). Color coding corresponds to timestamps. Our DTW-GI method jointly estimates temporal alignment and global rotation between time series. On the contrary, standard DTW alignment fails at capturing feature space distortions and therefore produces a mostly erroneous alignment (matching in red), except the beginning and end of the time series, whose alignments preserved thanks to DTW border constraints (see Section
3.1 Definitions
Let x xT. and y RT XPs be two time series of length Tr and Ty. In the following, we assumee that the dimension Ps 2 Py In order allow comparison between time series x and y, we optimize on family of functions F that map y onto the feature space in which x lies. More formally, define Dynamic Time Warping with Global Invariances (DTW-GI) as the solution of the following joint optimization problem:
DTW-GI(x.y)- = min
Σ d(xi, f(y:)),
(4)
(E (b,))
where F family of functions from R to RP=, Properties (including symmetry) of this similarity measure are detailed in Sec. 3.1.1. Note that this problem can also be written as:
min DTW-GT(X.y) SEX,
(W., f(x))
where f(y) is shorteut notation for the transformation f applicd to all observations in (...) denotes the Frobenius inner product, Wn is defined as:
[1 if e otherwise
Vi TT. (W=)..
(6)
and C(x, f(y)) is the cross-similarity matrix of squared Euclidean distances between samples from and f(y), respectively. This definition can be exlended to the softDTW case of Equation 3 as proposed in the following:
GI(x,) = min min (Wa. C(x, f(y))) JeF xeX(x,y)
= min -y log JeF
e eWW,.Ctx.,(/111
TEA(x.y)
Note that, due to the use of a soft-min operator, Equation 7 is no longer joint optimization.
These similarity measures estimate both temporal aligmment and feature space transformation bet ween time series simultaneously, allowing the alignment of time series when the similarity should be defined up to a global transformation. For instance, one can see in Figure P two temporal alignments between two series in 2D that have been rotated in their feature space. In this case DTW-GI, whose invariant is the space of rotations, recovers the proper alignment whereas DTW fails.
4

---

Published in Transactions on Machine Learning Research (10/2022)
3.1.1 Properties of DTW-GI
By definition, DTW-GI and softDTW-GI are invariant under any global transformation T(-) such that (SoTISE F (i.e. is stable under T), which motivales the name (soft)DTW with Global Invariances. Moreover, DTW-G1 inherits from some of the classical DTW properties. First, if for any f e F, f- exists and is in FF (which implics Pa Py), and if clements of F are norm preserving operations, then DTW-GI and Sof.DTW-GI are symmetric, since in this case:
DTW-Gl(x,y) =
min TEA,TE)(D,)
Σ
d(x;,
(8)
(i,))x
min SEJ,TEA(xx))
Σ
(x:))
(9)
(i,))=
=
min SEF,TEA(x.))
Σ (xi,
(10)
(iJ))z
min fEF,TEA(x.))
Σ d(f(xx),
(11)
((,))E
=
min )EF,TE((Yx)
Σ ((J)E
d(y,, f(x,)) = DTW-
(12)
Though the constraints on for this coudition to hold might appear rather strong, this still allows to include standard rigid transformations such as rotations, translations and reflections.
Finally, it is straightforward to see that DTW-GI(X, x) 0 for any time series soon F contains the identity map. More generally, regardless of the class of functions F and for any pair of time series (x,y), we have DTW-GI(x.y)) = 0 iff there exists f F such that x and fly) are equal up to repetitions in the series.
3.2
Optimization
Optimization the above-defined losses can be performed in several ways, depending of the nature of F. We now present one optimization scheme for each loss.
3.2.1 Gradient descent
We first consider the optimization on the softDTW-GI loss (Equation 7 in the case where F is a parametric family of functions, here denoted fe, that are differentiable with respect to their parameters 0. The optimization can be done with a gradient descent the parameters of fa. Since softDTW is smooth (contrary to DTW), this strategy can be used to compute gradients of DTW,-GT w.r.l. 0.
Complexity for this approach is driven by (i) that of a softDTW computation and (ii) that of computing fe(y). If we denote the latter cy, overall complexity for this approach is hence (T,TTT + cy)). Note that when Riemannian optimization involved, an extra complexity term has to be added, corresponding to the cost of projecting gradients onto the considered manifold. This cost O(p²) for example when optimization is performed on the Stiefel manifold (Wen & Yin 2013), which is an important case for our applications, discussed in more details in the following.
3.2.2 Block Coordinate Descent (BCD)
When DTW-GI (see Equation 5 coucerned, we introduce another strategy that consists in alternating minimization over (i) the temporal alignment and (ii) the feature space transformations. We will refer this strategy Block Coordinate Descent (BCD) in the following.
Optimization over the alignment path given fixed transformation ʃ solely consists in DTW alignment, described in Section 2 For fixed alignment path ग, the optimization problem then becomes:
min (W,, JEF
m. C(x,f(y)))
(13)
5

---

Published in Transactions on Machine Learning Research (10/2022)
Recall that C' is matrix of squared distances, which means that the problem above is weighted least square problem. Depending on F, there can exist closed form solution for this problem (e.g. when F is the set of affine maps with no further constraints). Let us first note that the matrix C' can be rewritten as:
C(x. f(y)) = ux + 11.VIy 2xf(y))
(14)
where:
ux = (|xx Xxx T|²)T and Vsy = (IIf(y))) II((,,))13
and 1n (1,
In particular, the optimization problem (13) reduces to maximizing xfx))((y")
times
when is a set of norm preserving operations.
3.2.3 Estimating in the Stiefel manifold
Let us consider the special case where is the of linear maps whose linear operator is an orthonormal matrix, hence lying on the Stiefel manifold that we denote Vp,.n in the following. It is defined for Py $ Pa as pyy.== (P x R } and this invariance class encodes rigid transformations of the features. In this case, the optimization problem becomes:
min PEV
( Ux 1, 11.11 Vp. 2xPy
(15)
and we have Vp.y || [Pyr, 13) (1 llyT, 1P) Vy since for all j. |ll,
y = I and thus the considered applications are norm- norm-preserving. Overall, we get the following optimization problem:
min PEV Pyy. Pm
(wx. uxlf + +11, 2 x. xPy
(16)
which, since the term ( (w*, uxl 1 +1, does not depend P, is equivalent to solving:
(W n; xPyT)
(x "'W,y,
(17)
PE
PE
the last equality being a direct consequence of the cyclic property of the trace.
Algorithm 1: Block-Coordinad Descent for DTW-GI with Stiefel registration
P P+L Ippppp
repeat.
Wr + Alignment matrix from DTW(x,yP")
M + x W.Y (see Equation 17]
U,E, V SVD(M);
P UVV
until convergence;
As described in Jaggi (2013) the latter problem can be solved exactly using Singular Value Decomposition (SVD): if UΣV M is the SVD of a matrix M of shape (Py,Pz), then = UV is solution to the linear problem maXsey, (S, M). Note that this method can also tackle the case where F is an affine map whose linear part lies the Stiefel manifold by realigning time series means, as discussed for example Lawrence et al. (209)) A sketch of the algorithm is presented in Algorithm (for the simplified case where time series means do not have to be realigned).
Interestingly, this optimization strategy where alternate between time series alignment, í.e. time corre- spondences between both time scries, and feature space transform optimization can be seen as a variant of the lterative Closesi Point (ICP) method in image registration (Chen & Medioni 1992). in which nearest neighbors are replaced by matches resulting from DTW alignment. Its overall complexity is then ( (T,T,Pa + +PpP)) This complexity is oqual to that of the gradient-descent when Pa O(p,)) However, in practice, the number of iterations required is much lower for this BCD variant, making it a very competitive optimization scheme, discussed in Section 4

---

Published in Transactions on Machine Learning Research (10/2022)
Generalizations. The algorithms presented above are mainly focused optimization on the Stiefel manifold. Note however that they are not strictly restricted to this case. Typically, (projected) gradient descent based optimization could be performed for softDTWGGI on any family of functions parametrized by a neural network. Regarding the BCD algorithm, requires a mumerically efficient way to compute the optimal feature space transform for a fixed aligument. In our experiment, we illust.raee this in the context. of cover song identification, for which aligning song keys is a well-known registration step (sce Section 4.5 for details). Another example is for block-structured linear transformations of the features. More precisely, this corresponds to the case where the features are structured into & groups i.e. Pz k qu and Py k 4y with By S 4r, k E N and when one looks for a linear transformation p E Rtx group. To make the connection with our framework, this coincides with a global transformation P E IR Xpy that can be written as P blockdiags (p) where:
Xev that aligns the feat of each
P 0
0
0
p
0
blockdiag, (p) diag P. .
: P
k times
In the special case of p E V Vov.ez it is easy to show that P P Ip, and thus P E Vpy..= which also corresponds to a rigid transform of the features but this time structured in blocks. In this situation, the alignment problem becomes:
min P=blockdiogc/(p) s.t. pp
(W., ux + 11, Vp. 2xPyT)
(18)
As P Vpup= we can use the same reasoning as above and show that it is equivalent MaXpEV su:e (x Way, blockdiag, (p)). Interestingly the latter problem also admits a closed form expression. More precisely by decomposing x Way into & blocks Cij, each of size Qa x qy, the solution is given by S = UV where U, V come from the SVD of E Ca, i.e. the sum of the diagonal blocks. For more details we refer the reader to the Lemma 6.1 in the supplementary materials. We will illustrate this type of transformation for the alignment of human motion trajectories in Section 4.4
3.3 Barycenters
Let us now assume we are given set fx(1) of time series of possibly different lengths and dimensionalitics. A barycenter of this set in the DTW-GI sense is a solution to the following optimization problem:
min Σ DERTXP
wi min (x (9, f((b)),
(19)
REF
where weights {w:}h as well as barycenter length T and dimensionality p are provided as input to the problem. Note that, with this formulation, when F is the Stiefel manifold, p is supposed to be lower equal to the dimensionality of any time series in the set {x(*),,
In terms of optimization, as for similarity estimation, two schemes can be used. First, softDTW-GI barycenters can be estimated through gradient descent (and when the set of scries to be averaged is large, a stochastic variant relying on minibatches can easily be implemented). Second, when BCD is used for time series alignment, barycenters can be estimated using a similar approach as DTW Barycenter Averaging (DBA, Petitjean et al. 2011), that would consist in alternating between barycentric coordinate estimation and DTW-GI alignments.
4 Experiments
In this section, we provide an experimental study of DTW-GI (and its soft counterpart) on simulated data and real-world datasets. Unless otherwise specified, the set F of feature space transforms is the set of affine maps whose linear part lies in the Stiefel manifold. In all our experiments, tslearn (Tavenard et al. 2020
implementation used for bascline methods and gradient descent on the Stiefel manifold performed using GeoOpt (Kochurov et al. 2019 Becigneul & Ganca 2019) in conjunction with PyTorch (Paszke al. Open source code of our method will be released upon publication.
2019
7

---

notice that (Soft-)DTW-GT are Published in Transactions on Machine Learning Research (10/2022)
20
2
sohDTW
CTW
24
GromosDIW
Computation timse (6)
GromesDTW
Computttion time
DTW-GI
DTW-GI
2-2
sOLDTW-GI
20
MARDWW-II
2
2-10
2-12
2:14
16
22
24
23
23
27
2
2
2
2
2
length
Time dimensionality
Computing time as function of time series length (left) and dimensionality (right). Solid lines correspond to median values and shaded areas correspond to 20th (resp. 80th) percentiles.
Figure 3:
4.1 Timings
We are first interested in quantitative evaluation of the temporal complexity of our methods. Note that the theoretical complexity of DTW and softDTW are the same, hence any difference observed in this series of experiments between DTW-GI and softDTW-GT would be solely due to their optimization schemes discussed in Section 3.2, In these experiments, the number of iterations for BCD as well as the number of gradient steps for the gradient descent optimizer are set to 5,000. The BCD algorithm used for DTW-GT is stopped as soon as it reaches local minimum, while early stopping used for the gradient-descent variant with a patience parameter set to 100 iterations.
We first study the computation time as function of the length of the time series involved. To do so, we generate random time series in dimension 8 and vary their lengths from 8 to 1,024 timestamps.
Figure (left)) shows a clear quadratic trend for all methods presented, except GromovDTW whose complexity is cubic w.r.f. the length of the time series due the tensor-matrix multiplication that is involved at each step of its pseudo-Frank-We Wolfe algorithm (Cohen al., 2021). Note that DTW-GI and its BCD optimizer clearly outperform the gradient descent strategy used for Sof.DW-GI because the latter requires more iterations before early stopping can be triggered. Building this, dimensionality (with a fixed time scries length of 32). DTW and softD baselines are asymptotically linear with respect. to Similarly, since Gromov DTW relies on pre-computed self-similarity matrices, it only linearly depends in the feature space dimensionality for the computation of these self-similarity matrices. Since feature space registration performed through optimization on the Stiefel manifold, both our optimization schemes rely on Singular Value Decomposition, which leads to an (p²²) complexity that can also be observod for both methods in Figure 3 (right). Note also that the CTW baseline is slightly more computationally expensive than DTW-GI in practice, even if asymptotic complexities are the same as for DTW-GL.
turn our focus the impact of feature space
4.2 Rotational invariance
We now evaluate the ability of our method recover invariance to rotation. To do so, we rely on a synthetic dataset of noisy spiral-like 2D trajectories. For increasing values of angle a, generate pairs of spirals rotated by with additive Gaussian noise. Alignments between reference time series and variants that are subject to an incrcasing rotation are computed and repeated 50 times per angle. The ratio of cach distance to the distance when a 0 is reported in Figure 4 (left). One can clearly see that the GI counterparts of DTW and softDTW are invariant to rotation in the 2d feature space, while DTW and softDWW are not. Interestingly, CTW and GromovDTW, that should be invariant to rotation, still exhibit an increase in the loss with the angle a, suggesting that their algorithm has more difficulties reaching a global minimum in practice. Also, when varying the noise level in Figure 4 (right),
8

---

Published in Transactions on Machine Learning Research (10/2022)
25
GromovaTI
GromevOTV/
DTW
DnW
softL (VN-G1
sollD/wl-51
Dismnnc nato
0-
3n2
Notso loval
Figure 4: Illustaaionn of the rotation invariance provided by DTW-GL. On the left, ratio of the distance to that of non-rotated pair spirals is presented as a function of the rotation angle for a fixed noise level. On the right, ratio of the distance to that of a non-rotated pair of spirals presented as a function of the noise level for a fixed rotation angle я. Median distance ratios are reported as solid lines and shaded areas correspond 20th (resp. 80th) percentiles.
Sample
Sample
Sample
Sample
Sample 5
softDTW Gromov-DTW DTW-GI
softDTW-GI
Samples
Barycenters
Figure 5: Barycenter computation using (i) DTW and softDTW bascline approaches, (ti) the alternative Gromov-DTW (Cohen et al. 2021) and (iii) proposed rotation-invariant DTW-GI and softDTW- Each row correspond to a different dataset, and the latter one contains both 2D and 3D trajectories, hence cannot be tackled by DTW nor softDTW. Trajectories are color-coded from blue (beginning of the series) to yellow (end of the series).
slightly more robust high levels of noise than the CTW bascline, while GromovDTW is very sensitive this noise level (the GW loss is quadratic function of its input).

---

Published in Transactions on Machine Learning Research (10/2022)
1 1 13345677
GromonDTN WONDTWOO DI
1 6
Voo
i nod
Figure 6:
Barycenters computed on the RTD Dataset from 50 sample trajectories from each of the 10 classes using DTW-GI, softDTW-G and GromovDTW. Trajectories are color-coded from blue (beginning of the series) to yellow (end of the series).
4.3 Barycenter computation
So as to better grasp the notion of similarity captured by our methods, we compute barycenters using the strategy presented in Section 3.3 Barycenters are computed for 3 diffcrent datascts: the first two are made of 2D trajectories of rotated and noisy spirals or folia, and the third one is composed of both 2- and 3-dimensional spirals (see samples in the left part of Figure 5 For each dataset, provide barycenters obtained by three bascline methods. DTW Barycenter Averaging (DBA, Petitjcan et al. 2011) is used for DTW while Sof resorts to a gradient-descent scheme to compute the barycenters. Their GI counterpart use the same algorithms but rely on the alignments obtained from DTW-GT and softDTW-GT respectively. Finally, GromovDTW is optimized by alternating between computation of the barycenter self-similarity matrix and alignments, as done in Cohen et al. (2021). Note that the DTW and softDTW baselines cannot be used for the third dataset since features of the time series do not lie in the same ambient space. We would like to emphasize that the barycenter based GromovDTW only finds pairwise distance matrix from which the positions of the points must be inferred, for example by applying multidimensionall scaling (MDS) (Kruskal & Wish 1978) (as done here and in Cohen et al. 2021
For the 2d spiral datasct, all the reconstructed barycenters can be considered as meaningful. Note however that the outer loop of the spiral (the one that suffers the most from the rotation) better reconstructed using DTW-GI and softDTW-GI variants. When comes to the folia trajectories, that are more impacted by rotations, baseline barycenters fail to capture the inherent structure of the trajectories at stake, while both our methods generate smooth and representative barycenters. DTW-GI and softDTW-GI are even able to recover barycenters when datasets are made of series that do not lie in the same space, as shown in the third row of Figure 5. Finally, in all three settings considered, temporal alignments successfully capture the irregular sampling from the samples to be averaged (denser towards the center of the spiral / loop of the folium).
The RealSense based Trajectory Digit (RTD) dataset Alam et al. (2020) is made of digit writing trajectories. In our experiment, we have randomly sampled 50 trajectories per digit class and computed trajectory barycenters using (soft) and GromovDTW. On such data, expected invariants rotations and translations. One can observe that invariance to mirroring strongly impacts CromovDTW's barycenter estimation on classes 4, 7 and 9. On the other hand, for both DTW-GI and Dof-D we obtain meaningful barycenters that do not suffer from mirroring artifacts and better preserve overall trajectories.
4.4 Time series forecasting
To further illustrate the benefit of our approach, we consider time series forecasting problem (Le Guen & Thome, 2019), where the goal is infer the future of a partially observed time series. In this setting, we suppose that we have access to a training set of full time series X, with (9) E X a time series of length T
10

---

Published in Transactions on Machine Learning Research (10/2022)
Ground truth
Train Sample 0
Train Sample
Train Sample
Train Sample
Train Sample
DTW-GI. Err=37.68
Coeff 0.89792
Coeff 0.09569
Coeff 0.00317
SoftDTW-GI. Err=39.23
Coeff = 0.79506
Coeff = 0.06918
Coeff 0.03905
CTW. Err=187.01
Coeff = 0.03336
Coeff = 0.03336
Coeff 0.03335
GromovDTW. Err= 184.9
Coeff 0.09044
Coeff 0.08969
Coeff 0.07673
Figure 7: Examples of the forecasted subseries. (first row) The first sample the ground-truth yT for the subject S1 and then training samples xf"_ are depicted. (from second to last row) Predictions for the methods DTW-GI, DTG-GG, CTW and GromovDTW (the other methods are given in 8) In the first column the prodiction ýr is depicted along with the error |/ - yr2 In the other columns, we illustrate the first 3 neighbors w.r.f. the method (()
x associated with their coefficients 0d (y-r: x x For each movement arrow indicates the orientation of the subject. The beginning of the movement is displayed in shaded blue while the end is displayed in bold red.
11

---

Published in Transactions on Machine Learning Research (10/2022)
L2. Err=187.01
Coeff 0.03334
Coeff 0.03334
Coeff 0.03334
Procrustes. Err=46.54
Coeff 0.93897
Coeff 0.02469
Coeff 0.02304
softDTW. Err=187.02
Coeff 0.03459
Coeff 0.03443
Coeff 0.03440
Prr+rrocss Err=43.34
Coeff 0.89792
Coeff 0.09569
Coeff 0.00317
SoftDTT-+Pocrustes: Err=43.22 43.22
Coeff 0.94239
Coeff 0.02054
Coeff 0.01462
Figure Examples of the forecasted subseries for the methods L,2 T.2+Procrssses, DTW. and
12

---

Published in Transactions on Machine Learning Research (10/2022)
and dimensionality Pa, and another test set of partial time series Y where each y Y is of length T < T and dimensionality py- The goal is to predict the values for timestamps T to T for each test time series. We will denote by x the beginning of the time series x (up to time T" and xT- its end (from time T" to time T).
Let d(y,x(0) denote a dissimilarity measure between time series y and x(0) associated with a transformation fi F: 12 + Hy that maps the features of x(0 onto the features of y. This function aims at capturing the desired invariances in the feature space, described in the previous section. A typical example is when d is the (soft) DTW-GI cost, then the f. are the Stiefel linear maps which capture the possible rigid transformation between the features. We propose to prodict the future of a time series y as follows:
ST = =aa ad (V-T,xx)) x fi (xT--
(20)
where da is the attention kernel:
e -xd(y,xx)
(y, xx)
(21)
Σ, xx xz)
with À > O. The prediction is based on the known timestamps for the time series of the training set and on transformations fi that aim at capturing the latent transformation between training and test time scries. The attention kernel gives more importance to time series that are close to the time series we want to forecast. w.d. the notion of dissimilarity d. Note that for large values of X, the softmax in Equation 21 converges to a hard max and the proposed approach corresponds to a nearest neighbor imputation.
4.4.1 Dataset and methodology
We use the Human3. 6.M dataset (Lonescu et al., 2014) which consists of 3.6 million video frames of human movements recorded in a controlled indoor motion capture sctting. This dataset is composed of actors performing 15 activities ("Walking", "Silting" ...) twice. We are interested in forecasting the 3D positions of the subject joints evolving over time. More precisely, each data point x(0 is a time series representing a skeleton of 32 joints where each joint is described by 3D coordinates. This problem corresponds to Pa = Py = 32 x 3. We follow the same data partition as Coskun et al. (2017): : the training set has 5 subjects (S6, S7, S8, S9 and S11) and the remaining 2 subjects (S1 and S5) compose the test set. In our experiments, 1) we split the limit frames as follows: we keep the first T" 300 timestamps to calculate the coefficient
ad (y-rr, (i) ) and the transformations fi 2) we find the hyperparameter À which gives the best prediction (w.r... the l norm) for t E [T", Tol (where To = 400) 3) the remaining times [To, T') are used for the test set. We set the last limit frame as T" = 1100 which corresponds to predicting T" - To = 700 timestamps, that is predicting 14 seconds of motion given the initial 8 seconds. To emulate possible changes in signal acquisition (e.g. rotations of the camera), we randomly rotate the train subjects w.r.t. the z-axis. We consider the movements of type "Walking", "WalkDog" and "WalkTogother for the training set and "Walking" for the test set. Top row of Figure 7 illustrates samples of movements x" resulting from this procedure and the resulting dataset is provided as supplementary material.
4.4.2 Competing structured prediction methods
We look for global transformations of the features ft : 1223 + 132233 In order to obtain coherent transformations for each joint of the skeleton, the fi are structured as fi -gi, 9a. 9i where gi R²3 R
In other words, we consider that there is only one global 3D transformation that aligns all the joints of two time series (such as one rotation). We use DTW-GI and SoftDTW-GI as our similarity mcasures and the associated maps Se as described in Equation 5 and in Equation 7 We compute DTW-GI using the BCD procedure with block-structured rigid transformations of the features as in Equation 18 (q. = qu = 3, A = 32 in this context). We calculate Soft.TT-GI with automatic differentiation as described in Section 3.2 In this experiment we set 7 0.05 for the smoothness parameter. We compare these methods 8 baselines, that correspond to different pairs of time series similarity measure and feature space invariances. The first two
13

---

Published in Transactions on Machine Learning Research (10/2022)
Method
Average test error
L2
183.11 + 3.90
sWf (Cuturi & Blondel
2017
183.12 12 + 3.90
CTW [Zou & Torre 2009)
183.11 = 3.90
GromovD (Cohen et al. 2021
181.28 + 3.71
L2 Procrusss
46.33 = 0.21
DTW+ + Prrocrsstss
43.31 0.03
SoftDTW HETW+PPee Procrustes
43.90 0.11
DTW-GI (ours)
38.05 + 0.37
softDTW-GT (ours)
39.58 0.34
Table 1: Average error on tests subjects for the time series forecasting on the Human3.6M dataset
baselines, denoted L2 and softDTW, do not encode any feature space invariance and are based on l and softDTW similaritics respectivcly. We also consider a Procrustes bascline (Goodall 1991h defined as:
x ..) = min [1 ( P +b) -rrr
(22)
P.b
where P blockdiag:: (p) with E V3,3 and b (b, ... b) with b R The corresponding transformation ft is the affine map based on the optimal P*, b found by the previous problem. We denote this baseline Procrustes. Two other baselines are computed by first registering series using the Procrustes procodure defined above and then using the similarity measure ,(y-r,,,",
= DTW(y -r,, x +1" P + b*) and + b*). They are denoted respectively by Procrusssss and softDTW Procrustes. Finally, also compare with GromovDTW (Cohen al. 2021) and CTW (Zhou &
x()
(t) d(y-T', x (8) T-) DTW, x
Torre 2009 Note that the methods L2, sonDTW, GromovDTW and CTW do not provide transformation
of the features of x onto those of y- and, as such, we set f, = id for all these methods.
(6)
4.4.3 Results
Qualitative and quantitative results are provided in Figures 7 and Table respectively. We evaluate, for each test subject, the & reconstruction loss Iyyr= - between the ground truth time series and its prediction. Table displays the average loss on the test subjects based on the best hyperparameter found using the timestamps [To, I"]. Figures 7 and present examples of reconstructed movements for the different methods one test subject as well the 3 highest coefficients da with the corresponding neighbors.
We observe from the quantitative study that sofDDT, L2, CTW and GromovDTW lead to the worst reconstruction losses while L2 Prorrrccsss + DoW and DTW-GI, SoftDTW- GI lead to the best ones. The results for the first four methods can be explained by the fact that none of them can use an explicit spatial transformation of the feature f; for the prediction and thus only a simple weighted average of the time-series X is realized. This is illustrated for CTW, GromovDTW, softDTW and L2 in Figures 7 and [ where we can see that the prediction tends to shrink. We can also see that DTW+Procruse and WoftDTW-Prorrusst importance of temporal realignment. More importantly, the performances of DTW-GT and softDTW-GI are also better than + realignment of time and space has an advantage over a two-step procedure such as DTW+ SoftDDWWProcrustee which first finds the feature transformation and then aligns series in time.
are superior to a simple P2*Prrcssss which highlights the
DoftDTW+Prooruse
and 1.2+Procruste which shows that our joint
Morcover, one can observe qualitatively that GromovDTW and CTW seem to uniformly average all the different motions lo compensate for the lack of reprojection fi. On the contrary, by capturing the possible spatial variability, L2+Procrustes and predicted movement slightly less accurate than the one of soft.DTW-GI. This is due the fact that mainly chooses the movement corresponding the first nearest.
perform reasonably well qualitatively but the
L2 12+Prrcuusees or MofDTW+Proeett neighbor (a 0.94) while soft DTW-GT is able to average other dynamics (aa[1) = 0.79). It is somehow
14

---

Published in Transactions on Machine Learning Research (10/2022)
DTW (OTI), M 0.6
CTW, 33.-3332
GromovDTW. MRI=25.0 0.6
1.0
DTW-GI (OTT) MRI=2455
softDTW-GI (OTD) 1-2.333 0.7
0.8
0.7
0.6
0.6
Recall
0.5
0.4
0.4
0.2
0.3
0.2
0.0
0.1
Rank
0.0
10
Figure 9: Cover song identification using the covers80 dataset. Methods compared in terms of recall and results averaged over 10 train / test set draws. For each method, the shaded area corresponds to standard deviation around the mean value.
a natural conclusion since the optimal transformations found by the Procrustes analysis supposes trivial one-to-one correspondence of the timestamps (i.e. (t) corresponds to x x" (t) at the same time t) and do not consider the temporal shifts between them. In this way, the method L2+ Procrusss leads to unrealistic transformations when the dynamics of movements are not the same. Note that the two-step procedure Procrutes is only slightly more precise as the feature realignment is independent of the temporal realigmment since both are not optimized jointly. On the opposite, SoftDT method leads to the best qualitative results, highlighting the benefits of our approach over methods that whether discard the temporal variability of the movements (I.2+ Procrustes) its spatial variability (softDTW).
4.5 Cover song identification
Cover song identification the task of retrieving, for a given query song, its covers (i.e. different versions of the same song) in a training set. State-of-the-art methods either rely on anchor matches in the songs and/or on temporal alignments. In most related works, chroma or harmonic pitch class profile (HPCP) features are usually chosen, they capture harmonic characteristics of the songs at stake (Heo et al. 2017
For this experiment, use the covers80 dataset (Ells & Cotton 2007) that consists in 80 cover pairs of pop songs and we evaluate the performance in terms of recall. Since the selection of features is not our main focus, we choose to extract chroma. energy normalized statistios (CENS, (Müller et al. 2005)) over half a second windows. We compare variants of our method to a bascline that consists in a DTW alignment between songs transposed to the same key using the Optimal Transposition Index (OTI, (Serra et al. 2008)). ). This OTI computes a transposition based on average energy in each semitone band. For each competitor, test set songs are ranked based their distances to query songs.
Figure presents recall scores for compared methods as well as the mean rank of the first correctly identified cover (MR1) that is a standard evaluation metric for the task (used in MIREXf for example). For the sake of readability, performance for DTW-GI with feature space optimization on the Stiefel manifold is omitted in this Figure. In practice, this approach leads to an MR1 of 29.0 = 1.0, which is clearly outperformed by the baseline relying on OTI. This is because a very common transformation in this setting when cover songs are played in different keys, which is captured by the OTI transposition strategy. Similarly, CTW, which
https://www/ wwwp:wwwmiiiiie wtt.ri/rrrr/eeeeeeiiii//////111 Audio_ Cover_ Sartii__Cver_SSog_____ Identificatiion
15

---

Published in Transactions on Machine Learning Research (10/2022)
does not allow to use prior information about the form of the feature space registration into account, behaves poorly in this setting. Interestingly enough, the flexibility of our DTW-GI framework allows us to use the OTI strategy. Since the registration family F in this OTI setting is restricted to the set of 12 possible key transpositions, we do not rely on BCD in this case and rather seek for the exact optimum by computing (soft-)DTW for each of the 12 possible transpositions ions and retain the minimizer. This way, we are able to compute the optimal transposition index along the alignment path instead of computing it on averaged features, as the "DTW (OTI)" baseline does. This leads to a significant improvement of the performance for both DTW-GI and its soft counterpart and illustrates both the versatility of our method and the importance of performing joint feature space transformation and temporal alignment.
Note finally that the performance reached by the competitors in this study is far from what deep models can achieve. ByteCover Du et al. (2021), for example, reaches an MR1 of 3.54 on this task, by relying on both a triplet loss and a classification loss derived from a proxy classification task to train a ResNet. The use of softDTW-GI as an alternative similarity measure in the triplct loss of such an approach left for future work.
5 Conclusion and Perspectives
We propose in this paper novel similarity measure that can compare time series across different spaces in order to tackle both temporal and feature space invariances. This work extends the well-known Dynamic Time Warping algorithun to deal with time series from different spaces thanks to the introduction of a joint optimization over temporal alignments and space transformations. In addition, we provide a formulation for the computation of the barycenter of a set of times series under our new geometry, which is, to the best of our knowledge, the first barycenter formulation for set of heterogencous time series. Another important special case of our approach allows for performing temporal alignment of time series with invariance to rotations in the feature space.
We illustrate our approach on several datasets. First, we use simulated time series to study the computational complexity of our approach and illustrate invariance to rotations. Then, we apply our approach on two real-life datasots for human motion prediction and cover song identification where invariant similarity measures are shown to improve performance.
Extensions of this work will consider scenarios where features of the series do not lie in a Euclidean space, which would allow covering the case of structured data such as graphs evolving over time, for example. Future works also include the use of our methods in more elaborated models where, following ideas from Cai el. al.
(2019); ; Iwana et al. 2020), softDTW-GI could be used as a feature extractor in neural networks. It could
also serve as a loss to train heterogencous time series forccasting models (Le Guen & Thome 2019 Cuturi & Blondel 2017) or for imitation learning problems as considered in Cohen et al. (2021) where one wants to learn an agent (parametrized by a neural network) that generates trajectories on a different. space than the initial ones.
Acknowledgments
This research was supported in part by ANR through the MATS project ANR-18-CE23-000 by the AllegroAssai project ANR-19-CHIA--000 and the ACADEMICS grant of the IDEXLYON, project of the Université de Lyon, PIA operated by ANR-16-IDEX-0005 NC is partially funded by the projects ОTTOPIA ANR-20- CHIA--0000 AI chair. This research was also supported by 3rd Programme d d'Investissements d' Avennr ANR-1S-EUR-0006:
This action benefited from the support of the Chair "Challenging Technology for Responsible Energy" led by I'X Ecole polytechnique and the Fondation de l'Ecole polytechnique. TV gratefully acknowledges the support of the Centre Blaise Pascal's IT test flat.orm at ENS de Lyon (Lyon, France) for Machine Learning facilities. The platform operates the SIDUS solution (Quemener & Corvellec 2013). The results are processod for visualizations using matplotlib (Hunter) 20077) Numerical computations involve numpy (Harris et al. 2020), scipy (Virtanen et al. 2020) and scikit-learn (Pedregosa et al. 2011 for the CTW implementation.
16

---

Published in Transactions on Machine Learning Research (10/2022)
References
Md. Shahinur Alam, Ki-Chul Kwon, Md. Ashraful Alam, Mohammed Y. Abbass, Shariar Md Imtiaz, and Nam Kim. Trajeclory-based air-wriling recognition using deep neural network and depth sensor. Sensors, 20(2), 2020. ISSN 1424-8220.
David Alvarez-Melis Melis, Stefanie Jegelka, and Tommi S Jaakkola. Towards optimal transport with global invariances. In International Conference on Artificial Intelligence and Statistics, 2019.
David Alvarez-Melis, Youssef Mroueh, and Tommi Jaakkola. Unsupervised hierarchy matching with optimal transport over hyperbolic spaces. In International Conference on Artificial Intelligence and Statistics, pp. 1606-1617 PMLR, 2020.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arviv preprint ar wwxXi:1907.028890 2019.
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andy Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Laugston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matt Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascamu. Relational inductive biases, deep learning, and graph networks. arXiv, 2018.
Gary Becigneul and Octavian-Eugen Ganea, Riemannian adaptive optimization methods. In Proceedings of the International Conference Learning Representations, 2019.
Shai Ben-David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In International Conference on Artificial Intelligence and Statistics, pp. 129-136, 2010.
Xingyu Cai, Tingyang Xu, Jinfeng Yi, Junzhou Huang, and Sanguthevar Rajasekaran. Dtwnet: a dynamic time warping network. In Neural Information Processing Systems, pp. 11636-11646, 2019.
Chien-Yi Yi Chang, De-An Huang, Yanan Sui, Li Fei-Fei, and Juan Carlos Niebles. D3tw: Discriminative
differentiable dynamic time warping for weakly supervised action alignment and segmentation. In IEEE Conference on Computer Vision and Pottern Recognition, pp. 3546 3546-3555, 2019.
Yang Chen and Gérard Medioni. Object modelling by registration of multiple range images. Image and Vision Computing, 10(3):145 155, 1992.
Samuel Cohen, Giulia Luise, Alexander Terenin, Brandon Amos, and Mare Peter Deiscnroth. Aligning time series on incomparable spaces. In International Conference on Artificial Intelligence and Statistics, volume 130, pp. 1036-1044, 2021.
Scott Cohen and L Guibas. The Earth mover's distance under transformation sets. In IEEE International Conference on Computer Vision, volume 2, pp. 1076-1083, 1999.
Huseyin Coskun, Felix Achilles, Robert DiPietro, Nassir Navab, and Federico Tombari. Long short-term memory kalman filters: Recurrent neural estimators for pose regularization. Tn International Conference Computer Vision, Oct 2017.
Marco Cuturi and Mathicu Blondel. Soft-DTW: a differentiable loss function for time-scrics. In International Conference on Machine Learning, pp. 894-903, 2017.
Marco Cuturi, Jean-Philippe Vert, Oystein Birkenes, and Tomoko Matsui. kernel for time series based on global aliguments. In JEEE International Conference on Acoustics, Speech, and Signal Processing, volume 2, pp. II-413. IEEE, 2007.
Huiqi Deng, Weifu Chen, Qi Shen, Andy J. Ma, Pong C. Yuen, and Guocan Feng. Invariant subspace learning for time series data based on dynamic time warping distance. Patlern Recognition, 102:107210, 2020.
17

---

Published in Transactions on Machine Learning Research (10/2022)
Xingjian Du, Zhesong Yu, Bilci Zhu, Xiaoou Chen, and Zejun Ma. Bytecover: Cover song identification via multi-loss training. In TEEE International Conference on Acoustics, Speech, and Signal Processing, pp- 551 551-555, 2021. doi: 10.1109/CCASS333722222222 20211923399722222211114111 99414128.
Danicl PW Ellis and Courtenay Valentine Cotton. The 2007 labrosa cover song detection system, 2007.
Colin Goodall. Procrustes methods in the statistical analysis of shape. Journal of the Royal Statistical Society: Series B (Methadological), 53(2):285- 321, 1991.
lan Goodfellow, Honglak Lee, Quoc V. Le, Andrew Saxe, and Andrew Y. Ng. Measuring invariances in deep networks. In Neural Information Processing Systems, pp. 646-654, 2009.
Charles R Harris, K Jarrod Millman, Stéfan Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Scbastian Berg, Nathanicl J Smith, et al. Array programming with numpy. Nature, 585(7825)3357 362, 2020.
Hoon Heo, Hyunwoo J Kim, Wan Soo Kim, and Kyogu Lee. Cover song identification with metric learning using distance as a feature. In Proceedings of the International Sociely for Music Information Retrieval Conference, 2017.
Shih-Feng Huang and Hong-Ping Lu. Classification of temporal data using dynamic time warping and compressed learning. Biomedical Signal Processing and Control, 57:101781, 2020.
John D Hunter. Matplotlib: A 2d graphics environment. Computing in science & engincering, 9(03):90-90 2007.
Catalin Tonescu, Dragos Papava, Vlad Olaru, and Cristian Sminchisescu. Human3.6m Large scale datasets and predictive methods for 3d human sensing in natural environments. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(7):1325-1339, jul 2014.
Brian Kenji Iwana, Volkmar Frinken, and Seichhi Uchida. DTW-NN: a novel neural network for time series recognition using dynamic alignment between inputs and weights. Knowledge-Bood Based Systems, 188, 2020. ISSN 0950-7051. doi: k..016/..knooys.2019.uk
Martin Jaggi. Revisiting Frank-Wolfe: Projection-Fee sparse convex optimization. In International Conference Machine Learning, 2013.
Hicham Janati, Marco Cuturi, and Alexandre Gramfort. Spatio-temporal alignments: Optimal transport. through space and time. In International Conference on Artificial Intelligence and Statistics, pp. 1695 1704, 2020.
Max Kochurov, Sergey Kozlukov, Rasul Karimov, and Viktor Yanush. Geoopt: Adaptive riemannian optimization in PyTorch, 2019. http:////iituub..omooooooo/
Wouter Marco Kouw and Marco Loog. A review of domain adaptation without target labels. IEEE Transactions Pattern Analysis and Machine Intelligence, 2019.
J.B. Kruskal and M. Wish. Multidimennionall Scaling. Sage Publications, 1978.
Jim Lawrence, Javicr Bornal, and Christoph Witzgall. purely algebraic justification of the kabsch- umeyama algorithm. Journal of Research of the National Instilute of Slandards and Technology, 124:1-6 2019.
Vincent Le Guen and Nicolas Thome. Shape and time distortion loss for training deep time series forecasting models supplementary matcrial. In Neural Information Processing Systems, 2019.
Meinard Müller, Frank Kurth, and Michael Clausen. Audio matching via throma-based statistical features. In Proceedings of the International Sociely for Music Information Retrieval Conference, 2005.
18

---

Published in Transactions on Machine Learning Research (10/2022)
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca. Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performanee deep learning library. In H. Wallach, H. Larochelle, A. Beygekimer, F. d' d'Alché Buc, E. Fox, and R. Garnett (eds.), Neurul Information Processing Systems, pp. 8024-8035. 2019.
F. Podregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prottenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 2011.
François Petitjean, Alain Ketterlin, and Pierre Gançarski. A global averaging method for dynamic time warping, with applications to clustering. Pattern Recogration, 44(3):678 - 693, 2011.
Emmanuel Quemener and Marianne Corvellec. Sidus the solution for extreme deduplication of an operating system. Linuz Journal, 2013(235):3, 2013.
Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1):43 49, 1978.
Joan Serra, Emilia Gómez, and Perfecto Herrera. Transposing chroma representations to common key. In Proceeding sof the IEEE Conference on The Use of Symboll to Represent Music and Multimedia Objects, pp. 45-45 48, 2008.
Romain Tavenard, Johann Faouzi, Gilles Vandewiele, Felix Divo, Guillaume Androz, Chester Holtz, Marie Payne, Roman Yurchak, Mare Rußwurm, Kushal Kolar, al. Tslearn, A Machine Learning Toolkit for Time Scries Data. J. Mach. Learn. Res., 21(118)11-6, 2020.
Gineke A Ten Holt, Marcel JT Reinders, and EA Hendriks. Multi-dimensional dynamic time warping for gesture recognition. In Annual conference of the Advanced School for Computing and Imaging, volume 300 pp. 1, 2007.
George Trigeorgis, Mihalis A Nicolaou, Stefanos Zafeiriou, and Bjorn W Schuller. Deep canonical time warping. In EEE Conference on Computer Vision and Pattern Recognition, pp. 5110-5118, 2016.
Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261 272, 2020.
Victor Wegner Maus, Gilberto Câmara, Marius Appel, and Edzer Pebesma. diwsat: Tiin-weighted dynamic time warping for satellite image lime series analysis in R. Journal of Stalisticnl Soflware, 88(5):1 -1,,, 2019.
Zaiwen Wen and Wotao Yin. feasible method for optimization with orthogonality constraints. Mathemalionl Programming, 142(1-2):397-4344 2013.
Martin Wöllmer, Mare Al-Hames, Florian Eyben, Björn Schuller, and Gerhard Rigoll. A multidimensionaal dy- namic time warping algorithm for efficient multimodal fusion of asynchronous data streams. Newrocomputing. 73(1-3):366 380, 2009.
Zheng Zhang, Romain Tavenard, Adeline Bailly, Xiaotong Tang, Ping Tang, and Thomas Corpetti. Dynamic time warping under limited warping path length. Information Sciences, 393:91-107, 2017.
Feng Zhou and Fernando De la Torre. Generalized time warping for multi-modal alignment human motion. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 1282-1289, 2012.
Feng Zhou and Fernando Torre. Canonical time warping for alignment. of human behavior. In Advances in neural information processing systems, pp. 2286-2201 2009.
19

---

Published in Transactions on Machine Learning Research (10/2022)
6 Appendix
For matrix p we note:
0
blockdiaga (p) - diag( p. p....
kttims
P
We will prove the following Lemma:
Lemma 6.1. Let qz 99 E N such that qv S au and & E N. Consider E R xk We write the block diagonal decomposition of C as:
Cn1
C12
C1k
C21
C2
Czk
C=
C
C22
Cak/
where Cúj R*=x,, for i,j E (1,... .k. Consider C = D C₁ E 12 the sum of the diagonal blocks of C and consider the full SVD decomposition of UEV
where U,E.V R xay, Then the solution to:
max PE PE 0y
(,, blockdiagg, (p))
(23)
is given by p UVT.
Proof. We have:
p
0
0
Cn
C12
CiR
0
p T
0
C2
C2
C2
(C, blockdiag, (p))r tr (blockdiag, (C) = tr
Ck
C22
Ckk
Cn C12 p C
p Cik
p Cz
p Czk
tr
Σ
tr(p T C.))
CHI
p
CC
p Cak
tr
p
C.)
C. (C.p)
Thus finding the solution to Equation 23 is the same as finding the solution to maxpeV ay (C.p) which is given by the SVD of C Jaggi
2013
0
20


Reviews:
[{"review_id": "8lb7GRdlOS", "reviewer": "Reviewer_PDzS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nI would like to draw the attention of the authors to the following points that can improve the manuscript. \n\n- My intuition is that the performance of the method heavily depends on the choice of the family of transformations $\\mathcal{F}$. Additionally, to the best of my understanding, the authors only consider the space of linear mappings. This, however, makes the contribution valuable, since for the arguably simplest family of transformations (linear maps) the proposed method outperforms the benchmarks in many aspects. \n\n- What are the invariances that DTW-GI can incorporate in practice? The linear assumption on the maps results (in, again, my intuition) only in rotations, so, how does this help for real-world datasets?\n\n- In the same line, are the invariances with which the method can deal truly \"global\" as the title suggests? After reading the paper I see that the invariances are \"linear\" only (which in the experiments works well, but I don't see how a global or more general class of invariances can be accounted for).\n\n- The analysis of the meaning of linear transformations can be studied deeper in the paper. For instance, in addition to rotations, a linear transformation can be a combination of sources and thus related to PCA or other factor models, with this in mind one could both perform the temporal matching and find a compressed representation of the data at the same time. Another linear transformation of interest are the Fourier/cosine/wavelet transforms, where one series lies in time and the other in the spectrum but they could in theory still be compared under DTW-GI nonetheless. \n\n- Lastly, a point that can be further explained is why the authors match the time series in the higher dimensional space. The method is applied (Sec 3.1) to two series x and y where dim(x)>dim(y) and x is compared to f(y), therefore, the DTW occurs in the space of x which is the high dimensional one (instead of the space of y). Why is this? isn't it better to compare the series in the lower domain due to computational complexity? I am also thinking that, if both series were to be transformed onto a lower dimensional domain, the method could provide a \"minimal-dimension\" comparison. These are just ideas but perhaps worth mentioning them", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Disclaimer:** I have reviewed this paper in the past for another journal. My impression of this manuscript, even in its earlier versions, has always been positive with a few points that can be improved. In my review below I include some of my comments given in a previous review that are still valid in this version. \n\n**Summary:** The article proposes an extension to the Dynamic Time Warping (DTW) and soft-DTW methods by jointly optimising a transformation of one of the series in order to compare series of different dimension. The authors refer to this methodology as a comparison among time series in both the temporal and feature spaces. The paper is clearly written, the contribution well placed within the literature, the experimental validation is convincing,  and the proposed idea is certainly of interest for the community. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "**In addition to changes derived by the comments above**, some particular changes are: \n\n- Eqs lack punctuation.  \n\n- Intro: aligns in \"times\" (is it \"time\"?)\n\n- Intro: in more \"details\" --> \"detail\"\n\n- Sec 2, page 3: what do you mean \"around the diagonal\"?\n\n- Sec 3.1: I suggest to state that Tx and px are the \"size\" and \"dimension\" of the time series x respectively (these concepts are used throughout the text)\n\n- Sec 4: Fig 9, I suggest to include axis labels in zoomed in figure\n\nI hope this recommendations helps improving the paper. \n", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wo1PjwqS0d", "reviewer": "Reviewer_LTHj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThis paper presents, to the best of my knowledge, an **original solution to a relevant problem**. Computing time series similarities is a non-trivial task, and this proposition tackles this issue with an interesting solution given its **simplicity, applicability and clear advantages**. In particular, the choice of invariance class and the recovered mapping between series make it transparent and appropriate when prior information on the compared series is available. Its **robustness to various settings**, stemming from this explicit choice of invariance class, is particularly appreciable. **All claims are well supported**, especially via a diverse set of experiments illustrating the interest of the proposed distance w.r.t. prior related approaches.\n\nThe paper is overall **well written**. It provides for the most part sufficient details on the proposed distance and experiments, making it **clear and easy to read** for a general audience. In particular, the most recent revision clearly improved the quality of the paper in this regard. The method is **sufficiently motivated** w.r.t. the existing literature and its presentation is supported by intuitive arguments and examples.\n\n### Weaknesses\n\nTo the best of my understanding, I detected no major weakness in the paper and/or method. Nonetheless, I think that there remains some room for improvement in some aspects.\n\nWhile the authors present two different optimization procedures to compute (soft)DTW-GI, **the interest of gradient descent remains unclear**. The performance difference between DTW-GI and softDTW-GI, as observed throughout the experiments and especially in Table 1 and Figure 2 is limited, while softDTW-GI is computationally more costly than DTW-GI. Moreover, all the experiments are performed in settings where other optimizations schemes can be be applied, like the proposed BCD over the Stiefel manifold. As hinted on page 6, gradient descent could be key to optimize DTW-GI when considering invariance w.r.t. a class of neural networks. However, **the use of DTW-GI combined with an overly large invariance class like neural networks might not be appropriate**: it could flatten differences between series and make the distance lose its meaning, which is one of its advantages.\n\nThe current set of experiments does show the interest of DTW-GI w.r.t. other distances in the literature, but **they do not demonstrate its interest w.r.t. other (non-distance based) approaches**. Indeed, the experiments with real-world data could be handled with other dedicated methods: sequential prediction models for time series forecasting, and deep models for cover song identification (as acknowledged by the authors). The barycenter experiment could highlight the interest of DTW-GI as a proper distance is key to compute barycenters, but it is only qualitative and performed on simple synthetic data.\n\nOne of the advantages of DTW-GI, shared with GromovDTW, is to handle time series lying in different feature spaces. However, **having different feature spaces raises applicability questions** which I think are not addressed in the paper. For example in the barycenter experiment, how can the dimensionality of the feature space be chosen? Moreover, only this toy experiment showcases this ability of DTW-GI; it would be beneficial for the paper to include an application case on real-world data.\n\nThe experiment of Section 4.2 raises an interesting comparison between GromovDTW and DTW-GI in terms of robustness to noise. This is a crucial property, yet **this robustness to noise is not highlighted in the paper beyond this experiment on synthetic data**. I believe that further comments and/or experiments could help strengthening the interest of DTW-GI.\n\nFinally, I would have two comments regarding the reproducibility of the experiments:\n - there is no available source code at submission time but the authors indicate that it will be released upon publication;\n - the ranking method in Section 4.5 should be explicitly stated: I assume rankings are obtained based on distances between the covers and the base songs but this should be clearly indicated.\n\n\n### Context of Review\n\n  - I am knowledgeable about this domain but this is not my primary area of research.\n  - This review was completed after the first revision of the paper (September 23rd, 2022).", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a time series distance, (soft)DTW-GI, based on matching the alignments of series both in time and in space. This is achieved by selecting the minimal (soft)DTW distance between the compared series up to pointwise transformations, e.g. rotations, defining an invariance class for the distance. DTW-GI provides two key advantages: integrating prior knowledge on the series via the invariance class, and recovering a related optimal mapping between series that are possibly lying in different feature spaces.\n\nThe authors expose two possible optimization procedures to compute DTW-GI depending on the invariance class: gradient descent for differentiable objectives, and alternating optimization between spatial and temporal alignments, which for rigid transformations can be accelerated though SVDs. The applicability of DTW-GI is then empirically assessed against prior related approaches in diverse experiments: firstly, on synthetic data with an efficiency and robustness analysis and a barycenter computation test; secondly on real-world data with human motion prediction and song identification relying on intra-dataset comparisons using the compared distances.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Accordingly with the previous section, I would like to highlight that none of the following suggested changes are critical to securing my recommendation, but I believe that addressing them would help improving the submission.\n\n - Could the authors comment on the interest of the gradient descent optimization scheme? In particular, how could we interpret DTW-GI when used with neural networks as invariance class?\n - Could the authors include a discussion and/or new experiments to motivate the use of DTW-GI beyond applications when other (non-distance based) dedicated methods might outperform it?\n - Could concrete examples of applications with time series lying in different feature spaces be included in the paper?\n - Could the experiments elaborate on the robustness to noise of DTW-GI w.r.t. GromovDTW, for example in the real-world data of Sections 4.4 and 4.5?\n - Could the authors explicitly state in Section 4.5 that rankings are obtained based on distances between the covers and the base songs?\n - Presentation request: please format Table 1 with the `booktabs` LaTeX package (for a better-looking presentation) and adjust the rainbow colormap of Figures 1, 2 and 5 to a perceptually uniform one (for better readability).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8s8zBVaIAh", "reviewer": "Reviewer_JXeQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The primary strength of the paper lies in the well-founded algorithmic\ndescription. Algorithms and concepts are, for the most part (see below\nfor some comments), introduced in sufficient detail and explained very\nwell. The theoretical derivation is correct; most experimental details\nare described adequately to ensure reproducibility.\n\nSome minor issues need to be rectified before publishing this work:\n\n- A more quantitative evaluation of certain results\n- Minor inconsistencies in descriptions\n- Missing details for forecasting setup\n\nI will subsequently comment on these changes (along with some minor\ntextual changes) but want to stress that the authors are to be commended\nfor a high-quality work; this paper is really a joy to read and\ncontributes a direly-needed perspective to time series analysis.\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission presents a novel framework for aligning time series. In\ncontrast to existing work, the proposed framework permits alignments in\ncases of differences in sampling frequency as well as certain geometric\ndeformations. The latter part is of particular interest in practice, as\nit permits imbuing the alignment algorithm with additional information,\nsuch as certain transformations, making it *invariant* to these.\n\nThe framework permits different operations with time series, such as:\n\n- Alignment\n- Similarity assessment\n- Calculation of barycentres\n\nMoreover, the proposed framework gives rise to algorithms that are\ndifferentiable under mild conditions. The state of the art is thus\nenriched by demonstrating the utility of a new perspective that is\ncapable of encoding desirable invariances. Next to this, the paper\nalso provides a thorough set of experiments to demonstrate how the\nproposed framework improves time series tasks in practice. This is\na valuable contribution to time series learning on its own.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "As a brief note: whenever I use the term \"consider\", I want to stress\nthat this is not a required change from my point of view, but there is\nno other place in the review form to collect my thoughts.\n\n- In Figure 1, the meaning of $\\mathbb{V}_{2,3}$ should either be\n  explained directly or the registration part of the figure should be\n  slightly simplified. Moreover, the notation of $f^\\ast$ and $\\pi^\\ast$\n  should be briefly explained in the caption. This notation only became\n  clear to me after reading the full paper.\n\n- Please provide some notational details to Equation 2 when describing\n  the time series segments.\n\n- When introducing the optimisation problem in Equation 3, consider\n  briefly discussing to what extent symmetry in the arguments is\n  required here. \n\n- I have trouble understanding the re-formulation of Equation 14. $C$ is\n  supposed to be a matrix, but the vectors that are being used here\n  appear to be incompatible in terms of their dimensions. I am probably\n  misunderstanding something; can you please clarify this point to me\n  and potentially revise the phrasing accordingly for the revision?\n\n- Consider providing more steps (i.e. a brief justification) when\n  describing the equivalence of the left-hand side and the right-hand\n  side in Equation 17.\n\n- When describing the barycentre formulation, does the fact that DTW is\n  *not* a distance change anything? In the case of optimal transport\n  distances between objects, for instance, the minimiser of an equation\n  like Equation 18 is *unique*. Is this also the case here?\n\n- Please try to quantify the results in Section 4.2 and Figure 5, 6, 7.\n  In particular for Figures 6 and 7, I had trouble relating the things\n  that are being *shown* in the figure to the errors. Is there maybe\n  a simpler way to show differences in the individual trajectories, for\n  instance by highlighting a sub-area that did not work well?\n\n- Figure 8 could use a small inset to show \"disentangle\" some of the\n  parts with many overlaps a little bit better.\n\n- Consider adding some more details about optimisation spaces other than\n  the Stiefel manifold. Are there \"canonical\" examples that one could\n  make use of in practice? (Such a discussion does **not** have to be\n  fleshed out; I think it would improve the scope of the paper to\n  a substantial extent if more examples could be provided here)\n\nSome minor points concerning the wording and typesetting:\n\n- \"is defined as equivalent\" --> \"is equivalent\"\n\n- \"produces mostly erroneous\" --> \"produces a mostly erroneous\"\n\n- \"depend in\" --> \"depend on\"\n\n- \"gaussian\" --> \"Gaussian\"\n\n- \"Extension of this work\" --> \"Extensions of this work\"\n\n- \"cf.\" --> see (I was under the impression, drilled into me by some\n  well-meaning English literature students, that \"cf.\" should be used to\n  point to a cited proposition that is *analogous* to the present one,\n  but not directly equivalent, following the idea to \"compare\" two\n  sources. In this sense, \"cf.\" is not directly equivalent to the plain\n  \"see\". Apologies for being nitpicky here.)\n\n- Consider using `\\operatorname` or `\\DeclareMathOperator` instead of\n  writing $DTW$ in plain (La)TeX.\n\n- Why is the citation by Paszke et al. typeset in a different colour?\n\n- Please check the bibliography carefully for erroneous bibliographical\n  items; for instance, I saw that the paper by Cohen and Guibas is\n  incorrectly cited as \"Cohen and Guibasm\". Likewise, the paper by Jaggi\n  (2013) should use proper capitalisation for the Franke--Wolfe algorithm.\n\n", "broader_impact_concerns": "There are no broader impact concerns to be raised by this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wJ3TSSHAoT", "reviewer": "Reviewer_1VCa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and the problem is clearly motivated.\n- The method is simple to understand and presumably simple to implement.\n- The proposed method empirically outperforms different baselines.\n\nWeaknesses:\n- The tradeoffs between the soft and hard versions of the proposed method could be explained in more detail.\n- For the real-world experiments, some more standard baselines could be helpful.\n\nMajor comments:\n- In the forecasting experiment, only softDTW-GI is used and not DTW-GI. Why is that? Would DTW-GI not be applicable?\n- Since Fig. 3 suggests that softDTW-GI is several orders of magnitude slower than the other baselines, it would also be useful to report the runtimes in the forecasting experiment.\n- In the cover identification experiment, only DTW-GI is used and not the soft version. Again, why is that? It seems from the previous experiments that softDTW-GI generally works a bit better.\n- It would be useful to not only use time series alignment methods as baselines in the real-world experiments (although I do understand that those are the main competitors of the proposed methods), but also methods that practitioners would actually use. Especially in the case of the cover identification, methods like ByteCover [Du et al. 2020] achieve an MR1 < 4, which seems much better than all reported methods. It should therefore be discussed how realistic it would really be to use the proposed method in practice in this application. Additionally, reporting the performance in this experiment in terms of mAP would be helpful to compare to the literature.\n\nMinor comments:\n- Is there any intuition for why softDTW-GI outperforms DTW-GI on the synthetic data in Fig. 4? The ground-truth rotation should in principle be included in the search space of DTW-GI, right? Why does it not find it?\n- Sec. 3.1 bottom: alignement -> alignment\n- Sec. 4.4.2: Procruste -> Procrustes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a way to compute similarities between time series which are invariant to temporal and feature-level distortions. They achieve this by using a (potentially soft) variant of dynamic time warping (DTW) to align the time points and a learnable feature mapping to align the features, which notably even works when the time series have a different dimensionality. They then show that this can be used to compute barycenters, find nearest neighbors, and perform time series forecasting.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "My main two requested changes, based on the comments above, would be:\n- Make sure that DTW-GI and softDTW-GI are both used in all experiments or otherwise discuss why they should not be used in certain settings. Generally, provide a clear discussion of which of the two methods would be advisable to use as a practitioner, including a discussion of the tradeoff between performance and runtime on the different tasks.\n- Report the performance of some more standard baselines in the two real-world tasks. Especially in the cover identification experiment, all the reported methods seem to be suspiciously bad compared to the standard literature on the subject.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new method for aligning time series jointly in time and in the feature space, denoted as DTW-GI.

The submission received positive reviews, highlighting the relevance of the the approach, the clarity of the presentation and the convincing experimental validation.
During the discussion period, the authors provided additional experimental results, clarified the notations in the paper, and answered more general reviewers' concerns about the generality of the approach. The reviewers were very satisfied with the answers and they unanimously recommended paper acceptance.  

The AE carefully reads the submission, the reviews and discussions. He agrees that the approach is valuable and provides a solid contribution for the TMLR community. Therefore, the AE recommends acceptance.
Decision: Accept (poster)