Explaining Point Processes by Learning Interpretable Temporal Logic Rules

Shuang Li, Mingquan Feng, Lu Wang, Abdelmajid Essofi, Yufeng Cao, Junchi Yan, Le SongICLR 2022 · OpenReview

Modern machine learning excels at predicting when the next event in a sequence will happen, but it usually fails to explain why. This paper introduces a principled method to make sense of "event sequences"—data points like medical alerts or crime reports that happen at irregular intervals. By teaching a model to discover human-readable logic rules that govern these events, the authors bridge the gap between high predictive accuracy and essential interpretability.

The Challenge of Modeling Event Sequences

In many fields, data arrives as a stream of events, such as a patient’s heart rate spiking followed by the administration of medication. To model this, researchers use Temporal Point Processes (TPPs), which calculate the "intensity" or instantaneous rate of an event occurring.

However, existing approaches face a major trade-off:

  1. Deep Learning TPPs (like Neural Hawkes Processes) are highly accurate but act as "black boxes." They cannot tell a doctor why a patient is at risk.
  2. Logic-based models are interpretable but often too rigid to handle the noise and timing variations inherent in real-world data.

The core challenge is automatically discovering the underlying "rules of the game" from raw data without requiring a human expert to hard-code them.

The TELLER Framework

To address this, the authors propose TELLER (TEmporal Logic rule LearnER). TELLER treats logic rules as "features" that drive the intensity of a point process, combining the mathematical framework of TPPs with interpretable logic.

Overview of the TELLER framework, alternating between rule discovery (Subproblem) and rule evaluation (Master Problem).

The Core Algorithm: Branch-and-Price

Because the space of all possible logic rules is infinitely large, testing them all is impossible. TELLER uses a "branch-and-price" approach—a type of column generation—that alternates between two stages:

  • The Master Problem (Evaluation): Given a small set of current rules, the algorithm optimizes their weights to best fit the observed data using Maximum Likelihood Estimation (MLE). The authors prove this optimization is convex, meaning the model can reliably find the best weights.
  • The Subproblem (Discovery): The algorithm searches for a new rule that, if added, would most improve the model's accuracy (calculated via the "dual price").

Temporal Logic and Rule Generation

The rules generated by TELLER utilize Allen’s Interval Algebra, which describes how two time-intervals relate (e.g., "Event A happens before Event B," or "Event A overlaps with Event B"). This allows the model to capture complex causal relationships rather than just simple correlations.

To make this search efficient, TELLER leverages the Heredity Principle: if a complex rule (e.g., $A \land B \land C \to Y$) is important, its simpler parts (e.g., $A \to Y$) likely show some statistical signal. This allows TELLER to "grow" rules progressively rather than searching blindly. Furthermore, instead of treating logic as a binary "True/False" switch, the authors use "softened" versions of step functions, allowing the model to handle the inherent fuzziness of time in real-world events.

Experimental Results

The model was evaluated on three types of data: synthetic datasets, MIMIC-III (healthcare records of over 4,000 sepsis patients), and Boston Crime Data (2015–2021).

Superior Accuracy and Human-in-the-Loop

On the MIMIC-III dataset, the goal was to predict "Low Urine" output (a sign of kidney failure) and patient survival. TELLER outperformed all baselines, including deep learning models like Transformer Hawkes Processes, in predicting both the timing of symptoms and patient survival. For survival prediction, it achieved 93% accuracy, compared to the next best at 88%.

Crucially, in the healthcare experiment, doctors reviewed the learned rules. They found that the model discovered medically sound patterns (e.g., the relationship between blood pressure and vasopressors) and were able to refine the rules to improve performance further.

Efficiency and Rule Recovery

In synthetic tests, TELLER consistently recovered the exact hidden rules as the sample size increased, demonstrating high "Jaccard similarity" to the ground truth.

Training process showing log-likelihood improvements as TELLER discovers new temporal logic rules.

Compared to a "brute-force" search of all possible rules, TELLER found the correct rules significantly faster. As shown in the training process, there are clear "jumps" in the model's log-likelihood whenever a meaningful new rule is discovered and added to the set.

Limitations and Future Work

While highly effective, TELLER does have limitations:

  • Search Depth: The algorithm struggles with extremely long, complex rules (e.g., rules involving 5+ different predicates) because the search space grows exponentially.
  • Tailing-off Effect: Like many column generation algorithms, TELLER can slow down as it approaches the absolute mathematical optimum.

Looking forward, the authors suggest applying TELLER to other high-stakes domains like autonomous driving, where understanding the "why" behind a system's decision is a critical safety requirement.

Reference: Li, S., Feng, M., et al. (2022). Explaining Point Processes by Learning Interpretable Temporal Logic Rules. ICLR 2022.

Summary updated

Abstract

We propose a principled method to learn a set of human-readable logic rules to explain temporal point processes. We assume that the generative mechanisms underlying the temporal point processes are governed by a set of first-order temporal logic rules, as a compact representation of domain knowledge. Our method formulates the rule discovery process from noisy event data as a maximum likelihood problem, and designs an efficient and tractable branch-and-price algorithm to progressively search for new rules and expand existing rules. The proposed algorithm alternates between the rule generation stage and the rule evaluation stage, and uncovers the most important collection of logic rules within a fixed time limit for both synthetic and real event data. In a real healthcare application, we also had human experts (i.e., doctors) verify the learned temporal logic rules and provide further improvements. These expert-revised interpretable rules lead to a point process model which outperforms previous state-of-the-arts for symptom prediction, both in their occurrence times and types.
BibTeX
@inproceedings{li2022explaining,
  author = {Shuang Li and Mingquan Feng and Lu Wang and Abdelmajid Essofi and Yufeng Cao and Junchi Yan and Le Song},
  title = {{Explaining Point Processes by Learning Interpretable Temporal Logic Rules}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=P07dq7iSAGr},
}
Figure