{"id":"c624b51b-df5d-4135-a694-cafd69b0e7e6","arxiv_id":"2411.17528","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"EMCs estimate kth-order conditional probabilities online with O(m^k) updates per observation, and use Hellinger-distance drift detection plus a mode memory to discover and recognize switching behavioral modes in data streams.","lead":"This paper introduces Evolving Markov Chains (EMCs), an online algorithm that tracks changing transition probabilities in categorical data streams, discovers behavioral modes, and recognizes recurring modes without labels. It offers a way to make real-time monitoring of human activity, industrial machinery, and EEG signals adaptive and unsupervised.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's entropy regularization contradicts Eq. (9), so the published EMC differs from the evaluated EMC on every real-world benchmark.","rationale":"The paper's central contribution is an online, label-free mode discovery method backed by synthetic and real-world ARI numbers. I read the method and proof in good faith. The convergence proof for Eq. (2) is internally sound for a stationary ergodic chain: the fixed point E(\\hat p) = B follows from the recursion, and no step in the proof appears invalid. The SLWE-based update is genuinely incremental and costs O(m^k). The main weakness is not the math of the update but the specification of entropy regulation, which all real-world experiments depend on. Since the paper gives no commit hash and the implementation is only a URL, the inconsistency between Algorithm 1 and Eq. (9) is the most load-bearing point: a reader cannot know whether the reported results correspond to Eq. (9), to the pseudocode, or to a third variant. The proposed check settles this. If the released code matches Eq. (9) and rerunning with β = 0 changes results, the paper needs a corrected Algorithm 1 and re-evaluated tables; if β has negligible effect, the inconsistency is a documentation bug and the conditional verdict can stand. The reader's named weakest assumption (fixed order and state space) is acknowledged by the authors in Section 7 and is not the primary blocker; the entropy-regulation mismatch is more concrete and more directly tied to the reported experiments.","tokens_in":99,"tokens_out":9279,"duration_ms":212863,"concrete_test":"Fetch the implementation from https://bckrlab.org/p/emc and inspect the entropy-regulation branch corresponding to Algorithm 1 lines 7–11. Then rerun the EEG eye-state experiment (or HAR Subject 2) under three configurations: (a) β as reported, (b) β = 0, and (c) the corrected Eq. (9) applied to every CPD. If the ARI under (b) is statistically indistinguishable from (a), the inconsistency is inert and the concern is cosmetic; if (a) differs materially from (b) or from (c), the published algorithm is not the evaluated one and the paper must be revised with a corrected pseudocode and re-run results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 lines 7–11 do not implement Eq. (9). Eq. (9) defines entropy regulation as Q[n] = (1−β)Q[n−1] + βU, pulling each CPD toward the uniform CPD U. In Algorithm 1, line 8 first overwrites U(·|c) with the just-updated \\hat P(·|c), and line 9 then computes \\hat P ← (1−β)\\hat P + βU. For the CPD at context c, this yields (1−β)\\hat P + β\\hat P = \\hat P, so no entropy regulation is applied to the CPD that was just modified; if U is instead read as only the current CPD, the entire block is a no-op. Under either reading, the pseudocode does not realize Eq. (9). This matters because every real-world experiment in Section 6 uses β > 0 (β = 0.01, 0.003, 0.001 in Supplementary Table A4), so the reported HAR, CWRU, and EEG results are produced by an algorithm different from the one specified in the paper. The central empirical claim therefore cannot be reproduced from the published specification unless the released code silently repairs line 8.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Evolving Markov Chains (EMCs), an online, unsupervised method for mode discovery and recognition from categorical data streams. EMCs maintain a kth-order Markov-chain probability tensor updated with a multiplicative rule derived from Stochastic Learning Weak Estimation (SLWE), detect drift via periodic Hellinger-distance comparisons, and store per-mode tensors in memory to recognize recurring regimes. The authors claim an O(m^k) per-observation update, convergence of the expected estimates to the true transition probabilities, and demonstrate the method on synthetic data, human activity recognition, electric motor condition monitoring, and EEG eye-state data.","tokens_in":20992,"tokens_out":4008,"duration_ms":38762,"significance":"If the claims hold, the paper offers a useful and efficient primitive for online temporal clustering and change-point detection: it avoids tracking windows, updates only the relevant tensor slice, handles arbitrary Markov order, and comes with released code and a broad empirical comparison against stream-clustering and change-detection baselines. The formal statement, however, only covers convergence in expectation for a fixed ergodic chain, and the non-stationary mode-switching behavior is supported empirically. The main strength is the combination of a simple, efficient update rule with a practical mode-memory mechanism; the main weakness is a reproducibility-relevant mismatch between the mathematical specification of entropy regulation and the pseudocode used for the real-world experiments.","major_comments":[{"comment":"The pseudocode does not implement the entropy regulation defined in Eq. (9). Eq. (9) requires Q[n] = (1−β)Q[n−1] + βU with U fixed as the uniform distribution. In Algorithm 1, line 8 first overwrites U(·|c) with the just-updated P^P(·|c), and line 9 then computes P^← (1−β)P^+ βU. For the CPD at context c this gives (1−β)P^+ βP^= P^, so no entropy regulation is applied; if U is instead read as the current CPD, the block is a no-op. Since all real-world experiments use β > 0 (β = 0.01, 0.003, 0.001 in Supplementary Table A4 for HAR, CWRU, and EEG respectively), the reported real-world results are produced by an algorithm different from the one specified in the manuscript. This is a load-bearing reproducibility issue: please correct Algorithm 1 (or Eq. (9)) and confirm with the released code that the evaluated algorithm matches the corrected specification.","section":null},{"comment":"The proof establishes only convergence of E(P^[n]) to the true probability; it does not provide variance bounds, almost-sure convergence, or the 'geometric convergence' claimed in Section 5.1 and the abstract. Since the mode-switching and drift-detection behavior relies on the estimate being close to the true tensor, a mean-only statement is weak support for the adaptation claim. Please either provide a concentration or variance result, or explicitly limit Theorem 1 and the abstract's convergence claim to convergence in expectation.","section":null}],"minor_comments":[{"comment":"The formula for the Hellinger distance is typeset ambiguously; it should read H(P,Q) = (1/√2) * sqrt(Σ_i (√p_i − √q_i)²).","section":null},{"comment":"Lines 3 and 14 contain 'append M P to M' / 'append M P to M', which appears to be a typo for appending the estimated tensor P^ to the mode memory M; please correct the notation.","section":null},{"comment":"The text says the first 3000 instances constitute 20% of the EEG sequence, but the total sequence length is not stated; please give the total length for clarity.","section":null},{"comment":"The caption states loads from 0 to 4 HP, but the table only reports 0, 1, 2, and 3 HP; please align the caption with the data.","section":null},{"comment":"Theorem 1 is described as 'weak convergence', but the statement E(P^[∞]) = P is convergence in expectation, not weak convergence in the usual probabilistic sense; please adjust the terminology to avoid confusion.","section":null}],"recommendation":"major_revision","confidential_remarks":"The Algorithm 1 / Eq. (9) mismatch is the decisive issue: since all real-world benchmarks use β > 0, the published specification cannot reproduce the reported results unless the released code silently repairs the pseudocode. This is fixable within the manuscript's scope by correcting the pseudocode and verifying the code, so I recommend major revision rather than rejection. The paper would also benefit from a careful statement of the theorem's scope, since the current convergence claim is in expectation only."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a genuinely useful paper — an online, label-free method for mode discovery in categorical streams, built on a clean extension of SLWE to kth-order conditional probabilities with an O(m^k) sparse tensor update. The empirical work is broad and mostly honest. But there's a reproducibility problem in the supplementary pseudocode that gives me pause: Algorithm 1's entropy-regulation block (lines 7–11) contradicts Eq. (9). Eq. (9) says pull each CPD toward a fixed uniform distribution; the pseudocode first copies the just-updated CPD into U, then mixes the tensor with itself — a no-op under either reading. Since all real-world experiments use β > 0, the published algorithm is not the one that produced the reported HAR, CWRU, and EEG numbers. Synthetic experiments use β = 0, so those results stand, but the real-world claims can't be reproduced from the specification.\n\nWhat's new and worth credit: the kth-order extension of the SLWE update is simple but real, and the proof of convergence in expectation (Theorem 1) is a faithful adaptation of the SLWE argument, though it only controls the first moment. The mode memory and Hellinger-drift combination is heuristic but sensible, and the paper is refreshingly clear about its limitations — fixed alphabet, fixed order, exponential tensor size.\n\nSoft spots, in proportion: besides the pseudocode bug, the theory is thin — no variance bound, no tracking guarantee under non-stationarity, and mode discovery has no formal guarantees. The hyperparameter set is large (λ_f, λ_s, β, δ, η, τ, k), though tuning on a small held-out portion is standard and the authors report it honestly. The comparison baselines are fair, and the synthetic experiments are well designed.\n\nWho's this for? Anyone working on streaming time-series analytics, condition monitoring, or activity recognition from discrete sequences. It's not a breakthrough, but it's a solid engineering contribution that deserves a serious referee.\n\nMy recommendation: send it to review, but the authors must fix Algorithm 1 to match Eq. (9) or explicitly set β = 0 in the real-world experiments, and ideally ship code with a commit hash. After that revision I'd be comfortable accepting.","headline":"Solid online mode discovery with a genuine algorithmic extension, but a pseudocode bug makes the published real-world algorithm differ from the one evaluated.","tokens_in":21614,"tokens_out":3426,"would_cite":true,"duration_ms":30789,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Evolving Markov chains track, discover, and recognize behavioral modes online without labels.","keywords":["incremental learning","online mode discovery","mode recognition","non-stationary systems","concept drift","Markov chains","data streams","change point detection"],"falsifier":"Run the estimator on a two-state first-order ergodic chain with a known transition matrix, e.g. $p(1\\mid 1)=0.9$, $p(2\\mid 2)=0.8$, with $\\lambda=0.9$, averaging many independent runs at a large $n$. If $|\\mathbb{E}[\\hat p(1\\mid 1)[n]] - 0.9|$ does not shrink toward zero as $n$ grows, Theorem 1 is false. Alternatively, feed EMC a stream built from two modes with identical transition tensors but different labels: the method cannot separate them by construction, so a claim that it does would indicate the evaluation protocol, not the model, is doing the work.","tokens_in":20550,"feed_emoji":"🔁","tokens_out":8936,"duration_ms":74948,"temperature":0.7,"pith_summary":"This paper claims that a single online update rule can maintain a $k$th-order Markov-chain model of a categorical data stream while discovering, recognizing, and switching between behavioral modes—segments of the stream generated by different stationary transition laws. The rule multiplies the matching conditional probability toward one, decays its competitors, and leaves unrelated entries untouched, so each observation costs only as much as one conditional distribution, not the whole tensor. The paper proves that the expected estimate converges to the true transition probability tensor for an ergodic $k$th-order Markov chain, and shows on synthetic and real streams—human activity, motor vibrations, EEG eye state—that the resulting mode assignments beat window- and distribution-based baselines. If the claim holds, live processes can be segmented and monitored online without ground-truth labels, known mode counts, or annotated change points.","feed_headline":"One online update rule learns modes from streams with no labels","feed_subtitle":"Evolving Markov chains estimate transition probabilities, spot drifts, and recognize recurring modes without labels.","key_machinery":"The carrying object is the $k$th-order conditional-probability tensor $\\hat P[n]$, whose entries are updated by the SLWE-style rule (Eq. 2), named for the Stochastic Learning Weak Estimator on which it is based: the entry matching the observed $k+1$-gram is bumped up, the other $m-1$ entries conditioned on the same $k$-gram are multiplied by $\\lambda$, and entries conditioned on other contexts are unchanged. The tensor is the mode model; the Hellinger distance between a current estimate and a $\\tau$-step-old snapshot is the drift detector that triggers mode switches; a mode memory stores one tensor per discovered mode and is consulted on drift-to-steady transitions; fast and slow learning coefficients ($\\lambda_f$, $\\lambda_s$) adapt the update speed depending on whether the stream is in a drift or steady phase.","core_discovery":"The central claim is that the stochastic tensor of a $k$th-order Markov chain can be estimated online, and that drift in that tensor is itself a signal for discovering and recognizing modes. The update, for each observed symbol, treats the current context $\\langle s_1,\\dots,s_k\\rangle$: the estimated probability of the observed next symbol is moved toward $1$ by adding $(1-\\lambda)$, every alternative next symbol is scaled by $\\lambda$, and all entries belonging to other contexts are left alone. Theorem 1 states that for an ergodic $k$th-order chain this estimator is weakly convergent, $\\mathbb{E}(\\hat P[\\infty]) = P$, and because the recurrence is multiplicative, convergence is geometric. The estimated tensor is compared against a delayed snapshot using Hellinger distance; a rise above a threshold flags a drift, a return below it ends the drift, and a memory of previously stored mode tensors lets the algorithm either recognize a recurring mode or create a new one. Entropy regulation and fast/slow learning are auxiliary mechanisms that keep rarely seen contexts from freezing stale probabilities and that trade estimation variance against adaptation speed.","pith_inferences":["The proof of convergence treats each mode as a fixed ergodic chain; a formal analysis of the same update under slowly time-varying transition matrices would quantify the tracking lag, which the paper currently assesses only empirically.","Entropy regulation is a second forgetting mechanism acting on the whole tensor; its interaction with the multiplicative $\\lambda$-forgetting is not characterized theoretically, so a combined analysis could predict when the two work against each other.","The fixed-alphabet and fixed-order assumptions could be relaxed by letting rarely used states split or merge; the paper lists this as future work, and it would turn EMC from a mode tracker into an adaptively structured model.","The Hellinger-distance drift detector compares whole tensors; replacing it with context-specific distances could yield finer-grained drift localization, identifying which transition probabilities changed, at the cost of more memory."],"forward_implications":["A stream of categorical observations can be segmented into behavioral regimes in real time with no labels, no known mode count, and no annotated change points.","Per-observation cost is $O(m^k)$ rather than $O(m^{k+1})$, because only the one active conditional distribution is updated, so higher-order dependencies remain tractable for moderate alphabets.","Expected transition estimates converge to the true tensor within each stationary regime, so longer regimes mean more accurate per-mode models in memory.","Recurring modes are recognized and their stored models are refined incrementally whenever the stream is steady, which supports non-stationary processes whose behaviors repeat.","The same machinery handles probability tracking, change-point detection, mode discovery, and mode recognition within one framework, as shown by a synthetic change-point F1 of 0.93 and a synthetic mode-discovery ARI of 0.85."],"supporting_citations":[{"why":"Supplies the SLWE multiplicative update scheme and the expectation-based convergence argument that Theorem 1 extends to kth-order conditional probabilities.","marker":"[32]"},{"why":"SCD is the predecessor that detects regime changes via estimated conditional probabilities and is the change-detection baseline EMC builds on.","marker":"[27]"},{"why":"Online mean transition-frequency estimation that maintains the full tensor, providing the O(m^{k+1}) per-step contrast to EMC's O(m^k) update.","marker":"[26]"},{"why":"Sliding-window Markov-chain construction used as a baseline in probability tracking experiments.","marker":"[24]"},{"why":"ADWIN adaptive windowing used both as a baseline for window-based Markov chains and as a change-point detector.","marker":"[37]"},{"why":"EPSTM is the offline variable-order Markov-chain mode discovery baseline compared on ARI in the synthetic mode discovery experiments.","marker":"[22]"},{"why":"Supplies the syntactic pattern recognition preprocessing that converts continuous sensor data into the discrete alphabet for the motor and activity experiments.","marker":"[23]"}],"fun_headline_variants":["Evolving Markov chains discover modes online","Unsupervised mode discovery with evolving Markov chains","No labels: evolving Markov chains spot drift and modes","Online evolving Markov chains discover and track modes","Evolving Markov chains recognize modes without labels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each mode is a stationary $k$th-order ergodic Markov chain over a fixed, known alphabet $\\Sigma$ with a fixed order $k$; the convergence theorem does not by itself cover non-stationary streams, where tracking is justified only by the empirical results.","fun_headline_variants_meta":{"raw":{"variants":["Evolving Markov chains discover modes online","Unsupervised mode discovery with evolving Markov chains","No labels: evolving Markov chains spot drift and modes","Online evolving Markov chains discover and track modes","Evolving Markov chains recognize modes without labels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001135,"raw_usage":{"total_tokens":4746,"prompt_tokens":1010,"completion_tokens":3736,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":3668}},"tokens_in":626,"tokens_out":3736,"duration_ms":22996,"temperature":1.0,"reasoning_tokens":3668,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:01:12.626147+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the estimator on a two-state first-order ergodic chain with a known transition matrix, e.g. $p(1\\mid 1)=0.9$, $p(2\\mid 2)=0.8$, with $\\lambda=0.9$, averaging many independent runs at a large $n$. If $|\\mathbb{E}[\\hat p(1\\mid 1)[n]] - 0.9|$ does not shrink toward zero as $n$ grows, Theorem 1 is false. Alternatively, feed EMC a stream built from two modes with identical transition tensors but different labels: the method cannot separate them by construction, so a claim that it does would indicate the evaluation protocol, not the model, is doing the work.","supporting_citations":[{"cited_title":"Stochastic Learning-Based Weak Estimation of Multinomial Random Variables and Its Applications to Pattern Recognition in Non-Stationary Environments","cited_arxiv_id":null,"evidence_quote":"Supplies the SLWE multiplicative update scheme and the expectation-based convergence argument that Theorem 1 extends to kth-order conditional probabilities."},{"cited_title":"Stochastic Optimal Control of Systems with Soft Constraints and Opportunities for Automotive Applications","cited_arxiv_id":null,"evidence_quote":"Online mean transition-frequency estimation that maintains the full tensor, providing the O(m^{k+1}) per-step contrast to EMC's O(m^k) update."},{"cited_title":"Anomaly Detection Based on a Dynamic Markov Model","cited_arxiv_id":null,"evidence_quote":"Sliding-window Markov-chain construction used as a baseline in probability tracking experiments."},{"cited_title":"Multivariate Time Series Clustering and Its Application in Industrial Systems","cited_arxiv_id":null,"evidence_quote":"EPSTM is the offline variable-order Markov-chain mode discovery baseline compared on ARI in the synthetic mode discovery experiments."}],"review_version":1}