Evolutionary Thoughts on Evolutionary Monte Carlo

Gopi Goswami

Thanks a lot to Mike Kellerman for inviting me over for the talk on Oct 26, 05 at the IQSS (see here for details). I really enjoyed giving the talk and getting interesting comments and questions from the audience. In particular, Prof. Donald Rubin, Prof. Gary King and others made important contributions which I really appreciate. Prof. Kevin Quinn gave me some excellent suggestions on how to improve the structure of the talk which I think will turn out to be very helpful in the near future when I prepare for the job market. In fact, along those lines, if anyone may have any inputs/suggestions/comments on the presentation please feel free to send them to me at goswami@stat.harvard.edu.

Here are some afterthoughts on the talk. The PBC (Population Based Clustering) moves I presented, namely, SCSC:TWO-NEW, SCSC:ONE-NEW and SCRC are new and they are very specific to the sampling based
clustering (which is a discrete space) problem. I haven't been successful in devising similar moves in dealing with general sampling problem on a continuous space. In the Evolutionary Monte Carlo (EMC) literature these types of moves are also called "cross-over" moves because these moves take two chromosomes (or states of two chains)
which are called two "parents" and implement some cross-over type operation with the parents to produce two chromosomes (or proposed states of two chains) which are called "children."

The main motivation behind devising the above mentioned moves, as I mentioned in the talk, is that we were looking for moves which propose to update "more than one coordinate but not too many" at a time. Gibbs sampler proposes one coordinate at a time update. This is the main reason why Jain and Neal (A Split-Merge Markov Chain Monte Carlo
Procedure for the Dirichlet Process Mixture Model with Radford M. Neal, Journal of Computational and Graphical statistics, volume 13, No. 1, pp. 158-182 . (2004)) proposed their sampler which updates more than one coordinates at a time but it does so for one too many of them. To counter this problem we proposed the above mentioned PBC moves which are kind of a middle ground between the Gibbs sampler and the Jain-Neal sampler.

The other main issue addressed by the two moves, namely, SCSC:ONE-NEW and SCRC, is that "they produce only one new child" after "cross-over." To expand on this, we note that since all the PBC moves, the mentioned ones included, are Metropolis-Hastings type moves, two "children" have to be produced to replace the parents so as to maintain reversibility or detailed balance. But the children produced by two good parents are usually not good enough, and one does not want to throw away some good parent by chance. Thus, it has long been desired to design some moves that both can take advantage of the "cross-over" strategy and can keep some good parent. Our new moves are the first such in the literature.

Lastly, some members of the audience in the talk were worried about the temperature placement problem in the parallel tempering set up. Prof. Jun Liu and I proposed a first cut solution to the problem which solves the problem in two steps. First, we determine the highest temperature to be used in the ladder, namely, $t_1 = \tau_{max}$. Next, we look at the length and the structure of the ladder i.e. the placement of the intermediate temperatures within the
range $(\tau_{min}, \tau_{max})$. You can find the details of this the paper at my website by clicking on "On Real-Parameter Evolutionary Monte Carlo Algorithm (ps file) [submitted]":

Posted by James Greiner at November 7, 2005 5:42 AM