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

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

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

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

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

1.1 概率空间 Probability Space

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

1. 样本空间(sample space), 是某个随机实验的所有可能结果(outcomes), 所以样本空间是一个集合 of outcomes, 集合中的每一个元素都可能在某次随机实验中得到. 例如对于掷骰子实验, .
2. 事件集合(events set), 是所有事件的集合, 事件(event )是一个包含0个以上结果(outcome )的集合(a set contains zeros or more outcomes). 比如空集, 或者掷得骰子点数1或2, 记为 . 另外这个事件集合 满足三个性质, 既 (1) 包含 , (2) 该集合对于交 操作封闭, (3)对于可数个并 操作封闭. 满足这三个性质的集合被称作 -algebra, 所以事件集合是一个 -algebra.
3. 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!)