Learning to Select Exogenous Events for Marked Temporal Point Process

Ping Zhang, Rishabh K Iyer, Ashish V. Tendulkar, Gaurav Aggarwal, Abir DeNeurIPS 2021 · OpenReview

Overview

Researchers have developed TPP-SELECT, a novel framework designed to automatically distinguish between "endogenous" and "exogenous" events in a stream of unlabeled data. By proving that this selection process follows a mathematical property known as $\alpha$-submodularity, the authors created an efficient algorithm that significantly improves the predictive accuracy of temporal models.

The Challenge of Unlabeled Temporal Data

Marked Temporal Point Processes (MTPPs) are the standard mathematical tools for modeling events that unfold over time, such as social media posts, financial trades, or disease outbreaks. In these dynamic systems, events generally fall into two distinct categories:

  1. Endogenous Events: Internal "ripples" where one event directly triggers another (e.g., a viral thread on social media).
  2. Exogenous Events: External "shocks" driven by outside forces (e.g., a sudden breaking news story that drives traffic).

The primary challenge is that in real-world datasets, events do not come neatly labeled as "internal" or "external." Most existing models simply mash these two types together using a superposition approach, assuming every event is equally likely to be either. This "one-size-fits-all" strategy often leads to blurry models that fail to capture the true underlying dynamics of the system. The authors set out to find a way to accurately filter out the exogenous events, allowing the underlying model to train much more effectively on the endogenous ones.

Methods: A Submodular Approach

The authors treat the problem as a joint optimization task: they aim to find the best set of exogenous events ($S$) and the optimal model parameters ($\theta$) simultaneously.

  • The Computational Hurdle: They first prove that this joint selection problem is NP-hard, meaning a brute-force approach to finding the perfect solution is impossible for large datasets.
  • The TPP-SELECT Solution: To bypass this complexity, they prove a vital theoretical property: the objective function is monotone and $\alpha$-submodular. In practical terms, this means that while the problem is computationally hard, a "greedy" approach—picking the best event one by one—is mathematically guaranteed to get very close to the optimal solution.
Progression of the greedy selection algorithm over iterations
  • Stochastic Greedy Algorithm: The framework utilizes a stochastic greedy algorithm that samples a subset of events in each step rather than evaluating the entire dataset. This makes the process computationally efficient enough for real-world applications.
  • Robustness: Crucially, the authors provide a mathematical guarantee that the algorithm remains effective even if the training process yields slightly imperfect estimates of the model parameters.

Datasets and Key Insights

The researchers evaluated TPP-SELECT using both controlled simulations and real-world data streams. Synthetic data was generated using Ogata’s thinning algorithm to provide a "ground truth" where the labels were known. Real-world datasets included social media/political event data (Club & Election), legal and media event streams (Series & Verdict), and financial/transactional data (BookOrder).

Key Insights: * The Submodularity Bridge: The most significant theoretical contribution of this paper is connecting MTPPs to the world of submodular optimization. Proving that the likelihood function of a point process behaves like a submodular set function opens up a vast toolbox of efficient algorithms for future researchers. * Filtering vs. Superposition: The paper demonstrates that it is far better to identify and separate exogenous events than to simply model them as an additive constant. By filtering out the "noise" of external shocks, the model learns the "signal" of the internal dynamics much more clearly. * The "Sweet Spot" for $k$: The results show that the number of events chosen to be labeled as exogenous ($k$) matters heavily. If $k$ is too small, noise remains in the data; if $k$ is too large, valuable signal is discarded. There is a clear "sweet spot" where model performance peaks.

Key Results

The empirical results demonstrate the clear superiority of the TPP-SELECT framework over existing methods.

  • Accuracy: On synthetic data, TPP-SELECT achieved a classification accuracy of 0.806, significantly outperforming standard baselines like K-means (0.620) or Expectation-Maximization (0.554).
Accuracy comparison of TPP-Select against baseline methods
  • Better Predictions: When tested on real-world data, TPP-SELECT consistently reduced the Mean Absolute Error (MAE) for predicting when the next event would happen, as well as the Misclassification Error (MPE) for predicting what the event would be (the "mark").
  • Versatility: The method proved highly effective for both simple linear models (Hawkes processes) and complex nonlinear models (like Recurrent Marked Temporal Point Processes).

Limitations and Future Work

While TPP-SELECT is a significant step forward, the authors note a few areas for future exploration. The current framework focuses on univariate processes, and extending this to multivariate processes (where different types of events interact) would be highly valuable. Additionally, in social media contexts, identifying which users are "exogenous" (influenced by outside sources) could potentially lead to privacy leaks, suggesting a need for a "differentially private" framework in the future. Finally, adapting TPP-SELECT for "online" settings—where it can select exogenous events from a live, continuous stream rather than a fixed batch—remains a promising direction for future research.

Summary updated

Abstract

Marked temporal point processes (MTPPs) have emerged as a powerful modeling tool for a wide variety of applications which are characterized using discrete events localized in continuous time. In this context, the events are of two types endogenous events which occur due to the influence of the previous events and exogenous events which occur due to the effect of the externalities. However, in practice, the events do not come with endogenous or exogenous labels. To this end, our goal in this paper is to identify the set of exogenous events from a set of unlabelled events. To do so, we first formulate the parameter estimation problem in conjunction with exogenous event set selection problem and show that this problem is NP hard. Next, we prove that the underlying objective is a monotone and \alpha-submodular set function, with respect to the candidate set of exogenous events. Such a characterization subsequently allows us to use a stochastic greedy algorithm which was originally proposed in~\cite{greedy}for submodular maximization. However, we show that it also admits an approximation guarantee for maximizing \alpha-submodular set function, even when the learning algorithm provides an imperfect estimates of the trained parameters. Finally, our experiments with synthetic and real data show that our method performs better than the existing approaches built upon superposition of endogenous and exogenous MTPPs.
BibTeX
@inproceedings{zhang2021learning,
  author = {Ping Zhang and Rishabh K Iyer and Ashish V. Tendulkar and Gaurav Aggarwal and Abir De},
  title = {{Learning to Select Exogenous Events for Marked Temporal Point Process}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=MckiHYXsBT},
}
Figure