When a model must find where an action happens in a long video using only the label "this video contains high jump," a natural approach is to learn a short template of the action's phases (approach, take-off, clearance, landing) and slide a differentiable alignment of that template along the video. In practice this fails in a specific way. Alignment scores add up costs along a path, so the cheapest match squeezes each phase into a single frame and treats everything else as background. This is the "degenerate sequence" collapse that D3TW could only prevent with ordered negative transcripts, and those do not exist when all you have is a set of video labels.
We propose scoring an alignment by its rate, meaning the average match quality per frame over a finite look-back window, instead of its sum. We compute this rate with a discounted dynamic program whose discount is set from the typical action duration. The discount choice follows the logic that reinforcement learning uses to approximate long-run average reward with a discounted surrogate: set the effective horizon $1/(1-\beta)$ well beyond the time the process needs to settle. The resulting score rises with the length of a well-matched span, falls when background is absorbed into the span, costs time linear in video length, and needs memory bounded by the horizon. It never forms a frame-by-frame video matrix.
Core Claim
The core claim is that a discounted soft alignment of a short learned template against an untrimmed video yields a per-class score that resists collapse by construction. Its maximizing path directly supplies start and end boundaries. It can therefore replace both negative-transcript mining and threshold-based proposal extraction in weakly-supervised temporal localization.
Concretely, let $s_c(t,k)$ be the network's score for frame $t$ matching phase $k \in \{1,\dots,K\}$ of class $c$'s template, and let $b_c$ be a learned background rate. The recursion is
$$V_c(t,k) = (1-\beta)\, s_c(t,k) + \beta \,\mathrm{smax}_\tau\big(V_c(t-1,k),\, V_c(t-1,k-1)\big), \qquad V_c(t-1,0) := b_c,$$
where $\beta \in (0,1)$ is the discount and $\mathrm{smax}_\tau$ is the log-sum-exp soft maximum at temperature $\tau$ from Soft-DTW. Because each step is a convex blend, $V_c$ stays on the same scale as the frame scores; it is a rate, not a sum. Consider a path that enters the template from background and matches $L$ frames with average score $\bar s$. Its completed value is approximately
$$V_c - b_c \approx (1-\beta^{L})(\bar s - b_c).$$
This single expression carries the argument. A one-frame match earns only a fraction $(1-\beta)$ of the available gain, so collapse is penalized. Absorbing background frames lowers $\bar s$, so over-extension is penalized. The reward saturates once $L$ exceeds roughly $1/(1-\beta)$ frames. This mirrors in-loss the inside-versus-outside contrast that the Outer-Inner-Contrastive loss of AutoLoc imposes on explicit proposal windows.
Research Program
The first component is the calibration of the discount, drawn from the discounted-to-average reduction literature. Towards Tight Bounds on the Sample Complexity of Average-reward MDPs shows that the gap between the rescaled discounted value and the average reward scales as $O((1-\gamma)t_{\text{mix}})$, and so sets $1-\gamma = \Theta(\epsilon/t_{\text{mix}})$. The analogue we will prove for a single finite segment is a bias bound of order $(1-\beta)\,t_{\text{enter}}$ between $V_c$ and the within-action rate. Here $t_{\text{enter}}$ is the number of frames the path spends transitioning from background into the template's first stable phase. This yields a per-dataset rule: set $1/(1-\beta)$ to a small multiple of the median action length estimated without labels, for example from CAS peak widths.
Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor plays a constraining role. It proves that an exact reduction threshold exists, but that threshold can sit within floating-point noise of 1. We deliberately give up exactness for a horizon in the tens to hundreds of frames, where $1-\beta \sim 10^{-2}$ and float32 is safe. We also account for the known tension that average-reward theory assumes recurrent, mixing chains, while a video is finite and dominated by background. We never average over the whole video. The rate is local to the horizon, and the video-level score is a soft top-$k$ pooling over $t$ of $V_c(t,K)$, trained with the usual multi-label loss against video labels.
The second component is localization and gradients. Following the backward recursion of Soft-DTW, the gradient $\partial V_c(t^\ast,K)/\partial s_c(t,k)$ gives the expected occupancy of each phase at each frame. The segment is then read off as the span where occupancy of any phase is non-negligible, with the start at the entry from background and the end at the completion time $t^\ast$. No watershed thresholding is needed. The temperature $\tau$ will be tied to $\beta$ as a secondary study, testing whether sharper soft maxima are needed at longer horizons. This addresses the static-smoothing sensitivity noted for soft alignment.
The third component treats quadratic cost as a design constraint. Time is $O(TKC)$ for $T$ frames, $K$ phases and $C$ classes. Because influence decays as $\beta^{\ell}$ with lag $\ell$, the backward pass can be truncated at $L_{\text{bp}} = \lceil \log\delta/\log\beta \rceil$ frames with gradient error at most $\delta$. Memory is therefore $O(L_{\text{bp}}KC)$ per chunk, which permits native-frame-rate training on long videos.
This contrasts with three existing approaches to cost. Weakly-Supervised Representation Learning for Video Alignment and Analysis aligns video pairs over a full $T\times T$ grid and leaves long videos as future work. Fast Global Alignment Kernels restricts paths to a diagonal band that only avoids degeneracy when lengths differ by less than a factor of two, which fails when a short action is buried in a long video. Random Warping Series matches whole sequences against random templates and cannot place boundaries. Our templates are learned, short, and matched locally anywhere in time.
Baselines
The naive reference point is a standard Class Activation Sequence (CAS) model, which produces frame-wise class scores pooled over time, with thresholding. The version we use is the attention-pooled design of STPN, sharing our features and backbone. AutoLoc reports that moving beyond such thresholding to learned boundaries raises THUMOS'14 mAP at IoU 0.5 from 13.7% to 21.2%. These numbers anchor the range in which a new loss must operate.
The strongest direct loss-level competitor is TSCN, which sharpens attention toward binary values and reports 28.7% mAP at IoU 0.5 on THUMOS'14 and 21.7% average mAP on ActivityNet v1.3. We will re-run it with identical two-stream features, identical training epochs, and an equal hyperparameter search budget of the same number of trials. It is the right comparison because it is a single-stage method that attacks the same blurry-boundary failure. Beating it means exceeding its re-run THUMOS'14 mAP at 0.5 by more than the seed-to-seed spread over five seeds.
The strongest existing system overall is FuSTAL, which reports 50.8% average mAP on THUMOS'14 and 28.4% on ActivityNet v1.3. It is a multi-stage pseudo-label pipeline, so the fair test is to swap our rate alignment in as its first-stage pseudo-label generator, keeping its filtering and teacher-student stages and budget fixed. Winning means a higher final average mAP than FuSTAL's own re-run under the same compute. A draw with fewer stages would be a weaker but still reportable result.
On transcript-supervised Breakfast, the comparison is D3TW. It reports 45.7% frame accuracy for segmentation and 57.0% for alignment, with the transcript given at test time. We will run our recursion with the transcript's classes chained as templates and with no negative transcripts. Matching D3TW without negatives is the success criterion.
The ablation that isolates the key ingredient keeps everything identical but replaces the rate recursion with cumulative soft alignment, a sum of $s - b_c$ along the path. This directly measures whether the rate formulation, and not the template, prevents collapse.
Why not just…?
Why not just smooth the CAS with an exponential moving average? This is the most serious threat. With a single phase ($K=1$), our recursion is an exponential moving average of the class score, so any gain must come from ordered multi-phase matching. The $K=1$ versus $K\in\{3,5,8\}$ comparison, together with a box-filter-smoothed CAS at matched width, settles this question. If $K>1$ does not beat both on boundary-sensitive metrics (mAP at IoU 0.7), the alignment component is unjustified. We would then report the rate-calibrated smoothing rule as the finding.
Why not just divide soft-DTW cost by path length? Per-length normalization is a ratio objective that does not decompose over the dynamic program, so it must be solved by repeatedly shifting costs by a candidate rate $\lambda$ and re-solving, as in fractional programming. We will implement this exact average-cost variant with its outer loop as a baseline. If it matches our accuracy, the argument for our method reduces to cost and stability. We will report its wall-clock and memory overhead and whether the outer loop converges on long videos.
Why not just use duration priors or negative transcripts, as in HMM segmentation or D3TW? The Language of Actions controls duration through HMM transition structure, reaching 25.34% accuracy on Breakfast with flat-start weak training. D3TW uses permuted negative transcripts. Both require an ordered transcript, which is unavailable on THUMOS'14 and ActivityNet, so they cannot be the answer there. On Breakfast, the head-to-head against D3TW described above tests whether the rate objective replaces negatives.
Why not just use FuSTAL's multi-stage pipeline? FuSTAL already exceeds 50% average mAP on THUMOS'14, and a new first-stage loss may add little to it. We treat this as an open outcome. The plug-in experiment reports whether better first-stage pseudo-labels, measured by pseudo-label IoU against held-out ground truth, carry through to final accuracy.
Proposed Experiments and Decisive Checks
The main experiments run on THUMOS'14 and ActivityNet v1.3 with video labels only, reporting mAP at IoU 0.1 to 0.7 and average mAP. Breakfast is used with transcripts, reporting frame accuracy for segmentation and alignment.
The first decisive check is collapse. We will plot predicted segment-length histograms against ground truth for the rate recursion, the cumulative-sum ablation, and the exact per-length-normalized variant. The prediction is that the cumulative version piles mass at lengths near $K$ frames, while the rate version tracks the true distribution.
The second check is calibration. We will sweep $1/(1-\beta)$ from 0.25× to 8× the median action length. The theory predicts that accuracy rises until the horizon exceeds the typical entry time and then plateaus or degrades slowly. A sharp optimum far from the predicted multiple would falsify the transfer from the average-reward analysis.
The third check is scale. On Breakfast videos at native frame rate (over 4 million frames in total), we will report peak GPU memory and throughput against full-grid soft alignment and a diagonal band. We will also verify that truncated backpropagation at the predicted $L_{\text{bp}}$ changes accuracy by less than seed noise.
The fourth check is the $K=1$ ablation. It decides whether this is an alignment contribution or a principled smoothing rule, and the paper's framing will follow that answer.
References
- D3TW: Discriminative Differentiable Dynamic Time Warping for Weakly Supervised Action Alignment and Segmentation
- Soft-DTW: a Differentiable Loss Function for Time-Series
- AutoLoc: Weakly-Supervised Temporal Action Localization in Untrimmed Videos
- Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
- Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor
- Weakly-Supervised Representation Learning for Video Alignment and Analysis
- Fast Global Alignment Kernels
- Random Warping Series: A Random Features Method for Time-Series Embedding
- Weakly Supervised Action Localization by Sparse Temporal Pooling Network
- Two-Stream Consensus Network for Weakly-Supervised Temporal Action Localization
- Full-Stage Pseudo Label Quality Enhancement for Weakly-supervised Temporal Action Localization
- The Language of Actions: Recovering the Syntax and Semantics of Goal-Directed Human Activities