#  Tragedy Plus Time: Capturing Unintended Human Activities from
Weakly-labeled Videos

Arnav Chakravarthy, Zhiyuan Fang, Yezhou Yang
Arizona State University
<EMAIL_ADDRESS><EMAIL_ADDRESS>yz.yang @asu.edu

###### Abstract

In videos that contain actions performed unintentionally, agents do not
achieve their desired goals. In such videos, it is challenging for computer
vision systems to understand high-level concepts such as goal-directed
behavior, an ability present in humans from a very early age. Inculcating this
ability in artificially intelligent agents would make them better social
learners by allowing them to evaluate human action under a teleological lens.
To validate this ability of deep learning models to perform this task, we
curate the W-Oops dataset, built upon the Oops dataset [15]. W-Oops consists
of 2,100 unintentional human action videos, with 44 goal-directed and 30
unintentional video-level activity labels collected through human annotations.
Due to the expensive segment annotation procedure, we propose a weakly
supervised algorithm for localizing the goal-directed as well as unintentional
temporal regions in the video leveraging solely video-level labels. In
particular, we employ an attention mechanism based strategy that predicts the
temporal regions which contributes the most to a classification task.
Meanwhile, our designed overlap regularization allows the model to focus on
distinct portions of the video for inferring the goal-directed and
unintentional activity, while guaranteeing their temporal ordering. Extensive
quantitative experiments verify the validity of our localization method. We
further conduct a video captioning experiment which demonstrates that the
proposed localization module does indeed assist teleological action
understanding. Project website can be found at: https://asu-
apg.github.io/TragedyPlusTime.

###### Abstract

This document provides additional details and further analysis of our model
architecture. We start by providing detailed statistics about the W-Oops
dataset in Sec. 6. We further analyse the dependence of unintentional actions
on goal-directed actions in Sec 7. We then give more details on the choice of
our backbone features and experimenting with human-pose features in Sec. 8 .
We further analyse the video embedding module by removing it
entirely/replacing it with a Transformer Encoder [64] in Sec. 9. We study the
effect of different selections of $\lambda$, the hyperparameter that controls
the trade-off between our losses in Sec. 10. Details into the 3D-CNN feature
extraction is provided in Sec. 11. Finally, we explain more about our
annotation tool in Sec. 12, and provide additional qualitative results for the
localization and captioning experiments in Sec. 13 and Sec. 14.

##  1 Introduction

Figure 1:  State-of-the-art action recognition models trained on traditional
video activity datasets view an unintentional action scene as an atomic
action. Although this scene involves a man falling on his face, the man’s
ultimate goal was to hit the ball. Green lines indicate the regions of the
video which indicate the man’s goal, red lines indicate the regions where the
action deviates from the goal, and purple lines indicate the region the action
recognition model focuses on.

Traditional video action recognition [26, 12, 69, 82, 35, 6, 60] focuses on
predicting only atomic actions present on the surface appearance of a video.
On the other hand, teleological understanding of actions entails understanding
the underlying goal of actions and why it was performed. These goals can be
easily inferred from intentional actions as they are directly defined by their
outcome. However, many actions do end up in unintended results where the goal
of the action is partially or never achieved. As shown in Fig. 1, an agent
tries to hit the ball with a bat, but ends up landing on his face, hence not
being able to achieve his goal of hitting the ball. State-of-the-art action
recognition models are all trained with vewing the whole scene as “faceplant”
without paying attention to the goal-directed behavior which was to “hit the
ball”.

Teleological action understanding provides the invaluable ability to explain
and justify an action, as well as learn from mistakes in the case the goal was
not achieved [10]. For fine-grained understanding of unintentional actions, it
is important to know the goal of the action, why was it not fulfilled, and
when (in time) did the action start transitioning away from its goal. These
abilities are present in humans from a very early age [2, 55, 73, 23, 9].
However, this is a challenging task for deep learning models since it requires
the model to understand high level concepts such as goal-directed behavior
from unintentional actions which would not be possible without penetrating
deeper than the surface appearance of the action [2]. There are few previous
works which have taken initial steps towards teleological action
understanding. [15] builds a dataset rich in unintentional human actions,
along with single point transition times manually labeled by human annotators
which separate the intentional and unintentional regions of the video. They
also train models on classification and localization tasks. However, it does
not contain well defined classes for the goal-directed action or why this goal
gets disrupted. [58] focuses on predicting whether an activity was intentional
or unintentional, but not the understanding of the underlying goal of an
unintentional action. Previous efforts [16, 32, 77] have tried to speculate
about all possible effects of actions but do not explore which effects are
undesirable.

In order to build a model which is capable of capturing the unintended
activity, it is crucial to first build a dataset containing goal-directed
actions and why they get disrupted Additionally, in order to localize their
respective regions in time, one may manually label the transition point as in
[15] and fully supervise the training. However, these annotations are
prohibitively expensive to collect and suffer from human error and bias.
Previous works such as [43, 41, 50, 79, 36, 44, 31], which focus on segmenting
atomic action scenes from untrimmed videos tackle this problem of expensive
manual labelling by training a model in a weakly supervised manner using only
video level action labels. Though this task differs from our task (which
involves separating the goal-directed action from the region it starts
deviating from its goal), it still provides encouragement to solve our task in
a weakly supervised manner.

We bring Weakly Augmented Oops (W-Oops), an augmented human activities dataset
which contains “fail” videos, building upon Oops [15] but also contains high
quality video-level annotations which describe the goal-directed as well as
unintentional actions in the video. We further develop an algorithm which
allows the model to attend to contextualized visual cues to localize these
regions as well as associate them with their respective goal-
directed/unintentional class label, leveraging solely video-level labels. Our
proposed learning schema includes an encoder to encode the joint
representation of the goal-directed and unintentional action in the video as
well as temporal attention modules which help the model focus on the
respective regions of interest in the video. We also introduce a novel
optimization target known as Overlap Regularization which allows the model to
pay attention to distinct parts of the video for inferring both types of
actions while ensuring their temporal ordering. Finally, we use class-agnostic
(bottom-up) as well as class-specific (top-down) attention mechanisms to
localize both types of actions. Additionally, we conduct a video captioning
experiment leveraging our localization module to demonstrate it’s teleological
ablity.

To summarize our contributions:

  1. 1.

We curate W-Oops, an augmented video dataset, built upon Oops [15], containing
high quality video level labels for the goal-directed as well as unintentional
action. To the best of our knowledge, we are the first to make a step towards
such fine-grained understanding of unintentional actions.

  2. 2.

We propose an attention mechanism based method that highlights relevant
temporal regions of the video important to a classification task when
inferring the goal-directed and unintentional action while also ensuring their
temporal ordering.

  3. 3.

Finally, we provide in-depth and comprehensive experimental analysis, which
validates the effectiveness of our method compared to competitive weakly
supervised action localization methods on W-Oops. Additionally, we demonstrate
the teleological ability of our localization module through a video captioning
experiment.

##  2 Related Work

Intent Recognition from Visual Input. There has been an increasing research
focus on intent recognition of agents in videos. [70] proposes a hierarchical
model to predict the intention, as well as the attention of an agent’s eye
gaze from a RGB-D video. [66] focuses on predicting the action, motivation and
scenes from an image by using a third order factor graph built using text.
[58] proposes an unsupervised algorithm to discriminate between an intentional
and unintentional action performed by an agent. [15] too focuses on
discriminating between an intentional and unintentional action, as well as
predicting the point in an unintentional video when the action deviates from
it’s original goal, but does this in a supervised manner. Our work differs
from these as we focus on discriminating between the different goal-directed
and unintentional action categories in unintentional videos, as well as
localizing these action regions in a weakly supervised manner. Action
anticipation can also be relevant to predicting an unintentional action or the
onset of it. [22, 49, 39, 48, 24] focus on forecasting an event or action
based on a small snippet of a video. [67, 62] focus on self supervised
learning approaches to predict future action representation using unlabeled
videos. [20, 47, 63] focus on predicting a pedestrian’s intent to cross the
road using the Joint Attention for Autonomous Driving (JAAD) dataset [46]. Our
work differs from this as it not only focuses on the past and not on
predicting the future, but is also generalized to more diverse environmental
settings.

Weakly Supervised Action localization (WSAL) has been drawing increasing
attention due to the expensive manual labelling process involved in a fully
supervised setting. Previous efforts involve localizing action regions in an
untrimmed video by training a model using only video level action labels [57,
52, 43, 45, 3, 27, 71, 51, 61, 53], or sentences [42, 18, 7, 19, 56, 17, 38].
In particular, STPN [43] trains a classification model using sum of features
weighted by their class-agnostic attention weights, which it learns using a
sparsity loss on the attention weights. It then performs the localization by
using both the classification activation as well as these class-agnostic
weights, thresholding them to select action locations. WTALC [44] forces the
foreground action features from the same action class to be similar and the
background features pertaining to an action class to be dissimilar from its
foreground feature, and finally localizes the action by thresholding the
classification activation. A2CL-PT [41] uses foreground and background
features to form triplets and apply the Angular Triplet Center Loss [33] to
separate the foreground and background features, as well as use an adversarial
branch in order to find supplementary activities from non-localized parts of
the video. DGAM [50] propose to separate action frames from context frames by
modeling the frame representation conditioned on the bottom-up attention. TSCN
[79] fuse the attention sequences from the RGB and optical flow stream and use
it as pseudo ground truth to supervise the training.

Figure 2: Illustration of our overall architecture. A backbone feature
extractor is used to convert raw videos into features, _i.e._ , $\mathbf{X}$
and is kept frozen throughout the training process. $\mathbf{X}$ is then
passed to a video encoder which can be either a GRU [8] or a Transformer
Encoder [64], to extract high level features $\mathbf{O}$. The two attention
modules use $\mathbf{O}$ to predict the bottom-up attention weights
$\lambda^{\text{IA}}$ and $\lambda^{\text{UA}}$ for the goal-directed and
unintentional action respectively, which are used for the Overlap
Regularization. We calculate the goal-directed, _i.e._ ,
$\mathbf{O}^{\text{IA}}$ and unintentional feature, _i.e._ ,
$\mathbf{O}^{\text{UA}}$ by computing a dot product between $\mathbf{O}$ and
their respective bottom-up attention weights. Finally we pass the goal-
directed and unintentional feature through weight-shared linear layers to
extract their respective TCAMs $\mathbf{C}^{\text{IA}}$ and
$\mathbf{C}^{\text{UA}}$. These TCAMs are used for the MIL Loss.

##  3 Methodology

We intend to identify the goal-directed and unintended human activities, as
well as their corresponding moment of occurrence from an unintentional video
in a weakly-supervised manner. To be specific, given the video $\mathcal{V}$
and its categorical labels representing the goal-directed activity,
$y^{\text{IA}}$, and the unintended activity, $y^{\text{UA}}$, we expect the
model to predict the triplets $\langle
s^{\text{IA}},e^{\text{IA}},c^{\text{IA}}\rangle$ and $\langle
s^{\text{UA}},e^{\text{UA}},c^{\text{UA}}\rangle$, containing the starting
point, end point and action class associated with this segment by leveraging
only the video-level annotations as weak supervision. We formulate this
challenge as a weakly supervised action localization (WSAL) task, and address
it using an attention mechanism based approach. We start this section by
providing an overview of our model, followed by the details of formulations
and our proposed learning objective.

###  3.1 Task Formulation

To encode the videos, pre-trained 3D neural networks are exploited to extract
a set of clip-level representations $\mathbf{X}$. We find that in order to
encode the goal-directed and unintentional features from the video, directly
using static features is not sufficient. Hence, we encode the clip embedding
by an encoder network $\mathcal{F}$, which outputs a joint representation for
the goal-directed and unintentional action:
$\mathbf{O}=\mathcal{F}(\mathbf{X}),$ where $\mathbf{O}\in\mathbb{R}^{l\times
d}$ denotes the representations in $d$ dimensions for $l$ clips. Here, encoder
network $\mathcal{F}$ can either be a bidirectional Gated Recurrent Unit or a
Transformer Encoder [64]. On this basis, we introduce two bottom-up attention
modules, which outputs the temporal attention weights that reflect the
temporal importance of clip representations for the goal-
directed/unintentional activity respectively. This is achieved by training the
model with a classification loss, _e.g._ , multiple instance learning loss.
Note that these attention weights are agnostic to the specific action, and are
used to identify generic regions of interest. A stack of 1-D Convolution
layers with RELU activation between layers, followed by a Sigmoid function is
used to obtain the attention weights $\lambda^{\text{IA}}$,
$\lambda^{\text{UA}}\in\mathbb{R}^{l}$ with a scale between 0 and 1.

In order to obtain goal-directed and unintentional features, we compute a dot
product between the joint representation $\mathbf{O}$ and each of the bottom-
up attention weights $\lambda^{\text{IA}}$ and $\lambda^{\text{UA}}$. These
features would represent those parts of the joint representation $\mathbf{O}$
which correspond to the goal-directed and unintentional region respectively.
Formally,

$\displaystyle\small\mathbf{O}^{\text{IA}}$
$\displaystyle=\mathbf{O}\cdot\lambda^{\text{IA}},$
$\displaystyle\mathbf{O}^{\text{UA}}$
$\displaystyle=\mathbf{O}\cdot\lambda^{\text{UA}}.$ (1)

We then compute Temporal Class Activation Maps (TCAM) [43],
$\mathbf{C}^{\text{IA}}\in\mathbb{R}^{l\times N_{\text{IA}}}$,
$\mathbf{C}^{\text{UA}}\in\mathbb{R}^{l\times N_{\text{UA}}}$ for the goal-
directed as well as unintentional actions, with $N_{\text{IA}}$ and
$N_{\text{UA}}$ corresponding to the number of goal-directed and unintentional
classes, by employing two weight-sharing linear transformation layer on
$\mathbf{O}^{\text{IA}}$ and $\mathbf{O}^{\text{UA}}$ respectively. These are
one dimensional class-specific activations that signify classification scores
over time for both the types of actions for each segment (as illustrated in
Fig. 2). These class-specific distributions, along with the class-agnostic
distributions are used to predict the triplets $\langle
s^{\text{IA}},e^{\text{IA}},c^{\text{IA}}\rangle$ and $\langle
s^{\text{UA}},e^{\text{UA}},c^{\text{UA}}\rangle$ associated with the goal-
directed and unintentional activities respectively.

###  3.2 Video Encoder

In order to learn a joint representation for inferring the goal-directed and
unintentional actions, we use a Bidirectional Gated Recurrent Unit [8] as the
video encoder. 3D-CNN architectures like R(2+1)D [60] and I3D [6] capture very
short clip level information. However, capturing information which helps
discriminate between the goal-directed region and an unintentional region
requires longer temporal context which can be modeled by a GRU. Specifically,
our GRU consists of a reset gate $r$ which controls how much importance to
give the previous hidden state $h^{t-1}$ in order to calculate the current
hidden state $h^{t}$, and an update gate $u$ which determines how much of the
previous hidden state $h^{t-1}$ should be carried on to the current hidden
state $h^{t}$. Given the backbone feature $\mathbf{X}$, we compute the hidden
state at each time-step $t$ using the following equations:

$\displaystyle z^{t}$
$\displaystyle=\sigma(\mathbf{W}^{z}\mathbf{X}^{t}+\mathbf{U}^{z}h^{t-1)})$
Update Gate (2) $\displaystyle r^{t}$
$\displaystyle=\sigma(\mathbf{W}^{r}\mathbf{X}^{t}+\mathbf{U}^{r}h^{t-1})$
Reset Gate $\displaystyle\tilde{h}^{t}$
$\displaystyle=\tanh(r^{t}\cdot\mathbf{U}h^{t-1}+\mathbf{W}\mathbf{X}^{t})$
New Memory $\displaystyle h^{t}$
$\displaystyle=(1-z^{t})\cdot\tilde{h}^{t}+z^{t}\cdot h^{t-1},$ Hidden State

where $\mathbf{U}$ and $\mathbf{W}$ correspond to learnable parameters of this
module. In order to capture the forward information flow
$\overrightarrow{h^{(t)}}$ as well as backward information flow
$\overleftarrow{h^{(t)}}$ we use a Bidirectional-GRU and obtain the final
representation $\mathbf{O}$ by concatenating these features from the final
hidden layer.

###  3.3 Multiple Instance Learning Loss

Following previous works in weakly supervised action localization [36, 44,
41], we use the $k$-max Multiple Instance Learning (MIL) [84] loss function
for classifying the goal-directed and unintentional activities in the video.
For each video, we average out the top-$k$ elements of the TCAMs, _i.e._ ,
$\mathbf{C}^{\text{IA}}$ and $\mathbf{C}^{\text{UA}}$ along the temporal axis
for each class to obtain the video-level classification scores
$A^{\text{IA}}\in\mathbb{R}^{{N_{IA}}}$ and
$A^{\text{UA}}\in\mathbb{R}^{{N_{UA}}}$. Here, $k$ is set by [$\frac{l}{s}$]
where $s$ is a hyper-parameter that regulates the number of clips to consider
when making the classification. We then apply a softmax function over class
scores, in order to obtain a probability mass function (pmf) over the goal-
directed as well as unintentional classes, _i.e._ , $p^{\text{IA}}$ and
$p^{\text{UA}}$. Let $y^{\text{IA}}$ and $y^{\text{UA}}$ be the ground truth
label vectors for a video. We then $l_{1}$-normalize them to obtain ground-
truth pmfs $q^{\text{IA}}$ and $q^{\text{UA}}$. Finally we conduct cross
entropy between these two.

$\displaystyle\mathcal{L}_{cls}^{\text{IA}}$
$\displaystyle=\dfrac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{N_{\text{IA}}}-q_{i}^{\text{IA}}(j)\log\big{(}p_{i}^{\text{IA}}(j)\big{)}$
(3) $\displaystyle\mathcal{L}_{cls}^{\text{UA}}$
$\displaystyle=\dfrac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{N_{\text{UA}}}-q_{i}^{\text{UA}}(j)\log\big{(}p_{i}^{\text{UA}}(j)\big{)},$

where $N$ corresponds to the total number of training videos, and the final
loss is the combination of them:
$\mathcal{L}_{cls}=\mathcal{L}_{cls}^{\text{IA}}+\mathcal{L}_{cls}^{\text{UA}}$.

###  3.4 Overlap Regularization

Let $\lambda^{\text{IA}}_{t}$,
$\lambda^{\text{UA}}_{t}\in[0,1]~{}{\forall}~{}t\in[1,l]$ be the bottom-up
attention weights for the goal-directed actions and unintentional action
respectively, obtained from the respective attention modules. $\lambda_{t}$
signifies the temporal attention weight for a clip $t$. During training, a
trivial solution which could be learned by the model is to pay attention to
the entire video when inferring the goal-directed and unintentional action,
_i.e._ , $\lambda^{IA}_{t},\lambda^{UA}_{t}=1~{}{\forall}~{}t\in[1,l]$, though
these actions take place at two distinct sections of the video. Simply
applying the MIL loss cannot guarantee that such distinctions can be learnt
from the data as shown in Section 4.4. We solve this problem by appending an
additional regularization term on the overlap of these attention weights:

$\\!\begin{aligned}
\small\mathcal{L}_{IA}&=\texttt{max}\Big{(}0,\dfrac{\sum_{r}^{N_{T^{\text{UA}}}}\lambda_{T_{r}^{\text{UA}}}^{IA}}{N_{T^{\text{UA}}}}-\dfrac{l}{p})\\\
\mathcal{L}_{\text{UA}}&=\texttt{max}\Big{(}0,\dfrac{\sum_{r}^{N_{T^{\text{IA}}}}\lambda_{T_{r}^{\text{IA}}}^{\text{UA}}}{N_{T^{\text{IA}}}}-\dfrac{l}{p})\\\
&\mathcal{L}_{overlap}=\mathcal{L}_{\text{IA}}+\mathcal{L}_{\text{UA}},\end{aligned}$
(4)

where ${T^{\text{IA}}}$ and ${T^{\text{UA}}}$ are the set of temporal indices
of the bottom-up goal-directed and unintentional attention weights at which
they are more than a predefined threshold. $N_{T^{\text{IA}}}$ and
$N_{T^{\text{UA}}}$ are the lengths of the sets of activated temporal indices.
$p$ is a design parameter which controls the amount of allowed overlap between
the attention maps. Lower the value of $p$, lower the penalization of
overlaps.

Model | Feature | Segment | mAP @ IoU
---|---|---|---
0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | AVG.
STPN [43] | R(2+1)D | Goal | 44.9 | 41.7 | 33.0 | 25.7 | 18.3 | 10.0 | 5.0 | 3.7 | 1.2 | 20.4
UnInt | 30.9 | 26.6 | 21.8 | 15.7 | 9.9 | 5.2 | 1.8 | 1.00 | 0.1 | 12.5
WTALC [44] | R(2+1)D | Goal | 45.1 | 41.8 | 36.1 | 28.9 | 22.8 | 15.9 | 10.4 | 8.1 | 2.0 | 23.5
UnInt | 25.5 | 21.2 | 15.3 | 12.6 | 7.7 | 4.3 | 2.3 | 1.0 | 0.5 | 10.1
A2CL-PT [41] | R(2+1)D | Goal | 41.1 | 38.8 | 34.3 | 28.4 | 23.9 | 16.6 | 10.9 | 8.4 | 2.5 | 22.8
UnInt | 30.2 | 24.2 | 19.8 | 14.2 | 8.6 | 5.0 | 1.8 | 0.6 | 0.1 | 11.6
Ours | R(2+1)D | Goal | 45.3 | 45.1 | 44.0 | 41.8 | 39.1 | 29.5 | 21.9 | 13.9 | 3.5 | 31.6
UnInt | 34.6 | 33.4 | 28.4 | 23.6 | 19.5 | 15.0 | 10.0 | 3.4 | 1.0 | 18.8
STPN [43] | I3D | Goal | 44.8 | 42.8 | 34.9 | 27.8 | 19.9 | 11.1 | 6.1 | 4.0 | 1.6 | 21.5
UnInt | 36.3 | 31.3 | 26.1 | 19.5 | 13.0 | 6.8 | 1.7 | 0.6 | 0.02 | 15.0
WTALC [44] | I3D | Goal | 38.8 | 36.4 | 30.4 | 26.3 | 18.6 | 13.1 | 7.2 | 4.5 | 1.8 | 19.7
UnInt | 22.9 | 18.4 | 14.2 | 11.0 | 6.8 | 3.6 | 1.2 | 0.5 | 0.1 | 8.8
A2CL-PT [41] | I3D | Goal | 38.1 | 36.7 | 31.8 | 26.6 | 22.7 | 17.6 | 12.5 | 9.0 | 4.9 | 22.2
UnInt | 32.4 | 26.1 | 21.6 | 15.3 | 9.9 | 5.2 | 1.6 | 0.7 | 0.1 | 12.5
Ours | I3D | Goal | 51.5 | 51.3 | 49.9 | 44.9 | 41.1 | 32.5 | 24.3 | 14.4 | 5.0 | 35.0
UnInt | 39.4 | 39.0 | 36.4 | 32.2 | 30.0 | 26.6 | 17.6 | 10.2 | 2.8 | 26.0
Table 1: Performance comparison of our model with competitive weakly
supervised action localization (WSAL) models. We adjust the WSAL models by
attaching two classification heads to compute two TCAMs (for the goal-directed
and unintentional action). We then retrain it on our dataset (W-Oops). We can
see that our model significantly outperforms the other methods.

In the goal-directed as well as unintentional regions of the video, the
attention weights should ideally be low at the borders of their respective
ground truth region and high towards the center of this region. Hence we view
$\lambda_{\text{IA}},\lambda_{\text{UA}}$ as Gaussian distributions
$\mathbf{P_{\text{IA}}}\sim\mathcal{N}(\mu_{\text{IA}},\,\sigma_{\text{IA}}^{2})$
and
$\mathbf{P_{\text{UA}}}\sim\mathcal{N}(\mu_{\text{UA}},\,\sigma_{\text{UA}}^{2})$.
Every unintentional action begins with an agent performing a goal-directed
action in order to achieve it’s goal, which then gets disrupted and
transitions into an unintentional action. Using this prior that a goal-
directed action transitions into an unintentional action, we need to ensure
$\mu_{\text{IA}}<\mu_{\text{UA}}$. We approach this by formulating the
following regularization:

$\\!\begin{aligned}
\small\mu_{\text{IA}}&=\dfrac{\sum_{t=1}^{l}\textit{P}^{\lambda_{\text{IA}}}_{t}\cdot{t}}{\sum_{t=1}^{l}\textit{P}^{\lambda_{\text{IA}}}_{t}}\\\
\mu_{\text{UA}}&=\dfrac{\sum_{t=1}^{l}\textit{P}^{\lambda_{\text{UA}}}_{t}\cdot{t}}{\sum_{t=1}^{l}\textit{P}^{\lambda_{\text{UA}}}_{t}}\\\
\mathcal{L}_{order}&=\texttt{max}(0,\dfrac{\mu_{\text{IA}}-\mu_{\text{UA}}}{l}+\dfrac{l}{q}),\end{aligned}$
(5)

where $\textit{P}^{\lambda_{\text{IA}}}$ and
$\textit{P}^{\lambda_{\text{UA}}}$ are probability distributions obtained by
applying softmax over the temporal axis of $\lambda_{\text{IA}}$ and
$\lambda_{\text{UA}}$ respectively. $q$ is a design parameter that helps
control the margin by which $\mu_{\text{UA}}$ has to be greater than
$\mu_{\text{IA}}$. Our model is end-to-end trained with the overall loss as
follows:

$\small\mathcal{L}=\lambda{L}_{cls}+(1-\lambda)(\mathcal{L}_{overlap}+\mathcal{L}_{order}),$
(6)

where $\lambda$ is the weighting hyper-parameter that controls the trade-off
between MIL loss and overlap regularization.

###  3.5 Classification and Localization

After training our network, we use it to classify goal-directed and
unintentional actions as well as localize the regions in which they occur. For
a single video, after obtaining the pmf $p^{\text{IA}}$ and $p^{\text{UA}}$
over each of the classes, as mentioned in Section 3.3, we use mean average
precision (mAP) to conduct evaluation for the classification task. For
localization of the goal-directed and unintentional regions, we consider only
categories having classification scores _i.e._ , $A^{\text{IA}}$ and
$A^{\text{UA}}$ above $0$. For each of these categories, we first scale the
respective TCAM outputs to [0,1] using a Sigmoid function and weight these
using the bottom-up attention weights. This can be formally expressed by:

$\displaystyle\psi^{\text{IA}}(c^{\text{IA}})$
$\displaystyle=\lambda_{\text{IA}}\cdot\texttt{Sigmoid}(C^{\text{IA}}(c^{\text{IA}}))$
$\displaystyle c^{\text{IA}}\in[1,N_{\text{IA}}],$ (7)
$\displaystyle\psi^{\text{UA}}(c^{\text{UA}})$
$\displaystyle=\lambda_{\text{UA}}\cdot\texttt{Sigmoid}(C^{\text{UA}}(c^{\text{UA}}))$
$\displaystyle c^{\text{UA}}\in[1,N_{\text{UA}}],$

where $\psi^{\text{IA}}(c^{\text{IA}})$,
$\psi^{\text{UA}}(c^{\text{UA}})\in\mathbb{R}^{l}$ are the weighted TCAMs, for
the respective classes $c^{\text{IA}}$ and $c^{\text{UA}}$. We finally
threshold $\psi^{\text{IA}}(c^{\text{IA}})$ and
$\psi^{\text{UA}}(c^{\text{UA}})$ to obtain the triplets $\langle
s^{\text{IA}},e^{\text{IA}},c^{\text{IA}}\rangle$ and $\langle
s^{\text{UA}},e^{\text{UA}},c^{\text{UA}}\rangle$.

##  4 Experiments

###  4.1 Dataset & Implementations

Data Preparation. The original Oops Dataset [15] consists of 20,338 videos
containing unintentional human actions obtained by collating “fail” videos
from different users on YouTube. Amazon Mechanical Turk workers are then asked
to label the time at which the video starts transitioning from the goal-
directed action to the unintentional action, as well as indicate whether a
video does not indicate an unintentional action.

In order to create our dataset, which is built upon the labeled portion of the
Oops dataset, we follow a similar pre-processing step as in [15] by removing
those videos that 1). Do not contain an unintentional action 2). Are More than
30 seconds which are likely to contain multiple scenes, as well as those less
than 3 seconds which are not likely to contain one full scene 3). Where the
transition time occurs in the initial/ending 1% of the video, since there
would not be enough context to understand the goal-directed/unintentional
action respectively. Post this process, we were left with a total of about
7,800 labeled videos.

The authors of [15] also provide annotations in the form of natural language
descriptions, which were obtained by asking Amazon Mechanical Turkers to watch
the video and answer: “what was the goal?” and “what went wrong?”. Since we
want to collect a distinct set of goal-directed and unintentional actions, we
followed a technique similar to the Epic Kitchens Dataset [11], by extracting
the verbs and associated noun using the SpaCy111https://spacy.io/ dependency
parser and concatenating them to form an action. We replace all compound nouns
by it’s second noun: _e.g._ , “ride mountain bike” is replaced with “ride
bike” and so on. Due to the diversity of the worker’s vocabulary, we find that
the resulting actions are of low quality, with many of them having ambiguous
meanings, _i.e._ , “fly bike” as well as redundant meanings. In order to
overcome this, we manually go over each of these extracted actions and remove
those with ambiguous meanings as well as merge the redundant ones, _i.e._ ,
“jump over fence” and “jump over chair” into a more general “jump over
obstacle” category. We finally carry out a human evaluation, going through all
the videos manually and ensuring the correctness of the labels, and correcting
them if need be. We also give the evaluator an option to discard the video if
the goal of the actor was ambiguous. We build an annotation tool in order to
make this process easier (refer to the Appendix for details). Finally, we keep
a threshold of 15 for the number of videos per goal-directed and unintentional
action class, discarding all classes below this threshold, as well as the
videos associated with these classes. This leaves us with 44 goal-directed and
30 unintentional classes. We provide detailed statistics and analysis of the
dataset in the Appendix.

Architecture | Feature | GOAL cMAP | UNINT. cMAP
---|---|---|---
Chance | - | $2.7$ | $3.3$
STPN | R(2+1)D | $44.0$ | $32.6$
WTALC | R(2+1)D | $48.5$ | $37.5$
A2CL-PT | R(2+1)D | $46.6$ | $32.6$
Ours | R(2+1)D | $50.5$ | $38.4$
STPN | I3D | $45.3$ | $37.5$
WTALC | I3D | $50.2$ | $38.2$
A2CL-PT | I3D | $48.5$ | $34.8$
Ours | I3D | $52.6$ | $41.1$
Table 2: Mean average precision of activity classification results using
different methods. First row shows the mAP of random chance.

Implementation Details. We extract RGB features by creating chunks of 16
consecutive and non-overlapping frames and using the I3D [6] as well as
R(2+1)D [60] pretrained architectures to extract clip-level features from
these chunks (details provided in the Appendix). This backbone feature
extractor is kept frozen throughout the entire training process. The kernel-
size of all the 1-D convolutional layers for the bottom-up attention modules
are set to 1. The learning rate and loss weighting function $\lambda$ is set
to $10^{-3}$ and 0.8 respectively. We set the MIL loss hyper-parameter $s$ to
3. The parameters of the Overlap Regularization, $p$ and $q$, are set to 1000
and 10 respectively. Finally we set the number of layers of our bidirectional
GRU to 3. Our network is implemented and trained on a machine with a single
Tesla X Pascal GPU for 10,000 iterations using the Adam Optimizer [30] with a
batch size of 16.

$\mathcal{L}_{cls}$ | $\mathcal{L}_{order}$ | $\mathcal{L}_{overlap}$ | SEG. | mAP @ IoU
---|---|---|---|---
0.3 | 0.5 | 0.9 | AVG.
✓ | - | - | Goal | $34.7$ | $17.6$ | $0.9$ | $21.2$
UnInt | $31.1$ | $14.4$ | $0.1$ | $17.4$
✓ | ✓ | - | Goal | $46.3$ | $35.2$ | $2.7$ | $30.1$
UnInt | $31.7$ | $17.9$ | $0.7$ | $19.0$
✓ | ✓ | ✓ | Goal | $49.9$ | $41.1$ | $5.0$ | $35.0$
UnInt | $36.4$ | $30.0$ | $2.8$ | $26.0$
Table 3: Ablation study on contributions of different losses in our model.
Figure 3: Our method is able to identify the temporal regions that correspond
to goal-directed/unintentional activity via the produced weighted TCAMs. Blue
and Orange attention maps correspond to the goal-directed action and
unintentional action respectively.  Figure 4: Effect on Average (Goal+UnInt)
mAP@IoU for the goal-directed and unintentional action when changing $p$
(blue) and $q$ (red).

###  4.2 Goal-directed/Unintent. Action Localization

Our model should be able to focus on the correct regions of the video in order
to infer the goal-directed and unintentional action segments, hence
understanding the transition between these two. In order to evaluate our model
on the task of localizing goal-directed as well as unintentional segments, we
follow the standard evaluation protocol for temporal localization tasks by
calculating the mean average precision (mAP) over different intersection over
union (IoU) thresholds for both the types of actions. Since there are no
quantitative results reported on our dataset, we use competitive models from
the traditional weakly supervised action localization task as baselines. Since
these models are trained using only one classification head which is used to
identify the atomic actions in the video, we repurpose these models by adding
an additional classification head (for the goal-directed and unintentional
action) and bottom-up attention module (in the case of STPN [43]) or
additional branch (in case of A2CL-PT [41]) to adapt it to our task. We then
retrain these models on our dataset and report quantitative results for
comparison in Tab. 5. It may be noted that our method performs significantly
better than other weakly supervised methods on this task, when using the same
backbone. For example, the average mAP@IoU score of our method outperforms
A2CL-PT by 12.8% for the goal-directed action and 13.5% for the unintentional
action, when using an I3D backbone. We conjecture that this localization
improvement is due to our overlap regularization on the bottom-up attention
weights since it enforces the model to focus on distinct portions of the
action scene while ensuring the temporal order of the actions, which is a
crucial property for solving this task. The qualitative results (see Appendix)
show how the WSAL models focus on overlapping regions when inferring the goal-
directed/unintentional action which reduces it’s localization performance.

###  4.3 Goal-directed/Unintent. Action Classification

Given any video our model is trained to predict the goal-directed action as
well as the unintentional action it eventually transitions into. Following
previous works [43, 44], we use mean average precision (mAP) to evaluate the
classification performance of our model on predicting the goal-directed action
as well as unintentional action. We report our results in Tab. 6. It is
interesting to note that our method performs the best on the classification
task as well. For example, it performs 4.1% higher on the Goal cMAP and 6.3%
higher on the Unintentional cMAP than A2CL-PT when using an I3D backbone.

###  4.4 Ablation Study

We conduct an ablation study to analyse various components of our model. We
analyse the significance of the overlap regularization introduced in Section
3.4. We observe very clearly in Tab. 3 that only using $\mathcal{L}_{cls}$ is
not sufficient to localize the goal-directed and unintentional actions, and
our final model performs the best. This implies that all components are
necessary in order to achieve the best performance and each one is effective.
We further analyse the importance of the hyper-parameters $p$ and $q$ used in
the overlap regularization in Fig. 4. We can see that increasing $p$ from 1 to
$10^{3}$ results in a significant increase in the average mAP@IoU. This shows
that the localization performance increases by penalizing the overlap of the
bottom-up attentions more, but plateaus after the $10^{3}$ mark. Analysing the
$q$ hyper-parameter, we notice that increasing the value of $q$ decreases the
performance. Since increasing the value of $q$ results in a lower margin of
separation between the expectations of the goal-directed and unintentional
bottom-up attention weights, we can conclude that a lower value of $q$, _i.e._
, higher margins of separation helps achieve a better localization
performance. However, $q=1$ signifies the extreme case when the margin is
equal to the length of the clips, forcing the goal-directed and unintentional
attention maps to be at two separate ends of the temporal axis, thereby
hurting the performance. Fig. 3 shows qualitative examples of localizing the
goal-directed and unintentional segments on our W-Oops dataset. We further
provide more qualitative examples in the Appendix, which compare our method
with previous WSAL methods.

Figure 5: We form the ground truth caption by concatenating the goal-directed
and unintentional caption with a but.

###  4.5 Video Captioning

Teleological understanding helps explain the action better especially when the
goal is partially/not achieved. In order to further verify whether our
localization module can assist in teleological understanding, we conduct a
captioning experiment which involves explaining the goal-directed and
unintentional parts of the video through natural language descriptions. We
obtain ground truth captions for the goal-directed and unintentional regions
from [15]. The goal-directed and unintentional captions are concatenated
(shown in Fig. 5) to form the ground truth caption for the entire video. We
use an $80\%$-$20\%$ train/test split obtaining $3,200$ training samples and
$800$ test samples. Our experimental setup is divided into two parts:

  * •

Train a state-of-the-art video captioner on the entire video and the whole
ground truth caption.

  * •

Automatically split the video into the goal-directed and unintentional regions
(inferred from their respective attention maps) using our trained localization
module. Train two video captioners with distinct weights, to caption the goal-
directed and unintentional regions with their respective captions as training
signals. Finally, concatenate the two outputted captions by a but to form the
final predicted caption (during inference). Pipeline shown in Fig. 6.

We use RMN [59] as our captioning module, and extract features in the same
manner as mentioned by the authors. Note that the localization module is kept
frozen throughout the training process. From Tab. 4, we observe that the
results obtained after splitting the video into its goal-directed and
unintentional region outperform those when trained on the entire video. In
particular, our method with transition localizer significantly outperforms the
baseline without localizer by $5.1$ SMURF [21] scores and $4.1$ CIDEr [65]
scores. Notably, SMURF [21] is a caption evaluation algorithm that
incorporates diction quality into its evaluation, which demonstrates SOTA
correlation with human judgment and improved explainability. Through SMURF, we
observe that our method improves semantic performance while maintaining the
descriptiveness of terms used in the sentence. These metrics clearly show that
the teleological ability of our localization module helps a captioning module
output more accurate captions on videos containing unintentional actions,
which is achieved by the precise capture of unintentional activity in video.

Figure 6: Pipeline for the captioning experiment (using our localization module).  Exp. |  R [34] |  M [1] |  C [65] |  S [21]
---|---|---|---|---
Without Loc. | 16.7 | 37.7 | 29.8 | 14.1
With Loc. | 17.0 | 38.0 | 33.9 | 19.8
Table 4: Captioning results with or without localization module. R, M, C, S
denote ROUGE_L, METEOR, CIDEr and SMURF metrics respectively for video
captioning evaluations.

##  5 Conclusion

In this paper, we propose W-Oops, an augmented unintentional human activity
dataset that consists of both goal-directed and unintentional video-level
activity annotations, built upon Oops [15]. We consider a weakly supervised
task to infer the respective classes as well as the temporal regions in which
they occur using only the video-level activity annotations. We further build a
neural network architecture which employs a novel overlap regularization on
top of the bottom-up attention weights outputted by our attention module,
which helps the model focus on distinct parts of the video while maintaining
the temporal ordering of these actions when inferring the temporal regions. We
conclude from our experiments that out method significantly outperform
previous WSAL baselines on our benchmark. The video captioning experiment
further verifies the teleological ability of our localization module, which
points a promising future research direction for improving captioning quality
through teleological analysis.

Acknowledgement. This work was supported by the National Science Foundation
under Grant CMMI-1925403, IIS-2132724 and IIS-1750082.

##  6 W-Oops Statistics and Analysis

The final W-oops dataset contains 1582 train samples and 526 testing samples,
containing a total of 44 diverse goal-directed and 30 unintentional action
classes, as seen in Fig. 7. We have also provided the distribution of the
goal-directed and unintentional segment lengths, as well as the total video
lengths. It shows that the goal-directed and unintentional segment lengths are
well diversified over then entire length of the video. The lengths of the
video are short in general, with a majority of them ranging from 6.2 - 7.7
seconds. This makes the task of identifying these sub-regions in the video
challenging. In our benchmark, train samples contain only video-level labels
whereas the test samples contain both the video-level labels as well as the
unintended activity transition points (taken from the original Oops dataset),
which we use to split the video into a goal-directed and unintentional region
in order, for evaluation.

Figure 7: Top: Distribution over the goal-directed and unintentional actions
(partially shown). Lower Left: Distribution over goal-directed and
unintentional segment lengths (normalized by the video length). Lower Right:
Distribution over the entire video length.

##  7 Can Unintentional Actions be predicted knowing the Goal-Directed Action?

In this section we analyse the amount of information knowing about a goal-
directed action gives us when inferring the unintentional action. In order to
do this, we calculate a probability distribution of the unintentional actions
conditioned on the goal-directed actions and calculate their entropy. An
entropy of 0 would indicate that the unintentional action can predicted from
the goal-directed action alone. On the other hand, an entropy of
4.91($-\log_{2}(30)$) indicates that the unintentional actions are
uncorrelated with the goal-directed action. Fig. 8 shows us that the
conditional entropy of unintentional actions lies between these two values,
suggesting that they are correlated but are not completely predictable knowing
the goal-directed action.

##  8 Using 2D Pose Features

Successful attempts at using human skeleton features for activity
recognition.[37, 68, 75], fall prediction [54, 25] and action localization
[40] provides encouragement to use them for our task as well. However human
skeleton features alone would not be enough as it does not capture the
surrounding environment information which the RGB features do. Hence we
concatenate both the RGB features and skeleton features to use as our backbone
features.

In order to test this hypothesis, for each video we extract 2D keypoint
coordinates of human(s) from each observed frame using OpenPose [4]. Since
OpenPose is able to capture multiple human(s) in a frame, we use DeepSort [72]
to cluster the keypoints of the same person across frames. We denote the
sequence of observed keypoints from the $i^{th}$ person in the video as
$\mathbf{K^{i}}=(\mathbf{k}_{1}^{i},\mathbf{k}_{2}^{i},...,\mathbf{k}_{t}^{i})$,
where $\mathbf{k}^{i}_{j}$ denotes the keypoint coordinates of the $i^{th}$
person in frame $j$, with $t$ being the total number of frames. Example showed
in 9

Using the COCO model of OpenPose, we obtain 18 keypoint coordinates for each
observed person in a frame, which include coordinates for the nose, neck, left
and right shoulders, hips, elbows, wrists, knees, ankles, eyes and ears, i.e.,
each

$\mathbf{k}^{i}_{j}=(x^{i}_{j,1},y^{i}_{j,1},x^{i}_{j,2},y^{i}_{j,2},...,x^{i}_{j,18},y^{i}_{j,18})$
(8)

Since these coordinates do not capture the correlation between different
keypoints, we follow the process in [25] to vectorize these coordinates to
incorporate these correlations. We ignore the face keypoints (eyes, ears and
nose), since we want to focus only on the body pose. We then transform the
remaining 13 coordinates into vectors connecting the adjacent keypoints as
illustrated in Fig. The shoulders are connected to the neck, elbows are
connected to the corresponding shoulders, wrists are connected to
corresponding elbows, hips to the neck, knees to the corresponding hips and
finally the ankles to the corresponding knees. Following this process as
followed in [25], we obtain 12 keypoint vectors from the 13 keypoint
coordinates, and normalize them to unit length. For the $m^{th}$ connection
pointing from the $p^{th}$ keypoint to the $q^{th}$ keypoint, the keypoint
vector $(\overline{x^{i}_{j,m}},\overline{y^{i}_{j,m}})$ for the $i^{th}$
person in frame $j$ is calculated as:

$(\overline{x^{i}_{j,m}},\overline{y^{i}_{j,m}})=\dfrac{(x^{i}_{j,q}-x^{i}_{j,p},y^{i}_{j,q}-y^{i}_{j,p})}{\sqrt{{(x^{i}_{j,q}-x^{i}_{j,p})}^{2}+{(y^{i}_{j,q}-y^{i}_{j,p})}^{2}}}$
(9)

We calculate this for each of the 12 connections, and concatenate them to get:

$\overline{\mathbf{k}^{i}_{j}}=(\overline{x^{i}_{j,1}},\overline{y^{i}_{j,1}},\overline{x^{i}_{j,2}},\overline{y^{i}_{j,2}},...,\overline{x^{i}_{j,12}},\overline{y^{i}_{j,12}})$
(10)

Figure 8: Entropy (in bits) of the unintentional actions conditioned on the
goal-directed actions. We can see that the unintentional actions are
correlated to the goal-directed actions but are not completely predictable.

Videos involving action such as two people colliding with another person, or a
person carrying another person, requires features of multiple people in order
to understand these actions. Hence we concatenate the keypoints of the two
most frequently occurring people $l$ and $r$ as detected by DeepSort, and
concatenate them to get the final feature vector for frame $j$ as
$\overline{\mathbf{k}_{j}}=\overline{\mathbf{k}^{l}_{j}}\oplus\overline{\mathbf{k}^{r}_{j}}$.

Note, that there may be partially missing or completely missing keypoint
coordinates for a person in a certain frame. In the case of partially missing
keypoints we set a keypoint vector containing a connection to a missing
keypoint to (0,0). In the case of completely missing keypoints we set all the
keypoint vectors to (0,0) in the case the person had not been detected yet, or
else set all the keypoint vectors to the corresponding last observed keypoint
vectors of the person.

RGB features are extracted by passing non-overlapping chunks of 16 frames to a
pretrained 3D CNN architecture. Since the skeleton feature are extracted for
each frame, we concatenate skeleton features extracted from consecutive and
non-overlapping chunks of 16 frames. We convert
$\overline{\mathbf{k}}=(\overline{\mathbf{k}_{1}},\overline{\mathbf{k}_{2}},...,\overline{\mathbf{k}_{t}})$
to
$\widetilde{\mathbf{k}}=(\widetilde{\mathbf{k}_{1}},\widetilde{\mathbf{k}_{2}},...,\widetilde{\mathbf{k}_{t/16}})$,
where $\widetilde{\mathbf{k}_{h}}$ for the $h^{th}$ chunk is given by :

$\widetilde{\mathbf{k}_{h}}=\overline{\mathbf{k}_{16(h-1)+1}}\oplus\overline{\mathbf{k}_{16(h-1)+2}}\oplus...\oplus\overline{\mathbf{k}_{16(h)}}$
(11)

We finally concatenate the RGB features $X$ and the skeleton features
$\widetilde{\mathbf{k}}$ to obtain
$X_{cat}=(X_{1}\oplus\widetilde{\mathbf{k}_{1}},X_{2}\oplus\widetilde{\mathbf{k}_{2}}),...,X_{l}\oplus\widetilde{\mathbf{k}_{l}})$,
where $l$ is the total number of 16 frame chunks (clips) in the video.

We then provide comparisons between using only the RGB features and using the
RGB features concatenated with the skeleton features in table 5 . We can see
that the performance decreases, from 35.0% to 34.7% for the goal-directed
mAP@IoU and from 26.0% to 24.6% for the unintentional mAP@IoU. We conjecture
that this performance decrease is due to the noise introduced by the
incorrect/missing keypoint coordinates at certain frames, as well as due to
some of the videos which involve an agent driving a vehicle and hence the
agent is partially or completely not seen in the video

Figure 9: An example of extracting body keypoint coordinates of multiple agents in videos using Openpose [4], followed by Deepsort [72] to cluster the keypoints of the same person across the frames. Feature | Segment | mAP@IoU
---|---|---
0.3 | 0.5 | 0.9 | Avg
RGB (I3D) | Goal | 49.9 | 41.1 | 5.0 | 35.0
UnInt | 36.4 | 30.0 | 2.8 | 26.0
RGB (I3D) + Skeleton | Goal | 47.1 | 42.1 | 4.8 | 34.7
UnInt | 34.4 | 27.4 | 2.1 | 24.6
Table 5: Analysis of the effect of skeleton features.

##  9 Analysis of Video Embedding Module

We now analyse the effectiveness of our video embedding module, by removing
the module and using only the raw features from the frozen feature extractor.
We also compare our video embedding module which consists of a GRU with a
Transformer Encoder [64], a component of the original Transformer architecture
which has achieved state of the art results on many vision [80, 5, 78, 14, 83,
81] as well as NLP [13, 76, 29, 74] tasks. As opposed to a GRU which learns
feature representations at each time step in a sequential manner by using the
hidden state in the previous timestep, a transformer encoder uses multiheaded
self attention to calculate the dependency of each token in the sequence to
encode the token at the current timestep. As seen in table 6, we can see that
using static backbone features result in a very poor localization performance.
Additionally it is also interesting to observe that the GRU performs better
than the transformer.

Embedding Module | Segment | mAP@IoU
---|---|---
0.3 | 0.5 | 0.9 | Avg(0.1:0.9)
None | Goal | 30.2 | 16.5 | 1.3 | 18.7
UnInt | 18.6 | 9.4 | 0.02 | 11.1
Transformer Encoder | Goal | 49.1 | 41.5 | 2.7 | 34.9
UnInt | 31.7 | 17.9 | 0.7 | 22.7
GRU | Goal | 49.9 | 41.1 | 5.0 | 35.0
UnInt | 36.4 | 30.0 | 2.8 | 26.0
Table 6: Ablation study of the contribution of the video embedding module.

##  10 Analysis of Weight Tradeoff Parameter $\lambda$

$\lambda$ is the scalar parameter used to control the tradeoff between the
Multiple Instance Learning Loss (MIL) and the Overlap Regularization. We study
the effects of changing this parameter in the range of [0,1], where
$\lambda$=0 corresponds to purely MIL Loss and $\lambda$=1 corresponds to
purely Overlap Regularization. As seen in Fig. 10, we notice that for
$0.3\leq\lambda\leq 0.8$, the average mAP@IoU for the goal-directed and
unintentional action remains almost constant, but on close observation we see
that $\lambda=0.8$ performs the best for the goal-directed as well as
unintentional action.

##  11 Feature Extraction Details

This section provides detailed explanation about the feature extraction
process. We follow previous work [15] and down-sample all raw videos at 25
FPS. We then create chunks of 16 consecutive and non-overlapping frames. In
order the extract the I3D and R(2+1)D features, we pass these chunks to the
respective backbone networks and obtain the features as the output of their
global pooling layers. We use the following libraries to extract
R(2+1)D222https://pytorch.org/vision/0.8/models.html and
I3D333https://github.com/deepmind/kinetics-i3d features from the videos.

I3D: For the I3D [6] features, we re-scale all frame pixels between -1 and 1,
after which we resize the frames preserving aspect ratio such that the
smallest dimension is 256 pixels. We then apply center crop to obtain
$224\times 224$ frames. Chunks of 16 non-overlapping frames are then passed
through the RGB stream of a I3D [6] backbone pretrained on the Kinetics
dataset [28] to obtain features $\mathbf{X_{i}}\in{}^{1024\times l_{i}}$ from
the global pooling layer.

R(2+1)D: For the R(2+1)D [60] network, we re-scale frame pixels between 0 and
1, after which we resize all frames to $128\times 171$. We then normalize
these frames and finally apply center crop to obtain $112\times 112$ frames.
We the chunk the frames in the same way and pass it through the R(2+1)D [60]
backbone pretrained on Kinetics to obtain features
$\mathbf{X_{i}}\in{}^{512\times l_{i}}$ from the global pooling layer.

Figure 10: Analysis of the effect of $lambda$ which is a scalar parameter for
controlling the tradeoff between the MIL Loss and Overlap Regularization.

##  12 Annotation Tool for Label Evaluation and Correction

The annotation tool used for the human evaluation and correction process is
shown in Fig.11. We provide a video to the evaluator along with the actions
extracted from the annotations. The evaluator can then view the videos and
mark the goal-directed actions as well as unintentional action as either
‘Good’ (G) or ‘Poor’ (P), with reference to the video. ‘Good’ is given to an
action which is entailed in the video and ‘Poor’ otherwise. In case the
evaluator marks an action as ‘Poor’, they can then choose another action from
the already present list of total actions, or else add a new action if not
contained in the list. The evaluator also has an option to not keep the video
in the case the goal of the agent in the video was ambiguous. Once this
process is complete, evaluators can hit ’Submit’, which would then load the
next video.

Figure 11: Interface for W-Oops annotations, where we ask the annotators to
rate the semi-automatically extracted goal-directed and unintentional actions
as ‘Good’ or ‘Poor’. If ‘Poor’, they can choose from a fixed list of already
present actions or input their own. They also have an option to indicate
whether or not to keep the video in the case the goal in the video is
ambiguous.

##  13 Qualitative Results of Goal-directed and Unintent. Action Localization

In this section, we provide additional qualitative results of our model, along
with previous weakly supervised action localization (WSAL) models, namley
WTALC [44] and STPN [43]. We have provided examples of videos containing
diverse actions, in order to show our model’s generalizability. From Fig. 12,
Fig. 13 and Fig. 14, we notice that our model is able to focus on distinct
regions in order to infer the goal-directed and unintentional actions, whereas
the previous WSAL models focus on overlapping regions, and in many cases have
very sparse attention weights. We conjecture this is due to the nature of task
these models were originally built for, _i.e._ , segmenting atomic actions
from untrimmed videos. Additionally, we can see that the Overlap
Regularization is able to enforce our model to maintain the temporal ordering
of the goal-directed/unintentional action.

##  14 Qualitative Results for Video Captioning

This section provides qualitative results of the video captioning experiment.
We report the ground-truth captions annotated by humans, captions generated
without using our localization module, as well as captions generated using our
localization module. Fig. 15 shows that leveraging our localization module
helps generate more descriptive and semantically correct captions, being able
to describe the video better and hence assisting in the teleological
understanding.

Figure 12: Qualitative results of our model’s outputs. We provide attention
weights outputted from STPN trained on our dataset, as well as the ground
truth segments for comparison.  Figure 13: Qualitative results of our model’s
outputs. We provide attention weights outputted from STPN trained on our
dataset, as well as the ground truth segments for comparison.  Figure 14:
Qualitative results of our model’s outputs. We provide attention weights
outputted from STPN trained on our dataset, as well as the ground truth
segments for comparison.  Figure 15: Qualitative results for the video
captioning experiment. We provide ground truth captions from a human
annotator, captions generated without as well as with our localization module.
We observe that the captions generated leveraging our localization module tend
to be more descriptive and semantically correct.

## References

  * [1] Satanjeev Banerjee and Alon Lavie.  Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  In Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization, pages 65–72, 2005.
  * [2] Amanda C Brandone and Henry M Wellman.  You can’t always get what you want: Infants understand failed goal-directed actions.  Psychological science, 20(1):85–91, 2009.
  * [3] Shyamal Buch, Victor Escorcia, Chuanqi Shen, Bernard Ghanem, and Juan Carlos Niebles.  Sst: Single-stream temporal action proposals.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 2911–2920, 2017.
  * [4] Zhe Cao, Gines Hidalgo, Tomas Simon, Shih-En Wei, and Yaser Sheikh.  Openpose: realtime multi-person 2d pose estimation using part affinity fields.  IEEE transactions on pattern analysis and machine intelligence, 43(1):172–186, 2019.
  * [5] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European Conference on Computer Vision, pages 213–229. Springer, 2020.
  * [6] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6299–6308, 2017.
  * [7] Zhenfang Chen, Lin Ma, Wenhan Luo, Peng Tang, and Kwan-Yee K Wong.  Look closer to ground better: Weakly-supervised temporal grounding of sentence in video.  arXiv preprint arXiv:2001.09308, 2020.
  * [8] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  arXiv preprint arXiv:1412.3555, 2014.
  * [9] Gergely Csibra.  Goal attribution to inanimate agents by 6.5-month-old infants.  Cognition, 107(2):705–717, 2008.
  * [10] Gergely Csibra and György Gergely.  ‘obsessed with goals’: Functions and mechanisms of teleological interpretation of actions in humans.  Acta psychologica, 124(1):60–78, 2007.
  * [11] Dima Damen, Hazel Doughty, Giovanni Maria Farinella, Sanja Fidler, Antonino Furnari, Evangelos Kazakos, Davide Moltisanti, Jonathan Munro, Toby Perrett, Will Price, et al.  Scaling egocentric vision: The epic-kitchens dataset.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 720–736, 2018.
  * [12] Mahdi Davoodikakhki and KangKang Yin.  Hierarchical action classification with network pruning.  In International Symposium on Visual Computing, pages 291–305. Springer, 2020.
  * [13] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [14] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [15] Dave Epstein, Boyuan Chen, and Carl Vondrick.  Oops! predicting unintentional action in video.  In The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [16] Zhiyuan Fang, Tejas Gokhale, Pratyay Banerjee, Chitta Baral, and Yezhou Yang.  Video2commonsense: Generating commonsense descriptions to enrich video captioning.  Conference on Empirical Methods in Natural Language Processing, 2020\.
  * [17] Zhiyuan Fang, Shu Kong, Charless Fowlkes, and Yezhou Yang.  Modularized textual grounding for counterfactual resilience.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6378–6388, 2019.
  * [18] Zhiyuan Fang, Shu Kong, Zhe Wang, Charless Fowlkes, and Yezhou Yang.  Weak supervision and referring attention for temporal-textual association learning.  arXiv preprint arXiv:2006.11747, 2020.
  * [19] Zhiyuan Fang, Shu Kong, Tianshu Yu, and Yezhou Yang.  Weakly supervised attention learning for textual phrases grounding.  arXiv preprint arXiv:1805.00545, 2018.
  * [20] Zhijie Fang and Antonio M López.  Intention recognition of pedestrians and cyclists by 2d pose estimation.  IEEE Transactions on Intelligent Transportation Systems, 21(11):4773–4783, 2019.
  * [21] Joshua Feinglass and Yezhou Yang.  Smurf: Semantic and linguistic understanding fusion for caption evaluation via typicality analysis.  In Proceedings of the Annual Meeting of the Association for Computational Linguistics, 2021.
  * [22] Antonino Furnari and Giovanni Maria Farinella.  What would you expect? anticipating egocentric actions with rolling-unrolling lstms and modality attention.  CoRR, abs/1905.09035, 2019.
  * [23] György Gergely and Gergely Csibra.  Teleological reasoning in infancy: The naıve theory of rational action.  Trends in cognitive sciences, 7(7):287–292, 2003.
  * [24] M. Hoai and F. De la Torre.  Max-margin early event detectors.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2863–2870, 2012.
  * [25] Minjie Hua, Yibing Nan, and Shiguo Lian.  Falls prediction based on body keypoints and seq2seq architecture.  In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 0–0, 2019.
  * [26] M Esat Kalfaoglu, Sinan Kalkan, and A Aydin Alatan.  Late temporal modeling in 3d cnn architectures with bert for action recognition.  In European Conference on Computer Vision, pages 731–747. Springer, 2020.
  * [27] Vicky Kalogeiton, Philippe Weinzaepfel, Vittorio Ferrari, and Cordelia Schmid.  Action tubelet detector for spatio-temporal action localization.  In Proceedings of the IEEE International Conference on Computer Vision, pages 4405–4413, 2017.
  * [28] Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al.  The kinetics human action video dataset.  arXiv preprint arXiv:1705.06950, 2017.
  * [29] Nitish Shirish Keskar, Bryan McCann, Lav R Varshney, Caiming Xiong, and Richard Socher.  Ctrl: A conditional transformer language model for controllable generation.  arXiv preprint arXiv:1909.05858, 2019.
  * [30] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [31] Pilhyeon Lee, Youngjung Uh, and Hyeran Byun.  Background suppression network for weakly-supervised temporal action localization.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 11320–11327, 2020.
  * [32] Jie Lei, Licheng Yu, Tamara L Berg, and Mohit Bansal.  What is more likely to happen next? video-and-language future event prediction.  arXiv preprint arXiv:2010.07999, 2020.
  * [33] Zhaoqun Li, Cheng Xu, and Biao Leng.  Angular triplet-center loss for multi-view 3d shape retrieval.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 8682–8689, 2019.
  * [34] Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In Text summarization branches out, pages 74–81, 2004.
  * [35] Ji Lin, Chuang Gan, and Song Han.  Tsm: Temporal shift module for efficient video understanding.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7083–7093, 2019.
  * [36] Daochang Liu, Tingting Jiang, and Yizhou Wang.  Completeness modeling and context separation for weakly supervised temporal action localization.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1298–1307, 2019.
  * [37] Diogo C Luvizon, David Picard, and Hedi Tabia.  2d/3d pose estimation and action recognition using multitask deep learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5137–5146, 2018.
  * [38] Minuk Ma, Sunjae Yoon, Junyeong Kim, Youngjoon Lee, Sunghun Kang, and Chang D Yoo.  Vlanet: Video-language alignment network for weakly-supervised video moment retrieval.  In European Conference on Computer Vision, pages 156–171. Springer, 2020.
  * [39] A. Miech, I. Laptev, J. Sivic, H. Wang, L. Torresani, and D. Tran.  Leveraging the present to anticipate the future in videos.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 2915–2922, 2019.
  * [40] Daisuke Miki, Shi Chen, and Kazuyuki Demachi.  Weakly supervised graph convolutional neural network for human action localization.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 653–661, 2020.
  * [41] Kyle Min and Jason J Corso.  Adversarial background-aware loss for weakly-supervised temporal activity localization.  In European Conference on Computer Vision, pages 283–299. Springer, 2020.
  * [42] Niluthpol Chowdhury Mithun, Sujoy Paul, and Amit K. Roy-Chowdhury.  Weakly supervised video moment retrieval from text queries.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [43] Phuc Nguyen, Ting Liu, Gautam Prasad, and Bohyung Han.  Weakly supervised action localization by sparse temporal pooling network.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6752–6761, 2018.
  * [44] Sujoy Paul, Sourya Roy, and Amit K Roy-Chowdhury.  W-talc: Weakly-supervised temporal activity localization and classification.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 563–579, 2018.
  * [45] Sujoy Paul, Sourya Roy, and Amit K Roy-Chowdhury.  W-talc: Weakly-supervised temporal activity localization and classification.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 563–579, 2018.
  * [46] A. Rasouli, I. Kotseruba, and J. K. Tsotsos.  Are they going to cross? a benchmark dataset and baseline for pedestrian crosswalk behavior.  In 2017 IEEE International Conference on Computer Vision Workshops (ICCVW), pages 206–213, 2017.
  * [47] Amir Rasouli, Mohsen Rohani, and Jun Luo.  Pedestrian behavior prediction via multitask learning and categorical interaction modeling.  arXiv preprint arXiv:2012.03298, 2020.
  * [48] M. S. Ryoo.  Human activity prediction: Early recognition of ongoing activities from streaming videos.  In 2011 International Conference on Computer Vision, pages 1036–1043, 2011.
  * [49] Mohammad Sadegh Aliakbarian, Fatemeh Sadat Saleh, Mathieu Salzmann, Basura Fernando, Lars Petersson, and Lars Andersson.  Encouraging lstms to anticipate actions very early.  In Proceedings of the IEEE International Conference on Computer Vision, pages 280–289, 2017.
  * [50] Baifeng Shi, Qi Dai, Yadong Mu, and Jingdong Wang.  Weakly-supervised action localization by generative attention modeling.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1009–1019, 2020.
  * [51] Zheng Shou, Jonathan Chan, Alireza Zareian, Kazuyuki Miyazawa, and Shih-Fu Chang.  Cdc: Convolutional-de-convolutional networks for precise temporal action localization in untrimmed videos.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5734–5743, 2017.
  * [52] Zheng Shou, Hang Gao, Lei Zhang, Kazuyuki Miyazawa, and Shih-Fu Chang.  Autoloc: Weakly-supervised temporal action localization in untrimmed videos.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 154–171, 2018.
  * [53] Zheng Shou, Dongang Wang, and Shih-Fu Chang.  Temporal action localization in untrimmed videos via multi-stage cnns.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1049–1058, 2016.
  * [54] Markus D Solbach and John K Tsotsos.  Vision-based fallen person detection for the elderly.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 1433–1442, 2017.
  * [55] Jessica A Sommerville and Amanda L Woodward.  Pulling out the intentional structure of action: the relation between action processing and action production in infancy.  Cognition, 95(1):1–30, 2005.
  * [56] Yijun Song, Jingwen Wang, Lin Ma, Zhou Yu, and Jun Yu.  Weakly-supervised multi-level attentional reconstruction network for grounding textual queries in videos.  arXiv preprint arXiv:2003.07048, 2020.
  * [57] Chen Sun, Sanketh Shetty, Rahul Sukthankar, and Ram Nevatia.  Temporal localization of fine-grained actions in videos by domain transfer from web images.  In Proceedings of the 23rd ACM international conference on Multimedia, pages 371–380. ACM, 2015.
  * [58] Stuart Synakowski, Qianli Feng, and Aleix Martinez.  Adding knowledge to unsupervised algorithms for the recognition of intent.  International Journal of Computer Vision, Jan 2021.
  * [59] Ganchao Tan, Daqing Liu, Meng Wang, and Zheng-Jun Zha.  Learning to discretely compose reasoning module networks for video captioning.  arXiv preprint arXiv:2007.09049, 2020.
  * [60] Du Tran, Heng Wang, Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri.  A closer look at spatiotemporal convolutions for action recognition.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 6450–6459, 2018.
  * [61] Du Tran and Junsong Yuan.  Max-margin structured output regression for spatio-temporal action localization.  In Advances in neural information processing systems, pages 350–358, 2012.
  * [62] Vinh Tran, Yang Wang, and Minh Hoai.  Back to the future: Knowledge distillation for human action anticipation.  CoRR, abs/1904.04868, 2019.
  * [63] D. Varytimidis, F. Alonso-Fernandez, B. Duran, and C. Englund.  Action and intention recognition of pedestrians in urban traffic.  In 2018 14th International Conference on Signal-Image Technology Internet-Based Systems (SITIS), pages 676–682, 2018.
  * [64] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [65] Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh.  Cider: Consensus-based image description evaluation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4566–4575, 2015.
  * [66] Carl Vondrick, Deniz Oktay, Hamed Pirsiavash, and Antonio Torralba.  Predicting motivations of actions by leveraging text.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2997–3005, 2016.
  * [67] Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Anticipating the future by watching unlabeled video.  CoRR, abs/1504.08023, 2015.
  * [68] Chunyu Wang, Yizhou Wang, and Alan L Yuille.  An approach to pose-based action recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 915–922, 2013.
  * [69] Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool.  Temporal segment networks: Towards good practices for deep action recognition.  In European conference on computer vision, pages 20–36. Springer, 2016.
  * [70] P. Wei, Y. Liu, T. Shu, N. Zheng, and S. Zhu.  Where and why are they looking? jointly inferring human attention and intentions in complex tasks.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6801–6809, 2018.
  * [71] Philippe Weinzaepfel, Zaid Harchaoui, and Cordelia Schmid.  Learning to track for spatio-temporal action localization.  In Proceedings of the IEEE international conference on computer vision, pages 3164–3172, 2015.
  * [72] Nicolai Wojke, Alex Bewley, and Dietrich Paulus.  Simple online and realtime tracking with a deep association metric.  In 2017 IEEE international conference on image processing (ICIP), pages 3645–3649. IEEE, 2017.
  * [73] Amanda L Woodward, Jessica A Sommerville, and Jose J Guajardo.  How infants make sense of intentional action.  Intentions and intentionality: Foundations of social cognition, pages 149–169, 2001.
  * [74] Chien-Sheng Wu, Steven Hoi, Richard Socher, and Caiming Xiong.  Tod-bert: Pre-trained natural language understanding for task-oriented dialogues.  arXiv preprint arXiv:2004.06871, 2020.
  * [75] Sijie Yan, Yuanjun Xiong, and Dahua Lin.  Spatial temporal graph convolutional networks for skeleton-based action recognition.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * [76] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  arXiv preprint arXiv:1906.08237, 2019.
  * [77] Rowan Zellers, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  From recognition to cognition: Visual commonsense reasoning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [78] Yanhong Zeng, Jianlong Fu, and Hongyang Chao.  Learning joint spatial-temporal transformations for video inpainting.  In European Conference on Computer Vision, pages 528–543. Springer, 2020.
  * [79] Yuanhao Zhai, Le Wang, Wei Tang, Qilin Zhang, Junsong Yuan, and Gang Hua.  Two-stream consensus network for weakly-supervised temporal action localization.  In European Conference on Computer Vision, pages 37–54. Springer, 2020.
  * [80] Dong Zhang, Hanwang Zhang, Jinhui Tang, Meng Wang, Xiansheng Hua, and Qianru Sun.  Feature pyramid transformer.  In European Conference on Computer Vision, pages 323–339. Springer, 2020.
  * [81] Ziqi Zhang, Yaya Shi, Chunfeng Yuan, Bing Li, Peijin Wang, Weiming Hu, and Zheng-Jun Zha.  Object relational graph with teacher-recommended learning for video captioning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 13278–13288, 2020.
  * [82] Bolei Zhou, Alex Andonian, Aude Oliva, and Antonio Torralba.  Temporal relational reasoning in videos.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 803–818, 2018.
  * [83] Luowei Zhou, Yingbo Zhou, Jason J Corso, Richard Socher, and Caiming Xiong.  End-to-end dense video captioning with masked transformer.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 8739–8748, 2018.
  * [84] Zhi-Hua Zhou.  Multi-instance learning: A survey.  Department of Computer Science & Technology, Nanjing University, Tech. Rep, 2, 2004.


# Neuro-Symbolic Sudoku Solver

Ashutosh Hathidara
Luddy School of Informatics Graduated from Indiana University and is no-longer
associated to University for any research. Computing & Engineering
Indiana University
Bloomington  IN 47405
<EMAIL_ADDRESS>
&Lalit Pandey
Luddy School of Informatics  Computing & Engineering
Indiana University
Bloomington  IN 47405
<EMAIL_ADDRESS>

###### Abstract

Deep Neural Networks have achieved great success in some of the complex tasks
that humans can do with ease. These include image recognition/classification,
natural language processing, game playing etc. However, modern Neural Networks
fail or perform poorly when trained on tasks that can be solved easily using
backtracking and traditional algorithms. Therefore, we use the architecture of
the Neuro Logic Machine (NLM) [5] and extend its functionality to solve a 9X9
game of Sudoku. To expand the application of NLMs, we generate a random grid
of cells from a dataset of solved games and assign up to 10 new empty cells.
The goal of the game is then to find a target value ranging from 1 to 9 and
fill in the remaining empty cells while maintaining a valid configuration. In
our study, we showcase an NLM which is capable of obtaining 100% accuracy for
solving a Sudoku with empty cells ranging from 3 to 10. The purpose of this
study is to demonstrate that NLMs can also be used for solving complex
problems and games like Sudoku. We also analyse the behaviour of NLMs with a
backtracking algorithm by comparing the convergence time using a graph plot on
the same problem. With this study we show that Neural Logic Machines can be
trained on the tasks that traditional Deep Learning architectures fail using
Reinforcement Learning. We also aim to propose the importance of symbolic
learning in explaining the systematicity in the hybrid model of NLMs.

_Keywords_ Neural Logic Machines $\cdot$ Symbolic Learning $\cdot$ Neuro
Symbolic $\cdot$ Sudoku Solver $\cdot$ Neural Networks $\cdot$ Deep
Reinforcement Learning.

##  1 Introduction

The groundbreaking results of the modern deep learning models have proved that
they are the ideal tools to solve complex problems, however the lack of
systematicity in these models have been a problem for some time. Recent
research has focussed on this issue by generating hybrid models which combine
Neural Networks with Symbolic Learning. In past, researchers have attempted to
create hybrid models for tasks such as Language Translation [1], Curriculum
Learning [2], Learnable Recursion Logic [3] and the Synthesizing complex logic
based on Input-Output example pairs [4], etc. By testing one such model,
called the Neural Logic Machine [5], we emphasise on the relevance of symbolic
learning in solving complex problems on which modern deep learning methods may
fail. More specifically, we validate the NLM model on a different mathematical
problem to realize their true potential as well as analyse their performance.
Importantly NLMs can utilize the knowledge gained from generated rules to
achieve a perfect generalization in several tasks. Therefore, we also aimed to
test the NLMs ability to recover these lifted rules and apply them in the
later stages of curriculum learning - when the complexity of the problem
rises. To accomplish this, we gradually changed the number of empty cells in
the grid while training.

We test the architecture of Neural Logic Machines [5] for solving a complex
puzzle called Sudoku using our own set of predicates as input. In this
experiment, we closely analyse the performance of this model and compare it
with traditional algorithms on the same problem. To perform this experiment,
we completed three main tasks. First, we trained the NLM on sudoku grids with
pre-defined empty cells, the number of which increased as training progressed.
This approach , where the complexity of the problem increases over training,
is known as curriculum learning. Secondly, we used symbolic learning with
reinforcement rewards to award the model every time a valid configuration of
the empty cells was achieved. Finally, the convergence time of the NLM and
Backtracking algorithm was compared using a graph plot. Towards the end of the
experiment, we successful tested the model with random sudoku grids.

In the later sections, we elaborate upon the robustness of the algorithm and
systematicity of the network layers.

###  1.1 Key Contributions

Our major contributions in this paper are:

####  1.1.1 Extending the Applications of Neural Logic Machines:

The NLM is trained and tested on a completely different problem set (e.g.,
Sudoku puzzles) to expand its scope in wide areas of applications. In [5],
linear space problems (e.g., sorting arrays) are used to test this model,
whereas, this paper focuses on using 2-dimensional problem set on the same
model. Instead of function approximation, the reinforcement training algorithm
‘REINFORCE’ is used to estimate the gradients using a policy-gradient
mechanism and calculate the gradients in a non-differentiable trainable
setting.

####  1.1.2 Time Complexity and Comparison with Backtracking:

Upon successful implementation of NLM on a 9X9 Sudoku grid, their convergence
time is compared with Backtracking algorithm and demonstrated using a
graphical representation. A thorough comparison of NLM with backtracking is
also mentioned in the result section.

####  1.1.3 Testing the Robustness of the Neural Logic Machine:

While the NLM [5] is tested with tasks like list sorting, path finding and
BlocksWorld games, we have chosen a more complex problem; solving a 9X9 sudoku
puzzle with upto 10 empty cells. To sort an array, we need to compare elements
with each other and swap if needed. Whereas, in Sudoku, we need to fill the
gaps with appropriate numbers checking rows, columns and sub-matrices. This
makes the problem more complex.

##  2 Related work

The rising demand to train Neural Networks for performing complex tasks has
generated great attention among the researchers. However, their lack of
systematicity and inability to generalize for a greater set of inputs has lead
them to perform poorly on more systematic tasks. To address these challenges,
[5] proposed the Neural Logic Machine, which can solve problems requiring
systems to perform actions by following systematic sets of rules. In [5], NLMs
utilizes the relationships of objects obtained from quantifiers and logic
predicates to solve BlocksWorld games, list sorting and path-finding tasks.
The study done in [5] highlights the difference between conventional RNNs
(Recurrent Neural Networks) with their proposed NLM, addressing the RNN’s
difficulty on smaller lists, and failure to sort slightly larger lists during
testing. The reason behind that is RNNs trained on smaller lists will not be
able to systematically generalize it for larger lists whereas NLM can.

#####

An alternate approach to function approximators has been used with NLM called
the REINFORCE algorithm [6], which is used for policy gradient optimization
and estimates the gradient using a Monte-Carlo method. This is commonly used
in deep reinforcement learning where the actions are sampled and the neural
network can not perform backpropagation since sampling is non-differentiable
operation. In such non-differentiable settings, we instead use gradient
estimation techniques.

In 2019, Wang et al. [7] proposed a novel deep-learning architecture called
the SATNet, which is a differentiable maximum satisfiability solver that uses
CNNs. It is an approximate-differentiable solver which works on a fast
coordinate descent approach for solving semidefinite programs (SDP) associated
with the Maximum Satisfiability problem.

#####

While the previous studies have focused on using NLMs on different problem
sets [5] or solving Sudoku puzzles with fully Deep Learning approaches [7],
our experiment emphasizes the combination of Symbolic Learning with Deep
Learning, as well as a hybrid architecture to solve a new sets of complex
problems. Lastly, this experiment also focuses on realizing the true potential
of NLMs in different areas of applications.

##  3 Proposed Methodology

Figure 1: Model Architecture of Neural Logic Machine

#####

Figure 1 illustrates our proposed model architecture for the Neuro-Symbolic
Sudoku Solver - a Hybrid architecture of Deep Reinforcement Learning
techniques and Symbolic Learning. The first half of the model constitutes the
learning phase, where the Sigmoid function acts as the activation function
between hidden layers, and the SoftMax function activates the output layer.
The input layer consists of 4 neurons each accepting a certain type of
parameter. The flexibility to allocate a certain type of input to each neuron,
leads to greater systematicity in the model. For instance, out of the four
neurons in the input layer, the first neuron, $i_{0}$, accepts only a nullary
predicate; $i_{1}$ accepts a unary predicate; $i_{2}$ accepts a binary
predicate, and $i_{3}$ receives a ternary predicate as an input.

The problem of solving Sudoku puzzles requires checking for each row, column,
and submatrix to maintain a valid configuration of the Sudoku grid. In order
to check this constraint, the coordinates of the rows and columns along with
the target values are passed to the input layer. Therefore, neurons $i_{2}$
and $i_{3}$ receive input as binary and ternary predicates, while neurons
$i_{0}$ and $i_{1}$ receive Null inputs. In contrast to this experiment, [5]
shows how their problems require predicates for a different set of neurons in
the NLM. For example, [5] uses $i_{1}$ and $i_{2}$ since unary and binary
predicates are required to solve the array sorting problem. Once the set of
predicates is received by the input layer, the input for the following layers
are reduced or expanded based on the arity of the previous layer.

The output from the SoftMax layer is fetched by the Reinforcement Learning
(RL) module, which constitutes Phase 2 of the architecture (see figure 2). The
RL module takes care of three main functionalities: Allocating a +1 positive
reward for a fully solved grid, a negative reward of -0.01 for every move and
performing environmental resets after checking all target values. The RL
Module will trigger an environmental reset if none of the target values from
1-9 can fill an empty cell while maintaining a valid configuration of the
Sudoku grid. During this reset, all filled values are emptied, the sudoku grid
is reinitialized, and a new iteration begins.

Figure 2: High Level System Architecture

#####

Given an unsolved Sudoku grid, we have implemented a multistage architecture
to solve the grid step-by-step. Figure 2 illustrates the high-level
architecture of the Neuro-Symbolic Sudoku solver, which aligns with problems
experimented in the original NLM paper.

The first step in this implementation diagram consists of calculating the
boolean predicates. There are three important rules to solve a sudoku grid:
The solver needs to put a number in an empty cell such that the resulting grid
configuration remains valid. Here, valid configurations refers to the states
where each number in every row, column, and 3x3 submatrix is distinct. With
the help of these conceptual rules, lifted Boolean predicates may be created.

Lifted rules are generalized rules which apply to a task to crack its
solvability. These rules are applicable to any example in that task domain,
irrespective of its configuration or complexity. These rules can be seen as
the simplest fundamental rules of solving a system. We define the predicate
isRow(r, x), which computes whether number x exists anywhere in row r.
Similarly, predicate isColumn(c, x) computes whether number x exists anywhere
in column c and predicate isSubMat(r, c, x) computes whether number x exists
in the 3x3 submatrix containing the cell (r, c). Based on above definition of
the predicates, isRow(r, x) and isColumn(c, x) are binary predicates and both
result in [9, 9] shaped tensors whereas isSubMat(r, c, x) is a ternary
predicate that results in a [9, 9, 9] shaped tensor.

It is also worth mentioning that in this study we do not input the unsolved
grid into the input layer of the neural network. Instead, we compute the
predicates as described above and pass those predicates as a set of input.
Since there are two binary predicates, we concatenate the values of isRow(r,
x) and isColumn(c, x) and call the resultant tensor as a stacked binary
predicate. Now, these predicates can be feeded into the input layer of the
neural network.

The last layer of the NLM logic machine computes the SoftMax value and
provides the empty cell position, (r, c), as well as the target value to place
in the empty cell. Here comes the role of the reinforcement module. The
Reinforcement module checks if placing x into (r, c) makes a valid sudoku grid
or not. Based on the previous assertion, it generates the next state and
computes the positive reward (if the next state is not a valid sudoku grid) or
negative reward (if the next state is not a valid sudoku grid). The
reinforcement algorithm also checks if the next state generated is a solved
Sudoku grid. In this case, we break from the iteration and print the output,
otherwise, we repeat the same steps.

However, the above strategy may take indefinite number of steps to find a
solution. To prevent this, we have defined an upper bound on the number of
steps the algorithm may take. The proposed algorithm yields a success rate of
1 if it solves the grid, and a 0 otherwise.

###  3.1 Training Details

Problem | Epochs | Batch Size | Loss | Optimizer | LR | RL Rewards | $\boldsymbol{\gamma}$
---|---|---|---|---|---|---|---
Sudoku Puzzle | 50 | 4 | Softmax-CE | Adam | 0.005 | +1,-0.01 | 0.99
Table 1: Training Details of Neuro-Symbolic Sudoku Solver

The hyper-parameters and the training details of the NLM for solving a 9x9
sudoku puzzle are shown in table 1.

##  4 Result and Analysis

No. of Empty Cells | Max. Steps | Success Rate
---|---|---
3 | 81 | 0.94
3 | 150 | 1.00
3 | 400 | 1.00
3 | 729 | 1.00
5 | 81 | 0.80
5 | 150 | 0.96
5 | 400 | 0.99
5 | 729 | 1.00
8 | 80 | 0.68
8 | 150 | 0.92
8 | 400 | 0.98
8 | 729 | 1.00
Table 2: Comparison of different training parameters

Our experiment involves multiple settings (number of empty cells, dimensions
and optimal steps) of the grid, which are often modified during the testing
phase to understand the performance of the model and obtain a pattern from the
results. To begin the experiment, the number of empty cells and the maximum
steps in the sudoku grid are limited to 3 and 81 respectively. These are then
gradually incremented as the model trains. As these parameters change over
time, the complexity to solve the problem also increases. However, our result
suggests that NLMs can perfectly confront this complexity and yields 100%
accuracy in most of the cases.

To give a better understanding on how the model performs with different
parameters, we have demonstrated the success rate with respect to each
parameter that the model was trained on. Table 1 shows the comparison and
performance under each setting that is tested on our modified version of the
NLM. The model when tested with the minimum number of empty cells (nr empty) 3
and max steps set to 81, gives a success rate of 0.94. However, when the
maximum number of steps (max steps) are increased from 81 to 150, the model
receives a perfect score of 1.

A similar case is also observed when the model receives 5 empty cells with 81
and 729 max steps. With fewer optimal steps, the model yields a comparatively
lower score as compared to 3 empty cells. However, when the model does not
have a restriction on the maximum number of steps (set to a max of 729), it
performs well and gets 100% accuracy. From this we conclude that success rate
is directly related to the maximum number of steps allowed by the model.
Another inference obtained from Table 2 is that when number of empty cells
increases keeping Max. steps constant, success rate drops. This shows the
inverse relation between success rate and empty cells. Therefore, the success
rate of NLM model is strongly determined by the relation of:

$\textit{Success Rate}\boldsymbol{\propto}\textit{max
steps}*\textit{$\frac{1}{emptycells}$}$ (1)

Figure 3: Comparison of NLM and backtracking convergence time Figure 4:
Separate convergence time for Backtracking and NLM for same problem

In addition to fine-tuning the model, we have also drawn a time complexity
analysis of the NLM with traditional backtracking algorithms for solving
Sudoku puzzles. Both the NLM and backtracking algorithms are provided with the
same set of grids and their time to solve the complete grid is highlighted in
Figure 3. The motivation behind this is to showcase the difference in the
principle working of both the algorithms and analyze their convergence time
(with limited training in the case of NLMs).

#####

The backtracking algorithm takes a constant average time of nearly 0.00045
seconds to solve the same set of 9X9 grids, on the other hand, the NLM takes a
considerably higher amount of time to converge. (It is also worth mentioning
that Figure 3 demonstrates the time taken by the NLM with 729 maximum number
of steps). The reason that backtracking converges faster is due to the fact
that it solves the grid in an optimal number of steps (i.e.,
$MaxStepsBacktracking=NumberOfEmptyCells$). In Figure 3, the peak time in the
case of the NLM denotes the instances in which the environment was reset due
the formation of an invalid configuration of the sudoku grid. During this
instance, the model first receives a negative reward through the reinforcement
module and then resets the environment once there are no possible target
values to test. In this case, the NLM again tries to fill the empty cells but
with a different set of target values from the beginning. However, even with
10 empty cells, our modified version of the NLM always takes less than 2.0
seconds to converge.

##  5 Conclusion and Future Work

The focus of this study is to tackle one of the drawbacks of the traditional
Neural Networks i.e., ‘systematicity’. Where Neural Networks perform poorly,
NLMs can solve some the same task with 100% accuracy. NLMs have been trained
and tested by [5] on various tasks which Deep Learning models have failed to
solve or converge. In our paper, we added to the existing applications of
their architecture and solved a more complex problem to test the robustness of
Neuro Logic Machines.

While the Neuro Logic Machines failed to converge for Sudoku puzzles faster
than the backtracking algorithm, it is evident from this study that a Neuro
Logic Machine can be trained to solve tasks where conventional Deep Learning
models may fail. Lastly, because the NLM receives a random combination of
grids and number empty cells from, we are confident that the high success rate
of NLMs is not due to the model’s over-fitting. Thus, with this experiment, we
have been able to strengthen the argument [5] that NLM can solve tasks with
100% accuracy without relying on over-fitting. In Section 4, we also deduce
that that the success rate is directly associated with the number of empty
cells and the maximum number of steps that model is allowed to take.

To conclude, Neuro Logic Machines can solve complex problems using a hybrid
approach of Reinforcement and Symbolic Learning. In future work, we intend to
cover the fine-tuning and convergence rate of the algorithm. We propose that
the applications of NLMs can be extended further with even more games (e.g.,
Ken Ken puzzles) and mathematical problems (such as search tasks). We also
anticipate that the architecture will cover problems where NLM have not
yielded a success rate of 100%.

##  6 Acknowledgment

We thank Dr. Leake, professor at Indiana University Bloomington, for being our
instructor and guiding us through this experiment and thereby supporting our
work.

###  6.1 Conflict of Interest

The authors declare that they have no conflict of interest.

###  6.2 Funding

The authors received no financial support for the research, authorship, and/or
publication of this article.

## References

  * [1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate, 2016.
  * [2] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  1 2009.
  * [3] Jonathon Cai, Richard Shin, and Dawn Song.  Making neural programming architectures generalize via recursion, 2017\.
  * [4] Xinyun Chen, Chang Liu, and Dawn Song.  Towards synthesizing complex programs from input-output examples, 2018\.
  * [5] Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou.  Neural logic machines, 2019.
  * [6] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour.  Policy gradient methods for reinforcement learning with function approximation.  In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.
  * [7] Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter.  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver, 2019.