Activity Grammars for Temporal Action Segmentation
Authors: Dayoung Gong
Joonseok Lee
Deunsol Jung
Suha Kwak
Minsu Cho
Venue: NeurIPS 2023 poster (2023)
Keywords: neuro-symbolic approach
Temporal action segmentation
grammar

Abstract: Sequence prediction on temporal data requires the ability to understand compositional structures of multi-level semantics beyond individual and contextual properties of parts. The task of temporal action segmentation remains challenging for the reason, aiming at translating an untrimmed activity video into a sequence of action segments. 
This paper addresses the problem by introducing an effective activity grammar to guide neural predictions for temporal action segmentation.  
We propose a novel grammar induction algorithm, dubbed KARI, that extracts a powerful context-free grammar from action sequence data. We also develop an efficient generalized parser, dubbed BEP, that transforms frame-level probability distributions into a reliable sequence of actions according to the induced grammar with recursive rules. 
Our approach can be combined with any neural network for temporal action segmentation to enhance the sequence prediction and discover its compositional structure. 
Experimental results demonstrate that our method significantly improves temporal action segmentation in terms of both performance and interpretability on two standard benchmarks, Breakfast and 50 Salads.

Activity Grammars for Temporal Action Segmentation
Dayoung Gong"
Joonseok Lee"
Deunsol Jung
Suha Kwak
Minsu Cho
Pohang University of Science and Technology (POSTECH)
{dayoung
grong, gong, jameslee, deunsol, jung, suha. kwak, macho)@postech..c.. ac.
http://cvlab. http://vlaa..ostechh. ltt.kr//eeeet kcrrrssearch/KAR
Abstract
Sequence prediction on temporal data requires the ability to understand com- positional structures of multi-level semantics beyond individual and contextual properties. The task of temporal action segmentation, which aims at translating an untrimmed activity video into sequence of action segments, remains challenging for this reason. This paper addresses the problem by introducing effective activity grammar to guide neural predictions for temporal action segmentation. We propose novel grammar induction algorithm that extracts powerful context-free grammar from action sequence data. We also develop an efficient generalized parser that transforms frame-level probability distributions into reliable sequence actions according to the induced grammar with recursive rules. Our approach can be combined with any neural network for temporal action segmentation enhance the sequence prediction and discover its compositional structure. Experi- mental results demonstrate that method significantly improves temporal action segmentation terms of both performance and interpretability on two standard benchmarks, Breakfast and 50 Salads.
1 Introduction
Human activities in videos not proceed by accident; they are structured being subject to generative rules imposed by the goal of activities, the properties of individual actions, the physical environment, and so on. Comprchending such a compositional structure of multi-granular semantics in human activity poses significant challenge in video understanding research. The task of temporal action segmentation, which aims at translating an untrimmed activity video into a sequence of action segments, remains challenging due the reason. The recent methods based deep neural net- works [25, 9, 45, 2, 15, 16, I] have shown remarkable improvement in learning temporal relations of actions in implicit manner, but often face out-of-contex errors that reveal the lack of capacity to capture the intricate structures of human activity, and the scarcity of annotated data exacerbates the issue in training. In this work, we address the problem by introducing effective activity grammar to guide neural predictions for temporal action segmentation.
Grammar is natural and powerful way of explicitly representing the hierarchical structure of languages [14] and can also be applied to express the structure of activities. Despite the extensive body of grammar- based research for video understanding [23, 24, 33, 35, 32], none of these approaches have successfully integrated recursive rules. Recursive rules are indispensable for expressing complex and realistic structures found in action phrases and activities. To achieve this, introduce novel activity grammar induction algorithm, Key-Action-base basedd Recursive Induction (KARI), that extracts a powerful probabilistic context-free grammar while capturing the characteristics of the activity. Since an activity is composed of multiple actions, each activity exhibits a distinctive temporal structure based pivotal actions, setting it apart from other activities. The proposed grammar induction
Equual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

enables recursive rules with flexible temporal orders, which leads to powerful generalization capability, We also propose novel activity grammar evaluation framework to evaluate the generalization and discrimination power of the proposed grammar induction algorithm. To incorporate the induced activity grammar into temporal action segmentation, we develop an effective parser, dubbed BEP, which searches the optimal rules according to the classification outputs generated by an off-the-shelf action segmentation model. Our approach can be combined with any neural network for temporal action segmentation to enhance the sequence prediction and discover its compositional structure.
The main contribution of this paper can be summarized as follows:
We introduce a novel grammar induction algorithm that extracts powerful context-free grammar with recursive rules based on key actions and temporal dependencies.
We develop an effective parser that efficiently handles recursive rules of context-free gram- mar by using Breadth-first search and pruning.
We propose new grammar evaluation framework to assess the generalization and discrimi- nation capabilities of the induced activity grammars.
We show that the proposed method significantly improves the performance of temporal action segmentation models, as demonstrated through comprehensive evaluation on two benchmarks, Breakfast and 50 Salads.
2 Related work
Grammar for activity analysis. Grammar is an essential tool to represent the compositional
structure of language [14] and has been mainly studied in the context of natural language processing
(NLP) [21, 22, 20,37] 37]. Grammar has been extensively studied in various research areas [28, 29, 32, 8, 43, 13, 42, 11, 27, 12]. Similarly, grammatical framework can be used to express the structure of activities. Several work [23, 24, 33, 35] have defined context-free grammars based on possible temporal transitions between actions for action detection and recognition. Vo and Bovick [41] propose a stochastic grammar to model a hierarchical representation of activity based on AND-rules and OR-rules. Richard et al. [34] propose context-free freee grammar defined on action sequences for weakly-supervised temporal action segmentation. Qi et al. [30, 32, 31] utilize a grammar induction algorithm named ADIOS [37] induce grammar from action corpus. However, none of the proposed grammar for activity analysis includes recursive rules, which are a fundamental factor in expressing repetitions of actions or action phrases. In this paper, we propose novel action grammar for temporal action segmentation based on key action and temporal dependency between actions considering recursive temporal structure.
Temporal action segmentation (TAS). Various methods have been proposed to address the task. Early work utilizes temporal sliding windows [36, 19] to detect action segments, and language- based methods [24, 23] has been proposed to utilize a temporal hierarchy of actions during segmentation. Recently, a deep-learning-basee based model named the temporal convolutional networks (TCN) has been proposed with an encoder-decoder architecture [25, 9]. Moreover, wransformrrbbase models [45, 2] recently introduced to leverage global temporal relations between actions based on self-attention and cross-attention mechanisms [40]. Other researches have been proposed to improve the accuracy of temporal action segmentation based on existing models [9, 45]. Huang et al. [15] introduce network module named Graph-based Temporal Reasoning Module (GTRM) that is applied on top of baseline models learn temporal relations of action segments. Ishikawa et al. [16] suggest an action segment refinement framework (ASRF) dividing a task into frame-wiss action segmentation and boundary regression. They refine frame-level classification results with the predicted action boundaries. Gao et al. [10] propose a global-to-local search scheme to find appropriate receptive field combinations instead of heuristic respective fields. Ahn and Lee [1] recently propose hierarchical action segmentation refiner (HASR). which refines segmentation results by applying multi- gultilggraular context information from videos. A fast approximate inference method named FIFA for temporal action segmentation and alignment instead of dynamic programming is proposed by Souri et al. [38]. Other researches [5, 6] reformulate TAS as a cross-domain problem with different domains of spatio-temporal variations, introducing self-supervised temporal domain adaptation. Xu et al. [44] proposes differentiable temporal logic (DTLL, which is model-agnostic framework to give temporal constraints to neural networks. In this paper, we propose syuoolyymbolic approach where the activity grammar induced by the proposed grammar induction algorithm guides a temporal action segmentation model to refine segmental errors through parsing.

---

TAS model
Seg. Opt.
KARI
BEP
action sequences
(a') L)
(a) activity grammar induction
(b) parsing
(c) optimization
KARI-induced grammar, video, prediction, (a',t") ..) refined (sequences, length), Seg. Opt.: segmentation optimization
Figure 1: Overall pipeline of the proposed method. (a) KARI induces activity grammar G from action sequences in the training data, (b) BEP parses neural predictions from the off-the-shelf temporal action segmentation model given video F using the KARI-induced grammar G, and (c) the final output of optimal action sequences and lengths (a", ,!*) is achieved through segmentation optimization. is best viewed in color.
3
Our approach
Given video of frames [Fi, F2,..., Fr) and a predefined of action classes A, the goal of temporal action segmentation is to translate the video into sequence of actions a = [01. 02 .... ON and their associated frame lengths
[4, 12, ..., IN] where N is unknown, a, A for S i N. a, F 0,+1 for S < N - 1, and > i- 1 = T.2 The resultant output of a and Z indicates that the video consists of N segments and each pair (a;, 4) represents the action and length of ith segment.
In this work, we introduce an activity grammar that guides neural predictions for temporal action segmentation through parsing. We propose novel activity grammar induction algorithm named KARI and an efficient parser called BEP. The overall pipeline of the proposed method consists of three steps, illustrated in Fig. 1. First of all, KARI induces activity grammar from action sequences in the training data. Using the KARI-induced grammar, BEP then takes the frame-level class prediction Y E 7 from the off-the-shelf temporal action segmentation model [45, 9] and produces grammar-consisten action sequence a". Finally, segmentation optimization is performed to obtain optimal action lengths /" based on a* and Y. In the following, we introduce the activity grammar probabilistic context-free grammar (Section 3.1), present KARI (Section 3.2) and BEP (Section 3.3), and describe a segmentation optimization method for final outputs (Section 3.4).
3.1 Activity grammar
We define the activity grammar probabilistic context-free grammar (PCFG) [17], designed to derive diverse action sequences pertaining to a specific activity class. The activity grammar, denoted G (V. Σ, P, S),, follows the conventional PCFG which consists of four components: finite set of variables V, finite set terminals Σ, finite set of production rules P, and the start symbol S E V. In our context, the of terminals Σ becomes the of action classes A, and the production rules P are used to generate action sequences from the start variable S. We use two types of production rules, 'AND' and 'OR', defined follows:
AND : V V
where E V Vand a E (EUV), OR: V Vi [P.] 1/2 [p2] ... V. [P.] where V, Vi. Vn E V.
(I)
(2)
The AND rule replaces head variable V with sequence of variables and terminals a, determining the order of the terminals and variables. In contrast, the OR rule converts a head variable V to sub-variable Vi with the probability pa, providing multiple alternatives for replacement; 'I' denotes "OR' operation. These two types of rules allow us to generate action sequences hierarchically.
3.2 Grammar induction: Key-Action-based Recursive Induction (KARI)
Grammar induction refers the process of learning grammars from data [37]. our context, takes action sequences of a specific activity in the training set and produces an activity grammar that is
'I fact. this form of output is equivalent to that of frame-level level action classification, which predict an action class for each frame, and the sequence of revel-level actions easily converted to (a, () and vice versa.

---

1 pour coffee, pour milk]
s yh ya pR
ppur coffee, spoon sugar, pour milk]
pt - takee cup' |
take cup. pour coffee, milk, spoen sugar. stir coffee]
yM "pour coffee'
[take cup. pour coffee, spoon sugar, stir coffee]
V V V
(a) Action sequences in the training set D
V pour milk 111 sspoon sugar F
V2 "stir coffee V
take cup
pour coffee
pour milk
spoon sugar
stir coffee
S
a3
(b) Sub-sequence partitioning based on the key action
D {[c], [take cup]}, D* [[pour eoffee]],
D [[pour milk], [spoon sugar, pour milk], [pour milk, spoon sugar, stir coffee], [spoon sugar, coffee]]
iVR
V.R
(c) The set of sub-sequences D DM, and
A (take cup), AM fpour eoffee), A fpour milk, spoon sugar, stir coffee]
(d) The action set A", AMM,, and AR
[take c. dM spoon sugar). (stir coffee]]
[(pour coffee]], d² [(pour milk,
variable
terminal
terminal (key action)
AND
(e) The dependency sequence d', and dR
(I) KARI-induced activity grammar
Figure 2: Example activity grammar induction of KARL. (a) Example action sequences are provided with 'pour coffee' as the key action with Nkey set to 1. (b) Action sequence, e.g., 0z, is segmented into sub- sequeneesss based on key actions. (c) All action sub-sequences a consist set of sub-sequences D (d) The action set A contains all the actions occurring in D (c) Temporally independent actions are grouped, where each action group is temporally dependent in the action group sequence df, (f)) The resultant KARI-induced activity grammar is shown. For simplicity, omit the probability, and it best viewed color.
able to parse action sequences of the activity; the induced grammar should be able parse unseen sequences the activity as well as the sequences in the training set for generalization. To obtain an effective activity grammar avoiding under-lover-geneee generalization, introduce main concepts for grammar induction: key action and temporal dependency.
The key actions for a specific activity are those consistently present in every action sequence from training dataset. Specifically, the top Nkey most frequently occurring actions among these are selected the key actions. The hyperparameters of the number of key actions Niky affects the degree of generalization achieved by induced grammar. The temporal dependency refers to the relevance of temporal orders across actions. Temporally independent actions do not occur in specific temporal order. This concept of temporal dependency can also be extended to groups of actions, meaning that some groups of actions can be temporally dependent others.
We induce an activity grammar based on the key actions and the temporal dependency. Action sequences are divided into sub-sequences using the key actions as reference points, and the temporal dependencies between actions within the sub-sequences are established; temporally dependent actions are represented using AND rules (Eq. 1), while temporally independent actions are expressed with OR rules (Bq. 2). We give an example of grammar induction in Fig. 2; four action sequences are given in Fig. 2a, where the action class 'pour coffee' is chosen as the key action with the number of key actions key set to
Given the action sequences from the training dataset D, we begin grammar induction by identifying of key actions C with the pre-defined hyperparameter likey Using the key actions, each action sequence a E D is divided into three parts: a = [at. a. R]. The sub-sequences a² a. and a denote the portions of the original action sequence that occurred before, between, and after the key actions, respectively; the sub-sequence a starts from the first key action and includes up to last key action IC. An example in Fig. 2b shows that the action sequence ag divided into three sub-sequences using the key actions. For notational convenience, we will use the superscript E (T., M, R) to denote one of the three parts. All action sub-sequences a in specific part are grouped to consist in corresponding set of sub-sequences D (cf. Fig 2c). The action set R C A

---

is then defined to contain all the actions occurring in D (cf. Fig 2d). To determine the temporal dependencies among the actions of A pairwise temporal orders are considered as follows. If one action always occurs before the other in DD, then the two actions are temporally dependent and otherwise temporally independent. Based on the concepts, we construct the action group sequence d by collecting the temporally independent actions as an action group and arranging such action groups according to their temporal dependencies (cf. Fig 2c).
In the following, we describe how to construct the production rules P of the activity grammar G.
Start rule. We first create the rule for the start variable S:
- V y VR,
where VL, VM, and VR are variables used to derive left, middle, and right parts of the action sequence, respectively.
Rule for the variable Va, For Vo, Ω E [I, construct an AND rule of action groups based on action group sequence d
Va VP V2
V/2 ldap
where the variable Viº represents the ith action group in the action group sequence of. Since actions in an action group are considered temporally independent, we construct an OR rule for each action group:
(5) where d, denotes the Jeh action from the action group df. The variable V,8 yields dh V.8 with the probability v.,-- This rule can be recursively used to proceed to the variable V,8 in the next step. This recursive structure allows for repeated selection of actions within the same action group, leading to the generation of diverse action sequences, which effective for generalization. To avoid an infinite loop of the recursion, the empty string with the escape probability p, is added to Eq. 5. For the details, refer to the transition probability pf, and the escape probability Pf. in Appendix A.1.
vp + c. V, [p.
V 12 ... ..... -.I1%, V; IP
11 [pf.,,
Rule for the middle variable VM, Since the temporal order of key actions might vary, we consider all the possible temporal orders between key actions in IC. A set of temporal permutations of actions is denoted as II, where each possible temporal permutation is represented by the OR rule:
V
V.M [pM]
V/2
[P2]
VM [n)) [p]1)
The rule for the permutation variable V;M is defined by the AND rule:
V.M .T M(.1)
T... V Mi.Im.))) V
where all the key actions are included. Note that m.j represents the jth action of the permutation π. E 11, and the variable M((5) derives action sub-sequences between actions Ti.j and π.,++1 The production rule for MM((J) adheres to the rules specified in Eq. 4 and 5. The resultant KARI-induced grammar from the example is shown Fig. 2f, highlighting the compositional structure of actions.
3.3 Parser: Breadth-first Earley Parser (BEP)
The goal of the parser is to identify the optimal action sequence a" by discovering the most likely grammatical structure based on the output of the action segmentation model [9, 45]. other words, the parser examines the production rules of the activity grammar to determine whether the given neural prediction Y can be parsed by the grammar G. However, when the grammar includes recursive rules, the existing parser struggles to complete the parsing within reasonable time due to the significant increase in branches from the parse tree. To address this challenge, we introduce an effective parser dubbed BEP, integrating Breadth-first search (BFS) and pruning technique into generalized Earley parser (GEP) [32]. Since the BFS prioritizes production rules closer to the start variable, it helps the parser understand the entire context of the activity before branching to recursive iterations. Simultaneously, pruning effectively reduces the vast search space generated by OR nodes and recursion, enabling the parser to focus more relevant rules for the activity.
For parsing, we employ two heuristic probabilities introduced in [32] to compute the probability of variables and terminals within the parse tree. Specifically, let Yt,z denote the probability of frame t
5

---

being labeled as r. In this context, we denote the last action in the action sequence a as 2, i.e. = aN. where a = [a) d2. ..., ax], for simplicity. The transition probability g(x Q1:N-1. G) determines the probability of parsing action x given the 01:N-1 and the grammar G.
The parsing probability pl Fi:r a () computes the probability of being the action sequence for Fi.r. The probability at = 1 is initialized by:
(a e, G) X1, if a contains only I. 0
p + a G) =
(8)
otherwise,
where e indicates an empty string.
Since assume that the last action of is classified as x, the parsing probability p(F1: a GG) can be represented with the probability of the previous frames:
P a GG) =
(PFF.t (1:11 a () g( a G) + GI) (9)
The prefix probability p(Fi.T + a... G) represents the probability of a being the prefix of a". This
probability is computed by measuring the probability that is the action sequence for the frame Fi:r with l in the range [1;
p F1:T - a... G) - p(Pi + a () + g a.celaG---..C G) Σ Y P.. + aI:N-1 (10)
1=2
The parsing operation is structured following the original Earley parser [7], consisting of three key operations: prediction, scanning, and completion. These operations involve the update and generation of states, where every state comprises the rule being processed, the parent state, the parsed action sequence denoted as and the prefix probability denoted as p(a...). The states are enqueued and prioritized by their depth d within the parse tree.
Prediction: for every state Q(m, n. d) of the form (A + a B3, ki, a. p(a..))) add (B + -1', (m,, n, d), a, p(a..)) to Q(m, n, d + 1) for every production rule in the grammar with B on the left-hand side.
Scanning: for every state in Q(m, n, d) of the form (A - a- wB, (i,, k:), a. a(p(a..)). append the new terminal w to a and compute the probability p((a+ + w)...) Create new set Q(m+ 1, n', d) where n' is the current size of Q(m + 1). Add (A - aw 3, (i,
w, w.p((a + w)..)) to Q(m + 1, nd)d).
Completion: for every state in (m, n, d) of the form (A + r., Q(ij,, a. a(p.....)) find states in Q(i, j. k) of the form (B + a A3, Q K'k,), p(a'..a))) and add (B aA 3, Q(' J", K)), a. p(a..)) to Q(m, n. 1).
The symbols a, B, and I' represent arbitrary strings consisting of terminals and variables, i.e. a, B, I' e (EUV). The symbols A and B refer to the variables, while denotes single terminal. The symbol Q represents the set of states, and the dot (-) denotes the current position of the parser within the production rule.
Additionally, we introduce a pruning technique of limiting the queue size to reduce the vast search space in the parse tree, similar to the beam search. Specifically, the parser preserves only the top Nqueee elements from the queue in order of the parsing probability of each state. The parsing process terminates when the parser identifies that the parsed action sequence a" has higher parsing probability than the prefix probabilities of any other states in the queue. For the further details, refer to Appendix B.
3.4 Segmentation optimization
The objective of segmentation optimization is to determine the optimal alignment between the input classification probability matrix Y and the action sequence a". In other words, the entire frames are allocated within the action sequences a" [a] 05, .... ]. obtained from the parser, to determine the optimal action lengths 1- = [[i 42.... ]. In this work, we utilize dynamic programming-bast Viterbi-like algorithm [35] for activity parsing. Similar to [26, 32], the optimizer explores all possible allocations and selects the one with the maximum product of probabilities:
l' arg max(p(1 aa", Yı:r)),
(11)
pll a, YI.) max(p((uxn))))) a1.N 1, Y..) it
II Y yax)
(12)

---

Lu synthetic
Syettati gantter lalos
G
generation
O
seen
unseen
Syntheic arsrerrr inkos
KARB KARt-indasal gramtrrr indes.
ADIOS-OR-indaa grammar intes
100 00oo
Figure 4: Confusion matrix of activity grammars. The results of KARI-induced grammar are similar to the synthetic grammar, showing high recall with comparable precision.
all
X
grammar induction
parser
Table 1: Synthetic G
Table 2: Synthetic G II
X
G
precision
recall
grammnr
precision
recall
ADIOS-AND
0.97
0.08
ADIOS-AND ADIOS OR
0.98
0.06
ADIOS OR
0.99
0.25
1.00
0.33
Figure 3: Grammar evaluation
KART (ouns)
0.93
0.98
KART (ours)
0.92
0.96
4 Experimental evaluation and analysis
4.1 Datasets and evaluation metrics
Datasets, We conduct experiments on two widely used benchmark datasets for temporal action segmentation: Breakfast [23] and 50 Salads [39]. The Breakfast dataset, consisting of 1,712 videos, involves 52 individuals preparing 10 different breakfast activities comprised 48 actions in 18 different kitchens. Similarly, the 50 Salads dataset comprises 50 egocentric videos of people preparing salads of a single activity with 17 fine-grained actions from 25 people. We used I3D [4] features provided by [9].
Evaluation metrics. For evaluation metrics, we report edit score, F1 @1 (10, 50) scores, and frame-wise accuracy following the previous work [9, 45].
4.2 Implementation details
For KARI, we set the hyperparameters of the number of key actions Nkey 4 for Breakfast, and for 50 Salads. We individually induce separate activity grammar for the ten activity classes within Breakfast and subsequently merge them into a unified grammar. For the comparison with the existing grammar used in the previous work [32, 31], we induce activity grammars of ADIOS [37] provided by [31]. Two types of ADIOS-induced grammar are induced: ADIOS-AND-induced grammar, primarily composed of AND rules with limited generalization capabilities, and ADIOS-OR-induce grammar, predominantly incorporating OR rules, offering improved generalization. Please refer to Appendix C.1 for grammar induction details.
For BEP, we configured the queue size Nqqueue to be 20. For efficiency, we adjust the sampling rate of the input video features 50 for Breakfast and 100 for 50 Salads. We use two widely used models for the temporal action segmentation: ASFormer [45] based on Transformer and MS-TCN [9] based on CNNs. Since apply the proposed method to the reproduced temporal action segmentation models, we directly compare and evaluate the performance based on the reproduced results.
4.3 Evaluation framework for activity grammar
We propose a novel evaluation framework to assess the generalization and discrimination capabilities of the activity grammar. Figure 3 shows the overall process of the grammar evaluation framework. We first generate set of synthetic activity grammars g randomly. Action sequences a E D:"ll are generated from each synthetic grammar G E gS and these sequences are randomly divided into two sets: seen and unseen. For each seen set, grammar induction algorithm is applied, resulting in the induced grammar G consisting in a corresponding set of induced grammars G¹. For grammar evaluation, the induced grammar G. E g parses action sequences from the entire unseen sets. The induced grammar should accurately parse the action sequences generated by the original synthetic grammar from which was induced, while also effectively discriminating those generated by other synthetic grammars.
To simulate real-world video action sequences, we generate the synthetic activity grammars assuming temporal dependencies across actions. This indicates that certain actions follow temporal order
7

---

Table 3: The performance comparison on 50Salads
model
re- prod.
refine- ment
grammar induction
edit
F1 @ 10
F1@25
FI @50
acc.
75.0
76.0
70.6
57.4
73.5
76.5
83.8
81.7
74.8
86.1
ASFormer [45]
ADIOS-AND
58.3
70.0
68.0
59.4
76.2
ADIOS-OR
61.1
72.0
70.1
62.4
78.9
KARI
79.9
85.4
83.8
77.4
85.3
67.9
76.3
74.0
64.5
80.7
62.4
69.5
65.3
55.7
75.2
MS-TCN
ADIOS-AND
56.8
66.4
63.8
52.9
72.5
ADIOS-OR
61.9
69.1
66.9
57.2
74.2
KARI
66.7
75.1
73.2
60.8
76.7
Table 4: The performance comparison on Breakfast
model
re- prod.
refine- ment
grammar induction
edit
@0@10
F1@25
F1 @5
acc.
75.0
76.0
70.6
57.4
73.5
75.6
77.3
72.0
59.4
74.3
ASFormer [45]
ADIOS-AND
69.2
69.8
64.9
52.2
72.4
V
ADIOS-OR
70.3
71.8
66.8
54.2
71.8
KARI
77.8
78.8
73.7
60.8
74.0
61.7
52.6
48.1
37.9
66.3
69.7
70.7
65.1
52.6
69.4
MS-TCN [9]
ADIOS-AND
68.0
66.7
61.0
48.0
68.4
ADIOS-OR
69.6
69.2
63.3
50.3
68.2
KARI
74.9
74.6
68.7
55.1
68.8
while others do not adhere to such dependencies. To prevent parsing failures arising from uncovered terminals, we maintain a consistent set of terminals throughout the entire grammar while randomly assigning key actions these terminals. The number of variables randomly determined for each synthetic grammar. As evaluation metrics, we use precision and recall similar to the previous work [37, 3]. For the induced grammar G.P, action sequences successfully parsed from the synthetic grammar G. classified positive samples from the entire unseen sets, otherwise considered negative samples.
Details. In our experiment, we generate total of 100 grammars, each consisting of 20 variables and 20 terminals. We have developed two types synthetic grammars that differ in terms of temporal hierarchical difficulty. In synthetic grammar I, each terminal is allocated to single variable, while in synthetic grammar II, terminals are randomly assigned multiple times to different variables. Three types of grammars are evaluated: induced ADIOS-ANI ADIOS-OR, and proposed KARI.
Results. Table and Table show the results of grammar evaluation by using synthetic grammar and II, respectively. Our activity grammar demonstrates robust generalization performances, achieving recall of approximately 1.0 on unseen action sequences compared to others, maintaining comparable precision. The ADIOS-OR -e-S--R--nnuued grammar shows better generalization ability compared to the BEHOS-AND-inducee grammar. We visualize confusion matrix of the three types of grammar: synthetic grammar, KARI-induced grammar, and ADIOS-OR iiddudd grammar, as shown in Fig. 4. The confusion matrix shows the parsing accuracy of each unseen set over the synthetic grammar Higher accuracy is represented by brighter cells in the matrix. KARI-induced grammars demonstrate similar patterns their confusion matrix compared to the synthetic grammars. This similarity indicates their capacity to generalize to unseen sets from which each grammar is induced, allowing effective discrimination of action sequences from other synthetic grammars.
4.4 Effects the grammar-based refinement on temporal action segmentation
Table and Table 4 show the performance of applying the proposed method to temporal action segmentation models [9, 45] across two benchmark datasets. The first row Table and Table indicates the performance from the original paper [9, 45], whereas the second row represents the
8

---

Table 5: Ablation study of KARI on 50 Salads. Using both key action and recursive rules is effective for refining neural predictions from the temporal action segmentation models.
refinement
key actions
recursive rules
edit
FI 10
FI 25
Fl @ 50
acc.
79.9
85,4
83.8
77.4 67.4 (10.0L)
85.3
69.2 (10.7.)
77.1 (8.31)
74,9 (8.9.)
80.9 (4.4J)
62.6 (17.3L)
72.9 (12.5L)
70.5 (13.3))
63.0 (14.11)
78.8 (6.5l)
Table 6: BEP vs. GEP. BEP is effective under a fair comparison to GEP.
Table 7: Ablation on N Using proper number of key actions matters.
parser
Nqueue
F1@
@5
acc.
N kayy
edit
FI
F1
F
acc.
73.3
81.1
79.1
72.9
84.0
73.0
81.5
79.9
72.6
83.5
GEP
72.1
80.5
79.1
72.3
83.9
77.8
85.1
83.5
77.1
85.8
30
72.3
79.8
78.1
71.4
84.2
79.9
85,4
83.8
77.4
85.3
10
78.3
84.9
83.2
76.9
84.9
4
74.3
82.2
80.5
73.5
83.3
BEP
20
79.9
85,4
83.8
77.4
85.3
5
71.2
78.6
76.3
68.6
80.4
78.9
85.5
83.8
77.3
85.1
6
68.4
75.2
73.3
64.2
77.9
reproduced performance obtained using official codes. The comparison between the second and the last row of each compartment in each table reveals significant improvements in both edit scores and FI scores. This result validates the effectiveness of leveraging activity grammars to refine segment- classification. Remarkably, the KARI-induces grammar shows great performance compared to both ADIOS- induced grammars, demonstrating the importance of generalizing the grammar to cover unseen action sequences during inference effectively.
4.5 Analysis
Ablation studies of KARI. Ablation studies of KARI are conducted on the 50 Salads dataset using ASFormer [45], as shown in Table 5 to demonstrate the effectiveness of each component, including key actions and temporal dependency. The results show that both key actions and recursive rules contribute to the significant improvement of grammar-based refinement. In particular, using recursive rules is essential for the activity grammar to be generalized to the unseen action sequences.
BEP vs. GEP. Table 6 presents the performance comparison of GEP and BEP using KARI-induced grammar. We limit the queue size of both parsers, as the parser without the limitation fails to complete parsing within reasonable time. The results indicate that BEP outperforms GEP under the same condition. This attributed to GEP prioritizing states based on the highest probability, which increases the risk of getting trapped in local optima when performing selective pruning within specific branches. In contrast, BEP, which prioritizes low-depth states, allows for easier escape from cycles and OR nodes, contributing to improved overall performance.
The number key actions. Table 7 shows the results by adjusting the number of key actions Nkey of KARI on 50 Salads. We set the value of Neyy ranging from to 6, where the induced grammar with smaller value generates the larger activity corpus. We find that setting Nkey to 3 outperforms the others, demonstrating the importance of achieving appropriate level of generalization for effective refinement. Both excessive and insufficient generalization can negatively impact performance, highlighting the need to strike balance in the generalization ability of the activity grammar.
Grammar evaluation on real data. We evaluate the parsing recall on the unseen action sequences of the Breakfast dataset. The results present the average recall across all splits for each activity. The number inside brackets indicates the average length of action sequences of each activity in D. Table 8 compares the generalization capability of the five grammar induction algorithms [23, 35, 37), including KARI (details Appendix C. The result demonstrates that KARI-induced grammar shows better generalization ability on real data compared to others. Remarkably, the KARI-induced grammar shows robust performance with the extended average length of the action sequences, whereas other algorithms exhibit poor generalization.
4.6 Qualitative results
Figure presents a visual representation of the refined segmentation results on benchmark datasets. The proposed method successfully parses and identifies the actions 'pour oil' (red bar in Fig. 5a)

---

Table Grammar evaluation on real data. We evaluate the proposed KARI-induced -armmmrr on Breakfast, demonstrating the superior high recall on unseen action sequences from each activity. The average length of action sequences of each activity shown in parentheses.
scrambled egg (11.9)
pancake
salad (9.9)
fried egg
juice (7.2)
coffee (6.7)
sandwich (6.0)
cereal (5.1)
milk (5.0)
total (7.7)
Grammar induction
(11.1)
(9.5)
(5.0)
Kuchne ef al. [23]
0.25
0.24
0.0
0.32
0,53
0.80
0.63
0.96
0.78
0.91
0.53
Richard et [35]
0.25
0.24
0.0
0.32
0.53
0.80
0.63
0.96
0.78
0.91
0.54
ADIOS-ANDI [37]
0.25
0.24
0.32
0.53
0.80
0.63
0.78
0,91
0.54
ADIOS-OR [37]
0.39
0.30
0.37
0.53
0.55
0,80
0.73
0.96
0.78
0.92
0.63
KARI
0.84
0.71
0.90
0.70
0.77
1,00
0.91
0.96
0.90
0.98
0.87
GT
ASFommer
ADIOS-OR
KARI (Ours)
egg
pour egg2pan
stirfty ese
add salmpppper
take plase
ogs2Pltte
put pancakciplate
(a) Breakfast
GT
ASFonner
ADIOS-OR
KARI (Ours)
action start/end
cut lettuce
place lestuce
cui tomatoo
place tomato
peel cucumber
cut cucumber
place cucumber
cheese
place cheese
ingredients
add
adá vinegar
add salt
add
mix dressing
salad
(b) 50 Salads
Figure 5: Qualitative results. KARI-induced grammar efficiently insert missing actions and removes out-of-context actions in ASFormer [45].
and 'add saltmpepper', (blue bar in Fig. 5a), which are omitted in the results obtained by using the ADIOS-OR induced grammar. The results show that KARI-induced grammar allows a more flexible temporal structure between actions. Furthermore, our method effectively removes actions such as 'put pancake2plate" that do not correspond to the intended activity. Similarly, qualitative results on 50 Salads in Fig. 5b show the effectiveness of the proposed method with complex action sequences. The overall results show that activity srammar-basel refinement for the temporal action segmentation model effective for correcting the neural predictions by using the grammar as a guide.
5 Conclusion
We have shown that the proposed approach enhances the sequence prediction and discovers its compositional structure, significantly improving temporal action segmentation in terms of both performance and interpretability. However, the improvement is limited by the initial output of the action segmentation network, which remains further research the future. We believe that the grammar induction and parsing methods can be easily applied to other sequence prediction tasks.
10

---

Acknowledgements
This work was supported by the IITP grants (2022-0-00264: Comprehensive video understanding and generation with knowledge-base deep logic (50%), 2022-0-00290: Visual intelligence for space- time understanding and generation based on multi-layered visual common sense (20%). 2022-0-00959: Few-shot learning of causal inference in vision and language (20%), and 2019-0-01906. Al graduate school program POSTECH (10%)) funded by the Korea government (MSIT).
References
[1] H. Ahn and D. Lee. Refining action segmentation with hierarchical video representations. In Proc. IEEE International Conference on Computer Vision (ICCV), pages 16302-16310, 2021. 1,2
[2] N. Behrmann, S. A. Golestaneh, Z. Kolter, J. Gall, and M. Noroozi. Unified fully and times-
tamp supervised temporal action segmentation via sequence to sequence translation. In Proc. European Conference on Computer Vision (ECCV), pages 52 52-68. Springer, 2022. 1,2
[3] P. Belcák, D. Hofer, and R. Wattenhofer. A neural model for regular grammar induction. arXiv preprint arXiv 16628, 2022. 8
[4] J. Carreira and A. Zisserman. Quo vadis, action recognition? new model and the kinetics dataset. Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 0299-6308, 2017.
[5] M.-H. Chen, B. Li, Y. Bao, and AlRegib. Action segmentation with mixed temporal domain adaptation. In Proc. IEEE Winter Conference on Applications of Computer Vision (WACV), pages 605-614, 2020.
[6] M.-H. Chen, B. Li, Y. Bao, G. AlRegib, and Kira. Action segmentation with joint self- supervised temporal domain adaptation. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 9454-9463, 2020. 2
[7] J. Earley, An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94- 102, 1970. 6, 15
[8] H.-S. Fang, Y. Xu, W. Wang, X. Liu, and S.-C. Zhu. Learning pose grammar to encode human body configuration for 3d pose estimation. In Proc. AAAI Conference Artificial Intelligence (AAAI), volume 32, 2018.
[9] Y. A. Farha and J. Gall. Ms-ten: Multi-stage temporal convolutional network for action segmentation. Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3575-3584, 2019.
[10] S.-H. Gao, Q. Han, 7.-Y. Li, P. Peng. I.. Wang, and M.-M. Cheng. Global2local: Efficient structure search for video action segmentation. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 16805-168 14, 2021. 2
[11] M. Guo, V. Thost, B. Li, P. Das, J. Chen, and W. Matusik. Data-efficient graph grammar learning for molecular generation. In Proc. International Conference Learning Representations (ICLR), 2021. 2
[12] Y. Hong, Q. Li, R. Gong, D. Ciao, S. Huang, and S.-C. Zhu. Smart: A situation model for algebra story problems via attributed grammar. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 13009- 2021. 2
[13] Y. Hong, Q. Li, S.-C. Zhu, and S. Huang. Vigrammar: Grounded grammar induction of vision and language. In Proc. IEEE International Conference on Computer Vision (ICCV), pages (665-1674, 2021.
[14] Hoperoft, Motwani, and J. Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60-65, 2001. 1, 2, 18

---

[15] Y. Huang, Y. Sugano, and Y. Sato. Improving action segmentation via graph- supp--bsed temporal reasoning. Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pages 14024-14033 2020. 1,2
[16] Y. Ishikawa, S. Kasai, Y. Aoki, and H. Kataoka. Alleviating over-segmentation errors by detecting action boundaries. In Proc. IEEE Winter Conference on Applications of Computer Vision (WACV), pages 2322-23333 2231, 2021. 1,2
[17] F. Jelinek, D. Lafferty, and L. Mercer. Basic methods of probabiliistic context free grammars. Springer, 1992. 3
[18] D. Jurafsky. Speech & language processing. Pearson Education India, 2000. 18
[19] S. Karaman, L. Seidenari, and A. Del Bimbo. Fast saliency based pooling of fisher encoded dense traeectories. In ECCV THUMOS Workshop, volume 1, page 5, 2014.
[20] Y. Kim. lequence-to-sequeee learning with latent neural grammars. Advances in Neural Information Processing Systems, 34:26302-26617,, 2021
[21] Y. Kim, C. Dyer, and M. Rush. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2369-2385, 2019,
[22] Y. Kim, M. Rush, L. Yu, A. Kuncoro, C. Dyer, and G. Melis. Unsupervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Pupers), pages 1105-1117, 2019. 2
[23] H. Kuchne, A. Arslan, and T. Serre. The language of actions: Recovering the syntax and semantics of goal-directed human activities. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 780-787, 2014. 2, 7, 9, 10, 18, 19
[24] H. Kuehne, A. Richard, and J. Gall. Weakly supervised learning of actions from transcripts. Computer Vision and Image Understanding, 163:78-89, 2017. 1,
[25] C. Lea, M. D. Flynn, R. Vidal, A. Reiter, and G. D. Hager. Temporal convolutional networks for action segmentation and detection. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 156-165, 2017. 1,2
[26] J. Li, P. Lei, and S. Todorovic. Weakly supervised energy- based learning for action segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019. 6
[27] Q. Li, S. Huang, Y. Hong, Y. Chen, Y. N. Wu, and S.-C. Zhu. Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In Proc. International Conference on Machine Learning (ICML), pages 1884-5894. PMLR, 2020.
[28] A. Piergiovanni, A. Angelova, and M. S. Ryoo. Differentiable grammars for videos. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 11874-11881, 2020. 2
[29] A. Piergiovanni, A. Angelova, A. Toshev, and M. S. Ryoo. Adversarial generative grammars for human activity prediction. In Prec. European Conference on Computer Vision (ECCV), pages 507-523. Springer, 2020. 2
[30] S. Qi, S. Huang, P. Wei, and S.-C. Zhu. Predicting human activities using stochastic grammar. In Proc. IEEE International Conference on Computer Vision (ICCV), pages 1164 1 1172, 2017.
[31] S. Qi, B. Jia, S. Huang, P. Wei, and S.-C. Zhu. A generalized earley parser for human activity parsing and prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence. 13(8):2538-2554 2020. 2,7, 15
[32] S. Qi B. Jia, and S.-C. Zhu. Generalized earley parser: Bridging symbolic grammars and sequence data for future prediction. Proc. International Conference on Machine Learning (ICML), pages 4171-4179, PMLR, 2018. 5,
12

---

[33] A. Richard, H. Kuehne, and J. Gall. Weakly supervised action learning with mn based fine- to-coarse modeling. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 754-763, 2017. 1,2
[34] A. Richard, H. Kuehne, and J. Gall. Action sets: Weakly supervised action segmentation without ordering constraints. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5987-5996, 2018.
[35] A. Richard, H. Kuehne, A. Iqbal, and J. Gall. Neuralnetwork--iterb::: A framework for weakly supervised video learning. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pages 7386-7395, 2018. 1, 6, 9, 10, 18, 19
[36] M. Rohrbach, S. Amin, M. Andriluka, and B. Schiele. A database for fine grained activity detection of cooking activities. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1194 1201. IEEE, 2012.
[37] Z. Solan, D. Horn, E. Ruppin, and S. Edelman. Unsupervised leaning of natural languages. Proceedings of the National Academy of Sciences, 102(33): 2005. 2, 3, 7, 8, 9, 10, 18
[38] Y. Souri, A. Farha, F. Despinoy, G. Francesca, and Gall. Fifa: Fast inference approximation for action segmentation. In Pattern Recognition: 43rd DAGM German Conference, DAGM GCPR 2021, Bonn, Germany, September -cttorober 1, 2021, Proceedings, pages 282-296.
Springer, 2022. 2
[39] S. Stein and S. McKenna. Combining embedded accelerometers with computer vision for recognizing food preparation activities. In Proceedings of the 2013 ACM international joint conference on Pervasive and ubiquitous computing, pages 729-738, 2013. 7, 19
[40] A. Vaswani, Shazeer, N. Parmar, Uszkoreit, L.. Jones, A. N. Gomez, Kaiser, and
I. Polosukhin. Attention is all you need. Proc. Neural Information Processing Systems (NeurIPS), 30, 2017.2 2
[41] N. N. Vo and A. F. Bobick. From stochastic grammar to bayes network: Probabilistic parsing of complex activity. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2641-2648, 2014. 2
[42] B. Wan, W. Han, Z. Zheng, and T. Tuytelaars. Unsupervised vision-language grammar induction with shared structure modeling. In Proc. International Conference Learning Representations (ICLR), 2021. 2
[43] Y. Xu, W. Wang, T. Liu, X. Liu, J. Xie, and S.-C. Zhu. Monocular 3d pose estimation via pose grammar and data augmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021. 2
[44] Z. Xu, Y. S. Rawat, Y. Wong, M. Kankanhalli, and M. Shah. Don't pour cereal into coffee: Dif- ferentiable temporal logic for temporal action segmentation. Advances in Neural Information Processing Systems (NeurIPS). 2
[45] F. Yi, H. Wen, and T. Jiang. Asformer: Transformer for action segmentation. In Proc. British Machine Vision Conference (BMVC), 2021. 1, 3, 5, 7, 8, 9, 10, 19
13

---

Appendices
In this supplement, we provide detailed descriptions of the proposed method and additional results, which are omitted in the main paper due to the lack of space. In Section A, we will describe the formulation of the probability of activity grammar. Algorithmic details of BEP is included in Section B. Section C compares KARI with the existing grammar induction algorithms for activity grammar and Section D presents additional qualitative results. We conclude this Appendix by discussing the broader impact of our research in Section E.
A Formulation of the probabilities in KARI
In this section, we describe the formulation of transition probability pl, and the escape probability Pa. and PM in Eq. and in Section A.1. In the following, the derivation of the expectation of the escape probability is described in Section A.2.
A.1 Formulation of the escape and transition probability
We first introduce and escape probabilities and the transition probabilities introduced in Eq. 5. Pre-processing. Let h. represent a list action sub-sequences, where the sub-sequence from h removes actions that does not exist in the action group d, from the action sub-sequence in DR, The empty string remains when the action sub-sequence does not include actions within the action group dfe For example in Fig. 2, a list of sub-sequences h can be structured as h = [pour milk], [spoon sugar, sugar, pour milk), [pour milk, spoon spoonsuugar) [spoon supoonssgar]]] with the corresponding action group dft {pour milk, spoon sugar). Similary, a list of sub-sequences h is structured as h [e,e, e, jstir coffee), [stir coffee]] with the action group di = [stir coffee). J. This me-processing step of generating h.? enables us consider the statistical probabilities associated with actions.
Formulation of the escape probability. The escape probability pf. and the transition probability př, are both defined based on the number of recursion ne of the current timestep; thereby these probabilities are represented as functions of n0 We first define the escape probability function:
E h a (a=e)) e]1
if nn =
Ple (o
(13)
otherwise,
where N is the average length of the sub-sequences in h. In the first recursion, i.e., n 1. the probability calculation solely considers statistics of the actions. Otherwise, the probability is calculated based the expected number of recursions, which will be introduced in Appendix A.2. In Fig. 2, p... (1) = 0, since none the action sub-sequence a from h is equal to the empty sequence, and yf, (ne 1) 3 since the average length of sub-strings in h is 1.5.
Formulation of the transition probability. The action sequence a = [a1, a2,-.., aN) represents the distinct action labels for the video segments, where a; # 0,41 described in Section 3. In order to prevent the repetition of the same action in Eq. 5, we introduce an additional input when defining the transition probability. Here, q refers the index of the actions selected by the rule in the previous step, specifically at fnc 1),, step where rec > 1. We simply put to 0 in the first recursion, i.e. n rec L, which does not affect the results. The transition probability pf, defined by:
01 = df,1 aa E h
in rec 1,
h
Pig (2
0
if rec
laddj
4,
(14)
Pl. (1,0) (1 pl. (n))))
otherwise.
E1eg (1,0)
The escape probability M and the transition probability M for the middle variable VM Eq. defined in the same way Eq. 13 and Eq. 14, respectively.
14

---

A.2 Derivation of the escape probability
We introduce the formulation of the escape probability p Appendix A.1. The escape probability is required to avoid an infinite loop of the rules and guarantee the length of sequences from the recursive rules in Eq. 5. Since the number of recursions directly determines the sequence lengths, we determine the escape probability regarding the length of action sequences. For notational simplicity, we denote the escape probabilities pf, by p. omitting superscripts and subseripts. The expectation of the number of recursions is calculated by:
p) (1-p) (1 p)" 1p(1 -p)")
(1-
lim
kp(1 p)*
lim 1-+30
(15)
p
1-
(16)
Since we derive the escape probability when n rec 1, the expected number of recursions is equal to N
1 P N 1 1,
(17)
where N the average length of action sequences. Finally, we obtain the escape probability by
1 p N
(18)
where this equation is used in Eq. 13 when n rec 1. The derivation of the escape probability P. of the middle variable V in Eq. 6 is also formulated as the same.
B
Breadth-first Earley Parser (BEP)
B.1
Earley parser
The Earley parser [7] is classic algorithm that efficiently parses strings for context-free grammar. It operates by maintaining a set states the parsing process. Each state consists a production rule, position within that rule, and position in the input string. The parser builds parse tree for the input string, which records the structure of parsing. The Earley parser is commonly used for natural language processing tasks, such syntactic analysis and semantic parsing.
The Earley parser consists of three main operations: scanning, prediction, and completion.
Scanning:
The parser matches terminal symbol in the input string with the current position in the production rule. This operation moves the parser forward in the input string.
Prediction: The parser expands variable in the production rule based on the current position. It adds new states to the set of states for possible future matches.
Completion: When the parser reaches the end the production rule, it searches for other states predicting the head variable of the current rule. Subsequently, the parser update the positions within the rule of the searched states.
By iterating these three operations, the Earley parser builds a parse chart that represents all possible parse trees for the input string.
B.2 Implementation details
The parsing probability p(Fi.t a G') (Eq. 9) can suffer from numerical underflow due to its exponential decrease as increases. To overcome the issue, we compute the probabilities in log- arithmic space, following [31]. For simplicity, denote log(p( F a alG)) Pv and
Log(p(F).tt - -1 G)) as P below:
P log(g(#)a1.N-))
PN-1,
(19)
max P
(20)
log(p(F + a G)) = log(Y,,)) + z + log(exp( PN - 2) + exp(Ply_1 - -2)).
(21)
15

---

8 + ABC
- A A2
A + 21 [0.7] x2 [0.3]
A2 + Aa A4 [0.5]
[0.5]
A3 + 24 A4 [0.5]
E [0.5]
A4 A3 00.5
[0.5
B + 26 [1.0]
C' 0.7] प7 [0.3]
Figure 6: Toy grammar used for the example of the BEP parsing
For the computational efficiency, we set the sampling stride of input matrix Y as 50 for Breakfast and 100 for 50Salads. Additionally, we set the maximum length of the refined action sequence as 20 for Breakfast and 25 for 50Salads.
B.3 Parsing algorithm
Algorithm shows the parsing procedure of BEP. We utilize priority queue that sorts the elements in ascending order. The currentSet stores multiple states with the same m, n, and d. See B.4 for the examples. BEP stops parsing when the probability of a has the highest probability compared to states the queue while ensuring the current state can reach depth with only completions.
B.4 Parsing example
In this section, we provide an example to help understand how BEP works. For simplicity, we assume that frame-wise class probabilities from the segmentation model are identical across all action classes. First of all, we define toy grammar as shown in Figure 6. In the context of grammar, S indicates the starting variable. A, B. C, and A, for i 2, 3, represent the variables. while zy for j = 21, 3, 4, 5, 7| represent terminals.
Table is the history of parsing with the toy grammar. It shows the currently popped state, the visiting order, the parsed prefix, the previous state, and which states are currently in the queue. The three consecutive numbers in the column pop. from, and queue indicate m, ni, and d of the state. The column represents the prefix probability excluding the frame-wise probability, which can be considered parsing probability since all frame-wise probabilities that the table includes some history after the parsed sequence satisfied the early stop constraint to illustrate how BEP prioritizes the states. Returning to the subject, the table shows BEP preferentially searches for states with a small depth. In order 14, even though the probability of state Q(1, 1, 3) is higher, BEP visits the state Q33, 0, 2) with lower depth.
assumed be the same. Note
16

---

Algorithm 1: Breadth-first Earley Parser (BEP)
Input: probability matrix Y, grammar G, queue size Nqueue
Output: Best parsed sequence a"
function Breadth-first Earley Parser
2 - priorityQueue()
// init priority queue set initial state 11 push initial state to queue
q.push(O, Q,, 0,000,0) 0) - (I' R. e(), 100;;
Q(0,0,)))
a' te;
// init
while (d. (p(a1:aa) 1). m. n, d1:aa-11: currentttet)) + g.pop() do for (r; Q(i k), p(p a...)) currenl.Sel
// update a' when a has higher probability
if p(a) p(a") then
a + a
10
end if
// prediction
11
if (A a- a-B3) then for each (B
12
D) in G do
r (B++I)
Q (r'QQ(m, d), a. a.p((a..))
@(m, n, + a). q.pushild + 1, (p(a..)) a, Qmm, n, d 1)))
15
end for
end if
// acanning
if is (A a x:3 then
19
r' - (A-+ (
n' Q' (r'.Q(i,j,k) a z, p((a p((a+))..)))
Q(m++)]
21
Q(m + +,,'', add(()
23
q.push(d, (p(a + I) I).. ,,,',d,
24
end if // completion
25
i is (B + r.) then for each ((A a. B3), Q(" p(aa..)) in kii,i,)) do
27
(A (A-aB) aB
(') a.),,,,,.....
29
Q(m, n. ()dd"d((")
q.push(d (p(a...) m, a, Q(m, 1)))
end for end if end for // early stop when has the highest probability and finished parsing if p(a")> > pppap(()f)) for all a' in q then a" has parsed then return a*
32
33
34
35
36
37
end if
38
end if
// Queue pruning
39
if
[g] Nqueue then
// sort in probability descending order sorted key p(a...), reverse Truee g.clear)
40
41
42
for i i Nqueee do q-push(g' (push(g'ppop()) pop()) end for
43
44
end if end while
47
return a"
end function
17

---

Table Parsing log for the given toy grammar through BEP.
pop
order
m
Y
d
rule
prefix
operation
from
P
queue
0
- S
ROOT
000
000
2
0
0
1
S + ABC
PRED
000
1
001
001
0
2
A + AA1A
PRED
001
002
0
0
3
A
+ -1
PRED
002
0.7
003
002
4
0
0
3
A > x2
PRED
002
0.3
5
1
0
3
A1 7 11' A + D22
SCAN
003
0.7
103, 113
003
19
1
1
3
SCAN
003
0.3
103
1
0
2
A - A1 A2
21
COMP
103
0.7
113, 102
102
7
1
0
3
A2 >
AgA4
21
PRED
102
0.35
103, 113
Ag +
21
PRED
102
0.35
0
4
Ag -
adA4
PRED
103
0.175
203, 113, 104
103
1
0
4
Ag e
21
PRED
103
0.175
3
A2 +
221
SCAN
103
0.35
203
9
2
0
2
A - A142-
COMP
203
0.35
202, 113, 104
202
2
0
1
+ A BC
211
COMP
202
0.35
201, 113, 104
201
11
2
0
2
B -
21
PRED
201
0.35
202, 113, 104
202
12
3
0
2
B + N6'
3i 36
SCAN
202
0.35
302, 113, 104
302
3
0
AB-C
31 37
COMP
302
0.35
301, 113, 104
301
3
0
2
C ->
JTS
PRED
301
0.245
302, 113, 104
3
0
2
C - :27
PRED
301
0.105
302
15
4
0
2
C + 216'
I1 275 376
SCAN
302
0,245
402, 412, 113, 104
17
4
1
2
C - 27'
27
SCAN
302
0.105
402
4
0
1
S + ABC-
21 26 276
COMP
402
0.245
401, 412, 113, 104
401
r S.
25 266
COMP
401
0.245
412, 113, 104
412
18
4
1
I
S + ABC-
I1 276 377
COMP
412
0.105
411, 113, 104
411
T S.
I1 26 27
COMP
411
0.105
113, 104
113
1 2 A - A A
COMP
113
0.3
112, 104
C
Comparison with the existing grammar induction algorithms
C.1
Existing grammar induction algorithms
Kuehne el al. [23] introduce a hierarchical context-free grammar induction algorithm. The root rule with the starting variable S is induced as S - Vi V22 .... VNA, where the variable V; represents single activity and NÅ is the number of activities from the dataset. Then each V; expands into action sequences from each activity, i.e. the rule is formed as: V- + Ar, A ... |A, where A, is set of action sequences from the i-th activity and each A.,, represents j-th action sequence in A,.
Richard et al. [35] propose a grammar induction method for probabilistic right-regular grammar, where every rule has the form of H c H. The algorithm is motivated by n-gram models [18] and finite grammars [14]. Specifically, the variable H represents action sequence d H represents an action sequence a1n-1. and a terminal is an action class of an The induced grammar can express the intermediate action sequences a1:. and expands its rules based on the sequential order of actions.
Recently, Qier al. [32] adopt the Automatic Distillation of Structure (ADIOS) [37] algorithm to induce a probabilistic context-free grammar. The ADIOS algorithm finds the significant patterns (AND rules) and equivalence action classes (OR rules) from the given action sequences. The algorithm identifies repetitive patterns in action sequences to minimize redundant sequences and find potential candidates for generalized action classes. Following the grammar induction methods of ADIOS,
18

---

Table 10: The performance comparison with other gramiaa induction algorithms on two benchmark datasets.
dataset
reprod.
refinement
grammar induction
edit
@0 25
F1 50
76.5
83.8
81.7
74.8
86,1
Kuehne al. [23]
62.9
73.0
70.6
63.0
78.6
50Salads [39]
Richard et [3553
63.1
73.1
70.5
62.9
78.7
ADIOS-AND
58.3
68.0
59.4
76.2
ADIOS-OR
61.1
72.0
70.1
62.4
78.9
KARI
79.9
85.4
83.8
77.4
85.3
75.6
77.3
72.0
59.4
74.3
Kuehne [23]
72.8
74.0
69.1
55.5
72.9
Breakfast [23]
Richard et al. [l.[35]
77.3
77.2
72.2
74.1
ADIOS-AMI ANDD
69.2
69.8
64,9
52.2
72.4
ADIOS-OR
70.3
71.8
66.8
54.2
71.8
KARI
77.8
78.8
73.7
60.8
74.0
set decreasing ratio of the motif extraction algorithm 1 to I, significance level for the decrease ratio y to 0. and the context window size I for ADIOS-AND AND-induced grammar. For ADIOS-OR- OR-induced grammar; we set to 0.9, y to 0.1, and the context window size to 4.
However, none of these approaches have managed to effectively integrate recursive rules, which are crucial for representing intricate and lifelike structures action phrases and activities. The proposed KARI algorithm introduces probabilistic context-free grammar that allows for the expression of complex activity structures, which captures a distinctive temporal structure based on key actions.
C.2 Performance on temporal action segmentation
In Table 10, compare the performance of each grammar induction algorithm refining tem- poral action segmentation models [45]. The overall results show that the KARI-induced grammar demonstrates the best refinement performance compared to the other grammar induction algorithms, showing a significant performance gap in both datasets. The induced grammar of Richard el al.also shows better performance than other grammar induction algorithms except for KARI, indicating that the ability to represent intermediate action sequences by production rules helps improve re- finement performance. In conclusion, the generalization capabilities and variability of expressing action sequences are essential to guide the temporal action segmentation network to better refinement results.
D Qualitative results
We provide additional qualitative results for the Breakfast and 50Salads. Figure shows examples of successful output refinements by the KARI-induced grammar, demonstrating its ability to cover various sequences comprising combinations of multiple actions. This is further evident in Figure 7a, where ADIOS-OR falls short in covering the 'add dressing' action following the 'serve salad' action, while KARI handles proficiently.
We also show failure cases of the KARI-induced grammar in Figure 8, where further improvement is needed. We acknowledge that the KARI-induced grammar sometimes deletes certain actions. This deletion of actions, along with the challenges posed by inaccurate identification of actions by the segmentation model, show areas for improvement in the refinement process. We recognize these as opportunities for future work to enhance the performance of the grammar induction algorithm and address these limitations.
E
Broader Impact
The research presented this paper holds significant potential for impact across multiple domains. The development of efficient and effective grammar induction algorithms for activity grammar, coupled with the Breadth-first Earley parser, has the potential to greatly enhance human activity recognition and understanding systems. This, in turn, have far-reaching implications in various
19

---

ASFermet
ADIOS-OR
(Ours)
oction start
out lottuce
place letuace
tomato
place tomatto
pesi cucumber
cut cucumber
glace cocumber
cheree
place choose
mix ingrodients
add
adi
add
adé
drowing
asM drowing
salad
(a) 50Salads
GT
ASForee
ADIOS-OR
KARI (Ours)
pour
Breakfast (activity: cercals)
ASFommt
ADIOS-OR
(Ouns)
SII
take rap
xid Jumbag
pour woter
(c) Breakfast (activity: tea)
Figure 7: Qualitative results on successful cases
20

---

ASFormer
AD10S-OR
(0ums)
action startlnd
add papper
zád salt
add odl
add vinegar mit dresting
cut choose
cut lettuce
peel
cucumber kowl
odk dressing
mix Lngnddent
serv saled onlo plate
place lelluce into bowl
cut oacumber
(a) 50Salads
A.Fommer
ADIOS-OR
KARI (Ous)
SIL
pour
crack
saltapepper
bake put roc2plate
(b) Breakfast (activity: scrambled egg)
Figure Qualitative results on failure cases
applications, such video surveillance, human-computer interaction, roboties, and healthcare monitoring. By improving the accuracy and efficiency of activity recognition systems, our research contributes to advancements in these domains, enabling more robust and intelligent systems. The broader implications of this research extend beyond activity grammar induction itself, fostering innovation and enhancing the capabilities of intelligent systems in diverse fields.
21


Reviews:
[{"review_id": "wdDNkidtpd", "reviewer": "Reviewer_YXrU", "summary": "This paper presents a grammar induction algorithm that takes as input sequences of frame-level predictions and outputs structured sequences of actions. The advantage of their approach is that it allows recursive rules, which enhances its generalization abilities.", "questions": "- Would it be possible to combine this approach to perform end-to-end training with the frame-level predictions Y? This is, train the grammar and the temporal action segmentation network simultaneously.\n\n- Accuracy does not improve when using grammars (it actually decreases). Why is that the case? I would assume that having contextual grammatical information about future and past actions would improve the accuracy of the current action prediction. Do you think the accuracy would improve with a flexible/good enough grammar, or this is a limitation of using action grammars?", "limitations": "Limitations and broader impact are discussed in the appendix.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The method is more flexible than previously proposed grammar induction methods. \n2. The results are better compared to baselines.\n3. All the steps are explained in detail and most of them are well justified.", "weaknesses": "1. The grammar explanation (section 3.2) is confusing. Especially the large amount of superindices and subindices representing different concepts. For example, what does E^{M(m,n)} mean? Or, in \"t \\in {b, a, k(m, n)}\" what does the \"b\" represent? Probably simpler notation or a figure would help. I also did not understand what \"each sub-string a_i^M starts with a key action and includes all the key actions in K\" means. Do you start at a key action and do not close the sub-string until all key actions have been found? But then, I assume there will only be one such sub-string in the whole sequence. Is there any overlap between sub-string? Is it possible that a sequence does not contain any key action?\n\n2. I do not think the synthetic activity grammars are a good setting to judge the quality of the proposed approach. Without delving into the details of the generated random grammars, it is unclear whether the biases introduced in the generation may make them easier to deal with for some kinds of methods than others. Real-world grammars do not have that problem. \n\n3. There are no results showing the importance of the specific contribution. Did the authors identify cases where the inclusion of recursive rules made a difference?\n\nMinor weakness: a few typos and grammar mistakes: \"due to the reason\" -> \"due to this reason\" (lines 4, 22), \"and also be applied\" -> \"and can also be applied\" (line 29), \"we proceeds\" (line 137), \"has\" -> \"have\" (line 70), \"other researches\" (line 74), a few empty citations (lines 109, 119), etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer YXrU for constructive comments and suggestions.\n\nWe will clearly revise Section 3.2 using simpler notations and more illustrations. \n\n### **[Grammar illustration]**\nFollowing the suggestion, we created Figure R1 with example sequences and KARI-induced grammar for a better understanding. We also provide the induction example in Section A.3 of the supplementary material.\nIn Figure R1-(a), we give an example sequence of $\\boldsymbol{a}$ of the 'milk' activity, where 'spoon powder' and 'pour milk' are the key actions, and visualize how the sequences are divided into sub-strings according to the key actions.\nFigure R1-(b) presents the KARI-induced grammar from $\\boldsymbol{a}$.\n\n### **[Partitioning strategy for sub-string $\\boldsymbol{a}^\\mathrm{M}_i$]**\nIn lines 143-144, the statement, \"each sub-string $\\boldsymbol{a}_i^\\mathrm{M}$ starts with a key action and includes all the key actions in $\\mathcal{K}$,\" indicates that the sub-string $\\boldsymbol{a}_i^\\mathrm{M}$ should include all of the key actions existed in the activity. \nIn the example in Figure R1-(a), the middle sequence $\\boldsymbol{a}^\\mathrm{M}$ is further divided into two distinct sub-strings, denoted as $\\boldsymbol{a}^\\mathrm{M}_1$ and $\\boldsymbol{a}^\\mathrm{M}_2$; \n$\\boldsymbol{a}^\\mathrm{M}_1$ consists of ['spoon powder', 'stir milk', 'pour milk', 'stir milk'] and $\\boldsymbol{a}^\\mathrm{M}_2$ comprises ['pour milk', 'spoon powder', 'pour milk'].\nEach sub-string starts with a key action, extends until all key actions of the activity have been included, and ends before the key action of the next sub-strings begins. As can be seen in this example, multiple sub-strings, i.e., $\\boldsymbol{a}^\\mathrm{M}_1$ and $\\boldsymbol{a}^\\mathrm{M}_2$, that contain the entire key actions, can exist in a single sequence $\\boldsymbol{a}$. \n\n### **[Middle variable $E^{\\mathrm{M}(m,n)}$]**\nIn line 156, $E^{\\mathrm{M}(m,n)}$ indicates a variable for the rule that covers an action sub-string between the $n_\\mathrm{th}$ key action and the $n+1_\\mathrm{th}$ key action when the $m_\\mathrm{th}$ permutation $\\pi_m$ is applied to key actions. \nSince the temporal order between key actions can vary, we introduce the concept of key action permutations $\\Pi^\\mathrm{M}$ (line 146). \nIn the example of Figure R1 with two key actions of 'pour milk' and 'spoon powder', there exist two possible permutations: $\\pi_1=$ ['pour milk', 'spoon powder'] and $\\pi_2=$ ['spoon powder', pour milk'], where $\\Pi^\\mathrm{M}=\\{\\pi_1, \\pi_2\\}$.\nThe rule of $E^\\mathrm{M(1,1)}$ thus has 'stir milk' as a body part. \nThis action occurs between 'spoon powder' and 'pour milk,' i.e., the first action of $\\pi_1$ and the second action of $\\pi_1$.\n\n### **[Action sequences without key actions]**\nIt is possible to extract grammar from the sequences without any key actions by simply putting the entire action sequence $\\boldsymbol{a}$ into $\\boldsymbol{a}^\\mathrm{L}$.  \n\n### **[Evaluation on synthetic \\& real dataset]**\nWe generated synthetic activity grammars based on the properties of real-world action sequences, which can be observed from existing activity datasets [20, 36]. The procedure for grammar generation can be summarized as follows. We randomly select one to five key actions among 20 terminal elements and randomly determine the number of variables. For production rules, we assign each terminal to variables in a random manner (lines 275-279) and generate rules by randomly compositing them with 'OR' and 'AND'. \n\nIn addition, we also conducted experiments using grammars without any key actions; 50 synthetic grammars are generated and evaluated with the same procedure in the main paper. As shown in the table below, the KARI-induced grammar shows powerful generalization performance compared to ADIOS-induced grammar, while precision is comparable with others. We also visualize the confusion matrix in Figure R2 for better understanding. \n\n|grammar|precision|recall|\n|---|---|---|\n|ADIOS-AND|1.00|0.09|\n|ADIOS-OR|1.00|0.60|\n|KARI (ours)|0.84|1.00|\n   \nWhile the analyses with diverse synthetic grammars demonstrate the efficacy of KARI, we agree with the reviewer's concern that synthetic activity grammar may introduce some biases that are different from real-world activity grammars. Note that we thus also did evaluate the grammar induction algorithms on the real-world dataset, as shown in Table S2 of the supplementary material. \n\n### **[Ablation study on KARI]**\nPlease refer to the general response for the ablation study on KARI.\n\n### **[End-to-end learning with KARI]**\nIn this paper, the proposed method is applied to the pre-trained models without fine-tuning. \nSince we do not incorporate grammar into the models in training, end-to-end training is currently unavailable. \nHowever, we believe that a learnable version of KARI would make it possible to be trained with the neural network regarding the previous work [25, 26], and we leave it as future work.\n\n### **[Accuracy drop]**\nTo analyze the slight decrease in accuracy while significantly increasing edit and F1 scores, we conduct a case study. \nWe present the quantitative and qualitative results of a single sample in Figure R4 and the table below:\n|model|acc|edit|F1@10|F1@25|F1@50|\n|---|---|---|---|---|---|\n|ASFormer[42]|91.87|85.71|85.0|85.0|77.5|\n|Ours|90.86(1.01$\\downarrow$)|100.0(14.29$\\uparrow$)|95.78(10.28$\\uparrow$)|95.78(10.28$\\uparrow$)|87.32(9.82$\\uparrow$)|\n\nFrom the red box drawn in Figure R4, we observe that this discrepancy seems to be caused by adjusting the boundary between actions based on the segmentation output. \nFuture improvements could be achieved by adding boundary regression modules [15] or other comparable methods.\n\n### **[Typos and empty citations]**\nIn line 160, $t\\in\\{\\mathrm{b}, \\mathrm{a}, \\mathrm{}(m,n)\\}$ should be revised to $t\\in\\{\\mathrm{L}, \\mathrm{R}, \\mathrm{M}(m,n)\\}$ which indicates a set of superscripts of notations. \n\nWe will add citations of [A1] in line 109 and [A2] in line 119.\n"}, {"review_id": "AVaa7dGsA7", "reviewer": "Reviewer_CeJ9", "summary": "This paper addresses the challenge of temporal action segmentation by introducing an activity grammar to guide neural predictions. The proposed approach involves a grammar induction algorithm (KARI) to extract a powerful context-free grammar from action sequence data. Additionally, an efficient generalized parser (BEP) transforms frame-level probabilities into a reliable sequence of actions based on the induced grammar. Experimental results on benchmark datasets show significant improvements in both performance and interpretability of temporal action segmentation.", "questions": "Is the proposed method limited by the action type? For example, it could only work for well-structured activities. ", "limitations": "as is mentioned in previous sections.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is well written which demonstrates its motivation, methodology and experiments. Especially, the method of this paper is easy to follow and the provided visualization is a plus to understand the proposed algorithm.\n\nThe idea of introducing the recursive rules is inspiring, which helps to identify the repetitions of actions and action phrases.  \n\nThe proposed grammar evaluation scheme demonstrates the effectiveness of the proposed KARI-induced activity grammar, achieving good recall while maintaining reasonable precision.\n\nThe experimental results look promising, achieving good performance on various benchmarks.\n", "weaknesses": "The benchmark is relatively small, which generates concerns about the scalability of the proposed method. Also, it’s good to know the computational cost of the proposed method to evaluate its scalability. \n\nThe design of the proposed KARI is not well justified by using ablation study. It will be good to show the effectiveness of each component and its alternatives.\n\nMinor:\n\nMissing reference for ln 109 and 119.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer CeJ9 for their meaningful comments and suggestions.\n\n### **[Scalability and computation cost of the proposed method]**\n\nFollowing the reviewer's suggestion, we analyze the computational cost of the KARI and BEP. \nSince KARI induces activity grammars based on the activity sequences in the dataset, the time consumption is directly affected by the number of sequences. The Breakfast dataset includes 196 unique action sequences from 1,712 video sequences. \n\nFigure R3-(a) shows the running time plot when gradually increasing the dataset from 40\\% to 100\\%, where we can empirically estimate linear running time with respect to the dataset size; it takes less than 0.1 seconds to induce grammar from the entire activity sequences in our implementation.\nFigure R3-(b) shows a similar plot when varying the number of sequences from 200 to 1,000.\nThese results indicate that KARI has reasonable scalability so that it can be applied to large-scale datasets.\n\nThe computational cost of BEP depends on the complexity of the grammar $G$ generated from the induction algorithm. \nRegarding BEP, the time complexity of computing the parsing probability for each sequence is $O(T)$ [29] where $T$ denotes the number of frames, resulting in a worst-case time complexity for the entire parsing process becomes $O(T|G|)$.\n\n### **[Ablation study on KARI]**\n\nPlease refer to the general response for the ablation study on KARI.\n\n### **[Limited to well-structured activities?]**\n\nKARI induces an activity grammar by analyzing action sequences using flexible temporal dependencies across actions; it uses OR rules for temporally equivalent actions and AND rules for dependent actions. It does not require specific activity structures in action sequences, showing impressive generalization to real-world data (Table S2) as well as random synthetic data (Table 1). \n\n### **[Missing reference]**\n\nThanks for letting us know. We will add citations of [A1] in line 109 and [A2] in line 119.\n"}, {"review_id": "lt4qZXNtJL", "reviewer": "Reviewer_FXdk", "summary": "This paper proposes a new grammar induction algorithm, an effective parser, and a grammar evaluation framework. They improve temporal action segmentation by extracting and handling context-free grammar with recursive rules. The assessment presents good generalization and discrimination capabilities of induced grammar. \n\nAfter reading the rebuttal, my concern about the second and third points are resolved. For the first point, the authors provide the SOTA table as requested. However, the performance of the proposed method is not convincing.\n\nOverall, given that this paper introduces a new framework for temporal action segmentation, I still consider the pros outweigh the cons and will keep my initial recommendation.", "questions": "See weaknesses. \n\nIn the first row of Section 3.1, the citation is missing.", "limitations": "Limitations are not discussed in the paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. KARI proposes a new grammar induction algorithm, an effective parser, and a grammar evaluation framework. They improve temporal action segmentation by extracting and handling context-free grammar with recursive rules. The assessment presents good generalization and discrimination capabilities of induced grammar. \n\n2. KARI outperforms state-of-the-art models on two benchmarks, Breakfast, and 50 Salads, for the temporal action segmentation task.\n\n3. The writing is good.", "weaknesses": "1. The evaluation of MIF is based on breakfast and 50salads. Can the author provide results on more benchmarks? The SOTA table is missing in the paper.\n2. The method is relatively new, but the details are mostly presented in the form of text. Some illustrations for the method's visual representation are missing. I think this is very beneficial to readers' understanding and the dissemination of the paper.\n3. For the first row of MS-TCN results in Table 2, is better than KARI, but the author did not bold it. Also, the author should give an explanation why KARI doesn't work here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer FXdk for constructive comments.\n\n### **[Comparison with SOTA]**\nFollowing the reviewer's suggestion, we compare ours with the state-of-the-art methods in Table R3 where ours shows comparable or superior performance. Note that most of the refinement methods [A3, 9, A5, 5, A6, 15, 41] typically fine-tune their underlying temporal action segmentation models, whereas our method does not require such fine-tuning, thus being able to apply to any black-box temporal action segmentation models. The breakfast and 50salads benchmarks are the two most standard benchmarks for action segmentation. We will add more experiments to the final manuscript using another benchmark. \n\n### **[Grammar illustration]**\nFollowing the suggestion, we created Figure R1 with example sequences and KARI-induced grammar for a better understanding. We also provide the induction example in Section A.3 of the supplementary material.\nIn Figure R1-(a), we give an example sequence of $\\boldsymbol{a}$ of the 'milk' activity, where 'spoon powder' and 'pour milk' are the key actions, and visualize how the sequences are divided into sub-strings according to the key actions.\nFigure R1-(b) presents the KARI-induced grammar from $\\boldsymbol{a}$.\n\n### **[MS-TCN results in Table 2]**\nLet us clarify that KARI works on MS-TCN in Table 2. \nThe first row of each compartment indicates the performance of the original paper. \nWe apply the proposed methods to the reproduced models, as the pre-trained model of MS-TCN is not open-sourced. \nTherefore, we compare the performance of the proposed methods with the reproduced performance in the second row of each compartment, similar to the previous work [1, 14, 41]. "}, {"review_id": "QlXOEtvgBE", "reviewer": "Reviewer_rBwB", "summary": "This paper proposes a grammar-based activity segmentation method. The authors proposed a grammar induction algorithm, as well as an improvement over the existing activity grammar parser, the Generalized Earley Parser (GEP). The proposed model shows improvements over prior works on both grammar induction and action segmentation.", "questions": "See weakness section", "limitations": "The authors have properly addressed the limitations.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The exploration of marrying neural-symbolic representations is an essential aspect of research, especially given the limited application of neural-symbolic methods for real-world problems.\n\n- The proposed grammar induction method does improve existing prior works and could potentially be beneficial for future research.", "weaknesses": "- The experiments on activity segmentation are mainly compared with baselines that are not state-of-the-art. Though the ablations prove the improvement in grammar induction and parsing, the overall performance can not be justified by the current experiments (i.e., might need better results to justify the motivation of grammar-based activity understanding methods).\n\n- Another concern is the design of grammar. Given recent advances in language modeling and unsupervised grammar induction, the motivation of symbolic methods is not very clear or not shown by the experiments.\n\n- The overall formulation and algorithm design for the BEP follows from the GEP parser.\n\n- The notation used in this paper is error-prone and needs to be clearer, especially given that the grammar-based method largely depends on these notations. (e.g. L.146, should it be $a_i^{M}$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer rBwB for their meaningful comments.\n\n### **[Comparison with SOTA]**\nFollowing the reviewer's suggestion, we compare ours with the state-of-the-art methods in Table R3 where ours shows comparable or superior performance. Note that most of the refinement methods [A3, 9, A5, 5, A6, 15, 41] typically fine-tune their underlying temporal action segmentation models, whereas our method does not require such fine-tuning, thus being able to apply to any black-box temporal action segmentation models. The breakfast and 50salads benchmarks are the two most standard benchmarks for action segmentation. We will add more experiments to the final manuscript using another benchmark. \n\n### **[Motivation of our approach]**\n\nSimilar to other neuro-symbolic approaches [A7], our grammar-based method facilitates an explainable output using its grammar structure, improving the generalization performance to unseen action sequences, which we have demonstrated in Tables 2-3, Figure 4, Table S1, and Figure S3.\n\nFurthermore, combining a symbolic approach with neural networks can also increase robustness and reliability [A8]. In our case, the induced grammar is used to improve the noisy output of a temporal action segmentation network. To better see the effect, we conduct experiments in Table R2 using the ASFormer that performs multiple refinement stages in decoding [8, 42]; as shown in the first compartment of Table R2, the performance of the lower decoding stages shows lower performance. \nThe second compartment of Table R2 \nshows the results of applying our method to each stage of the decoder in ASFormer.\nIt reveals that our grammar-based refinement brings more significant improvement when initial action segmentation is from lower stages, i.e., less accurate.\n\n### **[Effectiveness of BEP over GEP]**\nWhile both BEP and GEP are based on the Earley parser, they exhibit differences in their search algorithms. \nIn detail, BEP and GEP have distinct orders for exploring production rules, leading to differences in the searching space as we applied pruning techniques to BEP. For better understanding, we explain how the depth-based priority works during the parsing through the example in Table S1 and Section B.4 of the supplementary material. \n\nIn addition, the motivation of BEP stems from the fact that GEP was unable to parse the CFG generated through KARI within a reasonable time (lines 175-177). \nTo address the challenge, we have introduced additional pruning techniques and confirmed that the searching algorithm proposed in BEP was more effective (Table 4), prompting us to adopt it as the preferred solution.\n\n### **[Clarification on KARI]**\nThanks for the correction. $\\boldsymbol{a}^\\mathrm{M_i}$ should be revised to $\\boldsymbol{a}_i^\\mathrm{M}$ in line 146. We will try our best to clarify notations and explanations in the final version of our paper."}]

Author rebuttal:
We thank all the reviewers for their insightful comments and suggestions. 
We are happy to see that the reviewers have given our work a positive evaluation, noting that "the method is more flexible than previously proposed grammar induction methods (YXrU)," "the idea of introducing the recursive rules is inspiring (CeJ9)," "the assessment presents good generalization and discrimination capabilities(FXdk)," and "the proposed grammar induction method does improve existing prior works and could potentially be beneficial for future research(rBwB)."

Nevertheless, the reviewers also point out important comments that:

1. the explanation of grammar induction can be improved for clarity with illustrations,
2. the grammar induction algorithm requires ablation study,
3. comparison with the state of the arts needs to be added,
4. motivation for the proposed method needs to be clarified.

Through this rebuttal, we aim to clearly expound the components of KARI and their respective roles, compare the proposed method with the state-of-the-art models, and explain the motivation of our approach. 
We will revise the manuscript by incorporating the detailed comments from the reviewers.
We include Figures R1-R4 and Tables R1-R3 for additional results in the pdf files.

In response to the questions posed by reviewers YXrU and CeJ9 regarding the ablation study of KARI, the results are included in the general response.

### **[Ablation study on KARI]**
We conduct an ablation study to evaluate the two main components of KARI, key action extraction and recursive rule generation. The results are shown in Table R1, which demonstrates the effectiveness of both components. 
In particular, eliminating recursive rules (third row in Table R1) significantly decreases the overall performance. We will add these results to our final manuscript. 


### **[References]**

[A1] J. Frederick et al. Basic methods of probabilistic context free grammars. Springer Berlin Heidelberg 1992.

[A2] D. Klein and CD. Manning. A generative constituent-context model for improved grammar induction. ACL 2002.

[A3] D. Wang et al. Temporal relational modeling with self-supervision for action segmentation. AAAI Conference on Artificial Intelligence. 2021.

[A4] S.J. Li et al. MS-TCN++: Multi-stage temporal convolutional network for action segmentation. TPAMI 2020.

[A5] Z. Wang et al. Boundary-aware cascade networks for temporal action segmentation. ECCV 2020.

[A6] D. Singhania et al. Coarse to fine multi-resolution temporal convolutional network. arXiv. 2021.

[A7] P. Hitzler et al. Neuro-symbolic approaches in artificial intelligence, National Science Review. Volume 9, Issue 6. 2022.

[A8] R. Evans and E. Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research 61 (2018): 1-64.

Meta-review: This paper received four unanimous borderline accept recommendations. The reviewers generally appreciated the direction of the paper and acknowledged the empirical performance improvement over the baselines. However, there were several concerns about the adequacy of the experiments, such as the absence of ablation studies demonstrating the importance of the specific contributions (recursive rules and symbolic method), the focus on synthetic data instead of real data, the lack of evaluation on larger datasets, and the absence of a comparison with state-of-the-art approaches. The rebuttal provided additional results that addressed most of these concerns. The only remaining concern pertains to the absence of results on large-scale benchmarks, as raised by `FXdk`. This meta-reviewer recognizes this concern but also understands that conducting large-scale experiments may be challenging without access to substantial computational resources.

Overall, this meta-reviewer finds the main idea presented in the paper to be inspiring and experiments to be convincing to justify the claims made in the paper. The only remaining concern is the small-scale nature of the experiments, which puts the scalability of the approach in question. However, the rebuttal provided evidence showing the scalability (as shown in response to `CeJ9`). Given this, we recommend acceptance.
Decision: Accept (poster)