Dirichlet Processes 是一个什么样的随机过程？

Dirichlet Processes 究竟是何方神圣？

想象一下，我们有一个数据集，里面的每一个数据点都属于某个“类别”或者“组”。比如，我们可以说一篇新闻报道属于“体育”、“财经”还是“科技”类别；或者一个顾客可以被归为“年轻活跃”、“忠诚稳定”还是“偶尔消费”等等。我们希望能够自动地从数据中发现这些类别，并且知道每个数据点属于哪个类别。更进一步，我们还想知道这个“类别”的数量本身是不是也是不确定的，也就是说，数据中可能隐藏着我们事先不知道的、有意义的划分方式。

Dirichlet Process (DP) 就是一种能够帮助我们实现这个目标的随机过程。它并不是直接生成一组固定的类别，而是描述了一个生成无穷多个类别的概率分布，并且我们从中抽取（或者说“采样”）出有限个类别来给我们的数据点分配。

为了理解 DP，我们需要先摆脱“类别数量是固定的”这个思维定势。我们不是事先设定有 K 个类别，然后去分配数据点。相反，DP 允许我们从一个无限集合中去“抽取”类别，但由于我们拥有的数据点是有限的，所以最终我们只会用到其中有限的几个类别。这个概念有点像我们去一个无限大的商店里买东西，但我们只需要买几件，所以最终只是从这个无限多的商品里拿了几个。

核心思想：从“一个原子”开始，不断“分裂”

DP 的直观理解方式之一是基于一个叫做 “无限混合模型” 的概念。它描述了如何从一个“基本”的分布（比如高斯分布）中生成数据点。

假设我们有一个无限的、可数的名字集（可以想象成是无穷多的标签）。DP 的一个关键作用就是，它提供了一种机制，让我们能够将数据点分配到这些名字（类别）上。

更具体的，我们可以这样来理解 DP 的生成过程：

1. 生成“类别”的参数（或者说是“基本分布”）:
想象我们有一个“基底”分布 $G_0$（比如一个均值为 0，方差为 1 的标准正态分布）。这个 $G_0$ 代表了我们认为数据可能服从的“基本类型”的分布。
DP 的一个核心就是，它允许我们从 $G_0$ 中生成无穷多个“基本分布”的样本。我们通常称这些样本为“原子”或者“聚类中心”。你可以理解为，我们从一个大的“池子”里舀水，每一次舀出来的水（就是一个基本分布的样本），都代表了一种新的潜在类别。
从 DP 的数学定义上来说，一个 DP，记作 $DP(alpha, G_0)$，它生成的是一个离散的概率分布。这个离散分布可以看作是无穷多个狄拉克测度的混合：$G = sum_{k=1}^{infty} pi_k delta_{ heta_k}$。
$ heta_k$ 是从基底分布 $G_0$ 中抽取的样本，它们代表了每个类别的“特征”。
$pi_k$ 是一个概率分布的权重，这些权重加起来等于 1。

2. 给数据点分配类别:
一旦我们有了这些由 $pi_k$ 和 $ heta_k$ 组成的分布 $G$，我们就可以给新的数据点分配类别了。
对于每一个数据点 $x_i$，我们首先从这个离散分布 $G$ 中抽取一个类别标签（或者说是一个“基本分布”的索引 $k$），这个抽取是根据概率 $pi_k$ 进行的。
然后，我们根据被选中的基本分布 $ heta_k$ 来生成这个数据点的值。

关键之处在于，DP 的生成过程有一个很吸引人的性质，叫做“贴纸 वापरा”（Stickingthelanding）或者“马尔可夫链的固定点”性质。这可以更直观地理解为：

假设我们有一堆数据点，我们一个一个地给它们分配类别。

第一个数据点：它肯定会创建一个新的类别。我们从基底分布 $G_0$ 中抽取一个参数 $ heta_1$ 来代表这个新类别，并给它一个权重。
第二个数据点：它有两种选择：
它可能属于第一个数据点创建的那个类别（概率很大）。
它也可能创建一个全新的类别。我们再从 $G_0$ 中抽取一个新的参数 $ heta_2$ 来代表这个新类别。
第三个数据点：它有三种选择：
属于第一个类别。
属于第二个类别。
创建一个全新的类别。

这个过程可以一直持续下去。随着数据点的增多，我们创建新类别的“机会”似乎越来越小，因为我们有越来越多的现有类别可以分配。这就是 DP 的“泊松过程”先验（Poisson Process Prior）的思想，它预示了我们预计会创建多少个新类别。

更形象一点，我们可以借助 “印度自助餐模型”（Chinese Restaurant Process, CRP）来理解 DP。

想象有一个印度餐厅，里面有无限多的桌子（代表类别）。
第一位顾客进来，他可以选择坐在一张已经有人坐过的桌子（分配到一个现有类别），或者选择一张新的空桌子（创建一个新类别）。
如果他选择坐在一张有人坐过的桌子，那么他会被分配到那个桌子代表的类别。
如果他选择坐在一张新的空桌子，那么这张新桌子就代表了一个新的类别。
重点来了：选择哪种方式，以及选择哪张桌子，都有一个概率。这个概率是由一个参数 $alpha$ (称为浓度参数 concentration parameter) 和餐厅里已有的顾客数量决定的。
$alpha$ 控制着我们愿意开新桌子的倾向。如果 $alpha$ 很大，顾客倾向于开新桌子，也就是说，倾向于发现更多的新类别。如果 $alpha$ 很小，顾客更倾向于和别人挤在一张桌子上，也就是说，倾向于将数据点分配到少数几个类别中。
假设现在餐厅里有 $n$ 个顾客，有 $K$ 张桌子（$K$ 个类别）。新来的顾客坐在某张已有桌子的概率是 $frac{n_k}{n+alpha}$，其中 $n_k$ 是坐在第 $k$ 张桌子的顾客数量。而他选择开一张新桌子的概率是 $frac{alpha}{n+alpha}$。

这个 CRP 模型完美地描述了 DP 的一个重要性质：它生成的是一个数据点可以被分配到的类别的集合，并且这个集合的大小（类别数量）是随机的，由 DP 的参数决定。尽管 DP 的理论生成的是无穷多个类别，但由于我们拥有的数据点是有限的，所以实际上我们只会用到有限个类别。

DP 的关键参数：$alpha$ 和 $G_0$

$alpha$ (浓度参数 concentration parameter):
这是 DP 的一个非常重要的参数。它控制着新类别的生成率。
如果 $alpha$ 大，DP 倾向于生成更多的类别，每个类别中的数据点相对较少。数据点被分配到许多不同类别的可能性更大。
如果 $alpha$ 小，DP 倾向于生成更少的类别，每个类别中的数据点会更集中。数据点更有可能被分配到少数几个类别中。
可以理解为，$alpha$ 是一个“稀释”参数。它衡量了有多少“原子”（新类别）会被从基底分布 $G_0$ 中抽取出来。
$G_0$ (基底分布 base distribution):
这是 DP 用来生成每个“潜在类别”的参数（或者说基本分布）的分布。
$G_0$ 的选择非常重要，它决定了我们期望的类别特征是什么样的。
例如，如果我们假设数据点是连续值，并且我们认为不同类别的值服从不同的高斯分布，那么 $G_0$ 就可以是一个高斯分布的分布（比如一个关于均值和方差的分布）。
如果 $G_0$ 本身是一个离散分布，那么 DP 生成的也是一个离散的离散分布（可以想象成是嵌套的离散分布）。

为什么 DP 如此有用？

1. 非参数性（Nonparametrics）: DP 的“非参数性”是指它不像传统的聚类算法那样需要预先指定类别的数量 K。类别数量是模型自身学习到的。这对于我们不知道数据到底有多少个真实类别的场景非常有用。
2. 灵活性: DP 可以与各种其他模型结合，构建出非常灵活的生成模型。例如，DPMixture Models 是非常强大的聚类模型。
3. 强大的先验: DP 提供了一种非常自然的、从数据中发现潜在结构的先验。它倾向于将相似的数据点分到同一个类别。
4. 潜在的类别发现: DP 本身就包含了发现新类别的机制。

举个例子

假设我们要给一群学生按他们的学习风格分类。我们不知道有多少种学习风格。

我们选择一个 DP，其参数是 $alpha$（一个我们设定的值，比如 10）和 $G_0$（我们认为学习风格的一些特征，比如他们的平均学习时间、偏好的学习资源等，可以假设这些特征服从一个多维高斯分布）。
我们用 DP 来生成数据点的类别分配。
第一个学生进来，他创建一个新的学习风格类别。我们从 $G_0$ 中抽取一组学习风格的特征来代表这个新风格。
第二个学生进来，他可能也倾向于创建一个新风格，或者加入第一个学生的风格。
随着越来越多的学生进来，他们会被分配到已经存在的学习风格中，或者创建新的学习风格，直到所有的学生都被分配。
最终，我们可能发现有 35 种主要的学生学习风格，并且每一类学生都有其对应的学习风格特征。

总结

Dirichlet Process 是一种生成概率分布的随机过程，它非常适合用于建模数据的潜在分组或聚类结构，尤其是当类别的数量事先未知时。它通过一种“无限混合”的思想，允许我们从一个无限多的潜在类别中进行选择，但由于数据的有限性，最终只使用了有限个类别。其核心在于通过浓度参数 $alpha$ 控制新类别的生成概率，并通过基底分布 $G_0$ 定义了每个潜在类别的基本特征。印度自助餐模型（CRP）是一个非常形象的比喻，帮助我们理解 DP 如何通过顾客的选择来动态地分配类别。DP 的非参数性和灵活性使其成为机器学习和统计建模中一个非常强大的工具。

网友意见

Dirichlet Processes 对于初学者很难理解, 因为很多材料都喜欢从不同角度去讲Dirichlet Processes, 有些材料还将Dirichlet 过程的构造和定义混为一谈, 这些介绍对于整体结构触之不全, 很容易把初学者绕晕. 这篇文章打算从简入深的讲述Dirichlet Processes, 并假设大家已经知道了Dirichlet Distribution, 首先来看一下答题结构:

什么是概率空间(Probability Space) 和概率测度(Probability Measure)?
什么是随机过程 (Stochastic Process)? 什么是随机过程的有限边缘分布(finite marginal distribution)?
Dirichlet Processes 的定义是什么, 为什么它是一种随机过程?
安照定义, Dirichlet Processes存在与否? 如何构造?
Dirichlet Processes 有哪些性质?
Dirichlet Processes 用于mixture model 有什么好处?
如何从Dirichlet Processes中采样? (与4有重合)
Dirichlet Processes 用于概率图模型中, 如何进行推理(Inference)?
Hierarchical Dirichlet Processes 又是什么?

1. 什么是概率空间(Probability Space) 和概率测度(Probability Measure)?

这一部分对于理解Dirichlet Processes的定义有非常重要的作用, 这里仅对这两个概念进行简单介绍, 本人并没有学过测度论, 所以讲述的内容不需要什么基础.

1.1 概率空间 Probability Space

概率空间由三部分组成, 在看这三部分到底是什么之前, 我们先大概理解一下概率空间是什么东西, 简单来说就像函数有定义域一样, 概率当然也要有定义域, 它就是概率空间. 换句话讲, 概率和随机变量是定义在概率空间上的. 下面给出概率空间三个部分的定义

样本空间(sample space), 是某个随机实验的所有可能结果(outcomes), 所以样本空间是一个集合 of outcomes, 集合中的每一个元素都可能在某次随机实验中得到. 例如对于掷骰子实验, .
事件集合(events set), 是所有事件的集合, 事件(event )是一个包含0个以上结果(outcome )的集合(a set contains zeros or more outcomes). 比如空集, 或者掷得骰子点数1或2, 记为 . 另外这个事件集合满足三个性质, 既 (1) 包含 , (2) 该集合对于交操作封闭, (3)对于可数个并操作封闭. 满足这三个性质的集合被称作 -algebra, 所以事件集合是一个 -algebra.
P 概率, 这个最好理解, 就是我们知道的概率函数, 输入是一个事件, 输出是事件发生的概率, 在0 到 1之内.

基于概率空间, 概率和随机变量才有了定义, 一句话总结最关键的信息: 随机变量是一个函数, 它的定义域是 ,值域通常是 . 概率P也是一个函数, 定义域是 ,值域是[0,1]. 有些人可能会问了, 既然这么定义, 为啥随机变量还能作为概率函数的输入? 一个等式来解决这个疑问:

式中 S , 假设是X的值域. 所以我们平常用的概率函数其实是Pr, 而不是P.

1.2 概率测度 Probability Measure

这里概率测度分为两部分, 首先它得先是一个测度(measure), 之后, 它应该是一个能够反应概率的测度. 那么什么是测度呢? 简单来讲, 定义在集合 X 上的测度, 是一个函数, 这个函数的输入是X的任意子集, 输出是大于等于0的实数. 所以测度这个函数的定义域是 , 值域是[0, +infinity]. 注意到这里表述的是“X全部子集”这个集合的一部分, 因为这个定义域还需满足上一节中所说的 -algebra的三个性质, 也就是说定义域是一个 -algebra. 测度这个概念这么看起来很抽象, 但是生活中处处都会用到测度这个东西, 比如长度、体积、面积等等都是测度. 另外测度这么一个函数还需要满足一些性质, 比如可加性等等, 这里不做具体介绍. 大家只需要先记住测度是一个函数. 而且它的输入可以是X的任意子集, 是不是觉得这个定义域和之前讲的事件集合挺像的? 哈哈那么我们来看看概率测度!

讲完了概率空间和测度, 大家应该很容易就能猜到什么是概率测度了. 没错, 概率空间中的P就是概率测度! 更正式的说的话, 概率测度P 就是一个定义在样本空间上的测度函数, 它的定义域是 , 值域是[0, 1], 并且这个函数满足概率的定义(三个公理化条件, 这里不讲了很常见).

2. 随机过程 (Stochastic Processes) 和有限边缘分布 (Finite Marginal Distribution)

Dirichlet Processes 是一种随机过程, 所以要想真正理解Dirichlet Processes, 我们当然要知道什么是随机过程. 另外随机过程的有限边缘分布也很重要, 因为这个东西告诉我们了这个随机过程为什么叫Dirichlet. 类似的, 高斯过程的名字也是从这个过程的有限边缘分布来的.

2.1 Stochastic Porcesses

随机过程(stochastic/random process)又被称为随机函数(random function, 如果函数的输出是多元的话则被称为随机场, random field), 这个名字很直接的告诉我们了随机过程的本质, 它就是一个用来刻画函数随机性的一个东西. 随机变量是一个具有随机性的“值”X 或者说“个体”, 相对应的随机过程就是一个具有随机性的函数X(t). 上面曾经讲过随机变量其实也是一个函数: , 那么随机过程就是有两个输入的函数: . 这么来看是不是觉得随机过程其实是随机变量的自然延伸? 不过注意它们的“随机性”都在于上.

我们来看它的准确定义是什么:

一个随机过程定义在概率空间上, 可以表示为 , 其中T被称作索引集合(Index set), 它可以是多维空间. S 为状态空间(State space), 是一个measureable space, 可以先想像为实数空间. 另外对于任意一个固定的 , 被称作采样函数(sample path/function), 就像是随机变量X的一个实现(realization)一样, 是随机过程的一个实现. 所以我们从随机变量中draw出来的是一个“值“, 而在随机过程中draw出来的是一个函数. In another perspective, 对于任意一个固定的 , 则退化为一个定义在给定概率空间上的随机变量. 有时候为了方面, 我们会省略掉部分, 记随机过程为 .

2.2 Finite-Dimensional Marginal Distribution

像随机变量有一个概率分布P来刻画其随机性一样, 随机过程的随机性也应当有一个分布来刻画. 随机函数这个概念虽然很好理解, 但是它并不容易去表述性质, 因为函数是由无穷个随机变量组成的, 我们可以刻画有限个随机变量的性质, 但无法直接刻画无穷个随机变量. 那么怎么办呢? 这个时候有限边缘密度就发挥作用了! 而且这个东西很巧妙的用有限个随机变量去刻画随机过程这么一个无限的东西, 数学上很多定义都是用有限来刻画无限.

The distribution of a stochastic process is uniquely determined by the family of all its finite-dimensional marginal distribution (反之亦然). 下面给出finite-dimensional marginal distribution的定义, 并且注意到上面说的 all.

对于一个随机过程 , 对于一组索引 , 一个有限边缘分布是指的联合概率分布, 可以用cdf function 来刻画, 对于连续随机变量. 也可以用pdf function 来刻画. 下面给出cdf刻画的有限边缘分布:

注意到这样的有限边缘分布有无限个, 因为对于任意 , 任意的 , 都有一个有限边缘分布. 而这个随机过程的随机性, 就是由所有的有限边缘分布刻画的, 两者相互等价.

用无限个有限边缘分布来刻画一个随机过程的随机性, 这样一个概念看起来不好理解. 不妨去看看高斯过程是怎么定义的, 会帮助大家更好的理解. 具体的高斯过程定义这里不做介绍, 我只说一个特点, 高斯过程的任意有限边缘分布都是一个高斯分布, 所以这个过程才被称作高斯过程. 类似的, Dirichlet Process的名字, 也是因为它的有限边缘分布是一个Dirichlet Distribution.

3. Dirichlet Process 的定义是什么? 它为什么是一个随机过程?

重头戏来了, 有了前面几个概念的基础, 相信大家能够很深入的明白Dirichlet Process这东西到底是啥. 首先一句话概括Dirichlet Processes是什么: Dirichlet Processes是一类随机过程, 而且这类随机过程的实现 (realization), 或者说 sample path/function, 是概率测度. 也就是说跟随机过程一样, 从其中draw出来的是一个函数, 另外这个函数还得是概率测度. 这个概念十分重要, 如果没有看懂, 请回到前两节仔细看懂概率测度和随机过程的定义.

我们来看看能否根据上面那句话, 把Dirichlet Processes (DP)的符号表示安照随机过程的定义写出来: 因为DP是随机过程, 我们可以记一个DP为 , 由于是一个概率测度, 假设这个概率测度定义在集合空间上, 那么集合就对应于的所有子集, 则是[0,1] 的概率值空间. Ok, so far so good.

对于这么一个实现是概率函数的随机过程, 刻画它随机性的分布又会是什么呢? 上一节中我们讲过随机过程的分布可以由所有的有限边缘分布等价刻画, 而且还讲过随机过程的命名和它的有限边缘分布很有关系, 大家应该都已经猜到了, 对于Dirichlet Processes, 它的有限边缘分布应该是Dirichlet Distribution. 下面直接给出Dirichlet Processes的formal definition:

给定一个可测集合 , 一个正实数 (concentration parameter), 和一个基分布(base distribution) (基分布是连续分布), Dirichlet Processes是一个随机过程, 它的sample path 是一个定义在上的概率测度. 记集合的任意有限分割(partitions) 为 , 则:

上面的式子便是DP的严格定义了, 如果有人疑惑为什么set A_i 是G的输入, 请温故一下概率测度这个函数的定义域是什么. 有些同学可能会有疑问, 上述真的是Dirichlet Processes这个随机过程的有限边缘分布的随机变量么? 注意到对于 , , 结合第二节中随机过程的有限边缘分布的定义, 不难看出的分布就是Dirichlet Process的一个有限边缘分布. 但是, 之前我们讲过一个stochastic process 是由所有的有限边缘分布所刻画的, 而对于Dirichlet process, 它的定义中严格来说并没有要求所有的都符合Dirichlet distribution, 因为还要满足组成partitions这个条件. 即它们的union为全集 , 而且两两之间不相交. 所以, Dirichlet process是一种很特殊的stochastic process, 它的随机性是有所有的partitions的有限边缘分布来刻画的, 而不是所有可能的有限边缘分布. ( 一个很美的地方: Dirichlet distribution本来就要求所有的random variables的和恒为1, 这里partitions和概率测度定定义正好保证了 .)

4. 安照定义, Dirichlet Process存在与否? 如何构造?

单从Dirichlet Process的定义来看, 似乎它很厉害也很漂亮, 它的所有满足partitions要求的有限边缘密度都是符合Dirichlet Distribution的, 而Dirichlet Distribution又有很多漂亮的性质, 这就意味这Dirichlet Process也有很多漂亮的性质可以推出, 下一节我们将讲解Dirichlet Process的几个重要性质. 但是, 似乎这个定义的要求有点强: 任意draw from this process都是一个概率测度, 或者说概率分布, 而且所有满足有限partitions要求的有限边缘密度都是符合Dirichlet Distribution, 那么这么一个process真的可以存在么? 如果可以存在, 那么怎么样构造出这样一个过程呢? 首先提及一下: 现有的资料中讲解的Dirichlet Process的各种各样的定义, 其实是它的多种构造方法, 这一点明白后可以避免很多误解. (构造方法算是独立的一块, 先跳过)

5. Dirichlet Processes 有哪些性质?

Dirichlet Processes 的性质是由它的定义推出来的, 这些性质大多用到了Dirichlet distribution 的性质, 我们先提及Dirichlet distribution的几个重要性质.

5.1 Dirichlet distribution 的性质

5.1.1 PDF, 期望, 及方差

5.1.2 共轭先验(Conjugate prior) for 多项分布(Multinomial distribution)

数学表示如下:

5.1.3 Collapsing 性质

5.1.4 Splitting 性质

5.1.5 Renormalization 性质

最好自己推一下这些性质, 不会的可以参考:https://www.cs.cmu.edu/~epxing/Class/10708-14/scribe_notes/scribe_note_lecture19.pdf

5.2 Dirichlet Process 的性质

5.2.1 抽样出的distribution是离散分布的概率为1 [Discreteness property]

5.2.2 期望和方差

5.2.3 Posterior distribution是 Dirichlet Process

5.2.4 Posterior predictive distribution

5.2.5 Clustering property

Reference:

[1] Teh, Yee Whye. "Dirichlet process."Encyclopedia of machine learning(2010): 280-287.

[2] Notes on Dirichlet Processes (Code available!)

类似的话题

Dirichlet Processes 是一个什么样的随机过程？

Dirichlet Processes 究竟是何方神圣？想象一下，我们有一个数据集，里面的每一个数据点都属于某个“类别”或者“组”。比如，我们可以说一篇新闻报道属于“体育”、“财经”还是“科技”类别；或者一个顾客可以被归为“年轻活跃”、“忠诚稳定”还是“偶尔消费”等等。我们希望能够自动地从数据中发现.............
狄利克雷函数（Dirichlet Function）有什么用处？

狄利克雷函数，这玩意儿听起来挺高大上的，但实际上，它在数学里扮演着一个挺特别的角色，有点像数学世界里的“特立独行者”。说它有什么用处，得看你从什么角度去理解了。首先，我们得把狄利克雷函数是个啥弄明白。简单来说，它长这样：$$f(x) = egin{cases}1 & ext{if } x ex.............
沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌）是怎样的？

沃罗诺伊图，又称狄利克雷镶嵌，是一种非常直观且应用广泛的空间划分方式。它的核心思想是：在一个平面（或者更高维的空间）上，给定一组离散的点，我们想要把整个空间划分成若干个区域，使得每个区域里的所有点，都离这个区域的“代表点”（也就是我们给定的那个点）比离其他任何代表点都要近。想象一下，你在一片空地上插.............