Dirichlet process
In probability theory, Dirichlet processes (after Peter Gustav Lejeune Dirichlet) are a family of stochastic processes whose realizations are probability distributions. In other words, a Dirichlet process is a probability distribution whose range is itself a set of probability distributions. It is often used in Bayesian inference to describe the prior knowledge about the distribution of random variables—how likely it is that the random variables are distributed according to one or another particular distribution. As an example, a bag of 100 real-world dice is a "random probability mass function (random pmf)" - to sample this random pmf  you put your hand in the bag and draw out a die, that is, you draw a pmf. A bag of dice manufactured using a crude process 100 years ago will likely have probabilities that deviate wildly from the uniform pmf, whereas a bag of state-of-the-art dice used by Las Vegas casinos may have barely perceptible imperfections. We can model the randomness of pmfs with the Dirichlet distribution. The Dirichlet process is specified by a base distribution formula_1 and a positive real number formula_2 called the concentration parameter (also known as scaling parameter). The base distribution is  the expected value of the process, i.e., the Dirichlet process draws distributions "around" the base distribution the way a normal distribution draws real numbers around its mean. However, even if the base distribution is continuous, the distributions drawn from the Dirichlet process are almost surely discrete. The scaling parameter specifies how strong this discretization is: in the limit of formula_3, the realizations are all concentrated at a single value, while in the limit of formula_4 the realizations become continuous. Between the two extremes the realizations are discrete distributions with less and less concentration as formula_2 increases. The Dirichlet process can  also be seen as the infinite-dimensional generalization of the Dirichlet distribution. In the same way as the Dirichlet distribution is the conjugate prior for the categorical distribution, the Dirichlet process is the conjugate prior for infinite, nonparametric discrete distributions. A particularly important application of Dirichlet processes is as a prior probability distribution in infinite mixture models. The Dirichlet process was formally introduced by Thomas Ferguson in 1973. It has since been applied in data mining and machine learning, among others for natural language processing, computer vision and bioinformatics. One application area where the Dirichlet has proved to be particularly  useful is in modeling the distribution of words in text documents. If we have a dictionary containing k possible words, then a particular document can be represented by a pmf of length k produced by normalizing the empirical frequency of its words. A group of documents produces a collection of pmfs, and we can fit a Dirichlet distribution to capture the variability of these pmfs. Different Dirichlet distributions can be used to model documents by different authors or documents on different topics. Introduction. Dirichlet processes are usually used when modelling data that tends to repeat previous values in a so -called "rich get richer" fashion. Specifically, suppose that the generation of values formula_6 can be simulated by the following algorithm. <poem> At the same time, another common model for data is that the observations formula_6 are assumed to be independent and identically distributed (i.i.d.) according to some (random) distribution formula_20. The goal of introducing Dirichlet processes is to be able to describe the procedure outlined above in this i.i.d. model. The formula_6 observations in the algorithm are not independent, since we have to consider the previous results when generating the next value. They are, however, exchangeable. This fact  can be shown by calculating the joint probability distribution of the observations and noticing that the resulting formula only depends on which formula_16 values occur among the observations and how many repetitions they each have. Because of this exchangeability, de Finetti's representation theorem applies and it implies that the observations formula_6 are conditionally independent given a (latent) distribution formula_20. This formula_20 is a random variable itself and has a distribution. This distribution (over distributions) is called a Dirichlet process (formula_26). In summary, this means that we get an equivalent procedure to the above algorithm: In practice, however, drawing a  concrete distribution formula_20 is impossible, since its specification requires an infinite amount of information. This is a common phenomenon in the context of Bayesian non-parametric statistics where a typical task is to learn distributions on function spaces, which involve effectively infinitely many parameters. The key insight is that in many applications the infinite-dimensional distributions appear only as an intermediary computational device and are not required for either the initial specification of prior beliefs or for the statement of the final inference. Formal definition. Given a measurable set "S", a base probability distribution "H" and a positive real number  formula_2, the Dirichlet process formula_33 is a stochastic process whose sample path (or realization, i.e. an infinite sequence of random variates drawn from the process) is a probability distribution over "S", such that the following holds. For any measurable finite partition of "S", denoted formula_34, where formula_37 denotes the Dirichlet distribution and the notation formula_38 means that the random variable formula_39 has the distribution formula_40. Alternative views. There are several equivalent views of the Dirichlet process. Besides the formal definition above, the Dirichlet process can be defined implicitly through de Finetti's theorem as described in the first section; this  is often called the Chinese restaurant process. A third alternative is the stick-breaking process, which defines the Dirichlet process constructively by writing a distribution sampled from the process as formula_41, where formula_42 are samples from the base distribution formula_1, formula_44 is an indicator function centered on formula_45 (zero everywhere except for formula_46) and the formula_47 are defined by a recursive scheme that repeatedly samples from the beta distribution formula_48. The Chinese restaurant process. A widely employed metaphor for the Dirichlet process is based on the so-called Chinese restaurant process. The metaphor is as follows: Imagine a Chinese restaurant  in which customers enter. A new customer sits down at a table with a probability proportional to the number of customers already sitting there. Additionally, a customer opens a new table with a probability proportional to the scaling parameter formula_2. After infinitely many customers entered, one obtains a probability distribution over infinitely many tables to be chosen. This probability distribution over the tables is a random sample of the probabilities of observations drawn from a Dirichlet process with scaling parameter formula_2. If one associates draws from the base measure formula_1 with every table, the resulting distribution over the sample space  formula_52 is a random sample of a Dirichlet process. The Chinese restaurant process is related to the Pólya urn sampling scheme which yields samples from finite Dirichlet distributions. Because customers sit at a table with a probability proportional to the number of customers already sitting at the table, two properties of the DP can be deduced: The stick-breaking process. A third approach to the Dirichlet process is the so-called stick-breaking process view. Conceptually, this involves repeatedly breaking off and discarding a random fraction (sampled from a Beta distribution) of a "stick" that is initially of length 1 . Remember that draws from a Dirichlet process are distributions over a set formula_52. As noted previously, the distribution drawn is discrete with probability 1. In the stick-breaking process view, we explicitly use the discreteness and give the probability mass function of this (random) discrete distribution as: where formula_56 is the indicator function which evaluates to zero everywhere, except for formula_57. Since this distribution is random itself, its mass function is parameterized by two sets of random variables: the locations formula_58 and the corresponding probabilities formula_59. In the following, we present without proof what these random variables are. The locations  formula_60 are independent and identically distributed according to formula_1, the base distribution of the Dirichlet process. The probabilities formula_62 are given by a procedure resembling the breaking of a unit-length stick (hence the name): where formula_64 are independent random variables with the beta distribution formula_48. The resemblance to 'stick-breaking' can be seen by considering formula_62 as the length of a piece of a stick. We start with a unit-length stick and in each step we break off a portion of the remaining stick according to formula_64 and assign this broken-off piece to formula_62. The formula can  be understood by noting that after the first "k" − 1 values have their portions assigned, the length of the remainder of the stick is formula_69 and this piece is broken according to formula_64 and gets assigned to formula_62. The smaller formula_2 is, the less of the stick will be left for subsequent values (on average), yielding more concentrated distributions. The stick-breaking process is similar to the construction where one samples sequentially from marginal beta distributions in order to generate a sample from a Dirichlet distribution. See for the proof. The Pólya urn scheme. Yet another way to visualize  the Dirichlet process and Chinese restaurant process is as a modified Pólya urn scheme sometimes called the Blackwell-MacQueen sampling scheme. Imagine that we start with an urn filled with formula_2 black balls. Then we proceed as follows: The resulting distribution over colours is the same as the distribution over tables in the Chinese restaurant process. Furthermore, when we draw a black ball, if rather than generating a new colour, we instead pick a random value from a base distribution formula_1 and use that value to label the new ball, the resulting distribution over labels will be the same as  the distribution over the values in a Dirichlet process. Use as a prior distribution. The Dirichlet Process can be used as a prior distribution to estimate the probability distribution that generates the data. In this section, we consider the model The Dirichlet Process distribution satisfies prior conjugacy, posterior consistency, and the Bernstein–von Mises theorem. Prior conjugacy. In this model, the posterior distribution is again a Dirichlet process. This means that the Dirichlet process is a conjugate prior for this model. The posterior distribution is given by where formula_77 is defined below. Posterior consistency. If we take the frequentist view  of probability, we believe there is a true probability distribution formula_78 that generated the data. Then it turns out that the Dirichlet process is consistent in the weak topology, which means that for every weak neighbourhood formula_79 of formula_78, the posterior probability of formula_79 converges to formula_82. Bernstein-Von Mises theorem. In order to interpret the credible sets as confidence sets, a Bernstein–von Mises theorem is needed. In case of the Dirichlet process we compare the posterior distribution with the empirical process formula_83. Suppose formula_84 is a formula_85-Donsker class, i.e. for some Brownian Bridge formula_87. Suppose also that  there exists a function formula_88 such that formula_89 such that formula_90, then, formula_91 almost surely This implies that credible sets you construct are asymptotic confidence sets, and the Bayesian inference based on the Dirichlet process is asymptotically also valid frequentist inference. Use in Dirichlet mixture models. To understand what Dirichlet processes are and the problem they solve we consider the example of data clustering. It is a common situation that data points are assumed to be distributed in a hierarchical fashion where each data point belongs to a (randomly chosen) cluster and the members of a cluster are further distributed  randomly within that cluster. Example 1. For example, we might be interested in how people will vote on a number of questions in an upcoming election. A reasonable model for this situation might be to classify each voter as a liberal, a conservative or a moderate and then model the event that a voter says “Yes” to any particular question as a Bernoulli random variable with the probability dependent on which political cluster they belong to. By looking at how votes were cast in previous years on similar pieces of legislation one could fit a predictive model using a simple  clustering algorithm such as k-means. That algorithm, however, requires knowing in advance the number of clusters that generated the data. In many situations, it is not possible to determine this ahead of time, and even when we can reasonably assume a number of clusters we would still like to be able to check this assumption. For example, in the voting example above the division into liberal, conservative and moderate might not be finely tuned enough; attributes such as a religion, class or race could also be critical for modelling voter behaviour, resulting in more clusters in the model. Example  2. As another example, we might be interested in modelling the velocities of galaxies using a simple model assuming that the velocities are clustered, for instance by assuming each velocity is distributed according to the normal distribution formula_93, where the formula_94th observation belongs to the formula_95th cluster of galaxies with common expected velocity. In this case it is far from obvious how to determine a priori how many clusters (of common velocities) there should be and any model for this would be highly suspect and should be checked against the data. By using a Dirichlet process prior for the distribution  of cluster means we circumvent the need to explicitly specify ahead of time how many clusters there are, although the concentration parameter still controls it implicitly. We consider this example in more detail. A first naive model is to presuppose that there are formula_96 clusters of normally distributed velocities with common known fixed variance formula_97. Denoting the event that the formula_94th observation is in the formula_95th cluster as formula_100 we can write this model as: That is, we assume that the data belongs to formula_96 distinct clusters with means formula_103 and that formula_104 is the (unknown) prior probability of a  data point belonging to the formula_95th cluster. We assume that we have no initial information distinguishing the clusters, which is captured by the symmetric prior formula_106. Here formula_37 denotes the Dirichlet distribution and formula_108 denotes a vector of length formula_96 where each element is 1. We further assign independent and identical prior distributions formula_110 to each of the cluster means, where formula_1 may be any parametric distribution with parameters denoted as formula_112. The hyper-parameters formula_2 and formula_112 are taken to be known fixed constants, chosen to reflect our prior beliefs about the system. To understand the connection to Dirichlet  process priors we rewrite this model in an equivalent but more suggestive form: Instead of imagining that each data point is first assigned a cluster and then drawn from the distribution associated to that cluster we now think of each observation being associated with parameter formula_116 drawn from some discrete distribution formula_117 with support on the formula_96 means. That is, we are now treating the formula_116 as being drawn from the random distribution formula_117 and our prior information is incorporated into the model by the distribution over distributions formula_117. We would now like to extend this model to work without  pre-specifying a fixed number of clusters formula_96. Mathematically, this means we would like to select a random prior distribution formula_123 where the values of the clusters means formula_103 are again independently distributed according to formula_125 and the distribution over formula_104 is symmetric over the infinite set of clusters. This is exactly what is accomplished by the model: With this in hand we can better understand the computational merits of the Dirichlet process. Suppose that we wanted to draw formula_128 observations from the naive model with exactly formula_96 clusters. A simple algorithm for doing this would be to draw formula_96  values of formula_131 from formula_110, a distribution formula_133 from formula_106 and then for each observation independently sample the cluster formula_95 with probability formula_136 and the value of the observation according to formula_137. It is easy to see that this algorithm does not work in case where we allow infinite clusters because this would require sampling an infinite dimensional parameter formula_138. However, it is still possible to sample observations formula_139. One can e.g. use the Chinese restaurant representation described below and calculate the probability for used clusters and a new cluster to be created. This avoids having to explicitly specify formula_138 . Other solutions are based on a truncation of clusters: A (high) upper bound to the true number of clusters is introduced and cluster numbers higher than the lower bound are treated as one cluster. Fitting the model described above based on observed data formula_40 means finding the posterior distribution formula_142 over cluster probabilities and their associated means. In the infinite dimensional case it is obviously impossible to write down the posterior explicitly. It is, however, possible to draw samples from this posterior using a modified Gibbs sampler. This is the critical fact that makes the Dirichlet process prior useful for  inference. Applications of the Dirichlet process. Dirichlet processes are frequently used in "Bayesian nonparametric statistics". "Nonparametric" here does not mean a parameter-less model, rather a model in which representations grow as more data are observed. Bayesian nonparametric models have gained considerable popularity in the field of machine learning because of the above-mentioned flexibility, especially in unsupervised learning. In a Bayesian nonparametric model, the prior and posterior distributions are not parametric distributions, but stochastic processes. The fact that the Dirichlet distribution is a probability distribution on the simplex of sets of non-negative numbers that sum to one makes  it a good candidate to model distributions over distributions or distributions over functions. Additionally, the nonparametric nature of this model makes it an ideal candidate for clustering problems where the distinct number of clusters is unknown beforehand. In addition, the Dirichlet process has also been used for developing a mixture of expert models, in the context of supervised learning algorithms (regression or classification settings). For instance, mixtures of Gaussian process experts, where the number of required experts must be inferred from the data. As draws from a Dirichlet process are discrete, an important use is as a prior probability in  infinite mixture models. In this case, formula_52 is the parametric set of component distributions. The generative process is therefore that a sample is drawn from a Dirichlet process, and for each data point, in turn, a value is drawn from this sample distribution and used as the component distribution for that data point. The fact that there is no limit to the number of distinct components which may be generated makes this kind of model appropriate for the case when the number of mixture components is not well-defined in advance. For example, the infinite mixture of Gaussians model, as  well as associated mixture regression models, e.g. The infinite nature of these models also lends them to natural language processing applications, where it is often desirable to treat the vocabulary as an infinite, discrete set. The Dirichlet Process can also be used for nonparametric hypothesis testing, i.e. to develop Bayesian nonparametric versions of the classical nonparametric hypothesis tests, e.g. sign test, Wilcoxon rank-sum test, Wilcoxon signed-rank test, etc. For instance, Bayesian nonparametric versions of the Wilcoxon rank-sum test and the Wilcoxon signed-rank test have been developed by using the imprecise Dirichlet process, a prior ignorance Dirichlet  process.