论文阅读——使用聚类评估LDA的稳定性并提高其可靠性

Improving Reliability of Latent Dirichlet Allocation by Assessing Its Stability Using Clustering Techniques on Replicated Runs

https://arxiv.org/pdf/2003.04980.pdf

实现地址：https://github.com/JonasRieger/ldaPrototype（R语言）

 

主题模型中的潜在狄利克雷分布 LDA 是一种生成式概率模型，它将文本集中单个文本建模为潜在主题的混合，每个主题都以其单词分布为特征。由于将单词分配给主题依赖于初始值，因此 LDA 的结果在某种程度上是随机的。此外，Gibbs Sampling 是基于条件分布的，这会导致对相同文本进行重复运行时出现不同的结果。为了提高 LDA 结果的可靠性，使用一个修正的 Jaccard 系数来衡量两次生成主题的相似度，并使用相似度对主题进行聚类。作者提出一种对两次 LDA 产生的主题的层次聚类结果进行剪枝的算法，引入一种衡量 LDA 模型稳定性的方法 S-CLOP（Similarity of multiple sets by Clustering with LOcal Pruning 局部剪枝聚类得到多个集合的相似度）。实验表明，S-CLOP 可以用于评估 LDA 模型的稳定性，也可以用于通过单词分布描述主题的其他主题模型。多次运行 LDA 并以最具代表性的结果（即该结果与其他结果的平均相似度最高）作为 prototype，可以提高主题模型结果的可靠性和再现性。

语料库由 M 个文本组成，文本 m 由  个单词组成，m = 1, ..., M，文本的词汇表为 V。假设文本 m 中一共有 K 个主题 ，在位置 n（n = 1, ..., ）处的词  属于主题  ，。主题  的一个单词 v（v = 1, ..., V）的分配计数记为 ，所分配的词数可以汇总到向量：

        

 

每个主题的词计数矩阵为 。对于一个给定的参数集 {K, α, β}，LDA 概率模型为：

        

LDA 将每个词分配给 K 个主题之一，K 为主题数，α、β 为狄利克雷分布定义的文本中主题的分布和主题中单词的分布的先验参数。较高的 α 值会使多个不同的主题混合、而较低的 α 值容易产生更少但更占主导地位的主题。类似地，β 控制主题中词的混合程度。文本  的主题分布和主题  的词分布估计通常使用 Collapsed Gibbs Sampler，在这个过程中，词的初始分布是随机的，基于条件分布，这导致在固定参数下多次运行 LDA 的结果不同。LDA 这种不稳定性导致建模结果的可靠性不足。

现有几种方法可以提高 LDA 的可靠性（Agrawal et al. 2018、Maier et al. 2018、Koltcov et al. 2016），但它们都有缺点：建模的过程常常受到某种方式的影响，导致 LDA 失去了灵活性；或是不能在整个空间中搜索可能的模型，导致结果不是最优的。为了解决这些问题，作者提出的方法不影响建模，只是重复地运行 LDA。

 

为了评估 LDA 的稳定性，需要对主题进行相似性度量。作者定义了一个修正的 Jaccard 系数，它的意义是，不是所有的词都被认为与每个主题相关。Jaccard 系数的一般形式为：

        

其中 A, B 是单词的集合，在修正的 Jaccard 系数中，将 A 和 B 限定为比给定阈值更频繁地分配给两个相应主题的单词。

运行 R 次 LDA 后一共生成 N = RK 个主题，第 r 次运行每个主题的词计数矩阵为 ，主题 的分配总数为：

        

 为主题  的计数向量。重复建模使用符号 (Rep)：

对于两个主题 (i, j) 的给定的阈值下界 ，它们的词计数为：

        

修正后的Jaccard系数为：

 

        

 

对于所有单词，阈值向量  可以是一个相等的绝对下界 ，或者是一个相对下界 。修正的 Jaccard 系数  为两个主题中出现次数超过阈值的词的交集与并集之比，即使用与主题最相关的词来计算标准的 Jaccard 系数。

实例：使用相对下界 d = 500，这会使每个主题大约有100个重要的单词。最后两列表示单词属于修改后的交集还是并集，例如单词 election 不属于交集，因为它的计数低于主题的特定（相对）阈值，即应至少有9次分配给主题 。最后两列的总数之比得到两个主题的 。作者更喜欢 Jaccard 系数而不是 Jensen-Shannon 散度，因为下界阈值 c 提供了灵活性，并提高了解释性。

 

S-CLOP：衡量多组对象的相似度

在 LDA 中，对象是由词计数向量表示的主题，对象之间的两两距离由修改后的 Jaccard 系数计算。

S-CLOP：首先融合所有原始的集合为一个整体集合，聚类后使用局部后剪枝，然后检查簇中包含多少个原始集合的成员，计算每个集合中一个表征与最优解之间的差值。

对于一组主题模型，对象是主题，如果一个模型的一个主题与另一个模型的一个主题总是聚类在一起，可认为两个模型非常相似。在同一数据集反复运行多次 LDA，相似性高意味着每次可以识别许多主题。通常每次 LDA 使用50个主题，初始聚类使用具有完全相连的层次聚类（Hastie et al., 2009 ），即使用对象之间的最大距离来识别簇。这与作者确定高度同质群体的目标是一致的。

为了应用层次聚类，首先必须将主题相似度转换为距离。考虑一组主题的聚类 g，在 R 次 LDA 后使用所有 R·K 个主题进行聚类，向量  包含不同次 LDA 得到的主题数，定义偏差：

 

        

第一项  衡量 g 中每次运行恰好一个主题的最佳情况下的偏差，第二项决定簇中的成员数量，需要惩罚过大的簇，这是因为最小化差异和的算法将更喜欢一个大簇而不是一些小簇。

最小化聚类的所有簇 g∈G 上的差值之和 U(g)，所有 N 个对象（主题）的层次聚类得到 k 个簇，对得到的树状图进行局部剪枝：

        

其中 G 是一组主题簇，单个簇 g∈G 之间不相交。G* 表示树状图的最优的分割， 为最小差值的和。树状图的根节点包含由第一次分割得到的左右两个不相交的节点，迭代分割每个节点。

 

使用优化的聚类计算一组 LDA 运行结果的相似度，归一化最优聚类的差值和到 [0, 1] 区间（1 最好，0 最差，剪枝后有 R 个簇，每个簇包含一次 LDA 的所有主题）。剪枝算法2将生成一组 N 个单主题簇 ，最高的差值和为：

        

计算多次 LDA 运行结果相似度的方法：S-CLOP（使用局部剪枝聚类得到的多个集合的相似度），对最优聚类 G* 有：

        

 

实验结果

语料为 USA Today（2016年6月-11月），由 M = 7657 篇无重复的文章组成。小写字符、去掉数字和标点，停用词表为（Porter, 2001）；忽略出现次数少于6的单词，使词汇表总数 V 从 79734 减少到 25486。使用270次 Gibbs Sampler。每次 LDA 取 K = 50 个主题，令 α 和 β 的值为 1/50。

运行 4 次 LDA，即 R = 4，聚类的主题总数为 N = R·K = 4·50 = 200。使用修正的 Jaccard 系数Jm、完全链接和剪枝算法对 4 次独立运行中的 N 个主题进行聚类（从10000 次运行中选出 4 次）。将层次聚类与 200 个主题完全链接。主题被打上有意义的标签（单词或短语），这些标签是手工获得的，基于每个主题中最重要的 20 个单词的排名。因此，主题 k = 1, ..., K 中的单词 v = 1, ..., V 的重要性为：

        

ε是小正数 = ，重要性给当前主题中经常出现的、但在所有其他主题中平均出现的次数较少的单词打了高分。

图1显示了 200 个主题聚类的树状图，以及局部剪枝聚类算法的结果。横轴表示基于 d = 500 的  的完全链接距离，用于主题聚类。在左侧的树状图中，主题标签的颜色与 LDA 次数相关（Run1: petrol, Run2: green, Run3: orange, Run4: red），在右侧的树状图中，主题标签根据剪枝算法获得的簇进行着色，每个主题标签都以其运行编号作为前缀。

从右侧的树状图中可以看出，在确定的主题聚簇中，主题的标题通常非常相似。这表明 4 次 LDA 运行容易产生类似的主题，这些主题由类似的单词分布表示。此类稳定话题的例子有：黄色的 Trump vs Clinton Campaign，绿色的奥运奖牌。然而，也存在明显的差异：左边的树状图中，Run4 有几个主题的附近没有其他主题。值得注意的是，Run4 创造了如此多的单独主题，例如电子游戏、性别辩论、电视体育，而且 Run4 会产生 6 个停用词主题，而其他 Run 只产生 4 到 6 个停用词主题。

在右侧树状图中，颜色取决于聚簇成员的关系。使用剪枝算法衡量这四个 LDA 的稳定性，生成 61 个聚簇，稳定性为 0.83（归一化因子 ，最小化的差值之和 ，S-CLOP = 1−25/150 = 0.83）。有 7 个主题，分别来自前 3 个 Run 中的每个主题和 Run4中的4个主题。11 个簇包含 3 个主题，其中包含 Run1 主题的 10 次，来自 Run2 和 Run3 的主题分别出现了 9 次，只有 5 个簇包含来自 Run4 的主题，这说明 Run4 与其他 Run 有很大不同。

 

基于剪枝算法确定一个 LDA run 作为一组中最具代表性的 prototype，该算法可以获得更高的 LDA 相似度，原型 LDA 的结果具有更高的可靠性。稳定性度量 S-CLOP 量化了两个 LDA run 的两两相似度：

        

其中 K = 50 为每个模型的主题数，G* 为剪枝算法识别的优化的主题簇。训练 100 个 LDA 模型从中选择平均相似度最高的模型作为原型。这个过程重复 100 次，得到 100 个原型模型。下图右边的曲线描述了 100 个原型的平均相似度的经验累积分布函数，最左边是 100×100 的原始 run 的100条曲线。此外还从子样本中确定了 100 个原型，即从每组原始的 100 次运行中随机选择第 10、20、30、40 或 50 次运行用于计算。

原始的 100 个模型的 100 个簇的平均相似度的最小值为 0.796，最大值为 0.877。重复拟合更多次可以提高相似度，建议至少 50 次，可使最小值增加到 0.862，最大值增加到 0.895。一般来说，选择取决于语料库的复杂性，封装的主题或某些复杂的依赖结构使建模过程更倾向于更大的可能的匹配范围，因此平均相似度更小。然而，如果计算能力有限，从 10 个候选对象中获取原型模型也可以显著提高稳定性，其平均相似度的最小、最大值分别为 0.842 和 0.880，明显高于不进行重复运行的情况。

图1的树状图表明，随机选择可能产生一个解释性很差的模型。实际上，Run1 和 Run2 为 100 个原型中平均相似度最高的两个模型，这意味着它们位于图2中非常靠右的曲线的顶部，它们在原型簇中的相似度为 0.902、0.898，原始簇为 0.877、0.871。Run3 为 100 个原型模型中最差的模型，原型 / 原始簇的相似度为 0.872、0.863。随机选取的 Run4 模型为最差模型之一，原始簇的相似度为 0.807。由图2分析表明，随机选择会降低可靠性，使用重复运行和原型的方法可以增加平均相似度，从而提高结果的可靠性。