Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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].

The 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. 

The 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.

The 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.

[1] Learning to Segment Actions from Visual and Language Instructions via Differentiable Weak Sequence Alignment. Shen et al.

# post-rebuttal

Thanks for the authors' response. I read all reviews and responses. 

My 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.

Based on these points I decided to raise my final rating. 


limitations_and_societal_impact: To improve clarity, 

* 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? 
* The L_clust loss becomes L_reg in the supplementary material.

As 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?

The 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.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.  
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. 

The 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. 

I 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. 

Minor comments:
- "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. 

- For Experiments in Figure 3, how do you explain higher performance of Drop-DTW at 0 noise? 

- 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. 

--- Post Rebuttal ---

In 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.  

On a personal note, I do want to thank the authors for engaging in a continued and valuable discussion. 
limitations_and_societal_impact: Yes, no negative impacts need to be considered.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

The 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).

The 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.
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.

Regarding 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.

My 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.

Overall the paper makes a strong contribution. Clarification (ablation analysis) on the above-mentioned concerns would help to strengthen the paper even further.

 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: # After Rebuttal

First, I would like to thank the authors for their detailed rebuttal and discussion, including additional experiments.

My main concern was that the idea of incorporating the drop technique into DP is very common in the bioinformatics field. 
In 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.
I 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.
I have slightly increased my score to reflect this.

# Initial Review

## Pros.
1. 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.
1.  Various experiments demonstrate the superiority of the proposed method.

## Cons.
1. 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.
1. 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.
    - 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?


## Comments

1. 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)=...$. 
1. I could not find $\mathcal L_\text{clust}$ in the supplementary. $\mathcal L_\text{reg} = \mathcal L_\text{clust}$?
    - 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?
    - (minor): This regularization seems to be related to canonical time warping[4] and deep canonical time warping[5].
    - 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$)?
1. 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".
1. I could not find any info on licenses and computational resources in the supplementary, contrary to the checklists.


## References
- [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
- [2] T. F. Smith and M. S. Waterman. Identification of common molecular subsequences.Journal of molecularbiology, 147(1):195–7, Mar. 1981
- [3] Koide, Satoshi, Keisuke Kawano, and Takuro Kutsuna. "Neural edit operations for biological sequences." Advances in Neural Information Processing Systems 31 (2018): 4960-4970.
- [4] Zhou, Feng, and Fernando Torre. "Canonical time warping for alignment of human behavior." Advances in neural information processing systems 22 (2009): 2286-2294. 
- [5] Trigeorgis, George, et al. "Deep canonical time warping." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.
limitations_and_societal_impact: The limitation is clarified in the main text.
review_title: null

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)