层次狄利克雷过程简介(Hierarchical Dirichlet Process, HDP)

标签:## 时间:2018/09/29 16:32:09 作者:小木

层次狄利克雷过程(Hierarchical Dirichlet Process,HDP)是由Yee Whye Teh等人在2004年提出模型。这个模型解决的是不同组数据内的聚类问题。

假设我们的观测数据是一组数据集合(一组是一个group,比如说一个文档),我们希望在每组数据内进行聚类,得到一些簇(clusters),它可以描述这组数据内部的结构。但是每组数据内部的簇有多少个我们是不知道的。同时,我们希望组和组之间的簇是共享的。

举一个实际的例子,在信息检索领域,我们通常需要为文档集合之间的关系建模。文档通常都基于词袋模型假设,具有可交换性,即单词之间的顺序被忽略掉。同时,我们也认为一个文档中的单词是来自几个潜在的簇(或者称为主题),每一个主题一般都是一个基于基本词汇的多项式分布。因此,如果一篇文档是关于大学基金的,那么这篇文档中的单词可能是来自于“教育”和“财经”两个主题的结果。考虑有类似的这样一组文档,我们希望主题在不同的文档之间是共享的。比如,如果语料中还包含大学足球,那么其主题可能是“教育”和“体育”,我们希望前一个主题“教育”和之前的大学基金的文档中的“教育”主题是相关的。

我们考虑数据有是包含几组的情况。首先,我们考虑有一个随机测度的集合G_j,对于第j组数据来说,G_j是与该组数据相关的狄利克雷过程DP(\alpha_{0j},G_{0j})。为了解决这样的聚类问题,我们需要将组间数据的DP连接起来。之前的作者通常是把不同组之间的狄利克雷过程中的参数连接起来的,即把G_{0j}或者\alpha_{0j}之间连接起来。以G_{0j}为例,一直很自然的假设是使用层次模型,假设测度G_j是从一个DP过程DP(\alpha_0,G_0(\tau))抽取的独立样本,其中G_0(\tau)是一个参数为\tau的有参分布。将\tau积分掉之后就可以得到DP之间的依赖关系。这样不同组之间的G_j就可能是相等的。

这是一个很简单的思路,但是却无法解决我们的问题。当G_0(\tau)是一个连续分布的时候(例如G_0是一个高斯分布,均值是\tau),在这种情况下,G_j是来自于G_0(\tau)的独立的样本,因此,他们之间的原子并不是相等的。因此,尽管每一组内的簇都可以通过DP变成离散的情况,但是不同组之间的原子是不一样的,因此组和组之间的簇并不共享。这时候,我们只能假设G_0是一个离散的分布,这样组和组之间的簇就可以共享了。但是这种假设限制过大,不利于模型的应用。

我们用j表示数据中组的索引,用i表示每个组内部的观测值的索引,我们假设x_{j1},x_{j2},\cdots在组内部是可交换的。我们同样假设这些观测值在组间也是可交换的,也就是说,如果x_j={(x_{j1},x_{j2},\cdots)}表示组j中所有的观测值,那么x_1,x_2,\cdots也是可交换的。

假设每一个观测值,都是从一个混合模型中独立抽取的样本,那么每个观测值都有一个与之相关的混合分量(也就是这个混合分布中的一个)。我们用\theta_{ji}表示与第j组数据中第i个观测值相对应的分布,其参数是\theta_{ji}。我们称\theta_{ji}是因子。注意,并不是所有的因子都是不同的,它们之间可以有相同的。我们用F(\theta_{ji})表示给定因子\theta_{ji}条件下,x_{ji}的分布。我们用G_j表示第j组数据的因子\theta_j=(\theta_{j1},\theta_{j2},\cdots)的先验分布。因此,我们的模型如下:

\theta_{ji} | G_j \sim G_j

x_{ji} | \theta_{ji} \sim F(\theta_{ji})

接下来我们就要决定G_j是啥了。G_j是每一个因子的先验,当G_j已知的时候(先验通常都是我们自己设置的),对第j组下的第i个数据的产生是首先从这个先验中产生这个数据所属的分布的参数\theta_{ji},然后从F(\theta_{ji})中产生数据x_{ji},这个过程如下图所示。由于我们假设组内的数据也是来自不同的因子的(也就是来自于不同的簇,簇即英文中的cluster),因此每个数据对应的因子\theta_j都不一定是相同的,但也不能都不相同。应该是当组内某些数据来自于同一个簇的时候,他们所属的分布是相同的,这时候他们的参数\theta_{ji}就是相同的。比如,我们假设每个数据x_{ji}都是来自于一个高斯分布的多元向量,且不同的数据所属的高斯分布可能不同,但是他们共享一个先验,那么这时候,\theta_{ji}=(\mu_{ji},\Sigma_{ji})F(\theta_{ji})=N(\mu_{ji},\Sigma_{ji}),当均值和方差未知的情况下,这个时候G_j就是正态-逆威沙特分布(共轭先验)。

当我们要对组内部数据进行聚类的时候,我们希望属于同一个簇的数据,其所属的分布的参数相同,即相应的\theta_{ji}是相同的。但是,当G_j是一个连续分布的时候,例如上面例子的正态-逆威沙特分布,从这个连续分布中抽取的参数\theta_{ji}是不可能有完全一样的两个值。这显然不符合我们的要求。这时候,我们可以采用Dirichlet Process先验来解决这个问题,即我们以一个和G_j形状很相似的分布G_0作为基分布,它和一个正实值参数\alpha_0一起,形成一个Dirichlet Process,我们用这个DP作为因子的先验,取代之前的连续型的分布。我们的\theta_{ji}就是从这个DP中抽取的。根据DP的性质,这样做有几个好处:1)这个DP的样本是一个随机测度,它的均值就是G_0,也就是说我们并没有完全改变原来参数的先验,新的先验与原来的先验很接近;2)DP的样本是一个离散的情况,且通过\alpha_0可以决定这个离散程度,从而可以得到相同的因子的先验。这就解决了先验是连续分布时候,样本不可能相同的情况了。于是,新的基于Dirichlet Process聚类模型也就出来了。如下图所示:

但是,这是对一组数据的结果,如果我们有很多组数据,对于每一个数据我们都使用DP构造,这时候,虽然每组数据内部是可以得到非参的聚类结果,但是组与组之间的数据显然没有任何联系。为了使不同组之间的聚类产生联系,我们可以把每一组数据的先验连接起来。例如,每一组数据都有一个DP(\alpha_{0j},G_{0j}),自然的想法是假设不同组的G_{0j}都是来自于同一个先验分布G_0,如下图所示:

这样做依然有问题,因为当G_0是一个连续分布的时候,G_{01}G_{02}等是不可能相等的,虽然每一组数据内部可以通过DP来获得簇,但是不同组之间的簇是不共享的,这依然无法解决我们的问题。

对于这个问题,作者的解决思路很直接,也很暴力,既然当G_0是一个连续分布的时候,G_{01}G_{02}等是不可能相等,那么直接把G_0变成一个DP就可以了,这样G_{01}G_{02}就可以是相等了,那么相同的G_{0j}下小组的簇自然就可以共享了。

欢迎大家关注DataLearner官方微信,接受最新的AI技术推送
相关博客
Back to Top