CT-NOR: Representing and Reasoning About Events in Continuous Time

Aleksandr Simma, Moisés Goldszmidt, John MacCormick, Paul Barham, Richard Black, Rebecca Isaacs, Richard MortierUAI 2008

TL;DR

This paper introduces CT-NOR, a novel probabilistic model for understanding relationships between events occurring over continuous time, particularly useful in complex networked systems. By leveraging Poisson processes and a flexible delay function, CT-NOR enables efficient discovery of dependencies and detection of behavioral changes, outperforming existing methods on real-world network data.

What Problem Does This Paper Address?

In large-scale networked and distributed systems, understanding how different components (hosts, services) depend on each other is crucial for monitoring, troubleshooting, and diagnosis. However, these dependencies are often undocumented, complex, and dynamic. Existing methods for discovering these relationships can be computationally expensive or struggle with the continuous-time nature of event occurrences and the bursty traffic patterns common in networks. This paper aims to bridge this gap by providing a robust and efficient probabilistic framework for modeling and inferring these time-dependent relationships.

Methods

The core of the paper is the Continuous Time Noisy Or (CT-NOR) model. This model represents events as occurring within Poisson processes. The key innovation lies in how it models the interaction between input and output events: the intensity of the output Poisson process is modulated by a parameterized function that accounts for the time delay between an input event and a potential output event. This delay function allows for encoding domain knowledge about expected response times.

To fit the model parameters (weights of dependencies and parameters of the delay function), the authors employ the Expectation-Maximization (EM) algorithm. For inference tasks like dependency discovery and change-point detection, they utilize statistical hypothesis testing, specifically the log-likelihood ratio test. A significant contribution is the formalization of the relationship between CT-NOR and the discrete-time Noisy-Or (NOR) gate, showing CT-NOR as a continuous-time extension. They also propose an efficient bounding method for the log-likelihood ratio test to speed up computation.

Datasets

The paper evaluates its approach using two types of data:

  • Synthetic Data: Generated according to specific instantiations of the CT-NOR model to test the algorithms' performance under controlled conditions, particularly for dependency discovery and change-point detection.
  • Real-World Network Trace Data: A subset of a large enterprise network trace (approximately 13 billion packets over 3.5 weeks) from Microsoft Research Cambridge. Specifically, 24 hours of HTTP traffic data was used, with ground truth for dependencies and change points manually extracted through deep inspection of packets.

Key Insights and Ideas

  • Continuous Time Modeling is Crucial: The paper highlights that simply discretizing time can lead to loss of information and inaccurate dependency inference, especially in bursty network traffic. CT-NOR's continuous-time approach is a significant advantage.
  • Delay Matters: The explicit modeling of time delays between input and output events is a key differentiator. This allows for capturing nuanced dependencies that are not just about co-occurrence but also about the timing of responses.
  • CT-NOR as a Continuous-Time NOR Gate: Formalizing the link to the well-established NOR gate provides a theoretical foundation and allows leveraging existing insights from discrete graphical models. It also suggests that CT-NOR can handle more complex dependencies than traditional NOR gates.
  • Efficient Inference is Achievable: The development of an EM algorithm and a bounded log-likelihood ratio test demonstrates that complex probabilistic models can be fitted and used for inference on large datasets efficiently.
  • Domain Knowledge Integration: The parameterized delay function is a powerful mechanism for incorporating expert knowledge about system behavior, complementing data-driven learning.

Key Results

  • Dependency Discovery: CT-NOR successfully captures 85% of true correlations with a 1% false positive rate on real network data. It detects 95% of true correlations at a 10% false positive rate. The model significantly outperforms simpler "standard co-occurrence" and "unique input packet" heuristics.
  • Change-Point Detection: The algorithm produces well-calibrated p-values for null hypotheses (no change) and effectively identifies significant changes in event relationships, demonstrating high power for detecting alterations in system behavior.
  • Computational Efficiency: The bounded log-likelihood ratio test for dependency discovery can compute results for an hour of traffic in 7 seconds, compared to 86 seconds for exact computations, making it practical for real-time monitoring.

Limitations and Future Work

  • Ground Truth Generation: The authors acknowledge that generating ground truth for real-world data is labor-intensive and often requires manual inspection, which can be a bottleneck.
  • Ignoring Global Structure: The current approach focuses on local parent-child relationships. The authors suggest that future work could incorporate global structure to mitigate spurious causal dependencies.
  • Bayesian Framework: They plan to explore recasting the fitting and inference procedures within a Bayesian framework to incorporate priors, which could improve accuracy, especially for channels with varying event rates.
  • False Discovery Rate Control: Incorporating more sophisticated False Discovery Rate (FDR) calculations is a key area for future work to accurately estimate false positives, especially when ground truth is unavailable.
  • Application to Other Domains: The authors express interest in applying the model to other complex systems, such as biological networks (e.g., neurons communicating via electrical spikes).

Summary updated

BibTeX
@inproceedings{simma2008ct,
  author = {Aleksandr Simma and Moisés Goldszmidt and John MacCormick and Paul Barham and Richard Black and Rebecca Isaacs and Richard Mortier},
  title = {{CT-NOR: Representing and Reasoning About Events in Continuous Time}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure