1、第二十章 潜在狄利克雷分配 潜在狄利克雷分配 潜在狄利克雷分配(latent Dirichlet allocation, LDA)，作为 基于贝叶斯学习的话题模型，是潜在语义分析、概率潜在语义分 析的扩展， LDA 在文本数据挖掘、图像处理、生物信息处理等领域被广泛使 用 潜在狄利克雷分配 LDA模型是文本集合的生成概率模型 假设每个文本由话题的一个多项分布表示，每个话题由单词的一 个多项分布表示 特别假设文本的话题分布的先验分布是狄利克雷分布，话题的单 词分布的先验分布也是狄利克雷分布 先验分布的导入使LDA 能够更好地应对话题模型学习中的过拟合 现象 潜在狄利克雷分配 LDA的文本集合的生
2、成过程如下： 首先随机生成一个文本的话题分布 之后在该文本的每个位置，依据该文本的话题分布随机生成一个 话题 然后在该位置依据该话题的单词分布随机生成一个单词，直至文 本的最后一个位置，生成整个文本。 重复以 上过程生成所有文本。 潜在狄利克雷分配 LDA模型是含有隐变量的概率图模型 模型中，每个话题的单词分布，每个文本的话题分布，文本的每 个位置的话题是隐变量 文本的每个位置的单词是观测变量 LDA模型的学习与推理无法直接求解，通常使用吉布斯抽样 （Gibbs sampling）和变分EM算法（variational EM algorithm)，前者是蒙特卡罗法，而后者是近似算法。 狄利克雷
3、分布 分布定义 1. 多项分布 多项分布（multinomial distribution)是一种多元离散随机变 量的概率分布，是二项分布（binomial distribution）的扩展。 假设重复进行n次独立随机试验，每次试验可能出现的结果有k种， 第i种结果出现的概率为pi，第i种结果出现的次数为ni 如果用随机变量 表示试验所有可能结果的次数， 其中Xi表示第i种结果出现的次数，那么随机变量x服从多项分布 分布定义 当试验的次数n为1时，多项分布变成类别分布（categorical distribution) 类别分布表示试验可能出现的k种结果的概率 分布定义 2. 狄利克雷分布 狄
4、利克雷分布（Dirichlet distribution)是一种多元连续随机 变量的概率分布，是贝塔分布（(beta distribution)的扩展 在贝叶斯学习中，狄利克雷分布常作为多项分布的先验分布使用 分布定义 分布定义 式中 是伽马函数，定义为 具有性质 当s是自然数时，有 分布定义 由于满足条件 所以狄利克雷分布 存在于（k1)维单纯形上 右图为二维单纯形上的狄利克雷分布 狄利克雷分布的参数为 分布定义 令 则狄利克雷分布的密度函数可以写成 是规范化因子，称为多元贝塔函数（或扩展的贝塔函 数） 分布定义 由密度函数的性质 得 即多元贝塔函数的积分表示 分布定义 3. 二项分布和贝塔
5、分布 二项分布是多项分布的特殊情况，贝塔分布是狄利克雷分布的特 殊情况 二项分布是指如下概率分布。X为离散随机变量，取值为m，其概 率质量函数为 其中n和p (0p1) 是参数 分布定义 贝塔分布是指如下概率分布，X为连续随机变量，取值范围为 0,1，其概率密度函数为 其中s0和t0是参数， 是贝塔函数，定义为 当然s, t是自然数时， 分布定义 当n为1时，二项分布变成伯努利分布（Bernoulli distribution ）或0-1分布 伯努利分布表示试验可能出现的2种结果的概率 下图给出几种概率分布的关系。 共扼先验 狄利克雷分布有一些重要性质： (1)狄利克雷分布属于指数分布族 (2
6、)狄利克雷 分布是多项分布的共扼先验（conjugate prior） 共扼先验 贝叶斯学习中常使用共扼分布 如果后验分布与先验分布属于同类，则先验分布与后验分布称为共扼 分布（conjugate distributions)，先验分布称为共扼先验 （conjugate prior) 如果多项分布的先验分布是狄利克雷分布，则其后验分布也为狄利克 雷分布，两者构成共扼分布 作为先验分布的狄利克雷分布的参数又称为超参数 使用共扼分布的好处是便于从先验分布计算后验分布 共扼先验 设 是由k个元素组成的集合。随机变量X服从W 上的多项分布， ，其中 和 是参数 参数n为从W中重复独立抽取样本的次数，n
7、i为样本中wi出现的次 数（i = 1,2,k） 参数 为 wi 出现的概率（i = 1,2,k） 共扼先验 将样本数据表示为D，目标是计算在样本数据D给定条件下参数 的后验概率 。 对于给定的样本数据D，似然函数是 假设随机变量 服从狄利克雷分布 ，其中 为参数。则 的先验分布为 共扼先验 根据贝叶斯规则，在给定样本数据D和参数条件下， 的后验 概率分布是 共扼先验 可以看出先验分布和后验分布都是狄利克雷分布 两者有不同的参数，所以狄利克雷分布是多项分布的共扼先验 狄利克雷后验分布的参数等于狄利克雷先验分布参数 加上多项分布的观测 ，好像试验之前就已经观 察到计数 ，因此也把叫做先验伪计数（
8、prior pseudo-counts)。 潜在狄利克雷分配模型 基本想法 潜在狄利克雷分配（LDA）是文本集合的生成概率模型 模型假设话题由单词的多项分布表示，文本由话题的多项分布表 示，单词分布和话题分布的先验分布都是狄利克雷分布 文本内容的不同是由于它们的话题分布不同 基本想法 LDA模型表示文本集合的自动生成过程： 首先，基于单词分布的先验分布（狄利克雷分布）生成多个单词 分布，即决定多个话题内容 之后，基于话题分布的先验分布（狄利克雷分布）生成多个话题 分布，即决定多个文本内容 然后，基于每一个话题分布生成话题序列，针对每一个话题，基 于话题的单词分布生成单词，整体构成一个单词序列，
9、即生成文 本 重复这个过程生成所有文本 基本想法 文本的单词序列是观测变量，文本的话题序列是隐变量，文本的 话题分布和话题的单词分布也是隐变量。 基本想法 LDA模型是概率图模型，其特点是以狄利克雷分布为多项分布的 先验分布 学习就是给定文本集合，通过后验概率分布的估计，推断模型的 所有参数 利用LDA进行 话题分析，就是对给定文本集合，学习到每个文本 的话题分布，以及每个话题的单词分布。 基本想法 可以认为LDA是PLSA（概率潜在语义分析）的扩展 相同点是两者都假设话题是单词的多项分布，文本是话题的多项分布 不同点是LDA使用狄利克雷分布作为先验分布，而PLSA不使用先验分布 （或者说假设
10、先验分布是均匀分布） 学习过程LDA基于贝叶斯学习，而PLSA基于极大似然估计 LDA的优点是，使用先验概率分布，可以防止学习过程中产生的过拟合 （over-fitting) 模型定义 1. 模型要素 潜在狄利克雷分配（LDA）使用三个集合： 单词集合 文本集合 ，其中 wm 是一个单词序列 话题集合 基本想法 每一个话题 zk 由一个单词的条件概率分布 p(w|zk) 决定 分布 p(w|zk) 服从多项分布（严格意义上类别分布），其参数为 参数 服从狄利克雷分布（先验分布），其超参数为 。 参数 是一个V维向量 ，其中 表示话题 zk 生成单词 wv 的概率 所有话题的参数向量构成一个 K
11、 x V 矩阵 。 超参数 也是一个V维向量 基本想法 每一个文本 wm 由一个话题的条件概率分布 p(z|wm) 决定 分布 p(z|wm) 服从多项分布（严格意义上类别分布），其参数为 参数 服从狄利克雷分布（先验分布），其超参数为 参数 是一个K维向量 ，其中 表示文本 wm 生成话题 zk 的概率 所有文本的参数向量构成一个 M x K 矩阵 超参数 也是一个K维向量 每一个文本 wm 中的每一个单词 wmn 由该文本的话题分布 p(z|wm) 以及所有话题的单词分布 p(w|zk) 决定 基本想法 2. 生成过程 LDA文本集合的生成过程如下： 给定单词集合W，文本集合D，话题集合Z
12、，狄利克雷分布的超参 数 和 基本想法 （1）生成话题的单词分布 随机生成K个话题的单词分布 按照狄利克雷分布Dir() 随机生成一个参数向量 ，作 为话题 zk 的单词分布 p(wlzk) （2）生成文本的话题分布 随机生成M个文本的话题分布 按照狄利克雷分布Dir() 随机生成一个参数向量 ， 作为文本 wm 的话题分布 p(z|wm) 基本想法 （3）生成文本的单词序列 随机生成M个文本的Nm个单词 首先按照多项分布 随机生成一个话题 zmn, zmn 然后按照多项分布 随机生成一个单词 wmn， wmn 文本 wm 本身是单词序列 ，对应着隐式的话 题序列 LDA的文本生成算法 LDA
13、的文本生成算法 LDA的文本生成过程中，假定话题个数K给定，实际通常通过实验 选定 狄利 克雷分布的超参数 和 通常也是事先给定的 在没有其他先验知识的情况下，可以假设向量 和 的所有 分量均为1，这时的文本的话题分布 是对称的，话题的单词 分布 也是对称的。 概率图模型 LDA模型本质是一种概率图模型(probabilistic graphical model) 下图为 LDA作为概率图模型的板块表示（plate notation) 图中结点表示随机变量 实心结点是观测变量 空心结点是隐变量 有向边表示概率依存关系 矩形（板块）表示重复，板块 内数字表示重复的次数。 概率图模型 图中LDA板
14、块表示，结点 和 是模型的超参数 结点 表示话题的单词分布的参数 结点 表示文本的话题分布的参数 结点 zmn 表示话题，结点 vmn 表示单词 结点 指向结点 ，重复K次，表示根据超参数 生成K个话题的单词分布的 参数 结点 指向结点 ，重复M次，表示根据超参数 生成M个文本的话题分布的 参数 结点 指向结点 zmn ，重复Nm次，表示根据文本的话题分布 生成 Nm 个话题 zmn 结点 zmn 指向结点wmn，同时K个结点 也指 向结点 wmn，表示根据话题 zmn 以 及K个话题的单词分布 生成单词 wmn 。 概率图模型 板块表示的优点是简洁，板块表示展开之后，成为普通的有向图 表示
15、有向图中结点表示随机变量，有向边表示概率依存关系。可以看 出LDA是相同随机 变量被重复多次使用的概率图模型。 随机变量序列的可交换性 一个有限的随机变量序列是可交换的（exchangeable)，是指随 机变量的联合概率 分布对随机变量的排列不变 这里 代表自然数1,2,. ,N的任意一个排列。一 个无限的随机变量序列是无限可交换（(infinitely exchangeable）的，是指它的任意一个有限子序列都是可交换的 如果一个随机变量序列 是独立同分布的，那么它 们是无限 可交换的。反之不然。 随机变量序列的可交换性 随机变量序列可交换的假设在贝叶斯学习中经常使用 根据De Finet
16、ti定理，任意一个无限可交换的随机变量序列对一 个随机参数是条件独立同分布的 即任意一个 无限可交换的随机变量序列 的基 于一个随机参数Y的条件概率， 等于基于这个随机参数Y的各个 随机变量 的条件概率的乘积。 随机变量序列的可交换性 LDA假设文本由无限可交换的话题序列组成 由De Finetti定理知，实际是假设文本中的话题对一个随机参数 是条件独立同分布的 所以在参数给定的条件下，文本中的话题的顺序可以忽略 作为对比，概率潜在语义模型假设文本中的话题是独立同分布的， 文本中的话题的顺序也可以忽略 概率公式 LDA模型整体是由观测变量和隐变量组成的联合概率分布，可以 表为 观测变量 w 表
17、示所有文本中的单词序列 隐变量 z 表示所有文本中的话题序列 隐变量 表示所有文本的话题分布的参数 隐变量 表示所有话题的单词分布的参数 和 是超参数 概率公式 表示超参数 给定条件下第k个话题的单词分布的参数 的生成概率 表示超参数 给定条件下第m个文本的话题分布的参 数 的生成概率， 表示第m个文本的话题分布 给定条件下文本的 第n个位置的话题 zmn 的生成概率 表示在第m个文本的第n个位置的话题 zmn 及所 有话题的单词分布的参数 给定条件下第m个文本的第n个位置 的单词 wmn 的生成概率 概率公式 第m个文本的联合概率分布可以表为 其中 wm 表示该文本中的单词序列，zm 表示该
18、文本的话题序列， 表示该文本的话 题分布参数。 LDA模型的联合分布含有隐变量，对隐变量进行积分得到边缘分 布 概率公式 参数 和 给定条件下第m个文本的生成概率是 超参数 和 给定条件下第m个文本的生成概率是 超参数 和 给定条件下所有文本的生成概率是 LDA的吉布斯抽样算法 LDA的吉布斯抽样算法 潜在狄利克雷分配（LDA）的学习（参数估计）是一个复杂的最 优化问题，很难精确求解，只能近似求解 常用的近似求解方法有吉布斯抽样（Gibbs sampling）和变分 推理（variational inference) 基本想法 LDA模型的学习，给定文本（单词序列）的集合 ， 目标是要推断：
19、(1）话题序列的集合 的后验概率分布 (2）参数 ， 是文本 wm 的话题分布的参数 (3）参数 ， 是话题 zk 的单词分布的参数 也就是说，要对联合概率分布 进行估计 其中 w 是观测变量，而z, , 是隐变量。 基本想法 为了估计多元随机变量x的联合分布p(x)，吉布斯抽样法选择x的一个 分量，固定其他分量， 按照其条件概率分布进行随机抽样，依次循 环对每一个分量执行这个操作，得到联合分布p(x)的一个随机样本， 重复这个过程，在燃烧期之后，得到联合概率分布p(x)的 样本集合 LDA模型的学习通常采用收缩的吉布斯抽样（collapsed Gibbs sampling）方法 基本想法 基
20、本想法是，通过对隐变量 和 积分，得到边缘概率分布 （也是联合分布） 其中变量w是可观测的，变量z是不可观测的 对后验概率分布 进行吉布斯抽样，得到分布 的 样本集合 再利用这个样本集合对参数 和 进行估计，最终得到LDA模型 的所有参数估计 算法的主要部分 根据上面的分析，问题转化为对后验概率分布 的吉布 斯抽样 该分布表示在所有文本的单词序列给定条件下所有可能话题序列 的条件概率。 抽样分布的表达式 首先有关系 这里变量 w, 和 已知，分母相同，可以不予考虑 联合分布域 的表达式 可以进一步分解为 两个因子可以分别处理 抽样分布的表达式 推导第一个因子 的表达式。首先 其中 是第k个话题
21、生成单词集合第v个单词的概率，nkv 是 数据中第k话题生成第v个单词的次数 抽样分布的表达式 于是 其中 抽样分布的表达式 第二个因子 的表达式可以类似推导。首先 其中 是第m个文本生成第k个话题的概率， 是数据中 第m个文本生成第k 个话题的次数。 抽样分布的表达式 于是 其中 ，可得 抽样分布的表达式 于是可得收缩的吉布斯抽样分布的公式 满条件分布的表达式 分布 的满条件分布可以写成 即在所有文本单词序列、其他位置话题序列给定条件下第i个位 置的话题的条件概率分布。 wi 表示所有文本的单词序列的第i个位置的单词 zi 表示单词 wi 对应的话 题 表示分布 对变量 zi 的边缘化因子。
22、 满条件分布的表达式 结合收缩的吉布斯抽样分布的公式，可以推出 第m个文本的第n个位置的单词 wi 是单词集合的第v个单词 其话题 zi 是话题合集的第k个话题 nkv 表示第k个话题中第n个单词的计数，但减去当前单词的计数 nmk 表示第m个文本中第k个话题的计数，但减去当前单词的话题的 计数。 算法的后处理 通过吉布斯抽样得到的分布 的样本，可以得到变量z 的分配值，也可以估计变量 和 1. 参数 的估计 根据LDA模型的定义，后验概率满足 这里 是第m个文本的话题的计数 表示分布 对变量 的边缘化因子 算法的后处理 于是得到参数 的估计式 算法的后处理 2. 参数 的估计 后验概率满足
23、是第k个话题的单词的计数 表示分布 对变量 的边缘化因子 I是文本集合单词序列w的单词总数 算法的后处理 于是得到参数的估计式 算法 对给定的所有文本的单词序列w，每个位置上随机指派一个话题， 整体构成所有 文本的话题序列z。然后循环执行以下操作。 在每一个位置上计算在该位置上的话题的满条件概率分布，然 后进行随机抽样， 得到该位置的新的话题，分派给这个位置。 算法 这个条件概率分布由两个因子组成，第一个因子表示话题生成该位置的单词 的概率， 第二个因子表示该位置的文本生成话题的概率。 整体准备两个计数矩阵： 话题-单词矩阵 和文本一话题矩阵 在每一个位置，对两个矩阵中该位置的己有话题的计数减
24、1，计 算满条件概 率分布，然后进行抽样，得到该位置的新话题，之后对两个矩阵中该位置 的新话题的计数加1。 计算移到下一个位置 在燃烧期之后得到的所有文本的话题序列就是条件概率分布 样 本 LDA吉布斯抽样算法 LDA吉布斯抽样算法 LDA吉布斯抽样算法 LDA的变分EM算法 变分推理 变分推理（variational inference)是贝叶斯学习中常用的、含 有隐变量模型的学习和推理方法 变分推理和马尔可夫链蒙特卡罗法（MCMC）属于不同的技巧 MCMC 通过随机抽样的方法近似地计算模型的后验概率，变分推 理则通过解析的方法计算模 型的后验概率的近似值 变分推理 变分推理的基本想法如下
25、假设模型是联合概率分布 p(x,z)，其中x是观测变 量（数据）， z是隐变量，包括参数 目标是学习模型的后验概率分布p(z|x)，用模型 进行概率推 但这是一个复杂的分布，直接估计分布的参数很困难 变分推理 考虑用概率分布q(z)近似条件概率分布p(zlx)，用KL散度 D(q(z) | p(zlx)）计算两者的相似度 q(z）称为变分分布（variational distribution) 如果能找到与p(zlx）在KL散度意义下最近的分布q*(z)，则可以 用这个分布近似p(zlx) 变分推理 下图给出了q*(z)与p(z|x)的关系 变分推理 KL散度可以写成以下形式 注意到KL散度大
26、于等于零，当且仅当两个分布一致时为零，由此 可知右端第一项与第二项满足关系 不等式右端是左端的下界，左端称为证据（(evidence)，右端称 为证据下界（(evidence lower bound, ELBO)，证据下界记作 变分推理 KL散度的最小化可以通过证据下界的最大化实现，因为目标是求 q(z)使KL散度最小化，这时log p(x)是常量 因此，变分推理变成求解证据下界最大化的问题 变分推理 变分推理目标是通过证据log p(x)的最大化，估计联合概率分布 p(x,z) 因为含有隐变量z，直接对证据进行最大化困难，转而根据 对证据下界进行最大化。 变分推理 对变分分布q(z)要求是具
27、有容易处理的形式，通常假设q(z)对z 的所有分量都是互相独立的（实际是条件独立于参数），即满足 这时的变分分布称为平均场（mean filed) KL散度的最小化或证据下界最大化实际是在平均场的集合，即满 足独立假设的分布集合 进行的 变分推理 总结起来，变分推理有以下几个步骤： 定义变分分布q(z) 推导其证据下界表达式 用最优化方法对证据下界进行优化，如坐标上升，得到最优分布 q*(z)，作为后验分布p(z|x)的近似。 变分EM算法 变分推理中，可以通过迭代的方法最大化证据下界，这时算法是 EM算法的推广， 称为变分EM算法 假设模型是联合概率分布 ， x是观测变量 z是隐变量 是参数
28、 目标是通过观测数据的概率（证据） 的最大化，估计模 型的参数 变分EM算法 使用变分推理，导入平均场 定义证据下界 通过迭代，分别以q和0为变量对证据下界进行最大化，就得到变 分EM算法 变分EM算法 变分EM算法 变分EM算法的迭代过程中，以下关系成立： 左边的等式基于E步计算和变分推理原理 中间的不等式基于M步计算 右边的不等式基于变分推理原理 说明每次迭代都保证观测数据的概率不递减。因此，变分EM算法 一定收敛，但可能收敛到局部最优 变分EM算法 EM算法实际也是对证据下界进行最大化 EM算法的推广是求F函数的极大-极大算法，其中的F函数就是证 据下界 EM算法假设q(z) = p(z
29、lx)且p(zx)容易计算，而变分EM算法则考 虑一般情况使用容易计算的平均场 当模型复杂时，EM算法未必可用，但变分EM算法仍然可以使用。 算法推导 1. 证据下界的定义 为简单起见，一次只考虑一个文本，记作w 文本的单词序列 ，对应的话题序列 ， 以及话题分布 ，随机变量w, z和 的联合分布是 w是可观测变量， 和z是隐变量， 和 是参数 算法推导 定义基于平均场的变分分布 其中 是狄利克雷分布参数， 是多项分布参数， 变量 和z的各个分量都是条件独立的 目标是求KL散度意义下最相近的变分分布 ，以近似 LDA模型的后验分布 。 算法推导 下图是变分分布的板块表示。LDA模型中隐变量 和
30、z之间存在 依存关系， 变分分布中这些依存关系被去掉，变量 和z条件 独立。 算法推导 由此得到一个文本的证据下界 其中数学期望是对分布 定义的，为了方便写作 和 是变分分布的参数， 和 是LDA模型的参数 所有文本的证据下界为 算法推导 为求解证据下界 的最大化，首先写出证据下界的表 达式。为此展开证据下界 算法推导 根据变分参数 和 ，模型参数 和 继续展开，并将 展开式的每一项写成一行 算法推导 算法推导 算法推导 算法推导 算法推导 算法推导 2. 变分参数 和 的估计 首先通过证据下界最优化估计参数 。 表示第n个位置的单词是由第k个话题生成的概率。考虑式 （20.47）关于 的最大化， 满足约束条件 算法推导 包含 的约束最优化问题拉格朗日函数为 这里 是（在第n个位置）由第k个话题生成第v个单词的概 率 对 求偏导数得 算法推导 令偏导数为零，得到参数 的估计值 接着通过证据下界最优化估计参数 。 是第k个话题的狄 利克雷分布参数。考虑式（20.47）关于 的最大化 算法推导 简化为 对 求偏导数得 据此，得到由坐标上升算法估计变分参数的方法 LDA的变分参数估计算法 算法推导 3. 模型参数 和 的估计 给定一个文本合集 ，模型参数估计对所有文 本同时进行 算法推导 算法推导 算法推导 LDA的变分EM算法
