betaFeedback

WorksComputer Science

A Temporal Algebraic Framework for Data Stream Evaluation Under Delayed Labels and Distribution Shifts

Abstract

In data streams, labels often arrive late or only for some instances, class prevalence drifts, and rare classes vanish from short windows. Standard evaluation then confuses a degraded decision boundary with a change in prevalence, and is biased when labels are delayed or selected by the model. We extend an algebraic framework that obtains pooled (micro) and per-class (macro) measures from one confusion matrix to streams, weighting the counts in time by exponential fading or a sliding window; the update costs O(m^2) per step, whatever the stream length, and each pooled measure stays a weighted combination of the per-class ones. Delayed and selective feedback enter as an observation mask: until its label arrives, an instance is counted with the model's calibrated class probabilities, and the bias of this interim estimate is driven by their calibration error. Audited conventions report no value for a class without verified instances. We separate prior shift from concept drift by monitoring prior-free coordinates (recall and specificity) and attribute a change in a measure to the two sources with a first-order Jacobian decomposition. On synthetic streams and four real datasets, a detector on these coordinates with a memory per class raises no excess false alarms under label shift, unlike the Jacobian alarm and error-rate detectors. The correction for delayed labels recovers recall in some real settings and is only partial for precision, specificity and F1. Twenty-five statements are checked in Lean 4, and the code is in the aggmetrics package.

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 (WW). 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 pt\mathbf{p}_t are made at time tt but the true labels yt\mathbf{y}_t arrive after an uncertain latency Δt\Delta_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 F1F_1 depend on the class prior Pt(Y)P_t(Y), so a change in class prevalence moves them even when the decision boundary Pt(Y∣X)P_t(Y \mid 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 tt, and each label arrives separately at time k+Δkk + \Delta_k with latency Δk≥0\Delta_k \ge0. Both flows feed the temporal operator Σt\Sigma_t, which keeps one evolving state C(t)C(t). The global view reduces 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) (base layer, § 3) feeds two evaluation branches: functional reduction compositions (Σ∘Σt\Sigma\circ\Sigma_t, Branch A, § 3.2) and structural per-class projections (SjS_j, Branch B, § 3.3). Theorem 1 (§ 3.4) relates them. The dashed arrow shows that the per-class matrices Cj(t)C_j(t) of Branch B are the input of the macro reduction Σm∘Σt\Sigma_m \circ\Sigma_t of Branch A.

Our contributions are as follows.

  1. A temporal reduction operator Σt\Sigma_t that weights the confusion counts in time, in exponential-fading and sliding-window forms. It updates in O(m2)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).

  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 tt-norm, with a queue bounded by an analytic bound (Algorithm 1) and a bias that follows the calibration error of those probabilities.

  1. 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.

  1. 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) and sliding windows WW 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), prior probability shift P(Y)P(Y) and concept drift P(Y∣X)P(Y \mid 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, F1F_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. 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 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 and the core reduction operators (Σ1\Sigma_1, Σm\Sigma_m).

For readers unfamiliar with Prati [24], we briefly recall the two objects this paper extends. The core framework represents a batch of nn classified instances as a pair of indicator matrices Y,Y^∈Rn×mY,\hat{Y} \in\mathbb{R}^{n \times m} (one row per instance, one column per class), with C=YTY^∈Rm×mC = Y^{T}\hat{Y} \in\mathbb{R}^{m \times m} the resulting confusion matrix. A performance measure MM is then evaluated in one of two ways: the micro reduction Σ1\Sigma_1 pools all nmnm cell contributions into a single global confusion table before evaluating MM once, while the macro reduction Σm\Sigma_m evaluates MM separately on each class’s own 2×22 \times2 table and averages the mm 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} are replaced by the temporally weighted state C(t)C(t) defined next.

Notation and the Streaming Bilinear Formulation

Let S={(xt,yt,pt)}t∈N+S = \{(x_t, y_t, p_t)\}_{t \in\mathbb{N}^{+}} represent an ordered sequence of streaming instances arriving at discrete timestamps t∈{1,2,…}t \in\{1,2,\ldots\}, where yty_t denotes instance tt’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 Ok(t)\mathcal{O}_k(t) and its latency Δk\Delta_k. At time tt:

  • xt∈Xx_t \in\mathcal{X} denotes the input feature vector drawn from dynamic distribution Pt(X)P_t(X);

  • yt=[yt1,…,ytm]T∈Δm−1y_t = [y_{t1},\ldots,y_{tm}]^T \in\Delta^{m-1} is the true target vector on the standard probability simplex Δm−1={u∈[0,1]m:∑j=1muj=1}\Delta^{m-1} = \{\mathbf{u} \in[0,1]^m : \sum_{j=1}^{m} u_j = 1\}, representing deterministic labels (yt=ejy_t = e_j, the jj-th standard basis vector, i.e. a one-hot vector with a 11 in the true-class position and 00 elsewhere) or soft distributions Pt(Y∣xt)P_t(Y \mid x_t);

  • pt=[pt1,…,ptm]T∈Δm−1p_t = [p_{t1}, \ldots, p_{tm}]^T \in\Delta^{m-1} is the model output, representing discrete decisions (pt=ek\mathbf{p}_t = \mathbf{e}_k, the same one-hot construction as ej\mathbf{e}_j above, but with the 1 in the predicted-class position kk) or calibrated posterior probabilities.

Let Y1:t=[y1,…,yt]T∈Rt×m\mathbf{Y}_{1:t} = [\mathbf{y}_1, \ldots, \mathbf{y}_t]^T \in\mathbb{R}^{t \times m} and P1:t=[p1,…,pt]T∈Rt×m\mathbf{P}_{1:t} = [\mathbf{p}_1, \ldots, \mathbf{p}_t]^T \in\mathbb{R}^{t \times m} denote the accumulated label and prediction matrices up to time tt. In stationary batch evaluation, the sample reduction operator aggregates instances uniformly via C=YTP=∑i=1nyipiTC = \mathbf{Y}^T\mathbf{P} = \sum_{i=1}^{n}\mathbf{y}_i\mathbf{p}_i^T.

In non-stationary streams, we formalize temporal aggregation through a diagonal temporal weighting matrix W(t)=diag⁡(w1(t),w2(t),…,wt(t))∈Rt×t\mathbf{W}(t) = \operatorname{diag}(w_1(t), w_2(t), \ldots, w_t(t)) \in\mathbb{R}^{t \times t} with W(t)≥0\mathbf{W}(t) \ge0 (i.e., wk(t)≥0w_k(t) \ge0), normalized such that Tr⁡(W(t))=∑k=1twk(t)=1\operatorname{Tr}(\mathbf{W}(t)) = \sum_{k=1}^{t}w_k(t) = 1 (exactly for the sliding window once it has filled, t≥Wt \ge W, with WW the window size, a scalar that is not the weighting matrix W(t)\mathbf{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, and the residual mass αt\alpha^t is accounted for in Proposition 3).

Definition 1 (The Temporal Reduction Operator Σt\Sigma_t) The temporal reduction operator Σt\Sigma_t maps the historical matrix trajectory (Y1:t,P1:t)(\mathbf{Y}_{1:t}, \mathbf{P}_{1:t}) into the time-aggregated contingency matrix C(t)∈Rm×mC(t) \in\mathbb{R}^{m \times m} (with C(t)≥0C(t) \ge0) via the weighted bilinear form:

C(t)=Σt(Y1:t,P1:t)=Y1:tTW(t)P1:t=∑k=1twk(t)ykpkT(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)}

References

  1. [1]Aguiar GJ, Krawczyk B, Cano A (2024) A survey on learning from imbalanced data streams: taxonomy, challenges, empirical study, and reproducible experimental framework. Machine Learning 113(7):4165–4243. https://doi.org/10.1007/s10994-023-06353-6
  2. [2]Bifet A, Gavaldà R (2007) Learning from time-changing data with adaptive windowing. In: Proceedings of the 2007 SIAM International Conference on Data Mining, SIAM, pp 443–448, https://doi.org/10.1137/1.9781611972771.42
  3. [3]Bifet A, Holmes G, Kirkby R, et al (2010) Moa: Massive online analysis. Journal of Machine Learning Research 11:1601–1604. URL https://jmlr.org/papers/v11/bifet10a.htmlDOI
  4. [4]Brzeziński D, Stefanowski J (2017) Prequential AUC: properties of the area under the ROC curve for data streams with concept drift. Knowledge and Information Systems 52(2):531–562. https://doi.org/10.1007/s10115-017-1022-8
  5. [5]Cerqueira V, Gomes HM, Heyden M, et al (2026) A framework for evaluating and benchmarking concept drift detection methods. In: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (KDD ’26). Association for Computing Machinery, New York, NY, pp 8671–8682, https://doi.org/10.1145/3770855.3819070
  6. [6]Dal Pozzolo A, Caelen O, Johnson RA, et al (2015) Calibrating probability with undersampling for unbalanced classification. In: 2015 IEEE Symposium Series on Computational Intelligence, IEEE, pp 159–166, https://doi.org/10.1109/SSCI.2015.33
  7. [7]Dawid AP (1984) Present position and potential developments: Some personal views: Statistical theory: The prequential approach. Journal of the Royal Statistical Society: Series A (General) 147(2):278–292. https://doi.org/10.2307/2981683
  8. [8]Frías-Blanco I, del Campo-Ávila J, Ramos-Jiménez G, et al (2015) Online and non-parametric drift detection methods based on hoeffding’s bounds. IEEE Transactions on Knowledge and Data Engineering 27(3):810–823. https://doi.org/10.1109/TKDE.2014.2345382
  9. [9]Gama J, Medas P, Castillo G, et al (2004) Learning with drift detection. In: Brazilian Symposium on Artificial Intelligence (SBIA), Springer, pp 286–295, https://doi.org/10.1007/978-3-540-28645-5_29
  10. [10]Gama J, Žliobaitė I, Bifet A, et al (2014) A survey on concept drift adaptation. ACM Computing Surveys (CSUR) 46(4):1–37. https://doi.org/10.1145/2523813
  11. [11]Gomes HM, Grzenda M, Mello R, et al (2022) A survey on semi-supervised learning for delayed partially labelled data streams. ACM Computing Surveys 55(4):75:1–75:42. https://doi.org/10.1145/3523055
  12. [12]Grzenda M, Gomes HM, Bifet A (2020) Delayed labelling evaluation for data streams. Data Mining and Knowledge Discovery 34(5):1237–1266. https://doi.org/10.1007/s10618-019-00654-y
  13. [13]Guo C, Pleiss G, Sun Y, et al (2017) On calibration of modern neural networks. In: Proceedings of the 34th International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, vol 70. PMLR, pp 1321–1330, URL https://proceedings.mlr.press/v70/guo17a.htmlarxiv.org/abs/1706.04599
  14. [14]Harries M (1999) Splice-2 comparative evaluation: Electricity pricing. Tech. Rep. UNSW-CSE-TR-9905, University of New South Wales, School of Computer Science and Engineering, URL https://books.google.com.br/books?id=1ZrlvQAACAAJ
  15. [15]Kleinberg J (2003) Bursty and hierarchical structure in streams. Data Mining and Knowledge Discovery 7(4):373–397. https://doi.org/10.1023/A:1024940629314
  16. [16]Lu J, Liu A, Dong F, et al (2019) Learning under concept drift: A review. IEEE Transactions on Knowledge and Data Engineering 31(12):2346–2363. https://doi.org/10.1109/TKDE.2018.2876857
  17. [17]Montiel J, Read J, Bifet A, et al (2018) Scikit-multiflow: A multi-output streaming framework. Journal of Machine Learning Research 19(72):1–5. URL https://jmlr.org/papers/v19/18-251.htmlDOI
  18. [18]Montiel J, Halford M, Mastelini SM, et al (2021) River: machine learning for streaming data in Python. Journal of Machine Learning Research 22(110):1–8. URL https://jmlr.org/papers/v22/20-1380.htmlarxiv.org/abs/2012.04740
  19. [19]Moreno-Torres JG, Raeder T, Alaiz-Rodríguez R, et al (2012) A unifying view on dataset shift in classification. Pattern Recognition 45(1):521–530. https://doi.org/10.1016/j.patcog.2011.06.019
  20. [20]Parreira PH, Prati RC (2026) Feature-based reservoir of dynamic subspaces for data streams under intermediate latency. IEEE Access 14:123866–123879. https://doi.org/10.1109/ACCESS.2026.3723350
  21. [21]Plasse J, Adams N (2016) Handling delayed labels in temporally evolving data streams. In: 2016 IEEE International Conference on Big Data (Big Data). IEEE, pp 2416–2424, https://doi.org/10.1109/BigData.2016.7840877
  22. [22]Platt JC (2000) Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In: Smola AJ, Bartlett PL, Schölkopf B, et al (eds) Advances in Large Margin Classifiers. MIT Press, Cambridge, MA, pp 61–74, https://doi.org/10.7551/mitpress/1113.003.0008
  23. [23]Prati RC (2026) aggmetrics: Aggregating classification performance measures for machine learning. arXiv:2610.30456
  24. [24]Prati RC (2027) A unified algebraic framework for classification performance evaluation. Information Fusion 138:104767. https://doi.org/10.1016/j.inffus.2026.104767, URL https://www.sciencedirect.com/science/article/pii/S1566253526006433
  25. [25]Provost F, Fawcett T (2001) Robust classification for imprecise environments. Machine Learning 42:203–231. https://doi.org/10.1023/A:1007601015854

Paper details

vlnc:W_mefrcte6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents