Scalable and Decentralized Algorithms for Anomaly Detection via
Learning-Based Controlled Sensing
- URL: http://arxiv.org/abs/2112.04912v1
- Date: Wed, 8 Dec 2021 11:20:36 GMT
- Title: Scalable and Decentralized Algorithms for Anomaly Detection via
Learning-Based Controlled Sensing
- Authors: Geethu Joseph, Chen Zhong, M. Cenk Gursoy, Senem Velipasalar, and
Pramod K.Varshney
- Abstract summary: 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.
- Score: 40.14838268469627
- 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 a
subset of the processes at any given time instant 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 processes
to be observed at a given time instant, decides when to stop taking
observations, and declares the decision on anomalous processes. The objective
of the detection algorithm is to identify the anomalies with an accuracy
exceeding the desired value while minimizing the delay in decision making. We
devise a centralized algorithm where the processes are jointly selected by a
common agent as well as a decentralized algorithm where the decision of whether
to select a process is made independently for each process. Our algorithms rely
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 algorithms using the deep actor-critic reinforcement
learning framework. Unlike prior work on this topic that has exponential
complexity in the number of processes, our algorithms have computational and
memory requirements that are both polynomial in the number of processes. We
demonstrate the efficacy of these algorithms using numerical experiments by
comparing them with 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) - 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) - 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) - 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) - CRATOS: Cognition of Reliable Algorithm for Time-series Optimal Solution [12.906367105870341]
CRATOS is a self-adapt algorithms that extract features from time series, and then cluster series with similar features into one group.
Our methods can significantly reduce the cost of development and maintenance of anomaly detection.
The accuracy of the anomaly detection algorithms in this paper is 85.1%.
arXiv Detail & Related papers (2020-03-03T09:49:30Z)
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.