Search

In the era of Big Data, cluster analysis of high-dimensional data sets often suffers from the Curse of dimensionality. To overcome this problem, the dimensionality reduction through feature selection becomes inevitable. Co-clustering or two-way clustering is considered to be a more sophisticated tool than conventional one-way clustering. Moreover, the advent of multi-view learning shows that the subjects of a data set can be interpreted in many ways. Interestingly, a minimal number of existing feature selection algorithms take advantage of the co-clustering method and are designed to consider multi-view data. Motivated by this, in the current article, we propose a feature (gene) selection method for high dimensional gene expression (GE) data through a multi-objective optimization based multi-view Co-Clustering algorithm (named MMCo-Clus). A popular evolutionary technique – Non-dominated Sorting Genetic Algorithm-II (NSGA-II) has been utilized as the proposed method's underlying optimization strategy. First, we construct two views of a chosen data set, utilizing knowledge from two different biological data sources. Next, we develop the MMCo-Clus algorithm considering the constructed views to identify a set of “good” co-clustering solutions. Finally, based on a concept of consensus operation on the co-clustering outcome, a small number of most relevant and non-redundant features are extracted from the original feature-space. The reduced dimension formed by new feature-space causes to decrease the computational burden and noise level of original data. For experimental analysis, we have chosen three benchmark GE data sets. Our feature selection method's effectiveness is evaluated through sample-classification accuracy, accompanied by the cluster profile plot/Eisen plot/t-SNE plot, and biological/statistical significance test. A thorough comparative analysis with existing feature selection algorithms using external and internal evaluation metrics supports our proposed method's potency. [ABSTRACT FROM AUTHOR]

Software defect prediction aims to predict defect-prone code regions automatically before defects are discovered. Accurate prediction helps software practitioners to prioritize their testing efforts. In recent decades, dozens of approaches have been put forward and acquired good results in this field. However, in practical scenarios, many projects have limited labeled instances; more than that, most of these labeled instances are nondefective. The lack of training data and class imbalance problem together bring serious challenges to software defect prediction tasks. So far, few of prevailing approaches can well handle these two difficulties simultaneously. One important reason is that they do not pay adequate attention to several key instances, which are difficult to classify in a small imbalanced dataset. This article introduces the concept of “instance hardness” to integrate various difficulties of imbalance classification tasks. Based on it, a novel imbalance learning framework named self-paced ensemble of ensembles (SPE $^{2}$) is proposed to perform software defect prediction. SPE $^{2}$ aims to generate a strong ensemble of ensembles by self-paced harmonizing instance hardness via undersampling. Finally, SPE $^{2}$ is extensively compared with eight imbalance learning approaches on ten open-source defect datasets. Experiments indicate that SPE $^{2}$ improves the performance and achieves better and more significant F-measure values than its existing counterparts, based on Brunner’s statistical significance test and Cliff’s effect sizes. [ABSTRACT FROM AUTHOR]

$k$ k -means method using Lloyd heuristic is a traditional clustering method which has played a key role in multiple downstream tasks of machine learning because of its simplicity. However, Lloyd heuristic always finds a bad local minimum, i.e., the bad local minimum makes objective function value not small enough, which limits the performance of $k$ k -means. In this paper, we use coordinate descent (CD) method to solve the problem. First, we show that the $k$ k -means minimization problem can be reformulated as a trace maximization problem, then a simple and efficient coordinate descent scheme is proposed to solve the maximization problem. Two interesting findings through theory are that Lloyd cannot decrease the objective function value of $k$ k -means produced by our CD further, and our proposed method CD to solve $k$ k -means problem can avoid produce empty clusters. In addition, according to the computational complexity analysis, it is verified CD has the same time complexity with original $k$ k -means method. Extensive experiments including statistical hypothesis testing, on several real-world datasets with varying number of clusters, varying number of samples and varying number of dimensions show that CD performs better compared to Lloyd, i.e., lower objective value, better local minimum and fewer iterations. And CD is more robust to initialization than Lloyd whether the initialization strategy is random or initialization of $k$ k -means++. [ABSTRACT FROM AUTHOR]

Despite the promise of Convolutional neural network (CNN) based classification models for histopathological images, it is infeasible to quantify its uncertainties. Moreover, CNNs may suffer from overfitting when the data is biased. We show that Bayesian–CNN can overcome these limitations by regularizing automatically and by quantifying the uncertainty. We have developed a novel technique to utilize the uncertainties provided by the Bayesian–CNN that significantly improves the performance on a large fraction of the test data (about 6% improvement in accuracy on 77% of test data). Further, we provide a novel explanation for the uncertainty by projecting the data into a low dimensional space through a nonlinear dimensionality reduction technique. This dimensionality reduction enables interpretation of the test data through visualization and reveals the structure of the data in a low dimensional feature space. We show that the Bayesian-CNN can perform much better than the state-of-the-art transfer learning CNN (TL-CNN) by reducing the false negative and false positive by 11% and 7.7% respectively for the present data set. It achieves this performance with only 1.86 million parameters as compared to 134.33 million for TL-CNN. Besides, we modify the Bayesian–CNN by introducing a stochastic adaptive activation function. The modified Bayesian–CNN performs slightly better than Bayesian–CNN on all performance metrics and significantly reduces the number of false negatives and false positives (3% reduction for both). We also show that these results are statistically significant by performing McNemar’s statistical significance test. This work shows the advantages of Bayesian-CNN against the state-of-the-art, explains and utilizes the uncertainties for histopathological images. It should find applications in various medical image classifications. [ABSTRACT FROM AUTHOR]

Nonrigid point set (PS) registration is an outstanding and fundamental problem in the fields of robotics, computer vision, medical image analysis, and image-guided surgery (IGS). The aim of a nonrigid registration problem is to align together two point sets where one has been deformed. The assumption of isotropic localization error is shared in the previous nonrigid registration algorithms. In this article, we have derived and presented a novel nonrigid registration algorithm, where the position localization error (PLE) is generalized to be anisotropic, which means that the error distribution is not the same in different spatial directions. The motivation of considering the anisotropic characteristic is that the PLE is actually different in three spatial directions in real applications of registrations, such as IGS. Mathematically, the difficulty in dealing with the anisotropic error case comes from the change from a standard deviation that is a scalar to a covariance matrix. The formulas for updating the parameters in both expectation and maximization steps are derived. More specifically, in the expectation step, we compute the posterior probabilities that represent the correspondences between points in two PSs. In the maximization step, given the current posteriors, the covariance matrix of the PLE and the nonrigid transformation are updated. To further speed up the proposed algorithm, the low-rank approximation variation of our method is also presented. We have demonstrated through experiments on both general and medical data sets (corrupted with noise) that the proposed algorithm outperforms the state-of-the-art ones in terms of registration accuracy and robustness to noise. More specifically, all the experimental results have passed the statistical tests at the 5% significance level. Note to Practitioners—This article was motivated by solving the problem of nonrigidly registering two point sets where one has been deformed and corrupted with anisotropic noise. Most existing registration methods generally assume the positional error to be the same in all directions, which in fact is not the case in real scenarios. This article presents a new robust method that assumes the positional error to be anisotropic, which is the case in point sets coming from the stereo reconstruction. The nonrigid registration problem is formulated as a maximum-likelihood (ML) problem and solved with the expectation–maximization (EM) technique. We have demonstrated through extensive experiments on both general and medical data sets that the proposed registration algorithm achieves significantly improved accuracy, robustness to noise, and outliers compared with state-of-the-art algorithms. The algorithm is particularly suitable for biomedical applications involving the registration, such as medical imaging and image-guided surgery (IGS). [ABSTRACT FROM AUTHOR]

Recently, machine learning-based channel estimation has attracted much attention. The performance of machine learning-based estimation has been validated by simulation experiments. However, little attention has been paid to the theoretical performance analysis. In this paper, we investigate the mean square error (MSE) performance of machine learning-based estimation. Hypothesis testing is employed to analyze its MSE upper bound. Furthermore, we build a statistical model for hypothesis testing, which holds when the linear learning module with a low input dimension is used in machine learning-based channel estimation, and derive a clear analytical relation between the size of the training data and performance. Then, we simulate the machine learning-based channel estimation in orthogonal frequency division multiplexing (OFDM) systems to verify our analysis results. Finally, the design considerations for the situation where only limited training data is available are discussed. In this situation, our analysis results can be applied to assess the performance and support the design of machine learning-based channel estimation. [ABSTRACT FROM AUTHOR]

Motivated by the practical needs of simulation-based optimization, this paper considers a problem for selecting the best feasible design from a finite set of alternatives, subject to stochastic constraints given in several secondary objectives. We propose an efficient ranking and selection procedure that maximizes the accuracy of the selection under a limited simulation budget. The proposed procedure sequentially updates the simulation data of designs with a heuristic policy that allocates further simulation replications according to the evaluation results of data based on a statistical hypothesis test. Compared to recent studies, such as OCBA-CO and SCORE, this procedure can be more efficient when the simulation model involves large stochastic noise because its heuristic policy considers the precision of the sample mean ignored by the previous studies. Several experimental results of benchmarks demonstrate its improved efficiency, and a case study on the design of military network system shows its effectiveness for practical problems. [ABSTRACT FROM AUTHOR]

In principle, the Automatic Identification System (AIS) makes covert rendezvous at sea, such as smuggling and piracy, impossible; in practice, AIS can be spoofed or simply disabled. Previous work showed a means whereby such deviations can be spotted. Here we play the opponent's side, and describe the least-detectable trajectory that the elusive vessel can take. The opponent's route planning problem is formalized as a non-convex optimization problem capitalizing the Kullback-Leibler (KL) divergence between the statistical hypotheses of the nominal and the anomalous trajectories as key performance measure. The velocity of the vessel is modeled with an Ornstein-Uhlenbeck (OU) mean reverting stochastic process, and physical and practical requirements are accounted for by enforcing several constraints at the optimization design stage. To handle the resulting non-convex optimization problem, we propose a globally-optimal and computationally-efficient technique, called the Non-Convex Optimized Stealth Trajectory (N-COST) algorithm. The N-COST algorithm consists amounts to solving multiple convex problems, with the number proportional to the number of segments of the piecewise OU trajectory. The effectiveness of the proposed approach is demonstrated through case studies and a real-world example. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of selecting a Pareto set from among finite alternatives, where each alternative has multiple performance measures evaluated by stochastic simulations. Under limited simulation resources, we propose an efficient algorithm for solving this problem based on a statistical hypothesis test. Using the test, the proposed algorithm evaluates the uncertainty of each design based on the observed simulation results to identify whether the selected Pareto set is accurate. Based on the evaluated uncertainty, the algorithm assigns additional resources to the designs to maximize the accuracy of the selected Pareto set. Applying the sequential procedure, the algorithm increases the precision of the observed information selectively and gradually. Several experiments, including a practical case study, demonstrated its improved efficiency compared to the existing algorithms in the literature. This improved efficiency, along with low complexity and high robustness to noise, allows the proposed algorithm to be effectively applied to practical system designs. [ABSTRACT FROM AUTHOR]

A novel index termed weighted cyclic harmonic-to-noise ratio (WCHNR) is proposed to directly evaluate the quality and quantity of harmonics of bearing characteristic frequency (BCF) in the squared envelope spectrum (SES). There are four steps to construct the proposed index. First, cyclic harmonic-to-noise ratio (CHNR) is defined to evaluate the prominence of harmonic, which is inspired by harmonic-to-noise ratio (HNR) and ratio of cyclic content (RCC). Interestingly, it is showed in this paper that a special case of CHNR is a local $L\infty /L1$ norm, which bridges the proposed index with other indexes such as spectral Gini index and spectral kurtosis. Second, a local 0-dB threshold and a global threshold derived from a statistical hypothesis test are utilized to decide the detection of prominent harmonic. Third, if two consecutive harmonics are not prominent, the following higher order harmonics would not be considered, which helps avoid large gap between prominent harmonics and reduce the influence of random cyclic frequency noise. Finally, the sum of each type of CHNR is weighted based on the number of detected harmonics. The proposed index is compared with the spectral Gini index and spectral kurtosis in three case studies, which indicates that the proposed index is less sensitive to outliers and more effective in bearing fault diagnosis. It is also found that the number of detected harmonics can be potentially used in bearing fault classification easily and practically. [ABSTRACT FROM AUTHOR]

Due to the rapid development of sensing technologies, multiple sensors became available for real-time monitoring of the degradation status of machine systems. With such a wealth of data collected from multiple sensors, researchers have proposed different sensor fusion approaches for prognosis and condition monitoring, thus allowing accurate inference of the remaining useful life (RUL) of machine systems. However, almost no method provides a statistical metric to evaluate the quality of degradation signals for prognosis and condition monitoring. To fill this literature gap, this paper develops a sensor fusion framework to check the reliability of given degradation signals for prognosis and degradation analysis through a series of statistical hypothesis tests. A health index is constructed in the sensor fusion framework to help differentiate between distinct degradation states. Based on the health index, the remaining times to various degradation states are estimated, including the RUL to failure. A published degradation data set of aircraft engines is used to evaluate and compare the prognostic and condition monitoring performance of the proposed method with benchmark methods. Note to Practitioners—This paper aims to real-time forecast the condition of operating units given their real-time multisensor data. In particular, this paper proposes a data fusion framework that fuses the multisensor data to construct a health index signal. The health index is designed to distinguish between any two degradation states during the lifecycle of a unit. Therefore, it can be used to estimate the remaining life to reach any degradation state including failure, which helps to raise early maintenance and safety alarms. The overall procedure can be summarized in the following steps: 1) the architecture of the health index is learned from the multisensor data of historical units that already failed; 2) this architecture is then applied to the real-time multisensor data of an operating unit to construct its real-time health index signal; 3) the real-time health index signal is forecast for future time instances; and 4) for each forecast time instance, the forecast health index value is compared with the historical health index signals to find the most likely degradation state of the operating unit at that time instance. The proposed approach was shown to be effective for applications with a single failure mode. [ABSTRACT FROM AUTHOR]

Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback–Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the Lévy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently. [ABSTRACT FROM AUTHOR]

An active inference problem of detecting anomalies among heterogeneous processes is considered. At each time, a subset of processes can be probed. The objective is to design a sequential probing strategy that dynamically determines which processes to observe at each time and when to terminate the search so that the expected detection time is minimized under a constraint on the probability of misclassifying any process. This problem falls into the general setting of sequential design of experiments pioneered by Chernoff in 1959, in which a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically optimal as the error probability approaches zero. For the problem considered in this paper, a low-complexity deterministic test is shown to enjoy the same asymptotic optimality while offering significantly better performance in the finite regime and faster convergence to the optimal rate function, especially when the number of processes is large. Furthermore, the proposed test offers considerable reduction in computation complexity. [ABSTRACT FROM AUTHOR]

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]

Objective: Although optical imaging of neurons using fluorescent genetically encoded calcium sensors has enabled large-scale in vivo experiments, the sensors’ slow dynamics often blur closely timed action potentials into indistinguishable transients. While several previous approaches have been proposed to estimate the timing of individual spikes, they have overlooked the important and practical problem of estimating interspike interval (ISI) for overlapping transients. Methods: We use statistical detection theory to find the minimum detectable ISI under different levels of signal-to-noise ratio (SNR), model complexity, and recording speed. We also derive the Cramer–Rao lower bounds (CRBs) for the problem of ISI estimation. We use Monte-Carlo simulations with biologically derived parameters to numerically obtain the minimum detectable ISI and evaluate the performance of our estimators. Furthermore, we apply our detector to distinguish overlapping transients from experimentally obtained calcium imaging data. Results: Experiments based on simulated and real data across different SNR levels and recording speeds show that our algorithms can accurately distinguish two fluorescence signals with ISI on the order of tens of milliseconds, shorter than the waveform's rise time. Our study shows that the statistically optimal ISI estimators closely approached the CRBs. Conclusion: Our work suggests that full analysis using recording speed, sensor kinetics, SNR, and the sensor's stochastically distributed response to action potentials can accurately resolve ISIs much smaller than the fluorescence waveform's rise time in modern calcium imaging experiments. Significance: Such analysis aids not only in future spike detection methods, but also in future experimental design when choosing sensors of neuronal activity. [ABSTRACT FROM AUTHOR]

In this paper, we consider distributed testing problems with cascaded encoders, which allow cascaded communications among encoders so that each encoder can utilize messages from other encoders for encoding. We first focus on a special case of testing against independence and design a scheme that enables each encoder to take advantage of extra information from other encoders. We also derive a matching upper bound and prove that the designed scheme is optimal. We then investigate the case with general hypotheses and obtain a lower bound on the type 2 error exponent. We further compare the performances that can be achieved by schemes with and without cascaded communications. We show that cascaded communication improves the performance in terms of the type 2 error exponent under positive rate communication constraints. On the other hand, we prove that cascaded communication does not provide performance gain under zero-rate communication constraints. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of classification via composite sequential hypothesis testing. We focus on two possible schemes for the hypotheses: non-nested and nested. For the first case, we present the generalized sequential probability ratio test (GSPRT) and provide an analysis of its asymptotic optimality. Yet, for the nested case, this algorithm is shown to be inconsistent. Consequently, an alternative solution is derived based on Bayesian considerations, similar to the ones used for the Bayesian information criterion and asymptotic maximum a posteriori probability criterion for model order selection. The proposed test, named penalized GSPRT (PGSPRT), is based on restraining the exponential growth of the GSPRT with respect to the sequential probability ratio test. Furthermore, the commonly used performance measure for sequential tests, known as the average sample number, is evaluated for the PGSPRT under each of the hypotheses. Simulations are carried out to compare the performance measures of the proposed algorithms for two nested model order selection problems. [ABSTRACT FROM AUTHOR]

The optimal control of the heating, ventilation, and air-conditioning (HVAC) system in buildings has a significant energy saving potential and therefore is of a great practical interest. An event-based HVAC control adjusts control actions when certain events occur, which may be faster and more scalable than state-based or time-driven control methods. However, events may capture either local or global changes in the rooms. The choice of events is a tradeoff between the computational efficiency and the control performance. This challenging problem remains open. We consider this as an important problem in this paper and make three major contributions. First, we define local and global events for the HVAC control problem. The complexity of these event-based control policies is defined. Second, based on hypothesis testing, we develop a method to select events that capture a sufficient state information and with a relatively small event space. Third, we demonstrate the performance of this method on two groups of examples, including one group of small-scale problems for the proof of concept and the other group of large-scale problems in the HVAC control. It is shown that our method outperforms the Levin search, which is a traditional complexity-based search method and finds event-based HVAC control policies with a good performance. Note to Practitioners—When there are multiple rooms in a building, the HVAC control may achieve a significant energy saving and an indoor comfort satisfaction in the same time through exploring the coupling among the rooms. By appropriately defining the events, the size of the event space is usually much smaller than the state space. Therefore, an event-based control is more scalable and preferred in practice. Local events capture the state changes of rooms in a small neighborhood, which leads to a small event space but limited information. Global events capture the state changes of rooms in a large neighborhood, which leads to more information but a large event space. It remains open how to select events in large-scale HVAC control problems, especially when the computing budget is limited. In this paper, we define the complexity of an event-based control policy by the number of neighboring rooms considered. We develop a method based on hypothesis testing to select events with a proper complexity in order to achieve a good system performance. The performance of this method is demonstrated on an HVAC control problem. [ABSTRACT FROM AUTHOR]

An algorithm for the estimation of multiple targets from partial and corrupted observations is introduced based on the concept of a partially distinguishable multitarget system. It combines the advantages of engineering solutions like multiple hypothesis tracking with the rigor of point-process-based methods. It is demonstrated that under intuitive assumptions and approximations, the complexity of the proposed multitarget estimation algorithm can be made linear in terms of the number of tracks and the number of observations, while naturally preserving distinct tracks for detected targets, unlike point-process-based methods. [ABSTRACT FROM AUTHOR]

We are concerned with the issue of detecting model changes in probability distributions. We specifically consider the strategies based on the minimum description length (MDL) principle. We theoretically analyze their basic performance from the two aspects: data compression and hypothesis testing. From the view of data compression, we derive a new bound on the minimax regret for model changes. Here, the mini–max regret is defined as the minimum of the worst-case code-length relative to the least normalized maximum likelihood code-length over all model changes. From the view of hypothesis testing, we reduce the model change detection into a simple hypothesis testing problem. We thereby derive upper bounds on error probabilities for the MDL-based model change test. The error probabilities are valid for finite sample size and are related to the information-theoretic complexity as well as the discrepancy measure of the hypotheses to be tested. [ABSTRACT FROM AUTHOR]

It is well known that the mutual information between two random variables can be expressed as the difference of two relative entropies that depend on an auxiliary distribution, a relation sometimes referred to as the golden formula. This paper is concerned with a finite-blocklength extension of this relation. This extension consists of two elements: 1) a finite-blocklength channel-coding converse bound by Polyanskiy and Verdú, which involves the ratio of two Neyman–Pearson $\beta $ functions (beta–beta converse bound); and 2) a novel beta–beta channel-coding achievability bound, expressed again as the ratio of two Neyman–Pearson $\beta $ functions. To demonstrate the usefulness of this finite-blocklength extension of the golden formula, the beta–beta achievability and converse bounds are used to obtain a finite-blocklength extension of Verdú’s wideband-slope approximation. The proof parallels the derivation of the latter, with the beta–beta bounds used in place of the golden formula. The beta–beta (achievability) bound is also shown to be useful in cases where the capacity-achieving output distribution is not a product distribution due to, e.g., a cost constraint or structural constraints on the codebook, such as orthogonality or constant composition. As an example, the bound is used to characterize the channel dispersion of the additive exponential-noise channel and to obtain a finite-blocklength achievability bound (the tightest to date) for multiple-input multiple-output Rayleigh-fading channels with perfect channel state information at the receiver. [ABSTRACT FROM AUTHOR]

This paper considers a problem of distributed hypothesis testing over a network. Individual nodes in a network receive noisy local (private) observations whose distribution is parameterized by a discrete parameter (hypothesis). The marginals of the joint observation distribution conditioned on each hypothesis are known locally at the nodes, but the true parameter/hypothesis is not known. An update rule is analyzed in which nodes first perform a Bayesian update of their belief (distribution estimate) of each hypothesis based on their local observations, communicate these updates to their neighbors, and then perform a “non-Bayesian” linear consensus using the log-beliefs of their neighbors. Under mild assumptions, we show that the belief of any node on a wrong hypothesis converges to zero exponentially fast. We characterize the exponential rate of learning, which we call the network divergence, in terms of the nodes’ influence of the network and the divergences between the observations’ distributions. For a broad class of observation statistics which includes distributions with unbounded support such as Gaussian mixtures, we show that rate of rejection of wrong hypothesis satisfies a large deviation principle, i.e., the probability of sample paths on which the rate of rejection of wrong hypothesis deviates from the mean rate vanishes exponentially fast and we characterize the rate function in terms of the nodes’ influence of the network and the local observation models. [ABSTRACT FROM AUTHOR]

This paper studies how to deploy sensors in the context of detection in adversarial environments. A fusion center is performing a binary hypothesis testing based on measurements from remotely deployed heterogeneous sensors. An attacker may compromise some of the deployed sensors, which send arbitrary measurements to the fusion center. The problems of interest are: to characterize the performance of the system under attack and, thus, develop a performance metric; and to deploy sensors within a cost budget, such that the proposed performance metric is maximized. In this paper, we first present a performance metric by formulating the detection in adversarial environments in a game theoretic way. A Nash equilibrium pair of the detection algorithm and attack strategy, with the deployed sensors given, is provided and the corresponding detection performance is adopted as the performance metric. We then show that the optimal sensor deployment can be determined approximately by solving a group of unbounded knapsack problems. We also show that the performance metric gap between the optimal sensor deployment and the optimal one with sensors being identical is within a fixed constant for any cost budget. The main results are illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient ranking and selection algorithm for a stochastic simulation model. The proposed algorithm evaluates an uncertainty to assess whether the observed best design is truly optimal, based on hypothesis test. Then, it conservatively allocates additional simulation resources to reduce uncertainty with an intuitive allocation rule in each iteration of a sequential procedure. This conservative allocation provides a high robustness to noise for the algorithm. The results of several experiments demonstrated its improved performance compared to the other algorithms in the literature. The algorithm can be an efficient way to solve optimization problems in real-world systems where significant noise exists. [ABSTRACT FROM AUTHOR]

The problem of zero-rate multiterminal hypothesis testing is revisited from the perspective of information-spectrum approach and finite blocklength analysis. A Neyman–Pearson-like test is proposed and its non-asymptotic performance is clarified, for a short block length, it is numerically determined that the proposed test is superior to the previously reported Hoeffding-like test proposed by Han–Kobayashi. For a large deviation regime, it is shown that our proposed test achieves an optimal trade-off between the type I and type II exponents presented by Han–Kobayashi. Among the class of symmetric (type-based) testing schemes, when the type I error probability is non-vanishing, the proposed test is optimal up to the second-order term of the type II error exponent; the latter term is characterized in terms of the variance of the projected relative entropy density. The information geometry method plays an important role in the analysis as well as the construction of the test. [ABSTRACT FROM AUTHOR]

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors. [ABSTRACT FROM PUBLISHER]

Multiple-input multiple-output technology brings new challenges for detecting signal parameters in some intelligent systems. An accurate estimation of the transmit-antenna number is the prerequisite for estimating other signal parameters. Employing random matrix theory, we propose two hypothesis testing based algorithms to blindly estimate the transmit-antenna number. By exploiting hypothesis testing, the blind estimation problem is converted to a location problem, which seeks the location of the boundary between the signal subspace and the noise subspace of the received sample covariance matrix. Then, the estimated transmit-antenna number is determined by the dimension of the signal subspace. Extensive simulations verify that the two proposed algorithms perform better under a wide range of signal-to-noise ratios and sample lengths, compared with conventional algorithms based on Akaike information criterion, minimum description length, and predicted eigenvalue threshold. [ABSTRACT FROM AUTHOR]

A distributed binary hypothesis testing problem is studied with one observer and two decision centers. Achievable type-II error exponents are derived for testing against conditional independence when the observer communicates with the two decision centers over one common and two individual noise-free bit pipes and when it communicates with them over a noisy broadcast channel. The results are based on a coding and testing scheme that splits the observations into subblocks, so that transmitter and receivers can independently apply to each subblock either Gray-Wyner coordination coding with side-information or hybrid joint source-channel coding with side-information, followed by a Neyman-Pearson test over the subblocks at the receivers. This approach allows to avoid introducing further error exponents that one would expect from the receivers’ decoding operations related to binning or the noisy transmission channel. The derived exponents are shown to be optimal in some special cases when communication is over noise-free links. The results reveal a tradeoff between the type-II error exponents at the two decision centers. [ABSTRACT FROM AUTHOR]

We consider the problem of keyless message authentication over noisy channels in the presence of an active adversary. Different from the existing models, in our model, the legitimate users do not have any pre-shared key for authentication. Instead, we use the noisy channel connecting the legitimate users for authentication. The main idea is to utilize the noisy channel connecting the legitimate users to distinguish a legitimate message from a fake message, by generating an output at the receiver that is difficult for the adversary to replicate through its noisy channel. By interpreting the message authentication as a hypothesis testing problem, we investigate the authentication exponent and the authenticated channel capacity of the noisy channel. In the authentication exponent problem, for a given message rate, we investigate the speed at which the optimal successful attack probability can be driven to zero. We fully characterize the authentication exponent for the zero-rate message case and provide both an upper bound and a lower bound on the exponent for the non-zero message rate case. In the authenticated capacity problem, we study the largest data transmission rate under which the attacker’s optimal successful attack probability can still be made arbitrarily small. We establish an all or nothing result. In particular, we show that the authenticated channel capacity is the same as the classic channel capacity if a simulatability condition is not satisfied, while the authenticated capacity will be zero if this condition is satisfied. We also provide efficient algorithms to check this condition. We further show that our results are robust to modeling uncertainties about the eavesdropper’s channels. [ABSTRACT FROM PUBLISHER]

We study a variant of the source identification game with training data in which part of the training data is corrupted by an attacker. In the addressed scenario, the defender aims at deciding whether a test sequence has been drawn according to a discrete memoryless source X \sim PX , whose statistics are known to him through the observation of a training sequence generated by $X$ . In order to undermine the correct decision under the alternative hypothesis that the test sequence has not been drawn from X$ , the attacker can modify a sequence produced by a source Y \sim P_{Y} up to a certain distortion and corrupt the training sequence either by adding some fake samples or by replacing some samples with fake ones. We derive the unique rationalizable equilibrium of the two versions of the game in the asymptotic regime and by assuming that the defender makes his decision by relying only on the first order statistics of the test and the training sequences. By mimicking Stein’s lemma, we derive the best achievable performance for the defender when the first type error probability is required to tend to zero exponentially fast with an arbitrarily small, yet positive, error exponent. We then use such a result to analyze the ultimate distinguishability of any two sources as a function of the allowed distortion and the fraction of corrupted samples injected into the training sequence. [ABSTRACT FROM PUBLISHER]

Given samples from two distributions, a non-parametric two-sample test aims at determining whether the two distributions are equal or not, based on a test statistic. Classically, this statistic is computed on the whole data set, or is computed on a subset of the data set by a function trained on its complement. We consider methods in a third tier, so as to deal with large (possibly infinite) data sets, and to automatically determine the most relevant scales to work at, making two contributions. First, we develop a generic sequential non-parametric testing framework, in which the sample size need not be fixed in advance. This makes our test a truly sequential non-parametric multivariate two-sample test. Under information theoretic conditions qualifying the difference between the tested distributions, consistency of the two-sample test is established. Second, we instantiate our framework using nearest neighbor regressors, and show how the power of the resulting two-sample test can be improved using Bayesian mixtures and switch distributions. This combination of techniques yields automatic scale selection, and experiments performed on challenging data sets show that our sequential tests exhibit comparable performances to those of state-of-the-art non-sequential tests. [ABSTRACT FROM PUBLISHER]

This paper proposes an improved algorithm for the optimal subset selection of a stochastic simulation model. The algorithm uses a statistical hypothesis test based on frequentist inference to evaluate the uncertainty about the selection, and it distributes simulation resources to designs for minimizing the uncertainty in each iteration. Several experiments demonstrate the improved performance compared to the other algorithms, and the performance increases significantly as the noise of the model increases. As a result, its high robustness to noise allows the algorithm to efficiently analyze real-world problems. [ABSTRACT FROM PUBLISHER]

We study detection performance of the majority dominance rule in anm-ary relay tree with node and link failures. The leaves of the tree represent N identical and independent sensors, the root of the tree represents a fusion center that makes the final detection decision, each of the other nodes in the tree is a relay node that combines m binary messages from its immediate child nodes and forms a new binary message using the majority dominance rule. We first provide the limit performance of the detection error probability at the fusion center for the casewhenN goes to infinity. Then, we derive upper and lower bounds for the detection error probability at the fusion center as explicit functions of N. These bounds also characterize the asymptotic decay rate of the detection error probability asN goes to infinity, and showthat the decay rate in the failure case is not faster than that in the nonfailure case. Furthermore, we derive a necessary and sufficient condition in terms of the decay rate of the local failure probability (combination of node failure probability and link failure probability) at each level to ensure that the detection error probability of the tree with node and link failures decays as fast as that of the tree without failures. [ABSTRACT FROM AUTHOR]

This paper studies binary hypothesis testing based on measurements from a set of sensors, a subset of which can be compromised by an attacker. The measurements from a compromised sensor can bemanipulated arbitrarily by the adversary. The asymptotic exponential rate, with which the probability of error goes to zero, is adopted to indicate the detection performance of a detector. In practice, we expect the attack on sensors to be sporadic, and therefore the system may operate with all the sensors being benign for an extended period of time. This motivates us to consider the tradeoff between the detection performance of a detector, i.e., the probability of error, when the attacker is absent (defined as efficiency) and the worst case detection performance when the attacker is present (defined as security). We first provide the fundamental limits of this tradeoff, and then propose a detection strategy that achieves these limits. We then consider a special case, where there is no tradeoff between security and efficiency. In other words, our detection strategy can achieve the maximal efficiency and the maximal security simultaneously. Two extensions of the secure hypothesis testing problem are also studied and fundamental limits and achievability results are provided: first, a subset of sensors, namely "secure" sensors, are assumed to be equipped with better security countermeasures and hence are guaranteed to be benign; and second, detection performance with unknown number of compromised sensors. Numerical examples are given to illustrate the main results. [ABSTRACT FROM AUTHOR]

Under Markovian assumptions, we leverage a central limit theorem for the empirical measure in the test statistic of the composite hypothesis Hoeffding test so as to establish weak convergence results for the test statistic, and, thereby, derive a new estimator for the threshold needed by the test. We first show the advantages of our estimator over an existing estimator by conducting extensive numerical experiments. We find that our estimator controls better for false alarms while maintaining satisfactory detection probabilities. We then apply the Hoeffding test with our threshold estimator to detect anomalies in two distinct applications domains: One in communication networks and the other in transportation networks. The former application seeks to enhance cyber security and the latter aims at building smarter transportation systems in cities. [ABSTRACT FROM AUTHOR]

This paper deals with target classification by using both feature data and kinematic measurements. The problem is tackled by multihypothesis sequential testing with embedded target tracking. We implement an Armitage sequential test for nonmaneuvering and maneuvering targets. Both (centralized and distributed) fusion architectures are used for the embedded tracking. The contributions of the kinematic measurements to classification are analyzed, and classification performance improvement is shown analytically for a special case. Numerical results are provided to demonstrate the performance of our algorithms. [ABSTRACT FROM AUTHOR]

In this paper, the Gaussian quasi-likelihood ratio test (GQLRT) for non-Bayesian binary hypothesis testing is generalized by applying a transform to the probability distribution of the data. The proposed generalization, called measure-transformed GQLRT (MT-GQLRT), selects a Gaussian probability model that best empirically fits a transformed probability measure of the data. By judicious choice of the transform, we show that, unlike the GQLRT, the proposed test is resilient to outliers and involves higher order statistical moments leading to significant mitigation of the model mismatch effect on the decision performance. A Bayesian extension of the proposed MT-GQLRT is also developed that is based on selection of a Gaussian probability model that best empirically fits a transformed conditional probability distribution of the data. The non-Bayesian and Bayesian MT-GQLRTs are applied to signal detection and classification, in simulation examples that illustrate their advantages over the standard GQLRT and other robust alternatives. [ABSTRACT FROM AUTHOR]

Objective: Recent studies utilizing fetal magnetocardiography have demonstrated the efficacy of corrected QT interval (QTc) measurement for in utero diagnosis and prognosis of long QT syndrome, a leading cause of sudden death in early life. The objective of the study was to formulate and test a novel statistical estimation method to detect the end of the fetal T-wave and thereby improve the accuracy of fetal QT interval measurement. Methods: To detect the end of the T-wave, we apply a sequential composite hypothesis test to decide when the T-wave has returned to baseline. The method uses the generalized likelihood ratio test in conjunction with a low-rank spatiotemporal model that exploits the repetitive nature of cardiac signals. The unknown model parameters are determined using maximum likelihood estimation. Results: In realistic simulations, the detector was shown to be accurate to within 10 ms (95% prediction interval), even at noise-to-signal ratios as high as 6. When applied to real data from normal fetuses, the detector agreed well with measurements made by cardiologists ( $-$1.4 $\pm$ 6.9 ms). Conclusions: The method was effective and practical. Detector performance was excellent despite the continual presence of strong maternal interference. Significance: This detector serves as a valuable adjunct to traditional measurement based on subjective assessment. [ABSTRACT FROM PUBLISHER]

We prove new strong converse results in a variety of group testing settings, generalizing a result of Baldassini et al.. First, in the non-adaptive case, we mimic the hypothesis testing argument introduced in the finite blocklength channel coding regime by Polyanskiy et al., and using joint source–channel coding arguments of Kostina and Verdú. In the adaptive case, we combine this approach with a novel model formulation based on causal probability and directed information theory. In both cases, we prove results, which are valid for finite sized problems, and imply capacity results in the asymptotic regime. These results are illustrated graphically for a range of models. [ABSTRACT FROM AUTHOR]

Minimax robust hypothesis testing is studied for the cases where the collected data samples are corrupted by outliers and are mismodeled due to modeling errors. For the former case, Huber’s clipped likelihood ratio test is introduced and analyzed. For the latter case, first, a robust hypothesis testing scheme based on the Kullback–Leibler divergence is designed. This approach generalizes a previous work by Levy. Second, Dabak and Johnson’s asymptotically robust test is introduced, and other possible designs based on $f$ -divergences are investigated. All proposed and analyzed robust tests are extended to fixed sample size and sequential probability ratio tests. Simulations are provided to exemplify and evaluate the theoretical derivations. [ABSTRACT FROM AUTHOR]

Neuroscientists have recently shown that images that are difficult to find in visual search elicit similar patterns of firing across a population of recorded neurons. The L^1 distance between firing rate vectors associated with two images was strongly correlated with the inverse of decision time in behavior. But why should decision times be correlated with L^1 distance? What is the decision-theoretic basis? In our decision theoretic formulation, we model visual search as an active sequential hypothesis testing problem with switching costs. Our analysis suggests an appropriate neuronal dissimilarity index, which correlates equally strongly with the inverse of decision time as the L^1 distance. We also consider a number of other possibilities, such as the relative entropy (Kullback–Leibler divergence) and the Chernoff entropy of the firing rate distributions. A more stringent test of equality of means, which would have provided a strong backing for our modeling, fails for our proposed as well as the other already discussed dissimilarity indices. However, test statistics from the equality of means test, when used to rank the indices in terms of their ability to explain the observed results, places our proposed dissimilarity index at the top followed by relative entropy, Chernoff entropy, and the L^1 indices. Computations of the different indices require an estimate of the relative entropy between two Poisson point processes. An estimator is developed and is shown to have near unbiased performance for almost all operating regions. [ABSTRACT FROM AUTHOR]

This paper studies recursive composite hypothesis testing in a network of sparsely connected agents. The network objective is to test a simple null hypothesis against a composite alternative concerning the state of the field, modeled as a vector of (continuous) unknown parameters determining the parametric family of probability measures induced on the agents’ observation spaces under the hypotheses. Specifically, under the alternative hypothesis, each agent sequentially observes an independent and identically distributed time-series consisting of a (nonlinear) function of the true but unknown parameter corrupted by Gaussian noise, whereas, under the null, they obtain noise only. Two distributed recursive generalized likelihood ratio test type algorithms of the consensus+innovations form are proposed, namely, \mathcal CIGLRT-L and \mathcal CIGLRT-NL , in which the agents estimate the underlying parameter and in parallel also update their test decision statistics by simultaneously processing the latest local sensed information and information obtained from neighboring agents. For \mathcal CIGLRT-NL , for a broad class of nonlinear observation models and under a global observability condition, algorithm parameters which ensure asymptotically decaying probabilities of errors (probability of miss and probability of false detection) are characterized. For \mathcal CIGLRT-L , a linear observation model is considered and upper bounds on large deviations decay exponent for the error probabilities are obtained. [ABSTRACT FROM AUTHOR]

This paper revisits the Gaussian degraded relay channel, where the link that carries information from the source to the destination is a physically degraded version of the link that carries information from the source to the relay. The source and the relay are subject to expected power constraints. The $\varepsilon $ -capacity of the channel is characterized and it is strictly larger than the capacity for any $\varepsilon >0$ , which implies that the channel does not possess the strong converse property. The proof of the achievability part is based on several key ideas: block Markov coding, which is used in the classical decode-forward strategy, power control for Gaussian channels under expected power constraints, and a careful scaling between the block size and the total number of block uses. The converse part is proved by first establishing two non-asymptotic lower bounds on the error probability, which are derived from the type-II errors of some binary hypothesis tests. Subsequently, each lower bound is simplified by conditioning on an event related to the power of some linear combination of the codewords transmitted by the source and the relay. Lower and upper bounds on the second-order term of the optimal coding rate are also obtained. [ABSTRACT FROM PUBLISHER]

We consider the problem of optimally utilizing $N$ resources, each in an unknown binary state. The state of each resource can be inferred from state-dependent noisy measurements. Depending on its state, utilizing a resource results in either a reward or a penalty per unit time. The objective is a sequential strategy governing the decision of sensing and exploitation at each time to maximize the expected utility (i.e., total reward minus total penalty and sensing cost) over a finite horizon $L$. We formulate the problem as a partially observable Markov decision process and show that the optimal strategy is based on two time-varying thresholds for each resource and an optimal selection rule to sense a particular resource. Since a full characterization of the optimal strategy is generally intractable, we develop a low-complexity policy that is shown by simulations to offer a near optimal performance. This problem finds applications in opportunistic spectrum access, marketing strategies, and other sequential resource allocation problems. [ABSTRACT FROM PUBLISHER]

We study the maximum-likelihood estimator in a setting where the dependent variable is a random graph and covariates are available on a graph level. The model generalizes the well-known $\beta$-model for random graphs by replacing the constant model parameters with regression functions. Cramér–Rao bounds are derived for special cases of the undirected $\beta$-model, the directed $\beta$-model, and the covariate-based $\beta$-model. The corresponding maximum-likelihood estimators are compared with the bounds by means of simulations. Moreover, examples are given on how to use the presented maximum-likelihood estimators to test for directionality and significance. Finally, the applicability of the model is demonstrated using temporal social network data describing communication among healthcare workers. [ABSTRACT FROM PUBLISHER]

We consider asymptotic hypothesis testing (or state discrimination with asymmetric treatment of errors) between an arbitrary fixed bipartite pure state $ | \Psi \rangle $ and the white noise state (the completely mixed state) under one-way local operations and classical communications (LOCC), two-way LOCC, and separable Positive Operator Valued Measures (POVMs). As a result, we derive the Hoeffding bounds under two-way LOCC POVMs and separable POVMs. Further, we derive Stein’s lemma type of optimal error exponents under one-way LOCC, two-way LOCC, and separable POVMs up to the third order, which clarifies the difference between one-way and two-way LOCC POVM. Our results clarify the relationship between the entanglement of Renyi entropy and the hypothesis testing under LOCC, since the entanglement of Renyi entropy appears in the formula of both the Hoeffding bounds and Stein’s lemma type of error exponents. This paper gives a very rare example in which the optimal performance under the infinite-round two-way LOCC is also equal to that under separable operations and can be attained with two-round communication, but not with the one-way LOCC. [ABSTRACT FROM AUTHOR]

This paper investigates a new fault detection method for induction machines diagnosis. The proposed detection method is based on hypothesis testing. The decision is made between two hypotheses: the machine is healthy and the machine is faulty. The generalized likelihood ratio test is used to address this issue with unknown signal and noise parameters. To implement this detector, the unknown parameters are replaced by their estimates. Specifically, four estimations are required, which are model order, frequency, phase, and amplitude estimations. The model order is obtained using the Bayesian information criterion. Total least-squares estimation of signal parameters via rotational invariance techniques is used to estimate frequencies. Then, phases and amplitudes are obtained using the least-squares estimator. The proposed approach performance is assessed using simulation data by plotting the receiver operating characteristic curves. Two faults are considered: bearing and broken rotor bar faults. Experimental tests clearly show the effectiveness of the proposed detector. [ABSTRACT FROM PUBLISHER]

The non-deterministic nature of multi-threaded workloads running on multi-core platforms often leads to notable performance variability from run to run. Such variability makes experimental results prone to misinterpretations or misguided claims. To deal with such variability, statistical inference methods are usually used to summarize the experimental results with certain confidence levels by running the experiments or measurements a large number of times. However, such statistical results are often too vague or too simplistic. They are not sufficient to help users understand the causes of such variability, and allow more in-depth analysis on the results or reproduce the results for validation during design space exploration. To allow better analyzability and reproducibility, we propose a framework to tackle such variability, called VarCatcher. The key to VarCatcher is to characterize a parallel execution using Parallel Characteristics Vector (PCV). A clustering-based approach is then used to group runs with similar execution characteristics that can later be used to analyze results in-depth, to customize different evaluation strategies, reproduce the result for variability, to determine the impact of features, or to assist performance diagnosis. We have built a prototype of VarCatcher that includes a user-level toolset for runtime monitoring and measurements using the Intel Processor Trace feature on commodity Intel processors as well as an architecture extension with very low runtime overheads (around 3 and 0.01 percent accordingly). Several case studies confirm that VarCatcher enables several appealing features such as in-depth result analysis, customized evaluation strategies, and reproducibility. [ABSTRACT FROM AUTHOR]