Auxiliary Gibbs Sampling for Inference in Piecewise-Constant Conditional Intensity Models

Zhen Qin, Christian R. SheltonUAI 2015 · OpenReview

Introduction

In many domains, data is best represented as a continuous-time stream of events, such as server logs, social media interactions, or medical records. Piecewise-Constant Conditional Intensity Models (PCIMs) are a powerful class of models for such data. Unlike simpler Markovian models, PCIMs allow the likelihood of an event to depend on the entire history of the stream, capturing complex temporal dependencies.

However, while PCIMs are efficient to learn from complete datasets, they have historically lacked a general inference algorithm for handling missing data or unobserved intervals. This paper introduces ThinnedGibbs, the first general inference algorithm for PCIMs, enabling complex query answering and model learning from incomplete observations.

Piecewise-Constant Conditional Intensity Models

A PCIM defines the conditional intensity of each event type using a decision tree. Each node in the tree tests a property of the history (e.g., "Were there at least $n$ events of type $A$ in the last $t$ seconds?"), and the leaves provide the constant intensity $\lambda$ for that specific historical context.

PCIMs use decision trees to determine the event intensity $\lambda$ based on historical context.

The ThinnedGibbs Algorithm

The core challenge in PCIM inference is the continuous-time nature of the problem and the potential for "path explosion" when sampling trajectories. ThinnedGibbs addresses these through three key innovations:

  1. Thinning with Virtual Events: Following the thinning method of Lewis and Shedler, the algorithm introduces "virtual events" at a constant high rate $\lambda^*$. These virtual events are then probabilistically "thinned" (kept or dropped) based on the actual model intensity. This transforms the continuous-time problem into a discrete-time binary choice problem.
  2. Adaptive Rates: To improve efficiency, the algorithm uses the PCIM’s decision-tree structure to calculate an adaptive rate $\lambda^*$ that changes over time, rather than a single global maximum. This minimizes the number of unnecessary virtual events.
  3. Efficient State-Vector Representation: Standard sampling often suffers from exponential complexity. ThinnedGibbs identifies which parts of the history are relevant to the PCIM's tests and merges similar trajectories. This reduces the complexity from exponential to linear in most practical scenarios.
ThinnedGibbs uses virtual events and merges trajectories to maintain linear complexity.

Experimental Evaluation

The authors verified ThinnedGibbs using several complex datasets:

  • Ising Model Toroid Network: Used to compare ThinnedGibbs against state-of-the-art Markovian samplers.
  • Synthetic Non-Markovian PCIMs: Tested the algorithm's unique ability to handle complex, non-Markovian dynamics.
  • Partially Observed Event Streams: Demonstrated the algorithm's performance in Expectation-Maximization (EM) learning tasks where intervals of data were hidden.

The results show that ThinnedGibbs successfully converges to the true distribution. In parameter estimation tasks, models learned via ThinnedGibbs on partial data achieved significantly higher log-likelihood on test data compared to naive baselines. Furthermore, the state-vector representation effectively kept sampling complexity linear.

Conclusion

ThinnedGibbs provides a robust framework for inference in PCIMs, generalizing existing methods for models like Continuous Time Bayesian Networks. While the current framework requires piecewise-constant intensities, it opens the door for sophisticated modeling of event streams with missing data. Future work may explore extending these techniques to more general, continuously changing rate functions and further optimizing for high-frequency real-world datasets.

Summary updated

BibTeX
@inproceedings{qin2015auxiliary,
  author = {Zhen Qin and Christian R. Shelton},
  title = {{Auxiliary Gibbs Sampling for Inference in Piecewise-Constant Conditional Intensity Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=Y3XGv6u5kf},
}
Figure