潜在狄利克雷分配

  • 潜在狄利克雷分配（latent狄利克雷allocation, LDA）于2002年由Blei等提出。它和概率潜在语义分析都属于概率主题建模方法，二者之间的差异恰好反映了频率学派与贝叶斯学派对参数估计上的不同理解：

    • PLSA将模型参数看作是固定的未知常数，使用类似点估计的方法进行参数估计；
    • LDA则将模型参数看作是服从特定分布的随机变量，引入了狄利克雷先验分布，并通过观察到的数据来修正这个先验，得到后验分布。

    研究表明，虽然LDA更加复杂，但其模型性能比PLSA更好，泛化能力也更强。

狄利克雷分布

简要回顾一些概率论与数理统计的知识：

  1. 多项分布
    重复进行nn次独立随机试验，每次试验可能出现的结果有kk种，第ii种结果出现的概率为θi\theta_i，出现的次数为nin_i。
    • 如果用随机变量x=(x1,x2,⋯ ,xk)⊤\mathbf{x}=(x_1,x_2,\cdots,x_k)^\top表示试验所有可能结果的次数（其中xix_i表示第ii种结果出现的次数），那么随机变量x\mathbf{x}服从多项分布，对应概率密度函数为 P(x1=n1,x2=n2,⋯ ,xk=nk)=n!n1!n2!⋯nk!θ1n1θ2n2⋯θknk=n!∏i=1kni!∏i=1kpini\begin{aligned} P(x_1 = n_1, x_2 = n_2, \cdots, x_k = n_k) &= \frac{n!}{n_1!n_2!\cdots n_k!} \theta_1^{n_1} \theta_2^{n_2} \cdots \theta_k^{n_k} \\ &= \frac{n!}{\displaystyle\prod_{i=1}^k n_i!} \prod_{i=1}^k p_i^{n_i} \end{aligned} 也记作x∼Mult(n,θ)\mathbf{x}\sim\text{Mult}(n,\boldsymbol{\theta})，其中θ=(θ1,⋯ ,θk)⊤,n=∑i=1kni\displaystyle\boldsymbol{\theta}=(\theta_1,\cdots,\theta_k)^\top,n=\sum_{i=1}^k n_i。
    • 特别地，当n=1n=1时，多项分布退化为类别分布，表示表示试验可能出现的kk种结果的概率。
  2. 狄利克雷分布
    在贝叶斯学习中，狄利克雷分布常作为多项分布的先验分布使用。其定义如下：
    • 若多元连续随机变量θ=(θ1,θ2,⋯ ,θk)⊤\boldsymbol{\theta}= (\theta_1, \theta_2, \cdots, \theta_k)^\top的概率密度函数为 p(θ∣α)=Γ(∑i=1kαi)∏i=1kΓ(αi)∏i=1kθiαi−1p(\boldsymbol{\theta}| \alpha) = \frac{\displaystyle\Gamma \left( \sum_{i=1}^k \alpha_i \right)}{\displaystyle\prod_{i=1}^k \Gamma(\alpha_i)} \prod_{i=1}^k \theta_i^{\alpha_i - 1} 其中 ∑i=1kθi=1,θi≥0,α=(α1,α2,⋯ ,αk)⊤,αi>0,i=1,2,⋯ ,k\sum_{i=1}^k \theta_i = 1, \theta_i \geq 0, \boldsymbol{\alpha} = (\alpha_1, \alpha_2, \cdots, \alpha_k)^\top, \alpha_i > 0, i = 1, 2, \cdots, k Γ(⋅)\Gamma(\cdot)表示Gamma函数，则称随机变量θ\boldsymbol{\theta}服从参数为α\boldsymbol{\alpha}的狄利克雷分布，记作θ∼Dir(α)\boldsymbol{\theta}\sim \text{Dir}(\boldsymbol{\alpha})。
    • 上述概率密度函数表达式也可用多元Beta函数表示：记B(α)=∏i=1kΓ(αi)Γ(∑i=1kαi)\Beta(\boldsymbol{\alpha})=\frac{\displaystyle\prod_{i=1}^k\Gamma(\alpha_i) }{\displaystyle \Gamma \left( \sum_{i=1}^k \alpha_i\right)}，则有 p(θ∣α)=1B(α)∏i=1kθiαi−1p(\boldsymbol{\theta}|\boldsymbol{\alpha}) = \frac{1}{\Beta(\boldsymbol{\alpha})} \prod_{i=1}^k \theta_i^{\alpha_i - 1} 特别地，当k=2k=2时，就得到Beta分布。
  • 狄利克雷分布有一些重要性质：
    • 狄利克雷分布属于指数分布族；
    • 狄利克雷分布是多项分布的共轭先验分布。【共轭先验分布概念可参见数理统计 Cheat Sheet】
      • 具体而言，当总体分布D∼Mult(n,θ)D\sim\text{Mult}(n,\boldsymbol{\theta})，θ\boldsymbol{\theta}先验分布为Dir(α)\text{Dir}(\alpha)，那么其后验分布为Dir(α+n)\text{Dir}(\alpha+n)。因此α\boldsymbol{\alpha}也被称作先验伪计数（prior pseudo-counts）。

LDA模型

  • LDA是文本集合的生成概率模型。模型假设话题由单词的多项分布表示，文本由话题的多项分布表示，单词分布和话题分布的先验分布都是狄利克雷分布。

    • 严格意义上说，这里的多项分布都是类别分布，不过在机器学习与自然语言处理中，有时对两者不作严格区分。

  • LDA的文本集合的生成过程示意图如下：LDA
    利用LDA进行话题分析就是对给定文本集合，学习到每个文本的话题分布，以及每个话题的单词分布。

  • 下面给出模型的符号定义：

    • 单词、文本、话题集合符号沿用上一讲；
    • 设所有文本的长度均为ll，且每个文本did_i都有对应可观测的单词序列Wi=wi1,⋯ ,wilW_i=w_{i1},\cdots,w_{il}与不可观测的话题序列Zi=zi1,⋯ ,zilZ_i=z_{i1},\cdots,z_{il}；
    • 每个话题ziz_i可由单词的条件概率分布P(w∣zi),w∈WP(w|z_i),w\in\mathcal{W}表示，其服从多项（类别）分布，参数用φi=(φi1,⋯ ,φim)\boldsymbol{\varphi}_i=(\varphi_{i1},\cdots,\varphi_{im})表示，因而整个话题的参数可用矩阵φ=(φ1,⋯ ,φk)\boldsymbol{\varphi}=(\boldsymbol{\varphi}_1,\cdots,\boldsymbol{\varphi}_k)表示。【φi∼Dir(β),β=(β1,⋯ ,βm)⊤\boldsymbol{\varphi}_i\sim\text{Dir}(\boldsymbol{\beta}),\boldsymbol{\beta}=(\beta_1,\cdots,\beta_m)^\top】
    • 每个文本djd_j可由话题的条件概率分布P(z∣dj),z∈ZP(z|d_j),z\in\mathcal{Z}表示，同样服从多项（类别）分布，参数用θi=(θi1,⋯ ,θik)\boldsymbol{\theta}_i=(\theta_{i1},\cdots,\theta_{ik})表示，因而整个文本的参数可用矩阵θ=(θ1,⋯ ,θn)\boldsymbol{\theta}=(\boldsymbol{\theta}_1,\cdots,\boldsymbol{\theta}_n)表示。【θi∼Dir(α),α=(α1,⋯ ,αm)⊤\boldsymbol{\theta}_i\sim\text{Dir}(\boldsymbol{\alpha}),\boldsymbol{\alpha}=(\alpha_1,\cdots,\alpha_m)^\top】

  • 由此可得LDA文本生成算法如下：

    1. 对于话题ziz_i（i=1,2,⋯ ,ki = 1, 2, \cdots, k）：生成多项分布参数φi∼Dir(β)\boldsymbol{\varphi}_i \sim \text{Dir}(\boldsymbol{\beta})作为话题的单词分布p(w∣zk)p(w|z_k)。
    2. 对于文本did_i（i=1,2,⋯ ,ni = 1, 2, \cdots, n）：生成多项分布参数θi∼Dir(α)\boldsymbol{\theta}_i \sim \text{Dir}(\boldsymbol{\alpha})作为文本的话题分布p(z∣dn)p(z|d_n)。
    3. 对于文本did_i的单词wijw_{ij}（i=1,2,⋯ ,n, j=1,2,⋯ ,li = 1, 2, \cdots, n,\, j = 1, 2, \cdots, l）：生成话题zij∼Mult(θi)z_{ij} \sim \text{Mult}(\boldsymbol{\theta}_i)作为单词对应的话题，生成单词wij∼Mult(φzij)w_{ij} \sim \text{Mult}(\boldsymbol{\varphi}_{z_{ij}})作为该话题下的单词。

    最终得到文本序列Wi=wi1,wi2,⋯ ,wilW_i=w_{i1},w_{i2},\cdots,w_{il}。

    • 上述参数中，话题数kk一般通过实验确定。狄利克雷分布的超参数α\boldsymbol{\alpha}和β\boldsymbol{\beta}通常也是事先给定的。在没有其他先验知识的情况下，可以假设向量α\boldsymbol{\alpha}和β\boldsymbol{\beta}的所有分量均为11，此时文本与话题的先验分布均为均匀分布。

  • LDA模型的概率图形式如下：LDA-graph

  • LDA假设文本由无限可交换的话题序列组成，即话题序列的任意一个有限子序列的联合概率对随机变量的排列不变。由De Finetti定理知，实际是假设文本中的话题对随机参数（即上面的φ\boldsymbol{\varphi}）是条件独立同分布的。

    • 实际上，我们也可以证明在给定φ\boldsymbol{\varphi}的φ\boldsymbol{\varphi}时，文本序列的各个元素都是相互条件独立的。

  • LDA模型的概率计算公式如下：

    p(W,Z,θ,φ∣α,β)=∏t=1kp(φt∣β)∏i=1np(θi∣α)∏j=1lp(zij∣θi)p(wij∣φzij)p(W,Z, \boldsymbol{\theta}, \boldsymbol{\varphi}|\boldsymbol{\alpha}, \boldsymbol{\beta}) = \prod_{t=1}^{k} p(\boldsymbol{\varphi}_t|\boldsymbol{\beta}) \prod_{i=1}^{n} p(\boldsymbol{\theta}_i|\boldsymbol{\alpha}) \prod_{j=1}^{l} p(z_{ij}|\boldsymbol{\theta}_i) p(w_{ij}|\boldsymbol{\varphi}_{z_{ij}})

    其中WW为所有文本序列集合，ZZ为所有话题序列集合。如果具体到第ii个文本，则概率为

    p(Wi,Zi,θi,φ∣α,β)=∏t=1kp(φt∣β)p(θi∣α)∏j=1lp(zij∣θi)p(wij∣φzij)p(W_i,Z_i, \boldsymbol{\theta}_i, \boldsymbol{\varphi}|\boldsymbol{\alpha}, \boldsymbol{\beta}) = \prod_{t=1}^{k} p(\boldsymbol{\varphi}_t|\boldsymbol{\beta})p(\boldsymbol{\theta}_i|\boldsymbol{\alpha}) \prod_{j=1}^{l} p(z_{ij}|\boldsymbol{\theta}_i) p(w_{ij}|\boldsymbol{\varphi}_{z_{ij}})

    然后考虑给定文本与话题参数后文本WiW_i的生成概率：

    p(Wi∣θi,φ)=∏j=1l[∑t=1kp(zij=t∣θi) p(wij∣φt)]p(W_i | \boldsymbol{\theta}_i, \boldsymbol{\varphi}) = \prod_{j=1}^{l} \left[ \sum_{t=1}^{k} p(z_{ij} = t | \boldsymbol{\theta}_i) \, p(w_{ij} | \boldsymbol{\varphi}_t) \right]

    将参数替换为超参数α,β\boldsymbol{\alpha}, \boldsymbol{\beta}，得到

    p(Wi∣α,β)=∏t=1k∫p(φt∣β){∫p(θi∣α) p(Wi∣θi,φ) dθi}dφtp(W_i | \boldsymbol{\alpha}, \boldsymbol{\beta}) = \prod_{t=1}^{k} \int p(\boldsymbol{\varphi}_t | \boldsymbol{\beta}) \left\{ \int p(\boldsymbol{\theta}_i | \boldsymbol{\alpha}) \, p(W_i | \boldsymbol{\theta}_i, \boldsymbol{\varphi}) \, \mathrm{d}\boldsymbol{\theta}_i \right\} \mathrm{d}\boldsymbol{\varphi}_t

    最终得到超参数给定条件下所有文本的生成概率：

    p(W∣α,β)=∏t=1k∫p(φt∣β){∏i=1n[∫p(θi∣α) p(Wi∣θi,φ) dθi]}dφtp(W | \boldsymbol{\alpha}, \boldsymbol{\beta}) = \prod_{t=1}^{k}\int p(\boldsymbol{\varphi}_t | \boldsymbol{\beta}) \left\{ \prod_{i=1}^{n} \left[ \int p(\boldsymbol{\theta}_i | \boldsymbol{\alpha}) \, p(W_i | \boldsymbol{\theta}_i, \boldsymbol{\varphi}) \, \mathrm{d}\boldsymbol{\theta}_i \right] \right\} \mathrm{d}\boldsymbol{\varphi}_t

    其中∏t=1k∫[… ]dφt\displaystyle \prod_{t=1}^{k} \int[\dots]\mathrm{d}\boldsymbol{\varphi}_t表示kk重嵌套积分。

学习算法

  • LDA的学习（参数估计）是一个复杂的最优化问题，很难精确求解，只能近似求解。常用的近似求解方法有吉布斯抽样和变分EM算法。

下面只给出算法的形式，具体阐述请参见下一讲。

吉布斯抽样算法

  • 输入：文本的单词序列W=W1,⋯ ,Wi,⋯ ,WnW = W_1, \cdots, W_i, \cdots, W_n，其中Wi=wi1,wi2,⋯ ,wilW_i = w_{i1}, w_{i2}, \cdots, w_{il}。
  • 输出：文本的话题序列Z=Z1,⋯ ,Zi,⋯ ,ZnZ = Z_1, \cdots, Z_i, \cdots, Z_n，其中Zi=zi1,zi2,⋯ ,zilZ_i = z_{i1}, z_{i2}, \cdots, z_{il}的后验概率分布p(Z∣W,α,β)p(Z|W, \boldsymbol{\alpha}, \boldsymbol{\beta})的样本计数、模型的参数φ\boldsymbol{\varphi}和θ\boldsymbol{\theta}的估计值。
  • 参数：超参数α\boldsymbol{\alpha}和β\boldsymbol{\beta}，话题个数kk。
  1. 设所有计数矩阵的元素nitn_{it}、ntmn_{tm}，计数向量的元素nin_i、ntn_t初值为00。
  2. 对所有文本did_i（i=1,2,⋯ ,ni = 1, 2, \cdots, n），对第ii个文本中的所有单词wijw_{ij}（j=1,2,⋯ ,lj = 1, 2, \cdots, l），抽样话题zij=zt∼Mult(1/k)z_{ij} = z_t \sim \text{Mult}(1/k)；增加话题-单词计数ntm=ntm+1n_{tm} = n_{tm} + 1，增加话题-单词和计数nt=nt+1n_t = n_t + 1，增加文本-话题计数nit=nit+1n_{it} = n_{it} + 1，增加文本-话题和计数ni=ni+1n_i = n_i + 1。
  3. 循环执行以下操作，直到进入燃烧期：对所有文本did_i（i=1,2,⋯ ,ni = 1, 2, \cdots, n），对第ii个文本中的所有单词wijw_{ij}（j=1,2,⋯ ,lj = 1, 2, \cdots, l）：
    • 当前的单词wijw_{ij}是词汇表中第mm个单词，话题指派zijz_{ij}是第tt个话题；减少计数ntm=ntm−1n_{tm} = n_{tm} - 1，nt=nt−1n_t = n_t - 1，nit=nit−1n_{it} = n_{it} - 1，ni=ni−1n_i = n_i - 1；
    • 按照满条件分布进行抽样： p(zij=t∣Z−(ij),W,α,β)∝ntm+βm∑m=1M(ntm+βm)⋅nit+αt∑t′=1k(nit′+αt′)p(z_{ij} = t | Z_{-(ij)}, W, \boldsymbol{\alpha}, \boldsymbol{\beta}) \propto \frac{n_{tm} + \beta_m}{\sum_{m=1}^M (n_{tm} + \beta_m)} \cdot \frac{n_{it} + \alpha_t}{\sum_{t'=1}^k (n_{it'} + \alpha_{t'})} 得到新的第t′t'个话题，分配给zijz_{ij}；
    • 增加计数nt′m=nt′m+1n_{t'm} = n_{t'm} + 1，nt′=nt′+1n_{t'} = n_{t'} + 1，nit′=nit′+1n_{it'} = n_{it'} + 1，ni=ni+1n_i = n_i + 1；
    • 得到更新的两个计数矩阵Nk×M=[ntm]N_{k \times M} = [n_{tm}]和Nn×k=[nit]N_{n \times k} = [n_{it}]，表示后验概率分布p(Z∣W,α,β)p(Z|W, \boldsymbol{\alpha}, \boldsymbol{\beta})的样本计数。
  4. 利用得到的样本计数，计算模型参数： φtm=ntm+βm∑m=1M(ntm+βm)θit=nit+αt∑t′=1k(nit′+αt′)\begin{aligned} \varphi_{tm} &= \frac{n_{tm} + \beta_m}{\displaystyle\sum_{m=1}^M (n_{tm} + \beta_m)}\\ \theta_{it} &= \frac{n_{it} + \alpha_t}{\displaystyle\sum_{t'=1}^k (n_{it'} + \alpha_{t'})} \end{aligned}

变分EM算法

  • 输入：给定所有文本D=(d1,d2,⋯ ,di,⋯ ,dn)D = (d_1, d_2, \cdots, d_i, \cdots, d_n)，主题数kk，词汇表大小mm。
  • 输出：变分参数(γ,η)(\boldsymbol{\gamma}, \boldsymbol{\eta})，以及完整模型参数：kk个主题的词分布矩阵φ={φ1,φ2,⋯ ,φr,⋯ ,φk}\boldsymbol{\varphi} = \{\varphi_1, \varphi_2, \cdots, \varphi_r, \cdots, \varphi_k\}，狄利克雷超参数α\boldsymbol{\alpha}。
    1. E 步（变分参数估计）
      固定全局模型参数α,φ\boldsymbol{\alpha}, \boldsymbol{\varphi}，通过最大化证据下界（ELBO），估计变分参数γ,η\boldsymbol{\gamma}, \boldsymbol{\eta}。
      • 初始化：对所有文档ii和主题rr，令变分狄利克雷参数γir(0)=αr+l/k\gamma_{ir}^{(0)} = \alpha_r + l/k；对所有位置jj和主题rr，令变分多项分布参数ηijr(0)=1/k\eta_{ijr}^{(0)} = 1/k。
      • 重复（直到变分参数收敛）：
      1. 对所有文本位置j=1→lj = 1 \to l，对所有主题r=1→kr = 1 \to k： ηijr(t+1)=φr,wij⋅exp⁡[Ψ(γir(t))−Ψ(∑r′=1kγir′(t))]\eta_{ijr}^{(t+1)} = \varphi_{r, w_{ij}} \cdot \exp \left[ \Psi\left(\gamma_{ir}^{(t)}\right) - \Psi\left(\sum_{r'=1}^k \gamma_{ir'}^{(t)}\right) \right] 其中φr,wij\varphi_{r, w_{ij}}是主题rr下单词wijw_{ij}的概率，Ψ(⋅)\Psi(\cdot)为双伽马函数。（Gamma函数导数）
      2. 对每个ηijr(t+1)\eta_{ijr}^{(t+1)}进行归一化，使得∑r=1kηijr(t+1)=1\displaystyle\sum_{r=1}^k \eta_{ijr}^{(t+1)} = 1。
      3. 更新文档-主题变分参数： γir(t+1)=αr+∑j=1lηijr(t+1)\gamma_{ir}^{(t+1)} = \alpha_r + \sum_{j=1}^{l} \eta_{ijr}^{(t+1)}
    2. M 步（模型参数估计）
      固定当前的变分参数γ,η\boldsymbol{\gamma}, \boldsymbol{\eta}，通过最大化证据下界，估计全局模型参数α,φ\boldsymbol{\alpha}, \boldsymbol{\varphi}。
      • 更新词分布矩阵φ\boldsymbol{\varphi}：
        • 首先计算kk个主题的词分布。对于每个主题r∈{1,…,k}r \in \{1, \dots, k\}和词汇表中的每个单词v∈{1,…,m}v \in \{1, \dots, m\}： φrv∝∑i=1n∑j=1lηijr⋅1(wij=v)\varphi_{rv} \propto \sum_{i=1}^{n} \sum_{j=1}^{l} \eta_{ijr} \cdot \mathbf{1}(w_{ij} = v)
        • 然后对每个主题rr的所有词汇vv进行归一化： φrv=βv+∑i=1n∑j=1lηijr1(wij=v)∑v′=1m(βv′+∑i=1n∑j=1lηijr1(wij=v′))\varphi_{rv} = \frac{\displaystyle\beta_v + \sum_{i=1}^{n} \sum_{j=1}^{l} \eta_{ijr} \mathbf{1}(w_{ij}=v)}{\displaystyle\sum_{v'=1}^{m} \left(\beta_{v'} + \sum_{i=1}^{n} \sum_{j=1}^{l} \eta_{ijr} \mathbf{1}(w_{ij}=v')\right)}
      • 更新超参数α\boldsymbol{\alpha}：
        • α\boldsymbol{\alpha}没有解析解，可以通过牛顿法迭代求解，具体更新步骤如下：
          1. 计算梯度向量：对每个主题rr求导： ∇L(αr)=n[Ψ(∑r′=1kαr′)−Ψ(αr)]+∑i=1n[Ψ(γir)−Ψ(∑r′=1kγir′)]\nabla L(\alpha_r) = n \left[ \Psi\left(\sum_{r'=1}^k \alpha_{r'}\right) - \Psi(\alpha_r) \right] + \sum_{i=1}^{n} \left[ \Psi(\gamma_{ir}) - \Psi\left(\sum_{r'=1}^k \gamma_{ir'}\right) \right]
          2. 计算黑塞矩阵（Hessian）元素： ∇2L(αrαr′)=n[Ψ′(∑r′=1kαr′)−1(r=r′)Ψ′(αr)]\nabla^2 L(\alpha_r \alpha_{r'}) = n \left[ \Psi'\left(\sum_{r'=1}^k \alpha_{r'}\right) - \mathbf{1}(r=r')\Psi'(\alpha_r) \right]
          3. 执行牛顿更新迭代： αnew=αold−[∇2L(αold)]−1∇L(αold)\boldsymbol{\alpha}_{\text{new}} = \boldsymbol{\alpha}_{\text{old}} - [\nabla^2 L(\boldsymbol{\alpha}_{\text{old}})]^{-1} \nabla L(\boldsymbol{\alpha}_{\text{old}})