ADWIN: Adaptive Windowing for Drift DetectionOpen in Colab

ADWIN: Adaptive Windowing for Drift Detection

ADWIN (ADaptive WINdowing; Bifet & Gavaldà, 2007) solves two problems at once on a stream of real values — typically a model's error signal. It detects change (concept drift), and it maintains a window of exactly the right length: as long as the data looks stationary the window grows; the moment the mean shifts, it shrinks to just the recent, homogeneous part. That recovered window length is itself an estimate of "how far back the current concept extends."

The core idea: test every split of the window

ADWIN keeps a window WW of the most recent stream values. On each new element it asks:

Is there a way to cut WW into an older sub-window W0W_0 and a newer sub-window W1W_1 such that their sample means are distinguishably different?

If yes, the older data belongs to a stale concept, so ADWIN drops W0W_0 and reports drift. Formally, it declares a change at a split when

∣μ^W0−μ^W1∣  >  ϵcut,ϵcut=12m ln⁡4 ∣W∣δ,m=11∣W0∣+1∣W1∣,\big|\hat\mu_{W_0} - \hat\mu_{W_1}\big| \;>\; \epsilon_{\text{cut}}, \qquad \epsilon_{\text{cut}} = \sqrt{\frac{1}{2m}\,\ln\frac{4\,|W|}{\delta}}, \qquad m = \frac{1}{\tfrac{1}{|W_0|} + \tfrac{1}{|W_1|}},

where mm is the harmonic mean of the two sub-window sizes and δ∈(0,1)\delta \in (0,1) is the confidence parameter. The ∣W∣|W| inside the log is a union bound over the (many) possible cut points; the harmonic mean makes the threshold large when either side is small (little evidence) and small only when both sides are big.

Hoeffding vs Bernstein cut

The bound above is the Hoeffding form used in the lesson. The published ADWIN uses a slightly tighter Bernstein-style cut that folds in the observed variance σ^W2\hat\sigma^2_W:

ϵcut=2m σ^W2 ln⁡2δ′+23mln⁡2δ′,δ′=δ∣W∣.\epsilon_{\text{cut}} = \sqrt{\frac{2}{m}\,\hat\sigma^2_W\,\ln\frac{2}{\delta'}} + \frac{2}{3m}\ln\frac{2}{\delta'},\qquad \delta' = \frac{\delta}{|W|}.

For low-variance error streams this detects a bit sooner; the qualitative behaviour is identical.

Why the window length is the payoff

Most detectors only raise a boolean alarm. ADWIN additionally rightsizes its window: after a cut it retains only W1W_1, so downstream statistics (a running mean, a model refit on "the current window") automatically use only in-distribution data. There is no separate window-length hyperparameter to tune — the data sets it. This is why ADWIN is often wired directly into learners (e.g. as the change detector inside a Hoeffding Adaptive Tree, which grows an alternate subtree when a node's ADWIN fires).

Making it cheap: exponential histograms

Re-scanning every possible split of a length-∣W∣|W| window on every element would cost O(∣W∣)O(|W|) per step and O(∣W∣)O(|W|) memory. ADWIN2 compresses WW into an exponential histogram of buckets (the same power-of-two bucket structure as DGIM) storing per-bucket sums and counts with relative accuracy. This gives:

  • Memory: O(log⁡W)O(\log W) instead of O(W)O(W).
  • Time: only O(log⁡W)O(\log W) candidate split points (the bucket boundaries) are tested per update, not all ∣W∣−1|W|-1.

The approximation of using bucket boundaries as the only cut points costs a controllable constant factor and preserves the guarantees below.

Guarantees

For a suitable choice of the confidence δ\delta, ADWIN comes with two-sided rigor:

  1. Few false positives. If the mean is truly constant across WW, the probability that ADWIN wrongly shrinks the window is at most δ\delta.
  2. Reliable detection. If the mean changes by more than roughly ϵcut\epsilon_{\text{cut}}, ADWIN detects it and shrinks the window, with high probability, within a delay that scales with how large the change is (bigger jumps are caught faster).

The knob is δ\delta: larger δ\delta ⟹ smaller ϵcut\epsilon_{\text{cut}} ⟹ faster detection but more false alarms; smaller δ\delta is conservative. This is the universal detection-delay / false-alarm trade-off.

Worked cut calculation

Suppose the current window has ∣W∣=200|W| = 200 error bits, and we test the balanced split ∣W0∣=∣W1∣=100|W_0| = |W_1| = 100. Recent history shifted, so the older half averages μ^W0=0.08\hat\mu_{W_0} = 0.08 and the newer half μ^W1=0.42\hat\mu_{W_1} = 0.42. With δ=0.05\delta = 0.05:

m=11100+1100=50,ϵcut=12⋅50 ln⁡4⋅2000.05=0.01⋅ln⁡(16000)=0.01⋅9.68≈0.311.m = \frac{1}{\tfrac{1}{100} + \tfrac{1}{100}} = 50,\qquad \epsilon_{\text{cut}} = \sqrt{\frac{1}{2\cdot 50}\,\ln\frac{4\cdot 200}{0.05}} = \sqrt{0.01 \cdot \ln(16000)} = \sqrt{0.01 \cdot 9.68} \approx 0.311.

The observed gap ∣ 0.08−0.42 ∣=0.34>0.311|\,0.08 - 0.42\,| = 0.34 > 0.311, so the test fires: ADWIN drops W0W_0 and reports drift. Had the gap been the stationary-noise level (say 0.030.03), no split would exceed ϵcut\epsilon_{\text{cut}} and the window would keep growing. Note the threshold falls as the window grows (mm rises), so a change too subtle to catch now becomes detectable once more post-change data accumulates.

Watch it run

The trace reproduces the arithmetic above, then runs ADWIN on a stream with two changes of different sizes.

ADWIN — the window length is the output

1/6

The whole algorithm is one inequality, so start where the page does. A window of |W| = 200 error bits split evenly: m = 1/(1/100 + 1/100) = 50, and ε_cut = √( ln(4·200/0.05) / (2·50) ) = √(ln 16000 / 100) = 0.3111. A gap of |0.08 − 0.42| = 0.34 clears it, so the test fires. Two things do the work: **m is a harmonic mean**, so the threshold blows up whenever *either* side is small, and the |W| inside the log is a union bound over every cut point about to be tried. Note what ε_cut does *not* contain: any notion of how large a change you care about. ADWIN has no magnitude parameter, only δ.

python
1W.append(x)
2
3# only bucket boundaries, not every index
4for split in candidate_splits(W):
5 W0, W1 = W[:split], W[split:]
6
7 # harmonic mean of the two sizes
8 m = 1 / (1/len(W0) + 1/len(W1))
9 eps = sqrt(log(4*len(W)/delta) / (2*m))
10
11 if abs(mean(W0) - mean(W1)) > eps:
12 # older data is a stale concept
13 W = W1
14 return DRIFT
state
the page's worked cut
|W| → 200|W₀| = |W₁| → 100m → 50ε_cut → 0.3111gap → 0.340fires → yes

The page's own cut arithmetic (m = 50, ε_cut = 0.3111) reproduced exactly, then run on a stream with two changes of different sizes. Watch the threshold's U-shape across candidate splits, the delay while post-change evidence accumulates, and the bigger jump getting caught faster than the smaller one. Two payoffs, both of which contradicted the first draft and were rewritten from the measurements: ADWIN does not beat the best fixed window, it comes within 4% of it without being told what it is, while a wrong fixed choice costs 2x. And the famous delta trade-off is entirely one-sided here — delay grows 2.4x across the sweep while false alarms stay at zero across 300,000 stationary steps, because delta sits inside a logarithm inside a square root.

What to notice:

  • Frame 2: the threshold is a U. Plotting ϵcut\epsilon_{\text{cut}} against every candidate split shows why the harmonic mean matters: the threshold is enormous at both ends, where one sub-window is a handful of bits, and lowest in the middle. A change near the edge of the window is structurally harder to see than one in the middle.
  • Frames 3–4: delay is evidence accumulation, not sluggishness. ADWIN cannot fire right after the change because the newer sub-window is small, so mm is small and its threshold is huge. The larger jump (0.10 → 0.45) is caught in 56 steps and the smaller one (0.45 → 0.18) in 66.
  • Frame 5: the honest version of "no hyperparameter". ADWIN does not beat every fixed window: a fixed W=100W=100 scores marginally better on this stream. What ADWIN does is land within 4% of the best fixed width without being told what it is, while the spread across plausible widths is 2×. On a live stream you cannot identify the best width — that requires the ground truth you are estimating.
  • Frame 6: the δ trade-off is one-sided. Sweeping δ over five orders of magnitude, detection delay grows 2.4× while false alarms stay at zero across 300,000 stationary steps, even at δ = 0.5. δ sits inside a logarithm inside a square root, so the Hoeffding threshold is far more conservative than the nominal δ implies.

That last point qualifies the "larger δ ⟹ faster detection but more false alarms" rule above. The direction is right, but on streams of this length the false-alarm half is unobservable, so the practical advice inverts: pick δ loose, because tightening it buys a reduction you cannot measure and costs detection delay you can. δ is an upper bound on the false-alarm probability, and nothing promises it is tight.

Gotchas

  • δ is a rate, not a magnitude. It controls false-alarm probability, not the size of change you care about; pick it for your tolerance to spurious resets.
  • It monitors a scalar. ADWIN watches one real-valued signal (an error rate, a residual). For multivariate drift, run one detector per signal or feed it a scalar summary.
  • Recurring concepts. After a reset ADWIN forgets the old window, so genuinely recurring concepts are re-learned rather than recalled — pair it with an ensemble if recurrence matters.

See also

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
ADWIN: Adaptive Windowing for Dri…DGIM: Counting Ones in a …Concept Drift & Adaptation