Drop-DTW: Aligning Common Signal Between Sequences While Dropping Outliers
Authors: Nikita Dvornik
Isma Hadji
Konstantinos G. Derpanis
Animesh Garg
Allan Douglas Jepson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Sequence Matching
video representation learning
instructional videos
step localization

Abstract: In this work, we consider the problem of sequence-to-sequence alignment for signals containing outliers.  Assuming the absence of outliers, the standard Dynamic Time Warping (DTW) algorithm efficiently computes the optimal alignment between two (generally) variable-length sequences.  While DTW is robust to temporal shifts and dilations of the signal, it fails to align sequences in a meaningful way in the presence of outliers that can be arbitrarily interspersed in the sequences.  To address this problem, we introduce Drop-DTW, a novel algorithm that aligns the common signal between the sequences while automatically dropping the outlier elements from the matching.  The entire procedure is implemented as a single dynamic program that is efficient and fully differentiable.  In our experiments, we show that Drop-DTW is a robust similarity measure for sequence retrieval and demonstrate its effectiveness as a training loss on diverse applications. With Drop-DTW, we address temporal step localization on instructional videos, representation learning from noisy videos, and cross-modal representation learning for audio-visual retrieval and localization. In all applications, we take a weakly- or unsupervised approach and demonstrate state-of-the-art results under these settings.

Drop-DTW: Aligning Common Signal Between Sequences While Dropping Outliers
Nikita Dvornik Isma Hadji Konstantinos G. Derpanis Animesh Garg 2 Allan D. Jepson
'Samsung AI Centre Toronto
Universitty of Toronto. Vector Institute
(isma. (isma.hadji, allan. allan.jepsont jepson]]sammungg com
{n. (n.dvornik, k. derpanis) tner samsung.......... com gargêcs toronto. edu
Abstract
In this work, we consider the problem of sequence-to-sequees alignment for sig- nals containing outliers. Assuming the absence of outliers, the standard Dynamic Time Warping (DTW) algorithm efficiently computes the optimal alignment be- tween two (generally) variable-length sequences. While DTW is robust temporal shifts and dilations of the signal, it fails to align sequences in a meaningful way in the presence of outliers that can be arbitrarily interspersed in the sequences. To address this problem, we introduce Drop-DTW, a novel algorithm that aligns the common signal between the sequences while automatically dropping the outlier ele- ments from the matching. The entire procedure is implemented as a single dynamic program that is efficient and fully differentiable. In our experiments, we show that Drop-DTWW is robust similarity measure for sequence retrieval and demonstrate effectiveness as training loss on diverse applications. With Drop-DTW, we address temporal step localization on instructional vidcos, representation learn- ing from noisy vidcos, and cross-modal representation learning for audio-visual retrieval and localization. In all applications, we take a weakly- or unsupervised approach and demonstrate tfate-of-the-ar results under these settings.
Introduction
The problem of sequence-to-seeqeeee alignment is central to many computational applications. Align- ing two sequences (e.g., temporal signals) entails computing the optimal pairwise correspondence between the sequence elements while preserving their match orderings. For example, video []] or audio (2) synchronization are important applications of sequence alignment in the same modality, while the alignment of video audio (3] represents cross cross-modal task. Dynamic Time Warping (DTW) 2 is a standard algorithm for recovering the optimal alignment between two variable length sequences. It efficiently solves the alignment problem by finding all correspondences between the two sequences, while being robust to temporal variations in the execution rate and shifts.
A major issue with DTW is that it enforces correspondences between all elements of both sequences and thus cannot properly handle sequences containing outliers. That is, given sequences with inter- spersed outliers, DTW enforces matches between the outliers and clean signal, which is prohibitive in many applications. A real-world example of sequences containing outliers is instructional vidcos. These are long, untrimmed videos depicting person performing given activity (c.g.. making latte) following a pre-defined set of ordered steps (c.g., a recipe). Typically, only a few frames in the video correspond to the instruction steps, while the rest of the video frames unrelated the main activity (e.g., the person talking); see Figure [ for an illustration. In this case, matching the outlier frames instruction steps will not yield meaningful alignment. Moreover, the match score
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

DTW
Drop-DTW
Z:
Topic: making latte
pour espresso
2: steam
3: pour
outlier
Figure 1: Aligning instructional videos. Left: Both video sequences (top and bottom) depict the three main steps of "making latte"; however, there unrelated video segments, iee, outliers, inbetween the steps. DTW aligns all the frames with each other and creates false correspondences where outliers are matched signal (red links). Right: In contrast, Drop-DIW DTW finds the optimal alignment, while simultaneously dropping unrelated frames (crossed out), leaving only correct correspondences (green links).
between such sequences, computed by DTW, will be negatively impacted by "false" correspondences and therefore cannot be used reliably for downstream tasks, e.g., retrieval or representation learning.
In this paper, we introduce Drop-DTW address the problem of matching sequences that contain interspersed outliers as illustrated Figure (right) and compared to standard DTW (on the left). While various improvements DTW have been previously proposed (e.g.. [I 418). Drop-DTW is the first to augment DTW with the ability to flexibly skip through irrelevant parts of the signal during alignment, while still allowing one-to-many matching. Rather than relying on two-step greedy approach, where elements are first dropped before aligning the remaining signal, Drop-DTW achieves this in unified framework that solves for the optimal temporal alignment while jointly detecting outliers. Drop-DTV DTW casts sequence alignment as an optimization problem with novel component specifying the cost of dropping an element within the optimization process. efficiently realized using a dynamic program that naturally admits a differentiable approximation and can be efficiently used at training and inference time.
Contributions.
We propose extension of DTW that is able identify and align the common signal between sequences, while simultaneously excluding interspersed outliers from the alignment.
The proposed Drop-DTW formulation naturally admits differentiable approximation and we therefore demonstrate its usage as a training loss function.
We demonstrate the utility of Drop-DTW, for both training and inference for multi-step localization in instructional videos, using only ordered steps weak supervision. We achieve state-of- state-of-the-an tht-hhh-rtt art results on the CrossTase [9] dataset and are the first to tackle the COIN 10) and YouCook2 [1]] datasets, given only ordered steps (i.e., no framewise labels used).
We employ Drop-DTW as a loss function for wcakly-supervised video representation learning on the PennAction dataset 12]. modified to have interspersed outliers, and unsupervised audio-visual representation learning on the AVE dataset [13.. Compared to the baselines, Drop-DTW yields
superior representations, as measured by its performance on various downstream tasks.
Our code is available at: hhtps///hhhbbcccmmmmmmuuuuuutttp
2 Related work
Sequence alignment. The use of aligned sequences in learning has recently seen a growing interest
across various tasks [14] 4 5 15 1 6 [6] [7]. While some methods start from aligned paired signals [4. [8], others directly learn to align unsynchronized signals [15] 5 6.. One approach
tackles the alignment problem locally by maximizing the number of one-to-one correspondences
using a soft nearest neighbors method [15]. More closely related are methods 4 i 16 that seek a
global alignment between sequences by relying on Dynamic Time Warping (DTW) 2] To handle noise the feature space some methods use Canonical Correlation Analysis (CCA) with standard
DTW [99 20 To use DTW for end-to-end learning, differentiable approximations of the discrete operations (i.e., the min operator) in DTW have been explored 4 []. One of the main downsides of standard DTW-based approaches is that they require clean, tightly cropped, data with matching

---

endpoints. In contrast to such methods, Drop-DTW extends DTW and its differentiable variants with the ability to handle outliers in the sequences by allowing the alignment process automatically skip outliers (i.e., match signal while dropping outliers). While previous work [2] 6 [2] targeted rejecting outliers limited to the start or end of the sequences, our proposed Drop-DTW is designed to handle outliers interspersed in the sequence, including at the endpoints. Other work proposed limited approaches to handle such outliers either using a greedy two-step approach 77. consisting of outlier rejection followed by alignment, or by restricting the space of possible alignments 8 23 (e.g., only allowing one-to-one matches and individual drops). In contrast, Drop-DTW solves for the optimal temporal alignment while simultaneously detecting outliers and allowing for one-to-men many matches. As shown in our experiments, the ability of Drop-DTW to flexibly skip outliers during alignment can in turn be used at inference time to localize the start and end times of inlier subsequences.
approaches are increasingly popular for representation learning as they eschew the need of dense labels for training. Such approaches are even more appealing for video-based tasks that typically require inordinately large labeling efforts. A variety of (label-free) proxy tasks have emerged for the goal of video representation learning [1
Representation learning. Self- and weakly-superviie
More closely related are methods using sequence alignment as proxy task [3
T6 Our
approach has the added advantage of handling interspersed outliers during alignment. Also related are methods that leverage multimodal aspects of video, e.g., video-audio 42 43 or video-language
aligmment 47). Our step localization application builds on strong representations learned via the task of aligning vision and language using narrated instructional videos 45).. However, we augment these representations with a more global and robust approach to the alignment process, thereby directly enabling fine-grained applications, such as multi-step localization.
Step localization. Temporal step localization consists of determining the start and end times of one
or more activities present in a video. These methods can be broadly categorized into two classes
based on the level of training supervision involved. Fully supervised approaches (e.g.. [48] 49 I0)
rely on fine- graingd temporal labels indicating the start and end times of activities. Weakly supervised approaches eschew the need for framewise labels. Instead, they use a video-level label corresponding
to the activity category [50] 51. or sparse time stamps that provide the approximate (temporal)
locations of the activities. More closely related are methods that rely on the order of instruction steps
in clip to yield framewise step localization 54 5 9 contrast, we do not rely on categorical
step labels from a fixed set of categories and demonstrate that our approach applies to any ordered sequence of embedded steps, such as embedded descriptions in natural language.
3 Technical approach
3.1 Preliminaries: Dynamic time warping
Dynamic Time Warping (DTW) (2) computes the optimal alignment between two sequences subject to certain constraints. Let X [=i...., Iy] E RR xd and 2 = [Zı....,
E R xd be the input sequences, where N, K are the respective sequence lengths and d the dimensionality of each element. The valid alignments between sequences are defined as a binary matrix, M E {0. 1] R of the pairwise correspondences. where M.,, if 2; is matched to Zy, and otherwise. Note that Z corresponds to the first (row) index of M and X the second (column). Matching an element =; to element z, has a cost Ci,j which typically a measure of dissimilarity between the elements. DTW yields the optimal alignment M between sequencees sequences Z and X that minimizes the overall matching
cost:
M arg min(m,,MMMM C) = arr min MEM
Σ Ma,.Cr.. MEM 6.3
where (M, C*) is the Frobenius inner product and M is the set of all feasible alignments that satisfy the following constraints: monotonicity, continuity, and matching endpoints (M1,1 MM
1. VM E .M.. Fig. 2 (a) provides an illustration of feasible and optimal alignments. The cost of aligning two sequences with DTW is defined as the cost of the optimal matching: e* (M", C).
DTW proposes an efficient dynamic programming algorithm to find the solution to ①I
In the case of sequences containing outliers, the matching endpoints and continuity constraints are too restrictive leading to unmeaningful alignments. Thus, we introduce Drop-DTW that admits more flexibility in the matching process.
3

---

Feasible and Optimal Matchings
Aligning Sequences with Outliers
3
(a) DTW and Drop-DTW
(b) DTW
(c) Drop-DTW
Figure 2: Optimal alignment with DTW and Drop-DTW. Aligning two different videos where the digit "3" moves across the square frame. The colored matrices represent the pairwise matching costs, C, with darker cells indicating higher cost, Ct.y The paths the grid are alignment paths, while the points them indicate a pairwise match between paths, while only one of them (with solid line in green) is optimal. (b) When sequence X contains an outlier (i.c., digit "O"), DTW uses it in the alignment and incurs a high cost (red point). (c) In contrast, Drop-DTW skips the outlier (while paying the cost d5) and only keeps the relevant matches.
corresponding row and column elements. (a) three paths are feasible DTW
3.2 Sequence alignment with Drop-DTW
Drop-DTW extends consideration of feasible alignments, M, to those adhering to the monotonicity constraint only. Consequently, unlike DTW, elements can be dropped from the alignment process.
Before introducing Drop-DTW, let us discuss a naive solution to the problem of outlier filtering in DTW. One could imagine a greedy two-step approach where one first (i) drops the outliers, and then (ii) aligns remaining elements with standard DTW. Since step (i) (i.e., dropping) is performed independently from step (ii) (i.e., alignment), this approach yields sub-optimal solution. Critically, an important element is erroneously dropped in step (i), it is impossible to recover it in step (ii). Moreover, the outlier rejection step is order agnostic and results in drops broadly scattered over the entire sequence, which makes this approach inapplicable for precise step localization. To avoid such issues, it critical to jointly address (i) outlier detection and (ii) sequence alignment.
For this purpose, we propose Drop-DTW, a unified framework that solves for the optimal temporal alignment while jointly enabling element dropping by adding another dimension to the dynamic programming table. Specifically, dropping an element z means there is no element in Z that has been matched to z.. This is captured in the j-th column of the correspondence matrix M containing only zeros, i.e., M. =
To account for unmatched elements in the alignment objective, we extend the set of costs beyond pairwise matching, Ct,, used in DTW, with novel drop costs dē E RR and dž E R for elements E Z and 2z E X, respectively. The optimal matching can be then defined as follows:
M arg min C) P.(M) (d)) + (2MM) (d))
MEM
where denotes the inner product, M is the set of binary matrices satisfying just the monotonicity constraint, and P.. (M) is vector with the j-th element equal to one if the M.j. 0 and zero otherwise; Ps (2(M) is defined similarly, but on rows.
For clarity, in Algorithm I we describe the dynamic program for efficiently computing the optimal alignment and its cost with dropping elements limited X, i.e. de = co. Our general Drop-DTW algorithm that drops elements from both sequences, X and Z, is given in the supplemental.
3.3 Definition of match costs
The pairwise match costs, Cr,g. , are typically defined based on the dissimilarity between elements Ty and 2, In this paper, we consider two different ways define the pairwise costs, depending on the application. In general, when dropping elements from both X and Z is permitted, we consider the following symmetric match cost:
C -cos(2,, 2z).
(3)

---

Algorithm Subsequence alignment with Drop-DTW.
I: Inputs: Ce RKXNN pairwise match cost matrix, d drop costs for elements in
2:
inittializing dynamic programming tables
3: Dø = Di = oo; Dā. = 00;
i [K], E [N]
match table
4: Po.0 = 0; DT = 00; D0; = Ek=1 de:
E [ E [N]
D drop table b optimal solution table
5: Do.a = 0; Dau = Dioi Du. = Do.ji
i [ E [N]
6: for i 1,..., K do
> iterating over elements in Z iterating elements in X consider matching 2; z consider drupping æ; select the optimal action
7: for -.....,N do
8:
D Ci, + m 1,1-: Dig-1, 1
9:
DE, dj + Dij-1
10: Day min (D P,
end for
12: end for
13: M = ttraceback())
compute the optimal alignment by tracing back the minimum cost path
14: Output: DK.N M
Alternatively, when one of the sequences, i.e., Z, is known to contain only signal, we follow 0. who show that the following asymmetric matching cost is useful during representation learning:
s.j = log (Z" X/hl)i.j
(4)
where softmax1 (-) defines a standard softmax operator applied over the first tensor dimension.
Importantly, the matching cost C. does not solely dictate whether the elements T. and 2; are matched. Instead, the optimal matching is governed by (2) where the match cost Ci,j is just one of the costs affecting the optimal alignment, along with drop costs dī and dã.
3.4 Definition of drop costs
There many ways define the drop costs. As starting point, consider drop cost that is fixed constant across all elements in and Z: di = di = 8. Setting the constant 8 too low (relative to the match costs, C) will lead a high frequency of drops and thus matching only a small signal fraction. In contrast, setting s too high may result in retaining the outliers, i.c., no drops.
Percentile drop costs. To avoid such extreme outcomes, we define the drop cost per-instance basis with values comparable to those of the match cost, C. In particular, we define the drop costs as the p [0, 100] top percentile of the values contained in the cost matrix, C:
8 = Cercentile((CC, 1 S < K, S SJNNN,
(5)
Defining the drop cost as function of the top percentile match costs has the advantage that adjusting p allows to inject prior belief on the outlier rate in the input sequences.
Learnable drop costs. While injecting prior knowledge the system using the percentile drop cost can be advantageous, it may be hard to do when the expected level of noise is unknown changes from one dataset another. To address this scenario, we introduce an instantiation of a leanable drop cost here. We choose to define the outliers drop costs in X based the content of sequence Z. This realized as follows:
(6) 2, X are the respective means of sequences X, and (.) is a learnable function (i.e., feed- forward neural net) parametrized by W. This definition yield more adaptable system.
= fw. (Z); d= = fw: (X),
3.5 Drop-DTWW as a differentiable loss function
Differentiable approximation. To make the matching process differentiable, we replace the hard min operator in Alg. I with the following differentiable approximation introduced in MI:
2 2/7
(moothMin(z;g)) = -eftmmaaa((x/111
where 7 > is hyperparameter controlling trade-off between smoothness and approximation error.
5

---

Rocall 8
Drep-DTW
0
10
20
30
40
50
60
70
Percentage of noisy frames
Figure 3:
Drop-DTW for retrieval on TMNIST. We consider queries, Z. from TMNIST-parr with interspersed noise, for indexing into TMNIST-fulI. We show that Drop-DTW is more robust to interspersed noise.
Loss function. The differentiable Drop-DTW is sequence match cost suitable for representation learning (cf. []. The corresponding Drop-DTWW loss function is defined as follows:
Corw(Z, (Z, (Z, = -K.N (2, X),
(8)
where DK.v X) is the optimal match cost between and X computed in Alg.
Experiments
To demonstrate the advantages of Drop-DTW, we first present a controlled experiment using synthetic data to demonstrate the robustness of Drop-DTW (Sec. 4.1p. Next, we show the strength of Drop- DTW on various applications, including multi-step localization (Sec 4.2). representation learning from noisy videos (.3c and audio-visual alignment for retrieval and localization (Sec 4.4).
4.1 Controlled synthetic experiments
Synthetic dataset. We use the MNIST dataset (55) to generate videos of moving digits (cf. [56)). Each video in our dataset depicts single digit moving along given trajectory. For each digit- trajectory pair, we generate two videos: (i) the digit moves along the full trajectory (termed TMNIST- full) and (ii) the digit performs a random sub-part of the trajectory (termed TMNIST-part Each video frame independently encoded with a shallow ConvNet (55] trained for digit recognition. We elaborate the the dataset and the framewise embedding network in the supplemental. We use these datasets for sequence retrieval. We also show results on subsequence localization in the supplemental.
Video retrieval. In this experiment, videos in TMNIST-ful.. A correct retrieval is defined as identifying the video in TMNIST-full containing the same digit-trajectory pair as the one in the query. We use the Recall @ 1 metric to report performance. To analyze the strength of Drop-DTW in this controlled setting, we also introduce temporal noise in the query sequence by randomly blurring subset of the video frames. We compare Drop-DTTW to standard DTW 2 in this experiment. In all cases, we use the alignment score obtained from each algorithm as a matching cost between sequences. For this experiment, we use the symmetric matching costs defined in 3 Since no training is involved in this experiment, we set the drop costs to a constant, d= =
TMNIST-part as queries and look for the most similar
0.3, which we establish through cross- validation..
Figure 3 compares the performance of the two alignment algorithms with various levels of noise. As expected, DTW is very sensitive interspersed noise. contrast, Drop-DTW remains robust across the range of noise levels. Concretely, for the highest noise level in Fig. B we see that Drop-DTW is 8x better than DTW, which speaks decisively favor of Drop-DTW.
4.2 Multi-step localization
We now evaluate Drop-DTr -Top- on multi-step localization in more realistic settings. For this task, we are given as input: (i) long untrimmed video of a person performing a task (e.g., "making salad"), where the steps involved in performing the main task are interspersed with irrelevant actions (e.g.. intermittently washing dishes), and (ii) an ordered set textual descriptions of the main steps (e.g.. "cut tomatocs") in this video. The goal is to temporally localize each step in the video.

---

Datasets. For evaluation, we use the following three recent instructional video datasets: CrossTasi [.. COIN [TO,, and YouCook2 [T]. Both CrossTask and COIN include instructional videos of different activity types (i.e., tasks), with COIN being twice the size of CrossTask in the number of videos and spanning 10 times more tasks. YouCook2 is the smallest of these datasets and focuses on cooking tasks. While all datasets provide framewise labels for the start and end times of each step in a video, we take a weakly-supervised approach and only use the ordered step information.
Metrics. We evaluate the performance of Drop-DTW on step localization using three increasingly strict metrics. Recall [9] is defined as the number of steps correctly assigned to the ground truth time interval divided by the total number of steps and is the least strict metric out of the three considered. Framewise accuracy (Acc.) [TO] is defined as the ratio between the number of frames assigned the correct step label (including background) and the total number of frames. Finally, Intersection over Union (IoU) (IT) is defined as the sum of the intersections between the predicted and ground truth time intervals of each step divided by the sum of their unions. IoU the most challenging of the three metrics as it more strictly penalizes misalignments.
Training and Inference. We start from (pretrained) strong vision and language embeddings ob- tained from training on large instructional video dataset 445 We further train two-layer fully- connected network on top of the visual embeddings alone to align videos with a list of corresponding step (language) embeddings using the Drop-DTW loss, B). Notably, the number of different step descriptions in a video is orders of magnitude smaller than the number of video clips, which leads to degenerate alignments when training with an alignment loss (i.e., most clips are matched the most frequently occurring step). To regularize the training, we introduce an additional clustering loss, Letust defined in the supplemental. Lelust is an order-agnostic discriminative loss that encourages video embeddings to cluster around the embeddings of steps present in the video. Finally, we use CDTw with asymmetric costs, (4), and either 30%-percentiee drop cost, (5). or the learned variant, (6). in combination with Letuss during training.
At test time, temporarily localize each of the steps in the video, we align the learned vision and (pre-trained) language embeddings using Drop-DTWW and directly find step boundaries.
given video and the corresponding ordered list of step descriptions. To
4.2.1 Drop-DTW as loss for step localization
We now compare the performance of Drop-DTW to various alignment methods DS 5 6 previous reported results the datasets 44 following baselines:
as well as 45 471. In particular, we compare to the
SmoothDTW D: Learns fine-grained representations in contrastive setting using differentiable approximation of DTW. Drop-DTWW uses the same approximation, while supporting the ability to skip irrelevant parts of sequences.
DD [5]
Uses different diffcrentiable formulation of DTW, as well as a discriminative loss.
OTAA 6 Extends DW with the ability to handle outliers strictly present around the endpoints.
Learns strong vision and language representations by locally aligning videos and learning setting. Notably, we learn our embeddings top of representations trained with this loss on the HowTo 100M dataset [44]. There a slight difference in performance between our re-implementation and 44 which due to the difference in the input clip length and frame rate.
-II-NCEE 45
narrations using a noise contrastive loss in a
The results in Table speak decisively in favor of our approach, where we outperform all the baselines on all datasets across all the metrics with both the learned and percentile based definitions of our drop costs. Notably, although we are training a shallow fully-connected network on top of the MIL-NCE's 45 frozen pretrained visual representations. we still outperform it with sizeable margins due to the global perspective taken in aligning the two modalities. Also, note that the results of all other Daw-d methods [I
5 O are on-par due to their collective inability to handle interspersed background frames during alignment, as shown in Fig. 4 This figure also motivates the use of Drop-DTWW as the inference method for step localization. It uses the drop capability to 'label' irrelevant frames as background, without ever learning a background model, and does rather accurately according to Fig. 4 which other methods are not designed to handle.
7

---

Table 1: Step localization results the CrossTask 9 COIN
10
and YouCook2 11 datasets.
Method
Crass Tack
COIN
You YouConk2
Recall
Acc.
1oU
Recal
Acc.
loU
Recall
Acc.
IoUT
MaxMargin 44
33.6
UniVL
Non-DTW Methods
Viterbi 14
21.2
ProcNet [1
37.5
MIL-NCE 455
39.1
20.9
33.0
50.2
23.3
70.7
43.7
Smooth1) W
43.1
70.2
30.5
37.7
52.7
27.7
75.3
56.0
47.5
DaW-hased Methods
DPTW
70.4
30.6
37.9
52.8
75.3
66.4
47.1
OTAM
43.8
70.6
30.8
37.2
52.6
27.2
75.4
66.9
46.8
Drop DTW
Percentile drop
48.2
73.5
34.4
40.8
54,8
29.5
77.4
65.4
49.4
Drop-DTW + Leamned drop cost
49.1
71.3
34.5
42.8
59.6
29.5
76.8
69.6
48.4
Make Kerala Fish Curry
Ground Truth
Drop-DTW
OTAM
DTW
No action
Add onion
Add chill powder
Slir mixure
Add fish
Str curry leeves
Figure Step localization with DTW variants. Rows two four show step assignment results when the same alignment method is used for training and inference. Drop-DTW allows to identify interspersed unlabelled clips and much more closely approximates the ground truth. More examples are provided in the supplemental. 4.2.2 Drop-DTW as an inference method for step localization
Here, we further investigate the benefits of Drop-DTW (with the percentile drop cost) as an inference time algorithm for step localization. We compare to standard DTW (2) that does not allow for element dropping, OTAM 66] that allows for dropping elements around endpoints, LCSS ( that greedily excludes potential matches by thresholding the cost matrix, prior to the alignment operation, and the Needleman- Wunsch algorithm & that uses drop costs to reject outliers, but restricts the match space to one-to-one correspondences, making it impossible to match several frames to single step.
Notably, Drop-DTW does not restrict possible matches and infer the start and end times of each step directly during the alignment as our algorithm supports skipping outliers. To demonstrate the importance of performing dropping and matching within single optimal program, we also consider the naive baseline called "greedy drop DTW" that drops outliers before alignment. In this case, clip is dropped if the cost of matching it to any step is greater than the drop cost (5). Alignment is then performed on the remaining clips using standard DTW.
In all cases, use video and step embeddings extracted from pre-trained network 45 to remove the impact of training on inference performance. Table shows that Drop- outperforms all the existing methods all metries and datasets by significant margin. This is due their inability to drop interspersed outliers or their restricted space of possible matches. More interestingly, comparing Drop-DTTW "greedy drop + DTW" reveals the importance of formulating dropping and alignment together as part of the optimization, and finding the optimal solution to (2 rather than greedy one.
4.3 Drop-DTW for representation learning
In this section, we demonstrate the utility of the Drop-DTW loss, (8. for representation learning. We train the same network used in previous work [5. 1I
using the alignment proxy task PennAction 12]. Similar to previous work [15] T. we evaluate the quality of the learned representations (i.e., embeddings) on the task of video alignment using Kendall's Tau metric. Notably, the PennAction videos are tightly temporally cropped around the actions, making it suitable for an alignment based proxy task. To assess the robustness of Drop-DTW
the presence of outliers, we also contaminate PennAction sequences by randomly introducing 9% frames from other activities to each sequence. Note that this type of data transformation similar to a realistic scenario where a video of baseball game sequentially captures both baseball pitch and baseball swing actions, as well as crowd shots. For various amounts outlier frames, we contaminate PennAction videos as specified above and train a network to perform sequence alignment with the SmoothDTW 1 Drop-DTW loss. Notably, no regularization loss is needed here and the drop cost defined according to 5). Fig. demonstrates the strong performance of Drop-DTW which once again proves to be more resilient outliers.
8

---

Table 2: Comparison of different alignment algorithms for step localization the inference procedure.
first column describes alignment algorithm used for inference. The video text features used for alignment are obtained from the model
45 pre-trained on the How To100M dataset.
Cross Task
COIN
YouCook2
Method
Acc. t
IoU 1
Acc.t
loU
Acc.1
IoU f
DTW
11.2
10.1
21.6
18.3
35.0
31.1
OTAM 6
19.5
11.6
26.5
19.5
43.4
34.7
LCSS 7
50.3
4.1
47.0
4.5
43.4
9.0
Needleman- Beedleman-Wunsch
8
64.8
9.5
52.1
7.4
50.1
11.7
greedy drop + DTW
60.1
13.8
45.0
18.9
54.3
34.1
Drop-DTW (ours)
66.9
20.8
52.7
27.7
66.0
47.5
Table 3:
Unsupervised audio-visual cross-modal localization AVE [ A2V: visual localization from audio seg- ment query; V2A: audio localization from visual segment query.
Kondall Tau (KT)
60
58
Drop-aTW SmeothOTW
Model OTAM [6]
A2V
V2A f
Percentage of outtler frames
37.5
32.7
Figure:: 5: Representation learning with Drop-DTW. Video alignment results using Kendall's 's Tau metric on PennAction [22 with an increasing level of outliers introduced in training.
SmoothDTW [T
39.8
33.9
Drop-DTW (ours)
41.1
35.8
Supervised [3]
44.8
34.8
4.4 Drop-DTW for audio-visuee localization
To show the benefits of Drop-DTW for unsupervised audio-visual representation learning, we adopt the cross-modality localization task from [13]. Given trimmed signal from one modality (e.g.. audio), the goal is localize the signal in untrimmed sequence in the other modality (c.g.. visual). While previous work [[3] use supervised learning with clip-wise video annotations indicating the presence (or absence) of audio-viss visual event, train models completely unsupervised. We use margin- based loss that encourages audio-visual sequence pairs from the same video to be closer in the shared embedding space than audio-visur pairs from different videos, and measure the matching cost between the sequences with a matching algorithm. When applying Drop-DTW, we symmetric match costs, (3) and 70%-percentile drop costs, ( Otherwise, closely follow the experimental setup from [3 and adopt their encoder architecture and evaluation protocol; for additional details, please see the supplemental.
In Table 3 we compare different alignment methods used as a sequence matching cost to train the audio-visual model. We can that Drop-DTW outperforms both SmoothDTW and OTAM due to its ability to drop outliers from both sequences. Interestingly, Drop-DTW outperforms the fully-supervised baseline visual localization, given audio query. We hypothesize that this is due to our triplet loss formulation, that introduces learning signals from non mot-mai audio-visual signals, while supervised training in [13 only considers audio-visual pairs from the same video.
4.5 Discussion and limitations
Even though Drop-DTr DTW can remove arbitrary sequence elements as part the alignment process, the final alignment is still subject the monotonieity constraint, which is based the assumption that the relevant signals are strictly ordered. While not relevant for the applications presented this paper, training from partial ordered signals using Drop-DTW is not currently addressed and is interesting subject for future research.
Conclusion
In summary, we introduced an extension to the classic DTW algorithm, which relaxes the constraints of matching endpoints of paired sequences and the continuity of the path cost. This relaxation allows our method handle interspersed outliers during sequence alignment. The proposed algorithm efficiently implemented as dynamic program and naturally admits differentiable approximation. We showed that Drop-DTTW can be used both as flexible matching cost between sequences and a loss during training. Finally, we demonstrated the strengths of Drop-DTW across range of applications.

---

Acknowledgments
Nikita Dvomik is supported by the MITACS Accelerate Fellowship. Animesh Garg is a CIFAR AI Chair and is supported in part by NSERC Discovery Grants and Early career grants.
References
[1] I. Hadji, K. G. Derpanis, and A. D. Jepson, "Representation learning via global temporal aligument and cyclo-consisteney." in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
[2] H. Sakoe and Chiba, "Dynamic programming algorithm optimization spoken processing recognition," IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), vol. 26, 1978.
[3] T. Halperin, A. Ephrat, and S. Peleg, "Dynamic temporal alignment speech to lips." in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3980-39900 3984, 2019.
[4] M. Cuturi and M. Blondel, "Soft-DTW: A differentiable loss function for time-series," in International Conference on Machine Learning (ICML), 2017.
[5] C. Chang, D. Huang, Y. Sui, L. Fei-Fei, and J. C. Niebles, "D3TW: Discriminative differentiable dynamic time warping for weakly supervised action alignment and segmentation," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
[6] K. Cao, Ji, Can, C. Chang, and J. C. Niebles, "Few-shot video classification via temporal alignment," in Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2020.
[7] N. Nakatsu, Y. Kambayashi, and S. Yajima, longest common subsequence algorithm suitable for similar text strings." Acta Inf., 1982.
[8] S. B. Needleman and C. D. Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins." Journal of Molecular Biology, 1970.
[9] D. Zhukov, J.-B. Alayrac, R. G. Cinbis, D. Fouhey, I. Laptev, and J. Sivic, "Cross- task weakly supervised learning from instructional videos," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
[10] Y. Tang, D. Ding, Y. Rao. Y. Zheng, D. Zhang, L. Zhao, Lu, and J. Zhou, "COIN: A large-scale dataset for comprehensive instructional video analysis," in Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2019.
[11] I.. Zhou, C. Xu, and J. J. Corso, "Towards automatic learning of procedures from web instructional videos," in AAAI Conference on Artificial Intelligence 2018.
[12] Zhang, M. Zhu, and G. Derpanis. "From actemes to action: A strongly-superviee representation for detailed action understanding." in Proceedings of the International Conference on Computer Vision (ICCV), 2013.
[13] Y. Tian, J. Shi, B. Li, 7. Duan, and C. Xu, "Audio-visual event localization in unconstrained videos," in Proceedings of the Earopean Conference Computer Vision (ECCV), 2018.
[14] P. Sermanet, C. Lyneh, Y. Chebotar, J. Hsu, E. Jang, S. Schaal, and S. Levine, "Time-contrastive networks: self-supervised learning from video," in IEEE International Conference Robotics and Automation (ICRA), 2018
[15] D. Dwibedi, Y. Aytar, J. Tompson, P. Sermanet, and A. Zisserman, "Temporal cycle-consisteney learning," in Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
[16] X. Chang, F. Tung, and G. Mori, "Learning discriminative prototypes with dynamic time warping," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
[17] X. Cai, T. Xu, J. Yi, J. Huang, and S. Rajasckaran, "DTWNet: A dynamic time warping network," in Advances in Neural Information Processing Systems (NeurIPS),201
[18] G. A. Sigurdsson. A. Gupta, C. Schmid, A. Farhadi, and K. Alahari, "Actor and observer: Joint modeling of first and third-person person videos." in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018
10

---

[19] F. Zhou and F. Torre, "Canonical time warping for alignment of human behavior," Advances in Neurul Information Processing Systems (NeurlPS), 2009.
[20] G. Trigeorgis, M. A. Nicolaou, S. Zafeiriou, and B. W. Schuller, "Deep canonical time warping," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[21] M. Müller, Information Retrieval for for Music and Motion. Berlin, Heidelberg: Springer-Verlags 2007.
[22] Y. Sakurai, C. Faloutsos, and M. Yamamuro, "Stream monitoring under the time warping distance," in International Conference on Data Engineering (ICDE), 2007.
[23] T. Smith and M. Waterman, "Identification of common molecular suhsequences." " Journal of Molecular Biology, 1981.
[24] I. Misra, C. L. Zitnick, and M. Hebert, "Shuffle and learn: Unsupervised learning using temporal order verification," " Proceedings of the European Conference on Computer Vision (ECCV), 2016.
[25] B. Fermando, H. Bilen, E. Gavves, and S. Gould, "SSeff-suerrvieed video representation learning with odd- one-out networks," " in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
[26] H. Lee, J. Huang, M. Singh, and M. Yang, "Unsupervised representation learning by sorting sequences," in Proceedings of the International Conference on Computer Vision (ICCV), 2017.
[27] U. Büchler, B. Brattoli, and B. Ommer, "Improving spatiotemporal superviinn by deep reinforcement learning." in Proceedings of the European Conference on Computer Vision (ECCV), 2018.
[28] D. Xu, J. Xiao, Z. Zhao, J. Shao, D. Xie, and Y. Zhuang, "Seeff-supervseed spatiotemporal learning via video clip order prediction," " in Proceedings the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
[29] D. Wei, J. Lim, A. Zisserman, and W. T. Freeman, "Learning and using the arrow of time," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018
[30] J. Yu, A. W. Harley, and K. G. Derpanis, "Back to basies: Unsupervised learning of optical flow via brightness constancy and motion smoothness," in Proceedings of the European Conference Computer Vision Workshops (ECCVW), 2016.
[31] S. Mcister, J. Hur, and S. Roth, "UnFlow: Unsupervised learning of optical flow with bidirectional census loss," in AAAI Conference on Artificial Intelligence, 2018.
[32] C. Vondrick, A. Shrivastava, A. Fathi, S. Guadarrama, and K. Murphy, "Tracking emerges by colorizing videos," in Proceedings of the European Conference on Computer Vision (ECCV), 2018.
[33] J. Janai, F. Güney, A. Ranjan, M. J. Black, and A. Geiger. "Unsupervised learning of multi-frame frame optical flow with occlusions." " in Proceedings the European Conference on Computer Vision (ECCV), 2018.
[34] X. Wang and A. Gupta, "Unsupervised learning of visual representations using videos," in Proceedings of the International Conference Computer Vision (ICCV), 2015.
[35] X. Wang, A. Jabri, and A. A. Efros, "Leaming correspondence from the cycle-consistnccy of time," in Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR). 2019.
[36] A. Jabri, A. Owens, and A. A. Efros, "Space-time correspondence as a contrastive random walk." in NewrIPS, 2020.
[37] S. Benaim, A. Ephrat, Lang, I. Mosseri, W. T. Freeman, M. Rubinstein, M. Irani, and T. Dekel, "SpeedNet: Learning the speediness in videos," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[38] D. Jayaraman and K. Grauman, "Slow and steand feature analysis: Higher order temporal coherence in vidco," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[39] C. Vondrick, H. Pirsiavash, and A. Torralba, "Anticipating visual representations from unlabeled video," in Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR). 2016.
[40] J. Wang. J. Jiao, L. Bao, S. He, Y. Liu, and W. Liu, superviud spatio-tenn temporal representation learning for videos by predicting motion and appearance statistics." in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.

---

[41] T. Han, W. Xie. and A. Zisserman. "Video representation learning by dense predictive coding," in Pruceed- ings the International Conference on Computer Vision Workshops (ICCVW), 2019.
[42] A. Owens and A. A. Efros, "Audio-visual scene analysis with self-supervised multisensory features," in Proceedings of the European Conference Computer Vision (ECCV), 2018.
[43] R. Arandjelovic and A. Zisserman, "Objects that sound," in Proceedings of the Luropean Conference on Computer Vision (ECCV), 2018.
[44] A. Miech, D. Zhukov, J.-B. Alayrac, M. Tapaswi, I. Laptev, and J. Sivie, "HowTo100N, I Learning Text-Video Embedding by Watching Hundred Million Narrated Video Clips," in Proceedings of the International Conference on Computer Vision (ICCV), 2019.
[45] A. Miech, J.BB. Alayrac, L. Smaira, Laptev, J. Sivic, and Zisserman, "End-to-End Learning of Visual Representations from Uncurated Instructional Videos," Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[46] C. Sun, A. Myers, Vondrick, K. Murphy, and Schmid, "VideoBERT: joint model video and language representation learning," in Proceedings of the International Conference on Computer Vision (ICCV), 2019.
[47] Н. Luo. L. Ji, B. Shi, H. Huang. N. Duan, T. Li. J. Li, T. Bharti, and M. Zhou, "UniVL: A unified video and language pre-training model for multimodal understanding and generation." arXiv preprint MoXivv2002.00m 06353, 2020.
[48] B. G. Fabian Caba Heilbron, Victor Escorcia and J. C. Niebles, "ActivityNet: A large-scale video benchmark for human activity understanding." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
[49] M. Ma, H. Fan, and K. M. Kitani, "Going deeper into first-person activity recognition." in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016
[50] P. Nguyen, T. Liu, G. Prasad, and B. Han, "Weakly supervised action localization by sparse temporal pooling network," in Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2018.
[51] X. Nguyen, D. Ramanan, and C. Fowlkes, modeling," in Proceedings of the International Conference on Computer Vision (ICCV), 2019.
action localization with background
[52] D. Huang. L. Fei-Fei, and Niebles, "Connectionist temporal modeling weakly supervised action labeling." in Proceedings of the European Conference on Computer Vision (ECCV), 2016.
[53] L. Ding and C. Xu, sueariy-supervised action segmentation with iterative soft boundary assignment." Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR). 2018.
[54] A. Richard, H. Kuehne, A. lqbal, and Gall, "NeuralNNetork-WW -Vitebbb framework for weakly supervised video learning." in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
[55] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient-based learning applied to document recognition," Proceedings of the IEEE, 1998.
[56] N. Srivastava, E. Mansimov, and R. Salakhudinov, "Unsupervised learning of video representations using LSTMs." in International Conference on Machine Learning (ICML), 2015.
12


Reviews:
[{"review_id": "nIrHxikN-1r", "reviewer": "Reviewer_n8aa", "summary": "This paper proposed an algorithm named Drop-DTW, which enables DTW to drop outliers from the sequence-to-sequence matching. A differentiable Drop-DTW is trained for temporal step localization tasks, representation learning, audio-visual retrieval and localization. Drop-DTW gets good performance on these tasks. ", "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": "The main technical contribution of the paper is a DTW algorithm that can drop outliers. The key modification is that the cost matrix is threshold by a fixed scalar, then only low-cost points are considered in DTW. The idea is new, but there is a concurrent paper aiming at the same purpose worth some discussion [1].\n\nThe Drop-DTW is evaluated on synthetic image sequences, and the result shows that Drop-DTW can handle synthetic sequence outliers better than vanilla DTW. When trained on real instructional video datasets, the experiments show the auxiliary clustering loss is essential to get a good performance. \n\nThe clarity of the paper can be improved. Table 1 is not clear, Figure 3 can have more legends on the matrix. Some notation should be consistent.\n\nThe paper shows a modified version of DTW loss that will be useful on practical noisy data. It gets good results on downstream tasks, but from the experimental results, I think the auxiliary clustering loss is also important, which makes me think the significance of the proposed Drop-DTW is not strong.\n\n[1] Learning to Segment Actions from Visual and Language Instructions via Differentiable Weak Sequence Alignment. Shen et al.\n\n# post-rebuttal\n\nThanks for the authors' response. I read all reviews and responses. \n\nMy main concerns were 1) confusion between Drop-DTW and Drop-then-DTW and 2) effect of $L_{\\text{clust}}$. The authors have addressed these concerns in both the common response and specific response. The discussion with the reviewer VyHz clarifies the distinction between the proposed Drop-DTW and relevant prior works (MVM and Needleman-Wunch), and the authors promise to include these clarifications and revise the over-claimed core contribution.\n\nBased on these points I decided to raise my final rating. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "To improve clarity, \n\n* Table 1 needs more explanation for the right two columns ‘Drop-DTW’ and ‘drop then DTW’, maybe giving different names to differentiate these evaluation methods with the ‘Drop-DTW’ method in the bottom row? \n* The L_clust loss becomes L_reg in the supplementary material.\n\nAs shown in Algorithm 1, when using a fixed value of drop cost (i.e. d=0.3), the (non-differentiable) Drop-DTW loss is equivalent to first thresholding the cost matrix then applying DTW. But in Table 1, there is a clear gap between the ‘Drop-DTW’ column and ‘drop then DTW’ column. Could you point out the reason?\n\nThe experiments show the effect of clustering loss is great on natural datasets. Maybe consider introducing the auxiliary clustering loss as one of the contributions as well. \n", "review_text": "", "extra_scores": {"ethical_concerns": "There is no major ethical concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ggZAX4xgGa", "reviewer": "Reviewer_wLu7", "summary": "The paper presents a variant of DTW, denoted as Drop-DTW.  The author introduce drop costs, which is a criteria for deciding whether or not to ignore frames in times series. By ignoring some frames in input times series, the alignment performance between times series containing non-corresponding frames can be improved. They also propose a differentiable version using the softmin function for use as a loss function. Several experiments (e.g., video retrieval, weakly supervised action labeling, and representation learning) demonstrate the superiority of the proposed method over existing method.", "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": "# After Rebuttal\n\nFirst, I would like to thank the authors for their detailed rebuttal and discussion, including additional experiments.\n\nMy main concern was that the idea of incorporating the drop technique into DP is very common in the bioinformatics field. \nIn response to the concern, the authors have shown the difference in performance with NW by additional experiments. In addition, the deep discussions with reviewer VyHz showed that the \"one-to-many matching\" of DTW has an important role in their task.\nI think that their propose i.e.,  incorporating the drop technique into DTW has some values for our community, although the idea of drop+DP is quite common.\nI have slightly increased my score to reflect this.\n\n# Initial Review\n\n## Pros.\n1. In actual tasks e.g., weakly supervised action labeling and video alignment, there are many frames that do not correspond. The authors propose a reasonable solution to the problem by introducing the drop costs in the DP of the DTW.\n1.  Various experiments demonstrate the superiority of the proposed method.\n\n## Cons.\n1. The drop cost itself is very common in the field of bioinformatics, while the paper does not mention it.  The major algorithms (e.g., Needleman-Wunsch[1] and Smith-Waterman[2]) and some minors (e.g., differentiable variant [3]) seem to be very related to this work. I would like the authors to clarify the relationship.\n1. The drop costs are set to various values in the experiments, and some of them (Sec. 4.1.1) seem to be fixed without the percentile contrary to the claim in Sec. 3.3. I would like the authors to clarify how these values were determined. It would be even better if the impact of drop costs on performance could be investigated.\n    - On a related note, please clarify the criteria for dropping in \"drop then DTW\" setting. Is it possible to achieve similar performance to drop-DTW, if we carefully set the drop criteria?\n\n\n## Comments\n\n1. I think Eq.6 should be $\\text{smoothMin}(x; \\gamma) = x \\cdot \\text{softmin}(x/\\gamma) = \\frac{x \\cdot e^{-x/\\gamma}}{\\sum e^{-x/\\gamma}}$ or $\\text{smoothMax}(x; \\gamma)=...$. \n1. I could not find $\\mathcal L_\\text{clust}$ in the supplementary. $\\mathcal L_\\text{reg} = \\mathcal L_\\text{clust}$?\n    - If so, does Table 1 show that \"attention-based pooling\" without time series information ($\\mathcal L_\\text{clust}$ in the table) is better than the vanilla Drop-DTW? Why?\n    - (minor): This regularization seems to be related to canonical time warping[4] and deep canonical time warping[5].\n    - Are there any hyperparameters for $\\mathcal L_\\text{clust}$? (i.e., the total loss is $\\mathcal L_\\text{DTW} + \\lambda \\mathcal L_\\text{clust}, \\text{where}\\  \\lambda=1$)?\n1. If the drop cost is determined by the percentile of the match costs (depending on the inputs), strictly speaking, it may not be called \"fully differentiable\".\n1. I could not find any info on licenses and computational resources in the supplementary, contrary to the checklists.\n\n\n## References\n- [1] S. Needleman and C. Wunsch. A general method applicable to the search for similarities in the amino acidsequence of two proteins.Journal of Molecular Biology, 48(3):443–453, 3 1970\n- [2] T. F. Smith and M. S. Waterman. Identification of common molecular subsequences.Journal of molecularbiology, 147(1):195–7, Mar. 1981\n- [3] Koide, Satoshi, Keisuke Kawano, and Takuro Kutsuna. \"Neural edit operations for biological sequences.\" Advances in Neural Information Processing Systems 31 (2018): 4960-4970.\n- [4] Zhou, Feng, and Fernando Torre. \"Canonical time warping for alignment of human behavior.\" Advances in neural information processing systems 22 (2009): 2286-2294. \n- [5] Trigeorgis, George, et al. \"Deep canonical time warping.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation is clarified in the main text.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "9Yj3ZoSpq3f", "reviewer": "Reviewer_6MvG", "summary": "I really enjoyed reading this paper. It was very well written and positioned against existing works, and the technical aspects explained clearly. I have a few concerns but overall it would make for an excellent inclusion into the NeurIPS program.\n\nThe paper addresses the problem of aligning two contiguous temporal sequences, e.g., an untrimmed video and a given activity to match. Unlike previous approaches that make use of dynamic time warping to align the sequences, this paper proposes to model and remove outliers from the matching process. This could be done as a two-stage process: first find and remove outlier elements and then, second, apply dynamic time warping to the remaining sub-sequences. Rather than doing this the paper formulates a joint objective that aligns inliers (enforcing the monotonicity constraint) while allowing outliers to not be matched (i.e., not incur a mismatch penalty).\n\nThe approach is differentiable and is used as the loss function of a deep learning model. Experiments show that the method outperforms previous approaches on some standard tasks. In particular it does better than the two-stage baseline of first removing outliers and then matching as two disjoint steps.", "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": "As mentioned above the paper is very well written. While reading the introduction I was slightly confused thinking that the paper was proposing a two-stage solution rather than a joint (modified DTW) objective (see lines 37--41). However, later it is clear that the detection and removal of outliers is integrated into a single objective, which is then made differentiable.\n\nRegarding the latter, I was not completely convinced that the min operator needs to be approximated by smoothMin in Eqn. 6 for the DTW loss function to be differentiable (or at least subdifferentiable). Could the (exact) min not be retained and a subgradient computed for the optimal assignment? This would be faster and remove one hyperparameter from consideration.\n\nMy other bigger concern relates to the sensitivity of the trade-off between the \"drop costs\" and matching costs. It seems that if these are not carefully set then the model could learn that all elements are outliers and produce a trivial M^\\star = 0 solution, or not as extreme but equally problematic prefer very short sequences where matching scores are very high. This doesn't appear to have been a problem in the solutions, but I'd like the authors to still comment on whether its a potential issue that may bias the solutions. Specifically, how sensitive are the results to the choice of s in Eqn. 3? Moreover, the choice of d^x and d^z in Section 4.1.1 does not follow the same rule for assigning drop costs.\n\nOverall the paper makes a strong contribution. Clarification (ablation analysis) on the above-mentioned concerns would help to strengthen the paper even further.\n\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7YFn7CxE98", "reviewer": "Reviewer_VyHZ", "summary": "Paper proposes an approach for a sequence-to-sequence alignment specifically designed to handle sequences with outliers. The core of the approach is a simple extension to the DTW where \"no match\" is allowed and carries a certain cost. The standard DTW can then solve for the matching path, while selecting outliers (elements matched to \"no match\" token). This DTW variant is converted into a loss by following for mutation in [Hadji et al] and then shown on a number of tasks where it performs well.  ", "questions": "", "limitations": "", "rating": 5, "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": "The paper is well written and is easy to follow (though some details are relegated to supplemental materials which makes the flow a bit disjointed at times). The results are also competitive and compelling. \n\nThe real issue is the novelty. The approach relies heavily on [Hadji et al]. The core technical novelty is the extension of DTW to allow outlier dropping. However, this is not really novel. Authors claim that prior DTW variants \"enforce correspondences between all elements of both sequences\", a limitation that the paper is trying to solve. While this is indeed the most typical setup of DTW, other variants exist that do not require such assumptions. For example, subsequence variant of the DTW algorithm which allows partial matching also exists (e.g., see Meinard Muller. Information Retrieval for Music and Motion. Springer Verlag, 2007. or description of LCSS in https://www.cs.unm.edu/~mueen/DTW.pdf). As such the novelty of the approach is fairly marginal. In the very least, the paper should discuss and compare against such variants. \n\nI think the presented approach is useful and has not been illustrated in the context of problems being considered. But the novelty, in my opinion, is clearly below what one would expect from a NeurIPS paper. I think the paper maybe better suited for a lower-tier venue. \n\nMinor comments:\n- \"One of the main downsides of extant DTW-based approaches is that they require clean, tightly cropped, data with matching endpoints.\" This is not true of all DTW approaches. There are specific variants that do not require matching endpoints. Further, some do deal with noisy observation (e.g., Generalized Canonical Time Warping) at least in the feature space. \n\n- For Experiments in Figure 3, how do you explain higher performance of Drop-DTW at 0 noise? \n\n- For Experiments in Figure 3, do you assume that amount of noise is know for each operating point? Alternatively, how is the drop cost set? This doesn't seem to be discussed. \n\n--- Post Rebuttal ---\n\nIn light of the lengthy discussion with the authors, I am raising my score. This new score is a compromise between three factors: (a) acknowledging that I now do believe the approach has fundamental merits and the new experimental results provided in the discussion are highly valuable and illustrative, (b) the novelty, while I no longer perceive as marginal, is still moderate; and (c) the **very** significant amount of work and revisions necessary (in my opinion) to be carried out by the authors for the camera ready. Hence, while I no longer believe the work is unacceptable for publication at NeurIPS, and would go along with the acceptance decision, I also cannot bring myself to strongly argue for the acceptance itself, largely due to (c). As such, I am effectively converging to a Borderline-ish rating and will continue to engage in discussions with other Reviewers and AE to arrive at a final collective decision.  \n\nOn a personal note, I do want to thank the authors for engaging in a continued and valuable discussion. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, no negative impacts need to be considered. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There has been extensive discussion between the reviewers and authors in the post-rebuttal period to tease apart the novel contributions of this paper and accurately position it wrt prior work.

The authors have committed to repositioning the paper, clarifying the contributions, and thoroughly discussing close prior works in their final version.
Decision: Accept (Poster)