# Transformers are Universal Predictors

Sourya Basu  Moulik Choraria  Lav R. Varshney

###### Abstract

We find limits to the Transformer architecture for language modeling and show
it has a universal prediction property in an information-theoretic sense. We
further analyze performance in non-asymptotic data regimes to understand the
role of various components of the Transformer architecture, especially in the
context of data-efficient training. We validate our theoretical analysis with
experiments on both synthetic and real datasets.

Causal inference, discontinuity regression, dynamic programming, quantization
theory, reinforcement learning

##  1 Introduction

Language models that aim to predict the next token or word to
continue/complete a prompt have their origins in the work of Shannon (1948,
1950, 1951). In recent years, neural language models have taken the world by
storm, especially the Transformer architecture (Vaswani et al., 2017).
Following work on other neural network architectures (Cybenko, 1989), one can
show that the Transformer architecture has a _universal approximation_
property for sequence-to-sequence functions (Yun et al., 2020).

Transformer architectures have excellent performance and parallelization
capability on natural language processing (NLP) tasks, becoming central to
several state-of-the-art models including GPT-4 (OpenAI, 2023) and PaLM 2
(Anil et al., 2023). Such large language models (LLMs) are not only very good
at the statistical problem of predicting the next token, but also have
emergent capabilities in tasks that seemingly require higher-level semantic
ability (Wei et al., 2022). Moreover, transformer-based architectures have
achieved tremendous attention on domains beyond NLP, such as images
(Dosovitskiy et al., 2020), audio (Li et al., 2019), reinforcement learning
(Chen et al., 2021), and even multi-modal tasks (Jaegle et al., 2021).
Transformers also show cross-domain transfer learning capabilities, i.e.,
models trained on NLP tasks show good performance when fine-tuned for non-NLP
tasks such as image processing. In this sense, the Transformer architecture is
said to have a _universal computation_ property (Lu et al., 2021), reminiscent
of predictive coding hypotheses of the brain that posit one basic operation in
neurobiological information processing (Golkar et al., 2022).

The basic predictive workings of Transformers and previous findings of
universal approximation and computation properties motivate us to ask whether
they also have a _universal prediction_ property in the information-theoretic
sense (Feder et al., 1992; Weissman & Merhav, 2001), which itself is well-
known to be intimately related to universal data compression (Merhav & Feder,
1998). As far as we know, the predictive capability of Transformers has not
been studied in an information-theoretic sense, cf. Gurevych et al. (2022).

We investigate not only the underlying mathematical principles that govern the
performance of Transformers, but also aim to find limitations to their
learning capabilities. We show that Transformers are indeed universal
predictors, i.e. they can achieve information-theoretic limits asymptotically
in the amount of data available. We also analyze their performance in the
finite-data regime by understanding the role of various components of the
Transformer architecture, providing theoretical explanations wherever
applicable.

To summarize our main results, we find the limits to performance of
Transformers and show they are optimal predictors. Our limits only assume the
Markov nature of data and are otherwise universal. Moreover, we analyze the
role of the major components of a Transformer and provide better understanding
and directions for their data-efficient training. Finally, we validate our
theoretical analysis by performing experiments on both synthetic and real
datasets.

##  2 Definitions and Preliminaries

###  2.1 Finite-State Markov Processes (FSMPs)

Let $x=\\{x_{1},\ldots x_{n}\\}\in\mathcal{X}^{n}$ be sequential data, where
$\mathcal{X}$ is some finite set. The state sequence of an FSMP,
$s=\\{s_{1},\ldots,s_{n-1}\\}$, is generated recursively according to
$s_{i}=g(x_{i},\ldots,x_{(i-k+1)_{+}})$, where $g(\cdot)$ is the state
function for this FSMP, $s_{i}\in\mathcal{S}$, and $(i)_{+}=\max{\\{i,1\\}}$.
An FSMP has a predictor function $f(\cdot)$ that outputs a probability
distribution over possible values for $x_{i+1}$, i.e.
$\hat{x}_{i+1}=f(s_{i})\in\mathbb{R}^{|\mathcal{X}|}$,
$\sum_{j}f(s_{i})_{j}=1$. Hence, a FSMP is given by the pair $(g,f)$.

###  2.2 Transformers

A Transformer architecture consist of three components placed in a series: an
input embedding layer, multiple attention layers, and an output projection
matrix. Let us describe each of the subcomponents of a Transformer.

#### Input embedding layer

Let the input be sequential data $x=\\{x_{1},\ldots
x_{n-1}\\}\in\mathcal{X}^{n-1}$. The embedding layer $E$ processes the input
sequence individually to give a sequence $z=\\{z_{1},\ldots
z_{n-1}\\}\in\mathbb{R}^{(n-1)\times d_{in}}$.

#### Attention layer

The attention layer further consists of two subcomponents: the self attention
mechanism and the position-wise feedforward network.

The masked self-attention layer takes input
$X=[x_{1},x_{2},\ldots,x_{n-1}]^{\text{T}}\in\mathbb{R}^{(n-1)\times d_{in}}$.
Queries ($Q$), keys ($K$), and values ($V$) are computed from $X$ by
multiplying with three corresponding matrices as $Q=XW_{Q},K=XW_{K}$, and
$V=XW_{V}$, where each matrix $W_{Q},W_{K}$, and $W_{V}$ is of dimension
$d_{in}\times d_{model}$. The output of the self-attention layer,
$H^{(0)}=[h^{(0)}_{1},h^{(0)}_{2},\ldots,h^{(0)}_{n-1}]$ is given by

$\displaystyle H^{(0)}$
$\displaystyle=\text{Attention}(Q,K,V)=\text{softmax}(\text{mask}_{-\infty}(\frac{QK^{\text{T}}}{\sqrt{d_{model}}}))V,$

where mask-∞ is the causal binary mask used to preserve the auto-regressive
property of language modeling by ensuring $h^{(0)}_{i}$ depends only on
$x_{j\leq i}$ by setting all the entries in the matrix $QK^{\text{T}}$
corresponding to connections to $x_{j>i}$ to $-\infty$.

This attention mechanism is extended to multi-head attention with $m$ heads by
simply dividing the inputs of dimension $d_{model}$ into $m$ sub-parts and
computing attention separately and then concatenating them.

Masked self-attention followed by position-wise feedforward network, $FFN$,
gives a Transformer decoder layer
$H^{(1)}=[h^{(1)}_{1},h^{(1)}_{2},\ldots,h^{(1)}_{n-1}]$.

#### Output projection matrix

The output projection matrix $W_{p}$ takes as input a sequence of dimension
$\mathbb{R}^{(n-1)\times d_{model}}$ and outputs probabilities on the output
space of dimension $\mathbb{R}^{(n-1)\times|\mathcal{V}|}$, where
$\mathcal{V}$ is the vocabulary space.

An $L$-layered Transformer decoder consists of an embedding layer, followed by
$L$ attention layers, followed by an output projection matrix. A single-
layered Transformer decoder is shown in Fig. 1.

Figure 1: Single-layered Transformer decoder with attention span, $k$, $=3$.

##  3 Performance Limits of Transformers

Here we provide theoretical limits to the performance of the Transformer
architecture. First, we show that the Transformer architecture can be viewed
as an approximate FSMP.

###  3.1 Transformers as approximate FSMPs

An FSMP as defined in Sec. 2.1 is given by a function pair $(g,f)$, where $g$
is a state function that first _aggregates_ certain past observations
$(x_{j},\ldots,x_{i-1})$, where $j<(i-1)$ is a choice for the $g$ function and
$f$ is a probability function from the states given by $g$ to
$\mathbb{R}^{|\mathcal{V}|}$.

In an $L$-layered Transformer, we model the $g$ function by the embedding
layer $E$ followed by a sequence of $L$ attention layers. The $l$th attention
layer computes the weighted sum of past observations
$(h^{(2l)}_{j},\ldots,h^{(2l)}_{i-1})$ followed by an $FFN$. Note that the
weighted sum in the attention mechanism is performed in the higher dimension
$d_{model}$, which can retain as much information as concatenation in lower
dimension if $d_{model}$ is large enough. The output of the embedding layer
followed by $L$-attention layers can be seen as approximating the $g$
function, call it $\bar{g}$.

This is followed by the output projection matrix $W_{P}$, which can be seen as
approximating the output probability function $f$, call it $\bar{f}$. Fig. 2
shows a single-layer Transformer, comparing its components with that of an
FSMP.

Figure 2:  A single Transformer decoder layer with attention span equals to
three ($k=3$) and its comparison to a finite-state Markov predictor (FSMP).
The output of the Transformer decoder, $h_{i-1}^{1}$ can be interpreted as the
output of the state function, $g(x_{i},x_{i-1},\ldots,x_{i-k+1})$, of a FSMP.
The matrix $W_{P}$ can be interpreted as the predictor function $f(\cdot)$ of
a FSMP that takes the state as input and outputs a probability distribution
over the vocabulary space. The embedding layer is ignored for brevity.

###  3.2 Theoretical Limits

Here, we use the similarity between Transformers and FSMPs to find the limits
of the Transformer architecture. First we provide the training setup and loss
criterion for our results. Note that the only assumption we use in the
following data generation process is of Markovity and hence, the results
obtained are general otherwise. We first describe the dataset and the loss
criterion.

#### Dataset

We consider the train dataset
$\mathcal{D}_{Train}=\\{x_{1},\ldots,x_{n};y_{1},\ldots,y_{n}\\}$ of size $n$
and test dataset
$\mathcal{D}_{Test}=\\{x_{n+1},\ldots,x_{n+m};y_{n+1},\ldots,y_{n+m}\\}$ of
size $m$. In the datasets, $\\{x_{i}\\}_{i=1}^{n+m}$ is an arbitrary sequence
with distribution $p(x_{1},\ldots,x_{n+m})$ and $y_{i}$ is generated
conditioned on $g(x_{i},\ldots,x_{(i-l+1)_{+}})$, where $g$ is a state
function.Thus, we consider a sequence of Markov order $l$. For our theoretical
analysis, we use binary vocabulary, i.e. $x_{i},y_{i}\in\\{0,1\\}$, and will
let $m\to\infty$.

#### Loss criterion

A model is trained on $\mathcal{D}_{Train}$ with some state function $\bar{g}$
to obtain an order $k$ stationary Markov estimator
$p^{n}_{\theta_{k}}(\cdot)$, which is the $f$ function in the context of an
FSMP.

The train loss on $\mathcal{D}_{Train}$ is given by
$\mathcal{L}_{Train}^{(l,k,n)}(\mathcal{D}_{Train})=-\frac{1}{n}\sum_{i=1}^{n}\log{(p^{n}_{\theta_{k}}(y_{i}|\bar{g}(x_{\leq
i})))}.$

Denote the loss on $\mathcal{D}_{Test}$ by
$\mathcal{L}_{Test}^{(l,k,m,n)}(\mathcal{D}_{Test})=-\frac{1}{m}\sum_{i=1}^{m}\log{(p^{n}_{\theta_{k}}(y_{i+n}|\bar{g}(x_{\leq
i+n})))}$. Following (Manning & Schutze, 1999), we consider languages to show
stationary, ergodic properties. Now, taking $m\to\infty$, and using
stationarity of $p(\cdot)$, we define
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})=\lim_{m\to\infty}\mathcal{L}_{Test}^{(l,k,m,n)}(\mathcal{D}_{Test})$
to get

$\displaystyle\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})=$
$\displaystyle-\sum_{(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})\log{(p^{n}_{\theta_{k}}(y_{k}|\bar{g}(x_{k},\ldots,x_{1})))}.$
(1)

For fixed data Markov order $l$ with known state function $g$ and estimator
Markov order $k$, suppose the minimum loss is obtained by an estimator
$p^{n,*}_{\theta_{k}}$. Then, this minimum loss is

$\displaystyle\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})=$
$\displaystyle-$
$\displaystyle\sum_{(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k+1}}p(y_{k},x_{k},\ldots,x_{1})\log{(p^{n,*}_{\theta_{k}}(y_{k}|g(x_{k},\ldots,x_{1})))}.$
(2)

#### Bayesian estimator

An order-$k$ Bayesian estimator with a given state function $g$ is of the form

$\displaystyle
p_{\theta_{k}}^{n}(Y_{k+i}=y_{k}|g(X_{k+i},\ldots,X_{1+i})=g(x_{k},\ldots,x_{1}))$
$\displaystyle=\begin{cases}\frac{N{(y_{k};g(x_{k},\ldots,x_{1}))}}{N{(g(x_{k},\ldots,x_{1}))}}&\text{if
}k>0,\\\ \frac{N{(y_{0})}}{n}&\text{if }k=0,\end{cases}$ (3)

where $N{(y_{k};g(x_{k},\ldots,x_{1}))}$ denotes the number of counts of
$Y_{k+i}=y_{k}$ and $g(X_{k+i},\ldots,X_{1+i})=g(x_{k},\ldots,x_{1})$ for
$0\leq i\leq(n-k)$ in the train set, $\mathcal{D}_{Train}$. Similarly,
$N{(g(x_{k},\ldots,x_{1}))}$ is the number of occurrences of the subsequence
$g(X_{k+i},\ldots,X_{1+i})=g(x_{k},\ldots,x_{1})$, $N(y_{0})$ is the number of
occurrences of $Y_{i}=y_{0}$ for $0\leq i\leq(n-k)$, and $n$ is the size of
the train dataset. Note that the order $l$ and the state function $g$ of the
source is unknown to the estimator, hence it is not obvious what $k$ and $g$
should be chosen for best test performance.

Now we state and prove the theorem giving limits to the test loss obtained by
any Transformer architecture with attention span $k$. Thereafter we show the
obtained limits are indeed optimal. Proofs are in Appendix A.

######  Theorem 3.1.

Let $\\{\mathcal{D}_{Train},\mathcal{D}_{Test}\\}$ be an order-$l$ Markov
dataset with some state function $g$. Let $\bar{g}$ be the state function of a
Transformer such that
$H(Y_{m}|g(X_{m},\ldots,X_{1}))=H(Y_{m}|\bar{g}(X_{m},\ldots,X_{1}))$ for
$m=k,l$, e.g. choose $\bar{g}$ as the identity function and let
$p_{\theta_{k}}^{n}$ be the order-$k$ Bayesian estimator in (3.2) with state
function $\bar{g}$. Let $\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ be
the corresponding test loss of the Transformer.

Then, if $l\leq k$,

$\displaystyle\lim_{n\to\infty}\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})=H(Y_{l}|X_{l},\ldots,X_{1}),$
(4)

whereas, if $l>k$,

$\displaystyle\lim_{n\to\infty}\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})=H(Y_{k}|X_{k},\ldots,X_{1}).$
(5)

Here $H(Y_{m}|X_{m},\ldots,X_{1})$ is the conditional entropy of the
distribution $p(y_{m}|x_{m},\ldots,x_{1})$ for $m=l,k$.

Moreover,
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})\to\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})$
with convergence error $\mathcal{O}({\frac{|\mathcal{S}|}{n}})$ in expectation
in both the cases, (4), (5), where $\mathcal{S}$ is the range of the state
function $\bar{g}$.

Now, we show that the limits obtained in Thm. 3.1 are optimal.

######  Theorem 3.2.

Let $\\{\mathcal{D}_{Train},\mathcal{D}_{Test}\\}$ be an order-$l$ Markov
dataset with some state function $g$. Then, let $h$ be some arbitrary function
taking as input $(X_{i},\ldots,X_{i+k})$, and outputs some probability
$h(Y_{i+k}|X_{i},\ldots,X_{i+k})$ over the space of $Y_{i+k}$. Then, the
optimal cross-entropy loss obtained by $h$,
$\sum_{(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})\log{(h(y_{k}|x_{k}\ldots,x_{1}))}$
is greater than or equal to $H(Y_{l}|X_{l},\ldots,X_{1})$ if $l\leq k$, else,
greater than or equal to $H(Y_{k}|X_{k},\ldots,X_{1})$.

###  3.3 Understanding the limits

($l=10$)

($l=15$)

($l=20$)

Figure 3: Performance of Finite State Markov Predictor on a Boolean synthetic
dataset, where the output is 1 if the sum of previous $l$ observations is
greater than a threshold, else 0. Plot illustrates the nature of the obtained
limit in Thm. 3.1. Smaller values of $k$ converges faster but to a higher
value of test loss compared to larger values.

From the limits in Thm. 3.1, we know that for $k<l$, increasing the value of
$k$ improves the obtained limit. This is because conditioning reduces entropy
and hence using the stationarity property $H(Y_{k}|X_{k},\ldots,X_{1})\leq
H(Y_{k-1}|X_{k-1},\ldots,X_{1})$ (Cover & Thomas, 1999). But, for $k>l$,
$H(Y_{l}|X_{l},\ldots,X_{1})=H(Y_{k}|X_{k},\ldots,X_{1})$. To better
understand the limits in Thm. 3.1, we show the performance of an FSMP with the
aggregation function $g$ as the identity function with span of the input $k$,
and the output probability function $f$ is set as the Bayesion predictor in
(3.2). We test the performance of the FSMP on a synthetic Boolean dataset,
where the input is randomly generated binary values and the output at position
$i$ is 1 if the sum of the past $l$ observations is greater than a threshold,
else, 0. The main observation to note from Fig. 3 is that for smaller values
of $k$, the convergence is faster compared to larger values, but, the value
the losses converge to is much worse than for larger values of $k$.

The limits in Thm. 3.1 gives us two important design choices for efficiently
designing and training Transformers. First, the choice of the state function
$\bar{g}$ and its attention span $k$. Second, the amount of data, $n$, to
train on.

The choice of $\bar{g}$ and $k$ must be such that it does not lose any
information important to the output, i.e.
$H(Y_{m}|g(X_{m},\ldots,X_{1}))=H(Y_{m}|\bar{g}(X_{m},\ldots,X_{1}))$. One
such $\bar{g}$ can be simply the identity function. The corresponding $k$ must
be chosen large enough, i.e. $k\geq l$. Note that for all such $\bar{g}$ and
$k$ the optimal value remains the same as $n\to\infty$, but, in the finite
data regime, one needs to choose appropriate $\bar{g}$ and $k$ to get the best
performance. In particular, one needs to choose $\bar{g}$ and $k$ that has the
smallest range $\mathcal{S}$ while also satisfying
$H(Y_{m}|g(X_{m},\ldots,X_{1}))=H(Y_{m}|\bar{g}(X_{m},\ldots,X_{1}))$. Thus,
it indicates the need for sparsity in the design.

For the second choice, $n$, while it may seem obvious that training on larger
data would give better performance, we show that with increase in data, the
improvement in performance is significant, even with training for the same
number of training steps. Moreover, this also motivates an augmentation
technique that helps statistically explain the benefit gained from using
relative positional encodings (Shaw et al., 2018).

In Appendix B, we further aim to understand Transformers and data-efficient
training. In Appendix C, we provide further experiments on real-world data.

##  4 Conclusion

Here, we prove that the Transformer architecture yields universal predictors
in the information-theoretic sense, which may help explain why this
architecture seems to be a kind of state-of-the-art universal computation
system. We further analyzed the different components of the Transformer
architecture, such as attention weights and positional encodings.

Going forward, it may be of interest to take inspiration from information-
theoretic work in universal prediction (Merhav & Feder, 1998) to inspire novel
neural architectures.

## References

  * Anil et al. (2023) Anil, R., Dai, A. M., Firat, O., Johnson, M., Lepikhin, D., Passos, A., Shakeri, S., Taropa, E., Bailey, P., Chen, Z., Chu, E., Clark, J. H., et al.  PaLM 2 technical report.  arXiv:2305.10403 [cs.CL]., May 2023.
  * Chen et al. (2021) Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I.  Decision transformer: Reinforcement learning via sequence modeling.  _Advances in neural information processing systems_ , 34, 2021.
  * Chen et al. (2020) Chen, S., Dobriban, E., and Lee, J.  A group-theoretic framework for data augmentation.  _Advances in Neural Information Processing Systems_ , 33:21321–21333, 2020.
  * Cover & Shenhar (1977) Cover, T. M. and Shenhar, A.  Compound Bayes predictors for sequences with apparent Markov structure.  _IEEE Transactions on Systems, Man, and Cybernetics_ , 7(6):421–424, 1977.
  * Cover & Thomas (1999) Cover, T. M. and Thomas, J. A.  _Elements of information theory_.  John Wiley & Sons, 1999.
  * Cybenko (1989) Cybenko, G.  Approximation by superpositions of a sigmoidal function.  _Mathematics of Control, Signals and Systems_ , 2:303–314, December 1989.
  * Dosovitskiy et al. (2020) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2020.
  * Feder et al. (1992) Feder, M., Merhav, N., and Gutman, M.  Universal prediction of individual sequences.  _IEEE transactions on Information Theory_ , 38(4):1258–1270, 1992.
  * Golkar et al. (2022) Golkar, S., Tesileanu, T., Bahroun, Y., Sengupta, A., and Chklovskii, D.  Constrained predictive coding as a biologically plausible model of the cortical hierarchy.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), _Advances in Neural Information Processing Systems_ , volume 35, pp. 14155–14169. Curran Associates, Inc., 2022.
  * Gurevych et al. (2022) Gurevych, I., Kohler, M., and Şahin, G. G.  On the rate of convergence of a classifier based on a transformer encoder.  _IEEE Transactions on Information Theory_ , 68(12):8139–8155, December 2022.
  * Jaegle et al. (2021) Jaegle, A., Gimeno, F., Brock, A., Vinyals, O., Zisserman, A., and Carreira, J.  Perceiver: General perception with iterative attention.  In _International Conference on Machine Learning_ , pp. 4651–4664. PMLR, 2021.
  * Li et al. (2019) Li, N., Liu, S., Liu, Y., Zhao, S., and Liu, M.  Neural speech synthesis with transformer network.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pp. 6706–6713, 2019.
  * Lu et al. (2021) Lu, K., Grover, A., Abbeel, P., and Mordatch, I.  Pretrained transformers as universal computation engines.  _arXiv preprint arXiv:2103.05247_ , 2021.
  * Manning & Schutze (1999) Manning, C. and Schutze, H.  _Foundations of Statistical Natural Language Processing_.  MIT Press, 1999.
  * Merhav & Feder (1998) Merhav, N. and Feder, M.  Universal prediction.  _IEEE Transactions on Information Theory_ , 44(6):2124–2147, October 1998.
  * Merity et al. (2016) Merity, S., Xiong, C., Bradbury, J., and Socher, R.  Pointer sentinel mixture models.  _arXiv preprint arXiv:1609.07843_ , 2016.
  * OpenAI (2023) OpenAI.  GPT-4 technical report.  arXiv:2303.08774 [cs.CL]., March 2023.
  * Romero & Cordonnier (2020) Romero, D. W. and Cordonnier, J.-B.  Group equivariant stand-alone self-attention for vision.  _arXiv preprint arXiv:2010.00977_ , 2020.
  * Shannon (1948) Shannon, C. E.  A mathematical theory of communication.  _Bell Syst. Tech. J._ , 27:379–423, 623–656, July/Oct. 1948.
  * Shannon (1950) Shannon, C. E.  The redundancy of English.  In _Trans. 7th Conf. Cybern._ , pp. 123–158, March 1950.
  * Shannon (1951) Shannon, C. E.  Prediction and entropy of printed English.  _Bell Syst. Tech. J._ , 30(1):50–64, January 1951\.
  * Shaw et al. (2018) Shaw, P., Uszkoreit, J., and Vaswani, A.  Self-attention with relative position representations.  _arXiv preprint arXiv:1803.02155_ , 2018.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wei et al. (2022) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E. H., Hashimoto, T., Vinyals, O., Liang, P., Dean, J., and Fedus, W.  Emergent abilities of large language models.  _Transactions on Machine Learning Research_ , 2022.
  * Weissman & Merhav (2001) Weissman, T. and Merhav, N.  Universal prediction of individual binary sequences in the presence of noise.  _IEEE Transactions on Information Theory_ , 47(6):2151–2173, September 2001.
  * Yun et al. (2020) Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S., and Kumar, S.  Are transformers universal approximators of sequence-to-sequence functions?  In _International Conference on Learning Representations (ICLR)_ , 2020.

##  Appendix A Proofs

######  Lemma A.1.

$H(Y_{l}|g(X_{l},\ldots,X_{1}))=H(Y_{l}|X_{l},\ldots,X_{1})$ for the data
generation process in Sec. 3.

###### Proof.

We know $Y_{l}-g(X_{l},\ldots,X_{1})-(X_{l},\ldots,X_{1})$ forms a Markov
chain, hence,
$H(Y_{l}|g(X_{l},\ldots,X_{1}),X_{l},\ldots,X_{1})=H(Y_{l}|g(X_{l},\ldots,X_{1}))$,
But, since $g(X_{l},\ldots,X_{1})$ is a function of $(X_{l},\ldots,X_{1})$, we
have
$H(Y_{l}|g(X_{l},\ldots,X_{1}),X_{l},\ldots,X_{1})=H(Y_{l}|X_{l},\ldots,X_{1})$.
∎

###### Thm. 3.1.

First we consider the case where $l=0,k=0$ and understand the behavior of
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ and
$\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})$ as a function of $n$.
Then, we will use the results from these cases to understand more general
cases varying both $l$ and $k$.

#### Case $l=0,k=0$

Consider order $0$ estimator in (3.2). We first compute
$\mathcal{L}_{Test}^{(0,0,n),*}(\mathcal{D}_{Test})$ by writing

$\displaystyle\mathcal{L}_{Test}^{(0,0,n)}(\mathcal{D}_{Test})=\sum_{y_{0}\in\\{0,1\\}}p(y_{0})\log{\frac{1}{p(y_{0})}}+D(p||p_{\theta^{n}_{0}}),$
(6)

where
$D(p||p_{\theta^{n}_{0}})=\sum_{y_{0}\in\\{0,1\\}}p(y_{0})\log{\frac{p(y_{0})}{p_{\theta^{n}_{0}}(y_{0})}}$
is the KL divergence between $p$ and $p_{\theta^{n}_{0}}$. Further, from basic
information-theoretic inequalities we know that $D(p||q)\geq 0$ with the
equality holding only when $p=q$ (Cover & Thomas, 1999). Thus, we have
$\mathcal{L}_{Test}^{(0,0,n),*}(\mathcal{D}_{Test})=H(Y_{0})$, where
$H(Y_{0})=\sum_{y_{0}\in\\{0,1\\}}p(y_{0})\log{\frac{1}{p(y_{0})}}$ is the
entropy of the distribution $\\{p(y_{0}):y_{0}\in\\{0,1\\}\\}$. Moreover, we
have $p^{n,*}_{\theta_{0}}(y_{0})=p(y_{0})$ for $y_{0}\in\\{0,1\\}$.

Now, we show that $D(p||p_{\theta^{n}_{0}})\to 0$ as $n\to\infty$ and further
analyze its convergence rate. Using concentration inequalities, it follows
that $p_{\theta^{n}_{0}}\to p(y_{0})$ with rate
$\mathcal{O}(\frac{1}{\sqrt{n}})$ with high probability. For brevity, we do
not provide the calculations and use results from Cover & Shenhar (1977) that
show the convergence rate to be $\mathcal{O}(\frac{1}{\sqrt{n}})$ in
expectation. Now we show that this implies $D(p(y_{0})||p_{\theta^{n}_{0}})\to
0$ with an approximate rate $\mathcal{O}(\frac{1}{n})$. To this end, take
$p_{\theta^{n}_{0}}=p(y_{0})+t$, where $t=\mathcal{O}(\frac{1}{\sqrt{n}})$.
Say, $p(1)=p=p(y_{0})$ and hence, $p(0)=1-p$. Then, we have

$\displaystyle D(p||p+t)$
$\displaystyle=p\log{\frac{p}{p+t}}+(1-p)\log{\frac{(1-p)}{(1-p-t)}}$
$\displaystyle=-\frac{1}{\ln{2}}\left(p\ln{(1+\frac{t}{p})}+(1-p)\ln{(1-p-t)}\right)\mbox{.}$

Assuming $n$ to be large enough such that $t\ll\min{\\{p,1-p\\}}$ and using
the Taylor expansion of $\ln{(1-x)}$ up to second-order terms, we have

$\displaystyle D(p||p+t)$
$\displaystyle\approx\frac{t^{2}}{\ln{2}}\left(\frac{1}{p}+\frac{1}{1-p}\right).$

Thus, $D(p||p_{\theta^{n}_{0}})\to 0$ with $\mathcal{O}(\frac{1}{n})$ in
expectation.

Next, we generalize these optimal loss and convergence results for general $l$
and $k$ using results from the current case.

#### Case $l\leq k$

Here we have the evaluation loss
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ as

$\displaystyle\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test}$
$\displaystyle)=H(Y_{l}|\bar{g}(X_{l},\ldots,X_{1}))+$
$\displaystyle\sum_{(x_{k},\ldots,x_{1})}p(x_{k},\ldots,x_{1})\times$ (7)
$\displaystyle
D(p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))||p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))),$
(8)

where $p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))$ is as defined in
(3.2). Since $D(p||q))\geq 0$ with equality holding only when $p=q$, we have
$\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})=H(Y_{l}|\bar{g}(X_{l},\ldots,X_{1}))=H(Y_{l}|g(X_{l},\ldots,X_{1}))=H(Y_{l}|X_{l},\ldots,X_{1})$,
where $H(Y_{l}|g(X_{l},\ldots,X_{1}))$ is the conditional entropy of the
distribution $p(y_{k}|g(x_{k},\ldots,x_{1}))$. The equality
$H(Y_{l}|g(X_{l},\ldots,X_{1}))=H(Y_{l}|X_{l},\ldots,X_{1})$ follows directly
and is proved in Lem. A.1 for completeness.

Moreover, we have
$p^{n,*}_{\theta_{k}}(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))=p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))$
for $(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k+1}$. Note that here, for $l\leq
k$,
$\mathcal{L}_{Test}^{(l,k,n),*}(\mathcal{D}_{Test})=H(Y_{l}|\bar{g}(X_{l-1},\ldots,X_{0}))$
is independent of $k$.

Now we look at the convergence rate of
$D(p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))||p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1})))\to
0$ as $n\to\infty$. Here we only perform approximate calculations as this is
sufficient for present purposes. From the previous case with $l=0,k=0$, we
know $D(p(y_{0})||p_{\theta_{0}}^{n}(y_{0}))\to 0$ as
$\mathcal{O}(\frac{1}{n})$. For the convergence of
$D(p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))||p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1})))$,
we will only look at the indices $y_{k}$ that have prefix
$\bar{g}(x_{k},\ldots,x_{1})$. We know that the number of such prefixes is
approximately equal to $np(\bar{g}(x_{k},\ldots,x_{1}))$ in expectation. Thus
$D(p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))||p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1})))\to
0$ as $\mathcal{O}(\frac{1}{np(\bar{g}(x_{k},\ldots,x_{1}))})$. Thus, from (A)
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ converges to
$H(Y_{l}|\bar{g}(X_{l},\ldots,X_{1}))$ approximately as
$\sum_{\bar{g}(x_{k},\ldots,x_{1})}p(\bar{g}(x_{k},\ldots,x_{1}))\mathcal{O}(\frac{1}{np(\bar{g}(x_{k},\ldots,x_{1}))})\approx\mathcal{O}(\frac{|\mathcal{S}|}{n})$.

#### Case $l>k$

Here the evaluation loss $\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ is
given by

$\displaystyle\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$
$\displaystyle=H(Y_{k}|\bar{g}(X_{k},\ldots,X_{1}))$
$\displaystyle+\sum_{(x_{k},\ldots,x_{0})}p(x_{k},\ldots,x_{1})\times$ (9)
$\displaystyle
D(p(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))||p_{\theta_{k}}^{n}(y_{k}|\bar{g}(x_{k},\ldots,x_{1}))),$
(10)

The optimal value of $\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ is
clearly
$H(Y_{k}|\bar{g}(X_{k},\ldots,X_{1}))=H(Y_{k}|g(X_{k},\ldots,X_{1}))=H(Y_{k}|X_{k},\ldots,X_{1})$
from non-negativity of KL divergence and the data generation process.
Moreover, the convergence rate of
$\mathcal{L}_{Test}^{(l,k,n)}(\mathcal{D}_{Test})$ to
$H(Y_{k}|X_{k},\ldots,X_{1})$ approximately with rate
$\mathcal{O}(\frac{|\mathcal{S}|}{n})$, the same way as in the previous case.
∎

###### Thm. 3.2.

The proof follows directly from the non-negativity of KL divergence.

#### $l\leq k$

Here, we have

$\displaystyle\sum_{(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})\log{(h(y_{k}|x_{k}\ldots,x_{1}))}$
$\displaystyle=H(Y_{k}|X_{k},\ldots,X_{1})+\sum_{(x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})\times$
$\displaystyle D(p(y_{k}|x_{k}\ldots,x_{1})||h(y_{k}|x_{k}\ldots,x_{1}))$
$\displaystyle=H(Y_{l}|X_{l},\ldots,X_{1})+\sum_{(x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})$
$\displaystyle D(p(y_{k}|x_{k}\ldots,x_{1})||h(y_{k}|x_{k}\ldots,x_{1}))$

Note that $H(Y_{k}|X_{k},\ldots,X_{1})=H(Y_{l}|X_{l},\ldots,X_{1})$ because
$Y_{k}$ only depends on the past $l$ observations and the stationarity
assumption. Further, we have $D(\cdot||\cdot)\geq 0$ to conclude the proof.

#### $l>k$

Here, we have

$\displaystyle\sum_{(y_{k},x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})\log{(h(y_{k}|x_{k}\ldots,x_{1}))}$
$\displaystyle=H(Y_{k}|X_{k},\ldots,X_{1})+\sum_{(x_{k},\ldots,x_{1})\in\\{0,1\\}^{k}}p(y_{k},x_{k}\ldots,x_{1})$
$\displaystyle D(p(y_{k}|x_{k}\ldots,X_{1})||h(y_{k}|x_{k}\ldots,x_{1})),$
$\displaystyle\geq H(Y_{k}|X_{k},\ldots,X_{1})$

where we have $D(\cdot||\cdot)\geq 0$. ∎

##  Appendix B Understanding Transformers and Data-Efficient Training

First, we understand the role of various components of a Transformer in the
prediction process. Then, we show the importance of relative position
encodings (Shaw et al., 2018) and group-equivariant positional encodings
(Romero & Cordonnier, 2020) statistically in resource-constrained datasets. In
particular, our results show that these methods are beneficial only when the
available data is small, but their effect is negligible for larger datasets.
For this analysis, we use position augmentations and group augmentations
instead of equivariance for the ease of analysis. In practice, both
equivariance and augmentation enforce the same constraint on the model. While
equivariance applies the constraints by design in the model, augmentation does
it more implicitly when training.

###  B.1 Understanding Transformers

Here we discuss the role of various components of a Transformer.

#### Attention weights

Attention weights play an important role in filtering out unimportant data
points and hence help make the range of the state function $\bar{g}$ as small
as possible while also ensuring that the important information is retained. We
validate this claim by showing that when attention weights are used,
additional irrelevant information does not affect the loss values. Whereas,
without attention, the loss values are negatively affected.

On the other hand, in the extreme case where all the input variables are
important, we show, perhaps surprisingly, that attention performs worse than a
network without it.

#### Absolute positional encoding and $FFN$

Absolute positional encoding introduced by Vaswani et al. (2017) helps
identify the order of the words in a sentence for the Transformer. Without
positional encoding, the output of a Transformer is equivariant to the
permutation of words in the input. This is not desirable since changing the
order of words in a sentence can completely change its meaning or may even
make it gibberish. Hence, the understanding of the order of the words is
important to a Transformer.

In our experiments, we find that $FFN$ does not effectively filter out
unnecessary information like attention. But it does improve the results when
used with attention, indicating that it helps produce a better representation
of the state of the Transformer.

###  B.2 Data-Efficient Training: Positional Augmentation

Equivariance and augmentations are considered to be two sides of the same
coin. Whereas one applies constraints on the model, the other transforms the
data during the training process to implicitly introduce those constraints in
the learnt functions. Here, we use group augmentations (Chen et al., 2020) to
study its impact on the performance of Transformers as it helps our
theoretical analysis. Augmentations do not change the asymptotic performance
limits, but, improves finite data performance as we find next.

#### Positional augmentation

We study the role of translation augmentation in the performance of
Transformers. The key to our analysis is the following: we transform the data
while keeping the position encodings the same and since the input to the
Transformer is a summation of the data and the absolute encodings, the input
appears as new data. This effectively increases the number of training data
points in the dataset. Thus, for each augmentation, we count the effective
size of the augmented dataset and analyze the performance from the finite data
loss expression obtained in Thm. 3.1.

For translation augmentation for a dataset of size $n$ and each batch
processing $n_{pos}$ tokens at once. A translation augmentation parametrized
by $t_{0}$, can be obtained by shifting the data by $t$, where $t$ goes from
$t_{0}$ to $n_{pos}-1$. This way, the semantics of text does not change, but
we generate more data points. From the finitary analysis in Thm. 3.1, we know
the loss value converges with rate $O(1/n)$. Hence, with augmentation $t_{0}$,
we have the following gain in the convergence rate. The proof is direct from
the assumption that there are no repetitions in the dataset and counting the
size of the augmented dataset.

######  Proposition B.1.

Let a dataset of size $n$ be augmented by $t_{0}$ with $n_{pos}$ tokens
processed per batch. Then the gain convergence rate is
$O(\frac{1}{n}(1-\frac{1}{(n_{pos}-t_{0})}))$.

Two important consequences to note from Prop. B.1 are: a) the gain decreases
proportionally with increase in $n$, b) it increases with decrease in $t_{0}$.

##  Appendix C Further Experiments

Here we validate our findings using various experiments.

###  C.1 Datasets

We work with three sequential datasets: two are synthetic and one is a real
language dataset, WikiText2 (Merity et al., 2016). The synthetic datasets are
MarkovBoolSum and MarkovBin2Dec. MarkovBoolSum with Markovity $l$, is
constructed by first uniformly generating a binary input, then the labels are
set as 1 if the sum of previous $l$ inputs sum to greater than or equal to
$l/2$, else 0. For MarkovBin2Dec, the input is generated in a similar way as
MarkovBoolSum, but, the output is the decimal value corresponding to the
binary observation of the $l$ previous observations. The main difference
between the two datasets is that in MarkovBoolSum, not all the inputs
contribute to the output, hence attention should help performance. Whereas, in
MarkovBin2Dec, all the input values contribute to the output, hence, attention
might not perform as well. All experiments were run on one fixed seed.

###  C.2 Model Architecture

We use a single attention layer Transformer with varying attention span. The
model dimension is fixed to $64$, and the hidden dimension for $FFN$ is set to
$128$. For our experiments, we keep three design choices: a) attention or
aggregation; b) $FFN$ or no $FFN$; c) translation augmentation.

###  C.3 Attention

In Tab. 1, we show results that indicate the benefit of attention. The
synthetic datasets used $l=5$, and were trained for 10000 train batches for
2000 steps of batch size 20. It is found that using attention, the difference
between varying lengths of span $k$ is less than without attention. Also, in
the case $k=5$ for MarkovBin2Dec, we find that attention performs poorly
compared to no attention. This is because, for $k=5$, all points in the input
are important and attention may have neglected some of the inputs.

Table 1: Attention Dataset |  | Attention | Aggregation
---|---|---|---
k | 5 | 10 | 15 | 5 | 10 | 15
MarkovBoolSum | 0.016 | 0.34 | 0.36 | 0.011 | 0.375 | 0.421
MarkovBin2Dec | 0.036 | 0.87 | 0.99 | 0.015 | 0.91 | 1.08
WikiText2 | 6.17 | 6.18 | 6.19 | 6.49 | 6.66 | 6.70

###  C.4 Positional Encodings

Table 2: Position augmentation n | 1 | 1000
---|---|---
$t_{0}$ | 0 | 99 | 0 | 99
loss values | 9.68 | 0.87 | 0.628 | 0.624

The results for position augmentation are given in Tab. 2, where we find that
augmentation helps improve test loss performance. But, the loss is significant
only when the number of train batches are very small, corresponding to our
theoretical analysis.


# Likely, Light, and Accurate Context-Free
Clusters-based Trajectory Prediction

Tiago Rodrigues de Almeida and Oscar Martinez Mozos This work was supported by
the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by
the Knut and Alice Wallenberg Foundation.The authors are with Center for
Applied Autonomous Sensor Systems (AASS), Örebro University, Örebro, Sweden
<EMAIL_ADDRESS>
###### Abstract

Autonomous systems in the road transportation network require intelligent
mechanisms that cope with uncertainty to foresee the future. In this paper, we
propose a multi-stage probabilistic approach for trajectory forecasting:
trajectory transformation to displacement space, clustering of displacement
time series, trajectory proposals, and ranking proposals. We introduce a new
deep feature clustering method, underlying self-conditioned GAN, which copes
better with distribution shifts than traditional methods. Additionally, we
propose novel distance-based ranking proposals to assign probabilities to the
generated trajectories that are more efficient yet accurate than an auxiliary
neural network. The overall system surpasses context-free deep generative
models in human and road agents trajectory data while performing similarly to
point estimators when comparing the most probable trajectory.

##  I INTRODUCTION

For a wide range of applications, an accurate estimation of the future
position of moving agents is paramount. In the transportation sector, several
branches benefit from effective forecasting systems such as (1) flexible,
reliable and robust road traffic network relies on the prediction of traffic
to prevent congestion and provide safety and efficiency [1, 2]; (2) Advanced
Driver Assistance Systems (ADAS) capable of foreseeing the future can then
adapt accordingly [3]; (3) the task of transporting goods may resort to a
simulation of the future, which foster more informed planning and resource
allocation [4]. Further, trajectory prediction enhances situational awareness
in complex dynamic environments such as industrial facilities, public sites,
or home environments where multiple agents are moving. Finally, multimodal
probabilistic forecasting of trajectories yields a richer representation of
possible future events, which triggers subsequent decision-making systems [5].

The trajectory forecasting task mainly underlies three pillars such as agents
interactions modeling [6, 7, 8, 9, 10, 11], semantic context learning [12,
13], and multimodal predictions [14, 15, 16]. Also, multimodal approaches
brought a new view to the trajectory prediction domain as accounting for a set
of diverse behaviors, instead of a unique point estimate, offers a much more
reasonable and safe solution [17]. The problem with previous approaches is
that they do not provide probabilistic or score measures for each trajectory
estimate. In these cases, depending on the model’s variability (induced
usually by the _k-variety loss_ [17]), the predictions can be considered
accurate or not [11]. Most works following previous benchmarks [18] opt by
sampling $K$ trajectories (usually, $K=20$) and evaluating the closest to the
ground truth. The premise that the closest trajectory to the ground truth can
give a reasonable overview of the forecaster’s performance is ambiguous as the
model’s variability plays a major role in the reported results [11].
Therefore, the research community urges probabilistic and accurate predictions
with adequate results reporting. In addition, context-agnostic approaches have
had little attention from the research community [19, 20, 21], which we see as
a gap to explore novel strategies for adding trajectory-based information to
improve current context-free methods.

TrajectoriesDisplacementsClustersGenerative ProposalsRanking Proposals1234
Figure 1: System overview. (1) We transform spatiotemporal trajectory data
into the displacement space. (2) We cluster the displacement data into $K$
partitions. (3) We train deep generative models that take as inputs the
displacements ($dx$), the respective cluster class ($C$), and white noise
($z$). During inference, those models propose $K$ predictions, being $K$ the
number of clusters. (4) We proceed to the ranking proposals step, where we
assign probabilities to the predicted trajectories.

Following recent works [22, 23, 24], our method encompasses multiple stages
where the final objective is to provide a distribution of trajectories and the
respective probabilities. To that end, our system sequentially clusters the
input data, trains a conditional Deep Generative Model (cDGM) to map the input
data and clusters’ ids to the respective future trajectory, and assigns
likelihoods to the trajectories in a post-hoc fashion (see Fig. 1). The
clusters ids aim to represent akin similar behaviors that drive the final
predictions whereas the ranking proposals methods allow us to assign
probabilities to each generated trajectory. In this way, we can provide
diverse and probabilistic accurate predictions. Furthermore, inspired by [11],
we consider Top-3 scores for the assessment and comparison of methods.
Previous works have considered the Top-20 trajectories, which we agree can
mislead the interpretation of the results.

In summary, this work aims to improve standalone context-free Deep Generative
Models by adding trajectory-related information encoded in the conditioning
cluster class. Inspired by [25, 26], our first contribution is a novel deep
generative clustering algorithm, Full Path Self-Conditioned GAN (FP SC-GAN).
Besides clustering the input data, this framework generates complete sets of
displacements that can be part of a downstream data augmentation process.
However, in this work, we solely focus on the clustering capability of FP SC-
GAN. Alternatively to [22, 23, 24], our second contribution is the distance-
based ranking proposals methods, which do not rely on training an auxiliary
neural network but are still rather effective and efficient. The proposed
distance-based ranking proposals methods uniquely require access to the
clustering space. In this work, these methods perform likewise to an auxiliary
deep neural network, and run in _linear time_ whereas a Multilayer Perceptron
(MLP) requires _quadratic time_. Finally, to the best of our knowledge, we
propose the first quantitative metrics report where the likelihoods provided
by the system directly affect the Top-3 trajectory prediction metrics.

##  II RELATED WORK

Trajectory forecasting has been predominantly researched on two fronts:
context-agnostic and context-aware approaches. Context-agnostic methods solely
forecast based on observed trajectory patterns, whereas context-aware methods
include social and scene layout cues. While context-agnostic approaches have
received little attention [19, 20, 21] from the research community, context-
aware methods have been comprehensively investigated [17, 6, 27, 28, 29, 11].
This paper focuses on context-agnostic approaches and breeding mechanisms for
probabilistic trajectory forecasting based on encoded clustering information.

In the trajectory generation domain, some works tackled the problem from a
probabilistic view in road scenarios [30, 31, 32, 33] and human trajectory
data [22, 23, 24]. CoverNet [30] comprises a Convolutional Neural Network
(CNN) to extract contextual features from a road scene and a trajectory
generator module to produce a set of possible predictions. Then, the system
directly classifies the set of plausible trajectories yielding the score of
each prediction. Conversely, we aim to produce context-agnostic samples to
open the domain of applications of our system and reduce its requirements. In
[31], the authors propose a post-hoc method named Likelihood-Based Diverse
Sampling (LDS). In that paper, a novel objective function and a non-i.i.d
sampling method encourage diverse predictions by suppressing similar
predictions from the generated set of samples and leveraging the likelihoods
from a pre-trained generative model. However, this work does not determine the
scores (likelihoods) of the set of plausible trajectories, which we claim is
paramount for risk-aware downstream decision processes. _HAICU_ [32] is a
system that relies on perception and classification modules to give the class
distribution of road agents. This system stands for a Conditional Variational
Autoencoder (cVAE) conditioned on the class distribution and the observed
trajectory of road agents to produce multimodal predictions. Therefore, this
work heavily relies on upstream supervised methods to yield the class
distribution, which is not easily generalizable to human trajectory data. To
cope with this limitation, we propose unsupervised techniques to cluster akin
trajectories, which we consider agnostic to the trajectory domain and more
generalizable. In [33], the authors enforce underlying physical admissibility
constraints and diversity in a post-hoc trajectory sampling process based on a
determinantal point process (DDP). Although it proposes a robust strategy for
considering context using admissibility constraints induced in the objective
function, it does not provide a probabilistic view of the predicted
trajectories. [22] devises a three-step method based on clustering,
classification, and synthesis to predict. Contrarily to this work, we first
predict by using a cDGM and then propose a ranking proposals step. In this
work, we investigate ranking proposals methods based on the distance to the
already conceived clustering space and, therefore, not relying on a
classification network. Further, [23] proposes a method based on clustered
goal points and a final classification step. While both [22] and [23], at the
classification step, learn the mapping between the past trajectory and the
cluster class, we rank complete trajectories emphasizing the generated
tracklets. Finally, in [24], the authors investigated a system with two
branches: a motion pattern selector and a multimodal trajectory generator. The
former produces a _gallery_ of diverse motion patterns, while the latter
refines them and generates future trajectories. Then, a scoring method
produces the most diverse predictions.

Our work encompasses mechanisms under the same umbrella as [22, 23, 24], but
our main objective is to propose a system that can improve current deep
generative models by including information from clustered data. In our system
the clusters drive the multimodality, and the ranking proposals methods run on
the generated trajectories. In addition, our distance-based ranking proposals
methods does not rely on training any auxiliary neural network conversely to
previous works [22, 23, 24]. In our case, the ranking proposals step depends
exclusively on the intrinsic nature of the clustering space and a similarity
measure to the generated trajectories. Further, we propose a new deep
clustering method inspired by a self-supervised deep generative model
developed for the image generation task [25]. Finally, contrarily to previous
works, the probabilities of each trajectory strongly affect the evaluation of
our method, while in previous works, the probabilities only give a sense of
the likelihood of each particular event.

##  III Methodology

The objective of our system (see Fig. 1) is to offer accurate and
probabilistic future estimations for trajectory data. Succinctly, it comprises
four sequential steps: (1) transformation to the displacement space, (2)
clustering step, (3) deep generative proposals, and (4) ranking proposals
step. To gain a comprehensive understanding of each component, this section
provides a detailed description of the problem we address and an overview of
our proposed solution. Subsequently, we delve into the displacement
transformation and clustering steps. In the succeeding subsection, we outline
the process of acquiring the proposals. Lastly, we introduce the ranking
proposals step, which assigns probabilities to the set of predicted outputs.

###  III-A Problem Statement and System Overview

Most trajectory forecasting models generate a set of plausible futures,
$\\{\boldsymbol{\hat{y_{i}}}\\}^{K}$, given an observed tracklet,
$\boldsymbol{x}$. The observed tracklet is an evenly spaced time series of
$T_{O}$ observations in the $XY$-plane. Ultimately, the forecasting models’
goal is to predict the future behavior of the input time series for a certain
horizon of $T_{P}$ time steps. In this paper, we go beyond the trajectory
generative process and also propose a post-hoc method to assign probabilities,
$\\{\hat{p_{i}}\\}^{K}$, to the respective $K$ proposed trajectories. In this
way, besides future plausible trajectories we also provide the likelihood of
each trajectory. We consider the system’s starting point a dataset composed of
$N_{T}$ trajectories.

In the first step of our system, we transform the input trajectories into the
displacement space. As a result, we also perform any prediction in the
displacement space. In doing so, we avoid dependence on the spatial context
where the input data lies. Therefore, any downstream task is more
generalizable to new domains. Then, we cluster the displacement input vectors
into $K$ partitions via clustering. This step is paramount in the system as it
groups akin time series of displacements that we feed into the generation
process of future displacements. Consequently, we propose to train cDGMs, such
as a cVAE or a Conditional Generative Adversarial Network (cGAN) to learn the
future displacements given the observed displacements and the respective
cluster class, $c$ (i.e., the identifier for the cluster class conceived with
the ground truth displacements). As we cluster the entire set of
displacements, after training the cDGM, there will be a link between the
prediction and both the observed displacement tracklet and the respective
cluster class. Assuming a successful clustering and cDGM’s training steps,
this link allows us to claim that the prediction generated from the cluster
class $c$ will be more similar to the group of trajectories in $c$ than the
trajectories from any other cluster. Thus, during inference, we propose to
generate $K$ future displacement vectors (one per cluster class) and use a
ranking method to assign likelihoods to the proposed future displacements. The
idea behind the ranking method is to assign high likelihoods to displacement
vectors that resemble the ones on the respective ground truth cluster and do
the opposite for the remaining ones. For instance, assuming that the right
cluster class is $c_{i}$, our key insight is that the produced sample for
$c_{i}$, $\hat{\boldsymbol{dy_{i}}}$, will be more similar to the ground truth
displacements on $c_{i}$ than any prediction in
$\\{\boldsymbol{\hat{dy_{j}}}\\}_{j=1\setminus i}^{K}$ to the respective
ground truth displacements in each of the clusters in
$\\{{c_{j}}\\}_{j=1\setminus{i}}^{K}$.

###  III-B Displacement Transformation and Clustering Step

Primarily, our method transforms the raw trajectory data,
$\boldsymbol{x}\oplus\boldsymbol{y}$, into displacement vectors,
$\boldsymbol{D}\in{\rm I\\!R}^{N_{T}\times(T_{O}+T_{P})\times 2}$, where each
displacement vector is given by
$\boldsymbol{d}=\boldsymbol{dx}\oplus\boldsymbol{dy}$ or formally the finite
differences of the observed positions:

$s=\\{(d_{x},d_{y})^{1},...,(d_{x},d_{y})^{T_{P}}\\},$ (1)

being the superscript the time step.

At the clustering step, we group $\boldsymbol{D}$ into sub-partitions of akin
displacements, $\\{\boldsymbol{d_{j}}\\}_{j=1}^{K}$, where
$\boldsymbol{d_{j}}$ is a set itself with arbitrary cardinality (less or equal
than $N_{T}$). At the end of the clustering step, we guarantee that
$\sum_{j=1}^{K}|\\{\boldsymbol{d_{j}}\\}|=N_{T}$, i.e., each sample belongs to
only one cluster. We evaluate three different clustering methods: _k-Means_
[34], _TS k-Means_ [35], and our proposed FP SC-GAN. To this end, we feed _k-
Means_ with flattened displacements vectors in the form of:

$s_{f}=\\{d_{x}^{1},d_{y}^{1},...,d_{x}^{T_{P}},d_{y}^{T_{P}}\\}$ (2)

We also evaluate the extended version for time series provided by [35], _TS
k-Means_. The major differences between these two clustering methods are that
for the _TS k-Means_ , the input is given by Eq. 1 and the similarity measure
is evaluated time-wise (we use _soft-DTW_ [36]). Finally, Fig. 2 depicts our
proposed deep feature-based clustering method, FP SC-GAN. This architecture is
considered a two-fold provider: on one side, it produces the clustering space
used in the later forecasting task; on the other side, it generates a complete
set of synthetic displacements. This synthetic data can even serve as a data
augmentation process, which we do not cover in this work. FP SC-GAN underlies
the idea that the discriminator’s feature space can be meaningful for
downstream tasks [25] (in this case, the clustering task). To that end, FP SC-
GAN comprises a conditional generator ($G$) and a discriminator ($D$). We
condition the generator on a cluster class ($c$) drawn from the clustering
space and white noise ($\boldsymbol{z}$). Then one MLP-based decoder generates
an entire displacement vector,
$\boldsymbol{\hat{d}}=\boldsymbol{\hat{dx}\oplus\hat{dy}}$, that should
resemble one of the ground truth samples belonging to the conditioning
cluster. The discriminator ($D$) learns to distinguish generated and ground
truth samples according to a score ($s$). During training, to assess the
clustering process, we assume that the clustering is as good as the quality of
the generated displacements. We consider this a fair _proxy_ as the only
deterministic input signal given to the generator is the cluster id.
Analogously to [26], we train the FP SC-GAN with the binary cross entropy loss
to optimize the discriminator and a weighted sum of the discriminator’s loss
and the mean squared error (MSE) loss to optimize the generator, given by:

$\displaystyle L_{G}=$
$\displaystyle\lambda~{}MSE(\boldsymbol{y},\boldsymbol{\hat{y}})$ (3)
$\displaystyle+(1-\lambda)~{}(\frac{1}{2}\mathbb{E}[(D(\boldsymbol{d})-1)^{2}]+\frac{1}{2}\mathbb{E}[D(\boldsymbol{\hat{d}})^{2}]),$

being $\boldsymbol{\hat{y}}$ the entire generated $2D$ trajectory and
$\boldsymbol{y}$ the respective ground-truth, $\boldsymbol{\hat{d}}$ the
generated displacements vector and $\boldsymbol{d}$ the respective ground
truth, and $\lambda$ the weight applied to the MSE term. For more details on
the FP SC-GAN training, we refer the reader to [26, 25].

$\boldsymbol{\hat{dx}\oplus\hat{dy}}$or$\boldsymbol{dx\oplus dy}$Encoder  LSTM
or MLPClassifier MLP DISCRIMINATOR ($D$)$s$$\boldsymbol{z}\oplus c$Decoder MLP
GENERATOR ($G$)$\boldsymbol{\hat{dx}\oplus\hat{dy}}$Clustering Figure 2: FP
SC-GAN architecture. We pass random noise concatenated with the cluster class,
drawn according to the clustering space distribution, to the generator. The
generator aims to produce a complete set of displacements. Both generated and
real samples pass through the discriminator, which learns to classify them
into real or fake. During training, we periodically recluster the
discriminator’s feature space.

###  III-C Deep Generative Proposals

To produce potential displacement vectors, we train a cDGM that learns the
mapping $\\{\boldsymbol{dx},c\\}\rightarrow\boldsymbol{dy}$. In order to
strengthen the validation of our results, we evaluate two cDGMs: a cVAE and a
cGAN. In these methods, we first concatenate the cluster class to the input
displacement vector. Then, we extract features ($f_{e}$) from this joint
representation. The next step — noise sampling — is different in cVAE and
cGAN. While training the former, a recognition netowrk, $q_{\phi}$, learns a
low-dimensional latent representation ($\boldsymbol{z}$) by modeling the
ground truth set of future displacements ($\boldsymbol{dy}$). During
inference, it works like the conditional generator in cGAN therefore, we
sample this latent vector from a standard Gaussian Distribution. Afterward, we
concatenate the latent representation to the temporal hidden representation
learned by the feature extractor ($f_{e}$). Finally, we autoregressively
generate future displacements by decoding the last displacement vector and
using $f_{e}$.

To optimize the cVAE, we use a weighted sum of a reconstruction loss, given by
the MSE loss, and a regularization loss (Kullback-Liebler divergence)
encouraging the learned distribution to match the prior distribution

$\displaystyle L_{V}=$
$\displaystyle\lambda~{}MSE(\boldsymbol{y},\boldsymbol{\hat{y}})$ (4)
$\displaystyle-(1-\lambda)~{}\beta~{}D_{KL}[q_{\phi}(\boldsymbol{z}|\boldsymbol{dy},c)\rVert
p(\boldsymbol{z}|\boldsymbol{dx},c)],$

where $\beta$ is the weight applied to the regularization loss,
$q_{\phi}(\boldsymbol{z}|\boldsymbol{dy},c)$ and
$p(\boldsymbol{z}|\boldsymbol{dx},c)$ are the recognition and predictor
networks, respectively. For the recognition network, we employ an LSTM
followed by linear layers. The predictor, on the other hand, utilizes an MLP
to embed the input, an LSTM to extract temporal features, and an MLP to
generate the predictions.

To achieve optimal performance of the cGAN, we adopt Eq. 3 for optimization.
However, it should be noted that unlike the FP SC-GAN approach, the cGAN acts
as a forecaster. Consequently, the inputs for the MSE and discriminator losses
consist of future tracklets.

During inference, the trained cDGMs output a set of $K$ possible displacement
vectors, $\\{\boldsymbol{\hat{dy}_{i}}\\}^{K}$. This set is the input of the
last component in the system — ranking proposals — where we assign likelihoods
to each item.

###  III-D Ranking Proposals Step

The final step of the system aims to provide the mapping
$\\{\boldsymbol{\hat{dy}_{i}}\\}^{K}\rightarrow\\{p_{i}\\}^{K}$, which means
assigning probabilities to the respective $K$ predicted samples from each of
the existing clusters. As mentioned before, the mapping to the probability
space should ensure that samples from the right cluster have higher
probabilities when compared to samples from the remaining clusters. To cope
with this, one could train a deep neural network to learn the mapping
$\\{\boldsymbol{\hat{dy_{i}}}\\}^{K}\rightarrow\\{p_{i}\\}^{K}$ by itself [22,
23]. Alternatively, we propose mechanisms that rely on distance-based
similarity measures: _centroids_ and _neighbors_. For both methods, we
consider the inverse relationship between the distance and the similarity
between samples. For instance, the smaller the distance to a cluster’s
centroid, the greater the similarity to the samples of that cluster.
Similarly, in _neighbors_ , we hypothesize that the smaller the distance to
$N_{neig}$ neighbors from the same cluster, the greater the similarity to
those samples and so a higher probability of belonging to that cluster.
Formally, in distance-based methods, the probability of prediction
$\boldsymbol{\hat{dy_{i}}}$ belonging to the respective conditioning cluster,
$c_{i}$, is given by:

$\hat{p}_{c_{i}}=\frac{\exp(\frac{1}{m_{c_{i}}}/\tau)}{\sum_{j}^{K}\exp(\frac{1}{m_{c_{j}}}/\tau)},$
(5)

which is the soft-argmax function over the inverse of the distances, $m$. For
the _centroids_ approach, $m_{c_{i}}$ corresponds to the L2-distance to the
conditioning cluster’s centroid, $c_{i}$. For the _neighbors_ approach,
$m_{c_{i}}$ is the average L2-distance to the $N_{neig}$ closest neighbors
from cluster $c_{i}$. Formally, it is given as follows:

$m_{c_{i}}=\frac{1}{N_{neig}}\sum_{j}^{N_{neig}}L2(\boldsymbol{\hat{dy_{i}}},\boldsymbol{dy_{j}})$
(6)

We also evaluate a deep neural network [22, 23]. To this end, after training
the cDGM, we use it to generate a dataset of displacements following the
clustering space distribution. Then, we train a simple MLP that learns to
classify the generated samples into the respective pseudo-labels given by the
cluster assignments with the cross-entropy loss.

##  IV EXPERIMENTS

In this section we compare our proposed methods and current baselines in
different settings. Firstly, we describe the datasets, the baselines, and the
assessment metrics. Secondly, we show and analyze quantitatively and
qualitatively the results obtained in those datasets. Finally, we thoroughly
analyze the ranking proposals methods.

###  IV-A Datasets, Baselines, and Metrics

We use two settings to evaluate our methods: train-test split and leave-one-
dataset-out approach. For the former, we use two datasets: THÖR [37] and
Argoverse [38]. THÖR is a human trajectory dataset, where the participants’
roles — visitors, workers, and inspector — are scripted. We prepocess the raw
data as in [26], so we end up with $2052$ trajectories for training, $439$ for
validation, and $441$ for testing. Moreover, following the current benchmarks
[18], we create trajectories of $8$-time steps of observation
($3.2\text{\,}\mathrm{s}$) and $12$-time steps of forecasting
($4.8\text{\,}\mathrm{s}$). Argoverse is a road agents trajectory dataset,
where there are also supervised classes: autonomous vehicles (av), regular
vehicles (agents), and other road agents (others). For this dataset,
analogously to [26], we sample $5726$, $2100$, and $1678$ trajectories for
training, validation, and testing sets, respectively. Additionally, we perform
the leave-one-dataset-out in the widely used ETH/UCY benchmark [39, 40]. In
this benchmark, similarly to THÖR, the observation length is 8-time steps
($3.2\text{\,}\mathrm{s}$) and the prediction length is $12$-time steps
($4.8\text{\,}\mathrm{s}$). This benchmark comprises five datasets — ETH,
HOTEL, UNIV, ZARA1, and ZARA2 — of which four are used to train the model and
the remaining is left for testing. We use no overlapping between segments of
entire trajectories.

We conduct the experiments with baselines widely used in scientific works in
the trajectory prediction field:

  * •

Constant Velocity Model (_CVM_) [20] — heuristic model that assumes that the
humans move with constant velocity and direction. In this work we also include
its comparison in road agents’ data (Argoverse). In [20], the velocity is
given by the projection of the last displacement but we use a weighted sum of
the previous displacements based on a Gaussian kernel provided by [41]. Both
methods achieve similar results.

  * •

RED-LSTM predictor (_RED_) [19] — it is a stack of an LSTM ($64$ hidden
dimensions) and a 2-layer MLP (hidden dimensions in $\\{32,16\\}$) that
receives linearly embedded displacements (linear layer with $16$ hidden
dimensions). After every layer, we use a PreLU activation function.

  * •

Context-free GAN (_CF-GAN_) and Context-free VAE (_CF-VAE_) [18] — deep
generative approaches based on [18] but we remove any mechanisms that aim to
model social interactions since we are solely interested in seeing the
potential of trajectory-related additional information. _CF-VAE_ , _CF-GAN_ ,
and our deep generative proposals methods described in Sec. III-C have the
same design choice: initial linear layer with $16$ hidden dimensions, an LSTM
with $64$ hidden dimensions and a final linear layer with $32$ hidden
dimensions to decode the temporal features. To investigate the ability to
generate a wide range of plausible trajectories, we incorporate the _k-variety
loss_ introduced in [17], as a replacement for the MSE partial loss utilized
in the generator’s loss (in the case of _CF-GAN_) and the VAE’s loss (in the
case of _CF-VAE_).

As described in Section III-C, we compare two cDGMs: cVAE (_OURS-VAE_) and
cGAN (_OURS-GAN_). Additionally, we evaluate three clustering algorithms: _k-
Means_ , _TS k-Means_ , and the proposed _FP SC-GAN_. Furthermore, we have
three ranking proposals methods: (1) based on the Euclidean distance to the
centroids (_cent_); (2) based on the Euclidean distance to the $N_{neig}$
closest neighbors (set to $20$) in the displacement space and feature space,
denoted as _neigh-ds_ and _neigh-fs_ , respectively. It is important to note
here that _neigh-fs_ is only used in _FP SC-GAN_ as it is the unique method
that makes use of a deep feature space; (3) based on the classification
provided by the auxiliary network (_anet_). As our methods rely on a
clustering process, we need to determine the number of clusters in each
dataset. To do so, we average the results of five runs of each clustering
method. For the remaining experiments, we use the number of clusters that
yields the smallest Davies–Bouldin Index (DBI) [42].

The metrics we use to compare the different methods rely on Average
Displacement Error (ADE) that measures the average Euclidean distance between
the predicted positions and the ground truth and the Final Displacement Error
(FDE) that measures the Euclidean distance between the final predicted
position and the respective ground truth (at $t=T_{P}$). To compare both
deterministic point estimate predictors (_CVM_ and _RED_) to stochastic
multimodal models (_CF-GAN_ , _CF-VAE_ , _VAE-OURS_ , and _GAN-OURS_), we
provide the following metrics:

  1. 1.

Top-$3$ ADE/FDE (in meters) — used to assess the multimodal estimates produced
by generative models. From _CF-GAN_ and _CF-VAE_ , we sample $3$ trajectories
and evaluate the closest one to the ground truth, whereas from _GAN-OURS_ and
_VAE-OURS_ , we take the $3$ most likely trajectories and compare the closest
one to the ground truth.

  2. 2.

Top-$1$ ADE/FDE (in meters) — used to compare point estimate predictors to
stochastic multimodal models. From _CF-GAN_ and _CF-VAE_ , we use the first
prediction generated by the models, while from _GAN-OURS_ and _VAE-OURS_ , we
use the most likely trajectory.

Finally, to compare the ranking proposals methods, we use accuracy (in %). In
this case we compare the output of the ranking proposals methods to the soft
labels yielded by each clustering method.

###  IV-B Results

In this section we show the results obtained by our methods and the baselines
in the datasets, where bold scores denote the best score, and the results from
Deep Learning (DL)-based approaches are averaged over five runs. First, as the
main focus of our approach is to generate a probabilistic yet accurate set of
predictions, we depict in Tab. I the Top-3 ADE/FDE results for deep generative
approaches. Our methodology exhibits superior performance compared to the
baseline models across all datasets, indicating that among the three most
probable predicted trajectories, our system produces a more accurate
prediction. This finding reinforces the notion that generating multimodality
within the conditioning cluster, as opposed to relying on the latent space
learned through the _k-variety loss_ , leads to improved outcomes.
Furthermore, it is noteworthy to mention that the various clustering methods
and ranking proposal mechanisms yield similar results across the datasets.
However, in some specific datasets, one can find better results in other
configurations: in THÖR with _GAN-OURS_ , _cent_ yields $0.45\pm 0.02$ and
$0.75\pm 0.03$ and in ZARA2 where _TS k-Means_ followed by _neig_ yields
$0.37\pm 0.01$ and $0.62\pm 0.01$, for ADE and FDE, respectively.

TABLE I: Top-3 ADE/FDE ($\downarrow$) metrics in the test sets.

Datasets | _CF-GAN_ |  _GAN-OURS_ 1 | _CF-VAE_ |  _VAE-OURS_ 1
---|---|---|---|---
THÖR |  | $0.57\pm 0.01$
---
$1.04\pm 0.03$
| $\mathbf{0.53\pm 0.01}$
---
$\mathbf{0.84\pm 0.03}$
| $0.62\pm 0.02$
---
$1.05\pm 0.05$
| $\mathbf{0.56\pm 0.01}$
---
$\mathbf{0.89\pm 0.02}$
Argoverse |  | $1.62\pm 0.07$
---
$2.81\pm 0.14$
| $\mathbf{1.56\pm 0.02}$
---
$\mathbf{2.69\pm 0.02}$
| $1.96\pm 0.02$
---
$3.44\pm 0.06$
| $\mathbf{1.62\pm 0.02}$
---
$\mathbf{2.82\pm 0.04}$
ETH |  | $0.84\pm 0.03$
---
$1.64\pm 0.06$
| $\mathbf{0.77\pm 0.04}$
---
$\mathbf{1.60\pm 0.11}$
| $0.94\pm 0.02$
---
$1.84\pm 0.04$
| $\mathbf{0.82\pm 0.02}$
---
$\mathbf{1.60\pm 0.04}$
HOTEL |  | $0.87\pm 0.07$
---
$1.64\pm 0.12$
| $\mathbf{0.81\pm 0.10}$
---
$\mathbf{1.46\pm 0.11}$
| $1.08\pm 0.04$
---
$1.95\pm 0.06$
| $\mathbf{0.97\pm 0.08}$
---
$\mathbf{1.72\pm 0.14}$
UNIV |  | $0.56\pm 0.01$
---
$1.08\pm 0.02$
| $\mathbf{0.51\pm 0.01}$
---
$\mathbf{0.98\pm 0.03}$
| $0.61\pm 0.01$
---
$1.16\pm 0.01$
| $\mathbf{0.56\pm 0.01}$
---
$\mathbf{1.06\pm 0.02}$
ZARA1 |  | $0.43\pm 0.02$
---
$0.82\pm 0.07$
| $\mathbf{0.37\pm 0.01}$
---
$\mathbf{0.72\pm 0.03}$
| $0.48\pm 0.01$
---
$0.98\pm 0.04$
| $\mathbf{0.44\pm 0.01}$
---
$\mathbf{0.91\pm 0.03}$
ZARA2 |  | $0.46\pm 0.01$
---
$0.81\pm 0.05$
| $\mathbf{0.40\pm 0.01}$
---
$\mathbf{0.65\pm 0.03}$
| $0.49\pm 0.01$
---
$0.86\pm 0.05$
| $\mathbf{0.43\pm 0.01}$
---
$\mathbf{0.73\pm 0.01}$

1 _FP SC-GAN_ \+ _neig-fs_

The fact that our system performs better on the leave-one-dataset-out setting
suggests that the clusters are unbiased to the reference dataset. In
particular, Tab. II shows the results in the HOTEL dataset with _GAN-OURS_ ,
where the trajectories go in a different direction than most of the ones in
the training set [20]. Here we can see that the proposed _FP SC-GAN_ is more
robust to the distribution shift present in this dataset.

TABLE II: Top-3 ADE/FDE ($\downarrow$) metrics in HOTEL with GAN-OURS.

| Ranking
---
proposals
_K-means_ | _TS K-means_ | _FP SC-GAN_
_cent_ |  | $1.03\pm 0.05$
---
$1.80\pm 0.09$
| $1.04\pm 0.05$
---
$1.81\pm 0.06$
| $\mathbf{0.80\pm 0.10}$
---
$\mathbf{1.44\pm 0.12}$
_neig_ 1 |  | $0.98\pm 0.04$
---
$1.74\pm 0.06$
| $0.97\pm 0.11$
---
$1.71\pm 0.16$
| $\mathbf{0.81\pm 0.10}$
---
$\mathbf{1.46\pm 0.11}$
_anet_ |  | $1.02\pm 0.06$
---
$1.78\pm 0.10$
| $0.97\pm 0.04$
---
$1.70\pm 0.04$
| $\mathbf{0.90\pm 0.06}$
---
$\mathbf{1.59\pm 0.08}$

1 _neigh-ds_ for _k-Means_ and _TS K-means_ ; _neigh-fs_ for _FP SC-GAN_

To assess the variability of each model and the fine-grained accuracy, we also
provide in Tab. III the Top-1 ADE/FDE scores. Apart from HOTEL, this result
shows that our method yields similar Top-1 predictions to point estimate and
multimodal baselines, where _RED_ stood out the most. Nevertheless, when
considering a comparison between the generative models _CF-GAN_ and _CF-VAE_
and our proposed methods _GAN-OURS_ and _VAE-OURS_ , which share the same
network structure, our methods demonstrate superior performance in terms of
Top-3 scores across all datasets. Additionally, our methods achieve equal or
superior Top-1 scores in all datasets. Notably, our methods also effectively
alleviate the performance disparity resulting from the models’ variability
when comparing Top-3 and Top-1 results. On top of that, our methods yield more
information encoded in the probabilities assigned to the predicted
trajectories, thus, creating a space of probable future locations rather than
uninformative predictions. It is also interesting to note that _CVM_ provides
similar or better performance in human trajectory data. However, for road
agents’ trajectory data, this method cannot cope with the speed variation in
the trajectories.

TABLE III: Top-1 ADE/FDE ($\downarrow$) metrics in the test sets.

Datasets | _CVM_ | _RED_ | _CF-GAN_ |  _GAN-OURS_ 1 | _VAE_ |  _VAE-OURS_ 1
---|---|---|---|---|---|---
THÖR |  | $0.79$
---
$1.28$
| $\mathbf{0.65\pm 0.01}$
---
$\mathbf{1.06\pm 0.01}$
| $0.85\pm 0.09$
---
$1.68\pm 0.20$
| $0.76\pm 0.02$
---
$1.31\pm 0.05$
| $0.71\pm 0.02$
---
$1.30\pm 0.04$
| $0.71\pm 0.02$
---
$1.21\pm 0.04$
Argoverse |  | $2.57$
---
$3.93$
| $\mathbf{1.84\pm 0.01}$
---
$\mathbf{3.18\pm 0.02}$
| $2.41\pm 0.09$
---
$4.53\pm 0.17$
| $1.92\pm 0.02$
---
$3.27\pm 0.03$
| $2.69\pm 0.02$
---
$4.94\pm 0.02$
| $1.95\pm 0.01$
---
$3.39\pm 0.04$
ETH |  | $\mathbf{0.95}$
---
$2.11$
| $\mathbf{0.95\pm 0.01}$
---
$1.94\pm 0.02$
| $1.08\pm 0.08$
---
$2.18\pm 0.19$
| $0.96\pm 0.03$
---
$1.99\pm 0.05$
| $1.08\pm 0.03$
---
$2.15\pm 0.08$
| $\mathbf{0.95\pm 0.02}$
---
$1.95\pm 0.03$
HOTEL |  | $\mathbf{0.42}$
---
$\mathbf{0.74}$
| $1.03\pm 0.04$
---
$1.84\pm 0.06$
| $1.03\pm 0.05$
---
$1.99\pm 0.11$
| $0.95\pm 0.13$
---
$1.72\pm 0.19$
| $1.18\pm 0.05$
---
$2.21\pm 0.08$
| $1.09\pm 0.12$
---
$1.96\pm 0.18$
UNIV |  | $\mathbf{0.65}$
---
$1.29$
| $\mathbf{0.65\pm 0.01}$
---
$\mathbf{1.27\pm 0.01}$
| $0.74\pm 0.03$
---
$1.49\pm 0.05$
| $0.74\pm 0.01$
---
$1.44\pm 0.04$
| $0.71\pm 0.01$
---
$1.41\pm 0.01$
| $0.69\pm 0.01$
---
$1.36\pm 0.01$
ZARA1 |  | $0.54$
---
$1.05$
| $\mathbf{0.45\pm 0.01}$
---
$\mathbf{0.87\pm 0.01}$
| $0.60\pm 0.11$
---
$1.21\pm 0.24$
| $0.47\pm 0.01$
---
$0.92\pm 0.03$
| $0.64\pm 0.01$
---
$1.33\pm 0.03$
| $0.53\pm 0.01$
---
$1.10\pm 0.02$
ZARA2 |  | $0.55$
---
$0.91$
| $\mathbf{0.50\pm 0.01}$
---
$\mathbf{0.80\pm 0.01}$
| $0.65\pm 0.02$
---
$1.24\pm 0.09$
| $0.52\pm 0.01$
---
$0.86\pm 0.04$
| $0.60\pm 0.02$
---
$1.13\pm 0.07$
| $0.54\pm 0.01$
---
$0.93\pm 0.01$

1 _FP SC-GAN_ \+ _neig-fs_

In Fig. 3, we show qualitative results of the Top-3 predictions from our
methods and baselines in THÖR (left), Argoverse (center), and ZARA1 (right)
test sets. THÖR example pertains to a quite challenging scenario as the
heading change is sharp. Still, our method could capture this uncommon
behavior within the three most probable trajectories (with $p=0.26$), while
the most probable trajectory ($p=0.48$) is following the movement’s trend,
which is reasonable due to the most common constant velocity profile in humans
walking [20]. In Argoverse example, the auxiliary network plays an important
role in the hierarchical predictions: Top-1 prediction ($p_{1}=0.29$) is also
the closest to the ground truth; the second most likely trajectory
($p_{4}=0.23$) is following the same direction but with a shorter distance;
finally, the third most likely trajectory ($p=0.16$) goes in a different
direction, but we consider it a still reasonable prediction. Finally, in ZARA2
example, while _CF-GAN_ could not capture the static behavior ($X_{0}\sim
Y_{n_{pred}}$) but still yields a broad range of behaviors, our method
conditioned by the cluster id assigns the highest likelihood to the predicted
static behavior ($p=0.40$).

Figure 3: Top-3 predictions in test samples from THÖR (left), Argoverse
(center), and ZARA2 (right). $X_{0}$ denotes the first observed point,
$Y_{n_{pred}}$ denotes the last point of the ground-truth, and
$p_{i\in[0,K-1]}$ the probabilities provided by our ranking proposals methods.

###  IV-C Ranking Proposals Analysis

In this section, we analyze the ranking proposals methods with the estimates
from _GAN-OURS_. Tab. IV shows the accuracy of the ranking proposals methods
in the test sets of the train test split settings (THÖR and Argoverse). It is
evident that the accuracy of the ranking proposals methods directly affects
both Top-3 and Top-1 results presented in Tab. I and Tab. III, respectively. A
broad view of the results shows that the more accurate our ranking proposals
methods are, the better the ADE/FDE scores, specially Top-1 ADE/FDE. As it is
possible to observe within each clustering method and dataset, _anet_ is
(statistically) better only in THÖR for all clustering methods. We speculate
that this may be because the clusters in THÖR are closer to each other as
people were moving in the same environment (with similar moving patterns) in
both train and test sets. This phenomenon is less noticeable in Argoverse
since different behaviors stem from cars (agents and av) and other road agents
(others). Similarly, in the leave-one-dataset-out setting (see Tab. V), the
diversity of behaviors come from the different datasets. In the majority of
these datasets, our proposed distance-based methods (_cent_ , _neigh-ds_ and
_neigh-fs_) provide better results than an auxiliary deep neural network
(_anet_) across the different clustering methods. Furthermore, while a
constant-width MLP-based _anet_ provides accurate estimates, it
computationally scales as $\mathcal{O}({N_{L}}H_{U}^{2})$, where $N_{L}$ is
the number of layers of the MLP network and $H_{U}$ is the number of hidden
units per layer. On the contrary, distance-based methods, _centroids_ and
_neighbors_ , require $\mathcal{O}(K)$ and $\mathcal{O}(KN_{neig})$
computations, respectively. Hence, besides the fact that distance-based
methods do not require training an additional neural network, during
inference, they provide similar performance in _linear time_ while auxiliary
networks require _quadratic time_.

TABLE IV: Accuracy ($\uparrow$) of the ranking proposals methods in the test
sets of the tran test split setting.

| Clustering
---
method
| Ranking
---
proposals
THÖR | Argoverse
_k-Means_ | _cent_ | $83.0\pm 0.5$ | $95.1\pm 0.2$
| _neigh-ds_
---
$81.1\pm 0.8$ | $94.0\pm 0.2$
_anet_ | $\mathbf{86.6\pm 0.6}$ | $\mathbf{95.2\pm 0.2}$
_TS k-Means_ | _cent_ | $66.4\pm 0.4$ | $93.9\pm 0.9$
| _neigh-ds_
---
$65.8\pm 0.4$ | $94.6\pm 0.3$
_anet_ | $\mathbf{72.7\pm 0.8}$ | $\mathbf{96.0\pm 0.1}$
_FP SC-GAN_ | _cent_ | $64.3\pm 5.6$ | $\mathbf{96.5\pm 0.4}$
| _neigh-fs_
---
$68.0\pm 2.7$ | $96.3\pm 5.1$
_anet_ | $\mathbf{70.3\pm 1.3}$ | $94.9\pm 0.7$

TABLE V: Accuracy ($\uparrow$) of the ranking proposals methods in the test
sets in the leave-one-dataset-out setting.

| Clustering
---
method
| Ranking
---
proposals
ETH | HOTEL | UNIV | ZARA1 | ZARA2
_k-Means_ | _cent_ | $94.9\pm 1.0$ | $\mathbf{100.0\pm 0.0}$ | $\mathbf{84.0\pm 0.4}$ | $92.8\pm 0.2$ | $94.7\pm 0.3$
| _neigh-ds_
---
$\mathbf{97.7\pm 0.8}$ | $99.2\pm 0.3$ | $80.8\pm 1.0$ | $89.7\pm 0.9$ | $\mathbf{95.5\pm 0.2}$
_anet_ | $93.3\pm 2.0$ | $98.6\pm 0.4$ | $82.5\pm 0.9$ | $\mathbf{93.9\pm 0.9}$ | $95.2\pm 0.4$
_TS k-Means_ | _cent_ | $95.3\pm 1.0$ | $\mathbf{100.0\pm 0.0}$ | $\mathbf{86.6\pm 0.2}$ | $92.5\pm 0.2$ | $94.5\pm 0.1$
| _neigh-ds_
---
$\mathbf{97.7\pm 0.8}$ | $99.3\pm 0.0$ | $82.0\pm 0.9$ | $90.6\pm 0.6$ | $94.9\pm 0.1$
_anet_ | $94.5\pm 0.8$ | $98.3\pm 0.6$ | $84.1\pm 0.4$ | $\mathbf{93.2\pm 0.6}$ | $\mathbf{95.0\pm 0.3}$
_FP SC-GAN_ | _cent_ | $70.2\pm 11.2$ | $78.8\pm 8.7$ | $64.9\pm 2.1$ | $\mathbf{90.6\pm 3.5}$ | $\mathbf{91.4\pm 4.0}$
| _neigh-fs_
---
$\mathbf{75.3\pm 5.3}$ | $\mathbf{90.6\pm 6.2}$ | $\mathbf{65.2\pm 2.8}$ | $89.7\pm 5.1$ | $89.2\pm 2.2$
_anet_ | $68.6\pm 8.0$ | $83.3\pm 7.9$ | $55.8\pm 2.6$ | $\mathbf{90.6\pm 2.7}$ | $90.2\pm 3.2$

##  V Conclusion

In this paper, we propose a multi-stage probabilistic trajectory predictor:
displacement space transformation, clustering stage, proposals generation, and
ranking proposals. At the clustering stage, we propose a novel trajectory
clustering method (FP SC-GAN) based on deep features from a GAN framework. We
also propose distance-based ranking proposals methods for assigning
probabilities to the predictions.

We test our methods in two settings: train-test split and leave-one-dataset-
out. The former comprise human and road agents’ trajectory data, while the
latter only address pedestrians’ trajectory data. Experimental results show
that our system surpasses the multimodal generative baselines (with _k-variety
loss_) in Top-3 ADE/FDE scores. It also performs equally or better than
context-free generative baselines in Top-1 ADE/FDE scores. Moreover, the
proposed clustering method copes better with distributional shifts (HOTEL
dataset) than traditional clustering methods. Finally, our ranking proposals
methods based on distance similarity measures perform globally better than
auxiliary deep neural networks. It is even more remarkable since these
mechanisms do not require training an additional neural network and run in
_linear time_ , while a constant-width MLP runs in _quadratic time_.

## References

  * [1] J. J. Q. Yu, “Graph construction for traffic prediction: A data-driven approach,” _IEEE Trans. on Intell. Transp. Syst._ , vol. 23, no. 9, pp. 15 015–15 027, 2022.
  * [2] F. Li, J. Feng, H. Yan, G. Jin, F. Yang, F. Sun, D. Jin, and Y. Li, “Dynamic graph convolutional recurrent network for traffic prediction: Benchmark and solution,” _ACM Trans. Knowl. Discov. Data_ , vol. 17, no. 1, feb 2023.
  * [3] D. Singh and R. Srivastava, “Graph neural network with rnns based trajectory prediction of dynamic agents for autonomous vehicle,” _Appl. Intell._ , vol. 52, no. 11, p. 12801–12816, sep 2022.
  * [4] A. Dalgkitsis, P.-V. Mekikis, A. Antonopoulos, and C. Verikoukis, “Data driven service orchestration for vehicular networks,” _IEEE Trans. on Intell. Transp. Syst._ , vol. 22, no. 7, pp. 4100–4109, 2021.
  * [5] J. Dahl, G. R. d. Campos, and J. Fredriksson, “Prediction-uncertainty-aware threat detection for adas: A case study on lane-keeping assistance,” _IEEE Trans. on Intell. Vehicles_ , pp. 1–12, 2023.
  * [6] V. Kosaraju, A. Sadeghian, R. Martín-Martín, I. Reid, S. H. Rezatofighi, and S. Savarese, _Social-BiGAT: Multimodal Trajectory Forecasting Using Bicycle-GAN and Graph Attention Networks_. Red Hook, NY, USA: Curran Associates Inc., 2019.
  * [7] A. Sadeghian, V. Kosaraju, A. Sadeghian, N. Hirose, H. Rezatofighi, and S. Savarese, “Sophie: An attentive gan for predicting paths compliant to social and physical constraints,” in _2019 IEEE/CVF Conf. on Comput. Vision and Pattern Recognit. (CVPR)_ , 2019, pp. 1349–1358.
  * [8] H. Tang, P. Wei, J. Li, and N. Zheng, “Evostgat: Evolving spatiotemporal graph attention networks for pedestrian trajectory prediction,” _Neurocomputing_ , vol. 491, pp. 333–342, 2022.
  * [9] Y. Su, J. Du, Y. Li, X. Li, R. Liang, Z. Hua, and J. Zhou, “Trajectory forecasting based on prior-aware directed graph convolutional neural network,” _IEEE Trans. on Intell. Transp. Syst._ , vol. 23, no. 9, pp. 16 773–16 785, 2022.
  * [10] H. Minoura, T. Hirakawa, Y. Sugano, T. Yamashita, and H. Fujiyoshi, “Utilizing human social norms for multimodal trajectory forecasting via group-based forecasting module,” _IEEE Trans. on Intell. Vehicles_ , vol. 8, no. 1, pp. 836–850, 2023.
  * [11] P. Kothari and A. Alahi, “Safety-compliant generative adversarial networks for human trajectory forecasting,” _IEEE Trans. on Intell. Transp. Syst._ , vol. 24, no. 4, pp. 4251–4261, 2023.
  * [12] B. Xia, C. Wong, Q. Peng, W. Yuan, and X. You, “Cscnet: Contextual semantic consistency network for trajectory prediction in crowded spaces,” _Pattern Recognit._ , vol. 126, p. 108552, 2022.
  * [13] V. Kress, F. Jeske, S. Zernetsch, K. Doll, and B. Sick, “Pose and semantic map based probabilistic forecast of vulnerable road users’ trajectories,” _IEEE Trans. on Intell. Vehicles_ , vol. 8, no. 3, pp. 2592–2603, 2023.
  * [14] N. Deo, E. Wolff, and O. Beijbom, “Multimodal trajectory prediction conditioned on lane-graph traversals,” in _Proceedings of the 5th Conf. on Robot Learning_ , ser. Proceedings of Mach. Learning Research, A. Faust, D. Hsu, and G. Neumann, Eds., vol. 164. PMLR, 08–11 Nov 2022, pp. 203–212.
  * [15] I. Bae, J.-H. Park, and H.-G. Jeon, “Non-probability sampling network for stochastic human trajectory prediction,” in _Proceedings of the IEEE/CVF Conf. on Comput. Vision and Pattern Recognit. (CVPR)_ , June 2022, pp. 6477–6487.
  * [16] W. Chen, F. Zheng, L. Shi, Y. Zhu, H. Sun, and N. Zheng, “Multiple goals network for pedestrian trajectory prediction in autonomous driving,” in _2022 IEEE 25th Int. Conf. on Intell. Transp. Syst. (ITSC)_. IEEE Press, 2022, p. 717–722.
  * [17] A. Gupta, J. Johnson, L. Fei-Fei, S. Savarese, and A. Alahi, “Social gan: Socially acceptable trajectories with generative adversarial networks,” in _IEEE/CVF Conf. on Comput. Vision and Pattern Recognit._ , 2018, pp. 2255–2264.
  * [18] P. Kothari, S. Kreiss, and A. Alahi, “Human trajectory forecasting in crowds: A deep learning perspective,” _IEEE Trans. on Intell. Transp. Syst._ , pp. 1–15, 2020.
  * [19] S. Becker, R. Hug, W. Hübner, and M. Arens, “Red: A simple but effective baseline predictor for the trajnet benchmark,” in _ECCV Workshops_ , 2018\.
  * [20] C. Schöller, V. Aravantinos, F. Lay, and A. Knoll, “What the constant velocity model can teach us about pedestrian motion prediction,” _IEEE Robot. and Automat. Lett._ , vol. 5, no. 2, pp. 1696–1703, 2020.
  * [21] F. Giuliari, I. Hasan, M. Cristani, and F. Galasso, “Transformer networks for trajectory forecasting,” in _2020 25th Int. Conf. on Pattern Recognit. (ICPR)_. Los Alamitos, CA, USA: IEEE Comput. Society, jan 2021, pp. 10 335–10 342.
  * [22] J. Sun, Y. Li, H. Fang, and C. Lu, “Three steps to multimodal trajectory prediction: Modality clustering, classification and synthesis,” _2021 IEEE/CVF Int. Conf. on Comput. Vision (ICCV)_ , pp. 13 230–13 239, 2021.
  * [23] W. Chen, Z. Yang, L. Xue, J. Duan, H. Sun, and N. Zheng, “Multimodal pedestrian trajectory prediction using probabilistic proposal network,” _IEEE Trans. on Circuits and Syst. for Video Technology_ , pp. 1–1, 2022\.
  * [24] M. Kang, J. Fu, S. Zhou, S. Zhang, and N. Zheng, “Learning to predict diverse trajectory from human motion patterns,” _Neurocomputing_ , vol. 504, pp. 123–131, 2022.
  * [25] S. Liu, T. Wang, D. Bau, J.-Y. Zhu, and A. Torralba, “Diverse image generation via self-conditioned gans,” in _2020 IEEE/CVF Conf. on Comput. Vision and Pattern Recognit. (CVPR)_ , 2020, pp. 14 274–14 283.
  * [26] T. Rodrigues de Almeida, E. Gutierrez Maestro, and O. Martinez Mozos, “Context-free self-conditioned gan for trajectory forecasting,” in _2022 21st IEEE Int. Conf. on Mach. Learning and Applications (ICMLA)_ , 2022, pp. 1218–1223.
  * [27] P. Dendorfer, A. Ošep, and L. Leal-Taixé, “Goal-gan: Multimodal trajectory prediction based on goal position estimation,” in _Asian Conf. on Comput. Vision (ACCV)_ , 2021, pp. 405–420.
  * [28] H. Sun, Z. Zhao, and Z. He, “Reciprocal learning networks for human trajectory prediction,” in _2020 IEEE/CVF Conf. on Comput. Vision and Pattern Recognit. (CVPR)_. Los Alamitos, CA, USA: IEEE Comput. Society, jun 2020, pp. 7414–7423.
  * [29] T. Salzmann, B. Ivanovic, P. Chakravarty, and M. Pavone, “Trajectron++: Dynamically-Feasible Trajectory Forecasting With Heterogeneous Data,” _arXiv e-prints_ , p. arXiv:2001.03093, Jan. 2020.
  * [30] T. Phan-Minh, E. C. Grigore, F. A. Boulton, O. Beijbom, and E. M. Wolff, “Covernet: Multimodal behavior prediction using trajectory sets,” in _2020 IEEE/CVF Conf. on Comput. Vision and Pattern Recognit. (CVPR)_ , 2020, pp. 14 062–14 071.
  * [31] Y. Ma, J. Inala, D. Jayaraman, and O. Bastani, “Likelihood-based diverse sampling for trajectory forecasting,” in _2021 IEEE/CVF Int. Conf. on Comput. Vision (ICCV)_. Los Alamitos, CA, USA: IEEE Comput. Society, oct 2021, pp. 13 259–13 268.
  * [32] B. Ivanovic, K.-H. Lee, P. Tokmakov, B. Wulfe, R. Mcllister, A. Gaidon, and M. Pavone, “Heterogeneous-agent trajectory forecasting incorporating class uncertainty,” in _2022 IEEE/RSJ Int. Conf. on Intell. Robots and Syst. (IROS)_ , 2022, pp. 12 196–12 203.
  * [33] L. Calem, H. Ben-Younes, P. Pérez, and N. Thome, “Diverse probabilistic trajectory forecasting with admissibility constraints,” in _2022 26th Int. Conf. on Pattern Recognit. (ICPR)_ , 2022, pp. 3478–3484.
  * [34] X. Jin and J. Han, _K-Means Clustering_. Springer US, 2010, pp. 563–564.
  * [35] R. Tavenard, J. Faouzi, G. Vandewiele, F. Divo, G. Androz, C. Holtz, M. Payne, R. Yurchak, M. Rußwurm, K. Kolar, and E. Woods, “Tslearn, a mach. learning toolkit for time series data,” _Journal of Mach. Learning Research_ , vol. 21, no. 118, pp. 1–6, 2020.
  * [36] M. Cuturi and M. Blondel, “Soft-dtw: A differentiable loss function for time-series,” in _Proceedings of the 34th Int. Conf. on Mach. Learning \- Volume 70_ , ser. ICML’17. JMLR.org, 2017, p. 894–903.
  * [37] A. Rudenko, T. P. Kucner, C. S. Swaminathan, R. T. Chadalavada, K. O. Arras, and A. J. Lilienthal, “Thör: Human-robot navigation data collection and accurate motion trajectories dataset,” _IEEE Robot. and Automat. Lett._ , vol. 5, no. 2, pp. 676–682, 2020.
  * [38] M.-F. Chang, J. W. Lambert, P. Sangkloy, J. Singh, S. Bak, A. Hartnett, D. Wang, P. Carr, S. Lucey, D. Ramanan, and J. Hays, “Argoverse: 3d tracking and forecasting with rich maps,” in _IEEE/CVF Conf. on Comput. Vision and Pattern Recognit._ , 2019.
  * [39] S. Pellegrini, A. Ess, K. Schindler, and L. van Gool, “You’ll never walk alone: Modeling social behavior for multi-target tracking,” in _2009 IEEE 12th Int. Conf. on Comput. Vision_ , 2009, pp. 261–268.
  * [40] L. Leal-Taixé, M. Fenzi, A. Kuznetsova, B. Rosenhahn, and S. Savarese, “Learning an image-based motion context for multiple people tracking,” in _2014 IEEE Conf. on Comput. Vision and Pattern Recognit._ , 2014, pp. 3542–3549.
  * [41] A. Rudenko, W. Huang, L. Palmieri, K. O. Arras, and A. Lilienthal, “Atlas: a benchmarking tool for human motion prediction algorithms,” in _Robot.: Sci. and Syst._ , 2021.
  * [42] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” _IEEE Trans. on Pattern Anal. and Mach. Intell._ , vol. PAMI-1, no. 2, pp. 224–227, 1979\.