Keywords: Data stream mining, Concept drift, Prior probability shift, Verification latency, Prequential evaluation, Performance measures
Introduction
Models deployed on data streams process data at high velocity while the distribution changes, and the evaluation protocol is what tells an adaptive system whether the model is still healthy. A protocol that cannot separate a degraded decision boundary from a transient shift can trigger needless adaptation or hide a real failure.
Classification evaluation was developed for batch settings with independent and identically distributed observations, complete and immediate labels, and every class present in each evaluation sample. Three of these assumptions break in streams.
First, streams need continuous temporal aggregation. Under the prequential (test-then-train) paradigm, predictions are made sequentially and the history is discounted by exponential fading (α \alpha α ) or a sliding window (W W W ). Standard packages [3 , 17 , 18 ] compute streaming metrics as ad hoc functions, with no guarantee on how temporal weighting interacts with micro- and macro-averaging across classes, and embedded applications bound the cost of an update and the memory they may use.
Second, labels are not available immediately. Predictions p t \mathbf{p}_t p t are made at time t t t but the true labels y t \mathbf{y}_t y t arrive after an uncertain latency Δ t \Delta_t Δ t (a fraudulent chargeback is confirmed after weeks), and in credit underwriting or medical screening labels are revealed only for accepted candidates, so the model’s own decisions censor the rest. Evaluating only the verified or uncensored instances can then be biased.
Third, diagnostics under distribution shift are unreliable. Accuracy, Precision and F 1 F_1 F 1 depend on the class prior P t ( Y ) P_t(Y) P t ( Y ) , so a change in class prevalence moves them even when the decision boundary P t ( Y ∣ X ) P_t(Y \mid X) P t ( Y ∣ X ) is intact and can make drift detectors such as ADWIN [2 ] or DDM [9 ] raise spurious alarms. Under extreme imbalance, a short window may contain no instance of a rare class, which leaves recall and related measures undefined (0/0, a zero-division void), and the default conventions (0/0 → 0.0 or 1.0) create artificial steps in monitoring dashboards.
This paper extends the unified algebraic framework of indicator matrices [24 ] to continuous, resource-constrained and partially verified data streams. That framework builds a confusion matrix from indicator matrices of the true and the predicted classes, and obtains pooled (micro) and per-class (macro) performance measures from it by two reductions (§ 3 recalls them). Figure 1 shows the pipeline and Algorithm 1 in § 4.2 gives its update step by step.
Figure 1. Pipeline of the framework. Features and predictions arrive at time t t t , and each label arrives separately at time k + Δ k k + \Delta_k k + Δ k with latency Δ k ≥ 0 \Delta_k \ge0 Δ k ≥ 0 . Both flows feed the temporal operator Σ t \Sigma_t Σ t , which keeps one evolving state C ( t ) C(t) C ( t ) . The global view reduces C ( t ) C(t) C ( t ) directly, and the per-class view first extracts each class’s table and then averages across classes. Figure 2 gives the algebraic architecture.
Figure 2. Algebraic architecture of data stream evaluation. The temporal state C ( t ) C(t) C ( t ) (base layer, § 3 ) feeds two evaluation branches: functional reduction compositions (Σ ∘ Σ t \Sigma\circ\Sigma_t Σ ∘ Σ t , Branch A, § 3.2 ) and structural per-class projections (S j S_j S j , Branch B, § 3.3 ). Theorem 1 (§ 3.4 ) relates them. The dashed arrow shows that the per-class matrices C j ( t ) C_j(t) C j ( t ) of Branch B are the input of the macro reduction Σ m ∘ Σ t \Sigma_m \circ\Sigma_t Σ m ∘ Σ t of Branch A.
Our contributions are as follows.
A temporal reduction operator Σ t \Sigma_t Σ t that weights the confusion counts in time, in exponential-fading and sliding-window forms. It updates in O ( m 2 ) O(m^2) O ( m 2 ) operations per step independent of the stream length, and each pooled measure remains a weighted combination of the per-class measures (Theorem 1).
A model of delayed and selective feedback as an observation mask, which contains the four label-availability settings of Gomes et al. [11 ] , and an interim estimate of missing labels, which counts a pending instance with the model’s calibrated class probabilities combined by the product t t t -norm, with a queue bounded by an analytic bound (Algorithm 1) and a bias that follows the calibration error of those probabilities.
Prior-free canonical coordinates (recall and specificity for two classes, the confusion rows for several), with the conditions under which they are prior-free in the binary and the multiclass case, and a scheme that detects on these coordinates and attributes a metric change by a first-order Jacobian decomposition, evaluated on synthetic and real streams with thresholds calibrated for the run-level false alarm.
Audited conventions for undefined (zero-division) cases, a formula for the probability of an undefined window, and Pareto dominance over time for comparing online learners without choosing metric weights.
§ 2 reviews related work. § 3 introduces the temporal operator, per-class projections, complexity bounds and zero-division auditing. § 4 presents observation masks for latency and censoring and the interim estimate. § 5 treats prior shift and concept drift: prior-free coordinates, attribution and monitoring. § 6 reports the experiments and § 8 concludes. Examples 1 to 6 follow one small stream through the sections, and Appendix § 11 lists their values. Appendix § 10 collects the notation.
Related Work and Background
Prequential error estimation, pioneered by Dawid [7 ] and popularized in streaming literature by Gama et al. [10 ] and Bifet et al. [3 ] , evaluates streaming models by testing on incoming instances prior to model updating. Exponential fading factors α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and sliding windows W W W are widely used and implemented in standard streaming toolkits such as MOA [3 ] , scikit-multiflow ([17 ] ), and River ([18 ] ), but whether temporal weighting stays consistent with pooling the classes (micro) and averaging over them (macro) has remained unformalized: these packages compute streaming metrics as empirical, per-metric functions rather than as instances of one aggregation rule.
A related strand of work characterizes and detects the non-stationarity such packages are meant to track. Distinguishing covariate shift P ( X ) P(X) P ( X ) , prior probability shift P ( Y ) P(Y) P ( Y ) and concept drift P ( Y ∣ X ) P(Y \mid X) P ( Y ∣ X ) is an established problem ([16 , 19 ] (Webb et al. 2016)). The detectors built to monitor drift (DDM ([9 ] ), ADWIN ([2 ] ), HDDM ([8 ] )) track a scalar error rate, which moves with the class prior whenever the classifier’s errors differ between classes, and label-shift methods address the prior itself. What § 5 adds is a monitor on prior-free coordinates and an attribution of the change of a given metric to its prior-dependent and concept-dependent parts. A complementary line of work targets a different question given a known ground-truth drift point: how accurately and promptly a detector fires. Cerqueira et al. [5 ] recently formalized this with an acceptable detection window and timing-aware metrics (F1 detection score, Normalized Detection Time); their framework evaluates detector timing once a drift signal exists, while § 5 concerns the signal itself and keeps it free of prior shift.
A different failure mode arises even before drift needs to be detected at all: ground truth itself may not be available in time. In practical stream mining, immediate label feedback is an unrealistic assumption. Gomes et al. [11 ] survey semi-supervised learning for delayed, partially labelled streams and state the problem in four settings (immediate or delayed labels, fully or partially labelled), noting that the last, delayed and partially labelled, is the least explored; on the evaluation side they review benchmarking practice and propose a label-removal protocol, and they note that prequential evaluation of a partially labelled stream computes the loss only where labels are known, which is the naive estimator whose selection bias § 4.2 corrects. Grzenda et al. [12 ] propose continuous re-evaluation for delayed labels, which follows the predictions made for an instance over time until its label arrives and assumes that every label arrives after a finite delay; Gomes et al. [11 ] note that it could be adapted to partially labelled streams by using only the instances whose label arrives. Plassе and Adams [21 ] study the handling of delayed labels in learning, and Žliobaitė et al. (2014) address the complementary problem of where to spend a limited labelling budget under drift, without formalising the selection bias when evaluation is restricted to the actively queried or decision-accepted subset. What we add is an estimate of the current performance from the unverified instances and a correction of selection bias under decision-dependent censoring.
Rare-class evaluation compounds the same problem: online class imbalance learning ((Wang et al. 2018)) and the broader survey of imbalanced-stream methods by Aguiar et al. [1 ] both document how existing algorithms and metrics degrade under skewed, drifting class ratios, but neither formalizes the zero-division singularities that arise when a rare class disappears from a short evaluation window, the failure mode addressed in § 3.5 .
A third, largely orthogonal limitation concerns the metrics themselves, independent of how or when labels arrive. Beyond the measures covered by Theorem 1, which are ratios of linear combinations of confusion-matrix cells (recall, precision, F 1 F_1 F 1 and similar), ranking-based metrics pose their own streaming challenges. Brzeziński and Stefanowski [4 ] extend AUC to the prequential setting via an efficient sliding-window sorted-tree structure, addressing for that one metric the same consistency gap this paper generalizes to the whole family of such ratios under Σ t \Sigma_t Σ t . Model comparison under conflicting objectives has a parallel history in the Pareto-optimal (ROC convex hull) classifiers of Provost and Fawcett [25 ] ; § 6.5 extends this static, batch notion of Pareto dominance to continuously-updated temporal contingency states.
Temporal Indicator Matrices and the Σ t \Sigma_t Σ t Operator
This section establishes the formal foundations of prequential indicator matrices by unifying temporal evaluation with the matrix aggregation algebra of the core framework (Prati [24 ] ). We express temporal aggregation as a weighted bilinear matrix operator, formalize multiclass per-class projections via linear selection matrices, and define the composition algebra between the new temporal operator Σ t \Sigma_t Σ t and the core reduction operators (Σ 1 \Sigma_1 Σ 1 , Σ m \Sigma_m Σ m ).
For readers unfamiliar with Prati [24 ] , we briefly recall the two objects this paper extends. The core framework represents a batch of n n n classified instances as a pair of indicator matrices Y , Y ^ ∈ R n × m Y,\hat{Y} \in\mathbb{R}^{n \times m} Y , Y ^ ∈ R n × m (one row per instance, one column per class), with C = Y T Y ^ ∈ R m × m C = Y^{T}\hat{Y} \in\mathbb{R}^{m \times m} C = Y T Y ^ ∈ R m × m the resulting confusion matrix. A performance measure M M M is then evaluated in one of two ways: the micro reduction Σ 1 \Sigma_1 Σ 1 pools all n m nm nm cell contributions into a single global confusion table before evaluating M M M once, while the macro reduction Σ m \Sigma_m Σ m evaluates M M M separately on each class’s own 2 × 2 2 \times2 2 × 2 table and averages the m m m results. The two coincide for every choice of the per-class numerators exactly when every class’s denominator is equal (Corollary 1 of Prati [24 ] ), and generally differ otherwise. The same micro/macro distinction reappears, with a temporal twist, in § 3.2 below. This paper’s contribution is to show that both reductions, and the relationship between them, survive once the batch matrices Y , Y ^ Y,\hat{Y} Y , Y ^ are replaced by the temporally weighted state C ( t ) C(t) C ( t ) defined next.
Notation and the Streaming Bilinear Formulation
Let S = { ( x t , y t , p t ) } t ∈ N + S = \{(x_t, y_t, p_t)\}_{t \in\mathbb{N}^{+}} S = {( x t , y t , p t ) } t ∈ N + represent an ordered sequence of streaming instances arriving at discrete timestamps t ∈ { 1 , 2 , … } t \in\{1,2,\ldots\} t ∈ { 1 , 2 , … } , where y t y_t y t denotes instance t t t ’s true label as soon as it exists, whether or not it is yet observable to the evaluator, subject to a possibly random verification latency; § 4 formalizes this observability gap with the per-instance mask O k ( t ) \mathcal{O}_k(t) O k ( t ) and its latency Δ k \Delta_k Δ k . At time t t t :
x t ∈ X x_t \in\mathcal{X} x t ∈ X denotes the input feature vector drawn from dynamic distribution P t ( X ) P_t(X) P t ( X ) ;
y t = [ y t 1 , … , y t m ] T ∈ Δ m − 1 y_t = [y_{t1},\ldots,y_{tm}]^T \in\Delta^{m-1} y t = [ y t 1 , … , y t m ] T ∈ Δ m − 1 is the true target vector on the standard probability simplex Δ m − 1 = { u ∈ [ 0 , 1 ] m : ∑ j = 1 m u j = 1 } \Delta^{m-1} = \{\mathbf{u} \in[0,1]^m : \sum_{j=1}^{m} u_j = 1\} Δ m − 1 = { u ∈ [ 0 , 1 ] m : ∑ j = 1 m u j = 1 } , representing deterministic labels (y t = e j y_t = e_j y t = e j , the j j j -th standard basis vector, i.e. a one-hot vector with a 1 1 1 in the true-class position and 0 0 0 elsewhere) or soft distributions P t ( Y ∣ x t ) P_t(Y \mid x_t) P t ( Y ∣ x t ) ;
p t = [ p t 1 , … , p t m ] T ∈ Δ m − 1 p_t = [p_{t1}, \ldots, p_{tm}]^T \in\Delta^{m-1} p t = [ p t 1 , … , p t m ] T ∈ Δ m − 1 is the model output, representing discrete decisions (p t = e k \mathbf{p}_t = \mathbf{e}_k p t = e k , the same one-hot construction as e j \mathbf{e}_j e j above, but with the 1 in the predicted -class position k k k ) or calibrated posterior probabilities.
Let Y 1 : t = [ y 1 , … , y t ] T ∈ R t × m \mathbf{Y}_{1:t} = [\mathbf{y}_1, \ldots, \mathbf{y}_t]^T \in\mathbb{R}^{t \times m} Y 1 : t = [ y 1 , … , y t ] T ∈ R t × m and P 1 : t = [ p 1 , … , p t ] T ∈ R t × m \mathbf{P}_{1:t} = [\mathbf{p}_1, \ldots, \mathbf{p}_t]^T \in\mathbb{R}^{t \times m} P 1 : t = [ p 1 , … , p t ] T ∈ R t × m denote the accumulated label and prediction matrices up to time t t t . In stationary batch evaluation, the sample reduction operator aggregates instances uniformly via C = Y T P = ∑ i = 1 n y i p i T C = \mathbf{Y}^T\mathbf{P} = \sum_{i=1}^{n}\mathbf{y}_i\mathbf{p}_i^T C = Y T P = ∑ i = 1 n y i p i T .
In non-stationary streams, we formalize temporal aggregation through a diagonal temporal weighting matrix W ( t ) = diag ( w 1 ( t ) , w 2 ( t ) , … , w t ( t ) ) ∈ R t × t \mathbf{W}(t) = \operatorname{diag}(w_1(t), w_2(t), \ldots, w_t(t)) \in\mathbb{R}^{t \times t} W ( t ) = diag ( w 1 ( t ) , w 2 ( t ) , … , w t ( t )) ∈ R t × t with W ( t ) ≥ 0 \mathbf{W}(t) \ge0 W ( t ) ≥ 0 (i.e., w k ( t ) ≥ 0 w_k(t) \ge0 w k ( t ) ≥ 0 ), normalized such that Tr ( W ( t ) ) = ∑ k = 1 t w k ( t ) = 1 \operatorname{Tr}(\mathbf{W}(t)) = \sum_{k=1}^{t}w_k(t) = 1 Tr ( W ( t )) = ∑ k = 1 t w k ( t ) = 1 (exactly for the sliding window once it has filled, t ≥ W t \ge W t ≥ W , with W W W the window size, a scalar that is not the weighting matrix W ( t ) \mathbf{W}(t) W ( t ) ; the exponential-fading realization below satisfies it asymptotically, Tr ( W ( t ) ) = 1 − α t → 1 \operatorname{Tr}(\mathbf{W}(t)) = 1 - \alpha^t \to1 Tr ( W ( t )) = 1 − α t → 1 , and the residual mass α t \alpha^t α t is accounted for in Proposition 3).
Definition 1 (The Temporal Reduction Operator Σ t \Sigma_t Σ t ) The temporal reduction operator Σ t \Sigma_t Σ t maps the historical matrix trajectory ( Y 1 : t , P 1 : t ) (\mathbf{Y}_{1:t}, \mathbf{P}_{1:t}) ( Y 1 : t , P 1 : t ) into the time-aggregated contingency matrix C ( t ) ∈ R m × m C(t) \in\mathbb{R}^{m \times m} C ( t ) ∈ R m × m (with C ( t ) ≥ 0 C(t) \ge0 C ( t ) ≥ 0 ) via the weighted bilinear form:
C ( t ) = Σ t ( Y 1 : t , P 1 : t ) = Y 1 : t T W ( t ) P 1 : t = ∑ k = 1 t w k ( t ) y k p k T (1) C(t) = \Sigma_t(\mathbf{Y}_{1:t}, \mathbf{P}_{1:t}) = \mathbf{Y}_{1:t}^{T}\mathbf{W}(t)\mathbf{P}_{1:t} = \sum_{k=1}^{t}w_k(t)\mathbf{y}_k\mathbf{p}_k^T \tag*{(1)} C ( t ) = Σ t ( Y 1 : t , P 1 : t ) = Y 1 : t T W ( t ) P 1 : t = k = 1 ∑ t w k ( t ) y k p k T (1)
In classification evaluation, performance metrics are computed by reducing data along specific dimensions or axes. In the static indicator matrix framework ([24 ] ), three primary reduction operators govern this process: (i) the sample operator Σ n \Sigma_n Σ n sums across individual data instances to form contingency tables; (ii) the macro operator Σ m \Sigma_m Σ m averages per-class metrics to produce an unweighted, balanced summary; and (iii) the micro operator Σ 1 \Sigma_1 Σ 1 pools all class cells globally before computing a single overall rate. In dynamic streaming environments, the new operator Σ t \Sigma_t Σ t introduces the temporal axis . The operator Σ n \Sigma_n Σ n weights all past samples equally, which assumes an unchanging world, and Σ t \Sigma_t Σ t weights them by recency. Thus Σ t \Sigma_t Σ t generalizes Σ n \Sigma_n Σ n : both build C ( t ) C(t) C ( t ) from the raw instance stream and differ only in whether the weighting is uniform or time-dependent. It is not a fourth operator composed alongside it, which is why only ( Σ 1 , Σ m ) (\Sigma_1, \Sigma_m) ( Σ 1 , Σ m ) appear in the composition tuples of § 3.2 onward. By progressively fading out stale historical observations (via fading parameter α \alpha α ) or restricting focus to a recent moving window (W W W ), Σ t \Sigma_t Σ t continuously reflects the model’s present health while composing with spatial class reductions ( Σ 1 , Σ m ) (\Sigma_1, \Sigma_m) ( Σ 1 , Σ m ) .
The two canonical stream weighting matrices are:
Exponential fading (Σ t α \Sigma_t^\alpha Σ t α ) assigns the exponentially decaying weights w k ( t ) = ( 1 − α ) α t − k w_k(t) = (1 - \alpha)\alpha^{t-k} w k ( t ) = ( 1 − α ) α t − k for a fading parameter α ∈ ( 0 , 1 ) \alpha\in(0, 1) α ∈ ( 0 , 1 ) . This yields the recursive update:
C α ( t ) = α C α ( t − 1 ) + ( 1 − α ) y t p t T , n e f f = 1 1 − α (2) C_\alpha(t) = \alpha C_\alpha(t-1) + (1-\alpha)\mathbf{y}_t\mathbf{p}_t^T,\qquad n_{\mathrm{eff}} = \frac{1}{1-\alpha} \tag*{(2)} C α ( t ) = α C α ( t − 1 ) + ( 1 − α ) y t p t T , n eff = 1 − α 1 (2)
The implementation stores the unnormalised state C ~ α = C α / ( 1 − α ) \widetilde{C}_{\alpha}=C_{\alpha}/(1-\alpha) C α = C α / ( 1 − α ) , updated as α C ~ α + y t p t T \alpha\widetilde{C}_{\alpha}+\mathbf{y}_{t}\mathbf{p}_{t}^{T} α C α + y t p t T ; every metric is a ratio of cells and is the same under both conventions, but statements that read a cell as a probability use the normalised state. Here n e f f n_{\mathrm{eff}} n eff is the memory horizon of the weights; the effective sample size that governs variance is ( 1 + α ) / ( 1 − α ) (1+\alpha)/(1-\alpha) ( 1 + α ) / ( 1 − α ) (Proposition 3). As an example, for two classes and α = 0.9 \alpha=0.9 α = 0.9 , after a correct prediction of class 1 the state C α C_{\alpha} C α gains 0.1 in the cell ( 1 , 1 ) (1,1) ( 1 , 1 ) and every older cell is multiplied by 0.9; the recall of class 1 is TP/(TP + FN) of the resulting cells, a weighted average of the recent outcomes of that class.
The sliding window ( Σ t W ) (\Sigma_{t}^{W}) ( Σ t W ) assigns uniform weights over a moving historical horizon of length W ∈ N + W\in\mathbb{N}^{+} W ∈ N + with weighting matrix W ( t ) = 1 W diag ( 0 t − W , 1 W ) \mathbf{W}(t)=\frac{1}{W}\operatorname{diag}(\mathbf{0}_{t-W},\mathbf{1}_{W}) W ( t ) = W 1 diag ( 0 t − W , 1 W ) . For t ≥ W t\ge W t ≥ W this yields the windowed aggregation, whose recursive form holds for t > W t>W t > W (at t = W t=W t = W no instance exits) (before the window fills, the state is the sum of the t t t instances divided by W W W , and ratios are unaffected):
C W ( t ) = 1 W ∑ k = 0 W − 1 y t − k p t − k T = C W ( t − 1 ) + 1 W ( y t p t T − y t − W p t − W T ) (3) C_{W}(t)=\frac{1}{W}\sum_{k=0}^{W-1}\mathbf{y}_{t-k}\mathbf{p}_{t-k}^{T}=C_{W}(t-1)+\frac{1}{W}\left(\mathbf{y}_{t}\mathbf{p}_{t}^{T}-\mathbf{y}_{t-W}\mathbf{p}_{t-W}^{T}\right) \tag*{(3)} C W ( t ) = W 1 k = 0 ∑ W − 1 y t − k p t − k T = C W ( t − 1 ) + W 1 ( y t p t T − y t − W p t − W T ) (3)
Example 1 (Running example: the stream and its temporal state) Throughout the paper we follow one stream of 8 instances and m = 3 m=3 m = 3 classes A , B , C A,B,C A , B , C , with true labels A B A C B A B B A\,B\,A\,C\,B\,A\,B\,B A B A C B A B B and predictions A B B C B A C B A\,B\,B\,C\,B\,A\,C\,B A B B C B A C B , so that the classifier errs at t = 3 t=3 t = 3 (A A A predicted as B B B ) and at t = 7 t=7 t = 7 (B B B predicted as C C C ). With exponential fading α = 1 2 \alpha=\frac{1}{2} α = 2 1 the state after the first four instances is
C α ( 4 ) = ( 1 16 1 4 0 0 1 8 0 0 0 1 2 ) , total mass 1 − α 4 = 15 16 . C_{\alpha}(4)=\begin{pmatrix}\frac{1}{16} & \frac{1}{4} & 0 \\ 0 & \frac{1}{8} & 0 \\ 0 & 0 & \frac{1}{2}\end{pmatrix},\qquad\text{total mass }1-\alpha^{4}=\frac{15}{16}. C α ( 4 ) = 16 1 0 0 4 1 8 1 0 0 0 2 1 , total mass 1 − α 4 = 16 15 .
With a sliding window W = 4 W=4 W = 4 the state at t = 8 t=8 t = 8 covers instances 5 to 8,
C W ( 8 ) = ( 1 4 0 0 0 1 2 1 4 0 0 0 ) . C_{W}(8)=\begin{pmatrix}\frac{1}{4} & 0 & 0 \\ 0 & \frac{1}{2} & \frac{1}{4} \\ 0 & 0 & 0\end{pmatrix}. C W ( 8 ) = 4 1 0 0 0 2 1 0 0 4 1 0 .
Appendix B lists every intermediate value of the running example, and the script experiments/running_example.py reproduces them.
Figure 2 summarises the architecture: the temporal state, the two evaluation branches built on it (functional reductions, § 3.2 , and structural per-class projections, § 3.3 ) and the theorem that relates them (Theorem 1, § 3.4 ).
Both weightings give non-negative states through the bilinear form (1) and keep every downstream composition and the decomposability property. The choice between C α ( t ) C_{\alpha}(t) C α ( t ) and C W ( t ) C_{W}(t) C W ( t ) sets the memory profile and the responsiveness to drift:
The sliding window C W ( t ) C_{W}(t) C W ( t ) has a finite horizon over exactly the last W W W observations, so it keeps no memory of concepts older than W W W steps. It needs a FIFO buffer of size O ( W ⋅ m ) O(W\cdot m) O ( W ⋅ m ) to subtract exiting samples, and its step-like impulse response produces abrupt metric shifts when past bursts leave the window.
Exponential fading C α ( t ) C_\alpha(t) C α ( t ) forgets continuously with memory horizon n e f f = 1 1 − α n_{\mathrm{eff}}=\frac{1}{1-\alpha} n eff = 1 − α 1 , uses O ( m 2 ) O(m^2) O ( m 2 ) space and time per update, and stores no historical instances. Its trajectories are smooth and have no boundary artifacts.
Composition Algebra with Core Reduction Operators
Having established the global temporal matrix C ( t ) C(t) C ( t ) as the streaming state representation, we formalize how the temporal operator Σ t \Sigma_t Σ t composes functionally with the spatial reduction operators of the core framework (Σ 1 , Σ m \Sigma_1,\Sigma_m Σ 1 , Σ m ) to generate scalar streaming evaluations. Each reduction operator targets a distinct analytical goal in data stream monitoring:
The micro-temporal composition (Σ 1 ∘ Σ t \Sigma_1\circ\Sigma_t Σ 1 ∘ Σ t ) pools the m m m one-vs-rest tables S j C ( t ) S j T S_jC(t)S_j^{\mathsf{T}} S j C ( t ) S j T (§ 3.3 ) into one table over time before evaluating the scalar metric M M M once:
( Σ 1 ∘ Σ t M ) ( t ) = M ( ∑ j = 1 m S j C ( t ) S j T ) (4) (\Sigma_1\circ\Sigma_t M)(t)=M\left(\sum_{j=1}^{m}S_jC(t)S_j^{\mathsf{T}}\right) \tag*{(4)} ( Σ 1 ∘ Σ t M ) ( t ) = M ( j = 1 ∑ m S j C ( t ) S j T ) (4)
Every arrival contributes equally to the total cell mass, so this composition tracks the overall service level, which suits settings where an error costs the same whatever the class. A drop in a minority class can be masked if the majority class stays accurate. The pooled accuracy is the accuracy of the pooled one-vs-rest cells, 1 − 2 ( 1 − a c c ) / m 1-2(1-\mathrm{acc})/m 1 − 2 ( 1 − acc ) / m for multiclass accuracy a c c \mathrm{acc} acc , not multiclass accuracy itself.
The macro-temporal composition (Σ m ∘ Σ t \Sigma_m \circ\Sigma_t Σ m ∘ Σ t ) evaluates the scalar metric M M M on each class and averages the m m m values without weights:
( Σ m ∘ Σ t M ) ( t ) = 1 m ∑ j = 1 m M ( C j ( t ) ) (5) (\Sigma_m \circ\Sigma_t M)(t) = \frac{1}{m}\sum_{j=1}^{m} M(C_j(t)) \tag*{(5)} ( Σ m ∘ Σ t M ) ( t ) = m 1 j = 1 ∑ m M ( C j ( t )) (5)
The macro operator gives each class the weight 1 / m 1/m 1/ m whatever its prevalence at the time, so a degradation on a rare or emerging class is not hidden by accurate predictions on a prevalent one.
Multiclass Selection Matrices and Per-Class Projections
In contrast to the functional composition algebra of § 3.2 , which produces scalar summaries, evaluating non-linear metrics and isolating drift requires the structure of the state matrix itself. While the global temporal state C ( t ) ∈ R m × m C(t) \in\mathbb{R}^{m \times m} C ( t ) ∈ R m × m captures the full joint allocation of predictions and ground truth across all m m m classes, standard classification measures (such as Recall, Specificity, Precision, and F1) are intrinsically defined on binary 2 × 2 2 \times2 2 × 2 contingency tables. Furthermore, effective operational monitoring in data streams requires isolating which classes are experiencing concept drift.
To achieve this without procedural slicing, structural per-class projections are formalized via linear selection matrices S j ∈ R 2 × m S_j \in\mathbb{R}^{2 \times m} S j ∈ R 2 × m defined for each class j ∈ { 1 , … , m } j \in\{1,\ldots,m\} j ∈ { 1 , … , m } :
S j = [ e j T 1 m T − e j T ] (6) S_j =
\begin{bmatrix}
e_j^T \\
\mathbf{1}_m^T-e_j^T
\end{bmatrix} \tag*{(6)} S j = [ e j T 1 m T − e j T ] (6)
where e j e_j e j is the j j j -th standard basis vector and 1 m \mathbf{1}_m 1 m is the all-ones vector. The 2 × 2 2 \times2 2 × 2 per-class temporal contingency matrix for class j j j at time t t t is obtained via the matrix congruence transformation:
C j ( t ) = S j C ( t ) S j T = S j ( Y 1 : t T W ( t ) P 1 : t ) S j T = [ T P j ( t ) F N j ( t ) F P j ( t ) T N j ( t ) ] (7) C_j(t) = S_j C(t) S_j^T = S_j\left(Y_{1:t}^T W(t) P_{1:t}\right)S_j^T =
\begin{bmatrix}
\mathrm{TP}_j(t) & \mathrm{FN}_j(t) \\
\mathrm{FP}_j(t) & \mathrm{TN}_j(t)
\end{bmatrix} \tag*{(7)} C j ( t ) = S j C ( t ) S j T = S j ( Y 1 : t T W ( t ) P 1 : t ) S j T = [ TP j ( t ) FP j ( t ) FN j ( t ) TN j ( t ) ] (7)
The four entries of C j ( t ) C_j(t) C j ( t ) correspond directly to the temporally discounted counts for class j j j :
T P j ( t ) = [ C ( t ) ] j j , F N j ( t ) = ∑ k ≠ j [ C ( t ) ] j k , F P j ( t ) = ∑ l ≠ j [ C ( t ) ] l j , T N j ( t ) = ∑ l ≠ j ∑ k ≠ j [ C ( t ) ] l k (8) \begin{aligned}
\mathrm{TP}_j(t) &= [C(t)]_{jj}, & \mathrm{FN}_j(t) &= \sum_{k \ne j}[C(t)]_{jk},\\
\mathrm{FP}_j(t) &= \sum_{l \ne j}[C(t)]_{lj}, & \mathrm{TN}_j(t) &= \sum_{l \ne j}\sum_{k \ne j}[C(t)]_{lk} \tag*{(8)}
\end{aligned} TP j ( t ) FP j ( t ) = [ C ( t ) ] j j , = l = j ∑ [ C ( t ) ] l j , FN j ( t ) TN j ( t ) = k = j ∑ [ C ( t ) ] j k , = l = j ∑ k = j ∑ [ C ( t ) ] l k (8)
The structural per-class projection serves two primary analytical and operational goals:
When an aggregate alarm triggers (a drop in macro-F1 or micro-accuracy), global metrics cannot identify the cause. Tracking the per-class metrics M j ( t ) = M ( C j ( t ) ) M_j(t)=M(C_j(t)) M j ( t ) = M ( C j ( t )) separates a loss of class recall, T P j ( t ) / ( T P j ( t ) + F N j ( t ) ) \mathrm{TP}_j(t)/(\mathrm{TP}_j(t)+\mathrm{FN}_j(t)) TP j ( t ) / ( TP j ( t ) + FN j ( t )) , from a rise in false alarms F P j ( t ) \mathrm{FP}_j(t) FP j ( t ) .
Remark 1 (Pairwise projections are a diagnostic, not a result) The per-class projection collapses all other classes into a single rest, so F N j ( t ) \mathrm{FN}_j(t) FN j ( t ) and F P j ( t ) \mathrm{FP}_j(t) FP j ( t ) show that class j j j is losing recall or precision but not which competing class is responsible. For a pair j , k j,k j , k the selection matrix S j k = [ e j , e k ] S_{jk} = [e_j,e_k] S j k = [ e j , e k ] extracts the confusion restricted to { j , k } \{j,k\} { j , k } . This congruence alone is not a conditional rate, because instances whose true or predicted label lies outside { j , k } \{j,k\} { j , k } must be masked from the denominator, and no analogue of Theorem 1 recombines the pairwise tables. The base framework likewise treats the One-vs-One decomposition as partial [24 ] . We do not develop S j k S_{jk} S j k here.
Algebraic Theorems and Complexity Bounds
Having structured the dual evaluation branches, we state the results on the exactness, computational cost and statistical stability of the temporal state (t → ∞ t \to\infty t → ∞ ).
Proposition 1 (Resource Complexity of Exponential Fading) The recursive fading operator Σ t α \Sigma^\alpha_t Σ t α requires O ( m 2 ) O(m^2) O ( m 2 ) memory to store C α ( t ) C_\alpha(t) C α ( t ) and O ( m 2 ) O(m^2) O ( m 2 ) floating-point operations per stream update, both independent of the stream length t t t .
Proof. Evaluating Equation (2) requires scalar multiplication α C α ( t − 1 ) \alpha C_\alpha(t-1) α C α ( t − 1 ) , outer product ( 1 − α ) y t p t T (1-\alpha)y_t p_t^{T} ( 1 − α ) y t p t T , and matrix addition (3 m 2 3m^2 3 m 2 floating-point operations). No historical tuples ( y k , p k ) (y_k,p_k) ( y k , p k ) for k < t k<t k < t are retained, which bounds the state storage by m 2 m^2 m 2 scalar values. □
Proposition 2 (Sliding-Window Resource Complexity) The sliding-window operator Σ t W \Sigma^W_t Σ t W , maintained via a FIFO queue of the W W W most recent raw observation pairs ( y k , p k ) (y_k,p_k) ( y k , p k ) , requires O ( W ⋅ m ) O(W\cdot m) O ( W ⋅ m ) memory for the queue plus the O ( m 2 ) O(m^2) O ( m 2 ) state matrix C W ( t ) C_W(t) C W ( t ) , and executes each update in O ( m 2 ) O(m^2) O ( m 2 ) floating-point operations, independent of the stream length t t t . The per-update cost is the same as for exponential fading, but the memory grows linearly in W W W .
Proof. Updating C W ( t ) = C W ( t − 1 ) + y t p t T − y t − W p t − W T C_W(t)=C_W(t-1)+y_t p_t^{T}-y_{t-W}p_{t-W}^{T} C W ( t ) = C W ( t − 1 ) + y t p t T − y t − W p t − W T requires: (i) enqueuing ( y t , p t ) (y_t,p_t) ( y t , p t ) and dequeuing ( y t − W , p t − W ) (y_{t-W},p_{t-W}) ( y t − W , p t − W ) from the FIFO queue, both O ( 1 ) O(1) O ( 1 ) operations independent of W W W ; (ii) forming the new outer product and subtracting the evicted one, 2 m 2 2m^2 2 m 2 floating-point operations. Unlike exponential fading, which discards each instance immediately, the queue must retain the W W W most recent raw pairs to know what to subtract when they exit the window, giving O ( W ⋅ m ) O(W\cdot m) O ( W ⋅ m ) additional memory that grows with W W W , as measured in Table 24 . □
Table 24. Throughput and memory on S9 (300,000 instances, m = 2 m = 2 m = 2 , 7 repetitions). Analytic memory is the buffer of the window or the state of fading; measured memory is the allocation in use after filling the window, traced by tracemalloc.
Both operators thus meet the same O ( m 2 ) O(m^2) O ( m 2 ) per-update time bound, which does not depend on t t t , and differ only in memory profile. What makes either a safe choice for the aggregation machinery that follows is that both preserve linear decomposability across time, established next.
Theorem 1 (Dynamic Temporal Preservation of Linear Decomposability). Let M = ⟨ a , v ⟩ ⟨ b , v ⟩ M = \frac{\langle a,v\rangle}{\langle b,v\rangle} M = ⟨ b , v ⟩ ⟨ a , v ⟩ be a linear-fractional performance measure, a ratio of two linear functions of the four cells T P TP T P , F N FN F N , F P FP F P , T N TN T N of a class table (accuracy, recall, precision and F1 are of this form), with coefficient vectors satisfying 0 ≤ a ≤ b 0 \le a \le b 0 ≤ a ≤ b entrywise, and let v m i c r o ( t ) = ∑ j v j ( t ) v_{\mathrm{micro}}(t) = \sum_j v_j(t) v micro ( t ) = ∑ j v j ( t ) with ⟨ b , v m i c r o ( t ) ⟩ > 0 \langle b,v_{\mathrm{micro}}(t)\rangle> 0 ⟨ b , v micro ( t )⟩ > 0 . Under any nonnegative temporal weighting of nonnegative label and prediction vectors, in particular exponential fading Σ t E \Sigma_t^{\mathrm{E}} Σ t E and sliding window Σ t W \Sigma_t^{\mathrm{W}} Σ t W , the micro-temporal composition equals the denominator-weighted macro-temporal composition at every timestamp t t t , where classes with ⟨ b , v j ( t ) ⟩ = 0 \langle b,v_j(t)\rangle= 0 ⟨ b , v j ( t )⟩ = 0 get weight 0 and are omitted:
( Σ 1 ∘ Σ t M ) ( t ) = ∑ j = 1 m ω j ( t ) M ( S j C ( t ) S j T ) , where ω j ( t ) = ⟨ b , v j ( t ) ⟩ ∑ l = 1 m ⟨ b , v l ( t ) ⟩ (9) (\Sigma_1 \circ\Sigma_t M)(t) = \sum_{j=1}^{m}\omega_j(t)M\left(S_jC(t)S_j^{T}\right), \qquad\text{where }\omega_j(t) = \frac{\langle b,v_j(t)\rangle}{\sum_{l=1}^{m}\langle b,v_l(t)\rangle} \tag*{(9)} ( Σ 1 ∘ Σ t M ) ( t ) = j = 1 ∑ m ω j ( t ) M ( S j C ( t ) S j T ) , where ω j ( t ) = ∑ l = 1 m ⟨ b , v l ( t )⟩ ⟨ b , v j ( t )⟩ (9)
Proof. Let v j ( t ) = vec ( S j C ( t ) S j T ) = [ T P j ( t ) , F N j ( t ) , F P j ( t ) , T N j ( t ) ] T v_j(t) = \operatorname{vec}\left(S_jC(t)S_j^{T}\right) = [TP_j(t),FN_j(t),FP_j(t),TN_j(t)]^{T} v j ( t ) = vec ( S j C ( t ) S j T ) = [ T P j ( t ) , F N j ( t ) , F P j ( t ) , T N j ( t ) ] T denote the vectorized per-class contingency cells. Because Σ t \Sigma_t Σ t is a linear operator on the space of matrices, it commutes with the linear selection matrices S j S_j S j and global micro-summation v m i c r o ( t ) = ∑ j = 1 m v j ( t ) v_{\mathrm{micro}}(t) = \sum_{j=1}^{m}v_j(t) v micro ( t ) = ∑ j = 1 m v j ( t ) .
The micro-temporal metric evaluated on the global pooled stream is given by:
( Σ 1 ∘ Σ t M ) ( t ) = ⟨ a , v m i c r o ( t ) ⟩ ⟨ b , v m i c r o ( t ) ⟩ = ∑ j = 1 m ⟨ a , v j ( t ) ⟩ ∑ l = 1 m ⟨ b , v l ( t ) ⟩ (10) (\Sigma_1 \circ\Sigma_t M)(t) = \frac{\langle a,v_{\mathrm{micro}}(t)\rangle}{\langle b,v_{\mathrm{micro}}(t)\rangle} = \frac{\sum_{j=1}^{m}\langle a,v_j(t)\rangle}{\sum_{l=1}^{m}\langle b,v_l(t)\rangle} \tag*{(10)} ( Σ 1 ∘ Σ t M ) ( t ) = ⟨ b , v micro ( t )⟩ ⟨ a , v micro ( t )⟩ = ∑ l = 1 m ⟨ b , v l ( t )⟩ ∑ j = 1 m ⟨ a , v j ( t )⟩ (10)
A class with ⟨ b , v j ( t ) ⟩ = 0 \langle b,v_j(t)\rangle= 0 ⟨ b , v j ( t )⟩ = 0 also has ⟨ a , v j ( t ) ⟩ = 0 \langle a,v_j(t)\rangle= 0 ⟨ a , v j ( t )⟩ = 0 , because a ≤ b a \le b a ≤ b and v j ( t ) ≥ 0 v_j(t) \ge0 v j ( t ) ≥ 0 , so it contributes to neither sum. Multiplying and dividing each remaining summand by its positive local denominator ⟨ b , v j ( t ) ⟩ \langle b,v_j(t)\rangle ⟨ b , v j ( t )⟩ :
( Σ 1 ∘ Σ t M ) ( t ) = ∑ j = 1 m ( ⟨ b , v j ( t ) ⟩ ∑ l = 1 m ⟨ b , v l ( t ) ⟩ ) ( ⟨ a , v j ( t ) ⟩ ⟨ b , v j ( t ) ⟩ ) = ∑ j = 1 m ω j ( t ) M j ( t ) (11) (\Sigma_1 \circ\Sigma_t M)(t) = \sum_{j=1}^{m}\left(\frac{\langle b,v_j(t)\rangle}{\sum_{l=1}^{m}\langle b,v_l(t)\rangle}\right)\left(\frac{\langle a,v_j(t)\rangle}{\langle b,v_j(t)\rangle}\right) = \sum_{j=1}^{m}\omega_j(t)M_j(t) \tag*{(11)} ( Σ 1 ∘ Σ t M ) ( t ) = j = 1 ∑ m ( ∑ l = 1 m ⟨ b , v l ( t )⟩ ⟨ b , v j ( t )⟩ ) ( ⟨ b , v j ( t )⟩ ⟨ a , v j ( t )⟩ ) = j = 1 ∑ m ω j ( t ) M j ( t ) (11)
which establishes the equivalence for all timestamps t ≥ 1 t \ge1 t ≥ 1 . The argument uses only the linearity of C ↦ v j C \mapsto v_j C ↦ v j and the nonnegativity of the weights, so it holds for any temporal weighting and not only for the two operators of this paper. □
Theorem 1 applies to every linear-fractional measure. For instance, in stream Accuracy (a = [ 1 , 0 , 0 , 1 ] T a = [1,0,0,1]^{T} a = [ 1 , 0 , 0 , 1 ] T , b = [ 1 , 1 , 1 , 1 ] T b = [1,1,1,1]^{T} b = [ 1 , 1 , 1 , 1 ] T ), the weights ω j ( t ) = 1 / m \omega_j(t) = 1/m ω j ( t ) = 1/ m reduce to the standard uniform average; in stream Recall (a = [ 1 , 0 , 0 , 0 ] T a = [1,0,0,0]^{T} a = [ 1 , 0 , 0 , 0 ] T , b = [ 1 , 1 , 0 , 0 ] T b = [1,1,0,0]^{T} b = [ 1 , 1 , 0 , 0 ] T ), the weight ω j ( t ) \omega_j(t) ω j ( t ) equals the dynamic class prevalence P t ( Y = j ) = ∑ k [ C ( t ) ] j k P_t(Y = j) = \sum_k[C(t)]_{jk} P t ( Y = j ) = ∑ k [ C ( t ) ] j k ; and in stream Precision (a = [ 1 , 0 , 0 , 0 ] T a = [1,0,0,0]^{T} a = [ 1 , 0 , 0 , 0 ] T , b = [ 1 , 0 , 1 , 0 ] T b = [1,0,1,0]^{T} b = [ 1 , 0 , 1 , 0 ] T ), ω j ( t ) \omega_j(t) ω j ( t ) reflects the model’s positive prediction rate P t ( Y ^ = j ) = ∑ l [ C ( t ) ] l j P_t(\hat{Y} = j) = \sum_l[C(t)]_{lj} P t ( Y ^ = j ) = ∑ l [ C ( t ) ] l j .
Example 2 (Running example: pooled and per-class measures). The three tables S j C W ( 8 ) S j T S_jC_{\mathrm{W}}(8)S_j^{T} S j C W ( 8 ) S j T of the window state have ( T P j , F N j , F P j , T N j ) = ( 1 4 , 0 , 0 , 3 4 ) (TP_j,FN_j,FP_j,TN_j) = (\frac{1}{4},0,0,\frac{3}{4}) ( T P j , F N j , F P j , T N j ) = ( 4 1 , 0 , 0 , 4 3 ) , ( 1 2 , 1 4 , 0 , 1 4 ) (\frac{1}{2},\frac{1}{4},0,\frac{1}{4}) ( 2 1 , 4 1 , 0 , 4 1 ) and ( 0 , 0 , 1 4 , 3 4 ) (0,0,\frac{1}{4},\frac{3}{4}) ( 0 , 0 , 4 1 , 4 3 ) for A A A , B B B and C C C , and the pooled table is ( 3 4 , 1 4 , 1 4 , 3 4 ) (\frac{3}{4},\frac{1}{4},\frac{1}{4},\frac{3}{4}) ( 4 3 , 4 1 , 4 1 , 4 3 ) . The per-class precisions are ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) with denominators T P j + F P j = ( 1 4 , 1 2 , 1 4 ) TP_j+FP_j = (\frac{1}{4},\frac{1}{2},\frac{1}{4}) T P j + F P j = ( 4 1 , 2 1 , 4 1 ) , so the weights of Theorem 1 are ω = ( 1 4 , 1 2 , 1 4 ) \omega= (\frac{1}{4},\frac{1}{2},\frac{1}{4}) ω = ( 4 1 , 2 1 , 4 1 ) . The pooled precision is 3 4 \frac{3}{4} 4 3 and the denominator-weighted macro is 1 4 ⋅ 1 + 1 2 ⋅ 1 + 1 4 ⋅ 0 = 3 4 \frac{1}{4}\cdot1+\frac{1}{2}\cdot1+\frac{1}{4}\cdot0=\frac{3}{4} 4 1 ⋅ 1 + 2 1 ⋅ 1 + 4 1 ⋅ 0 = 4 3 , whereas the unweighted macro is 2 3 \frac{2}{3} 3 2 .
Theorem 1 also gives a class/prevalence attribution of a change in the pooled metric. When it shifts by Δ M m i c r o ( t ) = M m i c r o ( t ) − M m i c r o ( t − 1 ) \Delta M_{\mathrm{micro}}(t) = M_{\mathrm{micro}}(t) - M_{\mathrm{micro}}(t-1) Δ M micro ( t ) = M micro ( t ) − M micro ( t − 1 ) , the aggregate delta decomposes linearly into two distinct operational sources:
Δ ( Σ 1 ∘ Σ t M ) ( t ) = ∑ j = 1 m ω ˉ j ( t ) Δ M j ( t ) + ∑ j = 1 m Δ ω j ( t ) M ˉ j ( t ) (12) \Delta(\Sigma_1 \circ\Sigma_t M)(t) = \sum_{j=1}^{m} \bar{\omega}_j(t)\,\Delta M_j(t) + \sum_{j=1}^{m} \Delta\omega_j(t)\,\bar{M}_j(t) \tag*{(12)} Δ ( Σ 1 ∘ Σ t M ) ( t ) = j = 1 ∑ m ω ˉ j ( t ) Δ M j ( t ) + j = 1 ∑ m Δ ω j ( t ) M ˉ j ( t ) (12)
where ω ˉ j ( t ) \bar{\omega}_j(t) ω ˉ j ( t ) and M ˉ j ( t ) \bar{M}_j(t) M ˉ j ( t ) denote mid-point values. The first term quantifies the contribution of intrinsic performance drift localized within specific classes, whereas the second term isolates the impact of prevalence drift (dynamic class prior shifts) on aggregate accuracy. A formalization of drift taxonomies, dynamic response timescales, and continuous differential Jacobian decompositions is established in § 5 .
Proposition 3 (Asymptotic Expectation and Variance Scaling) Let the pairs ( y t , p t ) (y_t, p_t) ( y t , p t ) be independent and identically distributed with population state matrix C p o p = E [ y t p t T ] C_{\mathrm{pop}} = \mathbb{E}[y_t p_t^{\mathsf{T}}] C pop = E [ y t p t T ] and elementwise variance V i n s t = Var ( y t p t T ) V_{\mathrm{inst}} = \operatorname{Var}(y_t p_t^{\mathsf{T}}) V inst = Var ( y t p t T ) (for instance, a classifier that is not updated, so that predictions do not depend on past labels). The exponential fading estimator Σ t α \Sigma_t^\alpha Σ t α satisfies:
E [ C α ( t ) ] = ( 1 − α t ) C p o p → t → ∞ C p o p , (13) \mathbb{E}[C_\alpha(t)] = (1-\alpha^t)C_{\mathrm{pop}} \xrightarrow{t\to\infty} C_{\mathrm{pop}}, \tag*{(13)} E [ C α ( t )] = ( 1 − α t ) C pop t → ∞ C pop , (13) Var ( [ C α ( t ) ] j k ) = 1 − α 1 + α ( 1 − α 2 t ) [ V i n s t ] j k → t → ∞ [ V i n s t ] j k n e s s , n e s s = 1 + α 1 − α (14) \operatorname{Var}([C_\alpha(t)]_{jk}) = \frac{1-\alpha}{1+\alpha}(1-\alpha^{2t})[V_{\mathrm{inst}}]_{jk} \xrightarrow{t\to\infty} \frac{[V_{\mathrm{inst}}]_{jk}}{n_{\mathrm{ess}}}, \qquad n_{\mathrm{ess}} = \frac{1+\alpha}{1-\alpha} \tag*{(14)} Var ([ C α ( t ) ] j k ) = 1 + α 1 − α ( 1 − α 2 t ) [ V inst ] j k t → ∞ n ess [ V inst ] j k , n ess = 1 − α 1 + α (14)
Proof. Unrolling the recurrence (2) yields C α ( t ) = ( 1 − α ) ∑ s = 0 t − 1 α s y t − s p t − s T C_\alpha(t) = (1-\alpha)\sum_{s=0}^{t-1}\alpha^s y_{t-s}p_{t-s}^{\mathsf{T}} C α ( t ) = ( 1 − α ) ∑ s = 0 t − 1 α s y t − s p t − s T . Taking expectations gives E [ C α ( t ) ] = ( 1 − α ) 1 − α t 1 − α C p o p = ( 1 − α t ) C p o p \mathbb{E}[C_\alpha(t)] = (1-\alpha)\frac{1-\alpha^t}{1-\alpha}C_{\mathrm{pop}} = (1-\alpha^t)C_{\mathrm{pop}} E [ C α ( t )] = ( 1 − α ) 1 − α 1 − α t C pop = ( 1 − α t ) C pop . By independence the variance is
Var ( [ C α ( t ) ] j k ) = ( 1 − α ) 2 ∑ s = 0 t − 1 α 2 s [ V i n s t ] j k = ( 1 − α ) 2 ( 1 − α 2 t 1 − α 2 ) [ V i n s t ] j k , (15) \operatorname{Var}([C_\alpha(t)]_{jk}) = (1-\alpha)^2\sum_{s=0}^{t-1}\alpha^{2s}[V_{\mathrm{inst}}]_{jk} = (1-\alpha)^2\left(\frac{1-\alpha^{2t}}{1-\alpha^2}\right)[V_{\mathrm{inst}}]_{jk}, \tag*{(15)} Var ([ C α ( t ) ] j k ) = ( 1 − α ) 2 s = 0 ∑ t − 1 α 2 s [ V inst ] j k = ( 1 − α ) 2 ( 1 − α 2 1 − α 2 t ) [ V inst ] j k , (15)
and 1 − α 2 = ( 1 − α ) ( 1 + α ) 1-\alpha^2 = (1-\alpha)(1+\alpha) 1 − α 2 = ( 1 − α ) ( 1 + α ) gives the stated form. □
Proposition 3 gives the variance half of a bias-variance trade-off (the bias half is the tracking lag of § 5.1 ). A larger α \alpha α gives a lower-variance estimate and a slower response to drift, and a smaller α \alpha α the opposite.
sample autocorrelation up to lag 1,500 is 8.8 and 1.04 for the error indicator. For the class-time sequences that the detector of § 5.4 averages it is 20.8 (recall) and 13.3 (specificity) on Elec2, and 2.4 and 1.6 on Airlines, against 5.3, 4.0, 3.1 and 2.4 from the AR(1) formula with the lag-one autocorrelation. On Elec2 the sample variance of the fading estimate of the error indicator is 9.0 times the value for independent entries, against 8.8 from Eq. (16) . The factor measures any variation of the mean that the moving average leaves in, so on a stream with real drift it includes that drift, and we did not separate the two.
Explicit Auditing of Zero-Division Voids
In data streams with strong class imbalance or emerging classes (P t ( Y = j ) ≪ 1 P_t(Y = j) \ll1 P t ( Y = j ) ≪ 1 ), evaluation windows frequently experience intervals with zero class support (T P j ( t ) + F N j ( t ) = 0 \mathrm{TP}_j(t) + \mathrm{FN}_j(t) = 0 TP j ( t ) + FN j ( t ) = 0 ) or zero positive predictions (T P j ( t ) + F P j ( t ) = 0 \mathrm{TP}_j(t) + \mathrm{FP}_j(t) = 0 TP j ( t ) + FP j ( t ) = 0 ). In such states, metric denominators ⟨ b , v j ( t ) ⟩ = 0 \langle b, v_j(t)\rangle= 0 ⟨ b , v j ( t )⟩ = 0 create mathematical singularities.
Conventional batch libraries (such as scikit-learn) typically apply silent default substitutions (e.g., zero_division = 0), which distort stream evaluation: a rare class that does not appear in a moving window is scored as 0.0 without notice and can trigger false drift alarms in macro-aggregated indicators.
To prevent silent distortion while maintaining uninterrupted streaming pipelines, the framework formalizes a dynamic support indicator vector u ( t ) ∈ { 0 , 1 } m u(t) \in\{0,1\}^{m} u ( t ) ∈ { 0 , 1 } m , where, without latency, u j ( t ) = I [ ⟨ b , v j ( t ) ⟩ > ε ] u_j(t) = \mathbb{I}[\langle b, v_j(t)\rangle> \varepsilon] u j ( t ) = I [⟨ b , v j ( t )⟩ > ε ] (the case with latency is treated after Example 3), with ε = 0 \varepsilon= 0 ε = 0 under a sliding window and a small positive tolerance under exponential fading, where cell masses decay but never reach exactly zero. The macro-temporal composition Σ m ∘ Σ t \Sigma_m \circ\Sigma_t Σ m ∘ Σ t supports three auditable policies:
With policy = exclude the macro composition averages metrics over the classes with non-zero support in the current temporal state (and is undefined, as for nan, if no class has support):
( Σ m ∘ Σ t M ) e x c l u d e ( t ) = 1 ∑ j = 1 m u j ( t ) ∑ j : u j ( t ) = 1 M ( C j ( t ) ) (17) (\Sigma_m \circ\Sigma_t M)_{\mathrm{exclude}}(t) = \frac{1}{\sum_{j=1}^{m} u_j(t)} \sum_{j:u_j(t)=1} M(C_j(t)) \tag*{(17)} ( Σ m ∘ Σ t M ) exclude ( t ) = ∑ j = 1 m u j ( t ) 1 j : u j ( t ) = 1 ∑ M ( C j ( t )) (17)
With policy = zero an unobserved class gets 0.0, a conservative assumption:
( Σ m ∘ Σ t M ) z e r o ( t ) = 1 m ∑ j = 1 m u j ( t ) M ( C j ( t ) ) (18) (\Sigma_m \circ\Sigma_t M)_{\mathrm{zero}}(t) = \frac{1}{m} \sum_{j=1}^{m} u_j(t)M(C_j(t)) \tag*{(18)} ( Σ m ∘ Σ t M ) zero ( t ) = m 1 j = 1 ∑ m u j ( t ) M ( C j ( t )) (18)
With policy = nan the composition emits NaN whenever any class has undefined support, which forces explicit handling upstream.
In all cases, the framework emits an explicit diagnostic audit tuple ( u ( t ) , m a c t i v e ( t ) ) (u(t), m_{\mathrm{active}}(t)) ( u ( t ) , m active ( t )) , where m a c t i v e ( t ) = ∑ j = 1 m u j ( t ) m_{\mathrm{active}}(t) = \sum_{j=1}^{m} u_j(t) m active ( t ) = ∑ j = 1 m u j ( t ) is the number of classes with non-zero support (the same quantity already appearing as the denominator of Eq. (17) ), alongside every evaluation update, ensuring full transparency in automated monitoring dashboards.
Example 3 (Running example: a void) In the window state of Example 1 no instance of class C C C is true, so T P C + F N C = 0 \mathrm{TP}_{C}+\mathrm{FN}_{C}=0 TP C + FN C = 0 and R e c a l l C \mathrm{Recall}_{C} Recall C is 0 / 0 0/0 0/0 . The support indicator is u = ( 1 , 1 , 0 ) \mathbf{u}=(1,1,0) u = ( 1 , 1 , 0 ) and m a c t i v e = 2 m_{\mathrm{active}}=2 m active = 2 . The per-class recalls are ( 1 , 2 3 , undefined ) (1,\frac{2}{3},\text{undefined}) ( 1 , 3 2 , undefined ) , so the macro recall is 5 6 \frac{5}{6} 6 5 under exclude , 5 9 \frac{5}{9} 9 5 under zero and undefined under nan. The pooled recall is 3 4 \frac{3}{4} 4 3 , equal to the weighted macro with weights ( 1 4 , 3 4 , 0 ) (\frac{1}{4},\frac{3}{4},0) ( 4 1 , 4 3 , 0 ) that omit C C C (Theorem 1).
Under verification latency or censoring (§ 4 ) the state C ( t ) C(t) C ( t ) also holds interim estimates of the unverified instances (the model’s calibrated class probabilities standing in for the labels that have not arrived, § 4.2 ), which are spread over the rows of every class the model finds plausible, so a class can have mass in C ( t ) C(t) C ( t ) without an instance of it in the window. We therefore distinguish the interim support u j i n t ( t ) = I [ ⟨ b , v j ( C ( t ) ) ⟩ > ε ] u_j^{\mathrm{int}}(t)=\mathbb{I}[\langle b,v_j(C(t))\rangle>\varepsilon] u j int ( t ) = I [⟨ b , v j ( C ( t ))⟩ > ε ] and the verified support u j v e r ( t ) = I [ ⟨ b , v j ( C v e r i f i e d ( t ) ) ⟩ > ε ] u_j^{\mathrm{ver}}(t)=\mathbb{I}[\langle b,v_j(C_{\mathrm{verified}}(t))\rangle>\varepsilon] u j ver ( t ) = I [⟨ b , v j ( C verified ( t ))⟩ > ε ] , and the coverage κ j ( t ) \kappa_j(t) κ j ( t ) , the share of the denominator ⟨ b , v j ( C ( t ) ) ⟩ \langle b,v_j(C(t))\rangle ⟨ b , v j ( C ( t ))⟩ that comes from verified instances. By marginal prediction consistency (Eq. (29) ) the column sums of C ( t ) C(t) C ( t ) do not depend on the interim estimates. If the denominator is a combination of the prediction-side sums T P j + F P j \mathrm{TP}_j+\mathrm{FP}_j TP j + FP j and F N j + T N j \mathrm{FN}_j+\mathrm{TN}_j FN j + TN j (precision, accuracy), u j i n t u_j^{\mathrm{int}} u j int is exact. If it involves the label side (recall, specificity), only u j v e r u_j^{\mathrm{ver}} u j ver is safe. The policies below use u j = u j i n t u_j=u_j^{\mathrm{int}} u j = u j int for the first kind and u j = u j v e r u_j=u_j^{\mathrm{ver}} u j = u j ver for the second, which coincide without latency, and the audit tuple reports ( u j v e r , u j i n t , κ j ) (u_j^{\mathrm{ver}},u_j^{\mathrm{int}},\kappa_j) ( u j ver , u j int , κ j ) . A value computed for a class with 0 < κ j < 1 0<\kappa_j<1 0 < κ j < 1 is an estimate, and one with κ j = 0 \kappa_j=0 κ j = 0 is not reported as a measurement.
A practical question these policies raise immediately is how often they trigger for a given class and a given choice of W W W or α \alpha α . A practitioner needs this information before deployment, not only as a post-hoc diagnostic.
Proposition 4 (Undefined-Window Probability Under Stationary Arrivals) Let class j j j arrive i.i.d. with per-instance probability p j = Pr T ( Y = j ) p_j=\Pr_T(Y=j) p j = Pr T ( Y = j ) , stationary over the relevant horizon. Under a sliding window of size W W W (steady state, t ≥ W t\ge W t ≥ W ), the probability that u j ( t ) = 0 u_j(t)=0 u j ( t ) = 0 , that is, that R e c a l l j ( t ) \mathrm{Recall}_j(t) Recall j ( t ) is undefined because no instance of class j j j occurred in the window, is exactly
P ( u j ( t ) = 0 ) = ( 1 − p j ) W . (19) P(u_j(t)=0)=(1-p_j)^W. \tag*{(19)} P ( u j ( t ) = 0 ) = ( 1 − p j ) W . (19) Under exponential fading with a mass tolerance ε \varepsilon ε and t ≥ s ∗ t\ge s^* t ≥ s ∗ , ( 1 − p j ) s ε ≤ P ( u j ( t ) = 0 ) ≤ ( 1 − p j ) s ∗ (1-p_j)^{s_\varepsilon}\le P(u_j(t)=0)\le(1-p_j)^{s^*} ( 1 − p j ) s ε ≤ P ( u j ( t ) = 0 ) ≤ ( 1 − p j ) s ∗ , where s ∗ = min { s : ( 1 − α ) α s ≤ ε } = O ( n e f f log 1 n e f f ε ) s^*=\min\{s:(1-\alpha)\alpha^s\le\varepsilon\}=O\left(n_{\mathrm{eff}}\log\frac{1}{n_{\mathrm{eff}}\varepsilon}\right) s ∗ = min { s : ( 1 − α ) α s ≤ ε } = O ( n eff log n eff ε 1 ) is the first age at which the weight of a single arrival does not exceed ε \varepsilon ε (the eviction age of Eq. (33) is defined with a strict inequality and differs only when the weight equals ε \varepsilon ε ), and s ε = ⌈ ln ( 1 / ε ) / ln ( 1 / α ) ⌉ s_\varepsilon=\lceil\ln(1/\varepsilon)/\ln(1/\alpha)\rceil s ε = ⌈ ln ( 1/ ε ) / ln ( 1/ α )⌉ is the number of silent steps after which the whole mass of the class is at most $\varepsilon.
Proof. Under a sliding window, u j ( t ) = 0 u_j(t)=0 u j ( t ) = 0 iff none of the W W W i.i.d. arrivals in ( t − W , t ] (t-W,t] ( t − W , t ] has true label j j j , which by independence has probability ( 1 − p j ) W (1-p_j)^W ( 1 − p j ) W exactly. Under fading with eviction, u j ( t ) = 0 u_j(t)=0 u j ( t ) = 0 once the most recent class-j j j arrival is older than s ∗ s^* s ∗ steps (Eq. (33) ); the same independence argument gives the two bounds: an arrival within the last s ∗ s^* s ∗ steps keeps the mass above ε \varepsilon ε , and no arrival for s ε s_\varepsilon s ε steps brings it to at most ε \varepsilon ε . □ \square □
Corollary 1 (Design rule for the undefined-window rate) Sizing a streaming parameter to guarantee a target confidence level is the same design principle underlying adaptive windowing
schemes such as ADWIN [2 ] , applied here to the undefined-window rate specifically: to keep it below a target tolerance δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , Eq. (19) requires
W ≥ ln ( 1 / δ ) − ln ( 1 − p j ) ≈ ln ( 1 / δ ) p j (the approximation tightening as p j → 0 ), (20) W \ge\frac{\ln(1/\delta)}{-\ln(1-p_j)} \approx\frac{\ln(1/\delta)}{p_j} \qquad\text{(the approximation tightening as } p_j \to0\text{),} \tag*{(20)} W ≥ − ln ( 1 − p j ) ln ( 1/ δ ) ≈ p j ln ( 1/ δ ) (the approximation tightening as p j → 0 ), (20)
and under fading the upper bound of Proposition 4 gives the corresponding rule with s ∗ s^* s ∗ in place of W W W .
Corollary 2 (Undefined-window probability with latency) Let the delays be independent of the arrivals and of the class, with F ( s ) = P ( Δ ≤ s ) F(s) = P(\Delta\le s) F ( s ) = P ( Δ ≤ s ) , and let a label be requested with probability b b b independently of the instance. For a sliding window of size W W W , the probability that no instance of class j j j in the window is verified at time t t t , so that u j v e r ( t ) = 0 u_j^{\mathrm{ver}}(t) = 0 u j ver ( t ) = 0 , is
P ( u j v e r ( t ) = 0 ) = ∏ s = 0 W − 1 ( 1 − p j b F ( s ) ) . P\left(u_j^{\mathrm{ver}}(t) = 0\right) = \prod_{s=0}^{W-1} (1-p_j bF(s)). P ( u j ver ( t ) = 0 ) = s = 0 ∏ W − 1 ( 1 − p j b F ( s )) . where s s s is the age of the instance. For a constant delay Δ < W \Delta< W Δ < W it is ( 1 − p j b ) W − Δ (1-p_jb)^{W-\Delta} ( 1 − p j b ) W − Δ , that is ( 1 − p j ) W − Δ (1-p_j)^{W-\Delta} ( 1 − p j ) W − Δ for b = 1 b=1 b = 1 , and it is 1 if Δ ≥ W \Delta\ge W Δ ≥ W . The window needed for a target tolerance δ \delta δ grows by the delay, W ≥ Δ + ln ( 1 / δ ) / ( − ln ( 1 − p j b ) ) W \ge\Delta+ \ln(1/\delta)/(-\ln(1-p_jb)) W ≥ Δ + ln ( 1/ δ ) / ( − ln ( 1 − p j b )) .
Proof. An instance of age s s s is a verified instance of class j j j with probability p j b F ( s ) p_jbF(s) p j b F ( s ) and these events are independent across positions, so the probability that none occurs is the product. For a constant delay F ( s ) = I [ s ≥ Δ ] F(s) = \mathbb{I}[s \ge\Delta] F ( s ) = I [ s ≥ Δ ] . □ \square □
Remark 3 (Bursty arrivals inflate the undefined-window rate) Proposition 4 assumes i.i.d. arrivals, and rare events are often bursty. Model the arrivals of class j j j as a two-state on/off Markov process [15 ] , off→ \to → on with probability β \beta β and on→ \to → off with probability γ \gamma γ per step, with a small off-burst singleton arrival rate ρ \rho ρ (the generator of S8 in §6.5). The stationary undefined-window probability is approximately
P ( u j ( t ) = 0 ) ≈ γ β + γ ⏟ π o f f ( 1 − β ) W − 1 ( 1 − ρ ) W , (21) P(u_j(t) = 0) \approx\underbrace{\frac{\gamma}{\beta+\gamma}}_{\pi_{\mathrm{off}}}(1-\beta)^{W-1}(1-\rho)^W, \tag*{(21)} P ( u j ( t ) = 0 ) ≈ π off β + γ γ ( 1 − β ) W − 1 ( 1 − ρ ) W , (21)
which requires the chain to be off for the whole window, with probability π o f f ( 1 − β ) W − 1 \pi_{\mathrm{off}}(1-\beta)^{W-1} π off ( 1 − β ) W − 1 by the memoryless sojourn time and stationarity, and no singleton arrival in it. For β = 0.006 \beta= 0.006 β = 0.006 , γ = 0.03 \gamma= 0.03 γ = 0.03 , ρ = 0.0006 \rho= 0.0006 ρ = 0.0006 and W = 60 W = 60 W = 60 it gives 56.4%, and a simulation of 4 × 10 5 4 \times10^{5} 4 × 1 0 5 steps gives 57.6% on average over three seeds and two classes (§6.5). At the marginal prevalence of about 8% of these classes, the i.i.d. formula (19) predicts below 1% undefined windows, so burstiness accounts for almost all of the undefined-window rate: the arrival process, and not only its marginal rate, governs how often the audited policies trigger.
Verification Latency and Selective Feedback as Dynamic Masks
Stream evaluation often assumes that the true label is available immediately after each prediction (null latency). Labels often arrive late or only for some instances: fraud is confirmed after a dispute resolves, a diagnosis after laboratory results, a loan default months after the decision, a forecast after its horizon. Parreira and Prati [20 ] call this regime intermediate verification latency.
Latency affects drift detectors such as DDM [9 ] , ADWIN [2 ] and HDDM [8 ] , whose statistics are computed only over the verified sub-population. It also affects evaluation: Parreira and Prati [20 ] report, over eleven datasets and seven latency levels, that measured predictive performance degrades as latency increases. When the delay and the choice of which labels arrive do not depend on the model or on the label, the naive estimate over verified instances is only lagged (Table 17 , setting (ii)). Selection bias appears when what is observed depends on the model’s decision or on the label.
Table 17. Bias against the all-labels-immediately oracle at the end of the stream in the four label-availability settings of Gomes et al. [11 ] (full or partial labelling; immediate or delayed labels); bias mean (sd) over 30 seeds. Last column: mean queue size when the system decides which labels to request (only selected, pending instances are enqueued) and when eligibility is unknown (every pending instance is held until its label arrives or its fading weight drops below ε = 10 − 4 \varepsilon= 10^{-4} ε = 1 0 − 4 ).
We treat three feedback imperfections in one algebraic framework: temporal latency, endogenous censoring (labels withheld for instances the model rejects) and stochastic auditing (labels sought for a random or policy-driven subset). Each imposes a different structure on the observation mask O k ( t ) O_k(t) O k ( t ) defined next.
Dynamic Mask Formulation for Latency, Censoring, and Auditing
In operational stream environments labels rarely arrive with the prediction. We model the availability of a verified label for instance k k k at evaluation time t t t by a binary observation mask:
O k ( t ) = I [ k + Δ k ≤ t ] ⋅ A k (22) O_k(t) = \mathbb{I}[k + \Delta_k \le t] \cdot A_k \tag*{(22)} O k ( t ) = I [ k + Δ k ≤ t ] ⋅ A k (22)
where Δ k ≥ 0 \Delta_k \ge0 Δ k ≥ 0 is the verification latency (possibly random) and A k ∈ { 0 , 1 } A_k \in\{0,1\} A k ∈ { 0 , 1 } says whether a label is ever supplied for instance k k k (A k = 0 A_k = 0 A k = 0 is the same as Δ k = ∞ \Delta_k = \infty Δ k = ∞ ). The calligraphic O \mathcal{O} O is unrelated to the asymptotic O ( ⋅ ) O(\cdot) O ( ⋅ ) notation of Proposition 1. The first factor gates temporal availability, since no label can be used before it arrives. The second says whether a label is sought at all. When the system decides which labels to request, A k A_k A k is known at arrival; when an external process supplies the labels, A k A_k A k is revealed only if the label arrives. Four regimes follow, two for the delay and two for the audit:
Constant delay (Δ k = Δ \Delta_k = \Delta Δ k = Δ ): all labels arrive with fixed latency, as in batch annotation pipelines or periodic audit cycles. The mask simplifies to O k ( t ) = I [ k ≤ t − Δ ] O_k(t) = \mathbb{I}[k \le t - \Delta] O k ( t ) = I [ k ≤ t − Δ ] , creating a clean observation horizon with no stochastic component.
Stochastic latency (Δ k ∼ P ( λ ) \Delta_k \sim\mathcal{P}(\lambda) Δ k ∼ P ( λ ) ): labels arrive after a random delay drawn from a distribution such as the exponential or Poisson. This regime models asynchronous annotation queues, where the expected backlog at time t t t is E [ unverified ] = λ \mathbb{E}[\text{unverified}] = \lambda E [ unverified ] = λ instances. The effective number of verified instances up to time t t t is ∑ k = 1 t O k ( t ) \sum_{k=1}^{t} O_k(t) ∑ k = 1 t O k ( t ) , which varies stochastically around t − λ t - \lambda t − λ .
Decision-dependent (endogenous) censoring: the audit probability depends on the model’s own prediction,
π a u d i t ( k ) = π a u d i t ( p k , x k ) (23) \pi_{\mathrm{audit}}(k) = \pi_{\mathrm{audit}}(p_k, x_k) \tag*{(23)} π audit ( k ) = π audit ( p k , x k ) (23)
This arises in decision systems such as loan approval, where only accepted or flagged instances receive ground-truth feedback. The resulting selection bias couples the model’s decision boundary to the observed evaluation set and invalidates the naive estimate.
Stochastic (policy-driven) auditing: the audit decision is independent of the instance’s features and prediction and follows an external labelling budget or sampling policy,
π a u d i t ( k ) = b , b ∈ ( 0 , 1 ] , π a u d i t ( k ) ⊥ ( p k , x k ) (24) \pi_{\mathrm{audit}}(k) = b,\qquad b \in(0,1],\qquad\pi_{\mathrm{audit}}(k) \perp(\boldsymbol{p}_k,\boldsymbol{x}_k) \tag*{(24)} π audit ( k ) = b , b ∈ ( 0 , 1 ] , π audit ( k ) ⊥ ( p k , x k ) (24)
This models active-learning or manual-review budgets, where only a fraction b b b of the stream is labelled under a random or round-robin policy rather than by the classifier’s own decision. Because the audit gate is independent of ( p k , x k ) (\boldsymbol{p}_k,\boldsymbol{x}_k) ( p k , x k ) , the resulting verified sub-population is a representative sample of the full stream. Unlike decision-dependent censoring, naive evaluation restricted to it is unbiased up to sampling variance, at the cost of an effective sample size reduced to n e s s b n_{\mathrm{ess}} b n ess b .
Gomes et al. [11 ] organise label arrival along two axes: whether the labels that arrive do so immediately or after a delay, and whether every instance is eventually labelled. This gives four settings: (i) immediate and fully labelled, (ii) delayed and fully labelled, (iii) immediate and partially labelled, (iv) delayed and partially labelled. They are the four corners of the mask in Eq. (22) , obtained by switching its two factors on or off (Table 1 ). The delay axis is the pair of regimes 1 and 2 above; the survey’s delay D D D is a random variable with finite range, and the constant case is degenerate. The labelling axis is the pair 3 and 4.
Table 1. The four label-availability settings of Gomes et al. [11 ] as corners of the observation mask O k ( t ) = I [ k + Δ k ≤ t ] ⋅ I [ k a u d i t e d ] \mathcal{O}_k(t) = \mathbb{I}[k + \Delta_k \le t] \cdot\mathbb{I}[k\ \mathrm{audited}] O k ( t ) = I [ k + Δ k ≤ t ] ⋅ I [ k audited ] .
The survey rests on the assumption that the learner has no influence on which labels arrive, and it describes missing labels with the missing-completely-at-random, missing-at-random and missing-not-at-random vocabulary of the missing-data literature. Policy-driven auditing (regime 4) has a gate independent of the data and is missing completely at random. Decision-dependent censoring (regime 3) lets the audit probability depend on ( x k , p k ) (\boldsymbol{x}_k,\boldsymbol{p}_k) ( x k , p k ) , so it is missing at random, with the model itself shaping the labelled subset; the survey sets that case aside under active learning. Neither mechanism depends on the true label y k y_k y k given ( x k , p k ) (\boldsymbol{x}_k,\boldsymbol{p}_k) ( x k , p k ) , which is what allows a calibrated estimate to stand in for the missing label (§ 4.2 ). The estimate needs the audit probability to be positive wherever it is used.
Setting (iv) is the product of the two axes: any delay regime combined with any audit regime, the factors multiplying in Eq. (22) . An unaudited instance has Δ k = ∞ \Delta_k = \infty Δ k = ∞ , which is how the survey describes the labels that never arrive; we keep the audit indicator as a separate factor because its mechanism, not its timing, determines the selection bias. One convention differs: the survey’s “immediate” is a verification latency of one time unit, while here Δ k = 0 \Delta_k = 0 Δ k = 0 means that the label is usable at evaluation time k k k , so the two coincide up to a unit offset. Algorithm 1 handles the four settings without change, and § 6.4 reports all four in one experiment.
The censoring and auditing regimes often compose. § 6.4 simulates this combination in a credit/risk stream: writing c ^ k ∈ { 0 , 1 } \hat{c}_k \in\{0,1\} c ^ k ∈ { 0 , 1 } for the model’s realized scalar decision on instance k k k (distinct from the full prediction vector p k \boldsymbol{p}_k p k ), instances the model approves
(c ^ k = 0 \hat{c}_k = 0 c ^ k = 0 ) are always eventually observed, while instances it rejects (c ^ k = 1 \hat{c}_k = 1 c ^ k = 1 ) are censored unless separately selected by an independent audit budget b b b ,
π a u d i t ( k ) = I [ c ^ k = 0 ] + I [ c ^ k = 1 ] ⋅ U k , U k ∼ i i d Bernoulli ( b ) (25) \pi_{\mathrm{audit}}(k) = \mathbb{I}[\hat{c}_k = 0] + \mathbb{I}[\hat{c}_k = 1] \cdot U_k,\qquad U_k \overset{\mathrm{iid}}{\sim} \operatorname{Bernoulli}(b) \tag*{(25)} π audit ( k ) = I [ c ^ k = 0 ] + I [ c ^ k = 1 ] ⋅ U k , U k ∼ iid Bernoulli ( b ) (25)
composing Eq. (23) ’s decision-dependent gate with Eq. (24) ’s stochastic budget. The resulting evaluation set is neither purely censored nor an unbiased sample: it is fully observed for approved instances and b b b -sampled for rejected ones, and § 4.2 shows how the product t t t -norm interim estimator corrects the selection bias contributed by both components simultaneously.
The verified streaming contingency matrix at time t t t integrates only observed, labelled instances:
C v e r i f i e d ( t ) = ∑ k = 1 t O k ( t ) w k ( t ) y k p k T (26) C_{\mathrm{verified}}(t) = \sum_{k=1}^{t} \mathcal{O}_k(t)\,w_k(t)\,\mathbf{y}_k\mathbf{p}_k^{T} \tag*{(26)} C verified ( t ) = k = 1 ∑ t O k ( t ) w k ( t ) y k p k T (26)
where w k ( t ) w_k(t) w k ( t ) is the temporal weight assigned by Σ t \Sigma_t Σ t to instance k k k . Note that C v e r i f i e d ( t ) C_{\mathrm{verified}}(t) C verified ( t ) is sub-populational: it represents only a censored fraction of the stream, and any performance metric derived directly from it inherits the selection bias of the audit policy.
To manage latency without reprocessing history, the evaluator keeps a verification queue Q ( t ) Q(t) Q ( t ) of the instances whose labels have not arrived and may still arrive, with what the correction needs: Q ( t ) = { ( k , y ~ k , p k ) : O k ( t ) = 0 , E k = 1 , k not yet evicted } Q(t) = \{(k,\tilde{\mathbf{y}}_k,\mathbf{p}_k) : \mathcal{O}_k(t) = 0, \mathcal{E}_k = 1, k\ \text{not yet evicted}\} Q ( t ) = {( k , y ~ k , p k ) : O k ( t ) = 0 , E k = 1 , k not yet evicted } . The flag E k ∈ { 0 , 1 } \mathcal{E}_k \in\{0,1\} E k ∈ { 0 , 1 } records what the evaluator knows when instance k k k arrives: E k = 0 \mathcal{E}_k = 0 E k = 0 if it already knows that no label will be requested for k k k , and E k = 1 \mathcal{E}_k = 1 E k = 1 otherwise. Which instances are eligible depends on who controls the labelling:
When the system decides (active learning, decision-dependent censoring), the model’s decision c ^ k \hat{c}_k c ^ k and the audit draw U k U_k U k of Eq. (25) are known at arrival, and the instances that are not selected have E k = 0 \mathcal{E}_k = 0 E k = 0 . They contribute their interim term to C ( t ) C(t) C ( t ) at arrival (§ 4.2 ) and never enter the queue, since no correction can follow. The queue holds only the selected instances still waiting for a label, so its size is set by the latency and the audit budget, not by the stream length.
When labels are supplied by an external process for a subset that is not known in advance (the partially labelled streams of Gomes et al. [11 ] , or fraud confirmations that may never come), eligibility cannot be known at arrival, so E k = 1 \mathcal{E}_k = 1 E k = 1 for every instance. Every instance is held until its label arrives or it is evicted, and eviction (§ 4.2 ) is what keeps the queue bounded when some labels never arrive.
Marginally Consistent Interim Estimates via the Product t-norm
Instances whose true labels have not arrived (those in the queue Q ( t ) \mathcal{Q}(t) Q ( t ) and, when E k = 0 \mathcal{E}_k = 0 E k = 0 , those that never will) cannot contribute to C v e r i f i e d ( t ) C_{\mathrm{verified}}(t) C verified ( t ) . Ignoring them leaves a hole in the state that grows with the latency. We fill it with an estimate y ~ k ∈ [ 0 , 1 ] m \tilde{y}_k \in[0,1]^m y ~ k ∈ [ 0 , 1 ] m of the label, obtained as described next, in place of the observed label y k ∈ { 0 , 1 } m y_k \in\{0,1\}^m y k ∈ { 0 , 1 } m . We call it the interim estimate or, in the experiments, the stand-in. We write y ~ k \tilde{y}_k y ~ k , not y ^ k \hat{y}_k y ^ k , to avoid clashing with the prediction notation of § 3 : y ~ k \tilde{y}_k y ~ k stands in for the unavailable true label, while p k p_k p k remains the model’s prediction being evaluated.
The estimate is a calibrated function of the model’s score and needs no data beyond the stream. Let s k s_k s k be the score vector the model produces for instance k k k , from which its decision p k p_k p k is taken (for instance the class probabilities of a Hoeffding tree), and let g t g_t g t be a calibration map fitted at time t t t . Then y ~ k = g t ( s k ) \tilde{y}_k = g_t(s_k) y ~ k = g t ( s k ) is computed once, at arrival, and needs no label of instance k k k . The map g t g_t g t is the only learned component. It is fitted on the pairs ( s j , y j ) (s_j,y_j) ( s j , y j ) of the instances whose labels have arrived by time t t t (the verified set of Eq. (26) ), with s j s_j s j the score computed at the time of prediction, and it is updated online as each label arrives, optionally with the same fading or window weights as Σ t \Sigma_t Σ t so that it follows drift. Platt scaling, isotonic regression or temperature scaling can serve as g t g_t g t . Four points follow.
The raw score is not a safe substitute. A classifier’s own probabilities are often over- or under-confident, and Eq. (34) below ties the bias of the estimator to that error.
The verified set is a selected sample. Under regimes 1 to 4 the mechanism that decides which labels arrive does not depend on the true label y k y_k y k given ( x k , p k ) (x_k,p_k) ( x k , p k ) . Because g t g_t g t estimates P ( Y ∣ s ) P(Y \mid s) P ( Y ∣ s ) , it is consistent on the verified set only if the audit probability depends on the instance through the score s s s , as it does when it depends on the decision p k p_k p k , and is positive wherever the estimate is used. If it depends on other features of x k x_k x k , g t g_t g t is biased. Under decision-dependent censoring the flagged region reaches g t g_t g t only through the audit budget b b b , so with b = 0 b = 0 b = 0 that region is never observed and the correction cannot be validated there.
Under delay, g t g_t g t lags the stream by the latency, since it only sees labels that have arrived. If the delay depends on the label (the asymmetric regime of § 6.4 ), the labels that have arrived over-represent the class confirmed first, g t g_t g t inherits that bias, and the correction is only partial; § 6.4 measures it.
The value y ~ k \tilde{y}_k y ~ k used at arrival must be stored, not recomputed from the current g t g_t g t , so that the correction step subtracts exactly the term it added.
The soft contribution of an unverified instance ( x k , y ~ k , p k ) (x_k,\tilde{y}_k,p_k) ( x k , y ~ k , p k ) to the contingency matrix is computed by a bivariate aggregation operator T : [ 0 , 1 ] 2 → [ 0 , 1 ] T : [0,1]^2 \to[0,1] T : [ 0 , 1 ] 2 → [ 0 , 1 ] applied entry-wise:
C i n t e r i m , k = T ( y ~ k , p k ) ∈ [ 0 , 1 ] m × m (27) C_{\mathrm{interim},k} = T(\tilde{y}_k,p_k) \in[0,1]^{m \times m} \tag*{(27)} C interim , k = T ( y ~ k , p k ) ∈ [ 0 , 1 ] m × m (27)
We ask for marginal consistency : the row and column sums of the soft contribution must match y ~ k \tilde{y}_k y ~ k and p k p_k p k ,
∑ j ′ [ T ( y ~ k , p k ) ] j j ′ = y ~ k j (marginal label consistency) (28) \sum_{j'} [T(\tilde{y}_k,p_k)]_{jj'} = \tilde{y}_{kj}
\quad\text{(marginal label consistency)} \tag*{(28)} j ′ ∑ [ T ( y ~ k , p k ) ] j j ′ = y ~ k j (marginal label consistency) (28)
∑ j [ T ( y ~ k , p k ) ] j j ′ = p k j ′ (29) \sum_j [T(\tilde{y}_k,p_k)]_{jj'} = p_{kj'} \tag*{(29)} j ∑ [ T ( y ~ k , p k ) ] j j ′ = p k j ′ (29)
so that the soft matrix contributes the expected totals to the TP, FP, TN and FN cells. Among t t t -norms, only the product T P ( a , b ) = a ⋅ b T_P(a,b)=a\cdot b T P ( a , b ) = a ⋅ b satisfies both conditions for soft predictions [24 ] , and then
[ T P ( y ~ k , p k ) ] j j ′ = y ~ k j p k j ′ (30) [T_P(\tilde{y}_k,p_k)]_{jj'}=\tilde{y}_{kj}p_{kj'} \tag*{(30)} [ T P ( y ~ k , p k ) ] j j ′ = y ~ k j p k j ′ (30)
the outer product y ~ k p k T \tilde{y}_kp_k^{\mathsf{T}} y ~ k p k T . The minimum T M ( a , b ) = min ( a , b ) T_M(a,b)=\min(a,b) T M ( a , b ) = min ( a , b ) and the Łukasiewicz T L ( a , b ) = max ( 0 , a + b − 1 ) T_L(a,b)=\max(0,a+b-1) T L ( a , b ) = max ( 0 , a + b − 1 ) t t t -norms violate at least one condition, with marginal defect
defect ( T ) = ∥ 1 T [ T ( y ~ k , p k ) ] − p k T ∥ 1 + ∥ [ T ( y ~ k , p k ) ] 1 − y ~ k ∥ 1 (31) \operatorname{defect}(T)=\left\lVert\mathbf{1}^{\mathsf{T}}[T(\tilde{y}_k,p_k)]-p_k^{\mathsf{T}}\right\rVert_1+\left\lVert[T(\tilde{y}_k,p_k)]\mathbf{1}-\tilde{y}_k\right\rVert_1 \tag*{(31)} defect ( T ) = 1 T [ T ( y ~ k , p k )] − p k T 1 + ∥ [ T ( y ~ k , p k )] 1 − y ~ k ∥ 1 (31)
that is positive for soft p k p_k p k (Table 14 ) and zero for T P T_P T P . For hard one-hot decisions p k p_k p k every t t t -norm gives the same matrix, because T ( a , 1 ) = a T(a,1)=a T ( a , 1 ) = a and T ( a , 0 ) = 0 T(a,0)=0 T ( a , 0 ) = 0 , so the choice only matters for soft predictions. The product is also the right choice for a second reason: the prediction p k p_k p k is a function of x k x_k x k once the model is fixed, so E [ y k p k T ∣ x k ] = P ( Y ∣ x k ) p k T \mathbb{E}[y_kp_k^{\mathsf{T}}\mid x_k]=P(Y\mid x_k)p_k^{\mathsf{T}} E [ y k p k T ∣ x k ] = P ( Y ∣ x k ) p k T , which is an outer product.
Table 14. Latency regimes on S5, one run. The defect is the mean marginal defect (Eq. (31) ) of the stand-in and the soft prediction; it is zero for all three t t t -norms with hard predictions. The queue holds up to Δ − 1 \Delta- 1 Δ − 1 entries because an instance is recorded before the clock advances.
The unified streaming contingency matrix combines verified labels with interim estimates:
C ( t ) = ∑ k = 1 t O k ( t ) w k ( t ) y k p k T ⏟ verified contribution + ∑ k = 1 t ( 1 − O k ( t ) ) w k ( t ) y ~ k p k T ⏟ interim contribution (32) C(t)=\sum_{k=1}^{t}\underbrace{O_k(t)w_k(t)y_kp_k^{\mathsf{T}}}_{\text{verified contribution}}+\sum_{k=1}^{t}\underbrace{(1-O_k(t))w_k(t)\tilde{y}_kp_k^{\mathsf{T}}}_{\text{interim contribution}} \tag*{(32)} C ( t ) = k = 1 ∑ t verified contribution O k ( t ) w k ( t ) y k p k T + k = 1 ∑ t interim contribution ( 1 − O k ( t )) w k ( t ) y ~ k p k T (32)
It recovers C v e r i f i e d ( t ) C_{\mathrm{verified}}(t) C verified ( t ) in the limiting case of zero latency (Δ k = 0 \Delta_k=0 Δ k = 0 , A k = 1 A_k=1 A k = 1 ) and is built from outer products with the prescribed marginals. The zero marginal defect is a property of that construction. Correcting a selection bias is a separate matter that needs a mechanism that is missing at random given the score and a consistent calibration map g t g_t g t (point 2 above), and it fails when the delay depends on the label. Equation (32) is not recomputed from scratch. Algorithm 1 credits the interim term at arrival and swaps it for the verified term if the label later arrives, so that both live in one running matrix.
Each step costs O ( m 2 ) O(m^2) O ( m 2 ) operations, plus O ( m 2 ) O(m^2) O ( m 2 ) for each arriving label, independent of t t t and of ∣ Q ∣ |Q| ∣ Q ∣ : the weight of an entry is computed from its age when a label arrives, and eviction only inspects the oldest entry. Under a sliding window the weights are 1 / W 1/W 1/ W and the update is C ( t + 1 ) ← C ( t ) + 1 W ( T P ( y ~ t + 1 , p t + 1 ) − C(t+1)\leftarrow C(t)+\frac{1}{W}(T_P(\tilde{y}_{t+1},p_{t+1})- C ( t + 1 ) ← C ( t ) + W 1 ( T P ( y ~ t + 1 , p t + 1 ) − term of the instance leaving the window). A FIFO of the last W W W instances stores each instance’s current term, interim or verified, so that a label arriving within the window replaces the stored term and adds 1 W ( y k p k T − T P ( y ~ k , p k ) ) \frac{1}{W}(y_kp_k^{\mathsf{T}}-T_P(\tilde{y}_k,p_k)) W 1 ( y k p k T − T P ( y ~ k , p k )) to C C C . Eviction is then automatic, ∣ Q ( t ) ∣ ≤ W |Q(t)|\le W ∣ Q ( t ) ∣ ≤ W . The window variant and the eviction step are implemented in the package (§ 7 ) and run in § 6.4 (Table 18 ).
Table 18. Recall bias against the oracle (mean (sd) over 100 seeds) and queue size (mean and mean of the maximum) of the fading and sliding-window estimators on S6, with every instance queued. Fading uses α = 0.99 \alpha= 0.99 α = 0.99 and eviction tolerance 10 − 4 10^{-4} 1 0 − 4 ; the window is W = 100 W = 100 W = 100 .
Eviction bounds the queue. Writing the weight of an entry of age s = t − k s=t-k s = t − k as w ( s ) = ( 1 − α ) α s w(s)=(1-\alpha)\alpha^s w ( s ) = ( 1 − α ) α s , an entry is evicted once w ( s ) < ε w(s)<\varepsilon w ( s ) < ε , that is after s ∗ = min { s : w ( s ) < s^*=\min\{s:w(s)< s ∗ = min { s : w ( s ) < Algorithm 1 Prequential state update on arrival of instance t + 1 t+1 t + 1 (exponential fading)
Require: State C ( t ) C(t) C ( t ) , queue Q ( t ) Q(t) Q ( t ) , score s t + 1 s_{t+1} s t + 1 , prediction p t + 1 \mathbf{p}_{t+1} p t + 1 , eligibility flag E t + 1 \mathcal{E}_{t+1} E t + 1 , and the labels y k y_k y k that arrive at time t + 1 t+1 t + 1
Ensure: Updated state C ( t + 1 ) C(t+1) C ( t + 1 ) and queue Q ( t + 1 ) Q(t+1) Q ( t + 1 )
y ~ t + 1 ← g t ( s t + 1 ) \tilde{y}_{t+1} \leftarrow g_t(s_{t+1}) y ~ t + 1 ← g t ( s t + 1 ) ▷ interim estimate, stored with the entry
C ( t + 1 ) ← α C ( t ) + ( 1 − α ) T P ( y ~ t + 1 , p t + 1 ) C(t+1) \leftarrow\alpha C(t) + (1-\alpha) T_P(\tilde{y}_{t+1},\mathbf{p}_{t+1}) C ( t + 1 ) ← α C ( t ) + ( 1 − α ) T P ( y ~ t + 1 , p t + 1 ) ▷ decay, then credit the interim term
if E t + 1 = 1 \mathcal{E}_{t+1}=1 E t + 1 = 1 then
enqueue ( t + 1 , y ~ t + 1 , p t + 1 ) (t+1,\tilde{y}_{t+1},\mathbf{p}_{t+1}) ( t + 1 , y ~ t + 1 , p t + 1 ) into Q Q Q
end if
for all labels y k y_k y k arriving at time t + 1 t+1 t + 1 with k ∈ Q k \in Q k ∈ Q do
C ( t + 1 ) ← C ( t + 1 ) + ( 1 − α ) α t + 1 − k ( y k p k T − T P ( y ~ k , p k ) ) C(t+1) \leftarrow C(t+1) + (1-\alpha)\alpha^{t+1-k}(y_k\mathbf{p}_k^T-T_P(\tilde{y}_k,\mathbf{p}_k)) C ( t + 1 ) ← C ( t + 1 ) + ( 1 − α ) α t + 1 − k ( y k p k T − T P ( y ~ k , p k )) ▷ swap interim for verified
remove k k k from Q Q Q
end for
while the oldest entry k k k of Q Q Q has ( 1 − α ) α t + 1 − k < ε (1-\alpha)\alpha^{t+1-k}<\varepsilon ( 1 − α ) α t + 1 − k < ε do
remove k k k from Q Q Q ▷ its interim term stays in C C C and keeps decaying
end while
return C ( t + 1 ) , Q ( t + 1 ) C(t+1), Q(t+1) C ( t + 1 ) , Q ( t + 1 )
ε \varepsilon ε } steps. The entries that can no longer be corrected carry a share of the state of at most
∑ s ≥ s ∗ w ( s ) = α s ∗ < ε n e f f , s ∗ = min { s : w ( s ) < ε } , (33) \sum_{s\ge s^*} w(s)=\alpha^{s^*}<\varepsilon n_{\mathrm{eff}},\qquad s^*=\min\{s:w(s)<\varepsilon\}, \tag*{(33)} s ≥ s ∗ ∑ w ( s ) = α s ∗ < ε n eff , s ∗ = min { s : w ( s ) < ε } , (33)
an exact geometric tail (with n e f f = 1 / ( 1 − α ) n_{\mathrm{eff}}=1/(1-\alpha) n eff = 1/ ( 1 − α ) ) reached after s ∗ = O ( n e f f log 1 n e f f ε ) s^*=O\left(n_{\mathrm{eff}}\log\frac{1}{n_{\mathrm{eff}}\varepsilon}\right) s ∗ = O ( n eff log n eff ε 1 ) steps. Hence ∣ Q ( t ) ∣ ≤ s ∗ ≤ n e f f ln 1 n e f f ε + 2 |Q(t)|\le s^*\le n_{\mathrm{eff}}\ln\frac{1}{n_{\mathrm{eff}}\varepsilon}+2 ∣ Q ( t ) ∣ ≤ s ∗ ≤ n eff ln n eff ε 1 + 2 at any time when n e f f ε < 1 n_{\mathrm{eff}}\varepsilon<1 n eff ε < 1 , independent of t t t and of how many instances are permanently censored. The wait limit comes from the temporal operator and not from the labelling process: a label that arrives after the eviction point would be multiplied by a weight below ε \varepsilon ε and changes C ( t ) C(t) C ( t ) by less than ε \varepsilon ε , although it can still be used elsewhere, for instance to train the model and g t g_t g t . The correction therefore pays off only when the latency is short against the memory of the operator, Δ k ≪ W \Delta_k\ll W Δ k ≪ W under a window or Δ k ≪ n e f f \Delta_k\ll n_{\mathrm{eff}} Δ k ≪ n eff under fading. If Δ k ≥ W \Delta_k\ge W Δ k ≥ W for most instances, every instance leaves the window unverified and the windowed state consists of interim terms only, that is, of the model’s own calibrated belief. Table 17 is in the first regime (λ = 25 \lambda=25 λ = 25 , n e f f = 100 n_{\mathrm{eff}}=100 n eff = 100 ), and the effect of delay there is correspondingly small. The queue costs O ( ∣ Q ∣ m ) O(|Q|m) O ( ∣ Q ∣ m ) memory on top of the O ( m 2 ) O(m^2) O ( m 2 ) state of Proposition 1.
Let C o r a c l e ( t ) C_{\mathrm{oracle}}(t) C oracle ( t ) be the state that would be obtained if every label were available at arrival. The bias of the unified estimator (32) relative to it is
C o r a c l e ( t ) − C ( t ) = ∑ k = 1 t ( 1 − O k ( t ) ) w k ( t ) ( y k − y ~ k ) p k T (34) C_{\mathrm{oracle}}(t)-C(t)=\sum_{k=1}^{t}(1-O_k(t))w_k(t)(y_k-\tilde{y}_k)\mathbf{p}_k^T \tag*{(34)} C oracle ( t ) − C ( t ) = k = 1 ∑ t ( 1 − O k ( t )) w k ( t ) ( y k − y ~ k ) p k T (34)
The residual is driven by the calibration error of y ~ k \tilde{y}_k y ~ k . If E [ y k ∣ s k , p k ] = y ~ k \mathbb{E}[y_k\mid s_k,\mathbf{p}_k]=\tilde{y}_k E [ y k ∣ s k , p k ] = y ~ k (calibration) and O k ( t ) O_k(t) O k ( t ) is independent of y k y_k y k given ( s k , p k ) (s_k,\mathbf{p}_k) ( s k , p k ) , the expected residual is zero and C ( t ) C(t) C ( t ) is conditionally unbiased for the oracle matrix. Equations (32) and (34) are exact without eviction; eviction changes each entry of C ( t ) C(t) C ( t ) by less than ε \varepsilon ε for each late label it discards, and by at most α s ∗ < ε n e f f \alpha s^{*}<\varepsilon n_{\mathrm{eff}} α s ∗ < ε n eff in total (Eq. (33) ), when the entries of y k p k T − y ~ k p k T \mathbf{y}_{k}\mathbf{p}_{k}^{T}-\tilde{\mathbf{y}}_{k}\mathbf{p}_{k}^{T} y k p k T − y ~ k p k T are bounded by one. Metrics that are ratios of cells inherit only first-order consistency from this. Post-hoc calibration (isotonic regression (Zadrozny and Elkan 2002), Platt scaling [22 ] , temperature scaling [13 ] ) reduces the calibration error that drives the residual, which links classifier calibration to evaluation bias under delayed labels.
Example 4 (Running example: delayed labels, a stand-in and its correction) Let the label of instance k k k arrive at time k + Δ k k+\Delta_k k + Δ k with Δ = ( 0 , 1 , 2 , 3 , 2 , 3 , 2 , 1 ) \Delta=(0,1,2,3,2,3,2,1) Δ = ( 0 , 1 , 2 , 3 , 2 , 3 , 2 , 1 ) , and let instance 7 never be labelled, because the model flagged it as C C C and the system requested no label (A 7 = 0 A_7=0 A 7 = 0 , E 7 = 0 E_7=0 E 7 = 0 ). At t = 8 t=8 t = 8 the window holds instances 5 to 8: the label of 5 has arrived, those of 6 and 8 are pending (they arrive at t = 9 t=9 t = 9 ), and 7 is never labelled. Only 6 and 8 enter the queue. The stand-in puts 3 4 \frac{3}{4} 4 3 on the predicted class and 1 8 \frac{1}{8} 8 1 on each other class. With weights 1 4 \frac{1}{4} 4 1 the unified state of Eq. (32) and the oracle state are
C ( 8 ) = 1 32 ( 6 1 1 1 14 1 1 1 6 ) , C o r a c l e ( 8 ) = 1 32 ( 8 0 0 0 16 8 0 0 0 ) , C(8)=\frac{1}{32}\begin{pmatrix}6&1&1\\1&14&1\\1&1&6\end{pmatrix},\qquad C_{\mathrm{oracle}}(8)=\frac{1}{32}\begin{pmatrix}8&0&0\\0&16&8\\0&0&0\end{pmatrix}, C ( 8 ) = 32 1 6 1 1 1 14 1 1 1 6 , C oracle ( 8 ) = 32 1 8 0 0 0 16 0 0 8 0 , and their difference, 1 32 ( 2 − 1 − 1 − 1 2 7 − 1 − 1 − 6 ) \frac{1}{32}\begin{pmatrix}2&-1&-1\\-1&2&7\\-1&-1&-6\end{pmatrix} 32 1 2 − 1 − 1 − 1 2 − 1 − 1 7 − 6 , is the sum of ( y k − y ~ k ) p k T / 4 (\mathbf{y}_k-\tilde{\mathbf{y}}_k)\mathbf{p}_k^T/4 ( y k − y ~ k ) p k T /4 over the instances without a label (Eq. (34) ).
The recall of B B B is 2 3 \frac{2}{3} 3 2 in the oracle state, 7 8 \frac{7}{8} 8 7 in C ( 8 ) C(8) C ( 8 ) and 1 if only the verified instance is used; the recall of A A A is 1, 3 4 \frac{3}{4} 4 3 and undefined.
For the stand-in of instance 7 and the soft prediction ( 1 8 , 1 8 , 3 4 ) (\frac{1}{8},\frac{1}{8},\frac{3}{4}) ( 8 1 , 8 1 , 4 3 ) the marginal defect is 0 for the product t t t -norm, 3 8 \frac{3}{8} 8 3 for the minimum and 1 for the Łukasiewicz t t t -norm; for the hard prediction it is 0 for all three.
When the label of instance 6 arrives, the correction adds 1 4 ( y 6 p 6 T − T P ( y ~ 6 , p 6 ) ) = 1 32 ( 2 0 0 − 1 0 0 − 1 0 0 ) \frac{1}{4}(\mathbf{y}_6\mathbf{p}_6^T-T_P(\tilde{\mathbf{y}}_6,p_6))=\frac{1}{32}\begin{pmatrix}2&0&0\\-1&0&0\\-1&0&0\end{pmatrix} 4 1 ( y 6 p 6 T − T P ( y ~ 6 , p 6 )) = 32 1 2 − 1 − 1 0 0 0 0 0 0 . Under fading with α = 1 2 \alpha=\frac{1}{2} α = 2 1 the weights of instances 6 and 8 at t = 8 t=8 t = 8 are 1 8 \frac{1}{8} 8 1 and 1 2 \frac{1}{2} 2 1 , and with ε = 1 32 \varepsilon=\frac{1}{32} ε = 32 1 an entry is evicted once its age exceeds s ∗ = 5 s^{*}=5 s ∗ = 5 steps, which no queue entry has reached.
The stand-in also hides a void on the label side: it puts mass 1 4 \frac{1}{4} 4 1 in the row of C C C , so Recall C = 3 4 \operatorname{Recall}_{C}=\frac{3}{4} Recall C = 4 3 in C ( 8 ) C(8) C ( 8 ) although the oracle state has no support for C C C . The verified support is u v e r = ( 0 , 1 , 0 ) \mathbf{u}^{\mathrm{ver}}=(0,1,0) u ver = ( 0 , 1 , 0 ) and the coverage κ = ( 0 , 1 2 , 0 ) \boldsymbol{\kappa}=(0,\frac{1}{2},0) κ = ( 0 , 2 1 , 0 ) for the label-side denominators, so the policies of § 3.5 treat A A A and C C C as unsupported for recall: the macro recall is 7 8 \frac{7}{8} 8 7 under exclude, 7 24 \frac{7}{24} 24 7 under zero and undefined under nan, and the 7 8 \frac{7}{8} 8 7 is an estimate (κ B = 1 2 \kappa_B=\frac{1}{2} κ B = 2 1 ). The columns are exact: the column sums of C ( 8 ) C(8) C ( 8 ) equal those of the oracle, ( 1 4 , 1 2 , 1 4 ) (\frac{1}{4},\frac{1}{2},\frac{1}{4}) ( 4 1 , 2 1 , 4 1 ) , so the precision of every class keeps u i n t = ( 1 , 1 , 1 ) \mathbf{u}^{\mathrm{int}}=(1,1,1) u int = ( 1 , 1 , 1 ) .
Disentangling Concept Drift from Prior Probability Shifts
Non-stationarity in a stream has two statistical mechanisms. In real concept drift the conditional distribution P t ( Y ∣ X ) P_t(Y\mid X) P t ( Y ∣ X ) changes with the environment. In virtual drift the feature distribution P t ( X ) P_t(X) P t ( X ) or the class prior P t ( Y ) = π ( t ) P_t(Y)=\boldsymbol{\pi}(t) P t ( Y ) = π ( t ) changes while the decision boundary stays valid. Metrics such as Accuracy, Precision and F 1 F_1 F 1 depend on the prior π ( t ) \pi(t) π ( t ) , so a change in class balance moves them even when the classifier is unchanged, and drift detectors that monitor them or the error rate (DDM Gama et al. [9 ] , ADWIN Bifet and Gavaldà [2 ] ) can alarm on a prior shift alone.
This section works under label shift: a prior change means P t ( Y ) P_t(Y) P t ( Y ) changes while P t ( X ∣ Y ) P_t(X \mid Y) P t ( X ∣ Y ) stays fixed. We give the temporal taxonomy of drifts (§ 5.1 ), the canonical coordinates that are free of the prior and the conditions under which this holds in the binary and the multiclass case (§ 5.2 ), a first-order decomposition of a metric change into a concept term and a prior term (§ 5.3 ), and a monitoring scheme that detects on the canonical coordinates and attributes on the decomposition (§ 5.4 ).
Temporal Drift Taxonomy and Dynamic Filtering Dynamics
Drift events have different temporal profiles, which determine how quickly a learner must adapt and how Σ t \Sigma_t Σ t filters the history.
Abrupt drift is an instantaneous transition between two generating distributions P A P_A P A and P B P_B P B at time t 0 t_0 t 0 , P t ( X , Y ) = ( 1 − H ( t − t 0 ) ) P A + H ( t − t 0 ) P B P_t(X,Y) = (1 - H(t - t_0))P_A + H(t - t_0)P_B P t ( X , Y ) = ( 1 − H ( t − t 0 )) P A + H ( t − t 0 ) P B , with H H H the Heaviside step. Under exponential fading, in expectation and if the state had settled at C A C_A C A before t 0 t_0 t 0 , the state moves as
C α ( t ) = α t − t 0 + 1 C A + ( 1 − α t − t 0 + 1 ) C B , ∀ t ≥ t 0 (35) C_\alpha(t) = \alpha^{t-t_0+1}C_A + (1 - \alpha^{t-t_0+1})C_B,\qquad\forall t \ge t_0 \tag*{(35)} C α ( t ) = α t − t 0 + 1 C A + ( 1 − α t − t 0 + 1 ) C B , ∀ t ≥ t 0 (35)
The adaptation timescale is the half-life t 1 / 2 = ln 2 / ln ( 1 / α ) ≈ 0.693 n e f f t_{1/2} = \ln2/\ln(1/\alpha) \approx0.693\,n_{\mathrm{eff}} t 1/2 = ln 2/ ln ( 1/ α ) ≈ 0.693 n eff , whereas a sliding window purges the old concept after exactly W W W steps.
Gradual drift is a probabilistic mixture over a finite duration w d r i f t w_{\mathrm{drift}} w drift centred at t 0 t_0 t 0 , P t ( X , Y ) = ( 1 − s ( t ) ) P A + s ( t ) P B P_t(X,Y) = (1-s(t))P_A+s(t)P_B P t ( X , Y ) = ( 1 − s ( t )) P A + s ( t ) P B with s ( t ) = 1 / ( 1 + exp ( − 4 ( t − t 0 ) / w d r i f t ) ) s(t) = 1/(1+\exp(-4(t-t_0)/w_{\mathrm{drift}})) s ( t ) = 1/ ( 1 + exp ( − 4 ( t − t 0 ) / w drift )) . Samples from both concepts interleave during the transition.
Incremental drift is a smooth parameter trajectory θ ( t ) = θ 0 + v d r i f t ( t − t 0 ) \boldsymbol{\theta}(t) = \boldsymbol{\theta}_0+\mathbf{v}_{\mathrm{drift}}(t-t_0) θ ( t ) = θ 0 + v drift ( t − t 0 ) . Under a steady velocity v C = d C p o p ( t ) / d t \mathbf{v}_C = dC_{\mathrm{pop}}(t)/dt v C = d C pop ( t ) / d t the fading estimator has a constant asymptotic tracking lag,
C α ( t ) − C p o p ( t ) ≈ − ( α 1 − α ) v C = − ( n e f f − 1 ) v C (36) C_\alpha(t) - C_{\mathrm{pop}}(t) \approx-\left(\frac{\alpha}{1-\alpha}\right)\mathbf{v}_C = -(n_{\mathrm{eff}}-1)\mathbf{v}_C \tag*{(36)} C α ( t ) − C pop ( t ) ≈ − ( 1 − α α ) v C = − ( n eff − 1 ) v C (36)
which is the bias half of the trade-off between smoothing noise and tracking latency.
Reoccurring concepts are periodic or stochastic reappearances of earlier distributions P t ∈ { P 1 , … , P K } P_t \in\{P_1,\ldots,P_K\} P t ∈ { P 1 , … , P K } . Because Σ t \Sigma_t Σ t discounts by recency and not by identity, a returning concept enters C ( t ) C(t) C ( t ) like a new one, so reusing a specialised sub-model needs machinery outside Σ t \Sigma_t Σ t .
Transient outliers are isolated single-instance perturbations δ ( t − t 0 ) \delta(t-t_0) δ ( t − t 0 ) . The fading operator attenuates such a shock to an amplitude of ( 1 − α ) (1-\alpha) ( 1 − α ) and damps it as α s \alpha^s α s .
The Canonical Coordinates and Prior-Invariance
We call (Recall, Specificity) canonical because every binary measure is a function of them and of the prior. For a binary stream, or for the table of one class j j j , write π t \pi_t π t for the positive-class prior at time t t t and R ( t ) = [ R 11 ( t ) , R 00 ( t ) ] T = [ Recall ( t ) , Specificity ( t ) ] T \boldsymbol{R}(t) = [R_{11}(t), R_{00}(t)]^{T} = [\operatorname{Recall}(t), \operatorname{Specificity}(t)]^{T} R ( t ) = [ R 11 ( t ) , R 00 ( t ) ] T = [ Recall ( t ) , Specificity ( t ) ] T for the canonical coordinates (the true positive and true negative rates of the classifier at time t t t ). In terms of the cell masses of that table,
R 11 = A A + C , R 00 = D D + B , (37) R_{11} = \frac{A}{A+C}, \qquad R_{00} = \frac{D}{D+B}, \tag*{(37)} R 11 = A + C A , R 00 = D + B D , (37)
where A , B , C , D A, B, C, D A , B , C , D are the true positive, false positive, false negative and true negative masses. These are population quantities at time t t t when the cells are the expected cell masses at t t t . A cell mass that is a time-weighted accumulation needs the care of Remark 4 below.
Lemma 1 (A ratio of proportional cells is prior-invariant) If two nonnegative quantities A , C A, C A , C satisfy A = c ⋅ r A = c \cdot r A = c ⋅ r and C = c ⋅ ( 1 − r ) C = c \cdot(1-r) C = c ⋅ ( 1 − r ) for some c ≠ 0 c \ne0 c = 0 and some r r r , then A / ( A + C ) = r A/(A+C) = r A / ( A + C ) = r , independently of c c c .
Proof. A + C = c ⋅ r + c ⋅ ( 1 − r ) = c A + C = c \cdot r + c \cdot(1-r) = c A + C = c ⋅ r + c ⋅ ( 1 − r ) = c , so A / ( A + C ) = ( c ⋅ r ) / c = r A/(A+C) = (c \cdot r)/c = r A / ( A + C ) = ( c ⋅ r ) / c = r .
Proposition 5 (Prior-invariance of the canonical coordinates at a fixed time) Let f t : X → [ 0 , 1 ] f_t : \mathcal{X} \to[0,1] f t : X → [ 0 , 1 ] be the classifier’s decision function at time t t t (distinct from the prediction vector p t \boldsymbol{p}_t p t , which is f t f_t f t ’s output on one instance), and let P t ( X ∣ Y = 1 ) P_t(X \mid Y = 1) P t ( X ∣ Y = 1 ) , P t ( X ∣ Y = 0 ) P_t(X \mid Y = 0) P t ( X ∣ Y = 0 ) be the class-conditional feature distributions. Both may vary arbitrarily with t t t : the classifier may be fixed, periodically retrained or continuously adapted. Then, for 0 < π t < 1 0 < \pi_t < 1 0 < π t < 1 , the canonical coordinates at time t t t do not depend on the prior π t = P t ( Y = 1 ) \pi_t = P_t(Y = 1) π t = P t ( Y = 1 ) :
R 11 ( t ) = ∫ f t ( x ) d P t ( x ∣ Y = 1 ) , R 00 ( t ) = ∫ ( 1 − f t ( x ) ) d P t ( x ∣ Y = 0 ) (38) R_{11}(t) = \int f_t(x)\,\mathrm{d}P_t(x \mid Y = 1), \qquad R_{00}(t) = \int(1-f_t(x))\,\mathrm{d}P_t(x \mid Y = 0) \tag*{(38)} R 11 ( t ) = ∫ f t ( x ) d P t ( x ∣ Y = 1 ) , R 00 ( t ) = ∫ ( 1 − f t ( x )) d P t ( x ∣ Y = 0 ) (38) Neither expression contains π t \pi_t π t , so ∂ R 11 / ∂ π t = ∂ R 00 / ∂ π t = 0 \partial R_{11}/\partial\pi_t = \partial R_{00}/\partial\pi_t = 0 ∂ R 11 / ∂ π t = ∂ R 00 / ∂ π t = 0 . By contrast Precision and F1 depend on π t \pi_t π t even without concept drift, and so does Accuracy unless R 11 = R 00 R_{11} = R_{00} R 11 = R 00 .
Proof. By the law of total probability at the fixed time t t t , the expected cell masses are A = π t ∫ f t d P t ( ⋅ ∣ Y = 1 ) A = \pi_t \int f_t\,\mathrm{d}P_t(\cdot\mid Y = 1) A = π t ∫ f t d P t ( ⋅ ∣ Y = 1 ) and C = π t ∫ ( 1 − f t ) d P t ( ⋅ ∣ Y = 1 ) C = \pi_t \int(1-f_t)\,\mathrm{d}P_t(\cdot\mid Y = 1) C = π t ∫ ( 1 − f t ) d P t ( ⋅ ∣ Y = 1 ) . Both are π t \pi_t π t times a proportion of the positive-class distribution, so Lemma 1 with c = π t c = \pi_t c = π t gives R 11 ( t ) = ∫ f t d P t ( ⋅ ∣ Y = 1 ) R_{11}(t) = \int f_t\,\mathrm{d}P_t(\cdot\mid Y = 1) R 11 ( t ) = ∫ f t d P t ( ⋅ ∣ Y = 1 ) . The same lemma with c = 1 − π t c = 1-\pi_t c = 1 − π t gives R 00 ( t ) R_{00}(t) R 00 ( t ) .
a prior-weighted average of past recalls. It is free of the prior if R 11 ( s ) R_{11}(s) R 11 ( s ) is constant over the memory window or if π s \pi_s π s is, and not in general otherwise. When the classifier changes while the prior changes, the accumulated coordinates mix the two. Call the cells of C α ( t ) C_{\alpha}(t) C α ( t ) the time-fading coordinates. To estimate the instantaneous coordinates without this mixing, decay by the arrivals of each class instead of by time (class-time fading): update R ^ 11 ← α R ^ 11 + ( 1 − α ) 1 [ prediction positive ] \widehat{R}_{11} \leftarrow\alpha\widehat{R}_{11} + (1-\alpha)\mathbb{1}[\text{prediction positive}] R 11 ← α R 11 + ( 1 − α ) 1 [ prediction positive ] only on arrivals with Y = 1 Y=1 Y = 1 , and R ^ 00 \widehat{R}_{00} R 00 only on arrivals with Y = 0 Y=0 Y = 0 (with the usual correction for the initial mass). Each estimate is then a function of its own class arrivals alone, so its mean is free of the prior by construction, and its memory is n e f f n_{\mathrm{eff}} n eff arrivals of that class instead of n e f f n_{\mathrm{eff}} n eff steps. Its variance still depends on the number of arrivals of the class, hence on the prior.
Proposition 6 (Prior-invariance in the multiclass case) Let c k l ( t ) = P t ( Y ^ = l ∣ Y = k ) c_{kl}(t) = P_t(\widehat{Y}=l \mid Y=k) c k l ( t ) = P t ( Y = l ∣ Y = k ) be the rows of the confusion matrix and π k ( t ) = P t ( Y = k ) \pi_k(t) = P_t(Y=k) π k ( t ) = P t ( Y = k ) the class priors. Then
the rows c k ( t ) c_k(t) c k ( t ) , and in particular Recall j ( t ) = c j j ( t ) \operatorname{Recall}_j(t) = c_{jj}(t) Recall j ( t ) = c j j ( t ) , do not depend on π ( t ) \pi(t) π ( t ) ;
the one-vs-rest specificity is Specificity j ( t ) = ∑ k ≠ j π k ( t ) 1 − π j ( t ) ( 1 − c k j ( t ) ) \operatorname{Specificity}_j(t) = \sum_{k\ne j} \frac{\pi_k(t)}{1-\pi_j(t)}(1-c_{kj}(t)) Specificity j ( t ) = ∑ k = j 1 − π j ( t ) π k ( t ) ( 1 − c k j ( t )) , which depends on the prior only through the composition π k / ( 1 − π j ) \pi_k/(1-\pi_j) π k / ( 1 − π j ) , k ≠ j k\ne j k = j , of the other classes. It is invariant to every prior change that preserves that composition (for example a change of π j \pi_j π j alone, the other classes rescaled), and, if column j j j of the confusion matrix is constant over k ≠ j k\ne j k = j , to every prior change. Otherwise it moves with the priors of the other classes without any concept drift.
Proof. Part 1 is the law of total probability, as in Proposition 5 . For part 2, P ( Y ^ ≠ j ∣ Y ≠ j ) = ∑ k ≠ j P ( Y = k ∣ Y ≠ j ) P ( Y ^ ≠ j ∣ Y = k ) P(\widehat{Y}\ne j \mid Y\ne j) = \sum_{k\ne j} P(Y=k \mid Y\ne j)P(\widehat{Y}\ne j \mid Y=k) P ( Y = j ∣ Y = j ) = ∑ k = j P ( Y = k ∣ Y = j ) P ( Y = j ∣ Y = k ) and P ( Y = k ∣ Y ≠ j ) = π k / ( 1 − π j ) P(Y=k \mid Y\ne j) = \pi_k/(1-\pi_j) P ( Y = k ∣ Y = j ) = π k / ( 1 − π j ) . □
The binary case is the special case in which the rest is a single class. For multiclass streams the invariant coordinates are therefore the confusion rows P ( Y ^ ∣ Y = k ) P(\widehat{Y}\mid Y=k) P ( Y ∣ Y = k ) , one stream of outcomes per true class, and not the one-vs-rest pair ( Recall j , Specificity j ) (\operatorname{Recall}_j,\operatorname{Specificity}_j) ( Recall j , Specificity j ) .
Example 5 (Running example: a label shift among the other classes) Consider the population in which the classifier has the confusion rows c A = ( 3 4 , 1 4 , 0 ) c_A=(\frac{3}{4},\frac{1}{4},0) c A = ( 4 3 , 4 1 , 0 ) , c B = ( 0 , 3 4 , 1 4 ) c_B=(0,\frac{3}{4},\frac{1}{4}) c B = ( 0 , 4 3 , 4 1 ) , c C = ( 1 4 , 0 , 3 4 ) c_C=(\frac{1}{4},0,\frac{3}{4}) c C = ( 4 1 , 0 , 4 3 ) (each class is mistaken for the next one), and the prior moves from ( 1 2 , 1 4 , 1 4 ) (\frac{1}{2},\frac{1}{4},\frac{1}{4}) ( 2 1 , 4 1 , 4 1 ) to ( 1 2 , 1 8 , 3 8 ) (\frac{1}{2},\frac{1}{8},\frac{3}{8}) ( 2 1 , 8 1 , 8 3 ) , a label shift between B B B and C C C that leaves A A A unchanged. The rows are unchanged, so Recall A = 3 4 \operatorname{Recall}_A=\frac{3}{4} Recall A = 4 3 before and after. The one-vs-rest specificity is 1 − π C 1 − π A c C A 1-\frac{\pi_C}{1-\pi_A}c_{CA} 1 − 1 − π A π C c C A , which is 7 8 \frac{7}{8} 8 7 before and 13 16 \frac{13}{16} 16 13 after, and Precision A \operatorname{Precision}_A Precision A moves from 6 7 \frac{6}{7} 7 6 to 4 5 \frac{4}{5} 5 4 . The classifier has not changed, yet Specificity A \operatorname{Specificity}_A Specificity A moved, because the composition of the rest changed (Proposition 6 ).
For Remark 4, suppose that two steps ago the recall of A A A fell from 3 4 \frac{3}{4} 4 3 to 1 2 \frac{1}{2} 2 1 while its prior fell from 1 2 \frac{1}{2} 2 1 to 1 8 \frac{1}{8} 8 1 . With fading α = 1 2 \alpha=\frac{1}{2} α = 2 1 and a memory of four steps the accumulated recall is 5 8 \frac{5}{8} 8 5 , against an instantaneous recall of 1 2 \frac{1}{2} 2 1 and a plain weighted mean of the two recalls of 11 20 \frac{11}{20} 20 11 : the accumulation over-weights the old phase, in which A A A was frequent.
Remark 5 (Continually adapting classifiers and empirical confounding) Proposition 5 places no restriction on f t f_t f t , so it holds whether the classifier is frozen, periodically retrained or updated after every instance. The Jacobian decomposition of § 5.3 therefore needs no modification for continually learning classifiers: its concept term captures the combined rate of change from environmental concept drift (P t ( X ∣ Y ) P_t(X \mid Y) P t ( X ∣ Y ) evolving) and classifier self-adaptation (f t f_t f t evolving), and π t \pi_t π t contributes nothing to that term. Two cautions follow. First, zero functional dependence does not imply zero sample correlation between Recall(t t t ) and π t \pi_t π t over a realised trajectory: if f t f_t f t and π t \pi_t π t are driven by the same non-stationary stream, as when a classifier adapts to recent label proportions, they can co-vary. Second, the accumulated coordinates mix the prior with the history of the recall (Remark 4), which also produces residual correlations with the prior in a real stream.
Analytical Jacobian Drift Decomposition
A composite metric can be written as a differentiable function M ( R , π ) M(R,\pi) M ( R , π ) of the canonical coordinates and the prior (not to be confused with the decision function f t f_t f t ). Differentiating along the trajectory of the stream gives, in continuous time,
d M d t = J c o n c e p t T d R d t ⏟ concept term + J p r i o r d π d t ⏟ prior term (40) \frac{dM}{dt} = \underbrace{\mathbf{J}_{\mathrm{concept}}^{T}\frac{dR}{dt}}_{\text{concept term}} + \underbrace{J_{\mathrm{prior}}\frac{d\pi}{dt}}_{\text{prior term}} \tag*{(40)} d t d M = concept term J concept T d t d R + prior term J prior d t d π (40)
where J c o n c e p t = [ ∂ M / ∂ R 11 , ∂ M / ∂ R 00 ] T \mathbf{J}_{\mathrm{concept}} = [\partial M/\partial R_{11},\partial M/\partial R_{00}]^{T} J concept = [ ∂ M / ∂ R 11 , ∂ M / ∂ R 00 ] T and J p r i o r = ∂ M / ∂ π J_{\mathrm{prior}} = \partial M/\partial\pi J prior = ∂ M / ∂ π . The decomposition reparametrises the change of M M M in the coordinates ( R 11 , R 00 , π ) (R_{11},R_{00},\pi) ( R 11 , R 00 , π ) ; the concept term isolates concept drift only to the extent that R R R is free of the prior (Proposition 5 ). For the standard measures the Jacobians are, with D D D the denominator of the measure in each case:
J c o n c e p t = [ π ( 1 − π ) ( 1 − R 00 ) D 2 π ( 1 − π ) R 11 D 2 ] , J p r i o r = R 11 ( 1 − R 00 ) D 2 (41) \mathbf{J}_{\mathrm{concept}} =
\begin{bmatrix}
\frac{\pi(1-\pi)(1-R_{00})}{D^2} \\
\frac{\pi(1-\pi)R_{11}}{D^2}
\end{bmatrix},
\qquad
J_{\mathrm{prior}} = \frac{R_{11}(1-R_{00})}{D^2} \tag*{(41)} J concept = [ D 2 π ( 1 − π ) ( 1 − R 00 ) D 2 π ( 1 − π ) R 11 ] , J prior = D 2 R 11 ( 1 − R 00 ) (41)
J c o n c e p t = [ 2 π [ π + ( 1 − π ) ( 1 − R 00 ) ] D 2 2 π ( 1 − π ) R 11 D 2 ] , J p r i o r = 2 R 11 ( 1 − R 00 ) D 2 (42) \mathbf{J}_{\mathrm{concept}} =
\begin{bmatrix}
\frac{2\pi[\pi+(1-\pi)(1-R_{00})]}{D^2} \\
\frac{2\pi(1-\pi)R_{11}}{D^2}
\end{bmatrix},
\qquad
J_{\mathrm{prior}} = \frac{2R_{11}(1-R_{00})}{D^2} \tag*{(42)} J concept = [ D 2 2 π [ π + ( 1 − π ) ( 1 − R 00 )] D 2 2 π ( 1 − π ) R 11 ] , J prior = D 2 2 R 11 ( 1 − R 00 ) (42)
Accuracy, M = π R 11 + ( 1 − π ) R 00 M = \pi R_{11} + (1-\pi)R_{00} M = π R 11 + ( 1 − π ) R 00 : J c o n c e p t = [ π , 1 − π ] T \mathbf{J}_{\mathrm{concept}} = [\pi,1-\pi]^{T} J concept = [ π , 1 − π ] T and J p r i o r = R 11 − R 00 J_{\mathrm{prior}} = R_{11}-R_{00} J prior = R 11 − R 00 .
Balanced accuracy, M = ( R 11 + R 00 ) / 2 M = (R_{11}+R_{00})/2 M = ( R 11 + R 00 ) /2 : J c o n c e p t = [ 1 / 2 , 1 / 2 ] T \mathbf{J}_{\mathrm{concept}} = [1/2,1/2]^{T} J concept = [ 1/2 , 1/2 ] T and J p r i o r = 0 J_{\mathrm{prior}} = 0 J prior = 0 .
Here R R R is the time-fading state, whose prior-dependence is that of Remark 4, which the path integration below partly absorbs. For a change between two states of the stream, the decomposition is a first-order statement. Write Δ M = M ( R 1 , π 1 ) − M ( R 0 , π 0 ) \Delta M = M(R_1,\pi_1)-M(R_0,\pi_0) Δ M = M ( R 1 , π 1 ) − M ( R 0 , π 0 ) . Evaluating the Jacobians at the midpoint gives
Δ M ≈ J c o n c e p t ( R ˉ , π ˉ ) T Δ R + J p r i o r ( R ˉ , π ˉ ) Δ π , (43) \Delta M \approx\mathbf{J}_{\mathrm{concept}}(\bar{R},\bar{\pi})^{T}\Delta R + J_{\mathrm{prior}}(\bar{R},\bar{\pi})\Delta\pi, \tag*{(43)} Δ M ≈ J concept ( R ˉ , π ˉ ) T Δ R + J prior ( R ˉ , π ˉ ) Δ π , (43)
a quadrature of the line integral of ∇ M \nabla M ∇ M whose error grows with the size of the change. It is exact for a metric that is bilinear in ( R , π ) (R,\pi) ( R , π ) (Accuracy) and inaccurate for large prior changes of F 1 F_1 F 1 and Precision, where M M M is strongly curved in π \pi π . For large changes, summing the midpoint terms over intermediate states between the two end states (path integration) restores accuracy. When both R R R and π \pi π change, the split of Δ M \Delta M Δ M into a concept and a prior part depends on the order in which the two changes are applied (an interaction term), so the concept term of Eq. (43) lies near the two orderings (exactly between them for Accuracy). The sensitivity of F 1 F_1 F 1 to specificity is 2 π ( 1 − π ) R 11 / D 2 2\pi(1-\pi)R_{11}/D^2 2 π ( 1 − π ) R 11 / D 2 , which vanishes as π → 0 \pi\to0 π → 0 at fixed R 00 < 1 R_{00}<1 R 00 < 1 : a concept change in specificity moves F 1 F_1 F 1 little when positives are rare.
Example 6 (Running example: attribution of the change) For class A in Example 5, F 1 F_1 F 1 moves from 4 5 \frac{4}{5} 5 4 to 24 31 \frac{24}{31} 31 24 , a change of − 4 155 ≈ − 0.0258 -\frac{4}{155} \approx-0.0258 − 155 4 ≈ − 0.0258 . The prior π A \pi_A π A is unchanged, so the prior term is 0, and the midpoint Jacobian gives a concept term of − 96 3721 ≈ − 0.0258 -\frac{96}{3721} \approx-0.0258 − 3721 96 ≈ − 0.0258 with a residual of 7 × 10 − 6 7\times10^{-6} 7 × 1 0 − 6 . The decomposition attributes the whole change to the concept although no concept drift occurred: the movement of SpecificityA _A A comes from the other classes (Proposition 6 ). Computed on the confusion rows, which do not move, the concept term is 0.
Monitoring the Canonical Coordinates and Attributing Alarms
The decomposition answers a question about one metric: how much of an observed change of M M M is due to the concept and how much to the prior. It is not a general detector of concept change. Its concept term combines the two coordinates with signs, so changes of R 11 R_{11} R 11 and R 00 R_{00} R 00 that offset in M M M cancel in the term, and its weights shrink the sensitivity to specificity at low prior. Detection and attribution are therefore separated.
Detection acts on the canonical coordinates. For a binary stream let R ^ ( t ) \hat{R}(t) R ^ ( t ) be the class-time fading estimates of Remark 4, with n e s s + n_{\mathrm{ess}}^{+} n ess + and n e s s − n_{\mathrm{ess}}^{-} n ess − the effective numbers of positive and negative arrivals they average, and binomial variances R ^ ( 1 − R ^ ) / n e s s \hat{R}(1-\hat{R})/n_{\mathrm{ess}} R ^ ( 1 − R ^ ) / n ess . With a reference R r e f \mathbf{R}_{\mathrm{ref}} R ref and its variances, taken as the average of the estimates over a warm-up window, the statistic
χ 2 ( t ) = ∑ c ∈ { 11 , 00 } ( R ^ c ( t ) − R r e f , c ) 2 Var ^ ( R ^ c ( t ) ) + Var ^ ( R r e f , c ) (44) \chi^2(t)=\sum_{c\in\{11,00\}}\frac{\left(\hat{R}_c(t)-R_{\mathrm{ref},c}\right)^2}{\widehat{\operatorname{Var}}(\hat{R}_c(t))+\widehat{\operatorname{Var}}(R_{\mathrm{ref},c})} \tag*{(44)} χ 2 ( t ) = c ∈ { 11 , 00 } ∑ Var ( R ^ c ( t )) + Var ( R ref , c ) ( R ^ c ( t ) − R ref , c ) 2 (44)
is compared with a threshold τ \tau τ . For m > 2 m>2 m > 2 classes the same construction is applied to each confusion row c ^ k ( t ) \hat{c}_k(t) c ^ k ( t ) (with the multinomial covariance) and the maximum over rows is monitored. By Propositions 5 and 6 a label shift does not change these statistics in expectation. A per-step chi-square level controls the false alarm per step, not per run: the statistic is evaluated at every step on an autocorrelated estimator, so the run-level false alarm probability is much higher than nominal. We therefore calibrate τ \tau τ by simulation on a stationary stream with the same α \alpha α , length and priors so that the run-level false alarm probability is 5%. The binomial variances also assume independent arrivals. On the streams built by resampling they hold, and in native order the dependence of the data multiplies the variance of R ^ \widehat{R} R by the factor κ ( α ) \kappa(\alpha) κ ( α ) of Remark 2, which we measured and did not use in the detector. The positives seen after a change limit the power on the recall coordinate at low prior. § 6.3 measures this, together with four alternatives: the Jacobian z z z -alarm, ∣ J c o n c e p t T ( R ^ − R r e f ) ∣ / J c o n c e p t T ( Σ + Σ r e f ) J c o n c e p t \left|J_{\mathrm{concept}}^{T}(\widehat{R}-R_{\mathrm{ref}})\right|/\sqrt{J_{\mathrm{concept}}^{T}(\Sigma+\Sigma_{\mathrm{ref}})J_{\mathrm{concept}}} J concept T ( R − R ref ) / J concept T ( Σ + Σ ref ) J concept on time-fading coordinates, with delta-method variances R ^ ( 1 − R ^ ) / ( 2 n ) \widehat{R}(1-\widehat{R})/(2n) R ( 1 − R ) / ( 2 n ) and a reference frozen at the start of scoring; the chi-square of Eq. (44) on time-fading coordinates; DDM on the error indicator; and DDM stratified by class, one DDM on the errors of the positive arrivals and another on those of the negative arrivals, alarming when either does. The excess false alarm reported below is the paired difference between the probability of at least one alarm in a run under a label shift and under a stationary stream. Stratified ADWIN and Page-Hinkley raised almost no alarm, and their results are in the data files.
Attribution acts on a metric that a conventional monitor already tracks. When a monitor raises an alarm on M M M (for instance F 1 F_1 F 1 ), the decomposition between a reference state and the current state splits Δ M \Delta M Δ M into a concept term and a prior term, and the alarm is classified as concept-driven if the concept term accounts for at least a fraction θ \theta θ of ∣ Δ M ∣ |\Delta M| ∣Δ M ∣ (we use θ = 1 / 2 \theta=1/2 θ = 1/2 ) and as prior-driven otherwise. In the experiments the monitor raises an alarm on F 1 F_1 F 1 when it leaves a band of three standard errors around a reference window, with the delta-method variance, and the decomposition is the path-integrated one between the reference window and the current state, over 50-step block means. This triage can suppress alarms caused by a prior shift. It cannot detect a concept change that the monitored metric does not register.
Experimental Evaluation
Each subsection below tests specific claims of the paper, which are of three kinds. Exact identities (the linear decomposability of Theorem 1, the zero marginal defect of the product t t t -norm) can fail only if the proof or the code is wrong, so the experiment checks the implementation to floating-point precision. Quantitative predictions (prior invariance, detection under label shift, attribution accuracy, the bias of the interim estimator, the undefined-window rate, the complexity bounds) can fail, and we report where they do. For comparative claims (Pareto dominance, the zero-division policies) we report what holds and what does not. The synthetic experiments use fixed seeds, 30 to 200 per setting, and report means with standard deviations or intervals across seeds, except Tables 5 and Table 14 and the single-run Table 20 (single runs) and Table 24 (seven repetitions). The experiments on real streams are single runs of one stream, except the delay and censoring study of R3 and R4 in § 6.4 (15 seeds of the audit and delay draws, Table 16 ) and the comparison of learners on R4 in § 6.5 (10 seeds of the adaptive tree, Table 19 ). The streams and the protocol are described once in § 6.1 , and Table 4 lists the claim tested on each stream.
Table 4. Which claim is tested on which stream.
Table 16. Table 16 Bias against the oracle at the end of the stream, mean (sd) over 15 seeds, cumulative operator, audit budget 0.10, on R3 (Credit Card Fraud, oversampled Hoeffding tree) and R4 collapsed to a binary problem (plain Hoeffding tree, file order). The delay is simulated; class-dependent is Poisson 900 for positives and 100 for negatives. IPW uses the exact audit probability. The oracle precision is about 0.007 and the oracle F 1 F_1 F 1 about 0.014 on R3, and the oracle F 1 F_1 F 1 is about 0.96 on R4.
Table 19. NSL-KDD (R4): fraction of windows in which the adaptive tree dominates the plain tree minus the fraction in which the plain tree dominates the adaptive one, mean over 10 runs with a bootstrap interval, and the number of runs in which the adaptive tree is ahead. Only the adaptive tree has a seed; in the second block the rows are permuted within blocks of 1,000.
Table 20. Macro-temporal precision (Σ m ∘ Σ t \Sigma_m \circ\Sigma_t Σ m ∘ Σ t ) over 2 bursty rare event classes under each zero-division policy of § 3.5 . TV is computed over each convention’s own defined (non-undefined) subsequence; “Undefined” is the fraction of steps the convention leaves without a numeric value.
Datasets, Streams and Protocol
Table 2 lists the synthetic streams S1 to S10, each with a known generating process, so that the oracle value of every quantity is available. Classifier outputs on these streams are simulated from specified error rates (S2, S4, S7), from a simulated score (S5) or from a simulated posterior (S6); no model is trained on them.
Table 2. Table 2 Synthetic streams. n n n is the number of stream instances.
Table 3 lists the five real streams. Real labels are used throughout; the label-availability mechanisms are real only where stated and simulated otherwise.
Table 3. Real streams. n n n is the number of stream instances.
The real-stream experiments of § 6.4 and § 6.5 use an online Hoeffding tree from river ([18 ] ) run prequentially (test-then-train, one instance at a time) over the dataset’s native row order. The model, and where used the calibration map g t g_t g t of § 4.2 , are trained only on labels that have arrived. The label-shift studies of § 6.3 use a different protocol, because a label shift requires control of the class priors. A scikit-learn gradient-boosting classifier is trained once on an initial chunk of R1 or R2, or on a random 30% of R4 or R5, and frozen, so that P ( Y ^ ∣ X ) P(\hat{Y} \mid X) P ( Y ^ ∣ X ) is fixed. Streams are built by class-conditional resampling of the held-out pool: at each step the class is drawn from a prior path, then an instance of that class is drawn uniformly with replacement (a clean label shift) or taken in the original order within the class (native order, which keeps the real drift of P ( X ∣ Y ) P(X \mid Y) P ( X ∣ Y ) ). Concept drift is injected by permuting, across the stream instances after the change point, the values of the most important features of the frozen classifier, which lowers its recall and specificity by an amount measured on the pool.
Decomposability of the Temporal State
Theorem 1 says that, at every time step and for both operators, the measure of the pooled one-vs-rest cells equals the denominator-weighted average of the per-class measures for the linear-fractional measures, and its proof rests on the commutation of Σ t \Sigma_t Σ t with the selection matrices S j S_j S j . On S1 we keep a global multiclass state and, separately, one binary evaluator per class fed only ( y = j , p = j ) (y=j,p=j) ( y = j , p = j ) under the same operator. We compare S j C ( t ) S j T S_j C(t) S_j^{T} S j C ( t ) S j T with the binary evaluator’s table, the pooled measure with the weighted average for Accuracy, Recall, Precision, F 1 F_1 F 1 and Jaccard, and, as a contrast, the pooled MCC and balanced accuracy with the equal-weight average, since these are not linear-fractional. A violation above floating-point level would count against the theorem or the implementation. Table 5 shows that commutation and decomposition hold to rounding error under both operators, and that MCC and balanced accuracy do not decompose. This is a test of an algebraic identity, so it checks the implementation and not the claim’s empirical content.
Prior Invariance, Detection and Attribution of Drift
We test five claims. At a fixed time the canonical coordinates do not depend on the prior, while the pooled metrics do (Proposition 5 ). In the multiclass case the one-vs-rest specificity is not invariant and the confusion rows are (Proposition 6 ). A detector on the class-time coordinates raises no more false alarms under label shift than under
caption: Largest difference over 1,500 steps of S1. Decomposition is the largest of the five linear-fractional measures. Commutation is max ∣ S j C ( t ) S j T − binary evaluator ∣ \max\lvert S_j C(t) S_j^{T} - \text{binary evaluator}\rvert max ∣ S j C ( t ) S j T − binary evaluator ∣ . The last two columns are the largest difference between the pooled value and the equal-weight average of the per-class values.
:::
stationarity, once its threshold is calibrated for the run-level false alarm. The Jacobian decomposition attributes a metric change to concept and prior within a first-order error. An alarm on F 1 F_1 F 1 caused by a prior shift can be told from one caused by a concept change. A false-alarm excess under label shift, an attribution residual above 10% outside the large-shift regime, or a prior-driven alarm classified as concept-driven would count against them.
On S2, Table 6 gives the phase means over 200 seeds. A pure prior shift moves F 1 F_1 F 1 by − 0.49 -0.49 − 0.49 while Accuracy, Recall and Specificity stay within 0.01 (the classifier has T P R = T N R \mathrm{TPR} = \mathrm{TNR} TPR = TNR , so Accuracy is prior-free here). A concept drift of specificity moves F 1 F_1 F 1 by − 0.60 -0.60 − 0.60 and Accuracy by − 0.24 -0.24 − 0.24 . A monitor of F 1 F_1 F 1 therefore cannot tell the two apart, which is the motivation for the canonical coordinates.
Table 6. Phase means, mean (sd) over 200 seeds, for a pure prior shift (A: P ( Y = 1 ) P(Y=1) P ( Y = 1 ) from 0.50 to 0.05, T P R = T N R = 0.85 \mathrm{TPR} = \mathrm{TNR} = 0.85 TPR = TNR = 0.85 , S2) and an abrupt SEA concept drift (B, S3). The change is the difference of the phase means. The SEA boundary change of B also lowers the positive rate from 0.32 to 0.08, so part of the drop of F 1 F_1 F 1 in B is a prior effect; Recall and Specificity are not affected by it.
On R1 (Elec2) with a Hoeffding tree frozen after the first 20,000 instances and evaluated on the remaining 25,312, Table 7 gives the correlations with the prior π ( t ) \pi(t) π ( t ) , with moving-block bootstrap intervals (blocks of 100 steps, about two memory lengths, 2,000 resamples) and a null band from circular shifts of π ( t ) \pi(t) π ( t ) , which shows how large the correlation of two unrelated series with the same autocorrelation can be (up to 0.13 to 0.19). F 1 F_1 F 1 (0.548) and Accuracy (0.446) lie far outside the band (p = 0.002 p = 0.002 p = 0.002 ). Recall and Specificity, whether computed on the accumulated cells (0.111 and 0.124) or with class-time fading (0.138 and 0.123), lie inside it (p p p between 0.16 and 0.30), so the data show no dependence of the canonical coordinates on the prior, and they do not show that class-time fading removes any: the paired difference of the absolute correlation between the two estimators is + 0.027 +0.027 + 0.027 for recall (interval [− 0.003 -0.003 − 0.003 , + 0.061 +0.061 + 0.061 ]) and − 0.001 -0.001 − 0.001 for specificity ([− 0.017 -0.017 − 0.017 , + 0.012 +0.012 + 0.012 ]). With a classifier that keeps learning the correlations of the accumulated coordinates with the prior of the fading state are 0.316 for F 1 F_1 F 1 , −0.077 for Accuracy, 0.174 for Recall and −0.090 for Specificity, and class-time fading correlates less for both coordinates (0.122 against 0.174 for recall, 0.052 against 0.090 for specificity). Elec2 has real drift of P ( X ∣ Y ) P(X \mid Y) P ( X ∣ Y ) , so a correlation with π ( t ) \pi(t) π ( t ) in this stream cannot by itself refute Proposition 5 , and with blocks of 1,000 steps the intervals are wider than those of the table.
Table 7. Elec2 (R1), tree frozen after 20,000 instances, fading α = 0.98 \alpha= 0.98 α = 0.98 : correlation of each series with the prior π ( t ) \pi(t) π ( t ) of the fading state, a moving-block bootstrap interval, and the 95% band of ∣ corr ∣ |\operatorname{corr}| ∣ corr ∣ under circular shifts of π ( t ) \pi(t) π ( t ) with its p p p -value.
Table 8 gives the four drift profiles of S3. The abrupt, gradual and incremental profiles end in the same concept and lose 0.25 to 0.26 of specificity, with differences within one standard deviation across seeds. A single run that showed the incremental profile with the largest loss does not reproduce: it has the largest loss in none of 200 seeds. The reoccurring profile loses less because the post-drift window falls partly on a returned concept. The classifier is static, so no tracking lag is involved.
Table 8. Four drift profiles on SEA streams (S3), mean (sd) over 200 seeds. The classifier is static.
Table 9 reports, for each metric and Jacobian estimator, the share of cells (drift shape, classifier and α \alpha α ) of S2 in which the first-order residual is below 10% of the observed change of the metric. The population residual of the midpoint rule for F 1 F_1 F 1 under a prior change from 0.5 is 0.9%, 4%, 12%, 27% and 38% for final priors of 0.40, 0.30, 0.20, 0.10 and 0.05 (α = 0.98 \alpha= 0.98 α = 0.98 ), so the midpoint rule is accurate for modest changes and not for large ones, whatever the n n n changes and not for large ones, whatever the noise. Path integration over 50-step block means brings the sampled residual to 3% to 5% for final priors of 0.20 or lower, for the 0.85/0.85 classifier. For a concept change the population residual of the midpoint rule is below 1% for drops of specificity up to 0.4 and of recall up to 0.3 from a base prior of 0.5, and up to 2% for F 1 F_1 F 1 and 5% for Precision from a base prior of 0.2; the sampled residual is dominated by estimation noise when the change is small, and the estimated concept term is close to the counterfactual (for a specificity drop of 0.2, − 0.078 -0.078 − 0.078 against − 0.077 -0.077 − 0.077 ). When both change, the counterfactual depends on the order of the changes (for the 0.85 / 0.85 0.85/0.85 0.85/0.85 classifier, an interaction of − 0.03 -0.03 − 0.03 to − 0.11 -0.11 − 0.11 ), and the estimate lies between the two orderings. Accuracy is bilinear in ( R , π ) (R,\pi) ( R , π ) and the midpoint rule is exact for it.
Table 9. Table 9 Share of S2 cells in which the first-order residual of the decomposition is below 10% of the observed change of the metric (96 cells for concept only, 48 and 24 for prior only from base prior 0.5 and 0.2, 96 for both; Accuracy has valid prior-only residuals only for the asymmetric classifier, and its 83% from base prior 0.2 is 6 cells whose residual is sampling noise).
On the frozen-classifier streams the attribution reproduces the population values. For a fivefold drop of the prior, the prior term is − 0.149 -0.149 − 0.149 against − 0.156 -0.156 − 0.156 on R1 and − 0.202 -0.202 − 0.202 against − 0.216 -0.216 − 0.216 on R2, and the concept term is at most 0.006 0.006 0.006 in absolute value. For corruption only, the concept term is − 0.284 -0.284 − 0.284 , − 0.159 -0.159 − 0.159 and − 0.397 -0.397 − 0.397 against − 0.286 -0.286 − 0.286 , − 0.161 -0.161 − 0.161 and − 0.400 -0.400 − 0.400 on R1, R2 and R4. When the prior drops and the classifier is corrupted, the sum matches the observed change and the split differs from the one-order counterfactual by the interaction term.
For detection on the binary streams of S2, Table 10 compares the detector on the class-time coordinates (Eq. (44) ) with the Jacobian z z z -alarm, the same chi-square on time-fading coordinates and the standard river detectors. The nominal per-step threshold does not control the run-level false alarm: on the null stream, the default threshold gives a run-level false alarm of 0.08 to 0.68 depending on α \alpha α , because the post-reference period holds several hundred to two thousand autocorrelated checks. We therefore calibrate each threshold on the null so that the run-level false alarm is 5%, using 200 calibration seeds and evaluating on 200 disjoint seeds. The calibrated threshold grows with the stream length and decreases with α \alpha α (for the class-time chi-square at α = 0.98 \alpha= 0.98 α = 0.98 and π 0 = 0.5 \pi_0 = 0.5 π 0 = 0.5 with ( T P R , T N R ) = ( 0.85 , 0.85 ) (\mathrm{TPR},\mathrm{TNR}) = (0.85, 0.85) ( TPR , TNR ) = ( 0.85 , 0.85 ) it is 12.0 for n = 1000 n = 1000 n = 1000 and 20.8 for n = 3000 n = 3000 n = 3000 , against the nominal 11.83). Over 144 cells of prior, classifier, length and α \alpha α , the excess of the run-level false alarm under a pure label shift over the null is − 0.002 -0.002 − 0.002 and + 0.001 +0.001 + 0.001 for the two class-time detectors, with the largest single cell at 0.045, within the resolution of 200 paired seeds (± 0.04 \pm0.04 ± 0.04 ). It is + 0.055 +0.055 + 0.055 for the Jacobian alarm and + 0.064 +0.064 + 0.064 for the chi-square on time-fading coordinates, up to + 0.50 +0.50 + 0.50 at low prior, long streams and low α \alpha α . DDM on the error indicator has no excess with a symmetric classifier and an excess of up to + 0.70 +0.70 + 0.70 with ( T P R , T N R ) = ( 0.90 , 0.70 ) (\mathrm{TPR},\mathrm{TNR}) = (0.90, 0.70) ( TPR , TNR ) = ( 0.90 , 0.70 ) , because its error rate moves with the prior. The stratified DDM has no excess but a null false alarm of 0.21 because it is not calibrated.
Table 10. Detection on S2 over all cells of the sweep. Null FA is the run-level false alarm under the null. Excess FA is the paired difference between the run-level false alarm under a pure label shift and under the null, averaged over cells; in parentheses the number of cells whose interval lies above and below zero (144 cells for the calibrated detectors, 48 for the two DDM variants). Power is for an abrupt drop of specificity or recall of 0.2. Calibrated thresholds give a 5% null false alarm; DDM variants use the river defaults.
At the calibrated threshold, the class-time chi-square detects an abrupt specificity drop of 0.2 with probability 0.86 and a recall drop of 0.2 with 0.53, against 0.44 and
0.53 for the Jacobian alarm. A specificity drop is detected from the negatives, so its power hardly depends on the prior (0.87, 0.87 and 0.85 for π 0 = 0.05 \pi_0 = 0.05 π 0 = 0.05 , 0.2 and 0.5, for an abrupt drop of 0.2). A recall drop needs positives: for an abrupt recall drop of 0.2 at n = 1000 n = 1000 n = 1000 the power rises from 0.19 to 0.85 with π 0 \pi_0 π 0 , for about 25 to 250 positives after the change. Gradual and incremental drifts cost a few points of power, reoccurring drift more (0.70 against 0.86). For an abrupt specificity drop of 0.2 the median delay is 119 steps at n = 1000 n = 1000 n = 1000 and 144 at $n = 3000 (155 and 334 pooled over the four drift shapes).
Table 11 repeats the test on real instances and a real classifier, whose errors depend on x x x and are autocorrelated, on four streams (R1, R2, R4 and the Covertype stream R5). Calibrated on the shuffled null, the excess is +0.054 for the Jacobian alarm and +0.072 for the time-fading chi-square, against −0.010 and −0.005 for the class-time detectors, none of whose 12 cells has an interval above zero. The first two rise on R1 and R2, where the frozen classifier is asymmetric, and stay flatter on R4, where it is nearly symmetric. On R5, a fourth stream with an asymmetric classifier, the excess is +0.024 for the Jacobian alarm and +0.115 for the time-fading chi-square (4 of 4 cells above zero), against −0.013 and −0.019 for the class-time detectors, and the power after the corruption is 0.99 for the class-time chi-square. Power after a corruption-only change is high for the class-time chi-square on all three streams (0.90 to 0.98), with a median delay of about 120 steps on R1 against about 230 for the Jacobian alarm. In native order the real drift of P ( X ∣ Y ) P(X \mid Y) P ( X ∣ Y ) dominates: thresholds calibrated on the shuffled null give a null false alarm of 0.68 to 0.99 on R1 and R2, so alarms there cannot be read as label shift or concept drift, and thresholds calibrated on native-order null streams remove the false alarms at the price of almost no power against the corruption. To test whether the dependence of Remark 2 explains these false alarms, we divided each z z z statistic of the class-time detectors by κ ^ \sqrt{\hat{\kappa}} κ ^ and kept the threshold calibrated on the shuffled null. With κ ^ \hat{\kappa} κ ^ computed on the whole pool sequence after removing a moving average of 1,001 arrivals, the native-order null false alarm of the class-time chi-square falls from 0.99 to 0.22–0.25 on Elec2 and from 0.73–0.78 to 0.45–0.51 on Airlines, and the power after the corruption falls from 0.91–0.97 to 0.09–0.29 and from 0.91–0.95 to 0.60–0.81. With κ ^ \hat{\kappa} κ ^ computed on the 600-step warm-up window of the stream, which misses the long lags, the false alarm stays at 0.56–0.74. Without the moving average, the false alarm and the power both fall to nearly zero. On the resampled streams the warm-up estimate is close to one (1.06 to 1.10) and nothing changes, and on NSL-KDD κ ^ ≈ 1 \hat{\kappa} \approx1 κ ^ ≈ 1 . Dependence therefore explains part of the false alarms in native order. The rest is a variation of the mean that no variance inflation absorbs without removing the power, which is the real drift of P ( X ∣ Y ) P(X \mid Y) P ( X ∣ Y ) that this experiment cannot separate from the effect under test. No class-time detector shows a significant excess in native order.
Table 11. Label shift on frozen-classifier streams built from R1, R2, R4 and R5, thresholds calibrated on the shuffled null. Excess FA is the paired excess of the run-level false alarm under a prior-only change, averaged over datasets, α ∈ { 0.98 , 0.99 } \alpha\in\{0.98, 0.99\} α ∈ { 0.98 , 0.99 } and the two prior drops; in parentheses the number of cells (12 for R1, R2 and R4 together, 4 for R5) whose interval lies above zero. Power is the probability of an alarm after a corruption-only change and none before it, α = 0.98 \alpha= 0.98 α = 0.98 .
For m > 2 m > 2 m > 2 classes the one-vs-rest specificity moves with the priors of the other classes, as Proposition 6 says. Table 12 shows the consequence on S4. With a uniform confusion, where the proposition predicts invariance, no detector has an excess. With a cyclic confusion the one-vs-rest detectors have an excess of +0.40 (m = 3 m = 3 m = 3 ) and +0.33 (m = 5 m = 5 m = 5 ) at α = 0.98 \alpha= 0.98 α = 0.98 and up to +0.74 at α = 0.99 \alpha= 0.99 α = 0.99 , while the row-wise detectors stay within ±0.03. On R4 with five classes, a fivefold increase of the priors of U2R and R2L lowers the population specificity of the normal class from 0.955 to 0.880, and the one-vs-rest excess is +0.115 at α = 0.98 \alpha= 0.98 α = 0.98 and +0.605 at $\alpha = 0.99 for that shift, against 0.000 and −0.015 for the rows. The row-wise detectors also detect a concept change in the smallest row more often than the one-vs-rest ones (0.48 to 0.75 against 0.22 to 0.25 for m = 5 m = 5 m = 5 at α = 0.98 \alpha= 0.98 α = 0.98 ), although the family-wise calibration costs power: an oracle that monitors only the changed row reaches 0.80 to 0.93. When a label shift starves the changed row of arrivals, every detector is blind, and the U2R row has about five arrivals per 3,000 steps. The confusion structures of S4 are our choice, and the size of the effect depends on them.
Table 12. Excess of the run-level false alarm under label shift (mean over the label-shift scenarios) for one-vs-rest detectors on the pair (Recallj _j j , Specificityj _j j ) and row-wise detectors on the confusion rows, thresholds calibrated for a 5% family-wise false alarm. S4 for m = 3 m = 3 m = 3 and 5 classes; the last row is R4 with five classes.
For triage, Table 13 classifies the alarms of a 3-sigma monitor on F 1 F_1 F 1 . At α = 0.98 \alpha= 0.98 α = 0.98 , 93% of the alarms caused by a prior shift are classified as prior-driven and 86% of those caused by a concept change as concept-driven, with a pooled accuracy of 0.90; the pooled accuracy is 0.81 at α = 0.95 \alpha= 0.95 α = 0.95 and 0.95 at α = 0.99 \alpha= 0.99 α = 0.99 , and θ = 1 / 2 \theta= 1/2 θ = 1/2 balances the two kinds of error better than 1 / 4 1/4 1/4 or 3 / 4 3/4 3/4 . Triage is not a detector. After a prior shift to π = 0.05 \pi= 0.05 π = 0.05 the monitor on F 1 F_1 F 1 rarely fires on a later concept change (in 3% to 19% of runs), and an alarm caused by noise alone is classified as concept-driven, because noise lands in the concept term. The attribution has been tested on a binary stream with a fixed classifier, independent errors, fully labelled data and an abrupt prior change, and the other settings are not covered.
Table 13. Triage of F 1 F_1 F 1 alarms from a 3-sigma monitor on S2 with the path-integrated decomposition and θ = 1 / 2 \theta= 1/2 θ = 1/2 . Prior-driven alarms suppressed is the share of alarms in scenarios with only a prior change that are classified as prior-driven; concept alarms kept is the share of alarms caused by a concept change that are classified as concept-driven.
Verification Latency, Selective Feedback, and Auditing
Five claims are tested. With the product t t t -norm the interim stand-in has zero marginal defect (Eq. (31) ) and the verification queue stays bounded. The residual bias of the unified estimator follows the calibration error of the stand-in (Eq. (34) ). Under decision-dependent censoring with an audit budget the naive estimator is biased and the corrected one removes most of the bias. The same holds in the four label-availability settings of Table 1 . A non-zero defect, a bias that does not follow the calibration error, or a corrected estimate no closer to the oracle than the naive one would count against them. Throughout, the naive estimate is computed on the verified instances only, the corrected estimate is the unified state of Eq. (32) , in which the stand-in replaces the label of every pending or unaudited instance, and the oracle is the state obtained when every label is available at arrival.
On S5, with a non-perfect scorer, the verified recall differs from the oracle recall under label-dependent latency (Table 14 ): with positives confirmed after 60 steps and negatives after 5, the verified recall is 0.859 against an oracle of 0.711, because the verified set over-represents the class confirmed first. The product t t t -norm has zero defect for soft and for hard predictions, and the minimum and Łukasiewicz t t t -norms have a defect of about 1.17 for soft predictions and coincide with the product for hard ones. The queue is bounded by construction when Δ \Delta Δ is finite.
Airlines (R2) replaces this synthetic latency schedule with a real, covariate-dependent one (mean Δ k = 132 \Delta_k = 132 Δ k = 132 min, maximum 655 min, mean pending queue size 347). With an uncalibrated Hoeffding tree, the accuracy of the naive estimator is 0.0897 below that of the corrected one (mean absolute difference over the stream 0.0986). No oracle is evaluated, so this is the difference between the two estimators and not their bias. It is close to the calibration gap of the raw classifier, which is overconfident by 0.0906 (mean confidence 0.7284 against accuracy 0.6378), as Eq. (34) suggests. After online Platt-scaling recalibration the calibration gap is −0.0100 and the difference is −0.0165 (mean absolute 0.0448). Two points do not establish proportionality; Table 15 and the paragraph that follows test it directly.
Table 15. Recall bias against the oracle at the end of the stream, mean (sd) over 200 seeds of S6 and its variants. Audit by decision is the 10% budget for flagged instances; audit by label is 0.30 for flagged positives and 0.05 for flagged negatives; class-dependent delay is Poisson 60 for positives and 5 for negatives. Naive uses verified labels only; IPW weights verified instances by the inverse of the true audit probability, or of a probability that depends on the decision only; corrected uses a calibrated stand-in, online Platt scaling on the logit of the score, or the raw score. IPW ignores delay, so it is shown only where the audit is the only imperfection.
Table 15 reports 200 seeds of S6 and its variants. In the immediate partially labelled setting with audit by decision, the naive recall bias is −0.434, inverse-propensity weighting (IPW), which weights each verified instance by the inverse of its audit probability, is nearly unbiased with the true probability (−0.030) with a standard deviation five times that of the corrected estimator (RMSE 0.144 against 0.028), and the corrected estimator has bias +0.013. IPW is also fragile: with a label-dependent audit and a misspecified, decision-only probability it is biased by +0.227.
The bias of the corrected estimator is linear in the calibration error of the stand-in measured on the unverified instances: over eight stand-ins (logit shifts of −1 to +1, including the calibrated one, and temperatures of 0.5 to 3) the pooled slope over 1,600 runs is 0.346 (interval [0.340, 0.353]) with R 2 = 0.99 R^2 = 0.99 R 2 = 0.99 across the eight configuration means; with delayed labels the single-regressor fit is weaker (R 2 = 0.54 R^2 = 0.54 R 2 = 0.54 across configuration means) and the bias is linear only when the calibration errors of the flagged and the approved unverified instances enter separately (R 2 = 0.98 R^2 = 0.98 R 2 = 0.98 ), and it reproduces the residual of the calibrated stand-in, which is not exactly calibrated among flagged instances. Online Platt scaling on the logit of the raw score gives −0.018 in this setting, and a version that uses the raw probability as the feature is undertrained on a 2,000-step stream (−0.202).
A label-dependent audit with a six-to-one ratio leaves a corrected bias of +0.031, and the correction is partial under label-dependent delay: with the delay of S5, +0.094 in the delayed and partially labelled setting, which removes 79% of the naive bias but does not recover the oracle, and +0.055 in the fully labelled delayed setting, where the naive recall is nearly unbiased (−0.003) and the correction makes it worse.
The Credit Card Fraud stream (R3) reproduces the censoring-plus-audit composite (Eq. (25) ) on real transaction features and labels, with the censoring policy simulated on top (§ 6.1 ). At this base rate a plain Hoeffding tree predicted the majority class throughout (0 fraud predictions across 284,807 transactions), which is why R3 the oversampling wrapper. With the raw score as stand-in the corrected F 1 F_1 F 1 was 0.9469 against an oracle of 0.0119, because every censored instance is flagged by construction and its raw score is self-consistent with the decision. With online Platt-scaling recalibration trained only on observed labels, the recall bias goes from −47.3 percentage points (naive) to −0.8 points (corrected) and the specificity bias from +22.5 points to −0.01 points, on a stream in which 23.4% of the labels are censored. The corrected F 1 F_1 F 1 is 0.0109 against the oracle’s 0.0119, a relative error of 8%, and the naive F 1 F_1 F 1 is 0.0099, an error of 17%. That run has one audit seed.
Table 16 repeats the test with 15 seeds, adds delay to the censoring, and adds a second real stream, NSL-KDD collapsed to a binary problem (normal against attack, R4, file order) with a plain Hoeffding tree. The audit budget is 10%, the delay is none, Poisson 300 or class-dependent (Poisson 900 for positives and 100 for negatives), the operator is cumulative, and the model and the calibrator learn only from labels that have arrived. Without delay, the first seed reproduces the run above. The naive estimator is badly biased on both streams, in recall (−0.42 on R3, −0.24 to −0.27 on R4) whatever the delay. Inverse-propensity weighting with the exact audit probability, which is available only because we simulated the audit, is nearly unbiased in recall (within 0.005) under the cumulative operator. The corrected estimator recovers recall on R4 (bias −0.04 for every delay) and on R3 without delay (−0.010), but it is only partial elsewhere. On R3 with delay its recall bias is −0.14 and F 1 F_1 F 1 is underestimated by about two thirds (−0.010 against an oracle of about 0.014); on R4 it underestimates specificity (−0.074), precision (−0.09) and F 1 F_1 F 1 (−0.05) with or without delay. In a diagnostic run (R4, seed 0, no delay) the calibrated stand-in averaged 0.862 on the censored flagged instances against a true rate of 0.960; we did not diagnose the other cases, and the stand-ins disagree among themselves (Platt scaling on the logit gives +0.04 in recall on R3, and the raw score is far off, with a precision bias of +0.89). So the statement that the correction removes the censoring bias holds for recall on R4 and on R3 without delay, and not for R3 with delay or for precision, specificity and F 1 F_1 F 1 on R4. Under fading with α = 0.999 \alpha= 0.999 α = 0.999 IPW is noisy on R3 (recall bias −0.29, sd 0.41, with about 1.7 effective frauds in memory). With the eviction tolerance 10 − 4 10^{-4} 1 0 − 4 , the queue holds on average 243 (R3) and 170 (R4) entries under Poisson 300, and 80 and 110 under the class-dependent delay, when only audited instances are queued, and 528 to 1,154 entries when every instance is queued; eviction removed no audited entry in any run.
Table 17 runs the four settings on S6. Without censoring, the naive estimator is already close to the oracle, because a latency of about 25 steps is small against the memory n e f f = 100 n_{\mathrm{eff}} = 100 n eff = 100 , so delay alone shifts the estimate little and the interim correction mainly reduces its variability (recall bias sd 0.037 against 0.052). Censoring produces the large bias (−0.43 in recall for the naive estimator), and the corrected estimator removes it with or without delay. Adding delay to censoring changes the bias of neither estimator and increases the spread of the corrected one (recall bias sd 0.048 against 0.027 without delay), presumably because the stand-in stays in place until the label arrives; we did not isolate this. Where the system decides which labels to request, the queue holds only the selected instances still pending (19 on average in setting (iv)), whereas holding every instance until eviction needs 115 entries. These queue sizes are counted from the arrival schedule, and Table 18 reports them again with the eviction step executed.
Table 18 runs the sliding-window form of the interim estimator (W = 100 W = 100 W = 100 ) and the eviction step of Algorithm 1 (fading α = 0.99 \alpha= 0.99 α = 0.99 , tolerance ε = 10 − 4 \varepsilon= 10^{-4} ε = 1 0 − 4 , every instance queued) on S6 over 100 seeds. The windowed corrected estimator removes the censoring bias as the fading one does (recall bias +0.014 against −0.444 for the naive windowed estimator in setting (iii)). It also does when the delay is longer than the window (Poisson 150, setting (v)): every instance leaves the window unverified, the state consists of interim terms only, and its recall bias of +0.008 is the quality of the stand-in itself. The queue sizes of fading with eviction (96.3 and 115.3) reproduce the counts of Table 17 . With ε = 10 − 4 \varepsilon= 10^{-4} ε = 1 0 − 4 eviction (after s ∗ = 458 s^* = 458 s ∗ = 458 steps) changes the state in no run, because no label arrives that late. With ε = 5 × 10 − 3 \varepsilon= 5 \times10^{-3} ε = 5 × 1 0 − 3 (s ∗ = 69 s^* = 69 s ∗ = 69 steps) and the delay of setting (v), eviction does discard late corrections: it changes the state by at most 2.4 cell units on a total mass of about 100 (mean over seeds of the largest change 1.5), the recall bias is +0.011 against +0.010 without eviction, and the queue shrinks from 348 to 68 entries.
Multiclass Structural Diagnostics and Zero-Division Auditing
Three claims are examined. Pareto dominance over time separates learners that a scalar metric ranks arbitrarily; this is a demonstration of the framework and not a falsifiable prediction. We tested the conjecture that the exclude policy gives the smoothest macro trajectory, and it does not hold across regimes; what we claim instead is the audit property, that exclude and nan never report a number for a class without verified support. Except for S10 below, the experiments of this subsection have no latency, where the verified and the interim supports coincide. The undefined-window probability of Proposition 4 and the direction of its bursty extension (Remark 3) are tested on a real truncation timeline. Pareto dominance is defined at a time step: learner a a a dominates b b b if R 11 a ( t ) ≥ R 11 b ( t ) R^{a}_{11}(t) \ge R^{b}_{11}(t) R 11 a ( t ) ≥ R 11 b ( t ) and R 00 a ( t ) ≥ R 00 b ( t ) R^{a}_{00}(t) \ge R^{b}_{00}(t) R 00 a ( t ) ≥ R 00 b ( t ) with at least one strict inequality, and the two are incomparable if neither dominates.
On S7, over 100 seeds, Models A and B are incomparable in 98.8% of the windows (standard deviation 2.2 points) as their generating rates are, so any ranking between them by F 1 F_1 F 1 or Accuracy is an artifact of metric scalarization. The generating rates of Model C dominate those of Model A on both coordinates, yet the fading estimates (n e f f = 50 n_{\mathrm{eff}} = 50 n eff = 50 ) show C dominating A in only 60.7% of the windows (standard deviation 12.3 points), because of sampling noise at this memory, which the Pareto relation, unlike a scalar ranking, makes visible. A single seed gave 54.4%. The relation is that of the ROC convex hull [25 ] , extended to continuously updated temporal states.
NSL-KDD (R4) is the only multiclass real benchmark of this paper, and its row order is not chronological (§ 6.1 ). Applying the S j S_j S j projection (Eq. (7) ) to its five classes and comparing a plain with an adaptive Hoeffding tree gave, in one run (native order, adaptive seed 2027), a pattern in which the adaptive tree dominates more often on the rare classes (R2L: 39.2% against 16.3% of windows; U2R: 41.9% against 16.1%) and the plain tree on normal (20.7% against 9.8%). Table 19 shows that this run does not represent the other seeds. Over 10 seeds of the adaptive tree the adaptive advantage on normal, DoS and Probe is stable (DoS in 10 of 10 seeds), the single run was at the favourable end for R2L and U2R, and for normal it had the opposite sign to the mean. For R2L and U2R the sign is not stable across seeds (6 and 5 of 10), and when the rows are permuted within blocks of 1,000 it reverses (the adaptive tree ahead in 2 and 4 of 10 orders). The Pareto relation therefore separates the learners per class, but for the rare classes of this stream the sign of the difference depends on the seed and the order.
On S8, whose rare event classes arrive in bursts, Table 20 shows the macro-precision trajectory under the policies of § 3.5 . In this single run exclude reduces the total variation of the trajectory by 34% against the zero default (17.66 against 26.85) while flagging 26.4% of steps as partly undefined, and one, which counts 0/0 as 1.0 (11.85), is not reliably worse than exclude. Over 100 seeds the reduction is 21.6% (standard deviation 18.0 points), but the total variation is summed over different numbers of steps (the policies leave different shares of the stream undefined); per defined step it is −4.7% (standard deviation 26 points, interval [−9.8, +0.4]), so the smoothness advantage disappears once the number of steps is accounted for.
We repeated the protocol on two real streams, Credit Card Fraud (R3), whose fraud arrivals cluster in time, with a single binary metric and W = 200 W = 200 W = 200 , and NSL-KDD’s four event classes (R4; DoS, Probe, R2L, U2R, excluding the normal background) with W = 300 W = 300 W = 300 . Table 21 gives the outcome: the smoothing effect is negligible on real binary data (+2%) and reverses on the real multiclass stream (−35%). In 79% of the NSL-KDD windows three or four of the four event classes are supported, so this is not the regime of mostly empty support; the fluctuating membership of exclude shifts the average each time a class enters or leaves the support, a larger jump than the fixed composition of zero with occasional zero padding, since the rare classes’ true precision is often close to zero. These total variations are raw sums and have the step-count issue noted above.
Table 21. The exclude-vs-zero smoothness comparison across one synthetic and two real streams (Δ>0: exclude smoother). Sign and magnitude are regime-dependent, not a fixed property of the policy; NSL-KDD’s raw TV values are omitted as they are not directly comparable in scale to the other two rows’ single-metric TV (four-class macro composition vs. one).
The smoothness claim does not generalise, and we do not carry it forward. What holds in all three settings of Table 21 is the audit property: exclude and nan never report a number for a class without verified support, while zero and one always do, whether or not their constant happens to be close to the truth. With latency the property needs the verified support of § 3.5 , which only the experiment on S10 below exercises.
On S10 (three classes, window W = 60 W = 60 W = 60 , the rare class with prior 0.05), Table 22 compares the probability that no instance of the rare class in the window is verified with the formula of Corollary 2: 0.161 against 0.166 for a constant delay of 25, 0.409 against 0.412 with an audit probability of 0.5, 0.163 and 0.422 against 0.167 and 0.413 with Poisson delays, and 1 for a delay of 70 ≥ W W W . The probability that the class is absent from the window is 0.042 throughout. The verified support never reports a value for a class with no true instance, whereas the interim support does so in 4.2% of the steps, those at which the class is absent, because the stand-in always puts mass on it. The price is accuracy: the absolute error of the macro recall under exclude against the oracle is 0.012 to 0.041 with the verified support and 0.006 with the interim support, because the verified support drops a class that is present but whose labels are pending, and with a delay beyond the window it leaves the macro recall undefined.
Table 22. Verified support under latency on S10 (window W = 60 W = 60 W = 60 , rare class prior 0.05; 4 runs of 20,000 steps per row). Formula is the probability of Corollary 2 that no instance of the rare class is verified; Empirical is its frequency; Class absent is the frequency with which the class has no true instance in the window. MAE is the absolute error of the macro recall under exclude against the oracle when the support is the verified or the interim one.
On how often a policy trigger fires, Table 23 compares the empirical undefined-window rate on the chronologically ordered Credit Card Fraud stream, at the class’s marginal rate p = 0.001727 p = 0.001727 p = 0.001727 , with the i.i.d. prediction of Eq. (19) for three window sizes. The real rate exceeds the i.i.d. baseline at every W W W , by a factor of 1.1 at W = 200 W = 200 W = 200 , 1.4 at W = 500 W = 500 W = 500 and 2.2 at W = 1,000 W = 1{,}000 W = 1 , 000 , which is the direction that Remark 3 predicts for clustered arrivals. The Markov formula of that remark predicts 56.4% for the generator of S8 and a simulation of 4 × 10 5 4 \times10^{5} 4 × 1 0 5 steps gives 57.6% on average over three seeds and two classes (standard deviation 0.7 points).
Table 23. Undefined-window rate for the fraud class on the real, chronologically-ordered Credit Card Fraud stream (p = 0.001727 p = 0.001727 p = 0.001727 , n = 284,807 n = 284{,}807 n = 284 , 807 ), against the i.i.d. prediction of Eq. (19) at the same marginal rate. The growing gap is the real-data signature of the same clustering mechanism Remark 3 quantifies on the synthetic bursty generator.
Computational Throughput and Memory Footprint
Propositions 1 and 2 claim an update cost that does not depend on the stream length for both operators, with constant memory for fading and memory growing with W W W for the window. Table 24 gives the median of seven repetitions on S9 for fading and for windows from W = 100 W = 100 W = 100 to W = 100,000 W = 100{,}000 W = 100 , 000 . The time per instance of the window operator is about 1.1 to 1.3 times that of fading and does not grow with W W W over three orders of magnitude, while its memory grows linearly with W W W . The measured memory is about five times the analytic buffer size (two vectors of m m m doubles per stored instance) because of Python object overhead. The evaluators measured here are those of the package (§ 7 ), which validates its input at every update. Absolute times depend on the hardware; the claim is carried by the independence of W W W for time and the proportionality to W W W for memory.
Software
The framework is implemented as the experimental subpackage aggmetrics.stream of the aggmetrics Python package for indicator-matrix evaluation (Prati [23 ] ), from version 0.4.0 (https://github.com/rcprati/aggmetrics ; DOI of the version: https://doi.org/10.5281/zenodo.24291757 ). It is installed with pip install aggmetrics, needs only NumPy, and a notebook of the package (gallery notebook 17) shows its main functions on simulated streams. A TemporalState holds the state C ( t ) C(t) C ( t ) under exponential fading, a sliding window or no forgetting, and evaluates any measure of the package’s registry on it with the three aggregation operators, the zero-division policies of § 3.5 and the audit tuple ( u , m a c t i v e ) (u, m_{\mathrm{active}}) ( u , m active ) ; with a reference prior it returns the value of a measure at that prior, the quantity monitored in § 5.4 . A ClassTimeState gives the class-time estimates of Remark 4. A DelayedEvaluator is Algorithm 1 in both of its forms, with the interim term, the correction, the eviction and the window FIFO, and reports the verified and the interim support and the coverage κ j \kappa_j κ j of § 3.5 . attribute splits the change of a measure between two states into a concept and a prior part, by the counterfactual, the symmetric or the path-integrated Jacobian form of § 5.3 , and triages an alarm. The closed forms of the paper (the undefined-window probability of Proposition 4, the window size of Corollary 1, the queue bound of Eq. (33) and the factor κ ( α ) \kappa(\alpha) κ ( α ) of Remark 2) are in stream.sizing, so that a window or a fading factor can be sized before deployment. The chi-square monitor of § 5.4 and the calibration of its threshold are included and marked experimental, with the limits stated there.
ev = DelayedEvaluator(2, alpha=0.98, eps=1e-3) # Algorithm 1, fading
k = ev.arrive(proba, y_pred) # interim term, product t-norm
ev.label(k, y_true) # correction when the label comes
ev.compute("recall") # value under the verified support
ev.coverage() # verified share of each class
attribute("f1", ref.snapshot(), cur.snapshot()).triage()
The states are tested against the package’s batch evaluation on the same data, for the cumulative and the window states, against the decomposability of Theorem 1 for every decomposable measure, against the values of the running example of Appendix § 11 , and against simulation for the closed forms. It has full branch coverage. The experiments of § 6 run on the package: the evaluators of their scripts are thin adapters over it. A class with less than 10 − 12 10^{-12} 1 0 − 12 of the mass of the state is reported as undefined, since a ratio of such masses is a number made of rounding residue. The subpackage is experimental, and its interface may change in a later release.
Conclusions and Future Directions
We extended the indicator-matrix framework of classification evaluation [24 ] to data streams. The temporal operator Σ t \Sigma_t Σ t gives exponential-fading and sliding-window evaluation with an update cost that does not depend on the stream length, and linear decomposability between pooled and per-class measures holds under it. Delayed and selective feedback form an observation mask whose four corners are the four label-availability settings of the literature. An interim estimate built with the product t t t -norm fills the gap left by missing labels, and its bias is linear in the calibration error of the estimate when labels are not delayed. Zero-division voids are handled by audited conventions. Prior shift and concept drift are separated by monitoring prior-free coordinates and attributing a metric change with a first-order Jacobian decomposition.
The experiments changed some of our expectations. Detectors on class-time coordinates raise no excess false alarms under label shift on synthetic streams, on four frozen-classifier real streams and with several classes, while the Jacobian alarm we first proposed as a detector, and DDM on the error indicator, do. The Jacobian decomposition is useful for attribution and for triage of alarms, not as a general detector. The one-vs-rest specificity is not prior-free with several classes, so the confusion rows are the coordinates to monitor. The smoothness advantage we expected from excluding unsupported classes depends on the stream, and what we claim for the zero-division policies is that, with the verified support, they report no value for a class that has none. The correction of selection bias is only partial when the delay depends on the label and, on the real streams tested, for precision, specificity and F 1 F_1 F 1 on NSL-KDD and for recall on Credit Card with delay.
The evidence has limits. The detection and attribution studies use simulated streams, and frozen classifiers on real streams with the label shift imposed by resampling; in native order the real drift of P ( X ∣ Y ) P(X \mid Y) P ( X ∣ Y ) cannot be separated from the effect under test. A calibrated threshold that depends on α \alpha α and on the stream length is needed for a given run-level false alarm, and the power for a recall change is low at low prior. The variance model of the detector assumes independent arrivals, which holds for the resampled streams and not for native order, where Remark 2 measures an inflation that the detector does not correct. The sliding-window form of the interim estimate is run on one synthetic stream only, the eviction step of Algorithm 1 on that stream and on two real ones, the interim estimate on the synthetic streams is a noisy oracle and not a learned model, and the real-stream delay and censoring experiments simulate both on real features and labels. Future work includes interim estimators that adapt to calibration drift, tracked online with class-conditional calibration errors.
Twenty-five statements of the paper were checked in Lean 4 against Mathlib. Each covers the algebraic or analytic core of the statement, with probabilistic steps taken as hypotheses or left out. They are the decomposability of Theorem 1, for any nonnegative temporal weighting, including the commutation of Σ t \Sigma_t Σ t with the selection matrices and the classes with a zero denominator; the fading and sliding-window recurrences (Eqs. (2) and (3) ); the exact split of a change of the pooled measure into an intrinsic and a prevalence part (Eq. (12) ); the marginal consistency of the product t t t -norm (Eqs. (28) and (29) ), with the marginal defects of the minimum and the Łukasiewicz t t t -norm on the soft prediction of the running example (Example 4) and their agreement with the product on hard predictions; the bias identity of Eq. (34) and its zero expectation under calibration; the invariant of Algorithm 1 for exponential fading, which is the unified state of Eq. (32) without eviction and, with eviction, that state minus the discarded corrections, whose effect on each entry is bounded by the tail mass of Eq. (33) and by ε \varepsilon ε per discarded correction; the bound on the queue, with the explicit age s ∗ s^* s ∗ above; the independence of the column sums of the unified state from the stand-in; the audit property of the policies exclude and nan (no number for a class without support), with the value of zero as the exclude average shrunk by the share of supported classes; the cell-ratio lemma and Proposition 5 , with the recall and the specificity as integrals of the decision function against the class-conditional laws, free of the prior, and the dependence of the precision on it, shown on a numerical example; the undefined-window probability of Proposition 4, exact for the sliding window and bounded on both sides under fading, derived from the independence of the arrivals (Mathlib’s iIndepSet), with the two ages of the fading bounds taken through their defining inequalities; the latency corollary (Corollary 2), with its value for a constant delay and the window size it requires; the multiclass invariance of Proposition 6 , with the specificity formula and the values of the running example; the window-sizing rule of Corollary 1; the expectation and the variance of the fading estimator in Proposition 3, for every t t t and from the independence of the entries, with their limits; the variance of the fading estimator for autocorrelated entries (Remark 2), exact for every t t t and converging to Eq. (16) , with κ = 1 \kappa=1 κ = 1 for independent entries and κ = ( 1 + α r ) / ( 1 − α r ) \kappa=(1+\alpha r)/(1-\alpha r) κ = ( 1 + α r ) / ( 1 − α r ) for ρ d = r d \rho_d=r^d ρ d = r d ; the chain-rule form of the decomposition of Eq. (40) ; the closed-form Jacobians of the precision, F 1 F_1 F 1 and the accuracy and the exactness of the mid-point rule for the accuracy (§ 5.3 ); and the state after an abrupt drift with its half-life, the tracking lag under a steady velocity and the damping of a transient outlier (§ 5.1 ). The values of the running example are also recomputed in Lean. The bursty extension of the undefined-window probability (Remark 3), the sliding-window form of the algorithm with eviction, the complexity bounds, the Jacobian of the balanced accuracy, the error of the mid-point rule for F 1 F_1 F 1 and the precision, and the gradual and reoccurring drift profiles are not formalized. The formalization is at https://github.com/rcprati/aggmetrics-datastream-lean, and the implementation of § 7 is in the aggmetrics package, version 0.4.0 or later [23 ] .
Statements and Declarations
Funding. This work was supported by the São Paulo Research Foundation (FAPESP) and the National Council for Scientific and Technological Development (CNPq, grant 310534/2025-9).
Competing interests. The authors have no relevant financial or non-financial interests to disclose.
Ethics approval and consent to participate. Not applicable. The study uses public benchmark data sets and simulated streams, with no human participants or animals.
Data availability. All data sets are public: Electricity (Elec2) [14 ] , Airlines (Vanschoren et al. 2014), Credit Card Fraud [6 ] , NSL-KDD (Tavallaee et al. 2009) and Covertype (distributed with scikit-learn). The synthetic streams are generated by the code described under Code availability.
Code availability. The experiment scripts, the tables, the figures and the generated result files are at https://github.com/rcprati/data-stream-evaluation; the real data sets are fetched by a script of the repository. The Lean 4 formalization is at https://github.com/rcprati/aggmetrics-datastream-lean. The implementation of § 7 is in the aggmetrics package (https://github.com/rcprati/aggmetrics), version 0.4.0 or later, released on GitHub and archived on Zenodo (https://doi.org/10.5281/zenodo.24291757) [23 ] .
Author contributions. Ronaldo C. Prati: conceptualization, methodology, formal analysis, software, investigation, data curation, validation, visualization, writing – original draft, writing – review and editing, project administration. Elaine Ribeiro de Faria: conceptualization, validation, writing – review and editing. All authors approved the final manuscript.
Use of generative AI. The authors used Claude (Anthropic), through Claude Code, to help write and review code, run and analyse the experiments, develop the Lean 4 formalization, and draft and revise parts of the text. The authors specified the research questions and the design, reviewed and verified the outputs, and take full responsibility for the content.
Notation
The Running Example in Full
All values below are produced by experiments/running_example.py in exact fractions. The stream has 8 instances, with true labels A B A C B A B B A B A C B A B B A B A C B A B B and predictions A B B C B A C B A B B C B A C B A B B C B A C B . The label of instance k k k arrives at time k + Δ k k+\Delta_k k + Δ k , that is at t = ( 1 , 3 , 5 , 7 , 7 , 9 , 9 , 9 ) t=(1,3,5,7,7,9,9,9) t = ( 1 , 3 , 5 , 7 , 7 , 9 , 9 , 9 ) , and instance 7 is never labelled.
Temporal state (Example 1). Under fading with α = 1 2 \alpha=\frac{1}{2} α = 2 1 , C α ( 4 ) C_{\alpha}(4) C α ( 4 ) has rows ( 1 16 , 1 4 , 0 ) \left(\frac{1}{16},\frac{1}{4},0\right) ( 16 1 , 4 1 , 0 ) , ( 0 , 1 8 , 0 ) \left(0,\frac{1}{8},0\right) ( 0 , 8 1 , 0 ) , ( 0 , 0 , 1 2 ) \left(0,0,\frac{1}{2}\right) ( 0 , 0 , 2 1 ) and mass 15 16 \frac{15}{16} 16 15 . Under the window W = 4 W=4 W = 4 , C W ( 8 ) C_{W}(8) C W ( 8 ) has rows ( 1 4 , 0 , 0 ) \left(\frac{1}{4},0,0\right) ( 4 1 , 0 , 0 ) , ( 0 , 1 2 , 1 4 ) \left(0,\frac{1}{2},\frac{1}{4}\right) ( 0 , 2 1 , 4 1 ) , ( 0 , 0 , 0 ) \left(0,0,0\right) ( 0 , 0 , 0 ) .
Decomposition and the void (Examples 2 and 3). The per-class tables (TP, FN, FP, TN) are ( 1 4 , 0 , 0 , 3 4 ) \left(\frac{1}{4},0,0,\frac{3}{4}\right) ( 4 1 , 0 , 0 , 4 3 ) , ( 1 2 , 1 4 , 0 , 1 4 ) \left(\frac{1}{2},\frac{1}{4},0,\frac{1}{4}\right) ( 2 1 , 4 1 , 0 , 4 1 ) , ( 0 , 0 , 1 4 , 3 4 ) \left(0,0,\frac{1}{4},\frac{3}{4}\right) ( 0 , 0 , 4 1 , 4 3 ) and the pooled table is ( 3 4 , 1 4 , 1 4 , 7 4 ) \left(\frac{3}{4},\frac{1}{4},\frac{1}{4},\frac{7}{4}\right) ( 4 3 , 4 1 , 4 1 , 4 7 ) . Precision is ( 1 , 1 , 0 ) (1,1,0) ( 1 , 1 , 0 ) per class, with weights ( 1 4 , 1 2 , 1 4 ) \left(\frac{1}{4},\frac{1}{2},\frac{1}{4}\right) ( 4 1 , 2 1 , 4 1 ) , pooled and weighted macro 3 4 \frac{3}{4} 4 3 , unweighted macro 2 3 \frac{2}{3} 3 2 . Recall is ( 1 , 2 3 , undefined ) (1,\frac{2}{3},\text{undefined}) ( 1 , 3 2 , undefined ) with weights ( 1 4 , 1 2 , 0 ) \left(\frac{1}{4},\frac{1}{2},0\right) ( 4 1 , 2 1 , 0 ) , pooled and weighted macro 3 4 \frac{3}{4} 4 3 ; the macro recall is 5 6 \frac{5}{6} 6 5 (exclude), 5 9 \frac{5}{9} 9 5 (zero), undefined (nan); u = ( 1 , 1 , 0 ) u=(1,1,0) u = ( 1 , 1 , 0 ) .
Delayed labels (Example 4). In the window, instance 5 is verified, 6 and 8 are pending, and 7 is never labelled. The verified part is 1 32 ( 0 , 0 , 0 ; 0 , 8 , 0 ; 0 , 0 , 0 ) \frac{1}{32}(0,0,0;0,8,0;0,0,0) 32 1 ( 0 , 0 , 0 ; 0 , 8 , 0 ; 0 , 0 , 0 ) , the interim part is 1 32 ( 6 , 1 , 1 ; 1 , 6 , 1 ; 1 , 1 , 6 ) \frac{1}{32}(6,1,1;1,6,1;1,1,6) 32 1 ( 6 , 1 , 1 ; 1 , 6 , 1 ; 1 , 1 , 6 ) , so that C ( 8 ) = 1 32 ( 6 , 1 , 1 ; 1 , 14 , 1 ; 1 , 1 , 6 ) C(8)=\frac{1}{32}(6,1,1;1,14,1;1,1,6) C ( 8 ) = 32 1 ( 6 , 1 , 1 ; 1 , 14 , 1 ; 1 , 1 , 6 ) with mass 1 1 1 ; the oracle is 1 32 ( 8 , 0 , 0 ; 0 , 16 , 8 ; 0 , 0 , 0 ) \frac{1}{32}(8,0,0;0,16,8;0,0,0) 32 1 ( 8 , 0 , 0 ; 0 , 16 , 8 ; 0 , 0 , 0 ) and the difference is 1 32 ( 2 , − 1 , − 1 ; − 1 , 2 , 7 ; − 1 , − 1 , − 6 ) \frac{1}{32}(2,-1,-1;-1,2,7;-1,-1,-6) 32 1 ( 2 , − 1 , − 1 ; − 1 , 2 , 7 ; − 1 , − 1 , − 6 ) , equal to the right-hand side of Eq. (34) . Recalls (oracle, C ( 8 ) C(8) C ( 8 ) , verified only) are A: 1 1 1 , 3 4 \frac{3}{4} 4 3 , undefined; B: 3 8 \frac{3}{8} 8 3 , 1 1 1 ; C: undefined, 3 4 \frac{3}{4} 4 3 , undefined. For the label-side denominators the verified support is ( 0 , 1 , 0 ) (0,1,0) ( 0 , 1 , 0 ) and the coverage ( 0 , 1 2 , 0 ) (0,\frac{1}{2},0) ( 0 , 2 1 , 0 ) ; the macro recall under the verified support is 7 8 \frac{7}{8} 8 7 (exclude), 7 24 \frac{7}{24} 24 7 (zero), undefined (nan). The column sums of C ( 8 ) C(8) C ( 8 ) and of the oracle are both ( 1 4 , 1 2 , 1 4 ) (\frac{1}{4},\frac{1}{2},\frac{1}{4}) ( 4 1 , 2 1 , 4 1 ) . The marginal defect of the stand-in of instance 7 7 7 is ( 0 , 3 2 , 1 ) (0,\frac{3}{2},1) ( 0 , 2 3 , 1 ) for (product, minimum, Łukasiewicz) against the soft prediction ( 1 8 , 1 8 , 3 4 ) (\frac{1}{8},\frac{1}{8},\frac{3}{4}) ( 8 1 , 8 1 , 4 3 ) , and ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) against the hard one. The correction for instance 6 6 6 is 1 32 ( 2 , 0 , 0 ; − 1 , 0 , 0 ; − 1 , 0 , 0 ) \frac{1}{32}(2,0,0;-1,0,0;-1,0,0) 32 1 ( 2 , 0 , 0 ; − 1 , 0 , 0 ; − 1 , 0 , 0 ) under the window and 1 64 ( 2 , 0 , 0 ; − 1 , 0 , 0 ; − 1 , 0 , 0 ) \frac{1}{64}(2,0,0;-1,0,0;-1,0,0) 64 1 ( 2 , 0 , 0 ; − 1 , 0 , 0 ; − 1 , 0 , 0 ) under fading at t = 8 t=8 t = 8 ; the fading weights of instances 6 6 6 and 8 8 8 are 1 8 \frac{1}{8} 8 1 and 1 2 \frac{1}{2} 2 1 , and the eviction age for ε = 1 32 \varepsilon=\frac{1}{32} ε = 32 1 is s ∗ = 5 s^*=5 s ∗ = 5 .
Label shift (Examples 5 and 6). With rows ( 3 4 , 1 4 , 0 ) (\frac{3}{4},\frac{1}{4},0) ( 4 3 , 4 1 , 0 ) , ( 0 , 3 4 , 1 4 ) (0,\frac{3}{4},\frac{1}{4}) ( 0 , 4 3 , 4 1 ) , ( 1 4 , 0 , 3 4 ) (\frac{1}{4},0,\frac{3}{4}) ( 4 1 , 0 , 4 3 ) and the prior ( 1 2 , 1 2 , 1 4 ) → ( 1 2 , 1 8 , 3 4 ) (\frac{1}{2},\frac{1}{2},\frac{1}{4}) \to(\frac{1}{2},\frac{1}{8},\frac{3}{4}) ( 2 1 , 2 1 , 4 1 ) → ( 2 1 , 8 1 , 4 3 ) , the values of ( R e c a l l A , S p e c i f i c i t y A , P r e c i s i o n A , F 1 A ) (\mathrm{Recall}_A,\mathrm{Specificity}_A,\mathrm{Precision}_A,F^A_1) ( Recall A , Specificity A , Precision A , F 1 A ) are ( 3 4 , 7 8 , 6 7 , 2 4 ) (\frac{3}{4},\frac{7}{8},\frac{6}{7},\frac{2}{4}) ( 4 3 , 8 7 , 7 6 , 4 2 ) before and ( 3 4 , 13 16 , 4 5 , 24 31 ) (\frac{3}{4},\frac{13}{16},\frac{4}{5},\frac{24}{31}) ( 4 3 , 16 13 , 5 4 , 31 24 ) after. The change of F 1 A F^A_1 F 1 A is − 4 155 -\frac{4}{155} − 155 4 , and the midpoint concept term is − 96 3721 -\frac{96}{3721} − 3721 96 with prior term 0 0 0 . The accumulated recall of the example in Example 5 is 5 8 \frac{5}{8} 8 5 .
Table A1. Summary of notation used throughout the paper.