马尔可夫链蒙特卡洛重要度采样与多目标跟踪

针对强杂波环境下的多目标跟踪问题,提出一种基于马尔可夫链蒙特卡洛重要度采样的跟踪方法．通过马尔可夫链蒙特卡洛实现对联合关联事件的采样,据此计算目标可关联量测数据的边缘关联概率．在联合关联事件求解中利用单目标量测的概率密度进行重要度采样,提高采样效率．马尔可夫链蒙特卡洛重要度采样方法克服了联合概率数据关联中的“组合爆炸”问题,能够在强杂波干扰下较好地实现多目标实时跟踪．通过仿真实验对比分析了算法的跟踪精度和处理的时效性,验证了方法的有效性．     

不确定控制系统概率鲁棒性分析——自适应重要抽样法

将自适应重要抽样(AIS)法应用于不确定控制系统的概率鲁棒性分析问题,克服了标准MonteCarlo仿真(MCS)方法不能有效解决小概率事件的困难.给出了一种新的AIS方案.首先采用了一种递归的估计条件众数算法来产生一组使得系统不稳定或性能不可接受的不确定参数向量样本.然后利用这组样本来估计初始高斯型重要抽样密度函数的参数,并执行随后的迭代仿真过程.仿真结果验证了该方法的有效性.     

Iterated importance sampling in missing data problems

Missing variable models are typical benchmarks for new computational techniques in that the ill-posed nature of missing variable models offer a challenging testing ground for these techniques. This was the case for the EM algorithm and the Gibbs sampler, and this is also true for importance sampling schemes. A population Monte Carlo scheme taking advantage of the latent structure of the problem is proposed. The potential of this approach and its specifics in missing data problems are illustrated in settings of increasing difficulty, in comparison with existing approaches. The improvement brought by a general Rao–Blackwellisation technique is also discussed.     

基于重要抽样法和神经网络的模糊鲁棒性分析

将重要抽样(IS)法与神经网络(NN)用于不确定控制系统的模糊鲁棒性分析中.IS法被用于提高当模糊不可接受性能的概率很小时的抽样效率,而NN被用于预测每次仿真试验中所需计算时间较长的性能指标值.所建议方法降低了标准MonteCarlo仿真(MCS)方法在处理模糊鲁棒性分析中小概率事件以及性能指标计算时间较长所带来的过高计算成本.最后,仿真结果验证了方法的有效性.     

Automatic glottal inverse filtering with the Markov chain Monte Carlo method

This paper presents a new glottal inverse filtering (GIF) method that utilizes a Markov chain Monte Carlo (MCMC) algorithm. First, initial estimates of the vocal tract and glottal flow are evaluated by an existing GIF method, iterative adaptive inverse filtering (IAIF). Simultaneously, the initially estimated glottal flow is synthesized using the Rosenberg–Klatt (RK) model and filtered with the estimated vocal tract filter to create a synthetic speech frame. In the MCMC estimation process, the first few poles of the initial vocal tract model and the RK excitation parameter are refined in order to minimize the error between the synthetic and original speech signals in the time and frequency domain. MCMC approximates the posterior distribution of the parameters, and the final estimate of the vocal tract is found by averaging the parameter values of the Markov chain. Experiments with synthetic vowels produced by a physical modeling approach show that the MCMC-based GIF method gives more accurate results compared to two known reference methods.     

Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning

A Markov chain Monte Carlo method has previously been introduced to estimate weighted sums in multiplicative weight update algorithms when the number of inputs is exponential. However, the original algorithm still required extensive simulation of the Markov chain in order to get accurate estimates of the weighted sums. We propose an optimized version of the original algorithm that produces exactly the same classifications while often using fewer Markov chain simulations. We also apply three other sampling techniques and empirically compare them with the original Metropolis sampler to determine how effective each is in drawing good samples in the least amount of time, in terms of accuracy of weighted sum estimates and in terms of Winnow’s prediction accuracy. We found that two other samplers (Gibbs and Metropolized Gibbs) were slightly better than Metropolis in their estimates of the weighted sums. For prediction errors, there is little difference between any pair of MCMC techniques we tested. Also, on the data sets we tested, we discovered that all approximations of Winnow have no disadvantage when compared to brute force Winnow (where weighted sums are exactly computed), so generalization accuracy is not compromised by our approximation. This is true even when very small sample sizes and mixing times are used. An early version of this paper appeared as Tao and Scott (2003).     

Particle swarm optimization–Markov Chain Monte Carlo for accurate visual tracking with adaptive template update

A novel tracking method is proposed, which infers a target state and appearance template simultaneously. With this simultaneous inference, the method accurately estimates the target state and robustly updates the target template. The joint inference is performed by using the proposed particle swarm optimization–Markov chain Monte Carlo (PSO–MCMC) sampling method. PSO–MCMC is a combination of the particle swarm optimization (PSO) and Markov chain Monte Carlo sampling (MCMC), in which the PSO evolutionary algorithm and MCMC aim to find the target state and appearance template, respectively. The PSO can handle multi-modality in the target state and is therefore superior to a standard particle filter. Thus, PSO–MCMC achieves better performance in terms of accuracy when compared to the recently proposed particle MCMC. Experimental results demonstrate that the proposed tracker adaptively updates the target template and outperforms state-of-the-art tracking methods on a benchmark dataset.     

Learning effective state-feedback controllers through efficient multilevel importance samplers

Monte Carlo sampling can be used to estimate the solution of path integral control problems, which are a restricted class of nonlinear control problems with arbitrary dynamics and state cost, but with a linear dependence of the control on the dynamics and quadratic control cost. Although importance sampling is used to improve numerical computations, the effective sample size may still be low or many samples could be required. In this work, we propose a method to learn effective state-feedback controllers for nonlinear stochastic control problems based on multilevel importance samplers. In particular, we focus on the question of how to compute effective importance samplers considering a multigrid scenario. We test our algorithm in finite horizon control problems based on Lorenz-96 model with chaotic and non-chaotic behaviour, showing, in all cases, that our multigrid implementation reduces the computational time and improves the effective sample size.     

Time series of count data: modeling, estimation and diagnostics

Various models for time series of counts which can account for discreteness, overdispersion and serial correlation are compared. Besides observation- and parameter-driven models based upon corresponding conditional Poisson distributions, a dynamic ordered probit model as a flexible specification to capture the salient features of time series of counts is also considered. For all models, appropriate efficient estimation procedures are presented. For the parameter-driven specification this requires Monte-Carlo procedures like simulated maximum likelihood or Markov chain Monte Carlo. The methods, including corresponding diagnostic tests, are illustrated using data on daily admissions for asthma to a single hospital. Estimation results turn out to be remarkably similar across the different models.     

SampleSearch: Importance sampling in presence of determinism

The paper focuses on developing effective importance sampling algorithms for mixed probabilistic and deterministic graphical models. The use of importance sampling in such graphical models is problematic because it generates many useless zero weight samples which are rejected yielding an inefficient sampling process. To address this rejection problem, we propose the SampleSearch scheme that augments sampling with systematic constraint-based backtracking search. We characterize the bias introduced by the combination of search with sampling, and derive a weighting scheme which yields an unbiased estimate of the desired statistics (e.g., probability of evidence). When computing the weights exactly is too complex, we propose an approximation which has a weaker guarantee of asymptotic unbiasedness. We present results of an extensive empirical evaluation demonstrating that SampleSearch outperforms other schemes in presence of significant amount of determinism.     

An Introduction to MCMC for Machine Learning

This purpose of this introductory paper is threefold. First, it introduces the Monte Carlo method with emphasis on probabilistic machine learning. Second, it reviews the main building blocks of modern Markov chain Monte Carlo simulation, thereby providing and introduction to the remaining papers of this special issue. Lastly, it discusses new interesting research horizons.     

A Sequential Monte Carlo Method for Bayesian Analysis of Massive Datasets

Markov chain Monte Carlo (MCMC) techniques revolutionized statistical practice in the 1990s by providing an essential toolkit for making the rigor and flexibility of Bayesian analysis computationally practical. At the same time the increasing prevalence of massive datasets and the expansion of the field of data mining has created the need for statistically sound methods that scale to these large problems. Except for the most trivial examples, current MCMC methods require a complete scan of the dataset for each iteration eliminating their candidacy as feasible data mining techniques.In this article we present a method for making Bayesian analysis of massive datasets computationally feasible. The algorithm simulates from a posterior distribution that conditions on a smaller, more manageable portion of the dataset. The remainder of the dataset may be incorporated by reweighting the initial draws using importance sampling. Computation of the importance weights requires a single scan of the remaining observations. While importance sampling increases efficiency in data access, it comes at the expense of estimation efficiency. A simple modification, based on the rejuvenation step used in particle filters for dynamic systems models, sidesteps the loss of efficiency with only a slight increase in the number of data accesses.To show proof-of-concept, we demonstrate the method on two examples. The first is a mixture of transition models that has been used to model web traffic and robotics. For this example we show that estimation efficiency is not affected while offering a 99% reduction in data accesses. The second example applies the method to Bayesian logistic regression and yields a 98% reduction in data accesses.     

Tracking highly correlated targets through statistical multiplexing

We consider a special problem of multi-target tracking, where a group of targets are highly correlated, usually demonstrating a common motion pattern with individual variations. We focus on the task of searching and provide a statistical framework of embedding the correlation among targets and the most recent observations into sampling, where the correlation is learned dynamically from the previous tracking results. Proposal distribution is updated during the sampling process fused with the motion prior and observation information. In this way, the observation of a single target is multiplexed statistically through mutual correlation among the multiple targets, and the correlation serves as both a prior information to improve the efficiency and a constraint to prevent trackers from drifting. Extensive experiments on tracking both naturally correlated and environment-constrained targets demonstrate superior and promising robust results with low complexity.     

Parallel exact sampling and evaluation of Gaussian Markov random fields

Markov chain Monte Carlo algorithms are computationally expensive for large models. Especially, the so-called one-block Metropolis-Hastings (M-H) algorithm demands large computational resources, and parallel computing seems appealing. A parallel one-block M-H algorithm for latent Gaussian Markov random field (GMRF) models is introduced. Important parts of this algorithm are parallel exact sampling and evaluation of GMRFs. Parallelisation is achieved with parallel algorithms from linear algebra for sparse symmetric positive definite matrices. The parallel GMRF sampler is tested for GMRFs on lattices and irregular graphs, and gives both good speed-up and good scalability. The parallel one-block M-H algorithm is used to make inference for a geostatistical GMRF model with a latent spatial field of 31,500 variables.     

An adaptive Monte Carlo integration algorithm with general division approach

We propose an adaptive Monte Carlo algorithm for estimating multidimensional integrals over a hyper-rectangular region. The algorithm uses iteratively the idea of separating the domain of integration into 2^s$2^s$subregions. The proposed algorithm can be applied directly to estimate the integral using an efficient way of storage. We test the algorithm for estimating the value of a 30-dimensional integral using a two-division approach. The numerical results show that the proposed algorithm gives better results than using one-division approach.     

Robust specification of the roughness penalty prior distribution in spatially adaptive Bayesian P-splines models

The potential important role of the prior distribution of the roughness penalty parameter in the resulting smoothness of Bayesian P-splines models is considered. The recommended specification for that distribution yields models that can lack flexibility in specific circumstances. In such instances, these are shown to correspond to a frequentist P-splines model with a predefined and severe roughness penalty parameter, an obviously undesirable feature. It is shown that the specification of a hyperprior distribution for one parameter of that prior distribution provides the desired flexibility. Alternatively, a mixture prior can also be used. An extension of these two models by enabling adaptive penalties is provided. The posterior of all the proposed models can be quickly explored using the convenient Gibbs sampler.     

An adaptive surrogate modeling-based sampling strategy for parameter optimization and distribution estimation (ASMO-PODE)

Parameter distribution estimation has long been a hot issue for the uncertainty quantification of environmental models. Traditional approaches such as MCMC (Markov Chain Monte Carlo) are prohibitive to be applied to large complex dynamic models because of the high computational cost of computing resources. To reduce the number of model evaluations required, we proposed an adaptive surrogate modeling-based sampling strategy for parameter distribution estimation, named ASMO-PODE (Adaptive Surrogate Modeling-based Optimization – Parameter Optimization and Distribution Estimation). The ASMO-PODE can provide an estimation of the parameter distribution using as little as one percent of the model evaluations required by a regular MCMC approach. The effectiveness and efficiency of the ASMO-PODE approach have been evaluated with 2 test problems and one land surface model, the Common Land Model. The results demonstrated that the ASMO-PODE method is an economic way for parameter optimization and distribution estimation.     

An adaptive zero-variance importance sampling approximation for static network dependability evaluation

We propose an adaptive parameterized method to approximate the zero-variance change of measure for the evaluation of static network reliability models, with links subject to failures. The method uses two rough approximations of the unreliability function, conditional on the states of any subset of links being fixed. One of these approximations, based on mincuts, under-estimates the true unknown unreliability, whereas the other one, based on minpaths, over-estimates it. Our proposed change of measure takes a convex linear combination of the two, estimates the optimal (graph-dependent) coefficient in this combination from pilot runs, and uses the resulting conditional unreliability approximation at each step of a dynamic importance sampling algorithm. This new scheme is more general and more flexible than a previously proposed zero-variance approximation scheme, based on mincuts only, and which was shown to be robust asymptotically when unreliabilities of individual links decrease toward zero. Our numerical examples show that the new scheme is often more efficient when low unreliability comes from a large number of possible paths connecting the considered nodes rather than from small failure probabilities of the links.     

序列蒙特卡罗框架中引入对数取样的重采样

为解决粒子退化问题,在序列蒙特卡罗理论方面提出了一种引入对数取样的重采样策略,从仿真实验角度证实了它的有效性。对比其他几种典型的重采样,提出的重采样策略系统误差最小。在后验均值误差和均方差两项主要指标上,引入对数取样后的重采样由于平滑了采样点的分布,因此降低了重采样策略的系统误差;实验将提出的重采样策略嵌入到目标跟踪算法中,实际的测试结果同样验证了该重采样的收敛性和良好的抗噪性能。该理论性方法不仅适用于计算机视觉系统,而且可以应用于广泛的属于时间序列分析的非线性非高斯系统。