[LDA工程实践之算法篇-2] SparseLDA算法

2 SparseLDA算法

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

2.1 背景

\begin{equation}\label{eq:qz}
\begin{aligned}
q(z) &= \frac{n^{t}_{k,\neg i} + \beta}{n_{k,\neg i} + \beta V}(n^{k}_{m,\neg i} + \alpha_k)
\end{aligned}
\end{equation}

在介绍具体的算法之前,我们先细化一下算法 LdaGibbs 中的文档采样(主要是 $\tilde{k} \sim p(z_i|\{\vec{z}\}_{\neg i}, \{\vec{w}\})$ 的采样),具体见 StandardGibbs,可以看到主要的时间消耗在计算归一化系数 $Q$(时间复杂度为 $O(K)$)。

上一章给出的LDA训练算法 LdaGibbs :每个采样迭代复杂度是 $O(M\overline{N_m}K)$($\overline{N_m}$ 表示训练文档的平均长度);内存消耗主要在 $n^{k}_m$ 和 $n^{t}_k$,假设都采用Dense存储,内存复杂度是 $O\left(K(M+V)\right)$;考虑到 $n^{k}_m$ 的使用存在局部性,不用常驻内存(可以将上一个迭代的带有主题标号的文档 $m$ 以及对应文档主题直方图 $n^{k}_m$ 序列化到磁盘上,采样时通过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 $n^{k}_m$

Figure 8: Length distribution of $n^{t}_k$

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

\begin{equation}\label{eq:q}
\begin{aligned}
Q &= \sum_k \frac{n^{t}_{k,\neg i} + \beta}{n_{k,\neg i} + \beta V}\left(n^{k}_{m,\neg i} + \alpha_k\right) \\
&= \sum_k \left(\frac{n^{t}_{k,\neg i}\left(n^{k}_{m,\neg i} + \alpha_k\right)}{n_{k,\neg i} + \beta V} + \frac{\beta n^{k}_{m,\neg i}}{n_{k,\neg i} + \beta V} + \frac{\beta \alpha_k}{n_{k,\neg i} + \beta V}\right) \\
&= \underbrace{\sum_k \frac{n^{t}_{k,\neg i}\left(n^{k}_{m,\neg i} + \alpha_k\right)}{n_{k,\neg i} + \beta V}}_E + \underbrace{\sum_k \frac{\beta n^{k}_{m,\neg i}}{n_{k,\neg i} + \beta V}}_F + \underbrace{\sum_k \frac{\beta \alpha_k}{n_{k,\neg i} + \beta V}}_G
\end{aligned}
\end{equation}

基于以上认识,SparseLDA 将 $Q$ 作 Eq. \ref{eq:q} 的变形,同时令 $E=\sum_k e(k)$、$F=\sum_k f(k)$ 和 $G=\sum_k g(k)$。其中 $E$ 包含 $|Nonzero(n^{t}_{k,\neg i})|$ 项,称为“topic word”桶;$F$ 包含 $|Nonzero(n^{k}_{m,\neg i})|$ 项,称为“document topic” 桶;$G$ 包含 $K$ 项,称为“smoothing only”桶。

\begin{equation}\label{eq:c}
\begin{aligned}
c(z=k) &= \frac{n^{k}_{m,\neg i} + \alpha_k}{n_{k,\neg i} + \beta V}
\end{aligned}
\end{equation}

\begin{equation}\label{eq:e}
\begin{aligned}
e(z=k) &= n^{t}_{k,\neg i}c(k)
\end{aligned}
\end{equation}

\begin{equation}\label{eq:f}
\begin{aligned}
f(z=k) &= \frac{\beta n^{k}_{m,\neg i}}{n_{k,\neg i} + \beta V}
\end{aligned}
\end{equation}

\begin{equation}\label{eq:g}
\begin{aligned}
g(z=k) &= \frac{\beta \alpha_k}{n_{k,\neg i} + \beta V}
\end{aligned}
\end{equation}

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

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

具体桶内的主题采样,类似算法 StandardGibbs 的第三个for循环,不再赘述。具体算法见 SparseLda。 由于“smoothing only”桶与文档 $m$ 无关,$\vec{g}$ 和 $G$ 可以预先计算,由外部传入。同时注意算法参数中传入的 $\vec{c}$ 由Eq. \ref{eq:c} 令 $n^{k}_{m,\neg i} = 0$ 计算得出。

对文档 $m$ 中的词 $w=t$,算法 SparseLda 计算归一化系数 $Q$ 的时间复杂度为 $O(|Nonzero(n^{t}_{k,\neg i})|$,主题 $\tilde{k}$ 采样最坏情况下时间复杂度为 $O(K)$。然而,随着采样迭代的进行(小几十个迭代),$Q$ 值 99% 以上都将由“topic word”桶贡献,主题 $\tilde{k}$ 采样的平均复杂度将收敛为 $O(|Nonzero(n^{t}_{k,\neg i})|$。综上,采用SparseLDA 的训练算法,每个采样迭代的平均时间复杂度为 $O(M\overline{N_m}\overline{|Nonzero(n^{t}_{k,\neg i})|})$ (其中 $\overline{|Nonzero(n^{t}_{k})|}$ 表示 $n^{t}_{k}$ 向量的非零项平均个数)。显然,$n^{k}_m$ 和 $n^{t}_k$ 都将采用 Sparse 存储,如之前分析,假设只考虑 $n^{t}_k$,平均内存复杂度为 $O(\overline{|Nonzero(n^{t}_{k})|}V)$。$|Nonzero(n^{t}_{k})|$ 的物理意义就是词 $t$ 的语义种类数,显然,$|Nonzero(n^{t}_{k})| \ll 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$,$n^{k=1}_{m,\neg i}>0$ 且 $n^{t}_{k=1,\neg i}>0$;对 $k=2$,$n^{k=2}_{m,\neg i}>0$ 且 $n^{t}_{k=2,\neg i}=0$;对 $k=3$,$n^{k=3}_{m,\neg i}=0$ 且 $n^{t}_{k=3,\neg i}>0$;对 $k=4$,$n^{k=4}_{m,\neg i}=0$ 且 $n^{t}_{k=4,\neg i}=0$)。小伙伴们,图 9 中,相同的 $q(z)$ 分布和 $U$ 怎么采样得到的主题不一样(对 StandardGibbs,$\tilde{k}=3$;
对 SparseLDA,$\tilde{k}=1$)呢,这样会有问题么?

2.3 Misc

2.3.1 $n^k_m$ 和 $n^t_k$ 向量的数据结构

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


Figure 10: SortedSparseHistogram for $n^t_k$

关于整型数字 $e$ 的类型,uint64 基本上能满足所有的需求:假设 $K=100,000$,$b = \lceil log_2 K \rceil = 17$,剩下 $64-17=47$ 位可以用来表示 $n^t_k$ 或 $n^k_m$,最大值为 140 多亿。$n^k_m$ 不会超过文档长度 $N_m$,$n^t_k$ 值过大的词 $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)$:第一次“减减”排除“旧”主题 $z_i = k$,第二次“加加”添加“新”采样的主题 $z_i=\tilde{k}$。下面以“减减”排除“旧”主题 $z_i = k$ 时,更新 $g(k)$ 和 $G$ 为例,“加加”以及 $f(k)$、$F$ 和 $c(k)$ 的更新方法类似:

  • $G -= g(k)$;
  • update $n^{k}_m, n^{t}_k, n_k$: $n^{k}_m-=1, n^{t}_k-=1, n_k-=1$;
  • calculate $g(k)$ acc. to Eq. \ref{eq:g};
  • $G += g(k)$.
2.3.3 Perplexity的快速算法

回顾 1.3 节 Eq. 6,可以发现 $Perplexity(\{\vec{w}\}|\mathcal{M})$ 重点在于计算 $p(w_{m,n}|\mathcal{M})$,直接计算复杂度为 $O(K)$。对 $p(w_{m,n}|\mathcal{M})$ 进行 Eq. \ref{eq:ll} 的变形,同时令 $r(m,t)$ 如 Eq. \ref{eq:rmt}、$s(t)$ 如 Eq. \ref{eq:st} 代入 Eq. \ref{eq:ll},我们得到一种 $p(w_{m,n}|\mathcal{M})$ 的快速算法 Eq. \ref{eq:qll}。其中,$r(m,t)$ 平均计算复杂度为 $O(\overline{|Nonzero(n^k_m)|})$,$\vec{s}$ 是一个长度为 $V$ 的向量,可以预计算存储起来,后续查表取值。综上,Eq. \ref{eq:qll} 的平均计算复杂度为 $O(\overline{|Nonzero(n^k_m)|})$。

\begin{equation}\label{eq:ll}
\begin{aligned}
p(w_{m,n}=t|\mathcal{M}) &= \sum^K_{k=1} \varphi_{k,t} \vartheta_{k,m} \\
&= \sum^K_{k=1} \varphi_{k,t} \frac{n^k_m + \alpha_k}{N_m + \sum^K_{k=1} \alpha_k} \\
&= \frac{1}{N_m + \sum^K_{k=1} \alpha_k} \left(\sum^K_{k=1} \varphi_{k,t}n^k_m + \sum^K_{k=1} \varphi_{k,t} \alpha_k \right) \\
\end{aligned}
\end{equation}

\begin{equation}\label{eq:rmt}
\begin{aligned}
r(m,t) &= \sum^K_{k=1} \varphi_{k,t}n^k_m \\
&= \sum_{k \in Nonzero(n^k_m)} \varphi_{k,t}n^k_m \\
\end{aligned}
\end{equation}

\begin{equation}\label{eq:st}
\begin{aligned}
s(t) &= \sum^K_{k=1} \varphi_{k,t} \alpha_k
\end{aligned}
\end{equation}

\begin{equation}\label{eq:qll}
\begin{aligned}
p(w_{m,n}=t|\mathcal{M}) &= \frac{r(m,t) + s(t)}{N_m + \sum^K_{k=1} \alpha_k}
\end{aligned}
\end{equation}

向量 $\vec{s}$ 直接计算复杂度为 $O(KV)$,对其做 Eq. \ref{eq:qst} 的变形,利用 SparseLDA 中的一些预计算(G),复杂度可以降到 $O(\overline{|Nonzero(n^{t}_{k})|}V)$。

\begin{equation}\label{eq:qst}
\begin{aligned}
s(t) &= \sum^K_{k=1} \varphi_{k,t} \alpha_k \\
&= \sum^K_{k=1} \frac{\alpha_k (n^t_k + \beta)}{n_k + \beta V} \\
&= \sum^K_{k=1} \frac{\alpha_k n^t_k}{n_k + \beta V} + \sum^K_{k=1} \frac{\beta \alpha_k}{n_k + \beta V} \\
&= G + \sum^K_{k=1} \frac{\alpha_k n^t_k}{n_k + \beta V}
\end{aligned}
\end{equation}

综上所述,Perplexity 快速算法可以将整个测试集 Perplxity 计算复杂度由 $O(M\overline{N_m}K)$ 降低到 $O(\overline{|Nonzero(n^{t}_{k})|}V + M \overline{N_m} \overline{|Nonzero(n^k_m)|})$。

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

Figure 11: Time of Peacock sampling iteration

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

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

我们在这方面进行了一些尝试,一个主要的方法称之为 Topic Splitting:假设需要训练隐含语义数为 $K=a \times K_1$ 的模型 A,我们先使用相同语料训练隐含语义数为 $K_1$ 的模型 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

参考文献

  • [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.

本文链接:[LDA工程实践之算法篇-2] SparseLDA算法
本站文章若无特别说明,皆为原创,转载请注明来源:火光摇曳,谢谢!^^


火光摇曳

[LDA工程实践之算法篇-2] SparseLDA算法》有12个想法

      1. 您好,可否解答下“上文我们反复强调“K 不是非常大”,当 K 达到百万级别时,情况就完全不一样了,此时 Hashmap 较 SortedSparseHistogram 会更有优势”的原因?

  1. 主要是把公式拆分成三部分(总体的topic分布部分, 每个词的topic分布部分, 文档-词的topic分布部分) . 用三个向量标识. 向量的第t个维度的值是前i-1个维度的累加和. 这样可以用二分法在 (3-4)* log(主题个数)步左右的查找完成文档中一个词的topic采样(这里还有很多可以优化的地方). 这方法的主要开销在计算文档-词的topic分布部分的(一般是文档长度的2-3倍的加法和乘法运算).推断的话每秒可以完成1万多次文档-topic分布采样(文档包含20左右的词, java 代码 2.2GHz的cpu) .

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*