notebooks/Section4_1-Bayesian-Computation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/fonnesbeck/Bios8366/blob/master/notebooks/Section4_1-Bayesian-Computation.ipynb)\n",
    "\n",
    "# Computational Methods in Bayesian Analysis\n",
    "\n",
    "The process of conducting Bayesian inference can be broken down into three general steps (Gelman *et al.* 2013):\n",
    "\n",
    "![](images/123.png)\n",
    "\n",
    "### Step 1: Specify a probability model\n",
    "\n",
    "As was noted above, Bayesian statistics involves using probability models to solve problems. So, the first task is to *completely specify* the model in terms of probability distributions. This includes everything: unknown parameters, data, covariates, missing data, predictions. All must be assigned some probability density.\n",
    "\n",
    "This step involves making choices.\n",
    "\n",
    "- what is the form of the sampling distribution of the data?\n",
    "- what form best describes our uncertainty in the unknown parameters?\n",
    "\n",
    "### Step 2: Calculate a posterior distribution\n",
    "\n",
    "The mathematical form \\\\(p(\\theta | y)\\\\) that we associated with the Bayesian approach is referred to as a **posterior distribution**.\n",
    "\n",
    "> posterior /pos·ter·i·or/ (pos-tēr´e-er) later in time; subsequent.\n",
    "\n",
    "Why posterior? Because it tells us what we know about the unknown \\\\(\\theta\\\\) *after* having observed \\\\(y\\\\).\n",
    "\n",
    "This posterior distribution is formulated as a function of the probability model that was specified in Step 1. Usually, we can write it down but we cannot calculate it analytically. In fact, the difficulty inherent in calculating the posterior distribution for most models of interest is perhaps the major contributing factor for the lack of widespread adoption of Bayesian methods for data analysis. Various strategies for doing so comprise this tutorial.\n",
    "\n",
    "**But**, once the posterior distribution is calculated, you get a lot for free:\n",
    "\n",
    "- point estimates\n",
    "- credible intervals\n",
    "- quantiles\n",
    "- predictions\n",
    "\n",
    "### Step 3: Check your model\n",
    "\n",
    "Though frequently ignored in practice, it is critical that the model and its outputs be assessed before using the outputs for inference. Models are specified based on assumptions that are largely unverifiable, so the least we can do is examine the output in detail, relative to the specified model and the data that were used to fit the model.\n",
    "\n",
    "Specifically, we must ask:\n",
    "\n",
    "- does the model fit data?\n",
    "- are the conclusions reasonable?\n",
    "- are the outputs sensitive to changes in model structure?\n",
    "\n",
    "\n",
    "## Example: binomial calculation\n",
    "\n",
    "Binomial model is suitable for data that are generated from a sequence of exchangeable Bernoulli trials. These data can be summarized by $y$, the number of times the event of interest occurs, and $n$, the total number of trials. The model parameter is the expected proportion of trials that an event occurs.\n",
    "\n",
    "\\\\[p(Y|\\theta) = \\frac{n!}{y! (n-y)!} \\theta^{y} (1-\\theta)^{n-y}\\\\]\n",
    "\n",
    "where $y \\in \\{0, 1, \\ldots, n\\}$ and $p \\in [0, 1]$.\n",
    "\n",
    "To perform Bayesian inference, we require the specification of a prior distribution. A reasonable choice is a uniform prior on [0,1] which has two implications:\n",
    "\n",
    "1. makes all probability values equally probable *a priori* \n",
    "2. makes calculation of the posterior easy\n",
    "\n",
    "The second task in performing Bayesian inference is, given a fully-specified model, to calculate a posterior distribution. As we have specified the model, we can calculate a posterior distribution up to a proportionality constant (that is, a probability distribution that is **unnormalized**):\n",
    "\n",
    "$$P(\\theta | n, y) \\propto P(y | n, \\theta) P(\\theta) = \\theta^y (1-\\theta)^{n-y}$$\n",
    "\n",
    "We can present different posterior distributions as a function of different realized data.\n",
    "\n",
    "We can also calculate posterior estimates for $\\theta$ by maximizing the unnormalized posterior using optimization. \n",
    "\n",
    "### Exercise: posterior estimation\n",
    "\n",
    "Write a function that returns posterior estimates of a binomial sampling model using a uniform prior on the unknown probability. Plot the posterior densities for each of the following datasets:\n",
    "\n",
    "1. n=5, y=3\n",
    "2. n=20, y=12\n",
    "3. n=100, y=60\n",
    "4. n=1000, y=600\n",
    "\n",
    "what type of distribution do these plots look like?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Informative Priors\n",
    "\n",
    "Formally, we justify a non-informative prior by the **Principle of Insufficient Reason**, which states that uniform probability is justified when there is nothing known about the parameter in question. Frequently, it is inappropriate to employ an uninformative prior as we have done above. For some distributions there is no clear choice of such a prior, particularly when parameters are transformed. For example, a flat prior on the real line is not flat on the unit interval. \n",
    "\n",
    "There are two alternative interpretations of the prior distribution.\n",
    "\n",
    "1. **Population prior**: a distribution that represents a notional population of values for the parameter, from which those in the current experiment/study have been drawn.\n",
    "2. **Knowledge prior**: a distribution that represents our uncertainty about the true value of the parameter.\n",
    "\n",
    "In either case, a prior distribution should include in its support all parameter values that are plausible.\n",
    "\n",
    "Choosing an informative prior presents an analytic challenge with respect to the functional form of the prior distribution. We would like a prior that results in a posterior distribution that is simple to work with. Taking our binomial likelihood again as an example:\n",
    "\n",
    "$$P(\\theta | n, y) \\propto \\theta^y (1-\\theta)^{n-y}$$\n",
    "\n",
    "we can see that it is of the general form $\\theta^a (1-\\theta)^b$. Thus, we are looking for a parametric distribution that describes the distribution of or uncertainty in $\\theta$ that is of this general form. The **beta distribution** satisfies these criteria:\n",
    "\n",
    "$$P(\\theta | \\alpha, \\beta) \\propto \\theta^{\\alpha-1} (1-\\theta)^{\\beta-1}$$\n",
    "\n",
    "The parameters $\\alpha, \\beta$ are called **hyperparameters**, and here they suggest prior information corresponding to $\\alpha-1$ \"successes\" and $\\beta-1$ failures. \n",
    "\n",
    "Let's go ahead and calculate the posterior distribution:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "P(\\theta | n, y) &\\propto& \\theta^y (1-\\theta)^{n-y} \\theta^{\\alpha-1} (1-\\theta)^{\\beta-1} \\\\\n",
    "    &=& \\theta^{y+\\alpha-1} (1-\\theta)^{n-y+\\beta-1} \\\\\n",
    "    &=& \\text{Beta}(\\alpha + y, \\beta + n -y) \\\\\n",
    "\\end{aligned}$$\n",
    "\n",
    "So, in this instance, the posterior distribution follows the same functional form as the prior. This phenomenon is referred to as **conjugacy**, whereby the beta distribution is in the conjugate family for the binomial sampling distribution.\n",
    "\n",
    "> What is the posterior distribution when a Beta(1,1) prior is used?\n",
    "\n",
    "Formally, we defined conjugacy by saying that a class $\\mathcal{P}$ is a conjugate prior for the class $\\mathcal{F}$ of likelihoods if:\n",
    "\n",
    "$$P(\\theta | y) \\propto f(y|\\theta) p(\\theta) \\in \\mathcal{P} \\text{ for all } f \\in \\mathcal{F} \\text{ and } p \\in \\mathcal{P}$$\n",
    "\n",
    "This definition is quite vague for practical application, so we are more interested in **natural** conjugates, whereby the conjugacy is specific to a particular distribution, and not just a class of distributions.\n",
    "\n",
    "In the case of the binomial model with a beta prior, we can now analytically calculate the posterior mean and variance for the model:\n",
    "\n",
    "$$E[\\theta|n,y] = \\frac{\\alpha + y}{\\alpha + \\beta + n}$$\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\text{Var}[\\theta|n,y] &=& \\frac{(\\alpha + y)(\\beta + n - y)}{(\\alpha + \\beta + n)^2(\\alpha + \\beta + n +1)} \\\\\n",
    "&=& \\frac{E[\\theta|n,y] (1-E[\\theta|n,y])}{\\alpha + \\beta + n +1}\n",
    "\\end{aligned}$$\n",
    "\n",
    "Notice that the posterior expectation will always fall between the sample and prior means.\n",
    "\n",
    "Notice also what happens when $y$ and $n-y$ get large."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: probability of female birth given placenta previa\n",
    "\n",
    "Placenta previa is an unusual condition of pregnancy in which the placenta is implanted low in the uterus, complicating a normal delivery. An German study of the sex of placenta previa births found that of 980 births, 437 were female. \n",
    "\n",
    "How much evidence does this provide for the claim that the proportion of female births in the population of placenta previa births $\\theta$ is less than 0.485 (this is the proportion of female births in the general population)?\n",
    "\n",
    "1. Calculate the the posterior distribution for $\\theta$ using a uniform prior, and plot the prior, likelihood and posterior on the same axes.\n",
    "\n",
    "2. Find a prior distribution that has a mean of 0.485 and prior \"sample size\" of 100. Calculate the posterior distribution and plot the prior, likelihood and posterior on the same axes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your answer here "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approximate Computation\n",
    "\n",
    "Most interesting Bayesian models cannot be computed analytically in closed form, or simulated from directly using random number generators for standard distributions.\n",
    "\n",
    "Bayesian analysis often requires integration over multiple dimensions that is intractable both via analytic methods or standard methods of numerical integration.\n",
    "However, it is often possible to compute these integrals by simulating\n",
    "(drawing samples) from posterior distributions. For example, consider the expected value of a random variable $\\mathbf{x}$:\n",
    "\n",
    "$$E[\\mathbf{x}] = \\int \\mathbf{x} f(\\mathbf{x}) d\\mathbf{x}, \\qquad\\mathbf{x} = x_1, \\ldots ,x_k$$\n",
    "\n",
    "where $k$ (the dimension of vector $x$) is perhaps very large. If we can produce a reasonable number of random vectors $\\{{\\bf x_i}\\}$, we can use these values to approximate the unknown integral. This process is known as *Monte Carlo integration*. In general, MC integration allows integrals against probability density functions:\n",
    "\n",
    "$$I = \\int h(\\mathbf{x}) f(\\mathbf{x}) \\mathbf{dx}$$\n",
    "\n",
    "to be estimated by finite sums:\n",
    "\n",
    "$$\\hat{I} = \\frac{1}{n}\\sum_{i=1}^n h(\\mathbf{x}_i),$$\n",
    "\n",
    "where $\\mathbf{x}_i$ is a sample from $f$. This estimate is valid and useful because:\n",
    "\n",
    "-   By the strong law of large numbers:\n",
    "\n",
    "$$\\hat{I} \\rightarrow I   \\text{   with probability 1}$$\n",
    "\n",
    "-   Simulation error can be measured and controlled:\n",
    "\n",
    "$$Var(\\hat{I}) = \\frac{1}{n(n-1)}\\sum_{i=1}^n (h(\\mathbf{x}_i)-\\hat{I})^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How is this relevant to Bayesian analysis? \n",
    "\n",
    "When we observe data $y$ that we hypothesize as being obtained from a sampling model $f(y|\\theta)$, where $\\theta$ is a vector of (unknown) model parameters, a Bayesian places a *prior* distribution $p(\\theta)$ on the parameters to describe the uncertainty in the true values of the parameters. Bayesian inference, then, is obtained by calculating the *posterior* distribution, which is proportional to the product of these quantities:\n",
    "\n",
    "$$p(\\theta | y) \\propto f(y|\\theta) p(\\theta)$$\n",
    "\n",
    "unfortunately, for most problems of interest, the normalizing constant cannot be calculated because it involves mutli-dimensional integration over $\\theta$.\n",
    "\n",
    "Returning to our integral for MC sampling, if we replace $f(\\mathbf{x})$\n",
    "with a posterior, $p(\\theta|y)$ and make $h(\\theta)$ an interesting function of the unknown parameter, the resulting expectation is that of the posterior of $h(\\theta)$:\n",
    "\n",
    "$$E[h(\\theta)|y] = \\int h(\\theta) p(\\theta|y) d\\theta \\approx \\frac{1}{n}\\sum_{i=1}^n h(\\theta)$$\n",
    "\n",
    "We also require integrals to obtain marginal estimates from a joint model. If $\\theta$ is of length $K$, then inference about any particular parameter is obtained by:\n",
    "\n",
    "$$p(\\theta_i|y) \\propto \\int p(\\theta|y) d\\theta_{-i}$$\n",
    "\n",
    "where the `-i` subscript indicates all elements except the $i^{th}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Overdispersion Model\n",
    "\n",
    "[Tsutakawa et al. (1985)](http://onlinelibrary.wiley.com/doi/10.1002/sim.4780040210/abstract) provides mortality data for stomach cancer among men aged 45-64 in several cities in Missouri. The file `cancer.csv` contains deaths $y_i$ and subjects at risk $n_i$ for 20 cities from this dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "DATA_URL = 'https://raw.githubusercontent.com/fonnesbeck/Bios8366/master/data/'\n",
    "\n",
    "try:\n",
    "    cancer = pd.read_table('../data/cancer.data.txt')\n",
    "except FileNotFoundError:\n",
    "    cancer = pd.read_table(DATA_URL + 'cancer.data.txt')\n",
    "cancer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we use a simple binomial model, which assumes independent samples from a binomial distribution with probability of mortality $p$, we can use MLE to obtain an estimate of this probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ytotal, ntotal = cancer.sum().astype(float)\n",
    "p_hat = ytotal/ntotal\n",
    "p_hat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, if we compare the variation of $y$ under this model, it is to small relative to the observed variation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_hat*(1.-p_hat)*ntotal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cancer.y.var()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence, the data are strongly overdispersed relative to what is predicted under a model with a fixed probability of death. A more realistic model would allow for these probabilities to vary among the cities. One way of representing this is conjugating the binomial distribution with another distribution that describes the variation in the binomial probability. A sensible choice for this is the **beta distribution**:\n",
    "\n",
    "$$f(p \\mid \\alpha, \\beta) = \\frac{\\Gamma(\\alpha + \\beta)}{\\Gamma(\\alpha) \\Gamma(\\beta)} p^{\\alpha - 1} (1 - p)^{\\beta - 1}$$\n",
    "\n",
    "Conjugating this with the binomial distribution, and reparameterizing such that $\\alpha = K\\eta$ and $\\beta = K(1-\\eta)$ for $K > 0$ and $\\eta \\in (0,1)$ results in the **beta-binomial distribution**:\n",
    "\n",
    "$$f(y \\mid K, \\eta) = \\frac{n!}{y!(n-y)!} \\frac{B(K\\eta+y, K(1-\\eta) + n - y)}{B(K\\eta, K(1-\\eta))}$$\n",
    "\n",
    "where $B$ is the beta function.\n",
    "\n",
    "What remains is to place priors over the parameters $K$ and $\\eta$. Common choices for diffuse (*i.e.* vague or uninformative) priors are:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "p(K) &\\propto \\frac{1}{(1+K)^2} \\cr\n",
    "p(\\eta) &\\propto \\frac{1}{\\eta(1-\\eta)}\n",
    "\\end{aligned}$$\n",
    "\n",
    "These are not normalized, but our posterior will not be normalized anyhow, so this is not an issue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=(10,4))\n",
    "K_x = np.linspace(0, 10)\n",
    "K_prior = lambda K: 1./(1. + K)**2\n",
    "axes[0].plot(K_x, K_prior(K_x))\n",
    "axes[0].set_xlabel('K')\n",
    "axes[0].set_ylabel('p(K)')\n",
    "\n",
    "eta_x = np.linspace(0, 1)\n",
    "eta_prior = lambda eta: 1./(eta*(1.-eta)) \n",
    "axes[1].plot(eta_x, eta_prior(eta_x))\n",
    "axes[1].set_xlabel(r'$\\eta$')\n",
    "axes[1].set_ylabel(r'p($\\eta$)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, by multiplying these quantities together, we can obtain a non-normalized posterior.\n",
    "\n",
    "$$p(K, \\eta | \\mathbf{y}) \\propto \\frac{1}{(1+K)^2} \\frac{1}{\\eta(1-\\eta)} \\prod_i \\frac{B(K\\eta+y_i, K(1-\\eta) + n_i - y_i)}{B(K\\eta, K(1-\\eta))}$$\n",
    "\n",
    "This can be calculated in Python as follows (log-transformed):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.special import betaln\n",
    "\n",
    "def betabin_post(params, n, y):\n",
    "\n",
    "    K, eta = params\n",
    "    post = betaln(K*eta + y, K*(1.-eta) + n - y).sum()\n",
    "    post -= len(y)*betaln(K*eta, K*(1.-eta))\n",
    "    post -= np.log(eta*(1.-eta))\n",
    "    post -= 2.*np.log(1.+K)\n",
    "    \n",
    "    return post\n",
    "        \n",
    "betabin_post((15000, 0.003), cancer.n, cancer.y)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This posterior can be evaluated on a grid to give us an idea about its general shape. We can see that it is skewed in both dimensions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create grid\n",
    "K_x = np.linspace(1, 20000)\n",
    "eta_x = np.linspace(0.0001, 0.003)\n",
    "\n",
    "# Calculate posterior on grid\n",
    "z = np.array([[betabin_post((K, eta), cancer.n, cancer.y) \n",
    "               for eta in eta_x] for K in K_x])\n",
    "\n",
    "# Plot posterior\n",
    "x, y = np.meshgrid(eta_x, K_x)\n",
    "cplot = plt.contour(x, y, z-z.max(), [-4, -3, -2, -1, -0.5], cmap=plt.cm.RdBu)\n",
    "plt.ylabel('K')\n",
    "plt.xlabel('$\\eta$');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To deal with the extreme skewness in the precision parameter $K$ and to facilitate modeling, we can transform the beta-binomial parameters to the real line via:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\theta_1 &= \\log(K) \\cr\n",
    "\\theta_2 &= \\log\\left(\\frac{\\eta}{1-\\eta}\\right)\n",
    "\\end{aligned}$$\n",
    "\n",
    "which we can easily implement by modifiying `betabin_post`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def betabin_trans(theta, n, y):\n",
    "    K = np.exp(theta[0])\n",
    "    eta = 1./(1. + np.exp(-theta[1]))\n",
    "    \n",
    "    post = (betaln(K*eta + y, K*(1.-eta) + n - y) - betaln(K*eta, K*(1.-eta))).sum()\n",
    "    post += theta[0]\n",
    "    post -= 2.*np.log(1.+np.exp(theta[0]))\n",
    "    \n",
    "    return post\n",
    "    \n",
    "betabin_trans((10, -7.5), cancer.n, cancer.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create grid\n",
    "log_K_x = np.linspace(0, 20)\n",
    "logit_eta_x = np.linspace(-8, -5)\n",
    "\n",
    "# Calculate posterior on grid\n",
    "z = np.array([[betabin_trans((t1, t2), cancer.n, cancer.y) \n",
    "             for t2 in logit_eta_x] for t1 in log_K_x])\n",
    "\n",
    "# Plot posterior\n",
    "x, y = np.meshgrid(logit_eta_x, log_K_x)\n",
    "cplot = plt.contour(x, y, z - z.max(), levels=[-8, -4, -2, -1, -0.5], cmap=plt.cm.RdBu)\n",
    "plt.clabel(cplot, inline=1, fontsize=10, fmt='%1.1f')\n",
    "plt.ylabel('log(K)')\n",
    "plt.xlabel('logit($\\eta$)');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approximation Methods\n",
    "\n",
    "An alternative approach to summarizing a $p$-dimensional posterior distribution involves estimating the mode of the posterior, and approximating the density as multivariate normal. If we consider the logarithm of the unnormalized joint posterior:\n",
    "\n",
    "$$h(\\theta | y) = \\log[f(y|\\theta) p(\\theta)]$$\n",
    "\n",
    "one way to approximate this function is to usd a second-order Taylor series expansion around the mode $\\hat{\\theta}$:\n",
    "\n",
    "$$h(\\theta | y) \\approx h(\\hat{\\theta} | y) + \\frac{1}{2}(\\theta-\\hat{\\theta})' h''(\\hat{\\theta} | y) (\\theta-\\hat{\\theta})$$\n",
    "\n",
    "This form is simply the multivariate normal distribution with $\\hat{\\theta}$ as the mean and the inverse negative Hessian as the covariance matrix:\n",
    "\n",
    "$$\\Sigma = -h''(\\hat{\\theta} | y)^{-1}$$\n",
    "\n",
    "We can apply one of several numerical methods for multivariate optimization to numerically estimate the mode of the posterior. Here, we will use the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm that is provided by SciPy. In addition to returning an estimate of the mode, it returns the estimated variance-covariance matrix, which we will need to parameterize the mutlivariate normal distribution.\n",
    "\n",
    "Applying this to the beta-binomial posterior estimation problem, we simply provide an initial guess for the mode:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.optimize import minimize\n",
    "\n",
    "betabin_trans_min = lambda *args: -betabin_trans(*args)\n",
    "\n",
    "init_value = (10, -7.5)\n",
    "\n",
    "opt = minimize(betabin_trans_min, init_value, method='L-BFGS-B',\n",
    "          args=(cancer.n.values, cancer.y.values))\n",
    "mode = opt.x\n",
    "var = opt.hess_inv.todense()\n",
    "mode, var"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, our approximated mode is $\\log(K)=7.6$, $\\text{logit}(\\eta)=-6.8$. We can plug this value, along with the variance-covariance matrix, into a function that returns the kernel of a multivariate normal distribution, and use this to plot the approximate posterior:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "det = np.linalg.det \n",
    "inv = np.linalg.inv\n",
    "\n",
    "def lmvn(value, mu, Sigma):\n",
    "    # Log kernel of multivariate normal\n",
    "    delta = np.array(value) - mu\n",
    "    return -0.5 * (np.log(det(Sigma)) + np.dot(delta, np.dot(inv(Sigma), delta)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z = np.array([[lmvn((t1, t2), mode, var) \n",
    "             for t2 in logit_eta_x] for t1 in log_K_x])\n",
    "x, y = np.meshgrid(logit_eta_x, log_K_x)\n",
    "cplot = plt.contour(x, y, z - z.max(), levels=[-8, -4, -2, -1, -0.5], cmap=plt.cm.RdBu)\n",
    "plt.ylabel('log(K)')\n",
    "plt.xlabel('logit($\\eta$)');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Along with this, we can estimate a 95% probability interval for the estimated mode:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from scipy.stats.distributions import norm\n",
    "\n",
    "se = np.sqrt(np.diag(var))\n",
    "\n",
    "mode[0] + norm.ppf(0.025)*se[0], mode[0] + norm.ppf(0.975)*se[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mode[1] + norm.ppf(0.025)*se[1], mode[1] + norm.ppf(0.975)*se[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, this approximation is only reasonable for posteriors that are not strongly skewed, bimodal, or leptokurtic (heavy-tailed)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rejection Sampling\n",
    "\n",
    "Though Monte Carlo integration allows us to estimate integrals that are unassailable by analysis and standard numerical methods, it relies on the ability to draw samples from the posterior distribution. For known parametric forms, this is not a problem; probability integral transforms or bivariate techniques (e.g Box-Muller method) may be used to obtain samples from uniform pseudo-random variates generated from a computer. Often, however, we cannot readily generate random values from non-standard posteriors. In such instances, we can use rejection sampling to generate samples.\n",
    "\n",
    "Posit a function, $f(x)$ which can be evaluated for any value on the support of $x:S_x = [A,B]$, but may not be integrable or easily sampled from. If we can calculate the maximum value of $f(x)$, we can then define a rectangle that is guaranteed to contain all possible values\n",
    "$(x,f(x))$. It is then trivial to generate points over the box and enumerate the values that fall under the curve.\n",
    "\n",
    "\n",
    "$$\\begin{gathered}\n",
    "\\begin{split}\\frac{\\mbox{Points under curve}}{\\mbox{Points generated}} \\times \\mbox{box area} = \\lim_{n \\to \\infty} \\int_A^B f(x) dx\\end{split}\\notag\\\\\\begin{split}\\end{split}\\notag\\end{gathered}$$\n",
    "\n",
    "### Example: triangular distribution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rtriangle(low, high, mode):\n",
    "    alpha = -1\n",
    "    while np.random.random() > alpha:\n",
    "        u = np.random.uniform(low, high)\n",
    "        if u < mode:\n",
    "            alpha = (u - low) / (mode - low)\n",
    "        else:\n",
    "            alpha = (high - u) / (high - mode)\n",
    "    return(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "_ = plt.hist([rtriangle(0, 7, 2) for t in range(10000)], bins=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This approach is useful, for example, in estimating the normalizing constant for posterior distributions.\n",
    "\n",
    "\n",
    "If $f(x)$ has **unbounded support** (i.e. infinite tails), such as a Gaussian distribution, a bounding box is no longer appropriate. We must specify a majorizing (or, enveloping) function, $g(x)$, which implies:\n",
    "\n",
    "$$\\begin{gathered}\n",
    "\\begin{split}cg(x) \\ge  f(x) \\qquad\\forall x \\in (-\\infty,\\infty)\\end{split}\\notag\\\\\\begin{split}\\end{split}\\notag\\end{gathered}$$\n",
    "\n",
    "Having done this, we can now sample ${x_i}$ from $g(x)$ and accept or reject each of these values based upon $f(x_i)$. Specifically, for each draw $x_i$, we also draw a uniform random variate $u_i$ and accept $x_i$\n",
    "if $u_i < f(x_i)/cg(x_i)$, where $c$ is a constant. This procedure is repeated until a sufficient number of samples is obtained. This approach is made more efficient by choosing an **enveloping distribution** that is “close” to the target distribution, thus maximizing the number of accepted points. \n",
    "\n",
    "To apply rejection sampling to the beta-binomial example, we first need to find a majorizing function $g(x)$ from which we can easily draw samples. We have seen in the previous section that the multivariate normal might serve as a suitable candidate, if multiplied by an appropriately large value of $c$. However, the thinness of the normal tails makes it difficult to use as a majorizing function. Instead, a multivariate Student's T distribution offers heavier tails for a suitably-small value for the degrees of freedom $\\nu$:\n",
    "\n",
    "$$f(\\mathbf{x}| \\nu,\\mu,\\Sigma) = \\frac{\\Gamma\\left[(\\nu+p)/2\\right]}{\\Gamma(\\nu/2)\\nu^{p/2}\\pi^{p/2}\\left|{\\Sigma}\\right|^{1/2}\\left[1+\\frac{1}{\\nu}({\\mathbf x}-{\\mu})^T{\\Sigma}^{-1}({\\mathbf x}-{\\mu})\\right]^{(\\nu+p)/2}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can draw samples from a multivariate-T density by combining mutlivariate normal and $\\chi^2$ random variates:\n",
    "\n",
    "> ### Generating multivariate-T samples\n",
    "\n",
    "> If $X$ is distributed multivariate normal $\\text{MVN}(\\mathbf{0},\\Sigma)$ and $S$ is a $\\chi^2$ random variable with $\\mu$ degrees of freedom, then a multivariate Student's-T random variable $T = T_1,\\ldots,T_p$ can be generated by $T_i = \\frac{\\sqrt{\\nu}X_i}{S} + \\mu_i$, where $\\mu = \\mu_1,\\ldots,\\mu$ is a mean vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is implemented in Python by:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "chi2 = np.random.chisquare\n",
    "mvn = np.random.multivariate_normal\n",
    "\n",
    "rmvt = lambda nu, S, mu=0, size=1: (np.sqrt(nu) * (mvn(np.zeros(len(S)), S, size).T\n",
    "                                   / chi2(nu, size))).T + mu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we need an implementation of the multivariate T probability distribution function, which is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.special import gammaln\n",
    "\n",
    "def mvt(x, nu, S, mu=0): \n",
    "\n",
    "    d = len(S)\n",
    "    n = len(x)\n",
    "    X = np.atleast_2d(x) - mu\n",
    "    \n",
    "    Q = X.dot(np.linalg.inv(S)).dot(X.T).sum()\n",
    "    log_det = np.log(np.linalg.det(S))\n",
    "    log_pdf = gammaln((nu + d)/2.) - 0.5 * (d*np.log(np.pi*nu) + log_det) - gammaln(nu/2.)\n",
    "    log_pdf -= 0.5*(nu + d)*np.log(1 + Q/nu)\n",
    "    \n",
    "    return(np.exp(log_pdf))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next step is to find the constant $c$ that ensures:\n",
    "\n",
    "$$cg(\\theta) \\ge  f(\\theta|y) \\qquad\\forall \\theta \\in (-\\infty,\\infty)$$\n",
    "\n",
    "Alternatively, we want to ensure:\n",
    "\n",
    "$$\\log[f(\\theta|y)] - \\log[g(\\theta)] \\le c'$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_diff(theta, n, y, nu, S, mu):\n",
    "    \n",
    "    return betabin_trans(theta, n, y) - np.log(mvt(theta, nu, S, mu))\n",
    "\n",
    "calc_diff_min = lambda *args: -calc_diff(*args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can calculate an appropriate value of $c'$ by simply using the approximation method described above on `calc_diff` (tweaked to produce a negative value for minimization):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "opt = minimize(calc_diff_min, \n",
    "                (12, -7), \n",
    "                args=(cancer.n, cancer.y, 4, 2*var, mode), \n",
    "                method='bfgs')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "opt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = opt.fun"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can execute a rejection sampling algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reject(post, nu, S, mu, n, data, c):\n",
    "    \n",
    "    k = len(mode)\n",
    "    \n",
    "    # Draw samples from g(theta)\n",
    "    theta = rmvt(nu, S, mu, size=n)\n",
    "    \n",
    "    # Calculate probability under g(theta)\n",
    "    gvals = np.array([np.log(mvt(t, nu, S, mu)) for t in theta])\n",
    "\n",
    "    # Calculate probability under f(theta)\n",
    "    fvals = np.array([post(t, data.n, data.y) for t in theta])\n",
    "    \n",
    "    # Calculate acceptance probability\n",
    "    p = np.exp(fvals - gvals + c)\n",
    "    \n",
    "    return theta[np.random.random(n) < p]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nsamples = 1000\n",
    "np.random.seed(20180125)\n",
    "sample = reject(betabin_trans, 4, var, mode, nsamples, cancer, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "z = np.array([[betabin_trans((t1, t2), cancer.n, cancer.y) \n",
    "             for t2 in logit_eta_x] for t1 in log_K_x])\n",
    "x, y = np.meshgrid(logit_eta_x, log_K_x)\n",
    "cplot = plt.contour(x, y, z - z.max(), levels=[-8, -4, -2, -1, -0.5], cmap=plt.cm.RdBu)\n",
    "plt.clabel(cplot, inline=1, fontsize=10, fmt='%1.1f')\n",
    "plt.ylabel('log(K)');plt.xlabel('logit($\\eta$)')\n",
    "plt.scatter(*sample.T[[1,0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the efficiency of rejection sampling is not very high for this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "float(sample.size)/nsamples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rejection sampling is usually subject to declining performance as the dimension of the parameter space increases. Further improvement is gained by using optimized algorithms such as importance sampling which, as the name implies, samples more frequently from important areas of the distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importance Sampling\n",
    "\n",
    "As we have seen, the primary difficulty in Bayesian inference is calculating the posterior density for models of moderate-to-high dimension. For example, calculating the posterior mean of some function $h$ requires two difficult integration steps:\n",
    "\n",
    "$$E[h(\\theta) | y] = \\frac{\\int h(\\theta)f(y|\\theta) p(\\theta) d\\theta}{\\int f(y|\\theta) p(\\theta) d\\theta} = \\frac{\\int h(\\theta)p(\\theta | y) d\\theta}{\\int p(\\theta|y) d\\theta}$$\n",
    "\n",
    "If the posterior $p(\\theta|y)$ is a density from which it is easy to sample, we could approximiate these integrals using Monte Carlo simulation, but too often it is not.\n",
    "\n",
    "Instead, assume that we can draw from a probability density $q(\\theta)$ that is some approximation of $p$. We could then write:\n",
    "\n",
    "$$E[h(\\theta) | y] = \\frac{\\int h(\\theta) \\frac{p(\\theta|y)}{q(\\theta)} q(\\theta) d\\theta}{\\int \\frac{p(\\theta|y)}{q(\\theta)} q(\\theta) d\\theta}$$\n",
    "\n",
    "Expressed this way, $w(\\theta) = p(\\theta|y) / q(\\theta)$ can be regarded as *weights* for the $M$ values of $\\theta$ sampled from $q$ that we can use to correct the sample so that it approximates $h(\\theta)$. Specifically, the **importance sampling estimate** of $E[h(\\theta) | y]$ is:\n",
    "\n",
    "$$\\hat{h}_{is} = \\frac{\\sum_{i=1}^{M} h(\\theta^{(i)})w(\\theta^{(i)})}{\\sum_{i=1}^{M} w(\\theta^{(i)})}$$\n",
    "\n",
    "where $\\theta^{(i)}$ is the $i^{th}$ sample simulated from $q(\\theta)$. The standard error for the importance sampling estimate is:\n",
    "\n",
    "$$\\text{SE}_{is} = \\frac{\\sqrt{\\sum_{i=1}^{M} [(h(\\theta^{(i)}) - \\hat{h}_{is}) w(\\theta^{(i)})]^2}}{\\sum_{i=1}^{M} w(\\theta^{(i)})}$$\n",
    "\n",
    "The efficiency of importance sampling is related to the selection of the importance sampling distribution $q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example: Beta-binomial parameter\n",
    "\n",
    "As a simple illustration of importance sampling, let's consider again the problem of estimating the paramters of the beta-binomial example. Here, we will use a multivariate T density as the simulation distribution $q$.\n",
    "\n",
    "Here are 1000 sampled values to use for approximating the posterior:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(20180125)\n",
    "theta = rmvt(4, var, mode, size=1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can obtain the probability of these values under the posterior density:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f_theta = np.array([betabin_trans(t, cancer.n, cancer.y) for t in theta])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and under the T distribution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q_theta = np.log(mvt(theta, 4, var, mode))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.sort(f_theta - q_theta)[-10:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This allows us to calculate the importance weights:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "w = np.exp(f_theta - q_theta - max(f_theta - q_theta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "notice that we have subtracted the maximum value of the differences, which normalizes the weights.\n",
    "\n",
    "Now, we can obtain estimates of the parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "theta_si = [(w*t).sum()/w.sum() for t in theta.T]\n",
    "theta_si"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, the standard error of the estimates:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "se = [np.sqrt((((theta.T[i] - theta_si[i])* w)**2).sum()/w.sum()) for i in (0,1)]\n",
    "se"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sampling Importance Resampling\n",
    "\n",
    "The importance sampling method can be modified to incorporate weighted bootstrapping, in a procedure called sampling importance resampling (SIR). As previously, we obtain a sample of size $M$ from an importance sampling distribution $q$ and calculate the corresponding weights $w(\\theta_i) = p(\\theta|y) / q(\\theta)$. \n",
    "\n",
    "Instead of directly re-weighting the samples from $q$, SIR instead transforms the weights into probabilities via:\n",
    "\n",
    "$$p_i = \\frac{w(\\theta_i)}{\\sum_{i=1}^M w(\\theta_i)}$$\n",
    "\n",
    "These probabilities are then used to re-sample their respective $\\theta_i$ values, with replacement. This implies that the resulting resamples $\\theta_i^{\\prime}$ will be distributed approximately as the posterior $p(\\theta|y)$.\n",
    "\n",
    "Using again the beta-binomial example, we can take the weights calculated above, and convert them to probabilities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p_sir = w/w.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `choice` function in `numpy.random` can be used to generate a random sample from an arbitrary 1-D array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "theta_sir = theta[np.random.choice(range(len(theta)), size=10000, p=p_sir)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig, axes = plt.subplots(2)\n",
    "_ = axes[0].hist(theta_sir.T[0], bins=30)\n",
    "_ = axes[1].hist(theta_sir.T[1], bins=30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One advantage of this approach is that one can easily extract a posterior probability interval for each parameter, simply by extracting quantiles from the resampled values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "logK_sample = theta_sir[:,0]\n",
    "logK_sample.sort()\n",
    "logK_sample[[250, 9750]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: Sensitivity analysis\n",
    "\n",
    "Perform a Bayesian sensitivity analysis by performing SIR on the stomach cancer dataset $N$ times, with one observation (a city) removed from the dataset each time. Calculate and plot posterior medians and 95% posterior intervals for each $f(\\theta|y_{(-i)})$ to visually analyze the influence of each observation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "Chapter 6 of [Givens, Geof H.; Hoeting, Jennifer A. (2012-10-09). Computational Statistics (Wiley Series in Computational Statistics)](http://www.stat.colostate.edu/computationalstatistics/)\n",
    "\n",
    "Chapter 5 of [Albert, J. (2009). Bayesian computation with R.](http://www.amazon.com/Bayesian-Computation-R-Use/dp/0387922970)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.9"
  },
  "latex_envs": {
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 0
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}