The Metropolis-Hastings algorithm

In this post, we will investigate the Metropolis-Hastings algorithm, which is still one of the most popular algorithms in the field of Markov chain Monte Carlo methods, even though its first appearence (see [1]) happened in 1953, more than 60 years in the past. It does for instance appear on the CiSe top ten list … Continue reading The Metropolis-Hastings algorithm

Recurrent and ergodic Markov chains

Today, we will look in more detail into convergence of Markov chains - what does it actually mean and how can we tell, given the transition matrix of a Markov chain on a finite state space, whether it actually converges. So suppose that we are given a Markov chain on a finite state space, with … Continue reading Recurrent and ergodic Markov chains

Monte Carlo methods and Markov chains – an introduction

In our short series on machine learning, we have already applied sampling methods several times. We have used and implemented Gibbs sampling, and so far we have simply accepted that the approach works. Time to look at this in a bit more detail in order to understand why it works and what the limitations of … Continue reading Monte Carlo methods and Markov chains – an introduction

Turn on the heating – from Hopfield networks to Boltzmann machines

In my recent post on Hopfield networks, we have seen that these networks suffer from the problem of spurious minima and that the deterministic nature of the dynamics of the network makes it difficult to escape from a local minimum. A possible approach to avoid this issue is to randomize the update rule. Intuitively, we want to … Continue reading Turn on the heating – from Hopfield networks to Boltzmann machines

Boltzmann machines, spin, Markov chains and all that

The image above displays a set of handwritten digits on the left. They look a bit like being sketched on paper by someone in a hurry and then scanned and digitalized, not very accurate but still mostly readable - but they are artificial, produced by a neuronal network, more precisely a so called restricted Boltzmann … Continue reading Boltzmann machines, spin, Markov chains and all that