Dirichlet-multinomial distribution

Dirichlet-Multinomial

Notation	$\mathrm {DirMult} (n,{\boldsymbol {\alpha }})$
Parameters	$n>0$ number of trials (positive integer) $\alpha _{1},\ldots ,\alpha _{K}>0,\alpha _{0}=\sum \alpha _{k}$
Support	$x_{i}\in \{0,\dots ,n\}$ $\Sigma x_{i}=n\!,i=1...K$
PMF	${\frac {\Gamma \left(\alpha _{0}\right)\Gamma \left(n+1\right)}{\Gamma \left(n+\alpha _{0}\right)}}\prod _{k=1}^{K}{\frac {\Gamma (x_{k}+\alpha _{k})}{\Gamma (\alpha _{k})\Gamma \left(x_{k}+1\right)}}$
Mean	$\operatorname {E} (X_{i})=n{\frac {\alpha _{i}}{\alpha _{0}}}$
Variance	$\operatorname {Var} (X_{i})=n{\frac {\alpha _{i}}{\alpha _{0}}}\left(1-{\frac {\alpha _{i}}{\alpha _{0}}}\right)\left({\frac {n+\alpha _{0}}{1+\alpha _{0}}}\right)$ $\textstyle {\mathrm {Cov} }(X_{i},X_{k})=-n{\frac {\alpha _{i}}{\alpha _{0}}}{\frac {\alpha _{k}}{\alpha _{0}}}\left({\frac {n+\alpha _{0}}{1+\alpha _{0}}}\right)~~(i\neq k)$
MGF	$\operatorname {E} (\prod \limits _{k=1}^{K}{e}^{t_{k}\cdot x_{k}})={\frac {\Gamma (\alpha _{0})\Gamma (n+1)}{\Gamma (n+\alpha _{0})}}\cdot D_{n}({\boldsymbol {\alpha }},(e^{t_{1}},...,e^{t_{K}}))$ with $D_{n}={\frac {1}{n}}\sum \limits _{u=1}^{n}\left[\left(\sum \limits _{k=1}^{K}\alpha _{k}\cdot {e}^{t_{k}\cdot u}\right)D_{n-u}\right],D_{0}=1$
CF	$\operatorname {E} (\prod \limits _{k=1}^{K}{e}^{it_{k}\cdot x_{k}})={\frac {\Gamma (\alpha _{0})\Gamma (n+1)}{\Gamma (n+\alpha _{0})}}\cdot D_{n}({\boldsymbol {\alpha }},(e^{it_{1}},...,e^{it_{K}}))$ with $D_{n}={\frac {1}{n}}\sum \limits _{u=1}^{n}\left[\left(\sum \limits _{k=1}^{K}\alpha _{k}\cdot {e}^{it_{k}\cdot u}\right)D_{n-u}\right],D_{0}=1$
PGF	$\operatorname {E} (\prod \limits _{k=1}^{K}{z_{k}}^{x_{k}})={\frac {\Gamma (\alpha _{0})\Gamma (n+1)}{\Gamma (n+\alpha _{0})}}\cdot D_{n}({\boldsymbol {\alpha }},\mathbf {z} )$ with $D_{n}={\frac {1}{n}}\sum \limits _{u=1}^{n}\left[\left(\sum \limits _{k=1}^{K}\alpha _{k}\cdot {z_{k}}^{u}\right)D_{n-u}\right],D_{0}=1$

In probability theory and statistics, the Dirichlet-multinomial distribution is a family of discrete multivariate probability distributions on a finite support of non-negative integers. It is also called the Dirichlet compound multinomial distribution (DCM) or multivariate Pólya distribution (after George Pólya). It is a compound probability distribution, where a probability vector p is drawn from a Dirichlet distribution with parameter vector ${\boldsymbol {\alpha }}$, and an observation drawn from a multinomial distribution with probability vector p and number of trials n. The Dirichlet parameter vector captures the prior belief about the situation and can be seen as a pseudocount: observations of each outcome that occur before the actual data is collected. The compounding corresponds to a Pólya urn scheme. It is frequently encountered in Bayesian statistics, machine learning, empirical Bayes methods and classical statistics as an overdispersed multinomial distribution.

It reduces to the categorical distribution as a special case when n = 1. It also approximates the multinomial distribution arbitrarily well for large α. The Dirichlet-multinomial is a multivariate extension of the beta-binomial distribution, as the multinomial and Dirichlet distributions are multivariate versions of the binomial distribution and beta distributions, respectively.

Specification

Dirichlet-multinomial as a compound distribution

The Dirichlet distribution is a conjugate distribution to the multinomial distribution. This fact leads to an analytically tractable compound distribution. For a random vector of category counts $\mathbf {x} =(x_{1},\dots ,x_{K})$, distributed according to a multinomial distribution, the marginal distribution is obtained by integrating on the distribution for p which can be thought of as a random vector following a Dirichlet distribution:

$\Pr(\mathbf {x} \mid n,{\boldsymbol {\alpha }})=\int _{\mathbf {p} }\mathrm {Mult} (\mathbf {x} \mid n,\mathbf {p} )\mathrm {Dir} (\mathbf {p} \mid {\boldsymbol {\alpha }}){\textrm {d}}\mathbf {p}$

which results in the following explicit formula:

$\Pr(\mathbf {x} \mid n,{\boldsymbol {\alpha }})={\frac {\Gamma \left(\alpha _{0}\right)\Gamma \left(n+1\right)}{\Gamma \left(n+\alpha _{0}\right)}}\prod _{k=1}^{K}{\frac {\Gamma (x_{k}+\alpha _{k})}{\Gamma (\alpha _{k})\Gamma \left(x_{k}+1\right)}}$

where $\alpha _{0}$ is defined as the sum $\alpha _{0}=\sum \alpha _{k}$. Another form for this same compound distribution, written more compactly in terms of the beta function, B, is as follows:

$\Pr(\mathbf {x} \mid n,{\boldsymbol {\alpha }})={\frac {nB\left(\alpha _{0},n\right)}{\prod _{k:x_{k}>0}x_{k}B\left(\alpha _{k},x_{k}\right)}}.$

The latter form emphasizes the fact that zero count categories can be ignored in the calculation - a useful fact when the number of categories is very large and sparse (e.g. word counts in documents).

Observe that the pdf is the Beta-binomial distribution when $K=2$. It can also be shown that it approaches the multinomial distribution as $\alpha _{0}$ approaches infinity. The parameter $\alpha _{0}$ governs the degree of overdispersion or burstiness relative to the multinomial. Alternative choices to denote $\alpha _{0}$ found in the literature are S and A.

Dirichlet-multinomial as an urn model

The Dirichlet-multinomial distribution can also be motivated via an urn model for positive integer values of the vector ${\boldsymbol {\alpha }}$, known as the Polya urn model. Specifically, imagine an urn containing balls of $K$ colors numbering $\alpha _{i}$ for the ith color, where random draws are made. When a ball is randomly drawn and observed, then two balls of the same color are returned to the urn. If this is performed $n$ times, then the probability of observing the random vector $x$ of color counts is a Dirichlet-multinomial with parameters $n$ and ${\boldsymbol {\alpha }}$. If the random draws are with simple replacement (no balls over and above the observed ball are added to the urn), then the distribution follows a multinomial distribution and if the random draws are made without replacement, the distribution follows a multivariate hypergeometric distribution.

Properties

Moments

Once again, let $\alpha _{0}=\sum \alpha _{k}$ and let $p_{i}={\frac {\alpha _{i}}{\sum \alpha _{k}}}={\frac {\alpha _{i}}{\alpha _{0}}}$, then the expected number of times the outcome i was observed over n trials is

$\operatorname {E} (X_{i})=np_{i}=n{\frac {\alpha _{i}}{\alpha _{0}}}.\,$

The covariance matrix is as follows. Each diagonal entry is the variance of a beta-binomially distributed random variable, and is therefore

$\operatorname {var} (X_{i})=np_{i}(1-p_{i})\left({\frac {n+\sum \alpha _{k}}{1+\sum \alpha _{k}}}\right)=n{\frac {\alpha _{i}}{\alpha _{0}}}\left(1-{\frac {\alpha _{i}}{\alpha _{0}}}\right)\left({\frac {n+\alpha _{0}}{1+\alpha _{0}}}\right).\,$

The off-diagonal entries are the covariances:

$\operatorname {cov} (X_{i},X_{j})=-np_{i}p_{j}\left({\frac {n+\sum \alpha _{k}}{1+\sum \alpha _{k}}}\right)=-n{\frac {\alpha _{i}\alpha _{j}}{\alpha _{0}^{2}}}\left({\frac {n+\alpha _{0}}{1+\alpha _{0}}}\right)\,$

for i, j distinct.

All covariances are negative because for fixed n, an increase in one component of a Dirichlet-multinomial vector requires a decrease in another component.

This is a K × K positive-semidefinite matrix of rank K − 1.

The entries of the corresponding correlation matrix are

$\rho (X_{i},X_{i})=1.$

$\rho (X_{i},X_{j})={\frac {\operatorname {cov} (X_{i},X_{j})}{\sqrt {\operatorname {var} (X_{i})\operatorname {var} (X_{j})}}}={\frac {-p_{i}p_{j}({\frac {n+\alpha _{0}}{1+\alpha _{0}}})}{\sqrt {p_{i}(1-p_{i})({\frac {n+\alpha _{0}}{1+\alpha _{0}}})p_{j}(1-p_{j})({\frac {n+\alpha _{0}}{1+\alpha _{0}}})}}}=-{\sqrt {\frac {\alpha _{i}\alpha _{j}}{(\alpha _{0}-\alpha _{i})(\alpha _{0}-\alpha _{j})}}}.$

The sample size drops out of this expression.

Each of the k components separately has a beta-binomial distribution.

The support of the Dirichlet-multinomial distribution is the set

$\{(n_{1},\dots ,n_{k})\in \mathbb {N} ^{k}|n_{1}+\cdots +n_{k}=n\}.\,$

Its number of elements is

${n+k-1 \choose k-1}.$

Matrix notation

In matrix notation,

$\operatorname {E} (\mathbf {X} )=n\mathbf {p} ,\,$

and

$\operatorname {var} (\mathbf {X} )=n\lbrace \operatorname {diag} (\mathbf {p} )-\mathbf {p} \mathbf {p} ^{\rm {T}}\rbrace \left({\frac {n+\alpha _{0}}{1+\alpha _{0}}}\right),\,$

with p^T = the row vector transpose of the column vector p. Letting

$\alpha _{0}={\frac {1-\rho ^{2}}{\rho ^{2}}}\,$, we can write alternatively

$\operatorname {var} (\mathbf {X} )=n\lbrace \operatorname {diag} (\mathbf {p} )-\mathbf {p} \mathbf {p} ^{\rm {T}}\rbrace (1+\rho ^{2}(n-1)),\,$

The parameter $\rho \!$ is known as the "intra class" or "intra cluster" correlation. It is this positive correlation which gives rise to overdispersion relative to the multinomial distribution.

Aggregation

If

$X=(X_{1},\ldots ,X_{K})\sim \operatorname {DM} (\alpha _{1},\cdots ,\alpha _{K})$

then, if the random variables with subscripts i and j are dropped from the vector and replaced by their sum,

$X'=(X_{1},\ldots ,X_{i}+X_{j},\ldots ,X_{K})\sim \operatorname {DM} \left(\alpha _{1},\cdots ,\alpha _{i}+\alpha _{j},\cdots ,\alpha _{K}\right).$

This aggregation property may be used to derive the marginal distribution of $X_{i}$.

Likelihood function

Conceptually, we are making N independent draws from a categorical distribution with K categories. Let us represent the independent draws as random categorical variables $z_{n}$ for $n=1\dots N$. Let us denote the number of times a particular category $k$ has been seen (for $k=1\dots K$) among all the categorical variables as $n_{k}$, and $\sum _{k}n_{k}=N$. Then, we have two separate views onto this problem:

1. A set of $N$ categorical variables $z_{1},\dots ,z_{N}$.
2. A single vector-valued variable $\mathbf {x} =(n_{1},\dots ,n_{K})$, distributed according to a multinomial distribution.

The former case is a set of random variables specifying each individual outcome, while the latter is a variable specifying the number of outcomes of each of the K categories. The distinction is important, as the two cases have correspondingly different probability distributions.

The parameter of the categorical distribution is $\mathbf {p} =(p_{1},p_{2},\dots ,p_{K}),$ where $p_{k}$ is the probability to draw value $k$; $\mathbf {p}$ is likewise the parameter of the multinomial distribution $P(\mathbf {x} |\mathbf {p} )$. Rather than specifying $\mathbf {p}$ directly, we give it a conjugate prior distribution, and hence it is drawn from a Dirichlet distribution with parameter vector ${\boldsymbol {\alpha }}=(\alpha _{1},\alpha _{2},\ldots ,\alpha _{K})$.

By integrating out $\mathbf {p}$, we obtain a compound distribution. However, the form of the distribution is different depending on which view we take.

For a set of individual outcomes

Joint distribution

For categorical variables $\mathbb {Z} =z_{1},\dots ,z_{N}$, the marginal joint distribution is obtained by integrating out $\mathbf {p}$:

$\Pr(\mathbb {Z} \mid {\boldsymbol {\alpha }})=\int _{\mathbf {p} }\Pr(\mathbb {Z} \mid \mathbf {p} )\Pr(\mathbf {p} \mid {\boldsymbol {\alpha }}){\textrm {d}}\mathbf {p}$

which results in the following explicit formula:

$\Pr(\mathbb {Z} \mid {\boldsymbol {\alpha }})={\frac {\Gamma \left(A\right)}{\Gamma \left(N+A\right)}}\prod _{k=1}^{K}{\frac {\Gamma (n_{k}+\alpha _{k})}{\Gamma (\alpha _{k})}}$

where $\Gamma$ is the gamma function, with

$A=\sum _{k}\alpha _{k}{\text{ and }}N=\sum _{k}n_{k}{\text{, and where }}n_{k}={\text{number of }}z_{n}{\text{'s with the value }}k.$

Note the absence of the multinomial coefficient due to the formula being about the probability of a sequence of categorical variables instead of a probability on the counts within each category.

Although the variables $z_{1},\dots ,z_{N}$ do not appear explicitly in the above formula, they enter in through the $n_{k}$ values.

Conditional distribution

Another useful formula, particularly in the context of Gibbs sampling, asks what the conditional density of a given variable $z_{n}$ is, conditioned on all the other variables (which we will denote $\mathbb {Z} ^{(-n)}$). It turns out to have an extremely simple form:

$\Pr(z_{n}=k\mid \mathbb {Z} ^{(-n)},{\boldsymbol {\alpha }})\propto n_{k}^{(-n)}+\alpha _{k}$

where $n_{k}^{(-n)}$ specifies the number of counts of category $k$ seen in all variables other than $z_{n}$.

It may be useful to show how to derive this formula. In general, conditional distributions are proportional to the corresponding joint distributions, so we simply start with the above formula for the joint distribution of all the $z_{1},\dots ,z_{N}$ values and then eliminate any factors not dependent on the particular $z_{n}$ in question. To do this, we make use of the notation $n_{k}^{(-n)}$ defined above, and

$n_{j}={\begin{cases}n_{j}^{(-n)},&{\text{if }}j\not =k\\n_{j}^{(-n)}+1,&{\text{if }}j=k\end{cases}}$

We also use the fact that

$\Gamma (n+1)=n\Gamma (n)$

Then:

${\begin{aligned}&\Pr(z_{n}=k\mid \mathbb {Z} ^{(-n)},{\boldsymbol {\alpha }})\\\propto \ &\Pr(z_{n}=k,\mathbb {Z} ^{(-n)}\mid {\boldsymbol {\alpha }})\\=\ &\ {\frac {\Gamma \left(A\right)}{\Gamma \left(N+A\right)}}\prod _{j=1}^{K}{\frac {\Gamma (n_{j}+\alpha _{j})}{\Gamma (\alpha _{j})}}\\\propto \ &\prod _{j=1}^{K}\Gamma (n_{j}+\alpha _{j})\\=\ &\Gamma (n_{k}+\alpha _{k})\prod _{j\not =k}\Gamma (n_{j}+\alpha _{j})\\=\ &\Gamma (n_{k}^{(-n)}+1+\alpha _{k})\prod _{j\not =k}\Gamma (n_{j}^{(-n)}+\alpha _{j})\\=\ &(n_{k}^{(-n)}+\alpha _{k})\Gamma (n_{k}^{(-n)}+\alpha _{k})\prod _{j\not =k}\Gamma (n_{j}^{(-n)}+\alpha _{j})\\=\ &(n_{k}^{(-n)}+\alpha _{k})\prod _{j}\Gamma (n_{j}^{(-n)}+\alpha _{j})\\\propto \ &n_{k}^{(-n)}+\alpha _{k}\\\end{aligned}}$

In general, it is not necessary to worry about the normalizing constant at the time of deriving the equations for conditional distributions. The normalizing constant will be determined as part of the algorithm for sampling from the distribution (see Categorical distribution#Sampling). However, when the conditional distribution is written in the simple form above, it turns out that the normalizing constant assumes a simple form:

$\sum _{k}\left(n_{k}^{(-n)}+\alpha _{k}\right)=A+\sum _{k}n_{k}^{(-n)}=A+N-1$

Hence

$\Pr(z_{n}=k\mid \mathbb {Z} ^{(-n)},{\boldsymbol {\alpha }})={\frac {n_{k}^{(-n)}+\alpha _{k}}{A+N-1}}$

This formula is closely related to the Chinese restaurant process, which results from taking the limit as $K\to \infty$.

In a Bayesian network

In a larger Bayesian network in which categorical (or so-called "multinomial") distributions occur with Dirichlet distribution priors as part of a larger network, all Dirichlet priors can be collapsed provided that the only nodes depending on them are categorical distributions. The collapsing happens for each Dirichlet-distribution node separately from the others, and occurs regardless of any other nodes that may depend on the categorical distributions. It also occurs regardless of whether the categorical distributions depend on nodes additional to the Dirichlet priors (although in such a case, those other nodes must remain as additional conditioning factors). Essentially, all of the categorical distributions depending on a given Dirichlet-distribution node become connected into a single Dirichlet-multinomial joint distribution defined by the above formula. The joint distribution as defined this way will depend on the parent(s) of the integrated-out Dirichet prior nodes, as well as any parent(s) of the categorical nodes other than the Dirichlet prior nodes themselves.

In the following sections, we discuss different configurations commonly found in Bayesian networks. We repeat the probability density from above, and define it using the symbol $\operatorname {DirMult} (\mathbb {Z} \mid {\boldsymbol {\alpha }})$:

$\Pr(\mathbb {Z} \mid {\boldsymbol {\alpha }})=\operatorname {DirMult} (\mathbb {Z} \mid {\boldsymbol {\alpha }})={\frac {\Gamma \left(\sum _{k}\alpha _{k}\right)}{\Gamma \left(\sum _{k}n_{k}+\alpha _{k}\right)}}\prod _{k=1}^{K}{\frac {\Gamma (n_{k}+\alpha _{k})}{\Gamma (\alpha _{k})}}$

Multiple Dirichlet priors with the same hyperprior

Imagine we have a hierarchical model as follows:

${\begin{array}{lcl}{\boldsymbol {\alpha }}&\sim &{\text{some distribution}}\\{\boldsymbol {\theta }}_{d=1\dots M}&\sim &\operatorname {Dirichlet} _{K}({\boldsymbol {\alpha }})\\z_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {Categorical} _{K}({\boldsymbol {\theta }}_{d})\end{array}}$

In cases like this, we have multiple Dirichet priors, each of which generates some number of categorical observations (possibly a different number for each prior). The fact that they are all dependent on the same hyperprior, even if this is a random variable as above, makes no difference. The effect of integrating out a Dirichlet prior links the categorical variables attached to that prior, whose joint distribution simply inherits any conditioning factors of the Dirichlet prior. The fact that multiple priors may share a hyperprior makes no difference:

$\Pr(\mathbb {Z} \mid {\boldsymbol {\alpha }})=\prod _{d}\operatorname {DirMult} (\mathbb {Z} _{d}\mid {\boldsymbol {\alpha }})$

where $\mathbb {Z} _{d}$ is simply the collection of categorical variables dependent on prior d.

Accordingly, the conditional probability distribution can be written as follows:

$\Pr(z_{dn}=k\mid \mathbb {Z} ^{(-dn)},{\boldsymbol {\alpha }})\ \propto \ n_{k,d}^{(-n)}+\alpha _{k}$

where $n_{k,d}^{(-n)}$ specifically means the number of variables among the set $\mathbb {Z} _{d}$, excluding $z_{dn}$ itself, that have the value $k$ .

It is necessary to count only the variables having the value k that are tied together to the variable in question through having the same prior. We do not want to count any other variables also having the value k.

Multiple Dirichlet priors with the same hyperprior, with dependent children

Now imagine a slightly more complicated hierarchical model as follows:

${\begin{array}{lcl}{\boldsymbol {\alpha }}&\sim &{\text{some distribution}}\\{\boldsymbol {\theta }}_{d=1\dots M}&\sim &\operatorname {Dirichlet} _{K}({\boldsymbol {\alpha }})\\z_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {Categorical} _{K}({\boldsymbol {\theta }}_{d})\\{\boldsymbol {\phi }}&\sim &{\text{some other distribution}}\\w_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {F} (w_{dn}\mid z_{dn},{\boldsymbol {\phi }})\end{array}}$

This model is the same as above, but in addition, each of the categorical variables has a child variable dependent on it. This is typical of a mixture model.

Again, in the joint distribution, only the categorical variables dependent on the same prior are linked into a single Dirichlet-multinomial:

$\Pr(\mathbb {Z} ,\mathbb {W} \mid {\boldsymbol {\alpha }},{\boldsymbol {\phi }})=\prod _{d}\operatorname {DirMult} (\mathbb {Z} _{d}\mid {\boldsymbol {\alpha }})\prod _{d=1}^{M}\prod _{n=1}^{N_{d}}\operatorname {F} (w_{dn}\mid z_{dn},{\boldsymbol {\phi }})$

The conditional distribution of the categorical variables dependent only on their parents and ancestors would have the identical form as above in the simpler case. However, in Gibbs sampling it is necessary to determine the conditional distribution of a given node $z_{dn}$ dependent not only on $\mathbb {Z} ^{(-dn)}$ and ancestors such as $\alpha$ but on all the other parameters.

The simplified expression for the conditional distribution is derived above simply by rewriting the expression for the joint probability and removing constant factors. Hence, the same simplification would apply in a larger joint probability expression such as the one in this model, composed of Dirichlet-multinomial densities plus factors for many other random variables dependent on the values of the categorical variables.

This yields the following:

$\Pr(z_{dn}=k\mid \mathbb {Z} ^{(-dn)},\mathbb {W} ,{\boldsymbol {\alpha }},{\boldsymbol {\phi }})\ \propto \ (n_{k,d}^{(-n)}+\alpha _{k})\operatorname {F} (w_{dn}\mid z_{dn},{\boldsymbol {\phi }})$

Here the probability density of $\operatorname {F}$ appears directly. To do random sampling over $z_{dn}$, we would compute the unnormalized probabilities for all K possibilities for $z_{dn}$ using the above formula, then normalize them and proceed as normal using the algorithm described in the categorical distribution article.

Correctly speaking, the additional factor that appears in the conditional distribution is derived not from the model specification but directly from the joint distribution. This distinction is important when considering models where a given node with Dirichlet-prior parent has multiple dependent children, particularly when those children are dependent on each other (e.g. if they share a parent that is collapsed out). This is discussed more below.

Multiple Dirichlet priors with shifting prior membership

Now imagine we have a hierarchical model as follows:

${\begin{array}{lcl}{\boldsymbol {\theta }}&\sim &{\text{some distribution}}\\z_{n=1\dots N}&\sim &\operatorname {Categorical} _{K}({\boldsymbol {\theta }})\\{\boldsymbol {\alpha }}&\sim &{\text{some distribution}}\\{\boldsymbol {\phi }}_{k=1\dots K}&\sim &\operatorname {Dirichlet} _{V}({\boldsymbol {\alpha }})\\w_{n=1\dots N}&\sim &\operatorname {Categorical} _{V}({\boldsymbol {\phi }}_{z_{n}})\\\end{array}}$

Here we have a tricky situation where we have multiple Dirichlet priors as before and a set of dependent categorical variables, but the relationship between the priors and dependent variables isn't fixed, unlike before. Instead, the choice of which prior to use is dependent on another random categorical variable. This occurs, for example, in topic models, and indeed the names of the variables above are meant to correspond to those in latent Dirichlet allocation. In this case, the set $\mathbb {W}$ is a set of words, each of which is drawn from one of $K$ possible topics, where each topic is a Dirichlet prior over a vocabulary of $V$ possible words, specifying the frequency of different words in the topic. However, the topic membership of a given word isn't fixed; rather, it's determined from a set of latent variables $\mathbb {Z}$. There is one latent variable per word, a $K$ -dimensional categorical variable specifying the topic the word belongs to.

In this case, all variables dependent on a given prior are tied together (i.e. correlated) in a group, as before — specifically, all words belonging to a given topic are linked. In this case, however, the group membership shifts, in that the words are not fixed to a given topic but the topic depends on the value of a latent variable associated with the word. However, the definition of the Dirichlet-multinomial density doesn't actually depend on the number of categorical variables in a group (i.e. the number of words in the document generated from a given topic), but only on the counts of how many variables in the group have a given value (i.e. among all the word tokens generated from a given topic, how many of them are a given word). Hence, we can still write an explicit formula for the joint distribution:

$\Pr(\mathbb {W} \mid {\boldsymbol {\alpha }},\mathbb {Z} )=\prod _{k=1}^{K}\operatorname {DirMult} (\mathbb {W} _{k}\mid \mathbb {Z} ,{\boldsymbol {\alpha }})=\prod _{k=1}^{K}\left[{\frac {\Gamma \left(\sum _{v}\alpha _{v}\right)}{\Gamma \left(\sum _{v}n_{v}^{k}+\alpha _{v}\right)}}\prod _{v=1}^{V}{\frac {\Gamma (n_{v}^{k}+\alpha _{v})}{\Gamma (\alpha _{v})}}\right]$

Here we use the notation $n_{v}^{k}$ to denote the number of word tokens whose value is word symbol v and which belong to topic k.

The conditional distribution still has the same form:

$\Pr(w_{n}=v\mid \mathbb {W} ^{(-n)},\mathbb {Z} ,{\boldsymbol {\alpha }})\ \propto \ n_{v}^{k,(-n)}+\alpha _{v}$

Here again, only the categorical variables for words belonging to a given topic are linked (even though this linking will depend on the assignments of the latent variables), and hence the word counts need to be over only the words generated by a given topic. Hence the symbol $n_{v}^{k,(-n)}$, which is the count of words tokens having the word symbol v, but only among those generated by topic k, and excluding the word itself whose distribution is being described.

(The reason why excluding the word itself is necessary, and why it even makes sense at all, is that in a Gibbs sampling context, we repeatedly resample the values of each random variable, after having run through and sampled all previous variables. Hence the variable will already have a value, and we need to exclude this existing value from the various counts that we make use of.)

A combined example: LDA topic models

We now show how to combine some of the above scenarios to demonstrate how to Gibbs sample a real-world model, specifically a smoothed latent Dirichlet allocation (LDA) topic model.

The model is as follows:

${\begin{array}{lcl}{\boldsymbol {\alpha }}&\sim &{\text{A Dirichlet hyperprior, either a constant or a random variable}}\\{\boldsymbol {\beta }}&\sim &{\text{A Dirichlet hyperprior, either a constant or a random variable}}\\{\boldsymbol {\theta }}_{d=1\dots M}&\sim &\operatorname {Dirichlet} _{K}({\boldsymbol {\alpha }})\\{\boldsymbol {\phi }}_{k=1\dots K}&\sim &\operatorname {Dirichlet} _{V}({\boldsymbol {\beta }})\\z_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {Categorical} _{K}({\boldsymbol {\theta }}_{d})\\w_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {Categorical} _{V}({\boldsymbol {\phi }}_{z_{dn}})\\\end{array}}$

Essentially we combine the previous three scenarios: We have categorical variables dependent on multiple priors sharing a hyperprior; we have categorical variables with dependent children (the latent variable topic identities); and we have categorical variables with shifting membership in multiple priors sharing a hyperprior. In the standard LDA model, the words are completely observed, and hence we never need to resample them. (However, Gibbs sampling would equally be possible if only some or none of the words were observed. In such a case, we would want to initialize the distribution over the words in some reasonable fashion — e.g. from the output of some process that generates sentences, such as a machine translation model — in order for the resulting posterior latent variable distributions to make any sense.)

Using the above formulas, we can write down the conditional probabilities directly:

${\begin{array}{lcl}\Pr(w_{dn}=v\mid \mathbb {W} ^{(-dn)},\mathbb {Z} ,{\boldsymbol {\beta }})\ &\propto \ &\#\mathbb {W} _{v}^{k,(-dn)}+\beta _{v}\\\Pr(z_{dn}=k\mid \mathbb {Z} ^{(-dn)},w_{dn}=v,\mathbb {W} ^{(-dn)},{\boldsymbol {\alpha }})\ &\propto \ &(\#\mathbb {Z} _{k}^{d,(-dn)}+\alpha _{k})\Pr(w_{dn}=v\mid \mathbb {W} ^{(-dn)},\mathbb {Z} ,{\boldsymbol {\beta }})\\\end{array}}$

Here we have defined the counts more explicitly to clearly separate counts of words and counts of topics:

${\begin{array}{lcl}\#\mathbb {W} _{v}^{k,(-dn)}&=&{\text{number of words having value }}v{\text{ among topic }}k{\text{ excluding }}w_{dn}\\\#\mathbb {Z} _{k}^{d,(-dn)}&=&{\text{number of topics having value }}k{\text{ among document }}d{\text{ excluding }}z_{dn}\\\end{array}}$

As in the scenario above with categorical variables with dependent children, the conditional probability of those dependent children appears in the definition of the parent's conditional probability. In this case, each latent variable has only a single dependent child word, so only one such term appears. (If there were multiple dependent children, all would have to appear in the parent's conditional probability, regardless of whether there was overlap between different parents and the same children, i.e. regardless of whether the dependent children of a given parent also have other parents. In a case where a child has multiple parents, the conditional probability for that child appears in the conditional probability definition of each of its parents.)

The definition above specifies only the unnormalized conditional probability of the words, while the topic conditional probability requires the actual (i.e. normalized) probability. Hence we have to normalize by summing over all word symbols:

${\begin{array}{rcl}\Pr(z_{dn}=k\mid \mathbb {Z} ^{(-dn)},w_{dn}=v,\mathbb {W} ^{(-dn)},{\boldsymbol {\alpha }})\ &\propto \ &{\bigl (}\#\mathbb {Z} _{k}^{d,(-dn)}+\alpha _{k}{\bigr )}{\dfrac {\#\mathbb {W} _{v}^{k,(-dn)}+\beta _{v}}{\sum _{v'=1}^{V}(\#\mathbb {W} _{v'}^{k,(-dn)}+\beta _{v'})}}\\&&\\&=&{\bigl (}\#\mathbb {Z} _{k}^{d,(-dn)}+\alpha _{k}{\bigr )}{\dfrac {\#\mathbb {W} _{v}^{k,(-dn)}+\beta _{v}}{\#\mathbb {W} ^{k}+B-1}}\end{array}}$

where

${\begin{array}{lcl}\#\mathbb {W} ^{k}&=&{\text{number of words generated by topic }}k\\B&=&\sum _{v=1}^{V}\beta _{v}\\\end{array}}$

It's also worth making another point in detail, which concerns the second factor above in the conditional probability. Remember that the conditional distribution in general is derived from the joint distribution, and simplified by removing terms not dependent on the domain of the conditional (the part on the left side of the vertical bar). When a node $z$ has dependent children, there will be one or more factors $\operatorname {F} (\dots \mid z)$ in the joint distribution that are dependent on $z$. Usually there is one factor for each dependent node, and it has the same density function as the distribution appearing the mathematical definition. However, if a dependent node has another parent as well (a co-parent), and that co-parent is collapsed out, then the node will become dependent on all other nodes sharing that co-parent, and in place of multiple terms for each such node, the joint distribution will have only one joint term. We have exactly that situation here. Even though $z_{dn}$ has only one child $w_{dn}$, that child has a Dirichlet co-parent that we have collapsed out, which induces a Dirichlet-multinomial over the entire set of nodes $\mathbb {W} ^{k}$.

It happens in this case that this issue does not cause major problems, precisely because of the one-to-one relationship between $z_{dn}$ and $w_{dn}$. We can rewrite the joint distribution as follows:

${\begin{array}{lcl}p(\mathbb {W} ^{k}\mid z_{dn})&=&p(w_{dn}\mid \mathbb {W} ^{k,(-dn)},z_{dn})\,p(\mathbb {W} ^{k,(-dn)}\mid z_{dn})\\&=&p(w_{dn}\mid \mathbb {W} ^{k,(-dn)},z_{dn})\,p(\mathbb {W} ^{k,(-dn)})\\&\sim &p(w_{dn}\mid \mathbb {W} ^{k,(-dn)},z_{dn})\end{array}}$

where in the set $\mathbb {W} ^{k,(-dn)}$ (i.e. the set of nodes $\mathbb {W} ^{k}$ excluding $w_{dn}$ ), none of the nodes have $z_{dn}$ as a parent. Hence it can be eliminated as a conditioning factor (line 2), meaning that the entire factor can be eliminated from the conditional distribution (line 3).

A second example: Naive Bayes document clustering

Here is another model, with a different set of issues. This is an implementation of an unsupervised Naive Bayes model for document clustering. That is, we would like to classify documents into multiple categories (e.g. "spam" or "non-spam", or "scientific journal article", "newspaper article about finance", "newspaper article about politics", "love letter") based on textual content. However, we don't already know the correct category of any documents; instead, we want to cluster them based on mutual similarities. (For example, a set of scientific articles will tend to be similar to each other in word use but very different from a set of love letters.) This is a type of unsupervised learning. (The same technique can be used for doing semi-supervised learning, i.e. where we know the correct category of some fraction of the documents and would like to use this knowledge to help in clustering the remaining documents.)

The model is as follows:

${\begin{array}{lcl}{\boldsymbol {\alpha }}&\sim &{\text{A Dirichlet hyperprior, either a constant or a random variable}}\\{\boldsymbol {\beta }}&\sim &{\text{A Dirichlet hyperprior, either a constant or a random variable}}\\{\boldsymbol {\theta }}_{d=1\dots M}&\sim &\operatorname {Dirichlet} _{K}({\boldsymbol {\alpha }})\\{\boldsymbol {\phi }}_{k=1\dots K}&\sim &\operatorname {Dirichlet} _{V}({\boldsymbol {\beta }})\\z_{d=1\dots M}&\sim &\operatorname {Categorical} _{K}({\boldsymbol {\theta }}_{d})\\w_{d=1\dots M,n=1\dots N_{d}}&\sim &\operatorname {Categorical} _{V}({\boldsymbol {\phi }}_{z_{d}})\\\end{array}}$

In many ways, this model is very similar to the LDA topic model described above, but it assumes one topic per document rather than one topic per word, with a document consisting of a mixture of topics. This can be seen clearly in the above model, which is identical to the LDA model except that there is only one latent variable per document instead of one per word. Once again, we assume that we are collapsing all of the Dirichlet priors.

The conditional probability for a given word is almost identical to the LDA case. Once again, all words generated by the same Dirichlet prior are interdependent. In this case, this means the words of all documents having a given label — again, this can vary depending on the label assignments, but all we care about is the total counts. Hence:

${\begin{array}{lcl}\Pr(w_{dn}=v\mid \mathbb {W} ^{(-dn)},\mathbb {Z} ,{\boldsymbol {\beta }})\ &\propto \ &\#\mathbb {W} _{v}^{k,(-dn)}+\beta _{v}\\\end{array}}$

where

${\begin{array}{lcl}\#\mathbb {W} _{v}^{k,(-dn)}&=&{\text{number of words having value }}v{\text{ among documents with label }}k{\text{ excluding }}w_{dn}\\\end{array}}$

However, there is a critical difference in the conditional distribution of the latent variables for the label assignments, which is that a given label variable has multiple children nodes instead of just one — in particular, the nodes for all the words in the label's document. This relates closely to the discussion above about the factor $\operatorname {F} (\dots \mid z_{d})$ that stems from the joint distribution. In this case, the joint distribution needs to be taken over all words in all documents containing a label assignment equal to the value of $z_{d}$, and has the value of a Dirichlet-multinomial distribution. Furthermore, we cannot reduce this joint distribution down to a conditional distribution over a single word. Rather, we can reduce it down only to a smaller joint conditional distribution over the words in the document for the label in question, and hence we cannot simplify it using the trick above that yields a simple sum of expected count and prior. Although it is in fact possible to rewrite it as a product of such individual sums, the number of factors is very large, and is not clearly more efficient than directly computing the Dirichlet-multinomial distribution probability.

Related distributions

The one-dimensional version of the Dirichlet-multinomial distribution is known as the Beta-binomial distribution.

The Dirichlet-multinomial distribution has a relationship with the negative binomial distribution analogous to the relationship of the multinomial distribution with the Poisson distribution.

Uses

The Dirichlet-multinomial distribution is used in automated document classification and clustering, genetics, economy, combat modeling, and quantitative marketing.

See also

• Beta-binomial distribution
• Chinese restaurant process
• Stars and bars (combinatorics)
• Dirichlet process
• Generalized Dirichlet distribution
• Krichevsky–Trofimov estimator
• Dirichlet negative multinomial distribution

References

Sources

• Elkan, C. (2006) Clustering documents with an exponential-family approximation of the Dirichlet compound multinomial distribution. ICML, 289–296.
• Johnson, N. L., Kotz, S. and Balakrishnan, N. (1997) Discrete multivariate distributions (Vol. 165). New York: Wiley.
• Kvam, P. and Day, D. (2001) The multivariate Polya distribution in combat modeling. Naval Research Logistics, 48, 1–17.
• Madsen, R. E., Kauchak, D. and Elkan, C. (2005) Modeling Word Burstiness Using the Dirichlet Distribution. ICML, 545–552.
• Minka, T. (2003) Estimating a Dirichlet distribution. Technical report Microsoft Research. Includes Matlab code for fitting distributions to data.
• Mosimann, J. E. (1962) On the compound multinomial distribution, the multivariate β-distribution, and correlations among proportions. Biometrika, 49(1–2), 65–82.
• Wagner, U. and Taudes, A. (1986) A Multivariate Polya Model of Brand Choice and Purchase Incidence. Marketing Science, 5(3), 219–244.