Online learning (River) and incremental models

"You keep asking me to retrain on the whole history. I have already forgotten most of it, and I am a better model for it. I learned from each sample as it passed, and I kept only what a single number of memory could hold."

A Forgetful AI Agent

The learn-one, predict-one contract

An incremental model exposes two operations instead of one. A batch estimator offers fit(X, y), which consumes an entire matrix. An online estimator offers predict_one(x), which scores a single feature dictionary, and learn_one(x, y), which folds that single labelled example into the parameters and then discards it. The what is a stateful object \(\theta_t\) that evolves as the stream flows: after seeing example \(t\) it becomes \(\theta_{t+1}\), and example \(t\) is gone. The defining constraint is that per-sample cost, in both time and memory, must not grow with \(t\). A model that stores every sample it has seen is not online; it is a batch model in disguise that will exhaust its device by nightfall.

Why insist on this? Three reasons stack up for sensor work. First, the data never ends, so any algorithm whose footprint scales with the number of samples is disqualified before it starts. Second, the target moves: a gait classifier on a recovering patient, a bearing model on an ageing pump, a gesture recogniser adapting to a new user. An online model that weights recent evidence tracks that motion; a frozen batch model decays. Third, the label often arrives late and locally: the device learns the ground truth (the user corrected the gesture, the machine actually failed) after the prediction, on the device, where retraining a cloud model is impossible. The predict_one then learn_one ordering is not incidental. It is the natural shape of a stream, and it is also the honest evaluation order we will formalise as prequential testing in Section 60.6.

Three families that actually deliver constant-memory learning

Not every algorithm survives the one-sample-at-a-time constraint, but three families do, and between them they cover most sensor tasks.

The first is the stochastic linear model. Logistic or linear regression trained by stochastic gradient descent is online by construction: each example produces one gradient step \(\theta \leftarrow \theta - \eta_t \nabla \ell(\theta; x_t, y_t)\), and the parameter vector is the entire state. It is the workhorse: a few floats per feature, microseconds per update, and a learning rate \(\eta_t\) that doubles as a forgetting knob. Hold \(\eta_t\) constant rather than annealing it to zero and the model perpetually re-weights toward recent data, which is exactly what a drifting stream wants. The how is the same calculus you already know; the only change is that you take one step per arriving sample instead of one epoch over a matrix.

The second is the Hoeffding tree, also called the Very Fast Decision Tree. A batch decision tree needs the whole dataset in memory to choose each split. The Hoeffding tree instead accumulates class statistics at each leaf and uses the Hoeffding bound to decide when it has seen enough samples to split with confidence \(1-\delta\). The bound says the observed mean of a bounded variable is within

of its true mean after \(n\) observations, where \(R\) is the variable's range. When the gap between the best and second-best split criterion exceeds \(\epsilon\), the leaf splits and its raw statistics are released. This gives a tree that grows incrementally, keeps only per-leaf counters, and provably approaches the tree a batch learner would have built, all in bounded memory. It is the natural choice when sensor features interact non-linearly, as raw IMU statistics for activity recognition do (Chapter 26).

The third is the windowed neighbour or metric method: a k-nearest-neighbours model backed by a sliding buffer of the last \(w\) examples. It is not memoryless, but it is bounded, because the window caps its size. It shines for fast, local, non-parametric adaptation when the decision boundary is complex but the recent past is a good guide to the near future. The window length \(w\) is the stability knob: short forgets fast, long is steadier.

River in practice

River is the de facto Python library for this regime, formed from the merger of Creme and scikit-multiflow. Its whole design is the learn_one / predict_one contract: models consume plain dictionaries, compose into pipelines with the | operator, and carry their own streaming metrics. The snippet below builds a complete streaming classifier, standardising features online (the mechanism from Section 60.3) and feeding a Hoeffding tree, then evaluates it in the only honest way a stream allows: predict first, score, then learn.

from river import tree, preprocessing, metrics, datasets

model  = preprocessing.StandardScaler() | tree.HoeffdingTreeClassifier(grace_period=50)
metric = metrics.Accuracy()

for x, y in datasets.Phishing():          # a stream of (dict, label) pairs
    y_pred = model.predict_one(x)         # score BEFORE the model sees the label
    if y_pred is not None:
        metric.update(y, y_pred)          # prequential: test on the not-yet-learned sample
    model.learn_one(x, y)                 # now fold it in, then discard it

print(metric)                             # e.g. Accuracy: 88.5%

As Listing 60.4.1 shows, the entire streaming discipline is three lines inside the loop: predict, score, learn, in that order. Swap HoeffdingTreeClassifier for linear_model.LogisticRegression or neighbors.KNNClassifier and the loop is unchanged; the contract is the interface. Standardising inside the pipeline matters because an online scaler updates its running mean and variance from the same stream, so there is no separate fit phase to leak future statistics into the past.

What it costs and what it guarantees

Incremental learning is not free lunch, it is a different lunch. You give up multiple passes, so you cannot shuffle away the order of the data, and a badly-ordered stream (all of class A, then all of class B) can whipsaw a naive model; this is why streams are usually interleaved or the model is given a forgetting mechanism rather than assumed stationary. You give up the global view, so an online model can be transiently worse than a batch model that saw everything at once. In return you get three guarantees that matter more on a sensor than accuracy-in-the-lab: bounded memory (state size independent of stream length), bounded per-sample latency (the update is \(O(1)\) or \(O(\log)\) in the model size, never in \(t\)), and adaptivity (recent data can be made to dominate). The central tension you tune is the stability–plasticity trade-off: a high learning rate or short window is plastic and tracks change but forgets useful history and jitters on noise; a low rate or long window is stable but sluggish when the world moves. There is no universal setting, only a setting matched to how fast your particular sensor's world drifts, which is precisely what the drift detectors of the next section measure.

What's Next

In Section 60.5, we answer the question this section kept deferring: how does an online model know the world has changed, rather than just quietly tracking it and hoping? We build explicit concept-drift detectors, ADWIN and DDM, that watch a stream's error signal, raise an alarm when the distribution has genuinely shifted, and trigger a deliberate adaptation instead of relying on the learning rate alone.