DeCEMBERT: Learning from Noisy Instructional Videos via Dense Captions and Entropy Minimization

Leveraging large-scale unlabeled web videos such as instructional videos for pre-training followed by task-specific finetuning has become the de facto approach for many video-and-language tasks. However, these instructional videos are very noisy, the accompanying ASR narrations are often incomplete, and can be irrelevant to or temporally misaligned with the visual content, limiting the performance of the models trained on such data. To address these issues, we propose an improved video-and-language pre-training method that first adds automatically-extracted dense region captions from the video frames as auxiliary text input, to provide informative visual cues for learning better video and language associations. Second, to alleviate the temporal misalignment issue, our method incorporates an entropy minimization-based constrained attention loss, to encourage the model to automatically focus on the correct caption from a pool of candidate ASR captions. Our overall approach is named DeCEMBERT (Dense Captions and Entropy Minimization). Comprehensive experiments on three video-and-language tasks (text-to-video retrieval, video captioning, and video question answering) across five datasets demonstrate that our approach outperforms previous state-of-the-art methods. Ablation studies on pre-training and downstream tasks show that adding dense captions and constrained attention loss help improve the model performance. Lastly, we also provide attention visualization to show the effect of applying the proposed constrained attention loss.

Introduction
Video and language are ubiquitous in the world we live. The ability to understand the interplay of video and language is thus essential for intelligent agents to operate in real-world scenario. Past success in video-and-language has mostly been driven by supervised learning, where models are learned on manually labeled data for a particular task (e.g., text-to-video retrieval). However, manually annotating video and language data is very expensive, hence limiting the scale of such datasets, and consequently also limiting the performance of models trained on the datasets. The self-supervised pretraining then finetuning paradigm offers an easy and generic solution to this dilemma, where models are first pre-trained on large-scale unlabeled data by performing various "proxy tasks", followed by finetuning the pre-trained model on downstream tasks where data is often limited.
Recent advances on language pre-training (Devlin et al., 2019; demonstrate the effectiveness of this approach, where transformerbased (Vaswani et al., 2017) models pre-trained on large-scale unlabeled text corpus has shown to perform remarkably well across a wide range of natural language tasks (Rajpurkar et al., 2016;Williams et al., 2017;Zellers et al., 2018;Wang et al., 2018). Following this momentum, multimodal pre-training (Tan and Bansal, 2019;Su et al., 2019;Cho et al., 2021;Sun et al., 2019;Li et al., 2020c;Zhu and Yang, 2020;Miech et al., 2020;Li et al., 2020b; on large-scale image-text corpus (Sharma et al., 2018;Chen et al., 2015;Krishna et al., 2017) and video-text corpus Miech et al., 2019;Sun et al., 2019) have also shown to outperform existing approaches (Anderson et al., 2018;Yu et al., 2018a;Lei et al., 2020a,b) on vision and language tasks (Antol et al., 2015;Xu et al., 2016;Yu et al., 2018a;Suhr et al., 2019;Lei et al., 2020b). The most commonly used "proxy tasks" for multimodal pre-training are masked language modeling (Devlin et al., 2019) (MLM) and cross-modal matching (Tan and Bansal, 2019;Zhu and Yang, 2020) (e.g., video-text matching), where MLM aims to learn a better language model in the presence of the extra   (Miech et al., 2019). We show three clips and their corresponding ASR captions and dense captions. We use green box to indicate correct matched ASR caption for the middle clip. We highlight semantically misaligned ASR caption in pink. As can be seen from this example, the ASR captions are often incomplete and unpunctuated, and are semantically or temporally misaligned with their corresponding clips. In contrast, dense captions typically capture key objects, attributes and actions in the clips.
vision modality, and the matching objective encourages better association and alignment between relevant image-text or video-text pairs. Existing video-text pre-training models (Sun et al., 2019;Miech et al., 2020;Zhu and Yang, 2020) are typically trained on large-scale instructional video datasets such as HowTo100M (Miech et al., 2019). The dataset contains 1.2 million videos with 136 million clips that are automatically harvested from YouTube. Each clip is paired with text transcribed from the video narrations via an automatic speech recognition (ASR) system. While the models trained on HowTo100M have shown promising results, they suffer from a few inherent drawbacks from the dataset: (i) Semantic misalignment: the narration words are sometimes irrelevant to the visual content (e.g., credits or other nonvisual words, see Figure 1 text highlighted in pink), and vice versa, i.e., some important visual objects and actions are not described by words. (ii) Temporal misalignment: the videos and the captions are far from perfectly aligned, i.e., people might talk about something before or after they actually demonstrate it. For example, Figure 1 shows the caption "cross" is spoken after the action happened. Miech et al. (2019) reported that around 50% of the clip-caption pairs in HowTo100M suffers from these two misalignments, both of which cause difficulties in optimizing the video-text matching objective. (iii) Furthermore, the ASR captions are generally noisy, incomplete, and unpunctuated (Tilk and Alumäe, 2015) (e.g., in Figure 1, "taking pieces paper go"), which limits the language modeling ability of the systems that trained on such text.
To address the aforementioned issues, we propose to add Dense Captions (Johnson et al., 2016;Yang et al., 2017) as a complementary text input to the ASR captions. Beyond serving as an extra language input for better language modeling, dense captions also describes important object, attribute, and action details regarding several salient regions in the video frames, providing useful signals for video-text matching. In addition to its use in the pre-training stage, these dense captions also provide helpful clues for downstream tasks such as video question answering.
In parallel, to alleviate the temporal misalignment issue, we propose a constrained attention loss that encourages the model to automatically focus on the relevant ASR caption from a pool of continuous caption candidates. Instead of using only a single paired ASR caption for each clip, we also use the captions from its neighboring clips. We expect one of neighboring captions semantically aligns with the clip. To encourage the alignment between the clip and its relevant caption, we employ a "constrained attention loss" that encourages the attention mass from video features to the captions to be distributed mostly in one of the caption, by minimizing the entropy of attention scores.
We evaluate our DECEMBERT (Dense Captions and Entropy Minimization) model on a wide range of video-and-language tasks, including video question answering , text-to-video retrieval (Xu et al., 2016;, and video captioning (Xu et al., 2016;, where our approach outperforms previous state-of-the-art methods. To better understand the underlying factors that contribute to this success, we present comprehensive analyses concerning each of the added components. To summarize, our contribution is three-fold: (i) We propose incorporating automatically extracted dense captions as an extra text input for video-text pre-training. (ii) We propose an entropy minimization-based constrained attention loss to encourage the model to dynamically select the best matched captions from a pool of neighboring captions, to alleviate the inherent misalignment between the ASR captions and the videos. (iii) Extensive experiments on three video-and-language tasks (text-to-video retrieval, video captioning, and video question answering) across five datasets demonstrate the effectiveness of our approach. Furthermore, we also provide comprehensive ablation study and visualization to quantitatively and qualitatively examine the effect of using dense captions and the proposed constrained attention loss.

Related Work
Since the birth of BERT (Devlin et al., 2019), transformer (Vaswani et al., 2017) language pre-training models Lan et al., 2020;Dong et al., 2019;Song et al., 2019;Raffel et al., 2020;Clark et al., 2020) which perform unsupervised pre-training followed by downstream task specific finetuning has became the de facto approach for various natural language understanding tasks (Rajpurkar et al., 2016;Williams et al., 2017;Zellers et al., 2018;Wang et al., 2018). Followed by this success, image-and-language pretraining models (Tan and Bansal, 2019;Li et al., 2020a) and video-and-language pre-training models (Sun et al., 2019;Miech et al., 2019;Zhu and Yang, 2020;Miech et al., 2020;Li et al., 2020b;Luo et al., 2020;Stroud et al., 2020) have also shown promising results on many vision and language tasks (Antol et al., 2015;Xu et al., 2016;. For video-and-language pre-training in particular, most existing work (Sun et al., 2019;Miech et al., 2019;Zhu and Yang, 2020;Miech et al., 2020;Li et al., 2020b;Luo et al., 2020) are trained on large-scale unlabeled instructional videos, such as HowTo100M (Miech et al., 2019) videos. However, as the ASR captions associated with these videos are noisy, i.e., they are often temporally or semantically misaligned with the video content. Miech et al. (2020) propose Multiple Instance Learning Noise Contrastive Learning (MIL-NCE) to address the temporal misalignment issue, but semantic misalignment still remains. Moreover, MIL-NCE requires computing a separate similarity score from the target clip to each of the ASR caption candidates, it does not suitable for the prevailing single-stream transformer pre-training ar-chitecture due to linearly increased computation cost.
Inspired by recent work (Kim and Bansal, 2019;Kim et al., 2020) that uses dense captions (Johnson et al., 2016;Yang et al., 2017) to improve image and video QA models, we propose to add dense captions an as auxiliary text input that provide aligned visual cues to ease the difficulties of learning a video-text matching objective from often temporally and semantically misaligned ASR captions. In addition, we also propose a constrained attention loss, which employs an entropy minimizationbased regularization (Tanaka et al., 2018;Yi and Wu, 2019) to the model to encourage higher attention scores from the video to the correct matched caption among a pool of ASR caption candidates.

Method
In this section, we describe the details of DECEM-BERT, including its architecture, pre-training objectives, dense caption inputs, and the constrained attention loss. Figure 2 shows an overview of DE-CEMBERT.
Input Representations. Input text (e.g., ASR captions) are tokenized and represented as a sequence of WordPiece (Wu et al., 2016) tokens. We use a trainable word embedding layer to encode the tokens into feature representations. We use appearance and motion features to represent videos. For appearance, we use a resnet152 (He et al., 2016) model pre-trained on ImageNet (Deng et al., 2009) to extract 2D video features at 1FPS. Similarly, for motion, we use a 3D ResNeXt (Xie et al., 2017;Hara et al., 2018;Kataoka et al., 2020) to extract 3D video features at 1FPS. The temporally aligned appearance and motion features are L2-normalized and concatenated together at feature dimension. We then apply a two-layer MLP to map the it to the same dimension as the word embeddings. Next, we add learned positional embedding and token type embedding (Devlin et al., 2019) to the video and text representations to encode the position and token type information. The video and text representations are then concatenated as a single sequence as inputs to a 12-layer transformer encoder for pre-training and downstream task finetuning.
Dense Captions. The original captions from ASR systems might not well describe a video with rich content or can even be irrelevant to the video as discussed in Section 1. Moreover, as ASR cap- tions are often incomplete and unpunctuated, they might also be sub-optimal for language modeling. Therefore, we use dense captions (Johnson et al., 2016) automatically extracted from an off-the-shelf image dense captioning model (Yang et al., 2017) as additional language input for the model. This dense captioning model is pre-trained on Visual Genome (Krishna et al., 2017) regional captions.
To obtain video-level captions, we extract dense captions from frames sampled at every two seconds. There are on average 4.4 dense captions per frame, we sample two of them from each frame at each training step to avoid redundant information and reduce memory and computation cost. Note that the other dense captions might still be sampled in another training step. The sampled dense captions are then concatenated together as video-level captions for training. These extracted dense captions provide rich and comprehensive information regarding the salient objects, attributes, and actions (see examples in Figure 1 and Figure 2), which helps to optimize a video-text matching objective during pre-training and provide essential visual clues for many downstream tasks such as video question answering. Meanwhile, because the dense captions are text input with diverse semantics, it complements the typically short and incomplete ASR captions as additional resources for better language modeling. We observe in our ablation study that adding dense captions improves both MLM accuracy and videotext matching accuracy, demonstrating the effectiveness of using them as extra inputs.
Pre-Training Objectives. During pre-training, we use masked language modeling (Devlin et al., 2019) (MLM) and cross-modality matching (Tan and Bansal, 2019;Miech et al., 2019;Zhu and Yang, 2020) (also referred as videotext matching in our context) as our objectives to learn model parameters. For masked language modeling, the goal is to learn better language models conditioned on bidirectional text context and the video. We set a probability of 0.20 2 to replace an input language token with [MASK]. When dense captions are used as extra text input, we also perform masked language modeling on them with the same masking probability as the ASR captions.
For video-text matching, with a probability of 0.50, we replace the original ASR captions with randomly sampled captions from other videos or clips as a negative. Of the sampled negative ASR captions, 50% of them are from different videos, while another 50% are from the same video but different clips. Text from the same video clip is likely to have the same theme or similar context, and thus can serve as hard samples to improve the model's ability to do fine-grained matching. We do not designate a [CLS] token before the start of input caption, instead we take the mean pooling of the output sequence hidden states to perform binary classification for video-text matching. Empirically, we found this approach works better than using a then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the 350 correct matched caption for an input clip, i.e., the 351 attention mass from the video clip to the correct 352 matched caption should be higher than the others.

353
We denote the overall attention score from the input 354 video clip to one of the ASR captions as: The 355 maximum response between the ASR captions to 356 each element in the video can be computed as: We then employ an entropy-based loss: only inputting its associated caption s i , we also in-330 clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions.

333
We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix: Our goal is to encourage the model to focus on the 350 correct matched caption for an input clip, i.e., the 351 attention mass from the video clip to the correct 352 matched caption should be higher than the others.

353
We denote the overall attention score from the input 354 video clip to one of the ASR captions as: The 355 maximum response between the ASR captions to 356 each element in the video can be computed as: We then employ an entropy-based loss: en be expressed as:    n employ an entropy-based loss: s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions. 333 We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix: We then employ an entropy-based loss: anguage modeling on it with the same probability as the ASR captions. o-text matching, with a probability of 0.5, e the original ASR caption with a ranmpled caption from other videos or clips tive. Of the sampled negative ASR capof them are from different videos, while 0% are from the same video but different xt from the same video clip is likely to same theme or similar context, and thus as hard samples to improve the model's do fine-grained matching. We do not desoken before the start of input caption for predict text-video matching, instead we ean pooling [Jie: is it mean-pooled through sequence? ] of the output sequence hidres to perform binary classification. This e matching objective usually requires a learning rate as to text token prediction.
u have more reasons behind this? Like a refere: how the dense captions are used in video-text ] strained Attention SR captions are often temporally misith their corresponding clip, simply preodel over these misaligned clip-text pairs to sub-optimal performance. Recent work E (Miech et al., 2020) proposes to adproblem with a multiple instance learning sed objective, but it is more computational e as we need to get scores from multient pairs. Within the single-stream transchitecture, this means we need to add adput sequences, which effectively increase utation cost by a factor of N where N is the ber of neighboring captions and negative been used. In our formulation, we only rocess a single sequence that combines ighboring captions and without the need ive captions. that videos and extracted uth caption in the corresponding time do ly match in every sample, we address this llowing the model to automatically select ing caption. note an input video V as [c 1 , c 2 , ..., c N ], ponding ASR captions are denoted as , s N ], where c i is the i-th clip of V and ASR caption of c i , N is the total numps in the video. For a clip c i , instead of clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions. 333 We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the We then employ an entropy-based loss: onstrained Attention ASR captions are often temporally misd with their corresponding clip, simply premodel over these misaligned clip-text pairs ad to sub-optimal performance. Recent work CE (Miech et al., 2020) proposes to adhis problem with a multiple instance learning based objective, but it is more computational sive as we need to get scores from multiferent pairs. Within the single-stream transarchitecture, this means we need to add adl input sequences, which effectively increase putation cost by a factor of N where N is the umber of neighboring captions and negative ns been used. In our formulation, we only o process a single sequence that combines neighboring captions and without the need gative captions. that videos and extracted truth caption in the corresponding time do actly match in every sample, we address this y allowing the model to automatically select tching caption. denote an input video V as [c 1 , c 2 , ..., c N ], responding ASR captions are denoted as , ..., s N ], where c i is the i-th clip of V and he ASR caption of c i , N is the total numclips in the video. For a clip c i , instead of clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions.

333
We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the We then employ an entropy-based loss: 4 ed language modeling on it with the same ing probability as the ASR captions. video-text matching, with a probability of 0.5, eplace the original ASR caption with a rany sampled caption from other videos or clips negative. Of the sampled negative ASR cap-, 50% of them are from different videos, while er 50% are from the same video but different . Text from the same video clip is likely to the same theme or similar context, and thus erve as hard samples to improve the model's y to do fine-grained matching. We do not dese a token before the start of input caption for l to predict text-video matching, instead we the mean pooling [Jie: is it mean-pooled through hole sequence? ] of the output sequence hideatures to perform binary classification. This cause matching objective usually requires a rent learning rate as to text token prediction. Constrained Attention e ASR captions are often temporally mised with their corresponding clip, simply prea model over these misaligned clip-text pairs lead to sub-optimal performance. Recent work -NCE (Miech et al., 2020) proposes to adthis problem with a multiple instance learning ) based objective, but it is more computational nsive as we need to get scores from multiifferent pairs. Within the single-stream transer architecture, this means we need to add adal input sequences, which effectively increase omputation cost by a factor of N where N is the number of neighboring captions and negative ons been used. In our formulation, we only to process a single sequence that combines e neighboring captions and without the need egative captions. that videos and extracted nd truth caption in the corresponding time do xactly match in every sample, we address this by allowing the model to automatically select atching caption. e denote an input video V as [c 1 , c 2 , ..., c N ], orresponding ASR captions are denoted as 2 , ..., s N ], where c i is the i-th clip of V and the ASR caption of c i , N is the total numf clips in the video. For a clip c i , instead of clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions. 333 We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the We then employ an entropy-based loss: s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions.

333
We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the We then employ an entropy-based loss: as [c 1 , c 2 , ..., c N ], s are denoted as -th clip of V and is the total numclip c i , instead of clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions. 333 We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the We then employ an entropy-based loss: on it with the same SR captions. ith a probability of 0.5, R caption with a ranother videos or clips ed negative ASR capdifferent videos, while me video but different video clip is likely to ilar context, and thus improve the model's tching. We do not desrt of input caption for matching, instead we s it mean-pooled through output sequence hidry classification. This ive usually requires a text token prediction.
behind this? Like a referions are used in video-text n ften temporally misding clip, simply prealigned clip-text pairs ormance. Recent work 020) proposes to adltiple instance learning is more computational et scores from multie single-stream transans we need to add adich effectively increase tor of N where N is the captions and negative formulation, we only quence that combines and without the need videos and extracted orresponding time do ample, we address this to automatically select o V as [c 1 , c 2 , ..., c N ], tions are denoted as the i-th clip of V and , N is the total numr a clip c i , instead of clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions.

333
We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the 350 correct matched caption for an input clip, i.e., the 351 attention mass from the video clip to the correct 352 matched caption should be higher than the others.

353
We denote the overall attention score from the input 354 video clip to one of the ASR captions as: The 355 maximum response between the ASR captions to 356 each element in the video can be computed as: We then employ an entropy-based loss: Similarity Matrix sed as extra text input, we also perform guage modeling on it with the same bability as the ASR captions. text matching, with a probability of 0.5, the original ASR caption with a ranled caption from other videos or clips e. Of the sampled negative ASR capf them are from different videos, while are from the same video but different from the same video clip is likely to me theme or similar context, and thus hard samples to improve the model's fine-grained matching. We do not desen before the start of input caption for edict text-video matching, instead we an pooling [Jie: is it mean-pooled through uence? ] of the output sequence hidto perform binary classification. This matching objective usually requires a arning rate as to text token prediction.
ave more reasons behind this? Like a referhow the dense captions are used in video-text rained Attention captions are often temporally mish their corresponding clip, simply preel over these misaligned clip-text pairs sub-optimal performance. Recent work (Miech et al., 2020) proposes to adoblem with a multiple instance learning objective, but it is more computational s we need to get scores from multit pairs. Within the single-stream transitecture, this means we need to add adt sequences, which effectively increase tion cost by a factor of N where N is the r of neighboring captions and negative en used. In our formulation, we only cess a single sequence that combines hboring captions and without the need captions. that videos and extracted caption in the corresponding time do match in every sample, we address this wing the model to automatically select g caption. te an input video V as [c 1 , c 2 , ..., c N ], nding ASR captions are denoted as N ], where c i is the i-th clip of V and R caption of c i , N is the total numin the video. For a clip c i , instead of only inputting its associated caption s i , we also in-330 clude captions from its two neighboring clips, i.e., 331 s i 1 and s i+1 . In most cases, the correct matched 332 caption for the clip is from these three captions.

333
We denote X=[X ci ; X si 1 ; X si ; X si+1 ] 2 R l⇥d 334 as the generalized input sequence to each trans-335 former layer, where X ci , X si 1 , X si , X si+1 are 336 the embedding matrices correspond to the input 337 clip and captions. We further simplify the nota-338 tions as X=[X 0 ; X 1 ; X 2 ; X 3 ]. The self-attention 339 operation in the transformer encoder layers can 340 then be expressed as:

342
where softmax(·, dim = 1) denotes performing 343 softmax at the second dimension of the input ma-344 trix. A is the attention output. When multiple 345 attention heads are used, the formulation is similar.

346
We use S to denote the similarity matrix computed 347 by XX T . It can be expressed as a block matrix:

349
Our goal is to encourage the model to focus on the 350 correct matched caption for an input clip, i.e., the 351 attention mass from the video clip to the correct 352 matched caption should be higher than the others.

353
We denote the overall attention score from the input 354 video clip to one of the ASR captions as: The 355 maximum response between the ASR captions to 356 each element in the video can be computed as: We then employ an entropy-based loss: Constrained Attention Loss. The ASR captions are often temporally misaligned with their corresponding clips, simply pre-train a model over these misaligned clip-text pairs may lead to sub-optimal performance. To alleviate this issue, we propose a constrained attention loss that encourages the model to automatically select the best matched ASR caption from a pool of continuous caption candidates. This is achieved by minimizing the entropy of the attentions from the video to the ASR captions. Formally, we denote an input video V as [c 1 , c 2 , ..., c N ], its corresponding ASR captions are denoted as [s 1 , s 2 , ..., s N ], where c i is the i-th clip of V and s i is the ASR caption of c i , N is the total number of clips in the video. For a clip c i , instead of only inputting its associated caption s i , we also include captions from its two neighboring clips, 3 i.e., s i−1 and s i+1 . In most cases, the correct matched caption for the clip is from these three captions. We denote X=[X c i ; X s i−1 ; X s i ; X s i+1 ] ∈ R l×d as the generalized input sequence to each transformer layer (dense captions are ignored for simplicity), where X c i , X s i−1 , X s i , X s i+1 are the embedding matrices correspond to the input clip and three captions. We further simplify the notations as X=[X 0 ; X 1 ; X 2 ; X 3 ]. A single head 3 While our approach works for arbitrary number of neighbors, we use two neighbors to illustrate the idea for simplicity. In fact, we found that, of 100 randomly sampled videos, using two neighbors already covers 95% of the videos with at least one positive matched ASR caption. self-attention operation in the transformer encoder layers can then be expressed as: where softmax(·, dim=1) denotes applying softmax at the second dimension of the input matrix. A is the attention output matrix. When multiple attention heads are used, the formulation is similar. We use S to denote the similarity matrix computed by XX T , it can be expressed using block matrices: S q,r = X q X T r , q, r ∈ {0, 1, 2, 3}.
(2) Our goal is to encourage the model to focus on the correct matched caption for an input clip, i.e., the attention mass from the video clip to the correct matched caption should be higher than the others. To achieve this, we first define the maximum response between the video hidden states X 0 to the ASR captions hidden states X j as: (3) For a single example, we define its constrained attention loss as: This loss formulation is based on entropy minimization (Tanaka et al., 2018;Yi and Wu, 2019), it forces the model to assign high attention scores only to one of the ASR captions, i.e., to peak at only one caption rather than being flat because the one-hot distribution has the smallest entropy. Figrue 3 shows an overview of applying the constrained attention loss. During pre-training, we add this loss to each of the attention heads across all layers, we add these losses along with the MLM loss and video-text matching loss for joint optimization. Meanwhile, as the similarity matrix S is a symmetric matrix, the entropy minimization objective also encourages the correct matched ASR caption to have higher similarity to the video, while forcing the mismatched captions to put more attention on the other ASR captions rather than the video.

Experiments
In this section, we compare our model with state-ofthe-art methods on three video-and-language downstream tasks (e.g., video captioning, text-to-video retrieval, and video question answering) across five datasets. We then present a comprehensive ablation study, where we show that each of our proposed components help improve the pre-training task performance and downstream task performance. Lastly, we also provide an attention visualization example to demonstrate the effect of applying our proposed constrained attention loss.

Datasets and Tasks
Pre-training. We use HowTo100M (Miech et al., 2019) for pre-training. It contains 1.22 million YouTube instructional videos that cover 23.6K instruction tasks (e.g., making peanut butter, pruning a tree). Each video is associated with an English narration automatically transcribed by an Automatic Speech Recognition (ASR) system. On average, each video has 110 clip-caption pairs, with an average duration of 4 seconds per clip and 4 words per caption. We reserve 10K videos for validation, and use the rest of the videos for pre-training.
Video Captioning. We evaluate video captioning on MSRVTT (Xu et al., 2016) and YouCook2  datasets. The task is to generate a text description (a single sentence or a paragraph of multiple sentences) for a given video. Text-to-Video Retrieval. We evaluate text-tovideo retrieval on MSRVTT and YouCook2 datasets, where the goal is to retrieve a relevant video from a gallery of videos given a text query.
(i) MSRVTT is the same dataset as the captioning task. We follow previous work (Yu et al., 2018b;Miech et al., 2019) to use the 7k train+val videos for training and report results on the 1K test set sampled by Yu et al. (2018b). (ii) YouCook2 is the same dataset as the captioning task. We evaluate our model on the clip retrieval task as in previous work (Miech et al., 2019;Zhu and Yang, 2020).

Implementation Details
We use the BERT-base (Devlin et al., 2019)

Comparison to State-of-the-Art
We present our results on three downstream tasks across five datasets, and compare the results against the state-of-the-art methods. All the downstream results are obtained by fine-tuning the same pretrained model that is pre-trained with dense captions and constrained attention loss.   (Zhou et al., 2018), MART (Lei et al., 2020a), COOT (Ging et al., 2020), and MIL-NCE (Miech et al., 2020). PT indicates models with pre-training on HowTo100M.
Video Captioning. We follow Vaswani et al. (2017) to train auto-regressive captioning models, by only allowing the text tokens to attend to tokens that precede them at training. During inference time, we use beam search with beam size 5 to generate captions. For MSR-VTT, we evaluate captioning performance at sentence level. For YouCook2, we follow previous work (Lei et al., 2020a;Ging et al., 2020) to evaluate performance at paragraph-level, where single segment captions are concatenated as a paragraph for evaluation. We use standard metrics BLEU@4 (Papineni et al., 2002), METEOR (Denkowski and Lavie, 2014), Rouge-L (Lin, 2004), and CIDEr-D  to report performance. Table 1 shows the comparison on MSRVTT, our DECEMBERT model achieves significant performance gain over previous state-of-the-art. Notably, DECEMBERT outperforms ORG-TRL  by 1.6% BLEU@4, 2.6% Rouge-L, and 1.4% CIDEr-D, even though ORG-TRL uses a set of strong visual features (appearance, motion, and object) together with a sophisticated graph encoder network and external language model supervision. Table 2 shows the results on YouCook2 captioning task. Overall, DECEMBERT outperforms previous methods across all metrics. Compared to the strong baseline method MART+COOT+NIL-NCE (Lei et al., 2020a;Ging et al., 2020;Miech et al., 2020) PT, that uses HowTo100M videos for pre-training followed by a designated hierarchical modeling training, our approach still shows better performance with a reasonable margin. This shows the effectiveness of our pre-training strategy.
Text-to-video Retrieval. We train text-to-video retrieval models similar to the way we perform video-text matching, where we sample a negative caption 50% of the time. We use average recall at K (R@K) and median rank (MdR) to report perfor-  Table 3: Text-to-video retrieval results on MSRVTT 1k test set (Yu et al., 2018b). PT indicates models with pre-training on HowTo100M (or on HowTo100M+TV shows Liu et al., 2020a) for HERO).
We gray out models that used extra ASR features for a fair comparison.   (Klein et al., 2015), HowTo (Miech et al., 2019), COOT (Ging et al., 2020), MIL-NCE (Miech et al., 2020) mance on the retrieval tasks. We show MSRVTT text-to-video retrieval in Table 3. Overall, our approach achieves the best performance. Compared to the pre-trained models HowTo (Miech et al., 2019), ActBERT (Zhu and Yang, 2020), and HERO (Li et al., 2020b), DECEMBERT achieves strong performance with a reasonable margin. It outperforms HERO by 0.7% R1, note that HERO is pre-trained with extra TV show videos Liu et al., 2020a) in addition to the HowTo100M videos that we use. Moreover, DE-CEMBERT is also quite competitive compared to the HERO w/ ASR model that uses additional ASR features during finetuning. For YouCook2 text-to-video retrieval results shown in Table 4, our approach also show better performance compared to the pre-trained models HowTo and COOT+MIL-NCE. Notably, it outperforms previous state-of-theart COOT+MIL-NCE by 7.5% R@10.
Video Question Answering. We use a two-layer MLP followed by a softmax layer for open-ended question answering, where we optimize the probability of choosing the correct answer from a large pool of candidate answers. We report accuracy to Method Accuracy ST-VQA (Jang et al., 2017) 30.9 Co-Memory (Gao et al., 2018) 32.0 AMU  32.5 Heterogeneous Memory (Fan et al., 2019) 33.0 HCRN  35.6 DECEMBERT 37.4 measure the QA performance. We show MSRVTT-QA results in Table 5 where our approach outperform all the baseline methods by a large margin. Compared to HCRN (Le et al., 2020) which employs a complicated hierarchical reasoning module, our approach achieves 1.8% performance gain, achieving a new state-of-the-art for the task.

Analysis
Ablation Study. We present ablation study on our pre-training strategies, on both the pre-training tasks and the MSRVTT captioning downstream task. We report ablation results on our 10K holdout HowTo100M videos for pre-training tasks, i.e., masked language modeling (MLM) accuracy and video-text matching accuracy. Because we use MLM for both dense captions and the original ASR captions, we report their accuracy separately. The results are shown in Table 6. To understand how the pre-training strategies affect the downstream performance, we also perform downstream finetuning from pre-trained models using these different pre-training strategies. The results are shown in Table 7. Compared to the basic model that uses only a single paired ASR caption with each clip for training, we observe the the variant that takes three ASR captions achieves significantly higher accuracy in MLM and video-text matching. Adding dense captions and constrained attention loss further improve the performance. Overall, the same trend also holds true for the downstream performance on MSRVTT captioning and QA tasks. The best captioning and QA models are finetuned from the model pre-trained using both the dense captions and the constrained attention loss. Compared to the basic model with only MLM and video-text matching, our best models achieve a significant performance gain: e.g., 3.3% BLEU@4, 3.1% CIDEr-D for captioning, and 2.3% Accuracy for QA.
Qualitative Results During pre-training, we apply our proposed constrained attention loss to every    Figure 4: Attention visualization for models with and without constrained attention loss. After adding constrained attention, the attention mass concentrated to the ASR caption (e.g., AC3) that best matches the video content and the dense captions. These attention maps are taken from an attention head of the 10-th layer of the transformer model. attention heads across all layers. In Figure 4, we compare the attention maps from models with or without the proposed constrained attention loss during pre-training. As we found the attention weight distributions (not absolute values) on different layers look similar to each other, we randomly chose the 10-th layer to showcase the effect of adding constrained attention loss. We observe that after adding constrained attention loss as a regularization, the attention mass concentrated to the best-matched ASR caption rather than distributed to all the captions.

Conclusion
In this work, we propose DECEMBERT as an improved pre-training method for learning from noisy, unlabeled instructional videos. Specifically, we propose adding automatically-extracted framelevel dense captions as an auxiliary text input for learning better video and language associations. We also propose a constrained attention loss that forces the model to automatically focus on the bestmatched caption from a pool of misalignment caption candidates via entropy minimization. Comprehensive experiments on three popular video and language tasks (i.e., text-to-video retrieval, video captioning, and video question answering) across five datasets demonstrate the effectiveness of DE-CEMBERT compared to existing approaches. We also provide detailed ablation study and visualization to quantitatively and qualitatively examine the impact of our added components.


extfieldsofstudy:
Computer Science
Biology
Medicine

text:
Pheniqs 2.0: accurate, high-performance Bayesian decoding and confidence estimation for combinatorial barcode indexing

Background Systems biology increasingly relies on deep sequencing with combinatorial index tags to associate biological sequences with their sample, cell, or molecule of origin. Accurate data interpretation depends on the ability to classify sequences based on correct decoding of these combinatorial barcodes. The probability of correct decoding is influenced by both sequence quality and the number and arrangement of barcodes. The rising complexity of experimental designs calls for a probability model that accounts for both sequencing errors and random noise, generalizes to multiple combinatorial tags, and can handle any barcoding scheme. The needs for reproducibility and community benchmark standards demand a peer-reviewed tool that preserves decoding quality scores and provides tunable control over classification confidence that balances precision and recall. Moreover, continuous improvements in sequencing throughput require a fast, parallelized and scalable implementation. Results and discussion We developed a flexible, robustly engineered software that performs probabilistic decoding and supports arbitrarily complex barcoding designs. Pheniqs computes the full posterior decoding error probability of observed barcodes by consulting basecalling quality scores and prior distributions, and reports sequences and confidence scores in Sequence Alignment/Map (SAM) fields. The product of posteriors for multiple independent barcodes provides an overall confidence score for each read. Pheniqs achieves greater accuracy than minimum edit distance or simple maximum likelihood estimation, and it scales linearly with core count to enable the classification of > 11 billion reads in 1 h 15 m using < 50 megabytes of memory. Pheniqs has been in production use for seven years in our genomics core facility. Conclusion We introduce a computationally efficient software that implements both probabilistic and minimum distance decoders and show that decoding barcodes using posterior probabilities is more accurate than available methods. Pheniqs allows fine-tuning of decoding sensitivity using intuitive confidence thresholds and is extensible with alternative decoders and new error models. Any arbitrary arrangement of barcodes is easily configured, enabling computation of combinatorial confidence scores for any barcoding strategy. An optimized multithreaded implementation assures that Pheniqs is faster and scales better with complex barcode sets than existing tools. Support for POSIX streams and multiple sequencing formats enables easy integration with automated analysis pipelines. Supplementary Information The online version supplementary material available at 10.1186/s12859-021-04267-5.

Background
High-throughput next-gen bulk sequencing with multiplexed sample barcodes is now standard practice to increase throughput and reduce sequencing costs, and single-cell applications are rapidly proliferating and evolving [1]. The advent of barcodes to tag individual cells and molecules from which sequence reads originate both enhances resolution and helps control for quantification biases. Yet indeterminate reads that are discarded, and uneven barcode distributions that differ from expectation, are common and decrease both accuracy and sensitivity.
The fast pace of innovation in sequencing technologies and experimental designs continuously presents new challenges to the classification of sequence reads. Increasingly complex barcoding schemes are being devised to accommodate novel experimental designs, and combinatorial cellular indexing protocols involving several successive rounds of barcoding expand the potential space exponentially [2,3]. Just over the horizon, multimodal profiling-the simultaneous measurement of gene expression, protein abundance, chromatin state, spatial transcriptomics, and/or CRISPR-based readouts (e.g. lineage tracing, genetic screens)-is poised to become a new industry standard [1]. Third-generation platforms overcome some of the limitations of short-read sequencing by providing very long reads, but current long-read sequencers operate with very high error rates of 15-40%. To compensate, these are often complemented with high-fidelity short-read sequences or self-corrected using many-fold coverage [4]. Multiplexing with barcoding is now emerging as a way to increase throughput and lower costs for these platforms as well.
Several tools are currently available for decoding and classifying barcodes, an essential task for demultiplexing pooled bulk sequence libraries and for assigning reads to individual cells in single-cell workflows. However, existing tools for decoding index tags do not provide flexible support for the rising complexity of novel barcoding schemes. As a result, numerous custom solutions to handle different barcoding schemes are being implemented downstream of standard demultiplexing software, often geared to a specific application and implemented using convenient scripting languages such as R or Python. Various integrated workflows focusing on scRNA-seq analysis now bundle identification of cellular barcodes and molecular barcodes (UMIs) with transcript quantification and other downstream analyses to identify and study different cell types, including CellRanger [5], Seurat [6], Salmon-Alevin [7], and BUStools [8]. Such workflows could benefit from preprocessing by an efficient and flexible decoder that natively supports any arbitrary experimental design and can be easily integrated into automated pipelines. As sequence applications diversify, decoupling barcode classification from downstream analysis tasks becomes increasingly desirable, both to simplify workflows and to encourage the development of community standards for benchmarking and best practices.
Sequencing platforms generally tie in demultiplexing as a preprocessing step that is not directly accessible to users. The most widely used first-generation tool for sample demultiplexing is Illumina's bcl2fastq, which combines basecalling with sample demultiplexing. bcl2fastq accepts input only in the proprietary Illumina BCL format and is specifically geared toward sequence data from Illumina platforms. It relies on a naïve decoding method based on exact string matching with up to one mismatch, in other words a simple minimum Hamming distance decoder, and quality assessment procedures that are not obviously accessible to end-users. bcl2fastq can also generate FASTQ files without demultiplexing, but most other tools that classify sequences using barcodes, such as Picard [9], also use simple minimum distance decoding.
Standalone, peer-reviewed, classifiers include deML [10], Bayexer [11], and Axe [12]. deML is capable of handling a single barcode set with either one or two segments. While it consults basecalling qualities and reports classification scores in Sequence Alignment/Map (SAM) [13] auxiliary tags, deML does not accurately reflect the probability of correct classification for two reasons: it estimates maximum likelihood only for the top candidates that are within a short Hamming distance, and it operates under restrictive assumptions that do not hold in most complex cellular indexing designs-i.e. that barcodes are uniformly distributed and that contaminating sequences are extremely rare. Bayexer attempts to train a naïve Bayes classifier by studying the error pattern when the insert sequence is shorter than the read length and thus provides a second observation of the barcode. Although this approach can potentially increase accuracy in those specific cases, it is not applicable to general barcode decoding and the tool fails to produce output when such redundancy is not present. Axe uses a set of pre-computed prefix trees to find a match within a given Hamming distance and can partially handle barcodes that differ in length. Although this method can be very fast, it ignores quality scores and is highly sensitive to upstream errors in the prefix, and so sacrifices accuracy.
None of the above tools account for the prior distribution of barcoded samples (which is often nonuniform) or explicitly account for noise (i.e. contaminating or indeterminate sequences), nor do they compute or report the posterior classification probability for individual reads. They also lack the ability to address arbitrary offsets within read segments, decode barcodes with more than two components, or handle multiple types or combinations of barcodes, and thus often require custom pre-or post-processing.
Pheniqs overcomes many of the limitations of other decoders by taking into account key aspects of current decoding requirements: scalability, assumptions about the number of tags and their location, integration of richer metadata, and the ability to explicitly account for basecalling quality scores, uneven barcode distributions, and presence of indeterminate sequences.

Implementation
Pheniqs (PHilology ENcoder wIth Quality Statistics, pronounced phoenix) combines a generic and extensible approach to barcode decoding with flexible configuration options that easily accommodate custom experimental designs. It implements both a standard minimum distance decoder (MDD) based on Hamming distance and a probabilistic decoder (PAMLD). PAMLD consults base-calling quality scores as well as priors to compute the full posterior decoding probability for classification, rather than a simple maximum likelihood estimate.

Decoding with the posterior probability
Classification based on barcodes involves extracting a subsequence r from an observed read, along with the basecall quality scores associated with the individual nucleotides in r, and decoding the original sequence s. Let r ∈ {A, C, G, T , N } n be an observed sequence of length n extracted from the read and B ⊆ {A, C, G, T } n a given set of distinct barcodes where each b ∈ B identifies an individual class. A decoder is denoted as a decision function φ : {A, C, G, T , N } n � → B ∪ ε , where ε is a decoding failure for an indeterminate sequence s / ∈ B. A maximum likelihood decoder will identify the barcode b ∈ B which maximizes the posterior probability that b was sequenced given that r was observed.
Applying Bayes' rule we can compute P(b|r) using where P ε is the prior probability of encountering indeterminate sequences and P(r|b / ∈ B) is the probability of observing a particular such sequence. The Phred-adjusted maximum likelihood decoder (PAMLD) implemented by Pheniqs solves Eq. 2 by computing P(r|b) for each b ∈ B from the basecalling quality scores [14]. P(b), the expected fraction of reads identified by b, can be either provided a priori by the user or estimated directly from the data. In the absence of any prior information about potential sequence composition (base distribution or GC bias), we can only assume indeterminate sequences occur with maximum entropy so P(r|b / ∈ B) = 1/4 n . Such reads may arise from spiked in controls used for instrument calibration, contamination during library preparation or other unknown factors such as defective sequencing kits. Realistically, however, not every sequence in {A, C, G, T } n is equally likely to appear in sequencing, indeterminate entropy is lower, and P(r|b / ∈ B) > 1/4 n . Empirical studies can determine a more refined lower bound for P(r|b / ∈ B) . Pheniqs accommodates such refinements to the noise model by allowing advanced users to manually set this value.
When P(r|b) < P(r|b / ∈ B) , the initial evidence supporting the classification provided by the conditional probability is inferior to that provided by a random sequence, indicating that the b recovered in Eq. 1 cannot be distinguished from noise. The noise filter considers those a decoding failure without further consideration.
Reads that pass the noise filter are evaluated by the confidence filter, which compares P(b|r) to a user-provided confidence threshold C for the minimum acceptable probability of a correct decoding and declares a failure if P(b|r) ≤ C . The probability of a decoding error is Directly estimating P(b|r) allows Pheniqs to report intuitive classification confidence scores for every read. Deriving a confidence score for a combinatorial barcode, made up of several independent components, requires to simply multiply the confidence scores of the individual components. The governing threshold C allows researchers to choose between assignment confidence and yield of classified reads and defaults to 0.95. The PAMLD decoding workflow is summarized in Fig. 1B. By contrast, deML [10] assumes that P ε is infinitesimally small and that samples are uniformly pooled (and thus equally likely), thereby suggesting that for every b ∈ B Under such conditions P(b|r) ∝ P(r|b) and Eq. 1 can be simplified to While such assumptions simplify maximum likelihood estimation of b , they are often grossly imprecise. For example, the relatively low yield in (e.g. single-cell) experiments that rely on several layers of combinatorial indexing often results in an extremely uneven barcode distribution, with P ε representing a significant portion of the sequenced DNA. Furthermore, implementations that refrain from computing P(b|r) cannot report the posterior classification probability or a confidence score for combinatorial barcodes.
Pheniqs decoding pipeline architecture. A Pheniqs requires as input sequence data files in any standard format and (if not using default parameters) a JSON configuration file. Python API tools (not shown) assist with IO management and can automatically generate an initial configuration using metadata from an Illumina run directory. Pheniqs evaluates each configuration component to determine how the data should be processed and to ensure that all required directives are present and properly specified. Any validation failures trigger clear, explicit error messages. Prior distributions of expected barcodes either derive from initial sample proportions as given (e.g. per a sample sheet), or are estimated directly from the data during a preliminary PAMLD decoding run. Barcode tokens are extracted from read segments using transform directives and then passed to a decoder (PAMLD or MDD). New decoding algorithms may be implemented as derived classes. Decoded barcodes and quality scores are written to specific SAM auxiliary field for each barcode type. Pheniqs can emit FASTQ files split by sample barcode, but SAM format is preferred since it preserves all associated metadata, and binary (BAM) and compressed (CRAM) versions produce considerably smaller files. POSIX integration allows direct piping to automated workflows, and support for real-time translation of file formats enables teeing to multiple outputs (thus avoiding the need to write temporary files). A JSON-encoded run report is also generated that provides summary statistics for the analysis. B PAMLD noise and confidence filters. Reads with a lower conditional probability than random sequences fail the noise filter and are classified as noise without further consideration. Reads with a posterior probability that does not meet the confidence threshold fail the confidence filter; these reads are classified, but they are marked as qc fail so the confidence threshold can be reconsidered at a later stage

Estimating the prior distribution
Statistics from a preliminary PAMLD decoding run can be used to estimate the relative proportions of the individual barcodes P(b) for each b ∈ B and the noise P ε from the data. The high confidence estimator bundled with Pheniqs estimates the relative proportions from the high confidence reads alone, assuming that low confidence reads (those that passed the noise filter but failed the confidence filter) and high confidence reads (those that passed both filters) come from the same distribution.
Let S ε be the number of reads rejected by the noise filter, S b the number of reads classified to b with confidence higher than C, and S B = b∈B S b . A high confidence estimator for the noise prior is and for an individual barcode is The high confidence estimator is a general purpose estimator, but Pheniqs can be used with any prior estimates devised by the user.

Software architecture
Pheniqs is distributed as a compiled binary with a command-line interface that accepts a JSON encoded configuration file (Fig. 1A). Stable releases are also packaged in Bio-Conda. To accommodate a rapidly changing landscape, Pheniqs is designed to be easily extensible with alternative error models and additional decoder implementations. An efficient codebase with robust input validation and comprehensive documentation supports individual installations and large-scale production facilities alike.
Using a familiar syntax that mimics Python array slicing, Pheniqs can decode multiple barcodes located anywhere in any sequence read. It extracts tokens from multiple read segments by addressing either the 5' end, 3' end, or both (and optionally reverse complemented) to construct the output template segments and the sample, cellular and molecular barcodes (Fig. 2). For convenience, Pheniqs provides reusable definitions for several standard sample barcode sets that can be imported into any configuration file. Additional types of barcodes can easily be defined by declaring them in the configuration file (e.g. barcodes for split-pooling, antibody tags, spatial sequencing, etc.). This generic approach allows for arbitrary manipulation of sequence tokens that accommodates any potential barcoding scheme and obviates the need for pre-and post-processing for most experimental designs.
By directly interfacing with the low level HTSlib [15] C API Pheniqs can read, write, and manipulate either uncompressed or gzip compressed FASTQ files as well as the SAM file format or its binary compressed variants BAM and CRAM. Unlike FASTQ, the SAM format can encode sequencing data in a single, smaller file that supports richer metadata annotations. To allow multithreaded performance to scale linearly with core count, Pheniqs carefully synchronizes the many threads that read, decode and write with a consumer/producer model [16]. This allows threads that compute the posterior probabilities to work without waiting for threads that read and write. Each input feed uses two independent memory buffers: one for accepting incoming reads from the input file and one for supplying reads to the barcode decoding threads. When the first is full and the second is empty, a special thread momentarily locks both buffers and switches between them so that all operations may proceed with no interruption. The same principle is mirrored for output files. Since buffers may only be modified by one operation at a time to prevent data corruption, this design allows Pheniqs to concurrently receive input from multiple files, decode barcodes with multiple threads, and write output to multiple files, all with optimal efficiency. When integrated into a pipeline, Pheniqs can take advantage of POSIX standard streams to avoid the speed and storage bottlenecks associated with reading and writing temporary files.
Pheniqs reports the decoded sample, cellular, and molecular barcodes as well as their corresponding quality scores and the posterior decoding error probability in SAM auxiliary fields. It can associate standard SAM read groups with sample barcodes and can optionally perform an exhaustive quality assessment during processing that it includes in the final report. Each token comprises three colon separated components, "segment:start:end". Per Python array slicing syntax, the start coordinate (offset) is inclusive and the end coordinate is exclusive. Start and end coordinates default to 0 and the end of the segment, respectively. C Template read segments, observed and most likely inferred barcode sequences, quality scores, and error probabilities are emitted to designated SAM fields. The reported error for each barcode is one minus its estimated confidence (the posterior decoding probability); for a combinatorial barcode, the reported error is one minus the product of the confidence scores for each component

Results and discussion
We used a variety of performance metrics to evaluate the decoding accuracy and computational efficiency of Phred-aware maximum likelihood decoding with Pheniqs (PAMLD), simple maximum likelihood estimation with deML, and minimum distance decoding (MDD, as implemented by Pheniqs). We used a semi-synthetic short-read dataset with a known true barcode set to measure accuracy across a range of error rates, and data from one lane of an Illumina NovaSeq run (containing >11 billion reads) to compare run time and memory usage.

Accuracy
Decoding accuracy was analyzed using semi-synthetic barcoded sequence reads generated from the run published with deML [10]. To establish a ground truth for testing purposes, we simulated barcoded sequence reads by replacing the barcode nucleotides in each read with a perfect barcode sequence sampled from a known prior distribution. To simulate noise, we replaced a barcode with a sequence from a random offset in the genome of PhiX174, a 5386nt DNA bacteriophage with 45% GC content [17]). We used PhiX174 sequences because Illumina sequencers require balanced and random nucleotide composition for instrument calibration and quality control, and PhiX174 DNA is often spiked in as a control for this purpose at concentrations of 1-5% or up to 40% for low-complexity libraries. PhiX174 reads do not carry barcodes and should not be classified but instead labeled as Undetermined during demultiplexing. However, PhiX174 sequences can sometimes contribute to noise contamination because they resemble an expected barcode by chance and must be removed in a downstream step by read sequence alignment. Notably, a recent study has found that 1000 genomes in the Integrated Microbial Genomes Database are contaminated with PhiX174 sequences [18], suggesting that these are a common source of noise in Illumina sequence data.
We simulated sequencing errors by introducing a substitution at a nucleotide according to the basecall quality score and substitution frequencies made available with LRSim [19]. For this analysis we simulated substitution errors only since current short read platforms generate indel errors at a much lower rate than substitutions [20]. Finally, to simulate reads with different overall error rates, we recalibrated the quality scores produced in the first step and then simulated substitution errors on the recalibrated data. Additional file 1: Figure S1 shows the calibrated quality score distributions of each simulated dataset. The modular architecture of Pheniqs allows for the addition of alternative error models that may be better suited for sequencing platforms with different error characteristics and could be tested similarly.
We used the above datasets to evaluate classification accuracy across a range of error rates for Pheniqs MDD with default settings (MDD); deML with default settings (deML); and Pheniqs PAMLD with default settings (PAMLD uniform), true priors (PAMLD true), and high confidence estimated priors (PAMLD estimated). Pheniqs can compute estimated priors in a preliminary run by updating an initial set of priors using observed barcode frequencies (Fig. 3A shows the true sample barcode distribution in the dataset). High confidence estimated priors were computed here using statistics from a preliminary PAMLD run with the default 0.95 confidence threshold, 0.05 noise, and uniform barcode priors as input. We evaluated each barcode and the noise class as a binary classifier, so a correct assignment was counted as a true positive (TP), while an incorrect assignment was counted as a false negative (FN) for the correct class and as a false positive (FP) for the incorrectly assigned class. Reads marked as failing quality control (Fig. 1B) Fig. 3 Decoding F-score. A True frequency distribution of individual barcodes in the synthetic data. The control barcode (the only one > 3%, comprising 32% of the data used for evaluation) and noise (9%) were omitted for visual clarity. B All probabilistic decoders outperform minimum distance decoding by a wide margin, with differences becoming more pronounced as the error rate increases. C Among the probabilistic decoders, all configurations of PAMLD are more accurate than deML. The high confidence estimated prior performs nearly as well as the true prior classified to the noise class for this analysis. We then summed up the values from all classes and computed the false discovery rate (FDR), miss rate (MR) and F-score (harmonic mean of the precision and recall).
The resulting analysis showed that the probabilistic decoders consistently outperform MDD, which has very little resilience to errors and noise (Fig. 3B). Differences in accuracy become more pronounced as the substitution rate increases: at a rate of 0.05, the F-score for MDD is nearly 10% lower than other decoders. PAMLD with uniform priors is more accurate than deML, and high confidence prior estimation provides further gains that closely approximate performance with the true prior (Fig. 3C). Thus, computing the full posterior probability outperforms simple maximum likelihood estimation, even under the same assumption of a uniform prior, and estimating the true prior distribution approaches near-optimal decoding.
The effect of the noise filter is illustrated in Fig. 4, which shows the error in high confidence prior estimation for true barcode classes binned by their relative abundance across a range of substitution error rates. The difference between true and estimated priors is negligible at low overall error rates, but as basecalling quality decreases it becomes difficult to distinguish true barcodes from noise since P(r|b) for a true barcode is more likely to fail the noise filter. As a result, individual barcode classes are increasingly underestimated and P ε is correspondingly overestimated.
To examine the sources of performance gains at a more fine-grained level, we plotted FDR, MR and F-score statistics separately for classified, classifiable, and unclassified reads across a range of error rates. Classified reads represent true barcodes or noise reads that were classified to a real barcode. These include correct assignments (TP), noise or barcode reads assigned to the wrong barcode class (FP), and true barcodes not assigned to their proper class (FN). While all decoders perform reasonably well on classified reads overall (Additional file 1: Figure S2) Fig. 4 Error in high confidence prior estimation for true barcodes at different overall error rates. Results binned by relative barcode abundance reveals the tradeoff between noise and correct classification. As basecalling quality deteriorates, distinguishing true barcodes from noise becomes increasingly difficult, resulting in underestimation of the true barcode priors and overestimation of the noise prior P ε estimated priors consistently results in a lower rate of misclassified reads (lower FDR) and recovers more reads (lower MR) than other decoders. Filtering noise helps Pheniqs outperform deML in any configuration, primarily by reducing FDR (Additional file 1: Figure S2A). In the lower error range relevant to most Illumina runs ( ∼ 1/1000), PAMLD shows a lower FDR than even MDD (Additional file 1: Figure S2B). The FDR is flat for MDD because it ignores any reads with more than one mismatch, and for the same reason the miss rate climbs dramatically relative to the other decoders as the error rate increases.
Since datasets now contain increasingly large numbers of multiplexed samples or individual cells, the ability to accurately identify rare barcode classes is of high interest. We used read counts for each barcode class (Fig. 3A) to examine performance for classified reads binned by their relative abundance: very low (< 0.1% of reads), low (0.1-0.3%), similar to uniform (0.3-3%) and overrepresented (> 3%; here a single control barcode accounted for 32% of all reads). Across the entire spectrum, PAMLD with estimated or true priors shows better overall performance (F-score) than either deML or PAMLD with uniform priors (Additional file 1: Figure S3). For more abundant barcode classes, gains are mainly due to higher sensitivity (lower MR). For lower abundance barcodes (< 0.3% of total reads), PAMLD makes ∼ 10-fold fewer incorrect assignments than deML (lower FDR) with only a modest loss of sensitivity. Thus PAMLD is especially beneficial for the detection of rare barcodes.
Indeterminate barcodes are not uncommon in short-read datasets and can greatly reduce the yield of usable data. We found that PAMLD improves accuracy for both classifiable reads (true barcode reads, correctly classified or not) and unclassified reads (reads that are noise or fail quality control). For classifiable reads, both FDR and MR are consistently lower, leading to improved F-scores (Additional file 1: Figure S4; examples in Fig. 5A-C). For unclassified reads, probabilistic decoders have a lower FDR (Additional file 1: Figure S5) and also classify many fewer true barcodes as noise than MDD (Additional file 1: Figure S5; examples shown in Fig. 5A, B, D). The PAMLD noise filter rejects reads when the evidence for the barcode with the highest posterior is no better that for a random sequence (Fig. 1B). This is arguably a desired property since such reads have very weak evidence for classification. When the overall error rate is low, PAMLD errs on the side of caution and classifies slightly more true barcodes as noise than deML (FDR, Additional file 1: Figure S5A). On the other hand, PAMLD misses many fewer true noise reads (lower MR) than deML (Additional file 1: Figure S5A; example shown in Fig. 5D), and in the range of error rates for Illumina sequencers filters true noise better than even MDD (lower MR, Additional file 1: Figure S5B).
In summary, we find that using prior knowledge of barcode frequency and sequence quality statistics, combined with noise filtering, increases the recovery of true barcodes and reduces the number of misclassified reads. These benefits are most pronounced for barcodes present at low frequency and for data with high error rates. Thus probabilistic, quality-aware decoding offers distinct advantages for classifying short-read datasets that are highly complex and/or use combinatorial barcoding strategies. Pheniqs may also prove advantageous for third-generation single-molecule sequencing platforms that provide long sequence reads at much higher error rates.

Runtime speed and memory
To evaluate speed and memory usage we used a single lane from an Illumina NovaSeq, the highest throughput instrument available today, containing 94 multiplexed libraries with standard dual i7 and i5 barcodes. 151 cycles were sequenced on each of the two template segments and 8 cycles on each of the i7 and i5 index segments.
Benchmarking for speed (Fig. 6A) and memory (Fig. 6B) was executed on an Intel Xeon CPU E5-2690 v4 @ 2.60 GHz with 14 cores and 28 threads. Basecalling the lane with bcl2fastq (without demultiplexing) took 47 min and yielded 11,578,868,372 dualindexed paired-end reads that passed quality filtering. bcl2fastq produces reads with segments split over four gzip compressed FASTQ files that were used as input to Pheniqs. Pheniqs runtime benchmarks show that output format encoding greatly impacts speed. With null output Pheniqs decodes the barcodes and collects statistics (for instance to be used for prior estimation) but does not write any output. The null benchmark completed in less than half the time of all others, demonstrating that writing output files is the ratelimiting factor for performance. Pheniqs performs fastest when producing interleaved BAM output and demultiplexed the NovaSeq run in 3 h and 10 min. Even computing the full posterior probability, Pheniqs scales almost linearly with the number of available cores and is at least 20 times faster than deML, which lacks support for multithreading. Mismatched nucleotides in the Observed sequence are marked in red. D In this example the read was noise and should have been rejected and assigned to the undetermined bin. PAMLD initially classifies it to a barcode with 6 mismatches, but it rejects the classification because the error probability is above 9%. deML incorrectly classifies the read. PAMLD's decision is influenced by the prior for the barcode it chooses, which is about 10 times higher than the barcode chosen by deML deML could only produce FASTQ output with FASTQ input, so we could not test BAM output.

Future work
We can envision a variety of ways to enhance the performance of Pheniqs. Our initial focus will be to facilitate integration into standard analysis workflows. To assist with configuration, we are building a library of barcode configuration templates for common sequencing kits and experimental designs. The Pheniqs website currently includes vignettes for configuring standard Illumina sequencing runs, single-cell RNA sequencing using the Fluidigm platform, and two plate-based split-pooling methods for singlecell RNA-seq: sciRNA-seq [2] and SPLiT-seq [3]. We also plan to add vignettes for other types of single-cell profiling, as well as multimodal profiling, spatial transcriptomics, and other novel sequencing applications as they arise. One limitation of Bayesian decoding is that computing the posterior probability requires knowing the list of expected barcodes in advance. To overcome this problem, the same strategy used by Pheniqs to estimate priors for a known set of barcodes could be extended to an unknown set of barcodes. First, a preliminary run configured with a whitelist (e.g. a list of all known cellular barcodes in a single-cell sequencing kit) can be used to estimate the relative abundances of observed barcodes. A shorter list of barcodes can then be extracted from the preliminary run report by placing a threshold on the abundance of observed barcodes, which may then be decoded in a second run using the imputed priors. Providing decoding quality scores for whitelisted cellular barcodes based on the full posterior probability will allow improved estimation of their relative abundance, thus increasing accuracy and sensitivity for single-cell applications. An overall classification quality score combining multiple types of barcodes can then be computed, which will be easy to both report and understand. Since the complexity of computing the posterior is linearly correlated with the size of the barcode set, however, computing  Fig. 6 Speed and memory benchmarks. One lane of an Illumina NovaSeq run was analyzed. The two letter codes describe the output layout: S for split and I for interleaved, first for library and second for segment. A Pheniqs with PAMLD generated interleaved BAM output in 3:10 h. CRAM is much more complex than BAM and employs several compression algorithms that are more aggressive than gzip to produce smaller files, so writing CRAM output took slightly longer as expected. Pheniqs scales almost linearly with the number of available cores and is at least 20 times faster than deML, which took almost 80 h to complete. B Pheniqs memory consumption increases linearly with the number of output files, since each is allocated separate IO buffers, but even with 200 output files and generous buffers Pheniqs still used less than 1 GB of memory priors for a very large whitelist may become impractically slow. To address this, we are considering alternative strategies to reduce the complexity of the problem in such cases.
Another issue that Pheniqs currently does not address is error correction for UMIs (unique molecular identifiers)-barcodes that tag individual molecules in a library, which are used to identify PCR duplicates and to quantify the abundance of distinct molecular species. Since reads classified to a single combination of sample, cellular and molecular barcode are assumed to be a clone of the same biological sequence, the barcodes are not independent, making computing the full posterior probability unfeasible. To incorporate error correction for UMIs, we are looking into heuristic algorithms that rely on established peer-reviewed methods.
We are also interested in applying Pheniqs to data from other sequencing platforms. Performance evaluations of PAMLD on synthetic data show that gains in decoding accuracy become more pronounced as the rate of substitution errors increases. This suggests that Pheniqs could greatly enhance the analysis of sequence data with high error rates, such as third generation single-molecule sequencing platforms, which currently operate with error rates in the range of several percent [21][22][23]. In order to apply PAMLD to PacBio and Oxford Nanopore sequencing, we will need to incorporate support for insertions/deletion errors, which are more common on these platforms (particularly at homopolymers). We thus plan to evaluate performance and to investigate alternative noise models for these sequencing technologies.
Finally, while barcode decoding quality can have profound impacts on data quality, this issue has not so far received widespread attention. To address this, we advocate for working toward common benchmarks for barcode decoding quality, which would be tremendously useful for the development of community standards for evaluation and reporting conventions.

Conclusion
We show that barcode classification using full posterior probabilities with noise filtering is more accurate than other available methods. We provide a multithreaded software package with comprehensive input validation, Pheniqs, that is faster and more scalable than existing tools. The probability model implemented by Pheniqs accounts for both erroneous codewords and non-codeword random noise, can handle arbitrarily complex barcoding designs, and generalizes to multiple combinatorial tags. It relies on intuitive confidence thresholds for fine-tuning decoding accuracy and reports decoding confidence scores and barcode sequences for individual reads by populating standardized SAM format auxiliary fields. Pheniqs is designed for integration into automated analysis workflows and can be extended with new error models and alternative decoders. An efficient implementation, coupled with comprehensive documentation and a suite of helper tools, supports both individual users and core facilities alike. These combined features offer a new level of efficiency and flexibility for barcode decoding that is widely applicable to current experimental designs and is easily adaptable to the rapidly evolving landscape of sequencing applications.