Show simple item record

dc.contributor.author Raginsky, M
dc.contributor.author Willett, RM
dc.contributor.author Horn, C
dc.contributor.author Silva, J
dc.contributor.author Marcia, RF
dc.date.accessioned 2009-08-13T15:00:44Z
dc.date.issued 2012
dc.identifier.citation IEEE Transactions on Information Theory, 2012, 58 (8), pp. 5544 - 5562
dc.identifier.issn 0018-9448
dc.identifier.uri http://hdl.handle.net/10161/1286
dc.description.abstract This paper describes a methodology for detecting anomalies from sequentially observed and potentially noisy data. The proposed approach consists of two main elements: 1) filtering, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations and 2) hedging, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on the available feedback from an end user. Our algorithms, which combine universal prediction with recent work on online convex programming, do not require computing posterior distributions given all current observations and involve simple primal-dual parameter updates. At the heart of the proposed approach lie exponential-family models which can be used in a wide variety of contexts and applications, and which yield methods that achieve sublinear per-round regret against both static and slowly varying product distributions with marginals drawn from the same exponential family. Moreover, the regret against static distributions coincides with the minimax value of the corresponding online strongly convex game. We also prove bounds on the number of mistakes made during the hedging step relative to the best offline choice of the threshold with access to all estimated beliefs and feedback signals. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality, as well as on the Enron email dataset. © 1963-2012 IEEE.
dc.format.extent 5544 - 5562
dc.format.mimetype application/pdf
dc.language eng
dc.language.iso en_US en_US
dc.relation.ispartof IEEE Transactions on Information Theory
dc.relation.ispartofseries ECE-2009-01 en_US
dc.relation.isversionof 10.1109/TIT.2012.2201375
dc.subject Anomaly detection
dc.subject exponential families
dc.subject filtering
dc.subject individual sequences
dc.subject label-efficient prediction
dc.subject minimax regret
dc.subject online convex programming (OCP)
dc.subject prediction with limited feedback
dc.subject sequential probability assignment
dc.subject universal prediction
dc.title Sequential anomaly detection in the presence of noise and limited feedback
dc.type Journal Article
dc.department Engineering
pubs.issue 8
pubs.organisational-group /Duke
pubs.organisational-group /Duke/Pratt School of Engineering
pubs.organisational-group /Duke/Pratt School of Engineering/Electrical and Computer Engineering
pubs.volume 58

Files in this item

This item appears in the following Collection(s)

Show simple item record