Search

We investigate two closely related nonparametric hypothesis testing problems. In the first problem (i.e., the existence problem), we test whether a testing data stream is generated by one of a set of composite distributions. In the second problem (i.e., the association problem), we test which one of the multiple distributions generates a testing data stream. We assume that some distributions in the set are unknown, and instead, only training sequences generated by the corresponding distributions are available. For both problems, we construct the generalized likelihood tests and characterize the error exponents of the maximum error probabilities. For the existence problem, we show that the error exponent is mainly captured by the Chernoff information between the set of composite distributions and alternative distributions. For the association problem, we show that the error exponent is captured by the minimum Chernoff information between each pair of distributions as well as the Kullback-Leibler Divergences between the approximated distributions (via training sequences) and the true distributions. We also show that the ratio between the lengths of training and testing sequences plays an important role in determining the error decay rate. [ABSTRACT FROM AUTHOR]

A nonparametric anomalous hypothesis testing problem is investigated, in which there are totally $n$ observed sequences out of which $s$ anomalous sequences are to be detected. Each typical sequence consists of $m$ independent and identically distributed (i.i.d.) samples drawn from a distribution $p$ , whereas each anomalous sequence consists of $m$ i.i.d. samples drawn from a distribution $q$ that is distinct from $p$ . The distributions $p$ and $q$ are assumed to be unknown in advance. Distribution-free tests are constructed by using the maximum mean discrepancy as the metric, which is based on mean embeddings of distributions into a reproducing kernel Hilbert space. The probability of error is bounded as a function of the sample size $m$, the number $s$ of anomalous sequences, and the number $n$ of sequences. It is shown that with $s$ known, the constructed test is exponentially consistent if $m$ is greater than a constant factor of $\log n$, for any $p$ and $q$ , whereas with $s$ unknown, $m$ should have an order strictly greater than $\log n$. Furthermore, it is shown that no test can be consistent for arbitrary $p$ and $q$ if $m$ is less than a constant factor of $\log n$. Thus, the order-level optimality of the proposed test is established. Numerical results are provided to demonstrate that the proposed tests outperform (or perform as well as) tests based on other competitive approaches under various cases. [ABSTRACT FROM PUBLISHER]

Nonparametric detection of the possible existence of an anomalous structure over a network is investigated. Nodes corresponding to the anomalous structure (if one exists) receive samples generated by a distribution $q$, which is different from a distribution $p$ generating samples for other nodes. If an anomalous structure does not exist, all nodes receive samples generated by $p$ . It is assumed that the distributions $p$ and $q$ are arbitrary and unknown. The goal is to design statistically consistent tests with probability of errors converging to zero as the network size becomes asymptotically large. Kernel-based tests are proposed based on maximum mean discrepancy, which measures the distance between mean embeddings of distributions into a reproducing kernel Hilbert space. Detection of an anomalous interval over a line network is first studied. Sufficient conditions on minimum and maximum sizes of candidate anomalous intervals are characterized in order to guarantee that the proposed test is consistent. It is also shown that certain necessary conditions must hold in order to guarantee that any test is universally consistent. Comparison of sufficient and necessary conditions yields that the proposed test is order-level optimal and nearly optimal respectively in terms of minimum and maximum sizes of candidate anomalous intervals. Generalization of the results to other networks is further developed. Numerical results are provided to demonstrate the performance of the proposed tests. [ABSTRACT FROM PUBLISHER]

The kernel-based nonparametric approach proposed by Nguyen, Wainwright, and Jordan is further investigated for decentralized detection. In contrast with the uniform kernel used in the previous work, a weighted kernel is proposed, where weight parameters serve to selectively incorporate sensors’ information into the fusion center’s decision rule based on quality of sensors’ observations. Furthermore, weight parameters also serve as sensor selection parameters with nonzero parameters corresponding to sensors being selected. By introducing the l_1 regularization on weight parameters into the risk minimization framework, sensor selection is jointly performed with decision rules for sensors and the fusion center with the resulting optimal decision rule having only sparse nonzero weight parameters. A gradient projection algorithm and a Gauss-Seidel algorithm are developed to solve the risk minimization problem, which is nonconvex, and both algorithms are shown to converge to critical points. Conditions on the sample complexity to guarantee asymptotically small estimation error are characterized based on analysis of Rademacher complexity. Connection between the probability of error and the risk function is also studied. Numerical results are provided to demonstrate the advantages and properties of the proposed approach based on weighted kernel. [ABSTRACT FROM AUTHOR]

This paper studies clustering of data sequences using the k-medoids algorithm. All the data sequences are assumed to be generated from unknown continuous distributions, which form clusters with each cluster containing a composite set of closely located distributions (based on a certain distance metric between distributions). The maximum intracluster distance is assumed to be smaller than the minimum intercluster distance, and both values are assumed to be known. The goal is to group the data sequences together if their underlying generative distributions (which are unknown) belong to one cluster. Distribution distance metrics based k-medoids algorithms are proposed for known and unknown number of distribution clusters. Upper bounds on the error probability and convergence results in the large sample regime are also provided. It is shown that the error probability decays exponentially fast as the number of samples in each data sequence goes to infinity. The error exponent has a simple form regardless of the distance metric applied when certain conditions are satisfied. In particular, the error exponent is characterized when either the Kolmogrov–Smirnov distance or the maximum mean discrepancy are used as the distance metric. Simulation results are provided to validate the analysis. [ABSTRACT FROM AUTHOR]