Online and Incremental Models

"I was built to forget. Every observation I admit, I discount the last; every regime that ends, I let fade. The trouble started when the world stopped changing for a while, and I kept forgetting anyway, dropping perfectly good evidence out of sheer habit. Now I sit here, half my memory gone, refusing to forget how to forget, because the one thing I was never taught is when to stop."

An Incremental Model Refusing to Forget How to Forget

In Section 20.2 we built detectors that watch a stream and raise an alarm when the data-generating process has changed: ADWIN, the Page-Hinkley test, DDM and its kin. A detector that fires is only half a system. The other half, the half this section supplies, is the model that does something useful with the alarm, and more fundamentally the model that keeps learning between alarms so that it tracks slow drift the detector never trips on. We are moving from noticing drift to surviving it. The classical estimators we lean on were first met in Chapter 5, where exponential smoothing and recursive updates appeared as forecasting tools; here they return wearing a different hat, as the simplest possible online learners, and we read them through the lens of memory and adaptation rather than point prediction. We use the unified notation of Appendix A: $\mathbf{x}_t$ the features at time $t$, $y_t$ the target, $\boldsymbol{\theta}_t$ the parameter vector after seeing $t$ observations, $\hat{y}_t$ the prediction, $\lambda$ the forgetting factor.

Why does online learning deserve its own treatment rather than "just retrain the batch model on new data now and then"? Because periodic retraining is a coarse, expensive, and laggy approximation of what a true online learner does continuously and cheaply. Retraining nightly means the model is up to a day stale; retraining is wasteful when the world barely moved; and retraining throws away the elegant fact that many models admit an exact constant-time, constant-memory update per observation. The four competencies this section installs are these: to build incremental estimators whose memory you control with a window or a forgetting factor, and to compute the effective memory length that factor implies; to assemble a streaming ensemble that adds, weights, and drops members in response to drift; to choose deliberately between blind and informed adaptation and to handle recurring regimes with a model pool; and to understand the stability-plasticity tension that online deep learning inherits, the tension that Section 20.4 on continual and lifelong learning is devoted to resolving. These are the load-bearing skills of any temporal system that must run in production while the world refuses to hold still.

1. Incremental Updates Under Drift: Windows, Forgetting Factors, Adaptive Rates Beginner

An incremental model maintains a current parameter $\boldsymbol{\theta}_t$ and, on receiving a new pair $(\mathbf{x}_t, y_t)$, produces $\boldsymbol{\theta}_{t+1}$ from $\boldsymbol{\theta}_t$ and the new pair alone, without revisiting the past. The whole craft of online learning under drift is the craft of deciding how much the past should count, and there are three classical instruments for tuning that, each a different shape of memory.

The first is the sliding window. Keep an explicit buffer of the most recent $w$ observations, fit the model on exactly those, and let the oldest point fall out as each new one arrives. The window is a hard, rectangular memory: a point that is $w$ steps old counts fully, and a point that is $w+1$ steps old counts not at all. The window length $w$ is a direct knob on the stability-plasticity trade. A short window adapts fast to drift but is noisy and overreacts to outliers; a long window is smooth and statistically efficient but lags behind real change. The window's virtue is its honesty (you can point to exactly which data the model is using) and its vice is its abruptness (a single old point dominates until the instant it is evicted, then vanishes entirely).

The second, and the workhorse of this section, is the forgetting factor. Rather than a hard cutoff, weight each past observation by a geometric decay: at the current time, an observation of age $a$ contributes with weight $\lambda^{a}$ for some $\lambda \in (0, 1)$ close to one. The objective minimized at time $t$ is the exponentially weighted sum of squared errors,

so the most recent point ($i = t$) gets weight one, the previous gets $\lambda$, the one before $\lambda^2$, and so on into a smoothly fading tail. This is a soft, exponential memory: nothing is ever fully forgotten, but old evidence decays geometrically. The forgetting factor is the continuous cousin of the window, and (as subsection five derives) a given $\lambda$ corresponds to an effective window of about $1/(1-\lambda)$ points. The exponentially weighted moving average (EWMA) we met in Chapter 5.5 as exponential smoothing is the degenerate one-parameter case of this objective, $\hat{y}_{t+1} = \alpha y_t + (1-\alpha)\hat{y}_t$ with $\alpha = 1 - \lambda$, and recursive least squares (RLS) with forgetting is its full multivariate generalization.

The third instrument is the adaptive learning rate. For models updated by stochastic gradient descent, $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t\,\nabla_{\boldsymbol{\theta}}\ell_t$, the step size $\eta_t$ plays the role of forgetting: a large $\eta_t$ lets a new point move the parameters far (high plasticity, fast forgetting of the old fit), a small $\eta_t$ moves them little (high stability). In a stationary stream the textbook prescription is a decaying schedule $\eta_t \propto 1/t$ so the estimate converges; under drift that prescription is exactly wrong, because a vanishing learning rate freezes the model just when it most needs to keep moving. Online learning under drift therefore keeps the learning rate bounded away from zero, or adapts it upward when error rises, so the model never loses the plasticity to track change. This is the same vanishing-step pathology, in a different guise, that Chapter 9 raised for recurrent training, and the same instinct (never let the update fully die) recurs in the continual-learning methods of Section 20.4.

2. Ensemble Methods for Streams: Weighting, Adding, and Dropping Members Intermediate

A single incremental model with one memory setting is a blunt instrument: its forgetting factor is a compromise that is too fast for stable periods and too slow for abrupt change. Streaming ensembles relax that compromise by maintaining several learners at once and letting a meta-policy decide, observation by observation, which to trust, which to refresh, and which to discard. Three ensemble families dominate online practice.

The first is Dynamic Weighted Majority (DWM, Kolter and Maloof, 2007). Maintain a set of experts, each casting a weighted vote; on every observation, multiply the weight of any expert that predicted wrongly by a penalty $\beta \in (0,1)$; periodically remove experts whose weight has fallen below a threshold and add a fresh expert when the ensemble as a whole errs. DWM adapts without any explicit drift detector: the weighting silently demotes models that have gone stale and the add-on-error rule injects fresh capacity exactly when accuracy slips. It is blind adaptation (subsection three) realized as a weighting scheme.

The second is the Adaptive Random Forest (ARF, Gomes et al., 2017), the streaming counterpart of the batch random forest and one of the strongest off-the-shelf online learners. Each tree is grown incrementally on a different bootstrap of the stream; critically, each tree carries its own Section 20.2 drift detector (typically ADWIN) running on its own error stream. When a tree's detector signals a warning, the forest starts growing a background replacement tree on new data; when the detector confirms drift, the background tree takes over and the stale tree is dropped. ARF is the cleanest illustration of the informed-adaptation pattern (subsection three): detect, prepare a replacement in the background, swap on confirmation.

The third family is online bagging and boosting (Oza and Russell, 2001). Batch bagging resamples the dataset; you cannot resample a stream you have not fully seen, so online bagging instead presents each arriving point to each base learner $k \sim \text{Poisson}(1)$ times, the Poisson being the streaming limit of the binomial resample. Online boosting reweights similarly, increasing a point's Poisson rate for learners that got it wrong. These give the variance reduction of bagging and the bias reduction of boosting in a pure one-pass setting.

Across all three families, the operations that matter under drift are the same triad, summarized in Figure 20.3.1: weight members by recent accuracy so stale models fade from the vote; add fresh members (or background replacements) when accuracy drops or a detector warns; and drop members that have decayed or been superseded. The add-and-drop is where the ensemble couples to the drift detectors of Section 20.2: a confirmed alarm is the cue to retire a stale member and seat a fresh one, which is exactly the reset mechanism the worked ensemble of subsection five implements.

3. Drift-Aware Strategies: Blind Versus Informed, and Recurring Regimes Intermediate

Step up from individual mechanisms to the overall adaptation strategy, and online systems split into two philosophies. Blind adaptation never explicitly detects drift: it simply forgets a little on every observation, via a forgetting factor, a bounded learning rate, or continuous reweighting, so that the model is always gently tracking. Informed adaptation runs a drift detector (Section 20.2) and reacts only on an alarm, by resetting, retraining, or swapping in a fresh model. Each buys something and pays for it.

Blind adaptation is robust to slow, gradual drift that no detector would ever trip on, and it has no detection-lag, the model is already adapting before any alarm could fire. Its weakness is that it pays a constant price in stationarity: even when the world is perfectly stable, a blind learner keeps discounting good data, so its estimates are noisier than a model that knew to stop forgetting. Informed adaptation is the mirror image. It is statistically efficient in stable periods (it stops forgetting and lets data accumulate) and it reacts decisively to abrupt change (a clean reset throws out the now-irrelevant past in one move). Its weaknesses are detection lag (it does nothing until the alarm fires, so it is briefly wrong after a sudden shift) and a vulnerability to slow drift that creeps in below the detector's sensitivity. The practical synthesis, and the design most production systems converge on, is to do both: a blind forgetting factor to track gradual drift continuously, plus an informed detector to trigger a hard reset on the abrupt shifts the slow forgetting cannot keep up with. The worked ensemble of subsection five is exactly this synthesis: forgetting members that also reset on an alarm.

One drift pattern defeats both simple strategies on its own: recurring drift, where regimes that appeared before come back. Demand reverts to a holiday pattern every December; a market re-enters a volatility regime it has visited before; a sensor returns to a previously-seen operating mode. A model that resets on every drift discards a regime it will need again next month, then has to relearn it from scratch, paying the detection-lag and relearning cost over and over. The remedy is a model pool: instead of discarding a model when drift is detected, freeze it and store it in a pool keyed by a signature of the regime it was trained on. When drift is next detected, before training a fresh model, check whether any pooled model already matches the new regime (by recent error on the incoming window) and, if so, reactivate it instead of relearning. The pool converts recurring drift from a repeated full relearning cost into a near-instant model switch, and it is the streaming analogue of the recurring-state idea that the regime-switching models of Chapter 6 handled in batch. Recurring-regime pools are also a stepping stone to the lifelong learners of Section 20.4, which must retain many past skills rather than two or three regimes.

4. Online Deep Learning: Replay, Plasticity, and the Stability Tension Advanced

The estimators of subsection one update in closed form; a deep network has no such luxury, and online deep learning is where the memory question turns genuinely hard. The naive recipe, keep applying SGD to each new minibatch as it streams in, is continual finetuning, and on a drifting stream it fails in a characteristic way. A neural network trained only on recent data suffers catastrophic forgetting: the gradient steps that fit the new regime overwrite the weights that encoded the old one, so a model that adapts to December's pattern silently destroys its ability to handle June's. The very plasticity that lets the network track drift is what erases its earlier competence, and a pure forgetting factor at the weight level (which is what an unconstrained learning rate amounts to) makes the problem worse, not better.

The standard mitigation is a replay buffer. Maintain a bounded memory of past examples (a reservoir sample of the stream, or a class-balanced or regime-balanced selection), and at each update step mix a batch of fresh observations with a batch sampled from the buffer. The replayed examples re-inject gradient signal from older regimes, so the update that fits the new data is restrained from destroying the old; the network interleaves new and old as if it were training on a stationary mixture. Replay is the simplest and most reliable defense against catastrophic forgetting, and the size and sampling policy of the buffer are the knob that trades adaptation speed against retention.

Underneath every choice here sits the stability-plasticity dilemma: a learner must be plastic enough to acquire new patterns yet stable enough to retain old ones, and these pull in opposite directions. Too plastic and it forgets catastrophically; too stable and it cannot adapt to drift at all. A second, subtler failure has drawn recent attention, loss of plasticity: networks trained continually for long enough gradually lose the ability to learn new things at all, as units saturate and effective capacity shrinks, so the network becomes not just forgetful but unteachable. Online deep learning is the art of navigating between these two cliffs, and it is hard enough that Section 20.4 on continual and lifelong learning is devoted entirely to the regularization, replay, and architectural strategies that manage it. Here we simply name the tension and note that the classical forgetting-factor estimators of subsection one sidestep it precisely because their convexity guarantees a unique fit that no amount of forgetting can corrupt into uselessness, a luxury the non-convex network does not enjoy.

5. Worked Example: A Forgetting-Factor Forecaster and a Drift-Resetting Ensemble Advanced

We now make the section executable on the sensor-and-IoT stream that threads through Part V. The plan has three movements. First, build a forgetting-factor recursive least squares forecaster from scratch and watch it recover after an injected drift, the blind-adaptation half of subsection three. Second, build a tiny streaming ensemble whose members carry a forgetting factor and reset one member on a drift alarm, the blind-plus-informed synthesis. Third, reproduce the same streaming pattern with a few lines of river, the production online-learning library, reported as a single prequential metric over the stream, and state the line-count reduction. We start by generating a stream with an abrupt drift at the midpoint, then implement RLS with forgetting. Code 20.3.1 is the from-scratch incremental estimator.

import numpy as np

rng = np.random.default_rng(0)
T, d = 600, 3                               # stream length, feature dimension
drift_at = 300                              # an abrupt coefficient change at t=300

# A linear stream y = theta . x + noise, with theta jumping at the drift point.
X = rng.normal(0, 1.0, size=(T, d))
theta_a = np.array([2.0, -1.0,  0.5])       # regime A coefficients
theta_b = np.array([-1.0, 2.0, -0.5])       # regime B coefficients (post-drift)
theta_true = np.where(np.arange(T)[:, None] < drift_at, theta_a, theta_b)
y = np.einsum("td,td->t", X, theta_true) + rng.normal(0, 0.3, size=T)

class ForgettingRLS:
    """Recursive least squares with exponential forgetting factor lam in (0,1]."""
    def __init__(self, d, lam=0.98, delta=100.0):
        self.lam = lam
        self.theta = np.zeros(d)            # current weight estimate theta_t
        self.P = delta * np.eye(d)          # inverse correlation matrix (large = unsure)

    def predict(self, x):
        return self.theta @ x               # y_hat = theta . x

    def update(self, x, y):
        Px = self.P @ x
        denom = self.lam + x @ Px           # scalar gain denominator
        k = Px / denom                      # Kalman-like gain vector
        err = y - self.theta @ x            # prediction error (innovation)
        self.theta = self.theta + k * err   # move theta toward the new point
        self.P = (self.P - np.outer(k, Px)) / self.lam  # forgetting inflates P

# Run two forgetting factors over the stream and record absolute error.
errs = {}
for lam in (0.999, 0.95):                   # long memory vs short memory
    m = ForgettingRLS(d, lam=lam)
    e = np.empty(T)
    for t in range(T):
        e[t] = abs(m.predict(X[t]) - y[t])  # test-then-train (prequential)
        m.update(X[t], y[t])
    errs[lam] = e

print("lam=0.999  mean |err| pre-drift  = %.3f" % errs[0.999][:drift_at].mean())
print("lam=0.999  mean |err| 50 steps after drift = %.3f" % errs[0.999][drift_at:drift_at+50].mean())
print("lam=0.95   mean |err| 50 steps after drift = %.3f" % errs[0.95][drift_at:drift_at+50].mean())

lam=0.999  mean |err| pre-drift  = 0.279
lam=0.999  mean |err| 50 steps after drift = 2.913
lam=0.95   mean |err| 50 steps after drift = 1.146

The single forgetting factor is a fixed compromise. Code 20.3.2 builds the blind-plus-informed synthesis of subsection three: a small ensemble of forgetting-RLS members, weighted by recent accuracy, with a lightweight drift alarm (a jump in the running error) that resets the worst member so the ensemble injects fresh plasticity exactly when the stream shifts. This is the add-and-drop triad of subsection two realized in a few lines.

class DriftResettingEnsemble:
    """Forgetting-RLS members, accuracy-weighted, resetting a member on a drift alarm."""
    def __init__(self, d, lams=(0.999, 0.99, 0.95), window=30, alarm_mult=2.5):
        self.members = [ForgettingRLS(d, lam=l) for l in lams]
        self.w = np.ones(len(self.members))      # ensemble vote weights
        self.window = window
        self.alarm_mult = alarm_mult
        self.recent = []                         # rolling ensemble errors for the alarm
        self.baseline = None                     # learned "normal" error level

    def predict(self, x):
        preds = np.array([m.predict(x) for m in self.members])
        return (self.w @ preds) / self.w.sum()   # weighted-average prediction

    def update(self, x, y):
        for j, m in enumerate(self.members):
            e = abs(m.predict(x) - y)
            self.w[j] *= np.exp(-e)              # demote members that erred (DWM-style)
            m.update(x, y)
        self.w /= self.w.sum()                   # renormalize the vote weights
        ens_err = abs(self.predict(x) - y)
        self.recent.append(ens_err)
        if len(self.recent) > self.window:
            self.recent.pop(0)
            cur = np.mean(self.recent)
            if self.baseline is None:
                self.baseline = cur
            elif cur > self.alarm_mult * self.baseline:   # DRIFT ALARM fired
                worst = int(np.argmin(self.w))            # reset the least-trusted member
                self.members[worst] = ForgettingRLS(x.shape[0], lam=0.95)
                self.w[worst] = self.w.mean()             # give the fresh member a fair vote
                self.baseline = cur                       # accept the new error regime
            else:
                self.baseline = 0.99 * self.baseline + 0.01 * cur  # slow baseline drift

ens = DriftResettingEnsemble(d)
ens_err = np.empty(T)
for t in range(T):
    ens_err[t] = abs(ens.predict(X[t]) - y[t])
    ens.update(X[t], y[t])

print("ensemble mean |err| 50 steps after drift = %.3f" % ens_err[drift_at:drift_at+50].mean())
print("ensemble mean |err| pre-drift             = %.3f" % ens_err[:drift_at].mean())

ensemble mean |err| 50 steps after drift = 0.831
ensemble mean |err| pre-drift             = 0.291

Finally the library pair. Code 20.3.3 solves the same prequential streaming-regression task with river, the standard online-learning library, whose objects expose exactly the learn_one / predict_one incremental interface and ship ADWIN-coupled adaptive ensembles internally. The from-scratch RLS and ensemble above ran roughly 60 lines of state management; the executable river version is about 10.

from river import linear_model, optim, ensemble, tree, metrics

# An online linear regressor whose learning rate IS the forgetting knob.
model = linear_model.LinearRegression(optimizer=optim.SGD(lr=0.05))

# Or a drift-adaptive ensemble: bagging over Hoeffding trees with ADWIN per member.
# model = ensemble.ADWINBaggingRegressor(model=tree.HoeffdingTreeRegressor(), n_models=3)

mae = metrics.MAE()
for t in range(T):
    xi = {f"f{j}": X[t, j] for j in range(d)}   # river uses dict feature vectors
    y_pred = model.predict_one(xi)              # test ...
    mae.update(y[t], y_pred)
    model.learn_one(xi, y[t])                   # ... then train (prequential)

print("river streaming MAE over full drifting stream =", round(mae.get(), 3))

river streaming MAE over full drifting stream = 0.642

Read the three blocks together. Code 20.3.1 showed a single forgetting factor trading stationary accuracy against recovery speed; Code 20.3.2 escaped that single compromise with a weighted ensemble that resets a member on a drift alarm; Code 20.3.3 reproduced the whole streaming pattern in a few lines of river. The pedagogical payoff is that online learning under drift is not a black box: the memory is a knob you can write down ($\lambda$, a window, a learning rate), the ensemble logic is a short weight-add-drop loop, and a production library packages exactly these mechanics behind a two-method incremental API.

from river import ensemble, tree, drift, metrics

# An adaptive ensemble: each Hoeffding tree carries its own ADWIN detector and is
# replaced on confirmed drift, exactly the add-and-drop triad of subsection 2.
model = ensemble.ADWINBaggingRegressor(
    model=tree.HoeffdingTreeRegressor(),
    n_models=5,
    drift_detector=drift.ADWIN(),
)
mae = metrics.MAE()
for t in range(T):
    xi = {f"f{j}": X[t, j] for j in range(d)}
    mae.update(y[t], model.predict_one(xi))   # prequential test-then-train
    model.learn_one(xi, y[t])

Exercises