- 2014 年 5 月 20 日
- 瓦西利斯·弗里尼奥提斯(Vasilis Vryniotis)
- 。 没意见
本文是有关利用Dirichlet过程混合模型进行聚类的系列文章的第三部分。 上次我们基于Dirichlet分布定义了有限混合模型,并对如何使该特定模型无限化提出了疑问。 我们简要讨论了当k个簇趋于无穷大时采取模型极限的想法,但是由于我们强调了这样一个物体的存在并非无关紧要(换句话说,我们实际上如何“取模型的极限” ”?)。 提醒一下,我们想使k为无限大的原因是因为这样我们将拥有一个非参数模型,该模型不需要我们预先定义数据中簇的总数。
更新:Datumbox机器学习框架现在是开源的,免费提供给 下载。 检出com.datumbox.framework.machinelearning.clustering软件包,以了解Java中Dirichlet Process Mixture模型的实现。
尽管我们的目标是建立一个能够对数据集进行聚类的模型,但在此之前我们必须讨论Dirichlet过程。 我们将提供严格的数学定义和DP的更直观的解释,并且我们将讨论构造过程的方法。 这些构造/表示形式可以看作是一种在“现实生活”中查找狄利克雷特过程发生的方式。
尽管我试图以一种更容易理解的方式修改研究报告,但在跳入使用模型之前,定义必要的数学工具和分布仍然很重要。 Dirichlet过程模型是积极研究的主题,但是在使用它们之前,确实需要对统计和随机过程有很好的了解。 另一个问题是,正如我们将在本文中看到的那样,Dirichlet流程可以用多种方式表示/构造。 结果,几篇学术论文使用了完全不同的表示法/惯例,并从不同的角度审视了该问题。 在这篇文章中,我尝试尽可能简单地解释它们,并使用相同的符号。 希望这两篇即将发表的文章将使事情变得更加清晰,这两篇文章着重于Dirichlet过程混合物模型的定义以及如何实际使用它们执行聚类分析。
1. Dirichlet过程的定义
Θ空间上的Dirichlet过程是随机过程。 它是“θ空间上的概率分布”上的概率分布和 从中得出离散分布。 Dirichlet分布更正式地是概率度量的分布。 一种 概率测度 是空间θ到[0,1]的子集的函数。 G是DP分布随机概率测度,表示为 ,如果是任何分区(A1,…一种n)Θ .
图1:有限分区上的边际是Dirichlet分布的。
DP有两个参数:第一个是基本分布G0 这就像一个卑鄙 。 第二个是强度参数α,它严格为正,起反方差的作用 。 它确定输出分布值的重复程度。 a的值越高,重复次数越小; 值越小,输出分布值的重复率越高。 最后,Θ空间是定义DP的参数空间。 此外,空间Θ也是G的定义空间0 与G相同
更简单,更多 直观的方式 下面说明Dirichlet过程。 假设我们有一个可以用任何有限方式划分的空间Θ(A1,…,一种n)和为概率分配概率的概率分布G. G是关于θ的特定概率分布,但还有许多其他的分布。 Θ上的Dirichlet过程正是对此建模。 它是空间Θ上所有可能概率分布的分布。 Dirichlet过程用G参数化0 基本函数和α浓度参数。 可以说,G根据参数为DP的参数α和G分布0 如果G分配给Θ分区的概率的联合分布遵循Dirichlet分布。 或者,我们可以说G分配给Θ的任何有限分区的概率遵循Dirichlet分布。
图2:Dirichlet过程的图形模型
最后在上方,我们可以看到 DP的图形模型。 我们应该注意,α是标量超参数G0 是DP的基本分布,G是从DP采样的Θ参数空间上的随机分布,它为参数和θ分配了概率i 是从G分布得出的参数向量,它是Θ空间的元素。
2.后Dirichlet过程
后Dirichlet过程由 弗格森。 我们首先从Dirichlet过程中得出随机概率测度G, 。 由于G是Θ上的概率分布,因此我们也可以从该分布中采样并得出独立的,均匀分布的采样θ1,...,θn 〜G。由于Dirichlet过程的抽奖是离散分布,我们可以表示 哪里 是的简写 这是一个增量函数,如果需要则取1 和0在其他地方。 有趣的结果是,由于G是这样定义的,因此不同样本具有相同值的概率为正 。 稍后我们将看到,这将创建一个聚类效果,可用于对数据集执行聚类分析。
通过使用以上定义和观察,我们希望在给定样本θ的情况下估计Dirichlet过程的后验。 然而,由于我们知道 和 通过使用贝叶斯规则以及Dirichlet和多项式之间的共轭,我们得到 和 .
公式1:后狄利克雷过程
此属性非常重要,并且由各种DP表示形式使用。
3. Dirichlet过程表示
在前面的部分中,我们定义了Dirichlet过程并提出了其理论模型。 我们必须回答的一个重要问题是我们如何知道这样一个对象存在以及我们如何 构造并代表 Dirichlet过程。
存在的最初迹象是由 弗格森 他使用了Kolmogorov一致性定理,给出了Dirichlet过程的定义并描述了后Dirichlet过程。 继续他的研究, 布莱克韦尔和麦昆 利用de Finetti定理证明了这种随机概率测度的存在,并介绍了满足Dirichlet过程性质的Blackwell-MacQueen缸模型。 1994年 塞瑟拉曼 通过引入Stick-breaking结构,提供了另一种简单而直接的方式来构造DP。 最后,由 奥尔德斯 他介绍了中餐厅流程是构建Dirichlet流程的有效方法。
Dirichlet过程的各种表示形式在数学上是等效的,但是它们的表示形式不同,因为它们从不同的角度检查问题。 下面我们将介绍文献中最常见的表示形式,我们将重点介绍中餐厅过程,该过程为构造狄利克雷过程的推理算法提供了一种简单且计算效率高的方法。
3.1 Blackwell-MacQueen方案
Blackwell-MacQueen骨灰盒方案可用于表示Dirichlet过程,由 布莱克韦尔和麦昆。 它基于Pólya缸方案,可以看作是无需替换的相反采样模型。 在Pólya骨灰盒方案中,我们假设我们有一个不透明的骨灰盒,其中包含彩色球,并且我们随机绘制球。 当我们画一个球时,我们会观察它的颜色,然后将其放回骨灰盒中,然后再添加一个相同颜色的球。 Blackwell和MacQueen使用了类似的方案来构造Dirichlet过程。
该方案产生一个θ序列1,θ2,…与 条件概率 。 在这个方案中,我们假设G0 是颜色和每个θ的分布n 代表放置在the中的球的颜色。 的 算法 如下:
· 我们从一个空的开始。
· 与概率成正比 α 我们画 然后在骨灰盒中添加一个这种颜色的球。
· 以与n-1成正比的概率,我们从the中抽出一个随机的球,观察其颜色,将其放回the中,并在and中添加一个相同颜色的附加球。
以前,我们从Dirichlet过程开始,并推导了Blackwell-MacQueen方案。 现在,让我们从Blackwell-MacQueen方案开始反过来,推导DP。 由于θi 如果从G中以同等方式绘制,则它们的联合分布对于任何有限排列都是不变的,因此它们是可交换的。 因此,通过使用德芬内蒂定理,我们必须使度量具有一定的分布,以使它们成为同id,并且这种分布就是狄利克雷过程。 结果,我们证明了Blackwell-MacQueen缸方案是DP的表示,它为我们提供了构造它的具体方法。 正如我们将在后面看到的,该方案在数学上等同于中餐厅过程。
3.2防摔结构
折断构造是表示Dirichlet过程的另一种方式,由 塞瑟拉曼。 这是形成 分发并使用 依此类推:我们假设杆的长度为1,我们在位置β处将其折断1 我们分配π1 等于我们折断的木棍部分的长度。 我们重复相同的过程以获得π2,π3,…等; 由于定义了该方案的方式,我们可以无限次地继续执行它。
基于上面的πk 可以建模为 ,其中 与以前的方案一样,θ是通过基本分布直接采样的 。 因此,G分布可以写为以π加权的增量函数之和k 等于的概率 。 因此,“折断”结构为我们提供了一种简单直观的方法来构造Dirichlet过程。
3.3中餐厅流程
中餐厅流程,由 奥尔德斯,是表示Dirichlet过程的另一种有效方法,可以直接与Blackwell-MacQueen缸体方案关联。 该方案使用 依此类推:我们假设有一家中餐厅,桌子无限多。 当顾客进入餐厅时,他们会随机坐在任何一个被占用的桌子上,或者他们选择坐在第一个可用的空桌子上。
CRP在正整数的分区空间上定义分布。 我们先画θ1,...θn 来自Blackwell-MacQueen缸设计。 正如我们在前面的部分中讨论的那样,我们期望看到聚类效应,因此唯一θ值k的总数将大大小于n。 因此,这定义了集合{1,2,…,n}在k个簇中的分区。 因此,从Blackwell-MacQueen缸方案中提取的图像会引起{1,2,…,n}集的随机划分。 中餐厅的过程是由此引发的 分区分配。 算法如下:
· 我们从一家空餐厅开始。
· MTT综合医学训练疗法国际教学中心st 客户总是坐1st 表
· n + 1th 客户有2个选择:
o 坐在第一空置桌子上
o 坐在第k个已占用表中的任何一个上
哪里 那张桌子上的人数是多少
其中,α是DP的分散值,n是给定时间餐厅的顾客总数。 潜变量zi 存储i的表号th 客户,取值从1到kn 哪里kn 是n个顾客在餐厅中时已占用的桌子总数。 我们应该注意n 总是小于或等于n,平均约为 。 最后我们要注意表排列的概率 对于排列是不变的。 因此zi 是可交换的,这意味着具有相同客户数量的表具有相同的概率。
中餐厅流程与Pólya骨灰盒计划和Dirichlet流程紧密相关。 CRP是一种指定 分区分配 (表分配)n个点,并且可以在潜在变量z的空间上用作先验i 这 确定集群分配。 CRP等同于Pólya的urn方案,不同之处在于,它没有为每个表/集群分配参数。 去 从CRP到Pólya的骨灰盒计划 我们画 对于所有表k = 1,2…,然后对于每个xi 分组到表zi 分配一个 。 换句话说,分配给新的xi 表格的参数θ。 最后因为 我们不能分配 从一开始就将θ赋给无限表,每次有人坐在新表上时,我们都可以分配一个新θ。 由于上述所有原因,CRP可以帮助我们构建计算效率高的算法,以对数据集执行聚类分析。
在这篇文章中,我们讨论了Dirichlet过程及其构造方法。 在下一篇文章中,我们将使用以上想法。 我们将介绍Dirichlet过程混合模型,并使用中餐厅代表来构建Dirichlet过程和瓶坯聚类分析。 如果您错过了几点,请不要担心,因为接下来的两篇文章将使事情变得更加清晰。
希望您对此帖子感兴趣。 如果您这样做了,请花点时间在Facebook和Twitter上分享它。 🙂