This file contains data structures that implement Dirichlet processes and hierarchical Dirichlet processes. This file does not implement inference algorithms for these structures. See hdp/mcmc.h for examples that use DPs and HDPs and perform inference.

Dirichlet processes

A Dirichlet process (DP) can be understood as a distribution over distributions. That is, samples from a Dirichlet process are themselves distributions. A Dirichlet process is characterized by two parameters: a real-valued concentration parameter $ \alpha > 0 $, and a base distribution $ H $. So if we let $ G $ be a random variable distributed according to a Dirichlet process with parameters $ \alpha $ and $ H $, we can express this as:

\[ G \sim \text{DP}(H, \alpha). \]

There are a handful of equivalent representations of Dirichlet processes. One such representation is the Chinese restaurant process. Imagine a restaurant with an infinite number of tables, numbered $ 0, 1, \ldots $ On each table is an independent sample from the base distribution $ H $. When the first customer walks into the restaurant, they sit at table $ 0 $. When the second customer enters, they either sit at table $ 0 $ with probability $ 1/(1 + \alpha) $ or they sit at table $ 1 $ with probability $ \alpha/(1 + \alpha) $. More generally, when the $ n $-th customer enters the restaurant, they choose to sit at a non-empty table $ i $ with probability proportional to the number of people sitting at that table, or they sit at the next empty table with probability proportional to $ \alpha $.

This process is equivalent to the process of drawing samples from $G$.

\[ \begin{align*} G &\sim \text{DP}(H, \alpha), \\ X_1, X_2, \ldots, X_n &\sim G, \end{align*} \]
where $ X_1, \ldots, X_n $ are drawn independently and identically from $ G $. In the restaurant metaphor, $ X_1 $ is the sample from $ H $ that the first customer discovered at their table, $ X_2 $ is the sample from $ H $ that the second customer discovered, and so on. Thus, this representation describes how to draw samples from a Dirichlet process, when $ G $ is collapsed/integrated out.

It is impossible to write a closed-form expression for the distribution $ G $, since its specification requires an infinite amount of information. But for the useful applications of the Dirichlet process, this is not necessary.

Hierarchical Dirichlet processes

A hierarchical Dirichlet process (HDP) is a hierarchy of random variables, where each random variable is distributed according to a Dirichlet process with base distribution given by the parent in the hierarchy. To be more precise, given a tree $ T $. Every node $ \textbf{n} \in T $ is associated with a random variable $ G_{\textbf{n}} $ such that

\[ G_{\textbf{n}} \sim \text{DP}(G_{p(\textbf{n})}, \alpha_{\textbf{n}}), \]
where $ p(\textbf{n}) $ returns the parent node of $ \textbf{n} $ in $ T $. The root node $ \textbf{0} $ is drawn from a single root base distribution:
\[ G_{\textbf{0}} \sim \text{DP}(H, \alpha_{\textbf{0}}). \]
Note that the concentration parameter may also differ across the nodes in the tree.

The HDP allows statistical information to be shared across groups, and is useful for modeling clustered data.

DP/HDP mixture models

DPs and HDPs are frequently used in mixture models, where the samples from the DP/HDP are not themselves directly observed. Rather, they are inputs to another distribution, which in turn, provides the observed samples. For example, the following is a simple DP mixture model, where the base distribution is Beta and the likelihood is Bernoulli:

\[ \begin{align*} H &= \text{Beta}(2, 4), \\ G &\sim \text{DP}(H, 0.1), \\ X_1, \ldots, X_n &\sim G, \\ Y_i &\sim \text{Bernoulli}(X_i) \text{ where } i = 0, \ldots, n. \end{align*} \]
In the mixture model, we observe $ Y_i $ but not $ X_i $. If the user wishes to use the DP/HDP samples directly, they can do so by using the constant (degenerate) distribution as the likelihood.

Classes, functions, and variables in this file
#defineIMPLICIT_NODE
structnode
boolinit (node< K, V > & n, const V & alpha)
boolcopy (const node< K, V > & src, node< K, V > & dst, hash_map< const node< K, V > *, node< K, V > *> & node_map)
structnode_scribe
boolread (node< K, V > & node, FILE * in, node_scribe< AtomReader, KeyReader > & node_reader)
boolwrite (const node< K, V > & node, FILE * out, node_scribe< AtomWriter, KeyWriter > & node_writer)
structhdp
boolinit (hdp< BaseDistribution, DataDistribution, K, V > & h, BaseParameters & base_params, const V * alpha, unsigned int depth)
boolcopy (const hdp< BaseDistribution, DataDistribution, K, V > & src, hdp< BaseDistribution, DataDistribution, K, V > & dst, hash_map< const node< K, V > *, node< K, V > *> & node_map)
boolread (hdp< BaseDistribution, DataDistribution, K, V > & h, FILE * in, BaseDistributionScribe & base_reader, AtomScribe & atom_reader, KeyScribe & key_reader)
boolwrite (const hdp< BaseDistribution, DataDistribution, K, V > & h, FILE * out, BaseDistributionScribe & base_writer, AtomScribe & atom_writer, KeyScribe & key_writer)
booladd (hdp< BaseDistribution, DataDistribution, K, V > & h, const unsigned int * path, unsigned int depth, const K & observation)
boolcontains (NodeType & n, const unsigned int * path, unsigned int length, const typename NodeType::atom_type & observation)
#define IMPLICIT_NODE UINT_MAX

Each node in the HDP hierarchy has a collection of child nodes. Each child node is indexed by an unsigned int key. This is a special key that represents the set of all keys.

struct node

template<typename K, typename V>

Represents a non-root node in an HDP hierarchy.

To use this structure or hdp, an inference method is required. See hdp/mcmc.h for an example.

Template parameters
K

the generic type of the observations drawn from this distribution.

V

the type of the probabilities.

Public members
array_map< unsigned int, node< K, V > >children
Valpha
Vlog_alpha
array< K >observations
node (const V & alpha)
Vget_alpha () const
Vget_log_alpha () const
static voidmove (const node< K, V > & src, node< K, V > & dst)
static voidswap (node< K, V > & first, node< K, V > & second)
static voidfree (node< K, V > & n)
typedefK atom_type
typedefV value_type
array_map< unsigned int, node< K, V > > node::children

The child nodes of this node in the HDP hierarchy.

V node::alpha

The concentration parameter $ \alpha $ at this node.

V node::log_alpha

The natural logarithm of node::alpha.

array< K > node::observations

The observations drawn from this node.

node::node(
const V &alpha)

Constructs an HDP node with the given concentration parameter alpha and no child nodes or observations.

V node::get_alpha()

Returns the concentration parameter node::alpha.

V node::get_log_alpha()

Returns the logarithm of the concentration parameter node::log_alpha.

static void node::move(
const node< K, V > &src,
node< K, V > &dst)

Moves the HDP node from src to dst.

static void node::swap(
node< K, V > &first,
node< K, V > &second)

Swaps the HDP node in first and second.

static void node::free(
node< K, V > &n)

Releases the memory resources associated with the HDP node n.

typedef K node::atom_type

The type of the observations drawn from this distribution.

typedef V node::value_type

The type of the probabilities.

template<typename K, typename V>
bool init(
node< K, V > &n,
const V &alpha)

Initializes the given HDP node with the concentration parameter alpha and no child nodes or observations.

template<typename K, typename V>
bool copy(
const node< K, V > &src,
node< K, V > &dst,
hash_map< const node< K, V > *, node< K, V > *> &node_map)

Copies the HDP node from src to dst (as well as its descendants, recursively), while adding a entries to node_map mapping the pointers of every source node to the pointer of the corresponding destination node.

struct node_scribe

template<typename AtomScribe, typename KeyScribe>

A scribe structure useful for reading/writing/printing node and hdp objects.

Public members
AtomScribe &atom_scribe
KeyScribe &key_scribe
node_scribe (AtomScribe & atom_scribe, KeyScribe & key_scribe)
AtomScribe & node_scribe::atom_scribe

The scribe for reading/writing/printing observations drawn from HDP nodes.

KeyScribe & node_scribe::key_scribe

The scribe for reading/writing/printing the keys that index the children at each HDP node.

node_scribe::node_scribe(
AtomScribe &atom_scribe,
KeyScribe &key_scribe)

Constructs the node_scribe with the given atom scribe and the key scribe.

template<typename K, typename V, typename AtomReader, typename KeyReader>
bool read(
node< K, V > &node,
FILE *in,
node_scribe< AtomReader, KeyReader > &node_reader)

Reads an HDP node (and all descendants) from in.

Template parameters
AtomScribe

a scribe type for which the function bool read(K&, FILE*, AtomScribe&) is defined.

KeyScribe

a scribe type for which the function bool read(unsigned int&, FILE*, KeyScribe&) is defined.

template<typename K, typename V, typename AtomWriter, typename KeyWriter>
bool write(
const node< K, V > &node,
FILE *out,
node_scribe< AtomWriter, KeyWriter > &node_writer)

Writes the given HDP node (and all descendants) to out.

Template parameters
AtomScribe

a scribe type for which the function bool write(const K&, FILE*, AtomScribe&) is defined.

KeyScribe

a scribe type for which the function bool write(unsigned int, FILE*, KeyScribe&) is defined.

struct hdp

template<typename BaseDistribution, typename DataDistribution, typename K, typename V>

Represents the root node in an HDP hierarchy (or equivalently, a single Dirichlet process). The hierarchy has a maximum depth, as specified by the hdp::depth variable. When new nodes are added to the HDP using the function add, they are initialized using the concentration parameter in hdp::alpha that corresponds to the level of the node in the tree. However, the concentration parameter can easily be changed by the user after the node is created. In addition, the user can add nodes manually to the hierarchy.

To use this structure, an inference method is required. See hdp/mcmc.h for an example.

Template parameters
BaseDistribution

the type of the base distribution.

DataDistribution

the type of the likelihood (as in a DP/HDP mixture model).

K

the generic type of the observations drawn from this distribution.

V

the type of the probabilities.

Public members
BaseDistributionpi
unsigned intdepth
V *alpha
Vlog_alpha
array_map< unsigned int, node< K, V > >children
array< K >observations
hdp (const BaseParameters & base_params, const V * alpha, unsigned int depth)
Vget_alpha () const
Vget_log_alpha () const
static voidfree (hdp< BaseDistribution, DataDistribution, K, V > & h)
typedefK atom_type
typedefV value_type
typedefBaseDistribution base_distribution_type
typedefDataDistribution data_distribution_type
BaseDistribution hdp::pi

The base distribution.

unsigned int hdp::depth

The depth of the HDP hierarchy, where a depth of 1 indicates that the root node is the only node in the hierarchy.

V * hdp::alpha

An array of concentration parameters, with length hdp::depth, one for each level in the HDP.

V hdp::log_alpha

The natural logarithm of the concentration parameter of this node (i.e. hdp::alpha[0]).

array_map< unsigned int, node< K, V > > hdp::children

The child nodes of this root node in the HDP hierarchy.

array< K > hdp::observations

The observations sampled from this distribution.

template<typename BaseParameters>
hdp::hdp(
const BaseParameters &base_params,
const V *alpha,
unsigned intdepth)

Constructs this HDP root node with the given parameters to the base distribution base_params, the given array of concentration parameters alpha (one for every level in the hierarchy), and the given depth of the hierarchy.

Template parameters
BaseParameters

the type of the parameters passed to the constructor of BaseDistribution.

V hdp::get_alpha()

Returns the concentration parameter of this root node.

V hdp::get_log_alpha()

Returns the natural logarithm of the concentration parameter of this root node.

static void hdp::free(
hdp< BaseDistribution, DataDistribution, K, V > &h)

Releases the memory resources of this HDP root node.

typedef K hdp::atom_type

The generic type of the observations drawn from this distribution.

typedef V hdp::value_type

The type of the probabilities.

typedef BaseDistribution hdp::base_distribution_type

The type of the base distribution.

typedef DataDistribution hdp::data_distribution_type

The type of the likelihood (as in a DP/HDP mixture model).

template<typename BaseDistribution, typename DataDistribution, typename K, typename V, typename BaseParameters>
bool init(
hdp< BaseDistribution, DataDistribution, K, V > &h,
BaseParameters &base_params,
const V *alpha,
unsigned intdepth)

Initializes the given HDP root node h with the given parameters to the base distribution base_params, the given array of concentration parameters alpha (one for every level in the hierarchy), and the given depth of the hierarchy.

Template parameters
BaseParameters

the type of the parameters passed to the constructor of BaseDistribution.

template<typename BaseDistribution, typename DataDistribution, typename K, typename V>
bool copy(
const hdp< BaseDistribution, DataDistribution, K, V > &src,
hdp< BaseDistribution, DataDistribution, K, V > &dst,
hash_map< const node< K, V > *, node< K, V > *> &node_map)

Copies the HDP root node (as well as its descendants, recursively) from src to dst, while adding a entries to node_map mapping the pointers of every source node to the pointer of the corresponding destination node.

template<typename BaseDistribution, typename DataDistribution, typename K, typename V, typename BaseDistributionScribe, typename AtomScribe, typename KeyScribe>
bool read(
hdp< BaseDistribution, DataDistribution, K, V > &h,
FILE *in,
BaseDistributionScribe &base_reader,
AtomScribe &atom_reader,
KeyScribe &key_reader)

Reads the given HDP root node h (and all descendants) from in.

Template parameters
BaseDistributionScribe

a scribe type for which the function bool read(BaseDistribution&, FILE*, BaseDistributionScribe&) is defined.

AtomScribe

a scribe type for which the function bool read(K&, FILE*, AtomScribe&) is defined.

KeyScribe

a scribe type for which the function bool read(unsigned int&, FILE*, KeyScribe&) is defined.

template<typename BaseDistribution, typename DataDistribution, typename K, typename V, typename BaseDistributionScribe, typename AtomScribe, typename KeyScribe>
bool write(
const hdp< BaseDistribution, DataDistribution, K, V > &h,
FILE *out,
BaseDistributionScribe &base_writer,
AtomScribe &atom_writer,
KeyScribe &key_writer)

Writes the given HDP root node h (and all descendants) to out.

Template parameters
BaseDistributionScribe

a scribe type for which the function bool write(const BaseDistribution&, FILE*, BaseDistributionScribe&) is defined.

AtomScribe

a scribe type for which the function bool write(const K&, FILE*, AtomScribe&) is defined.

KeyScribe

a scribe type for which the function bool write(unsigned int, FILE*, KeyScribe&) is defined.

template<typename BaseDistribution, typename DataDistribution, typename K, typename V>
bool add(
hdp< BaseDistribution, DataDistribution, K, V > &h,
const unsigned int *path,
unsigned intdepth,
const K &observation)

Adds the given observation to the HDP hierarchy rooted at h to the node at the end of the path. The unsigned int array path, with length depth - 1, provides the indices to follow from each node to its child, in order to locate the node to which the observation is added. If the node does not exist, it is created, with its concentration parameter copied from the appropriate index in hdp::alpha. Thus, depth cannot be larger than hdp::depth of h. If depth == 1, the observation is added to the root node.

template<typename NodeType>
bool contains(
NodeType &n,
const unsigned int *path,
unsigned intlength,
const typename NodeType::atom_type &observation)

Returns true if and only if the given observation is contained in the HDP node at the end of the given path. The unsigned int array path, with given length, provides the indices to follow from each node to its child. The node at the end of this path is checked to determine if it contains the given observation. Note that the path may contain IMPLICIT_NODE elements to specify a set of paths. In this case, all nodes at the end of a path in this set are checked.