Name
Abstract | ||
|---|---|---|
Anomaly detection is a fundamental problem for which a wide variety of algorithms have been developed. However, compared to supervised learning, there has been very little work aimed at understanding the sample complexity of anomaly detection. In this paper, we take a step in this direction by introducing a Probably Approximately Correct (PAC) framework for anomaly detection based on the identification of rare patterns. In analogy with the PAC framework for supervised learning, we develop sample complexity results that relate the complexity of the pattern space to the data requirements needed for PAC guarantees. We instantiate the general result for a number of pattern spaces, some of which are implicit in current state-of-the-art anomaly detectors. Finally, we design a new simple anomaly detection algorithm motivated by our analysis and show experimentally on several benchmark problems that it is competitive with a state-of-the-art detector using the same pattern space. |
Year | Venue | Field |
|---|---|---|
2016 | UAI | Data mining,Anomaly detection,Probably approximately correct learning,Computer science,Supervised learning,Artificial intelligence,Analogy,Sample complexity,Detector,Machine learning |
DocType | Citations | PageRank |
Conference | 1 | 0.36 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Md Amran Siddiqui | 1 | 4 | 1.42 |
| Alan Fern | 2 | 1528 | 111.59 |
| Thomas G. Dietterich | 3 | 9336 | 1722.57 |
| Shubhomoy Das | 4 | 106 | 7.95 |