Categorical distribution
Parameters |
number of categories (integer) event probabilities | ||
---|---|---|---|
Support | |||
PMF |
(1)
| ||
Mode |
In
The categorical distribution is the generalization of the Bernoulli distribution for a categorical random variable, i.e. for a discrete variable with more than two possible outcomes, such as the roll of a dice. On the other hand, the categorical distribution is a special case of the multinomial distribution, in that it gives the probabilities of potential outcomes of a single drawing rather than multiple drawings.
Terminology
Occasionally, the categorical distribution is termed the "discrete distribution". However, this properly refers not to one particular family of distributions but to a
In some fields, such as machine learning and natural language processing, the categorical and multinomial distributions are conflated, and it is common to speak of a "multinomial distribution" when a "categorical distribution" would be more precise.[2] This imprecise usage stems from the fact that it is sometimes convenient to express the outcome of a categorical distribution as a "1-of-K" vector (a vector with one element containing a 1 and all other elements containing a 0) rather than as an integer in the range 1 to K; in this form, a categorical distribution is equivalent to a multinomial distribution for a single observation (see below).
However, conflating the categorical and multinomial distributions can lead to problems. For example, in a
Formulating distributions
A categorical distribution is a discrete probability distribution whose sample space is the set of k individually identified items. It is the generalization of the Bernoulli distribution for a categorical random variable.
In one formulation of the distribution, the sample space is taken to be a finite sequence of integers. The exact integers used as labels are unimportant; they might be {0, 1, ..., k − 1} or {1, 2, ..., k} or any other arbitrary set of values. In the following descriptions, we use {1, 2, ..., k} for convenience, although this disagrees with the convention for the Bernoulli distribution, which uses {0, 1}. In this case, the probability mass function f is:
where , represents the probability of seeing element i and .
Another formulation that appears more complex but facilitates mathematical manipulations is as follows, using the Iverson bracket:[3]
where evaluates to 1 if , 0 otherwise. There are various advantages of this formulation, e.g.:
- It is easier to write out the independent identically distributedcategorical variables.
- It connects the categorical distribution with the related multinomial distribution.
- It shows why the posterior distributionof the parameters to be calculated.
Yet another formulation makes explicit the connection between the categorical and multinomial distributions by treating the categorical distribution as a special case of the multinomial distribution in which the parameter n of the multinomial distribution (the number of sampled items) is fixed at 1. In this formulation, the sample space can be considered to be the set of 1-of-K encoded[4] random vectors x of dimension k having the property that exactly one element has the value 1 and the others have the value 0. The particular element having the value 1 indicates which category has been chosen. The probability mass function f in this formulation is:
where represents the probability of seeing element i and . This is the formulation adopted by Bishop.[4][note 1]
Properties
- The distribution is completely given by the probabilities associated with each number i: , i = 1,...,k, where . The possible sets of probabilities are exactly those in the standard -dimensional simplex; for k = 2 this reduces to the possible probabilities of the Bernoulli distribution being the 1-simplex,
- The distribution is a special case of a "multivariate Bernoulli distribution"[5] in which exactly one of the k 0-1 variables takes the value one.
- Let be the realisation from a categorical distribution. Define the random vector Y as composed of the elements:
- where I is the indicator function. Then Y has a distribution which is a special case of the multinomial distribution with parameter . The sum of independent and identically distributed such random variables Y constructed from a categorical distribution with parameter is multinomially distributed with parameters and
- The conjugate prior distribution of a categorical distribution is a Dirichlet distribution.[2] See the section below for more discussion.
- The sufficient statistic from n independent observations is the set of counts (or, equivalently, proportion) of observations in each category, where the total number of trials (=n) is fixed.
- The indicator function of an observation having a value i, equivalent to the Iverson bracket function or the Kronecker delta function is Bernoulli distributed with parameter
Bayesian inference using conjugate prior
In
Formally, this can be expressed as follows. Given a model
then the following holds:[2]
This relationship is used in
Further intuition comes from the expected value of the posterior distribution (see the article on the Dirichlet distribution):
This says that the expected probability of seeing a category i among the various discrete distributions generated by the posterior distribution is simply equal to the proportion of occurrences of that category actually seen in the data, including the pseudocounts in the prior distribution. This makes a great deal of intuitive sense: if, for example, there are three possible categories, and category 1 is seen in the observed data 40% of the time, one would expect on average to see category 1 40% of the time in the posterior distribution as well.
(This intuition is ignoring the effect of the prior distribution. Furthermore, the posterior is a distribution over distributions. The posterior distribution in general describes the parameter in question, and in this case the parameter itself is a discrete probability distribution, i.e. the actual categorical distribution that generated the data. For example, if 3 categories in the ratio 40:5:55 are in the observed data, then ignoring the effect of the prior distribution, the true parameter – i.e. the true, underlying distribution that generated our observed data – would be expected to have the average value of (0.40,0.05,0.55), which is indeed what the posterior reveals. However, the true distribution might actually be (0.35,0.07,0.58) or (0.42,0.04,0.54) or various other nearby possibilities. The amount of uncertainty involved here is specified by the variance of the posterior, which is controlled by the total number of observations – the more data observed, the less uncertainty about the true parameter.)
(Technically, the prior parameter should actually be seen as representing prior observations of category . Then, the updated posterior parameter represents posterior observations. This reflects the fact that a Dirichlet distribution with has a completely flat shape — essentially, a
MAP estimation
The maximum-a-posteriori estimate of the parameter p in the above model is simply the mode of the posterior Dirichlet distribution, i.e.,[2]
In many practical applications, the only way to guarantee the condition that is to set for all i.
Marginal likelihood
In the above model, the
This distribution plays an important role in
Posterior predictive distribution
The posterior predictive distribution of a new observation in the above model is the distribution that a new observation would take given the set of N categorical observations. As shown in the Dirichlet-multinomial distribution article, it has a very simple form:[2]
There are various relationships among this formula and the previous ones:
- The posterior predictive probability of seeing a particular category is the same as the relative proportion of previous observations in that category (including the pseudo-observations of the prior). This makes logical sense — intuitively, we would expect to see a particular category according to the frequency already observed of that category.
- The posterior predictive probability is the same as the expected value of the posterior distribution. This is explained more below.
- As a result, this formula can be expressed as simply "the posterior predictive probability of seeing a category is proportional to the total observed count of that category", or as "the expected count of a category is the same as the total observed count of the category", where "observed count" is taken to include the pseudo-observations of the prior.
The reason for the equivalence between posterior predictive probability and the expected value of the posterior distribution of p is evident with re-examination of the above formula. As explained in the posterior predictive distribution article, the formula for the posterior predictive probability has the form of an expected value taken with respect to the posterior distribution:
The crucial line above is the third. The second follows directly from the definition of expected value. The third line is particular to the categorical distribution, and follows from the fact that, in the categorical distribution specifically, the expected value of seeing a particular value i is directly specified by the associated parameter pi. The fourth line is simply a rewriting of the third in a different notation, using the notation farther up for an expectation taken with respect to the posterior distribution of the parameters.
Observe data points one by one and each time consider their predictive probability before observing the data point and updating the posterior. For any given data point, the probability of that point assuming a given category depends on the number of data points already in that category. In this scenario, if a category has a high frequency of occurrence, then new data points are more likely to join that category — further enriching the same category. This type of scenario is often termed a preferential attachment (or "rich get richer") model. This models many real-world processes, and in such cases the choices made by the first few data points have an outsize influence on the rest of the data points.
Posterior conditional distribution
In
That is, for a set of nodes , if the node in question is denoted as and the remainder as , then
where is the number of nodes having category i among the nodes other than node n.
Sampling
There are a number of
Assume a distribution is expressed as "proportional to" some expression, with unknown normalizing constant. Before taking any samples, one prepares some values as follows:
- Compute the unnormalized value of the distribution for each category.
- Sum them up and divide each value by this sum, in order to normalize them.
- Impose some sort of order on the categories (e.g. by an index that runs from 1 to k, where k is the number of categories).
- Convert the values to a cumulative distribution function (CDF) by replacing each value with the sum of all of the previous values. This can be done in time O(k). The resulting value for the first category will be 0.
Then, each time it is necessary to sample a value:
- Pick a uniformly distributednumber between 0 and 1.
- Locate the greatest number in the CDF whose value is less than or equal to the number just chosen. This can be done in time O(log(k)), by binary search.
- Return the category corresponding to this CDF value.
If it is necessary to draw many values from the same categorical distribution, the following approach is more efficient. It draws n samples in O(n) time (assuming an O(1) approximation is used to draw values from the binomial distribution[6]).
function draw_categorical(n) // where n is the number of samples to draw from the categorical distribution r = 1 s = 0 for i from 1 to k // where k is the number of categories v = draw from a binomial(n, p[i] / r) distribution // where p[i] is the probability of category i for j from 1 to v z[s++] = i // where z is an array in which the results are stored n = n - v r = r - p[i] shuffle (randomly re-order) the elements in z return z
Sampling via the Gumbel distribution
In machine learning it is typical to parametrize the categorical distribution, via an unconstrained representation in , whose components are given by:
where is any real constant. Given this representation, can be recovered using the softmax function, which can then be sampled using the techniques described above. There is however a more direct sampling method that uses samples from the Gumbel distribution.[7] Let be k independent draws from the standard Gumbel distribution, then
will be a sample from the desired categorical distribution. (If is a sample from the standard
See also
Related distributions
- Dirichlet distribution
- Multinomial distribution
- Bernoulli distribution
- Dirichlet-multinomial distribution
Notes
- ^ However, Bishop does not explicitly use the term categorical distribution.
References
- ISBN 0262018020.
- ^ a b c d e f Minka, T. (2003) Bayesian inference, entropy and the multinomial distribution. Technical report Microsoft Research.
- ^ Minka, T. (2003), op. cit. Minka uses the Kronecker delta function, similar to but less general than the Iverson bracket.
- ^ ISBN 0-387-31073-8.
- ISBN 0-471-12844-9(p. 105)
- ISBN 978-0-471-22618-5, pp. 25
- ^ Adams, Ryan. "The Gumbel–Max Trick for Discrete Distributions".