Next recommendation performance of and state-of-the-art baselines for the dataset. Here, we exclude a comparison with STGN <cit.> as it requires the precise geographical coordinates for locations, which we lack in the dataset. All results are statistically significant (, two-sided Fisher's test with $p \le 0.1$) over the best baseline. Numbers with bold font (boxes) indicate the best (second best) performer.

Baselines     NDCG/Hits@1     NDCG@5     NDCG@10     Hits@5     Hits@10
FPMC <cit.>     0.5906     0.6021     0.6402     0.6162     0.6481

TransRec <cit.>     0.5437     0.5803     0.6055     0.5839     0.6081

GRU4Rec+ <cit.>     0.6291     0.6432     0.6796     0.6443     0.6867

Caser <cit.>     0.6418     0.6472     0.6782     0.6507     0.6991

AUM <cit.>     0.5718     0.6089     0.6358     0.6097     0.6433

Bert4Rec <cit.>     0.7031     0.7346     0.7442     0.7188     0.7301

SASRec <cit.>     0.7279     0.7530     0.7562     0.7583     0.7648

TiSRec <cit.>     0.7284     0.7542     0.7558     0.7618     0.7663
ReVAMP     0.7865     0.8021     0.8186     0.8203     0.8340

Next performance comparison between and state-of-the-art baselines for the dataset. All results are statistically significant over the best baseline as in Table <ref>.

Baselines     NDCG/Hits@1     NDCG@5     NDCG@10     Hits@5     Hits@10
FPMC <cit.>     0.7224     0.7362     0.7704     0.7408     0.7892

TransRec <cit.>     0.6872     0.6892     0.7691     0.6902     0.7784

GRU4Rec+ <cit.>     0.7319     0.7654     0.7913     0.7703     0.7962

Caser <cit.>     0.7321     0.7802     0.8079     0.8157     0.8482

STGN  <cit.>     0.6694     0.7981     0.8132     0.8224     0.8549

AUM <cit.>     0.7184     0.7395     0.7646     0.7782     0.8179

Bert4Rec <cit.>     0.7728     0.8247     0.8281     0.8614     0.8743

SASRec <cit.>     0.8295     0.8621     0.8680     0.9027     0.9108

TiSRec <cit.>     0.8307     0.8619     0.8693     0.8998     0.9014
ReVAMP     0.8793     0.9324     0.9371     0.9492     0.9594

§.§ Performance Comparison

In this section, we address RQ1 and report the location recommendation performance of different methods across both mobility datasets. The results for and datasets are given in Table <ref> and Table <ref>, respectively. From these results, we make the following observations.

* consistently outperforms all other baselines for sequential mobility prediction across both datasets. The superior performance signifies the importance of including the smartphone usage pattern of a user to determine her mobility preferences. We also note that the performance gains over other self-attention-based models – Bert4Rec <cit.>, SASRec <cit.>, and TiSRec <cit.> further reinforce our claim that including relative positional encodings based on the smartphone, spatial and temporal characteristics can better learn the mobility preferences.

* We also note that the self-attention-based models, such as Bert4Rec, SASRec, TiSRec, and consistently yield the best performance on all the datasets and easily outperform CNN and RNN-based models, namely Caser <cit.> and GRU4Rec+ <cit.>. This further signifies the unequaled proficiency of the transformer <cit.> architecture to capture the evolution of user preferences across her trajectory sequence. More importantly, it outperforms the state-of-the-art location recommendation model STGN <cit.> that uses the additional information of precise geographical coordinates of each POI location.

* also outperforms the other smartphone-activity-based approach, AUM <cit.> by up to 34% across different metrics.

* We also note that neural baselines such as Caser <cit.>, GRU4Rec+ <cit.> achieve better results as compared to FPMC <cit.> and TransRec <cit.>. It asserts the utmost importance of designing modern recommender systems using neural architectures. Moreover, GRU4Rec+ achieves a similar performance compared to Caser.

To sum up, our empirical analysis suggests the following: [(i)]
* the state-of-the-art models, including self-attention and standard neural models, are not suitable for modeling mobile-user trajectories, and
* achieves better recommendation performance as it captures the mobility dynamics as well as the smartphone-activity of a user.

POI recommendation performance of with different methods for obtaining the relative positional encodings, , the inter-differences between app- and location embeddings. Here, the time-based representations are kept consistent across all the models.

§.§ Ablation Study

To address RQ2, we perform an ablation study to estimate the efficacy of different components in the architecture. More specifically, we aim to calculate the contribution of (i) the embedding initiator and (ii) relative positional embeddings.

Analysis of Embedding Initiator
We reiterate that EI, defined in Section <ref>, is used to learn the semantic meaning of each app- and POI category as well as the influence between these embeddings in a mobility sequence. We accomplish this via a joint loss that consists of – minimizing the divergence between the category vector and the pre-trained BERT<cit.> vectors and a collaborative-filtering (CF) loss. These trained embeddings are later used to learn the inter-differences through relative positional encodings. To emphasize its importance, we compare the prediction performances of with different procedures to learn category embeddings and thus the relative embeddings. Specifically, we consider: [(i)]
* word-movers-distance(WMD) <cit.> between the word2vec <cit.> representations of each category,
* WMD on Glove <cit.> based representations,
* WMD based on BERT <cit.> initialized vectors,
* simple collaborative filtering based parameter training,
* using pre-trained BERT, and (vi) the proposed EI model. From the results in Figure <ref>, we note that our proposed EI achieves the best prediction performance compared to other approaches. We also note that standard pre-trained BERT vectors outperform other WMD-based approaches.

Relative Positional Encodings
Relative positional embeddings are a crucial element in our model. We calculate the performance gains due to the different relative encodings – app-, time- and location-based by estimating the recommendation performance of the following approaches: [(i)] SASRec <cit.>;
* TiSRec <cit.>;
* with time-based relative positional encoding called -t;
* with app-based encodings, denoted as -a;
* with location-based encodings, denoted as -l; and
* the complete model with all relative encodings.

Ablation study with different relative positional encodings used in and their comparison with SASRec <cit.> and TiSRec <cit.>.

Figure <ref> summarizes our results where we observe that including relative positional encodings of any form, whether app-based or location-based, leads to better prediction performances. Interestingly, the contribution of location-based relative positional embeddings is more significant than the app-based and could be attributed to larger variations in location-category than the app-category across an event sequence. For example, the difference between location categories of a university region and an office space will capture larger dynamics than the differences in smartphone app usage across these two regions. However, jointly learning all positional encoding leads to the best performance over both datasets. The improvements of -t over TiSRec <cit.> could be due to the inclusion of absolute event encodings (both app and location).

ST (App)

TD (App)

ST (POI)

TD (POI)

Root-mean squared distance between the user-preference vector estimated by the model and the mean of the app- and location-category vectors of events in the test set. It shows that is the best performer for all the datasets.

§.§ App and Location Prediction Category

Our goal via is to understand the smartphone activity of a user and correlate it with her mobile trajectories. Therefore, we perform an additional experiment to evaluate how effectively is able to predict the app- and the location category for the next user . We also introduce an additional state-of-the-art smartphone-activity modeling baseline, Appusage2Vec <cit.> which considers the category of the app and the time spent on the app by the user to learn an app-preference embedding for a user. We also compare with the state-of-the-art transformer-based models – SASRec <cit.> and TiSRec <cit.>. For an even comparison, we rank the models using the root-mean-squared (RMS) distance between the final user preference embedding obtained after learning on $N$ consecutive events of a user and the mean of location and category embeddings of the $N+1$ event in the sequence. Accordingly, we also modify the architectures of SASRec and TiSRec to predict user affinity across the location and app category affinities. From the results in Figure <ref>, we make the following observations: [(i)]
* easily outperforms all other baselines for both apps and location category prediction. This illustrates the better user-preference modeling power of over other approaches,
* For app-category prediction, Appusage2Vec also outperforms both SASRec and TiSRec; however, easily outperforms Appusage2Vec across both the datasets.

§.§ Scalability of

To address RQ3, , determine the scalability of with different positional encodings – absolute and relative, we present the epoch-wise time taken for training in Table <ref>. Note that these running times exclude the time for pre-processing, where we calculate the inter-event app and location category-based differences. We note that the runtime of is linear with the number of users, and secondly, even for a large-scale dataset, like , we can optimize all parameters in well within 170 minutes. These run times are well within the range for designing recommender systems.

Run-time Statistics of training in minutes on a 32GB Tesla V100 GPU with 256 batch-size.

Epochs     20     60     100     160     200     300

2.43     6.31     10.48     16.72     21.47     32.01

11.39     33.73     56.12     89.81     112.35     168.49

Epoch-wise recommendation performance of for both datasets in terms of Hits@1, 5, 10.

Convergence of Training
As we propose the first-ever application of the self-attention model for smartphones and human mobility, we also perform a convergence analysis during training . To emphasize the stability of training procedure, we plot the epoch-wise best prediction performance of across both datasets in Fig <ref>. From the results, we note that despite the multi-variate nature of the data and the disparate positional encodings, converges only in a few training iterations. It is also important to note that the significantly outperforms other RNN-based baselines even with limited training of 40 iterations.

§ CONCLUSION

In this chapter, we highlighted the drawbacks of modern POI recommender systems that ignore the smartphone usage characteristics of users. We also proposed a novel sequential POI recommendation model, called , that incorporates the smartphone usage details of a user while simultaneously maintaining user privacy. Inspired by the success of relative positional encodings and self-attention models, uses relative as well as absolute positional encodings determined by the inter-variances in the smartphone app category, POI category, and time over the in the sequence. Our experiments over two diverse datasets from China show that significantly outperforms other state-of-the-art baselines for POI recommendation. Moreover, we also show the contribution of each component in the architecture and analyze the learning stability of the model.

Applications of Modeling Temporal Sequences

CHAPTER: LARGE-SCALE RETRIEVAL OF TEMPORAL SEQUENCES

§ INTRODUCTION

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. In this chapter, we address the problem of retrieving temporal event sequences from a large corpus using neural MTPP models. This is a first-of-its-kind application of MTPP as the earlier developments in MTPP models focused on improving 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) <cit.>. Therefore, 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; the retrieval of ECG sequences relevant to one pathological query ECG sequence can help in the early detection of cardiac disease; in social networks, retrieval of trajectories of information diffusion, relevant to a given trajectory can assist in viral marketing, fake news detection,  Despite having a rich literature on searching similar time-series <cit.>, 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 varies across these two domains.

§.§ Our Contribution

In this chapter, we first introduce , 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 <cit.>. 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 <cit.>. To tackle this problem,  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 <cit.>.

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 <cit.> between the corpus and the unwarped query sequences. Such a kernel offers two key benefits over other distribution similarity measures, , 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 , which allows a nice tradeoff between accuracy and efficiency.

: Here, we use transformer Hawkes process <cit.> 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.

: 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 is not directly compatible with such a hashing-based retrieval, it can be employed in a telescopic manner— where a smaller set of relevant candidates are first retrieved using LSH applied on top of , and then reranked using . Therefore, from the design perspective, these two models provide a tradeoff between accuracy and efficiency.

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  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 <cit.> 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  outperform several baselines including the methods for continuous-time series retrieval. Moreover, we observe that our hashing method applied on  can make a tradeoff between the retrieval accuracy and efficiency more effectively than baselines based on random hyperplanes as well as exhaustive enumeration.

§ PRELIMINARIES

§.§ Notations and MTPP

An event $e$ in an MTPP is realized using a tuple $(t,x)$, where $t\in\mathbb{R}_+$ and $x\in \mathcal{C}$ are the arrival time and the mark of the event $e$. Then, we use $\Hcal(t)$ to denote a continuous time event sequence (CTES) where each event has arrived until and excluding time $t$, , $\Hcal(t):=\set{e_i=(t_i,x_i)\given t_{i-1}<t_{i}<t}$. Moreover we use $\Tcal(t)$ and $\Mcal(t)$ to denote the sequence of arrival times $\set{t_i\given e_i\in\Hcal(t)}$  and the marks $\set{x_i\given e_i\in\Hcal(t)}$.  Finally, we denote the counting process $N(t)$ as counts of the number of events that 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 <cit.> model the first component using an intensity function which explicitly models the likelihood of an event in the infinitesimal time window $[t,t+dt)$, ,  $\lambda^{\pend}(t )= \text{Pr} (dN(t)=1|\Hcal(t))$. In contrast, we use an intensity-free approach following the proposal by <cit.>, where we explicitly model the distribution of the arrival time $t$ of the next event $e$. Specifically, we denote the density $\intensity$ of the arrival time and  the distribution $m^{\pend}$ of the mark  of the next event as follows:

\begin{align}\label{eq:qm}
\intensity(t) dt & = \text{Pr} (e \text{ in } [t,t+dt) \given \Hcal(t)), \\
m^{\pend}(x)&=\text{Pr} (x\given \Hcal(t))
\end{align}

As discussed by <cit.>, such an intensity-free MTPP model enjoys several benefits over its intensity-based counterparts in terms of facilitating efficient training, scalable prediction, computation of expected arrival times,  Given a sequence of observed events $\Hcal(T)$ collected during the time interval $(0,T]$, the likelihood function is given by:

\begin{equation}
p (\Hcal(T)) =\textstyle  \prod_{e_i=(t_i,x_i)\in\Hcal(T)}  \intensity(t_i) \times   m^{\pend}(x_i)
\end{equation}

§.§ Problem setup

Next, we set up our problem of retrieving a ranked list of sequences 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 $\set{\Hcal_c(T_c)\given c\in \Cr}$, where $\Hcal_c(T_c)=\{(t^{(c)} _i, x^{(c)} _i)  \given t^{(c)} _i < T_c \}$. We are given a set of query sequences $\set{\Hcal_q(T_q) \given q\in\Qr}$ with $\Hcal_q(T_q)=\{(t^{(q)} _i, x^{(q)} _i) \given 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 $\Hcal_q$, we have: $y(\Hcal_q,\Hcal_c)=+1$  if $\Hcal_c$ is marked as relevant to $\Hcal_q$ and $y(\Hcal_q,\Hcal_c)=-1$ otherwise.

We define $\Cr_{q\rel} =\{c\in\Cr \given y(\Hcal_q,\Hcal_c)=+1  \}, \text{and, }
\Cr_{q\nrel} =\{c\in\Cr \given y(\Hcal_q,\Hcal_c)=-1  \}$, with $\Cr = \Cr_{q\rel}  \cup \Cr_{q\nrel} $. Finally, we denote $T=\max\{T_q,T_c\given q\in\Qr,c\in\Cr\}$ 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 $\Hcal_q$. Therefore, we can view a sequence retrieval task as an instance of the ranking problem. Similar to other information retrieval algorithms, a CTES retrieval algorithm first computes the estimated relevance $s(\Hcal_q,\Hcal_c)$ of the corpus sequence $\Hcal_c$ for a given query sequence $\Hcal_q$ and then provides a ranking of $\Cr$ in the decreasing order of their scores.

§ MODEL

In this section, we describe 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.

§.§ Components of

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,  works in two steps. First, it unwarps the query sequences to make them compatible for comparison 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 <cit.>. Thus, a direct comparison between a relevant sequence pair may give a poor relevance score. To address this challenge, we first apply a trainable unwarping function <cit.> $U(\cdot)$ on the arrival times of a query sequence, which enhances its compatibility for comparing it with the corpus sequences[We only apply the unwarping function on the times. Since marks belong to a fixed discrete set, we believe marks are directly comparable.]. More specifically, we define $\unw (\Hcal_q):=\{(\unw(t^{(q)} _i), x^{(q)} _i) \}$. In general, $\unw$  satisfies two properties <cit.> which are: unbiasedness, , having a small value of $\left\|\unw(t )]-t\right\|$ and monotonicity, , $ {d\, \unw(t  ) }/{dt} \ge 0$. These properties ensure that the chronological order of the events across both the warped observed sequence and the unwarped sequence remains the 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 <ref>).

Computation of relevance scores
Given a query sequence $\Hcal_q$ and a corpus sequence $\Hcal_c$, we compute the relevance score $s(\Hcal_q,\Hcal_c)$
using two similarity scores, ,  (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 <cit.>. They are computed using different distance measures between two sequences, , DTW, Wasserstein distance, , 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}_{\unw}(\Hcal_q,\Hcal_c)$, between $\Hcal_q$ and $\Hcal_c$ as follows:

\begin{align}
\textsc{Sim}_{\unw}(\Hcal_q,\Hcal_c)& = -\Delta_{t}(\unw(\Hcal_q),\Hcal_c)-\Delta_{x}(\Hcal_q,\Hcal_c)
\end{align}

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

\begin{equation}
\Delta_{t}(\unw(\Hcal_q),\Hcal_c) = \sum_{i=0}^ {H_{\min}} \left| \unw(t^{(q)} _i)- t^{(c)} _i\right| + \hspace{-2mm}\sum_{\substack{t_i \in \Hcal_c\cup\Hcal_q\\ i > |H_{\min}| }} (T -t  _i),
\end{equation}

\begin{equation}
\Delta_{x}(\Hcal_q,\Hcal_c) = \sum_{i=0}^{H_{\min}} \II[x^{(q)} _i \neq x^{(c)}_i] + \big||\Hcal_c|-|\Hcal_q|\big|.
\end{equation}

Here, $H_{\min} = \min\{|\Hcal_q|,|\Hcal_c|\}$, $T=\max\{T_q,T_c\}$ where the events of $\Hcal_q$ and $\Hcal_c$ are gathered until time $T_q$ and $T_c$ respectively; $\Delta_{t}(\unw(\Hcal_q),\Hcal_c)$ is the Wasserstein distance between the unwarped arrival time sequence $\unw(\Hcal_q)$ and the corpus sequence <cit.> and, $\Delta_{x}(\Hcal_q,\Hcal_c)$ measures the matching error for the marks, wherein the last term penalizes the marks of last $|\Hcal_c|-|\Hcal_q|$ events of $|\Hcal_c|$.

Model-based similarity score using Fisher kernel:
We hypothesize that the relevance score $s(\Hcal_q,\Hcal_c)$ also depends on a latent similarity that may not be immediately evident from the observed query and corpus sequences even after unwarping. Such 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}(\Hcal)$ parameterized by $\theta$ and then compute a similarity score using the Fisher similarity kernel between the unwarped query and corpus sequence pairs $(\unw(\Hcal_q),\Hcal_c)$ <cit.>. Specifically, we compute the relevance score between the unwarped query sequence $\unw(\Hcal_q)$ and the corpus sequence $\Hcal_c$ as follows:

\begin{align}
\kernel_{p_{\theta}}(\Hcal_q,\Hcal_c) = \vb_{p_{\theta}}(\unw(\Hcal_q)) ^\top \vb_{p_{\theta}}(\Hcal_c),   \label{eq:fisher}
\end{align}

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

\begin{align}
\vb_{p}(\Hcal) =  \Ib^{-1/2} _{\theta} \nabla_{\theta} \log p_{\theta}(\Hcal)/||\Ib^{-1/2} _{\theta} \nabla_{\theta} \log p_{\theta}(\Hcal)||_2,
\end{align}

$\Ib_{\theta}$ is the Fisher information matrix <cit.>, ,
$\Ib_{\theta} = \mathbb{E}_{\Hcal\sim p_{\theta}(\bullet)}\left[\nabla_{\theta} \log p_{\theta}(\Hcal)\nabla_{\theta} \log p_{\theta}(\Hcal) ^\top\right]$. We would like to highlight that $ \kernel_{p_{\theta}}(\Hcal_q,\Hcal_c)$ in Eq. (<ref>) is a normalized version of Fisher kernel since $||\vb_{p_{\theta}}(\cdot)||=1$. Thus, $\kernel_{p_{\theta}}(\Hcal_q,\Hcal_c)$ measures the cosine similarity between $ \vb_{p_{\theta}}(\unw(\Hcal_q))$ and $\vb_{p_{\theta}}(\Hcal_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 the Fisher similarity kernel because of two reasons: (i) it is known to be a natural similarity measure that allows us to use the underlying generative model in a discriminative learning task <cit.>; and, (ii) unlike KL divergence or other distribution (dis)similarities, it computes the cosine similarity between $ \vb_{p_{\theta}}(\unw(\Hcal_q))$ and $\vb_{p_{\theta}}(\Hcal_c) $, which makes it compatible with locality-sensitive hashing <cit.>.

Net relevance score:
Finally, we compute the relevance score as:

\begin{align}\label{eq:relevance-score-function}
s_{p,\unw}\left(\Hcal_q,\Hcal_c\right) & =   \kernel_{p}\left(\Hcal_q,\Hcal_c\right)
+\gamma \textsc{Sim}_U\left(\Hcal_q,\Hcal_{c}\right)
\end{align}

where $\gamma$ is a hyperparameter.

§.§ Neural Parameterization of

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. (<ref>). As we describe later, we use two MTPP models with different levels of modeling sophistication, ,  and . In , the likelihood of a corpus sequence is computed independently of the query sequence using self attention-based MTPP model, , Transformer Hawkes Process <cit.>. As a result, we can employ a locality-sensitive hashing-based efficient retrieval-based . In , 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 <ref>, the unwarping function $U(\cdot)$ should be unbiased, , a small value of $\left\|\unw(t)-t\right\|$ and monotonic, , $d \unw(t) /dt > 0$. 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) <cit.>,,

\begin{equation}
U_{\phi}(t) = \int_0 ^t u_{\phi}(\tau) d\tau + \eta,\label{eq:umnn}
\end{equation}

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 non-linear function. Since the underlying monotonicity can be achieved only by enforcing the 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. (<ref>) 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 a 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\|\unw(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, ,  and . These two models offer a nice tradeoff between accuracy and efficiency.

: Here, we use the Transformer Hawkes process <cit.>, which applies a self-attention mechanism to model the underlying generative process. In this model, the gradient of corpus sequences $\vb_{\theta}(\Hcal_c) =\nabla_{\theta} \log p_{\theta}(\Hcal_c)$ are computed independently of the query sequence $\Hcal_q$. Once we train the retrieval model,  $\vb_{\theta}(\Hcal_c)$ can be precomputed 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.

: 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 the underlying query sequence while modeling the likelihood of the corpus sequence. Specifically, we measure the latent cross-attention relevance score between $\Hcal_q$ and $\Hcal_c$ using the likelihood of a corpus sequence via a query-induced MTPP model built using the cross-attention between the generative process of both the sequences.

Given a query sequence $\Hcal_q$ and the first $r$ events of  the corpus sequence $\Hcal_c$, we parameterize the generative model for $(r+1)$-th event, , $p (e^{(c)}_{r+1} \given  \Hcal({t_r}))$ as $ p_{\theta  \pend}(\cdot)$, where $p_{\theta  \pend} (e^{(c)} _{r+1}) = \intensity _{\theta  \pend} (t^{(c)} _{r+1})\, m^{\pend}_{\theta  \pend} (x^{(c)} _{r+1})$, where $\intensity$ and $m^{\pend}$ are the density and distribution functions for the arrival time and the mark respectively, as described in Eq. (<ref>).

Input Layer: For each event $e_i ^{(q)}$ in the query sequence $\Hcal_q$ and each event $e_j ^{(c)}$ in the first $r$ events in the corpus sequence $\Hcal_c$,  the input layer computes the initial embeddings $\yb^{(q)} _i$ and $\yb^{(c)} _j$ as follows:

\begin{equation}
\yb^{(q)}_i = \wb_{y, x} x^{(q)}_i + \wb_{y, t}\unw(t^{(q)}_i) + \wb_{y, \Delta t} \left(\unw(t^{(q)}_i) - \unw(t^{(q)}_{i-1})\right) + \bb_{y}, \forall i\in[|\Hcal_q|],
\end{equation}

\begin{equation}
\yb^{(c)}_j = \wb_{y, x} x^{(c)}_j + \wb_{y, t}t^{(c)}_j + \wb_{y, \Delta t} \left(t^{(c)}_j - t^{(c)}_{j-1}\right)   + \bb_{y}, \forall j\in[|\Hcal_c(t_{r})|-1]
\end{equation}

where $\wb_{\bullet,\bullet}$ and $\bb_{y}$ are trainable parameters.

Attention layer:
The second layer models the interaction between all the query events and the past corpus events, , $\Hcal_q$ and $\Hcal_c(t_{r})$ using an attention mechanism. Specifically, following the existing attention models <cit.> it first adds a trainable position embedding $\pb$ with $\yb$— the output from the previous layer. As compared to fixed positional encodings <cit.>, these learnable encodings demonstrate better performances <cit.>. More specifically, we have the updates: $\yb^{(q)}_i \leftarrow \yb^{(q)}_i + \pb_i$ and $ \yb^{(c)}_j \leftarrow \yb^{(c)}_j + \pb_j$. Where, $\pb_\bullet\in \mathbb{R}^D$. Next, we apply  two linear transformations on the vectors  $[\yb^{(q)}_i]_{i\in [|\Hcal_q|]}$ and one linear transformation on  $[\yb^{(c)}_j]_{j\in[r]}$, , $ \sb_j = \Wb^S  \yb^{(c)}_j,   \kb_i = \Wb^K  \yb^{(q)}_i,   \vb_i = \Wb^V  \yb^{(q)}_i$. The state-of-the-art works on attention models <cit.> often refer $\sb_\bullet$, $\kb_\bullet$ and $\vb_\bullet$ as ,[The term   in this attention model is different from “query” sequence],  and  vectors respectively. Similarly, we call the trainable weights $\Wb^S, \Wb^K$ and $\Wb^V$ as the ,  and  matrices, respectively. Finally, we use the standard attention recipe <cit.> to compute the final embedding vector $\hb_j ^{(c,q)}$ for the event $e^{(c)} _j$, induced by query $\Hcal_q$. Such a recipe adds the values weighted by the outputs of a softmax function induced by the  and , ,

\begin{align}
\hb^{(c,q)} _j =
\sum_{i\in [|\Hcal_q|]} \frac{\exp\left( \sb_j ^\top \kb_i /\sqrt{D} \right)}{\sum_{i'\in [|\Hcal_q|]}\exp\left( \sb_j ^\top \kb_{i'} /\sqrt{D} \right)} \vb_i, \label{eq:attn}
\end{align}

Output layer:
Given the vectors $\hb^{(c,q)} _j$ provided by the attention mechanism (<ref>), we first apply a feed-forward neural network on them to compute  $\bhbc_r$ as follows:

\begin{equation*}
\bhbc _{r} = \sum_{j=1}^r \left[\wb_{\overline{h}}\odot\text{ReLU}(\hb^{(c,q)} _j \odot \wb_{h, f} + \bb_{h, o})  + \bb_{\overline{h}}\right],
\end{equation*}

where $\wb_{\bullet,\bullet}$, $\wb_\bullet$ and $\bb_{v}$. Finally, we use these vectors to compute the probability density of the arrival time of the next event $e^{(c)} _{r+1}$, ,  $\intensity_{\theta  \pend}(t_{r+1})$ and the mark distribution $m^{\pend} _{\theta  \pend}(x_{r+1})$. In particular, we realize $\intensity_{\theta  \pend}(t_{r+1})$ using a lognormal distribution of inter-arrival times, ,

\begin{align}
\hspace{-2mm}t^{(c)}_{r+1}- t^{(c)}_r \sim \textsc{LogNormal}\left(\mu_e\left(\bhbc _{r} \right),\sigma^2 _e\left(\bhbc _{r} \right) \right)\nn,
\end{align}

where, $\left[\mu_e\left(\bhbc _{r} \right),\sigma_e\left(\bhbc _{r} \right)\right] = \Wb_{t,q}  \bhbc _{r} \hspace{-2mm}+\bb_{t,q}$. Similarly, we model the mark distribution as,

\begin{align}
\hspace{-2mm} m^{\pend} _{\theta  \pend}(x_{r+1}) =  \dfrac{\exp\left(\wb_{x,m}^\top \bhbc +b_{x,m} \right)}{\sum_{x'\in \mathcal{C}}\exp\left(\wb_{x',m}^\top \bhbc +b_{x',m}\right)}, \label{eq:mark-mtpp-x}
\end{align}

where $\Wb_{\bullet,\bullet}$ are the trainable parameters. Therefore the set of trainable parameters for the underlying MTPP models is $\theta=\set{\Wb^\bullet, \Wb_{\bullet,\bullet}, \wb_\bullet,\wb_{\bullet,\bullet}, \bb_{\bullet},\bb_{\bullet,\bullet}}$.

Tradeoff between accuracy and efficiency Note that, unlike ,  the likelihoods of corpus sequences in  depend on the query sequence, making it more expressive than . However, these query-dependent corpus likelihoods cannot be precomputed before observing the query sequences and thus cannot be directly used for hashing. However, it can be deployed on top of , where a smaller set of relevant candidates is first selected using LSH applied on  and then reranked using this . Thus, our proposal offers a nice tradeoff between accuracy and efficiency.

§.§ Parameter estimation

Given the query sequences $\set{\Hcal_q}$, the corpus sequences $\set{\Hcal_c}$ along with their relevance labels $\set{y(\Hcal_q,\Hcal_c)}$, we seek to find $\theta$ and $\phi$ which ensure that:

\begin{align}
s_{p_{\theta},\unw_{\phi}}(\Hcal_q,\Hcal_{c_+}) \gg s_{p_{\theta},\unw_{\phi}}(\Hcal_q, \Hcal_{c_-})\, \forall\, c_{\pm} \in \Cr_{q \pm}.
\end{align}

To this aim, we minimize the following pairwise ranking loss <cit.> to estimate the parameters $\theta,\phi$:

\begin{align}
\underset{\theta,\phi} {\text{min}}\sum_{q\in\Qr}\sum_{\substack{c_+\in \Cr_{q\rel},\\ c-\in \Cr_{q\nrel} }}&    \big[s_{p_{\theta},\unw_{\phi}}(\Hcal_q,\Hcal_{c_-})- \nn  s_{p_{\theta},\unw_{\phi}}(\Hcal_q,\Hcal_{c_+}) + \delta \big]_+, %\label{eq:estimation_margin}
\end{align}

where, $\delta$ is a tunable margin.

§ SCALABLE RETRIEVAL WITH HASHING

Once we learn the model parameters $\theta$ and $\phi$, we can rank the set of corpus sequences $\Hcal_c$ in the decreasing order of $s_{p_{\theta},\unw_{\phi}}(\Hcal_{\newq},\Hcal_c)$ for a new query $\Hcal_{\newq}$ and return top$-K$ sequences. Such an approach requires $|\Ccal|$ comparisons per each test query, which can take a huge amount of time for many real-life applications where $|\Cr|$ 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. We first briefly describe the traditional random hyperplane-based hashing method and highlight its limitations before presenting our retrieval approach that uses a specific trainable hash code with desirable properties.

§.§ Random hyperplane based hashing method

Since the relevance between the query and corpus sequence pairs $(\Hcal_q,\Hcal_c)$ is measured using the cosine similarity between the gradient vectors, , $\kernel_{p_{\theta}}(\Hcal_q,\Hcal_c)$, one can use random hyperplane based locality sensitive hashing method for hashing the underlying gradient vectors $\vb_{p_{\theta}} (\Hcal_c)$ <cit.>.
Towards this goal, after training   we generate $R$ unit random vectors $\ub_r\in \mathbb{R}^D$ from i.i.d. Normal distributions and then compute a binary hash code, $\hash^c = [\sgn (\ub_1 ^\top \vb_{p_{\theta}}(\Hcal_c)),\dots, \sgn (\ub_R ^\top \vb_{p_{\theta}}(\Hcal_c))] $ for each $c\in \Ccal$. This leads to $2^R$ possible hash buckets $\set{\Bcal}$, where
each corpus sequence is assigned to one hash bucket using the algorithm proposed by <cit.>.

When we encounter an unseen test query $\Hcal_q$,  we compute the corresponding hash code $\hash^q$, assign it to a bucket $\Bcal$ and finally return only those sequences $\Hcal_c$ which were assigned to this bucket $\Bcal$. Thus, for each query, the number of comparisons is reduced from $|\Ccal|$ to $|\Bcal|$, , the number of corpus sequences in the bucket $\Bcal$.
Thus, if the corpus sequences are assigned uniformly across the different buckets, then the expected number of comparisons becomes $|\Ccal|/2^R$, which provides a significant improvement for  $R>2$.

Limitations of Binary Hash Codes In practice, binary hash codes are not trained from data, and consequently, they are not optimized to be uniformly distributed across different hash buckets. Consequently, the assignment of corpus sequences across different buckets may be quite skewed, leading to inefficient sequence retrieval.

§.§ Trainable Hashing for Retrieval

Responding to the limitations of the random hyperplane-based hashing method, we propose to learn the hash codes from data so that they can be optimized for performance.

Computation of a trainable hash code
We first apply a trainable nonlinear transformation $\Lambda_{\psi}$ with parameter $\psi$ on the gradients $\zzc = \vb_{p_{\theta}}(\Hcal_c)$ and then learn the binary hash vectors $\hash^c = \sgn\bracex{\Lambda_{\psi}\bracex{\zzc}}$  by solving the following optimization, where we use $\tanh\left(\Lambda_{\psi}(\cdot)\right)$ as a smooth approximation of $\sgn\left(\Lambda_{\psi}(\cdot)\right)$.

\begin{align}\label{eq:hash}
& \min_{\psi} \frac{\eta_1}{|\Cr|}\sum_{c\in\Cr}   \left|\bm{1}^\top \tanh\bracex{\Lambda_{\psi}\bracex{\zzc}}\right| + \frac{\eta_2}{|\Cr|}\sum_{c\in\Cr}   \left\| \left|\tanh\bracex{\Lambda_{\psi}\bracex{\zzc}}\right|-\bm{1}\right\|_1  \\
&\qquad + \frac{2\eta_3}{{D \choose 2}}  \cdot \bigg| \sum_{\substack{c\in \Ccal \\ i\neq j\in [D]}}  \tanh\bracex{\Lambda_{\psi}\bracex{\zzc}[i]} \cdot  \tanh\bracex{\Lambda_{\psi} \bracex{\zzc}[j]}\bigg| \nn
\end{align}

Efficient retrieval with hashing
[1]
Trained corpus embeddings
$\set{\vb^c = \vb_{p_{\theta}} (\Hcal_c)} $ using ;

new query sequences $\set{\Hcal_{\newq}}$, $K$:
# of corpus sequences to return; trained models for  and .
Output: $\set{L_\newq}$: top-$K$ relevant sequences from $\set{\Hcal_c}$.
$\psi\leftarrow\textsc{TrainHashNet}\left(\Lambda_{\psi},[\vb^c]_{c\in\Cr} \right)$
InitHashBuckets$(\cdot )$
$c\in \Cr$
$\hash^c\leftarrow \textsc{ComputeHashCode}\left(\zzc;\Lambda_{\psi}\right)$
each new query $\Hcal_{\newq}$
$\vb^{q'}\leftarrow  \nsrf(\Hcal_{\newq})$
$\hash^{q'}\leftarrow \textsc{ComputeHashCode} (\vb^{q'};  {\Lambda_{\psi}} )$
$c\in \Bcal$
$\vb^{\newq} _{\text{cross}}, \vb^{c} _{\text{cross}} \leftarrow \nsrs(\Hcal_{\newq},\Hcal_c)$
$s_{p_{\theta},U_{\phi}} (\Hcal_{q'},\Hcal_c) \leftarrow \textsc{Score}(\vb^{\newq} _{\text{cross}}, \vb^{c} _{\text{cross}}, \Hcal_q,\Hcal_c)$
$L_{\newq}\leftarrow \textsc{Rank}(\set{s_{p_{\theta},U_{\phi}} (\Hcal_{q'},\Hcal_c)},K)$
Return  $\set{L_{\newq}}$

Here, $\sum_{i=1}^3 \eta_i=1$. Moreover, different terms in Eq. (<ref>) allow the hash codes, $\hash^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 $\hash^c=  \tanh\bracex{\Lambda_{\psi}\bracex{\zzc}}$; (ii) the second term encourages the entries of $\hash^c$ to become as close to $\pm 1$ as possible so that $\tanh(\cdot)$ gives an accurate approximation of $\sgn(\cdot)$ ; (iii) the third term ensures that the entries of the hash codes, $\hash^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 <cit.>, document retrieval <cit.>. 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 <ref>. We are given gradient vectors $\vb^c = \vb_{p_{\theta}}(\Hcal_c)$ obtained by training .  Next, we train an additional neural network $\Lambda_{\psi}$ parameterized by $\psi$ (TrainHashNet$()$, line 2), which is used to learn a binary hash vector $\hash^c$ for each sequence $\Hcal_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 <cit.>, so that two sequences $\Hcal_c, \Hcal_{c'}$ lying in the same hash bucket have a very high value of cosine similarity $\cos(\vb^c,\vb^{c'})$. Finally, once a new query $\Hcal_\newq$ comes, we first compute  $\vb^{\newq}$ using the trained  model and then compute the binary hash codes $\hash^{\newq}$ using the trained hash network $\Lambda_\psi$ (lines 9–10). Next, we assign an appropriate bucket $\Bcal$ to it (line 11) and finally compare it with only the corpus sequences in the same bucket, , $\Hcal_c\in\Bcal$ (lines 12–15) using our model.

Bucket Assignment
As suggested in <cit.>, we design multiple hash tables and assign a bucket to the hashcode of a sequence using only a set of bits selected randomly. More specifically, let the number of hash tables be $M$. Given a query sequence, we calculate its hashcode using the procedure described in Algorithm <ref>, $\hash^{\newq} = \sgn\left(\Lambda_{\psi}(\vb^{\newq})\right)$. The hash code is a $R$ dimension vector with $\hash^{\newq} \in \{-1, 1\}^{R}$ and from this vector, we consider $L$ bits at random positions to determine the bucket to be assigned to the sequence. Here, $\hash^{\newq} $ represents the numbers between $\{0, 2^{L}-1\}$, ,  one of the $2^{L}$ different buckets in a hash table. Correspondingly, we assign $\hash^{\newq}$ into a bucket. However, such a procedure is dependent on the specific set of bits –that were selected randomly– used for deciding the bucket ID. Therefore, we use $M$ hash-tables and repeat the procedure of sampling $L$ bits and bucket assignment for each table. We follow a similar bucket assignment procedure for corpus sequences. As described in Algorithm <ref>, for an incoming query sequence in the test set, we use the above bucket assignment procedure and compute the relevance score for only the corpus sequences within the same buckets. For all our experiments, we set $H$ the same as the hidden dimension $D$, $M = 10$, and $L=12$.

Recall that we must use  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 (in line 13), preferably , since the corpus sequences have already been indexed by our LSH method.

§ EXPERIMENTS

In this section, we provide a comprehensive evaluation of and our hashing method.

Statistics of the search corpus for all datasets. ${|\Cr_{q\rel}|}/{|\Cr|}$ denotes the ratio of positive corpus sequences to the total sequences sampled for training. The ratio is kept the same for all queries.

Dataset     Audio     Celebrity     Electricity     Health     Sports
$  {|\Cr_{q\rel}|}/{|\Cr|} $     0.25     0.23     0.20     0.28     0.30

Total Events     1M     50M     60M     60M     430k

# Marks     5     16     5     5     21

§.§ Experimental Setup

Datasets We use five real-world datasets containing event sequences from various domains: (i) Audio <cit.>, (ii) Sports <cit.>, (iii) Celebrity <cit.>, (iv) Electricity <cit.>, and (v) Health <cit.>. The statistics of all datasets are given in Table <ref>. Across all datasets, $|\Hcal_q| = 5K$ and $|\Hcal_c| = 200K$. We partition the set of queries into 50% training, 10% validation, and the rest as test sets. During training, we negatively sample 100 corpus sequences for each query.

* 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.

* Sports: The dataset contains actions (, 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.

* 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.

* 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 an 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.

* 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. Here, a query corpus sequence pair is relevant if they are from a common patient.

For Health, Celebrity, and Electricity datasets, we lack the true ground-truth labeling of relevance between sequences. Therefore, we adopt a heuristic in which, given a dataset $\Dcal$, from each sequence $\seq_q\in\Dcal$ with $q\in[|\Dcal|]$, we first sample a set of sub-sequences $\mathcal{U}_q=\set{\Hcal\subset \texttt{seq}_q}$ with $|\Ucal_q|\sim \text{Unif}\,[200,300]$. For each such collection $\Ucal_q$, we draw exactly one query $\Hcal_q$ uniformly at random from $\Ucal_q$, , $\Hcal_q\sim\Ucal_q$. Then, we define $\Cr=\cup_{q\in[|\Dcal|]}\Ucal_q\cp \Hcal_q$, $\Cr_{q\rel}=\Ucal_q\cp \Hcal_q$ and $\Cr_{q\nrel}=\cup_{c\neq q}\big(\Ucal_c\cp \Hcal_c\big)$.

System Configuration
All our models were implemented using Pytorch v1.6.0 [https://pytorch.org/]. We conducted all our experiments on a server running Ubuntu 16.04, CPU: Intel(R) Xeon(R) Gold 6248 2.50GHz, RAM: 377GB, and GPU: NVIDIA Tesla V100.

Hyperparameters setup
We set the hyper-parameters values of  as follows: [(i)]
* contribution of model-independent similarity score in Eq. (<ref>), $\gamma = 0.1$;
* margin parameters for parameter estimation, $\delta \in \{0.1, 0.5, 1\}$ and weight for constraint violations, $\lambda \in \{0.1, 0.5, 1\}$;
* weight parameters for hashing objective (<ref>) $\eta_1, \eta_2, \eta_3 \in \{0.1, 0.2, 0.25\}$ and correspondingly $\eta_4 \in \{0.25, 0.4, 0.7\}$.

Hyper-parameter values used for different datasets. The values are determined by fine-tuning the performance on the validation set.

2*Parameters     5cDatasets

Audio     Celebrity     Electricity     Health     Sports
$\gamma$     0.1     0.1     0.5     0.1     0.1

$\delta$     0.5     0.5     0.1     0.1     0.5

$\{\eta_1, \eta_2, \eta_3\}$     {0.4, 0.3, 0.3}     {0.4, 0.3, 0.3}     {0.4, 0.3, 0.3}     {0.5, 0.25, 0.25}     {0.5, 0.25, 0.25}

Batch-size $\mathcal{B}$     32     32     32     16     16

$D$     64     64     48     32     32

Moreover, the values of training specific parameter values are: [(i)]
* batch-size, $\mathcal{B}$ is selected from $\{16, 32\}$, , for each batch we select $\mathcal{B}$ query sequences and all corresponding corpus sequences;
* hidden-layer dimension for cross-attention model, $D \in \{32, 48, 64\}$;
* number of attention blocks $N_b = 2$;
* number of attention heads $N_h = 1$ and
* UMNN network as a two-layer feed-forward network with dimension $\{128, 128\}$.  We also add a dropout after each attention layer with probability $p = 0.2$ and an $l_2$ regularizer over the trainable parameters with the coefficient set to $0.001$. All our parameters are learned using the Adam optimizer. We summarize the details of hyperparameters across different datasets in Table <ref>.

Evaluation metrics
We evaluate and the baselines using mean average precision (MAP), NDCG@k, and mean reciprocal rank (MRR). We calculate these metrics as follows:

\begin{equation}
\text{MAP} = \frac{1}{|\Hcal_{q'}|}\sum_{q' \in \Hcal_{q'}} \text{AP}_{q'}, \quad \text{NDCG@k} = \frac{\text{DCG}_k}{\text{IDCG}_k}, \quad \text{MRR} = \frac{1}{|\Hcal_{q'}|} \sum_{q' \in \Hcal_{q'}}\frac{1}{r_{q'}},
\end{equation}

where $\text{AP}_{q'}, \text{DCG}_k, \text{IDCG}_k$, and $r_{q'}$ denote the average precision, discounted cumulative gain at top-$k$ position, ideal discounted cumulative gain (at top-$k$), and the topmost rank of a related corpus sequence respectively. For all our evaluations, we follow a standard evaluation protocol <cit.> for our model and all baselines wherein for each query sequence in the test set, we rank all relevant corpus sequences and 1000 randomly sampled non-relevant sequences. All confidence intervals and standard deviations are calculated after five independent runs. For all metrics – MAP, NDCG, and MRR, we report results in terms of percentages with respect to maximum possible value , 1.

Baseline Implementations
For all the baselines, we use the official python implementations released by the authors of MASS, UDTW, and Sharp. The other implementations are same as in Chapter <ref>. For MASS and UDTW, we report the results using the default parameter values. For Sharp, we tune the hyper-parameter `gamma' (for more details see <cit.>) based on the validation set. In RMTPP, we set the BPTT length to 50, the RNN hidden layer size to 64, and the event embedding size 16. These are the parameter values recommended by the authors. For SAHP and THP, we set the dimension to 128 and the number of heads to 2. The values for all other transformer parameters are similar to the ones we used for the attention part in .

Retrieval quality in terms of Mean Average Precision (MAP in %) of all the methods across five datasets on the test set. Numbers with bold font (underlined) indicate the best (second best) performer. Boxed numbers indicate the best-performing state-of-the-art baseline. Results marked $\dagger$ are statistically significant (two-sided Fisher's test with $p \le 0.1$) over the best performing state-of-the-art baseline (-THP or Sharp). The standard deviation for MASS and UDTW are zero since they are deterministic retrieval algorithms.

Dataset     5cMean Average Precision (MAP) in %
Audio     Celebrity     Electricity     Health     Sports
MASS <cit.>     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

UDTW <cit.>     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

Sharp <cit.>     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

RMTPP <cit.>     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

-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

SAHP <cit.>     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

-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

THP <cit.>     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

-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

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

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

Retrieval quality in terms of NDCG@10 (in %) of all the methods.

Dataset     5cNDCG@10
Audio     Celebrity     Electricity     Health     Sports
MASS <cit.>     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 <cit.>     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 <cit.>     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 <cit.>     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

-RMTPP     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 <cit.>     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

-SAHP     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 <cit.>     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

-THP     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
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

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

Retrieval quality in terms of mean reciprocal rank (MRR in %).

Dataset     5cMean Reciprocal Rank (MRR)
Audio     Celebrity     Electricity     Health     Sports
MASS <cit.>     57.3$\pm$0.0     63.7$\pm$0.0     17.6$\pm$0.0     27.2$\pm$0.0     61.6$\pm$0.0

UDTW <cit.>     58.5$\pm$0.0     64.8$\pm$0.0     18.7$\pm$0.0     29.2$\pm$0.0     61.2$\pm$0.0

Sharp <cit.>     58.7$\pm$1.7     65.4$\pm$2.6     19.8$\pm$0.6     30.4$\pm$0.7     61.1$\pm$2.3

RMTPP <cit.>     54.2$\pm$3.9     64.5$\pm$4.6     15.8$\pm$1.2     25.2$\pm$1.8     56.2$\pm$4.8

-RMTPP     60.8$\pm$3.7     65.6$\pm$4.0     23.3$\pm$1.5     30.7$\pm$1.7     62.7$\pm$3.9

SAHP <cit.>     56.9$\pm$4.3     64.2$\pm$4.8     17.2$\pm$1.3     26.7$\pm$2.1     59.4$\pm$4.9

-SAHP     60.3$\pm$2.5     66.1$\pm$2.9     25.9$\pm$1.2     32.6$\pm$1.4     62.1$\pm$2.9

THP <cit.>     58.6$\pm$2.6     65.0$\pm$2.9     20.1$\pm$1.1     28.2$\pm$1.3     60.9$\pm$3.3

-THP     62.2$\pm$2.8     68.9$\pm$3.0     31.4$\pm$1.4     36.2$\pm$1.7     63.4$\pm$2.9

63.6$\pm$2.7     69.3$\pm$3.1     33.4$\pm$1.6     37.9$\pm$1.7     64.3$\pm$3.1

64.5$\pm$2.9     70.1$\pm$3.3     35.2$\pm$1.7     40.3$\pm$1.9     66.7$\pm$3.1

Retrieval quality in terms of NDCG@20 (in %) of all the methods.

Dataset     5cNDCG@20
Audio     Celebrity     Electricity     Health     Sports
MASS <cit.>     17.5$\pm$0.0     31.4$\pm$0.0     8.1$\pm$0.0     13.5$\pm$0.0     16.3$\pm$0.0

UDTW <cit.>     17.9$\pm$0.0     32.5$\pm$0.0     8.8$\pm$0.0     14.4$\pm$0.0     16.0$\pm$0.0

Sharp <cit.>     18.2$\pm$0.5     33.6$\pm$0.7     11.9$\pm$0.3     15.9$\pm$0.4     17.2$\pm$0.7

RMTPP <cit.>     16.0$\pm$1.1     32.2$\pm$1.6     7.1$\pm$0.5     12.1$\pm$0.7     17.1$\pm$1.1

-RMTPP     20.2$\pm$1.0     33.4$\pm$1.4     10.5$\pm$0.5     15.4$\pm$0.6     21.8$\pm$1.2

SAHP <cit.>     19.8$\pm$1.4     31.7$\pm$2.1     7.8$\pm$0.5     13.1$\pm$0.9     19.2$\pm$1.5

-SAHP     21.5$\pm$0.9     34.1$\pm$1.0     12.3$\pm$0.4     17.4$\pm$0.6     22.9$\pm$1.0

THP <cit.>     19.7$\pm$0.8     32.9$\pm$1.0     9.5$\pm$0.4     14.4$\pm$0.5     20.8$\pm$0.9

-THP     21.8$\pm$0.9     37.7$\pm$1.2     14.4$\pm$0.6     19.3$\pm$0.6     23.3$\pm$1.1

22.9$\pm$1.3     40.3$\pm$1.5     16.3$\pm$0.7     20.9$\pm$1.0     23.8$\pm$1.6

24.2$\pm$1.5     42.0$\pm$1.8     17.6$\pm$0.8     22.3$\pm$1.0     25.7$\pm$1.7

Baselines We consider three continuous time-series retrieval models: (i) MASS <cit.>, (ii) UDTW <cit.>, and (iii) Sharp <cit.>; and, three MTPP models (iv) RMTPP <cit.>, (v) SAHP <cit.>, and (vi) THP <cit.>. For sequence retrieval with MTPP models, we first train them across all the sequences using maximum likelihood estimation. Then, given a test query $\Hcal_{\newq}$, this MTPP method ranks the corpus sequences $\set{\Hcal_c}$ in decreasing order of their cosine similarity  $\text{CosSim}(\texttt{emb}^{(\newq)},\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., -RMTPP, -SAHP and -THP corresponding to RMTPP, SAHP, and THP. Specifically, -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 -MTPP models work as supervised models.

Evaluation protocol We partition the set of queries $\Qr$ into 50% training, 10% validation, and the rest as test sets. First, we train a retrieval model using the set of training queries. Then, for each test query $\newq$, 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 \in \{10, 20\}$.

§.§ Results on retrieval accuracy

Comparison with baselines
First, we compare the retrieval performance of our model against the baselines. Tables <ref>, <ref>, <ref>, and <ref> summarizes the results in terms of MAP, NDCG@10, MRR, and NDCG@20 respectively. From the results, we make the following observations:

* Both  and  outperform all the baselines by a substantial margin.

* outperforms , since the former has a higher expressive power.

* The variants of baseline MTPP models trained for sequence retrieval, , -RMTPP, -SAHP, and -THP outperform the vanilla MTPP models.

* The performances of vanilla MTPPs and the time series retrieval models (MASS, UDTW, and Sharp) are comparable.

Ablation study of and its variants in terms of Mean Average Precision (MAP) in %.

Variation of $s_{p_{\theta},U_{\phi}} (\Hcal_q,\Hcal_c)$     Audio     Celebrity     Health     Electricity     Sports
$-\Delta_x (\Hcal_q,\Hcal_c) - \Delta_t (U_{\phi}(\Hcal_q),\Hcal_c)$     36.1$\pm$0.0     43.7$\pm$0.0     18.9$\pm$0.0     18.9$\pm$0.0     41.3$\pm$0.0

$ \kernel_{p_{\theta}}(\Hcal_q,\Hcal_c)$     53.9$\pm$1.9     62.5$\pm$1.3     33.6$\pm$0.7     30.6$\pm$0.9     56.3$\pm$2.1

$\kernel_{p_{\theta}}(\Hcal_q,\Hcal_c) -\gamma \Delta_x (\Hcal_q,\Hcal_c)$     54.6$\pm$1.9     63.1$\pm$1.4     33.7$\pm$0.7     30.8$\pm$0.8     55.6$\pm$2.0

$\kernel_{p_{\theta}}(\Hcal_q,\Hcal_c) -\gamma \Delta_t (U_{\phi}(\Hcal_q),\Hcal_c)$     55.7$\pm$2.0     63.7$\pm$1.8     35.9$\pm$0.8     31.3$\pm$0.8     58.1$\pm$2.0

Without $U_{\phi}(\cdot)$     55.2$\pm$2.2     62.9$\pm$2.0     34.3$\pm$0.9     29.7$\pm$1.3     56.2$\pm$2.3

56.2$\pm$2.1     65.1$\pm$1.9     37.4$\pm$0.9     32.4$\pm$0.8     58.7$\pm$2.1

Ablation Study
Next, we compare the retrieval performance across four model variants:

* our model with only model-independent score, , $s_{p_{\theta},U_{\phi}} (\Hcal_q,\Hcal_c) = -\Delta_x (\Hcal_q,\Hcal_c) - \Delta_t (U_{\phi}(\Hcal_q),\Hcal_c)$;

* our model with only model-dependent score, , $s_{p_{\theta},U_{\phi}}(\Hcal_q,\Hcal_c) = \kernel_{p_{\theta}}(\Hcal_q,\Hcal_c)$;

* our model without any model-independent time similarity, , $s_{p_{\theta},U_{\phi}}(\Hcal_q,\Hcal_c) = \kernel_{p_{\theta}}(\Hcal_q,\Hcal_c) -\gamma \Delta_x (\Hcal_q,\Hcal_c)$;

* our model without any model-independent mark similarity, , $s_{p_{\theta},U_{\phi}}(\Hcal_q,\Hcal_c) = \kernel_{p_{\theta}}(\Hcal_q,\Hcal_c) -\gamma \Delta_t (U_{\phi}(\Hcal_q),\Hcal_c)$;

* our model without unwarping function $U_{\phi}(\cdot)$;

* the complete design of our model.

$\Hcal_q, \Hcal_c$

$U_{\phi}(\Hcal_q), \Hcal_c$

Effect of unwarping on a relevant query-corpus pair in Audio. $U_{\phi}(\cdot)$ learns to transform $\Hcal_q$ in order to capture a high value of its latent similarity with $\Hcal_c$.

In all cases, we used . Table <ref> shows that the complete design of our model (variant (<ref>))  achieves the best performance. We further note that removing $\kernel_{p_\theta}$ from the score (variant (<ref>)) leads to significantly poor performance. Interestingly, our model without any mark-based similarity (variant (<ref>)) leads to better performance than the model without time similarity  (variant (<ref>))— this could be attributed to the larger variance in query-corpus time distribution than the distribution of marks.

Effect of $U_{\phi}(\cdot)$
Finally, we observe that the performance deteriorates if we do not use an unwarping function $U_{\phi}(\cdot)$ (variant (<ref>)). Figure <ref> illustrates the effect of $U_{\phi}(\cdot)$. It shows that $U_{\phi}(\cdot)$ is able to learn a suitable transformation of the query sequence, which encapsulates the high value of latent similarity with the corpus sequence.

$\Hcal_q, \Hcal_c$

$\Hcal_q, \Hcal_c$

$\Hcal_q, \Hcal_c$

Tradeoff between NDCG@10 vs. Reduction factor, , % reduction in number of comparisons between query-corpus pairs w.r.t. the exhaustive comparisons for different hashing methods. The point marked as $ \color{red} {\star}$ indicates the case with exhaustive comparisons on the set of corpus sequences.

§.§ Results on Retrieval Efficiency

We compare our efficient sequence retrieval method given in Algorithm <ref> against the random hyperplane (RH) method and three variants of our proposed training problem in Eq. (<ref>).

* Our $(\eta_2, \eta_3)$ which sets $\eta_1=0$ and thus does not enforce even distribution of $\pm 1 $ in $\hash^c$;

* Our $(\eta_1, \eta_3)$ which sets $\eta_2=0$ and thus $\tanh$ does not accurately approximate $\sgn$;

* Our $(\eta_1, \eta_2)$ which sets $\eta_3=0$ and thus does not enforce $\hash^c$ to be compact and free of redundancy.

Our $(\eta_1,\eta_2,\eta_3)$ is the complete design that includes all trainable components. Figure <ref> summarizes the results.

Comparison with random hyperplane   Figure <ref>  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. (<ref>)
Figure <ref> 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.

§.§ Analysis at a Query Level

Next, we compare the performance between and other state-of-the-art methods at a query level. Specifically, for each query $\Hcal_q$ we compute the advantage of using in terms of gain in average precision, , AP() $-$ AP(baseline) for two most competitive baselines – -SAHP and -THP. We summarize the results in Figure <ref>, which show that for at least 70% of the queries, outperforms or fares competitively with these baselines across all datasets.

Query-wise performance comparison between and best baseline methods – -THP, -SAHP. Queries are sorted by the decreasing gain in AP.

Training-times of for all datasets.

Run Time     Audio     Celebrity     Electricity     Health     Sports
$\le$ 3hr     $\le$ 5hr     $\le$ 6hr     $\le$ 6hr     $\le$ 2hr

§.§ Runtime Analysis

Next, we calculate the run-time performance of . With this experiment, our goal is to determine if the training times of are suitable for designing solutions for real-world problems. From the results in Table <ref>, we note that even for datasets with up to 60 million events, the training times are well within the feasible range for practical deployment.

§.§ Query Length

We perform an additional experiment of sequence retrieval with varying query lengths. Specifically, we sample queries of lengths $|\mathcal{H}_q| \sim Unif(10, 50)$ and $|\mathcal{H}_q| \sim Unif(50, 100)$ and report the sequence retrieval results in Table <ref> and Table <ref> respectively. The results show that the performance of all models deteriorates significantly as we reduce the length of query sequences. They also show that even with smaller query lengths, significantly outperforms the other state-of-the-art baseline -THP.

Retrieval quality in terms of mean average precision (MAP) for query sequence lengths sampled between 10 and 50.

$|\mathcal{H}_q| = (10,20)$     Audio     Celebrity     Health     Electricity     Sports
-THP     18.97     22.06     9.48     12.27     26.58

21.30     25.77     15.83     10.79     27.63

Retrieval quality in terms of mean average precision (MAP) for query sequence lengths sampled between 50 and 100.

$|\mathcal{H}_q| = (50,100)$     Audio     Celebrity     Health     Electricity     Sports
-THP     27.94     37.85     17.58     21.61     31.26

28.58     41.92     19.67     23.54     36.92

§.§ Qualitative Analysis

To get deeper insights into the working of our model, we perform a qualitative analysis between a query sequence from the dataset and the sequence retrieved by . More specifically, we aim to understand the similar patterns between query and corpus sequences that searches for in the corpus and plot the query sequence and the corresponding top-ranked relevant corpus sequence retrieved by . The results across all datasets in Figure <ref> show that the inter-arrival times of the CTES retrieved by closely matches the query inter-arrival times.

Qualitative examples of inter-event times of events in a query sequence and the top-search results by for all datasets.

§ CONCLUSION

In this chapter, we proposed a novel supervised continuous-time event sequence retrieval system called  using neural MTPP models. To achieve efficient retrieval over a 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 our retrieval model is more effective than several baselines. Our work opens several avenues for future work, including the design of generative models for relevance sequences and counterfactual explanations for relevance label predictions.

CHAPTER: MODELING HUMAN ACTION SEQUENCES

§ INTRODUCTION

A majority of the data generated via human activities such as running, playing basketball, cooking, , can be represented as a sequence of actions over a continuous time. These actions denote a step taken by a user towards achieving a certain goal and vary in their start and completion times, depending on the user and the surrounding environment <cit.>. Therefore, unlike synthetic time series, these continuous-time action sequences (CTAS) can vary significantly even if they consist of the same set of actions. For , one person making omelets may take a longer time to cook eggs while another may prefer to cook for a short time[https://bit.ly/3F5aEwX (Accessed October 2022)]; or in a football game, Xavi may make a faster pass than Pirlo, even though the goals and the sequence of actions are the same. In addition, modeling the dynamics of CTAS becomes increasingly challenging due to the limited ability of the current neural frameworks, recurrent or self-attention-based, in capturing the continuous nature of action times <cit.>. This situation is further exacerbated due to the large variance in action-times and types. Therefore, the problem of modeling a CTAS has been overlooked by the past literature.

In recent years, neural marked temporal point processes (MTPP) have shown significant promise in modeling a variety of continuous-time sequences in healthcare <cit.>, finance <cit.>, education <cit.>, and social networks <cit.>. However, standard MTPP have a limited modeling ability for CTAS as: (i) they assume a homogeneity among sequences, , they cannot distinguish between two sequences of similar actions but with different time duration; (ii) in a CTAS, an action may finish before the start of the next action and thus, to model this empty time interval an MTPP must introduce a new action type, , NULL or end-action, which may lead to an unwarranted increase in the types of actions to be modeled; and (iii) they cannot encapsulate the additional features associated with an action, for , the minimum time for completion, necessary previous actions, or can be extended to sequence generation.

§.§ Our Contribution

In this chapter, we present (Point Process flows for Activity Sequences), a normalizing flow-based neural MTPP framework, designed specifically to model the dynamics of a CTAS <cit.>. Specifically, addresses three challenging problems – (i) action prediction, (ii) goal detection, and (iii) the first-of-its-kind task of end-to-end sequence generation. We learn the distribution of actions in a CTAS using temporal normalizing flows (NF) <cit.> conditioned on the dynamics of the sequence as well as the action features (, minimum completion time, ). Such a flow-based formulation provides flexibility over other similar frameworks <cit.> to better model the inter-action dynamics within and across the sequences. Moreover, our model is designed for early detection of the sequence goal, , identifying the result of a CTAS without traversing the complete sequence. We achieve this by using a time-bounded optimization procedure, , by incrementally increasing the probability of identifying the true goal via a margin-based and a weighted factor-based learning <cit.>. Such an optimization procedure allows to model the goal-action hierarchy within a sequence, , the necessary set of actions in a CTAS towards achieving a particular goal, and simultaneously, the order of actions in CTAS with similar goals.

To the best of our knowledge, in this paper, we present the first-ever application of MTPP via end-to-end action sequence generation. Specifically, given the resultant goal, can generate a CTAS with the necessary set of actions and their occurrence times. Such a novel ability for MTPP models can reinforce their usage in applications related to bio-signals <cit.>, sensor-data <cit.>, , and overcome the modeling challenge due to scarcity of activity data <cit.>. Buoyed by the success of attention models in sequential applications <cit.>, we use a self-attention architecture in to model the inter-action influences in a CTAS. In summary, the key contributions we make in this paper via are:

* We propose , a novel temporal flow-based MTPP framework designed specifically for modeling human activities with a time-bounded optimization framework for early detection of CTAS goal.

* Our normalizing flow-based modeling framework incorporates the sequence and individual action dynamics along with the action-goal hierarchy. Thus, introduces the first-of-its-kind MTPP application of end-to-end action CTAS generation with just the sequence-goal as input.

* Finally, we empirically show that outperforms the state-of-the-art models for all three tasks –  action prediction, goal detection, and sequence generation.

§ PRELIMINARIES

In this section, we present a background on activity prediction and the problems addressed in this chapter.

§.§ Activity Prediction

Activity modeling in videos is a widely used application with recent approaches focusing on frame-based prediction. <cit.> predicts the future actions via hierarchical representations of short clips, <cit.> jointly predicts future activity ad the starting time by capturing different sequence features, and a similar procedure is adopted by <cit.> that predicts the action categories of a sequence of future activities as well as their starting and ending time. <cit.> propose a method for early classification of a sequence of frames extracted from a video by maximizing the margin-based loss between the correct and the incorrect categories, however, it is limited to visual data and cannot incorporate the action times. This limits its ability for use in CTAS, and sequence generation. A recent approach <cit.> proposed to model the dynamics of action sequences using a variational auto-encoder built on top of a temporal point process. We consider their work as most relevant to as it also addressed the problem of CTAS modeling. However, as shown in our experiments was able to easily outperform it across all metrics. This could be attributed to the limited modeling capacity of VAE over normalizing flows. Moreover, their sampling procedure could not be extended to sequence generation. Therefore, in contrast to the past literature, is the first application of MTPP models for CTAS modeling and end-to-end sequence generation.

§.§ Problem Formulation

As mentioned earlier, we represent an activity via a continuous-time action sequence, , a series of actions undertaken by users and their corresponding time of occurrences. We derive each CTAS from annotated frames of videos consisting of individuals performing certain activities. Specifically, for every video, we have a sequence of activity labels being performed in the video along with timestamps for each activity. Therefore, each CTAS used in our experiments is derived from these sequences of a video. Formally, we provide a detailed description of a CTAS in Definition <ref>.

We define a continuous-time action sequence (CTAS) as a series of action events taken by a user to achieve a particular goal. Specifically, we represent a CTAS as an MTPP $\cm{S}_k=\{e_i=(c_i, t_i) | i \in[k] , t_i<t_{i+1}\}$, where $t_i \in \mathbb{R}^+$ is the start time of the action, $c_i\in \cm{C}$ is the discrete category or mark of the $i$-th action, and $\cm{C}$ is the set of all categories. Each CTAS has an associated result, $g \in \cm{G}$, that signifies the goal of the CTAS. Here, $\cm{G}$ denotes the set of all possible sequence goals.

To highlight the relationship between sequence goal and actions, consider the example of a CTAS with the goal of making-coffee, would comprise of actions – take-a-cup, pour-milk, add-coffee-powder, add-sugar, and stir – at different time intervals. Given the aforementioned definitions, we formulate the tasks of next action, sequence goal prediction, and sequence generation as:

A CTAS of all actions, $\cm{S}_k$, consisting of categories and times of different actions that lead to a goal $g$.

A probabilistic prediction model with three distinct tasks – (i) to estimate the likelihood of the next action $e_{k+1}$ along with the action category and occurrence time; (ii) to predict the goal of the CTAS being modeled, , $\widehat{g}$; and (iii) a generative model to sample a sequence of actions, $\widehat{\cm{S}}$ given the true sequence goal, $g$.

§ MODEL

In this section, we first present a high-level overview of the model and then describe the neural parameterization of each component in detail. Lastly, we provide a detailed description of its optimization and sequence generation procedure.

§.§ High Level Overview

We use an MTPP denoted by $p_{\theta}(\cdot)$, to learn the generative mechanism of a continuous-time action sequence. Moreover, we design the sequence modeling framework of $p_{\theta}(\cdot)$ using a self-attention-based encoder-decoder model <cit.>. Specifically, we embed the actions in a CTAS, , $\cm{S}_k$, to a vector embedding, denoted by $\bs{s}_k$, using a weighted aggregation of all past actions. Therefore, $\bs{s}_k$ signifies a compact neural representation of the sequence history, , all actions till the $k$-th index and their marks and occurrence times. Recent research <cit.> has shown that an attention-based modeling choice can better capture the long-term dependencies as compared to RNN-based MTPP models <cit.>. A detailed description of the embedding procedure is given in Section <ref>.

We use our MTPP $p_{\theta}(\cdot)$ to estimate the generative model for the $(k+1)$-th action conditioned on the past, , $p(e_{k+1})$ as:

\begin{equation}
p_{\theta}(e_{k+1} | \bs{s}_k) = \mathbb{P}_{\theta}(c_{k+1}|\bs{s}_k) \cdot \rho_{\theta}(\Delta_{t, k+1}|\bs{s}_k),
\end{equation}

where $\mathbb{P}_{\theta}(\cdot)$ and $\rho_{\theta}(\cdot)$ denote the probability distribution of marks and the density function for inter-action arrival times, respectively. Note that both the functions are conditioned on $\bs{s}_k$ and thus requires a joint optimizing procedure for both – action time and mark prediction. Next, we describe the mechanism used in to predict the next action and goal detection in a CTAS.

Next Action Prediction
We determine the most probable mark and time of the next action, using $p_{\theta} (\cdot)$ via standard sampling techniques over $\mathbb{P}_{\theta}(\cdot)$ and $\rho_{\theta}(\cdot)$ respectively <cit.>.

\begin{equation}
\widehat{e_{k+1}} \sim p_{\theta}(e_{k+1} | \bs{s}_k),
\end{equation}

In addition, to keep the history embedding up-to-date with all past actions, we iteratively update $\bs{s}_k$ to $\bs{s}_{k+1}$ by incorporating the details of action $e_{k+1}$.

Goal Detection
Since the history embedding, $\bs{s}_k$, represents an aggregation of all past actions in a sequence, it can also be used to capture the influences between actions and thus, can be extended to detect the goal of the CTAS. Specifically, to detect the CTAS goal, we use a non-linear transformation over $\bs{s}_k$ as:

\begin{equation}
\widehat{g} \sim \mathbb{P}_{g' \in \cm{G}}(\Phi(s_k)),
\label{proact_eq:goal}
\end{equation}

where $\mathbb{P}_{\bullet}$ denotes the distribution over all sequence goals and $\Phi(\cdot)$ denotes the transformation via a fully-connected MLP layer.

§.§ Neural Parameterization

Here, we present a detailed description of the architecture of our MTPP, $p_{\theta}(\cdot)$, and the optimization procedure in . Specifically, we realize $p_{\theta}(\cdot)$ via a three-layer architecture:

(1) Input Layer
As mentioned in Section <ref>, each action $e_i \in \cm{S}_k$ is represented by a mark $c_i$ and time $t_i$. Therefore, we embed each action as a combination of all these features as:

\begin{equation}
\bs{y}_i = \bs{w}_{y, c} c_i + \bs{w}_{y, t} t_{i} + \bs{w}_{y, \Delta} \Delta_{t,i} + \bs{b}_y,
\end{equation}

where $\bs{w}_{\bullet, \bullet}, \bs{b}_{\bullet}$ are trainable parameters and $\bs{y}_i \in \mathbb{R}^D$ denotes the vector embedding for the action $e_i$ respectively. In other sections as well, we denote weight and bias as $\bs{w}_{\bullet, \bullet}$ and $\bs{b}_{\bullet, \bullet}$ respectively.

(2) Self-Attention Layer
We use a masked self-attention layer to embed the past actions to $\bs{s}_k$ and to interpret the influence between the past and the future actions. In detail, we follow the standard attention procedure <cit.> and first add a trainable positional encoding, $\bs{p}_i$, to the action embedding, , $\bs{y}_i \leftarrow \bs{y}_i + \bs{p}_i$. Such trainable encodings are shown to be more scalable and robust for long sequence lengths as compared to those based on a fixed function <cit.>. Later, to calculate an attentive aggregation of all actions in the past, we perform three independent linear transformations on the action representation to get the query, key, and value embeddings, ,

\begin{equation}
\bs{q}_i = \bs{W}^Q  \bs{y}_i, \quad \bs{k}_i = \bs{W}^K  \bs{y}_i, \quad \bs{v}_i = \bs{W}^V  \bs{y}_i,
\end{equation}

where $\bs{q}_{\bullet}, \bs{k}_{\bullet}, \bs{v}_{\bullet}$ denote the query, key, and value vectors, respectively. Following standard self-attention model, we represent $\bs{W}^{Q}$, $\bs{W}^{K}$ and $\bs{W}^{V}$ as trainable Query, Key, and Value matrices respectively. Finally, we compute $\bs{s}_k$ conditioned on the history as:

\begin{equation}
\bs{s}_k =  \sum_{i=1}^{k} \frac{\exp\left(\bs{q}_k^{\top} \bs{k}_i /\sqrt{D} \right)}{\sum_{i'=1}^{k}\exp\left( \bs{q}_k^{\top} \bs{k}_{i'} /\sqrt{D} \right)} \bs{v}_i, \label{proact_eq:attn}
\end{equation}

where $D$ denotes the number of hidden dimensions. Here, we compute the attention weights via a softmax over the interactions between the query and key embeddings of each action in the sequence and perform a weighted sum of the value embeddings.

Now, given the representation $\bs{s}_k$, we use the attention mechanism in Eqn. (<ref>) and apply a feed-forward neural network to incorporate the necessary non-linearity to the model as:

\begin{equation*}
\bs{s}_k \leftarrow \sum_{i=1}^k \big[ \bs{w}_{s, m}\odot\textsc{ReLU}(\bs{s}_i \odot \bs{w}_{s, n} + \bs{b}_{s, n})  + \bs{b}_{s, m} \big],
\end{equation*}

where $\bs{w}_{s, m}, \bs{b}_{s, m}$ and $\bs{w}_{s, n}, \bs{b}_{s, n}$ are trainable parameters of the outer and inner layer of the point-wise feed-forward layer.

To support faster convergence and training stability, we employ (i) layer normalization; (ii) stacking multiple self-attention blocks; and (iii) multi-head attention. Since these are standard techniques <cit.>, we omit their mathematical descriptions.

(3) Output Layer
At every index $k$, outputs the next action and the most probable goal of the CTAS. We present the prediction procedure for each of them as follows:

Action Prediction:
We use the output of the self-attention layer, $\bs{s}_k$ to estimate the mark distribution and time density of the next event, , $\mathbb{P}_{\theta}(e_{k+1})$ and $\rho_{\theta}(e_{k+1})$ respectively. Specifically, we model the $\mathbb{P}_{\theta}(\cdot)$ as a softmax over all other marks as:

\begin{equation}
\mathbb{P}_{\theta}(c_{k+1}) = \frac{\exp\left(\bs{w}_{c, s}^{\top} \bs{s}_i + \bs{b}_{c, s} \right)}{\sum_{c'=1}^{|\cm{C}|}\exp\left( \bs{w}_{c', s}^{\top} \bs{s}_i + \bs{b}_{c', s} \right)},
\label{proact_eqn: samplemark}
\end{equation}

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

In contrast to standard MTPP approaches that rely on an intensity-based model <cit.>, we capture the inter-action arrival times via a temporal normalizing flow (NF). In detail, we use a lognormal flow to model the temporal density $\rho_{\theta}(\Delta_{t, k+1})$. Moreover, standard flow-based approaches <cit.> utilize a common NF for all events in a sequence, , the arrival times of each event are determined from a single or mixture of flows trained on all sequences. We highlight that such an assumption restricts the ability to model the dynamics of a CTAS, as unlike standard events, an action has three distinguishable characteristics – (i) every action requires a minimum time for completion; (ii) the time taken by a user to complete an action would be similar to the times of another user; and (iii) similar actions require similar times to complete. For example, the time taken to complete the action add-coffee would require a certain minimum time of completion, and these times would be similar for all users. Intuitively, the time for completing the action add-coffee would be similar to those for the action add-sugar.

To incorporate these features in , we identify actions with similar completion times and model them via independent temporal flows. Specifically, we cluster all actions $c_i \in \cm{C}$ into $\cm{M}$ non-overlapping clusters based on the mean of their times of completion, and for each cluster, we define a trainable embedding $\bs{z}_r \in \mathbb{R}^{D} \, \forall r \in \{1, \cdots, \cm{M}\}$. Later, we sample the start-time of the future action by conditioning our temporal flows on the cluster of the current action as:

\begin{equation}
\widehat{\Delta_{t, k+1}} \sim \textsc{LogNormal}\left(\bs{\mu}_k , \bs{\sigma}^2_k \right),
\label{proact_eqn: sampletime}
\end{equation}

where, $[\bs{\mu}_k ,\bs{\sigma}^2_k]$, denote the mean and variance of the lognormal temporal flow and are calculated via the sequence embedding and the cluster embedding as:

\begin{equation}
\bs{\mu}_k = \sum_{r=1}^{\cm{M}} \cm{R}(e_k, r) \big(\bs{w}_{\mu} \left(\bs{s}_{k}\odot\bs{z}_{c, i} \right) + \bs{b}_{\mu}\big),
\end{equation}

\begin{equation}
\bs{\sigma}^2_k  = \sum_{r=1}^{\cm{M}} \cm{R}(e_k, r)  \big( \bs{w}_{\sigma} \left(\bs{s}_{k}\odot\bs{z}_{c, i} \right) + \bs{b}_{\sigma}\big),
\end{equation}

where $\bs{w}_{\bullet}, \bs{b}_{\bullet}$ are trainable parameters, $\cm{R}(e_k, r)$ is an indicator function that determines if event $e_k$ belongs to the cluster $r$ and $\bs{z}_r$ denotes the corresponding cluster embedding. Such a cluster-based formulation facilitates the ability of the model to assign similar completion times for events in the same cluster. To calculate the time of the next action, we add the sampled time difference to the time of the previous action $e_k$, ,

\begin{equation}
\widehat{t_{k+1}} = t_k + \widehat{\Delta_{t, k+1}}
\end{equation}

where, $\widehat{t_{k+1}}$ denotes the predicted time for the action $e_{k+1}$.

Goal Detection:
In contrast to other MTPP approaches <cit.>, an important feature of is identifying the goal of a sequence, , a hierarchy on top of the actions in a sequence, based on the past sequence dynamics. To determine the goal of a CTAS, we utilize the history embedding $\bs{s}_k$ as it encodes the inter-action relationships of all actions in the past. Specifically, we use a non-linear transformation via a feed-forward network, denoted as $\Phi(\cdot)$ over $\bs{s}_k$ and apply a softmax over all possible goals.

\begin{equation}
\Phi(\bs{s}_k) = \textsc{ReLU} (\bs{w}_{\Phi, s} \bs{s}_k + \bs{b}_{\Phi, s}),
\end{equation}

where, $\bs{w}_{\bullet, \bullet}, \bs{b}_{\bullet, \bullet}$ are trainable parameters. We sample the most probable goal as in Eqn. (<ref>).

We highlight that we predict the CTAS goal at each interval, though a CTAS has only one goal. This is to facilitate early goal detection in comparison to detecting the goal after traversing the entire CTAS. More details are given in Section <ref> and Section <ref>.

§.§ Early Goal Detection and Action Hierarchy

Here, we highlight the two salient features of – early goal detection and modeling the goal-action hierarchy.

Early Goal Detection
Early detection of sequence goals has many applications ranging from robotics to vision <cit.>. To facilitate early detection of the goal of a CTAS in , we devise a ranking loss that forces the model to predict a non-decreasing detection score for the correct goal category. Specifically, the detection score of the correct goal at the $k$-th index of the sequence, denoted by $p_k(g| \bs{s}_k, \Phi)$, must be more than the scores assigned the correct goal in the past. Formally, we define the ranking loss as:

\begin{equation}
\cm{L}_{k, g} = \max \big(0, p^*_k(g) - p_k(g| \bs{s}_k, \Phi)\big),
\label{proact_eqn: margin}
\end{equation}

where $p^*_k(g)$ denotes the maximum probability score given to the correct goal in all past predictions.

\begin{equation}
p^*_k(g) = \max_{j \in \{1, k-1\}} p_j(g| \bs{s}_j, \Phi),
\label{proact_eqn: pastmax}
\end{equation}

where $p_k(g)$ denotes the probability score for the correct goal at index $k$. Intuitively, the ranking loss $\cm{L}_{k,g}$ would penalize the model for predicting a smaller detection score for the correct CTAS goal than any previous detection score for the same goal.

Action Hierarchy
Standard MTPP approaches assume the category of marks as independent discrete variables, , the probability of an upcoming mark is calculated independently <cit.>. Such an assumption restricts the predictive ability while modeling CTAS, as in the latter case, there exists a hierarchy between goals and actions that lead to the specific goal. Specifically, actions that lead to a common goal may have similar dynamics and it is also essential to model the relationships between the actions of different CTAS with a common goal. We incorporate this hierarchy in along with our next action prediction via an action-based ranking loss. In detail, we devise a loss function similar to Eqn. <ref> where we restrict the model to assign non-decreasing probabilities to all actions leading to the goal of CTAS under scrutiny.

\begin{equation}
\cm{L}_{k, c} = \sum_{c' \in \cm{C}^*_g} \max \big(0, p^*_k(c') - p_k(c'| \bs{s}_k)\big),
\label{proact_eqn: cat_margin}
\end{equation}

where $\cm{C}^*_g, p_k(c'| \bs{s}_k)$ denote a set of all actions in CTAS with the goal $g$ and the probability score for the action $c' \in \cm{C}^*_g$ at index $k$ respectively. Here, $p^*_k(c')$ denotes the maximum probability score given to action $c'$ in all past predictions and is calculated similar to Eqn. <ref>. We regard  $\cm{L}_{k, g}$ and $\cm{L}_{k, c}$ as margin losses, as they aim to increase the difference between two prediction probabilities.

§.§ Optimization

We optimize the trainable parameters in , , the weight and bias tensors ($\bs{w}_{\bullet, \bullet}$ and $\bs{b}_{\bullet, \bullet}$) for our MTPP $p_{\theta} (\cdot)$, using a two channels of training consisting of action and goal prediction. Specifically, to optimize the ability of for predicting the next action, we maximize the joint likelihood for the next action and the lognormal density distribution of the temporal flows.

\begin{equation}
\mathscr{L} = \sum_{k = 1}^{|\cm{S}|} \log \big( \mathbb{P}_{\theta}(c_{k+1}|\bs{s}_k) \cdot \rho_{\theta} (\Delta_{t, k+1}| \bs{s}_k) \big ),
\label{proact_eqn:likelihood}
\end{equation}

where $\mathscr{L}$ denotes the joint likelihood, which we represent as the sum of the likelihoods for all CTAS. In addition to action prediction, we optimize the parameters for early goal detection via a temporally weighted cross entropy (CE) loss over all sequence goals. Specifically, we follow a popular reinforcement recipe of using a time-varying discount factor over the prediction loss as:

\begin{equation}
\cm{L}_g = \sum_{k = 1}^{|\cm{S}|} \gamma^k \cdot \cm{L}_{\textsc{CE}} \big(p_k(g| \bs{s}_k)\big),
\label{proact_eqn: discount}
\end{equation}

where $\gamma \in [0,1], \cm{L}_{\textsc{CE}} \big(p_k(g| \bs{s}_k)\big)$ denote the decaying factor and a standard softmax-cross-entropy loss respectively. Such a recipe is used exhaustively for faster convergence of reinforcement learning models <cit.>. Here, the discount factor penalizes the model for taking longer times to detect the CTAS goal by decreasing the gradient updates to the loss.

Margin Loss
In addition, we minimize the margin losses given in Section <ref> with the current optimization procedure. Specifically, we minimize the following loss:

\begin{equation}
\cm{L}_m = \sum_{k=1}^{|\cm{S}|} \cm{L}_{k, g} + \cm{L}_{k, c},
\end{equation}

where $\cm{L}_{k, g}$ and $\cm{L}_{k, c}$ are margin losses defined in Eqn. <ref> and Eqn. <ref> respectively. We learn the parameters of using an Adam <cit.> optimizer for both likelihood and prediction losses.

§.§ Sequence Generation

An important ability of is the end-to-end generation of action sequences. Specifically, given the CTAS goal as input, we can generate a most probable sequence of actions that may lead to that specific goal. Such a feature has a range of applications from sports analytics <cit.>, forecasting <cit.>, identifying the duration of an activity <cit.>,

A standard approach for training a sequence generator is to sample future actions in a sequence and then compare them with the true actions <cit.>. However, such a procedure has multiple drawbacks as it is susceptible to noises during training and deteriorates the scalability of the model. Moreover, we highlight that such sampling-based training cannot be applied to a self-attention-based model as it requires a fixed-sized sequence as input <cit.>. Therefore, we resort to a two-step generation procedure that is defined below:

1 Pre-Training: The first step requires training all parameters for action prediction and goal detection. This step is necessary to model the relationships between actions and goals and we represent the set of optimized parameters as $\theta^*$ and the corresponding MTPP as $p_{\theta^*}(\cdot)$ respectively.

2 Iterative Sampling: We iteratively sample events and update parameters via our trained MTPP till the model predicts the correct goal for CTAS or we encounter an  action. Specifically, using $p_{\theta^*}(\cdot)$ and the first real action ($e_1$) as input, we calculate the detection score for the correct goal, , $p_1(g| \bs{s}_k)$ and while its value is highest among all probable goals, we sample the mark and time of next action using Eqn. <ref> and Eqn. <ref> respectively.

Such a generation procedure harnesses the fast sampling of temporal normalizing flows and simultaneously is conditioned on the action and goal relationships. A detailed pseudo-code of the sequence generation procedure used in is given in Algorithm <ref>.

Input: $g$: Goal of CTAS
$e_1$: First Action
$p_{\theta^*}(\cdot)$: Trained MTPP

Output: $\widehat{S}$: Generated CTAS
$\cm{S}_1 \leftarrow e_1$

$k = 1$

$k < \mathtt{max\_len}$

Sample the mark of next action: $\widehat{c_{k+1}} \sim \mathbb{P}_{\theta^*}(\bs{s}_k)$

Sample the time of next action: $\widehat{t_{k+1}} \sim \rho_{\theta^*}(\bs{s}_k)$

Add to CTAS: $\cm{S}_{k+1} \leftarrow \cm{S}_{k} + e_{k+1}$

Update the MTPP parameters $\bs{s}_{k+1} \leftarrow p(\bs{s}_{k}, e_{k+1})$

Calculate most probable goal: $\widehat{g}_k = \max_{\forall g'} \big(p_k(g'| \bs{s}_k)\big)$

$\widehat{g_i} != g \, \mathrm{or} \, \widehat{c_{k+1}} == \mathtt{<EOS>}$

Add EOS mark: $\widehat{\cm{S}} \leftarrow \cm{S}_{k+1} + \mathtt{<EOS>}$

Exit the sampling procedure: $\textsc{Break}$

Increment iteration: $k \leftarrow k + 1$

Return generated CTAS: return $\widehat{\cm{S}}$

Sequence Generation with

§ EXPERIMENTS

In this section, we present the experimental setup and the empirical results to validate the efficacy of . Through our experiments, we aim to answer the following research questions:

RQ1 What is the action-mark and time prediction performance of in comparison to the state-of-the-art baselines?

RQ2 How accurately and quickly can identify the goal of an activity sequence?

RQ3 How effectively can generate an action sequence?

§.§ Datasets

To evaluate , we need timestamped action sequences and their goals. Therefore, we derive CTAS from three activity modeling datasets sourced from different real-world applications – cooking, sports, and collective activity. The datasets vary significantly in terms of origin, sparsity, and sequence lengths. We highlight the details of each of these datasets below:

*  <cit.>. This dataset contains CTAS derived from 1712 videos of different people preparing breakfast. The actions in a CTAS and sequence goals can be classified into 48 and 9 classes, respectively. These actions are performed by 52 different individuals in 18 different kitchens.

*  <cit.>. A sports activity dataset that is designed for action recognition in videos. We derive the CTAS using 400 videos of individuals involved in different sports such as discus throw, baseball,  The actions and goals can be classified into 65 and 9 classes, respectively and on average, there are 10.5 action class labels per video.

*  <cit.>. This dataset comprises activity categories collected from 591 YouTube videos with a total of 49 action labels and 14 goals.

We highlight that in , many of the videos are shot by amateurs in many uncontrolled environments, the variances within the CTAS of the same goal are often large, and the lengths of CTAS vary and are often long and complex.

§.§ Baselines

We compare the action prediction performance of with the following state-of-the-art methods:

* NHP <cit.>: Models an MTPP using continuous-time LSTMs for capturing the temporal evolution of sequences.

* RMTPP <cit.>: A recurrent neural network that models time differences to learn a representation of past events.

* AVAE <cit.>: A variational autoencoder-based MTPP framework designed specifically for activities in a sequence.

* SAHP <cit.>: A self-attention model to learn the temporal dynamics using an aggregation of historical events.

* THP <cit.>: Extends the transformer model <cit.> to include the conditional intensity of event arrival and the inter-mark influences.

We omit comparison with other continuous-time models <cit.> as they have already been outperformed by these approaches.

§.§ Evaluation Criteria

Given the dataset $\cm{D}$ of $N$ action sequences, we split them into training and test sets based on the goal of the sequence. Specifically, for each goal $g \in \cm{G}$, we consider 80%  of the sequences as the training set and the other last 20% as the test set. We evaluate and all baselines on the test set in terms of (i) mean absolute error (MAE) of predicted times of action, and (ii) action prediction accuracy (APA) described as:

\begin{equation}
\mathrm{MAE} = \frac{1}{|\cm{S}|}\sum_{e_i\in \cm{S}}[|t_i-\widehat{t}_i|], \quad \mathrm{APA} = \frac{1}{|\cm{S}|}\sum_{e_i\in \cm{S}} \#(c_i=\widehat{c}_i),
\end{equation}

where, $\widehat{t_i}$ and $\widehat{c_i}$ are the predicted time and type the $i$-th action in test set. Moreover, we follow a similar protocol to evaluate the sequence generation ability of and other models. For goal prediction, we report the results in terms of accuracy (ratio) calculated across all sequences. We calculate confidence intervals across five independent runs.

§.§ Experimental Setup

System Configuration
All our experiments were done on a server running Ubuntu 16.04. CPU: Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz , RAM: 125GB and GPU: NVIDIA Tesla T4 16GB DDR6.

Parameter Settings
For our experiments, we set $D=16$, $\cm{M}=8$, $\gamma=0.9$ and weigh the margin loss $\cm{L}_m$ by 0.1. In addition, we set a $l_2$ regularizer over the parameters with coefficient value $0.001$.

Performance of all the methods in terms of action prediction accuracy (APA). Bold (underline) fonts indicate the best performer (baseline). Results marked $\dagger$ are statistically significant (i.e. two-sided Fisher's test with $p \le 0.1$) over the best baseline.

Dataset     3cAction Prediction Accuracy (APA)

NHP <cit.>     0.528$\pm$0.024     0.272$\pm$0.019     0.684$\pm$0.034

AVAE <cit.>     0.533$\pm$0.028     0.279$\pm$0.022     0.678$\pm$0.036

RMTPP <cit.>     0.542$\pm$0.022     0.274$\pm$0.017     0.683$\pm$0.034

SAHP <cit.>     0.547$\pm$0.031     0.287$\pm$0.023     0.688$\pm$0.042

THP <cit.>     0.559$\pm$0.028     0.305$\pm$0.018     0.693$\pm$0.038

-c     0.561$\pm$0.027     0.297$\pm$0.020     0.698$\pm$0.038

-t     0.579$\pm$0.025     0.306$\pm$0.018     0.722$\pm$0.035

0.583$\pm$0.027$\dagger$     0.316$\pm$0.019     0.728$\pm$0.037$\dagger$

Performance of all the methods in terms of mean absolute error (MAE).

Dataset     3cMean Absolute Error (MAE)

NHP <cit.>     0.411$\pm$0.019     0.017$\pm$0.002     0.796$\pm$0.045

AVAE <cit.>     0.417$\pm$0.021     0.018$\pm$0.002     0.803$\pm$0.049

RMTPP <cit.>     0.403$\pm$0.018     0.017$\pm$0.002     0.791$\pm$0.046

SAHP <cit.>     0.425$\pm$0.031     0.019$\pm$0.003     0.820$\pm$0.072

THP <cit.>     0.413$\pm$0.023     0.019$\pm$0.002     0.806$\pm$0.061
-c     0.415$\pm$0.027     0.015$\pm$0.002     0.774$\pm$0.054

-t     0.407$\pm$0.025     0.015$\pm$0.002     0.783$\pm$0.058

0.364$\pm$0.028$\dagger$     0.013$\pm$0.002$\dagger$     0.742$\pm$0.059$\dagger$

Real life true and predicted inter-arrival times $\Delta_{t,k}$ of different events $e_k$ for (a)  and (b)  datasets. The results show that the true arrival times match with the times predicted by .

Sequence goal prediction performance of , its variants – -m and -$\gamma$, and other baseline models. The results show that can effectively detect the CTAS goal even with smaller test sequences as input.

§.§ Action Prediction Performance

To address RQ1, we report on the performance of action prediction of different methods in terms of APA and MAE in Table <ref> and Table <ref>, respectively. In addition, we include two variants of – (i) -c, which represents our model without the goal-action hierarchy loss and cluster-based flows, and (ii) -t, which represents our model without cluster-based flows. From the results, we note the following:

* consistently yields the best prediction performance on all the datasets. In particular, it improves over the strongest baselines by 8-27% for time prediction and by 2-7% for action prediction. These results signify the drawbacks of using standard sequence approaches for modeling a temporal action sequence.

* RMTPP <cit.> is the second-best performer in terms of MAE of time prediction in almost all the datasets. We also note that for dataset, THP <cit.> outperforms RMTPP for action category prediction. However, still significantly outperforms these models across all metrics.

* Neural MTPP methods that deploy a self-attention for modeling the distribution of action – namely THP, SAHP, and , achieve better performance in terms of category prediction.

* Despite AVAE <cit.> being a sequence model designed specifically for activity sequences, other neural methods that incorporate complex structures using self-attention or normalizing flows easily outperform it.

To sum up, our empirical analysis suggests that can better model the underlying dynamics of a CTAS as compared to all other baseline models. Moreover, the performance gain over -c and -t highlights the need for modeling action hierarchy and cluster-based flows.

Qualitative Assessment
We also perform a qualitative analysis to highlight the ability of to model the inter-arrival times for action prediction. Specifically, we plot the actual inter-action time differences and the time-difference predicted by in Figure <ref> for  and  datasets. From the results, we note that the predicted inter-arrival times closely match with the true inter-arrival times, and is even able to capture large time differences (peaks).

§.§ Goal Prediction Performance

To address RQ2, we evaluate the goal detection performance of along with other baselines. To highlight the early goal detection ability of our model,  we report the results across different variants of the test set, , with the initial 30% and 60% of the actions in the CTAS in terms of goal prediction accuracy (GPA). In addition, we introduce two novel baselines, LSTM-c, and LSTM-t, that detect the CTAS goal using just the types and the times of actions, respectively. We also compare with the two best-performing MTPP baselines – RMTPP and THP which we extend for the task of goal detection by a $k$-means clustering algorithm. In detail, we obtain the sequence embedding, say $\bs{s}_k$ using the MTPP models and then cluster them into $|\cm{G}|$ clusters based on their cosine similarities and perform a maximum polling across each cluster, , predict the most common goal for each cluster as the goal for all CTAS in the same cluster. In addition, we introduce two new variants of our model to analyze the benefits of early goal detection procedures in – (i) -m, which represents our model without the goal-based margin loss given in Eqn. <ref> and (ii) -$\gamma$, is our model without the discount-factor weight in Eqn. <ref>. We also report the results for the complete model .

The results for goal detection in Figure <ref>, show that the complete design of achieves the best performance among all other models. We also note that the performance of MTPP-based models deteriorates significantly for this new task which shows the unilateral nature of the prediction prowess of MTPP models, unlike . Interestingly, the variant of without the margin loss -m performs poorly as compared to the one without the discount factor, -$\gamma$. This could be attributed to better convergence guarantees with a margin-based loss over the latter. Finally, we observe that standard LSTM models are easily outperformed by our model, thus reinforcing the need for joint training of types and action times.

Sequence Generation results for and other baselines in terms of APA for action prediction.

Sequence Generation results for and other baselines in terms of MAE for time prediction.

§.§ Sequence Generation Performance

To address RQ3, we evaluate the sequence generation ability of . Specifically, we generate all the sequences in the test set by giving the true goal of the CTAS and the first action as input to the procedure described in Section <ref>. However, there may be differences in the lengths of the generated and true sequences, , the length of generated sequences is usually greater than the true CTAS. Therefore, we compare the actions in the true sequence with the initial $|\cm{S}|$ generated actions. Such an evaluation procedure provides us the flexibility of comparing with other MTPP models such as RMTPP <cit.> and THP <cit.>. As these models cannot be used for end-to-end sequence generation, we alter their underlying model for forecasting future actions given the first action and then iteratively update and sample from the MTPP parameters. We report the results in terms of APA and MAE for action and time prediction in Figure <ref> and Figure <ref>, respectively. The results show that can better capture the generative dynamics of a CTAS in comparison to other MTPP models. We also note that the prediction performance deteriorates significantly in comparison to the results given in Tables <ref> and  <ref>. This could be attributed to the error that gets compounded in further predictions made by the model. Interestingly, the performance advantage that has over THP and RMTPP is further widened during sequence generation.

Length Comparison
Here, we report the results for the length comparison of the generated sequence and the true sequence. Specifically, we identify the count of instances where was able to effectively capture the generative mechanism of a sequence as:

\begin{equation}
\mathrm{CL} = \frac{1}{N}\sum_{\forall \cm{S}} \#(|\cm{S}|=|\widehat{\cm{S}}|),
\end{equation}

where CL denotes the Correct-Length ratio with values $0.21$, $0.11$, and $0.16$ for datasets , , and  respectively. On a coarse level, these results might seem substandard; however, given the difficulty associated with the problem of sequence generation using just the CTAS goal, we believe these values are satisfactory. Moreover, we believe that the sequence generation procedure of opens up new frontiers for generating action sequences.

Scalability For all datasets, the run-times for training are within 1 hour and thus are within the practical range for deployment in real-world scenarios. These running times further reinforce our design choice of using a neural MTPP due to their faster learning and closed-form sampling <cit.>.

§ CONCLUSION

Standard deep-learning models are not designed for modeling sequences of actions localized in continuous time. However, neural MTPP models overcome this drawback but have limited ability to model the events performed by a human. Therefore, we developed a novel point process flow-based architecture called for modeling the dynamics of a CTAS. solves the problems associated with action prediction and goal prediction, and for the first time, we extend MTPP for end-to-end CTAS generation. Our experiments on three large-scale, diverse datasets reveal that can significantly improve over the state-of-the-art baselines across all metrics. Moreover, the results also reinforce the novel ability of to generate a CTAS. We hope that such an application will open many horizons for using MTPP in a wide range of tasks.

CHAPTER: CONCLUSION AND FUTURE WORK

To conclude, traditional recommender systems have limited ability to model user-item interactions with changing dynamics. In this thesis, we present the research directions, possible data-related problems, and solutions for learning recommender systems that utilize user-item interactions in the form of continuous-time event sequences (CTES). This thesis has been divided into three parts based on the issues addressed and the type of solutions proposed. We also identify the sequence modeling prowess of our proposed models and design solutions for applications beyond recommender systems. Here, we summarize the contribution of each part of this thesis:

In Chapter <ref>, we address the problem of modeling missing events in temporal sequences. The presence of missing events can significantly deteriorate the quality of the CTES data and, consecutively, the performance of recommender systems trained on these datasets. The traditional sequence models assume that the underlying sequence is complete – an ideal setting. Thus, we proposed , a novel MTPP model that learns the generative processes of observed events and missing events with missing events as latent random variables. Then, we devise an unsupervised training method to jointly learn the parameters of the observed and missing MTPP models using variational inference. can effectively impute the missing data among the observed events, which in turn enhances its predictive prowess. Later, its enhanced version, , can impute and identify the optimal position of missing events in a sequence. However, one unaddressed aspect of the missing data problem is partially missing events , events with either the time or mark missing. This is a challenging problem, as standard MTPP models are not designed to handle such sequences or functions in the absence of event times. In addition, the constrained optimization procedure in can be improved by using Lagrangian multipliers. This would prevent the two-step procedure mentioned in while simultaneously facilitating faster convergence.

In the second part of the thesis, we address the problems associated with designing better sequence modeling frameworks for the application of spatial recommendations. Specifically, given the continuous-time mobility records of a user, we use external data or features to overcome the data scarcity in the region and better recommend better POI candidates to a user in the spatial network. This part is divided into three chapters based on the three different real-world applications: (i) top-$k$ POI recommendation; (ii) sequential POI recommendation and time prediction; and (iii) using smartphone usage to predict the mobility of a user.

In Chapter <ref>, we design solutions for the top-$k$ POI recommendation and propose (Automated cross Location-network Transfer Learning), a graph neural network-based framework that transfers mobility knowledge across regions via – (i) a novel meta-learning procedure derived from spatial as well as a social network, and (ii) a lightweight unsupervised cluster-based transfer technique. We also address the problems associated with an extremely data-scarce region and devise a suitable cluster-based alignment loss that enforces similar embeddings for communities of users and locations with similar dynamics. In future work, we plan to modify the transfer procedure of to incorporate novel meta-learning approaches, namely ProtoMAML <cit.> and Reptile <cit.>. Additionally, we plan to experiment with approaches <cit.> that automatically identify the number of clusters within a region while simultaneously maintaining the scalability of our model.

In Chapter <ref>, we design solutions to overcome the problems due to data scarcity for developing sequential POI recommendation frameworks. Thus, we propose (Reusable Flows for Mobility Data), a point process framework that learns the dynamics of user-specific check-in sequences in a region using normalizing flows to learn the inter-check-in time and geo-distributions. achieved better performance in data-scarce regions without any prerequisite of overlapping users. In future work, we plan to explore the relationship between MTPP-based transfer for product recommendation and incorporate complex transfer techniques such as meta-learning <cit.>.

In Chapter <ref>, we propose (Relative position Vector for App-based Mobility Prediction. This sequential POI recommendation approach uses smartphone app-usage logs to identify the mobility preferences of a user while simultaneously maintaining the user's privacy. Inspired by the success of relative positional encodings and self-attention models, uses relative and absolute positional encodings determined by the inter-variances in the smartphone app category, POI category, and time over the in the sequence. Through , we aim to understand the relationship between the smartphone usage of users and their mobility preferences. A drawback of the current formulation is that it requires the entire dataset to train its parameters. However, modern privacy-conscious techniques use a federated learning approach to train the model parameters with decentralized data. In future work, we plan to expand using such an efficient architecture.

In the third part, we highlight that the sequence modeling ability of the proposed models can have applications beyond recommender systems. Thus, we extend these models for two novel applications – (i) efficient retrieval of event sequences; and (ii) human activity prediction. In Chapter <ref>, we propose , a novel MTPP model to retrieve and rank a relevant set of continuous-time event sequences for a given query sequence from a large corpus of sequences. has many advantages over the previous models, such as a trainable unwarping function that makes it easier to compare query-corpus sequence pairs, especially when they have individually different attributes. Moreover, it has a learnable hashing for efficient retrieval of sequences with millions of events. Currently, in high-impact applications like healthcare, our method requires additional care since an incorrect prediction made by our model would have an adverse impact. In the end, one may consider a human-in-loop retrieval system that will mitigate such risk via human intervention. Moreover, event sequences from some domains, , mobility records, can contain user-specific data and their use may lead to privacy violations. To that aim, it would be interesting to consider designing a privacy-preserving retrieval system for continuous-time event sequences. Empirically we show that our hash-code-based retrieval is Pareto-efficient, offering a sweet spot in trading off the computational cost and the retrieval performance.

In Chapter <ref>, we address the problem of modeling action sequences and first highlight the dissimilarities between standard time series and human-performed action sequences. To efficiently model these action sequences, we propose (Point Process flows for Activity Sequences), a neural MTPP framework for modeling the continuous-time distribution of actions in activity sequences while simultaneously addressing three real-world applications – next action prediction, sequence-goal prediction, and end-to-end sequence generation. brings forward the first-of-its-kind application of MTPP models via sequence generation, , given the goal of an action sequence, it can generate a sequence with actions towards achieving that particular goal. In future work, we plan to incorporate a generative adversarial network <cit.> with action sampling and train it simultaneously with the MTPP.

Therefore, this thesis addresses some critical limitations of the current approaches for modeling continuous-time event sequences. To achieve this, we proposed robust and scalable neural network-based models that show their prowess in their respective applications. In addition, we design MTPP frameworks for two novel and high-impact applications. However, the research directions addressed in this have led to several open questions and future works. Here, we list out a few of them that were unaddressed in this thesis and, to the best of our knowledge, have been overlooked by the past literature as well.

* Evaluating Time Prediction Performance. A significant advantage of the neural MTPP over traditional sequence modeling frameworks is their ability to effectively understand the time of a future event. To evaluate the time-prediction performance of an MTPP model, the current procedures utilize one of the two popular metrics – mean absolute error (MAE) or root mean squared error (RMSE) <cit.>. However, both of these metrics evaluate the time-prediction ability in an event-wise setting, , perform a one-vs-one matching between the predicted and the actual data and then take mean overall events. This metric provides limited insights into the generative ability of MTPP models and the ability to results for the entire sequence. An interesting future direction for this thesis will be to utilize sequence-to-sequence comparison metrics such as dynamic time warping (DTW) to evaluate the prediction performance, or if possible, use a trainable DTW <cit.> as a loss in the optimization procedure. Such an optimization procedure can give deeper insights into the generative and long-tail forecasting ability of MTPP models, which can be further used to design better MTPP frameworks.

* Repetitiveness in Recommendations. Recent research has shown that the purchase records of users on an e-commerce platform may have repetitive patterns, , there is a temporal dependency between the consecutive purchase of similar items <cit.>. Incorporating this dependency into a continuous-time model has been studied with traditional MTPP models. However, there has been limited research in exploring periodicity in a neural MTPP model. This is a challenging task as the neural MTPP models do not have an explicit influence function, and these influences are approximated by a neural layer. Thus, an interesting future work could be to incorporate the repetitive purchasing nature of a user into the mathematical framework of a neural MTPP. A possible solution could be to optimize the ability of the model to predict similar purchases in the next time window, , the likelihood that a user will re-buy the same product in the near future.

* Learning Neural MTPP at Scale. A drawback of using MTPP for modeling the dynamics of a CTES is their larger inference and sampling times for long sequences. This problem arises due to the inherently sequential nature of MTPP, which restricts their scalability even in the presence of highly-parallel modern hardware. However, recent research has shown that the conditional intensity function of an MTPP can be replaced by a normalizing flow based on triangular maps that allows parallel sampling and likelihood computation <cit.>. In a similar context, researchers have also decoupled the neural MTPP to gain better scalability, , rather than a joint neural MTPP, they use deep recurrent neural networks to capture complex temporal dependency patterns, and the self-excitation dynamics are modeled with a traditional Hawkes processes <cit.>. These techniques can be used to design scalable MTPP models, however, a detailed analysis of how these additions result in the overall improvement in scalability in the context of recommender systems has not been performed in the past. Thus, another interesting future work for this thesis will be a detailed study that compares the training and inference times of MTPP models while plugging-in several heuristics that will be a breakthrough in scaling these techniques and their applicability in large-scale recommender systems.

* Human in the Loop. Lastly, we highlight the limited ability of sequence modeling frameworks to incorporate feedback given by users along with the training data. Incorporating additional feedback given by a user, such as a ranked list of desired items, is necessary for modern recommender systems as recent research has shown that the recommendations produced by a majority of ML models do not correlate with actual human preferences <cit.>. This is a major drawback of the current models and highlights their limited practicability even when they consist of sophisticated ML techniques. Thus, a crucial problem that needs to be addressed will be training neural models over CTES data with additional aids from other domains, such as crowd-sourcing, with the goal of incorporating real human feedback on the ranked recommendations.

To summarize, in this thesis, we have designed solutions for a few real-world problems associated with recommender systems, and have discussed some open questions and directions for improvements.

CHAPTER: LIST OF PUBLICATIONS

tocchapterList of Publications
Here we list out all first-author articles accepted/published during the Ph.D tenure.

Publications based on this Thesis

* Vinayak Gupta, Abir De, Sourangshu Bhattacharya, and Srikanta Bedathur. “Learning Temporal Point Processes with Intermittent Observations”, In Proc. of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.

* Vinayak Gupta and Srikanta Bedathur. “Region Invariant Normalizing Flows for Mobility Transfer”, In Proc. of the 30th ACM Intl. Conference on Information and Knowledge Management (CIKM), 2021.

* Vinayak Gupta, Abir De, and Srikanta Bedathur. “Learning Temporal Point Processes for Efficient Retrieval of Continuous Time Event Sequences”, In Proc. of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022.

* Vinayak Gupta and Srikanta Bedathur. “ProActive: Self-Attentive Temporal Point Process Flows for Activity Sequences”, In Proc. of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2022.

* Vinayak Gupta and Srikanta Bedathur. “Doing More with Less: Overcoming Data Scarcity for POI Recommendation via Cross-Region Transfer”, ACM Transactions on Intelligent Systems and Technology (ACM TIST), 2022.

* Vinayak Gupta, Abir De, Sourangshu Bhattacharya, and Srikanta Bedathur. “Modeling Continuous Time Sequences with Intermittent Observations using Marked Temporal Point Processes”, ACM Transactions on Intelligent Systems and Technology (ACM TIST), 2022.

* Vinayak Gupta and Srikanta Bedathur. “Modeling Spatial Trajectories using Coarse-Grained Smartphone Logs”, IEEE Transactions on Big Data (IEEE TBD), 2022.

Other Publications

* Ankita Likhyani*, Vinayak Gupta*, P. K. Srijith, Deepak, and Srikanta Bedathur. “Modeling Implicit Communities from Geo-tagged Event Traces using Spatio-Temporal Point Processes”, In Proc. of the 21st International Conference on Web Information Systems Engineering (WISE), 2020.

This work received the Outstanding Doctoral Paper award at

The First International Conference on AI-ML-Systems 2021.

CHAPTER: BIOGRAPHY

Vinayak Gupta is a Ph.D. student at the Department of Computer Science and Engineering, Indian Institute of Technology (IIT) Delhi. He obtained a Bachelors' degree in Computer Science and Engineering from the Indian Institute of Information Technology (IIIT) Jabalpur. His research interests are in data mining. Specifically, his research addresses the problems related to – limited training data, asynchronous data collection in sequences, event-imputation, end-to-end sequence generation, activity recognition, and spatial recommendation for users – in temporal sequences using point processes and graph neural networks.