Dirichlet process 应用

Dirichlet process 很久以前试图研究过一次,但是翻来覆去还是有些不明白。这次好生处理下。

一些相关的概念

Dirichlet process 是一个随机过程,有两个参数,比如我们记为 \mathrm{DP} (\alpha, G_0),其中 G_0 是定义在某个样本空间 \Omega 上的概率测度。和 Gaussian process 相似的一点是:GP 是给定有限个点 x_i,对应的 y \sim \mathrm{GP} (m, K) 是服从某个正态分布的 y(X) \sim N (\cdot \mid m(X), K(X, X));若 \theta \sim \mathrm{DP}(\alpha, G_0) 是对任意一个 \Omega 的有限划分 \cup A_i,则 \big(\theta (A_i) \big) 是服从参数为 (\alpha G_0 (A_i)) 的 Dirichlet 分布。换言之随机变量 \theta 建立了一个有限划分到 Dirichlet 分布的映射。

从 DP 中采样获得的是离散的值,即使 G_0 本身是连续分布。这意味着

\displaystyle\theta \sim \mathrm{DP} (\alpha, G_0) \quad \Rightarrow \quad \theta = \sum_{i = 1}^\infty \pi_i \delta (\theta - \theta_j)

其中 \theta_j \in \Omega, \sum_{i = 1}^\infty \pi_i = 1, \pi_i \geq 0

与 Dirichlet process 相关的还有下面两个过程,它们提供了另外一种理解这个过程的方式,也为对应的 inference 算法提供了思路。

Stick breaking process 所谓的 SBP 类似于折断一根长度为 1 的棍子,每折断一次都会选择从 G_0 中抽取一个新的 \theta_i。生成的过程如下,从一个 \mathrm{Beta} (1, \alpha) 分布中抽取 \beta_i, i = 1, \ldots, \infty,折断的比例为 \pi_i = \beta_i \prod_{j = 1}^{i-1} (1 - \beta_j),这样获得的

\displaystyle \theta = \sum_{i = 1}^\infty \pi_i \theta_i

称 为 SBP。不难想象有限样本情况下由于 \theta_i\Omega 上的随机变量服从 G_0 分布,这样对 G_0 (A_j) 的计算就可以通过落入这个划分的 \theta_i 的个数判断。最后可以证明 \theta (A_i) 的确是 Dirichlet 分布。

SBP: 是 K\to infty 情况下的极限

Chinese restaurant process 所谓的 CRP 是指这样一个过程一个中国餐馆,顾客依次进入,桌子上人多的新顾客过来的可能性就更大,这样生成的过程是使用条件概率的形式:如选择了 \theta_1, \ldots, \theta_{i - 1} \in \{ \theta_j^\star\},此时 \theta_i = \theta_j^\star 的条件概率为 \frac{\#(\theta_j = \theta_j^\star)}{i - 1 + \alpha},而剩下的 \frac{\alpha}{i - 1 + \alpha} 的概率是从 G_0 中抽取新的 \theta_j^\star。CRP 可以看成是 SBP 对 \beta_j 进行 marginalization,这是 z_i 就耦合在一起,只有条件概率是 tractable 的,

CRP 的生成过程是将这个 graph 展开的过程。

利用 CRP 这种条件概率以及 exchangability 容易获得 Gibbs sampler;利用 SBP 的 truncated 逼近我们可以获得 variational approximation。而我们一般拿来说的 DP 是将 z_i 进一步 marginalize out 之后获得的。

DP

inference

对 DP 的 inference 主要有两种,一种是 MCMC 策略(见 Radford Neal 大牛的 paper),一种是 variational 策略(见 Blei 和 Jordan 的文章)。

在有限样本情况下,给定如果希望对 DP 的后验进行采样,这会包含两个方面,

  • 我 们需要为多项分布隐变量抽样,这往往是根据 model 和 CRP 对应的概率计算后验:根据 exchangability,每个隐变量都能当做最后一个,这样对应的 CRP 的概率就是根据每个 \theta_j^\star 管理的样本个数和 \alpha 决定的抽样
  • 我们需要更新 \theta_j^\star,这往往是在确定所管理的样本之后计算此时的后验分布(如果 G_0 选择为 model 的 conjugate prior,这步就很 trivial),在这个后验分布下采样

这个策略简单,容易实现。但是 Gibbs sampler 往往收敛较慢。这也就是导致 variational approximate inference 的重要理由。我们知道对一个后验分布进行 variational approximation 需要引入一个近似分布 q,这里需要注意的是如果近似分布我们还是取某个 DP 则很难求解,为此一般能计算的是选用 truncated SBP,换言之,我们需要设定一个“段数”,从某个意义上来说这似乎把选择 cluster 个数问题转换成为了近似精度。在 SBP 里面我们有随机变量 \beta_i \sim \mathrm{Beta} (1, \alpha),有多项分布 z_i 以及对应的参数 \theta_i \sim G_0。这样在 truncated SBP 里面我们假定截断为 T 份,这需要 T - 1 个 Beta 分布的 q_{\lambda_{1, i}, \lambda_{2, i}} (b_i),需要 T 个多项分布 \xi_i(可选择有 T 个 value,假定对应为 \mu_{i, s})和 T\zeta_i \sim G(这里不见得是 G_0,因为对应的参数,即 variational 参数 \eta_i 是待优化的)。

因为 SBP 是一个 generative 过程,我们相当于有了 DP 的显式的 prior 表示形式,乘以 z_i, x_i 相关的 model 部分,我们就得到了联合分布的 close-form 表示,我们记其为 \Pr(x_i, z_i, \theta_j, \beta_j \mid i = 1, \ldots, N, j = 1, \ldots) \propto p,其中 p 是未知的后验分布,在 variational Bayesian 里面我们需要

\displaystyle \min_{\lambda_{1,i}, \lambda_{2, i}, \mu_{i, s}, \eta_i} \mathrm{KL} (q \| p)

这个优化我们使用类似 coordinate descent 的策略,每次取一个 q \in \{q(b_i), q(xi_i), q(\zeta_i)\} 出来做优化。此时 p 是不知道但是我们可以直接将联合分布代入并不改变优化的本质,这样我们等价于在具有 decomposition 结构下进行求解,但是注意到 p 里面含有无穷项,而 q 只有有限项,这样最后就会出现截断的解(具体结果看 paper 吧)。

例子:mixture model

我 们这里拿混合分布模型作为例子,我们有一个 model 是 \Pr (x \mid \theta),其有限混合模型就是假定观测到的数据是由几个可能的 \theta_j 分别产生,为此我们往往引入了隐变量 z,它用来选择对应的模型参数 \theta_j,为此这是一个 multinomial distribution,我们设参数对应为 \Pr (z = j) = \pi_j。这样一来得到了 frequentist’s mixture。对 Bayesian 来说会为 \pi 引入额外的分布,一般是 multinomial distribution 的 conjugate prior,即 Dirichlet distribution,不妨设为 \pi \sim \mathrm{Dirichlet} (\alpha),类似为模型的参数 \theta 也可以假定一个先验,这一般会去模型自己的 conjugate prior(也有例外)。新的模型在独立同分布假设下的联合分布形式为

\displaystyle\Pr (x_i, z_i, \theta, \pi \mid \alpha, \beta) = \prod_{i = 1}^N \prod_{j = 1}^k \big( \pi_j\Pr (x_i \mid \theta_j) \big)^{\delta (z, j)} \Pr(\pi \mid \alpha) \Pr (\theta_j \mid \beta)

其中 \beta\Pr (\theta \mid \beta) 的超参数。这样一来如果我们希望 k\to \infty,就等价于引入了一个 DP,其参数 \alpha 反应产生新 z 可选值的强度,而 G_0 = \Pr (\theta \mid \beta)。由于每次从 DP 的抽样获得的 \theta_i 来自于 G_0,这样一来就有如下的后验 \theta_j^\star \propto G_0 \prod_{z_i = j} \Pr(x_i \mid \theta_j^\star)

如果将 variational 与之比较我们会发现两者有非常的相似之处:

  • sampling 计算后验采样更新
  • variational 使用类似 mean field approximation 的策略更新近似 factor 的参数

HDP

与 mixture model 相比,更加复杂的就是所谓的 aspect model:我们知道 mixture model 所有的隐变量 z_i 均来自一个给定的 multinomial distribution,参数为 \pi。很多情况下,我们的确存在 x \in \mathcal{X} 空间的结构,但实际观察到的样本 \textbf{x} 是由 \mathcal{X} 一组样本合成的,这意味着 \mathcal{X} 上的结构应用到样本 \textbf{x} 此时却存在问题:很可能是多个子结构(aspect)产生的观测,为此我们必须为对应的 \textbf{z} 建立跟样本 \textbf{x} 对应的一个抽取 aspect 的比例:这里的 \pi_i 对应于每个样本 \textbf{x}_i,组成 \textbf{x}_i\{ x_{i, s}\} 对应于 \textbf{z}_i = \{ z_{i, s}\}

这 个双层结构的 modeling 我们知道 pLSA 算是 frequentist 的版本,但是其 per doc 的多项分布使用了一个莫名其妙的 \Pr(z \mid d),导致这个 generative model 有点解释不清。而 LDA 客服了这个问题,并为 \pi_i 设定了一个分布,即 \mathrm{Dirichlet}(\alpha)。这个形式仍然来自于共轭的需要。另外从 de Finitte 定理看来,由于每个文档自身表示为 bag of words 每个 word 存在 exchangability 这导致是一个 mixture(我们引入了 z_{i, s} 这个多项分布),而每个文档又满足 exchangability 这导致另一个 mixture(我们引入了 Dirichlet distribution)。因此 LDA 获得了一个 mixture of mixture 的双层结构。

HDP 算是对 LDA 这类型模型的非参化。事实上,简单的说我们首先从一个 \mathrm{DP} (\gamma, H) 中抽取 G_0,这样我们的 G_0 不再是预先给定的,然后我们从 \mathrm{DP} (\alpha_0, G_0) 中再抽取 \theta_i。实际上对 HDP 的表述也有类似 SBP 和 CRP 的扩展。

HDPSBP(我自己生造的名字)类似 SBP 我们有折断过程,用一个 \mathrm{Beta}(1, \gamma) 产生 \beta_i,但这里并不是让 \beta_i 确定性生成 $\latex \pi_i$,而是从 \mathrm{DP}(\alpha_0, \beta) 中产生 \pi_j(这个过程大致是将 \beta 转换成为每段长度后,以此为某个 Beta 分布的参数继续生成新的截断概率,而 \pi_j 就是这些截断概率变成每段长度后的结果,类似将一根棍子分割后,每段继续无穷细分),这样 H 中抽出来的其实是 \theta_j^\star

Chinese Restaurant Franchse(CRF)这本意是说 share 菜的几个中国餐馆,这时的选择其实是选定某个菜(参数)后,如果在某个餐馆 j 里面这个时候情形类似 CRP,但此时 G_0 需要向上一层对 \mathrm{DP} (\gamma, H) 的后验采样决定是否上新菜(新的参数)还是换馆子。

根据这两个东西,我们其实也可以获得两种类型的后验估计(一篇是 Yee Whye Teh、Jordan、Beal 和 Blei 写的,另一篇是 Yee Whye Teh、Kenichi Kruihara 和 Max Welling 写的),其实对 MCMC 策略来说无非就是将 Gibbs sampler 上多套一次回退过程,原来直接问 G_0 要新参数而现在要额外的多问上面一层的 GP 是不是先换馆子。这里暂不赘述细节。

==================

谨以此文纪念一下第 1k 篇 wp 的 blog。

——————
And Abraham stood up, and bowed himself to the people of the land, even to the children of Heth.

Advertisements
Dirichlet process 应用

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s