A Scalable Algorithm for Anomaly Detection via Learning-Based Controlled Sensing

• URL: http://arxiv.org/abs/2105.06289v1
• Date: Wed, 12 May 2021 17:46:01 GMT
• Title: A Scalable Algorithm for Anomaly Detection via Learning-Based Controlled Sensing
• Authors: Geethu Joseph, M. Cenk Gursoy, Pramod K. Varshney
• Abstract summary: 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.
• Score: 37.78306297797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the problem of sequentially selecting and observing processes from a given set to find the anomalies among them. The decision-maker observes one process at a time and obtains a noisy binary indicator of whether or not the corresponding process is anomalous. In this setting, we develop an anomaly detection algorithm that chooses the process to be observed at a given time instant, decides when to stop taking observations, and makes a decision regarding the anomalous processes. The objective of the detection algorithm is to arrive at a decision with an accuracy exceeding a desired value while minimizing the delay in decision making. Our algorithm relies on a Markov decision process defined using the marginal probability of each process being normal or anomalous, conditioned on the observations. We implement the detection algorithm using the deep actor-critic reinforcement learning framework. 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 polynomial in the number of processes. We demonstrate the efficacy of our algorithm using numerical experiments by comparing it with the state-of-the-art methods.

Related papers

• Anomaly Detection via Learning-Based Sequential Controlled Sensing [25.282033825977827]
  We address the problem of detecting anomalies among a set of binary processes via learning-based controlled sensing. To identify the anomalies, the decision-making agent is allowed to observe a subset of the processes at each time instant. Our objective is to design a sequential selection policy that dynamically determines which processes to observe at each time.
  arXiv  Detail & Related papers  (2023-11-30T07:49:33Z)
• 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)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Anomaly Detection via Controlled Sensing and Deep Active Inference [43.07302992747749]
  In this paper, we address the anomaly detection problem where the objective is to find the anomalous processes among a given set of processes. We develop a sequential selection algorithm that decides which processes to be probed at every instant to detect the anomalies. Our algorithm is based on active inference which is a general framework to make sequential decisions in order to maximize the notion of free energy.
  arXiv  Detail & Related papers  (2021-05-12T17:54:02Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• Anomaly Detection Under Controlled Sensing Using Actor-Critic Reinforcement Learning [31.841289319809807]
  We consider the problem of detecting anomalies among a given set of processes using noisy binary sensor measurements. The noiseless sensor measurement corresponding to a normal process is 0, and the measurement is 1 if the process is anomalous. We propose a sequential sensor selection policy that dynamically determines which processes to observe at each time and when to terminate the detection algorithm.
  arXiv  Detail & Related papers  (2020-05-26T22:53:17Z)
• 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.