2 SparseLDA算法

本章将介绍一种Gibbs Sampling算法的加速算法——SparseLDA [9]，它主要利用LDA 模型的稀疏性，来达到加速以及节省内存的目的，是一种精确算法（没有近似）。

2.1 背景

在介绍具体的算法之前，我们先细化一下算法 LdaGibbs 中的文档采样（主要是 k~∼p(zi|{z? }¬i,{w? }) 的采样），具体见 StandardGibbs，可以看到主要的时间消耗在计算归一化系数 Q（时间复杂度为 O(K)）。

上一章给出的LDA训练算法 LdaGibbs ：每个采样迭代复杂度是 O(MNm¯¯¯¯¯K)（Nm¯¯¯¯¯表示训练文档的平均长度）；内存消耗主要在 nkm 和 ntk，假设都采用Dense存储，内存复杂度是 O(K(M+V))；考虑到 nkm 的使用存在局部性，不用常驻内存（可以将上一个迭代的带有主题标号的文档 m 以及对应文档主题直方图 nkm 序列化到磁盘上，采样时通过loader线程预取），内存复杂度是 O(KV)。我们有没有复杂度更低的算法呢？

Porteous等人 [10] 以及Yao等人 [9] 分别给出了自己的解法，都是在优化算法 StandardGibbs 方面做文章。前者的FastLDA算法利用Hölder不等式 [11] 迭代逼近 Q，使得不用每次都计算所有的 q(z)。后者的SparseLDA算法利用LDA模型的稀疏性，也使得不用每次都计算所有的 q(z)，同时给出了一种更经济的模型存储方式。因为 SparseLDA 有更好的性能，本章重点介绍 SparseLDA 算法。

题外话，最近（KDD’2014 Best Research Track Paper）Li等人 [12] 利用 Alias 采样以及 Metropolis-Hastings 采样，给出了一个较 SparseLDA 更优的采样算法 AliasLDA。论文给出的实测数据显示，在 K=10,000 情况下，AliasLDA 较 SparseLDA 有一倍左右的性能提升。

2.2 SparseLDA 算法

Figure 7: Length distribution of nkm

Figure 8: Length distribution of ntk

LDA 模型中的 nkm 和 ntk （实现时，一般将 ntk 按词 t 组织成向量）非常稀疏，图 7 和 8 给出了二者的分布。分布来自一份英文语料、主题数 K=200 的实验 [13]，语料的文档平均长度 Nm¯¯¯¯¯ 在 30 左右（因为作者的懒惰，没有给出实际的大规模互联网语料上的分布图，但是引用的图已经能说明问题）。实际工程上使用的语义理解 LDA 模型一般使用搜索引擎 Query Log 或 Query Session Log 训练（因为 Query Log 中语义丰富），文档平均长度小于 30，而主题数 K 远大于 200（系列文章后续将介绍的 Peacock 系统支持百万级别主题数模型训练），所以 nkm 和 ntk 将更加稀疏。

基于以上认识，SparseLDA 将 Q 作 Eq. 2 的变形，同时令 E=∑ke(k)、F=∑kf(k) 和 G=∑kg(k)。其中 E 包含 |Nonzero(ntk,¬i)| 项，称为“topic word”桶；F 包含 |Nonzero(nkm,¬i)| 项，称为“document topic” 桶；G 包含 K项，称为“smoothing only”桶。

采样文档中词的主题时，首先计算 Q=E+F+G，同时生成一个随机变量U∼Uniform(0,Q)，然后在三个桶里进行具体的主题采样：

• 若 U<E，主题落在“topic word” 桶；
• 若 U<E+F，主题落在“document topic”桶；
• 否则，主题落在“smoothing only”桶。

具体桶内的主题采样，类似算法 StandardGibbs 的第三个for循环，不再赘述。具体算法见 SparseLda。 由于“smoothing only”桶与文档 m 无关，g?  和 G 可以预先计算，由外部传入。同时注意算法参数中传入的 c?  由Eq. 3 令 nkm,¬i=0 计算得出。

对文档 m 中的词 w=t，算法 SparseLda 计算归一化系数 Q 的时间复杂度为 O(|Nonzero(ntk,¬i)|，主题 k~ 采样最坏情况下时间复杂度为 O(K)。然而，随着采样迭代的进行（小几十个迭代），Q 值 99% 以上都将由“topic word”桶贡献，主题 k~采样的平均复杂度将收敛为 O(|Nonzero(ntk,¬i)|。综上，采用SparseLDA 的训练算法，每个采样迭代的平均时间复杂度为 O(MNm¯¯¯¯¯|Nonzero(ntk,¬i)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯) （其中 |Nonzero(ntk)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ 表示 ntk 向量的非零项平均个数）。显然，nkm 和 ntk 都将采用 Sparse 存储，如之前分析，假设只考虑 ntk，平均内存复杂度为 O(|Nonzero(ntk)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯V)。|Nonzero(ntk)| 的物理意义就是词 t 的语义种类数，显然，|Nonzero(ntk)|?K。搜索引擎 Query Log 语料，K=800 时，实测性能数据显示，算法 SparseLda 较 StandardGibbs 有小几十倍的性能提升。随着 K 的增大，加速比将更加惊人。

Figure 9: Comparison of algorithm StandardGibbs and SparseLDA

图 9 给出了算法 StandardGibbs 和 SparseLDA 采样文档 m 中词 w=t 的主题的对比示意图，此处主题数 K=4（对 k=1，nk=1m,¬i>0 且 ntk=1,¬i>0；对 k=2，nk=2m,¬i>0 且 ntk=2,¬i=0；对 k=3，nk=3m,¬i=0 且 ntk=3,¬i>0；对 k=4，nk=4m,¬i=0 且 ntk=4,¬i=0）。小伙伴们，图 9 中，相同的 q(z) 分布和 U怎么采样得到的主题不一样（对 StandardGibbs，k~=3；
对 SparseLDA，k~=1）呢，这样会有问题么？

2.3 Misc

2.3.1 nkm 和 ntk 向量的数据结构

显然，nkm 和 ntk 将采用 Sparse 存储，大家首先想到的当然是 Hashmap，Yao 等人 [9] 提出了一种更加高效的数据结构 SortedSparseHistogram。下面解释以 ntk 为例，nkm 同样适用。(k,ntk) 被编码到一个整型数字 e 中，e=(ntk<<b)|k)，其中 b为满足 2b≥K 的数。采样过程中，同时维护 e 向量按降序排列（这样可以加速采样，小伙伴们，想想这是为什么呢？），因为算法对 ntk 只存在“加加”和“减减”操作，使用类似索引排序的算法，在 K 不是非常大时，操作复杂度都是 O(1)。图 10 给出了一个具体的例子。

Figure 10: SortedSparseHistogram for ntk

关于整型数字 e 的类型，uint64 基本上能满足所有的需求：假设 K=100,000，b=⌈log2K⌉=17，剩下 64−17=47 位可以用来表示 ntk 或 nkm，最大值为 140 多亿。nkm 不会超过文档长度 Nm，ntk 值过大的词 t 应该去掉（停用词），一般公司的训练语料应该是不会超过如上限制的。Mimno [13] 给出的实际性能如下：在不是非常大的 K 情况下，SortedSparseHistogram 较 Hashmap 快 2 倍以上。

上文我们反复强调“K 不是非常大”，当 K 达到百万级别时，情况就完全不一样了，此时 Hashmap 较 SortedSparseHistogram 会更有优势。小伙伴们，你知道原因么？

2.3.2 O(1) 更新 g(k)、G、f(k)、F 和 c(k)

算法 SparseLda 采样文档 m 中词 w=t 时，需要 2 次更新 g(k)、G、f(k)、F 和c(k)：第一次“减减”排除“旧”主题 zi=k，第二次“加加”添加“新”采样的主题 zi=k~。下面以“减减”排除“旧”主题 zi=k 时，更新 g(k) 和 G 为例，“加加”以及 f(k)、F 和 c(k) 的更新方法类似：

• G−=g(k);
• update nkm,ntk,nk: nkm−=1,ntk−=1,nk−=1;
• calculate g(k) acc. to Eq. 6;
• G+=g(k).

2.3.3 Perplexity的快速算法

回顾 1.3 节 Eq. 6，可以发现 Perplexity({w? }|M) 重点在于计算 p(wm,n|M)，直接计算复杂度为 O(K)。对 p(wm,n|M) 进行 Eq. 7 的变形，同时令 r(m,t) 如 Eq.8、s(t) 如 Eq. 9 代入 Eq. 7，我们得到一种 p(wm,n|M) 的快速算法 Eq. 10。其中，r(m,t) 平均计算复杂度为 O(|Nonzero(nkm)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯)，s?  是一个长度为 V 的向量，可以预计算存储起来，后续查表取值。综上，Eq. 10 的平均计算复杂度为 O(|Nonzero(nkm)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯)。

向量 s?  直接计算复杂度为 O(KV)，对其做 Eq. 11 的变形，利用 SparseLDA 中的一些预计算（G），复杂度可以降到 O(|Nonzero(ntk)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯V)。

综上所述，Perplexity 快速算法可以将整个测试集 Perplxity 计算复杂度由 O(MNm¯¯¯¯¯K) 降低到 O(|Nonzero(ntk)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯V+MNm¯¯¯¯¯|Nonzero(nkm)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯)。

2.3.4 随机初始化带来的工程问题

Figure 11: Time of Peacock sampling iteration

如算法 LdaGibbs，LDA模型训练初始化时，通常给语料中所有词随机采样一个主题，这会带来一个工程上的问题：假设训练语料包含 M=2,000,000,000 个文档，文档平均长度为 Nm¯¯¯¯¯=5，模型主题数 K=100,000，那么初始化时模型 |Nonzero(ntk)|¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯=M∗Nm¯¯¯¯K=100,000=K （为了简化问题，假设训练集中的词频是均匀的，实际情况没有这么严重，因为词频满足长尾分布）！！问题退化为了 StandardGibbs，SparseLDA完全起不到加速和省内存的作用，反而因为要维护特殊的数据结构，增加了复杂度和内存。当然，随着迭代的进行，模型会变得越来越稀疏，采样迭代会越来越快。图 11 给出了分布式训练系统Peacock上，K=10,000的一次模型训练采样迭代时间随迭代次数的变化曲线（上述曲线出自非常早期的Peacock系统，只实现了Model Parallelism，没有Data Parallelism，同步消耗非常大）。假设模型收敛后的稀疏比为1%，而初始化时的稀疏比为 100%，为了训练时的前小几十个迭代，我们需要付出几十上百倍的模型内存、网络间数据传输以及计算时间！

有没有办法增大模型初始化时的稀疏性呢？

我们在这方面进行了一些尝试，一个主要的方法称之为 Topic Splitting：假设需要训练隐含语义数为 K=a×K1 的模型 A，我们先使用相同语料训练隐含语义数为 K1的模型 B，再将模型 B 训练结果语料中词的主题号随机分裂为 a 个，作为模型 A 训练的初始化。若模型 B 已经存在，但是模型 A 的训练语料和模型 B 的训练语料不相同，我们使用模型 B 在线 Inference （见第三章）所有的训练语料中词的主题号，继续上述过程即可。

图 12 给出了一次 Topic Splitting 实验的 Log Likehood 曲线，其中模型 A 的 K=100,000，模型 B 的 K=10,000，a=10。然而，这个方法有非常严重的问题，尤其在 a 取值较大时，小伙伴们知道是什么问题么？实际上Topic Splitting方法最终被我们放弃了，当有足够强大的训练系统时，这个方法不用也罢。如果没有强大的训练系统，又需要 K 非常大的模型，Topic Spliting 倒是一个可以考虑的方法（a>1 越小越好，可以取小数）。

Figure 12: Initialization using Topic Splitting

转自 http://www.flickering.cn/nlp/2014/10/lda%E5%B7%A5%E7%A8%8B%E5%AE%9E%E8%B7%B5%E4%B9%8B%E7%AE%97%E6%B3%95%E7%AF%87-2-sparselda%E7%AE%97%E6%B3%95/

参考文献

• [9] Limin Yao, David Mimno, and Andrew McCallum. Efficient Methods for Topic Model Inference on Streaming Document Collections. In KDD’ 2009.
• [10] Ian Porteous, David Newman, Alexander Ihler, Arthur Asuncion, Padhraic Smyth and Max Welling. Fast Collapsed Gibbs Sampling For Latent Dirichlet Allocation. In KDD’ 2008.
• [11] Hölder’s inequality. http://en.wikipedia.org/wiki/H%C3%B6lder%27s_inequality.
• [12] Aaron Q. Li, Amr Ahmed, Sujith Ravi, and Alexander J. Smola. Reducing the sampling complexity of topic models. In KDD’ 2014.
• [13] David Mimno. Efficient Inference for Multinomial Mixed Membership Models.

SparseLDA算法