Sequential anomaly detection under sampling constraints

Abstract

The problem of sequential anomaly detection is considered, where multiple data sources are monitoredin real-time, and the goal is to identify the ones that exhibit outlying statistical behavior,when it is not possible to sample all sources at all times. A detection scheme in this context requiresspecifying not only when to stop sampling and which sources to identify as anomalous uponstopping but also which sources to sample at each time instance until stopping. A novel formulationfor this problem is proposed, in which the number of anomalous sources is not necessarilyknown in advance and the number of sampled sources per time instance is not necessarily fixed.Instead, an arbitrary lower bound and an arbitrary upper bound are assumed on the number ofanomalous sources, and the fraction of the expected number of samples over the expected timeuntil stopping is required not to exceed an arbitrary, user-specified level. In addition to this samplingconstraint, the probabilities of at least one false alarm and at least one missed detection arecontrolled below user-specified tolerance levels. A general criterion is established for a policy toachieve the minimum expected time until stopping to a first-order asymptotic approximation asthe two familywise error rates go to zero. Moreover, asymptotic optimality is established for twofamilies of sampling policies. In the first family, named as probabilistic family, each sampling rulechooses each source at each time instance with a probability that depends on past observationsonly through the current estimate of the subset of anomalous sources. In the second family, namedas ordering family, each sampling rule decides the sources to sample based on the ordering of thelikelihood ratio statistics, where randomization may be applied only for the treatment of the decimalpart of the sampling size. The detection policies can also be adapted to treat generalized errormetrics. We examine two error metrics: in the first one, we control the probability of a prescribednumber of misclassification errors, and in the second one, both the probabilities of a number offalse alarms and a number of missed detections. We also study the sequential anomaly detectionproblem from the perspective of the composite hypotheses setting. In the composite hypothesessetting, the samples collected from each source follow the model of a distribution parameterizedby a parameter that belongs to one of two disjoint subsets of a compact Euclidean space. The twocandidate subsets are not necessarily the same for each source. If the parameter belongs to the firstsubset, we characterize the source as outlying; otherwise, we characterize it as regular. The samiiples received from different sources are independent of each other. In all frameworks, we providesimulations that compare the performance of the sampling rules from both families for small fixedthresholds on the error probabilities.

Το πρόβλημα της διαδοχικής ανίχνευσης ανωμαλιών εξετάζεται, όπου πολλαπλές πηγές δεδομένων παρακολουθούνται σε πραγματικό χρόνο και ο στόχος είναι ο εντοπισμός εκείνων που παρουσιάζουν ακραία στατιστική συμπεριφορά, όταν δεν είναι δυνατόν να δειγματοληπτούνται όλες οι πηγές σε κάθε χρονική στιγμή. Ένα σχήμα ανίχνευσης σε αυτό το πλαίσιο απαιτεί τον καθορισμό όχι μόνο του πότε θα σταματήσει η δειγματοληψία και ποιες πηγές θα χαρακτηριστούν ως ανώμαλες κατά τη στιγμή της παύσης, αλλά και ποιες πηγές θα δειγματοληπτούνται σε κάθε χρονική στιγμή μέχρι την παύση. Προτείνεται μια νέα διατύπωση του προβλήματος, στην οποία ο αριθμός των ανώμαλων πηγών δεν είναι κατ’ ανάγκη γνωστός εκ των προτέρων και ο αριθμός των πηγών που δειγματοληπτούνται ανά χρονική στιγμή δεν είναι κατ’ ανάγκη σταθερός. Αντ’ αυτού, υποτίθεται ένα αυθαίρετο κατώτερο και ένα αυθαίρετο ανώτερο όριο στον αριθμό των ανώμαλων πηγών, και απαιτείται το κλάσμα του αναμενόμενου αριθμού δειγμάτων προς τον αναμενόμενο χρόνο μέχρι την παύση να μην υπερβαίνει ένα αυθαίρετο, καθορισμένο από τον χρήστη επίπεδο. Εκτός από αυτόν τον περιορισμό στη δειγματοληψία, οι πιθανότητες τουλάχιστον ενός ψευδούς συναγερμού και τουλάχιστον μίας αποτυχημένης ανίχνευσης ελέγχονται ώστε να παραμένουν κάτω από επίπεδα ανοχής που καθορίζονται από τον χρήστη. Θεσπίζεται ένα γενικό κριτήριο ώστε μια πολιτική να επιτυγχάνει τον ελάχιστο αναμενόμενο χρόνο μέχρι την παύση σε προσέγγιση ασυμπτωτικής βέλτιστης τάξης πρώτης τάξης, καθώς τα δύο οικογενειακά ποσοστά σφάλματος τείνουν στο μηδέν. Επιπλέον, αποδεικνύεται η ασυμπτωτική βέλτιστη απόδοση για δύο οικογένειες πολιτικών δειγματοληψίας. Στην πρώτη οικογένεια, που ονομάζεται πιθανοκρατική οικογένεια, κάθε κανόνας δειγματοληψίας επιλέγει κάθε πηγή σε κάθε χρονική στιγμή με πιθανότητα που εξαρτάται από τις παρελθούσες παρατηρήσεις μόνο μέσω της τρέχουσας εκτίμησης του υποσυνόλου των ανώμαλων πηγών. Στη δεύτερη οικογένεια, που ονομάζεται οικογένεια διάταξης, κάθε κανόνας δειγματοληψίας αποφασίζει ποιες πηγές θα δειγματοληπτηθούν βάσει της διάταξης των στατιστικών λόγου πιθανοφάνειας, όπου τυχαιοποίηση μπορεί να εφαρμοστεί μόνο για τον χειρισμό του δεκαδικού μέρους του μεγέθους δειγματοληψίας. Οι πολιτικές ανίχνευσης μπορούν επίσης να προσαρμοστούν ώστε να χειρίζονται γενικευμένα μέτρα σφάλματος. Εξετάζουμε δύο μέτρα σφάλματος: στο πρώτο, ελέγχουμε την πιθανότητα ενός προκαθορισμένου αριθμού σφαλμάτων ταξινόμησης, και στο δεύτερο, ελέγχονται τόσο οι πιθανότητες ενός αριθμού ψευδών συναγερμών όσο και ενός αριθμού αποτυχημένων ανιχνεύσεων. Μελετούμε επίσης το πρόβλημα της διαδοχικής ανίχνευσης ανωμαλιών από την οπτική του πλαισίου σύνθετων υποθέσεων. Στο πλαίσιο των σύνθετων υποθέσεων, τα δείγματα που συλλέγονται από κάθε πηγή ακολουθούν το μοντέλο μιας κατανομής παραμετροποιημένης από μια παράμετρο που ανήκει σε ένα από δύο ασύμβατα υποσύνολα ενός συμπαγούς Ευκλείδειου χώρου. Τα δύο υποψήφια υποσύνολα δεν είναι κατ’ ανάγκη τα ίδια για κάθε πηγή. Αν η παράμετρος ανήκει στο πρώτο υποσύνολο, χαρακτηρίζουμε την πηγή ως ανώμαλη· διαφορετικά, τη χαρακτηρίζουμε ως κανονική. Τα δείγματα που λαμβάνονται από διαφορετικές πηγές είναι ανεξάρτητα μεταξύ τους. Σε όλα τα πλαίσια, παρέχουμε προσομοιώσεις που συγκρίνουν την απόδοση των κανόνων δειγματοληψίας και από τις δύο οικογένειες για μικρά, σταθερά κατώφλια στις πιθανότητες σφάλματος.