Multi-granularity Correspondence Learning from Long-term Noisy Videos
Authors: Yijie Lin
Jie Zhang
Zhenyu Huang
Jia Liu
zujie wen
Xi Peng
Venue: ICLR 2024 oral (2024)
Keywords: Video-language pre-training
Noisy correspondence
Primary area: representation learning for computer vision, audio, language, and other modalities

Abstract: Existing video-language studies mainly focus on learning short video clips, leaving long-term temporal dependencies rarely explored due to over-high computational cost of modeling long videos. To address this issue, one feasible solution is learning the correspondence between video clips and captions, which however inevitably encounters the multi-granularity noisy correspondence (MNC) problem. To be specific, MNC refers to the clip-caption misalignment (coarse-grained) and frame-word misalignment (fine-grained), hindering temporal learning and video understanding. In this paper, we propose NOise Robust Temporal Optimal traNsport (Norton) that addresses MNC in a unified optimal transport (OT) framework. In brief, Norton employs video-paragraph and clip-caption contrastive losses to capture long-term dependencies based on OT. To address coarse-grained misalignment in video-paragraph contrast, Norton filters out the irrelevant clips and captions through an alignable prompt bucket and realigns asynchronous clip-caption pairs based on transport distance. To address the fine-grained misalignment, Norton incorporates a soft-maximum operator to identify crucial words and key frames. Additionally, Norton exploits the potential faulty negative samples in clip-caption contrast by rectifying the alignment target with OT assignment to ensure precise temporal modeling. Extensive experiments on video retrieval, videoQA, and action segmentation verify the effectiveness of our method. 
Code is available at https://lin-yijie.github.io/projects/Norton.

Published as a conference paper at ICLR 2024
MULTI-GRANULARITY CORRESPONDENCE LEARNING FROM LONG-TERM NOISY VIDEOS
Yijie Lin'
Jie Zhang Zhenyu Huang'
Jia Liu'
Zujie Wen
Xi Peng
"iihhuan University BBejjing University of Posts and Telecommunications Dalian University of Technology flinyijie.oo pengx. Lengx.gme@gmee emm.gmmmllmmmmmmm com
ABSTRACT
Existing video-language studies mainly focus on learning short video clips, leav- ing long-term temporal dependencies rarely explored due to over-high computa- tional cost of modeling long videos. To address this issue, one feasible solution is learning the correspondence between video clips and captions, which however in- evitably encounters the multi-grane qulti-granularity noisy correspondence (MNC) problem. To be specific, MNC refers to the clip-caption misalignment (coarse-grained) and frame-word misalignment (fine (ine-grained), hindering temporal learning and video understanding. this paper, we propose NOise Robust Temporal Optimal traNs- port (Norton) that addresses MNC in unified optimal transport (OT) framework. brief, Norton employs video-paragen paraggapa and clip-caption contrastive losses to capture long-ter song-term dependencies based on OT. To address noarse-graing misalign- ment in aadeo-paragraph contrast, Norton filters out the irrelevant clips and cap- tions through alignable prompt bucket and realigns asynchronous clip-caption pairs based on transport distance. To address the fine-grained misalignment, Norton incorporates soft- offt-maximum operator identify erucial words and key frames. Additionally, Norton exploits the potential faulty negative samples in clip- caption contrast by rectifying the alignment target with OT assignment to ensure precise temporal modeling. Extensive experiments on video retrieval, videoQA. and action segmentation verify the effectiveness of our method. Code available at
INTRODUCTION
Video-Language Pre-training (VLP) has emerged as a popular approach for video understand- ing (Miech et al., 2020; Bain al., 2021: Ge al., 2022; Wang et al., 2022c; Luo al., 2020) in recent years. Although promising results have been achieved, the pioneer works are mainly de- voted learning short video clips while overlooking long-term temporal dependencies. In practice, it is generally acknowledged that the long-term temporal dependency plays an indispensable role understanding the relationships and transitions over time various applications such as video- paragraph retrieval (Yang et al., 2023b; Sun et al., 2022) and action segmentation (Tang et al., 2019).
To learn the long-term temporal correspondence from the long videos, one important challenge the heavy demand for computation resources. For example, Han et al. (2022); Bertasius et al. (2021) employ long-form vision transformers to capture the temporal correlation, which involves comput- typically composed of
ing tross-attention among every frame in long videos. As long videos a sequence of short video clips according to ASR timestamps (Miech et al., 2020), an alternative approach is to explore the temporal correlation among video clips and captions. For instance, Tem- PCLR (Yang et al., 2023b) uses Dynamic Time Warping (Müller, 2007; Cuturi & Blondel, 2017; Zhou & Torre, 2009) to measure the sequential distance between video clips and captions, and in- corporates the temporal correlation across clips by contrasting the video with the paragraph. This strategy is remarkably efficient than directly modeling the entire video, making attractive option for learning long-term temporal correspondence.
However, dividing long videos into short clips would inevitably introduce an accompanied chal- lenge, i.e., multi- granularity noisy correspondence (MNC). As shown in Fig. 1, MNC refers to the
"Corresponding author.

---

Published as a conference paper at ICLR 2024
Clip
Cuara-grained Asynchmunous
Fine- Fine-graneed Misalignment
Caption
brven and jusc gitty nogiashh
fors cunsay brunch:
suges sporis suger
and wathh
lake ell the sugar
pastry
Coars--grained
grained Inslovant
Irrelevant
2:25
2447
425
521 5.27
5:34
Figure 1: Our observation on multi guntiigramullarity noisy correspondence (MNC) in video understand- ing. (Left) The green timeline denotes the alignable captions while the red timeline indicates the unalignable captions. The green text in i; denotes partially correlated words w.r. V5- (Right) The dashed line represents the original alignment according to timestamps and the red block indicates the misaligned clip-caption pair. The green block denotes the ground-truthh alignment. The solid line denotes the re-alignment by Dynamic Time Warping (Müller, 2007) which struggles to handle noisy correspondence well.
misaligned video-text pairs at two different granularities: i) Coarse- prrsse-graied misalignuent (Clip- caption). -gainerr misalignment includes asynchronous and irrelevant misalignments ac- cording to whether a clip//capioo is alignable with the captions/clips in the long video. To be specific, asynchronous misalignment refers to temporal misalignment between subtitles and visual clips, e,g. ti in Fig. 1. It often occurs when people explain their actions before after actually performing them, resulting in the mismatch between the order of statements and actions. On the other hand, irrelevant misalignment refers to irrelevant meaningless captions that cannot be aligned with any available video clips (e.g.. t2 and t. in Fig. 1), and vice versa for video clips. According to Han et al. (2022), only 30% of clip-caption pairs are visually aligned in How To 10M (Miech et al., 2019), with even fewer 15% being naturally well-aligned; ii) Fine-grained misalignment (Frame-word). Within each video clip, the narration sentences may only partially correlate with the visual frames. As de- picted in Fig. 1. "the sugar goes on top" in t5 is strongly correlated with visual content v;, while the action "watch the glaze take off" is uncorrelated. Irrelevant words or frames can distort the identi- fication of crucial ones and result in inaccurate similarity measurements, further contaminating the clip-caption alignment. Note that only a few methods (Han et al., 2022) consider the coarse coarse-grained misalignment problem in temporal learning while none of them realize this fine-grained misalign- ment problem. Undoubtedly, MNC poses a significant obstacle to effective temporal modeling.
To this end, we propose NOise Robust Temporal Optimal traNsport (Norton), unified optimal trans- port approach for addressing multi-granularity noisy correspondence in temporal learning. Specifi- cally, Norton proposes iido-paraggaph and clip-caption contrastive loss based on optimal trans- port (OT) to explore the temporal correlations.
In video- pardgrap contrast, Norton employs OT to measure sequence distances between video clips and captions from a fine-to-coarse perspective. To handle fine- line-grained misalignment, Norton incor- porates token-wise soft-maximun operator to identify crucial words and key frames within each clip-caption pair. This operator improves the measurement of clip-caption similarity from fine- grained multi-modal interactions. Building upon this clip-caption similarity, Norton establishes flexible assignment between clips and captions by maximizing the global alignment similarity of OT. Based on the transport assignment, Norton realigns each video clip to multiple related captions, and vice versa, thereby mitigating the asynchronous misalignment. To further address the irrelevant misalignment, Norton introduces an alignable prompt bucket which serves as a candidate alignable target for noisy clips or captions. By discarding the ones aligned to the bucket, Norton effectively filters out meaningless content during the OT process. Note that our late interaction between clips and captions through OT alleviates the computational cost of directly modeling long videos.
In clip-caption contrast, Norton tackles the faulty negative problem (Chuang et al., 2020; Yang et al., 2021b) through OT. Specifically, semantically similar clip and captions would be wrongly treated as negatives in contrastive learning (Chen et al., 2020; Lin et al., 2021; 2022; Liu et al., 2022a) and impact the clip-wise representation. Norton leverages OT assignments of within-bar batch clip-caption pairs as additional supervision in clip-caption contrastive loss, which exploits potential faulty negative samples and improves temporal learning.
2

---

Published as a conference paper at ICLR 2024
The main contributions of this work summarized below:
We reveal multi multi-granularity noisy correspondence problem in temporal learning, which refers to coarse- coarse-grained grained asynchronous and irrelevant misaligaments, as well as fine-grained misalignment.
We achieve efficient and robust correspondence learning by incorporating several innovative com- ponents such as the soft-maximum operator, alignable prompt bucket, and faulty negative exploita- tion within the optimal transport framework. Extensive experiments various tasks including video retrieval, videoQA, and action segmentation verify its effectiveness.
RELATED WORK
Video Temporal Learning. Temporal learning is a critical yet challenging topic in video under- standing. Traditional works focus on integrating spatial-temporal operations into convolution (Fe- ichtenhofer et al., 2019) or Transformer architectures (Bertasius et al., 2021: Wang et al., 2023; Sun et al., 2022). Inspired by image-language pre-training approaches (Radford et al., 2021; Jia et al,, 2021), recent works leverage natural language to guide video temporal learning. Among these works, one scheme is "sorting the clips" (7ellers al., 2021; Zeng et al., 2023a;h; Ma et al., 2023) which involves ranking the video clips according to their sequential sentences. While effective, this framework generally requires encoding long video into one sequence and entails significant com- putational resources. Another type of scheme proposes to leverage Dynamic Time Warping (Yang al., 2023b; Müller, 2007: Dvornik et al., 2021) measure the sequence distance between video clips and captions, and achieve temporal learning by aligning the video with the corresponding paragraph.
Although promising results have been achieved, existing temporal learning methods suffer from the noisy correspondence problem where the ground truth order of captions w.r.t. video clips does not conform to the original timestamp order. This issue can significantly impact temporal learning, leading to suboptimal results for sorting-based and DTW-based approaches. Different from these works, this paper is dedicated solving noisy correspondence in temporal learning and accordingly proposes an MNC-robust optimal transport framework that effectively measures sequence similarity between noisy video and paragraph.
Noisy Correspondence Learning in Video-language Pre-training. Video-languas pre-training has achieved promising progress thanks large-scale datasets such How Tow00000M (Miech al., 2019). As the text description is often not well-aligned to the visual content (Han et al., 2022), noisy correspondence learning (Huang et al., 2021; Gao et al., 2021) becomes new fashion in VI.P. To be specific, MIL-NCE (Miech et al., 2020) first studies this problem by simply aligning each video clip with multiple adjacent sentences to mitigate the impact noise. TAN (Han et al., 2022) proposes a co-training strategy that uses mutual agreement to filter out the noisy pairs. Different from the above on-the-fly fly noise rectified methods, Decembert (Tang et al., 2021) generates high-quality video descriptions using an off the--hehlff image captioning model from a data collection aspect.
Our method differs from existing works in two key aspects. First, the above noisy correspondence methods only consider coarse-grained asynchrony while ignoring the frame-word misalignment problem. In contrast, we point out that fine- fine-grained misalignment can impact temporal learning and accordingly propose unified optimal transport approach that effectively addresses noisy corre- spondence at both coarse and fine-grained levels. Second, our method is computationally efficient with low memory cost, It operates in bootstrapping manner without requiring additional models, e.g., dual networks (Han et al., 2022), momentum networks (Li et al., 2021; Han et al., 2022), or image caption models (Tang et al., 2021). These advantages make our approach more practical and scalable for real-world applications.
Optimal Transport. OT is originally proposed to depict the distance between two probability dis- tributions. Recently. OT has gained significant attention in various fields such as domain adapta- tion (Xu et al., 2020), clustering (Caron et al., 2020), document matching (Yu et al., 2022; Kusner al., 2015), and sequence alignment (Su & Hua, 2017; Liu et al., 2022b). However, none of these works specifically focus on the alignment of video and text, which is the primary focus of our re- search. In addition to addressing the traditional sequence alignment, we point out the fine-grained misalignment problem that is specific to video-text learning. Experimental results show that the proposed multi- graiie-r alignment effectively improves temporal learning.
3

---

Published as a conference paper at ICLR 2024
Fine-grained Aligoment
Coarse-grained Aligoment
Video-paragraph Contrastive Learning
Captions
UrW
R Sul Tj
Video ciis
Optinal
Transport
Wordh (orth
2.Maaan
Sinkhom
Distance Q Su:
T,
Captions
Frangs (42)
Alignable Prompt Bucket
Transport Assignment Q'
Words 44
Figure 2: Overview of our multi-granularity correspondence learning. We perform video-paragrape paragraph contrastive learning capture long-term temporal correlations from fine-to-coarse perspective. Specifically, we first utilize the log-sum-exp operator the frame-word similarity matrix to ob- tain gre-ggrineed similarity between clip and caption. Additionally, we append an alignable prompt bucket the clip-caption similarity matrix to filter out the irrelevant clips or captions. By apply- ing Sinkhorn iterations on the clip-caption similarity matrix, we effectively tackle the asynchronous problem and obtain the optimal transport distance the video- pareoopa similarity.
METHOD
In this section, we first introduce overall pre-training objective of Norton in Section 3.1. Subse- quently, we elaborate how to exploit the faulty negative samples clip-caption contrastive learning in Section 3.3.
multi-granularig correspondence learning in Section 3.2 and explain
3.1 PRE-TNAINING OBJECTIVE
Given instructional video dataset ( where V; and T, represent the video and paragraph of i-th instance, we formulate each vireo/paragraph as a sequence of video clips/captions according the ASR timestamps. Specifically, we mark the video clips and captions in i-th video as (va (Va)==1 and [ta]m Here {v:) and [t]]}= represent the frames and words within va and to where and w represent the length of the clip and caption. Based the above definitions, propose the following training objectives:
(1) where video- paragraph contrastive loss Lvideo explores the temporal correlations between the long video V; and its corresponding paragraph through a novel noise robust temporal optimal trans- port distance. The clip-caption contrastive loss Letip exploits potential faulty negative samples to improve clip representation and ensure accurate temporal modeling. We will elaborate on these two losses in the following sections.
C ALvidco
3.2 CORRESPONDENCE LEARNING VIA ROBUST OPTIMAL TRANSPORT
As long videos are typically composed of a sequence of short video clips, we propose to use the optimal transport distance between video clips and captions as the similarity criterion for video- paragraph contrastive learning a robust and efficient way.
Let S E 2 denote the clip-caption similarity matrix where [S]a, measures the similarity be- tween clip and caption t, Q _ denotes the corresponding transport assignment where [Qla, represents the probabilities of aligning Va with t.. Optimal transport seeks to establish a flexible alignment between clips and captions by maximizing global similarity (Q, = tr (QT)) S). Formally, the objective of optimal transport is defined as follows:
max QE
(Q, S) (Q)
s.t.
I puxm
Q1m = μ4, n. Q 13.
where 1,, represents the vector of ones in dimension m, μ R and E T indicate the rela- tive importance of each clip or caption. Since each clip or caption is sampled independently. we choose uniform probability distribution μ = ! 1, and Iim assign equal weight to each

---

Published as a conference paper at ICLR 2024
instance following Su & Hua (2017). (Q) is entropy regularizer derived from the optimization perspective (Cuturi, 2013) and E controls its smoothness.
As illustrated in Eq. (2), optimal transport can realign each clip caption to multiple related cap- tions or clips based on global similarity, thus effectively resolving the potential asynchronous mis- alignment problem between the two modalities. The optimal Q" of Eq. (2) has a simple normalized exponential matrix solution by Sinkhorn fixed point iterations (Cuturi, 2013),
Q' (iag(()) exp (S/e) Diag(k2),
(3)
with iteratively updated Ki n./ (exp (S/e)
f v./ (exp (S /E) KI),
where Ki E IR" Kig I' are the non-negative left and right scaling vectors. By utilizing OT dis-
tance between clips and captions as the vidco- paraeorpp similarity, our aadeo-aarggrah contrastive loss captures the long-tern temporal dependencies as follows,
.V.
exp (Qi, St)/T) + log j==1 exp (Qij. S,y)/T)
exp exp ((Qni Sk)/T) Σ exp (QQj. Syi)/T)
videe Σ
log
(4)
where Sij E IR is the clip-caption similarity matrix between video V; and paragraph T,, Quj is the corresponding transport assignment of Sty. and is a learnable temperature initialized as 0.07. Note that when calculating Eq. (4), we stop the gradient of the transport assignment Q to keep the stability of our video-pan partoo-p contrastive loss. To ensure the discriminative capacity of the model, we search the nearest videos as the hard negative samples following Xu et al. (2021). By using optimal transport to measure sequence distance instead of directly modeling the long videos, our method significantly reduces computational cost. A detailed training efficiency discussion is placed in Appendix C.
However, the optimal transport objective Eq. (2) still has some limitations: i) OT estimates the misalign- problem unexplored; ii) OT requires each source instance must exactly map to the targets, which is not practical when dealing with a large amount of meaningless text. To address these challenges, we propose soft-maximum operator for fine- -re-grained alignment and an alignment prompt bucket to filter out meaningless clips and captions for noise robust distance estimation.
sequence distance based on clip-caption similarity ccoarse-grainett leaving ment
Fine-grained Alignment. Most previous works (Xu al., 2021; Yang et al., 2023b; Han et al., 2022) typically encode frames or words to a global feature using [CL.S] token or averaging the frame or word embeddings (e.g., AvgPool( (v: [v j===)) )). However, such strategies neglect fine-gra ine-grained in- teractions between modalities and do not address the problem of frame-word misalignment.
To address this issue, we propose cross-modal late interaction mechanism to identify crucial words and key frames for fine-grained alignment inspired by Yao al. (2022); Wang et al. (2022b). Specif- ically, we define the fine-grained similarity between clip va and caption to follows:
)) (5)
1 S)abb 2
Σ ar log
Σ exp
to
ar log
exp
v
a
W
Take the front part for example, for each frame in the video clip, we identify the most impor- lant words through soft-maximum operation, i.e., log-sum-exp approximation (Beck & Teboulle, 2012), and then compute the average moft-maximum similarities of all frames shown in Fig. 2. Similarly, for each textual token, we also find its related video frames in the latter part of Eq. (5). The parameter a magnifies the importance of the most relevant words or frames. As a approaches the log-sum-exp approximates the maximum. Specifically, this soft-maximum operation allows us to reduce the negative influence of background words or frames on clip-caption similarity estimation.
Though inspired from Wang et al. (2022b); Yao et al. (2022), our method differs in several aspects. Firstly, we introduce a straightforward log-sum-exp operator as a soft approximation of the maxi- mum. This allows us to concentrate video content as opposed to images. Experiments in Table 7 demonstrate that our design yields a substantial improvement compared to solely focusing the most important item. Secondly, leverage the estimated clip-caption similarity for sequence alignment, effectively enhancing tempo- ral learning. In contrast, Wang et al. (2022b) exclusively concentrates clip-caption alignment.
more crucial words, making it particularly well-suited for
5

---

Published as a conference paper at ICLR 2024
Alignable Prompt Bucket. Optimal transport requires every source instance to exactly map to the targets. Yet, in real-world scenarios, a sigmificant amount of captions and video clips might be noisy irrelevant that cannot be aligned, Le., coarse-grainee irrelevant misalignments. Motivated by Sarlin et al. (2020), we propose an innovative solution that uses an alignable prompt bucket (APB) to filter out semantic irrelevant clips and captions. As shown in Fig. 2, the prompt bucket consists of one new row and column, filled with the same value p. The prompt bucket is appended the similarity matrix S that
[ [S] [S] 1m p, [S]a, [S]a,o, Va [L, 6 [1. (6)
When calculating the transport distance given S, each video clip be aligned with either available captions or the prompt bucket. Substituting Eq. (2) with Eq. (6), we obtain the final optimal transport
assignment by dropping the last row and column of the transport assignment, ie.. Q' 1am
From an intuitional viewpoint, the prompt value in Eq. (6) serves as a similarity margin that distinguishes between alignable and unalignable clips and captions. If video clip v. lacks an alignable caption, its pairwise similarities with the set of captions {to) are generally small. Consequently, the margin p is larger than these pairwise similarity values, Va is forced to align with the prompt bucket and subsequently filtered from the transport assignment. In our implementation, we determine the value of p as the bottom 30% similarity of the original aligned clip-caption pairs in data-driven manner.
3.3 CLIP-CAPTION ALIGNMENT VIA FAULTY NEGATIVE EXPLOITATION
Since self-supervised contrastive learning (He et al., 2020) relies on the random sampling of neg- ative instances, captions that are semantically similar to the anchor clips can be treated faulty negatives (Han et al., 2020; Zolfaghari et al., 2021), and vice versa. However, the existing one-hot target used in contrastive learning penalizes all negative predictions regardless of their correlations.
To mitigate this issue, we propose to exploit the faulty negatives through optimal transport. Let E BxB denotes the within- batch clip-caption similarity matrix where B represents the number of clips/captions for all videos in the batch. We apply optimal transport on the similarity matrix S,
max (Q. S) + (Q) s.t. ê - {- E QEO
1 1 1B. Q1 BxR Q1g = B
B 1
(7)
where the transport assignment Q attempts to realign the clips with similar captions (i.e., faulty negatives). After implementing the Sinkhorn algorithm described in Eq. (3), utilize the clip-wise realigned targets Q' as additional supervision for contrastive learning,
exp((S),,/7 Celip Σ [T), log Et (S., ==1
exp(1S),. /T) T -T- BQ"
log 5 6 exp( (8)),
(8)
where B is a weighted parameter that balances the identity target I and realigned targets Q By replacing identity matrix 1g with estimated soft-alignment probabilities, the model can recalibrate the attractive and repulsive forces between clips and captions. Specifically, the entire training batch is treated as a support set (Patrick et al., 2021) with a subset of relevant clips and captions. Our method enables the detection and correction of potential faulty negatives within the set.
EXPERIMENTS
We verify the effectiveness of Norton in comprehending both long and short videos across range of downstream tasks. Additionally, we perform extensive ablation studies to analyze the impact of different design choices on the model's performance. For comprehensive training details, training efficiency results, and additional experiments please refer to the Appendix.
4.1 COMPARISONS ON VIDEO-PARAGRAPH RETRIEVAL
As the main contribution of this work lies in long-term temporal learning, we first evaluate method on the video- video-paragrapl retrieval task. The objective of this task is to accurately find the corresponding video using of sentence queries that describe different parts of the long video.

---

Published as a conference paper at ICLR 2024
Video-parees parea-pargg retrieval on YouCookII (Background Removed). The best and second-best re- sults are bold and underlined, respectively.
Table 1:
Table 2: Video-paragrapp retrieval on YouCookll (Background Kept).
Approach
Measure
R@1
R@5
R
Approach
R@1
R@5
R@
MIL-NCE (Miech et al., 2020)
Cap. Avg.
43.1
68.6
79.1
Cap. Avg.
HT100M (Miech et al., 2019)
Cap. Avg.
46.6
74.3
83.7
VideoCLII
73.6
94.7
98.4
MCN (Chen et al., 2021)
Cap. Avg.
53.4
75.0
81.4
TempCLR
71.7
94.5
97.9
VidcoCLIP (Xu al., 2021)
Cap. Avg. 74.5
94.5
97.9
Norton (Ours)
74.8
94.7
98.4
TempCLR (Yang et al., 2023b)
Cap. Avg.
74.5
94.6
97.0
DTW
Norton (Ours)
Cap. Avg.
75.5
95.0
97.7
VideoCI.I IIP
55.7
93.1
98.9
VideoCLIP (Xu et al., 2021)
DTW
56.0
89.9
96.3
TempCLR
70.4
93.8
97.9
TempCIR R (Yang et al., 2023b)
DTW
83.5
97.2
99.3
Norton (Ours)
76.1
95.0
97.7
Norton (Ours)
DTW
88.7
98.8
99.5
OTAM
VideoCLIP (Xu et al., 2021)
OTAM
52,8
89.2
95.0
VideoCLIP
56.6
92.8
98.9
TempCIR (Yang et al., 2023b)
OTAM
84.9
97.9
99.3
TempCTR
72.2
94.5
97.7
Norton (Ours)
OTAM
88.9
98.4
99.5
Norton (Ours)
73.6
94.7
97.7
Setup and Metric. We evaluate the zero-shot performance of our method in two different set- tings, namely, Background Removed and Background Kept. The former setting discards the text- uncorrelated video clips based on the timestamps, while the latter uses the full video. As times- lamps may not always be available, paragraph retrieval with background is a more realistic scenario. To provide a comprehensive evaluation, we employ three standard strategies, namely, Cap. Avg. (Caption Average), DTW, and OTAM (Ordered Temporal Alignment Module (Cao et al., 2020)). Specifically, Cap. Avg. matches one clip for each caption and retrieves the video with the most matched clips. DTW and OTAM calculate the sequence distance by accumulating the clip-caption distance based on chronological order. We report recall metrics R@I 1, R@5, and R@ 10 for all se- tups. Specifically, R@ indicates how often the correct prediction is the first result, which is highly desirable in many applications, while R @ 10 provides wider scope and may be less critical as users typically focus on the top few results in practical scenarios.
Datasets. We conduct the evaluation YouCookII (Zhou al., 2018) where the testing data consists of 436 videos with 3,350 clip-caption pairs in total. The videos existing in YouCookII have been removed from Howto 100M (Miech et al., 2019) following the same protocol as previous works (Miech et al., 2020; Xu et al., 2021; Yang et al., 2023b).
Results. i) Background Removed: As shown in Table 1, TempCLR (Yang al., 2023b) performs remarkably better than VideoCLIP (Xu et al., 2021) in terms of DTW and OTAM, as it is trained to explore the global temporal context. However, all these methods suffer from noisy correspon- dence in the temporal alignment. In contrast, our proposed robust optimal transport framework explicitly overcomes multi-granularity noisy correspondence. Specifically, our method effectively improves the performance of all measurements by large margin (+ 1% Cap. Avg.. 5.2% DTW, and 4% OTAM in terms of R @ 1), indicating that our method learns better temporal information. ii Background Kept: As shown in Table 2, compared with the Background Removed results, the recall of all methods dropped as the irrelevant information in the background can distract the video features. Nevertheless, our proposed method consistently outperformed VideoCLIP and TempCLR, even under such challenging conditions.
4.2 EVALUATION ON DIVERSE DOWNSTREAM TASKS
To verify the generalization of our method, we conduct experiments on three downstream tasks with four datasets described below.
Texteto-Video retrieval (clip level). This task aims to find a corresponding video clip given a query caption. We use YouCookII (Zhou et al., 2018) and MSR-VTT (Xu et al., 2016) to evaluate the transferability of our method. MSR-VTT (Xu et al., 2016) is a well-known retrieval benchmark containing 10,000 short videos with 20 captions each. Following Xu et al. (2021), utilize the 1,000 clip-caption test pairs for evaluation. For YouCookII, we use 3,350 clip-caption pairs as introduced in Section 4.1.
7

---

Published as a conference paper at ICLR 2024
As shown in Table 3, method achieves remarkable improvement state-of-the methods on YouCooklI. On MSR-VTT (Table 5), our method shows solid improvements especially about 1.9% R@5 and 1.6% R@ 10 zero-shot improvement compared with VideoCLIP. After fine-tuning, our method still reaches state-of-the-art R @@1, 1. Here we include SupportSet (Patrick et al., 2021) and Frozen (Bain et al., 2021) for completeness, while they different pre-training data such 65 million Instagram videos (Ghadiyaram et al., 2019), 2.5 million WebVid videos (Bain et al., 2021) and 3 million Google Conceptual Captions (Sharma et al., 2018). The results in this clip-caption retrieval experiment indicate that our method not only improves the global temporal information (long video retrieval as shown in Section 4. 4.1), but also facilitates clip-level representation learning.
Table 3: Clip-caption retrieval on YouCookII.
Table 4: Action segmentation on COIN.
Approach
Feature
R@ R@5
R@ 10
Frame
Approach
ActBERT (Zhu & Yang, 2020)
R101+Res3D
9.6 26.7
38.0
Accuracy
MIL-NCE (Miech ct al., 2020)
S3D-G
15.1 38.0
51.2
VAVA (Liu et al., 2022b)
47.3
MCN (Chen et al., 2021)
R15++RX101
18.1 35.5
45.2
ActBERT (Zhu & Yang. 2020)
57.0
TACo (Yang ct al., 2021a)
S3D-G
19.9 43.2
55.7
Drop-DTW (Dvormik ct al., 2021)
()
59.6
VT-TWINS (Ko al., 2022)
S3D-G
9.7 27.0
38.8
MIL-NCE (Miech et al., 2020)
61.0
MMFT (Shvetsova al., 2022)
S3D-G
19.8 42.9
55.1
ClipBERT (Lei et al., 2021)
65.4
TAN (Han et al., 2022)
S3D-G
20.1 45.5
59.5
TACo (Yang al., 2021a)
68.4
VideoCIIIP (Xu et al., 2021)
S3D-G
22.7 50.4
63.1
VideoCLIP (Xu et al., 2021)
68.7
TempCLR (Yang et al., 2023b)
S3D-G
23.3 51.0
64.5
TempCLR (Yang et al., 2023b)
68.7
Norton (Ours)
S3D-G
24.2
51.9
64.1
Norton (Ours)
69.8
Table 5: Text-to-video retrieval on MSR-VTV
Table 6: VideoQA on MSR-VTT.
Superivsed
R@1
R@5
RΦ 10
Superivsed
Accuracy
SupportSet (Patrick et al., 2021)
30.1
58.5
69.3
ElTanque (Kaufman et al., 2017)
65.5
Frozen (Bain al., 2021)
31.0
59.5
70.5
MLB(Kim al., 2016)
76.1
MMFT (Shvetsova et al., 2022)
23.7
52.1
63.7
JSFusion (Yu al., 2018)
83.4
VidcoCLIP (Xu et al., 2021)
30.9
55.4
66.8
TempCLR (Yang ct al., 2023b)
30.6
55.1
65.5
ActBERT (Zhu & Yang, 2020)
85.7
Norton (Ours)
31.2
55.7
66.8
ClipBERT (Lei et al., 2021)
88.2
Zero-shot
R@1
R@5
R@
MERLOT (Zellers al., 2021)
90.9
SupportSet (Patrick et al., 2021)
8.7
23.0
31.1
VideoCLIP (Xu et al., 2021)
92.1
Frozen (Bain et al., 2021)
23.2
44.6
56.6
TempCLR (Yang et al., 2023b)
92.2
MIL-NCE (Miech al., 2020)
9.9
24.0
32.4
Norton (Ours)
92.7
MMFT (Shvetsova et al., 2022)
24.0
32.6
Zero-shot
Accuracy
VT-TWINS (Ko et al., 2022)
9.4
23.4
31.6
VideoCIIP (Xu et al., 2021)
10.4
22.2
30.0
VideoCLIP (Xu et al., 2021)
73.9
TempCI. (Yang et al., 2023b)
10.1
22.2
29.4
TempCLR (Yang et al., 2023b)
74.4
Norton (Ours)
10.7
24.1
31.6
Norton (Ours)
77.1
VideoQA. We conduct the multiple choice VideoQA experiment on MSR- VTT (Yu et al., 2018). Given video query and some candidate textual answers (5 average), the task is to find the one that fits the query out of possible candidates. As shown Table 6, our method outperforms the counterparts with +2.7% in terms of zero-shot accuracy and achieves 0.5% improvements after finetuning, showing the superiority of our method.
Action Segmentation. This task assumes that each video associated with various actions. The goal is to determine the specific action for each second, which requires fully exploring the temporal dependencies. We use the long video dataset COIN (Tang et al., 2019) to evaluate the action segmen- tation performance of our method. COIN contains 11,827 videos (476 hours) in total where each video labeled with 3.91 action segments on average, according to 778 candidate segment labels. Following Xu et al. (2021), to classify the action label. We report the frame-wiss wise accuracy using the evaluation protocol of Xu al. (2021); ) Miech et al. (2020). As shown in Table 4, our method outperforms all baselines.
apply one-layer classification head on top of the visual encoder
8

---

Published as a conference paper at ICLR 2024
Table 7: Ablation experiments evaluated on YouCooklI, where "Clip" is short for clip-caption retrieval, "Video" for video-pane paragraph retrieval, "B" for video backgrounds, and "FNE" for faulty negative exploitation. We report the DTW measurement for video- rideo-paragraph retrieval.
Basic Setting
Clip
Video (w/o B)
Video (w B)
Model
FNE
Soft-max
APB p R@
R@1 1
R@5
R@1
R@5
VideoCLIP (Xu al., 2021)
22.7
50.4
56.0
89.9
55.7
93.1
TempCLR (Yang et al., 2023b)
23.3
51.0
83.5
97.2
70.4
93.8
(w/o Locko)
56.7
89.0
91.8
(wfo Lvide))
23.4
50.8
63.3
93.3
65.1
92.4
C
Mean average Yao et al., 2022)
23.1
50.1
84.2
97.3
74.3
94.7
23.5
50.5
86.9
98.6
74.1
94.6
0.1
23.8
51.7
88.1
98.6
74.2
94.7
0,2
24.0
51.8
88.2
98.6
74.9
94.4
24.0
88.4
98.8
75.2
94.7
H
/
10%
24.2
51.8
88.4
98.8
75.9
94.9
I
/
50%
24.2
51.9
88.4
98.6
75.9
94.9
J (Norton)
30%
24.2
51.9
88.7
98.8
76.1
95.0
4.3 ABLATION STUDY ON THE PROPOSED METHODS
In this section, we investigate the effects of our design choices and discuss the results in Table 7.
Effect of Faulty Negative Exploitation. In model-(A,B): we tackle the issue of faulty negatives in clip-caption contrastive learning through the correction of optimal transport. This strategy not only improves the performance of clip-caption retrieval but also enhances the temporal ability.
Effeet of OT in Temporal Learning. In model-C, utilize vanilla optimal transport measure the distance between sequences where the clip/caption representation obtained by averaging the frame/word embeddings. As shown, model-C achieves comparable performance to TempCLR and even outperforms TempCLR in retrieval tasks involving backgrounds.
Effect of Fine-grained Alignment. In (D..F.( we investigate the effect of fine fine-graines grained alignment by varying the weight of the ong-sum-ent approximation. We also compare our approach with Yao et al. (2022) which selects the most important token for fine-grained alignment. The comparison demonstrates that our strategy outperforms Yao et al. (2022), supporting our claim that focusing on more crucial words/frames yields better fine-graines measurements in video under- standing. When the weight tends towards O, the log-sum-exp approximation approximates the maximum, resulting in the selection of the most relevant words/frames. The comparison between (oFeI-(E,F..) shows that larger leads to better performance, further validating assumption that focusing on more important tokens would enhance performance.
Effeet of Alignable Prompt Bucket. In model- (H.JJ,, we integrate the prompt bucket into the optimal transport framework and vary the value of p to be the bottom 10%, 30%. and 50% similarity between the original aligned clips and captions. We observe that the use of APB results in clear performance improvement for video-paue paragraph retrieval with background, and setting the value of the bottom 30% similarity an effective choice.
CONCLUSION
Learning temporal correlations long-form videos is prohibitively expensive in terms of the hard- ware required. To address this, we propose Norton, noise robust temporal optimal transport to es- timate the sequence distance that can be easily extended and scaled to larger datasets with minimal computational cost. Notably, our unified optimal transport solution resolves the noisy correspon- dence problem at both frame-word and clip-caption levels. Extensive experiments demonstrate that method not only captures long-term temporal dependencies but also facilitates clip-level repre- sentation learning. the future, we plan to extend our method to address noisy correspondence for more modalities videos typically include visual, textual, and audio content.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by NSFC under Grant U21B2040, 62176171; and in part by the Fundamental Research Funds for the Central Universities under Grant CJ202303.
REFERENCES
Max Bain, Arsha Nagrani, Gül Varol, and Andrew Zisserman. Frozen in time: joint video and image encoder for end-to-end retrieval. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pp. 1728-1738, 2021.
Amir Beck and Marc Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557-580, 2012.
Gedas Bertasius, Heng Wang, and Lorenzo Torresani. Is space-time attention all you need for video understanding? In International Conference on Machine Learning, volume 2, pp. 4, 2021.
Kaidi Cao, Jingwei Ji, Zhangjie Cao, Chien-Yi Chang, and Juan Carlos Niebles. Few-shot video classification via temporal alignment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10618-1062) 2020.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems, 33:9912-99244 2020.
Brian Chen, Andrew Rouditchenko, Kevin Duarte, Hilde Kuehne, Samuel Thomas, Angie Boggust, Rameswar Panda, Brian Kingsbury, Rogerio Feris, David Harwath, et al. Multimodal clustering networks for self-supervised learning from unlabeled videos. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5012-8021, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International Conference on Machine Learning. pp. 1597-1607. PMLR, 2020.
Ching- Yao Chuang, Joshua Robinson, Yen-Cher Lin, Antonio Torralba, and Stefanic Jegelka. De- biased contrastive learning. Advances in Neural Information Processing Systems, 33:8765-8775, 2020.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26, 2013.
Marco Cuturi and Mathieu Blondel. Soft-dtw: a differentiable loss function for time-series. In International Conference Machine Learning, pp. 894 PMLR, 2017.
Jacob Devlin, Ming-Was Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800. 2018.
Mikita Dvorikk Isma Hadji, Konstantinos G Derpanis, Animesh Garg, and Allan Jepson. Drop- dtw: Aligning common signal between sequences while dropping outliers. Advances in Neural Information Processing Systems, 34:13782-13799, 2021.
Christoph Feichtenhofer, Haoqi Fan, Jitendra Malik, and Kaiming He. Slowfast networks for video recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 0202-6211, 2019.
Zijian Gao, Jingyu Liu, Weiqi Sun, Sheng Chen, Dedan Chang, and Lili Zhao. Clip2tv: Align, match and distill for video-text retrieval. arXiv preprint arXiv:2111.05611 2021.
Yuying Ge, Yixiao Ge, Xihui Liu, Dian Li, Ying Shan, Xiaohu Qie, and Ping Luo. Bridging video- text retrieval with multiple choice questions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16167-16176, 2022.
10

---

Published as a conference paper at ICLR 2024
Deepti Ghadiyaram, Du Tran, and Dhruv Mahajan. Large-scale supervisu pre-training for video action recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12046-12055, 2019.
Haochen Han, Kaiyao Miao, Qinghua Zheng, and Minnan Luo. Noisy correspondence learning with meta similarity correction. In Proceedings of the IEEE/CVF Conference on Compuler Vision and Puttern Recognition, pp. 7517-7526, 2023.
Tengda Han, Weidi Xie, and Andrew Zisserman. Self-supervised co-training for video representa- tion learning. Advances in Neural Information Processing Systems, 33:5679-5690, 2020.
Tengda Han, Weidi Xie, and Andrew Zisserman. Temporal alignment network for long-term video. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2022.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2020.
Zhenyu Huang, Guocheng Niu, Xiao Liu, Wenbiao Ding, Xinyan Xiao, Hua Wu, and Xi Peng- Learning with noisy correspondence for cross modal matching. Advances in Neural Information Processing Systems, 34:29406-299 29419, 2021.
Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoe Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and vision-language representation learning with noisy text supervision. In International Conference on Machine Learning, pp. 4904-4916. PMLR, 2021.
Dotan Kaufman, Gil Levi, Tal Hassner, and Lior Wolf. Temporal tessellation: A unified approach for video analysis. Proceedings of the IEEE International Conference on Computer Vision, pp- 94-104, 2017.
Jin-Hwa Kim, Kyoung- Syoung-Woon Woon On, Woosang Lim, Jeonghee Kim, Jung- Woo Ha, and Byoung-Tee Tak Zhang. Hadamard product for low-rank bilinear pooling. arXiv preprint arXiv: 1610.0435,, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.688 69800, 2014.
Dohwan Ko, Joonmyung Choi, Juyeon Ko, Shinyeong Noh, Kyoung-Wan Woon On, Fun-Sol Kim, and Hyunwoo J Kim. Video-text representation learning via differentiable weak temporal alignment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5016-5025, 2022.
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document distances. In International Conference on Machine Learning, pp. 957-966. PMLR, 2015.
Jie Lei, Linjie Li, Luowei Zhou, Zhe Gan, Tamara L Berg, Mohit Bansal, and Jingjing Liu. Less is more: Clipbert for iideo-and-languag learning via sparse sampling. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7331-7341, 2021.
Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi. Align before fuse: Vision and language representation learning with momentum distillation. Advances in Neural Information Processing Systems, 34:9694-9705, 2021.
Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. Blip: Bootstrapping language-image pre- training for unified languaee understanding and generation. In International Conference on Machine Learning, pp. 12888-12960 PMLR, 2022.
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. Blip-2: Bootstrapping language- image pre-training with frozen image encoders and large language models. arXiv preprint arXiv:2301. 12597, 2023.
Xuelong Li. Positive-inncetivee noise. IEEE Transactions on Neural Networks and Learning Systems, 2022.
11

---

Published as a conference paper at ICLR 2024
Yijie Lin, Yuanbiao Gou, Zitao Liu, Boyun Li, Jiancheng Lv, and Xi Peng. Completer: Incomplete multi-view clustering via contrastive prediction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11174-11183, 2021.
Yijie Lin, Yuanbiao Gou, Xiaotian Liu, Jinfeng Bai, Jiancheng Lv, and Xi Peng. Dual contrastive prediction for incomplete multi-view representation learning. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence, pp. 1-14, 2022. doi: 10.1 00.1199/PAMM..222..11999
Yijie Lin, Mouxing Yang, Jun Yu, Peng Hu, Changqing Zhang, and Xi Peng. Graph matching with bi-level noisy correspondence. In Proceedings the IEEE/CVF International Conference Computer Vision, pp. 13362-233777 2023.
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. arXiv preprint arXiv:2304.0844 2023.
Junhong Liu, Yijie Lin, Liang Jiang, Jia Liu, Zujie Wen, and Xi Peng. Improve interpretability of neural networks via sparse contrastive coding. In Findings of the Association for Computational Linguistics: EMNLP 2022, 2022a.
Weizhe Liu, Bugra Tekin, Huseyin Coskun, Vibhav Vineet, Pascal Fua, and Mare Pollefeys. Learn- ing to align sequential actions in the wild. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 2181-2191, 2022b.
Huaishao Luo, Lei Ji, Botian Shi, Haoyang Huang, Nan Duan, Tianrui Li, Jason Li, Taroon Bharti, and Ming Zhou. Univl: unified video and language pre-training model for multimodal under- standing and generation. arXiv preprint arXiv:2002.06353, 2020.
Fan Ma, Xiaojie Jin, Heng Wang, Jingjia Huang, Linchao Zhu, Jiashi Feng, and Yi Yang. Temporal perceiving video-language pre-training. arXiv preprint arXiv:2301.07465 2023.
Antoine Miech, Dimitri Zhukov, Jean- Caan-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivie. Howtol00m: Learning a text-video embedding by watching hundred million narrated video clips. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 2630-2640, 2019.
Antoine Miech, lean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisser- man. End-to-end learning of visual representations from uncurated instructional videos. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition, pp. 9879- 9889, 2020.
Meinard Müller. Dynamic time warping. Information retrieval for music and motion, pp. 69-84, 2007.
OpenAl. Gpt-4 technical report. 2023.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances Neural Information Processing Systems, pp- 2019.
Mandela Patrick, Yao Huang, Yuki Asano, Florian Metze, Alexander Hauptmann, Joao Hen- riques, and Andrea Vedaldi. Support-set bottlenecks for video-text representation learning. In Proceedings of the International Conference on Learning Representations, 2021.
Yang Qin, Dezhong Peng, Xi Peng. Xu Wang, and Peng Hu. Deep evidential learning with noisy cor- respondence for cross-modal retrieval. In Proceedings of the 30th ACM International Conference on Multimedia, pp. 9948-4956, 2022.
Yang Qin, Yuan Sun, Dezhong Peng. Joey Tianyi Zhou, Xi Peng, and Peng Hu. Cross-modal active complementary learning with self-refining correspondence. In Advances in Neural Information Processing Systems, 2023.
12

---

Published as a conference paper at ICLR 2024
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748-8763. PMLR, 2021.
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Proceedings of the IEEE/CVE Confer- ence on Computer Vision and Pattern Recognition, pp. 1998-49417 2020.
Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. Conceptual captions: A cleaned, hypemymed, image alt-text dataset for automatic image captioning. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics, pp. 2556-2565, 2018.
Nina Shvetsova, Brian Chen, Andrew Rouditchenko, Samuel Thomas, Brian Kingsbury, Rogerio S Feris, David Harwath, James Glass, and Hilde Kuehne. Everything at once-multi once-multi-moda fusion transformer for video retrieval. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 20020-20022 2022.
Bing Su and Gang Hua. Order-preserving wasserstein distance for sequence matching. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1049-1057, 2017.
Yuchong Sun, Hongwei Xue, Ruihua Song, Bei Liu, Huan Yang, and Jianlong Fu. Long-form video-language pre-training with multimodal temporal contrastive learning. Advances in Neural Information Processing Systems, 2022.
Yansong Tang, Dajun Ding, Yongming Rao, Yu Zheng, Danyang Zhang, Lili Zhao, Jiwen Lu, and Jie Zhou, Coin: large-scale dataset for comprehensive instructional video analysis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1207-1216, 2019.
Zineng Tang, Jie Lei, and Mohit Bansal. Decembert: Learning from noisy instructional videos via dense captions and entropy minimization. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2415-2426, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Informa- fion Processing Systems, 30, 2017.
Alex Jinpeng Wang, Yixiao Ge, Rui Yan, Yuying Ge, Xudong Lin, Guanyu Cai, Jianping Wu, Ying Shan, Xiaohu Qie, and Mike Zheng Shou. All one: Exploring unified video-language pre- training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- lion, 2023.
Haobo Wang, Mingxuan Xia, Yixuan Li, Yuren Mao, Lei Feng, Gang Chen, and Junbo Zhao. Solar: Sinkhorn label refinery for imbalanced partial-label learning. arXiv preprint arXiv:2209. 2022a.
Qiang Wang, Yanhao Zhang, Yun Zheng, Pan Pan, and Xian-Sheng Hua. Disentangled representa- tion learning for text-video retrieval. arXiv preprint arXiv:2203.07111, 2022b.
Zixu Wang, Yujie Zhong, Yishu Miao, Lin Ma. and Lucia Specia. Contrastive video-language learning with fine-grained frame sampling. arXiv preprint arXiv:2210.05039, 2022c
Hu Xu, Gargi Ghosh, Po- Yao Huang, Dmytro Okhonko, Armen Aghajanyan, Florian Metze, Luke Zettlemoyer, and Christoph Feichtenhofer. Videoclip: Contrastive pre-training for zero-shot video-text understanding. In Proceedings of the 2021 Conference on Empirical Methods in Nat- ural Language Processing, pp. 6787-6800, 2021.
Jun Xu, Tao Mei, Ting Yao, and Yong Rui. Msr-vtt: A large video description dataset for bridging video and language. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2288-5296. 2016.
13

---

Published as a conference paper at ICLR 2024
Renjun Xu, Pelen Liu, Liyan Wang, Chao Chen, and Jindong Wang. Reliable weighted optimal transport for unsupervised domain adaptation. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp.
2020.
Jianwei Yang, Yonatan Bisk, and Jianfeng Gao. Taco: Token-aware cascade contrastive learning for video-text alignment. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1 11522-11572, 2021a. la.
Mouxing Yang, Yunfan Li, Zhenyu Huang, Zitao Liu, Peng Hu, and Xi Peng. Partially view-aligned representation learning with noise-robust contrastive loss. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 1134-1143, 2021b.
Mouxing Yang, Zhenyu Huang, Peng Hu, Taihao Li, Jiancheng Lv, and Xi Peng. Learning with twin noisy labels for visible-infrared person re-identification. In Proceedingy of the IEEF/CVF conference on computer vision and pattern recognition, pp. 14308-14317, 2022.
Mouxing Yang, Yunfan Li, Zhang Changging, Peng Hu, and Xi Peng. Test-time adaption against multi-modal reliability bias. In Proceedings of the International Conference Learning Repre- sentations, May 2024.
Shuo Yang, Zhaopan Xu, Kai Wang. Yang You, Hongxun Yao, Tongliang Liu, and Min Xu. Biero: Noisy correspondence rectification for multi-modality data via bi-directional cross-modal simi- larity consistency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 19892, 2023a.
Yuncong Yang. Jiawei Ma, Shiyuan Huang, Long Chen, Xudong Lin, Guangxing Han, and Shih-Fu Chang. Tempeir: Temporal alignment representation with contrastive learning. In Proceedings of the International Conference on Learning Representations, 2023b.
Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu. Filip: Fine-grained interactive language-image Proceedings of the International Conference on Learning Representations, 2022.
image pre-training. In
Weijie Yu, Liang Pang, Jun Xu, Bing Su, Zhenhua Dong, and Ji-Rong Wen. Optimal partial trans- port based sentence selection for long-form document matching. In Proceedings of the 29th International Conference on Computational Linguistics, pp. 2363-2373, 2022.
Youngjae Yu, Jongseok Kim, and Gunhee Kim. A joint sequence fusion model for video question answering and retrieval. In Proceedings of the European Conference Computer Vision, pp. 471-487, 2018
Rowan Zellers, Ximing Lu, Jack Hessel, Youngjae Yu, Jae Sung Park, Jize Cao, Ali Farhadi, and Yejin Choi. Merlot: Multimodal neural script knowledge models. Advances in Neural Information Processing Systems, 34:23634-2366 126511, 2021.
Ziyun Zeng, Yixiao Ge, Zhan Tong, Xihui Liu, Shu-Tao Xia, and Ying Shan. Tvtsv2: Learning out-of-the-box spatiotemporal visual representations at scale. arXiv preprint arXiv:230. 2023a.
Ziyun Zeng, Yuying Ge, Xihui Liu, Bin Chen, Ping Luo, Shu-Tao Xia, and Yixiao Ge. Learning transferable spatiotemporal representations from natural script knowledge. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023b.
Feng Zhou and Fernando Torre. Canonical time warping for alignment of human behavior. Advances in Neural Information Processing Systems, 22, 2009.
Luowei Zhou, Chenliang Xu, and Jason Corso. Towards automatic learning of procedures from web instructional videos. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Linchao Zhu and Yi Yang. Actbert: Learning global-local video-text representations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8746-8755, 2020.
Mohammadreza Zolfaghari, Yi Zhu, Peter Gehler, and Thomas Brox. Crosselr: Cross-modal con- trastive learning for multi-modal video representations. In Proceedings of the IEEE/CVF Inter- national Conference Computer Vision, pp. 1450-1459, 2021.
14

---

Published as a conference paper at ICLR 2024
APPENDIX
In this supplementary material, we present:
1. Full details of pre-training (Section A)
2. Derivation of the Sinkhorn-Knopp iteration for optimal transport (Section B)
Training efficiency discussion (Section C)
4. Experiments on noisy correspondence analysis (Section D)
5. Applications and potential implications (Section E)
Challenges in future works (Section F)
Visualization of re-alignment by Dynamic Time Warping and Optimal Transport (Section G)
A DETAILS OF PRE-TRAINING
Following mainstream VLP works (Miech al., 2020; Xu al., 2021; Yang al., 2023b; Han al., 2022), we use the instructional videos HowToo000 (Miech et al., 2019) for pre-training. Below, we provide an overview of the network architecture, data sampling, and training setting.
Architecture. We adopt dual Transformer encoders (Devlin et al., 2018) for processing video clips and captions, separately. Specifically, the video encoder consists 6-layer Transformer, while the text encoder consists of 12-layer Transformer. For each video clip, use HowTo100M pre- trained S3D (Miech et al., 2020) to extract one video token per second at 30 fps. For each text, we obtain word tokens via embedding lookup in BERT (Devlin et al., 2018). The video tokens and text tokens are then separately passed through the video and text Transformer encoders to obtain frame and word representations, respectively. As the quality of the representations plays a crucial role in temporal learning, we initialize our network with VideoCLIP checkpoint (Xu et al., 2021) due to limited computation resources, following the same setting of TempCLR (Yang et al., 2023b). Experimental results demonstrate that our method significantly improves VideoCLII'ss performance on various long and short video tasks, with only GPU day post-training.
Data sampling. We follow the sampling strategy of VideoCLIP (Xu al., 2021) as below:
1. Sample text caption with 8 ~ 32 tokens by merging the timestamps of the raw captions. This is done because sampling a video clip first may not have corresponding caption nearby;
2. Sample timestamp within the boundary of the caption as the center for video clip;
3. Grow video clip with random duration (3 16 seconds) from this center timestamp.
We sample 16 clips/captions from each Ho 100M video and form the long video sequence with consecutive 8 clips/captions. The batch size is set to 64 videos, resulting in 128 (64x 16/8) //8) video sequences in total for rideo-paragraph contrastive learning in mini-batch.
Training setting, We implement our method in PyTorch 1.11.0 (Paszke et al., 2019) and conduct all experiments the Red Hat 6.4.0-1 OS. We train the network for 10 epochs with fp16 precision, which takes approximately 1 A100 GPU day. We use Adam optimizer (Kingma & Ba, 2014) with the learning rate of 15 optimize the network. Each training batch consisted of 64 videos, each paired with 16 corresponding clips and captions. We set the balanced weight À between clip and video loss to 0. The log-sum-exy parameter a and the faulty negative exploitation B are set and 0.3, respectively. We run 50 steps of the Sinkhorn algorithm and set the entropy to 0.1 and for calculating the optimal transport in Lvidco and Leip- respectively.
To compute clip-caption loss Lelip. derive clip and caption representations through average pool- ing on the token embeddings of frames and words, respectively. For aadeo-paaagrah loss Lvisss enhance the average pooling similarity by incorporating the proposed fine-grat fine-grained similarity measure. For downstream tasks such as retrieval and QA, we maintain computational efficiency by averaging the embeddings of frames and words as the clip and caption representations, respectively.
15

---

Published as a conference paper at ICLR 2024
B DERIVATION OF THE SINKHORN-KNOPH ITERATION
In this section, we briefly introduce the derivation of the Sinkhorn algorithm (Cuturi, 2013) for calculating the optimal transport distance. Given the similarity matrix S _=*= where [S]a.b measures the similarity between video clip Ya and caption b. optimal transport aims to maximize the expectation of the global similarity through.
max QE
(Q, S) tr
()
Σ> 6=1b=1
Q Q
[S]a,b
s.t.
{
R nx
QQm= - Q =
where probability vectors μl, v denote the amount of mass that could transport from v to t (Wang et al., 2022a). If each clip in video V caption in paragraph T is sampled independently from distribution, the weights can be set equally, i.e., = 1,,, and v = 1=11 1m-
m
Note that Eq. (9) is standard linear programming problem and can be solved in polynomial time (around O log n)). However, considering the high volume of data points, common linear pro- gramming solvers be time-consuming. To overcome this limitation, Cuturi (2013) investigates fast approximation version of this optimization by adding an entropy regularization term,
max QE
(Q. S) + (H)
(10)
where - I log[Q]a. is derived from an optimization perspective and makes the objective function smoothing and convex, allowing for efficient computation. Let L(Q, u, v) be the Lagrangian of Eq. (10) with dual multipliers u E R" v E R"
C(Q, u. v) () - =H((Q) + u (QL -1) + T 1, -))
(11)
Since the original optimization problem is convex, the solution must satisfy the Karush-Kuu Kuhn-Kuhnhhae- Tucker (KKT) conditions. Therefore, by taking the partial derivative of the Lagrangian in (q.(1) with respect to [Q]a. we obtain the following equation:
AC(Q, u. aQQ,B
[S].,b (log ((Q)a,)) + +) + ua - 2b =
(12)
For any couple (a, b),
19a.b (0C/O(Q)a.) = 1Qa.6 1b.b- - e e 3+
(13)
Therefore, solving Eq. (10) equals to finding the dual multipliers u and v, which is also equivalent to get another two scaling coefficients vectors H1 R", K2, E F such that,
[11] = "y and [K2]
(14)
These scaling coefficients are used to compute the optimal transport matrix Q as a normalized exponential matrix form,
Q Diag(Rn) exp (S/e) Diag(K2).
(15)
Recall Q" meets the constraints in Eq. (9) that,
Q' imm Diag(R1) exp (S/=) K2 μt Q* Diag(R2) exp (S (ST k²
(16)
which gives rise to alternative coordinate descent algorithm, known the Sinkhorn-Knope Knopp fixed point iteration (Cuturi, 2013), that updates the scaling coefficients as follows:
K1 + /./ (exp (S/E) K2). K2 - v./ (exp (ST /s) k1).
(17)
Empirically, rumning 50 steps is often sufficient to obtain satisfactory alignment result. Finally, we get optimal transport distance through (Q",S).
16

---

Published as a conference paper at ICLR 2024
Table 8: Training time per epoch. 'f' denotes the sampled frame for a video clip. We use the time cost of clip-caption contrastive learning (Line 1) as the base value for comparison in the third column. The default setting is marked gray.
Line
Approach
Time Cost
Clip-caption Contrast (16f)
87 min (x 1.000)
2
+ Faulty Negative Exploitation
92 min (x 1.0077
3
Video-paragraph Contrast (16fx8)
142 min (x 1x62))
4
aen-ggranedd mot-mmaxiumm Operator (161x8)
146 min (x 1.678)
Clip-caption Contrast (32f)
172 min (x1,977)
6
Sinkhorn iteration in Lolp
2.4 min (x0.027)
7
Sinkhorn iteration in Liiden
2.6 min (x0.029)
C TRAINING EFFICIENCY DISCUSSION
Most existing temporal learning methods (Han et al., 2022; Zeng al., 2023b) directly model long videos using the video Transformer encoder. However, the complexity of the Transformer (Devlin al., 2018; Vaswani et al., 2017) is approximately ( where / is the number of the video frames. Consequently, these methods require significant computational resources to model lengthy videos. In contrast, our approach utilizes optimal transport to estimate the sequence distance between short video clips and captions in a late fusion manner, thereby alleviating the need to encode entire long videos. Although the complexity of the Sinkhorn algorithm directly proportional the number of video clips, captions, and Sinkhorn iterations, this late computation is negligible compared to the computation of the deep network.
Table 8 presents the training time for different settings on a single A100 GPU. "16f" indicates that we sample video clips up to 16 seconds. "'"fx8" denotes that we employ OT to measure the distance between 8 clips and 8 captions, resulting in a sequence length increase to 128. For contrastive learning in Lines 1 and 5, we average the token embeddings of frames/words as the clip/caption representation following Xu et al. (2021). As shown, the proposed faulty negative exploitation (Line 2) and fine-grand fine-grained operator (Line 4) only require a small amount time compared with Lines and 3. This is because our fine-gras men-griieed operator and optimal transport both operate in late interaction mechanism, which is only conducted on the final output of the encoder.
When extending the video length to 32 frames (Line 5), the training time increases from 87 minutes (Line 1) to 172 minutes (approximately x 1.98). This experiment aims to simulate temporal learning methods that encode the entire long video into single sequence (Zeng al., 2023b; Han et al., 2022). In contrast, our method (Line 4) requires a smaller amount of time (146 minutes) while still being capable of embedding videos with 128 frames. We further evaluate the time cost of Sinkhorn iteration per epoch in Lines 6 and 7. Compared to the forward and backward passes of the network, the computation of the Sinkhorn iterations is minimal.
D ROBUSTNESS ON NOISY CORRESPONDENCE
In this section, evaluate the effectiveness of different methods against noisy correspondence through visual-textual alignment experiments on the HTM-Align dataset (Han et al., 2022). HTM- Align subset of the HowTo 100M dataset, consisting of 80 videos with 49K sentences that have been manually annotated to rectify the alignment in the presence of noisy correspondence. The annotators have two main tasks: i) determining if a sentence from ASR is visually related to the video, and ii) adjusting the start & end timestamps to accurately cover the visual content if the sentence is related.
After training the models on the HowTol00M dataset, we evaluated their performance on this align- ment task to assess their ability to handle noise. We report the Recall metrics for this alignment task. Specifically, for misaligned sentence, if its most closely matched video frame falls into the ground -ruth segment annotated by the human, it counted as a successful recall. The Recall scores averaged across all the text segments.
17

---

Published as a conference paper at ICLR 2024
For fair comparison, the maximum number of video frames is set to 32 for Han et al. (2022); Xu et al. (2021); ); Yang et al. (2023b) and our method. We also include the 64 frame version of TAN (Han et al., 2022) for completeness. We use sliding window approach to calculate the similarity between video frames and sentences with a window size of 32 seconds and step size of seconds. We averaged the similarity scores for overlapping visual tokens from multiple windows. As shown in Table 9, CLIP exhibits inferior performance, possibly because it has only been trained on images and lacks the ability to capture video dynamics. In contrast, our method outperforms VideoCLIP and TempCLR, providing evidence that our approach is not prone to fit noisy correspondence.
Table 9: Alignment results on the HTM-Align datasets.
Approach
Recall
CLIP (ViT-B/32) (Radford et al., 2021)
17.5
MIL-NCE (Miech et al., 2020)
34.2
TAN (Han et al.. 2022) - 32 frame
41.1
TAN (Han et al.. 2022) 64 frame
49.2
VideoCLIP (Xu et al., 2021)
44.4
TempCLR (Yang et al., 2023b)
44.1
Norton (Ours)
46.9
E APPLICATIONS AND POTENTIAL IMPLICATIONS
Application scenarios. Norton is a representation learning method that exhibits versatility across various tasks including video retrieval, video QA, and classification, as confirmed by our experi- ments. A notable strength of Norton lies in its ability to effectively address the common challenge of noisy correspondence, particularly in uncurated instructional videos. This adaptability allows Norton to be implemented in diverse scenarios without necessitating meticulous video curation. For instance, Norton proves effective in tasks such as long video retrieval or classification for various content genres like movies, education videos, and cooking tutorials. It's also essential to acknowl- edge that Norton is tailored for representation learning and may exhibit suboptimal performance in tasks focused on content generation, such as video captioning.
Potential implications. This paper delves into two challenging problems in video understanding, namely, long video learning and noisy correspondence learning- In addressing the former, where computational constraints have limited prior works, our proposed efficient solution may spark in- creased interest in long video understanding tasks. Regarding the latter, the noisy correspondence problem (mismatched data pairs) has garnered attention in diverse multi-modal applications, ex- tending beyond video-text domains to encompass challenges image-text retrieval (Huang al., 2021: Qin et al., 2022; 2023; Han et al., 2023; Yang et al., 2023a). cross-modal generation (Li et al., 2022), person re-identification (Yang et al., 2022), and graph matching (Lin al., 2023). Our work has the potential to attract increased attention to the broader spectrum of noisy correspondence challenges across various domains.
F CHALLENGES IN FUTURE WORKS
Multi-modal scenarios. Our approach introduces an optimal transport solution to address the noisy correspondence between bi-modalities in videos and text. However, videos inherently encompass visual, textual, and audio content (Shvetsova et al., 2022; Yang et al., 2024), the noisy correspon- dence challenge might extend across multiple modalities. Addressing multi-modal noisy correspon- dence using optimal transport presents an open challenge, given the quadratic growth in combina- tions concerning the number of modalities. We acknowledge this limitation and plan extend our method to effectively tackle multi-modal noisy correspondence, exploring these scenarios in future work.
Utilization of Noise. In this paper, employ the prompt bucket directly filter out irrelevant clips and captions during sequential alignment, attempting to mitigate the influence of noisy corre- spondence. However, intriguing question arises regarding whether these noisy samples could be
18

---

Published as a conference paper at ICLR 2024
utilized incentive for training (Li, 2022). Exploring the possibility of generating associated text for unalignable video clips using large multimodal models (LMMs), e.g., LLaVA (Liu et al., 2023), BLIP-2 (Li et al., 2023) and GPT-4V(ision)) (OpenAI, 2023), could open up novel avenue for exploration and improvement in future research endeavors.
G VISUALIZATION OF RE-ALIGNMENT FOR YOUTUBE VIDEOS
In this section, we present the visualization the optimal transport assignment Q to demonstrate the robustness of our method. Specifically, compared our proposed Norton with the Dynamic Time Warping and vanilla optimal transport. As shown in Fig. 3c, the vanilla OT falsely aligns the meaningless text "It's mapping between each source instance and the targets. In contrast, as depicted in Fig. 3d, our method successfully filters the semantically irrelevant captions with the help of the proposed Alignable Prompt Bucket. Moreover, shown in Fig. 3b, DTW erroneously aligns video clips to multiple captions and fails to address the issue of irrelevant captions. In word, the visualization illustrates that our Norton outperforms DTW and vanilla OT in aligning the clips with captions in the presence noisy correspondence.
moment" some irrelevant video clips, because OT requires exact
19

---

Published as a conference paper at ICLR 2024
Sprinkle powdered gelatin the soften
0.8
2. Dissolve the gelatin water bath
Whip
4. Pour the no-bake cheesecake over the cookies
Arrange strawberries
0.2
(a) Similarity Matrix
Sprinkle powdered gelatin milk to soften it
Dissolve the gelatin water bath
3. Whip the fresh cream
4. Pour the no-bake cheesecake over the cookies
5. Arrange the strawberries
Irrelevant
6. It's tense moment
(b) Re-alignment by Dynamic Time Warping
Sprinkle powdered gelatin
milk to soften
2. Dissolve the gelatin water bath
Whip cream
4. Pour the no-bake cheesecake over the cookies
Arrange strawberries
Irrelevant
tense
(c) Transport Assignment of Vanilla Optimal Transport
Sprinkle powdered gelatin milk to soften it
Dissalve the gelatin water bath
3. Whip the fresh cream
4. Pour the no-hake cheesecake over the cookies
5. Arrange the strawberries
Irrelevant
6. It's tense moment
(d) Transport Assignment of Norton
Figure 3: Visualization of the re-alignment.
20


Reviews:
[{"review_id": "1zhQ5aqWdm", "reviewer": "Reviewer_UrFs", "summary": "The paper introduces NOise Robust Temporal Optimal traNsport (Norton), a method designed to address multi-granularity noisy correspondence (MNC) in video-language studies, particularly focusing on long-term temporal dependencies in long videos. Norton utilizes optimal transport (OT) to handle both coarse-grained clip-caption misalignment and fine-grained frame-word misalignment, hindering temporal learning and video understanding. The method incorporates video-paragraph and clip-caption contrastive losses, an alignable prompt bucket for filtering irrelevant clips and captions, and a soft-maximum operator for identifying crucial words and keyframes. Additionally, Norton rectifies alignment targets in clip-caption contrastive learning to ensure precise temporal modeling. The effectiveness of Norton is demonstrated through extensive experiments on video retrieval, video QA, and action segmentation tasks.", "questions": "1. Could you provide more details on the design choices behind the Norton method, specifically the alignable prompt bucket and the soft-maximum operator? Understanding the rationale behind these components could offer deeper insights into their roles and contributions to the overall approach.\n\n2. The paper presents a comparison with existing methods, but could you elaborate on specific scenarios or cases where Norton particularly excels or struggles? This information would help in understanding the practical implications and limitations of the method.\n\n3. Could you discuss any potential limitations or challenges associated with the Norton method? Acknowledging these aspects would provide a more balanced view of the method and help set realistic expectations for its performance.\n\n4. Could you provide more detailed implementation details, including hyperparameter settings, training procedures, and computational resources? This information would enhance the reproducibility of the results and facilitate future research building upon this work.\n\n5. Could you elaborate on the potential implications and applications of the Norton method in real-world scenarios? Understanding the practical impact of the method could offer additional motivation for the work and highlight its significance in the field.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel method, NOise Robust Temporal Optimal traNsport (Norton), which addresses the multi-granularity noisy correspondence (MNC) problem in video-language studies. This method is unique in its approach to handling both coarse-grained and fine-grained misalignments using optimal transport.\n2. Norton incorporates innovative components such as an alignable prompt bucket and a soft-maximum operator to address specific challenges in video-language representation learning.\n3. The method is rigorously evaluated across various tasks, including video retrieval, videoQA, and action segmentation, demonstrating its effectiveness and robustness.\n4. The paper provides extensive experimental results, comparisons with existing methods, and visualizations to validate the proposed approach.\n5. The paper effectively communicates the core ideas, methodologies, and results, making it accessible to readers with a background in the field.\n6. Norton addresses a significant challenge in video-language studies, particularly the handling of long-term temporal dependencies in extended videos.\n7. The method’s ability to improve temporal learning and video understanding has potential implications for various applications in computer vision and natural language processing.", "weaknesses": "1. The paper could benefit from providing more context and justification for the chosen methodologies and design decisions. For instance, the rationale behind the specific components of the Norton method, such as the alignable prompt bucket and the soft-maximum operator, could be elaborated upon to give readers a deeper understanding of their significance and contribution to the overall approach.\n\n2. The paper could be improved by including a more thorough discussion of the limitations of the proposed method. Acknowledging and addressing potential shortcomings or challenges in the approach would provide a more balanced view and help to set realistic expectations for the method’s applicability and performance.\n\n3. Providing more detailed implementation details, including hyperparameter settings, training procedures, and computational resources, would enhance the reproducibility of the results and allow other researchers to more easily build upon the work.", "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": "", "extra_scores": {}}, {"review_id": "qe4eJIxX7b", "reviewer": "Reviewer_TtfV", "summary": "The paper presents an innovative approach Norton for video-language pre-training that learns long-term temporal dependencies between short video clips and captions. The paper addresses two challenges: 1) the high computational cost of modeling long videos and 2) the noisy correspondence between clips and captions due to asynchronous and irrelevant pairs. The paper uses a modified optimal transport framework to measure the sequence similarity between clips and captions, and to filter out the noisy pairs. The paper also exploits the faulty negative samples in contrastive learning to improve clip representation. The paper evaluates the method on video-paragraph retrieval, text-to-video retrieval, videoQA, and action segmentation tasks, and shows that it outperforms existing methods on various metrics. The paper also conducts ablation studies to analyze the impact of different components.", "questions": "The primary queries for the rebuttal are predominantly derived from the \"weaknesses\" section outlined earlier. For instance, it would be highly appreciated if the authors could augment their experiments regarding noisy correspondence and offer more clarification on how their approach differs from other OT-based methods. Resolving these raised concerns will make the submission stronger and I vote for accepting this paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1.This paper is well-written, well-organized, and easy to follow.\n2.The problem tackled by the authors is an interesting one - noisy correspondence, almost all video harvested from the web would include such cases and hinders the performance of large-scale multi-modal video learning. This challenge is inherent in the data and has received little attention in the literature. The paper explores this novel and important problem in depth.\n3.The paper presents a unified OT framework that can efficiently and effectively solve the MNC problem at different levels of granularity. I commend the authors for providing a time cost table in the appendix which shows the efficiency of their method with various settings and verifies their claims.\nThis method's unique strength lies in using existing pre-training model and works in a self-bootstrapping capability. Note that directly pretraining a large multi-modal model is unpractical for the researchers not in company. This paper significantly improves the temporal ability of VideoCLIP without the need for additional models like DecemBert or TAN. This self-sufficiency significantly contributes to its enhanced scalability.", "weaknesses": "1.This paper does not provide specific numerical results on how well the proposed method handles noisy correspondence. It would be beneficial if the authors could provide more detailed numerical results or analysis on this aspect in their rebuttal or future work. For example, they could conduct experiments on synthetic noisy datasets to show the performance of their method. They could also compare their method with other methods that are designed to handle noisy correspondence and show how their method performs in comparison. This would provide more concrete evidence on the effectiveness of their method in handling noisy correspondence.\n2.In certain scenarios, such as video-paragraph retrieval on YouCookII (as shown in Table 1) and in the context of ablation experiments (as indicated in Table 7), we observe encouraging indications of potential improvements. While in other experiments (as depicted in Table 2), there are mixed results across various metrics. Can you shed light on the reasons behind this disparity?\n3.How does the proposed method compare with other OT-based methods like action sequence matching? What are the benefits or drawbacks of using OT for video-text learning? Please provide some comparisons and discussions.", "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": "", "extra_scores": {}}, {"review_id": "tHlhMgjMW5", "reviewer": "Reviewer_pP85", "summary": "This paper delves into the long-term video-text learning task and reveals a new problem named multi-granularity noisy correspondence (MNC), referring to both course-grained clip-caption misalignment and fine-grained frame-word misalignment. Clearly, such a problem would hinder temporal learning and video understanding. To address the MNC problem, the authors propose NOise Robust Temporal Optimal traNsport (Norton), which formulates the solutions to both course- and fine-grained NC into a unified optimal transport (OT) framework. On the one hand, Norton filters the irrelevant clips and captions using an alignable prompt bucket and realigns the asynchronous clip-caption pairs based on transport distance, contributing to robustness against course-grained NC. On the other hand, a soft-maximum operator is used to identify crucial words and keyframes so that the negative impact of fine-grained NC can be alleviated. The effectiveness of Norton is validated through extensive experiments on commonly used video-text tasks, including video retrieval, video QA, and action segmentation.", "questions": "The major concern is the lack of some claims, as highlighted in the weaknesses.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Revealing a new problem**. This paper studies a new and practical challenge in the context of long-term video-text representation learning, namely, multi-granularity noisy correspondence (MNC). MNC encompasses both coarse-grained clip-caption misalignment and fine-grained frame-word misalignment, both of which hinder temporal learning and video comprehension. While some studies have been concentrated on addressing the coarse-grained clip-caption misalignment, as far as I know, there are no formal studies on the fine-grained NC for video-text learning. From this perspective, I think this paper would bring some new insights to the community.\n\n**Novel approach**. To handle MNC and achieve robust long-term video-text learning, this paper proposes Norton, which formulates the solutions to both course- and fine-grained NC into a unified optimal transport (OT) framework. Norton first incorporates a token-wise soft-maximum operator to identify crucial words and keyframes within each clip-caption pair, so that the fine-grained NC could be eliminated. After that, Norton filters the irrelevant clips and captions using an alignable prompt bucket, and realigns the asynchronous clip-caption pairs based on transport distance, leading to robustness against course-grained NC. \n\n**Good shape**. This paper is well-written and structured. Besides, the experiment designs are interesting and sufficient. Extensive experimental results validated the effectiveness of the proposed methods and the necessity of solving MNC problems.", "weaknesses": "- While the authors effectively illustrate the motivation in Fig. 1, the advantages of the proposed OT method over DTW require more elaboration. It is advisable to include further discussions to expound upon and clarify the claims made regarding the superiority of OT over DTW.\n- The use of the stop-gradient operation in transport assignment Q is highlighted by the authors as a means to enhance the efficiency of their video-paragraph contrastive loss. However, the rationale behind this operation's efficacy is not entirely clear. To remedy this, additional discussions should be included to provide a more comprehensive explanation of why this operation is meaningful and how it improves efficiency.\n- To enhance clarity, it is suggested that the authors highlight the second-best results alongside the primary results in each table. This practice can provide a useful point of reference for readers and facilitate a more comprehensive understanding of the findings.\n- The results of DTW should be included as a baseline for comparison. This can help demonstrate the advancements made in the proposed methodology and provide a clearer context for the contributions of this work.", "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": "", "extra_scores": {}}, {"review_id": "fXXYESyduO", "reviewer": "Reviewer_83JB", "summary": "This paper proposes a novel method for learning long-term temporal correspondence from noisy instructional videos. The main idea is to use optimal transport (OT) to measure the sequence similarity between video clips and captions, and address the multi-granularity noisy correspondence (MNC) problem at both coarse and fine levels. The paper also introduces several techniques to enhance the OT framework, such as a soft-maximum operator, an alignable prompt bucket, and a faulty negative exploitation strategy. The paper evaluates the proposed method on various downstream tasks, such as video-paragraph retrieval, videoQA, and action segmentation, and shows that it outperforms existing state-of-the-art methods.", "questions": "(1) How do you choose the value of p of clip-caption pairs for the alignable prompt bucket? Is it fixed per epoch or adaptive to different batches? How sensitive is the performance to different values of p? \n(2) How do you deal with clips or captions that have different lengths as you choose a random window size for clip and caption sampling? Do you perform any preprocessing or padding on the clips or captions? How does this affect the optimal transport computation?\n[1] Tengda Han, Weidi Xie, and Andrew Zisserman. Temporal alignment network for long-term video. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.\n[2 ] Bing Su and Gang Hua. Order-preserving wasserstein distance for sequence matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1049–1057, 2017.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) The paper tackles an important and challenging MNC problem of learning long-term temporal dependency from noisy video-text data, which has many potential applications in video understanding. Although temporal misalignment has been explored in TAN [1], they only consider the noisy correspondence from a course grained sentence level. While this paper proposes a novel and efficient method based on optimal transport, which can handle the multi-granularity noisy correspondence problem in a unified framework and outperform previous work TAN. The paper also provides empirical evidence to support the proposed method. \n(2) The paper introduces several innovative components to enhance the optimal transport framework, such as the soft-maximum operator for fine-grained alignment, the alignable prompt bucket for filtering out irrelevant clips or captions, and the faulty negative exploitation for improving clip representation. \n(3) The paper conducts extensive experiments on diverse downstream tasks and datasets and demonstrates that the proposed method achieves remarkable improvements over existing state-of-the-art methods. The paper also performs ablation studies to analyze the impact of different design choices.", "weaknesses": "(1) The explanation of why using optimal transport effectively learns video-paragraph similarity in the paper could be more explicit. Specifically, when the similarity calculated by the S matrix might not be accurate in the early stages of model training, it is important to understand how the training objective, which aims to maximize the similarity of ⟨Q,S⟩, prevents misleading the model. Additional clarification on this point would be beneficial.\n(2) The paper does not compare the proposed method with other methods that use optimal transport for sequence alignment, such as Su & Hua (2017) [2]. It would be interesting to see how the proposed method differs from these methods in terms of performance and efficiency.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (oral)