Searching for a Hidden Markov Anomaly over Multiple Processes

• URL: http://arxiv.org/abs/2506.17108v1
• Date: Fri, 20 Jun 2025 16:10:38 GMT
• Title: Searching for a Hidden Markov Anomaly over Multiple Processes
• Authors: Levli Citron, Kobi Cohen, Qing Zhao,
• Abstract summary: We propose a novel algorithm, dubbed Anomaly Detection under Hidden Markov model (ADHM)<n>ADHM adapts the probing strategy based on accumulated statistical evidence and belief updates over hidden states.<n>It consistently outperforms existing methods in extensive simulations.
• Score: 13.582085518282849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the problem of detecting an anomalous process among a large number of processes. At each time t, normal processes are in state zero (normal state), while the abnormal process may be in either state zero (normal state) or state one (abnormal state), with the states being hidden. The transition between states for the abnormal process is governed by a Markov chain over time. At each time step, observations can be drawn from a selected subset of processes. Each probed process generates an observation depending on its hidden state, either a typical distribution under state zero or an abnormal distribution under state one. The objective is to design a sequential search strategy that minimizes the expected detection time, subject to an error probability constraint. In contrast to prior works that assume i.i.d. observations, we address a new setting where anomalies evolve according to a hidden Markov model. To this end, we propose a novel algorithm, dubbed Anomaly Detection under Hidden Markov model (ADHM), which dynamically adapts the probing strategy based on accumulated statistical evidence and predictive belief updates over hidden states. ADHM effectively leverages temporal correlations to focus sensing resources on the most informative processes. The algorithm is supported by an asymptotic theoretical foundation, grounded in an oracle analysis that characterizes the fundamental limits of detection under the assumption of a known distribution of the hidden states. In addition, the algorithm demonstrates strong empirical performance, consistently outperforming existing methods in extensive simulations.

Related papers

• Asymptotically Optimal Search for a Change Point Anomaly under a Composite Hypothesis Model [10.514231683620517]
  We address the problem of searching for a change point in an anomalous process among a finite set of M processes.<n>Our goal is to design a sequential search strategy that minimizes the Bayes risk by balancing sample complexity and detection accuracy.
  arXiv  Detail & Related papers  (2024-12-27T00:44:34Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  We introduce a novel framework called GST-Pro, which utilizes a graphtemporal process and anomaly scorer to detect anomalies. Our experimental results show that the GST-Pro method can effectively detect anomalies in time series data and outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-01-11T10:10:16Z)
• Video Anomaly Detection via Spatio-Temporal Pseudo-Anomaly Generation : A Unified Approach [49.995833831087175]
  This work proposes a novel method for generating generic Video-temporal PAs by inpainting a masked out region of an image. In addition, we present a simple unified framework to detect real-world anomalies under the OCC setting. Our method performs on par with other existing state-of-the-art PAs generation and reconstruction based methods under the OCC setting.
  arXiv  Detail & Related papers  (2023-11-27T13:14:06Z)
• Don't Miss Out on Novelty: Importance of Novel Features for Deep Anomaly Detection [64.21963650519312]
  Anomaly Detection (AD) is a critical task that involves identifying observations that do not conform to a learned model of normality. We propose a novel approach to AD using explainability to capture such novel features as unexplained observations in the input space. Our approach establishes a new state-of-the-art across multiple benchmarks, handling diverse anomaly types.
  arXiv  Detail & Related papers  (2023-10-01T21:24:05Z)
• Reasonable Anomaly Detection in Long Sequences [3.673497128866642]
  We propose to completely represent the motion patterns of objects by learning from long-term sequences. A Stacked State Machine (SSM) model is proposed to represent the temporal dependencies which are consistent across long-range observations.
  arXiv  Detail & Related papers  (2023-09-06T23:35:55Z)
• CARLA: Self-supervised Contrastive Representation Learning for Time Series Anomaly Detection [53.83593870825628]
  One main challenge in time series anomaly detection (TSAD) is the lack of labelled data in many real-life scenarios. Most of the existing anomaly detection methods focus on learning the normal behaviour of unlabelled time series in an unsupervised manner. We introduce a novel end-to-end self-supervised ContrAstive Representation Learning approach for time series anomaly detection.
  arXiv  Detail & Related papers  (2023-08-18T04:45:56Z)
• Multimodal Motion Conditioned Diffusion Model for Skeleton-based Video Anomaly Detection [46.8584162860564]
  We propose a novel generative model for video anomaly detection (VAD) We consider skeletal representations and leverage state-of-the-art diffusion probabilistic models to generate multimodal future human poses. We validate our model on 4 established benchmarks.
  arXiv  Detail & Related papers  (2023-07-14T07:42:45Z)
• Are we certain it's anomalous? [57.729669157989235]
  Anomaly detection in time series is a complex task since anomalies are rare due to highly non-linear temporal correlations. Here we propose the novel use of Hyperbolic uncertainty for Anomaly Detection (HypAD) HypAD learns self-supervisedly to reconstruct the input signal.
  arXiv  Detail & Related papers  (2022-11-16T21:31:39Z)
• Temporal Detection of Anomalies via Actor-Critic Based Controlled Sensing [31.841289319809807]
  We address the problem of monitoring a set of binary processes and generating an alert when the number of anomalies among them exceeds a threshold. For this, the decision-maker selects and probes a subset of the processes to obtain noisy estimates of their states. Using the posterior probability, we construct a Markov decision process and solve it using deep actor-critic reinforcement learning.
  arXiv  Detail & Related papers  (2022-01-03T20:59:40Z)
• Scalable and Decentralized Algorithms for Anomaly Detection via Learning-Based Controlled Sensing [40.14838268469627]
  We develop an anomaly detection algorithm that chooses the processes to be observed at a given time instant. The objective of the detection algorithm is to identify the anomalies with an accuracy exceeding the desired value.
  arXiv  Detail & Related papers  (2021-12-08T11:20:36Z)
• A Scalable Algorithm for Anomaly Detection via Learning-Based Controlled Sensing [37.78306297797]
  We develop an anomaly detection algorithm that chooses the process to be observed at a given time instant. The objective of the detection algorithm is to arrive at a decision with an accuracy exceeding a desired value. Unlike prior work on this topic that has exponential complexity in the number of processes, our algorithm has computational and memory requirements that are both in the number of processes.
  arXiv  Detail & Related papers  (2021-05-12T17:46:01Z)
• Optimal Sequential Detection of Signals with Unknown Appearance and Disappearance Points in Time [64.26593350748401]
  The paper addresses a sequential changepoint detection problem, assuming that the duration of change may be finite and unknown. We focus on a reliable maximin change detection criterion of maximizing the minimal probability of detection in a given time (or space) window. The FMA algorithm is applied to detecting faint streaks of satellites in optical images.
  arXiv  Detail & Related papers  (2021-02-02T04:58:57Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.