📊 statistics

Multiple change-point detection for Poisson point processes

This paper proposes a minimum contrast estimator combined with a cross-validation procedure for detecting multiple offline change-points in inhomogeneous and marked Poisson processes, including self-exciting ones, and demonstrates its effectiveness through simulations and real data via an R package implementation.

Original authors: C. Dion-Blanc, D. Hawat, E. Lebarbier, S. Robin

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: C. Dion-Blanc, D. Hawat, E. Lebarbier, S. Robin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are listening to a radio station that plays music. Sometimes, the DJ changes the genre: first it's jazz, then rock, then classical, then back to jazz. Your goal is to listen to the whole recording and figure out exactly when those genre switches happened.

This paper is about solving that problem, but instead of music, the "radio station" is a stream of random events (like earthquakes, volcano eruptions, or cyber-attacks). The authors have built a new, highly precise tool to find these "switching points" in time.

Here is a breakdown of their work using simple analogies:

1. The Problem: The "Continuous" Puzzle

Most existing tools for finding these switches treat time like a staircase. They chop time into tiny, fixed steps (like seconds or minutes) and count how many events happened in each step.

The Flaw: Real life doesn't happen in steps. Events happen at exact moments (e.g., 3:14:02 PM). If you chop time into steps, you might miss the exact moment a change happened, or you might get confused by the "graininess" of your steps.
The Authors' Solution: They treat time like a smooth, flowing river. They don't chop it up. Instead, they look directly at the specific moments when events occur.

2. The Core Trick: The "Concave Hill"

To find the best places to cut the timeline, the authors use a mathematical concept called a "contrast function." Think of this as a landscape with hills and valleys. The goal is to find the deepest valley (the best fit).

The Challenge: Usually, this landscape is jagged and full of traps, making it hard to find the true bottom.
The Discovery: The authors realized that for this specific type of random event (Poisson process), the landscape between two events is actually a smooth, downward-sloping hill (concave).
The Result: Because the hill is smooth, they proved mathematically that the perfect "cut" to separate the events must happen right at the moment an event occurs (or a split-second before). You don't need to guess; you only need to check the specific times when things happened.

3. The Engine: The "Efficient Search"

Once they know they only need to check the event times, they use a clever algorithm called Dynamic Programming.

The Analogy: Imagine you are trying to cut a long loaf of bread into the perfect number of slices. A brute-force method would try every possible combination of cuts, which would take forever.
The Smart Way: The authors' method is like a smart baker who knows that if a cut is good here, it helps decide the best cut there. They build the solution piece by piece, ensuring they find the exact best arrangement of cuts without wasting time checking impossible options. This makes the process fast and exact.

4. Avoiding "Zero-Size" Slices

A common problem with these methods is that the math might try to create a "slice" of time that has zero length (a cut right on top of another cut) just to make the math look perfect.

The Fix: The authors introduced a "regularization" technique (using something called a Poisson-Gamma contrast). Think of this as adding a tiny bit of "glue" or "friction" to the math. It discourages the algorithm from making zero-length slices, forcing it to find realistic, meaningful segments.

5. Choosing the Right Number of Slices

How do you know if you should cut the timeline into 3 pieces or 10?

The Solution: They use a technique called Cross-Validation.
The Analogy: Imagine you are teaching a student (the algorithm) to recognize the music genres. You give them 80% of the recording to study (the "learning" set) and save 20% for a final test (the "test" set).
The Magic: Because these events are random, you can mathematically prove that if you randomly pick 20% of the events to be the test set, they behave exactly like a smaller version of the whole stream. This allows them to test different numbers of cuts and see which one predicts the test set best, without needing to guess.

6. Handling "Self-Exciting" Events (Hawkes Processes)

Sometimes, an event triggers more events. For example, one earthquake causes aftershocks, which cause more aftershocks. This makes the math much harder because the events aren't independent.

The Transformation: The authors found a way to "stretch" the timeline. By applying a specific mathematical stretch to the time axis, they can turn this complex, self-triggering stream into a simple, standard stream of random events.
The Result: Once stretched, they can use their standard, high-precision tool to find the changes, and then "un-stretch" the timeline to find the real dates.

7. Real-World Tests

The authors tested their method on:

Simulated Data: They created fake earthquake and volcano data to see if the tool worked. It did, finding the changes more accurately than older methods that chop time into steps.
Real Data:
- Volcanoes: They analyzed eruption dates for Kilauea and Mauna Loa in Hawaii, finding distinct periods of activity.
- Mount Etna: They looked at both when eruptions happened and how much lava was spewed (treating the volume as a "mark"). They found that looking at the volume helped spot a change in 1755 that the timing alone missed.
- Earthquakes: They analyzed aftershocks in Thailand following major 2004 and 2005 earthquakes, successfully identifying the shifts in seismic activity.

Summary

The paper presents a new, mathematically rigorous way to find "when things changed" in a stream of random events. Instead of approximating time with steps, it flows with the events, uses a smart search algorithm to find the exact best cuts, and includes a built-in test to ensure it doesn't find changes where there are none. It works for simple random events and even for complex chains of events where one triggers the next.

Technical Summary: Multiple Change-Point Detection for Poisson Processes

Problem Statement

The paper addresses the problem of detecting multiple change-points in the intensity function of point processes observed over a continuous time interval $[0, 1]$ . Specifically, the authors focus on inhomogeneous Poisson processes where the intensity function $\lambda(t)$ is assumed to be piecewise constant. The goal is to identify the unknown change-point locations $\tau = (\tau_1, \dots, \tau_{K-1})$ and the corresponding constant intensity levels $\lambda_k$ for each segment, given a sequence of observed event times $T_1, \dots, T_n$ .

The challenge lies in the continuous nature of the optimization space. Unlike discrete time settings, the change-points can occur at any real value within the interval. Standard optimization techniques (e.g., gradient descent) are inapplicable because the contrast functions (such as negative log-likelihood) are not continuous with respect to the change-point locations. Furthermore, the search space is infinite-dimensional, and the number of possible segmentations grows exponentially with the number of events.

Methodology

1. Theoretical Foundation: Reduction to Discrete Space

The core theoretical contribution is the proof that the optimal change-points for a fixed number of segments $K$ can be restricted to a finite grid derived from the event times.

Assumptions: The methodology relies on two assumptions regarding the contrast function $\gamma(\tau)$ $γ (τ)$ :
1. Segment-Additivity: The total contrast is the sum of costs for individual segments.
2. Strict Concavity: The cost function for a segment is strictly concave with respect to the segment length.
Key Insight: Building on observations by Young Yang and Kuo (2001) for single change-points, the authors prove that under these assumptions, the optimal change-points must lie either exactly at an event time $T_i$ or immediately before it ( $T_i^-$ ).
Consequence: This reduces the continuous optimization problem to a discrete one on a grid of size $2n$ (the set $\{T_1^-, T_1, \dots, T_n^-, T_n\}$ ). This allows the use of Dynamic Programming (DP) to find the exact global minimum with a computational complexity of $O(n^2 K)$ .

2. Admissible Contrasts and Regularization

The standard Poisson negative log-likelihood contrast is additive but fails the strict concavity assumption when a segment contains zero events ( $\nu_k=0$ ), leading to degenerate solutions (segments of zero length).

Solution: The authors propose Poisson-Gamma (PG) contrasts. By assuming a Gamma prior on the intensities (a Bayesian approach used to derive a frequentist contrast), they introduce hyperparameters that act as regularization. This ensures the cost function remains strictly concave even for zero counts, preventing degenerate segments and allowing for exact solutions not forced to the boundaries of event times.
Marked Processes: The framework is extended to Marked Poisson processes, where both the intensity and the distribution of marks (e.g., magnitude) change simultaneously. A Marked Poisson-Gamma-Exponential-Gamma (MPGEG) contrast is derived to handle this case.

3. Model Selection via Cross-Validation

Selecting the number of segments $K$ is treated as a model selection problem.

Thinning Property: The authors leverage the thinning property of Poisson processes. If events are sampled with probability $f$ , the remaining events form an independent Poisson process with intensity scaled by $(1-f)$ .
Procedure: The observed process is split into a "learning" set (probability $f$ ) and a "test" set. The model is trained on the learning set, and the contrast is evaluated on the test set. This avoids the ambiguity of deleting discrete time points in continuous settings, making cross-validation valid for this problem.

4. Extension to Self-Exciting (Hawkes) Processes

The methodology is extended to Piecewise-Hawkes Processes (PHP), where the intensity depends on the history of events (self-excitation).

Transformation: Using the time-rescaling theorem (Papangelou, 1972), the authors transform the Hawkes process into a heterogeneous Poisson process.
Strategy: If the parameters of the baseline Hawkes intensity ( $\alpha, \beta$ ) are known or estimated from a homogeneous period, the observed event times are transformed via the compensator $\Lambda_0(t)$ . The change-point detection is then performed on the transformed times using the standard Poisson methodology.

Key Results

Simulation Studies

The authors evaluated the method on synthetic data across three models:

Poisson Process: The method successfully recovers the correct number of segments and change-point locations as the mean intensity ( $\lambda$ ) and the contrast ratio between segments ( $\lambda_R$ ) increase. It outperforms discrete-time alternatives (binning or inter-event time analysis) in terms of Hausdorff distance and intensity estimation accuracy, particularly when event counts are low.
Marked Poisson Process: The method effectively detects change-points when signals exist in the intensity, the marks, or both. The inclusion of mark information improves detection power.
Hawkes Process: The transformation-based approach accurately detects change-points in piecewise Hawkes processes. The method performs well even when the Hawkes parameters ( $\alpha, \beta$ ) must be estimated from a preliminary homogeneous period.

Real-World Applications

The methodology was applied to two geological datasets:

Volcanic Eruptions (Kilauea and Mauna Loa): The method identified distinct regimes in eruption frequencies, detecting 3 change-points for Kilauea and 1 for Mauna Loa.
Mount Etna (Flank Eruptions): Comparing a standard Poisson model with a Marked Poisson model (using lava volume as the mark) revealed different change-point structures. The marked model detected a regime shift in 1755 related to lava volume, whereas the standard model detected a shift in 1968 related to eruption frequency.
Seismic Activity (Thailand): Applied to earthquake aftershocks, the PHP model successfully identified three major seismic events (including the 2004 Phuket earthquake) that were missed by standard Poisson modeling, demonstrating the utility of accounting for self-excitation.

Significance and Claims

The paper claims to provide a rigorous frequentist framework for multiple change-point detection in continuous-time point processes. Its primary significance lies in:

Exactness without Discretization: It proves that an exact solution exists on a finite grid tied to observations, eliminating the need for arbitrary time discretization or "binning" which can compromise accuracy.
Computational Efficiency: By reducing the problem to a discrete grid, it enables the use of efficient Dynamic Programming algorithms ( $O(n^2 K)$ ) for exact optimization.
Robustness: The introduction of admissible contrasts (Poisson-Gamma) resolves the issue of degenerate solutions common in maximum likelihood estimation for Poisson processes.
Versatility: The framework is generalizable to marked processes and self-exciting Hawkes processes via time-rescaling, unifying the treatment of various point process types under a single optimization strategy.

The authors note that the method has been implemented in the R package CptPointProcess and is available for public use. They acknowledge that while the DP complexity is quadratic in the number of events, it can be further optimized using pruned algorithms (e.g., PELT) for very large datasets.