PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Learning from Narrated Instruction Videos

Jean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivic, Ivan Laptev, Simon Lacoste-Julien

arXiv:1506.09215v4cs.CVcs.LG

TL;DR

The paper asks how to automatically learn the main steps of a task from narrated instruction videos, where language, appearance, and sequence structure vary. It clusters text and video sequentially under joint constraints, and demonstrates unsupervised step discovery and localization on a new five-task dataset. The method consistently outperforms localization baselines for Change tire and Perform CPR, while showing task-dependent results elsewhere.

  • Problem

    Automatically learning task steps from narrated instruction videos is challenging because language, visual appearance, and overall step order vary across videos.

  • Method

    The method performs text and video clustering linked by joint constraints to learn a common ordered script, multimodal step representations, and temporal assignments.

  • Results

    The method automatically discovers and localizes task steps; it consistently outperforms all baselines for Change tire and Perform CPR across reported K values.

  • Takeaways & Limitations

    The approach supports unsupervised learning of task scripts and step locations from narrated instruction videos, demonstrated on a dataset of five tasks and about 800,000 frames.

  • Takeaways & Limitations

    The model assumes a common script with a fixed ordering of the main steps across videos.

Abstract

from arXiv · show

We address the problem of automatically learning the main steps to complete a certain task, such as changing a car tire, from a set of narrated instruction videos. The contributions of this paper are three-fold. First, we develop a new unsupervised learning approach that takes advantage of the complementary nature of the input video and the associated narration. The method solves two clustering problems, one in text and one in video, applied one after each other and linked by joint constraints to obtain a single coherent sequence of steps in both modalities. Second, we collect and annotate a new challenging dataset of real-world instruction videos from the Internet. The dataset contains about 800,000 frames for five different tasks that include complex interactions between people and objects, and are captured in a variety of indoor and outdoor settings. Third, we experimentally demonstrate that the proposed method can automatically discover, in an unsupervised manner, the main steps to achieve the task and locate the steps in the input videos.

1. Introduction

The paper targets unsupervised discovery of task steps from narrated instruction videos, despite substantial linguistic, visual, and sequence variability. It jointly uses narration and video to learn a coherent step script and locate each step temporally.

  • Instruction videos provide abundant task demonstrations but generally lack direct supervisory signals for automatic learning.The paper motivates unsupervised learning from large online collections of videos intended to teach people.
  • The method learns a common ordered sequence of steps together with their textual and visual representations from narrated videos.It exploits complementary modalities to resolve ambiguities without a predefined script.
  • The same task step can vary substantially in language, visual appearance, and position across videos.Videos may omit steps or slightly change their order, while people, objects, viewpoints, and action performances also differ.
  • The output is a discovered task script plus the temporal location of each step in every input video.For example, tire-changing steps such as loosening nuts, jacking up the car, and removing the spare tire are discovered and localized.

2. Related work

The paper learns event sequences directly from noisy narrated instruction videos rather than relying on structured recipes or manually annotated event orders. Its joint use of visual and linguistic modalities also distinguishes it from video summarization.

  • Unlike prior script-learning methods based on general text or scenario-specific descriptions, this work learns event sequences from unstructured narrated instruction videos.The videos contain detailed event descriptions but more noise than the structured inputs used by related methods.
  • Unlike cooking-video methods that rely on readily available recipes, this approach discovers instruction steps using discriminative clustering.It also differs from methods using manually annotated event sequences by discovering the sequence from clustered narration.
  • The task differs from video summarization because it extracts key steps required for a concrete task in a consistent sequence.The approach jointly exploits visual and linguistic modalities, whereas summarization is described as subjective.

3. New dataset of instruction videos

The authors introduce a 150-video dataset spanning five narrated tasks and complex person-object activities in varied settings. Videos were selected from YouTube, transcriptions were corrected, and step intervals were manually annotated for evaluation.

  • The dataset contains 150 YouTube videos covering five tasks: making coffee, changing a car tire, performing CPR, jumping a car, and repotting a plant.There are 30 videos per task, selected among top YouTube results with English ASR and verified task performance.
  • 800,000 frames comprise the dataset, with videos averaging about 4,000 frames or two minutes.
  • The tasks were chosen to cover varied activities involving complex interactions between people, objects, and other people.
  • Automatic YouTube transcriptions were manually corrected for misspellings and punctuation without changing the spoken content.The transcriptions therefore retain the challenging variability of the original verbal instructions.
  • For evaluation, annotators defined ordered ground-truth steps and assigned each video time interval to a step or no step.Step intervals are separated by transitions or verbal explanations, and some steps may be omitted in individual videos.

4. Modelling narrated instruction videos

The method learns a common ordered task script by clustering narrated text first, then localizing corresponding steps in video under cross-modal constraints.

  • The input consists of multiple videos depicting one task, with frame segments and transcribed narration, from which K main steps must be recovered and localized.
  • 4.1. Clustering transcribed verbal instructions: Text clustering converts narrations into direct object-relation sequences and seeks their most common ordered sequence of task steps.A direct object relation pairs a verb with its direct object, such as “remove tire.”
  • 4.1. Clustering transcribed verbal instructions: Multiple sequence alignment creates a globally consistent template, aligning relations with similar senses and accommodating gaps across transcripts.The alignment uses a sum-of-pairs cost over mapped relations and gaps.
  • 4.1. Clustering transcribed verbal instructions: Frank-Wolfe optimization solves an integer quadratic-program reformulation of multiple sequence alignment, producing lower objective values than state-of-the-art heuristic procedures.The formulation also permits flexible alignment costs and scales with sequence length and vocabulary size.
  • 4.1. Clustering transcribed verbal instructions: The main textual steps are selected from the most-supported aligned slots, with ties potentially yielding fewer than the requested K steps.The output is encoded as assignment matrices Rn indicating each token’s assigned step or no assignment.
  • 4.2. Discriminative clustering of videos under text constraints: Video clustering assigns time intervals to discovered steps using binary matrices Zn, while allowing intervals containing no visually present step.The visual representation combines motion descriptors for actions with appearance descriptors for objects.
  • 4.2. Discriminative clustering of videos under text constraints: The video assignments are learned discriminatively with global ordering constraints from the discovered script and weak temporal constraints from caption timing.The method predicts the most salient interval for each step and uses textual timing as fine-grained weak supervision.

5. Experimental evaluation

Experiments evaluate step discovery from narrations and temporal localization in a five-task dataset, comparing the method with uniform, visual, text-augmented, and supervised baselines.

  • The evaluation uses five instruction tasks and tests both the quality of recovered textual step sequences and their temporal localization in video.All data and code are reported as available through the project webpage.
  • The representation combines parsed, lemmatized direct object relations with video motion descriptors for actions and appearance descriptors for objects.
  • The alignment cost is -1 for exact WordNet matches of both verbs and objects and 100 otherwise, favoring high-precision alignments.
  • 5.1. Discovering main steps from text narrations: Text-based step discovery is evaluated at maximum K = 10 using precision for correctly recovered steps appearing in the correct order.
  • 5.2. Localizing instruction steps in video: Temporal localization is evaluated with one-to-one global matching and F1, combining precision and recall without exposing ground-truth annotations during learning.
  • Baselines include uniform placement, video-only clustering, video plus bag-of-words direct-object features, and a supervised approach trained with ground-truth constraints.
  • 5.2. Localizing instruction steps in video: For Change tire and Perform CPR, the method consistently outperforms all baselines across K values; results vary for Repot, Jump car, and Make coffee.The reported variations are associated with text importance, visually repeating steps, and narration variability.

6. Conclusion and future work

The paper demonstrates unsupervised discovery of task steps from narrated videos and identifies broader temporal structures as future work.

  • The method automatically discovers a task’s main steps from narrated instruction videos without supervision.It is tested on an annotated dataset of challenging real-world videos with complex person-object interactions across indoor and outdoor scenes.
  • The current model assumes a common script with a fixed ordering of the main steps across videos.The paper notes that some tasks permit swapped or omitted steps, motivating recovery of more complex temporal structures.

Outline of Supplementary Material

The supplementary material expands dataset, optimization, and experimental-result details.

  • Section A: Section A provides detailed statistics and an illustration of the newly collected instruction-video dataset.
  • Section B: Section B reformulates multiple sequence alignment as a quadratic program and reports empirical results for Frank-Wolfe optimization.It reports solutions with lower objective values.

A. New challenging dataset of instruction videos

The dataset is characterized by ordered steps, missing demonstrations, and repeated actions across five instruction-video tasks. Its videos combine substantial linguistic and visual variability with globally consistent task structure, making step discovery challenging.

  • A.1. Dataset statistics: The dataset statistics measure step-ordering consistency, missing steps, and repeated steps across instruction videos.These three scores target distinct structural properties of the dataset.
  • A.1. Dataset statistics: For each task, annotations are compared with an ordered ground-truth sequence using total, unique, and longest-common-subsequence step counts.The notation distinguishes the total annotated steps, unique steps, and the longest common subsequence with ground truth.
  • A.1. Dataset statistics: The order consistency error is the proportion of unique annotated steps that violate the ground-truth global ordering.It measures ordering violations among non-repeated annotated steps.
  • A.1. Dataset statistics: The missing-steps score measures the proportion of ground-truth steps that are visually absent from a video.This captures demonstrations that omit steps relative to the ground truth.
  • A.1. Dataset statistics: The repetition score measures the proportion of annotated steps that are repeated.Repeated actions are treated as a separate structural property of the videos.
  • A.1. Dataset statistics: 6% total order error, 27% missing steps, and 14% global repetition characterize the five-task dataset.Performing CPR is the main contributor to repetition because compressions and breaths alternate repeatedly.
  • A.2. Complete illustration of the dataset: The dataset exhibits large variability in verbal expressions, terminology, viewpoints, objects, and ways of performing actions.Each task is illustrated through events represented by sample frames and extracted verbal narrations.

B. Clustering transcribed verbal instructions

This section formulates narrated-instruction text clustering as multiple sequence alignment and video clustering as a constrained quadratic optimization problem. It introduces a Frank-Wolfe solution and reports lower objective values than a state-of-the-art heuristic in this setting.

  • B. Clustering transcribed verbal instructions: Narrated instructions are represented as sequences of direct object relation tokens whose lengths vary across videos.The representation converts raw transcriptions into structured token sequences for alignment.
  • B. Clustering transcribed verbal instructions: Multiple sequence alignment maps each token sequence to a common template while minimizing the sum-of-pairs alignment cost.Empty template slots represent gaps, and pairwise costs reflect similarity between verb and direct-object constituents.
  • B.1. Reformulating multiple sequence alignment as a quadratic program: The multiple sequence alignment formulation is an integer quadratic program with combinatorial constraints and is NP-hard in general.The quadratic objective captures pairwise token-alignment costs while the constraints enforce valid increasing remappings.
  • B. Clustering transcribed verbal instructions: The alignment is encoded with indicator matrices for token identities and valid increasing remappings into global template slots.The matrices represent both sequence composition and the assignment of original token positions to template locations.
  • B.2. Comparison of methods: Frank-Wolfe optimization relaxes the feasible set to its convex hull and rounds the converged fractional solution to a valid integer alignment.The rounding selects a previously visited integer corner supplied by the linear minimization oracle.
  • B.2. Comparison of methods: Lower objective values indicate better alignments, and Frank-Wolfe consistently outperforms the compared state-of-the-art method on the paper’s five tasks.The comparison concerns the paper’s instruction-video application rather than general biological MSA problems.
  • B.2. Comparison of methods: The authors explicitly limit their claim to this application, noting that the formulation is not shown to outperform computational-biology heuristics on their original problems.The observed advantage may reflect structure specific to the instruction-video setting.
  • C. Discriminative clustering of videos under text constraints: The resulting text-clustering framework supplies constraints for discriminative video clustering, where shared classifiers model visual steps across videos.The video clustering cost is derived from ridge regression and is jointly linked to the textual constraints.

C.2. Frank Wolfe algorithm for minimizing h(Z)

The algorithm localizes discovered steps by optimizing constrained video assignments under text-derived temporal and ordering constraints. A dynamic program solves each Frank-Wolfe linear oracle, followed by rounding to a feasible binary assignment.

  • C.2. Frank Wolfe algorithm for minimizing h(Z): Video localization assigns each discovered step to time intervals through a binary matrix Z, allowing intervals with no visually present step.Each entry indicates whether step k appears at interval t in video n.
  • C.2. Frank Wolfe algorithm for minimizing h(Z): Text clustering produces a fixed assignment matrix R that links direct-object tokens to the K discovered visual steps.R is obtained before optimizing Z and supplies the cross-modal constraints.
  • C.2. Frank Wolfe algorithm for minimizing h(Z): The feasible set enforces temporal consistency with captions, within-video event ordering, and one salient time interval for each event.Caption-linked constraints require at least one nearby video interval to represent a text-assigned action.
  • C.2. Frank Wolfe algorithm for minimizing h(Z): Frank-Wolfe linear oracles decompose by video because the linear objective and constraints are blockwise across videos.Each per-video oracle can therefore be solved independently.
  • C.2. Frank Wolfe algorithm for minimizing h(Z): The dynamic program finds an ordered path through an expanded cost matrix, using dummy zero-cost columns to permit jumps between successive step assignments.The matrix is shifted and padded so path search represents valid ordered assignments with possible gaps.
  • C.2. Frank Wolfe algorithm for minimizing h(Z): After optimization, continuous assignments are rounded by minimizing their distance to classifier predictions, yielding feasible binary matrices for all videos.The rounding problem becomes a linear program solved by the same dynamic-programming procedure.

D.2. Error bars for Frank-Wolfe methods.

The supplementary analysis explains how error bars are obtained for unsupervised Frank-Wolfe methods. The reported variation is small, indicating stability of the procedure.

  • D.2. Error bars for Frank-Wolfe methods.: Error bars span the minimum and maximum performance observed after rounding solutions during Frank-Wolfe optimization.Because the bounds are extrema rather than symmetric standard errors, the error bars need not be symmetric.
  • D.2. Error bars for Frank-Wolfe methods.: The dataset covers five instruction-video tasks with varied real-world scenes and person-object interactions.Examples include repotting a plant, CPR, jumping cars, changing a tire, and making coffee.
  • D.2. Error bars for Frank-Wolfe methods.: The observed performance variation is not very important, highlighting the stability of the unsupervised procedure.This conclusion is based on the spread across rounded points visited during optimization.

E.1. Script discovery

The method recovers meaningful, ordered scripts across diverse tasks and localizes their steps in the input videos. Its recovered sequences generally correspond well to ground-truth steps while also capturing finer-grained and repeated actions.

  • Recovered steps and their ordering correspond well to the ground-truth steps across the five tasks.
  • For CPR and changing a tire, the method recovers finer-grained actions beyond the main annotated steps.Examples include tilt head and lift chin for CPR, and remove jack or put jack for changing a tire.
  • The method recovers repeated actions, including alternating breaths and compressions in CPR and connecting cables twice for jumping cars.
  • The method automatically discovers meaningful scripts describing very different tasks.
  • The recovered steps are localized in videos using clustered direct-object relations and representative frames, although some visually similar steps are incorrectly localized.

keep soil

The recovered sequences contain task-specific action phrases for preparing plants, making coffee, and performing CPR. The examples show repeated action descriptions alongside more distinctive procedural steps.

  • Plant-repotting sequences include taking and loosening roots, adding soil, placing the plant, filling the pot, and watering it.
  • Coffee-making sequences include grinding coffee, adding coffee to a filter or basket, filling the chamber, heating, and pouring coffee.
  • CPR sequences include checking response, breathing, and pulse, opening the airway, tilting the head, lifting the chin, giving breaths, and performing compressions.
  • Table 4 reports recovered step sequences under maximum-step settings K = {7, 10, 12, 15}, with the method sometimes selecting fewer than K steps.
  • The recovered-step examples cover changing a car tire, jumping cars, repotting a plant, making coffee, and performing CPR.
Loading 1506.09215v4…