All Posts

In this post we look at two MCMC algorithms that propose future states in the Markov Chain using Hamiltonian dynamics rather than a probability distribution. This allows the Markov chain to explore target distribution much more efficiently, resulting in faster convergence.

The Metropolis-Hastings algorithm is a Markov chain Monte Carlo algorithm that can be used to draw samples from both discrete and continuous probability distributions of all kinds, as long as we compute a function f that is proportional to the density of target distribution.

Markov Chains are integral component of Markov Chain Monte Carlo (MCMC) techniques. Under MCMC Markov Chain is used to sample from some target distribution. This post tries to develop basic intuition about what Markov Chain is and how we can use it to sample from a distribution. A Markov Chain is a stochastic process that undergoes transition from one state to another on a given set of states called state space of Markov Chain.

Monte Carlo methods is a class of methods or algorithms in which we try to approximate the numerical results using repeated random sampling. Monte Carlo methods are useful to obtain numerical solution to problems which are too complicated to be solved analytically. The most popular class of Monte Carlo methods are Monte Carlo approximations for integration a.k.a Monte Carlo integration.

MY PR for No-U-Turn-Sampler (NUTS) and NUTS with dual averaging has been merged. Apart from that I made a slight change in API of all the continuous sampling algorithms. Earlier I made the `grad_log_pdf` argument to be optional. Also since PR which dealt with implementing `JointGaussianDistribution` has been merged, I also made changes to accommodate it.

During week 5, I started working on No U Turn Sampler (NUTS). NUTS is an extension of Hamiltonian Monte Carlo that eliminates the need to set trajectory length. NUTS recursively builds a tree in forward and backward direction proposing set of likely candidates for new value of position and momentum and stopping automatically when it proposed values are no longer useful (doubling back). During week 6 apart from working on NUTS with dual-averaging I also used profiling to see scope of optimizations in my current implementation.

In terms of progress week 3 turned to be dull. I was having doubts in my mind regarding the representation since start of coding period and somehow I always forgot to have my doubts cleared in meeting. I wasted a lot of time reading theory to help me out with this doubt of mine and till mid of the week 4 it remained unclear.

During this week with some good amount of effort I was able to get ahead from my proposed time-line by writing sample method. My this week's time was spend in writing the sample method and reading Handbook of Markov Chain Monte Carlo. My experience of reading book proved rather depressing as I wasn't able to even partially gasp content given in introductory chapter but seeing `HamiltonianMCda` class returning samples boosted my moral. I also wrote tests for the HMC algorithm. I was thinking of using mock as it was already being used in tests for other sampling methods in pgmpy, but my mentor recommended to generate samples and apply inference on them.

This week of work proved to be quite productive. I was consistent with my proposed time line. For this week work I proposed to write base class structure for Hamiltonian Monte Carlo (HMC), and implement methods for leapfrog, modified Euler and algorithm for finding a reasonable starting value of epsilon.

This all started around a year back, when I got introduced to open source (Free and Open Source, Free as in speech) world. Feeling of being a part of something big was itself amazing and to add someone will be using my work in something great this proved to be more than driving force needed to get me going. The more I worked the more addicted I got. In around October 2015 through my brother and some answers on Quora I came to know about pgmpy(A python library for Probabilistic Graphical Models), and since then I have been contributing continuously.