Conditional Score Learning for Quickest Change Detection in Markov Transition Kernels
Wuxia Chen, Taposh Banerjee, Vahid Tarokh · 2025
Read Conditional Score Learning for Quickest Change Detection in Markov Transition Kernels by Wuxia Chen, Taposh Banerjee, Vahid Tarokh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03953.txt.
Introduction
Wuxia Chen, Taposh Banerjee, and Vahid Tarokh address quickest change detection for Markov processes whose transition rules are unknown. Instead of estimating full likelihoods, they learn the conditional score, the gradient of the log density of the next state given the current one, directly from sample pairs.
A score-based CUSUM procedure uses differences of conditional Hyvarinen scores to flag kernel changes, with a truncated version keeping increments bounded. For uniformly ergodic chains, exponential lower bounds on mean time to false alarm and asymptotic upper bounds on detection delay are proved. High-dimensional settings, where explicit likelihoods are impractical, are the main target for this detection route.
Catalog record
| CREATOR | Wuxia Chen, Taposh Banerjee, Vahid Tarokh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-03953
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Conditional Score Learning for Quickest Change Detection in Markov Transition Kernels Wuxia Chen, Taposh Banerjee, Vahid Tarokh Abstract We address the problem of quickest change detection in Markov processes with unknown transition kernels. The key idea is to learn the conditional score ∇ 𝐲 log p ( 𝐲 | 𝐱 ) \nabla_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x}) directly from sample pairs ( 𝐱 , 𝐲 ) (\mathbf{x},\mathbf{y}) , where both 𝐱 \mathbf{x} and 𝐲 \mathbf{y} are high-dimensional data generated by the same transition kernel. In this way, we avoid explicit likelihood evaluation and provide a practical way to learn the transition dynamics. Based on this estimation, we develop a score-based CUSUM procedure that uses conditional Hyvärinen score differences to detect changes in the kernel. To ensure bounded increments, we propose a truncated version of the statistic. With Hoeffding’s inequality for uniformly ergodic Markov processes, we prove exponential lower bounds on the mean time to false alarm. We also prove asymptotic upper bounds on detection delay. These results give both theoretical guarantees and practical feasibility for score-based detection in high-dimensional Markov models. I Introduction Detecting changes in sequential data is a fundamental problem with broad applications, including biology [ 22 ] , quality control [ 10 ] , and power systems [ 5 ] . In statistics, this problem is formulated as the problem of quickest change detection (QCD), where the goal is to detect distributional changes as quickly as possible while controlling false alarms [ 21 ] . A classical solution is the Cumulative Sum (CUSUM) algorithm [ 18 ] . CUSUM is recursive, easy to implement, and optimal in the i.i.d. setting under Lorden’s and Pollak’s criteria [ 14 , 17 , 19 ] . For comprehensive overviews, see [ 27 , 25 , 26 , 3 ] . However, CUSUM and related optimal methods require explicit knowledge of the pre- and post-change distributions. In high-dimensional applications, such as energy-based models [ 13 ] or score-based generative models [ 23 ] , evaluating likelihoods is often infeasible. Several recent works have advanced score-based approaches for quickest change detection and hypothesis testing. These methods replace log-likelihood ratios with differences of Hyvärinen scores and analyze performance using Fisher divergence in place of the Kullback–Leibler divergence. Examples include score-based QCD for unnormalized models [ 29 , 2 ] , Bayesian formulations for score-based models [ 1 ] , large deviation analysis of score-based hypothesis testing [ 8 ] , and robust extensions based on least-favorable scores [ 16 ] . While these papers demonstrate the strength of Fisher divergence as the natural information measure in score-based settings, they all rely on i.i.d. data to learn the score. In contrast, real-world processes often exhibit dependence, such as Markovian dynamics, where the i.i.d. assumption does not hold. Our work addresses this gap by extending score-based change detection to dependent data. We introduce conditional score learning together with a conditional Fisher divergence, providing a new framework for analyzing changes in Markov processes. The key idea is to learn the conditional score \nabla_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x}) directly from paired samples (\mathbf{x},\mathbf{y}) , where both \mathbf{x} and \mathbf{y} are high-dimensional vectors generated by the same transition kernel. A neural network trained via score matching serves as the conditional score estimator. Using this estimator, we propose a conditional score-based CUSUM procedure that generalizes existing score-based algorithms from i.i.d. data to dependent data. To ensure bounded increments and numerical stability, we introduce a truncated version of the statistic. We derive a lower bound on the mean time to a false alarm for uniformly ergodic Markov processes. We also obtain an asymptotic upper bound on the average detection delay. Our proof techniques are inspired by the techniques used in [ 4 ] and [ 30 ] . Finally, to demonstrate the effectiveness of the proposed algorithm, we apply it to CMU motion capture data [ 6 ] to detect a change in the type of activity being performed (running, playing, jumping, etc). We also apply our algorithm to a simulated Markov process where there is a change in the Gaussian transition kernel. The main contributions of this paper are: • A framework for conditional score learning that estimates \nabla_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x}) from paired samples of the same transition kernel, enabling score-based analysis in Markov processes. • A conditional score-based CUSUM procedure for dependent data, with a truncated version ensuring bounded increments and stable implementation. • Theoretical performance guarantees, including an exponential lower bound on the mean time to false alarm and an asymptotic upper bound on detection delay, derived using Hoeffding’s inequalities. • Application to CMU motion capture data and simulated Markov process data. The rest of the paper is organized as follows. In Section II , we present the conditional score learning framework and its properties. In Section III , we introduce a score matching method for conditional score learning via a neural network. In Section IV , we formulate the change detection problem in Markov processes. In Section V , we introduce the conditional score-based CUSUM algorithm with truncation. In Sections VI and VII , we analyze false alarm and delay performance. Finally, in Section VIII , we apply the proposed algorithm to real and simulated data. II Conditional Score Definition and Properties To formalize our framework, we begin with a general pair of random vectors (\mathbf{X},\mathbf{Y}) defined on measurable spaces \mathcal{X} and \mathcal{Y} with joint density p(\mathbf{x},\mathbf{y}) . The corresponding conditional distribution of \mathbf{Y} given \mathbf{X}=\mathbf{x} is denoted by p(\mathbf{y}|\mathbf{x}) . While classical score-based approaches [ 11 ] typically focus on the gradient of an unconditional density \nabla_{\mathbf{y}}\log p(\mathbf{y}) , our interest lies in conditional distributions, which arise naturally in dependent-data settings. We introduce the notion of a conditional score, defined as the gradient of the conditional log-density with respect to y : \nabla_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x}). (1) The conditional score captures the sensitivity of \log p(\mathbf{y}|\mathbf{x}) to changes in \mathbf{y} , with \mathbf{x} held fixed. This generalizes the classical score function used in the i.i.d. setting [ 29 , 24 ] to models with conditional structure and temporal or spatial dependencies. Inspired by the original formulation of the Hyvärinen score for unnormalized models [ 11 ] , we define a version suited to the conditional density p(\mathbf{y}|\mathbf{x}) . This conditional Hyvärinen score is given by S_{H}(\mathbf{y},\mathbf{x};p)\triangleq\frac{1}{2}\left\|\nabla_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x})\right\|^{2}+\Delta_{\mathbf{y}}\log p(\mathbf{y}|\mathbf{x}), (2) where \Delta_{y} denotes the Laplacian with respect to y . It aggregates the squared norm and divergence of the conditional score into a scalar quantity. For high-dimensional data, this quantity can be efficiently learned from i.i.d. samples (\mathbf{x}_{1},\mathbf{y}_{1}),\ldots(\mathbf{x}_{n},\mathbf{y}_{n}),\ldots . Moreover, when \mathbf{Y} is independent of \mathbf{X} , our definition reduces to the classical Hyvärinen score for marginal densities, thereby recovering the i.i.d. setting as a special case. II-A Hyvärinen Score Difference Between Conditional Models We now analyze how the conditional Hyvärinen scores differ under two models and study the implications of this difference. Let p(\mathbf{y}|\mathbf{x}) and q(\mathbf{y}|\mathbf{x}) be two conditional densities, associated with joint distributions p(\mathbf{x},\mathbf{y}) and q(\mathbf{x},\mathbf{y}) , respectively. We define the difference in conditional Hyvärinen scores between the two models at a given pair (\mathbf{x},\mathbf{y}) as s(\mathbf{y},\mathbf{x};p,q)\triangleq S_{H}(\mathbf{y},\mathbf{x};p)-S_{H}(\mathbf{y},\mathbf{x};q), (3) where S_{H}(\mathbf{y},\mathbf{x};p) denotes the conditional Hyvärinen score defined in ( 2 ). When the context is clear, we will write s(\mathbf{y},\mathbf{x}) for