BOCPD flashcards

31 cards. Read the term and the definition here. The deck at the top of this page is optional.

Run length r_t

The number of observations since the most recent change point, counting the current one. r_t = 0 means a change occurred exactly at time t.

Hazard rate H

The prior probability that a change point occurs at each new observation, given no change yet. Constant H implies geometrically distributed segment lengths with mean 1/H.

Run-length posterior

The distribution P(r_t | x_1:t) over all possible current run lengths after observing data up to time t. It fully summarizes belief about the last change point.

Growth vs reset

The two transitions in BOCPD: the run length grows by one with probability 1 - H, or resets to zero with probability H, representing no change or a change.

Change-point probability

The posterior mass assigned to run length zero, P(r_t = 0 | x_1:t). It is the online signal used to flag that a change just occurred.

MAP change location

The time index obtained as t minus the most probable run length, argmax_r P(r_t = r | x_1:t). It estimates where the current segment started.

Conjugate prior

A prior distribution that, combined with a likelihood, yields a posterior in the same family. It makes per-run-length predictive updates cheap and closed-form.

Normal known-variance update

Posterior precision equals prior precision plus n/σ²; posterior mean is the precision-weighted average of the prior mean and the sample mean of the current segment.

Normal-Inverse-Gamma predictive

With unknown mean and variance, the marginal predictive of a new observation is a Student-t distribution whose degrees of freedom are twice the inverse-gamma shape parameter.

Beta-Bernoulli predictive

With Beta(α, β) prior and s successes in n trials, the posterior predictive probability of success is (α + s)/(α + β + n).

Dirichlet-multinomial predictive

With Dirichlet(α) prior and category counts n_k, the predictive probability of category k is (α_k + n_k)/(Σα + n), the posterior mean probability.

Gamma-Poisson predictive

With Gamma(α, β) prior on the rate and n counts summing to S, the predictive for a new count is negative binomial with parameters α + S and β/(β+1).

Gamma-exponential predictive

With Gamma(α, β) prior on an exponential rate and n observations summing to S, the predictive density for a new observation is Lomax (Pareto type II).

Sufficient statistics

Compact summaries of a segment, such as count, sum, and sum of squares, that are enough to compute the posterior and predictive without storing raw data.

Log-sum-exp trick

A stable way to normalize log probabilities: subtract the maximum log value before exponentiating, then renormalize. It prevents underflow in long run-length vectors.

Recursive message passing

The BOCPD filtering algorithm that propagates the run-length posterior forward one observation at a time using growth and reset messages, costing O(t) per step.

Quadratic complexity

Naive BOCPD filtering costs O(t²) overall because the run-length vector has t entries at step t and each entry is updated. Pruning or truncation reduces it.

Posterior pruning

Dropping run-length hypotheses whose normalized posterior falls below a threshold and renormalizing the rest. It bounds memory and time with little accuracy loss.

Particle BOCPD

An approximation that represents the run-length posterior with weighted particles, resampling and rejuvenating them to avoid degeneracy when exact updates are too costly.

Viterbi run-length decoding

A max-product pass over the run-length lattice that returns the single most probable joint segmentation rather than per-time marginal change probabilities.

Forward-backward smoothing

An offline pass combining forward filtered run-length posteriors with backward messages to give P(r_t | x_1:T), which uses future data and differs from filtering.

Hazard sensitivity trade-off

Larger H detects changes faster but raises false alarms and shortens segments; smaller H is conservative, smoothing over real changes and increasing detection delay.

Model evidence

The marginal likelihood of the data under the BOCPD model, accumulated from one-step predictive probabilities. It supports comparing hazard values or component models.

Detection delay

The number of observations between a true change point and the first time the change-point probability crosses the decision threshold. It measures online responsiveness.

False alarm rate

The expected rate of threshold crossings when no change has occurred. It is traded against detection delay by adjusting the threshold or hazard prior.

Tolerance-window scoring

Segment-level evaluation that counts a detected change as correct if it falls within k observations of a true change, then computes precision and recall.

Posterior entropy diagnostic

The entropy of the run-length posterior measures segmentation confidence. Low entropy means a sharp, confident estimate; high entropy signals ambiguity about the change location.

Online versus offline

BOCPD is causal and online, using only past data, whereas optimal partitioning and binary segmentation are offline and may revise earlier change points.

Constant-hazard assumption

Assuming a fixed hazard implies geometric segment lengths and no duration dependence. Trended or heavy-tailed data may require a time-varying hazard or detrending.

Run-length heatmap

A plot of the run-length posterior over time, with run length on one axis and time on the other. Diagonal resets mark detected change points for inspection.

Typical BOCPD applications

Sensor and machine fault detection, network traffic anomaly monitoring, speech and music segmentation, and econometric regime-shift detection in streaming time series.