A Survey on Bayesian Nonparametric Learning A Survey on Bayesian Nonparametric Learning

In probability theory, a stochastic process is a set of (indexed) random variables, where indexes are derived from an (countably infinite) index/parameter space and the variables are derived from a state space. Statistics defines a number of different stochastic processes according to the different properties of these random variables, which we have organised some popular ones in BNL into a relational diagram in Figure 1. Not all of these processes have been used in machine-learning field (yet), but the most popular and representative ones are reviewed below.

Fig. 1. Various stochastic processes in the literature.

—Gaussian Process (GP). A GP [151] is a specific set of random variables with a property that any finite subset of these variables satisfies a Gaussian distribution. A GP prior is represented as

When used in machine learning, $g(x)$ models an underlying function, e.g., the mapping relationships between the features and labels of data. Hence, the GP is a good prior for latent functions and is especially useful for situations when there no knowledge of the functional form exists. It has been proven that GP has a deep relationship with traditional algorithms in machine learning, e.g., support vector machines [178].

One large group of popular stochastic processes in BNL falls within the scope of Lévy processes [148], which are (informally) defined as the stochastic processes with stationary and independent increments. According to the Lévy-Itô decomposition, a Lévy process could be roughly decomposed into two components: one continuous component and one discrete component. When there is no continuous component and discrete jumps are positive, the Lévy process is called a pure-jump increasing Lévy process and is characterised by Lévy measure [177]. One merit of this pure-jump increasing Lévy process is its close relationship with Poisson process that each pure-jump increasing Lévy process is corresponding to a Poisson process using Lévy measure as mean measure. Because of this relationship, the realisation of each pure-jump increasing Lévy process could be viewed as a (countably infinite) set of points in a product space defined by its index/parameter space and state space, where each point is a pair <a parameter, a variable>. These points/pairs are all that is obtained from a stochastic process. Based on these points/pairs, a measure on parameter space can be constructed as $M = \sum _{k=1}^{\infty } \text{variable}_k \,\delta _{\text{parameter}_k}$, where $M$ is a measure, $k$ is the point index, and $\delta$ is Dirac measure. The constructed measure is called a random measure since the realisation of process is random. Furthermore, an important property of the Poisson process is its equivalence with completely random measures (CRM), noting that any measure $M$ from a Poisson process is a completely random measure [100]. A number of stochastic processes in this area have been proven to be as special cases of CRMs, and these special stochastic processes can be manipulated thank to such property as discussed in more detail in the following section. Figure 2 illustrates these concepts using three examples. Next, we review some representative examples in this group in more details.

Fig. 2. Illustrations of a parameter/index set, a state space, a realisation, and corresponding measure. The three illustrated examples are: Poisson, gamma, and beta processes.

—Poisson Process (PP). A PP [102] over the product space is represented as $\Pi \sim \text{PP}(\Pi _0)$, where $\Pi _0$ is a base measure over $\Theta$. Note that, in theory, the base measure $\Pi _0$ could be any measure, but PP is normally used as the likelihood, so $\Pi _0$ is often a discrete measure from a prior, such as $\Pi _0=\sum _{k=1}^\infty \lambda _k\delta _{\theta _k}$. A realisation $\Pi$ is set of points , and is represented as

—Gamma Process (GaP). A GaP [145] $\Gamma \sim \text{GaP}(c, \Gamma _0)$ is a Lévy process whose Lévy measure depends on two parameters: $c$ and $\Gamma _0$. $c$ denotes concentration parameter, and $\Gamma _0$ represents the base measure,

—Beta Process (BP). A BP [87, 170] $B \sim BP(c, B_0)$ is a Lévy process whose Lévy measure depends on two parameters: $c$ and $B_0$. $c$ is a positive concentration parameter, and $B_0$ is a base measure on $\Theta$. If $B_0$ is continuous, then the Lévy measure of $\Theta \times [0, 1]$ of the BP is

—Negative-binomial Process (NBP). A NBP [196, 200] $X \sim \text{NBP}(\Gamma _0, B_0)$ is another process over the product space , parameterised by two parts: $\Gamma _0 = \sum _k r_k \delta _{\theta _k}$ is a shape measure and $B_0 = \sum _k b_k \delta _{\theta _k}$ is the probability measure. A realisation $X$ from NBP is a set of points and the obtained measure is

—Bernoulli Process (BeP). A BeP [102] $I$ is Lévy process $I \sim \text{BeP}(I_0)$ where $I_0 = \sum _k b_k \delta _{\theta _k}$ is a hazard measure and a realisation of BeP is

There are also some processes that are not Lévy processes but can be derived from them. For example, Dirichlet process is a normalisation of GaP and Mondrian process is a multidimentional extension of PP.

—Dirichlet Process (DP). DP [57, 162] is the pioneer and foundation of the BNL. It is defined as: A DP, which is specified by a base measure $H$ on a measurable space $\Theta$ and a concentration parameter $\alpha$, is a set of countably infinite random variables that can be viewed as a (probability) measure on partitions from a random infinite partition $\lbrace \Omega \rbrace _{k=1}^{\infty }$ of $\Theta$. An explicit representation of a DP using the stick-breaking process [162] is

—Mondrian Process (MoP). Let $\Theta$ be a box in with a positive linear dimension. The Mondrian process [143] on $\Theta$, denoted as MP($\Theta$), is a temporal stochastic process $(M_t)_{t\ge 0}$ takes values in guillotine partitions of $\Theta$ and its distribution is specified by the generative process Mondrian($\Theta$): The random variable $M_t$ is the guillotine partition of $\Theta$ formed by cuts/nodes with birth time $t_b \le t$.

Although the measure is not a widely used concept in computer science, we have still included it in this article because the measure view of these stochastic processes is essential for developing aspects of BNL, such as new manipulations and posterior inference algorithms. The following example illustrates such concept: The bottom row of Figure 2 shows a sample (i.e., an infinite number of points): ${(b_1,\theta _1),(b_2,\theta _2), \ldots ,(b_k,\theta _k)}$ from a beta process with a 2-simplex as the index space and (0, 1) as the state space. The measure composed by these points is $M=\sum _{k} b_k \delta _{\theta _k}$, which is defined as a measure of the index/parameter space, i.e., it maps a subset of this space to a nonnegative value. For a subset of the 2-simplex (i.e., $A$ in the figure), the measure value on $A$ by $M$ is $M(A)=\sum _{k} b_k \delta _{\theta _k}(A) = b_1 + b_2$. From this example, we can see that the summation in the measure definitions is to sum the weights of the points within the subset $A$. To make it further simple, particularly for the computer scientists, a measure can be simply considered as a set of points, e.g., ${(b_1,\theta _1),(b_2,\theta _2), \ldots ,(b_k,\theta _k)}$ shown in Figure 2. Such points are, in fact, what we obtain and operate in the BNL. A concrete example to show how the points from measure definition are used follows: Suppose we have a number of data, i.e., $\mathbf {x}$, in two-dimensional real space as shown in Figure 3. We can use the points from the Dirichlet Process, i.e., ${(\pi _1,\theta _1 = \lt \mu _1, \Sigma _1\gt),(\pi _2,\theta _2= \lt \mu _2, \Sigma _2\gt), \ldots ,(\pi _k,\theta _k= \lt \mu _k, \Sigma _k\gt)}$, to model these data as $p(\mathbf {x})=\sum _k \pi _k \mathcal {N}(x; \mu _k, \Sigma _k)$ where $\mathcal {N}(x; \mu _k, \Sigma _k)$ denotes a Gaussian probability density function parameterised by a mean vector $\mu _k$ and covariance matrix $\Sigma _k$. We can see that one component of a point $\theta$ is used as the parameters for a mixture, and the other component $\pi$ is used as a weight for a mixture. After the posterior inference, an appropriate number of points are selected to optimally model the data. As shown in Figure 3, three points/mixtures (i.e., eclipses) are chosen for modelling/representing the data. The above model is well-known as an infinite Gaussian mixture model [137].

Fig. 3. Illustrations of the usage of a measure. A DP measure $G = \sum _k \pi _k \delta _{\theta _k}$ is used to model a set of two-dimensional data. After the posterior inference, three mixtures/points (i.e., three ecllipes in the figure) are chosen to represent/model such data.

Some important properties of the above stochastic processes are summarised in Table 1, including the stick-breaking construction methods and the power-law extensions. Note that these stochastic processes are only a very small portion of all stochastic processes. In addition to the above processes, there are a large number of stochastic processes with special properties existing in the current statistic literature, many of which may be valuable for modelling different data structures or resolving different learning tasks. We believe these processes are a huge undiscovered treasure that deserves more attention from the machine-learning community.

Recall that the definition of a process only states its respective properties but does not provide a way to construct its realisations. Discovering a way to construct the realisation of a stochastic process (also known as a representation) is crucial in posterior analysis. The above subsection only gives the definitions of different processes from which we can judge whether a measure is from a specific stochastic process. To obtain an instance/sample from a process and perform the model inference, an explicit construction method is needed. Based on the properties of Beta distribution, stick-breaking is commonly accepted as an efficient construction methodology. Several sticking-breaking methods have been proposed for different processes. These are summarised below.

—Sticking-breaking for Dirichlet Process [152]. Sticking-breaking continuously breaks a stick with a unit length, and constructs the weights using these breaks. For DP, the procedure is as follows:

—Sticking-breaking for Hierarchal Dirichlet Process [167, 176]. There are two versions of stick-breaking for HDP: Teh's version [167] and Sethuraman's version [176]. The Sethuraman's verion is

—Sticking-breaking for Indian Buffet Process [164]. To obtain $Z \sim \text{IBP}(\alpha)$, the stick-breaking procedure is

Fig. 4. Illustrations of the connection between the stick-breaking procedures for DP and IBP.

—Sticking-breaking for Beta Process [13]. The stick-breaking construction procedure for $B \sim \text{BP}(c, B_0)$ is different from IBP, in that there are more than one unit sticks. The procedure is

The base measure of a stochastic process can either be a continuous or discrete, and the realisation of a stochastic process is a random measure. Hence, it is possible to use a random measure from one stochastic process as the base measure for other stochastic processes to share the statistical strength between these processes. Take document modelling for example. The random measure in the upper layer could be the topic pool and the lower measure at the document level could be the topics in a document. The existing new Bayesian nonparametric priors based on this manipulation are summarised as follows.

—Hierarchical Dirichlet Process (HDP). HDP [167] is built by piling one DP on top of another DP(s) to transfer some statistical strengths from top layer to the bottom layer. For example, suppose a top measure $G_0$ over $\Theta$ is with a DP ($\alpha$, $H$) prior and $G_d$ is the measure in the bottom layer also with a DP ($\alpha _d, G_0$) prior, then we have

—Hierarchical Pitman-Yor processes (HPYP). Similarly to HDP, HPYP [110] piles one PYP on top of other PYP(s). Unlike HDP, HPYP has two parameters: a concentration parameter $\alpha$ and a discount parameter $\beta$.

—Hierarchical Beta Process (HBP). Akin to HDP, HBP [170] was proposed to make the different BPs share the same discrete measure (an infinite number of probabilities) from a global BP through

—Gamma-Negative Binomial Process (GNBP). In contrast to HDP and HBP, GNBP [197] is not composed of a single process (e.g., a DP and a BP), but rather of two processes: a GaP and a NBP as follows:

—Beta-Negative Binomial Process (BNBP). Analogous to a negative-binomial distribution, a BNP has two parameters. While GNBP places a GaP on one parameter, another BNBP layering manipulation [14] is to place a BP on another parameter as follows:

—Enriched Dirichlet Process (enDP). EnDP [173] could be viewed as a special case of HDP, which is defined as

Superposition is used to combine two or more random measures together, like a “plus” operation. If layering is considered to be a form of vertical manipulation, then the superposition is a horizontal manipulation.

—Superposition of Poisson Processes. According to the Superposition Theorem in Reference [102], it is known that combining a set of independent Poisson processes yields a new PP with a mean measure that is the sum of the mean measures of the individual processes:

—Superposition of Dirichlet Processes. Inspired by the superposition of PP, the authors of Reference [112] proposed the superposition of DP as follows:

—Superposition of Normalised Random Measures (SNRM). Since DP is a special case of NRM, the superposition manipulation of DP has been extended to the more general NRMs [28] as follows; the superposition of $n$ independent normalised random measures $\lbrace \mu _j\rbrace ^n_{j=1}$ on $\Theta$ is

Subsampling (randomly) selects parts of infinite components in a random measure from a stochastic process. When certain conditions are satisfied, the selected components form a new random measure from an underlying process.

—Thinned Poisson Process [112]. Based on the Marking Theorem [102], let $\Pi \sim \text{PP}(\mu)$ be a PP on the space $\Theta$, and a measurable function $q : \Theta \rightarrow [0, 1]$. If independently drawing $z_{\theta } \in \lbrace 0, 1\rbrace$ for each $\theta \in \Pi$ with $P(z_{\theta } = 1) = q(\theta)$, then a new PP is

—Thinned Completely Random Measures (TCRM) [59]. Let $\Pi = \sum _{k=1}^{\infty }\pi _k \delta _{\theta _k}$ be a CRM on $\Theta$ and a measurable function $q : \Theta \rightarrow [0, 1]$. For each point $(\theta _k, \pi _k)$, we define a Bernoulli variable $r_k$ with $P(r_k = 1) = q(\theta _k)$ (independent with other $\lbrace r\rbrace$),

—Thinned Dirichlet Process [112]. Let $G \sim \text{DP}(\mu)$ be a DP on $\Theta$ that can be represented as $G = \sum _{k=1}^{\infty } \pi _k \delta _{\theta _k}$ and a measurable function $q : \Theta \rightarrow [0, 1]$. For each $k$, independently draw $r_k$ through $P(r_k = 1) = q(\theta _k)$,

—Thinned Normalised Random Measures (TNRM) [28, 29, 112]. Given an NRM $\mu = \sum _{k=1}^{\infty } \pi _k \delta _{\theta _k}$ on $\Theta$ and a Bernoulli variable $r_k \in [0, 1]$. The TNRM is

Point-transition moves the points of a random measure according to an underlying probabilistic transition.

—Point-transition of Poisson Process. Based on the Transition Theorem [102], let $\Pi \sim \text{PP}(\mu)$ be a PP on space $\Theta$ and $T: \Theta \times \mathcal {F}_{\Theta } \rightarrow [0, 1]$ be a probabilistic transition. From Reference [112], the transformed measure is

—Point-transition of Dirichlet Process [112]. Let $G = \sum _{k=1}^{\infty } \pi _k \delta _{\theta _k} \sim \text{DP}(\mu)$, and its point-transition is

—Point-transition of Normalised Random Measures (PNRM) [28]. Given an NRM $\mu = \sum _{k=1}^{\infty } \pi _k \delta _{\theta _k}$ on $\Theta$, the point-transition of $\mu$ is to draw atoms $\theta _k^{^{\prime }}$ from a transformed base measure to yield a new NRM as

With a partition of a space by a process, e.g., DP, nesting is to further partition each area through another process. In other words, each component of a random measure is attached to an additional random measure.

—Nested Dirichlet Process (nDP) [8]. The root partition is created by a DP, and each component in that partition is further attached to another DP. Repeating this procedure forms a tree of infinite width and depth. Each datum (e.g., a document) is associated with a path of this tree.

—Nested Hierarchical Dirichlet Process (nHDP) [129]. This process generates a nested structure similar to a nDP but associates a datum with a new revised copy of the generated tree structure rather than a simple path.

According to de Finetti's Theorem [2], an exchangeable sequences could be obtained through marginalising Finetti mixing measure out as follows,

—Chinese Restaurant Process (CRP). Marginalising a DP through,

—Chinese Restaurant Franchise (CRF) [167]. CRF is a marginalisation of HDP. Based on CRP, the metaphor to understand this process is as follows: There are $D$ Chinese restaurants with a shared menu. The $i$th customer walks into the $d$th restaurant and picks an occupied table at which to sit with the probability $\frac{n_{d,t}}{\alpha _d+i-1}$ or a new table with the probability $\frac{\alpha _d}{\alpha _d+i-1}$, where $n_{d,t}$ is the number of customers siting at table $t$ in $d$th restaurant. If this customer picks an occupied table, then she just eats the dish already on that table; if a new table is picked, then she needs to order a new dish. The new dish is ordered from the menu according to its popularity. The probability that the new dish is the same as the one on other tables has a probability of $\frac{T_k}{\alpha +\sum _k T_k}$ and the probability that it is a new dish is $\frac{\alpha }{\alpha +\sum _k T_k}$, where $T_k$ is the number of tables with the same dish $\theta _k$. As a result, $\theta _{d,t}$ is the dish on table $t$ of restaurant $d$, and $\theta _{d,i}$ is the dish eaten by customer $i$ in restaurant $d$.

—Nested Chinese Restaurant Process (nCRP) [141]. nCRP is a marginalisation of nDP. A metaphor based on CRP can be used to understand this process is as follows. There are infinite restaurants in a city and each restaurant has infinite tables. On each table, there is a card with the address of another restaurant. As such, all restaurants are organised into an infinite tree structure. A customer visiting this city dines first at the root restaurant and chooses a table using the CRP strategy. she notes the name of the restaurant on the card on her table and the next night she dines there, again choosing the table using CRP. This procedure repeats infinitely many times.

—Nested Chinese Restaurant Franchise (nCRF) [1]. Analogous to nCRP and nDP, nCRF is a marginalisation of nHDP. The metaphor based on CRP and CRF to understand this process is slightly different: There are multiple cities, and each city has infinite restaurants with infinite table. The card on the table has the name of another restaurant in the same city as with nCRP. However, there are also an infinite number of menus organised using nCRP. The tree structures for all cities and menus are the same. A customer visiting a city dines first at the root restaurant and again chooese a table using nCRP. But this time, the meal is ordered from the menu (at the same position of the infinite tree) according to popularity as determined by CRF. Hence, nCRF combined with CRF helps to share the menus between restaurants, and nCRP helps to build the hierarchy.

—Indian Buffet Process (IBP). Marginalising a BP through,

—Nested Indian Buffet Process (nIBP) [31]. Similar to nCRP, a nested version of IBP is able to build a hierarchy where each layer is composed of a number of IBPs (i.e., the number of features in IBPs at the up-layer). Continuing the metaphor, there are infinite number of Indian buffet restaurants in a city, each has an infinite number of dishes, and a card with the address of another restaurant in the same city next to each dish. Hence, the restaurants in this city are organised as an infinite tree structure. A customer who visits the root restaurant in this city and chooses dishes using the IBP strategy but uses a layer-dependent probability $\text{Poisson}(\frac{\alpha /\ell }{i})$ to choose any new dishes. The next day, the customer will visit all the restaurants on the cards next to her chosen dishes. Note that a customer can go to multiple restaurants with nIBP, rather than only a single one in nCRP.

While the (countably) infinite nature of BNL enables great modelling power, it also brings a challenge on model inference in that an infinite number of factors and weights make the posterior inference of the latent variables much harder. One commonly accepted solution in BNL is the truncation method [62, 181], which sets the component number so large that the given data would only adopt a subset of them, but it does introduce an approximation error. Another successful technique to resolve this problem is data/variable augmentation [160, 172], also known as Slice Sampling [39, 126]. The existing Bayesian nonparametric models that use the slice sampling method for model inference are summarised below.

—Slice Sampling for DP. A realisation from DP can be represented as $G=\sum _{k=1}^{\infty } \pi _k \delta _{\theta _k}$, where $\pi _k$ are (a countably infinite number of) stick weights. The slice sampling for DP [97] introduces an auxiliary variable $u_i \sim \text{Unif}(0, \pi _{k_i})$, which functions as an adaptive truncation for the data $i$, and then only needs to sample $\pi \gt u_i$ for data $i$.

—Slice Sampling for BP. Instead of the fixed range used in DP, a positive decay function $f : \lim _{k \rightarrow \infty } f(\pi _k) = 0$ controls the support for the auxiliary variable $u_k \sim \text{Unif}(0, f(\pi _k))$ [14]. Compared to the function used in DP, the decay function is more flexible and more applicable to many other models.

Using variational inference involves two important components: setting variational distributions and choosing optimisation methods. Clearly setting the variational distribution can significantly reduce the additional approximation error and appropriate optimisation methods can boost the inference efficiency and adapt to the complex scenarios, e.g., large-scale and streaming data. Existing work on variational inference for BNL is summarised below.

—Ordinary Variational Inference. The form of variational inference for BNL is based on a stick-breaking representation where the latent variables in this representation include stick weights, atom parameters, and data assignment indexes. Since stochastic processes such as DP [9, 106] and GaP [145] have the potential to produce an infinite number of atoms, we have opted for a truncation method to ensure that only a finite number of atoms need to be approximated with a finite number of mean-field (latent variable) distributions. Other similar works have been applied for HDP [9], IBP [44], and nCRP [174].

—Collapsed Variational Inference. As stated, there are normally three groups of latent variables in BNL (i.e., stick weights, atom parameters, and data assignment indexes). Sometimes stick weights could be marginalised out to make the inferences of DP [105] and HDP [147, 168] more accurate and efficient.

—Online/Stochastic Variational Inference. Instead of coordinate-ascent optimisation that is not efficient for large datasets because a full pass of all the data at each iteration is required, stochastic optimisation is used to update the variational parameters [15, 176]. At each iteration, a number of data are sampled from the entire dataset before updating the variational parameters. This optimisation could improve the inference efficiency because of the estimated noisy gradients of the variational objective have been proven to be natural gradients of the Kullback-Leibler divergence objective [90].

—Truncation-free Variational Inference. One problem with the above variational inference methods is that the truncation is needed, which brings additional approximation errors that are resolved with a locally collapsed method. Here, the global latent variables are marginalised, and the distribution of the local variables could be sampled [175]. This method can be viewed as a combination of the sampling and variational inference methods. Another idea to avoid truncation is variational DP [106], where a tying assumption is given. That is, the variational distributions of components larger than $T$ are set as priors, and $T$ are adaptively increased with a decrease in the optimisation objective and KD-tree-based data organisation is introduced to accelerate the speed of inference.

—Streaming Variational Inference. Streaming variational inference algorithms were proposed to handle data that arrives sequentially in the form of a data stream. This method does not require data to be preserved in memory, which means it can be discarded after processing. The idea is to decompose the joint posterior to a recursive form where the distribution of the incoming datum is derived from the posterior distribution of the former observed data. Different techniques can then be used for approximation, such as a designed variational stochastic process with independent factors for DP [111] or more general extensions based on assumed density filtering [159] or component identification [16].

Considering the exponentially increasing amount of data in many areas, the ability to handle Big Data is also a research direction for BNL. The idea is to extend current inference algorithms, particularly those designed for a single processor/machine into parallel versions for multiple processors/machines. Existing inferences algorithms for this problem are mainly categorised into the following two groups: MCMC and variational.

—Parallel MCMC. The authors of Reference [155] proposed a parallel MCMC for HDP using an asynchronous method. The advantages of this approach are that it is easy to incorporate new data and processors, and it is extremely fault-tolerant. The disadvantages is with additional approximation. To overcome this disadvantage, further parallel MCMC for DP, HDP, and PYP were proposed [48, 113, 179] based on the inverse-superposition of DPs. Here, each processor or machine handles one supercluster (i.e., one of DPs). Generating data-based super-clusters generation further improves the efficiency [23]. Although the above methods could use marginalised representations of DP or HDP to avoid truncation, a slice sampling-based parallel MCMC [68] has been developed to explicitly sample the stick weights in DP and HDP in an elegant way.

—Parallel Variational Inference. In this form of inference, the posterior distribution is decomposed for the streaming and parallel inference, and a component identification algorithm resolves the mismatch problem when merging different variational posteriors from different processing nodes [16]. Instead of obtaining the exact variational approximation of the real posterior distribution by combining subposteriors (from different processing nodes) together, a Markov chain is designed to collect samples from the variational approximation [127], which again can be viewed as a combination of variational and sampling.

Some other inference methods that have been applied to BNL are as follows:

—Sequential Monte Carlo. Also known as particle filtering, this approach approximates the posterior distribution through a large collection of samples (i.e., particles) that are propagated over time and updated by sequential importance sampling. The sequential Monte Carlo method has been applied to DP mixture with time varying mixtures [20], beta-binomial DP mixtures [116], general conjugate DP mixtures [56], and nonparametric Bayesian matrix factorisation [182].

—Power Expectation Propagation. [121] This method generalises expectation propagation and variational inference using a flexible $\alpha$-divergence. An example is nonparametric Bayesian matrix factorisation [42].

Sometimes data have labels (also known as responses), such as the emotion tags, the GDPs of countries, network relations, and so on. Supervised learning is a method for modelling the relationships between data and these responses/covariants to make predictions—a basic task in machine learning. Supervised BNL tends to fall into two categories.

—Generalized linear models (GLM)-based, where the data are assigned to a number of clusters, and the responses (for classification) of the data are modelled by multinomial logistic models (also called “softmax”) [82, 153]. A DP is used as a prior for weighting $\lbrace \pi _k\rbrace _{k=1}^{\infty }$ the clusters and the parameters $\lbrace \theta _k\rbrace _{k=1}^{\infty }$ are used in the multinomial logit models. Although the data and the responses in each cluster have a linear relationship, multiple clusters make it possible to capture non-linear relationships. This idea has been further extended for group data using HDP [36, 193].

—Covariant space-based. The relationship between the covariant space and the data is captured by dependent stochastic processes by (1) setting the base measure as a special stochastic process, such as a single-variable stochastic process [114] and a multi-variable Gaussian process [69]; (2) varying the stick-breaking procedure, such as linking stick weights through a stochastic process [115], a kernel function [50], or a permutation stick-breaking order [34, 115]; (3) auxiliary PP in a covariant space, such as kernel beta process [140] and correlated normalised random measure [76]; and (4) revising the seating mechanisms in CRP or IBP, such as ddCRP [7] and ddIBP [71]. More discussions on this aspect can be found in Reference [60].

Factor analysis describes or captures the variability of observed or correlated data with the help of a collection of unobserved variables called factors, which is useful for denoising or storage [171]. The mathematical definition is $Y=\Phi X+E$, where $Y$ is data, $\Phi$ is factors, $X$ is the factor loading matrix, and $E$ is the error. Traditionally, the dimensionality of $\Phi$ needs to be given in advance, but BNL relaxes this requirement. Since IBP defines a distribution for infinite (on columns) binary matrices, it has become a significant cog in this field [77]. Below, we summarise the studies into two important branches of factor analysis: Principal component analysis and Non-negative matrix/tensor factorisation.

—Principal component analysis (PCA). PCA is a very popular tool for dimension reduction, but the selection of the number of significant components requires strong background knowledge that is normally unknown. Unlike general factor analysis, PCA aims to project the data to an space spanned by orthonormal vectors. A BNP-PCA [51] is defined as

—Non-negative matrix/tensor factorisation (NMF/NTF). Same with PCA, the nonparametric versions of NMF/NTF are also mainly based on IBP or BP. The basic idea is to factor the data matrix or tensor into two matrices: one is binary (mask) matrix and the other is a factor matrix, and an infinite prior is given to the binary matrix, such as IBP [42, 182] or BP [108],

Transfer learning [131] is a learning scheme that extracts transferable knowledge from the a source domain(s) and reuses this knowledge in a target domain to resolve the problem of insufficient data in traditional machine-learning schemes. It appears that the core of the transfer learning is to extract transferable knowledge between domains that can be generalised to the target domain. BNL is good at generalisation because of its ability to build a flexible prior and, hence, has been applied to transfer learning. The existing works in this area are summarised according to the different forms of the transferable knowledge below.

—Transfer by sharing factors. Factors are real-valued vectors and can also be viewed as high-level semantic descriptions of data; this allows them to be transferred from one domain to another. In Bayesian nonparametric joint factor analysis (NJFA) [79], domains are jointly factorised with shared factors and domain-specified factors. In contrast to simply sharing factors between two domains through a matrix product and summation, factor sharing in NJFA relies on an ingenious HBP prior. HBP is used to control the assignment of factors between domains, and its advantages are (1) factors are shared by domains through hierarchically dependent beta processes and (2) the number of both shared and domain-specified factors does not need to be prefixed but rather automatically learned from the data.

—Transfer by sharing topics. Different from factors, topics are a set of latent variables characterised by the unit summation and are used as the transferable statistical strengths between domains. BNL makes these transferable statistical strengthens more flexible by giving them Bayesian nonparametric priors. In Clustered Naive Bayes [142], a number of Naive Bayes share topics (named parameters in Reference [142]) from a DP. Further tasks within the same group share the same parameters so that well-trained tasks can help to train the insufficiently-trained task. As we discussed in Section 4.2, HDP defines a way to share statistical strengths, which has also been applied to transfer learning [18]. Here, categories share the topics/clusters. HPYP is also able to benefit the transfer learning analogy to HDP. For example, a set of basic topics is first generated for sharing, and each domain uses these topics as the base measure of a Transformed PYP, which transforms these topics to another set of topics using a domain-specific transformation matrix [27]. Unlike HDP, the activated topics are controlled by an additional IBP. The advantage over HDP is that sharing of topics and their weights could be decoupled, which makes it possible to share low-weight topics between domains [53].

—Transfer by sharing tree. Knowledge is inherently multi-granular, and the more general the knowledge in the source domain, the larger the probability it will be reusable in a (related) target domain compared to specific knowledge. Hence, sharing trees has emerged as an efficient method for transfer learning. In terms of the tree construction, BNL could contribute a rather flexible tree prior. One example is the transfer Hierarchical LDA (thLDA) [98], which transfers the knowledge in an existing tree to a target domain, where a path of the tree from the root to the bottom node is sampled for each document in the target domain through nCRP. In addition to thLDA, the second example is Reference [146] where a tree structure is built with a fixed three-layer depth and unbounded width through nCRP. In this model, domains are treated as nodes in the bottom layer (named “level 1”), the parent nodes of the domains are named supercategory in the middle layer (named “level 2”), and the root node in the top layer (named “level 3”) is a set of two variables. Each domain is characterized by a Gaussian distribution, and domains are expected to share similar parameters with their parent nodes (i.e., supercategories or root nodes). The third example treats the parameters in the tree as transferable knowledge to assist the classification of classes with less labeled data [156] where a tree structure with leaf nodes as labels/domains is built with an nCRP prior. Another example is the polylingual tree-based topic model [91], which uses a similar method to nCRP. A tree is assigned a path through a probability made up of the product of the weights of branches in the path, where the tree is also separately built from the source domain. Without resorting to nCRP, the doubly Hierarchal Pitman-Yor Language Model [183] builds a latent HPYLM as the transferable knowledge and, simultaneously, two separate HPYLMs are built for the two domains with the latent HPYLM as part of the base measures in PYPs in two HPYLMs.

Tree structures play an important role in machine learning because they are pervasively applied and reflect the human habit of organising information. Thus, learning out a hierarchical structure from plain data has attracted a great deal of attention from researchers in the Bayesian nonparametric field. Compared to other approaches to this task, Bayesian nonparametric models have the advantage of a more flexible hierarchical structure. The lack of bounds on the structure's width and depth makes it much easier to incorporate the new data.

—nCRP-based. Here, the nCRP views a tree as a nested sequence of partitions. A space is first partitioned by a CRP and each area in this partition is further partitioned into several areas to generate a tree of potentially infinite depth and branches. A datum (i.e., a document) is associated with a path in the tree using DP or Flexible Martingale [157] priors with the nCRP [8]. The datum could also be associated with a subtree of the generated tree using HDP priors in nHDP [129] instead of with a path.

—Stick-breaking-based. With this method, an iterative stick-breaking process is used to construct a Pólya Tree (PT) [133] in a nested fashion. A datum is associated with a leaf node of the generated tree, and the traditional stick-breaking process is revised to generate breaks within the tree structure to result in a Tree Structured Stick Breaking (TSSB) [72]. A datum is attached to a node in the generated tree.

—Diffusion-based. Both Kingman's coalescent [101, 163, 165] and Dirichlet Diffusion Tree (DDT) [125] define a prior for an infinite (binary) tree. The idea is that the data are generated by a diffusion procedure with several divergences during this procedure. An additional time-varying continuous stochastic processes (i.e., Markov process) is needed for the divergence control. A datum is placed at the end of branches in the diffusions. DDT has been extended into a more general structure: multifurcating branches by a Pitman-Yor Diffusion Tree (PYDT) [103] and to a feature hierarchy by Beta Diffusion Tree (BDT) [84].

—Others. Motivated by the deep belief network (DBN) [86], the Poisson gamma belief network (PGBN) [199] learns a hierarchical structure where nodes have nonnegative real-valued weights rather than binary-valued weights in DBN and the width of each layer is flexible rather than fixed. Each layer's nodes can be viewed as an abstract feature expression of the input data.

The aim of relational learning (also known as stochastic relational learning) is to analyse, model, and predict the relationships between entities. Many data contain relationships by nature, e.g., social networks, traffic networks, protein interactions, and user-item relationships. Hence, a typical and practical application of relational learning is predicting potential future connections using a trained model. In traditional Bayesian learning, the key to better predictions is learning the hidden generative procedures in a network given a prior that encodes different understandings and explanations. BNL holds the potential provide a much more flexible prior [149]. The existing research in this direction is summarised below.

—Latent class models. The idea of these models is to group nodes into a number of classes based on the same behaviours. For example, all the nodes in one class may have the same probability of being related to all the nodes in another class [188] or to all the nodes that sit outside their own class [30]. DP is usually the main machinery behind latent class modelling due to its flexibility on latent classes. [188] was the first to model relationships using BNL. By Xu et al.’s definition, the probability of observing a link $l_{a, b}$ is modelled as $p(l_{a, b} | A_a, A_b) = \theta _{a,b}$ where $A_a$ and $A_b$ are the attributes of nodes linked by $l_{a,b}$, and $\theta _{a,b}$ is the link probability from a DP prior to make it more flexible. Further, the attributes of nodes are generated according to the latent variables $Z_a$, i.e., $p(A_a|Z_a)$, and the link $p(l_{a, b} | Z_a, Z_b, W)$ is modelled using these latent variables rather than directly using node attributes where $W$ is a model (connectivity) parameter. These latent variables can be understood as the “interests” or hidden features (i.e., latent classes) of nodes that determine the formation of the links. Using a DP prior for $Z$ means the data itself determines the optimal number of states for the variables [99, 187], which has been proven to be effective for social network analysis [186]. This link patterns between groups are also set to be shared across multiple networks in Reference [93] for multi-relational data. Rather than modelling the link probability between groups, the authors of Reference [188] model the probability that a node belongs to a class, and nodes with similar patterns are grouped into classes.

—Latent feature models. The authors of References [120, 122] model a link as $p(l_{a, b} | Z_a, Z_b, W)$, where $Z_a$ is a binary vector in Reference [187] and IBP is used as the prior for $Z$. This means that each node is either characterised by a series of hidden features or it belongs to a series of clusters. A DP can also be used to supplement the IBP by creating sub-clusters within each feature/cluster [130].

—Random network models. In contrast to the above models that focus on a given network with a fixed number of nodes and links, random network models try to model the generation of both links and nodes to allow the network to grow as more nodes join. Another advantage of random network models is their ability to model sparse networks (i.e., where the number of nodes is $o(n^2)$). Essentially, a network is represented as a link sequence by $Z = \sum _{n=1}^N z_{i,j} \delta _{\theta _i, \theta _j}$, where $\theta _i$ for each node is from a CRM or NCRM, e.g., PP [22] and DP [180]. Additionally, with a simple transformation, the same idea could also be applied to binary, integer, and multi-relational networks.

The reinforcement learning (RL) is a category of sequential decision-making problems that seeks to find the optimal policy for maximising its long-term profit given an agent that interacts with an uncertain environment. RL is normally modelled through a Markov Decision Process (MDP), which is usually represented as tuple $\lt S, A, T, R\gt$ in which $S$ denotes the environment state set, $A$ denotes the action set of the agent, $T(s^{\prime }|s,a)$ is the state transition function from the state $s$ to $s^{\prime }$ after the action $a$, and $R(r|a, s^{\prime })$ represents reward function that defines the profit from action $a$. The agent needs to find the optimal policy $\pi (a|s)$ for attaining a long-term reward through the interaction with the environment. While RL has many applications, it is typically used in robots and games, such as the famous AlphaGo program [154]. In RL, BNL could provide a principled way to tackle the core task of exploration-exploitation problem [73] and the ability to model the underlying environment dynamics in a flexible way. The existing studies on BNL in RL are summarised below according to whether the target is a policy or a reward.

—Forward reinforcement learning. Sometimes, the state of an environment cannot be observed or can only be partially observed, which provides incomplete information (termed observation $o$). Determining the optimal policy in such situations is known as partially-observable RL and is modelled as a Partially-Observable MDP. Here, the hidden states or environmental models need to be inferred through the historical (interaction) data. In other words, the transition, observation, and reward functions need to be learned from a history. GP [37, 40] is a natural and powerful prior for unknown functions and is particularly efficient in a continuous state space. However, in discrete state spaces, a Bayesian nonparametric approach based on HDP-HMM [45–47] models the hidden state transitions as stick weights from HDP. The base measure is composed of two parts: one is a function for reward evaluation, the other generates observations. Another form of forward reinforcement learning is based on PYP [46], which extends the classical Deterministic Markov Models (DMM) [117] using the same method.

—Inverse reinforcement learning. In contrast to forward RL, the target of inverse reinforcement learning is a reward function. The reward function is given to other elements of an MDP and the trajectories/demonstrations (i.e., state-action pairs) determined by experts with an assumption that experts made decisions with knowledge of the underlying environment model. Classical methods model this reward function as a linear combination of handcrafted features, which apparently limits the ability to capture the complex behaviours, but this constraint is relaxed using GP [107]. Instead of improving the learning capability of a single function, a different idea to resolve the complex function learning is to partition the observations [118, 119] or divide experts [32] into groups and learn relatively simple reward function for each group based on DP. A similar idea was used to resolve switched MDP using sticky HDP-HMM [158] as the prior with the additional ability to partition the data based on their temporal properties, which is beneficial for representing rich behaviours. Another IBP-based or BP-based idea [33, 136] is to learn the composite features as conjunctions of the original features and then learn the reward function for the composite features rather than original features.

Causal inference and metric learning are other interesting applications of BNL.

—Causal inference, which estimates the effect of an action, such as a medical treatment or a sales policy, given some observational data. Consider the following basic scenario. Suppose there are a number of patients $X$, a treatment regime $A$, and observed medical history data $\lt X, Y, A\gt$. $X$ takes $A$, which leads to the result $Y$, noting that each $X$ can only choose to take $A=1$ or take $A=0$ at any given time. The goal is to estimate the effect of the treatment regime, i.e., or . In Reference [85], GP is used to approximate the conditional distributions $P(Y | X, A=0)$ and $P(Y | X, A=1)$ separately. Another strategy is to approximate the joint distribution $P(X, Y, A)$ and then obtain the conditional expectations through marginalisation [144], while a counterfactual GP [150] is designed for the continuous-time scenarios.

—Metric learning, which aims to learn out a similarity measure that forces similar data to be close and dissimilar data to be further apart. A Bayesian nonparametric model for this task is based on BP [5], where the data likelihood is defined as $p(X|H) = f(H)$ and H is the latent features of the data and decomposed as $H=S \odot Z$. BP is used as the prior for $Z$, and an additional regulariser is introduced to the target variational inference optimisation function to control the similar and dissimilar data pairs.

The goal of text mining is to understand a document corpus. Below, we have summarised the various text mining applications for BNL according to the different types of document corpora to be mined.

—Single corpus. This task seeks to learn the knowledge shared between different documents in a corpus. HDP [167] was designed to deal with such tasks by assigning a random measure to each document using a generated global random measure as a base measure. However, with an HDP approach, the word vocabulary needs to be fixed in advance, which means new words cannot be incorporated if subsequent documents are added to the corpus. Latent IBP Compound Dirichlet Allocation [4] relaxes this constraint through a four-parameter IBP. Further, by using dependent GaPs or a mixed GaP-NBP, additional information from the corpus can be introduced into a model. The authors of the Reference [191] incorporated the links (e.g., citations between scientific papers) between the documents using a dependent GaPs and authorship information using a mixed GaP-NBP [190].

—Multiple corpora. This task aims to learn the knowledge shared across different corpora. The first attempt at such a task was undertaken by a three-level HDP [167] that assigned each corpus with a random measure using a generated global random measure as the base measure. Through this hierarchical method, the topics shared by different corpora could be inferred. Moving beyond shared topics, the difference between topics at different corpora is also learned by Differential Topic Models [27] based on PYP.

—Multiple time-varying corpora. This task aims to learn the shared knowledge across time-varying corpora. Beyond the idea of HDP, an Evolutionary HDP [194] was proposed to deal with this task, which added another time-varying dependency between the random measures for different corpora. The base measure of a corpus is the (convex) combination of two measures: the global measure and the measure at the previous time stamp.

The main applications of BNL in the field of natural language processing are detailed below.

—Word segmentation. This task is to identify word boundaries in continuous speech. CRP is used to capture the word sequence generation process [75] with two options: if a novel lexical item arrives, generate a phonemic form; if not, choose an existing lexical form. This idea has subsequently been applied to HDP and performs better than DP.

—Phrase alignment. This task aims to find frequent phrase pairs from bilingual texts for the benefit of phrase-based translation systems. Since bilingual texts do not come already segmented, and the number of aligned phrase pairs is unknown, DP and HDP are used as priors to identify each aligned phrase pair in a probabilistic model for this task [41].

—Unsupervised part-of-speech (PoS) tagging. Pos tagging is to mark the words in a text with its corresponding part-of-speeches, which is the basis of text analysis. Infinite HMM is used to model the word sequence with the help of an HMM and the hidden states (PoS tags) are unbounded with the help of HDP [66].

In the field of computer vision (i.e., image processing and video processing), BNL has been successfully applied to the following problems:

—Image interpolation. It is one of the most common image processing tasks and mainly includes image resizing and remapping. The goal is to factor an image by a linear, but finite, combination of dictionary atoms [83], which are represented as a matrix. BP and IBP [198] are used as the prior for this matrix to avoid the need to predetermine the number of dictionary atoms with an additional sparsity property. Zhou et al. [201] proposed a dependent HBP to incorporate a constraint on the patch positions in an image.

—Motion capture segmentation. This task aims to identify a finite number of hidden dynamic behaviours in multiple time series given that each time series may contain multiple dynamic behaviours. The mapping relationship between time series and dynamic behaviours is expressed as a matrix, which is given a BP prior to make it infinite [63].

—Background subtraction. This task aims to delineates background information in video streams. The background is modelled by a probability density and performs better as a multi-mode probability density with dynamic backgrounds. The appropriate number of modes in the distribution tends to depend on the target video stream. Hence, [81] proposed a DP-based Gaussian Mixture Model to allow the number of nodes to be determined by the data.

The field of biology is fortunate to boast a massive amount of data, much of which has been derived from clinical trials and personalised medicines. BNL provides an efficient paradigm in a fully model-based probabilistic framework that is highly flexible and adaptable [49]. Therefore, BNL has the potential to be extremely useful in biology, because of the lack of knowledge on the parametric model establishing.

—Brain MRI tissue classification. MRIs are an effective and routine diagnostic tool, and, as such, the accurate automatic classification of brain MRI can assist doctors’ diagnoses. Mixture model clustering algorithms have dominated this task for some time due to their relatively good performance. However, more recently, nonparametric extensions to these algorithms, such as DP [35] and HDP [94], have performed even better.

—Positive selection detection. This task aims to detect the positive natural selection from alignments of protein-coding DNA. Traditional methods assume that the non-synonymous/ synonymous rate ratio at a site as a random variable that satisfies an underlying distribution. DP is used as the prior of the non-synonymous/synonymous rate ratios of site clusters [92].

—Expressed sequence tag (EST) analysis. It plays a crucial role in gene analysis in molecular biology, like gene identification in organisms. One aim of this task is to predict the number of new genes in a new coming sample that can benefit the experimental design and redundancy measuring of an EST library [49, 109]. PYP [109] is used to estimate the gene proportion in the EST library and the number of new genes, while the probability of discovering new genes estimated by additional samples [55].

Music analysis is another interesting application scenario for BNL. Such applications include teaching music, analysing the human perception of sounds, and designs for music searches [138, 169]. Music data is stored as acoustic waveforms. Among a number of methodologies for music analysis, Bayesian techniques have been found to be very effective, which has paved the way for further advancements using BNL. The following applications are highlighted.

—Musical similarity computation. This task is to estimate the timbral similarity between recorded songs, which could be further applied to music retrieval. HDP is used for this task through representing each song as a (stick weight) posterior distribution. The similarity between two songs can then be evaluated by the symmetrised KL divergence of two corresponding distributions. Compared to the traditional single Gaussian-based or GMM-based approaches, HDP-based approaches perform better [89]. A similar idea was also adopted by the authors of Reference [124] with a two-dimensional tree structure learned to represent each song.

—Blind source separation. This task is to separate different types of sounds, e.g., instruments or people, from an audio clip. One challenge for this task is that the number of sound sources is unknown; however, Blei et al. [6] proposed a GP-based NMF to resolve this problem.

Using BNL to teach robots how to complete specific tasks is arguably one of the most pioneering tasks in current machine learning. Some examples are given below:

—Robot teaching. This task aims to train robots, such as autonomous quadrotor flights or self-driving cars, to learn actions from hand-held demonstrations [24, 119]. Experts demonstrate good or perfect actions for a specific task, and the robots learn from these demonstrations through reinforcement learning (also known as imitation learning).

—Robot object identification. This task aims to enhance the a robot's ability to identify (often complex) objects, such as clothes [104] and tactile surfaces [38].

—Robot navigation. This task requires a robot to build a map, locate itself, and find a route to a target according to its sensor data, which has been modelled as a regression task using GP in References [95, 132].

—Robot introspection. This task helps a robot understand what it is doing by identifying the actions and sub-tasks it executes [184], which makes it able to react to unstructured environments.