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.     

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.      

Monte Carlo Methods for Volumetric Light Transport Simulation

The wide adoption of path‐tracing algorithms in high‐end realistic rendering has stimulated many diverse research initiatives. In this paper we present a coherent survey of methods that utilize Monte Carlo integration for estimating light transport in scenes containing participating media. Our work complements the volume‐rendering state‐of‐the‐art report by Cerezo et al. [ CPP*05 ]; we review publications accumulated since its publication over a decade ago, and include earlier methods that are key for building light transport paths in a stochastic manner. We begin by describing analog and non‐analog procedures for free‐path sampling and discuss various expected‐value, collision, and track‐length estimators for computing transmittance. We then review the various rendering algorithms that employ these as building blocks for path sampling. Special attention is devoted to null‐collision methods that utilize fictitious matter to handle spatially varying densities; we import two “next‐flight” estimators originally developed in nuclear sciences. Whenever possible, we draw connections between image‐synthesis techniques and methods from particle physics and neutron transport to provide the reader with a broader context.     

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 模型定阶方法,仿真结果表明该方法可行有效.     

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.     

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.     

Parallel and interacting Markov chain Monte Carlo algorithm

In many situations it is important to be able to propose N independent realizations of a given distribution law. We propose a strategy for making N parallel Monte Carlo Markov chains (MCMC) interact in order to get an approximation of an independent N-sample of a given target law. In this method each individual chain proposes candidates for all other chains. We prove that the set of interacting chains is itself a MCMC method for the product of N target measures. Compared to independent parallel chains this method is more time consuming, but we show through examples that it possesses many advantages. This approach is applied to a biomass evolution model.     

Parallel and interacting Markov chain Monte Carlo algorithm

In many situations it is important to be able to propose N independent realizations of a given distribution law. We propose a strategy for making N parallel Monte Carlo Markov chains (MCMC) interact in order to get an approximation of an independent N-sample of a given target law. In this method each individual chain proposes candidates for all other chains. We prove that the set of interacting chains is itself a MCMC method for the product of N target measures. Compared to independent parallel chains this method is more time consuming, but we show through examples that it possesses many advantages. This approach is applied to a biomass evolution model.     

Markov chain Monte Carlo based video tracking algorithm

The paper considers a problem of multiple person tracking. We present the algorithm to automatic people tracking on surveillance videos recorded by static cameras. Proposed algorithm is an extension of approach based on tracking-by-detection of people heads and data association using Markov chain Monte Carlo (MCMC). Short track fragments (tracklets) are built by local tracking of people heads. Tracklet postprocessing and accurate results interpolation were shown to reduce number of false positives. We use position deviations of tracklets and revised entry/exit points factor to separate pedestrians from false positives. The paper presents a new method to estimate body position, that increases precision of tracker. Finally, we switched HOG-based detector to cascade one. Our evaluation shows proposed modifications significantly increase tracking quality.