Interval Biclustering for Unsupervised Action Discovery in Untrimmed Video

Untrimmed web videos are mostly not the action. A clip labeled "javelin throw" spends most of its length on a crowd, a commentator, and an empty athletic field, and that field looks almost identical before and after the throw. Unsupervised methods that group video moments by overall similarity are therefore pulled toward the scene rather than the action. They also assume each video holds a single action and that the number of action types is known in advance. Biclustering, a family of methods from gene-expression analysis, addresses the same structural problem in a different setting. It looks for a block of the data table: a subset of rows that behave consistently on a subset of columns, with everything else ignored. In genomics, the rows are genes that switch on together only under certain conditions.

This note proposes treating action discovery as biclustering of a table whose rows are short time windows of video, pooled across a whole collection, and whose columns are interpretable semantic channels: object detectors, scene detectors, and body-part motion signals. Each discovered action is a block, meaning a set of time intervals across many videos that agree on a small set of channels. The search is constrained in two ways. Rows must form contiguous intervals within each video. The chosen channels must also separate those intervals from the rest of the same video. Selecting columns lets the method discard the scene channels that the action shares with its background. Allowing blocks to overlap lets one video, or even one moment, belong to several actions. Stopping the block search against a shuffled-data null decides how many actions there are.

Core Claim

The claim is narrow and testable. On untrimmed benchmarks, the failure cases of current unsupervised co-localization are videos with several actions and actions whose background shares their scene. Both failures come from forcing every moment to be compared on every feature dimension, and from forcing each video into one cluster. A biclustering objective with three properties should reduce both failures without supervision: it selects a column subset per block, it builds rows from contiguous intervals, and it requires the selected channels to contrast each interval with its own video's other moments. If the method works, its gains over the strongest existing method should concentrate in exactly those two strata. If the gains are uniform, or absent there, the mechanism is not doing what we claim.

Relation to Prior Work

The closest work is Learning Temporal Co-Attention Models for Unsupervised Video Action Localization. It alternates two steps. It spectrally clusters whole videos into a known number $C$ of actions, then trains attention modules with an action–background separation loss so that action segments agree across videos in a cluster and differ from their own video's background. This paper motivates the proposal: it reports the single-action and known-$C$ assumptions as limitations. It also supplies one ingredient we reuse in non-neural form, the within-video action–background contrast. The key difference is in the unit being clustered. Its clustering assigns whole videos to exactly one cluster, on all feature dimensions. We assign time intervals to possibly several blocks, on chosen dimensions.

Video co-summarization: Video summarization by visual co-occurrence is the nearest use of bicliques in video. It finds shots that are mutually similar between pairs of videos, using sparsity to drop unmatched shots. It differs from our proposal in three ways. It works pairwise rather than across the whole collection, it has no temporal ordering (the authors flag this), and it does not select feature channels. Its results do show that dropping noise beats assigning everything: $k$-means reaches 0.507 top-5 mAP, generic co-clustering 0.662, and the biclique method 0.707. Unsupervised Action Discovery and Localization in Videos makes a similar point with dominant sets, but treats categories as mutually exclusive per video.

Two lines constrain the design. Temporal Subspace Clustering for Human Motion Segmentation shows that ignoring temporal order produces jittery labels; a temporal smoothness penalty lifts Keck Gesture accuracy from 41.89% to 57.12%. Classical biclustering treats columns and rows as unordered, so it would inherit that jitter, and our contiguity constraint exists for this reason. Probabilistic Temporal Subspace Clustering and Bayesian temporal biclustering with applications to multi-subject neuroscience studies infer the number of groups and model temporal persistence. However, they were demonstrated on motion capture and low-channel brain recordings. The file reports nothing on web video at THUMOS scale, and their sampling-based inference is a poor fit for it. We borrow their goal of inferring the number of groups, not their inference machinery.

The algorithm comes from the biclustering literature. Biclustering Using Message Passing casts block membership as binary variables on a factor graph and solves it by Max-Sum message passing, which handles overlapping blocks better than local search. ARBic: an all-round biclustering algorithm for analyzing gene expression data contributes two things: globally chosen seeds followed by noise-tolerant greedy extension, and the trend-preserving notion of coherence. That notion fits video channels whose absolute scales vary across cameras.

Research Program

The data table $X$ has one row per 16-frame window, stacked over all videos in a collection. It has one column per semantic channel. The channels are of three kinds: ImageNet object scores and Places scene scores, following the object and scene streams of Harnessing Object and Scene Semantics for Large-Scale Video Understanding, but kept per window rather than averaged over the clip; and per-body-part motion energy from pose estimates, grouped by the joint partitions used in Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition. Interpretable channels are a deliberate choice: a block's column set then reads as "javelin + running legs, not stadium," which we can audit.

A block is a pair $(R, Q)$. Here $R$ is a set of windows that must be a union of contiguous intervals, at most a few per video, and $Q$ is a set of channels. Its score is

$$S(R,Q) = -H(R,Q) + \lambda \, D(R,Q) - \gamma\,|\partial R|,$$

where $H$ is the mean squared residue of the submatrix (how far entries deviate from row-plus-column averages), computed on rank-transformed values so that only trends must agree. $D$ is the mean, over videos touched by $R$, of the gap on channels $Q$ between the video's windows inside $R$ and its windows outside $R$. $|\partial R|$ counts interval boundaries, which penalizes fragmentation in the spirit of the temporal smoothness term. $\lambda$ and $\gamma$ are weights.

The contrast term is the non-neural counterpart of the action–background separation loss of the co-attention paper. It is what makes scene channels unattractive to select: they are high both inside and outside the action interval.

We optimize with the message-passing formulation of the factor-graph method, adding pairwise chain factors between adjacent windows' membership variables. This keeps each block's row set interval-shaped while Max-Sum stays local. Seeds are pairs of windows from different videos that agree strongly on a small channel set, chosen ARBic-style to cover broad blocks (many windows, few channels) and narrow ones. Blocks are found one at a time. Each accepted block is down-weighted rather than removed, so later blocks may overlap it.

The search stops when the best new block scores below the 95th percentile of best-block scores on copies of $X$ in which each column has been shuffled within videos. The number of actions therefore comes from the data. For benchmark scoring, a window's predicted label set is the set of blocks covering it, and a window may carry several labels.

Baselines

The naive reference point is global clustering. We run $k$-means on the same per-window channel vectors with $k$ set to the true class count, smooth the labels with a median filter, and merge runs into intervals. This is the "averaging out" failure that biclustering claims to fix. On the co-summarization data, $k$-means scored 0.507 top-5 mAP against 0.707 for bicliques, which suggests the gap is real, but no result on Lacuna was found for $k$-means co-localization on THUMOS14.

The strongest existing method is the temporal co-attention model of Learning Temporal Co-Attention Models for Unsupervised Video Action Localization. It reports 25.0% [email protected] for unsupervised co-localization on THUMOS14 and 21.1% average mAP on ActivityNet-1.2. It is the strongest competitor because it already has a within-video background contrast and is evaluated in exactly our setting.

For fairness we run it twice. First, we use its published numbers with its own features and the true $C$. Second, we retrain it on our semantic-channel features under the same tuning budget, measured in GPU-hours and the number of hyperparameter configurations tried. Our method is likewise run on its features, treating feature dimensions as columns. The comparison therefore separates the effect of the objective from the effect of the features. Beating it means a higher [email protected] on THUMOS14 than the retrained co-attention model on matched features. A larger margin is predicted, and required for the claim, on the multi-action and background-confusable strata described below.

Two further baselines probe the parts of the method. The first is temporal subspace clustering, the method of Temporal Subspace Clustering for Human Motion Segmentation, applied to the same table with the true $K$. It represents temporally smoothed clustering that uses all dimensions. The second is a temporally regularized sparse non-negative matrix factorization described below. Ablations remove one ingredient at a time. Forcing $Q$ to contain all channels isolates column selection. Setting $\lambda=0$ isolates the contrast term. Dropping the chain factors isolates contiguity. Replacing the shuffle-null stop with the true $C$ isolates count inference.

Why not just…?

Why not just run spectral or $k$-means clustering on strong per-window embeddings and smooth in time? Clustering over all dimensions weights scene and action channels together. In THUMOS, background videos share scene context with the actions, and the THUMOS challenge paper reports that removing background videos raised classification mAP by 15% (The THUMOS challenge on action recognition for videos "in the wild"). This baseline is included directly, and the background-confusable stratum is where we expect it to lose most.

Why not just use sparse non-negative matrix factorization with a temporal smoothness penalty? This is the real threat. Sparse factor loadings select columns, non-negative activations can overlap, and a smoothness penalty glues windows together, so this gives overlapping soft blocks almost for free. Its weakness is that factorization explains each window as an additive sum of parts and has no term asking a part to be absent from the same video's other windows. A stadium factor explains scene energy well and will be learned. We run this baseline with the same channels and tuning budget, and with a background-contrast term added as a variant. If the variant with the contrast term matches our method, the honest conclusion is that the contribution is the contrast term, not the biclustering search, and we will report it that way.

Why not just extend the co-attention model with multi-label clusters and a learned cluster count? This is plausible, but its clustering step assigns whole videos, and the class-specific attention is trained per cluster. Multi-action videos would need a video-to-several-clusters assignment, which reintroduces the combinatorial search that biclustering performs explicitly. Our retrained co-attention comparison on matched features, stratified by the number of actions per video, tests whether the per-video assignment is the bottleneck.

Proposed Experiments

The main benchmark is THUMOS14 temporal localization (mAP at IoU 0.3 to 0.7, with 0.5 as the headline), followed by ActivityNet-1.2 average mAP over IoU 0.5:0.95. We follow the co-attention paper's evaluation, which maps anonymous clusters to labels by optimal matching. Because our block count may differ from $C$, we report both the many-to-one mapping and a run with the count fixed to $C$, so that no result depends on a favorable mapping.

There are two decisive stratified checks. The first stratum is THUMOS14 test videos containing two or more annotated classes, compared with single-class videos. The second is the classes whose THUMOS background videos share their scene. For the second, the false-positive rate on the background videos is reported separately. The hypothesis predicts that our margin over the matched-feature co-attention model and over sparse factorization is at least twice as large in each hard stratum as in its easy complement. A uniform or reversed margin falsifies the column-selection story even if the overall mAP improves.

Count inference is checked by comparing the inferred number of blocks with the true class count on THUMOS14 and ActivityNet-1.2. We also check what happens when a random fraction of classes is removed from the collection: the inferred count should fall correspondingly.

Interpretability is checked by having annotators judge, for 50 blocks, whether the selected channels name the action rather than its setting. A secondary transfer check runs the same objective on the co-summarization YouTube collection against the 0.707 top-5 mAP of maximal biclique finding. That comparison tests whether collection-wide, interval-shaped blocks improve on pairwise bicliques when temporal order is enforced.