Structure & Discovery / arXiv 2023

A Cooking Video Shows an Order. Which Steps Must Come First?

MSG² combines video frames and speech transcripts to estimate the dependencies behind a task, including which subtasks are prerequisites for others.

Multimodal Subtask Graph Generation from Instructional Videos

Yunseok Jang, Sungryull Sohn, Lajanugen Logeswaran, Tiange Luo, Moontae Lee, Honglak Lee

Overview

A cook might chop vegetables before boiling water or do those steps in the opposite order. Washing a dirty pan before cooking in it is a different kind of relationship. A video shows one execution of a task, and the order it shows can mix preferences with prerequisites. This paper uses multiple demonstrations to estimate a graph that separates those patterns.

Key Findings

The camera can show a step the annotation skips

An instructional video can skip an explicit label for preparing a tool, even though the tool is visibly ready later. A graph learner that only follows the annotations could mistake the missing label for a missing prerequisite. MSG² combines video and language cues to infer what has actually happened before it tries to learn which steps depend on one another.

Figure 1. From imperfect video annotations, MSG² estimates subtask states and then infers their prerequisites.
Figure 1. From imperfect video annotations, MSG² estimates subtask states and then infers their prerequisites.

A step can already be under way

The first stage predicts whether each subtask is not started, in progress, or complete at annotated segment boundaries. It treats those states as ordered, with a training objective built from two thresholds. One predicts whether the task has begun. The other predicts whether it has finished. The video and text can supply clues for a state that a single time annotation misses. Figure 2 and Equation 4

Search for a rule that makes a useful prediction

A completed subtask has a state vector cc describing which earlier steps are complete. The next step can begin when its learned condition fn(c)f_n(c) is true. Observed starts give positive evidence of eligibility. The absence of a start is ambiguous. A rule that says yes to every state can therefore score well under a naïve accuracy objective on observed starts.

The authors use a precision-oriented objective, P(en=1∣fn(c)=1)P(e_n=1\mid f_n(c)=1), to penalize rules that allow a step too freely, and add a penalty for complex Boolean expressions. A greedy search adds Boolean operations until it can no longer improve the objective. Combining the rules gives a graph that can allow alternative ways to meet a prerequisite. Equations 5–8 · Figure 3

A faithful graph still has to predict a useful next step

MethodAccuracy (%)SPOC (%)Compatibility (%)
ProScript57.5062.3437.12
MSGI+73.5972.3976.08
MSG² without state prediction81.6288.3597.86
MSG²83.1689.9198.30

Accuracy measures agreement with reference eligibility rules. SPOC measures agreement on which steps are ancestors of others, and compatibility asks whether the graph admits observed sequences. The no-state-prediction variant relies on annotated state labels. The full model improves all three averages on ProceL. In a separate next-step test, MSG² reaches 55.38% on ProceL and 54.42% on CrossTask, compared with 29.86% for STAM and 41.96% for ViViT, respectively. The paper’s CPR graph still shows a learned dependency that the reference does not require. Good aggregate compatibility cannot tell a user that every proposed prerequisite is real. Table 1 · Figure 4 · Table 2

Questions & Answers

The opening answers are simulated author responses based on the paper.

Q: Why use the video if there is a transcript?

A: Narration can skip actions or mention them at a different moment. Frames can help identify which subtask is active and which state has already been reached.

Q: Why can two people take different valid paths?

A: Some actions have alternative prerequisites, and independent steps can be reordered. The goal is to learn those constraints instead of copying one linear sequence.

Q: Does an action that never appears prove it was unavailable?

A: A recorded action offers evidence that its requirements were met. A person can also skip an available action or edit it out of the clip, so absence gives weaker evidence about whether it was possible. Treat the inferred edge as a hypothesis and test whether omitting or reordering the proposed prerequisite changes execution.

Future Ideas

Let a training editor challenge a prerequisite

In a procedure simulator with known dependencies, present each proposed dependency beside clips that support it and any clips that appear to violate it. Give experts an option to test the procedure with the suspected prerequisite omitted. Compare this view with a linear step editor at the same review time. Measure invalid dependencies removed, valid alternatives retained, and successful execution on unseen demonstrations.

Include deliberately edited recordings in which a necessary step is omitted from view while the procedure still succeeds. The simulator should retain the true execution record so reviewers can distinguish omitted footage from evidence against the prerequisite.

Sources

Original abstract

Real-world tasks consist of multiple inter-dependent subtasks (e.g., a dirty pan needs to be washed before it can be used for cooking). In this work, we aim to model the causal dependencies between such subtasks from instructional videos describing the task. This is a challenging problem since complete information about the world is often inaccessible from videos, which demands robust learning mechanisms to understand the causal structure of events. We present Multimodal Subtask Graph Generation (MSG 2), an approach that constructs a Subtask Graph defining the dependency between a task’s subtasks relevant to a task from noisy web videos. Graphs generated by our multimodal ap- proach are closer to human-annotated graphs compared to prior approaches. MSG 2 further performs the down- stream task of next subtask prediction 85% and 30% more accurately than recent video transformer models in the ProceL and CrossTask datasets, respectively.