Video-Mined Task Graphs for Keystep Recognition in Instructional Videos

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.

Strengths

- The approach of task graph mining eliminates need for prior keystep recognition work of having set linear order of keysteps. *** - 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 *** - Authors clearly understand task and nature of instructional videos well, I particularly liked the insights given on lines 42-45 *** - 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. - 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. - 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. - 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]. - 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]. - 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. - Adding the supervision used to the results tables would greatly help assess this better. *** - The importantance of the keystep vocabularly isn't evaluated - 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. - 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. *** - 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. - I recommend the authors include example task graph(s) in supplementary in future versions. *** - From related work Paprika [85] sounds the most similar and it isn't clear why this work isn't compared to. - 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]. - Comparing on the setting used by [85] would make the work stronger. *** - 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. *** [A] StepFormer: Self-supervised Step Discovery and Localization in Instructional Videos. CVPR 2023.

Questions

- How does the supervision used in this work compare with prior works? Particularly [44], [82] and [84]. - Why is [84] not compared to? - How important is a clean and well-defined keystep vocabularly to the method performance? The 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. Since 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

A small section on limitations is present in the supplementary material. It can be improved by also considering negative societal impact.

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.

Strengths

1 The key step recongnition is an important topic for procedural activity understanding. 2 The idea of building task graph seems to be technical sound as key step relation prior. 3 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? (2) What is the computation time of Path Search, when updating the low-confident key step prediction?

Questions

Please see the weakness section.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Please see the weakness section.

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. * The reviewer read the author rebuttal and other reviews.

Strengths

- The paper is easy to read and overall framework is sufficiently well presented. - 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. - 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. - 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. - 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. - 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$). - 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. - 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.

Questions

In addition to the questions raised in the weakness section: - From Table 1, one can se that the improvement of the performance on COIN is often more significant than on CrossTask. Why? - 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?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

There is no discussion of limitations and possible negative societal aspects of the work and need to be included in the main paper.

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: (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] (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.] (3) Classification of fixed-size, pre-segmented chunks [this is inaccurate]. The 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.

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. (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. (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? (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. (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.

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? (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]”)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Not explicitly discussed in the main paper.

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.

Strengths

1. Using the graph structure to generate broader context and assign the correct keystep labels is an intuitive idea. 2. 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? 2. 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?

Questions

1. What is the cost for building the video-mined graph? Will this graph leads to great overhead? 2. 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: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

1. What is the cost for building the video-mined graph? Will this graph leads to great overhead? 2. 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?

Response to rebuttal

Thank you for highlighting the improved clarity in the supervision used by the proposed and prior works. I hope this clarity can also be added to a future version of the paper. I also appreciated the visualization of the task graph in the rebuttal. It is a shame the authors could not experiment with the keystep vocabulary. I understand the vocabulary used within a task is much smaller than the vocabulary available to the model, however the available vocabulary, in COIN for instance, is still much smaller than the one used in HowTo100M and much smaller than the vocabulary available in the English language. It is also a shame the authors refuse to consider any potential negative societal impact. Nonetheless, I will enter the discussion phase more positive than my initial review thanks to the clarity on supervision.