Multiple observation sequences are collected, among which there is a small subset of outliers. A sequence is considered an outlier if the observations therein are generated by a mechanism different from that generating the observations in the majority of sequences. In the universal setting, the goal is to identify all the outliers without any knowledge about the underlying generating mechanisms. In prior work, this problem was studied as a universal hypothesis testing problem, and a generalized likelihood test was constructed and its asymptotic performance characterized. Here a connection is made between the generalized likelihood test and clustering algorithms from machine learning. It is shown that the generalized likelihood test is equivalent to combinatorial clustering over the probability simplex with the Kullback-Leibler divergence being the dissimilarity measure. Applied to synthetic data sets for outlier hypothesis testing, the performance of the generalized likelihood test is shown to be superior to that of a number of other clustering algorithms for sufficiently large sample sizes.

In outlier hypothesis testing, multiple observation sequences are collected, a small subset of which are outliers. Observations in an outlier sequence are generated by a mechanism different from that generating the observations in the majority of sequences. The goal is to best discern all the outlier sequences without any knowledge of the underlying generating mechanisms. A generalized likelihood test is considered in the fixed sample size setting. In the sequential setting, a test based on the Multihypothesis Sequential Probability Ratio Test and the repeated significance test is considered. The sequential test outperforms the generalized likelihood test when the lengths of the observation sequences exceed certain values. Applied to a real data set for spam detection, the performance of the proposed tests is shown to be superior to those based on the maximum mean discrepancy for large sample size.

Universal outlier hypothesis testing is studied in a sequential setting. Multiple observation sequences are collected, one of which is an outlier. Observations in the outlier sequence are generated by a unique mechanism, different from that generating the observations in all other sequences. The goal is to design a universal test to best discern the outlier sequence with the fewest observations on average. Based on the Multihypothesis Sequential Probability Ratio Test and the generalized likelihood test, a universal test is proposed and shown to be universally exponentially consistent. A lower bound on the achievable error exponents of such a test is derived. The proposed test can be modified to accommodate an additional null hypothesis with no outlier. In particular, it is shown to be consistent under the null hypothesis while retaining universally exponential consistency under all other hypotheses.

Outlier hypothesis testing is studied in a universal setting. Multiple sequences of observations are collected, a small subset of which are outliers. A sequence is considered an outlier if the observations in that sequence are distributed according to an outlier distribution, distinct from the typical distribution governing the observations in all the other sequences. Nothing is known about the outlier and typical distributions except that they are distinct and have full supports. The goal is to design a universal test to best discern the outlier sequence(s). For models with exactly one outlier sequence, the generalized likelihood test is shown to be universally exponentially consistent. A single-letter characterization of the error exponent achievable by the test is derived, and it is shown that the test achieves the optimal error exponent asymptotically as the number of sequences approaches infinity. When the null hypothesis with no outlier is included, a modification of the generalized likelihood test is shown to achieve the same error exponent under each non-null hypothesis, and also consistency under the null hypothesis. Then, models with more than one outlier are studied in the following settings. For the setting with a known number of distinctly distributed outliers, the achievable error exponent of the generalized likelihood test is characterized. The limiting error exponent achieved by such a test is characterized, and the test is shown to be asymptotically exponentially consistent. For the setting with an unknown number of identically distributed outliers, a modification of the generalized likelihood test is shown to achieve a positive error exponent under each non-null hypothesis, and also consistency under the null hypothesis. When the outlier sequences can be distinctly distributed (with their total number being unknown), it is shown that a universally exponentially consistent test cannot exist, even when the typical distribution is known and the null hypothesis is excluded.

The following outlier hypothesis testing problem is studied in a universal setting. Vector observations are collected each with M ≥ 3 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 and the 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. 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 a limiting error exponent that is equal to the largest achievable error exponent when the outlier and typical distributions are both known.