{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Dirichlet Processes\n",
"\n",
"We have seen with parametric mixture models that we can assign group labels to observations using a model, but so far we have assumed that we know how many groups there are *a priori*. What if we don't know how many groups produced the data? We often want the choice of $K$ to be **data-driven**.\n",
"\n",
"There are a number of approaches for allocating samples to groups where the number of groups is not pre-determined. We will look at two generative methods here.\n",
"\n",
"## The Bayesian Histogram\n",
"\n",
"One way to approximate an unknown density using sample observations is using a *histogram*. One way to parametrically describe a histogram is by specifying a series of knots that define the bins of a histogram:\n",
"\n",
"$$\\zeta = \\{\\zeta_i: \\zeta_1 \\lt \\zeta_2 \\lt \\ldots \\lt \\zeta_k \\}_{h=1}^k$$\n",
"\n",
"We can specify an associated probability model as:\n",
"\n",
"$$f(x) = \\sum_{h=i}^k I(\\zeta_{h-1} \\lt x \\le \\zeta_h) \\frac{\\pi_h}{\\zeta_h - \\zeta_{h-1}}$$\n",
"\n",
"where $I$ is the indicator function and $\\pi = \\pi_1, \\ldots, \\pi_k$ a probability simplex.\n",
"\n",
"We require a prior for the unknown probabilities, for which a natural choice is the *Dirichlet* distribution:\n",
"\n",
"$$f(\\mathbf{\\pi}) = \\frac{\\prod \\Gamma(\\alpha_h)}{\\Gamma(\\sum_{h=1}^k \\alpha_h)}\\prod_{h=1}^{k} \\pi_h^{\\alpha_h - 1}$$\n",
"\n",
"$$\\text{where } \\, E(\\pi|\\alpha) = \\pi_0 = \\frac{\\alpha_1}{\\sum_h \\alpha_h}, \\ldots , \\frac{\\alpha_k}{\\sum_h \\alpha_h}$$\n",
"\n",
"Notice that the Dirichlet is just a generalization of the beta distribution to $k \\gt 2$ classes.\n",
"\n",
"It is easy to show that the resulting posterior distribution for $\\pi$ is another Dirichlet:\n",
"\n",
"$$\\pi|x \\sim \\text{Dirichlet}(\\alpha_1 + n_i, \\ldots, \\alpha_k + n_k)$$\n",
"\n",
"where $n_h$ is the number of observations contained by the $h^{th}$ histogram bin."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"from matplotlib import pyplot as plt\n",
"import numpy as np\n",
"import pymc3 as pm\n",
"import scipy as sp\n",
"import seaborn as sns\n",
"import pandas as pd\n",
"from statsmodels.datasets import get_rdataset\n",
"import theano.tensor as tt\n",
"\n",
"sns.set_context('notebook')\n",
"SEED = 20090425\n",
"np.random.seed(SEED)\n",
"\n",
"BLUE, *_ = sns.color_palette()\n",
"\n",
"n = 100\n",
"y = 0.75 * np.random.beta(1, 5, n) + 0.25 * np.random.beta(20, 2, n)\n",
"\n",
"counts, bins, patches = plt.hist(y, bins=10, color=BLUE)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"counts"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can use these bin counts to calculate the expected value of the Dirichlet posterior:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = np.random.dirichlet(1+counts)\n",
"p = np.append(p, 1.-p.sum())\n",
"y_exp = n*p"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plt.hist(y, bins=10)\n",
"plt.step(bins, y_exp, color='red', where='post', linewidth=4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"While this does a good job of density approximation, the estimates are clearly sensitive to the choice of bins (both number and location):"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"counts, bins, patches = plt.hist(y, bins=20)\n",
"\n",
"p = np.random.dirichlet(1+counts) \n",
"y_exp = n*np.append(p, 1.-p.sum())\n",
"\n",
"plt.hist(y, bins=20)\n",
"plt.step(bins, y_exp, color='red', where='post', linewidth=4);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So, while this is a simple, straightforward approach to flexible density estimation, we would prefer not to have to specify bins *a priori*. Happily, with a little work, we can generalize the Dirichlet to make it more flexible\n",
"\n",
"## Dirichlet Process Prior\n",
"\n",
"Consider a sample space $\\Omega$ that we may partition into $k$ non-overlapping subsets $\\{B_1,\\ldots,B_k\\} \\in \\mathcal{B}$. We can assign a probability measure $P$ to this partition:\n",
"\n",
"$$P(B_1),\\ldots,P(B_k) = \\int_{B_1} f(x) dx, \\ldots, \\int_{B_k} f(x) dx$$\n",
"\n",
"A Dirichlet distribition would be a natural conjugate prior on these partition (bin) probabilities:\n",
"\n",
"$$P(B_1),\\ldots,P(B_k) \\sim \\text{Dirichlet}(a P_0(B_1), \\ldots, a P_0(B_k))$$\n",
"\n",
"where $P_0$ is a base probability measure and $a > 0$ can be interpreted as prior sample size, which essentially controls the amount of prior shrinkage.\n",
"\n",
"However, we want our model to be insensitive to the choice of partition and to the number of bins. The important implication of specifying this prior is that although probabilities are assigned to each bin, it does not prescribe how that probability mass is distributed across any particular bin.\n",
"\n",
"If we combine (or split) the elements of a Dirichlet distribution, it results in another Dirichlet:\n",
"\n",
"$$\\begin{aligned}\n",
"\\pi_1, \\ldots, \\pi_k &\\sim \\text{Dirichlet}(\\alpha_1, \\ldots, \\alpha_k) \\\\\n",
"\\Rightarrow \\pi_1 + \\pi_2, \\pi_3, \\ldots, \\pi_k &\\sim \\text{Dirichlet}(\\alpha_1 + \\alpha_2, \\alpha_3, \\ldots, \\alpha_k)\n",
"\\end{aligned}$$\n",
"\n",
"or generally, for partition $\\{B_1,\\ldots,B_k\\} \\in \\mathcal{B}$:\n",
"\n",
"$$\\sum_{h \\in B_1} \\pi_h, \\ldots, \\sum_{h \\in B_k} \\pi_h \\sim \\text{Dirichlet}(\\sum_{h \\in B_1} \\alpha_h, \\ldots, \\sum_{h \\in B_k} \\alpha_h)$$\n",
"\n",
"Similarly, for $\\beta_1 + \\beta_2 = 1$,\n",
"\n",
"$$\\begin{aligned}\n",
"\\pi_1, \\ldots, \\pi_k &\\sim \\text{Dirichlet}(\\alpha_1, \\ldots, \\alpha_k) \\\\\n",
"\\tau_1, \\tau_2 &\\sim \\text{Dirichlet}(\\alpha_1 \\beta_1, \\alpha_1 \\beta_2) \\\\\n",
"\\Rightarrow \\pi_1\\tau_1 + \\pi_1\\tau_2, \\pi_2, \\ldots, \\pi_k &\\sim \\text{Dirichlet}(\\alpha_1\\beta_1, \\alpha_1\\beta_2, \\alpha_2, \\alpha_3, \\ldots, \\alpha_k)\n",
"\\end{aligned}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Just as the Gaussian process is a distribution over functions, a **Dirichlet process** is a distribution over distributions (or, measure over measures). \n",
"\n",
"$$P \\sim DP(\\alpha P_0)$$\n",
"\n",
"It is centered upon the baseline probability measure $P_0$, with $\\alpha$ specifying the certainty in this baseline (*i.e.* inverse variance).\n",
"\n",
"The expectation of a DPP is:\n",
"\n",
"$$E[P(B)] = P_0(B)$$\n",
"\n",
"in other words, centered on the baseline measure, and the variance is:\n",
"\n",
"$$\\text{Var}(P(B)) = \\frac{P_0(B)(1-P_0(B))}{1 + \\alpha}$$\n",
"\n",
"It is essentially an *infinitely decimated* Dirichlet distribution. The marginal probability assigned to any subset $B$ is beta distributed:\n",
"\n",
"$$P(B) \\sim \\text{Beta}(\\alpha P_0(B), \\alpha (1-P_0(B)))$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Stick-breaking Process\n",
"\n",
"The specification of the DP above may not be intuitive, in terms of what a DP realization looks like. A generative approach for allocating observations to groups is the stick-breaking process, which involves breaking the support of a particular variable into $k$ disjoint segments. Here, we start with a \"stick\" of unit length. To \"break\" the stick, we generate random points along the stick via the following algorithm:\n",
"\n",
"1. generate a random variable $\\beta_1 \\sim Beta(1, \\alpha_0)$\n",
"2. use this random variable (which is on the unit interval) to define a break point on the stick\n",
"3. iterate $k-1$ times:\n",
" - generate $\\beta_i \\sim Beta(1, \\alpha_0)$\n",
" - identify next break point at $\\pi_i = \\beta_i \\prod_{j=1}^{i-1} (1-\\beta_j)$ (which is on the part of the stick that remains after the previous break)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This results in the creation of $k$ \"pieces\". Associated with each piece is a probability that is proportional to its length; these $k$ probabilities will have a Dirichlet distribution -- thus, the DP is a distribution over distributions. \n",
"\n",
"This process defines an **exchangeable** distribution on partitions of the stick; though there is an order to the generation of the segments, the distribution is independent of order.\n",
"\n",
"Notice that $k$ can be infinite, making $G$ an infinite mixture.\n",
"\n",
"One way to implement a stick-breaking constructive process in Python is as follows:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from numpy.random import beta\n",
"\n",
"def stick_breaking(alpha, k):\n",
" betas = beta(1, alpha, k)\n",
" remaining_pieces = np.append(1, np.cumprod(1 - betas[:-1]))\n",
" p = betas * remaining_pieces\n",
" return p/p.sum()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For example, let's construct a DP with a baseline distribution that is standard normal:\n",
"\n",
"$$P_0 = N(0,1)$$\n",
"\n",
"We take a draw of $k$ values from the baseline distribution:\n",
"\n",
"$$ \\theta_1, \\theta_2, \\ldots \\theta_k \\sim P_0 $$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"k = 25\n",
"alpha = 7\n",
"theta = np.random.normal(0, 1, k)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"then, using a stick breaking process, we can obtain a set of draws $\\beta_1, \\beta_2, \\ldots$ from a $\\text{Beta}(1,\\alpha)$. These are used to assign probabilities to the $\\theta_i$ values. As we established above, the probability of each $\\theta_i$ is calculated via:\n",
"\n",
"$$ \\pi_i = \\beta_i \\prod_{j=1}^{i-1} (1 - \\beta_j) $$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = stick_breaking(alpha, k)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"These probabilities correspond to the set of draws from the baseline distribution, where each of the latter are point masses of probability. So, the DP density function is:\n",
"\n",
"$$ P(x) = \\sum_{i=1}^{n} \\pi_i I(x=\\beta_i) $$\n",
"\n",
"where $I$ is the indicator function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = np.random.multinomial(k, p)\n",
"dp = theta[x]\n",
"dp"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = list(set(dp))\n",
"f = [(dp==i).sum() for i in x]\n",
"plt.bar(x, f, width=0.01)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So, you can see that the Dirichlet process is discrete, despite the fact that its values may be non-integer. This can be generalized to a mixture of continuous distributions, which is called a DP mixture."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here are several realizations with $k=20$ and $\\alpha=0.5$. So, there are 20 bars (sorted), and the height of the bar represents that group's probability."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"k = 20\n",
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" ax.bar(np.arange(k), np.sort(stick_breaking(alpha=0.5, k=k))[::-1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For $\\alpha=5$:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" ax.bar(np.arange(k), np.sort(stick_breaking(alpha=5, k=k))[::-1])\n",
" ax.set_ylim(0,1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For $\\alpha=25$:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" ax.bar(np.arange(k), np.sort(stick_breaking(alpha=25, k=k))[::-1])\n",
" ax.set_ylim(0,1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As $\\alpha_0$ increases, the weights (stick sizes) are more even across the samples.\n",
"\n",
"We can use the stick-breaking process to induce $P \\sim DP(\\alpha P_0)$ for some $P_0$.\n",
"\n",
"$$P(\\cdot) = \\sum_{h=1}^k \\pi_h \\delta_{\\theta_h}(\\cdot)$$\n",
"\n",
"Where the $\\pi_h$ are geenrated by stick-breaking, $\\delta_{\\theta}$ is a degenerate distribution with the entire probability mass at $\\theta$, which in turn, are generated by $P_0$; here, we will use a standard normal."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from numpy.random import choice\n",
"\n",
"def dirichlet_process(p, n, P0=np.random.randn):\n",
" theta = P0(len(p))\n",
" return np.random.choice(theta, size=n, p=p)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\alpha=0.5$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = stick_breaking(alpha=0.5, k=1000)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"_ = plt.hist(dirichlet_process(p, 100))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\alpha=5$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = stick_breaking(alpha=5, k=1000)\n",
"_ = plt.hist(dirichlet_process(p, 100))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\alpha=25$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = stick_breaking(alpha=25, k=10000)\n",
"_ = plt.hist(dirichlet_process(p, 1000))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that, while the particular values of the DP realizations are continuous, the distribution is discrete. But, as $\\alpha \\rightarrow \\infty$, the likelihood of indexing the same $\\theta_h$ more than once goes to zero, and one is essentially drawing from $P_0$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = stick_breaking(alpha=1000, k=10000)\n",
"_ = plt.hist(dirichlet_process(p, 1000))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Dirichlet Process Mixtures\n",
"\n",
"So, while the DP is of limited use as a direct prior of a data distribution, it is extremely useful as a prior for an unknown mixture.\n",
"\n",
"If we generalize the above approach such that the DP is used as the mixture measure for some kernel $\\mathcal{K}(y|\\theta)$, then we can define the mixture model:\n",
"\n",
"$$f(y) = \\sum_{h=1}^{\\infty} \\pi_h \\mathcal{K}(y|\\theta_h)$$\n",
"\n",
"This is no different than other mixture models we have seen, except that the number of components is infinite. In practice, almost all the components are empty when we consider using it to model a finite dataset, but the model has the capacity to increase the number of mixture components as data are added.\n",
"\n",
"This model can be specified hierarchically by:\n",
"\n",
"$$\\begin{aligned}\n",
"P &\\sim DP(\\alpha P_0) \\\\\n",
"\\theta_i &\\sim P \\\\\n",
"y_i &\\sim \\mathcal{K}(y|\\theta_i)\n",
"\\end{aligned}$$\n",
"\n",
"To illustrate this model, we simulate draws from a Dirichlet process mixture with $\\alpha = 2$, $\\theta \\sim N(0, 1)$, $x\\ |\\ \\theta \\sim N(\\theta, (0.3)^2)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"N = 5\n",
"K = 30\n",
"\n",
"# Concentration parameter\n",
"alpha = 2\n",
"# Baseline distribution\n",
"P0 = sp.stats.norm\n",
"# Mixture kernel PDF\n",
"def kernel(x, theta, s=0.3): \n",
" return sp.stats.norm.pdf(x, theta, s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x_plot = np.linspace(-3, 3, 200)\n",
"np.random.seed(42)\n",
"\n",
"beta = sp.stats.beta.rvs(1, alpha, size=(N, K))\n",
"w = np.empty_like(beta)\n",
"w[:, 0] = beta[:, 0]\n",
"w[:, 1:] = beta[:, 1:] * (1 - beta[:, :-1]).cumprod(axis=1)\n",
"\n",
"theta = P0.rvs(size=(N, K))\n",
"\n",
"dpm_pdf_components = kernel(x_plot[np.newaxis, np.newaxis, :], theta[..., np.newaxis])\n",
"dpm_pdfs = (w[..., np.newaxis] * dpm_pdf_components).sum(axis=1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(8, 6))\n",
"\n",
"ax.plot(x_plot, dpm_pdfs.T, c='gray');\n",
"\n",
"ax.set_yticklabels([]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now focus on a single mixture and decompose it into its individual (weighted) mixture components."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(8, 6))\n",
"\n",
"ix = 1\n",
"\n",
"ax.plot(x_plot, dpm_pdfs[ix], c='k', label='Density');\n",
"ax.plot(x_plot, (w[..., np.newaxis] * dpm_pdf_components)[ix, 0],\n",
" '--', c='k', label='Mixture components (weighted)');\n",
"ax.plot(x_plot, (w[..., np.newaxis] * dpm_pdf_components)[ix].T,\n",
" '--', c='k');\n",
"\n",
"ax.set_yticklabels([]);\n",
"ax.legend(loc=1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The computational hurdle is in how to characterize the mixture when we cannot generate infinite mixture components. For this, we will use another generative model metaphor, the *Chinese restaurant process*.\n",
"\n",
"## Chinese Restaurant Process\n",
"\n",
"Consider a hypothetical Chinese restaurant with an *infinite* number of tables. \n",
"\n",
"![chinese restaurant](images/chinese_restaurant.jpg)\n",
"\n",
"* The first customer entering the restaurant sits at the first empty table.\n",
"\n",
"* The next customer either joins the first customer with some probability $1/(1 + \\alpha), \\alpha>0$, or selects an empty table with probability $\\alpha/(1 + \\alpha)$.\n",
"\n",
"* Subsequent customers either join an occupied table with a probability proportional to the number of customers already at each table, or selects an empty table.\n",
"\n",
"This process is formalized as:\n",
"\n",
"$$p(\\theta_n | \\theta_1, \\ldots, \\theta_{n-1}) \\sim \\left(\\frac{\\alpha}{\\alpha + n - 1}\\right) P_0(\\theta_n) + \\sum_{j=1}^{n-1} \\left(\\frac{1}{\\alpha + n - 1}\\right)\\delta_{\\theta_j}$$\n",
"\n",
"This is called the *Pólya urn model*.\n",
"\n",
"Of course, the analogy here is that the customers are data and the tables are clusters. Hence, the process describes a prior on the partitioning of the data into clusters."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def chinese_restaurant_process(n, alpha):\n",
" \n",
" if n < 1:\n",
" return None\n",
" \n",
" table_assignments = np.empty(n)\n",
" next_table = 0\n",
" \n",
" for c in range(n):\n",
"\n",
" if np.random.random() < (1. * alpha / (alpha + c)):\n",
" \n",
" # Sit at new table\n",
" table_assignments[c] = next_table\n",
" next_table += 1\n",
" \n",
" else:\n",
" \n",
" # Calculate selection probabilities as function of population\n",
" probs = [(table_assignments[:c]==i).sum()/float(c) \n",
" for i in range(next_table)]\n",
" # Randomly assign to existing table\n",
" table_assignments[c] = choice(range(next_table), p=probs)\n",
" \n",
" return table_assignments"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try a few runs. First, with 10 customers:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = 10\n",
"alpha = 1\n",
"\n",
"def plot_crp(table_nums, ax=None):\n",
" x = list(range(int(table_nums.max()) + 1))\n",
" f = [(table_nums==i).sum() for i in set(table_nums)]\n",
" if ax is None: ax = plt\n",
" ax.bar(x, f)\n",
" \n",
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" plot_crp(chinese_restaurant_process(n, alpha), ax=ax)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then 100:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = 100\n",
"\n",
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" plot_crp(chinese_restaurant_process(n, alpha), ax=ax)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And 500:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"n = 500\n",
"\n",
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"for ax in np.ravel(axes):\n",
" plot_crp(chinese_restaurant_process(n, alpha), ax=ax)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that the number of occupied tables increases with $n$ (and with $\\alpha$). Hence, in the context of a prior on the number of clusters, the process is non-parametric (grows approximately as $\\mathcal{O}(\\log(n)$))."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we examine the sample draws from either the Chinese restaurant process or the stick-breaking process above, it is apparent that each sample represents a realization from the same underlying process (when the parameter values are the same). We can use either of these generative processes to generate weights for the DP.\n",
"\n",
"Alternately, we could use a CRP to generate groups (tables), where each element from the same group would be assigned the same value sampled from $P_0$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Example: Sunspots\n",
"\n",
"![sunspots](images/Sunspots_1302_Sep_2011_by_NASA.jpg)\n",
"\n",
"The Dirichlet process mixture model is incredibly flexible in terms of the family of parametric component distributions $\\{f_{\\theta}\\ |\\ f_{\\theta} \\in \\Theta\\}$. We illustrate this flexibility below by using Poisson component distributions to estimate the density of sunspots per year."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from statsmodels.datasets import get_rdataset\n",
"\n",
"sunspot_df = get_rdataset('sunspot.year', cache=True).data\n",
"sunspot_df.head()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"sunspot_df.shape"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For this example, we can specify a DP model by:\n",
"\n",
"$$\n",
"\\begin{align*}\n",
" \\alpha\n",
" & \\sim \\textrm{Gamma}(1, 1) \\\\\n",
" \\beta_1, \\ldots, \\beta_K\n",
" & \\sim \\textrm{Beta}(1, \\alpha) \\\\\n",
" w_i\n",
" & = \\beta_i \\prod_{j = i - 1}^i (1 - \\beta_j) \\\\\n",
" \\\\\n",
" \\lambda_i, \\ldots, \\lambda_K\n",
" & \\sim U(0, 300)\n",
" \\\\\n",
" x\\ |\\ w_i, \\lambda_i\n",
" & \\sim \\sum_{i = 1}^K w_i\\ \\textrm{Poisson}(\\lambda_i).\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"K = 50\n",
"N = sunspot_df.shape[0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def stick_breaking(beta):\n",
" portion_remaining = tt.concatenate([[1], tt.extra_ops.cumprod(1 - beta)[:-1]])\n",
"\n",
" return beta * portion_remaining"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with pm.Model() as ss_model:\n",
" \n",
" α = pm.Gamma('α', 1., 1.)\n",
" β = pm.Beta('β', 1, α, shape=K)\n",
" w = pm.Deterministic('w', stick_breaking(β))\n",
" \n",
" μ = pm.Uniform('μ', 0., 300., shape=K)\n",
" obs = pm.Mixture('obs', w, pm.Poisson.dist(μ), observed=sunspot_df.value)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with ss_model:\n",
" trace = pm.sample(njobs=2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pm.traceplot(trace, varnames=['α']);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that between ten and fifteen mixture components have appreciable posterior expected weight."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(8, 6))\n",
"\n",
"plot_w = np.arange(K) + 1\n",
"\n",
"ax.bar(plot_w - 0.5, trace['w'].mean(axis=0), width=1., lw=0);\n",
"\n",
"ax.set_xlim(0.5, K);\n",
"ax.set_xlabel('Component');\n",
"\n",
"ax.set_ylabel('Posterior expected mixture weight');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now calculate and plot the fitted density estimate."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x_plot = np.arange(250)\n",
"\n",
"post_pmf_contribs = sp.stats.poisson.pmf(np.atleast_3d(x_plot),\n",
" trace['μ'][:, np.newaxis, :])\n",
"post_pmfs = (trace['w'][:, np.newaxis, :] * post_pmf_contribs).sum(axis=-1)\n",
"\n",
"post_pmf_low, post_pmf_high = np.percentile(post_pmfs, [2.5, 97.5], axis=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(8, 6))\n",
"\n",
"ax.hist(sunspot_df.value.values, bins=40, normed=True, lw=0, alpha=0.75);\n",
"\n",
"ax.fill_between(x_plot, post_pmf_low, post_pmf_high,\n",
" color='gray', alpha=0.15)\n",
"ax.plot(x_plot, post_pmfs[0],\n",
" c='gray', label='Posterior sample densities');\n",
"ax.plot(x_plot, post_pmfs[-20:].T, c='gray');\n",
"ax.plot(x_plot, post_pmfs.mean(axis=0),\n",
" c='k', label='Posterior expected density');\n",
"\n",
"ax.set_xlabel('Yearly sunspot count');\n",
"ax.set_yticklabels([]);\n",
"ax.legend(loc=1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Again, we can decompose the posterior expected density into weighted mixture densities."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, ax = plt.subplots(figsize=(8, 6))\n",
"\n",
"ax.hist(sunspot_df.value.values, bins=40, normed=True, lw=0, alpha=0.75);\n",
"ax.plot(x_plot, post_pmfs.mean(axis=0),\n",
" c='k', label='Posterior expected density');\n",
"ax.plot(x_plot, (trace['w'][:, np.newaxis, :] * post_pmf_contribs).mean(axis=0)[:, 0],\n",
" '--', c='k', label='Posterior expected\\nmixture components\\n(weighted)');\n",
"ax.plot(x_plot, (trace['w'][:, np.newaxis, :] * post_pmf_contribs).mean(axis=0),\n",
" '--', c='k');\n",
"\n",
"ax.set_xlabel('Yearly sunspot count');\n",
"ax.set_yticklabels([]);\n",
"ax.legend(loc=1);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Non-parametric Random Effects in Hierarchical Models\n",
"\n",
"A standard parametric assumption in linear and hierarchical modeling is that errors or random effects are Gaussian. For example,\n",
"\n",
"$$y_i = X_i \\beta + \\epsilon_i$$\n",
"\n",
"$$\\epsilon_i \\sim f$$\n",
"\n",
"where the error distribution is typically specified as $f = N(0,\\sigma^2)$. In robust regression, this restriction is partially relaxed by assuming a Student's $t$ model, which downweights the influence of outliers, but the shape is still restrictive.\n",
"\n",
"A more flexible alternative is to use an infinite mixture of normals for $f$, using a Dirichlet process:\n",
"\n",
"$$\\begin{aligned}\n",
"P &\\sim DP(\\alpha P_0) \\\\\n",
"\\tau_i &\\sim P \\\\\n",
"\\epsilon_i &\\sim N(0, \\tau_i^{-1})\n",
"\\end{aligned}$$\n",
"\n",
"If we specify $P_0$ as $\\text{Gamma}(\\nu/2, \\nu/2)$, the corresponding DP is centered on a $t$ distribution, which still models the error distribution as unimodal and zero mean. \n",
"\n",
"In the context of hierarchical models, we may want to model individual variation in some parameter, such as a subject-varying mean:\n",
"\n",
"$$\\begin{aligned}y_{ij} &= \\mu_i + \\epsilon_{ij} \\\\\n",
"\\mu_i &\\sim f \\\\\n",
"\\epsilon_{ij} &\\sim g\n",
"\\end{aligned}$$\n",
"\n",
"where $y_{i}$ is a vector of $j = 1,\\ldots,n_i$ repreated measurements for individual $i$. In the majority of applications, both $f$ and $g$ are specified with normal distributions.\n",
"\n",
"If we want a less-restrictive form for this random effect, we can place a DP prior on the $\\mu_{i}$.\n",
"\n",
"$$\\mu_i \\sim P$$\n",
"\n",
"$$P \\sim DP(\\alpha P_0)$$\n",
"\n",
"This approach induces a latent class model on the $\\mu_i$, where there are an unknown number of clusters:\n",
"\n",
"$$\\mu_i = \\mu_{S_i}$$\n",
"\n",
"$$Pr(S_i = h) = \\pi_h$$\n",
"\n",
"where $\\pi_h$ is the probability of allocation to class $h = 1, \\ldots, \\infty$. This will result in a posterior distribution of cluster allocations (and hence, for the $\\mu_i$), since the clustering is probabilistic.\n",
"\n",
"Since we do not observe the $\\mu_i$ directly, it relies on information in the repeated measurements for each individual, so this model will not be useful for $n_i$ = 1."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example: Estimating household radon levels\n",
"\n",
"As an example of implementing Dirichlet processes for random effects, we will use the radon measurement and remediation example from [Gelman and Hill (2006)](http://amzn.to/gFfJbs). This problem uses measurements of [radon](http://en.wikipedia.org/wiki/Radon) (a carcinogenic, radioactive gas) from households in 85 counties in Minnesota to estimate the distribution of the substance across the state. This dataset has a natural hierarchical structure, with individual measurements nested within households, and households in turn nested within counties. Here, we are certainly interested in modeling the variation in counties, but do not have covariates measured at that level. Since we are more interested in the variation among counties, rather than the particular levels for each, a random effects model is appropriate. \n",
"\n",
"In the original example from Gelman and Hill, measurements are modeled as being normally distributed, with a mean that is a hierarchical function of both a county-level random effect and a fixed effect that accounted for whether houses had a basement (this is thought to increase radon levels).\n",
"\n",
"$$ y_i \\sim N(\\alpha_{j[i]} + \\beta x_i, \\sigma_y^2) $$\n",
"\t\n",
"So, in essence, each county has its own intercept, but shares a slope among all counties. This can easily be generalized to both random slopes and intercepts, but let's keep things simple, in order to focus on implementing a single random effect.\n",
"\n",
"The constraint that is applied to the intercepts in Gelman and Hill's original model is that they have a common distribution (Gaussian) that describes how they vary from the state-wide mean.\n",
"\n",
"$$ \\alpha_j \\sim N(\\mu_{\\alpha}, \\sigma_{\\alpha}^2) $$\n",
"\t\n",
"This comprises a so-called \"partial pooling\" model, whereby counties are neither constrained to have identical means (full pooling) nor are assumed to have completely independent means (no pooling); in most applications, the truth is somewhere between these two extremes. Though this is a very flexible approach to accounting for county-level variance, one might be worried about imposing such a restrictive (thin-tailed) distribution like the normal on this variance. If there are counties that have extremely low or high levels (for whatever reason), this model will fit poorly. To allay such worries, we can hedge our bets by selecting a more forgiving functional form, such as [Student's t](http://en.wikipedia.org/wiki/Student's_t-distribution) or [Cauchy](http://en.wikipedia.org/wiki/Cauchy_distribution), but these still impose parametric restrictions (*e.g.* symmetry about the mean) that we may be uncomfortable making. So, in the interest of even greater flexibility, we will replace the normal county random effect with a non-parametric alternative, using a Dirichlet process.\n",
"\n",
"First, let's import the data:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import pandas as pd\n",
"\n",
"# Import radon data\n",
"srrs2 = pd.read_csv('../data/srrs2.dat')\n",
"srrs2.columns = srrs2.columns.map(str.strip)\n",
"srrs_mn = srrs2[srrs2.state=='MN']\n",
"\n",
"counties = srrs_mn.county.values\n",
"y = srrs_mn.activity.values\n",
"x = srrs_mn.floor.values\n",
"\n",
"## gelman adjustment for log\n",
"y[y==0]=.1\n",
"y = np.log(y)\n",
"\n",
"## groupings\n",
"def createCountyIndex(counties):\n",
" counties_uniq = sorted(set(counties))\n",
" counties_dict = dict()\n",
" for i, v in enumerate(counties_uniq):\n",
" counties_dict[v] = i\n",
" ans = np.empty(len(counties),dtype='int')\n",
" for i in range(0,len(counties)):\n",
" ans[i] = counties_dict[counties[i]]\n",
" return ans\n",
"\n",
"index_c = createCountyIndex(counties)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One of the difficulties in implementing DP computationally is how to handle an infinite mixture. The easiest way to tackle this is by using a truncated Dirichlet process to approximate the full process. This can be done by choosing a size $N$ that is sufficiently large that it will exceed the number of point masses required. By doing this, we are assuming\n",
"\n",
"$$ \\sum_{i=1}^{\\infty} p_i I(x=\\theta_i) \\approx \\sum_{i=1}^{N} p_i I(x=\\theta_i) $$\n",
"\n",
"[Ohlssen et al. 2007](http://onlinelibrary.wiley.com/doi/10.1002/sim.2666/abstract) provide a rule of thumb for choosing $N$ such that the sum of the first $k-1$ point masses is greater than 0.99:\n",
"\n",
"$$ N \\approx 5\\alpha + 2 $$\n",
"\n",
"To be conservative, we will choose an even larger value (100), which we will call `N_dp`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"N_dp = 100"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We first must specify the baseline distribution and the concentration parameter. As we have no prior information to inform a choice for $\\alpha$, we will specify a uniform prior for it, with reasonable bounds:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import pymc3 as pm\n",
"\n",
"with pm.Model() as radon_model_dp:\n",
" \n",
" α = pm.Uniform('α', lower=0.5, upper=10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Though the upper bound may seem small for a prior that purports to be uninformative, recall that for large values of $\\alpha$, the DP will converge to the baseline distribution, suggesting that a continuous distribution would be more appropriate.\n",
"\n",
"Since we are extending a normal random effects model, I will choose a Gaussian baseline distribution, with vague hyperpriors:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with radon_model_dp:\n",
" \n",
" τ_0 = pm.Uniform('τ_0', 0, 100)\n",
" μ_0 = pm.Normal('μ_0', mu=0, tau=0.01)\n",
" η = pm.Normal('η', mu=0, sd=1, shape=N_dp)\n",
" \n",
" θ = pm.Deterministic('θ', μ_0 + η*τ_0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that I have specified a uniform prior on the standard deviation, rather than the more common [gamma](http://en.wikipedia.org/wiki/Gamma_distribution)-distributed precision; for hierarchical models this is [good practice](http://ba.stat.cmu.edu/journal/2006/vol01/issue03/gelman.pdf). So, now we that we have `N_dp` point masses, all that remains is to generate corresponding probabilities. Following the recipe above:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with radon_model_dp:\n",
"\n",
" v = pm.Beta('v', alpha=1, beta=α, shape=N_dp)\n",
" \n",
" p = pm.Deterministic('p', stick_breaking(v))\n",
"\n",
" # Expected value of random effect\n",
" E_dp = pm.Deterministic('E_dp', tt.dot(p, θ))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The final step involves using the Dirichlet probabilities in a normal mixture. Since we have an individual covariate, we need to use a `Potential` to specify the likelihood, and subtract the linear effect from the observed value to model the random intercepts."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with radon_model_dp:\n",
"\n",
" σ_y = pm.HalfCauchy('σ_y', 3)\n",
" b = pm.Normal('b', mu=0, sd=100)\n",
" y_adj = y - b*x\n",
" \n",
" y_like = pm.Potential('y_like', pm.NormalMixture.dist(w=p, mu=θ, sd=σ_y).logp(y_adj))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"with radon_model_dp:\n",
"\n",
" approx = pm.fit(20000)\n",
" trace = approx.sample(1000)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Substitution of the above code into Gelman and Hill's original model produces reasonable results. The expected value of $\\alpha$ is approximately 1.3, as shown by the posterior output below:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pm.traceplot(trace, varnames=['E_dp'])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plt.subplots(figsize=(6, 14))\n",
"pm.forestplot(trace, varnames=['p'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here are several random samples taken from the DP:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fig, axes = plt.subplots(2, 5, sharex=True, sharey=True, figsize=(10,6))\n",
"\n",
"for ax in np.ravel(axes):\n",
" i = np.random.randint(0, 1000)\n",
" theta = trace['θ'][i]\n",
" p = trace['p'][i]\n",
" dp = np.random.choice(theta, size=len(y), p=p)\n",
" ax.hist(dp)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercise: Random effects meta-analysis\n",
"\n",
"Recall the beta-blockers meta-analysis from Homework 2, where Carlin (1992) considers a Bayesian approach to meta-analysis, and includes examples of 22 trials of beta-blockers to prevent mortality after myocardial infarction. \n",
"\n",
"In one possible random effects model we assume the true effect (on a log-odds scale) $d_i$ in a trial $i$ is drawn from some population distribution. Let $r^C_i$ denote number of events in the control group in trial $i$, and $r^T_i$ denote events under active treatment in trial $i$. Our model is:\n",
"\n",
"$$\\begin{aligned}\n",
"r^C_i &\\sim \\text{Binomial}\\left(p^C_i, n^C_i\\right) \\\\\n",
"r^T_i &\\sim \\text{Binomial}\\left(p^T_i, n^T_i\\right) \\\\\n",
"\\text{logit}\\left(p^C_i\\right) &= \\mu \\\\\n",
"\\text{logit}\\left(p^T_i\\right) &= \\mu + \\delta_i \\\\\n",
"\\delta_i &\\sim f\n",
"\\end{aligned}$$\n",
"\n",
"Instead of assuming a Gaussian random effect $f$, experiment with Dirichlet process priors, and check whether it improves the resulting model."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"r_t_obs = [3, 7, 5, 102, 28, 4, 98, 60, 25, 138, 64, 45, 9, 57, 25, 33, 28, 8, 6, 32, 27, 22]\n",
"n_t_obs = [38, 114, 69, 1533, 355, 59, 945, 632, 278,1916, 873, 263, 291, 858, 154, 207, 251, 151, 174, 209, 391, 680]\n",
"r_c_obs = [3, 14, 11, 127, 27, 6, 152, 48, 37, 188, 52, 47, 16, 45, 31, 38, 12, 6, 3, 40, 43, 39]\n",
"n_c_obs = [39, 116, 93, 1520, 365, 52, 939, 471, 282, 1921, 583, 266, 293, 883, 147, 213, 122, 154, 134, 218, 364, 674]\n",
"N = len(n_c_obs)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Write your answer here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## References\n",
"\n",
"1. Dunson D. Bayesian nonparametric hierarchical modeling. Biometrical Journal. January 2009.\n",
"2. Rochford, A. [Density Estimation with Dirichlet Process Mixtures using PyMC3](http://austinrochford.com/posts/2016-02-25-density-estimation-dpm.html). February 25, 2016.\n",
"3. Teh, Y. W., & Jordan, M. I. (2010). [Hierarchical Bayesian nonparametric models with applications](http://www.cs.berkeley.edu/~jordan/papers/teh-jordan-bnp.pdf). Bayesian nonparametrics, 158–207."
]
}
],
"metadata": {
"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.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}