Non Parametric Distributed Inference in Sensor Networks Using Box Particles Messages

This paper deals with the problem of inference in distributed systems where the probability model is stored in a distributed fashion. Graphical models provide powerful tools for modeling this kind of problems. Inspired by the box particle filter which combines interval analysis with particle filtering to solve temporal inference problems, this paper introduces a belief propagation-like message-passing algorithm that uses bounded error methods to solve the inference problem defined on an arbitrary graphical model. We show the theoretic derivation of the novel algorithm and we test its performance on the problem of calibration in wireless sensor networks. That is the positioning of a number of randomly deployed sensors, according to some reference defined by a set of anchor nodes for which the positions are known a priori. The new algorithm, while achieving a better or similar performance, offers impressive reduction of the information circulating in the network and the needed computation times.     

Finding the needles in the haystack: efficient intelligence processing

As a result of communication technologies, the main intelligence challenge has shifted from collecting data to efficiently processing it so that relevant, and only relevant, information is passed on to intelligence analysts. We consider intelligence data intercepted on a social communication network. The social network includes both adversaries (eg terrorists) and benign participants. We propose a methodology for efficiently searching for relevant messages among the intercepted communications. Besides addressing a real and urgent problem that has attracted little attention in the open literature thus far, the main contributions of this paper are two-fold. First, we develop a novel knowledge accumulation model for intelligence processors, which addresses both the nodes of the social network (the participants) and its edges (the communications). Second, we propose efficient prioritization algorithms that utilize the processor’s accumulated knowledge. Our approach is based on methods from graphical models, social networks, random fields, Bayesian learning, and exploration/exploitation algorithms.     

Efficient Bayesian Inference for Multivariate Probit Models With Sparse Inverse Correlation Matrices

We propose a Bayesian approach for inference in the multivariate probit model, taking into account the association structure between binary observations. We model the association through the correlation matrix of the latent Gaussian variables. Conditional independence is imposed by setting some off-diagonal elements of the inverse correlation matrix to zero and this sparsity structure is modeled using a decomposable graphical model. We propose an efficient Markov chain Monte Carlo algorithm relying on a parameter expansion scheme to sample from the resulting posterior distribution. This algorithm updates the correlation matrix within a simple Gibbs sampling framework and allows us to infer the correlation structure from the data, generalizing methods used for inference in decomposable Gaussian graphical models to multivariate binary observations. We demonstrate the performance of this model and of the Markov chain Monte Carlo algorithm on simulated and real datasets. This article has online supplementary materials.     

Cooperative target localization by multiple unmanned aircraft systems using sensor fusion quality

Over the past several years, researchers at the U.S. Air Force Academy developed cooperative, distributed aerial sensor networks (Pack et?al. in IEEE Trans Syst Man Cybern Part B Cybern 39(4):959?C970, 2009) using multiple small unmanned aerial vehicles (SUAVs) to search, detect, and locate ground targets. The use of distributed SUAVs, however, introduced a set of problems, including difficulties in reliable air-to-air communication and clock synchronization among onboard systems of multiple SUAVs. The communication problems further aggravate the synchronization problem contributing to a large target localization error. Conventional methods use multiple sensor outputs of the same target seen from different perspectives to increase the target localization accuracy. These methods are effective only when the pose errors of sensor platforms based on GPS data are modeled accurately, which is not a reasonable assumption for SUAVs, especially when SUAVs operate in an environment with wind gusts. In this paper, we propose a robust, novel technique that analyzes what we call ??sensor fusion quality?? to assign an appropriate sensor reliability value to each set of updated sensor data. In the proposed approach, we characterize the quality of a set of newly acquired sensor data, containing a target, by examining the joint target location probability density function. The validity of the proposed method is demonstrated using flight test data.     

Structural-EM for learning PDG models from incomplete data

Probabilistic Decision Graphs (PDGs) are a class of graphical models that can naturally encode some context specific independencies that cannot always be efficiently captured by other popular models, such as Bayesian Networks. Furthermore, inference can be carried out efficiently over a PDG, in time linear in the size of the model. The problem of learning PDGs from data has been studied in the literature, but only for the case of complete data. We propose an algorithm for learning PDGs in the presence of missing data. The proposed method is based on the Expectation-Maximisation principle for estimating the structure of the model as well as the parameters. We test our proposal on both artificially generated data with different rates of missing cells and real incomplete data. We also compare the PDG models learnt by our approach to the commonly used Bayesian Network (BN) model. The results indicate that the PDG model is less sensitive to the rate of missing data than BN model. Also, though the BN models usually attain higher likelihood, the PDGs are close to them also in size, which makes the learnt PDGs preferable for probabilistic inference purposes.     

Decomposition of Covariate-Dependent Graphical Models with Categorical Data

Graphical models are wildly used to describe conditional dependence relationships among interacting random variables. Among statistical inference problems of a graphical model, one particular interest is utilizing its interaction structure to reduce model complexity. As an important approach to utilizing structural information, decomposition allows a statistical inference problem to be divided into some sub-problems with lower complexities. In this paper, to investigate decomposition of covariate-dependent graphical models, we propose some useful definitions of decomposition of covariate-dependent graphical models with categorical data in the form of contingency tables. Based on such a decomposition, a covariate-dependent graphical model can be split into some sub-models, and the maximum likelihood estimation of this model can be factorized into the maximum likelihood estimations of the sub-models. Moreover, some sufficient and necessary conditions of the proposed definitions of decomposition are studied.     

Precision Matrix Estimation by Inverse Principal Orthogonal Decomposition

We investigate the structure of a large precision matrix in Gaussian graphical models by decomposing it into a low rank component and a remainder part with sparse precision matrix.Based on the decomposition,we propose to estimate the large precision matrix by inverting a principal orthogonal decomposition(IPOD).The IPOD approach has appealing practical interpretations in conditional graphical models given the low rank component,and it connects to Gaussian graphical models with latent variables.Specifically,we show that the low rank component in the decomposition of the large precision matrix can be viewed as the contribution from the latent variables in a Gaussian graphical model.Compared with existing approaches for latent variable graphical models,the IPOD is conveniently feasible in practice where only inverting a low-dimensional matrix is required.To identify the number of latent variables,which is an objective of its own interest,we investigate and justify an approach by examining the ratios of adjacent eigenvalues of the sample covariance matrix?Theoretical properties,numerical examples,and a real data application demonstrate the merits of the IPOD approach in its convenience,performance,and interpretability.     

High-Dimensional Mixed Graphical Models

While graphical models for continuous data (Gaussian graphical models) and discrete data (Ising models) have been extensively studied, there is little work on graphical models for datasets with both continuous and discrete variables (mixed data), which are common in many scientific applications. We propose a novel graphical model for mixed data, which is simple enough to be suitable for high-dimensional data, yet flexible enough to represent all possible graph structures. We develop a computationally efficient regression-based algorithm for fitting the model by focusing on the conditional log-likelihood of each variable given the rest. The parameters have a natural group structure, and sparsity in the fitted graph is attained by incorporating a group lasso penalty, approximated by a weighted lasso penalty for computational efficiency. We demonstrate the effectiveness of our method through an extensive simulation study and apply it to a music annotation dataset (CAL500), obtaining a sparse and interpretable graphical model relating the continuous features of the audio signal to binary variables such as genre, emotions, and usage associated with particular songs. While we focus on binary discrete variables for the main presentation, we also show that the proposed methodology can be easily extended to general discrete variables.     

Semisupervised data classification via the Mumford–Shah–Potts-type model

More and more high dimensional data are widely used in many real world applications. This kind of data are obtained from different feature extractors, which represent distinct perspectives of the data. How to classify such data efficiently is a challenge. Despite of existence of millions of unlabeled data samples, it is believed that labeling a handful of data such as the semisupervised scheme will remarkably improve the searching performance. However, the performance of semisupervised data classification highly relies on proposed models and related numerical methods. Following from the extension of the Mumford–Shah–Potts-type model in the spatially continuous setting, we propose some efficient data classification algorithms based on the alternating direction method of multipliers and the primal-dual method to efficiently deal with the nonsmoothing problem in the proposed model. The convergence of the proposed data classification algorithms is established under the framework of variational inequalities. Some balanced and unbalanced classification problems are tested, which demonstrate the efficiency of the proposed algorithms.     

Qualitative inequalities for squared partial correlations of a Gaussian random vector

We describe various sets of conditional independence relationships, sufficient for qualitatively comparing non-vanishing squared partial correlations of a Gaussian random vector. These sufficient conditions are satisfied by several graphical Markov models. Rules for comparing degree of association among the vertices of such Gaussian graphical models are also developed. We apply these rules to compare conditional dependencies on Gaussian trees. In particular for trees, we show that such dependence can be completely characterised by the length of the paths joining the dependent vertices to each other and to the vertices conditioned on. We also apply our results to postulate rules for model selection for polytree models. Our rules apply to mutual information of Gaussian random vectors as well.     

Sparse graphical models for exploring gene expression data

We discuss the theoretical structure and constructive methodology for large-scale graphical models, motivated by their potential in evaluating and aiding the exploration of patterns of association in gene expression data. The theoretical discussion covers basic ideas and connections between Gaussian graphical models, dependency networks and specific classes of directed acyclic graphs we refer to as compositional networks. We describe a constructive approach to generating interesting graphical models for very high-dimensional distributions that builds on the relationships between these various stylized graphical representations. Issues of consistency of models and priors across dimension are key. The resulting methods are of value in evaluating patterns of association in large-scale gene expression data with a view to generating biological insights about genes related to a known molecular pathway or set of specified genes. Some initial examples relate to the estrogen receptor pathway in breast cancer, and the Rb-E2F cell proliferation control pathway.     

Divide-and-Conquer With Sequential Monte Carlo

We propose a novel class of Sequential Monte Carlo (SMC) algorithms, appropriate for inference in probabilistic graphical models. This class of algorithms adopts a divide-and-conquer approach based upon an auxiliary tree-structured decomposition of the model of interest, turning the overall inferential task into a collection of recursively solved subproblems. The proposed method is applicable to a broad class of probabilistic graphical models, including models with loops. Unlike a standard SMC sampler, the proposed divide-and-conquer SMC employs multiple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this approach can outperform standard methods in terms of the accuracy of the posterior expectation and marginal likelihood approximations. Divide-and-conquer SMC also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging subproblems. We demonstrate its performance on a Markov random field and on a hierarchical logistic regression problem. Supplementary materials including proofs and additional numerical results are available online.     

Characterizations of pseudo-codewords of (low-density) parity-check codes

An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph.     

LTC: A latent tree approach to classification

Latent tree models were proposed as a class of models for unsupervised learning, and have been applied to various problems such as clustering and density estimation. In this paper, we study the usefulness of latent tree models in another paradigm, namely supervised learning. We propose a novel generative classifier called latent tree classifier (LTC). An LTC represents each class-conditional distribution of attributes using a latent tree model, and uses Bayes rule to make prediction. Latent tree models can capture complex relationship among attributes. Therefore, LTC is able to approximate the true distribution behind data well and thus achieves good classification accuracy. We present an algorithm for learning LTC and empirically evaluate it on an extensive collection of UCI data. The results show that LTC compares favorably to the state-of-the-art in terms of classification accuracy. We also demonstrate that LTC can reveal underlying concepts and discover interesting subgroups within each class.     

无线通信中的最优资源分配―复杂性分析与算法设计

最优资源分配问题是无线通信系统设计中的基本问题之一.最优地分配功率、传输波形和频谱等资源能够极大地提高整个通信系统的传输性能.目前,相对于通信技术在现实生活中的蓬勃发展,通信系统优化的数学理论和方法显得相对滞后,在某些方面已经成为影响其发展和应用的关键因素.无线通信中的最优资源分配问题常常可建模为带有特殊结构的非凸非线性约束优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,如隐含的凸性和可分结构等.本文着重考虑多用户干扰信道中物理层资源最优分配问题的复杂性刻画,以及如何利用问题的特殊结构设计有效且满足分布式应用等实际要求的计算方法.     

Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks

In this paper, we consider the duty scheduling of sensor activities in wireless sensor networks to maximize the lifetime. We address full target coverage problems contemplating sensors used for sensing data and transmit it to the base station through multi-hop communication as well as sensors used only for communication purposes. Subsets of sensors (also called covers) are generated. Those covers are able to satisfy the coverage requirements as well as the connection to the base station. Thus, maximum lifetime can be obtained by identifying the optimal covers and allocate them an operation time. The problem is solved through a column generation approach decomposed in a master problem used to allocate the optimal time interval during which covers are used and in a pricing subproblem used to identify the covers leading to maximum lifetime. Additionally, Branch-and-Cut based on Benders’ decomposition and constraint programming approaches are used to solve the pricing subproblem. The approach is tested on randomly generated instances. The computational results demonstrate the efficiency of the proposed approach to solve the maximum network lifetime problem in wireless sensor networks with up to 500 sensors.     

Fast algorithm for singly linearly constrained quadratic programs with box-like constraints

This paper focuses on a singly linearly constrained class of convex quadratic programs with box-like constraints. We propose a new fast algorithm based on parametric approach and secant approximation method to solve this class of quadratic problems. We design efficient implementations for our proposed algorithm and compare its performance with two state-of-the-art standard solvers called Gurobi and Mosek. Numerical results on a variety of test problems demonstrate that our algorithm is able to efficiently solve the large-scale problems with the dimension up to fifty million and it substantially outperforms Gurobi and Mosek in terms of the running time.     

A framework of distributed indexing and data dissemination in large scale wireless sensor networks

Many data dissemination techniques have been proposed for wireless sensor networks (WSNs) to facilitate data dissemination and query processing. However, these techniques may not work well in a large scale sensor network where a huge amount of sensing data is generated. In this paper, we propose an integrated distributed connected dominating set based indexing (CBI) data dissemination scheme to support scalable handling of large amount of sensing data in large scale WSNs. Our CBI can minimize the use of limited network and computational resources while providing timely responses to queries. Moreover, our data dissemination framework ensures scalability and load balance as well as adaptivity in the presence of dynamic changes. Analysis and simulations are conducted to evaluate the performance of our CBI scheme. The results show that the CBI scheme outperforms the external storage-based scheme, local storage-based scheme and the data-centric storage-based scheme in overall performance.     

A Heuristic Procedure for Leasing Channels in Telecommunications Networks

Rapid advances in computing and communications technology have made distributed computing an attractive alternative for geographically dispersed organizations. A telecommunication sub-network forms the backbone of these distributed systems. In general, this paper focuses on the assignment of communication channel capacities in the presence of time variant usage patterns. Specifically, we concentrate on long-range capacity planning for organizations that construct networks by leasing communication channels from telecommunication companies. We formulate the capacity assignment problem as a 0-1 integer program that seeks to minimize total leasing cost subject to communication delay restrictions. Unlike previous models that include a single-system wide-average delay constraint, our model allows the flexibility of specifying delay restrictions by communicating node pairs. We propose an efficient heuristic, and a Lagrangian relaxation based procedure to obtain performance guarantees on the solution obtained from the heuristic.     

<Emphasis Type="Italic">Graph_sampler</Emphasis>: a simple tool for fully Bayesian analyses of DAG-models

Bayesian networks (BNs) are widely used graphical models usable to draw statistical inference about directed acyclic graphs. We presented here Graph_sampler a fast free C language software for structural inference on BNs. Graph_sampler uses a fully Bayesian approach in which the marginal likelihood of the data and prior information about the network structure are considered. This new software can handle both the continuous as well as discrete data and based on the data type two different models are formulated. The software also provides a wide variety of structure prior which can depict either the global or local properties of the graph structure. Now based on the type of structure prior selected, we considered a wide range of possible values for the prior making it either informative or uninformative. We proposed a new and much faster jumping kernel strategy in the Metropolis–Hastings algorithm. The source C code distributed is very compact, fast, uses low memory and disk storage. We performed out several analyses based on different simulated data sets and synthetic as well as real networks to discuss the performance of Graph_sampler.