Population Markov Chain Monte Carlo

Stochastic search algorithms inspired by physical and biological systems are applied to the problem of learning directed graphical probability models in the presence of missing observations and hidden variables. For this class of problems, deterministic search algorithms tend to halt at local optima, requiring random restarts to obtain solutions of acceptable quality. We compare three stochastic search algorithms: a Metropolis-Hastings Sampler (MHS), an Evolutionary Algorithm (EA), and a new hybrid algorithm called Population Markov Chain Monte Carlo, or popMCMC. PopMCMC uses statistical information from a population of MHSs to inform the proposal distributions for individual samplers in the population. Experimental results show that popMCMC and EAs learn more efficiently than the MHS with no information exchange. Populations of MCMC samplers exhibit more diversity than populations evolving according to EAs not satisfying physics-inspired local reversibility conditions.     

Markov Chain Monte Carlo Modular Ensemble Tracking

Recent years have been characterized by the overgrowth of video-surveillance systems and by automation of the processing they integrate. Object Tracking has become a recurrent problem in video-surveillance and is a very important domain in computer vision. It was recently approached using classification techniques and still more recently using boosting methods.We propose in this paper a new machine learning based strategy to build the observation model of tracking systems. The global observation function results of a linear combination of several simplest observation functions so-called modules (one per visual cue). Each module is built using a Adaboost-like algorithm, derived from the Ensemble Tracking Algorithm. The importance of each module is estimated using an original probabilistic sequential filtering framework with a joint state model composed by both the spatial object parameters and the importance parameters of the observation modules.Our system is tested on challenging sequences which prove its performance for tracking and scaling on fix and mobile cameras and we compare the robustness of our algorithm with the state of the art.     

Stratified Markov Chain Monte Carlo Light Transport

Markov chain Monte Carlo (MCMC) sampling is a powerful approach to generate samples from an arbitrary distribution. The application to light transport simulation allows us to efficiently handle complex light transport such as highly occluded scenes. Since light transport paths in MCMC methods are sampled according to the path contributions over the sampling domain covering the whole image, bright pixels receive more samples than dark pixels to represent differences in the brightness. This variation in the number of samples per pixel is a fundamental property of MCMC methods. This property often leads to uneven convergence over the image, which is a notorious and fundamental issue of any MCMC method to date. We present a novel stratification method of MCMC light transport methods. Our stratification method, for the first time, breaks the fundamental limitation that the number of samples per pixel is uncontrollable. Our method guarantees that every pixel receives a specified number of samples by running a single Markov chain per pixel. We rely on the fact that different MCMC processes should converge to the same result when the sampling domain and the integrand are the same. We thus subdivide an image into multiple overlapping tiles associated with each pixel, run an independent MCMC process in each of them, and then align all of the tiles such that overlapping regions match. This can be formulated as an optimization problem similar to the reconstruction step for gradient-domain rendering. Further, our method can exploit the coherency of integrands among neighboring pixels via coherent Markov chains and replica exchange. Images rendered with our method exhibit much more predictable convergence compared to existing MCMC methods.     

Calibration of cellular automata urban growth models from urban genesis onwards - a novel application of Markov chain Monte Carlo approximate Bayesian computation

Cellular Automata (CA) models are widely used to study spatial dynamics of urban growth and evolving patterns of land use. One complication across CA approaches is the relatively short period of data available for calibration, providing sparse information on patterns of change and presenting problematic signal-to-noise ratios. To overcome the problem of short-term calibration, this study investigates a novel approach in which the model is calibrated based on the urban morphological patterns that emerge from a simulation starting from urban genesis, i.e., a land cover map completely void of urban land. The application of the model uses the calibrated parameters to simulate urban growth forward in time from a known urban configuration.This approach to calibration is embedded in a new framework for the calibration and validation of a Constrained Cellular Automata (CCA) model of urban growth. The investigated model uses just four parameters to reflect processes of spatial agglomeration and preservation of scarce non-urban land at multiple spatial scales and makes no use of ancillary layers such as zoning, accessibility, and physical suitability. As there are no anchor points that guide urban growth to specific locations, the parameter estimation uses a goodness-of-fit (GOF) measure that compares the built density distribution inspired by the literature on fractal urban form. The model calibration is a novel application of Markov Chain Monte Carlo Approximate Bayesian Computation (MCMC-ABC). This method provides an empirical distribution of parameter values that reflects model uncertainty. The validation uses multiple samples from the estimated parameters to quantify the propagation of model uncertainty to the validation measures.The framework is applied to two UK towns (Oxford and Swindon). The results, including cross-application of parameters, show that the models effectively capture the different urban growth patterns of both towns. For Oxford, the CCA correctly produces the pattern of scattered growth in the periphery, and for Swindon, the pattern of compact, concentric growth. The ability to identify different modes of growth has both a theoretical and practical significance. Existing land use patterns can be an important indicator of future trajectories. Planners can be provided with insight in alternative future trajectories, available decision space, and the cumulative effect of parcel-by-parcel planning decisions.     

Markov Chain Monte Carlo for Automated Face Image Analysis

We present a novel fully probabilistic method to interpret a single face image with the 3D Morphable Model. The new method is based on Bayesian inference and makes use of unreliable image-based information. Rather than searching a single optimal solution, we infer the posterior distribution of the model parameters given the target image. The method is a stochastic sampling algorithm with a propose-and-verify architecture based on the Metropolis–Hastings algorithm. The stochastic method can robustly integrate unreliable information and therefore does not rely on feed-forward initialization. The integrative concept is based on two ideas, a separation of proposal moves and their verification with the model (Data-Driven Markov Chain Monte Carlo), and filtering with the Metropolis acceptance rule. It does not need gradients and is less prone to local optima than standard fitters. We also introduce a new collective likelihood which models the average difference between the model and the target image rather than individual pixel differences. The average value shows a natural tendency towards a normal distribution, even when the individual pixel-wise difference is not Gaussian. We employ the new fitting method to calculate posterior models of 3D face reconstructions from single real-world images. A direct application of the algorithm with the 3D Morphable Model leads us to a fully automatic face recognition system with competitive performance on the Multi-PIE database without any database adaptation.     

Markov Chain Monte Carlo Data Association for Multi-Target Tracking

This paper presents Markov chain Monte Carlo data association (MCMCDA) for solving data association problems arising in multi-target tracking in a cluttered environment. When the number of targets is fixed, the single-scan version of MCMCDA approximates joint probabilistic data association (JPDA). Although the exact computation of association probabilities in JPDA is NP-hard, we prove that the single-scan MCMCDA algorithm provides a fully polynomial randomized approximation scheme for JPDA. For general multi-target tracking problems, in which unknown numbers of targets appear and disappear at random times, we present a multi-scan MCMCDA algorithm that approximates the optimal Bayesian filter. We also present extensive simulation studies supporting theoretical results in this paper. Our simulation results also show that MCMCDA outperforms multiple hypothesis tracking (MHT) by a significant margin in terms of accuracy and efficiency under extreme conditions, such as a large number of targets in a dense environment, low detection probabilities, and high false alarm rates.      

Robust particle tracker via Markov Chain Monte Carlo posterior sampling

Particle Filter has grown to be a standard framework for visual tracking. This paper proposes a robust particle tracker based on Markov Chain Monte Carlo method, aiming at solving the thorny problems in visual tracking induced by object appearance changes, occlusions, background clutter, and abrupt motions. In this algorithm, we derive the posterior probability density function based on second order Markov assumption. The posterior probability density is the joint density of the previous two states. Additionally, a Markov Chain with certain length is used to approximate the posterior density to avoid the drawbacks of traditional importance sampling based algorithm, which consequently improves the searching ability of the proposed tracker. We compare our approach with several alternative tracking algorithms, and the experimental results demonstrate that our tracker is superior to others in dealing with various types of challenging scenarios.     

Multiple-Target Tracking by Spatiotemporal Monte Carlo Markov Chain Data Association

We propose a framework for tracking multiple targets, where the input is a set of candidate regions in each frame, as obtained from a state-of-the-art background segmentation module, and the goal is to recover trajectories of targets over time. Due to occlusions by targets and static objects, as also by noisy segmentation and false alarms, one foreground region may not correspond to one target faithfully. Therefore, the one-to-one assumption used in most data association algorithms is not always satisfied. Our method overcomes the one-to-one assumption by formulating the visual tracking problem in terms of finding the best spatial and temporal association of observations, which maximizes the consistency of both motion and appearance of trajectories. To avoid enumerating all possible solutions, we take a data-driven Markov Chain Monte Carlo (DD-MCMC) approach to sample the solution space efficiently. The sampling is driven by an informed proposal scheme controlled by a joint probability model combining motion and appearance. Comparative experiments with quantitative evaluations are provided.     

Improving Markov Chain Monte Carlo Model Search for Data Mining

The motivation of this paper is the application of MCMC model scoring procedures to data mining problems, involving a large number of competing models and other relevant model choice aspects.To achieve this aim we analyze one of the most popular Markov Chain Monte Carlo methods for structural learning in graphical models, namely, the MC ³ algorithm proposed by D. Madigan and J. York (International Statistical Review, 63, 215–232, 1995). Our aim is to improve their algorithm to make it an effective and reliable tool in the field of data mining. In such context, typically highly dimensional in the number of variables, little can be known a priori and, therefore, a good model search algorithm is crucial.We present and describe in detail our implementation of the MC ³ algorithm, which provides an efficient general framework for computations with both Directed Acyclic Graphical (DAG) models and Undirected Decomposable Models (UDG). We believe that the possibility of commuting easily between the two classes of models constitutes an important asset in data mining, where an a priori knowledge of causal effects is usually difficult to establish.Furthermore, in order to improve the MC ³ method we propose provide several graphical monitors which can help extracting results and assessing the goodness of the Markov chain Monte Carlo approximation to the posterior distribution of interest.We apply our proposed methodology first to the well-known coronary heart disease dataset (D. Edwards &; T. Havránek, Biometrika, 72:2, 339–351, 1985). We then introduce a novel data mining application which concerns market basket analysis.     

基于Hamiltonian马氏链蒙特卡罗方法的突变运动跟踪

在计算机视觉领域,由镜头切换、目标动力学突变、低帧率视频等引起的突变运动存在极大的不确定性,使得突变运动跟踪成为该领域的挑战性课题.以贝叶斯滤波框架为基础,提出一种基于有序超松弛Hamiltonian马氏链蒙特卡罗方法的突变运动跟踪算法.该算法将Hamiltonian动力学融入MCMC（Markov chain Monte Carlo）算法,目标状态被扩张为原始目标状态变量与一个动量项的组合.在提议阶段,为抑制由Gibbs采样带来的随机游动行为,提出采用有序超松弛迭代方法来抽取目标动量项.同时,提出自适应步长的Hamiltonian动力学实现方法,在跟踪过程中自适应地调整步长,以减少模拟误差.提出的跟踪算法可以避免传统的基于随机游动的MCMC跟踪算法所存在的局部最优问题,提高了跟踪的准确性而不需要额外的计算时间.实验结果表明,该算法在处理多种类型的突变运动时表现出出色的处理能力.     

基于RJMCMC的视觉多目标跟踪算法

研究了基于MCMC的多目标跟踪算法。针对MCMC迭代过程中抽样置信度低以及不能进行有效迭代的问题,提出一种新的基于RJMCMC的视觉多目标跟踪算法。给定观测量,将跟踪问题建模为状态量的最大后验估计(MAP)、关于MAP的先验与似然的估计。借助匹配阵给出了目标先验建议分布,设计了4种马氏链可逆运动方式;似然度量采用随空间加权的颜色直方图匹配衡量。MCMC抽样过程中的状态由MS迭代产生,而不是随机走生成。基于似然度量导出了MS迭代式。实验结果及定量分析评估结果说明了本算法的有效性。     

Bayesian Estimation of Agent-Based Models via Adaptive Particle Markov Chain Monte Carlo

Computational Economics - Over the last decade, agent-based models in economics have reached a state of maturity that brought the tasks of statistical inference and goodness-of-fit of such models...     

Distributed Markov Chain Monte Carlo kernel based particle filtering for object tracking

Particle filters are computationally intensive and thus efficient parallelism is crucial to effective implementations, especially object tracking in video sequences. Two schemes for pipelining particles under high performance computing environment, including an alternative Markov Chain Monte Carlo (MCMC) resampling algorithm and kernel function, are proposed so as to improve tracking performance and minimize execution time. Experimental results on a network of workstations composed of simple off-the-shelf hardware components show that global parallelizable scheme provides a promising resolution to clearly reduce execution time with increasing particles, compared with generic particle filtering.     

基于可逆跳 MCMC 的 AR 模型定阶方法

由于传统的 AR 模型定阶方法在小样本情况下经常会失效,所以提出一种基于可逆跳马尔科夫蒙特卡罗(MCMC)的 AR 模型定阶方法,仿真结果表明该方法可行有效.     

Markov Chain Monte Carlo simulation for projection of end stage renal disease patients in Greece

End stage renal disease (ESRD) treatment methods are considered to be among the most expensive procedures for chronic conditions worldwide which also have severe impact on patients' quality of life. During the last decade, Greece has been among the countries with the highest incidence and prevalence, while at the same time with the lowest kidney transplantation rates. Predicting future patients' number on Renal Replacement Therapy (RRT) is essential for health care providers in order to achieve more effective resource management. In this study a Markov Chain Monte Carlo (MCMC) simulation is presented for predicting the future number of ESRD patients for the period 2009-2020 in Greece. The MCMC model comprises Monte Carlo sampling techniques applied on probability distributions of the constructed Markov Chain. The model predicts that there will be 15,147 prevalent patients on RRT in Greece by 2020. Additionally, a cost-effectiveness analysis was performed on a scenario of gradually reducing the hemodialysis patients in favor of increasing the transplantation number by 2020. The proposed scenario showed net savings of 86.54 million Euros for the period 2009-2020 compared to the base-case prediction.     

Bayesian Analysis of the Stochastic Switching Regression Model Using Markov Chain Monte Carlo Methods

This study develops Bayesian methods for estimating the parameters of astochastic switching regression model. Markov Chain Monte Carlo methods, dataaugmentation, and Gibbs sampling are used to facilitate estimation of theposterior means. The main feature of these methods is that the posterior meansare estimated by the ergodic averages of samples drawn from conditionaldistributions, which are relatively simple in form and more feasible to samplefrom than the complex joint posterior distribution. A simulation study isconducted comparing model estimates obtained using data augmentation, Gibbssampling, and the maximum likelihood EM algorithm and determining the effectsof the accuracy of and bias of the researcher's prior distributions on theparameter estimates.     

Bayesian identification of a cracked plate using a population-based Markov Chain Monte Carlo method

Estimating damage in structural systems is a challenging problem due to the complexity of the likelihood function describing the observed data. From a Bayesian perspective a complicated likelihood means efficient sampling of the posterior distribution is difficult and standard Markov Chain Monte Carlo samplers may no longer be sufficient. This work describes a population-based Markov Chain Monte Carlo approach for efficient sampling of the damage parameter posterior distributions. The approach is shown to accurately estimate the state of damage in a cracked plate structure using simulated, free-decay response data. The use of this approach in identifying structural damage has not previously been explored.     

Bayesian parameter inference for individual-based models using a Particle Markov Chain Monte Carlo method

Parameter estimation for agent-based and individual-based models (ABMs/IBMs) is often performed by manual tuning and model uncertainty assessment is often ignored. Bayesian inference can jointly address these issues. However, due to high computational requirements of these models and technical difficulties in applying Bayesian inference to stochastic models, the exploration of its application to ABMs/IBMs has just started. We demonstrate the feasibility of Bayesian inference for ABMs/IBMs with a Particle Markov Chain Monte Carlo (PMCMC) algorithm developed for state-space models. The algorithm profits from the model's hidden Markov structure by jointly estimating system states and the marginal likelihood of the parameters using time-series observations. The PMCMC algorithm performed well when tested on a simple predator-prey IBM using artificial observation data. Hence, it offers the possibility for Bayesian inference for ABMs/IBMs. This can yield additional insights into model behaviour and uncertainty and extend the usefulness of ABMs/IBMs in ecological and environmental research.     

Using Markov Chain Monte Carlo to quantify parameter uncertainty and its effect on predictions of a groundwater flow model

A statistical Bayesian framework is used to solve the inverse problem and develop the posterior distributions of parameters for a density-driven groundwater flow model. This Bayesian approach is implemented using a Markov Chain Monte Carlo (MCMC) sampling method. Three sets of data pertaining to the location of the freshwater–seawater transition zone exist for the site, including chemistry data, hydraulic head data and newly collected magnetotelluric (MT) data. A sequential conditioning approach is implemented where the chemistry data and MT-converted salinity are combined as a single data set and are used to first condition the parameter distributions. The head data are subsequently used as a second conditioning data set where the posterior distribution developed by the first conditioning is used as a prior for this second conditioning. Results of this analysis indicate that conditioning on the available data sets yields dramatic reduction of uncertainty compared to unconditioned simulations, especially for the recharge–conductivity ratio. This ratio controls the location of the transition zone, and the conditioning results in a smaller range of variability compared to the distribution used in previous modelling of the site. Using the conditioned distributions to solve the density-driven flow problem in a stochastic framework (i.e., model parameters are randomly sampled from the posterior distributions) results in a range of output flow fields that is much narrower than the previous model. The ensemble mean of these solutions and the uncertainty bounds expressed by the mean ± one standard deviation lie within the uncertainty bounds of the original model. For the case study shown here, the effect of conditioning data is dominant over the effect of prior information.     

基于贝叶斯和蒙特卡罗的多信号模型扩展研究

传统多信号模型基于确定性测试假设条件,忽略了系统存在不确定性的真实情况,在传统多信号模型基础上引入贝叶斯条件概率来表示不确定性问题,并通过蒙特卡罗方法进行仿真模拟,将不确定性问题转化为单次试验确定性问题,进而使用相关矩阵进行测试性分析,通过程序实现和算例验证了该方法的有效性,并可以根据反馈数据进行参数学习,修正初始条件概率。