💻 computer science

Adaptive-Hazard Bayesian Online Change-Point Detection for Text Streams: A Dirichlet-Multinomial Formulation

This paper proposes an adaptive-hazard Bayesian online change-point detection method for text streams that dynamically adjusts reset probabilities based on lexical distribution drift via a Dirichlet-multinomial formulation, demonstrating improved detection performance and reduced delay particularly in scenarios involving gradual or weak lexical changes.

Original authors: Muhammad Ali Gunawan, Amalia Fitri

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Muhammad Ali Gunawan, Amalia Fitri

Original paper licensed under CC BY 4.0 (https://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 a detective trying to spot when a story changes its plot. You're reading a never-ending stream of text messages, one after another. Your job is to figure out: "Did the writer just switch topics, or are they just rambling a bit?"

For a long time, detectives used a simple rule: "If you've been reading the same story for a while, assume a new chapter might start soon." This is like a clock that ticks down the chance of a change based only on how long you've been reading. It's a bit rigid. It doesn't care what the words actually are; it just cares about time.

This paper introduces a smarter detective. Instead of just watching the clock, this new detective looks at the words themselves. It asks, "Hey, does this new sentence sound totally different from the last few?" If the words start drifting away from the recent history, the detective gets a little more suspicious that a new chapter is starting.

The "Smart Clock" vs. The "Word Watcher"

The authors built a system called Adaptive-Hazard Bayesian Online Change-Point Detection. That's a mouthful, so let's break it down with a game.

Imagine you are playing a game where you guess the next word in a story.

The Old Way (Constant Hazard): You have a rule that says, "Every 60 words, there's a 1 in 60 chance the story changes." It doesn't matter if the story is about cats or quantum physics; the chance is the same.
The New Way (Adaptive Hazard): You have a rule that says, "If the new words look really different from the last 10 words, the chance of a story change goes up." If the words are just slightly different, the chance stays low.

The paper tests this new "Word Watcher" against the old "Clock Watcher" using 7,000 made-up text streams and 700,000 simulated documents. They didn't just guess; they ran the numbers.

What They Found (The Good, The Bad, and The "Meh")

The results are a bit like a sports team that is great at some games and just okay at others.

1. The "Obvious Change" Game:
When the story suddenly switches from talking about "pizza" to "rockets" (an abrupt shift), both detectives are amazing. They both spot the change almost instantly.

The Result: The new method found the change 99.8% of the time, and the old method found it 100% of the time.
The Takeaway: If the change is loud and clear, the fancy new "Word Watcher" doesn't really beat the simple "Clock Watcher." They are tied.

2. The "Slow Drift" Game:
This is where the new detective shines. Imagine the story slowly changes from talking about "summer" to "winter" over 20 words. The old clock might miss the slow creep. The new "Word Watcher" notices the words drifting and says, "Hey, something is shifting!"

The Result: For these slow changes, the new method found the change 0.933 of the time, while the old one only found it 0.929 of the time.
The Speed: The new method also spotted the change faster. On average, it took 6.391 steps to find the change, compared to 6.829 steps for the old method.
The Weak Signal: When the change was super subtle (like a whisper), the new method found it 0.169 of the time, beating the old method's 0.135.

3. The "Short & Noisy" Game:
Sometimes the text messages are very short and full of random words (like a text message with typos). Here, the new detective gets a little too excited. Because short messages are noisy, the "Word Watcher" sometimes thinks a change happened when it didn't.

The Result: The new method made more "false alarms" (0.077) compared to the old method (0.050). It was faster (0.551 steps vs 0.614), but it was less careful.

The "Real World" Test

To see if this works on real life, the authors tested it on a real stream of text: weekly summaries of research papers from a specific category on arXiv (a website for science papers). They looked at 106 weeks of data.

The Outcome: Neither detective found a "change point." They both agreed that the stream of papers was just one long, continuous story.
Why it matters: This is actually a good thing! It means the new method didn't get fooled by normal weekly variations. It stayed calm and didn't scream "New Story!" when the words just shifted slightly. The "Word Watcher" noticed the drift, but the math behind it said, "Nah, it's not enough to start a new chapter."

What They Explicitly Say It Is NOT

The paper is very clear about what this method is not:

It is not a magic bullet that solves every problem. The authors state it is a "conditional extension," meaning it helps in specific situations (like slow drifts) but doesn't always win.
It is not a replacement for the old method when changes are sudden and obvious. In those cases, the old method works just as well.
It is not proven to work on every type of text in the real world. The authors admit their tests were mostly on simulated data (made-up streams) and one specific real-world example. They suggest future work needs to test it on more varied data.

The Bottom Line

The authors suggest that by making the "reset probability" (the chance of a new chapter) depend on how different the words actually are, you can catch slow, sneaky changes in text streams a little better and a little faster.

However, if the text is very short and messy, this new method might get a little jumpy and sound the alarm too often. It's a useful upgrade for the detective's toolkit, especially for spotting slow drifts, but it's not a perfect replacement for the old tools in every single situation. The paper proves it works in simulations and shows it behaves conservatively on real data, but it leaves the door open for more testing in the future.

Technical Summary: Adaptive-Hazard Bayesian Online Change-Point Detection for Text Streams

Problem Statement
Bayesian Online Change-Point Detection (BOCPD) offers a recursive framework for sequential monitoring by updating the posterior distribution of the "run length" (time since the last change point). However, standard implementations typically rely on a constant or duration-dependent hazard function to determine the prior probability of a segment reset. This limitation is particularly consequential for sparse text streams, where observations are high-dimensional word-count vectors and distributional changes often manifest as gradual lexical drift rather than abrupt shifts in low-dimensional summaries. In standard BOCPD, the discrepancy between an incoming document and recent history influences the posterior only through the predictive likelihood, leaving the prior reset weight static. This paper addresses the methodological gap of connecting sparse count-based predictive updating with a hazard function that explicitly responds to online lexical-drift evidence.

Methodology
The authors propose an Adaptive-Hazard Dirichlet-Multinomial BOCPD method tailored for sparse text streams. The approach integrates three core components:

Observation Model: Documents are represented as word-count vectors. The model employs a Dirichlet-Multinomial predictive distribution, which provides a conjugate update for high-dimensional sparse counts. This allows for efficient calculation of the one-step posterior predictive probability for any candidate run length.
Adaptive Hazard Function: The core innovation is replacing the fixed hazard $H_0$ $H_{0}$ with a time-varying hazard $H_t$ $H_{t}$ . This hazard is modeled as a bounded logistic function of an online Jensen–Shannon (JS) divergence.
- The JS divergence ( $z_t$ ) measures the lexical-distributional discrepancy between the current document's smoothed empirical distribution and a recent rolling-window history.
- The hazard is defined as $H_t = h_{min} + (h_{max} - h_{min})\sigma(\alpha + \beta z_t)$ , where $\sigma$ is the logistic sigmoid.
- This formulation allows the prior reset probability to increase in response to significant lexical drift while remaining bounded to prevent degeneration (0 or 1).
- When the sensitivity coefficient $\beta = 0$ , the model reduces to the standard constant-hazard BOCPD, ensuring the new method is a nested extension of the existing framework.
Computational Implementation: To handle the quadratic complexity of standard BOCPD over long streams, the authors implement probability pruning. States with posterior probabilities below a threshold $\epsilon$ are discarded, while the reset state ( $r=0$ ) and the Maximum A Posteriori (MAP) state are always retained. The algorithm operates on the logarithmic scale to prevent numerical underflow.

Key Contributions
The paper makes three primary contributions:

Formulation: It establishes a Dirichlet-Multinomial BOCPD procedure for sparse text streams with explicit posterior predictive updating for high-dimensional word-count observations.
Adaptive Mechanism: It introduces a bounded logistic adaptive hazard that links online JS drift to the prior reset probability. This separates "boundary plausibility" (driven by the hazard) from "segment-level predictive compatibility" (driven by the observation model).
Empirical Evaluation: It provides a sparse computational implementation and evaluates the method against a constant-hazard baseline (DM-BOCPD-CH) and several non-Bayesian baselines (JS-CUSUM, JS-PH, JS-PELT) across seven controlled regimes: stationarity, abrupt shifts, gradual drift, recurring topics, sparse documents, noisy vocabulary, and weak lexical drift.

Experimental Results
The method was tested on 7,000 synthetic text streams (700,000 sequential documents) and a real-world application on arXiv cs.CL weekly metadata.

Abrupt and Recurring Shifts: Under abrupt shifts and recurring topics, the adaptive-hazard filter (DM-BOCPD-AH) performed nearly identically to the constant-hazard baseline (DM-BOCPD-CH). Valid detection rates were near 1.0 (e.g., 0.998 vs. 1.000), and delays were negligible. This indicates that the Dirichlet-Multinomial predictive likelihood alone provides sufficient evidence for sharp boundaries.
Gradual and Weak Drift: The adaptive hazard showed its clearest gains in scenarios where changes were distributed over time or weak.
- Gradual Drift: Valid detection increased from 0.929 (constant) to 0.933 (adaptive), and mean detection delay decreased from 6.829 to 6.391.
- Weak Drift: Valid detection improved from 0.135 to 0.169, with a corresponding reduction in mean delay.
Sparse Documents: In scenarios with short documents, the adaptive method became more responsive (delay decreased from 0.614 to 0.551) but slightly less conservative, with false alarm rates rising from 0.050 to 0.077 due to increased sampling variation in the JS divergence.
Stationarity: Both BOCPD methods maintained low false alarm rates (0.004–0.005) under stationary conditions, significantly outperforming direct JS monitoring baselines (0.050).
Real-World Application: On the arXiv cs.CL stream, the adaptive hazard increased the mean reset probability slightly (0.0167 to 0.0190) in response to lexical variation but did not declare spurious boundaries. The posterior remained concentrated on a single continuing segment, demonstrating that the filter correctly distinguished between natural lexical fluctuation and true regime changes.

Significance and Claims
The paper claims that the adaptive-hazard formulation is best interpreted as a conditional extension of constant-hazard BOCPD rather than a uniformly dominant detector. Its significance lies in its ability to improve detection sensitivity and reduce latency specifically when change signals are weak or gradual, without sacrificing performance on abrupt changes.

The authors emphasize that the method preserves the recursive filtering structure of BOCPD while allowing the prior reset weight to adapt to online evidence. Unlike topic-modeling approaches that rely on latent topic structures, this method monitors sparse word-count vectors directly. The study concludes that the adaptive hazard effectively reacts to online drift evidence, but the final decision to reset a segment remains governed by the joint effect of the hazard weighting and the Dirichlet-Multinomial predictive support, ensuring conservative behavior in the absence of strong predictive evidence.