\subsection{#1}}
\newcommand{\myparagraph}[1]{\paragraph{#1}}
\newcommand{\newmyparagraph}[1]{\paragraph{#1}}
\newcommand{\vspace{-5pt}\item}{\vspace{-5pt}\item}
\newcommand{\mybf}[1]{\vspace{4pt}\noindent\textbf{#1}}
\newcommand{\mycell}[1]{\begin{tabular}{@{}l@{}l}#1\end{tabular}}
\newcommand{\mycellc}[1]{\begin{tabular}{@{}c@{}l}#1\end{tabular}}
\newcommand\crule[3][black]{\textcolor{#1}{\rule{#2}{#3}}}

 


\newtheorem{example}{Example}
\newtheorem{theorem}{Theorem}





\pdfinfo{
/TemplateVersion (IJCAI.2021.0)
}

\title{Temporal and Object Quantification Networks}


\author{
Jiayuan Mao$^{1*}$\and
Zhezheng Luo$^{1*}$\and
Chuang Gan$^2$\and
Joshua B. Tenenbaum$^1$\and
Jiajun Wu$^3$\and\\
Leslie Pack Kaelbling$^1$\And
Tomer D. Ullman$^4$\\
\affiliations
$^1$Massachusetts Institute of Technology\quad\\
$^2$MIT-IBM Watson AI Lab\quad\\
$^3$Stanford University\quad\\
$^4$Harvard University
}

\begin{document}

\maketitle

\footnotetext{\hspace{-7pt}*: equal contribution; order determined by a coin toss.\par Email: {\{jiayuanm,ezzluo\}@mit.edu}\par Project page: \url{http://toqnet.csail.mit.edu}}

\begin{abstract}



We present {\it Temporal and Object Quantification Networks\xspace} (TOQ-Nets\xspace), a new class of neuro-symbolic networks with a structural bias that enables them to learn to recognize complex relational-temporal events. This is done by including reasoning layers that implement finite-domain quantification over objects and time.   The structure allows them to generalize directly to input instances with varying numbers of objects in temporal sequences of varying lengths.
We evaluate TOQ-Nets\xspace on input domains that require recognizing event-types in terms of complex temporal relational patterns. 
We demonstrate that TOQ-Nets\xspace can generalize from small amounts of data to scenarios containing more objects than were present during training and to temporal warpings of input sequences.
\end{abstract}
 %
\section{Introduction}

\begin{figure*}[t]
    \includegraphics[width=0.9\textwidth]{fig/ltl_teaser_new2.pdf}
    \vspace{-10pt}
    \caption{(a) An input sequence composed of relational states: each column represents the state of an entity that changes over time. A logic formula describes a complex concept or feature that is true of this temporal sequence using object and temporal quantification. The sequence is segmented into three stages: throughout the first stage, \crule[red]{1em}{1em} holds for at least one entity, until the second stage, in which each entity is always either \crule[blue]{1em}{1em} or \crule[green]{1em}{1em}, until the third stage, in which  \crule[yellow]{1em}{1em} eventually becomes true for at least one of the entities. (b) Such events can be described using first-order linear temporal logic expressions.}
    \label{fig:teaser}
    \vspace{-5pt}
\end{figure*} 
Every day, people interpret events and actions in terms of concepts, defined over temporally evolving relations among agents and objects~\cite{zacks2007event,stranger1996perception}. For example, in a soccer game, people can easily recognize when one player has control of the ball, when a player {\it passes} the ball to another player, or when a player is {\it offsides}.  Although it requires reasoning about intricate relationships among sets of objects over time, this cognitive act is effortless, intuitive, and fast. It also generalizes directly over different numbers and arrangements of players, and detailed timings and trajectories.
In contrast, most computational representations of sequential concepts are based on fixed windows of space and time, and lack the ability to perform relational generalization.

In this paper, we develop generalizable representations for learning complex activities in time sequences from realistic data.  As illustrated in \fig{fig:teaser}, we can describe complex events with a first-order linear temporal logic~\citeb{FO-LTL;}{pnueli1977temporal} formula,
which allows us to flexibly decompose an input sequence into stages that satisfy different criteria over time.  Object quantifiers ($\forall$ and $\exists$) are used to specify conditions on sets of objects that define each stage.  
Such representations immediately support generalization to situations with a varying number of objects, and sequences with different time warpings.

More concretely, the variety of complicated spatio-temporal trajectories that {\it high pass} can refer to in a soccer game can be described in these terms:
in a high pass from player $A$ to teammate $B$, $A$ is {\it close} to the ball ($\mathit{distance}(A, \mathit{ball}) < \theta_1$) and moving ($\mathit{velocity}(A) > \theta_2$) {\it until} the ball moves over the ground ($\mathit{z_\textit{position}}(\mathit{ball}) > \theta_3$), which is in turn  {\it until} teammate $B$ gets control of the ball ($\mathit{teammate}(A, B) \wedge \mathit{distance}(B, \mathit{ball}) < \theta_1$). 
Beyond modeling human actions in physical environments, these structures can be applied to events in any time sequence of relational states, e.g\onedot} \def\Eg{E.g\onedot, characterizing particular offensive or defensive maneuvers in board games such as chess or in actual conflicts, or detecting a process of money-laundering amidst financial transaction records. 






In this paper, we propose a neuro-symbolic approach to learning to recognize temporal relational patterns, called {\it Temporal and Object Quantification Networks\xspace} (TOQ-Nets\xspace), in which we design structured neural networks with an explicit bias that represents finite-domain quantification over both entities and time.  
A TOQ-Net\xspace is a multi-layer neural network whose inputs are the properties of agents and objects and their relationships, which may change over time. Each layer in the TOQ-Net\xspace performs either {\it object} or {\it temporal} quantification. 

The key idea of TOQ-Nets\xspace is to use {\it tensors} to represent relations between objects, and to use tensor pooling operations over different dimensions to realize temporal and object quantifiers (\textbf{\textit{G}} and $\forall$).  For example, the colorful matrix in \fig{fig:teaser}(a) can be understood as representing a unary color property of a set of 8 entities over a sequence of 8 time steps. Representing a sequence of relations among objects over time would require a 3-dimensional tensor.
Crucially, the design of TOQ-Nets\xspace allows {\em the same network weights} to be applied to domains with different numbers of objects and time sequences of different lengths.
By stacking object and temporal quantification operations, TOQ-Nets\xspace can easily learn to represent higher-level sequential concepts based on the relations between entities over time, starting from low-level sensory input and supervised with only high-level class labels.

There are traditional symbolic learning or logic synthesis methods that construct first-order or linear temporal logic expressions from accurate symbolic data~\cite{neider2018learning,camacho2018finite,chou2020explaining}.  TOQ-Nets\xspace take a different approach and can learn from noisy data by backpropagating gradients, which allows them to start with a general perceptual processing layer that is directly fed into logical layers for further processing.



We evaluate TOQ-Nets\xspace on two perceptually and conceptually different benchmarks: trajectory-based sport event detection and human activity recognition, demonstrating several important contributions.
First, TOQ-Nets\xspace outperform both convolutional and recurrent baselines for modeling temporal-relational concepts across benchmarks. Second, by exploiting  temporal-relational features learned through supervised learning, TOQ-Nets\xspace achieve strong few-shot generalization to novel actions. Finally, TOQ-Nets\xspace exhibit strong generalization to scenarios with more entities than were present during training and are robust w.r.t\onedot time warped input trajectories. %
These results illustrate the power of combining symbolic representational structures with learned continuous-parameter representations to achieve robust, generalizable interpretation of complex relational-temporal events.



 %
\section{TOQ-Nets\xspace}

\begin{figure*}[!tp]
    \includegraphics[width=0.97\textwidth]{fig/model-overview.pdf}
    \vspace{-5pt}
    \caption{A TOQ-Net\xspace contains three modules: (i) an input feature extractor, (ii) relational reasoning layers, and (iii) temporal reasoning layers.
    %
    To illustrate the model's representational power, we show that logical forms of increasing complexity can be realized by stacking multiple layers.}
    \label{fig:model-overview}
\end{figure*}

 %

The input to a TOQ-Net\xspace is a tensor representation of the properties of all entities at each moment in time. For example, in a soccer game, the input encodes the position of each player and the ball, as well as their team membership at each step of an extended time interval. The output is a label of the category of the sequence, such as the type of soccer play it contains.

The first layer of a TOQ-Net\xspace (\fig{fig:model-overview} (i)) extracts temporal features for each entity with an {\it input feature extractor} that focuses on entity features within a fixed and local time window. These features may be computed, e.g., by a convolutional neural network
or a bank of parametric feature templates.
The output of this step is a collection of nullary, unary, and binary relational features over time for all entities. Throughout the paper we will assume that all output tensors of this layer are binary-valued, but it can be extended directly to real-valued functions. 
This input feature extractor is task-specific and is not the focus of this paper.

Second, these temporal-relational features go through several {\em relational reasoning} layers ({\sc rrl}s), detailed in \sect{sect:relational}, each of which performs linear transformations, sigmoid activation, and {\it object quantification} operations. The linear and sigmoid functions allow the network to realize learned Boolean logical functions, and the object quantification operators can realize quantifiers.  Additional {\sc rrl}s enable deeper nesting of quantified expressions, as illustrated in \fig{fig:model-overview}. All operations in these layers are performed for all time steps in parallel.

Next, the {\sc rrl}s perform a final quantification, computing for each time step a set of a nullary features that are passed to the \textit{temporal reasoning layers} ({\sc trl}s), as detailed in \sect{sect:temporal}. Each {\sc trl} performs linear transformations, sigmoid activation, and {\it temporal quantification}, allowing the model to realize a subset of linear temporal logic~\cite{pnueli1977temporal}.
As with {\sc rrl}s, adding more {\sc trl}s enables the network to realize logical forms with more deeply nested temporal quantifiers.

In the last layer, all object and time information is projected into a set of features of the initial time step,  which summarize the temporal-relational properties of the entire trajectory (e.g., ``the kicker eventually scores''), and fed into a final softmax unit to obtain classification probabilities for the sequence.  

It is important to understand the representational power of this model. The {\it input transformation layer} learns basic predicates and relations that will be useful for defining more complex concepts, but no specific predicates or relations are built into the network in advance. 
The relational reasoning layers build quantified expressions over these basic properties and relations, and might construct expressions that could be interpretable as ``the player is close to the ball.'' Finally, the temporal reasoning layer applies temporal operations to these complex expressions, such as ``the player is close to the ball until the ball moves with high speed.'' Critically, {\it none} of the symbolic properties or predicates are hand defined---they are all constructed by the initial layer in order to enable the network to express the concept it is being trained on.

 TOQ-Nets\xspace are not fully first-order: all quantifiers operate only over the finite domain of the input instance, and can be seen as ``short-hand'' for finite disjunctions or conjunctions over objects or time points.  In addition, the depth of the logical forms it can learn is determined by the fixed depth of the network.
 However, our goal is not to fully replicate temporal logic, but to bring ideas of object and temporal quantification into neural networks, and to use them as structural inductive biases to build models that generalize better from small amounts of data to situations with varying numbers of objects and time courses.

\mysubsection{Temporal-Relational Feature Representation}
TOQ-Nets\xspace use tensors as internal representations between layers;  they represent, all at once, the values of all predicates and relations grounded on all objects at all time points.  The operations in a TOQ-Net\xspace are vectorized, operating in parallel on all objects and times, sometimes expanding the dimensionality via outer products, and then re-projecting into smaller dimensions via max-pooling.
This processing style is analogous to representing an entire graph using an adjacency matrix and using matrix operations to compute properties of the nodes or of the entire graph.
In TOQ-Nets\xspace, the input to the network, as well as the feature output of intermediate layers, is represented as a tuple of three tensors.

Specifically, we use a vector of dimension $D_0$ to represent 
aspects of the state that are global and do not depend on any specific object at each time $t$.  We use a matrix of shape $N \times D_1$ to represent the unary properties of each entity at time $t$, where $N$ is the number of entities and $D_1$ is the hidden dimension size. Similarly, we use a tensor of shape $N \times N \times D_2$ to represent the relations between each pair of entities at time step $t$.
As a concrete example, illustrated in \fig{fig:model-overview}, the number of entities $N$ is the total number of players plus one (the ball). For each entity $x$ and each time step, the inputs are their 3D position, type (ball or player) and team membership. The TOQ-Net\xspace outputs the action performed by the target player. Since there are only entity features, the input trajectory is encoded with a ``unary'' tensor of shape $T \times N \times D_1$, where $T$ is the length of the trajectory. That is, there are no nullary or binary inputs in this case.


\begin{figure*}[!t]
    \centering
    \includegraphics[width=\textwidth]{fig/model.pdf}
    \caption{Illustration of (i) relational reasoning layers and (ii) temporal reasoning layers. We provide two illustrative running traces. (i) The first relational reasoning layer takes unary predicates $q_1$ and $q_2$ as input and its output $Q_1$ is able to represent $q_1 \wedge q_2$. The $\max(Q_1, dim=0)$ in layer 2 can represent $\exists x.~q_1(x, t) \wedge q_2(x, t)$.
    (ii) Assume $P_K$ encodes the occurance of events $e_1$ and $e_2$ at each time step. The first temporal reasoning layer can realize {\it always} $e_2$ with a temporal pooling from time step $3$ to time step $T$. In the second temporal reasoning layer, the temporal pooling summarizes that $e_1$ holds true from time step 1 to 2. Thus, the NN should be able to realize $e_1$ {\it until} ({\it always} $e_2$).
    }
    \vspace{-5pt}
    \label{fig:model}
\end{figure*} 
\mysubsection{Relational Reasoning Layers}
\label{sect:relational}
Our Relational reasoning layers ({\sc rrl}s) follow prior work on Neural Logic Machines \cite{dong2018neural}, illustrated in \fig{fig:model}~(i).
Consider a specific time step $t$. At each layer $l$, the input to a neural logic layer is a 3-tuple $(P_{l-1}, Q_{l-1}, R_{l-1})$, which corresponds to nullary, unary, and binary features respectively. Their shapes are $D_0$, $N \times D_1$, and $N \times N \times D_2$. The output is another 3-tuple $(P_{l}, Q_{l}, R_{l})$, given by
\vspace{-5pt}
\begin{adjustwidth}{0em}{0em}
\small
\begin{eqnarray*}
    P_{l} & = & \mathrm{NN}_P \left( \mathrm{Concat}\left[ P_{l-1} ;\max(Q_{l-1}, \mathrm{dim}=0) \right] \right),\\
    Q_{l} & = & \mathrm{NN}_Q \left( \mathrm{Concat}\left[ Q_{l-1} ; \max(R_{l-1}, \mathrm{dim}=0) ;
    \right.\right.\\ 
    & & \left.\left.\max(R_{l-1}, \mathrm{dim}=1) ; \mathrm{expand}(P_{l-1}, \mathrm{dim}=1) \right] \right),\\
    R_{l} & = & \mathrm{NN}_R \left( \mathrm{Concat}\left[ R_{l-1} ; \mathrm{expand}(Q_{l-1}, \mathrm{dim}=0) ;
    \right.\right.\\ 
    & & \left.\left.\mathrm{expand}(Q_{l-1}, \mathrm{dim}=1) \right] \right).
\end{eqnarray*}
\end{adjustwidth}
where $\mathrm{NN}_{*}$ are single fully-connected layers with sigmoid activations. For unary and binary features, $\mathrm{NN}_Q$ and $\mathrm{NN}_R$ are applied along the feature dimension. That is, we apply the same linear transformation to the unary features of all entities. A different linear transformation is applied to the binary features of all entity pairs.
$\mathrm{Concat}[\cdot~;~\cdot]$ is the concatenation operation, applied to the last dimension of the tensors (the feature dimension).
$\max$, also called the ``reduced'' max operation, takes the maximum value along the given axis of a tensor. The $\mathrm{expand}$ operation, also called ``broadcast,'' will duplicate the input tensor $N$ times and stack them together along the given axis. {\sc rrl}s are applied identically to the input features at every time step $t$. That is, we use the same neural network weights in a {\sc rrl} for all time steps in parallel.

{\sc rrl}s are motivated by relational logic rules in a finite and fully grounded universe.
The $\max$ reduction operations implement a differentiable version of an existential quantifier over the finite universe of individuals, given that the truth values of the propositions are represented as values in $(0.0, 1.0)$. Because preceding and subsequent {\sc rrl}s
can negate propositions as needed, we omit explicit implementation of finite-domain universal quantification, although it could be added by including analogous $\min$ reductions. Thus, as illustrated in \fig{fig:model} (i), given input features $\mathit{q_1}(x, t)$ and $\mathit{q_2}(x, t)$, we can realize the formula $\exists x.~\mathit{q_1}(x, t) \wedge \mathit{q_2}(x, t)$ by stacking two such layers.

Throughout the paper we have been using only nullary, unary, and binary features, but the proposed framework itself can be easily extended to higher-order relational features. From a graph network~\cite{bruna2013spectral,kipf2016semi,battaglia2018relational} point of view, one can treat these features as the node and edge embeddings of a fully-connected graph and the relational reasoning layers as specialized graph neural network layers for realizing object quantifiers.



\mysubsection{Temporal Reasoning Layers}
\label{sect:temporal} 
Temporal reasoning layers ({\sc trl}s) perform {\it quantification} operations similar to relational reasoning layers, but along the {\it temporal} rather than the object dimension. The first {\sc trl} takes as input the summarized event representation produced by the $K$-th relational reasoning layer, $P_{K}^{(t)}$ for at all time steps $t$, as a matrix of shape $T \times D$.
Each {\sc trl} is computed as 
\vspace{-1em}
\begin{adjustwidth}{0em}{0em}
\begin{equation}
    P_{K+l}^{(t)}  = \max_{t' > t} \mathrm{NN}_l \left( \mathrm{Concat}\left[  P_{K+l-1}^{(t')}; \max_{t \le t'' < t'} P_{K+l-1}^{(t'')} \right] \right).
\label{eq:temporallayer}
\end{equation}
\end{adjustwidth}
We will walk through the subexpressions of this formula.
\begin{enumerate}
    \item $P_{K+l-1}$ is the output tensor of the previous temporal reasoning layer, of shape $T \times C$, where $T$ is the number of time steps, and $C$ is the number of feature channels. Each entry in this tensor $P_{K+l-1}^{(t)}\left[i\right]$ can be interpreted as: event $i$ happens at time $t$.
    \item $\left(\max_{t \le t'' < t'} P_{K+l-1}^{(t'')}\right)$, abbreviated as $Q^{(t, t')}_{k+l-1}$ in the following text, is a vector of shape $C$. Its entry $Q^{(t, t')}_{k+l-1}[i]$, where $t \le t'$, represents the concept that event $i$ happens some time between $t$ and $t'$. {\bf Importantly, } together with the preceding and subsequent neural network operations, which can realize negation operations, it also allows us to describe the event that $i$ holds true for all time steps between $t$ and $t'$.
    \item $\mathit{NN}_l$ is a fully connected neural network with sigmoidal activation, which gets uniformly applied to all time steps $t$ and a future time step $t' > t$. Its input is composed of two parts: the events that happen at $t'$, i.e\onedot} \def\Ie{I.e\onedot, $P_{K+l-1}^{(t)}$, and the events that happen between $t$ and $t'$, summarized with temporal quantification operations, i.e\onedot} \def\Ie{I.e\onedot, $\left(\max_{t \le t'' < t'} P_{K+l-1}^{(t'')}\right)$.
    \item The outer-most max pooling operation $\max_{t'>t}$ enumerates over all $t' > t$, and test whether the condition specified by $\mathit{NN}_l$ holds for at least one such $t'$.
\end{enumerate}

A special case is the first temporal reasoning layer. It takes $P_{K}$ as its input, which is the output of last relational reasoning layer. Thus, the first temporal reasoning layer implements:
\vspace{-1em}
\begin{adjustwidth}{0em}{0em}
\begin{eqnarray*}
    P_{K+1}^{(t)}  = \mathrm{NN}_1 \left(\max_{t \le t'' < T} P_{K}^{(t'')} \right),
\end{eqnarray*}
\end{adjustwidth}
where $T$ is the sequence length. Note that there is no enumeration for a future time step $t' > t$ involved. In addition, for all temporal layers, we add residual connections by concatenating their inputs with the outputs.

Next, let's consider a running example illustrating how a TOQ-Net\xspace can recognize the event that: event $p$ holds true until event $q$ becomes always true. In LTL, this can be written as $p \textit{\textbf{U}} (\textit{\textbf{G}} q)$. Using the plain first-order logic (FOL) language, we can describe it as: $\exists~t. \left[ \forall t'.~(0 \le t' < t) \implies p(t') \right) \wedge \left( \forall t'.~(t' \ge t) \implies q(t') \right]$.

For simplicity, we consider a tensor representation for two events $p(t)$ and $q(t)$, where $p(t) = 1$ if it happens at time step $t$ and $p(t) = 0$ otherwise. Given the input sequence of length 4 in \tbl{tab:temporalexample} ($p(t)$ and $q(t)$), the first layer is capable of computing the following four properties for each time step $t$: $\textit{\textbf{G}}p$ ($\textit{\textbf{always}}~p$), which is true if $p$ holds true for all future time steps starting from $t$, $\textit{\textbf{F}}p$ ($\textit{\textbf{eventually}}~p$), which is true if $p$ is true for at least one time step starting from $t$, and similarly, $\textit{\textbf{G}}q$ ($\textit{\textbf{always}}~q$) and $\textit{\textbf{F}}q$ ($\textit{\textbf{eventually}}~q$). Overall, together with residual connections, the first layer can recognize six useful events: $p(t)$, $q(t)$ (from residual connection), $\textit{\textbf{G}}p$, $\textit{\textbf{F}}p$, $\textit{\textbf{G}}q$, and $\textit{\textbf{F}}q$ (by temporal quantification, i.e\onedot} \def\Ie{I.e\onedot pooling operations along the temporal dimension). 

\begin{table}[!tp]
    \centering
    \setlength{\tabcolsep}{7pt}
    \small
    \begin{tabular}{l|cc|cccc|c}
    \toprule
        & \multicolumn{2}{c}{Input} &  \multicolumn{4}{|c|}{1-st Layer} &  \multicolumn{1}{c}{2-nd Layer}\\
        $t$ & $p(t)$ & $q(t)$ & \textit{\textbf{G}}$p$ & \textit{\textbf{F}}$p$ & \textit{\textbf{G}}$q$ & \textit{\textbf{F}}$q$ & $p$~\textit{\textbf{U}}~(\textit{\textbf{G}}$q$) \\ \midrule
        1 & T & T & F & T & F & T & T \\
        2 & T & F & F & T & F & T & T \\
        3 & F & T & F & F & T & T & F \\
        4 & F & T & F & F & T & T & F \\
    \bottomrule
    \end{tabular}
    \caption{A running example of different temporal quantification formulas that TOQ-Nets\xspace can realize. For clarity, we use T and F for True/False. In the actual computation, they are ``soft'' Boolean values ranges in $[0, 1]$. \textbf{G} means \textit{\textbf{always}}; \textbf{F} means \textit{\textbf{Eventually}}; \textbf{U} means \textit{\textbf{until}}.}
    \label{tab:temporalexample}
\end{table}

\begin{algorithm}[!tp] 
\caption{An example temporal structure that the second temporal reasoning layer can recognize.}
\label{alg:secondlayer}
\begin{algorithmic}[1]
\Require{$p(t)$, $q(t)$, $(\textit{\textbf{G}}p)(t)$, $(\textit{\textbf{F}}p)(t)$, $(\textit{\textbf{G}}q)(t)$, and $(\textit{\textbf{F}}q)(t)$} 
\Ensure{$\left(p\textit{\textbf{U}} (\textit{\textbf{G}} q))\right)(t)$, which is {\it true} if $p$ holds {\it true} from time step $t$ until $q$ becomes always {\it true}.}

\For{$t \gets 1$ to $T$}
  \For{$t' \gets t + 1$ to $T$}
    \If{$\forall t'' \in [t, t').~p(t'')$ and $(\textit{\textbf{G}}q)(t')$}
      \State $\left(p\textit{\textbf{U}} (\textit{\textbf{G}} q))\right)(t) \gets \mathit{true}$
    \EndIf
  \EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

The second layer can realize the computation depicted in Algorithm~\ref{alg:secondlayer}. For every time step $t$, it enumerates all $t' > t$ and computes the output based on
\begin{enumerate}
    \item the events at $t'$ (represented as $P^{(t')}_{K+l-1}$ in \eqn{eq:temporallayer}, concretely the $(\textit{\textbf{G}}q)(t')$ in the Algorithm~\ref{alg:secondlayer} example), and
    \item the state of another event between $t$ and $t'$ (represented as $\left(\max_{t \le t'' < t'} P_{K+l-1}^{(t'')}\right)$ in \eqn{eq:temporallayer}, concretely the $\forall t''\in[t,t').~p(t'')$ in the Algorithm~\ref{alg:secondlayer} example).
\end{enumerate}

From the perspective of First-Order Linear Temporal Logic (FO-LTL), stacking multiple temporal reasoning layers enables us to realize FO-LTL formulas such as:
\[ p_1~\textit{\textbf{U}}~p_2~\textit{\textbf{U}}~p_3~\textit{\textbf{U}}~\cdots~\textit{\textbf{U}}~p_k, \]
which is interpreted as $p_1$ holds true until $p_2$ becomes true and $p_2$ holds true from that until $p_3$ becomes true $\cdots$, and
\[ \textit{\textbf{F}} p_1~\textit{\textbf{XF}}~p_2~\textit{\textbf{XF}}~p_3~\textit{\textbf{XF}}~\cdots~\textit{\textbf{XF}}~p_k, \]
which is interpreted as $p_1$ eventually becomes true and after that $p_2$ eventually becomes true and after that $\cdots$, and in addition, formulas with interleaved until and eventually quantifiers. Here, $\textit{\textbf{XF}}$ is a composition of the ne\textit{\textbf{X}}t operator and the \textit{\textbf{F}}inally operator in LTL. Meanwhile, as described so far, TOQ-Nets\xspace can only nest object quantification inside temporal quantification, so it can represent
\textbf{\textit{always}} $\exists x.~q_1(x) \wedge q_2(x)$, but not $\exists x.~\textbf{\textit{always}}\; q_1(x) \wedge q_2(x)$. This can be solved by interleaving relational and temporal reasoning layers.

It is important to notice that, by using object and temporal pooling operations together with trainable neural networks to realize logic formulas with object and temporal quantifiers, the idea itself generalizes to a broader set of FO-LTL formulas. We design TOQ-Nets\xspace to model only a subset of FO-LTL formulas, because they can be computed efficiently (with only $O(T^2)$ space) and they are expressive enough for the type of data we are trying to model.














 %
\section{Experiments}

We compare our model with other approaches to object-centric temporal event detection in this section,
and include an application of TOQ-Nets\xspace to concept learning over robot object-manipulation trajectories in the supplementary material.
The setups and metrics focus on data efficiency and generalization.

\mysubsection{Baseline Approaches}
We compare TOQ-Nets\xspace against five baselines. The first two are spatial-temporal graph convolutional neural networks \citeb{STGAN;}{yan2018spatial} and its variant STGCN-MAX, which models entity relationships with graph neural networks and models temporal structure with temporal-domain convolutions. The third is STGCN-LSTM, which uses STGCN layers for entity relations but LSTM~\cite{hochreiter1997long} for temporal structures. The last two baselines are based on space-time graphs: Space-Time Graph~\cite{wang2018videos} and Non-Local networks~\cite{wang2018non}. We provide details about our implementation and how we choose the model configurations in the supplementary material.

\mysubsection{Trajectory-Based Soccer Event Detection}

We start our evaluation with an event-detection task in soccer games. The task is to recognize the action performed by a specific player at specific time step in a soccer game trajectory.

\begin{table}[!tp]
\vspace{0pt}
    \centering\small
    \setlength{\tabcolsep}{10.5pt}
    %
    \begin{tabular}{lccc}
    \toprule
        Model & Reg. & Few-Shot  & Full  \\ \midrule
        %
        %
        %
        %
        %
        %
        STGCN & 73.2$_{\pm 1.6}$ & 26.0$_{\pm 5.7}$ & 62.8$_{\pm 0.6}$ \\
        STGCN-MAX & 73.6$_{\pm 1.5}$ & 28.6$_{\pm 5.0}$ & 63.6$_{\pm 0.7}$ \\
        STGCN-LSTM & 72.7$_{\pm 1.4}$ & 23.8$_{\pm 5.9}$ & 61.9$_{\pm 0.6}$ \\
        Space-Time & 74.8$_{\pm 1.5}$ & 31.7$_{\pm 6.1}$ & 65.2$_{\pm 0.6}$ \\
        Non-Local & 76.5$_{\pm 2.4}$ & 45.0$_{\pm 6.3}$ & 69.5$_{\pm 2.4}$ \\
        TOQ-Net\xspace (ours) & \textbf{87.7$_{\pm 1.3}$} & \textbf{52.2$_{\pm 6.3}$} & \textbf{79.8$_{\pm 0.8}$} \\
        %
        %
    \bottomrule
    \end{tabular}
    \vspace{-5pt}
        \captionof{table}{Results on the soccer event dataset. Different columns correspond to different action sets (the regular, few-shot, and full action sets). The performance is measured by per-action (macro) accuracy, averaged over nine few-shot splits. The ${\pm}$ values indicate standard errors. TOQ-Net\xspace significantly outperforms all baseline methods on the few-shot action set.}
        \label{tab:gfootball}
\end{table}


    %
 
\newmyparagraph{Dataset and setup.}
We collect training and evaluation datasets based on the gfootball simulator\footnote{\url{https://research-football.dev/}}, which provides a physics-based 3D football simulation. It also provides AI agents that can be used to generate random plays.
The simulator provides the 3D coordinates of the ball and the players as well as the action each player is performing at each time step. There are in total 13 actions defined in the simulator, including \textit{movement, ball\_control, trap, short\_pass, long\_pass, high\_pass, header, shot, deflect, catch, interfere, trip} and \textit{sliding}. 
We exclude \textit{header} and \textit{catch} actions, as they never appear in AI games. We also exclude \textit{ball\_control} and \textit{movement}, since they just mean the agent is moving (with or without the ball). Thus, in total, we have nine action categories. We run the simulator with AI-controlled players to generate plays, and formulate the task as classifying the action (9-way classification) of a specific player at a specific time step given a temporal context (25 frames). For each action, we have generated 5,000 videos, expect for \textit{sliding}, for which we generated 4,000 videos because it is rare in the AI games. Among the generated examples, 62\% (2,462 or 3,077) are used for training, 15\% are used for validation, and 23\% are used for testing. Each trajectory is an 8-fps replay clip that contains 17 frames (about two seconds). There is a single ``target'' player in each trajectory. The action label of the trajectory is the action performed by this target player at frame \#9. We randomly split all actions into two categories: seven ``regular'' actions, for which all game plays are available, and two ``few-shot'' actions, for which only 50 clips are available during training. 

\begin{table*}
    \centering\small
    \begin{tabular}{lccccccc}
    \toprule
        Model   & 3v3 & 4v4 & 6v6 & 6v6 \scriptsize{(Time Warp)} & 8v8 & 11v11  \\ \midrule
STGCN &\cellcolor{yellow!25}{\mycellc{40.7$_{\pm 1.0}$~~{\scriptsize (-40.4\%)}}}  & \cellcolor{yellow!25}{\mycellc{63.2$_{\pm 4.9}$~~{\scriptsize (-7.4\%)}}}  & {\mycellc{68.2$_{\pm 2.8}$}} & \cellcolor{blue!5}{\mycellc{52.8$_{\pm 7.0}$~~{\scriptsize (-22.6\%)}}}  & \cellcolor{yellow!25}{\mycellc{55.4$_{\pm 3.3}$~~{\scriptsize (-18.8\%)}}}  & \cellcolor{yellow!25}{\mycellc{44.4$_{\pm 2.1}$~~{\scriptsize (-34.9\%)}}} \\
STGCN-MAX & \cellcolor{yellow!25}{\mycellc{47.4$_{\pm 3.2}$~~{\scriptsize (-33.7\%)}}}  & \cellcolor{yellow!25}{\mycellc{68.8$_{\pm 2.0}$~~{\scriptsize (-3.8\%)}}}  & {\mycellc{71.5$_{\pm 1.9}$}} & \cellcolor{blue!5}{\mycellc{56.5$_{\pm 4.5}$~~{\scriptsize (-21.0\%)}}}  & \cellcolor{yellow!25}{\mycellc{59.1$_{\pm 0.7}$~~{\scriptsize (-17.3\%)}}}  & \cellcolor{yellow!25}{\mycellc{45.6$_{\pm 2.5}$~~{\scriptsize (-36.2\%)}}} \\
STGCN-LSTM & \cellcolor{yellow!25}{\mycellc{39.7$_{\pm 1.1}$~~{\scriptsize (-43.1\%)}}}  & \cellcolor{yellow!25}{\mycellc{60.4$_{\pm 0.2}$~~{\scriptsize (-13.5\%)}}}  & {\mycellc{69.8$_{\pm 0.1}$}} & \cellcolor{blue!5}{\mycellc{30.6$_{\pm 0.6}$~~{\scriptsize (-56.1\%)}}}  & \cellcolor{yellow!25}{\mycellc{55.8$_{\pm 2.0}$~~{\scriptsize (-20.0\%)}}}  & \cellcolor{yellow!25}{\mycellc{44.1$_{\pm 0.7}$~~{\scriptsize (-36.8\%)}}} \\
Space-Time & \cellcolor{yellow!25}{\mycellc{29.0$_{\pm 1.6}$~~{\scriptsize (-60.4\%)}}}  & \cellcolor{yellow!25}{\mycellc{53.5$_{\pm 3.2}$~~{\scriptsize (-27.0\%)}}}  & {\mycellc{73.3$_{\pm 0.3}$}}  & \cellcolor{blue!5}{\mycellc{70.7$_{\pm 0.3}$~~{\scriptsize (-3.5\%)}}} & \cellcolor{yellow!25}{\mycellc{33.9$_{\pm 2.8}$~~{\scriptsize (-53.7\%)}}}  & \cellcolor{yellow!25}{\mycellc{15.2$_{\pm 1.8}$~~{\scriptsize (-79.3\%)}}} \\
Non-Local & \cellcolor{yellow!25}{\mycellc{45.9$_{\pm 5.1}$~~{\scriptsize (-41.2\%)}}}  & \cellcolor{yellow!25}{\mycellc{70.7$_{\pm 5.3}$~~{\scriptsize (-9.5\%)}}}  & {\mycellc{78.1$_{\pm 5.8}$}} & \cellcolor{blue!5}{\mycellc{77.7$_{\pm 5.0}$~~{\scriptsize (-0.5\%)}}}  & \cellcolor{yellow!25}{\mycellc{58.5$_{\pm 10.8}$~~{\scriptsize (-25.1\%)}}}  & \cellcolor{yellow!25}{\mycellc{41.8$_{\pm 13.6}$~~{\scriptsize (-46.5\%)}}} \\
TOQ-Net\xspace & \cellcolor{yellow!25}{\mycellc{\bf 77.4$_{\pm 3.5}$~~{\scriptsize (-12.4\%)}}}  & \cellcolor{yellow!25}{\mycellc{\bf 88.3$_{\pm 0.7}$~~{\scriptsize (-0.0\%)}}}  & {\mycellc{\bf 88.4$_{\pm 0.6}$}} & \cellcolor{blue!5}{\mycellc{\bf 86.9$_{\pm 0.4}$~~{\scriptsize (-1.7\%)}}}  & \cellcolor{yellow!25}{\mycellc{\bf 81.3$_{\pm 1.7}$~~{\scriptsize (-8.0\%)}}}  & \cellcolor{yellow!25}{\mycellc{\bf 77.1$_{\pm 1.7}$~~{\scriptsize (-12.8\%)}}} \\
    \bottomrule
    \end{tabular}
    \vspace{-5pt}
    \caption{Results on generalization to scenarios with more agents and temporally warped trajectories on the soccer event dataset.
    All models are trained only on 6v6 games. The standard errors indicated by the $\pm$ signs are computed with three random seeds.
    %
    %
    }
    \label{tab:gfootball-generalization}
\end{table*}




    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
    %
  
\newmyparagraph{Input features.}
Each trajectory is represented with 7 time-varying unary predicates, including the 3D coordinate of each player and the ball and four extra predicates defining the type of each entity $x$: $\mathrm{IsBall}(x)$, $\mathrm{IsTargetPlayer}(x)$, $\mathrm{SameTeam}(x)$, $\mathrm{OpponentTeam}(x)$, where $\mathrm{SameTeam}(x)$ and $\mathrm{OpponentTeam}(x)$ indicates whether $x$ is of the same team as the target player. We also add a temporal indicator function which is a Gaussian function centered at frame of interest with variance $\sigma^2=25$.

\newmyparagraph{Results.}
\tbl{tab:gfootball} shows the result. Our model significantly outperforms all the baselines in all three action settings,  suggesting that our model is able to discover a set of useful features at both input and intermediate levels and use them to compose new action classifiers from only a few examples.




\newmyparagraph{Generalization to more players.} Due to their object-centric design, TOQ-Nets\xspace can generalize to soccer games with a varying number of agents. After training on 6v6 soccer games (i.e\onedot} \def\Ie{I.e\onedot, 6 players on each team), we evaluate the performance of different models on games with different numbers of players: 3v3, 4v4, 8v8, and 11v11.
For each action we have generated, on average, 1,500 examples for testing. \tbl{tab:gfootball-generalization} summarizes the result and the full results are provided in the supplementary material.
Comparing the columns highlighted in yellow, we notice a significant performance drop for all baselines while TOQ-Net\xspace performs the best.
By visualizing data and predictions, we found that misclassifications of instances of {\it shot} as {\it short pass} contribute most to the performance degradation of our model when we have more players. Specifically, the recall of {\it shot} drops from 97\% to 60\%. In soccer plays with many agents, a shot is usually unsuccessful and a player from another team steals the ball in the end. In such scenarios, TOQ-Net\xspace tends to misclassify such trajectories as a {\it short pass}. Ideally, this issue should be addressed by understanding actions based on agents' goals instead of the actual outcome~\cite{intille2001recognizing}. We leave this extension as a future direction.



\newmyparagraph{Generalization to temporally warped trajectories.} Another crucial property of TOQ-Nets\xspace is to recognize actions based on their sequential order in the input trajectory, instead of binding features to specific time steps in the trajectory. To show this, we test the performance of different models on time warped trajectories. Each test trajectory has a length of 25, and each trajectory is labeled by the action performed by the target player at any time step between the 6-th and 19-th frame. We ensure that the target player performs only one action during the entire input trajectory. Thus, the label is unambiguous.
The results are shown in \tbl{tab:gfootball-generalization}. Specifically, our test set consists of 25-frame trajectories, and the action may occur at anytime between the 6th and the 19th frame. By comparing rows with and without time warping, we notice a $60\%$ performance drop for STGCN, STGCN-MAX, and STGCN-LSTM. In contrast, TOQ-Nets\xspace still have reasonable performance. Note that Space-Time and Non-Local model have almost no performance drop against time warping because they are completely agnostic to temporal ordering.


\mysubsection{Extension to Real-World Datasets}
The proposed TOQ-Net\xspace can also be extended to other real-world datasets. %
These examples further illustrate the robustness of TOQ-Net to temporal variations in activities.

\subsubsection{Toyota Smarthome}
Toyota Smarthome~\cite{das2019toyota} is a dataset that contains videos of humans performing everyday activities such as ``walk'', ``take pills'', and ``use laptop''. It also comes with 3D-skeleton detections. There are around 16.1k videos in the dataset, and 19 activity classes. The videos’ length varies between a few seconds to 3 minutes. We subsample 30 frames for each video. We split frames into training (9.9k), validation (2.5k), and testing (3.6k). We treat human joints as entities. The input is then the position of joints, the velocity of joints, limb lengths, and joint angles. We evaluated our model and STGCN on a 19-way classification task. We also test model performance on time-warped sequences by accelerating the trajectories by two times.




Our model achieves a comparable accuracy to STGCN on the standard classification task: (42.0\% vs. 43.0\%). Importantly, on the generalization test to time-warped sequences, our model has only a 0.8\% performance drop (41.2\%), while STGCN drops 10.7\% (32.3\%). This indicates that the temporal structures learned by TOQ-Net\xspace improve model generalization to varying time courses.

\subsubsection{Volleyball Activity}
The volleyball dataset~\cite{msibrahi2016deepactivity} contains 4830 video clips collected from 55 youtube volleyball videos. They are labeled with 8 group activities (e.g. “left spike” and “right pass”). Each video contains 20 frames with the labeled group activity performed at the 10-th frame. The dataset also includes annotations for players, including the bounding box, the indicator of whether the player is involved in the group activity, and the individual action such as ``setting'', ``digging'', and ``spiking''. We use the manual annotations (processed by an MLP) as the input features. We train models to classify the video into one of the eight group activities, following the original split, i.e., 24, 15, and 16 of 55 videos are used for training, validation, and testing.



On the standard classification task, TOQ-Net achieves a comparable performance with STGCN (73.3\% vs. 73.6\%). When we perform time warping on the input sequences, STGCN’s performance drops by more than 25.0\% (39.5\% on temporally shifted trajectories and 48.6\% on 2$\times$ quick motion trajectories), while our model drops only 3\% (70.3\% on temporally shifted trajectories and 70.7\% on quick motion trajectories). This again shows the generalization ability of TOQ-Net w.r.t\onedot varying time courses, and the robustness of learned temporal structures.

\iffalse
\mysubsection{Skeleton-based Activity Recognition}
\jiayuan{Given that we may drop this dataset in the end, I will stop editing it}
The second benchmark that we use for evaluation is Toyota Smarthome, a skeleton-based action recognition dataset. It contains real-world videos recorded in an apartment where human subjects will perform different household actions.

\begin{table}[]
    \caption{Results on the Toyota Smarthome dataset for skeleton-based action recognition. Different columns correspond to different action set (the regular actions set, the few-shot action set, and the full action set). In each cell we show both of the micro average accuracy and the macro average accuracy. Our model TOQ-Net\xspace achieves a comparable results with the baselines on the regular action set and surpass them by a significant margin in the few-shot learning setting. The results with STGCN as the feature extractor shows that our model can be integrated with convolutional neural networks as local feature extractors to perform temporal-relational reasoning.}
    \vspace{5pt}
    \centering\small
    \begin{tabular}{llccc}
    \toprule
        Model & Feature & \mycellc{Reg.\\Micro/Macro} & \mycellc{Few-Shot\\Micro/Macro}  & \mycellc{Full \\Micro/Macro}  \\ \midrule
        STGCN~\cite{yan2018spatial} & * & 40.6 / 38.9 & 23.9 / 21.6 & 35.8 / 36.1 \\
        \midrule
        %
        %
        %
        TOQ-Net\xspace & Human-defined feature & ??.? / ??.? & ??.? / ??.? & ??.? / ??.? \\
        TOQ-Net\xspace & MLP feature           & ??.? / ??.? & ??.? / ??.? & ??.? / ??.? \\
        TOQ-Net\xspace & STGCN feature         & ??.? / ??.? & ??.? / ??.? & ??.? / ??.? \\
    \bottomrule
    \end{tabular}
    \label{tab:smarthome}
\end{table} 
\myparagraph{Dataset and setup.}
Toyota Smarthome dataset contains 19 actions in total. In each video, there is a single person performing different household actions such as drinking water or using a laptop. We only use the 3D skeleton of the person as the model input.

Following the same evaluation metric as in the soccer play dataset, we split the action set into two subsets: regular actions and few-shot actions. For each regular action, on the average 500 video clips will be available for the model while for few-shot actions, there will be only 25 videos. We report the classifications on both the regular action set and the full action set.

\myparagraph{Baselines.}
We again compare our model with the STGCN model, which was originally designed for skeleton-based action recognition. We follow the original STGCN design where the edges in the graph are pre-defined human joint connections (e.g\onedot} \def\Eg{E.g\onedot, the limbs of the human). For TOQ-Net\xspace, we input the binary joint connectivity as a binary feature in the model input.

\myparagraph{Results.}
The results are summarized in \tbl{tab:smarthome}. TOQ-Net\xspace outperforms the baseline with a significant margin, especially on the full action classification benchmark.
\fi %
\section{Related Work}

\newmyparagraph{Action concept representations and learning.}
First-order and linear temporal logics~\citeb{LTL;}{pnueli1977temporal}
have been used for analyzing sporting events~\cite{intille1999framework,intille2001recognizing} and activities of daily living~\cite{tran2008event,brendel2011probabilistic} in logic-based reasoning frameworks. However, these frameworks require extra knowledge to annotate relationships between low-level, primitive actions and complex ones, or performing search in a large combinatorial space for candidate temporal logic rules~\cite{penning2011nsca,lamb2007connectionist}. By contrast, TOQ-Nets\xspace enable end-to-end learning of complex action descriptions from sensory input with only high-level action-class labels. 








\newmyparagraph{Temporal and relational reasoning.} 
This paper is also related to work on using data-driven models for modeling relational and temporal structure, such as LTL ~\cite{neider2018learning,camacho2018finite,chou2020explaining}, Logical Neural Networks~\cite{riegel2020logical}, ADL description languages~\cite{intille1999framework}, and hidden Markov models~\cite{tang2012learning}. These models need human-annotated action descriptions and symbolic state variables (e.g\onedot} \def\Eg{E.g\onedot, {\it pick up} $x$ means a state transition from not {\it holding} $x$ to {\it holding} $x$), and dedicated inference algorithms such as graph structure learning. In contrast, TOQ-Nets\xspace have an end-to-end design, and can be integrated with other neural networks.
People have also used structural representations to model object-centric temporal concepts with graph neural networks~\citeb{GNNs;}{yan2018spatial}, recurrent neural networks~\citeb{RNNs;}{msibrahi2016deepactivity}, and integrated GNN-RNN architectures \cite{deng2016sim,qi2018stag}.
TOQ-Nets\xspace use a similar relational representation, but different models for temporal structures.

 %
\section{Conclusion and Discussion}
The design of TOQ-Nets\xspace suggests multiple research directions. For example, the generalization of the acquired action concepts to novel object kinds, such as from {\it opening fridges} to {\it opening bottles}, needs further exploration. Meanwhile, TOQ-Nets\xspace are based on physical properties, e.g\onedot} \def\Eg{E.g\onedot 6D poses. Incorporating representations of mental variables such as goals, intentions, and beliefs can aid in action and event recognition~\cite{baker2017rational,zacks2001perceiving,vallacher1987people}.

In summary, we have presented TOQ-Nets\xspace, a neuro-symbolic architecture for learning to describe complex state sequences with quantification over both entities and time.  TOQ-Nets\xspace use tensors to represent the time-varying properties and relations of different entities, and use tensor pooling operations over different dimensions to realize temporal and object quantifiers. 
TOQ-Nets\xspace generalize well to scenarios with varying numbers of entities and time courses.

 
\section*{Acknowledgements} We thank Tom\'as Lozano-P\'erez for helpful discussions and suggestions. We gratefully acknowledge support from the Center for Brains, Minds and Machines (NSF STC award CCF1231216), ONR MURI N00014-16-1-2007, NSF grant 1723381, AFOSR grant FA9550-17-1-0165, ONR grant N00014-18-1-2847, the Honda Research Institute, MIT-IBM Watson Lab, SUTD Temasek Laboratories, the Samsung Global Research Outreach (GRO) Program, and the Stanford Institute for Human-Centered AI (HAI). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of our sponsors.

\clearpage


{
\bibliographystyle{named}

\subsection{#1}}
\newcommand{\myparagraph}[1]{\paragraph{#1}}
\newcommand{\newmyparagraph}[1]{\paragraph{#1}}
\newcommand{\vspace{-5pt}\item}{\vspace{-5pt}\item}
\newcommand{\mybf}[1]{\vspace{4pt}\noindent\textbf{#1}}
\newcommand{\mycell}[1]{\begin{tabular}{@{}l@{}l}#1\end{tabular}}
\newcommand{\mycellc}[1]{\begin{tabular}{@{}c@{}l}#1\end{tabular}}
\newcommand\crule[3][black]{\textcolor{#1}{\rule{#2}{#3}}}

 
\title{Supplementary Material for\\Temporal and Object Quantification Networks}

\author{
Jiayuan Mao$^{1*}$\and
Zhezheng Luo$^{1*}$\and
Chuang Gan$^2$\and
Joshua B. Tenenbaum$^1$\and
Jiajun Wu$^3$\and\\
Leslie Pack Kaelbling$^1$\And
Tomer D. Ullman$^4$\\
\affiliations
$^1$Massachusetts Institute of Technology\quad\\
$^2$MIT-IBM Watson AI Lab\quad\\
$^3$Stanford University\quad\\
$^4$Harvard University
}

\begin{document}

\maketitle

We start from inrtoducing a new dataset  we collected for model evaluation, namely the RLBench dataset (\sectapp{app:rlbench}). We then provide implementation details of different models in \sectapp{app:implementation}. Finally, in \sectapp{app:additional}, we present additional ablation studies and visualizations.

