Procedural Activity Representation and Online Mistake Detection from Egocentric Videos (2024)

3.1 Task Graph Maximum Likelihood Learning Framework

Preliminaries Let $\mathcal{K}=\{K_{0}=S,K_{1},\ldots,K_{n},K_{n+1}=E\}$ be the set of key-steps involved in the procedure, where $S$ and $E$ are placeholder “start” and “end” key-steps denoting the start and end of the procedure. We define the task graph as a directed acyclic graph, i.e., a tuple $G=(\mathcal{K},\mathcal{A},\omega)$, where $\mathcal{K}$ is the set of nodes (the key-steps), $\mathcal{A}=\mathcal{K}\times\mathcal{K}$ is the set of possible directed edges indicating ordering constraints between pairs of key-steps, and $\omega:\mathcal{A}\to[0,1]$ is a function assigning a score to each of the edges in $\mathcal{A}$.An edge $(K_{i},K_{j})\in\mathcal{A}$ (also denoted as $K_{i}\to K_{j}$) indicates that $K_{j}$ is a pre-condition of $K_{i}$ (for instance $\text{mix}\to\text{crack egg}$) with score $\omega(K_{i},K_{j})$. We assume normalized weights for outgoing edges, i.e., $\sum_{j}w(K_{i},K_{j})=1\forall i$.We also represent the graph $G$ as the adjacency matrix $Z\in[0,1]^{n\times n}$, where $Z_{ij}=\omega(K_{i},K_{j})$. For ease of notation, we will denote the graph $G=(\mathcal{K},\mathcal{A},\omega)$ simply with its adjacency matrix $Z$ in the rest of the paper.We assume that a set of $N$ sequences $\mathcal{Y}=\{y^{(k)}\}_{k=1}^{N}$ showing possible orderings of the key-steps $\mathcal{K}$ is available, where the generic sequence $y\in\mathcal{Y}$ is defined as a set of indexes to key-steps $\mathcal{K}$, i.e., $y=<y_{0},\ldots,y_{t},\ldots,y_{m+1}>$, with $y_{t}\in\{0,\ldots,n+1\}$. We further assume that each sequence starts with key-step $S$ and ends with key-step $E$, i.e., $y_{0}=0$ and $y_{m+1}=n+1$¹¹1In practice, we prepend/append $S$ and $E$ to each sequence. and note that different sequences $y^{(i)}$ and $y^{(j)}$ have in general different lengths. Since we are interested in modeling key-step orderings, we assume that sequences do not contain repetitions.²²2Since sequences may in practice contain repetitions, we map each sequence containing repetitions to multiple sequences with no repetitions (e.g., $ABCAD\to(ABCD,BCAD)$).. We frame task graph learning as determining an adjacency matrix $\hat{Z}$ such that sequences in $\mathcal{Y}$ can be seen as topological sorts of $\hat{Z}$. A principled way to approach this problem is to provide an estimate of the likelihood $P(\mathcal{Y}|Z)$ and choose the maximum likelihood estimate $\hat{Z}=\underset{Z}{\arg\max}\text{ }P(\mathcal{Y}|Z)$.

3.2 Models

Direct Optimization (DO) The first model aims to directly optimize the parameters of the adjacency matrix by performing gradient descent on the TGML loss (Eq.(6)).We define the parameters of this model as an edge scoring matrix $A\in\mathbb{R}^{(n+2)\times(n+2)}$, where $n$ is the number of key-steps, plus the placeholder start ($S$) and end ($E$) nodes, and $A_{ij}$ is a score assigned to edge $K_{i}\rightarrow K_{j}$.To prevent the model from learning edge weights eluding the assumptions of directed acyclic graphs, we mask black cells in Figure2 with $-\infty$.To constrain the elements of $Z$ in the $[0,1]$ range and obtain normalized weights, we softmax-normalize the rows of the scoring matrix to obtain the adjacency matrix $Z=softmax(A)$. Note that elements masked with $-\infty$ will be automatically mapped to $0$ by the softmax function similarly to[36]. We train this model by performing batch gradient descent directly on the score matrix $A$ with the proposed TGML loss. We train a separate model per procedure, as each procedure is associated to a different task graph.As many applications require an unweighted graph, we binarize the adjacency matrix with the threshold $\frac{1}{n}$, where $n$ is the number of nodes. We also employ a post-processing stage in which we remove redundant edges, loops, and add obvious missing connections to $S$ and $E$ nodes.³³3See the supplementary material for more details.

Task Graph Transformer (TGT) Figure3 illustrates the proposed model, which is termed Task Graph Transformer (TGT). The proposed model can take as input either $D$-dimensional embeddings of textual descriptions of key-steps or $D$-dimensional video embeddings of key-step segments extracted from video. In the first case, the model takes as input the same set of embeddings at each forward pass, while in the second case, at each forward pass, we randomly sample a video embedding per key-step from the training videos (hence each key-step embedding can be sampled from a different video). We also include two $D$-dimensional learnable embeddings for the $S$ and $E$ nodes.All key-step embeddings are processed by a transformer encoder, which outputs $D$-dimensional vectors enriched with information from other embeddings. To prevent representation collapse, we apply a regularization loss encouraging distinctiveness between pairs of different nodes. Let $X$ be the matrix of embeddings produced by the transformer model.We L2-normalize features, then compute pairwise cosine similarities $Y=X\cdot X^{T}\cdot\exp(T)$ as in[29].To prevent the transformer encoder from mapping distinct key-step embeddings to similar representations, we enforce the values outside the diagonal of $Y$ to be smaller than the values in the diagonal. This is done by encouraging each row of the matrix $Y$ to be close to a one-hot vector with a cross-entropy loss. Regularized embeddings are finally passed through a relation transformer head which considers all possible pairs of embeddings and concatenates them in a $(n+2)\times(n+2)\times 2D$ matrix $R$ of relation vectors. For instance, $R[i,j]$ is the concatenation of vectors $X[i]$ and $X[j]$. Relation vectors are passed to a transformer layer which aims to mine relationships among relation vectors, followed by a multilayer perceptron to reduce dimensionality to $16$ units and another pair of transformer layer and multilayer perceptron to map relation vectors to scalar values, which are reshaped to size $(n+2)\times(n+2)$ to form the score matrix $A$. We hence apply the same optimization procedure as in the DO method to supervise the whole architecture.

4.1 Graph Generation

Problem Setup We evaluate the ability of our approach to learn task graph representations on CaptainCook4D[26], a dataset of egocentric videos of 24 cooking procedures performed by 8 volunteers. Each procedure is accompanied by a task graph describing key-steps constraints.We tackle task graph generation as a weakly supervised learning problem in which models have to generate valid graphs by only observing labeled action sequences (weak supervision) rather than relying on task graph annotations (strong supervision), which are not available at training time.All models are trained on videos that are free from ordering errors or missing steps to provide a likely representation of procedures.We use the two proposed methods in the previous section to learn $24$ task graph models, one per procedure, and report average performance across procedures.

Compared Approaches We compare our methods with previous approaches to task graph generation, and in particular with MSGI [35] and MSG² [18], which are approaches for task graph generation based on Inductive Logic Programming (ILP).We also consider the recent approach proposed in[3] which generates a graph by counting co-occurrences of matched video segments. Since we assume labeled actions to be available at training time, we do not perform video matching and use ground truth segment matching provided by the annotations. This approach is referred to as “Count-Based”. Given the popularity of large language models as reasoning modules, we also consider a baseline which uses a large language model⁴⁴4We base our experiments on ChatGPT[1]. to generate a task graph from key-step descriptions, without any access to key-step sequences.${}^{\ref{note:supp2}}$We refer to this model as “LLM”.

Graph Generation Results Results in Table1 highlight the complexity of the task, with classic approaches based on inductive logic, such as MSGI, achieving poor performance ($12.8$ $F_{1}$), language models and count-based statistics reconstructing only basic elements of the graph ($55.0$ and $61.0$ $F_{1}$ for LLM and Count-Based respectively), and even more recent methods based on inductive logic and heuristics only partially predicting the graph ($71.1$ $F_{1}$ of $MSG^{2}$). The proposed Direct Optimization (DO) approach outperforms all other methods, achieving the highest scores across all measures, with improvements in the $[+15.5,+18.1]$ range with respect to the best competitor $MSG^{2}$. This result highlights the effectiveness of the proposed framework to learn task graph representations from key-step sequences, especially considering the simplicity of the DO method, which performs gradient descent directly on the adjacency matrix. We obtain a slightly higher recall as compared to the precision ($89.7$ vs $86.4$), showing that our approach tends to retrieve most ground truth edges, while hallucinating some pre-conditions, probably due to the dataset being unbalanced towards the most common ways of completing a procedure. Second best results are consistently obtained by our feature-based TGT approach, showing the generality of our learning framework and the potential of integrating it into complex neural architectures. Tight confidence intervals for DO highlight the stability of the proposed loss.The lower performance of TGT, as compared to DO, may be due to the relatively small size of the dataset, which makes it hard for complex architecture to generalize.

Video Understanding Results Table2 reports the performance of TGT trained on videos on two fundamental video understanding tasks[42] of pairwise clip ordering and future prediction.⁵⁵5See the supplementary material for more details. For pairwise ordering, we feed our TGT model with video embeddings of two clips and sort them according to the predicted adjacency matrix, placing first the clip identified as a pre-condition. For future predictions, given an anchor clip, we have to choose which among two other clips is the correct future. In this case, we feed the model with the three clips and select as future the clip with the smallest $anchor\to clip$ edge weight (future clips are not likely pre-conditions). Despite TGT not being explicitly trained for pairwise ordering and future predictions, it exhibits promising emerging video understanding abilities, surpassing the random baseline.

4.2 Online Mistake Detection

Problem Setup We follow the PREGO benchmark recently proposed in[12], in which models are tasked to perform online action detection from procedural egocentric videos. To evaluate the usefulness of task graphs on this downstream task, we design a system which flags the current action as a mistake if its pre-conditions in the predicted graph do not appear in previously observed actions.${}^{\ref{note:supp2}}$

Competitors We compare our approach with respect to the PREGO model proposed in[12], which detects mistakes based on the comparison between the currently observed action and an action predicted by a forecasting module. We note that PREGO is based on an implicit representation of the procedure (the forecasting module), while our approach is based on the explicit task graph representation, learned with the proposed framework. We also compare our approach with respect to baselines based on all graph prediction approaches compared in Table1 to assess how the ability to predict accurate graphs affects downstream performance. For all methods, we report results based on ground truth action segments and on action sequences predicted by a MiniRoad[2] instance, a state-of-the-art online action detection module trained on each target dataset.

Results Results in Table3 highlight the usefulness of the learned task graphs for downstream applications. The proposed DO method achieves significant gains over prior art with improvements of $+19.8$ and $+7.5$ in average $F_{1}$ score on Assembly101 and EPIC-Tent respectively when ground truth action sequences are considered to make predictions. While TGT is the second-best performer on Assembly101, it obtains best results on EPIC-Tent ($64.1$ vs $58.3$ in average $F_{1}$ score). This is due to the nature of action annotations in the two datasets. Indeed, while key-step names are informative in EPIC-Tent (e.g., “Place Vent Cover”, “Open Stake Bag”, or “Spread Tent”), they are less distinctive in Assembly101 (e.g., “attach cabin”, “attach interior”, or “screw chassis”). This highlights the flexibility of the proposed learning framework which can work in purely abstract, symbolic settings, with the DO approach, but can also leverage semantics with TGT when beneficial. Interestingly, the second best performers are graph-based approaches, with $MSG^{2}$ achieving an average $F_{1}$ of $56.1$ on Assembly101 and the simple Count-Based approach obtaining an average $F_{1}$ score of $56.6$ on EPIC-Tent. In contrast, PREGO obtains average $F_{1}$ scores of $39.4$ and $32.1$ on Assembly101 and EPIC-Tent respectively, suggesting the potential of explicit graph-based representations for mistake detection, versus the implicit one of PREGO. Breaking down performance into correct and mistake $F_{1}$ scores reveal some degree of unbalance of our approaches and the main competitor $MSG^{2}$ towards identifying correct actions rather than mistakes. This suggests that the related graph-based representations tend to detect some spurious pre-conditions, probably due to the limited demonstrations included in the videos, while the implicit PREGO model exhibits a skew with respect to mistakes. Further breaking down $F_{1}$ scores into related precision and recall values highlights that the main failure modes are due to large imbalances between precision and recall. For instance, the Count-Based method achieves a precision of only $5.1$ with a recall of $86.2$ in predicting correct segments on Assembly101. In contrast, the proposed approach obtains balanced precision and recall values in detecting correct segments in Assembly101 ($98.2$/$83.4$) and EPIC-Tent ($94.8$/$92.4$), and detecting mistakes in EPIC-Tent ($33.2$/$35.7$), while the prediction of mistakes on Assembly101 is more skewed ($46.7$/$90.4$).Results based on action sequences predicted from video (bottom part of Table3) highlight the challenging nature of the task, when considering noisy action sequences. While the explicit task graph representation may not accurately reflect the predicted noisy action sequences, we still observe improvements over previous approaches of $+7.3$ and $+1.3$ in average $F_{1}$ score in Assembly101 and EPIC-Tent. Remarkably, best competitors are still graph-based methods, such as $MSG^{2}$ and the Count-Based approach, with significant improvements over the implicit representation of the PREGO model ($32.5$ average $F_{1}$ versus $53.5$ of the proposed DO model). Also in this case, we observe that graph-based methods tend to be skewed towards detecting correct action sequences. In this regard, our TGT model only achieves $38.2$ mistake $F_{1}$ score, a drop in $5.5$ points over the best performer, the Count-Based method, which, on the other hand, only achieves an $F_{1}$ score of $2.5$ when predicting correct segments.

Task Graph Generation

Task graph generation is evaluated by comparing a generated graph $\hat{G}=(\hat{\mathcal{K}},\hat{\mathcal{A}})$ with a ground truth graph $G=(\mathcal{K},\mathcal{A})$. Since task graphs aim to encode ordering constraints between pairs of nodes, we evaluate task graph generation as the problem of identifying valid pre-conditions (hence valid graph edges) among all possible ones. We hence adopt classic detection evaluation measures such as precision, recall, and $F_{1}$ score. In this context, we define True Positives (TP) as all edges included in both the predicted and ground truth graph (Eq.(7)), False Positives (FP) as all edges included in the predicted graph, but not in the ground truth graph (Eq.(8)), and False Negatives (FN) as all edges included in the ground truth graph, but not in the predicted one (Eq.(9)). Note that true negatives are not required to compute precision, recall and $F_{1}$ score.
$$TP=\hat{\mathcal{A}}\cap\mathcal{A}$$(7)$$FP=\hat{\mathcal{A}}\setminus\mathcal{A}$$(8)$$FN=\mathcal{A}\setminus\hat{\mathcal{A}}$$(9)

Online Mistake Detection

We follow previous works on mistake detection from procedural egocentric videos[33, 37, 12] and evaluate online mistake detection with standard precision, recall, and $F_{1}$ scores. We break down metrics by the “correct” and “mistake” classes, as well as report average values.

B.1 Data Augmentation

In procedural tasks, it is common for certain actions to be repeated multiple times throughout the execution of a task. For example, in the EPIC-Tent dataset[17], an operation such as "reading the instructions" may be performed repeatedly at any point during the task. To model key-step orderings within the framework of topological sorts, our approach assumes that sequences should not contain such repetitions. Since repetitions denote that a specific action can appear at different stages of a procedure, we expand each sequence with repetitions to all distinct sequences obtained by dropping repeated actions.This data augmentation strategy enhances the robustness of our model on Assembly101[33] and EPIC-Tent[17], while it was not necessary for the CaptainCook4D dataset[26], as sequences do not contain any repetitions.

B.2 Early Stopping

B.3 Hyperparameters

Table4 details the hyperparameters employed in the experiments for task graph generation on the CaptainCook4D dataset[26]. During the training of TGT, we utilized a pre-trained EgoVLPv2[28] to extract text and video embeddings. The temperature value $T$ used in the cross-entropy distinctiveness loss was set to $0.9$ as in[29].

For the downstream task of online mistake detection within the DO model framework, we extended the maximum training epochs to 1200 for Assembly101[33]. This change was necessary because, even after 1000 epochs, the model continued to exhibit many cycles among its 86 nodes. Extending the number of epochs allows the model additional time to learn and minimize these cycles, which is crucial given the complexity of the graph. In the TGT configuration, we preserved the hyperparameters consistent with those used in the CaptainCook4D settings, except for adjusting the beta values to 1.

You are referred to the code for additional implementation details.

B.4 LLM Prompt

Below is the prompt that was employed to instruct the model on its task, which involves identifying pre-conditions for given procedural steps.

I would like you to learn to answer questions by telling me the stepsthat need to be performed before a given one.The questions refer to procedural activities and these are of the following type:Q - Which of the following key steps is a pre-condition for the current key step"add brownie mix"?- add oil- add water- break eggs- mix all the contents- mix eggs- pour the mixture in the tray- spray oil on the tray- None of the aboveYour task is to use your immense knowledge and your immense ability to tell mewhich preconditions are among those listed that must necessarily be carried outbefore the key step indicated in quotes in the question.You have to give me the answers and a very brief explanation of why you chose them.Provide the correct preconditions answer inside a JSON format like this:{ "add brownie mix": ["add oil", "add water", "break eggs"]}

B.5 Data Split

The CaptainCook4D dataset[26] comprises various error types, including order errors, timing errors, temperature errors, preparation errors, missing steps errors, measurement errors, and technique errors. Of these, missing steps and order errors directly impact the sequence integrity. Consequently, for our task graph generation, we utilized only those sequences of actions free from these specific types of errors. Table5 shows statistics on the CaptainCook4D subsets used for task graph generation.

For Online Mistake Detection, we considered the datasets defined by the authors of PREGO[12].

In the context of pairwise ordering and forecasting, we employed the subset of the CaptainCook4D dataset designated for task graph generation (refer to Table5) and divided it into training and testing sets. This division was carefully managed to ensure that 50% of the scenarios were equally represented in both the training and testing sets.

B.6 Pairwise ordering and future prediction

We setup the pairwise ordering and future prediction video understanding tasks following[42].

B.7 Graph Post-processing

We binarize the adjacency matrix with the threshold $\frac{1}{n}$, where $n$ is the number of nodes. After this thresholding phase, it is possible to encounter situations like the one illustrated in Figure4, where node A depends on nodes B and C, and node B depends on node C. Due to the transitivity of the pre-conditions, we can remove the edge connecting node A to node C, as node B must precede node A. Sometimes, it may occur that a node does not serve as a pre-condition for any other node; in such cases, the END node should be directly connected to this node. Conversely, if a node has no pre-conditions, an edge is added from the current node to the START node.

At the end of the training process, obtaining a graph containing cycles is also possible. In such cases, all cycles within the graph are considered, and the edge with the lowest score within each cycle is removed. This method ensures that the graph remains a Directed Acyclic Graph (DAG).

B.8 Details on Online Mistake Detection

Given the noisy sequences in Assembly101[33] and EPIC-Tent[17], a distinct approach was adopted during the post-processing phase of task graph generation. Specifically, if a key-step in the task graph has only two pre-conditions and one is the START node, the other pre-condition will be removed regardless of its score, otherwise we apply the transitivity dependences reduction aforementioned. This approach allows for a graph with fewer pre-conditions in the initial steps.

B.9 Qualitative Examples

Figure5 reports a qualitative example of a prediction.

B.10 Experiments Compute Resources

The experiments involving the training of the DO model on symbolic data from the CaptainCook4D dataset proved to be highly efficient. We were able to generate all the task graphs in approximately half an hour using a Tesla V100S-PCI GPU. This GPU allowed us to run up to 8 training processes simultaneously. In contrast, training the TGT models for all scenarios in the CaptainCook4D dataset required about 24 hours, with the same GPU supporting the concurrent training of up to 2 models. Additionally, once the task graphs were obtained, executing the PREGO benchmarks for mistake detection was significantly faster, requiring online action prediction, which could be performed in real-time on a Tesla V100S-PCI GPU.