Dirichlet Process

Posted on In Waline:

关于狄利克雷过程的思想整理。主要结合了知乎上的相关博客。

Dirichlet Process

1. 介绍

Dirichlet 分布（Dirichelt Distribution）和 Dirichlet 过程 （Dirichlet Process）广泛应用于信息检索、自然语言处理等领域，是理解主题模型的重要一步。作为一种非参数模型（non-paramatric model），和参数模型一样有着广泛的应用。

2. Dirichlet 分布

2.1. 简介

Dirichlet 分布（DP）是一种概率分布的分布，由参数 α,G0\alpha, G_0 确定，即 G∼DP(α,G0)G \sim DP(\alpha, G_0)，α\alpha 是分布参数，值越大分布越近似于均匀分布，G0G_0 是基分布。可以简单理解为给定分布 G0G_0，通过 α\alpha 的控制得到输出分布 GG。

2.2. Dirichlet 的应用场景

有一组来源于混合高斯分布的数据集，希望对其进行聚类，然而并不知道这组数据是由几组高斯分布生成。即：

  • 聚类数量未知；
  • 非参数化；
  • 聚类数量服从概率分布。

2.3. Dirichlet 分布的数学形式

假设有 mm 个数据 x1,...,xmx_1, ..., x_m，每个数据由不同的分布 g1,...,gmg_1, ..., g_m 产生，每个分布对应不同的参数 θ1,...,θm\theta_1, ..., \theta_m。如 gig_i 是高斯分布，则 θi={μi,σi}\theta_i = \lbrace \mu_i, \sigma_i \rbrace。对 θi\theta_i 建模，假设 θi\theta_i 服从分布 H(θ)H(\theta)，当 H(θ)H(\theta) 是连续分布时 P(θi=θj)=0,i≠jP(\theta_i = \theta_j)=0, i\ne j，即之前所假设的数据来自不同分布。而为解决聚类问题，则构造一个离散分布 GG 使得 θi∼G\theta_i \sim G 且 GG 和 H(θ)H(\theta) 非常相似。GG 就服从 Dirichlet 过程，即 G∼DP(α,H)G \sim DP(\alpha, H)。

2.4. 离散分布 GG 的采样（Dirichlet 过程）

一种采样过程被形象地称为 Stick Breaking（折棍子过程）。

首先，取 θ1∼G0\theta_1 \sim G_0，再有 β1∼Beta(1,α),π1=β1\beta_1 \sim Beta(1, \alpha), \pi_1 = \beta_1，即先采样第一个样本，然后把样本的权重设为 β1\beta_1。

再采样第二个样本：θ2∼G0,β2∼Beta(1,α),π2=(1−π1)×β2\theta_2 \sim G_0, \beta_2 \sim Beta(1, \alpha), \pi_2 = (1 - \pi_1) \times \beta_2。理解为由于第一个样本占用了棍子的 β1\beta_1，则棍子还剩 (1−π1)(1 - \pi_1)，因此再从棍子上折下 β2\beta_2。

之后，继续上述过程，由于棍子还剩下 (1−π1−π2)(1 - \pi_1 - \pi_2)，则采样 β3\beta_3，从剩下的棍子上折走 π3=(1−π1−π2)×β3\pi_3 = (1 - \pi_1 - \pi_2) \times \beta_3。

不断重复上述过程，最终得到离散分布 GG，θi\theta_i 是所在的位置，πi\pi_i 是对应的权重。这个过程也可以看出 α\alpha 对 GG 的离散程度影响。

由于对于 X∼Beta(a,b)X \sim Beta(a, b)，有 E(X)=aa+bE(X) = \frac{a}{a+b}，因此对上述过程：

  • 当 α=0\alpha=0 时，有 E(β1)=1E(\beta_1)=1，即第一个样本取走了所有的棍子，那么就使得这个离散分布的所有密度都落在了 θ1\theta_1 上。
  • 当 α=∞\alpha = \infty，则 E(βi)=0E(\beta_i)=0，使得分布趋向于均匀连续。

3. Dirichlet 过程的性质

  1. 期望值与基分布相同：EDP(α,G0)(X)=EG0(X)E_{DP(\alpha, G_0)}(X) = E_{G_0}(X)
  2. 随着 α→∞\alpha \rightarrow \infty，有 DP(α,G0)=G0DP(\alpha, G_0) = G_0
  3. 可以嵌套表示：G2∼DP(α,G1),G1∼DP(α,G0)G_2 \sim DP(\alpha, G_1), G_1 \sim DP(\alpha, G_0)
  4. 无法用电脑完全表示

4. Dirichlet 过程的直观理解 —— CRP

当参加大型聚餐时，往往人们会趋向于去人多的一桌，即“聚集效应”，而独自去新的一桌则由某种原因导致的概率 α\alpha 决定。

设 XiX_i 表示第 ii 张桌子上的人数，目前已经有 kk 张桌子上有客人。当第 nn 个客人到来时，其所去的桌子有两种情况：

table(n)={i,existing table,with p=Xin−1+αk+1,new table,with p=αn−1+α\text{table}(n) = \begin{cases} i, &\text{existing table}, &\text{with } p = \frac{X_i}{n - 1 + \alpha} \\ k+1, &\text{new table}, &\text{with } p = \frac{\alpha}{n - 1 + \alpha} \end{cases}

5. Dirichlet 过程的计算流程

  1. 将所有样本随机分配到初始聚类中；

  2. 对于每一个样本 ii，迭代进行：

    2.1. 根据离散采样算法，计算 ii 的所属类的概率；

    2.2. 根据计算得到的概率，分配 ii 所属的聚类。

参考