Timezone: »
We propose a novel non-parametric adaptive anomaly detection algorithm for high dimensional data based on score functions derived from nearest neighbor graphs on n-point nominal data. Anomalies are declared whenever the score of a test sample falls below q, which is supposed to be the desired false alarm level. The resulting anomaly detector is shown to be asymptotically optimal in that it is uniformly most powerful for the specified false alarm level, q, for the case when the anomaly density is a mixture of the nominal and a known density. Our algorithm is computationally efficient, being linear in dimension and quadratic in data size. It does not require choosing complicated tuning parameters or function approximation classes and it can adapt to local structure such as local change in dimensionality. We demonstrate the algorithm on both artificial and real data sets in high dimensional feature spaces.
Author Information
Manqi Zhao (Boston Univesity)
Venkatesh Saligrama (Boston University)
More from the Same Authors
-
2019 Poster: Efficient Near-Optimal Testing of Community Changes in Balanced Stochastic Block Models »
Aditya Gangrade · Praveen Venkatesh · Bobak Nazer · Venkatesh Saligrama -
2019 Poster: Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices »
Don Dennis · Durmus Alp Emre Acar · Vikram Mandikal · Vinu Sankar Sadasivan · Venkatesh Saligrama · Harsha Vardhan Simhadri · Prateek Jain -
2017 Poster: Adaptive Classification for Prediction Under a Budget »
Feng Nan · Venkatesh Saligrama -
2016 Poster: Pruning Random Forests for Prediction on a Budget »
Feng Nan · Joseph Wang · Venkatesh Saligrama -
2016 Poster: Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings »
Tolga Bolukbasi · Kai-Wei Chang · James Y Zou · Venkatesh Saligrama · Adam T Kalai -
2015 Poster: Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction »
Joseph Wang · Kirill Trapeznikov · Venkatesh Saligrama -
2014 Poster: Efficient Minimax Signal Detection on Graphs »
Jing Qian · Venkatesh Saligrama -
2012 Poster: Local Supervised Learning through Space Partitioning »
Joseph Wang · Venkatesh Saligrama -
2010 Poster: Probabilistic Belief Revision with Structural Constraints »
Peter B Jones · Venkatesh Saligrama · Sanjoy K Mitter -
2009 Spotlight: Anomaly Detection with Score functions based on Nearest Neighbor Graphs »
Manqi Zhao · Venkatesh Saligrama
