Segregating event streams and noise with a Markov renewal process model

Dan Stowell, Mark D. Plumbley

In signal processing, tracking continuous movement is a well-established field. However, many real-world signals are inherently intermittent—think of birds chirping at irregular intervals or sporadic user interactions in a server log. These "event streams" consist of discrete bursts of data separated by silence, making them difficult to track using standard continuous-time models like Kalman filters.

In their research, Dan Stowell and Mark D. Plumbley propose a robust framework to untangle these messy event streams. Their approach, based on a Multiple Markov Renewal Process (MMRP), allows for the simultaneous segregation of signal from noise and the reconstruction of individual source tracks, even when the number of sources is unknown.

The Challenge of Intermittent Tracking

Traditional multi-object tracking often assumes sources are "always on." Intermittent sources introduce three primary difficulties:

  1. Unknown Population: The number of active sources is typically not known beforehand.
  2. Intermittency: Sources can remain silent for variable, often long, periods.
  3. Clutter: Data is frequently contaminated with random noise events that mimic real signals.

Existing methods often struggle to group these discrete "dots" into coherent "lines" when timing is irregular and noise is high.

Methodology: From Rhythm to Flow

The core innovation of this work lies in combining Markov Renewal Processes with Network Flow Theory.

The MMRP Model

Unlike standard Markov models that focus solely on state transitions, a Markov Renewal Process (MRP) explicitly models the time elapsed between events. By defining an MMRP, the authors characterize each source by its birth rate, death probability, and a transition distribution that captures both what the source does next and when it does it. This allows the model to use the "rhythm" of a source as a key feature for identification.

Conceptual diagram of event transitions where nodes represent observations and arcs represent potential sequences.

Mapping to Network Flow

To avoid the "combinatorial explosion" of checking every possible event sequence, the authors map the tracking problem onto a directed graph. In this formulation:

  • Nodes: Each observed event is represented as a node.
  • Arcs: Possible transitions between events are arcs, with costs defined by the negative log-likelihood of the transition.
  • Source and Sink: Special nodes ($s$ and $t$) represent the start and end of all possible tracks.
The tracking problem formulated as a minimum-cost network flow. Bold lines indicate a recovered track from source s to sink t through observed events.

Finding the most likely set of tracks is transformed into a minimum-cost flow problem. Using the Edmonds-Karp algorithm, the system identifies the "cheapest" paths through the graph, which correspond to the most probable sequences of events. This optimization naturally handles noise: if an event doesn't fit into a low-cost path, it is effectively labeled as clutter.

Experimental Evaluation

The model was tested on both synthetic and real-world datasets:

  • Synthetic Data: Sequences modeled after audio streaming experiments allowed for precise control over Signal-to-Noise Ratio (SNR) and timing drift.
  • Birdsong (The Chiffchaff): The authors used recordings of the Common Chiffchaff (Phylloscopus collybita) to create complex digital "choruses" of up to five birds.

Key Results

The MMRP approach demonstrated high accuracy, maintaining an F-measure above 0.95 for signal detection and track reconstruction in synthetic tests. Notably, the algorithm remained robust even when noise levels were significantly higher than the signal (down to -24 dB). In birdsong experiments, it vastly outperformed baseline systems that relied only on syllable frequency, successfully separating multiple overlapping birds with high reliability.

Conclusion and Future Directions

This research provides an elegant mathematical bridge between probability and graph theory for event-based tracking. While highly effective, the current model is limited to first-order Markov transitions and assumes observed events directly represent states. Future work could incorporate higher-order memory or hidden states to capture more complex behaviors. Nevertheless, the network flow formulation offers a powerful, polynomial-time solution for making sense of intermittent data in noisy environments.

Summary updated

BibTeX
@article{stowell2013segregating,
  author = {Dan Stowell and Mark D. Plumbley},
  title = {{Segregating event streams and noise with a Markov renewal process model}},
  journal = {J. Mach. Learn. Res.},
  year = {2013},
}
Figure