Skip-Chain Time Warping: Within-Video Consistency for Weakly Supervised Action Alignment

When a model learns to segment a cooking video using only the ordered list of actions it contains, it has to discover where each action starts and stops. The standard approach is dynamic time warping (DTW), an algorithm that finds the best order-preserving way to stretch a sequence of video frames against a sequence of action labels. DTW makes each alignment decision by looking only at the neighbouring cell of its table. As a result, when the same action appears twice in one video, say "pour milk" early and again near the end, the two occurrences are aligned independently. Nothing ties them to each other. Each is matched only against a dataset-wide notion of what "pour milk" looks like, not against the other occurrence in the same kitchen, with the same mug and the same lighting.

Text labeling ran into the same problem years ago. Taggers that look only at neighbouring words gave a gene name one label in one sentence and a different label later in the same abstract. Skip-chain models fixed this by adding edges that link repeated mentions directly. We propose the same move for elastic alignment. We add "skip edges" between transcript positions that carry the same action, and these edges reward the frames assigned to those positions for looking alike within the video. We show the resulting non-local alignment problem can be solved exactly by alternating two steps, each of which is an ordinary DTW pass. The method can be trained end to end by differentiating along the single best alignment path.

Core Claim

The long-range dependency that matters in transcript-supervised alignment is a dependency between alignment decisions, not between input features. Making the frame encoder more global, for example by replacing a recurrent network with self-attention, gives every frame access to every other frame. It still does not tell the model which distant frames will be assigned to the same action. A coupling term placed inside the alignment objective can express exactly that. We claim this term reduces a specific, measurable error: one occurrence of a repeated action aligned well while its twin is misaligned. We further claim it does so beyond what dataset-wide shared prototypes already achieve.

Concretely, let $x_1,\dots,x_T$ be frame features and $a_1,\dots,a_K$ the ordered transcript. A monotone alignment $W$ assigns each frame $t$ to a transcript position $k(t)$. For each action label $a$ that occurs more than once, introduce a per-video appearance center $m_a$. We minimize

$$E(W, m) = \sum_{t=1}^{T} d\big(x_t, p_{a_{k(t)}}\big) + \lambda \sum_{t:\, a_{k(t)} \in R} \big\|x_t - m_{a_{k(t)}}\big\|^2,$$

where $d$ is the usual frame-to-prototype cost, $p_a$ is a learned dataset-wide prototype for action $a$, $R$ is the set of repeated labels in this transcript, and $\lambda$ sets the strength of the skip coupling.

The second term is the frame-level form of a pairwise penalty between occurrences. Summed over frames, it equals the squared distances between each occurrence's mean feature and the shared center, scaled by segment length, plus a within-segment spread term. Minimizing over $m$ therefore pulls the occurrences together.

The objective cannot be solved by a single DTW pass, because $m$ depends on the alignment. Once $m$ is fixed, however, it becomes a plain DTW unary cost. Once $W$ is fixed, the optimal $m_a$ is simply the mean of the frames assigned to $a$. Alternating the two steps never increases $E$, and each step costs the same $O(TK)$ as one ordinary alignment.

Relation to Prior Work

Two lines of work motivate the proposal. Recognizing Biomedical Named Entities Using Skip-Chain Conditional Random Fields adds edges between similar tokens to a linear-chain tagger. This raised F-score from 83.29% to 84.67% on BioCreAtIvE II and removed over 70% of the errors correctable by consistency. It also showed that randomly placed edges are useless, at 2.15% correct edge precision. This is a constraint on our design: edges must be placed on genuinely related positions. We use repeated transcript labels, which are given by the weak supervision itself and need no heuristics or parser. A Lexicon-Based Graph Neural Network for Chinese NER gets long-range context through a global relay node in the encoder. That model is the representative of "make the features global," which our claim says is not sufficient on its own.

Three DTW papers supply the method and the baselines. D3TW aligns frames to transcripts with a soft-min relaxation of DTW and a hinge loss against shuffled transcripts, which prevents actions collapsing to single frames. We keep that discriminative loss but add the non-local term D3TW lacks. Learning Discriminative Prototypes With Dynamic Time Warping (DP-DTW) learns one prototype per action and concatenates prototypes into a master sequence. A repeated action therefore already reuses the same template. This is the closest existing mechanism and the main threat to the idea. It couples occurrences only through a template shared across the whole dataset, whereas our term couples them through a center estimated from this video alone. DTWNet shows that one can differentiate along the single best path instead of over all paths. We reuse this to train through the alternating solver without storing soft-min tables.

Deep Declarative Dynamic Time Warping motivates choosing sharp paths over blurred ones. On Oxford RobotCar, a soft-path baseline reached 0.7% localization accuracy at 2 m against 25.4% for the sharp path, though at 15 to 50 times the inference cost. Our solver stays discrete, which avoids that cost.

Research Program

The first step is measurement. We will count how often Breakfast and Hollywood Extended transcripts contain repeated non-background actions. We will also define a consistency error, modeled on the skip-chain paper's correctable-by-consistency count: the fraction of repeated-action pairs in which exactly one occurrence reaches a frame-overlap threshold with ground truth. If repeats are rare, the headline gains are bounded by their frequency, and we will report that bound up front rather than averaging it away.

Second, we build the solver. It uses a background-aware variant in which the start and end silence segments are treated as a repeated label. It warm-starts $m$ from the prototype and runs a small fixed number of alternations, which we cap and report.

Third, we train end to end on the same encoder as DP-DTW. Gradients flow along the final path, as in DTWNet. The centers $m_a$ are treated as functions of the encoder features through the assignment, which is a simple mean, so this part is differentiable.

Fourth, we build a controlled synthetic benchmark in the style of DTWNet's warped-signal test. Sequences are formed by concatenating motifs under random warps. Repeated motifs inside a sequence share a per-sequence offset that is absent from the class template. This isolates exactly the within-video signal the method targets.

Baselines

The naive reference point is uniform segmentation: transcript actions are given equal-length segments in order. This shows how much any alignment helps.

The first published baseline is D3TW, run from its reported configuration with a GRU encoder. On Breakfast it reports 45.7% frame accuracy for segmentation and 57.0% for alignment with the transcript given at test time, against 43.0% for NN-Viterbi. We treat 57.0% alignment accuracy as the published number to beat on alignment.

The strongest existing method is DP-DTW, because its shared prototypes are the closest mechanism to ours. It reports a 10.6% frame-accuracy improvement over CDFL on Hollywood Extended. We found no absolute Breakfast segmentation number for DP-DTW on Lacuna, so we will rerun it ourselves.

Our method is implemented as DP-DTW plus the skip term, using the same encoder, the same features, the same epochs, and the same hyperparameter search budget, with $\lambda$ counted inside that budget. Beating DP-DTW means a statistically significant gain in frame accuracy across splits, together with a reduction in the consistency error. A gain in accuracy without a drop in consistency error would mean the improvement comes from somewhere other than the claimed mechanism.

Two ablations isolate the key ingredient. In the first, $\lambda=0$, which recovers DP-DTW exactly. In the second, the skip edges connect random pairs of transcript positions rather than repeated labels. The skip-chain paper predicts this random-edge version should help nothing.

Why not just…?

Why not just use a self-attention encoder instead of a GRU? This is the most serious alternative. Attention gives each frame a view of the whole video and might learn per-video appearance on its own. Our argument is that attention cannot know which frames the alignment will assign to the same transcript position, but this is an argument, not evidence. We will therefore run DP-DTW with a self-attention encoder, both with and without the skip term. If the skip term adds nothing on top of attention, the claim fails and we will say so. If the gain persists and concentrates on the consistency error, the claim survives.

Why not just rely on DP-DTW's shared prototypes? Shared prototypes already push both occurrences toward one template. They cannot absorb appearance specific to this video, such as camera, person, or utensils, without also changing the template for every other video. The synthetic benchmark settles this cleanly, because per-sequence offsets there are invisible to any dataset-wide template. On real data, the $\lambda=0$ ablation is the test.

Why not just re-estimate prototypes per video at test time and re-align? This is in fact our inference procedure run without training, so it is a fair and cheap competitor rather than a strawman. We will report it as a separate row. If test-time-only alternation matches end-to-end training, the contribution reduces to a simple inference trick, which is still useful but smaller. We will state that result plainly.

Proposed Experiments

The main experiments run on Breakfast (1,712 videos) and Hollywood Extended (937 videos). Both alignment, where the transcript is given at test, and segmentation are evaluated by frame accuracy, with the consistency error reported alongside. Results are broken down by whether a video contains a repeated action, since the method should change nothing on videos without repeats. That stratification is the decisive check. Gains on repeat-free videos would indicate a regularization side effect, not the claimed skip-chain mechanism.

A second check sweeps $\lambda$ and the number of alternations. Consistency error should fall monotonically with $\lambda$ until occurrences are over-merged, at which point boundary accuracy should degrade. On the synthetic benchmark we vary the size of the per-sequence offset. The gap between our method and DP-DTW should grow with the offset and vanish when the offset is zero. If it does not, the mechanism is not what we think it is.

Finally, we report wall-clock cost per video relative to a single DTW pass. This shows the non-local coupling is bought for a small constant factor, not the order-of-magnitude overhead of continuous declarative solvers.