A Temporal Algebraic Framework for Data Stream Evaluation Under Delayed Labels and Distribution Shifts
Organizations: Center for Mathematics, Computing and Cognition (CMCC), Universidade Federal do ABC (UFABC), Santo André, SP, Brazil. · Faculdade de Computação (FACOM), Universidade Federal de Uberlândia (UFU), Uberlândia, MG, Brazil.
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.
Figures & tables
| Setting | Delay factor | Audit factor | Regimes used |
|---|---|---|---|
| (i) immediate, fully labelled | none (Section 3.4 ) | ||
| (ii) delayed, fully labelled | constant or random | 1, 2 | |
| (iii) immediate, partially labelled | 3 or 4 (or both, Eq. ( 25 )) | ||
| (iv) delayed, partially labelled | constant or random | (1 or 2) with (3 or 4) |
| ID | Stream and configuration | Used in | |
|---|---|---|---|
| S1 | 3-class stream with continuous prior drift, ; fading and window . | 1,500 | § 6.2 |
| S2 | Binary stream with classifier errors drawn independently from a specified , base prior and one change at : a prior change or with the classifier fixed (label shift), or a concept change (an abrupt, gradual, incremental or reoccurring drop of specificity by 0.1 to 0.3 or of recall by 0.1 to 0.2), or both. Fading . | 1,000 to 3,000 | § 6.3 |
| S3 | SEA streams with the four drift profiles: abrupt ( at ), gradual (mixing the two concepts), incremental ( moving linearly from to over ) and reoccurring ( alternating between and every steps). | 1,500 | § 6.3 |
| S4 | Multiclass streams with 3 and 5 classes, confusion rows with diagonal and the errors spread uniformly, mildly concentrated (two thirds of the errors to the next class) or cyclic (all errors to the next class); base prior or ; label shifts and one-row concept changes at . | 3,000 | § 6.3 |
| S5 | Binary, positive class, a non-perfect scorer (score for positives and for negatives, decision at , the score as stand-in posterior), fading . Three latency regimes: constant ; Poisson ; class-conditional for the positive (fraud) class and for the negative class. | 1,200 | § 6.4 |
| S6 | Credit/risk stream: , . The stand-in is the true probability plus Gaussian noise (standard deviation , clipped to ), approximately calibrated; an instance is flagged when it exceeds . Flagged instances are censored unless audited with a budget (Eq. ( 25 )). Fading . Variants add a Poisson latency , a class-dependent latency (Poisson for positives, for negatives), a label-dependent audit ( for flagged positives, for flagged negatives), a miscalibrated or online-calibrated stand-in, inverse-propensity weighting as a baseline, the sliding-window form with , and the eviction step with tolerances and . | 2,000 | § 6.4 |
| ID | Stream and configuration | Used in | |
|---|---|---|---|
| R1 | Electricity (Elec2) ( Harries, 1999 ) : half-hourly electricity-market records with seasonal drift and a documented abrupt regime change from a 1996 market-rule expansion. A gradient-boosting classifier trained once on the first instances is used for the label-shift studies. | 45,312 | § 6.3 |
| R2 | Airlines ( Vanschoren et al., 2014 ) (OpenML data_id=1169 , from U.S. DOT on-time performance records). For the latency study, a flight’s scheduled duration ( Length ) sets , since its on-time or delayed outcome is only known once it has landed. A gradient-boosting classifier trained once on the first instances is used for the label-shift studies. | 539,383 | § 6.3 , § 6.4 |
| R3 | Credit Card Fraud ( Dal Pozzolo et al., 2015 ) : fraud rate, chronologically ordered by Time ; fraud arrivals cluster in time ( of consecutive fraud pairs land within seconds). The censoring policy is simulated: approved instances ( , threshold ) are always observed, flagged ones only with a audit budget (Eq. ( 25 )). A plain Hoeffding tree collapses to the majority class at this base rate, so it is wrapped in random oversampling ( Wang et al., 2018 ; Aguiar et al., 2024 ) . Cumulative aggregation (no fading) for the censoring runs; the oversampler targets a class distribution. | 284,807 | § 6.4 , § 6.5 |
| R4 | NSL-KDD ( Tavallaee et al., 2009 ) : the standard KDDTrain+ and KDDTest+ partitions concatenated into one stream, not a chronological order. Five coarse attack categories (normal , DoS , Probe , R2L , U2R ). Fading in the Pareto runs. For the label-shift studies a gradient-boosting classifier, binary (normal against attack) or with the five classes, is trained once on a random . The binary version with an online Hoeffding tree is also used for the delay and censoring study of § 6.4 . | 148,517 | § 6.4 , § 6.3 , § 6.5 |
| R5 | Covertype ( sklearn.datasets.fetch_covtype ): features, positive class Spruce/Fir (cover type 1, rate ); the file order is geographic, not chronological. Used only for the label-shift studies, with a gradient-boosting classifier trained once on a random . | 581,012 | § 6.3 |
| Claim | Kind | Streams | Where |
|---|---|---|---|
| Linear decomposability of the temporal state (Theorem 1 ) | exact identity | S1 | § 6.2 |
| Prior invariance of the canonical coordinates (Propositions 5 , 6 ) | quantitative | S2, S4, R1, R2, R4 | § 6.3 |
| Drift profiles | quantitative | S3 | § 6.3 |
| Attribution by the Jacobian decomposition | quantitative | S2, R1, R2, R4 | § 6.3 |
| Detection on the canonical coordinates under label shift | quantitative | S2, S4, R1, R2, R4, R5 | § 6.3 |
| Triage of alarms | quantitative | S2 | § 6.3 |
| Operator | Commutation | Decomposition | MCC contrast | Bal. acc. contrast |
|---|---|---|---|---|
| Fading ( ) | ||||
| Window ( ) |
| Latency regime | Queue, mean / max | Verified | Recall (oracle) | Defect | Defect , |
|---|---|---|---|---|---|
| Constant ( ) | 28.7 / 29 | 1,171 / 1,200 | 0.796 (0.800) | 0.000 | 1.171 |
| Poisson ( ) | 23.5 / 29 | 1,176 / 1,200 | 0.923 (0.942) | 0.000 | 1.169 |
| Class-dependent ( / ) | 13.3 / 20 | 1,182 / 1,200 | 0.859 (0.711) | 0.000 | 1.179 |
| Recall bias | bias | Queue size | |||
|---|---|---|---|---|---|
| Setting | Naive | Corrected | Naive | Corrected | decides / unknown |
| (i) immediate, full | / | ||||
| (ii) delayed, full | / | ||||
| (iii) immediate, partial | / | ||||
| (iv) delayed, partial | / | ||||
| Convention | Action | Undef. | TV | Mean Std |
|---|---|---|---|---|
| (sklearn / MOA) | 26.85 | |||
| (alt. default) | 11.85 | |||
| avg. over supported | 17.66 | |||
| (strict) | any undefined | 4.05 |
| Setting | Real? | Classes | TV (zero) | TV (excl.) | |
|---|---|---|---|---|---|
| Synthetic (Table 20 ) | No | 2 | 26.85 | 17.66 | |
| Credit Card Fraud | Yes | 1 (fraud) | 242.74 | 236.74 | |
| NSL-KDD | Yes | 4 (event) | — | — |
| Window ( ) | i.i.d. prediction, Eq. ( 19 ) | Empirical (real data) | Gap |
|---|---|---|---|
| 200 | 70.8% | 78.7% | pts |
| 500 | 42.1% | 59.1% | pts |
| 1,000 | 17.7% | 38.1% | pts |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Stream and instances | |
|---|---|
| Discrete evaluation time step, | |
| Index of a specific instance’s arrival/generation time (may differ from the current evaluation time ) | |
| Number of classes | |
| Number of instances in a batch (stationary setting only) | |
| Feature vector, true label vector, and prediction vector at time | |
| -th standard basis (one-hot) vector | |
Temporal Distribution Shift
Temporal distribution shift studies how changing data over time affects model accuracy and reliability, and how systems can detect and adapt to those changes.
See all 47 papers