The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M > 2 coordinates. When a given coordinate is the outlier, the observations in that coordinate are assumed to be distributed according to the “outlier” distribution, distinct from the common “typical” distribution governing the observations in all the other coordinates. Nothing is known about the outlier or typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier coordinate. Applications of outlier detection include event detection and environment monitoring in sensor networks, understanding of visual search in humans and animals, and fraud detection and anomaly detection in big data. A universal test based on the generalized likelihood principle is proposed and is shown to be universally exponentially consistent, and a single-letter characterization of the error exponent achievable by the test is derived. It is shown that as the number of coordinates approaches infinity, our universal test is asymptotically efficient. Specifically, it achieves the limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known. The results are also generalized to the case with multiple outliers wherein the number of outliers is fixed and known at the outset.
(This is a joint work with Yun Li and Professor Venugopal V. Veeravalli.)
Sirin Nitinawarat obtained the B.S.E.E. degree from Chulalongkorn University, Bangkok, Thailand, with first class honors, and the M.S.E.E. degree from the University of Wisconsin, Madison. He received his Ph.D. degree from the Department of Electrical and Computer Engineering and the Institute for Systems Research at the University of Maryland, College Park, in December 2010. He is now a postdoctoral research associate at the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign. His research interests are in information and coding theory, statistical signal processing, estimation and detection, stochastic control, communications, and machine learning.
Dr. Nitinawarat was a co-organizer for the special session on “Controlled Sensing for Inference” at the 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). He was a finalist for the best student-paper award at the IEEE International Symposium on Information Theory, which was held at Austin, Texas, in 2010. During his Ph.D. study at the University of Maryland, he received graduate teaching fellowships in Fall 2007, Spring 2008, and Spring 2009.
