Distributed evolutionary Monte Carlo for Bayesian computing

Sampling from a multimodal and high-dimensional target distribution posits a great challenge in Bayesian analysis. A new Markov chain Monte Carlo algorithm Distributed Evolutionary Monte Carlo (DGMC) is proposed for real-valued problems, which combines the attractive features of the distributed genetic algorithm and the Markov chain Monte Carlo. The DGMC algorithm evolves a population of Markov chains through some genetic operators to simulate the target function. Theoretical justification proves that the DGMC algorithm has the target function as its stationary distribution. The effectiveness of the DGMC algorithm is illustrated by simulating two multimodal distributions and an application to a real data example.     

A note on the attractor-property of infinite-state Markov chains

In the past 5 years, a series of verification algorithms has been proposed for infinite Markov chains that have a finite attractor, i.e., a set that will be visited infinitely often almost surely starting from any state. In this paper, we establish a sufficient criterion for the existence of an attractor. We show that if the states of a Markov chain can be given levels (positive integers) such that the expected next level for states at some level n>0 is less than n−Δ for some positive Δ, then the states at level 0 constitute an attractor for the chain. As an application, we obtain a direct proof that some probabilistic channel systems combining message losses with duplication and insertion errors have a finite attractor.     

Stochastic adaptive sampling for mobile sensor networks using kernel regression

In this paper, we provide a stochastic adaptive sampling strategy for mobile sensor networks to estimate scalar fields over surveillance regions using kernel regression, which does not require a priori statistical knowledge of the field. Our approach builds on a Markov Chain Monte Carlo (MCMC) algorithm, viz., the fastest mixing Markov chain under a quantized finite state space, for generating the optimal sampling probability distribution asymptotically. The proposed adaptive sampling algorithm for multiple mobile sensors is numerically evaluated under scalar fields. The comparison simulation study with a random walk benchmark strategy demonstrates the excellent performance of the proposed scheme.     

Probably correct k-nearest neighbor search in high dimensions

A novel approach for k-nearest neighbor (k-NN) searching with Euclidean metric is described. It is well known that many sophisticated algorithms cannot beat the brute-force algorithm when the dimensionality is high. In this study, a probably correct approach, in which the correct set of k-nearest neighbors is obtained in high probability, is proposed for greatly reducing the searching time. We exploit the marginal distribution of the k th nearest neighbors in low dimensions, which is estimated from the stored data (an empirical percentile approach). We analyze the basic nature of the marginal distribution and show the advantage of the implemented algorithm, which is a probabilistic variant of the partial distance searching. Its query time is sublinear in data size n, that is, O(mnδ) with δ=o(1) in n and δ≤1, for any fixed dimension m.     

Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems

Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm.     

Reachability problems for Markov chains

We consider the following decision problem: given a finite Markov chain with distinguished source and target states, and given a rational number r, does there exist an integer n such that the probability to reach the target from the source in n steps is r? This problem, which is not known to be decidable, lies at the heart of many model checking questions on Markov chains. We provide evidence of the hardness of the problem by giving a reduction from the Skolem Problem: a number-theoretic decision problem whose decidability has been open for many decades.     

Perfect sampling for closed queueing networks

In this paper we investigate coupling from the past (CFTP) algorithms for closed queueing networks. The stationary distribution has a product form only in a very limited number of particular cases when queue capacity is finite, and numerical algorithms are intractable due to the cardinality of the state space. Moreover, closed networks do not exhibit any monotonic property enabling efficient CFTP. We derive a bounding chain for the CFTP algorithm for closed queueing networks. This bounding chain is based on a compact representation of sets of states that enables exact sampling from the stationary distribution without considering all initial conditions in the CFTP. The coupling time of the bounding chain is almost surely finite, and numerical experiments show that it is close to the coupling time of the exact chain.     

Monte Carlo TD(λ)-methods for the optimal control of discrete-time Markovian jump linear systems

In this paper, we present an iterative technique based on Monte Carlo simulations for deriving the optimal control of the infinite horizon linear regulator problem of discrete-time Markovian jump linear systems for the case in which the transition probability matrix of the Markov chain is not known. We trace a parallel with the theory of TD(λ) algorithms for Markovian decision processes to develop a TD(λ) like algorithm for the optimal control associated to the maximal solution of a set of coupled algebraic Riccati equations (CARE). It is assumed that either there is a sample of past observations of the Markov chain that can be used for the iterative algorithm, or it can be generated through a computer program. Our proofs rely on the spectral radius of the closed loop operators associated to the mean square stability of the system being less than 1.     

EM algorithms for nonlinear mixed effects models

Implementing the Monte Carlo EM algorithm (MCEM) algorithm for finding maximum likelihood estimates (MLEs) in the nonlinear mixed effects model (NLMM) has encountered a great deal of difficulty in obtaining samples used for estimating the E step due to the intractability of the target distribution. Sampling methods such as Markov chain techniques and importance sampling have been used to alleviate such difficulty. The advantage of Markov chains is that they are applicable to a wider range of distributions than the approaches based on independent samples. However, in many cases the computational cost of Markov chains is significantly greater than that of independent samplers. The MCEM algorithms based on independent samples allow for straightforward assessment of Monte Carlo error and can be considerably more efficient than those based on Markov chains when an efficient candidate distribution is chosen, which forms the motivation of this paper. The proposed MCEM algorithm in this paper uses samples obtained from an easy-to-simulate and efficient importance distribution so that the computational intensity and complexity is much reduced. Moreover, the proposed MCEM algorithm preserves the flexibility introduced by independent samples in gauging Monte Carlo error and thus allows the Monte Carlo sample size to increase with the number of EM iterations. We also introduce an EM algorithm using Gaussian quadrature approximations (GQEM) for the E step. In low-dimensional cases, the GQEM algorithm is more efficient than the proposed MCEM algorithm and thus can be used as an alternative. The performances of the proposed EM methods are compared to the existing ML estimators using real data examples and simulations.     

A recursive algorithm for the reliability of a circular connected-(r,s)-out-of-(m,n):F lattice system

A circular connected-(r, s)-out-of-(m, n):F lattice system consists of m×n components arranged in a cylindrical grid. Each of m circles has n components, and this system fails if and only if there exists a grid of size r ×s which all components are failed. A circular connected-(r, s)-out-of-(m, n):F lattice system might be used in reliability models for ‘Feelers for measuring temperature on reaction chamber’ and ‘TFT Liquid Crystal Display system with 360° wide area’.In this study, we proposed a new recursive algorithm for obtaining the reliability of a circular connected-(r, s)-out-of-(m, n):F lattice system. We evaluated our proposed algorithms in terms of computing time and memory capacity. Furthermore, a numerical experiment comparing our proposed algorithm with Yamamoto and Miyakawa's algorithm [Yamamoto, H., & Miyakawa, M. (1996). Reliability of circular connected-(r, s)-out-of-(m, n):F lattice system. Journal of the Operations Research Society of Japan, 39(3), 389–406] showed that our proposed algorithm is more effective for systems with a large n.     

A variational Bayesian methodology for hidden Markov models utilizing Student's-t mixtures

The Student's-t hidden Markov model (SHMM) has been recently proposed as a robust to outliers form of conventional continuous density hidden Markov models, trained by means of the expectation-maximization algorithm. In this paper, we derive a tractable variational Bayesian inference algorithm for this model. Our innovative approach provides an efficient and more robust alternative to EM-based methods, tackling their singularity and overfitting proneness, while allowing for the automatic determination of the optimal model size without cross-validation. We highlight the superiority of the proposed model over the competition using synthetic and real data. We also demonstrate the merits of our methodology in applications from diverse research fields, such as human computer interaction, robotics and semantic audio analysis.     

Estimation and Approximation Bounds for Gradient-Based Reinforcement Learning

We model reinforcement learning as the problem of learning to control a partially observable Markov decision process (POMDP) and focus on gradient ascent approaches to this problem. In an earlier work (2001, J. Artificial Intelligence Res.14) we introduced GPOMDP, an algorithm for estimating the performance gradient of a POMDP from a single sample path, and we proved that this algorithm almost surely converges to an approximation to the gradient. In this paper, we provide a convergence rate for the estimates produced by GPOMDP and give an improved bound on the approximation error of these estimates. Both of these bounds are in terms of mixing times of the POMDP.     

Approximation schemes for load balanced clustering in wireless sensor networks

Clustering sensor nodes is an efficient technique to improve scalability and life time of a wireless sensor network (WSN). However, in a cluster based WSN, the leaders (cluster heads) consume more energy due to some extra load for various activities such as data collection, data aggregation, and communication of the aggregated data to the base station. Therefore, balancing the load of the cluster heads is a crucial issue for the long run operation of the WSNs. In this paper, we first present a load balanced clustering scheme for wireless sensor networks. We show that the algorithm runs in O(nlogn) time for n sensor nodes. We prove that the algorithm is optimal for the case in which the sensor nodes have equal load. We also show that it is a polynomial time 2-approximation algorithm for the general case, i.e., when the sensor nodes have variable load. We finally improve this algorithm and propose a 1.5-approximation algorithm for the general case. The experimental results show the efficiency of the proposed algorithm in terms of the load balancing of the cluster heads, execution time, and the network life.     

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives

We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes $O(n \cdot\sqrt{m})$ symbolic steps as compared to the previous known algorithm that takes O(n ²) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes $O(n \cdot\sqrt{n})$ symbolic steps, as compared to the previous known O(n ²) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires $O(n \cdot\sqrt{K})$ symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5?n symbolic steps, whereas our new algorithm takes 4?n symbolic steps.     

Generalized darting Monte Carlo

One of the main shortcomings of Markov chain Monte Carlo samplers is their inability to mix between modes of the target distribution. In this paper we show that advance knowledge of the location of these modes can be incorporated into the MCMC sampler by introducing mode-hopping moves that satisfy detailed balance. The proposed sampling algorithm explores local mode structure through local MCMC moves (e.g. diffusion or Hybrid Monte Carlo) but in addition also represents the relative strengths of the different modes correctly using a set of global moves. This ‘mode-hopping’ MCMC sampler can be viewed as a generalization of the darting method [1]. We illustrate the method on learning Markov random fields and evaluate it against the spherical darting algorithm on a ‘real world’ vision application of inferring 3D human body pose distributions from 2D image information.     

How to sample from a truncated distribution if you must

Sampling from a truncated distribution is difficult. There are currently two major methods proposed for solving this task. The first proposed solution is a random-walk MCMC algorithm. Although it eventually gives the correct distribution, it can be very slow in multi-modal distributions. The second approach called the ellipsoid method is practically more efficient for problems in which users have good prior information, but a correctness is not guaranteed. In this paper, we present a framework which can unify these two approaches. The key idea is to merge both methods into a single Markov chain using a trick called Metropolis-coupled MCMC. Once merged, they can validly exchange information to each other. Although the chain constructed from the ellipsoid approach cannot be proven to be correct, it usually rapidly converges to a useful stationary distribution, and its information can help the other chain constructed by the random-walk approach to converge faster to the correct distribution.     

A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time Θ(n logn). We present a bidirectional search algorithm that has expected running time Θ(√n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time Θ(a√n) on graphs of average degreea, as compared with Θ(an) for unidirectional search.     

A branch and price algorithm for the SS/TDMA problem with cardinality constraint

In this paper, we consider a square n×n traffic matrix D   and a satellite having l≤n$l\le n$ receiving and transmitting antennas. Transmissions are allowed by interconnecting pairs of receiving–transmitting antennas, through an on-board switch. We also assume that no preemption of the communications is allowed, and that changing the configuration of the switch requires a negligible time. We ask for a set of switch configurations that minimizes the total time occurring for transmitting the entire traffic matrix. In the literature, an exact method has been already proposed for the SS/TDMA optimization problem without cardinality constraint (i.e. for instances having l=n), but only heuristics have been proposed for the general case. In this paper, from a known MILP formulation we derive an extended formulation, and we use a column generation method to obtain its LP-relaxation. We address the derived pricing problem through a polynomial time algorithm based on solvers for the k-cardinality assignment problem. We insert this lower bound method in a two-phase branch and price algorithm in order to obtain the optimal solutions. To compare our new exact method with the one proposed in literature to solve the SS/TDMA optimization problem without cardinality constraint, we extend this older method to consider the cardinality constraint. The final computational experiments, comparing our new method with other already known methods, show the efficiency of our algorithms.     

A linear time algorithm for max-min length triangulation of a convex polygon

We consider the following planar max-min length triangulation problem: given a set of n points in the Euclidean plane, find a triangulation such that the length of the shortest edge in the triangulation is maximized. In this paper, a linear time algorithm is proposed for computing the max-min length triangulation of a set of points in convex position. In addition, an O(nlogn) time algorithm is proposed for computing the max-min length k-set triangulation of a set of points in convex position, where we are to compute a set of k vertices such that the max-min length triangulation on them is minimized over all possible k-set. We further show that the graph version of max-min length triangulation is NP-complete, and some common heuristics such as greedy algorithm are in general not able to give a bounded-ratio approximation to the max-min length triangulation.     

A Distributed Algorithm for Computing the Node Search Number in Trees

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50–79, 1994). It can be executed in an asynchronous environment, requires an overall computation time of O(nlog?n), and n messages of log?₃ n+4 bits each. The main contribution of this work lies in the data structure proposed to design our algorithm, called hierarchical decomposition. This simple and flexible data structure is used for four operations: updating the node search number after addition or deletion of any tree-edges in a distributed fashion; computing it in a tree whose edges are added sequentially and in any order; computing other graph invariants such as the process number and the edge search number, by changing only initialization rules; extending our algorithms for trees and forests of unknown size (using messages of up to 2log?₃ n+5 bits).