Scalable anomaly detection in large homogeneous populations

DOI10.1016/J.AUTOMATICA.2014.03.008MaRDI QIDQ458772zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Henrik Ohlsson, Tianshi Chen, Sina Khoshfetrat Pakazad, Lennart Ljung, S. Shankar Sastry

Publication date 8 October 2014

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5803, http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-108173

zbMATH Keywords

outlier detectionanomaly detectionsystem identificationdistributed optimizationmulti-hypothesis testing

Mathematics Subject Classification ID

Convex programming (90C25) System identification (93B30)

Abstract: Anomaly detection in large populations is a challenging but highly relevant problem. The problem is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomal systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problems of practical interests. In the current paper we take an optimization approach to this multi-hypothesis problem. We first observe that the problem is equivalent to a non-convex combinatorial optimization problem. We then relax the problem to a convex problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.

Recommendations

• Unsupervised learning based distributed detection of global anomalies
• Compressed anomaly detection with multiple mixed observations
• Detection of an anomalous cluster in a network
• Change-point detection in multichannel and distributed systems
• Bayesian anomaly detection methods for social networks

Cites work

• scientific article; zbMATH DE number 41467 (Why is no real title available?)
• scientific article; zbMATH DE number 194744 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 3395249 (Why is no real title available?)
• Bayesian analysis of some outlier problems in time series
• Compressed sensing
• Detection of abrupt changes: theory and application
• Model Selection and Estimation in Regression with Grouped Variables
• Outlier Detection and Time Series Modeling
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• The elements of statistical learning. Data mining, inference, and prediction

Cited in

(4)

• An ordinal anomaly probability algorithm for anomaly detection problems in massive data sets
• Distributed primal–dual interior-point methods for solving tree-structured coupled convex problems using message-passing
• Large scale anomaly detection in mixed numerical and categorical input spaces
• Compressed anomaly detection with multiple mixed observations

Describes a project that uses

Uses Software

• ElemStatLearn

This page was built for publication: Scalable anomaly detection in large homogeneous populations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458772)