Video-Mined Task Graphs for Keystep Recognition in Instructional Videos
Authors: Kumar Ashutosh
Santhosh Kumar Ramakrishnan
Triantafyllos Afouras
Kristen Grauman
Venue: NeurIPS 2023 poster (2023)
Keywords: Instructional Videos
Task Graph
Keystep Recognition
TL;DR: We construct and use a task graph for keystep recognition. Contrary to the prior work, we use the longer activity context that improves state of the art performance on many instructional video datasets.

Abstract: Procedural activity understanding requires perceiving human actions in terms of a broader task, where multiple keysteps are performed in sequence across a long video to reach a final goal state---such as the steps of a recipe or the steps of a DIY fix-it task.  Prior work largely treats keystep recognition in isolation of this broader structure, or else rigidly confines keysteps to align with a particular sequential script.  We propose discovering a task graph automatically from how-to videos to represent probabilistically how people tend to execute keysteps, then leverage this graph to regularize keystep recognition in novel videos.  On multiple datasets of real-world instructional video, we show the impact: more reliable zero-shot keystep localization and improved video representation learning, exceeding the state of the art.

Video-Mined Task Graphs for Keystep Recognition in Instructional Videos
Kumar Ashutosh UT Austin and FAIR, Meta
Santhosh Kumar Ramakrishnan
UT Austin
Triantafyllos Afouras FAIR, Meta
Kristen Grauman UT Austin and FAIR, Meta
Abstract
Procedural activity understanding requires perceiving human actions in terms broader task, where multiple keysteps performed in sequence across long video to reach a final goal state-sur as the steps of a recipe or a DIY fix-it task. Prior work largely treats keystep recognition in isolation of this broader structure, or else rigidly confines keysteps to align with a predefined sequential script. We propose discovering task graph automatically from how-to videos represent probabilistically how people tend to execute keysteps, and then leverage this graph to regularize keystep recognition in novel videos. On multiple datasets of real-world instructional videos, we show the impact: more reliable zero-shot keystep localization and improved video representation learning, exceeding the state of the art. Project Page: https://vision.co www.uuexa..ceom wuspppojccss///uskkk ggaaptp
1 Introduction
Instructional "how-to" videos online allow users to master new skills and everyday DIY tasks, from cooking to crafts to sports [51]. In the future, AR assistants able to parse such procedural activities could augment human skills by providing interactive guidance throughout the task in sync with the user's visual context [25, 56, 64], by automatically creating video summaries of the most important information [2, 23, 54]. Similarly, human expert demonstration videos have the potential steer robot behavior in the right direction for complex sequential tasks that have notoriously sparse rewards [52, 62, 81].
In procedural activity, there is single task goal that a person accomplishes by executing series of keysteps, some which have causal dependencies. For example, to make tiramisu, keysteps include whisk the eggs, lay out the ladyfinges, sprinkle the cocoa-aa and the cocoa must be sprinkled only after laying ladyfingers in the pan; to replace a bike tube, the wheel needs to be removed from the bicycle, then the old tube deflated and removed before the video recognition tasks focused on naming an action in short video clip [13, 14] like shaking hands, playing instruments, etc., procedural activity understanding requires perceiving actions in terms of the broader goal, breaking down a long-form video into its component keysteps.
is fitted in. Thus, unlike mainstream
To address keystep recognition, prior work has proposed creative ideas to either match video clips to keystep names based on the transcribed narrations [45, 55] or align visual steps to rigid linear script (c.g., with dynamic time warping) [15, 18, 19, 36]. Other methods pose keystep recognition as a classification problem and label each fixed-sized chunk into one of the possible classes [48, 50, 77, 79, 80, 88]. However, these existing approaches face important limitations. Simple feature-keystep similarity matching and classification assume all actions are independent and can appear anywhere throughout the video, while the existing alignment models assume every keystep will match some
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Video-Minnd Graph
take out the slice
broad
Score-based
put slice of bread
run the toester and
Keystep
get an prepared
elice
flpp repeatly
take the slice of broad
adjust
Assignment
of bread
Ours using
-*-
put a siice of bread
run the loaster and adjust
take out the slice breed
take out the slice of breed
flip clothes repeatly
Task Graph
Figure I: Our method uses a video-mined task graph as prior to update the preliminary keystep assignments. The visual signals confuse a toaster with iron and bread with clothes, whereas our method focuses on the broader context using the task graph and assigns the correct keystep labels. When the visual signal predicts taking out bread, we instead correctly map running the toaster since taking out can only happen after putting the bread and running the toaster.
video neitent-neither of which holds universally. Furthermore, the status quo is to rely on text- based knowledge bases to represent the likely order of keysteps [19, 45, 55], e-g. WikiHow, which fails to encapsulate the rich variety of ways in which the procedure may be executed in practice.
We propose to regularize keystep predictions on novel videos based on task graph automatically mined from how-to videos. The task graph is probabilistic data structure capturing the keysteps (nodes) and their dependency relationships (edges). First, we show how to automatically discover the graph structure directly from unlabeled, narrated how-to videos. Notably, video demonstrations are much richer than scripted list of (text) steps like WikiHow; they show how to perform the task and, through different video instances, reveal the strength of dependencies between steps and the alternative ways in which the same goal can be reached. Next, we perform keystep recognition on novel videos using the task graph as prior for task execution. Here we develop a beam-search approach in which keysteps confidently recognized from the visual and/or narration inputs are anchors, and subsequent less-confident steps are inferred leveraging the graph to find high probability path. The task graph allows our model to "see the forest through the trees," " since it can anticipate the overall are of progress required to complete an instance of the full task.
Ours is the first work to use task graphs to enhance keystep prediction in instructional videos, and the first to discover a probabilistic task graph model directly from video. We first demonstrate that our novel approach improves zero-shot keystep localization for two challenging procedural activity datasets, COIN [67] and Cross' Task [89], outperforming prior work [18, 19, 45, 79]. We also show that our graph learned from real-world videos surpasses the prior supplied by traditional written scripts. Next, we show that our task graph improves video representation learning for the large-scale How To 100M dataset [51], where our corrected keystep pseudo-labels benefit pretraining compared to sfate-of-the-art keystep understanding work [45] and popular multimodal embeddings [50, 79]. In addition, we show the resulting pretrained video representations benefit multiple downstream tasks: keystep classification, keystep forecasting, and task classification. Finally, visualizing our learned task graphs, we show their ability to discover ties even across different tasks.
2 Related Work
Keystep Recognition and Localization. Keystep recognition for instructional video is focus for multiple recent influential datasets [51, 67, 89]. COIN [67] and CrossTask [89] offer manually annotated keysteps for more than 900 keystep labels and 198 diverse procedural tasks. The even larger HowTo100M dataset [51] covers tens of thousands of tasks; while not labeled for keysteps due to its massive size, recent work shows the promise of (noisily) localizing keysteps in How 1000 using a text-based matching between keysteps from a knowledge base (c.g.. WikiHow) and the words spoken in the how-to video narration [45, 55, 86]. Our approach builds on this idea when mining videos to form a task graph.
Grounding keysteps in instructional videos [6. 19, 20, 21, 50, 79, 89] is crucial for procedural planning [9, 12, 16, 40, 61, 71, 83, 85) and learning task structure [55, 87J. Some prior work localizes the keysteps by finding a similarity score between keystep (text) embeddings and video features using a multimodal embedding [50, 79], while others learn an embedding to map corresponding keysteps close together [6]. Unlike our approach, this assignment ignores the broader context about

---

the keysteps and their sequence. Another line of work uses Dynamic Time Warping (DTW) to ground keysteps to video [11, 15, 19, 40]. These methods take as input an ordered list of keysteps and localize them in the video while preserving the given ordering. While this has the potential advantage of enforcing known ordering, existing methods do so rigidly: the single linear order is required, and it is assumed that all the actions are guaranteed to be present in the video-a a very strong assumption for unconstrained video. While Drop-DTW [18] removes the last assumption by introducing a mechanism that allows dropping outliers, it remains constrained by the monotonic ordering. The set-supervised action recognition method [47] proposes a more relaxed pairwise consistency loss that uses weakly labeled videos and encourages the attentions on actions to follow similar ordering. In contrast to any of the above, our proposed method uses a probabilistic task graph to guide the localization process and correct predictions based on the keystep transition patterns discovered in in-the-wild video demonstrations.
Graphs for Video Understanding. Prior work uses graphs to understand spatio-temporal relations between objects and actors in videos [7, 53, 74, 82]. Such modeling helps to surface underlying relationships that may not be captured implicitly by models. Graph Convolutional Networks (GCN) are another promising method to incorporate graph structure in the training process [30, 38, 53, 58]. Earlier work in activity recognition has explored a variety of statistical models to represent complex sequential activities, such as Bayesian Logic Networks [68], dynamic Bayesian Networks [60], AND- OR graphs [35], latent SVMs [39]. and sauph-pasiing neural networks [57]. Our work is distinct for generating data-driven graphs from large-scale video samples, rather than exploit a predefined statistical model, and for bootstrapping noisy activity labels for recognition.
Methods for unsupervised procedure learning aim to discover the common structure from a set of videos showing the same task [2, 22, 59, 86] in order to reveal a common storyline [2, 22, 59] or in Paprika [86] (a concurrent approach) to generate pseudo-labels for video feature learning [86]. The goal of discovering the latent procedural structure resonates with our task graph formation; however, unlike the prior methods, we show how the task graph serves as an effective prior for accurate keystep recognition from video. Paprika [86] uses task graph nodes pretraining signal- their constructed graph is probabbiiiiss,, cannot represent that some transitions are more likely than others, and cannot be directly used for keystep recognition. Additionally, fusing supervisory signals from the graph and a weakly-supervisee similarity metric between video features and candidate keysteps, eliminating the need for explicit graph annotation [19, 64).
approach predicts keysteps by
Video Representation Learning. Pretraining to extract meaningful visual representations useful for many downstream tasks including action recognition [26, 33, 42, 43, 76] and action anticipation [1, 27, 28, 32, 49]. The pretraining objective is either to map the visual representations to meaningful classes [8, 45] or to its equivalent text representation [3, 44, 50, 79]. Text-guided pretraining further enables tasks like text-to- viideo retrieval [17, 24, 48, 79, 84] or video captioning [31, 48, 72, 78). is desirable pretrain on large video datasets [13, 14, 34, 51] for better generalization. In particular, HowTo 1000 [51] is the largest instructional video dataset (134,472 hours of video); its scale makes annotations for keysteps impractical. Recent work uses external WikiHow (text) steps to generate keystep classes for pretraining [45, 55]. However, the generated keystep classes are noisy due to misalignments [37] and non-visual narrations [4]. which affects the resulting representations. We show how to use a task graph to improve keystep label assignment across the massive dataset, which in turn significantly improves the resulting video representation and downstream benchmarks.
3 Technical Approach
We propose to discover task graphs from how-to videos and then use them as a prior for keystep recognition. Given keystep vocabulary (in text only) and videos from various instructional tasks, our goal is to automatically localize any instances of those keysteps in each video.
To that effect, we first use external text corpora to obtain keystep vocabulary. Next we obtain preliminary keystep labels by linking visual and/or narration representations between the video clips and candidate keystep names. Then we use those (noisy) keystep labels to construct a task graph, and finally we use the preliminary keystep labels and task graph prior to obtain high-quality keystep labels. The recognized and localized keysteps are themselves useful output of the method. We also explore using the inferred keystep labels to support large-scale video representation learning for instructional videos. Fig. 2 contains an overview of the method.
3

---

Task Construction
Task Graph
Keystep Recognition using Graph
T
Video Encoder
Similarit--bsedd Keyslep
Video Encoder
Me rle)
Video Encoder
Proposed Keystep Assignment
(e4, ri))
Keystep Set XC
Video
Video Encoder
2 7
(14 r4g)
f1 ne))
V2
Figure 2: Overview of the proposed keystep recognition using our video-mined task graph. Left: We obtain similarity-based keystep k for each video clip in the dataset using similarity between keysteps and text and/or video features. Top middle: We use the inferred keystep labels to learn a probabilistic task graph T. Right: Finally, we keep confident video segments and use the task graph priors to obtain the final keystep predictions. See text.
Task Definition. We have two inputs: (1) an unannotated dataset of narrated instructional videos D = [1:)_1) and (2) a keystep vocabulary K. Each video V; in D is comprised of a sequence of clips, each which has an associated spoken narration provided by the how-to demonstrator (and converted to text with ASR): Vi = {(11, n1). .... (Mp2 mpp;)) where et and ny are the visual and text segment corresponding to t clip in the instructional video. The keystep vocabulary K. is an unordered set of natural language terms for all the relevant keysteps in the tasks depicted D. For example, if the dataset contains the tasks "make tiramisu" and "fix bike derailleur", then K. would contain terms like (whisk eggs, soak ladyfingers, To give sense of scale, datasets in experiments contain 18 1,059 unique tasks and 105 to 10,588 unique keystep names. We do not assume the task labels are known per video. Note that words in the keystep vocabulary are not equivalent to the spoken narrations- latter is unconstrained.
prop up the bike, shift bike to highest gear...).
Our goal to predict the correct keystep label k E K. for every (v,, nz). For notation simplicity, we refer to localized keystep predictions as k; and keystep names in the vocabulary as k;, for i + t.
Sourcing a Keystep Vocabulary. To obtain a keystep vocabulary K., we consult existing text knowledge bases, namely WikiHow and the vocabulary curated by experts for the COIN dataset [67]. WikiHow [75] contains written instructions of more than 240K how-to tasks. Each article has list of steps that needs to be taken to achieve the desired task. For example, "Make Instant Pudding" has steps "Tear open the instant pudding mix and pour it into the bowl", "Pour the mixture into small serving bowls". - Note that several tasks share common keysteps, e.g. "Pour the mixture into small serving bowls" " can happen many recipes. our experiments, we either use keysteps provided in COIN [67] (IAC 749) and CrossTask [89] (IAC 105), or WikiHow keysteps for the HowTo 10M [51] dataset ([A) = 588). See [45] for details on keystep set curation and Supp. for details.
Preliminary Keystep Assignment. First we make preliminary estimate of each kz- Following recent work [45, 79], we draw the similarity between (1) language features for the keystep names k; and (2) visual and/or language features for the video clip (v). Specifically, let fo : [gxlWXCCM
RD and fn R E. be the D-dimensional visual encoder and text encoder. respectively. Here, (H, denotes (height, width, channels, time) and L is the maximum language token length. Correspondingly. for every segment (vt, n2) we obtain feature vectors fo (vz) and fn (r+). Since keystep names are themselves text sentences, we also use fr. (k:) to obtain each keystep embedding. Here we denote f(,, ni) as generic feature extractor that can be either f. or fn or combination of both (to be specified per experiment). We obtain the preliminary keystep assignments kn argmax ( n4)" f. (k.). Next, will use these (noisy) keystep estimates to construct our task graph, which in turn will allow us to improve our keystep assignments
Instatt Instant-Pudding Pudding

---

Dieccionsl Thanalfons
Top-i Nest Keyatop Tranatione
Preporn the gandan
Place mrzzzrdls cheese
wocos the botoes the pizze
Maahh rargo feah with ter untll you gat pupp minrss
Gol tarn Jokk stannd
Pourine rg warr
Al wean quric
in
Add
gandr unit seradieed
Cutla chesse of choice
Tornere fance a3d Iu jaie at spai
Support the vehide with dands
Iruullooon welpprrt toe)
of rosole to ulludling
Fo in the lintll caion
It's
and the roadd becu golliious
Raiss the veliils uding cM jok
Cook mudvoorrs
and enjoy
Mango
Figure 3: Visualization of properties emerging from the video-mined task graph. Some of the keysteps are directional e.g., pouring gelatin into boiling water must be preceded by the keystep prepare gelatin (left). Some examples of top-4 next keysteps (center), and visualization showing keystep sharing discovered across related How To100M tasks (right). Best viewed in zoom.
for all clips. These initial estimates & will also serve as a bascline, corresponding to what is done in practice today by existing multimodal methods using either visual [79] or narration text [45] features.
Video-Mined Task Graphs. Having obtained rough keystep assignment, we next construct a task graph to capture how keysteps are related to each other. Our task graph design is motivated by two key observations. First, keysteps can share different relationships. Some keystep pairs are directional, that is, one is the precursor to the other (e.g.. whisking egg must be preceded by breaking an egg); others are simply connected, meaning they often both appear an activity but with less constrained temporal ordering (e.g., whisking egg and sifting flour), while others are unconnected, meaning they support different task goals altogether (c.g.. mixing the salad and cutting wood with a saw). Second, multiple video demonstrations of the same task share the same high-level objective and hence similar keysteps, yet not necessarily in the same temporal order. For example, two how-to's for making pizza may use different ingredients and perform steps in different order.
Hence, rather than dand-nesign the task graph [19, 64], we propose to mine it directly from video samples. In addition, rather than encode possible transitions uniformly [86], we propose to represent them probabilistically. Finally, rather than constrain the graph to be representative of single task [19), we aim to discover single task graph across all tasks, such that related tasks can share information (e.g., whisk eggs would be common to many different recipes, and any sequential patterns surrounding it could inform other tasks in the graph). See Fig. 3 (right).
Formally, the task graph T= = (V, E, w) has all the keysteps as nodes, i.e., V KC and all transitions as edges, E' = K. x K. Naturally, we want the graph to be directed and weighted so that more probable keystep transitions have higher weights. For any pair of keysteps k; and ky. we define the weights of the edges as:
Σ Σ 1(ke = kis Kes = kj)
VED tElV
w(ki, T)
Σ Σ VED DE
Σ 1(ke = Kis Reet km)
where 1 is the indicator function. In other words, the weight of an edge between k; and ky is the count of transitions between the two keysteps normalized by total count of keysteps K; being exccuted. The normalization converts the weight into probability distribution and the sum of all outgoing edges is 1, i.e. Wk; E KC, Ek,ek w(kk, k.) = 1.
Fig 3 (left) shows interesting properties emerging from the task graph. Some pairs of keysteps are directional, e.g., only after preparing the gelatin can be poured into the boiling water. Fig 3 (middle) shows example top-4 transitions-al of which show the expected trend. Finally, the keystep transition heatmap (right) shows that the task graph discovers transitions between keysteps of related tasks like (luning ukulele, fixing violin string) or (kombucha lea, kombucha scoby), while also detecting that neither pair shares with the other. We stress that these inter-task relationships are a direct consequence of our vidco-mined, probabilistic keystep transitions, unlike [19, 64, 86].
Keystep Update Using the Video-Mined Task Graph. Next, we use the preliminary keystep labels k; and task graph T to obtain corrected keystep labels kt Intuitively, we want the task graph to regularize the initial estimates: keep keystep labels with strong signal of support from the visual and/or text signal in the video, but adapt those keystep labels with low confidence using the prior given by the graph structure T.
5

---

Specifically, we estimate the confidence score for keystep hy as the similarity between the video feature(s) f(r; me) and the keystep name feature (k(): s(k,) f(,, nz) (n (k+). Given any high-confidence pair hi- and het, where t- and 1+ are the closest high-confidence time instances before and after t, respectively, we find the highest probability path in T between by and het. Formally.
Re he PathSeeachh&t ,et,()
if f(1,, nz) (n(e)) 27 otherwise
where y is confidence threshold, and 1- and 1+ are time instances with confidence more than Y- PathSearch finds the maximum probability path between k and ky- from the task graph T. We convert all the probabilities to their negative log and use Dijkstra's algorithm to find the minimum weight path. To account for self-loops, we prepend and append h,- and kit, respectively to the resulting path. Since the obtained path can have a variable number of keysteps, we assign the discovered keysteps uniformly between t- and ++ (see Supp. for an example).
The idea of PathSearch is inspired from Beam Search algorithms, commonly used in Machine Translation [5, 10, 29, 65] for pursuing multiple possible sequential hypotheses in parallel, where we assume ki- and ki+ as the start and end token. Instead of finding the maximum probable token (keystep in our context), Beam Search finds a sequence of tokens that maximize the overall likelihood of the selected token sequence. The above process yields corrected keysteps k, that we use as our predicted keystep label. Fig. 4 shows some qualitative results. Note that PathSearch algorithm's s time complexity is ((I(()) that introduces minimal overhead. In general, this overhead is even less than forward pass to the model.
Keystep Localization and Instructional Video Representation Learning. We explore the effective- ness of our approach in two settings: zero-shot keystep localization and representation learning for instructional videos. For zero-shot keystep localization, we evaluate the accuracy of our model's final keystep predictions compared to withheld ground truth labels. We stress that the results are zero-shot, since we are provided no clips annotated with their keysteps.
For representation learning, we augment the original unannotated dataset with pscudo-labeled keysteps to create D' = (V.)(2), where V; = {(vi, Ri, narrations, and our model's inferred pseudo-labels. Our objective is to learn a video representation (v := l x WxCxT + k(x] such that g (u,;; 0) = k2 Here (H, W, T') denote (height, width, channels, time) in video segment. This is a standard classification problem and we choose cross entropy as the training loss.
ki), kit (Via.:"1. kiy,)) } are the clips,
To evaluate the quality of the resulting learned representation Fv, consider several downstream tasks. First, we evaluate task classification on D against the withheld ground truth task labels (e.g.. is the video depicting "make tiramisu" or "make omelet"), common task for feature learning in instructional video [3, 8, 45] that can be evaluated more readily on large-scale datasets given the availability of task labels (vs. unavailability of keystep labels). In addition, we evaluate keystep classification given the temporal region of keystep and keystep, forecasting, where we must anticipate the next keystep given the video observed far.
Network Architecture and Implementation Details. For zero-shot keystep recognition fo and fn fis-dimensional frozen visual and text encoders of VideoCLIP [79]. For representation learning, we use MP-Net [63] to compute sentence embeddings and a modified TimeSformer [8] with 10, 588 output classes as the visual encoder. The weights of the visual encoder are initialized to Kinetics [14] pretraining. For downstream tasks, we freeze the backbone and only replace the last linear layer with the dimension of the classification task, namely 778 and 133 output classes for keystep classification and forecasting in COIN and CrossTaask respectively, and 180 and 18 classes for task classification.
For zero-shot respectively, since video features offer stronger supervision. We observe that the performance not sensitive for |0.3, 0.5]: details in Supp. In experiments where we consider both the video and text modalities, during path search, in the case of conflicting keystep suggestions, we choose the video
keystep segmentation, we 7 0.5 and = 0.3 for text and video features,
"We also explored a variant using Bayes Recursive Filtering (BRF) [69] to update the keystep belief state, but found this model less effective, likely because BRF only looks backward in time thus using less temporal context. See Supp. for experimental comparisons.

---

Ours (C) ve DistentSuperviion (B)
A
take your two fingers and place middle
begin compression pushing down chest, that for thiny beals press cheat
push hard anough and
utlizz how much potato have
you don't nead much water here
you can't get a good clean scrub
pull out needle and press press
of the pallent
pull out the neecle and press of the patient
cut posato into strips
some water to
vessel
rinse the dish
press
pour
the patien!
of the patient
removal liuiid
removal liquid
potatoes/rust remover
Ours (C) ve VideoCLIP (B)
open the car key cover
remove rearview mirror remove
Instail the door
cut potato into strips
add seasoning salmon
fry the dough
remove
reinstall rearview mirror
sessoning salmon
seasoning
fry salmon
rearview mirror
rearview mirror
salmon
Figure 4: Qualitative examples comparing keystep recognition with DistantSupervision [45] (first
row) and VideoCLIP [79] (second row). Red/green denote incorrect/correct keystep predictions; yellow shows ASR narrations. Our proposed method is effective in correcting preliminary keystep assignments and reasons about the overall task structure. Best viewed in color and zoom.
keystep since the visuals tend be stronger See Supp. for experiments justifying this design. For representation learning, similar to [45], we train the video model for 15 epochs with SGD with learning rate 5 10-3 followed by 15 epochs with AdamW [46] with learning rate x 10-5, In both cases, the learning rate is decayed progressively by 10 times in epochs 11 and 14.
4 Experiments and Results
Datasets. We three public datasets of instructional videos-COIN. CrossTask, and HowTo100M- all which were compiled from in-the-wild data on YouTube, and are accompanied by ASR transcriptions of the YouTuber's spoken narrations (n²). COIN [67] and CrossTask [89] contain 11,827 and 2,750 instructional videos, respectively, and are annotated for 778 and 133 (749 and 105 unique keysteps, respectively) keystep labels spanning 180 and 18 tasks, respectively. We clip labels for evaluation only. HowTo 100x larger than the others) spread over 23,000 tasks. As noted above, we leverage WikiHow [75] obtain the keystep vocabulary K. for How To100M. We use COIN and CrossTask for both zero-shot keystep recognition and downstream task evaluation of our pretrained features. We HowTo100M for downstream tasks only, since it lacks ground truth keystep annotations.
[51] contains 1.22M instructional videos (i.c. more than
Evaluation Metrics. For keystep segmentation, we evaluate Frame-wise Accuracy (Acc) and Intersection over Union (IoU), following [18, 19, 79]. For every keystep k; Frame-wise Accuracy is the fraction of frames with ground truth k; that has the correct assignment. The overall Frame-wind Accuracy is the mean accuracy for every keystep. Likewise, IoU is the intersection over union of a keystep k; averaged for every i. Consistent with prior work [18, 19], do not consider background frames. For keystep classification, task classification, and keystep forecasting, we use the standard accuracy metric.
4.1 Zero-Shot Keystep Recognition
In this task, we predict keystep k; for each time instance in given video the test set. Following [79], make one keystep prediction per second. We compare the following competitive baselines:
DistantSupervision [45]. state-of-the-art model for zero-shot keystep recognition that predicts keysteps based on the text feature similarity between narrations and keysteps, i.c, f(2,, (e) = (nt).

---

Table 1: Zero-shot keystep recognition on COIN and CrossTask for three modality choices text, video and video-text. We outperform strong baselines on all tasks. '-' means the method is n/a.
Text-only
Video-only
Video-Text
COIN
CrossTask
COIN
CrossTask
COIN
CrossTask
Method
Acc
loU
Acc
loU
Acc
loU
Acc
loU
Acc
loU
Acc
loU
Random
0.0
0.0
0.01
0.01
0.0
0.0
0.01
0.01
0.0
0.0
0.01
0.01
VideoCIII [79]
13.2
4.0
28.5
6.5
13.3
4.0
28.5
6.5
Dup. [45]
3.0
3.7
Linear Steps
10.4
3.1
16.3
3.8
13.4
4.3
28.5
6.5
13.4
4.0
28.5
6.5
Auto-Reg [66]
10.2
3.1
16.4
3.7
13.6
4.3
28.5
6.5
13.7
4.2
28.5
6.5
Pruning Keysteps
11.3
3,4
16.4
3.8
13.4
4.2
28.5
6.5
13.5
4.1
28.5
6.5
Ours
16.3
5.4
20.0
4.9
15.4
4.7
28.6
16.9
5.4
28.9
6.7
03
0.1
4:02
0.0.1
4: 0.1
0.1
4: 0.0
4 1.00
4.0.1
= 0.1
0.1
4.0.0
Table 2: Task-leva keystep recognition on CrossTask. We outperform all meth- ods in accuracy despite lacking their privileged information.
Table 3: Task classification on HowTo100M. On both
modalities outperform all state-of-the-ard methods.
Method
Modality
Acc@1
Acc@
MIL-NCE [50]
6.2
19.7
Method
Acc
IoU
VideoCLIP [79]
7.9
25.5
Random
11.0
4.7
DistantSup. [45]
Video
9.5
30.1
Bag of Steps
20.5
13.7
DistantSup. [45]
Text
12.3
28.5
Drop-DTW [18]
22.3
Ours
Vidco
14.0
33.5
Graph2Vid [19]
24.8
16.8
0.3.3
0.
Ours
30.5
16.0
Ours
Text
15.5
35.0
= 0.2
:: 0.2
VideoCLIP [79]. A popular transformer-base contrastive pretraining approach for zero-shot video- text understanding. To apply it here, we use the cross-modal video feature similarity with the keysteps, i.., f((re m4) = (.(w)..
Bag of Steps. This baseline (devised in [19]) is similar to the first two, except here the keystep set only contains known steps in given task. Naturally, the number of candidate keysteps this case is much lower than the keystep set used above and by our model.
Auto-Regressive [66, 70]. Instead of constructing explicit task graph, implicit representation could also model dependencies between keysteps. We use transformer network to revise the preliminary noisy keystep labels (previous baselines) based their aggregation over time.
Pruning Keysteps. The keystep set generally broad and contains unlikely keysteps for some tasks, e.g., unscrew the bolt is irrelevant in the cooking task. We first cluster keysteps into C semantically similar clusters using k-means on their keystep embeddings and assign each video to one of the clusters per average similarity of the video's 's clips with the cluster members. Then, compute similarity between only the selected cluster's keysteps and the video features to infer the per-elip keystep labels.
Linear Steps. Instead of using task graph, this baseline uses linear order of keysteps as given in the dataset annotations. We still use keystep set K. for preliminary assignment.
Drop-DTW [18]. A SotA DTW-based approach where linear order of steps is assumed. requires a known order for execution for each task in the dataset.
Graph2Vid [19]. A SotA DTW-based approach that parses oon-probabilistic graph for each task and then performs Daw-based matching on all possible paths and chooses the one with the highest matching score.
Note that the Bag of Steps, Drop-DTW, and Graph2Vid models all have privileged information during inference compared to our model, namely the known task and its (ordered) list of keysteps. Hence below we compare those models separate experiment called task-level keystep recognition [19], where candidate keysteps for all methods come only from the subset of keysteps Kr per task T as mined from WikiHow (Krrl & (KD. In all other zero-shot experiments, we use the universal keystep vocabulary I.

---

Table Downstream evaluation on CrossTask and COIN for keystep recognition (SR), task recogni- tion (TR), and keystep forecasting (SF), using either an MLP (left) or transformer (right).
MLP
Transformer
CrossTask
COIN
CrossTask
COIN
Method
SR
TR
SF
SR
TR
SF
SR
TR
SF
SR
TR
SF
TSN [73]
36.5
73.4
ClipBERT [41]
30.8
65.4
S3D [50]
39.9
87.4
20.1
37.5
68.5
19.9
45.3
87.8
21.7
37.3
70.2
28.1
SlowFast [26]
44.9
89.7
23.4
32.9
72.4
23.0
48.5
89.8
24.0
39.6
71.6
25.6
VideoCLIP [79]
51.3
94.7
24.2
39.4
82.9
30.0
60.1
92.3
26.0
51.2
72.5
34.6
TimeSformer [8]
55.5
95.0
25.9
48.3
87.0
32.7
60.9
93.8
27.1
54.6
88.9
38.2
DistantSup. [45]
58.4
96.1
28.3
54.1
88.2
35.5
64.2
95.2
29.7
57.0
90.0
39.4
Ours
59.5
97.1
29.5
55.2
89.4
36.3
64.5
96.0
30.2
57.2
90.5
40.2
0.0.
0.0.1
6.1.1
4.00
0.0
0.1
+: 0.00
4:00
4.0.1
Results. Table shows the zero-shot results on COIN and CrossTask. Throughout, standard errors denote variation across different test data splits. In all the three variants (text-only, video-only, and video-text), our method outperforms strong basclines and prior work. We see a gain of up to 6.5% (relative 66%). Importantly, model's preliminary keystep assignments correspond to the VideoCLIP [79] and DistantSSperrision [45] baselines for the video-only and text-only settings; relative gains directly show the impact of our video-mined task graph in correcting those labels. In addition, our gains over Linear Steps show the impact of our full probabilistic graph structure, compared a prior based linear ordering of steps.
Fig. 4 shows some qualitative examples comparing our outputs with DistantSupervision [45] (top) and VideoCLIP [79] (bottom). The narration pushing for thirty beats is incorrectly mapped to using needle by DistantSupervision, whereas VideoCLIP confuses salmon with cloth. Our task graph prior improves recognition.
Table shows the task-level keystep recognition results. We outperform all methods, including the state-of-the-art Vraph2Vid [19] by 5.7% (relative 23%) in accuracy. Our IoU is similar to Graph2 We observe that the baselines conservatively assign the background label whenever confidence is low, which helps IoU since background is not counted in the union operation [18, 19]. In contrast, accuracy accounts equally for false negatives and false positives, making a more complete metric. We also emphasize that unlike Drop-DTW [18] and Graph2Vid [19], we do not assume keystep ordering from WikiHow recipes since that restricts the applicability to general in mn-the-wild instructional videos. Overall, our method provides significant advantage over all the strong baselines and achieves state-of-the-art keystep recognition.
4.2 Instructional Video Representation Learning for Downstream Tasks
Next we apply our model to learn features (v; 0) on the large-scale HowTo 10000 and assess their impact for multiple downstream tasks. We add comparisons to other popular pretrained representations, MIL-NCE [50], VideoCLIP [79], and TSN [73].
Table shows the task classification results compared to multiple state-of-the ooftthe-art art methods on the validation split of HowToo10MM the dataset use for pretraining Fv. Following [45], we infer task labels by predicting keysteps then mapping them back to the task category. Our approach outperforms all the existing methods. Again, gain of our improved laeudo-labels.
VideoCLIP and DistantSupervision shows the impact
Table 4 shows the results when transfer the features pretrained How 100M to downstream tasks on COIN and CrossTask We deploy both MLPs and transformers fine-tuned for each task,
Paprika [86] uses setting different from the SotA DistantSupervision [45], which makes their numbers not comparable; DistantSupervision's reported results are higher than those re- implemented in [86] for all tasks, making it stronger baseline to beat. Further, keeping our setting consistent with DistantSupervision allows compare with other SotA methods.
Note that the concurrent

---

add Snion
add fish
add mustard seeds
put bread in pan
cut onion
add
powdet
páncake
cut
top toost
rernove breaeeuker paaisiee from add salt
3dd spices
Taste steak
add sugait butter
oR steak
cucumbyysser Steak put vegerables
Tlip bread
dip breed in mixture pour mixture into panadd flour
mixture
put steak tlpp Steak
pack cucumbers jar
vanilla extract
pour
pour Vinegar
move steak on grill
whisk mixture
put jar water
check temperatyue
pour
pour milk
close lid
press coffee
lid
pour espresso
add coffee
Figure 5: Task graph visualization of CrossTask (35/108 keysteps). We only show top 5 transitions (excluding self-loops) within this keystep subset for clear visualization. The edges directed. Please zoom for best view.
Our results are strongest overall. We outperform the state-of-the-ee DistantSupervision [45] on all downstream tasks for both datasets under both architectures.
4.3 Task Graph Visualization
We display portion of the mined task graph CrossTask in Figure It contains 35 out of 108 keysteps with top 5 transitions labeled (to avoid clutter). We see some interesting properties. For example, "press coffee" happens only after "add coffee", "close lid" after "open lid" whereas "cut cucumber" and "cut onion" can both happen after each other. Again, this structure is discovered automatically from unannotated videos.
Conclusion
We introduced an approach to discover the structure of procedural tasks directly from video, and then leverage the resulting task graph to bolster keystep recognition and representation learning. Our model offers substantial gains over SotA methods, and our qualitative results also validate improvements. In future work we plan to explore video-mined task graphs for other video understanding tasks including procedure planning and mistake detection.
Acknowledgement
UT Austin is supported in part by the IFML NSF AI Institute. KG is paid as research scientist at Meta. We thank the authors of DistantSup. [45] and Paprika [86] for releasing their codebases.
10

---

References
[1] Yazan Abu Farha, Alexander Richard, and Juergen Gall. When will you do what?-anticipatin temporal occurrences of activities. In Proceedings of the IEEE conference on computer vision and pattern recognition.
pages 5343-5352, 2018. 3
Jean-Baptiste Alayrac, Piotr Bojanowski, Nishant Agrawal, Josef Sivie, Ivan Laptev, and Simon Lacoste- Julien. Unsupervised learning from narrated instruction videos. CVPR, 2016. 3,3
[3] Kumar Ashutosh, Rohit Girdhar, Lorenzo Torresani, and Kristen Grauman. Hiervl: Learning hierarchical vidco-language embeddings. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern
Recognition, 2023. 3, 6
[4] Kumar Ashutosh, Rohit Girdhar, Lorenzo Torresani, and Kristen Grauman. What you say is what you
show; Visual narration detection in instructional videos. arXiv preprint arXiv:230I 02307, 2023. 3 [5] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning
to align and translate. arXiv preprint arXiv: 1409.0473, 2014. 6
[6] Siddhant Bansal, Chetan Arora, and C. V. Jawahar. My view is the best view: Procedure learning from
egocentric videos. In ECCV, 2022. 2
[7] Fabien Baradel, Natalia Neverova, Christian Wolf, Julien Mille, and Greg Mori. Object level visual reasoning in videos. In Proceedings of the European Conference on Computer Vision (ECCV), pages 105-121, 2018.
[8] Gedas Bertasius, Heng Wang, and Lorenzo Torresani. space-time attention all you need for video understanding? In ICML, volume 2. page 4, 2021. 3, 6, 9
19] Jing Bi, Jicbo Luo, and Chenliang Xu. Procedure planning in instructional videos via contextual modcling and model-based policy learning. In Proceedingy of the IEEE/CVF International Conference on Compuler
Vision, pages 15611-15620 2021. 2
[10] Denny Britz, Anna Goldie, Minh-Thang Thang Luong, and Quoc Le. Massive exploration of neural machine translation architectures. arXiv preprint arXiv: aet::0703000000 03906. 2017. 6
[11] Kaidi Cao. Jingwei Ji. Zhangjie Cao. Chien-Ys Yi Chang. and Juan Carlos Niebles. Few-shot video classifica- tion via temporal alignment. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10615-10624, 2020.
[12] Meng Cao, Tianyu Yang, Junwu Weng, Can Zhang, Jue Wang, and Yuexian Zou. Locvtp: Video-text pre-training for temporal localization. In European Conference on Computer Vision, 2022.
[13] Joao Carreira, Eric Noland, Andras Banki Horvath. Chloe Hillier, and Andrew Zisserman. A short note about kinetics-666 -600. arXiv preprint arXiv: 1808,013800 01340. 2018. 1.3
[14] Joao Carreira and Andrew Zisserman. Quo vadis, action recognition? a new model and the kinetics dataset. In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6299-6308,
2017. 1. 6
[15] Chien- Yi Chang, De-An Huang, Yanan Sui, Li Fei-Fei, and Juan Carlos Nicbles. D3tw: Discriminative differentiable dynamic time warping for weakly supervised action alignment and segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3546-3555,
2019. 1,3
[16] Chien-Ys Yi Chang, De-An Huang. Danfei Xu, Ehsan Adeli. Li Fei-Fei. and Juan Carlos Niebles. Procedure planning in instructional videos. In Computer Esion-ECCV// 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI, pages 334-350. Springer, 2020. 2
[17] Xing Cheng. Hezheng Lin, Xiangyu Wu, Fan Yang, and Dong Shen. Improving video-text retrieval by multi-stream corpus alignment and dual softmax loss. arXiv preprint arXiv:2109, 1XX::2009,04299. 042990. 2021. 3
[18] Mikita Dvornik, Isma Hadji, Konstantinos G Derpanis, Animesh Garg, and Allan Jepson. Drop-DTW: Aligning common signal between sequences while dropping outliers. Advances in Neural Information
Processing Systems, 34:13782-13793 2021. 1, 2, 3, 7, 8.9
[19] Nikita Dvorikk, Isma Hadji. Hai Pham, Dhaivat Bhatt, Brais Martinez, Afsaneh Fazly, and Allan D Jepson. Flow graph to video grounding for weakly-supervised multi-step localization. Computer -Ccv 2022: 17th European Conference, Tel Aviv; Israel, October 23-27, 2022, Proceedings, Part XXXV, pages
319-335. Springer, 2022. 1, 2, 3, 5, 7, 9
[20] Nikita Dvornik, Isma Hadji, Ran Zhang, Konstantinos G Derpanis, Richard P Wildes, and Allan D Jepson. Stepformer: Self-supervised step discovery and localization in instructional videos. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 18952-1896 2023.
[21] Ehsan Elhamifar and Dat Huynh. Self-supervised multi-task procedure learning from instructional vidcos. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVII 16, pages 557-573. Springer,
S 2020. 2
[22] Ehsan Elhamifar and Dat Huynh. Self-supervised multi-task procedure learning from instructional videos.
In ECCV, 2020. 3
[23] F. Elhamifar and Z. Naing. Unsupervised procedure learning via joint dynamic summarization. ICCV,
2019. 1
[24] Han Fang, Pengfei Xiong, Luhui Xu, and Yu Chen. Clip2video: Mastering video-text retrieval via image
clip. arXiv preprint arXiv:2/06. / 1097, 2021. 3
[25] Alireza Fathi, Ali Farhadi, and James M Rehg. Understanding egocentric activities. In 2011 international
conference oR computer vision, pages 407-414. IEBE, 2011. 1
[26] Christoph Feichtenhofer. Haoqi Fan. Jitendra Malik, and Kaiming He. Slowfast networks for video
recognition. In Proceedings of the IEEE/CVF international conference on computer vision, pages 6202-
11

---

6211, 2019. 3,
[27] Antonino Furnari and Giovanni Maria Farinella. Rolling unrolling Istms for action anticipation from fist-person video. IEEE transactions on pattern analysis and machine intelligence, 43(11):4021-4033
2020. 3
[28] Jiyang Gao. Zhenheng Yang. and Ram Nevatia. Red: Reinforced encoder-decoder networks for action anticipation. arXiv preprint M.Kiv1177..4455 2017.
[29] Jonas Gehring, Michael Auli, David Grangier, and Yann N Dauphin. A convolutional encoder model for neural machine translation. arXiv preprint arXiv: 1.000244, 2016.
[30] Pallabi Ghosh, Yao, Larry Davis, and Ajay Divakaran. Stacked spatio-temporal graph convolutional networks for action segmentation. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 576-585, 2020. 3
[31] Simon Ging, Mohammadreza Zolfaghari, Hamed Pirsiavash, and Thomas Brox. Coot: Cooperative hierarchical transformer for video-text representation learning. Advances in neural information processing
systems. 33:22605-2266 22618, 2020.
[32] Rohit Girdhar and Kristen Grauman. Anticipative video transformer. In Proceedings of the IEEE/CVF
International Conference on Computer Vision, pages 13505 13505-13515, 2021.
[33] Rohit Girdhar, Mannat Singh, Nikhila Ravi, Laurens van der Maaten, Armand Joulin, and Ishan Misra. Omnivore: single model for many visual modalities. In Proceedings of the IEEE/CVF Conference on
Computer Vision and Pattern Recognition, pages 16102-161 12, 2022. 3
[34] Kristen Grauman, Andrew Westbury, Eugene Byme, Zachary Chavis, Antonino Furnari, Rohit Girdhar, Jackson Hamburger, Hao Jiang, Miao Liu, Xingyu Liu, et al. Ego4d: Around the world in 3,000 hours of egocentric video. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 18995-19012, 2022. 3
[35] A. Gupta. P. Srinivasan. J. Shi, and L. Davis. Understanding videos, constructing plots learning a visually grounded storyline model from annotated videos. In CVPR, 2009. 3
[36] Isma Hadji. Konstantinos G Derpanis, and Allan Jepson. Representation learning via global temporal alignment and cycle-consistency. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages 11068-1077, 2021.
[37] Tengda Han, Weidi Xie, and Andrew Zisserman. Temporal alignment networks for long-ter vidco. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2906-2916 16,
2022. 3
[38] Deng Huang, Peihao Chen, Runhao Zeng, Qing Du, Mingkui Tan, and Chuang Gan. Location aware graph convolutional networks for video question answering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1021-11028, 2020.
[39] Hamid Izadinia and Mubarak Shah. Recognizing complex events using large margin joint low-level event
model. In ECCV. 2012. 3
[40] Dohwan Ko, Joonmyung Choi, Juyeon Ko, Shinyeong Noh, Kyoung- -Wonn On, Eun-Sol Kim, and Hyunwoo J Kim. Video-text representation learning via differentiable weak temporal alignment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5016-5025,
2022. 2.3
[41] Jie Lei, Linjie Li, Luowei Zhou, Zhe Gan, Tamara L Berg, Mohit Bansal, and Jingjing Liu. Less is more: Cliphert for video-and-lange lannuuuage learning via sparse sampling. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 7331-7341, 2021.
[42] Kunchang Li, Yali Wang, Junhao Zhang, Peng Gao, Guanglu Song, Yu Liu, Hongsheng Li, and Yu Qiao. Uniformer: Unifying convolution and self-attention for visual recognition. arXiv preprint arXiv:2201. 094500 2022, 3
[43] Yanghao Li, Chao- Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 4804 4814,
2022. 3
[44] Kevin Qinghong Lin, Alex Jinpeng Wang, Mattia Soldan, Michael Wray, Rui Yan, Eric Zhongcong Xu, Difei Gao, Rongcheng Tu, Wenzhe Zhao, Weijie Kong, al. Egocentric video-language pretraining, In NeurlPS, 2022.
[45] Xudong Lin, Fabio Petroni, Gedas Bertasius, Marcus Rohrbach, Shih-Fu Chang, and Lorenzo Torresani.
Learning to recognize procedural activities with distant supervision. In Proceedings of the IEEE/CVF
Conference on Computer Vision and Puttern Recognition, pages 13853-13863, 2022. 1, 5, 7,
9, 10
[46] Ilya Loshchilov and Frank Hutter.
Decoupled weight decay regularization.
arXiv preprint
1 2017. 7
[47] Zijia Lu and Ehsan Elhamifar. Set-supervised action learning in procedural task videos via pairwise order consistency. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19903-19913, 2022. 3
[48] Huaishao Luo. Lei Ji, Botian Shi, Haoyang Huang. Nan Duan, Tianrui Li, Jason Li, Taroon Bharti, and Ming Zhou Univl: A unified video and language pre-training model for multimodal understanding and generation. arXiv preprint 2002 00333,,3 2020. 1,
[49] Esteve Valls Mascaro, Hyemin Ahn, and Dongheui Lee. Intention-condiiooned long-term human egocentric
action forecasting @ ego4d challenge 2022. arXiv preprint arXiv:2207. 12080, 2022. 3
12

---

[50] Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic. and Andrew Zisserman. End-to-end learning of visual representations from uncurated instructional videos. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9879-9889. 2020, 1, 3. 8, [51] Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makaaann Tapaswi. Ivan Laptev, and Josef Sivie. Nowto100m: Learning a text-video embedding by watching hundred million narrated video clips. In Proceedings of the JEEE/CVF International Conference on Computer Vision, pages 2630-2640, 2019. 1, 2,
3. 7.
[52] Tushar Nagarajan and Kristen Grauman. Shaping embodied agent bchavior with activity-context priors from egocentric video. Advances in Neural Information Processing Systems, 34:29794-2996 29805, 2021. 1 Tushar Nagarajan, Yanghao Li, Christoph Feichtenhofer, and Kristen Grauman. Ego-topo: Environment affordances from egocentric video. In Proceedings of the IEEE/CVF Conference on Computer Vision and 2020.
[53]
Pattern Recognition, pages
[54] Medhini Narasimhan, Arsha Nagrani, Chen Sun, Michael Rubinstein, Trevor Darrell, Anna Rohrbach, and Cordelia Schmid. Tl:dw? summarizing instructional videos with task relevance and cross-modal saliency.
In ECCV, 2022. 1
[55] Mcdhini Narasimhan, Licheng Yu, Sean Bell, Ning Zhang, and Trevor Darrell. Learning and verification
of task structure in instructional vidcos. arXiv preprint arXiv:2303. Ttt:2233./3511 /3519, 2023. 1, 2, 3
[56] Hamed Pirsiavash and Deva Ramanan. Detecting activities of daily living in first-person camera views. In
2012 IEEE conference on computer vision and pattern recognition, pages 2847-2854, IEEE, 2012. 1 [57] S Qi, W Wang. B Jia. J Shen. and SC Zhu. Learning numan-objec interactions by graph parsing neural networks. In RCCVV 2018. 3
[58] Maheen Rashid, Hedvig Kjellstrom, and Yong Jae Lee. Action graphs: Weakly-supervised action localiza- tion with graph convolution networks. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 615-624, 2020. 3
[59]
Ozan Sener, Amir Zamir, Silvio Savarese, and Ashutosh Saxena. Unsupervised semantic parsing of video collections.
CVPR, 2016. 3
[60]
Yifan Shi, Yan Huang, David Minnen, Aaron Bobick. and Irfan Essa. Propagation networks for recognition of partially ordered sequential action. In CVPR, 2014. 3
[61]
Nina Shvetsova, Brian Chen, Andrew Rouditchenko, Samuel Thomas, Brian Kingsbury, Rogerio S Feris, David Harwath, James Glass, and Hilde Kuehne. Everything at once-multi-modal fusion transformer for video retrieval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 20020-20029, 2022. 2
[62] Laura Smith, Nikita Dhawan, Marvin Zhang, Pieter Abbeel, and Sergey Levine. Avid: Learning multi-stage tasks via pixel-level translation of human videos. arXiv preprint 191.v:9112.0445:: 2019. 1
[63] Kaitao Song. Xu Tan, Tao Qin, Jianfeng Lu, and Tie- Liu. Mpnet: Masked and permuted pre-training for language understanding. Advances in Neural Information Processing Systems, 13:66857-16867 2020.
[64] Bilge Soran, Ali Farhadi, and L. Linda Shapiro. Generating notifications for missing actions: Don't forget to turn the lights off! In ICCV, 2015. 1, 3,5
[65]
Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014. 6
[66]
llya Sutskever, Oriol Vinyals, and Quoe V. Le. Sequence to sequence learning with neural networks. In P Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS' 14, page 3104-3112, Cambridge, MA, USA, 2014. MIT Press. 8
[67] Yansong Tang, Dajun Ding. Yongming Rao, Yu Zheng, Danyang Zhang, Lili Zhao, Jiwen Lu, and Jie Zhou. Coin: A large-scale dataset for comprehensive instructional video analysis. In Proceedings of the IFFF/CV Conference on Computer Vision and Pattern Recognition, pages 1207-1216, 2019. 2, 4, Temorth, F. De la Torre, and M. Beetz. Learning probability distributions over partially-ordered human everyday activities. In ICRA, 2013.
[68]
[69] Sebastian Thrun. Probabilistic robotics. Communications of the ACM, 45(3):52-57 57, 2002. 6
[70]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems. volume 30. Curran Associates. Inc., 2017. 8
[71] Hanlin Wang, Yilu Wu, Sheng Guo, and Limin Wang. Pdpp: Projected diffusion for procedure planning in instructional videos. arXiv preprint 203. 2023. 2
[72] Junke Wang. Dongdong Chen, Zuxuan Wu, Chong Luo, Luowei Zhou, Yucheng Zhao, Yujia Xie, Ce Liu, Yu- Gang Jiang. and Lu Yuan. Omnivl: One foundation model for image-language and video- languaae tasks. arXiv preprint arXiv:2209.077 02260007.666....0 2022.
[73] Limin Wang. Yuanjun Xiong. Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang. and Luc Van Gool. Temporal segment networks: Towards good practices for deep action recognition. In European conference on
computer vision, pages 20-36. Springer. 2016. 9
[74] Xiaolong Wang and Abhinav Gupta. Vidcos as space-time region graphs. In Proceedings of the European
conference on computer vision (ECCV), pages 497, 2018. 3
[75] Wikihow, https:/ /////ww /www. wikihow. com. 7,7
[76] Chao-Yua Wu, Yanghao Li, Karttikeya Mangalam, Haoqi Fan, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Memvit: Memory- augmeeee multiscale vision transformer for efficient long-term vidco
13

---

recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13587-13597, 2022. 3
[77] Hu Xu, Gargi Ghosh, Yao Huang, Prahal Arora, Masoumch Aminzadch, Christoph Feichtenhofer, Florian Metze, and Luke Zettlemoyer. VIm: Task-agnostic video-language model pre-training for video understanding. arXiv preprint arXiv:210S.0999:
2021.
[78] Hu Xu, Gargi Ghosh, Yao Huang. Prahal Arora, Masoumeh Aminzadeh. Christoph Feichtenhofer. Florian Metze, and Luke Zettlemoyer. Vlm: Task-agnostic video-language model pre-training for video understanding. arXiv preprint prepritt arXiv:2/05.0990
2021. 3
[79] Hu Xu, Gargi Ghosh, Po- Yao Huang, Dmytro Okhonko, Armen Aghajanyan, Florian Metze, Luke Zettlemoyer, and Christoph Feichtenhofer. Videoclip: Contrastive pre-training for zero-shot video-text understanding. arXiv preprint arXiv:2109. 14084, 2021. 1, 2, 3, 4, 5, 6, 7, 8.9
[80] Jianwei Yang. Yonatan Bisk. and Jianfeng Gao. Taco: Token-aware cascade contrastive learning for video-text alignment. In Proceedings of the IEER/CVF International Conference on Computer Vision,
pages 11562-11572 2021. I
[81] Hejia Zhang and Stefanos Nikolaidis. Robot learning and execution of collaborative manipulation plans from youtube cooking vidcos. arXiv preprint arXiv:1911, 10686, 2019. 1
[82] Yubo Zhang, Pavel Tokmakov, Martial Hebert, and Cordelia Schmid. structured model action detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
pages 9975-9984, 2019. 3
[83] He Zhao. Isma Hadji, Nikita Dvomikk Konstantinos G Derpanis, Richard P Wildes, and Allan D Jepson.
P3iv: Probabilistic procedure planning from instructional videos with weak supervision. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 2938-2948, 2022. 2
[84] Shuai Zhao, Linchao Zhu, Xiaohan Wang, and Yi Yang. Centerclip: Token clustering for efficient text-video
retrieval. arXiv preprint arXiv:2205.000 00823,0833 2022.
[85] Yiwu Zhong, Licheng Yu, Yang Bai, Shangwen Li, Xueting Yan, and Yin Li. Learning procedure-aware video representation from instructional videos and their narrations. arXiv preprint arXiv:2303. /7839, 2023.
[86] Honglu Zhou, Roberto Martín- Martún, Mubbasir Kapadia, Silvio Savarese, and Juan Carlos Niebles. Procedure-aware pretraining for instructional vidco understanding. Proceedings of the IEEE/CVF Confer- Computer Vision and Pattern Recognition, 2023. 2, 5, 9, 10
[87]
Luowei Zhou, Chenliang Xu, and Jason Corso. Towards automatic learning of procedures from web instructional videos. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018. Linchao Zhu and Yi Yang. Actbert: Learning global-local video-text representations. In Proceedings the IEFF/CVF conference on computer vision and pattern recognition, pages 8746-8755, 2020. Dimitri Zhukov, cean-Baptiste Alayrac, Ramazan Gokberk Cinbis, David Fouhey. Ivan Laptev, and Josef Sivic. Cross-task weakly supervised learning from instructional videos. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1537-3545, 2019. 2, 4,
[88]
[89]
14


Reviews:
[{"review_id": "SpokDxWvzs", "reviewer": "Reviewer_iD7r", "summary": "This paper focuses on the procedural activity understanding task. Considering that the feature-keystep matching in current methods is independent and fails to encapsulate the rich variety, the authors propose a video-mined task graph as a prior to update the preliminary keystep assignments.", "questions": "1.  What is the cost for building the video-mined graph? Will this graph leads to great overhead?\n\n2. The authors use the graph structure to amplify the context receptive field. How about using the attention mechanism (e.g. self-attention) since it is also a relation extraction manner?", "limitations": "1.  What is the cost for building the video-mined graph? Will this graph leads to great overhead?\n\n2. The authors use the graph structure to amplify the context receptive field. How about using the attention mechanism (e.g. self-attention) since it is also a relation extraction manner?", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Using the graph structure to generate broader context and assign the correct keystep labels is an intuitive idea.\n\n2. The propsed method offers substantial gains over state-of-the-art methods.", "weaknesses": "1.  What is the cost for building the video-mined graph? Will this graph leads to great overhead?\n\n2. The authors use the graph structure to amplify the context receptive field. How about using the attention mechanism (e.g. self-attention) since it is also a relation extraction manner?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for encouraging comments and feedback. \n\n**Q1. What is the cost for building the video-mined graph? Will this graph leads to great overhead?**\n\nThe overhead is minimal since the only extra computation is counting transitions given similarity scores followed by averaging. There are only $Nd$ additional operations for N-videos, each d-seconds long followed by averaging across $\\mathcal{K}$ keystep classes. In fact, the cost of building the graph is comparable to a forward pass on only one test video that involves significantly more FLOPs. Hence our idea adds minimal overhead while achieving notable advantages in both keystep recognition and video representation pretraining.\n\n**Q2. The authors use the graph structure to amplify the context receptive field. How about using the attention mechanism (e.g. self-attention) since it is also a relation extraction manner?**\n\nThe auto-regressive baseline (L280 and Table 1) does exactly this self-attention. In this baseline, an auto-regressive model first learns the transitions of the predicted keysteps. In the refining step, the model takes previous predictions and the current keystep-video score and generates the next prediction, typical of a self-attention mechanism. Our explicit representation significantly outperforms this baseline. It can be concluded that the proposed explicit task graph prior is more effective than self-attention, despite its implicit context modeling.\n"}, {"review_id": "lFsl6fcLvo", "reviewer": "Reviewer_G41M", "summary": "The paper considers the task of \"keystep\" recognition. Keystep is one of the N sub-tasks that are performed sequentially to achieve a goal / task. Keysteps can have causal dependencies. Prior work has the following limitations: \n(1) only considers each keystep in isolation, without considering the overall task (sequence of keysteps) [this is suboptimal, especially when powerful models like Transformers can efficiently model temporal context] \n(2) Keysteps are expected to conform exactly to a predetermined script of actions [sequence is not always precisely defined — there can be order inversions, skips, alternate keysteps, etc.] \n(3) Classification of fixed-size, pre-segmented chunks [this is inaccurate]. \n\nThe paper presents an approach to probabilistically represent the keystep transitions for tasks in the form of a \"task graph\". The approach leverages the prior probabilities for keystep transitions in the task graph in cases where there is low-confidence for video evidence. This results in improvements in performance in the zero-shot keystep localization task. It further improves video representations for other downstream tasks.", "questions": "(1) Frame-wise accuracy metric is defined (in L264) as “the fraction of frames with ground truth k_i that has the correct assignment.” Accuracy metrics usually penalize both false negatives and false positives. The definition of frame-wise accuracy suggests that this is a recall-like metric (only penalizes false negatives). Am I interpreting the metric definition correctly?\n\n(2) A question that arises wrt Strengths (1) is — is using the task graph probabilities explicitly, better than providing the relevant nodes in the task graph as input condition / context to a “revise” model (similar to baseline “Auto-Regressive [65, 69]”)?", "limitations": "Not explicitly discussed in the main paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The proposed approach explicitly leverages the probabilities of the task graph. This has the advantage that it is more interpretable than, e.g., encoding the relevant nodes and keysteps as an embedding, and then making predictions based on this. \n\n(2) There is consistent performance improvements in all tasks, especially zero-shot keystep prediction. Also, a big plus is the improvement in downstream tasks that leverage the better video representation that is trained on predicted pseudo-labels for other tasks. \n\n(3) It is nice that the task graph is constructed across the entire dataset, and contains common keysteps across tasks. This makes the task graph extensible across (theoretically) infinite data. With a much larger task graph, one could encode the keysteps for a majority of human activities present in videos.", "weaknesses": "(1) The approach involves constructing a task graph that probabilistically models the transitions between keysteps. Inference on this task-graph is also done by a principled path-search algorithm. However, to incorporate the probabilities from the task graph, a simple confidence-based thresholding operation is proposed. I.e., if the evidence (confident predictions) are below a certain threshold, then fall-back to the prior. This seems simplistic, and might not capture the complexity of individual data samples. Do we expect that a single threshold value across an entire dataset is a reasonable choice? Alternately, is there a way to have continuous bayesian approach incorporating the evidence and the prior for all samples? \n\n(2) Solely relying on priors for low-confidence perceptual predictions can work for tasks with very high predictability of keysteps. For almost all others, this might cause large errors. Is there a breakdown of errors from the perceptual model and the task-graph-prior model? Please include this in future versions of the paper. \n\n(3) Keystep classification on a temporal span of exactly 1-second-long clips is arbitrary. What’s the distribution of keystep temporal spans? Prior work indeed does this, but it would be nice to progress beyond this. However, I recognize that this may become very challenging in the case of novel or rare keysteps.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for encouraging comments and insightful feedback.\n\n**Q1. Do we expect that a single threshold value across an entire dataset is a reasonable choice? Alternately, is there a way to have continuous bayesian approach incorporating the evidence and the prior for all samples?**\n\nThanks for the question.  Our submission did consider this.  We provided experiments with a Bayesian Recursive Filter (BRF) variant of our approach that does consider the evidence and prior for all samples.  See section 6 and Table 1 in supplementary and Footnote 2. However, the performance is lower than the proposed method because BRF is causal and hence observes less context, and errors made in earlier prediction rounds are propagated to all time instances after that (Supp L49-52). The proposed simpler method is empirically better than the more complicated BRF. Establishing this was part of our research exploration, as we originally pursued both models in parallel.\n\nAs discussed in L245, performance is not highly sensitive to choices of the threshold $\\gamma$ in the range [0.3, 0.5] (also see ablation in Supp. Table 1).  We experimented with adaptive thresholding and found the performance to be inferior to using a constant threshold. The result can be seen in Table 1(a) in the attached rebuttal PDF. We adaptively identify one threshold per video, such that 50% of the video clips are considered to have “high-confidence” similarity scores. This works even for videos dominated by low similarity scores. The performance drops in this setting. We attribute this decrease to the fact that the model is assigning noisy samples as the high-confidence keystep and hence the overall keystep prediction is affected. We will add this ablation in the final paper. \n\n**Q2. Solely relying on priors for low-confidence perceptual predictions can work for tasks with very high predictability of keysteps. For almost all others, this might cause large errors. Is there a breakdown of errors from the perceptual model and the task-graph-prior model?**\n\nThanks for suggesting this breakdown of errors. First, given the set of low-confidence perceptual predictions, we split it into two sets – first where the keystep predictability using task graph prior is high and the second where it is low. To measure keystep predictability, we use Shannon entropy of starting keystep. We choose a threshold such that the predictions are split into half. High Shannon entropy means low keystep predictability and vice-versa. Table 1(c) in the attached rebuttal PDF shows the performance. We see that our task graph outperforms the baselines even in the case of low predictability of keysteps. Of course, the gain is lower than it is for cases with high keystep predictability. Thus, our task graph prior can be seen as a way to correct noisy perceptual predictions, even in cases of low predictability. We will add this observation in our final paper.\n\n**Q3. Keystep classification on a temporal span of exactly 1-second-long clips is arbitrary. What’s the distribution of keystep temporal spans? Prior work indeed does this, but it would be nice to progress beyond this. However, I recognize that this may become very challenging in the case of novel or rare keysteps**\n\nAverage temporal span of a keystep is 14.91s and 9.61s for COIN and CrossTask, respectively. Our setting is consistent with prior work [78,47]. Choosing non-overlapping contiguous segments of 1 seconds makes the keystep classification uniform and independent of keystep duration (some are long and some are short). For longer keysteps, the model can classify the same keystep for contiguous segments, denoting a longer temporal span of a particular keystep. So, in short, processing 1-second clips does not preclude identifying longer keystep instances when they occur. Work progressing beyond 1s video clips is orthogonal to our contributions.\n\n**Q4. Accuracy metrics usually penalize both false negatives and false positives. The definition of frame-wise accuracy suggests that this is a recall-like metric (only penalizes false negatives). Am I interpreting the metric definition correctly?**\n\nThe definition in L264 only means that the ground truth set does not contain non-labelled (i.e. background) segments. The accuracy is the standard (Correct predictions)/(All non-background segments). Concretely, if $\\phi$ is the background label, then we use the standard multi-class accuracy as \n\n$Acc = \\frac{\\sum \\limits_{V \\in D} \\sum \\limits_{t \\in |V|} 1(\\hat{k}_t = k_t)}{ \\sum 1(k_t \\neq \\phi)}$\n\nHere, D is the dataset and V is video. This setting is consistent with prior work [19]. Using background in the accuracy metric is not ideal due to class imbalance (>50% background in both COIN and CrossTask). Note that IoU (another metric we report in Table 1) still penalizes false positives that are in the background. In the denominator of IoU we do add the false positives. We also add the F1 metric (including the background) for completeness in the rebuttal PDF Table 1(b). Our method outperforms the baselines and SOTA in all metrics.\n\n**Q5. A question that arises wrt Strengths (1) is — is using the task graph probabilities explicitly, better than providing the relevant nodes in the task graph as input condition / context to a “revise” model (similar to baseline “Auto-Regressive [65, 69]”)?**\n\nPlease note that we provided a baseline that addresses this question.  Pruning keysteps (L283-288) is the baseline that first clusters the keysteps and tries to find the “relevant nodes” and provides only those to the “revise” model. The performance is stronger than SOTA and auto-regressive, but still weaker than our method. Thus, explicit task graph probabilities are better than both auto-regressive baseline and providing only “relevant nodes”.\n\n**Q6. Limitation not explicitly discussed in the main paper.**\n\nWe have discussed limitations in Supp (L59-65). Please also see the global comment above.\n"}, {"review_id": "mvdbh7wzgc", "reviewer": "Reviewer_vrnW", "summary": "This paper addresses the problem of key-step recognition and localization in instructional videos by learning and leveraging a probabilistic task graph. The proposed method first localizes key-steps mined from text sources (such as wikihow) in videos by measuring the similarity between visual-narration features in videos (obtained from pretrained models) and key-step feature. It then constructs a graph whose nodes are key-steps and whose edges are transitions between key-steps (obtained from the localization results). Finally, the initial key-steps whose confidence is lower than a threshold will be replaced by the key-steps from the optimal key-step path in the task graph. The experimental results show some improvement compared to key-step recognition baselines.\n\n* The reviewer read the author rebuttal and other reviews.", "questions": "In addition to the questions raised in the weakness section:\n\n- From Table 1, one can se that the improvement of the performance on COIN is often  more significant than on CrossTask. Why? \n\n- Is the task graph built based on the videos and narrations in the training set and uses the same task graph during test? Or is the task graph only built based on the test set?", "limitations": "There is no discussion of limitations and possible negative societal aspects of the work and need to be included in the main paper.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is easy to read and overall framework is sufficiently well presented.\n\n- Leveraging a task graph to improve recognition is interesting (although the paper is not the first work addressing it).", "weaknesses": "-  The paper claims that it is the first to use task graphs to enhance keystep predictions in instructional video (see line50). The reviewer disagrees with this claim. Parika [85] has addressed learning and leveraging task graphs to learn video representation for better key-step recognition. The final goal that the submission and Parika pursue is almost the same. In fact the submission has a narrower scope compared to [85] as it does not address representation learning while [85] addresses it along with better key-step recognition.\n\n- The graph learned in the paper is not exactly a \"task graph\" (a task graph encodes all possible ways of doing a task). It is rather a transition probability model between key-steps. In particular, a limitation of the transition model in the paper is that it does not properly encode task executions, e.g., a transition model allows multiple transitions between two key-steps (e.g., a-->b-->a-->...-->b-->a), which may be invalid for task execution. This is because of the short-sightedness of the transition model that does not model long-range action dependencies. \n\n- Related to the comment above, there is a need for an experiment that measures the edit distance between the predicted key-step sequences and the ground-truth key-step sequences, compared with baselines. \n\n- Compared to [85] which also builds a task graph, the advantage of the studied method is not clear. Given the high similarity between the two works, there is a need to include [85] with its experimental setting in the paper for a fair comparison. \n\n- The key-step to narration assignment can lead to violation of the transition model (see the formulation after line 205). Specifically, when the similarity between video and key-step is above a threshold, the key-step will be assigned to the video frame and is lower than a threshold it will be assigned by following the transition model. Additionally, there is a need in the experiment that shows the effect of the hyper-parameter $\\gamma$ on the step recognition results (e.g., horizontal axis $\\gamma$ and vertical axis $acc$). \n\n- The evaluation metric in the paper does not consider background. Given that at least 40% of instructional videos in crosstalk and coin consist of background frames, there is a need to measure how well the proposed method avoids assigning key-step labels to the background frames. By measuring ACC and IOU for only key-step regions, one cannot evaluate whether the paper wrt SOTA assigns large or small portions of background frames as key-steps. \n\n- In Table 1, for Video-only and Video-Text, both ACC and IOU of the method is very close to SOTA, which makes the effectiveness of the learn transition model questionable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments. Our responses show where multiple requests from the reviewer were addressed in the submitted paper.  Also please note the concurrent work policy of NeurIPS re: [85].\n\n**Q1. Comparison with [85]**\n\nPaprika [85] is a contemporaneous work per the conference guidelines (see global rebuttal), meaning a comparison is not required. \n\nRegarding relative contributions: As we were completing our submission, we saw their paper appear on arXiv; we explain the important differences with [85] in L96-105. Paprika learns a task graph ONLY for video representation learning, whereas we use the task graph for both keystep recognition (Sec 4.1) and video representation learning (Sec 4.2). Paprika does not perform zero-shot keystep recognition. Our work is the first to use task graphs to enhance keystep predictions. Hence our scope is broader than [85].\n\nRegarding empirical comparisons: In [85], the resulting task graph has equi-probable edges, whereas ours is based on empirically observed transitions in video. A non-probabilistic baseline in Table 1(a) in the attached rebuttal PDF shows that a probabilistic graph performs better.  Important: please see our response to Q9 for Reviewer wv2a discussing issues with direct comparison with [85] on representation learning.\n\n**Q2. Transition probabilities vs “task graph” e.g. transition model allows multiple transitions between two key-steps, which may be invalid**\n\nAs a counterexample to the reviewer’s claim, keystep a: “add salt to boiling soup” and keystep b: “stir the soup to dissolve salt” can have a→b→a→b…. transitions when a user is not sure about how much salt to add and hence this transition cannot be disallowed. Specifically, given the stochastic nature of human activity, it is impossible to encode ALL possible ways of doing a task. Thus, a transition probability model is a reasonable way to capture all typical transitions, also helping accommodate transitions outside a fixed recipe. Note that the PathSearch algorithm (L205-211) finds a keystep path between high confidence keysteps, regardless of the duration in between, i.e., our method can also consider long-range action dependencies.\n\nPlease see the “Linear Script” baseline (L289-290) where we take the explicit order of steps. Also see the “Auto-Regressive” (L280-282) baseline that has long-range action dependencies and still performs worse. Both these baselines show that our explicit task graph is helpful in assigning keysteps.\n\n**Q3. Add edit distance as a metric**\n\nThanks for the suggestion. We think edit distance is a useful additional metric, since it captures how similar the sequence of keysteps are w.r.t. the ground truth. Please see Table 1(b)  in the attached PDF. On this metric, too, our method outperforms baselines for all modalities for both datasets. We will add this metric in the paper.\n\n**Q4. Violation of transition model (L205) and effect of $\\gamma$**\n\nPlease note that Supp. Table 1 already includes the suggested experiment with $\\gamma$. See also L245.\n\nRegarding transition violations – the algorithm first chooses instances where the similarity between video and key-step is above a threshold and between any two such time instants, we use the transition model (L203-205). We also have another version of the transition model - Bayesian Recursive Filter (BRF), (please see footnote 2 of the main paper and section 6 of the supp). In this version, we make predictions based only on the transition model and we observe that the performance in that case is weaker. Applying the transition model only between two high confidence segments is empirically better. Establishing this was part of our research exploration, since we originally pursued both models in parallel.\n\n**Q5. Metrics do not consider background**\n\nWe also have metrics that do consider background. The chosen setting is consistent with prior work [19]. Accuracy metric is not ideal using background due to class imbalance (simply predicting everything as background results in high Acc). Note that IoU (reported in our submission) does consider background and penalizes false positives. Moreover, we add F1 metrics to further address the background frames question. See Table 1(b) in the attached rebuttal PDF. Our method outperforms all the baselines on all metrics consistently, including IoU and F1, which consider background.\n\n**Q6. Performance close to SOTA in Video-only and Video-Text**\n\nThe increase in Acc for COIN dataset is 2.2% and 3.6% for video-only and video-text wrt SOTA. The difference is indeed lower for CrossTask while still being statistically significant. We attribute this to the smaller keystep set in CrossTask (105 vs 749 keysteps in COIN) and thus the transitions having lower predictability on average. The video features may themselves have low perceptual errors as we still see a gain of 3.9% in CrossTask text-only. As suggested by reviewer G41M, if we split the performance into low and high predictability segments, we see that the performance gain in highly predictable keystep transitions is more significant (3.4% for video-only and 3.5% for video-text). Therefore, our method performs better with a larger keystep set — important for the natural setting.\n\n**Q7. Gain on COIN more than CrossTask**\n\nPlease see response to Q6. In short, COIN offers a much larger keystep taxonomy, and hence a greater need for our regularization.\n\n**Q8. Construction of task graph on training or test set?**\n\nFor zero-shot keystep recognition (Sec 4.1), the task graph is built only based on the test set since we do not want supervision transfer between different splits. For representation learning (Sec 4.2), the task graph is built on the train set to pseudo label itself.\n\n**Q9. Limitations**\n\nWe have discussed limitations in Supp (L59-65). Also see the global rebuttal. Though we've given it careful thought, we do not see negative societal impact for our contributions."}, {"review_id": "v3k4Tp19oa", "reviewer": "Reviewer_qtTp", "summary": "In this work, the authors propose to address keystep recognition in instructional videos. To achieve this goal, they attempt to build a task graph from videos, which show how keysteps are related to each other. Based on this graph, one can further update the preliminary keystep assignment, when the initial prediction is with low confidence. \n", "questions": "Please see the weakness section.", "limitations": "Please see the weakness section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 The key step recongnition is an important topic for procedural activity understanding. \n2 The idea of building task graph seems to be technical sound as key step relation prior.\n3 The experiments show the effectiveness of the method.", "weaknesses": "(1) The task graph is pre-computed offline or built online? I assume, it should be built offline, according to the unannotated dataset of narrated instructional videos. Moreover, when working on another dataset, the task graph should be re-computed again? \n\n(2) What is the computation time of Path Search, when updating the low-confident key step prediction? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging comments and insightful feedback. \n\n**Q1. The task graph is pre-computed offline or built online? I assume, it should be built offline, according to the unannotated dataset of narrated instructional videos. Moreover, when working on another dataset, the task graph should be re-computed again?**\n\nYes, the task graph is pre-computed offline. When working on a dataset with a different vocabulary, the task graph needs to be re-computed to accommodate for the difference in ground truth keystep set. We generalize with HowTo100M where we use a large-scale keystep set (>10k keysteps). More precisely, if the keystep set were the same in all dataset, we would not have to compute the task graph again.\n\n**Q2. What is the computation time of Path Search, when updating the low-confident key step prediction?**\n\n\nPathSearch uses Dijkstra’s algorithm (L208) that has a worst-case complexity of $O(V^2)$ for $V$ nodes (equal to number of keysteps, $V = 105/749/10588$ for CrossTask/COIN/HowTo100M). This computation is minimal. When performing keystep assignment, PathSearch is less compute intensive than video feature extraction since forward pass is typically more than just $O(V^2)$ hence no delay is observed compared to the baselines.  Hence our idea adds minimal overhead while achieving notable advantages in keystep recognition and video representation pretraining.\n"}, {"review_id": "ZMgHvCRfmL", "reviewer": "Reviewer_wv2a", "summary": "This paper aims to recognize the keysteps in instructional videos using automatically mined task graphs. These task graph is automatically discovered from a set of narrated instructional videos and contains all keysteps in a given vocabularly, i.e. it is not limited to a single task. This allows dependences between keysteps to be represented and helps move away from the requirement of prior work to have a strict ordering of keysteps in a task. The mined task graph is used for keystep recognition, task recognition and keystep forecasting on COIN and CrossTask.", "questions": "- How does the supervision used in this work compare with prior works? Particularly [44], [82] and [84].\n\n- Why is [84] not compared to?\n\n- How important is a clean and well-defined keystep vocabularly to the method performance?\n\nThe rebuttal responded to the majority of my concerns particularly, it improved clarity in the supervision used by the proposed and prior works,. visualization of the task graph, experiments on the expanded keystep vocabulary with relative gain over distant supervision particularly convincing. I hope these are included in the final version of the paper.\n\nSince the rebuttal has addressed all my major concerns and I found no major concerns in the other reviews I have raised my rating to weak accept. While comparison to paprika isn't a reason to reject this work since it is concurrent, better explaining the differences or having some kind of numerical comparison would make this work stronger and help future readers.", "limitations": "A small section on limitations is present in the supplementary material. It can be improved by also considering negative societal impact.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The approach of task graph mining eliminates need for prior keystep recognition work of having set linear order of keysteps.\n\n***\n\n- Benefits not constrained to task of keystep prediction, the paper also shows the video representation is useful for related but distinct tasks of key step forecasting and task classification\n\n***\n\n- Authors clearly understand task and nature of instructional videos well, I particularly liked the insights given on lines 42-45\n\n***\n\n- The method is well motivated", "weaknesses": "- The main weakness of the work is the lack of clarity in supervision used in relation to prior works, making it difficult to assess the suitability of the baselines used.\n- Particularly as the proposed work to a vocabularly of keysteps as supervision in addition to the video's narrations. The predefined keystep vocabularly isn't clear until the beginning of the method section. \n- The difference in supervision to prior works, e.g. [70], [82], [84], could be better explained in the related work. Currently not clear why these aren't explained and compared to without reading these papers in depth. Particularly [84] appears to only be supervised by the narration of the video which is also used by this paper in addition to the keystep vocabularly. \n- I only looked at these three works as a sample, so it is very possible that there are other papers mentioned in related work with similar supervision levels to [82] and [84].\n- From Table 1 of [84], [84] appears to outperform the proposed approach when comparing to the downstream step forecasting result of COIN in Table 4. This seems to also be the case for the results provided in Table 2 of [84].\n- It also isn't clear if DistantSupervison [44] use the same keystep vocabularly as the proposed work. From figure 4 many of the mistakes made by [44] appear to be due to the name of the keystep, sometimes [44] even gives more information e.g. in press chest, as the keystep names appear to be less limited.\n- Adding the supervision used to the results tables would greatly help assess this better.\n\n***\n\n- The importantance of the keystep vocabularly isn't evaluated\n- My main question is whether the proposed method is robust to noise in the keystep vocabularly? I.e. how does the performance degrade with a larger keystep vocabularly containing keysteps which aren't used.\n- It eems to work well for COIN and CrossTask with curated keystep vocab. For HowTo100M a presumably noisier vocab is used from WikiHow, however it would be much stronger if this effect was tested.\n\n***\n\n- Limited visualization of the task graph. The graph itself might be interesting and contain some insights for learning from instructional video as hinted on in lines 165-174. It would be useful to be able to see (a portion of) the mined task graph. A very small part is shown in Figure 3. However it should have been possible to visualize the full crosstask graph in supplementary.\n- I recommend the authors include example task graph(s) in supplementary in future versions.\n\n***\n\n- From related work Paprika [85] sounds the most similar and it isn't clear why this work isn't compared to.\n- It is a contemporaneous work, appeared online 31 March 2023, so this could be a valid reason. However, the footnote explains that [85] is using a different setting to [44]. \n- Comparing on the setting used by [85] would make the work stronger.\n\n***\n\n- Not factored into reviewing score as its a contempoaneous work but [A] has similarities to this paper so it might help to include a citation to [A] and explain the differences in a future version.\n\n***\n\n[A] StepFormer: Self-supervised Step Discovery and Localization in Instructional Videos. CVPR 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging comments and insightful feedback. \n\n**Q1. Lack of clarity in supervision used vs. prior work**\n\nThis seems to be a misunderstanding. All the baselines use the same level of supervision. Specifically, task graph construction does not use ground-truth keysteps in zero-shot keystep recognition (Sec 4.1). Similarly, in video representation learning (Sec 4.2), there is no annotation for keysteps hence the pseudo-labels are generated from similarity scores. In table 1, in addition to the keystep set, the supervision is narration (text-only), video feature (video-only) and both (video-text) for all baselines. Hence, all the comparisons are fair and baselines are a suitable comparison.\n\n**Q2. Use of a vocabulary of keystep in addition to narrations**\n\nThe keystep vocabulary is the set of annotated keysteps in COIN/CrossTask. It is used by all the methods and not specific to our method. All the baselines and SOTA use the keystep vocabulary when assigning keysteps (L252-261). We have described keysteps (L20-27) in detail in the introduction. We appreciate the feedback, and we will accentuate this further in the text. \n\n**Q3. Difference in supervision to [70], [82], [84]**\n\nNote that [70, 84] are contemporaneous work per the conference policy (also see the global comment at the top). We will add a detailed comparison between the tasks and supervision used in these works. Here are the differences:\n\n[70, 82] - The task the authors solve is “procedure planning” which is distinct from keystep recognition and representation learning. The goal in procedure planning is given a start and end image, the model needs to generate a “plan” to achieve the final goal. This task is unrelated to ours and comparison with it is not possible.\n\n[84] - The paper proposes procedure-aware video representation. For supervision, they use videos and their narrations from HowTo100M. However, they use a text encoder trained with CLIP that uses 400 million (image, text) pairs. Hence, the level of supervision used is incomparable. Further, it is a contemporaneous work that appeared in CVPR 2023 *after* the NeurIPS deadline.\n\n**Q4. Empirical comparison to [84]**\n\nSee above discussion about [84] – it is contemporaneous work published after we submitted our paper, and according to NeurIPS policy, a paper should not be rejected for not comparing to concurrent work. We will explore ways to relate the two methods empirically, though note that regardless of how they may each fare on video representation learning, our idea to enhance keystep recognition with the task graph remains novel with respect to [84].\n\n**Q5. Supervision used by DistantSupervision [44]**\n\nDistantSupervision [44] uses the same keystep vocabulary (L151). Since the keystep set is the same, the mistake cannot be due to the name of the keystep. Regarding figure 4, the keystep set between [44] and our work is the same and the yellow boxes (row A) represent ASR text of the narrations and not keysteps. Overall, our method uses exactly the same supervision as [44].\n\n**Q6. Add supervision used to results tables**\n\nAll results in every table (1, 2, 3) use the same level of supervision, so we don’t add supervision explicitly in the tables. We will make sure to accentuate this in the paper.\n\n**Q7. Importance of keystep vocabulary and its robustness to noise**\n\nThe proposed method uses a vocabulary set much larger than the set of keysteps for one task. Eg. an average task in COIN consists of 3.9 keysteps but the vocabulary set is 749 keysteps. Similarly, in HowTo100M representation learning (Sec 4.2), the vocabulary set is 10588 keysteps which is much larger than keystep set of any one task (and hence, quite noisy). Therefore, the method is robust to noise in keysteps and we indeed use keysteps that are not part of the task for a given video.\n\n**Q8. Visualization of the task graph**\n\nThank you for the suggestion!  We add a portion of the mined task graph for CrossTask in the attached rebuttal PDF (Figure 1). It contains 61 out of 105 keysteps with top 5 transitions labeled (to avoid clutter). We do see some interesting properties (also see Fig 3 of main paper). For example, “lower jack” happens only after “brake on”, “close lid” after “open lid” whereas “cut cucumber” and “cut onion” can both happen after each other.\n\n**Q9. Comparison on the setting used by [85], a contemporaneous work, appeared online 31 March 2023**\n\nThank you for noting that this work is contemporaneous. Regarding comparison with [85], apart from the fact that it is contemporaneous, we found that [85] and [44] use different experimental settings. We use the original setting of [44] for better reproducibility, given the detailed setup descriptions in that paper. In fact, DistantSup [44] performs much better in its original implementation compared to the adjusted settings reported in [85] (DistantSup [44] gets only 32.74 as reported in [85] vs the DistantSup authors’ originally reported 54.1 in [44] for COIN step classification, similarly 82.66 vs 90.0 for COIN task classification; see DS* in Table 1 of [85] vs results in [44]). Hence, there is some disadvantage to DistantSup [44] in the revised setting deployed in [85], though the reason is not elaborated in [85]’s paper. Therefore, we stick to comparison with [44] (where the existing method DistantSup achieves its better numbers) for fairness and better reproducibility.  We observe clear gains over those numbers (Table 4 in the main paper).\n\n**Q10. [A] is a similar work**\n\nThanks for pointing out concurrent [A]. It uses non-annotated data for discovering steps in instructional videos and shows downstream keystep localization (different than our task). We will add it in the final version of the paper and discuss the differences.\n\n**Q11. Societal impact**\n\nPlease see the global comment above. Though we gave it careful thought, we do not see any negative societal impact specific to our contributions in this paper."}]

Author rebuttal:
We thank all the reviewers for their insightful comments.

**Three reviewers lean towards acceptance**. We believe our responses below clarify the items raised in the reviews, which include questions about metrics and a concurrent paper [85] (*vrnW*) and a possible misunderstanding about supervision (*wv2a*). There are several instances where requested experiments/baselines are indeed already in our original submission, detailed below.

All the reviewers are positive about the method – *iD7r* states the method is intuitive, *G41M* calls it more interpretable, *vrnW* suggests the method is technically sound and finally, *wv2a* agrees that it is well-motivated. Further, reviewer *iD7r* states that “proposed method offers substantial gains over state-of-the-art methods” and *qtTp* says the experiments “show effectiveness”. *G41M* agrees that “there is consistent performance improvements in all tasks, especially zero-shot keystep prediction” and that improvement in downstream tasks is a “big plus” by using a “better video representation”. *G41M* correctly notes that the task graph is constructed across the entire dataset and “with a much larger task graph, one could encode the key steps for a majority of human activities present in videos.” *wv2a* notes that the “benefits are not constrained to task of keystep prediction but distinct tasks of key step forecasting and task classification”. Finally, we thank *vrnW* for noting that the paper is easy to read and to *wv2a* to note that we “clearly understand task and nature of instructional videos well”. 

We address the weakness individually to each reviewer alongside their review.

**We would also like to draw attention of the AC and the reviewers to several contemporaneous works [70, 84, 85, A] (thanks to *wv2a* for pointing out [A])**. All of them are published in CVPR 2023 (**after** this paper deadline in June 2023) and appeared first online (on arXiv) within two months of the paper submission (i.e. after March 17th 2023). This means they are concurrent work per the NeurIPS policy given in the call for papers:.  **“...for the purpose of the reviewing process, papers that appeared online within two months of a submission will generally be considered "contemporaneous" in the sense that the submission will not be rejected on the basis of the comparison to contemporaneous work.”**

That said, all of them use different ideas for video representation learning. [85] is most relevant to our work, and (upon seeing their arxiv post as we were finishing our submission) we have differentiated with it in the submitted paper in detail (see L96-L105). These contemporaneous works further suggest the importance of video representation learning and using task graphs for keystep localization. 


Finally, we have included a **Limitations section in the supplementary (Supp L59-65)**. As far as dependencies, our method relies on the strength of the perceptual prediction model, and our task graph construction and keystep prediction can be noisy if the perceptual model is weak. We do not foresee any negative societal impact.

Meta-review: This method proposes an approach to compute transition probabilities between keysteps for instructional videos. Reviewers appreciated that the method was well motivated, and proposes an interesting formulation to the problem of keystep recognization and localization. There are some concerns about the actual inference on the task graph, which thresholds confidences, but the authors argue that they tried a more probabilistic approach but found that the results were worse. One reviewer was also concerned about whether the technical formulation of the task-graph is correct but after some discussion the ACs agree that being able to repeatedly transition to the same step is a reasonable assumption.
Decision: Accept (poster)