{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Modules Imported!\n" ] } ], "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import scipy as sp\n", "import scipy.stats as st\n", "from math import sqrt\n", "from IPython.display import Latex,display,Math\n", "print(\"Modules Imported!\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Steady-state distributions of Markov chains\n", "(30 pts)\n", "\n", "In this excercise, let \n", "$$P=\\left[\\begin{array}{cc}\n", "\\frac{1}{2} & \\frac{1}{2}\\\\\n", "\\frac{1}{3} & \\frac{2}{3}\n", "\\end{array}\\right]$$\n", "denote the transition matrix of a Markov chain process $X_n$ with two states $\\{W,S\\}$. For example, $Pr(X_n=W|X_{n-1}=S)=\\frac13$. Recall that if $\\pi^{(n)}$ denotes the distribution of $X_n$, we have $\\pi^{(n+1)}=\\pi^{(n)}P$. Note that $X_n$ is irreducible and aperiodic. So it has a unique steady state distribution $\\phi$, which corresponds to the left eigenvector for eigenvalue 1.\n", "\n", "_____________\n", "Using python find the eigenvalues and eigenvectors of $P$. To do this, use [numpy.linalg](https://docs.scipy.org/doc/numpy/reference/routines.linalg.html): \n", " python\n", "import numpy.linalg as la\n", "\n", "and then use [numpy.linalg.eig](https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eig.html#numpy.linalg.eig):\n", " python\n", "w,v = la.eig(P.T)\n", "\n", "to get the eigenvaules/vectors. Find the eigenvector that corresponds to the eigenvalue 1. To do so, make sure you understand the output format of eig. Normalize this eigenvector such that it sums to 1 and verify that we indeed have $\\phi=P\\phi$ (use np.dot(P,phi))." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy.linalg as la\n", "P=np.array([[1/2,1/2],[1/3,2/3]])\n", "# ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "____________\n", "Pick an arbitrary initial distribution $\\pi^{(0)}$. Find $\\pi^{(n)}$ for $n=0,1,2,3,4$. Does convergence to $\\phi$ in fact occur? From the Perron-Frobenius theorem, we also know that the rows of $P^n$ converge to $\\phi$. Verify this through computation." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Sampling from Markov Chains:__ Suppose that we need to generate iid (independent and identically distributed) random samples from a given distribution $q$. Sometimes, it is difficult to do this directly, but we can construct a Markov chain whose stationary distribution is $q$. Then we can simulate this Markov chain and sample from it. Technically speaking, these samples are identically distributed but not independent. However, if there is enough of a gap between consecutive samples, they are \"approximately\" independent. For example, in the above Markov chain, if we take a sample at $n=3,6,9,\\dotsc$, we get nearly independent samples since $\\pi P^3\\simeq \\phi$ for any $\\pi$. (In practice we may decide to use all samples since dropping samples has a computational cost.)\n", "\n", "Simulate the above Markov chain by starting from an arbitrary state and take 1000 samples at steps that are multiples of 3. Verify that the distribution of these samples is the same as $\\phi$.\n", "\n", "_Hint_: Randomly transitioning to the next state where the trasition probabilities for going out of the current state are given by $p$ is equivalent to generating a random variable that is equal to $i$ with probability $p_i$, which can be done as follows (why?):\n", "python\n", "r = st.uniform.rvs()\n", "rv = np.sum(r>np.cumsum(p))\n", "" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def sample_MC(P,N,skip):\n", " M = len(P)\n", " y = [0] * N # initializing the vector of samples\n", " state = 0 # starting the chain from state 0\n", " # ...\n", " return(y)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "y = sample_MC(P,1000,3)\n", "# ..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "# Gibbs, Metropolis, Hamiltonian Metropolis Sampling\n", "(70 pts)\n", "\n", "We will implement several MCMC sampling algorithms and compare and contrast their performance. To make things simple, the code for everything except the sampling algorithms are given. You should review and understand all the given code and make sure the code you write is compatible. If you use a different language, you need to re-write the given code." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "__Setting up target distributions:__ First, we will define three python functions representing our target distributions, which are\n", "- $p_0$: a 2-d multivarate normal (__MVN__) with independent components,\n", "- $p_1$: a 2-d MVN with highly dependant components, and\n", "- $p_2$: a 2-d mixture of two MVNs.\n", "\n", "We have chosen 2-d targets to make it easier to plot the results." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "m = np.empty([4,2]); c = np.empty([4,2,2])\n", "\n", "m[0] = [0,0]; c[0] = [[1,0],[0,1]]\n", "\n", "m[1] = [0,0]; c[1] = 2*np.array([[1,0.98],[.98,1]])\n", "\n", "\n", "m[2] = [-1,-1]; c[2] = [[.7,.3],[.3,.7]]\n", "m[3] = [ 1, 1]; c[3] = [[.7,.3],[.3,.7]]\n", "\n", "def p0(th):\n", " rv = st.multivariate_normal(mean=m[0],cov=c[0])\n", " grad = np.dot(th,np.linalg.inv(c[0])) # Note how the gradient is computed\n", " return [rv.pdf(th),grad]\n", "\n", "def p1(th):\n", " rv = st.multivariate_normal(mean=m[1],cov=c[1])\n", " grad = np.dot(th,np.linalg.inv(c[1]))\n", " return [rv.pdf(th),grad]\n", "\n", "def p2(th):\n", " rv1 = st.multivariate_normal(mean=m[2],cov=c[2])\n", " rv2 = st.multivariate_normal(mean=m[3],cov=c[3])\n", " return [rv1.pdf(th)+rv2.pdf(th), np.nan]\n", "\n", "pp = [p0,p1,p2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "__Sampling methods:__ Implement a Gibbs sampler, a metropolis sampler, and a Hamiltonian metropolis sampler.\n", "\n", "For the metropolis algorithm, use a Normal jump distribution. The covariance of the jump distribution is passed to the functions as an argument. The metropolis algorithm should work for all three targets.\n", "\n", "Implement the Gibbs and the HMC samplers for 2-d MVNs. So it only needs to work with $p_0$ and $p_1$ but not the mixture $p_2$. Note that the functions for $p_0$ and $p_1$ given above also pass the gradient in addition to the value of the pdf." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# metropolis with normal jumps\n", "def metropolis(target_p, covJump, init, N_samples):\n", " # covJump: the covariance of the mustivariate normal jumping distn\n", " # target_p is the target distribution from which we want to sample. this is a function\n", " # N_samples is the number of samples we want\n", " # th = np.empty((N,len(init))) ## th will hold the samples that we generate\n", " # th[0] = init ## the starting point, i.e., the first sample\n", " # ...\n", " \n", " # for i in range(1,N):\n", " # ...\n", " \n", " return # return th" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Gibbs for 2-d normal\n", "def Gibbs_normal(mean, cov, init, N_samples):\n", " # mean: mean of the target MVN distribution\n", " # cov: covariance of the target MVN\n", " # th = np.empty([N,2])\n", " # th[0] = init\n", " # ...\n", " return # return th" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# HMC with standard normal momentum proposal, refer to McKay, \"Information Theory, Inference, and Learning Algorithms\"\n", "def HMC(target_p, eps, L, init, N_samples,):\n", " # eps is the scale of each leapfrog step\n", " # L is the number of leapfrog steps in each iteration\n", " # target_p(theta) returns [pdf, gradient] for the point theta\n", " # momentum_rv = ... ## proposal rv for momentum is a standard 2-d MVN\n", " # th = np.empty((N,len(init)))\n", " # ...\n", " return #return th\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Comparison of sampling methods:__ We now plot the samples obtained using each method for four random starting point. You need to run this 3 times to see the result for each of the targets. Note that Metropolis is the only method implemented here to handle $p_2$. Try different numbers of samples and a variety of values for the other parameters and compare the results of the methods. Describe the differences between the sampling methods based on this observations in a couple of paragraphs." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "# target distn\n", "\n", "i = 2\n", "p = pp[i]\n", "N = 500\n", "\n", "# the parameteres of the jumping distn\n", "covJump = np.array([[1,0],[0,1]])\n", "scale = .1\n", "\n", "# Metropolis\n", "f, ax = plt.subplots(2,2, sharex='col', sharey='row')\n", "for j in range(2):\n", " for k in range(2):\n", " init = st.uniform.rvs(-2,2,2)\n", " th = metropolis(p, scale*covJump, init, N)\n", " plt.axes(ax[j][k])\n", " plt.axis([-3,3,-3,3])\n", " plt.contourf(x,y,p(pos)[0])\n", " plt.plot(th[:,0],th[:,1],'k.',alpha=.5)\n", " # with small number of samples try also ':k.' to see the order of samples\n", "\n", "if i == 0 or i == 1:\n", " # HMC\n", " f, ax = plt.subplots(2,2)\n", " for j in range(2):\n", " for k in range(2):\n", " init = st.uniform.rvs(-2,2,2)\n", " th = HMC(p, 0.1, 10, init, N)\n", " plt.axes(ax[j][k])\n", " plt.axis([-3,3,-3,3])\n", " plt.contourf(x,y,p(pos)[0])\n", " plt.plot(th[:,0],th[:,1],'k.',alpha=.5)\n", " \n", " # Gibbs\n", " f, ax = plt.subplots(2,2)\n", " for j in range(2):\n", " for k in range(2):\n", " init = st.uniform.rvs(-2,2,2)\n", " th = Gibbs_normal(m[i], c[i], init, N)\n", " plt.axes(ax[j][k])\n", " plt.axis([-3,3,-3,3])\n", " plt.contourf(x,y,p(pos)[0])\n", " plt.plot(th[:,0],th[:,1],'k.',alpha=.5) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__corner:__ The [corner package](http://corner.readthedocs.io/en/latest/) is useful for demonstrating multivariate samples. Install it (open the Anaconda Prompt and type \"pip install corner\") and then run the following code. This should show the difference between Metropolis and HMC more clearly. In particular, describe the difference between the marginals." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import corner\n", "th = metropolis(pp[1], scale*covJump, init, 500)\n", "corner.corner(th);\n", "\n", "th = HMC(pp[1], 0.1, 10, init, 500)\n", "corner.corner(th);" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 2 }