=1pt

# Learning Temporal Point Processes for
Efficient Retrieval of Continuous Time Event Sequences

Vinayak Gupta∗, Srikanta Bedathur∗ and Abir De†

###### Abstract

Recent developments in predictive modeling using marked temporal point
processes (MTPP) have enabled an accurate characterization of several real-
world applications involving continuous-time event sequences (CTESs). However,
the retrieval problem of such sequences remains largely unaddressed in
literature. To tackle this, we propose NeuroSeqRet which learns to retrieve
and rank a relevant set of continuous-time event sequences for a given query
sequence, from a large corpus of sequences. More specifically, NeuroSeqRet
first applies a trainable unwarping function on the query sequence, which
makes it comparable with corpus sequences, especially when a relevant query-
corpus pair has individually different attributes. Next, it feeds the unwarped
query sequence and the corpus sequence into MTPP guided neural relevance
models. We develop two variants of the relevance model which offer a tradeoff
between accuracy and efficiency. We also propose an optimization framework to
learn binary sequence embeddings from the relevance scores, suitable for the
locality-sensitive hashing leading to a significant speedup in returning top-K
results for a given query sequence. Our experiments with several datasets show
the significant accuracy boost of NeuroSeqRet beyond several baselines, as
well as the efficacy of our hashing mechanism.

##  1 Introduction

The recent developments in marked temporal point processes (MTPP) has
dramatically improved the predictive analytics in several real world
applications— from information diffusion in social networks to healthcare— by
characterizing them with continuous-time event sequences (CTESs) (Tabibian et
al. 2019; Gupta et al. 2021a; Samanta et al. 2017; De et al. 2018; Valera et
al. 2014; Rizoiu et al. 2017; Wang et al. 2017; Daley and Vere-Jones 2007; Guo
et al. 2018; Du et al. 2015; Tabibian et al. 2019; Kumar et al. 2019; De et
al. 2016; Zhang et al. 2021; Du et al. 2016; Farajtabar et al. 2017; Jing and
Smola 2017; Saha et al. 2018; Gupta and Bedathur 2021; Likhyani et al. 2020).
In this context, given a query sequence, retrieval of _relevant_ CTESs from a
corpus of sequences is a challenging problem having a wide variety of search-
based applications. For example, in audio or music retrieval, one may like to
search sequences having different audio or music signatures; in social
network, retrieval of trajectories of information diffusion, relevant to a
given trajectory can assist in viral marketing, fake news detection, _etc_.
Despite having a rich literature on searching similar time-series (Blondel et
al. 2021; Gogolou et al. 2020; Alaee et al. 2020; Yoon et al. 2019; Cai et al.
2019; Shen et al. 2018; Cuturi and Blondel 2017; Paparrizos and Gravano 2015),
the problem of designing retrieval models specifically for CTES has largely
been unaddressed in the past. Moreover, as shown in our experiments, the
existing search methods for time sequences are largely ineffective for a CTES
retrieval task, since the underlying characterization of the sequences vary
across these two domains.

###  1.1 Present Work

In this paper, we first introduce NeuroSeqRet, a family of supervised
retrieval models for continuous-time event sequences and then develop a
trainable locality sensitive hashing (LSH) based method for efficient
retrieval over very large datasets. Specifically, our contributions are as
follows:

Query unwarping. The notion of relevance between two sequences varies across
applications. A relevant sequence pair can share very different individual
attributes, which can mislead the retrieval model if the sequences are
compared as-it-is. In other words, an observed sequence may be a warped
transformation of a hidden sequence (Xu et al. 2018; Gervini and Gasser 2004).
To tackle this problem, NeuroSeqRet first applies a trainable unwarping
function on the query sequence before the computation of a relevance score.
Such an unwarping function is a monotone transformation, which ensures that
the chronological order of events across the observed and the unwarped
sequences remains the same (Xu et al. 2018).

Neural relevance scoring model. In principle, the relevance score between two
sequences depends on their latent similarity. We measure such similarity by
comparing the generative distribution between the query-corpus sequence pairs.
In detail, we feed the unwarped query sequence and the corpus sequence into a
neural MTPP based relevance scoring model, which computes the relevance score
using a Fisher kernel (Jaakkola et al. 1999) between the corpus and the
unwarped query sequences. Such a kernel offers two key benefits over other
distribution similarity measures, _e.g._ , KL divergence or Wasserstein
distance: (i) it computes a natural similarity score between query-corpus
sequence pairs in terms of the underlying generative distributions; and, (ii)
it computes a dot product between the gradients of log-likelihoods of the
sequence pairs, which makes it compatible with locality-sensitive hashing for
certain design choices and facilitates efficient retrieval. In this context,
we provide two MTPP models, leading to two variants of NeuroSeqRet, which
allows a nice tradeoff between accuracy and efficiency.

SelfAttn-NeuroSeqRet: Here, we use transformer Hawkes process (Zuo et al.
2020) which computes the likelihood of corpus sequences independently of the
query sequence. Such a design admits precomputable corpus likelihoods, which
in turn allows for prior indexing of the corpus sequences before observing the
unseen queries. This setup enables us to apply LSH for efficient retrieval.

CrossAttn-NeuroSeqRet: Here, we propose a novel cross attention based neural
MTPP model to compute the sequence likelihoods. Such a cross-attention
mechanism renders the likelihood of corpus sequence dependent on the query
sequence, making it a more powerful retrieval model. While CrossAttn-
NeuroSeqRet is not directly compatible with such a hashing based retrieval, it
can be employed in a telescopic manner— where a smaller set of relevant
candidate set is first retrieved using LSH applied on top of SelfAttn-
NeuroSeqRet, and then reranked using CrossAttn-NeuroSeqRet.

Having computed the relevance scores, we learn the unwarping function and the
MTPP model by minimizing a pairwise ranking loss, based on the ground truth
relevance labels.

Scalable retrieval. Next, we use the predictions made by SelfAttn-NeuroSeqRet
to develop a novel hashing method that enables efficient sequence retrieval.
More specifically, we propose an optimization framework that compresses the
learned sequence embeddings into binary hash vectors, while simultaneously
limiting the loss due to compression. Then, we use locality-sensitive hashing
(Gionis et al. 1999) to bucketize the sequences into hash buckets, so that
sequences with similar hash representations share the same bucket. Finally,
given a query sequence, we consider computing relevance scores only with the
sequences within its bucket. Such a hashing mechanism combined with high-
quality sequence embeddings achieves fast sequence retrieval with no
significant loss in performance.

Finally, our experiments with real-world datasets from different domains show
that both variants of NeuroSeqRet outperform several baselines including the
methods for continuous-time series retrieval. Moreover, we observe that our
hashing method applied on SelfAttn-NeuroSeqRet can make a trade-off between
the retrieval accuracy and efficiency more effectively than baselines based on
random hyperplanes as well as exhaustive enumeration.

##  2 Preliminaries

In this section, we first sketch an outline of marked temporal point processes
(MTPP) and then setup our problem of retrieving a set of continuous time event
sequences relevant to a given query sequence.

###  2.1 Marked Temporal Point Processes: Overview

Continuous time event sequences (CTESs). Marked temporal point processes
(MTPP) are stochastic processes which capture the generative mechanism of a
sequence of discrete events localized in continuous time. Here, an event $e$
is realized using a tuple $(t,x)$, where $t\in\mathbb{R}_{+}$ and
$x\in\mathcal{X}$ are the arrival time and the mark of the event $e$. Then, we
use $\mathcal{H}(t)$ to denote a continuous time event sequence (CTES) where
each event has arrived until and excluding time $t$, _i.e._ ,
$\mathcal{H}(t):=\left\\{e_{i}=(t_{i},x_{i})\,|\,t_{i-1}<t_{i}<t\right\\}$.
Moreover we use $\mathcal{T}(t)$ and $\mathcal{M}(t)$ to denote the sequence
of arrival times $\left\\{t_{i}\,|\,e_{i}\in\mathcal{H}(t)\right\\}$ and the
marks $\left\\{x_{i}\,|\,e_{i}\in\mathcal{H}(t)\right\\}$. Finally, we denote
the counting process $N(t)$ as counts of the number of events happened until
and excluding time $t$, encapsulating the generative mechanism of the arrival
times.

Generative model for CTES. The underlying MTPP model consists of two
components— (i) the dynamics of the arrival times and (ii) the dynamics of the
distribution of marks. Most existing works (Du et al. 2016; Zhang et al. 2020;
Mei et al. 2019; Mei and Eisner 2017; Shelton et al. 2018; Zuo et al. 2020)
model the first component using an intensity function which explicitly models
the likelihood of an event in the infinitesimal time window $[t,t+dt)$, _i.e._
, $\lambda(t)=\text{Pr}(dN(t)=1|\mathcal{H}(t))$. In contrast, we use an
intensity free approach following the proposal by Shchur et al. (2020), where
we explicitly model the distribution of the arrival time $t$ of the next event
$e$. Specifically, we denote the density $\rho$ of the arrival time and the
distribution $m$ of the mark of the next event as follows:

$\displaystyle\rho(t)dt$ $\displaystyle=\text{Pr}(e\text{ in
}[t,t+dt)\,|\,\mathcal{H}(t)),$ (1) $\displaystyle m(x)$
$\displaystyle=\text{Pr}(x\,|\,\mathcal{H}(t))$ (2)

As discussed by Shchur et al. (2020), such an intensity free MTPP model enjoys
several benefits over the intensity based counterparts, in terms of
facilitating efficient training, scalable prediction, computation of expected
arrival times, etc. Given a sequence of observed events $\mathcal{H}(T)$
collected during the time interval $(0,T]$, the likelihood function is given
by:

$\displaystyle
p(\mathcal{H}(T))=\textstyle\prod_{e_{i}=(t_{i},x_{i})\in\mathcal{H}(T)}\rho(t_{i})\times
m(x_{i})$ (3)

###  2.2 Problem Setup

Next, we setup our problem of retrieving a ranked list of sequence from a
corpus of continuous time event sequences (CTESs) which are relevant to a
given query CTES.

Query and corpus sequences, relevance labels. We operate on a large corpus of
sequences $\left\\{\mathcal{H}_{c}(T_{c})\,|\,c\in\mathcal{C}\right\\}$, where
$\mathcal{H}_{c}(T_{c})=\\{(t^{(c)}_{i},x^{(c)}_{i})\,|\,t^{(c)}_{i}<T_{c}\\}$.
We are given a set of query sequences
$\left\\{\mathcal{H}_{q}(T_{q})\,|\,q\in\mathcal{Q}\right\\}$ with
$\mathcal{H}_{q}(T_{q})=\\{(t^{(q)}_{i},x^{(q)}_{i})\,|\,t^{(q)}_{i}<T_{q}\\}$,
as well as a query-specific relevance label for the set of corpus sequences.
That is, for a given query sequence $\mathcal{H}_{q}$, we have:
$y(\mathcal{H}_{q},\mathcal{H}_{c})=+1$ if $\mathcal{H}_{c}$ is marked as
relevant to $\mathcal{H}_{q}$ and $y(\mathcal{H}_{q},\mathcal{H}_{c})=-1$
otherwise.

We define
$\mathcal{C}_{q{+}}=\\{c\in\mathcal{C}\,|\,y(\mathcal{H}_{q},\mathcal{H}_{c})=+1\\},\text{and,
}\mathcal{C}_{q{-}}=\\{c\in\mathcal{C}\,|\,y(\mathcal{H}_{q},\mathcal{H}_{c})=-1\\}$,
with $\mathcal{C}=\mathcal{C}_{q{+}}\cup\mathcal{C}_{q{-}}$. Finally, we
denote $T=\max\\{T_{q},T_{c}\,|\,q\in\mathcal{Q},c\in\mathcal{C}\\}$ as the
maximum time of the data collection.

Our goal. We aim to design an efficient CTES retrieval system, which would
return a list of sequences from a known corpus of sequences, relevant to a
given query sequence $\mathcal{H}_{q}$. Therefore, we can view a sequence
retrieval task as an instance of ranking problem. Similar to other information
retrieval algorithms, a CTES retrieval algorithm first computes the estimated
relevance $s(\mathcal{H}_{q},\mathcal{H}_{c})$ of the corpus sequence
$\mathcal{H}_{c}$ for a given query sequence $\mathcal{H}_{q}$ and then
provides a ranking of $\mathcal{C}$ in the decreasing order of their scores.

##  3 NeuroSeqRet Model

In this section, we describe NeuroSeqRet family of MTPP-based models that we
propose for the retrieval of continuous time event sequences (CTES). We begin
with an outline of its two key components.

###  3.1 Components of NeuroSeqRet

NeuroSeqRet models the relevance scoring function between query and corpus
sequence pairs. However the relevance of a corpus sequence to the query is
latent and varies widely across applications. To accurately characterize this
relevance measure, NeuroSeqRet works in two steps. First, it unwarps the query
sequences to make them compatible for comparing with the corpus sequences.
Then, it computes the pairwise relevance score between the query and corpus
sequences using neural MTPP models.

Unwarping query sequences. Direct comparison between a query and a corpus
sequence can provide misleading outcomes, since they also contain their own
individual idiosyncratic factors in addition to sharing some common
attributes. In fact, a corpus sequence can be highly relevant to the query,
despite greatly varying in timescale, initial time, etc. In other words, it
may have been generated by applying a warping transformation on a latent
sequence (Xu et al. 2018; Gervini and Gasser 2004). Thus, a direct comparison
between a relevant sequence pair may give poor relevance score.

To address this challenge, we first apply a trainable unwarping function (Xu
et al. 2018) $U(\cdot)$ on the arrival times of a query sequence, which
enhances its compatibility for comparing it with the corpus sequences. More
specifically, we define
$U(\mathcal{H}_{q}):=\\{(U(t^{(q)}_{i}),x^{(q)}_{i})\\}$. In general, $U$
satisfies two properties (Xu et al. 2018; Gervini and Gasser 2004):
_unbiasedness_ , _i.e._ , having a small value of $\left\|U(t)-t\right\|$ and
_monotonicity_ , _i.e._ , ${d\,U(t)}/{dt}\geq 0$. These properties ensure that
the chronological order of the events across both the warped observed sequence
and the unwarped sequence remains same. Such a sequence transformation learns
to capture the similarity between two sequences, even if it is not apparent
due to different individual factors, as we shall later in our experiments
(Figure 1).

Computation of relevance scores. Given a query sequence $\mathcal{H}_{q}$ and
a corpus sequence $\mathcal{H}_{c}$, we compute the relevance score
$s(\mathcal{H}_{q},\mathcal{H}_{c})$ using two similarity scores, _e.g._ , (i)
a _model independent_ sequence similarity score and (ii) a _model based_
sequence similarity score.

_—Model independent similarity score:_ Computation of model independent
similarity score between two sequences is widely studied in literature (Xiao
et al. 2017; Mueen and Keogh 2016; Su et al. 2020; Abanda et al. 2019; Müller
2007). They are computed using different distance measures between two
sequences, _e.g._ , DTW, Wasserstein distance, etc. and therefore, can be
immediately derived from data without using the underlying MTPP model. In this
work, we compute the model independent similarity score,
$\textsc{Sim}_{U}(\mathcal{H}_{q},\mathcal{H}_{c})$, between $\mathcal{H}_{q}$
and $\mathcal{H}_{c}$ as follows:

$\displaystyle\textsc{Sim}_{U}(\mathcal{H}_{q},\mathcal{H}_{c})$
$\displaystyle=-\Delta_{t}(U(\mathcal{H}_{q}),\mathcal{H}_{c})-\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})$
(4)

where, $\Delta_{t}$ and $\Delta_{x}$ are defined as:

$\displaystyle\Delta_{t}(U(\mathcal{H}_{q}),\mathcal{H}_{c})$
$\displaystyle=\sum_{i=0}^{H_{\min}}\left|U(t^{(q)}_{i})-t^{(c)}_{i}\right|+\sum_{\begin{subarray}{c}t_{i}\in\mathcal{H}_{c}\cup\mathcal{H}_{q}\\\
i>|H_{\min}|\end{subarray}}(T-t_{i}),$
$\displaystyle\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})$
$\displaystyle=\sum_{i=0}^{H_{\min}}\mathbb{I}[x^{(q)}_{i}\neq
x^{(c)}_{i}]+\big{|}|\mathcal{H}_{c}|-|\mathcal{H}_{q}|\big{|}.$

Here, $H_{\min}=\min\\{|\mathcal{H}_{q}|,|\mathcal{H}_{c}|\\}$,
$T=\max\\{T_{q},T_{c}\\}$ where the events of $\mathcal{H}_{q}$ and
$\mathcal{H}_{c}$ are gathered until time $T_{q}$ and $T_{c}$ respectively;
$\Delta_{t}(U(\mathcal{H}_{q}),\mathcal{H}_{c})$ is the Wasserstein distance
between the unwarped arrival time sequence $U(\mathcal{H}_{q})$ and the corpus
sequence (Xiao et al. 2017) and, $\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})$
measures the matching error for the marks, wherein the last term penalizes the
marks of last $|\mathcal{H}_{c}|-|\mathcal{H}_{q}|$ events of
$|\mathcal{H}_{c}|$.

_—Model based similarity score using Fisher kernel:_ We hypothesize that the
relevance score $s(\mathcal{H}_{q},\mathcal{H}_{c})$ also depends on a latent
similarity which may not be immediately evident from the observed query and
corpus sequences even after unwarping. Such a similarity can be measured by
comparing the generative distributions of the query-corpus sequence pairs. To
this end, we first develop an MTPP based generative model
$p_{\theta}(\mathcal{H})$ parameterized by $\theta$ and then compute a
similarity score using the Fisher similarity kernel between the unwarped query
and corpus sequence pairs $(U(\mathcal{H}_{q}),\mathcal{H}_{c})$ (Jaakkola et
al. 1999). Specifically, we compute the relevance score between the unwarped
query sequence $U(\mathcal{H}_{q})$ and the corpus sequence $\mathcal{H}_{c}$
as follows:

$\displaystyle\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})=\bm{v}_{p_{\theta}}(U(\mathcal{H}_{q}))^{\top}\bm{v}_{p_{\theta}}(\mathcal{H}_{c})$
(5)

where $\theta$ is the set of trainable parameters;
$\bm{v}_{p_{\theta}}(\cdot)$ is given by

$\displaystyle\bm{v}_{p}(\mathcal{H})=\bm{I}^{-1/2}_{\theta}\nabla_{\theta}\log
p_{\theta}(\mathcal{H})/||\bm{I}^{-1/2}_{\theta}\nabla_{\theta}\log
p_{\theta}(\mathcal{H})||_{2},$

$\bm{I}_{\theta}$ is the Fisher information matrix (Jaakkola et al. 1999),
_i.e._ , $\bm{I}_{\theta}=\mathbb{E}_{\mathcal{H}\sim
p_{\theta}(\bullet)}\left[\nabla_{\theta}\log
p_{\theta}(\mathcal{H})\nabla_{\theta}\log
p_{\theta}(\mathcal{H})^{\top}\right]$. We would like to highlight that
$\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})$ in Eq. (5) is a
normalized version of Fisher kernel since $||\bm{v}_{p_{\theta}}(\cdot)||=1$.
Thus, $\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})$ measures the
cosine similarity between $\bm{v}_{p_{\theta}}(U(\mathcal{H}_{q}))$ and
$\bm{v}_{p_{\theta}}(\mathcal{H}_{c})$.

Note that, KL divergence or Wasserstein distance could also serve our purpose
of computing the latent similarity between the generative distributions.
However, we choose Fisher similarity kernel because of two reasons: (i) it is
known to be a natural similarity measure which allows us to use the underlying
generative model in a discriminative learning task (Jaakkola et al. 1999;
Sewell 2011); and, (ii) unlike KL divergence or other distribution
(dis)similarities, it computes the cosine similarity between
$\bm{v}_{p_{\theta}}(U(\mathcal{H}_{q}))$ and
$\bm{v}_{p_{\theta}}(\mathcal{H}_{c})$, which makes it compatible with
locality sensitive hashing (Charikar 2002).

Finally, we compute the relevance score as

$\displaystyle s_{p,U}\left(\mathcal{H}_{q},\mathcal{H}_{c}\right)$
$\displaystyle=\kappa_{p}\left(\mathcal{H}_{q},\mathcal{H}_{c}\right)+\gamma\textsc{Sim}_{U}\left(\mathcal{H}_{q},\mathcal{H}_{c}\right)$
(6)

where $\gamma$ is a hyperparameter.

###  3.2 Neural Parameterization of NeuroSeqRet

Here, we first present the neural architecture of the unwarping function and
then describe the MTPP models used to compute the model based similarity score
in Eq. (5). As we describe later, we use two MTPP models with different levels
of modeling sophistication, _viz._ , SelfAttn-NeuroSeqRet and CrossAttn-
NeuroSeqRet. In SelfAttn-NeuroSeqRet, the likelihood of a corpus sequence is
computed independently of the query sequence using a self attention based MTPP
model, _e.g._ , Transformer Hawkes Process (Zuo et al. 2020). As a result, we
can employ a locality sensitive hashing based efficient retrieval based
SelfAttn-NeuroSeqRet. In CrossAttn-NeuroSeqRet, on the other hand, we propose
a more expressive and novel cross attention MTPP model, where the likelihood
of a corpus sequence is dependent on the query sequence. Thus, our models can
effectively tradeoff between accuracy and efficiency.

Neural architecture of $U(\cdot)$. As discussed in Section 3.1, the unwarping
function $U(\cdot)$ should be unbiased and monotonic. To this end, we model
$U(\cdot)\approx U_{\phi}(\cdot)$ using a nonlinear monotone function which is
computed using an unconstrained monotone neural network (UMNN) (Wehenkel and
Louppe 2019), _i.e._ ,

$\displaystyle U_{\phi}(t)=\int_{0}^{t}u_{\phi}(\tau)d\tau+\eta,$ (7)

where $\phi$ is the parameter of the underlying neural network
$u_{\phi}(\cdot)$, $\eta\in\mathcal{N}(0,\sigma)$ and
$u_{\phi}:\mathbb{R}\to\mathbb{R}_{+}$ is a non-negative nonlinear function.
Since the underlying monotonicity can be achieved only by enforcing non-
negativity of the integrand $u_{\phi}$, UMNN admits an unconstrained, highly
expressive parameterization of monotonic functions. Therefore, any complex
unwarping function $U_{\phi}(\cdot)$ can be captured using Eq. (7), by
integrating a suitable neural model augmented with ReLU$(\cdot)$ in the final
layer. In other words, if $u_{\phi}$ is a universal approximator for positive
function, then $U_{\phi}$ can capture any differentiable unwarping function.
We impose an additional regularizer
$\frac{1}{\sigma^{2}}\int_{0}^{T}\left\|u_{\phi}(t)-1\right\|^{2}dt$ on our
training loss which ensures that $\left\|U(t)-t\right\|$ remains small.

Neural architecture of MTPP model $p_{\theta}(\cdot)$. We provide two variants
of $p_{\theta}(\cdot)$, which leads to two retrieval models, _viz._ ,
SelfAttn-NeuroSeqRet and CrossAttn-NeuroSeqRet.

SelfAttn-NeuroSeqRet: Here, we use Transformer Hawkes process (Zuo et al.
2020) which applies a self attention mechanism to model the underlying
generative process. In this model, the gradient of corpus sequences
$\bm{v}_{\theta}(\mathcal{H}_{c})=\nabla_{\theta}\log
p_{\theta}(\mathcal{H}_{c})$ are computed independently of the query sequence
$\mathcal{H}_{q}$. Once we train the retrieval model,
$\bm{v}_{\theta}(\mathcal{H}_{c})$ can be pre-computed and bucketized before
observing the test query. Such a model, together with the Fisher kernel based
cosine similarity scoring model, allows us to apply locality sensitive hashing
for efficient retrieval.

CrossAttn-NeuroSeqRet: The above self attention based mechanism models a query
agnostic likelihood of the corpus sequences. Next, we introduce a _cross
attention_ based MTPP model which explicitly takes into account of the
underlying query sequence while modeling the likelihood of the corpus
sequence. Specifically, we measure the latent relevance score between
$\mathcal{H}_{q}$ and $\mathcal{H}_{c}$ via a query-induced MTPP model built
using the cross attention between the generative process of both the
sequences. Given a query sequence $\mathcal{H}_{q}$ and the first $r$ events
of the corpus sequence $\mathcal{H}_{c}$, we parameterize the generative model
for $(r+1)$-th event, _i.e._ , $p(e^{(c)}_{r+1}\,|\,\mathcal{H}({t_{r}}))$ as
$p_{\theta{}}(\cdot)$, where
$p_{\theta{}}(e^{(c)}_{r+1})=\rho_{\theta{}}(t^{(c)}_{r+1})\,m_{\theta{}}(x^{(c)}_{r+1})$,
where $\rho$ and $m$ are the density and distribution functions for the
arrival time and the mark respectively, as described in Eq. (1).

_—Input Layer:_ For each event $e_{i}^{(q)}$ in the query sequence
$\mathcal{H}_{q}$ and each event $e_{j}^{(c)}$ in the first $r$ events in the
corpus sequence $\mathcal{H}_{c}$, the input layer computes the initial
embeddings $\bm{y}^{(q)}_{i}$ and $\bm{y}^{(c)}_{j}$ as follows:

$\displaystyle\bm{y}^{(q)}_{i}$
$\displaystyle=\bm{w}_{y,x}x^{(q)}_{i}+\bm{w}_{y,t}U(t^{(q)}_{i})$
$\displaystyle\quad+\bm{w}_{y,\Delta
t}\left(U(t^{(q)}_{i})-U(t^{(q)}_{i-1})\right)+\bm{b}_{y},\forall
i\in[|\mathcal{H}_{q}|]$ $\displaystyle\bm{y}^{(c)}_{j}$
$\displaystyle=\bm{w}_{y,x}x^{(c)}_{j}+\bm{w}_{y,t}t^{(c)}_{j}$
$\displaystyle\quad+\bm{w}_{y,\Delta
t}\left(t^{(c)}_{j}-t^{(c)}_{j-1}\right)+\bm{b}_{y},\forall
j\in[|\mathcal{H}_{c}(t_{r})|-1]$

where $\bm{w}_{\bullet,\bullet}$ and $\bm{b}_{y}$ are trainable parameters.

_—Attention layer:_ The second layer models the interaction between all the
query events and _the past corpus events_ , _i.e._ , $\mathcal{H}_{q}$ and
$\mathcal{H}_{c}(t_{r})$ using an attention mechanism. Specifically, following
the existing attention models (Vaswani et al. 2017; Kang and McAuley 2018; Li
et al. 2020) it first adds a trainable position embedding $\bm{p}$ with
$\bm{y}$— the output from the previous layer. More specifically, we have the
updates: $\bm{y}^{(q)}_{i}\leftarrow\bm{y}^{(q)}_{i}+\bm{p}_{i}$ and
$\bm{y}^{(c)}_{j}\leftarrow\bm{y}^{(c)}_{j}+\bm{p}_{j}$. where,
$\bm{p}_{\bullet}\in\mathbb{R}^{D}$. Next, we apply two linear transformations
on the vectors $[\bm{y}^{(q)}_{i}]_{i\in[|\mathcal{H}_{q}|]}$ and one linear
transformation on $[\bm{y}^{(c)}_{j}]_{j\in[r]}$, _i.e._ ,
$\bm{s}_{j}=\bm{W}^{S}\bm{y}^{(c)}_{j},\bm{k}_{i}=\bm{W}^{K}\bm{y}^{(q)}_{i},\bm{v}_{i}=\bm{W}^{V}\bm{y}^{(q)}_{i}.$
The state-of-the-art works on attention models (Vaswani et al. 2017; Zuo et
al. 2020; Kang and McAuley 2018; Li et al. 2020) often refer
$\bm{s}_{\bullet}$, $\bm{k}_{\bullet}$ and $\bm{v}_{\bullet}$ as query, key
and value vectors respectively. Similarly, we call the trainable weights
$\bm{W}^{S},\bm{W}^{K}$ and $\bm{W}^{V}$ as the Query, Key and Value matrices,
respectively. Finally, we use the standard attention recipe (Vaswani et al.
2017) to compute the final embedding vector $\bm{h}_{j}^{(c,q)}$ for the event
$e^{(c)}_{j}$, induced by query $\mathcal{H}_{q}$. Such a recipe adds the
values weighted by the outputs of a softmax function induced by the query and
key, _i.e._ ,

$\displaystyle\bm{h}^{(c,q)}_{j}=\sum_{i\in[|\mathcal{H}_{q}|]}\frac{\exp\left(\bm{s}_{j}^{\top}\bm{k}_{i}/\sqrt{D}\right)}{\sum_{i^{\prime}\in[|\mathcal{H}_{q}|]}\exp\left(\bm{s}_{j}^{\top}\bm{k}_{i^{\prime}}/\sqrt{D}\right)}\bm{v}_{i},$
(8)

_—Output layer:_ Given the vectors $\bm{h}^{(c,q)}_{j}$ provided by the
attention mechanism (8), we first apply a feed-forward neural network on them
to compute $\overline{\bm{h}}^{(c,q)}_{r}$ as follows:

$\overline{\bm{h}}^{(c,q)}_{r}=\sum_{j=1}^{r}\left[\bm{w}_{\overline{h}}\odot\text{ReLU}(\bm{h}^{(c,q)}_{j}\odot\bm{w}_{h,f}+\bm{b}_{h,o})+\bm{b}_{\overline{h}}\right],$

where $\bm{w}_{\bullet,\bullet}$, $\bm{w}_{\bullet}$ and $\bm{b}_{v}$.
Finally, we use these vectors to compute the probability density of the
arrival time of the next event $e^{(c)}_{r+1}$, _i.e._ ,
$\rho_{\theta{}}(t_{r+1})$ and the mark distribution $m_{\theta{}}(x_{r+1})$.
In particular, we realize $\rho_{\theta{}}(t_{r+1})$ using a log normal
distribution of inter-arrival times, _i.e._ ,

$\displaystyle
t^{(c)}_{r+1}-t^{(c)}_{r}\sim\textsc{LogNormal}\left(\mu_{e}\left(\overline{\bm{h}}^{(c,q)}_{r}\right),\sigma^{2}_{e}\left(\overline{\bm{h}}^{(c,q)}_{r}\right)\right),$

where,
$\left[\mu_{e}\left(\overline{\bm{h}}^{(c,q)}_{r}\right),\sigma_{e}\left(\overline{\bm{h}}^{(c,q)}_{r}\right)\right]=\bm{W}_{t,q}\overline{\bm{h}}^{(c,q)}_{r}+\bm{b}_{t,q}$.
Similarly, we model the mark distribution as,

$\displaystyle
m_{\theta{}}(x_{r+1})=\dfrac{\exp\left(\bm{w}_{x,m}^{\top}\overline{\bm{h}}^{(c,q)}+b_{x,m}\right)}{\sum_{x^{\prime}\in\mathcal{X}}\exp\left(\bm{w}_{x^{\prime},m}^{\top}\overline{\bm{h}}^{(c,q)}+b_{x^{\prime},m}\right)},$
(9)

where $\bm{W}_{\bullet,\bullet}$ are the trainable parameters. Therefore the
set of trainable parameters for the underlying MTPP models is
$\theta=\left\\{\bm{W}^{\bullet},\bm{W}_{\bullet,\bullet},\bm{w}_{\bullet},\bm{w}_{\bullet,\bullet},\bm{b}_{\bullet},\bm{b}_{\bullet,\bullet}\right\\}$.

###  3.3 Parameter Estimation

Given the query sequences $\left\\{\mathcal{H}_{q}\right\\}$, the corpus
sequences $\left\\{\mathcal{H}_{c}\right\\}$ along with their relevance labels
$\left\\{y(\mathcal{H}_{q},\mathcal{H}_{c})\right\\}$, we seek to find
$\theta$ and $\phi$ which ensure that:

$\displaystyle s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c_{+}})\gg
s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c_{-}})\,\forall\,c_{\pm}\in\mathcal{C}_{q\pm}.$
(10)

To this aim, we minimize the following pairwise ranking loss (Joachims 2002)
to estimate the parameters $\theta,\phi$:

$\displaystyle\underset{\theta,\phi}{\text{min}}\sum_{q\in\mathcal{Q}}\sum_{\begin{subarray}{c}c_{+}\in\mathcal{C}_{q{+}},\\\
c-\in\mathcal{C}_{q{-}}\end{subarray}}$
$\displaystyle\big{[}s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c_{-}})-s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c_{+}})+\delta\big{]}_{+},$

where, $\delta$ is a tunable margin.

##  4 Scalable Retrieval with Hashing

Once we learn the model parameters $\theta$ and $\phi$, we can rank the set of
corpus sequences $\mathcal{H}_{c}$ in the decreasing order of
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{{q{{}^{\prime}}}},\mathcal{H}_{c})$ for
a new query $\mathcal{H}_{{q{{}^{\prime}}}}$ and return top$-K$ sequences.
Such an approach requires $|\mathcal{C}|$ comparisons per each test query,
which can take a huge amount of time for many real-life applications where
$|\mathcal{C}|$ is high. However, for most practical query sequences, the
number of relevant sequences is a very small fraction of the entire corpus of
sequences. Therefore, the number of comparisons between query-corpus sequence
pairs can be reduced without significantly impacting the retrieval quality by
selecting a small number of candidate corpus sequences that are more likely to
be relevant to a query sequence.

###  4.1 Trainable Hashing for Retrieval

Computation of a trainable hash code. We first apply a trainable nonlinear
transformation $\Lambda_{\psi}$ with parameter $\psi$ on the gradients
$\bm{v}^{c}=\bm{v}_{p_{\theta}}(\mathcal{H}_{c})$ and then learn the binary
hash vectors
$\bm{\zeta}^{c}=\mathop{\mathrm{sign}}\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)\right)$
by solving the following optimization, where we use
$\tanh\left(\Lambda_{\psi}(\cdot)\right)$ as a smooth approximation of
$\mathop{\mathrm{sign}}\left(\Lambda_{\psi}(\cdot)\right)$.

$\displaystyle\min_{\psi}\frac{\eta_{1}}{|\mathcal{C}|}\sum_{c\in\mathcal{C}}\left|\bm{1}^{\top}\tanh\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)\right)\right|$
$\displaystyle\qquad\qquad\qquad+\frac{\eta_{2}}{|\mathcal{C}|}\sum_{c\in\mathcal{C}}\left\|\left|\tanh\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)\right)\right|-\bm{1}\right\|_{1}$
(11) $\displaystyle\qquad+\frac{2\eta_{3}}{{D\choose
2}}\cdot\bigg{|}\sum_{\begin{subarray}{c}c\in\mathcal{C}\\\ i\neq
j\in[D]\end{subarray}}\tanh\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)[i]\right)\cdot\tanh\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)[j]\right)\bigg{|}$

Algorithm 1 Efficient retrieval with hashing

0: Trained corpus embeddings
$\left\\{\bm{v}^{c}=\bm{v}_{p_{\theta}}(\mathcal{H}_{c})\right\\}$ using
SelfAttn-NeuroSeqRet; new query sequences
$\left\\{\mathcal{H}_{{q{{}^{\prime}}}}\right\\}$, $K$: # of corpus sequences
to return; trained models for SelfAttn-NeuroSeqRet and CrossAttn-NeuroSeqRet.

1: Output: $\left\\{L_{q{{}^{\prime}}}\right\\}$: top-$K$ relevant sequences
from $\left\\{\mathcal{H}_{c}\right\\}$.

2:
$\psi\leftarrow\textsc{TrainHashNet}\left(\Lambda_{\psi},[\bm{v}^{c}]_{c\in\mathcal{C}}\right)$

3: InitHashBuckets$(\cdot)$

4: for $c\in\mathcal{C}$ do

5:
$\bm{\zeta}^{c}\leftarrow\textsc{ComputeHashCode}\left(\bm{v}^{c};\Lambda_{\psi}\right)$

6: $\mathcal{B}\leftarrow\textsc{AssignBucket}(\bm{\zeta}^{c})$

7: end for

8: for each new query $\mathcal{H}_{{q{{}^{\prime}}}}$ do

9:
$\bm{v}^{q^{\prime}}\leftarrow\textsc{SelfAttn-}{\textsc{NeuroSeqRet}}(\mathcal{H}_{{q{{}^{\prime}}}})$

10:
$\bm{\zeta}^{q^{\prime}}\leftarrow\textsc{ComputeHashCode}(\bm{v}^{q^{\prime}};{\Lambda_{\psi}})$

11:
$\mathcal{B}\leftarrow\textsc{AssignBucket}(\bm{\zeta}^{{q{{}^{\prime}}}})$

12: for $c\in\mathcal{B}$ do

13:
$\bm{v}^{{q{{}^{\prime}}}}_{\text{cross}},\bm{v}^{c}_{\text{cross}}\leftarrow\textsc{CrossAttn-}{\textsc{NeuroSeqRet}}(\mathcal{H}_{{q{{}^{\prime}}}},\mathcal{H}_{c})$

14:
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q^{\prime}},\mathcal{H}_{c})\leftarrow\textsc{Score}(\bm{v}^{{q{{}^{\prime}}}}_{\text{cross}},\bm{v}^{c}_{\text{cross}},\mathcal{H}_{q},\mathcal{H}_{c})$

15: end for

16:
$L_{{q{{}^{\prime}}}}\leftarrow\textsc{Rank}(\left\\{s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q^{\prime}},\mathcal{H}_{c})\right\\},K)$

17: end for

18: Return $\left\\{L_{{q{{}^{\prime}}}}\right\\}$

Here $\sum_{i=1}^{3}\eta_{i}=1$. Moreover, different terms in Eq. (4.1) allow
the hash codes $\bm{\zeta}^{c}$ to have a set of four desired properties: (i)
the first term ensures that the numbers of $+1$ and $-1$ are evenly
distributed in the hash vectors
$\bm{\zeta}^{c}=\tanh\left(\Lambda_{\psi}\left(\bm{v}^{c}\right)\right)$; (ii)
the second term encourages the entries of $\bm{\zeta}^{c}$ become as close to
$\pm 1$ as possible so that $\tanh(\cdot)$ gives an accurate approximation of
$\mathop{\mathrm{sign}}(\cdot)$ ; (iii) the third term ensures that the
entries of the hash codes $\bm{\zeta}^{c}$ contain independent information and
therefore they have no redundant entries. Trainable hashing has been used in
other domains of information retrieval including graph hashing (Liu et al.
2014; Qin et al. 2020; Roy et al. 2020), document retrieval (Zhang et al.
2010; Salakhutdinov and Hinton 2009; Zamani Dadaneh et al. 2020). However, to
the best of our knowledge, such an approach has never been proposed for
continuous time sequence retrieval.

Outline of our retrieval method. We summarize our retrieval procedure in
Algorithm 1. We are given gradient vectors
$\bm{v}^{c}=\bm{v}_{p_{\theta}}(\mathcal{H}_{c})$ obtained by training
SelfAttn-NeuroSeqRet. Next, we train an additional neural network
$\Lambda_{\psi}$ parameterized by $\psi$ (TrainHashNet$()$, line 2), which is
used to learn a binary hash vector $\bm{\zeta}^{c}$ for each sequence
$\mathcal{H}_{c}$. Then these hash codes are used to arrange corpus sequences
in different hash buckets (for-loop in lines 4–7) using the algorithm proposed
by Gionis et al. (1999), so that two sequences
$\mathcal{H}_{c},\mathcal{H}_{c^{\prime}}$ lying in the same hash bucket have
very high value of cosine similarity $\cos(\bm{v}^{c},\bm{v}^{c^{\prime}})$
(bucketization details are in Appendix B). Finally, once a new query
$\mathcal{H}_{q{{}^{\prime}}}$ comes, we first compute
$\bm{v}^{{q{{}^{\prime}}}}$ using the trained SelfAttn-NeuroSeqRet model and
then compute the binary hash codes $\bm{\zeta}^{{q{{}^{\prime}}}}$ using the
trained hash network $\Lambda_{\psi}$ (lines 9–10). Next, we assign an
appropriate bucket $\mathcal{B}$ to it (line 11) and finally compare it with
only the corpus sequences in the same bucket, _i.e._ ,
$\mathcal{H}_{c}\in\mathcal{B}$ (lines 12–15) using our model.

Recall that we must use SelfAttn-NeuroSeqRet to compute gradient vectors for
subsequent hash code generation (in lines 9–10). However, at the last stage
for final score computation and ranking, we can use any variant of NeuroSeqRet
(in line 13), preferably CrossAttn-NeuroSeqRet, since the corpus sequences
have already been indexed by our LSH method.

##  5 Experiments

In this section, we provide a comprehensive evaluation of NeuroSeqRet and our
hashing method. Appendix D (Gupta et al. 2021b) contains additional
experiments. Our implementation and datasets are available at
https://github.com/data-iitd/neuroseqret/.

| Mean Average Precision (MAP) in % | NDCG@10 in %
---|---|---
| Audio | Celebrity | Electricity | Health | Sports | Audio | Celebrity | Electricity | Health | Sports
MASS (Mueen et al. 2017) | 51.1$\pm$0.0 | 58.2$\pm$0.0 | 19.3$\pm$0.0 | 26.4$\pm$0.0 | 54.7$\pm$0.0 | 20.7$\pm$0.0 | 38.7$\pm$0.0 | 9.1$\pm$0.0 | 13.6$\pm$0.0 | 22.3$\pm$0.0
UDTW (Rakthanmanon et al. 2012) | 50.7$\pm$0.0 | 58.7$\pm$0.0 | 20.3$\pm$0.0 | 28.1$\pm$0.0 | 54.5$\pm$0.0 | 21.3$\pm$0.0 | 39.6$\pm$0.0 | 9.7$\pm$0.0 | 14.7$\pm$0.0 | 22.9$\pm$0.0
Sharp (Blondel et al. 2021) | 52.4$\pm$0.2 | 59.8$\pm$0.5 | 22.8$\pm$0.2 | 28.6$\pm$0.2 | 56.8$\pm$0.3 | 21.9$\pm$0.2 | 40.6$\pm$0.5 | 11.7$\pm$0.1 | 16.8$\pm$0.1 | 23.7$\pm$0.2
RMTPP (Du et al. 2016) | 48.9$\pm$2.3 | 57.6$\pm$1.8 | 18.7$\pm$0.8 | 24.8$\pm$1.2 | 50.3$\pm$2.5 | 20.1$\pm$1.9 | 39.4$\pm$2.1 | 8.3$\pm$0.8 | 12.3$\pm$0.5 | 19.1$\pm$1.8
Rank-RMTPP | 52.6$\pm$2.0 | 60.3$\pm$1.7 | 23.4$\pm$0.7 | 29.3$\pm$0.6 | 55.8$\pm$2.1 | 22.4$\pm$1.3 | 41.2$\pm$1.3 | 11.4$\pm$0.4 | 15.5$\pm$0.5 | 23.9$\pm$1.4
SAHP (Zhang et al. 2020) | 49.4$\pm$3.2 | 57.2$\pm$2.9 | 19.0$\pm$1.8 | 26.0$\pm$2.1 | 53.9$\pm$3.6 | 20.4$\pm$2.3 | 39.0$\pm$3.1 | 8.7$\pm$1.2 | 13.2$\pm$1.4 | 22.6$\pm$2.5
Rank-SAHP | 52.9$\pm$1.8 | 61.8$\pm$2.3 | 26.5$\pm$1.2 | 31.6$\pm$1.1 | 55.1$\pm$2.3 | 23.3$\pm$1.4 | 42.1$\pm$1.7 | 13.3$\pm$0.7 | 17.5$\pm$0.9 | 25.4$\pm$1.8
THP (Zuo et al. 2020) | 51.8$\pm$2.3 | 60.3$\pm$1.9 | 21.3$\pm$0.9 | 27.9$\pm$0.9 | 54.2$\pm$2.1 | 22.1$\pm$1.1 | 40.3$\pm$1.2 | 10.4$\pm$0.6 | 14.4$\pm$0.3 | 22.9$\pm$1.1
Rank-THP | 54.3$\pm$1.7 | 63.1$\pm$2.1 | 29.4$\pm$0.9 | 33.6$\pm$1.3 | 56.3$\pm$1.9 | 25.4$\pm$0.9 | 44.2$\pm$1.0 | 15.3$\pm$0.4 | 19.7$\pm$0.4 | 26.5$\pm$0.9
SelfAttn-NeuroSeqRet | 55.8$\pm$1.8 | 64.4$\pm$1.9 | 30.7$\pm$0.7 | 35.9$\pm$0.9 | 57.6$\pm$1.9 | 25.9$\pm$1.1 | 45.8$\pm$1.0 | 16.5$\pm$0.5 | 20.4$\pm$0.4 | 27.8$\pm$1.1
CrossAttn-NeuroSeqRet | 56.2$\pm$2.1$\dagger$ | 65.1$\pm$1.9$\dagger$ | 32.4$\pm$0.8$\dagger$ | 37.4$\pm$0.9$\dagger$ | 58.7$\pm$2.1 | 28.3$\pm$1.1$\dagger$ | 46.9$\pm$1.2$\dagger$ | 18.1$\pm$0.7$\dagger$ | 22.0$\pm$0.4$\dagger$ | 27.9$\pm$1.2

Table 1: Retrieval accuracy in terms of mean average precision (MAP) and
NDCG@10 (both in %) of all the methods across five datasets on the test set.
Numbers with bold font (underline) indicate best (second best) performer.
Boxed numbers indicate best performing state-of-the-art baseline. Results
marked $\dagger$ are statistically significant (two-sided Fisher’s test with
$p\leq 0.05$) over the best performing state-of-the-art baseline (Rank-THP or
Sharp). The standard deviation for MASS and UDTW are zero, since they are
deterministic retrieval algorithms.

###  5.1 Experimental Setup

Datasets. We evaluate the retrieval performance of NeuroSeqRet and other
methods across large-scale real-world datasets with up to 60 million events.
The statistics of all datasets are given in Appendix (Gupta et al. 2021b).
Across all datasets, $|\mathcal{H}_{q}|=5K$ and $|\mathcal{H}_{c}|=200K$.

  1. (1)

Audio: The dataset contains audio files for spoken commands to a smart-light
system and the demographics(age, nationality) of the speaker. Here, a query
corpus sequence pair is relevant if they are from an audio file with a common
speaker.

  2. (2)

Sports: The dataset contains actions (_e.g._ run, pass, shoot) taken while
playing different sports. We consider the time of action and action class as
time and mark of sequence respectively. Here, a query corpus sequence pair is
relevant if they are from a common sport.

  3. (3)

Celebrity: In this dataset, we consider the series of frames extracted from
youtube videos of multiple celebrities as event sequences where event-time
denotes the video-time and the mark is decided upon the coordinates of the
frame where the celebrity is located. Here, a query corpus sequence pair is
relevant if they are from a video file having a common celebrity.

  4. (4)

Electricity: This dataset contains the power-consumption records of different
devices across smart-homes in the UK. We consider the records for each device
as a sequence with event mark as the normalized change in the power consumed
by the device and the time of recording as event time. Here, a query corpus
sequence pair is relevant if they are from a similar appliance.

  5. (5)

Health: The dataset contains ECG records for patients suffering from heart-
related problems. Since the length of the ECG record for a single patient can
be up to 10 million, we generate smaller individual sequences of length 10,000
and consider each such sequence as an independent sequence. The marks and
times of events in a sequence are determined using a similar procedure as in
Electricity. A query corpus sequence pair is relevant if they are from a
common patient.

For Health, Celebrity and Electricity, we lack the true ground-truth labeling
of relevance between sequences. Therefore, we adopt a heuristic in which,
given a dataset $\mathcal{D}$, from each sequence
$\texttt{seq}_{q}\in\mathcal{D}$ with $q\in[|\mathcal{D}|]$, we first sample a
set of sub-sequences
$\mathcal{U}_{q}=\left\\{\mathcal{H}\subset\texttt{seq}_{q}\right\\}$ with
$|\mathcal{U}_{q}|\sim\text{Unif}\,[200,300]$. For each such collection
$\mathcal{U}_{q}$, we draw exactly one query $\mathcal{H}_{q}$ uniformly at
random from $\mathcal{U}_{q}$, _i.e._ , $\mathcal{H}_{q}\sim\mathcal{U}_{q}$.
Then, we define
$\mathcal{C}=\cup_{q\in[|\mathcal{D}|]}\mathcal{U}_{q}\backslash\mathcal{H}_{q}$,
$\mathcal{C}_{q{+}}=\mathcal{U}_{q}\backslash\mathcal{H}_{q}$ and
$\mathcal{C}_{q{-}}=\cup_{c\neq
q}\big{(}\mathcal{U}_{c}\backslash\mathcal{H}_{c}\big{)}$.

Baselines. We consider three continuous time-series retrieval models: (i) MASS
(Mueen et al. 2017), (ii) UDTW (Rakthanmanon et al. 2012) and (iii) Sharp
(Blondel et al. 2021); and, three MTPP models (iv) RMTPP (Du et al. 2016), (v)
SAHP (Zhang et al. 2020), and (vi) THP (Zuo et al. 2020). For sequence
retrieval with MTPP models, we first train them across all the sequences using
maximum likelihood estimation. Then, given a test query
$\mathcal{H}_{{q{{}^{\prime}}}}$, this MTPP method ranks the corpus sequences
$\left\\{\mathcal{H}_{c}\right\\}$ in decreasing order of their cosine
similarity
$\text{CosSim}(\texttt{emb}^{({q{{}^{\prime}}})},\texttt{emb}^{(c)})$, where
$\texttt{emb}^{(\bullet)}$ is the corresponding sequence embedding provided by
the underlying MTPP model. In addition, we build supervised ranking models
over these approaches, _viz.,_ Rank-RMTPP, Rank-SAHP and Rank-THP
corresponding to RMTPP, SAHP, and THP. Specifically, Rank-MTPP formulates a
ranking loss on the query-corpus pairs based on the cosine similarity scores
along with the likelihood function to get the final training objective.
Therefore, the vanilla MTPP models are used as unsupervised models and the
corresponding Rank-MTPP models work as supervised models. Appendix C (Gupta et
al. 2021b) contains the implementation details.

Evaluation protocol. We partition the set of queries $\mathcal{Q}$ into 50%
training, 10% validation and rest as test sets. First, we train a retrieval
model using the set of training queries. Then, for each test query
${q{{}^{\prime}}}$, we use the trained model to obtain a top-$K$ ranked list
from the corpus sequences. Next, we compute the average precision (AP) and
discounted cumulative gain (DCG) of each top-$K$ list, based on the ground
truth. Finally, we compute the mean average precision (MAP) and NDCG@$K$, by
averaging AP and DCG values across all test queries. We set $K=10$.

###  5.2 Results on Retrieval Accuracy

Comparison with baselines. First, we compare our model against the baselines
in terms of MAP and NDCG. Table 1 summarizes the results, which shows that (i)
both CrossAttn-NeuroSeqRet and SelfAttn-NeuroSeqRet outperform all the
baselines by a substantial margin; (ii) CrossAttn-NeuroSeqRet outperforms
SelfAttn-NeuroSeqRet, since the former has a higher expressive power; (iii)
the variants of baseline MTPP models trained for sequence retrieval, _i.e._ ,
Rank-RMTPP, Rank-SAHP, and Rank-THP outperform the vanilla MTPP models; (iv)
the performances of vanilla MTPPs and the time series retrieval models (MASS,
UDTW and Sharp) are comparable.

Variant | Audio | Celebrity | Health
---|---|---|---
(i) $s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=-\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})-\Delta_{t}(U_{\phi}(\mathcal{H}_{q}),\mathcal{H}_{c})$ | 36.1$\pm$0.0 | 43.7$\pm$0.0 | 18.9$\pm$0.0
(ii) $s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})$ | 53.9$\pm$1.9 | 62.5$\pm$1.3 | 33.6$\pm$0.7
(iii) $s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})-\gamma\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})$ | 54.6$\pm$1.9 | 63.1$\pm$1.4 | 33.7$\pm$0.7
(iv) $s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})-\gamma\Delta_{t}(U_{\phi}(\mathcal{H}_{q}),\mathcal{H}_{c})$ | 55.7$\pm$2.0 | 63.7$\pm$1.8 | 35.9$\pm$0.8
(v) CrossAttn-NeuroSeqRet Without $U_{\phi}(\cdot)$ | 55.2$\pm$2.2 | 62.9$\pm$2.0 | 34.3$\pm$0.9
(vi) CrossAttn-NeuroSeqRet | 56.2$\pm$2.1 | 65.1$\pm$1.9 | 37.4$\pm$0.9

Table 2: Ablation study.

(a) $\mathcal{H}_{q},\mathcal{H}_{c}$ (b)
$U_{\phi}(\mathcal{H}_{q}),\mathcal{H}_{c}$

Figure 1: Effect of unwarping on a _relevant_ query-corpus pair in Audio.
$U_{\phi}(\cdot)$ learns to transform $\mathcal{H}_{q}$ in order to capture a
high value of its latent similarity with $\mathcal{H}_{c}$.

Ablation study. Next, we compare the retrieval performance across four model
variants:  (i) our model with only model-independent score _i.e._ ,
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=-\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})-\Delta_{t}(U_{\phi}(\mathcal{H}_{q}),\mathcal{H}_{c})$;
(ii) our model with only model-dependent score, _i.e._ ,
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})$;
(iii) our model without any model independent time similarity _i.e._ ,
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})-\gamma\Delta_{x}(\mathcal{H}_{q},\mathcal{H}_{c})$;
(iv) our model without any model independent mark similarity _i.e._ ,
$s_{p_{\theta},U_{\phi}}(\mathcal{H}_{q},\mathcal{H}_{c})=\kappa_{p_{\theta}}(\mathcal{H}_{q},\mathcal{H}_{c})-\gamma\Delta_{t}(U_{\phi}(\mathcal{H}_{q}),\mathcal{H}_{c})$;
(v) our model without unwarping function $U_{\phi}(\cdot)$; and  (vi) the
complete design of our model.  In all cases, we used CrossAttn-NeuroSeqRet.

Table 2 shows that the complete design of our model (variant (vi)) achieves
the best performance. We further note that removing $\kappa_{p_{\theta}}$ from
the score (variant (i)) leads to significantly poor performance.
Interestingly, our model without any mark based similarity (variant (iv))
leads to better performance than the model without time similarity (variant
(iii))— this could be attributed to the larger variance in query-corpus time
distribution than the distribution of marks. Finally, we observe that the
performance deteriorates if we do not use an unwarping function
$U_{\phi}(\cdot)$ (variant (v)). Figure 1 illustrates the effect of
$U_{\phi}(\cdot)$. It shows that $U_{\phi}(\cdot)$ is able to learn suitable
transformation of the query sequence, which encapsulates the high value of
latent similarity with the corpus sequence.

(a)  (b)  (c)

Figure 2: Tradeoff between NDCG@10 vs. Reduction factor, _i.e._ , % reduction
in number of comparisons between query-corpus pairs w.r.t. the exhaustive
comparisons for different hashing methods. The point marked as
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{\star}$
indicates the case with exhaustive comparisons on the set of corpus sequences.

###  5.3 Results on Retrieval Efficiency

We compare our efficient sequence retrieval method given in Algorithm 1
against random hyperplane (RH) method (Appendix B in (Gupta et al. 2021b)) and
three variants of our proposed training problem in Eq. (4.1).  (i)
Our$(\eta_{2},\eta_{3})$ which sets $\eta_{1}=0$ and thus does not enforce
even distribution of $\pm 1$ in $\bm{\zeta}^{c}$;  (ii)
Our$(\eta_{1},\eta_{3})$ which sets $\eta_{2}=0$ and thus $\tanh$ does not
accurately approximate $\mathop{\mathrm{sign}}$;  (iii)
Our$(\eta_{1},\eta_{2})$ which sets $\eta_{3}=0$ and thus does not enforce
$\bm{\zeta}^{c}$ to be compact and free of redundancy.
Our$(\eta_{1},\eta_{2},\eta_{3})$ is the complete design which includes all
trainable components. Figure 2 summarizes the results.

Comparison with random hyperplane. Figure 2 shows that our method
(Our$(\eta_{1},\eta_{2},\eta_{3})$) demonstrates better Pareto efficiency than
RH. This is because RH generates hash code in a data oblivious manner whereas
our method learns the hash code on top of the trained embeddings.

Ablation study on different components of Eq. (4.1). Figure 2 summarizes the
results, which shows that (i) the first three variants are outperformed by
Our$(\eta_{1},\eta_{2},\eta_{3})$; (ii) the first term having $\eta_{1}\neq
0$, which enforces an even distribution of $\pm 1$, is the most crucial
component for the loss function— as the removal of this term causes
significant deterioration of the performance.

##  6 Conclusions

In this paper, we proposed a novel supervised continuous time event sequence
retrieval system called NeuroSeqRet using neural MTPP models. To achieve
efficient retrieval over very large corpus of sequences, we also propose a
trainable hash-coding of corpus sequences which can be used to narrow down the
number of sequences to be considered for similarity score computation. Our
experiments with real world datasets from a diverse range of domains show that
both our retrieval model and hashing methods are more effective than several
baselines.

## References

  * Abanda et al. (2019) Abanda, A.; Mori, U.; and Lozano, J. A. 2019.  A review on distance based time series classification.  In _DMKD_.
  * Alaee et al. (2020) Alaee, S.; Kamgar, K.; and Keogh, E. 2020.  Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW.  In _ICDM_.
  * Blondel et al. (2021) Blondel, M.; Mensch, A.; and Vert, J.-P. 2021.  Differentiable Divergences Between Time Series.  In _AISTATS_.
  * Cai et al. (2019) Cai, X.; Xu, T.; Yi, J.; Huang, J.; and Rajasekaran, S. 2019.  DTWNet: a dynamic time warping network.  In _NeurIPS_.
  * Charikar (2002) Charikar, M. S. 2002.  Similarity estimation techniques from rounding algorithms.  In _STOC_.
  * Cuturi and Blondel (2017) Cuturi, M.; and Blondel, M. 2017.  Soft-dtw: a differentiable loss function for time-series.  In _ICML_.
  * Daley and Vere-Jones (2007) Daley, D. J.; and Vere-Jones, D. 2007.  _An Introduction to the Theory of Point Processes: Volume II: General Theory and Structure_.  Springer Science & Business Media.
  * De et al. (2018) De, A.; Bhattacharya, S.; and Ganguly, N. 2018.  Demarcating endogenous and exogenous opinion diffusion process on social networks.  In _WWW_.
  * De et al. (2016) De, A.; Valera, I.; Ganguly, N.; Bhattacharya, S.; and Gomez-Rodriguez, M. 2016\.  Learning and Forecasting Opinion Dynamics in Social Networks.  In _NeurIPS_.
  * Du et al. (2016) Du, N.; Dai, H.; Trivedi, R.; Upadhyay, U.; Gomez-Rodriguez, M.; and Song, L. 2016\.  Recurrent marked temporal point processes: Embedding event history to vector.  In _KDD_.
  * Du et al. (2015) Du, N.; Farajtabar, M.; Ahmed, A.; Smola, A. J.; and Song, L. 2015.  Dirichlet-hawkes processes with applications to clustering continuous-time document streams.  In _KDD_.
  * Farajtabar et al. (2017) Farajtabar, M.; Yang, J.; Ye, X.; Xu, H.; Trivedi, R.; Khalil, E.; Li, S.; Song, L.; and Zha, H. 2017.  Fake news mitigation via point process based intervention.  In _ICML_.
  * Gervini and Gasser (2004) Gervini, D.; and Gasser, T. 2004.  Self-modelling warping functions.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 66(4): 959–971.
  * Gionis et al. (1999) Gionis, A.; Indyk, P.; and Motwani, R. 1999.  Similarity Search in High Dimensions via Hashing.  In _VLDB_.
  * Gogolou et al. (2020) Gogolou, A.; Tsandilas, T.; Echihabi, K.; Bezerianos, A.; and Palpanas, T. 2020\.  Data series progressive similarity search with probabilistic quality guarantees.  In _SIGMOD_.
  * Guo et al. (2018) Guo, R.; Li, J.; and Liu, H. 2018.  INITIATOR: Noise-contrastive Estimation for Marked Temporal Point Process.  In _IJCAI_.
  * Gupta and Bedathur (2021) Gupta, V.; and Bedathur, S. 2021.  Region Invariant Normalizing Flows for Mobility Transfer.  In _CIKM_.
  * Gupta et al. (2021a) Gupta, V.; Bedathur, S.; Bhattacharya, S.; and De, A. 2021a.  Learning Temporal Point Processes with Intermittent Observations.  In _AISTATS_.
  * Gupta et al. (2021b) Gupta, V.; Bedathur, S.; and De, A. 2021b.  Supplementary Material for Learning Temporal Point Processes for Efficient Retrieval of Continuous Time Event Sequences.  https://github.com/data-iitd/neuroseqret/.
  * Jaakkola et al. (1999) Jaakkola, T. S.; Haussler, D.; et al. 1999.  Exploiting generative models in discriminative classifiers.  In _NeurIPS_.
  * Jing and Smola (2017) Jing, H.; and Smola, A. J. 2017.  Neural survival recommender.  In _WSDM_.
  * Joachims (2002) Joachims, T. 2002.  Optimizing Search Engines Using Clickthrough Data.  133–142. ACM.
  * Kang and McAuley (2018) Kang, W.-C.; and McAuley, J. 2018.  Self-Attentive Sequential Recommendation.  In _ICDM_.
  * Kumar et al. (2019) Kumar, S.; Zhang, X.; and Leskovec, J. 2019.  Predicting dynamic embedding trajectory in temporal interaction networks.  In _KDD_.
  * Li et al. (2020) Li, J.; Wang, Y.; and McAuley, J. 2020.  Time Interval Aware Self-Attention for Sequential Recommendation.  In _WSDM_.
  * Likhyani et al. (2020) Likhyani, A.; Gupta, V.; Srijith, P.; Deepak, P.; and Bedathur, S. 2020.  Modeling Implicit Communities from Geo-tagged Event Traces using Spatio-Temporal Point Processes.  In _WISE_.
  * Liu et al. (2014) Liu, W.; Mu, C.; Kumar, S.; and Chang, S.-F. 2014.  Discrete graph hashing.
  * Mei and Eisner (2017) Mei, H.; and Eisner, J. M. 2017.  The neural hawkes process: A neurally self-modulating multivariate point process.  In _NeurIPS_.
  * Mei et al. (2019) Mei, H.; Qin, G.; and Eisner, J. 2019.  Imputing Missing Events in Continuous-Time Event Streams.  In _ICML_.
  * Mueen and Keogh (2016) Mueen, A.; and Keogh, E. 2016.  Extracting optimal performance from dynamic time warping.  In _KDD_.
  * Mueen et al. (2017) Mueen, A.; Zhu, Y.; Yeh, M.; Kamgar, K.; Viswanathan, K.; Gupta, C.; and Keogh, E. 2017.  The Fastest Similarity Search Algorithm for Time Series Subsequences under Euclidean Distance.  Http://www.cs.unm.edu/ mueen/FastestSimilaritySearch.html.
  * Müller (2007) Müller, M. 2007.  Dynamic time warping.  _Information retrieval for music and motion_ , 69–84.
  * Paparrizos and Gravano (2015) Paparrizos, J.; and Gravano, L. 2015.  k-shape: Efficient and accurate clustering of time series.  In _SIGMOD_.
  * Qin et al. (2020) Qin, Z.; Bai, Y.; and Sun, Y. 2020.  GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases.  In _KDD_.
  * Rakthanmanon et al. (2012) Rakthanmanon, T.; Campana, B.; Mueen, A.; Batista, G.; Westover, B.; Zhu, Q.; Zakaria, J.; and Keogh, E. 2012.  Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping.  In _KDD_.
  * Rizoiu et al. (2017) Rizoiu, M.-A.; Xie, L.; Sanner, S.; Cebrian, M.; Yu, H.; and Van Hentenryck, P. 2017\.  Expecting to be hip: Hawkes intensity processes for social media popularity.  In _WWW_.
  * Roy et al. (2020) Roy, I.; De, A.; and Chakrabarti, S. 2020.  Adversarial Permutation Guided Node Representations for Link Prediction.  _arXiv preprint arXiv:2012.08974_.
  * Saha et al. (2018) Saha, A.; Samanta, B.; Ganguly, N.; and De, A. 2018.  Crpp: Competing recurrent point process for modeling visibility dynamics in information diffusion.  In _CIKM_.
  * Salakhutdinov and Hinton (2009) Salakhutdinov, R.; and Hinton, G. 2009.  Semantic hashing.  In _International Journal of Approximate Reasoning_.
  * Samanta et al. (2017) Samanta, B.; De, A.; Chakraborty, A.; and Ganguly, N. 2017.  LMPP: a large margin point process combining reinforcement and competition for modeling hashtag popularity.  In _IJCAI_.
  * Sewell (2011) Sewell, M. 2011.  The fisher kernel: a brief review.  _RN_ , 11(06): 06.
  * Shchur et al. (2020) Shchur, O.; Biloš, M.; and Günnemann, S. 2020.  Intensity-Free Learning of Temporal Point Processes.  In _ICLR_.
  * Shelton et al. (2018) Shelton, C. R.; Qin, Z.; and Shetty, C. 2018.  Hawkes Process Inference with Missing Data.  In _AAAI_.
  * Shen et al. (2018) Shen, Y.; Chen, Y.; Keogh, E.; and Jin, H. 2018.  Accelerating time series searching with large uniform scaling.  In _SDM_.
  * Su et al. (2020) Su, H.; Liu, S.; Zheng, B.; Zhou, X.; and Zheng, K. 2020.  A survey of trajectory distance measures and performance evaluation.  _VLDB Journal_.
  * Tabibian et al. (2019) Tabibian, B.; Upadhyay, U.; De, A.; Zarezade, A.; Schölkopf, B.; and Gomez-Rodriguez, M. 2019.  Enhancing human learning via spaced repetition optimization.  _PNAS_.
  * Valera et al. (2014) Valera, I.; Gomez-Rodriguez, M.; and Gummadi, K. 2014.  Modeling Diffusion of Competing Products and Conventions in Social Media.  _arXiv preprint arXiv:1406.0516_.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention is All You Need.  In _NeurIPS_.
  * Wang et al. (2017) Wang, P.; Fu, Y.; Liu, G.; Hu, W.; and Aggarwal, C. 2017.  Human Mobility Synchronization and Trip Purpose Detection with Mixture of Hawkes Processes.  In _KDD_.
  * Wehenkel and Louppe (2019) Wehenkel, A.; and Louppe, G. 2019.  Unconstrained monotonic neural networks.  In _NeurIPS_.
  * Xiao et al. (2017) Xiao, S.; Farajtabar, M.; Ye, X.; Yan, J.; Song, L.; and Zha, H. 2017.  Wasserstein Learning of Deep Generative Point Process Models.  In _NeurIPS_.
  * Xu et al. (2018) Xu, H.; Carin, L.; and Zha, H. 2018.  Learning registered point processes from idiosyncratic observations.  In _ICML_.
  * Yoon et al. (2019) Yoon, J.; Jarrett, D.; and van der Schaar, M. 2019.  Time-series generative adversarial networks.  In _NeurIPS_.
  * Zamani Dadaneh et al. (2020) Zamani Dadaneh, S.; Boluki, S.; Yin, M.; Zhou, M.; and Qian, X. 2020.  Pairwise Supervised Hashing with Bernoulli Variational Auto-Encoder and Self-Control Gradient Estimator.  In _UAI_.
  * Zhang et al. (2010) Zhang, D.; Wang, J.; Cai, D.; and Lu, J. 2010.  Self-taught hashing for fast similarity search.  In _SIGIR_.
  * Zhang et al. (2021) Zhang, P.; Iyer, R.; Tendulkar, A.; Aggarwal, G.; and De, A. 2021.  Learning to Select Exogenous Events for Marked Temporal Point Process.  In _NeurIPS_.
  * Zhang et al. (2020) Zhang, Q.; Lipani, A.; Kirnap, O.; and Yilmaz, E. 2020.  Self-attentive Hawkes processes.  _ICML_.
  * Zuo et al. (2020) Zuo, S.; Jiang, H.; Li, Z.; Zhao, T.; and Zha, H. 2020.  Transformer Hawkes Process.  In _ICML_.