Evolutionary Monte Carlo EM for Change Point Analysis

Abstract

In the change point inference of incomplete data, the expectation-maximization (EM) algorithm is often difficult to handle, and thus the Markov chain Monte Carlo (MCMC) method has been used in this area for a long time. However, the traditional MCMC algorithm tends to be trapped to local minima when generating samples from the posterior distribution of change points. To overcome this problem, various advanced Monte Carlo methods have been proposed, but still somewhat difficult to use. This paper proposes an evolutionary Monte Carlo EM (EMCEM) algorithm that combines the evolutionary Monte Carlo algorithm (EMC) with EM using the maximum likelihood method for efficient and user-friendly sampling. EMC has incorporated several attractive features of genetic algorithms and simulated annealing into the framework of MCMC. EMCEM is compared with reversible jump MCMC version of EM (RJMCMCEM), the stochastic approximation version of EM (SAEM) and the stochastic approximation Monte Carlo version of EM (SAMCEM) on simulated and real datasets. The numerical results indicate that EMCEM can outperform RJMCMCEM and SAEM by producing much more accurate parameter estimates, and EMCEM is comparable to SAMCEM.