Question

1. 标准LDA 的模型训练过程中，对于文档 $ \mathcal D_{i} $ （令 $ t=z^i_j, v=w_j^i $ ，采用基于位置的更新） ：

   $ p(\text{topic}_{t} \mid \mathbf{TOPIC}_{\neg{(i,j)}},\mathbf{WORD}) \propto \left(n_z^{\prime}(i,t)+\alpha_{t}\right) \times \frac{n_v^{\prime}(t,v)+\eta_{v}}{F(t) -1 +\eta_{\mathbb D}} $

   常规的采样方式是：

   • 计算 $ p_t = p(t)= p(\text{topic}_{t} \mid \mathbf{TOPIC}_{\neg{(i,j)}},\mathbf{WORD}),t=1,2,\cdots,T $
   • 将采样空间划分为：第一段 $ [0,p_1 ) $ ， 第二段 $ [p_1,p_1+p_2) $ ，... 第 $ T $ 段 $ \left[\sum_{t=1}^{T-1}p_t, \sum_{t=1}^Tp_t \right) $ ，称作分桶。
   • 在 $ \left[0, \sum_{t=1}^Tp_t\right] $ 之间均匀采样一个点，该点落在哪个桶内则返回对应桶的主题。

2. 常规LDA 采样算法：

   • 在 $ \left[0, \sum_{t=1}^Tp_t\right] $ 之间均匀采样一个点，假设为 $ x $ 。其算法复杂度为 $ O(T) $ ，因为需要计算 $ \sum_{t=1}^Tp_t $ 。
   • 查找下标 $ K $ ，使得满足 $ \sum_{t=1}^{K-1}p_t \le x\lt \sum_{t=1}^Kp_t $ ，返回 $ K $ 。通过二分查找，其算法复杂度为 $ O(\log T) $ 。

3. 事实上如果执行非常多次采样，则常规LDA 采样算法第一步的成本可以分摊到每一次采样。因此整体算法复杂度可以下降到 $ O(\log T) $ 。如果仅执行一次采样，则整体算法复杂度为 $ O(T) $ 。

   $ p(t) $ 与 $ v $ 有关，而 $ v = w_j^i $ 在文档 $ \mathcal D_i $ 的不同位置 $ j $ 取值不同。这意味着每一次采样的概率分布都不同，因此采样每个主题的算法复杂度为 $ O(T) $ 。

4. 有三种算法对采样过程进行了加速：

   • SparseLDA 和 AliasLDA 使用基于位置的采样，这是为了方便对采样概率进行有效分解。
   • LightLDA 使用基于单词的采样，这种采样更能够满足LDA 的假设：LDA 假设同一篇文档中同一个单词都由同一个主题生成。

4.1 SparseLDA

1. sparseLDA 推断比传统 LDA 快大约20倍，且内存消耗更少。

   

4.1.1 概率分解

1. SparseLDA 主要利用了LDA 的稀疏性。事实上，真实场景下的一篇文档只会包含少数若干个主题，一个词也是参与到少数几个主题中。因此可以将采样公式分解（令 $ t=z^i_j, v=w_j^i $ ，采用基于位置的更新）：

   $ p_{i,t} = p(i,t) = \left(n_z^{\prime}(i,t)+\alpha_{t}\right) \times \frac{n_v^{\prime}(t,v)+\eta_{v}}{F(v) -1 +\eta_{\mathbb D}} = r(t ) +s(t )+ q (t )\\ r(t )= \frac{ \alpha_{t}\times \eta_{v}}{F(t) -1 +\eta_{\mathbb D}}; \quad s(t ) = \frac{n_z^{\prime} (i,t)\times \eta_{v}}{F(t) -1 +\eta_{\mathbb D}};\quad q(t) = \frac{\left(n_z^{\prime} (i,t)+\alpha_{t}\right)\times n_v^{\prime} (t,v)}{F(t )-1 +\eta_{\mathbb D}} $

   令：

   $ R^i = \sum_{t=1}^T r(t);\quad S^i = \sum_{t=1}^T s(t);\quad Q^i = \sum_{t=1}^T q(t) $

   其中： $ R ^i $ 仅仅和主题的单词统计有关； $ S ^i $ 和文档 $ \mathcal D_i $ 的主题统计、主题的单词统计都有关； $ Q ^i $ 和文档 $ \mathcal D_i $ 的主题统计、主题的单词统计、文档 $ \mathcal D_i $ 的单词统计都有关。

   假设 $ \eta_1=\eta_2=\cdots=\eta $ 为常数，即：主题的所有单词的先验频数都为常数 $ \eta $ 。现在仅考虑一篇文档的训练，因此忽略角标 $ i $ ，有：

   $ p_{t} = p(t) = r(t) + s(t) + q(t)\\ r(t )= \frac{ \alpha_{t}\times \eta}{F(t) -1 +\eta V}; \quad s(t ) = \frac{n_z^{\prime} (t)\times \eta}{F(t) -1 +\eta V};\quad q(t) = \frac{\left(n_z^{\prime} (t)+\alpha_{t}\right)\times n_v^{\prime} (t,w_j)}{F(t ) -1 +\eta V}\\ R = \sum_{t=1}^T r(t);\quad S = \sum_{t=1}^T s(t);\quad Q = \sum_{t=1}^T q(t) $

2. 令 $ U=\sum_{t=1}^T p_t $ ，原始LDA 的采样方式为：

   • 将 $ [0, U) $ 划分为 $ T $ 个桶，将每个桶根据其 $ (r,s,q) $ 分解继续划分为三个子桶。
   • 根据从均匀分布 $ (0 \sim U) $ 中采样一个点。该点落在那个桶，则采样该桶对应的主题。

   假设该点落在桶 $ t $ ，则有三种情况：

   • 若该点落在 r 对应的子桶，其概率为 $ \frac{p_t}{U}\times \frac{r(t)}{p_t} $ 。
   • 若该点落在 s 对应的子桶，其概率为 $ \frac{p_t}{U}\times \frac{s(t)}{p_t} $ 。
   • 若该点落在 q 对应的子桶，其概率为 $ \frac{p_t}{U}\times \frac{q(t)}{p_t} $ 。

3. 考虑重新组织分桶，按照 $ R,S,Q $ 划分为 [0,R)、[R,R+S)、[R+S,U) 三个桶。将第一个桶根据 $ r(1),\cdots,r(T) $ 划分为 T 个子桶； 将第二个桶根据 $ s(1),\cdots,s(T) $ 划分为 T 个子桶；将第三个桶根据 $ q(1),\cdots,q(T) $ 划分为 T 个子桶。

   则上述采样过程的三种情况等价于：从均匀分布 $ (0 \sim U) $ 中采样一个点。该点落在那个桶，则就在桶内的子桶中继续采样主题。

   • 该桶落在 R 桶的子桶 t ，其概率为： $ \frac{R}{U}\times \frac{r(t)}{R} $ 。
   • 该桶落在 S 桶的子桶 t ，其概率为： $ \frac{S}{U}\times \frac{s(t)}{S} $ 。
   • 该桶落在 Q 桶的子桶 t ，其概率为： $ \frac{Q}{U}\times \frac{q(t)}{Q} $ 。

4.1.2 采样过程

1. sparseLDA 采样过程中假设：在同一篇文档的同一次迭代期间，文档-主题 计数、主题-单词 矩阵保持不变。即：参数延迟更新。

2. sparseLDA 采样过程：从均匀分布 $ (0 \sim U) $ 中采样一个点 $ x $ 。

   • 如果 $ x\lt R $ ，则从 $ (0\sim R) $ 中继续均匀采样一个点，设该点落在子桶 $ [r(t-1),r(t)) $ ，则返回主题 $ \text{topic}_t $ 。

     考虑到 $ r(t )= \frac{ \alpha_{t}\times \eta}{F(t) -1 +\eta V} $ 对于同一篇文档中的所有位置都相同，这使得对桶 $ R $ 采样的平摊算法复杂度为 $ O(\log T) $ 。

   • 如果 $ R\lt x\le R+S $ ，则从 $ (0\sim S) $ 中继续均匀采样一个点，设该点落在子桶 $ [s(t-1),s(t)) $ ，则返回主题 $ \text{topic}_t $ 。

     此时只需要考虑当前文档中出现的主题，因为对于其它未出现的主题有 $ n_z^{\prime}(t)=0 $ ，则 $ s(t) = \frac{n_z^{\prime} (t)\times \eta }{F(t) -1 +\eta V }=0 $ 。

     因此对桶 $ S $ 采样的算法复杂度为 $ O(T_d) $ ， $ T_d $ 为文档中出现的主题数量。 同时内存消耗更少，因为只需要保存非零值对应的分量。

   • 如果 $ R+S\lt x\le U $ ，则从 $ (0\sim Q) $ 中继续均匀采样一个点，设该点落在子桶 $ [q(t-1),q(t)) $ ，则返回主题 $ \text{topic}_t $ 。

     此时只需要考虑使得当前单词 $ \text{word}_v $ 的 主题-单词 计数非零的那些主题。因为对于其它主题有 $ n_v^{\prime}(t,v)= 0 $ ，则 $ q(t) = \frac{\left(n_z^{\prime}(t)+\alpha_{t}\right)\times n_v^{\prime}(t,v)}{F(t) -1 +\eta V} = 0 $ 。

     因此对桶 $ Q $ 采样的算法复杂度为 $ O(T_{v}) $ ， $ T_{v} $ 为当前单词 $ \text{word}_v $ 涉及到的主题数量 。 同时内存消耗更少，因为只需要保存非零值对应的分量。

   • 整体推断的算法复杂度为 $ O(T_d+T_{v} + \log T) $ 。

3. 对于小数据集， $ T_d +T_{v} +\log T\ll T $ ，但是对于大数据集可能发生 $ T_{v} \rightarrow T $ 。即：单词 $ \text{word}_v $ 出现在了几乎所有主题中。

   假设单词 $ \text{word}_v $ 由主题 $ t $ 生成的可能性为 $ \delta $ ，则 $ n $ 篇文档中 $ \text{word}_v $ 至少由主题 $ t $ 生成的一次的概率为：

   $ \lim _{n \rightarrow \infty}1-(1-\delta )^n = 1 $

   因此对于非常大的数据集对于 sparseLDA 是不利的。

4.2 AliasLDA

4.2.1 概率分解

1. AliasLDA 通过引入 Alias Table 和 Metropolis-Hastings 方法来进一步加快采样速度。

2. AliasLDA 对采样公式进行不同的分解（令 $ t=z^i_j, v=w_j^i $ ，采用基于位置的更新）：

   $ \left(n^{\prime}_z (t)+\alpha_{t}\right) \times \frac{n^{\prime}_v (t,v)+\eta}{F(t) -1+\eta V} = s(t) + q(t)\\ s(t) = n_z^{\prime} (t) \frac{n^{\prime}_v (t,v)+\eta}{F(t) -1 +\eta V};\quad q(t) = \alpha_{t} \frac{n^{\prime}_v (t,v)+\eta}{F(t)-1 +\eta V}\\ S=\sum_{t=1}^Ts(t);\quad Q=\sum_{t=1}^Tq(t);\quad U = S+Q $

   其中 $ Q $ 与文档无关。

3. AliasLDA 采样过程是：从均匀分布 $ (0 \sim U) $ 中采样一个点 $ x $ 。

   • 如果 $ x<=S $ ，则从 $ (0\sim S) $ 中继续均匀采样一个点，设该点落在子桶 $ [s(t-1),s(t)) $ ，则返回主题 $ \text{topic}_t $ 。

     此时只需要考虑当前文档中出现的主题，因为对于其它未出现的主题有 $ n^{\prime}_z(t)=0 $ ，则 $ s(t) = n_z ^{\prime}(t) \frac{n_v^{\prime} (t,v)+\eta}{F(t) -1+\eta V}=0 $ 。

     因此对桶 $ S $ 采样的算法复杂度为 $ O(T_d) $ ， $ T_d $ 为文档中出现的主题数量。 同时内存消耗更少，因为只需要保存非零值对应的分量。

   • 如果 $ x>S $ ，则从 $ (0\sim Q) $ 中继续均匀采样一个点，设该点落在子桶 $ [q(t-1),q(t)) $ ，则返回主题 $ \text{topic}_t $ 。

     如果能够使得该子采样的算法复杂度为 $ O(1) $ ，则整体采样的算法复杂度为 $ O(T_d) $ ，要大大优于 sparseLDA的 $ O(T_d+T_{v} + \log T) $ 。

4.2.2 Alias Table

1. Alias Table 用于将离散的、非均匀分布转换成离散的、均匀的分布。这是为了采样方便：离散均匀分布的采样时间复杂度为 $ O(1) $ 。

2. 假设一个离散、非均匀分布为 $ \{P(X=1)=\frac 12,P(X=2)=\frac{1}{3},P(X=3)=\frac{1}{12},P(X=4)=\frac{1}{12} \} $ 。

   常规的采样方式为：

   • 分桶：1:[0,1/2), 2:[1/2,5/6), 3:[5/6,11/12), 4:[11/12,1) 。
   • 采样：从0~1 之间均匀生成一个随机数 x ，x 落在哪个桶（二分查找），则返回对应的桶的编号。

   其平均每次采样的复杂度为 $ O(\log N) $ ，其中 $ N $ 为事件的数量。

3. 一个改进的方法是：

   • 建立四个分桶，桶的编号分别为 1~4 。

   • 从1~4 中均匀采样一个整数，决定落在哪个桶。假设在第 $ i $ 个桶。

   • 从 0~1 之间均匀采样一个小数 $ x $ ，则：

     • 计算非归一化概率： $ p_i = \frac{P(X=i)}{\max_{j}P(X=j)} $ （即：归一化概率除以其中的最大值）。
     • 若 $ x\le p_i $ ，则接受采样，返回事件 $ i $ ；若 $ x\gt p_i $ ，则拒绝接受，重新采样（重新选择分桶、重新采样小数）。

   理想情况下其算法复杂度为 $ O(1) $ ，平均情况下算法复杂度为 $ O(N) $ 。

   可以看到：事件 $ \{X=1,X=2,X=3,X=4\} $ 被选中的概率（非归一化）为： $ \{\frac 14\times 1,\frac 14\times \frac 23,\frac 14\times \frac 16,\frac 14\times \frac 16\} $ ，归一化之后就是 $ \{\frac 12,\frac 13,\frac{1}{12},\frac{1}{12} \} $ 。

   

4. Alias Table 在上述思想指导下更进一步，它对概率除以均值而不是最大值。

   • 构建 Alias Table （算法复杂度 $ O(N ) $ ）：

     • 初始化数组 $ P_{array} = [p_1,p_2,\cdots,p_N] $ ，第 $ i $ 个桶的容量 $ p_i $ 表示事件 $ i $ 发生的概率； $ G_{array}=[0,0,\cdots,0] $ ， $ G_{array}[i] $ 存放第 $ i $ 个桶中的另外一个事件的编号。

       第 $ i $ 个桶要么完全由事件 $ i $ 组成，要么由事件 $ i $ 和另外一个事件组成（由 $ G_{array}[i] $ 给出）。每个桶最多包含2个事件。

     • 将每个桶的容量乘以 $ N $ ： $ P_{array}[i] \leftarrow P_{array}[i]\times N $ 。即：计算非归一化概率。

     • 构建队列 A，存放容量大于1的桶编号；构建队列 B，存放容量小于1的桶编号。

     • 处理每个桶，直到满足条件：队列 B 为空。处理方式为：

       从队列 A 取出一个桶，假设为 $ i $ ；从队列 B 取出一个桶，假设为 $ j $ 。将 $ j $ 填充到容量为1，填充的容量从 $ i $ 消减。假设消减的容量为 $ \Delta_{i\rightarrow j } $

       • 记录容量： $ P_{array}[i] \leftarrow P_{array}[i]- \Delta_{i\rightarrow j } $ ；登记： $ G_{array}[j] = i $ 。

       注意：此时不需要更新 $ P_{array}[j] $ ， $ P_{array}[j] \lt 1 $ 存放的是事件 $ j $ 的非归一化概率，也等于它在桶中的比例。

       • 若 $ P_{array}[i] \gt 1 $ ，则继续放入队列A；若 $ P_{array}[i] \lt 1 $ ，则放入队列B ；若 $ P_{array}[i] = 1 $ ，则桶 $ i $ 处理完成。

       最终每个桶的容量都是1，桶内最多存放两个事件（由 $ G_{array} $ 记录）。

   • 从1~N 中均匀采样一个整数，决定落在哪个桶。

   • 从 0~1 之间均匀采样一个小数 $ x $ 。假设在第 $ j $ 个桶：若 $ x \le P_{array}[j] $ ，则返回事件 $ j $ ；否则返回事件 $ G_{array}[j] $ 。

5. Alias Table 的算法复杂度：

   • 构建 Alias Table 步骤复杂度 $ O(N) $ ，采样步骤复杂度 $ O(1) $
   • 如果采样1次，则算法复杂度为 $ O(N) $ 。如果采样非常多次，则构建 Alias Table 的代价会被平均，整体的平摊复杂度为 $ O(1) $ 。

4.2.3 MH 采样算法

1. 如果直接对 $ q(t) = \alpha_{t} \frac{n^{\prime}_v (t,v)+\eta}{F(t) -1+\eta V} $ 采用 Alias Table 采样，则会发现一个严重的问题：对于文档中不同位置 $ j $ 的单词 $ v=w_j $ 不同，因此概率分布 $ q(t) $ 随位置 $ j $ 发生变化。这就相当于采样 1 次的 Alias Table 算法，完全没有发挥出 Alias Table 的优势。

   解决方式是：提出一个不随位置 $ j $ 变化的概率分布 $ \bar q(t) $ ，它近似原始分布 $ q(t) $ 但是更容易采样。然后采用基于 MH 的 MCMC 采样算法。

2. 标准的 MH 算法需要构建状态转移矩阵，但是这里的状态转移比较特殊：状态转移概率仅与最终状态有关，与前一个状态无关，即： $ q(i) = q(i\leftarrow j),\bar q(i) = \bar q(i\leftarrow j) $ 。

   • 算法输入： 近似概率分布 $ \bar q(t) $ ，原始概率分布 $ q(t) $

   • 算法输出：满足原始分布的采样序列 $ \{x_0,x_1,\cdots,x_{n},x_{n+1},\cdots\} $

   • 算法步骤：

     • 从概率分布 $ \bar q(t) $ 中随机采样一个样本 $ x_0 $

     • 对 $ i=1,2,\cdots $ 执行迭代。迭代步骤如下：

       • 根据 $ [\bar q_1,\bar q_2,\cdots,\bar q_T] $ 采样出候选样本 $ x^{*} $

       • 计算接受率 $ \alpha(x^{*}) $ ：

         $ \alpha( x^{*} )=\min \left(1,\frac{q( x^{*})\bar q( x _{i-1} )}{q( x _{i-1})\bar q( x^{*} )} \right) $

       • 根据均匀分布从 $ (0,1) $ 内采样出阈值 $ u $ ，如果 $ u \le \alpha( x^{*}) $ ，则接受 $ x^{*} $ ， 即 $ x_{i}= x^{*} $ 。否则拒绝 $ x^{*} $ ， 即 $ x_{i}= x_{i-1} $ 。

         由于 $ \bar q(t) $ 近似于 $ q(t) $ ，因此大多数情况下会接受 $ x^{*} $ 。

     • 返回采样序列 $ \{x_0,x_1,\cdots\} $ 。

     注意：返回的序列中，只有充分大的 $ k $ 之后的序列 $ \{ x_{k}, x_{k+1},\cdots\} $ 才是服从原始分布的采样序列。

4.2.4 AliasLDA

1. AliasLDA 综合采用了 AliasTable 和 MH 采样算法。对分桶 $ Q $ 采样的算法步骤：

   • 构建不随文档中的位置 $ j $ 变化的概率分布 $ \bar q(t) $ ，算法复杂度 $ O(T) $ 。

   • 根据 $ \bar q(t) $ 构建 AliasTable ，算法复杂度 $ O(T) $ 。

   • 循环：遍历文档的所有位置 $ j=1,2,\cdots,n $ ：

     对于文档的当前位置 $ j $ 根据前述的 MH 算法采样出主题 $ t $ ，其算法复杂度为 $ O(1) $ 。

   考虑到前面两步的代价可以平摊到每次采样过程，因此平摊算法复杂度为 $ O(1) $ 。

4.3 LightLDA

1. web-scale 规模的预料库非常庞大也非常复杂，通常需要高容量的主题模型（百万主题、百万词汇表，即：万亿参数级别）来捕捉长尾语义信息。否则，当主题太少时会丢失这些长尾语义信息。

   这种规模数据集的训练需要上千台机器的集群，而LightLDA 允许少量的机器来训练一个超大规模的LDA 主题模型，它可以用 8 台机器训练一个包含百万主题&百万词汇表（万亿级参数）、包含千亿级单词的数据集。

2. LightLDA 主要采用了以下方法：

   • 更高效的MH 采样算法，其算法复杂度为 $ O(1) $ ，并且与当前最先进的Gibbs 采样器相比收敛效率快了近一个量级。
   • structure-aware 的模型并行方案，其利用主题模型中的依赖关系，产生一个节省机器内存和网络通信的采样策略。
   • 用混合数据结构来存储模型，其针对高频单词和低频单词采用不同的数据结构，从而使得内存可以放置更大规模的模型，同时保持高效的推断速度。
   • 有界异步数据并行方案，其可以降低网络同步和通信的成本，从而允许通过参数服务器对海量数据进行有效的分布式处理。

4.3.1 structure-aware 模型并行

1. 数据并行：分割数据集，将不同文档集交给不同的 worker 来处理。所有 worker 共享同一份模型参数，即：共享同一份全局 主题-单词 矩阵 $ \mathbf W $ 。

   如：YahooLDA 和 基于参数服务器的LDA 实现就是采取数据并行。

2. 数据并行+模型并行：分割数据集，将不同文档集交给不同的 worker 来处理。同时分割模型，不同 worker 处理不同的 主题-单词 分布。即：每个worker 只会看到并处理本地文档出现过的单词的 主题-单词 分布。

   如：PLDA 和 Peacock ，以及 LDA 就是采取这种策略。

3. 为了解决模型内存需求太大与worker 内存较小的问题，LightLDA 提出了 structure-aware 模型并行方案。

   • 在每个worker 中，采样算法执行之前先将本 worker 分割到的数据集进一步划分为数据块 Data Block 1,Data Block 2,... 。同时计算每个数据块包含的单词的词汇表，并将该词汇表作为元数据附加到数据块上。

     该操作只需要线性扫描，其计算复杂度为 $ O(1) $ 。

   • 在worker 对 Data Block i 执行采样时：

     • 首先加载数据块 Data Block i 到 worker 的内存，取得该 block 的元数据。

     • 然后根据元数据，将该数据块的词汇表划分为集合 $ \mathbb V_1,\mathbb V_2,\cdots $ 。

     • 对每个词表集合 $ \mathbb V_j $ ，拉取参数服务器中的全局 主题-单词 矩阵 $ \mathbf W $ 中涉及 $ \mathbb V_j $ 的单词的部分，称作模型切片，记作 $ \mathbf W_j $ 。因此worker 仅仅需要保存模型的一个切片。

       然后对 Data Block i 中的所有文档执行采样并更新 $ \mathbf W_j $ ，采样时仅仅考虑出现在 $ \mathbb V_j $ 中的单词。

     • 当对 $ \mathbf W_j $ 更新完毕时，将本次更新同步到参数服务器中的全局 主题-单词 矩阵 $ \mathbf W $ 。然后继续处理下一个词汇集合 $ \mathbb V_{j+1} $ 。

   • 一旦对 Data Block i 处理完毕，继续采样下一个数据块 Data Block i+1 。

   如下图所示为 Data Block 2 的采样过程， $ S_2 $ 表示该数据块包含的文档数量。在d1,d2,... 中的箭头给出了主题采样的顺序。每个文档通过灰色块表明出现对应的单词（出现一次或多次）、白色块表明没有出现对应的单词。

   

4. structure-aware 除了降低worker 内存需求之外，还通过以下方式减轻网络通信瓶颈：

   • 在处理数据块 Data Block i 时，只有当前模型切片相关的所有单词都被采样时，才会移动到下一个模型切片。

     这使得在处理数据块 Data Block i 时，每个模型切片只需要被换入换出内存一次，而不是反复换入换出内存。模型切片的换入换出需要和参数服务器进行同步，因此多次交换会增大通信压力。

   • 在利用当前模型切片对数据块采样时，可以同步进行下一个模型切片的加载（从参数服务器拉取到本地）、上一个模型切片的同步更新（从本地推送到参数服务器）。

     这进一步降低了网络通信的时间延迟。

4.3.2 高效的 MH 采样算法

1. AliasLDA 采样的计算复杂度为 $ O(T_d) $ ，因此它不擅长处理比较长的文档，比如网页。这是因为：在初始迭代中，文档每个位置的主题都是随机初始化的，因此对于较长的文档 $ T_d $ 非常大。这会使得AliasLDA 在迭代初期非常缓慢，消耗大量时间。

2. 当利用分布 $ \bar q(t) $ 对 $ q(t) $ 进行采样时，一个好的 $ \bar q(t) $ 需要满足两个条件（从而加速采样速度）：从 $ \bar q(t) $ 中采样相对更加容易；马尔科夫链更快混合mix 。

   因此在设计分布 $ \bar q(t) $ 时，存在一个折中：

   • 如果分布 $ \bar q(t) $ 和 $ q(t) $ 更接近，则马尔科夫链混合的更快，但是从 $ \bar q(t) $ 采样的代价可能与 $ q(t) $ 相差无几。
   • 如果分布 $ \bar q(t) $ 非常容易采样但是与 $ q(t) $ 很不一样，则马尔科夫链混合的很慢。

3. 所谓马尔科夫链的良好的混合意味着：马尔科夫链能够收敛，且收敛速度不会太长。

   当拒绝率太高时，MCMC 采样很可能长期处于某些值附近（如下图所示的平摊区域），搜索整个参数空间要花非常多的时间。下图中，横轴为迭代次数，纵轴表示采样结果。

   

4. 与 AliasLDA 和 SparseLDA 不同，LightLDA 用两个近似分布 $ \bar q_1(t),\bar q_2(t) $ 来对 $ p(t) $ 进行采样。

   考虑采样概率：

   $ p(t) = \frac{n_z^{\prime}(t)+\alpha_{t}}{n-n_w(v)+\alpha_\mathbb D} \times \frac{n^{\prime}_v (t,v)+\eta}{F(t) +\eta V - n_w(v)} = p_1(t) \times p_2(t)\\ p_1(t) = \frac{n_z^{\prime}(t)+\alpha_{t}}{n-n_w(v)+\alpha_\mathbb D},\quad p_2(t) = \frac{n^{\prime}_v (t,v)+\eta}{F(t) +\eta V - n_w(v)} $

   • 定义 ：

     $ \bar q_1(t) = \frac{n_z(t)+\alpha_{t}}{n+\alpha_\mathbb D} $

     其中 $ n_z(t) $ 为文档内主题 $ t $ 的频次， $ n $ 为文档长度。则接受率为：

     $ \alpha_1( x^{*} )=\min \left(1,\frac{p( x^{*})\bar q_1( x _{i-1} )}{p( x _{i-1})\bar q_1( x^{*} )} \right) $

   • 定义：

     $ \bar q_2(t) = \frac{n_v (t,v)+\eta}{F(t) +\eta V} $

     其中 $ n (t,v) $ 表示数据集 $ \mathbb D $ 中由主题 $ t $ 生成的单词中单词 $ \text{word}_v $ 的次数， $ F(t) $ 表示数据集 $ \mathbb D $ 中由主题 $ t $ 生成的单词总频数。则接受率为：

     $ \alpha_2( x^{*} )=\min \left(1,\frac{p( x^{*})\bar q_2( x _{i-1} )}{p( x _{i-1})\bar q_2( x^{*} )} \right) $

5. 为了提高对 $ \bar q_1 $ 的采样效率，对 $ \bar q_1 $ 进一步拆分：

   $ \bar q_1(t) = \frac{n_z(t)+\alpha_{t}}{n+\alpha_\mathbb D} = \bar q_{1,1}(t)+ \bar q_{1,2}(t)\\ \bar q_{1,1}(t) = \frac{ n_z(t)}{n+\alpha_\mathbb D},\quad \bar q_{1,2}(t) = \frac{ \alpha_{t}}{n+\alpha_\mathbb D}\\ Q_{1,1} = \sum_{t=1}^T \bar q_{1,1}=\frac{n}{n+\alpha_\mathbb D},\quad Q_{1,2} = \sum_{t=1}^T \bar q_{1,2}=\frac{\alpha_\mathbb D}{n+\alpha_\mathbb D} $

   因此采样步骤为：

   • 首先从均匀分布 $ (0 \sim Q_{1,1}+Q_{1,2}) $ 中采样一个点。

   • 如果该点落在 $ (0,Q_{1,1}) $ 之间，则使用 $ \bar q_{1,1}(t) $ 进行采样。此时无需建立 AliasTable，直接从文档中均匀随机选择一个单词，其背后的主题就是采样得到的主题，该分布刚好就是 $ \bar q_{1,1}(t) $ 。

   • 如果该点落在 $ [Q_{1,1},Q_{1,1}+Q_{1,2}) $ 之间，则使用 $ \bar q_{1,2}(t) $ 进行采样。

     • 如果 $ \alpha_1=\alpha_2=\cdots=\alpha $ 为常数，则此时 $ \bar q_{1,2}(t) $ 为均匀分布，无需建立 AliasTable 。
     • 如果 $ \alpha_t $ 并不是全部相等，则由于 $ \bar q_{1,2}(t) $ 与单词、文档都无关，因此可以建立全局 $ \bar q_{1,2}(t) $ AliasTable，它可以跨单词、跨数据块共享，其平均时间、空间复杂度为 $ O(1) $ 。

   因此从 $ \bar q_1 $ 采样的平摊时间、空间复杂度均为 $ O(1) $ 。

6. 为了提高对 $ \bar q_2 $ 的采样效率，采用类似于 AliasLDA 的Alias Table 方式，从而使得对 $ \bar q_2 $ 的采样复杂度为 $ O(1) $ 。

   • 注意：虽然在文档内部， $ \bar q_2(t) $ 在不同位置处不同，是变化的，因此不满足 Alias Table 的要求。但是在同一个数据块中，对于同一个单词 $ v $ ， $ \bar q_2(t) $ 是相同的，是不变的，因此满足 Alias Table 的要求。因此 $ \bar q_2(t) $ 是在同一个数据块内，跨文档共享。

   • 建立 $ \bar q_2(t) $ 的空间复杂度是 $ O(T) $ ，因为它需要存储 $ T $ 个分桶的边界，以及桶内的值。为了降低空间复杂度，可以进一步拆分：

     $ \bar q_2(t) = \frac{n_v (t,v)+\eta}{F(t) +\eta V} = q_{2,1}(t) + q_{2,2}(t)\\ q_{2,1}(t)= \frac{n_v (t,v) }{F(t) +\eta V},\quad q_{2,2}(t) = \frac{\eta}{F(t) +\eta V}\\ Q_{2,1} = \sum_{t=1}^T q_{2,1}(t),\quad Q_{2,2} = \sum_{t=1}^T q_{2,2}(t) $

     其采样步骤为：

     • 首先从均匀分布 $ (0 \sim Q_{2,1}+Q_{2,2}) $ 中采样一个点。
     • 如果该点落在 $ (0,Q_{2,1}) $ 之间，则使用 $ q_{2,1}(t) $ 进行采样。此时只需要考虑单词 $ v $ 涉及的主题即可，空间复杂度为 $ O(T_v) $ 。
     • 如果该点落在 $ [Q_{2,1},Q_{2,1}+Q_{2,2}) $ 之间，则使用 $ q_{2,2}(t) $ 进行采样。它与单词 $ v $ 无关，因此可以在所有单词之间共享，这使得平均的空间复杂度为 $ O(1) $ 。

     因此对 $ \bar q_2 $ 的采样的平摊时间复杂度为 $ O(1) $ ，平摊空间复杂度为 $ O(T_v) $ 。

7. 考虑到 $ p(t) = p_1(t) \times p_2(t) $ ， $ p_1(t) $ 为文档-主题 概率，与 $ \bar q_1(t) $ 比较接近； $ p_2(t) $ 为主题-单词 概率，与 $ \bar q_2(t) $ 比较接近。

   • 如果仅仅用 $ \bar q_1(t) $ 采样，则有可能出现 $ p_1(t) $ 较小、 $ p_2(t) $ 很大的情形。此时 $ p(t) $ 较大，而 $ \bar q_1(t) $ 较小，使得接受率较低，收敛速度较慢。
   • 同理：如果仅仅用 $ \bar q_2(t) $ 采样，则有可能出现 $ p_2(t) $ 较小、 $ p_1(t) $ 很大的情形。此时 $ p(t) $ 较大，而 $ \bar q_2(t) $ 较小，使得接受率较低，收敛速度较慢。

   因此：虽然单独利用 $ \bar q_1(t) $ 或者单独利用 $ \bar q_2(t) $ 都可以对 $ p(t) $ 进行采样，但是单独使用时收敛速度较慢。

8. LightLDA 联合采用 $ \bar q_1(t), \bar q_2(t) $ 来加速采样的收敛速度，它轮流在二者之间采样。这等价于用 $ \bar q_c(t) = \bar q_1(t) \times \bar q_2(t) $ 进行采样，其接受率较大、收敛速度较快。

   • 算法输入：原始函数分布 $ p(t) $ ，文档-主题近似分布 $ \bar q_1(t) $ ，主题-单词近似分布 $ \bar q_2(t) $

   • 算法输出：满足原始分布的采样序列 $ \{x_0,x_1,\cdots,x_{n},x_{n+1},\cdots\} $

   • 算法步骤：

     • 从 $ \bar q_1(t) $ 中随机采样一个样本 $ x_{0} $

     • 对 $ i=1,2,\cdots $ 执行迭代。迭代步骤如下：

       • 根据 $ \bar q_1 (t) $ 采样出候选样本 $ x^{1,*} $ ，计算接受率 $ \alpha(x^{1,*}) $ ：

         $ \alpha( x^{1,*} )=\min \left(1,\frac{p( x^{1,*})\bar q_1( x _{i-1} )}{p( x _{i-1})\bar q_1( x^{1,*} )} \right) $

         根据均匀分布从 $ (0,1) $ 内采样出阈值 $ u $ ，如果 $ u \le \alpha( x^{1,*}) $ ，则接受 $ x^{1,*} $ ， 即 $ x_{i-1}^{tmp}= x^{1,*} $ 。否则拒绝 $ x^{*} $ ， 即 $ x_{i-1}^{tmp}= x_{i-1} $ 。

       • 根据 $ \bar q_2 (t) $ 采样出候选样本 $ x^{2,*} $ ，计算接受率 $ \alpha(x^{2,*}) $ ：

         $ \alpha( x^{2,*} )=\min \left(1,\frac{p( x^{2,*})\bar q_1( x _{i-1}^{tmp} )}{p( x^{tmp} _{i-1})\bar q_1( x^{2,*} )} \right) $

         根据均匀分布从 $ (0,1) $ 内采样出阈值 $ u $ ，如果 $ u \le \alpha( x^{2,*}) $ ，则接受 $ x^{2,*} $ ， 即 $ x_i= x^{2,*} $ 。否则拒绝 $ x^{*} $ ， 即 $ x_i= x_{i-1}^{tmp} $ 。

     • 返回采样序列 $ \{x_0,x_1,\cdots \} $ 。

4.3.3 混合数据结构

1. 对于百万词汇表 x 百万主题，如果每一项（单词-主题计数）是 32 bit，则需要 4 TB内存才能存放。假设一台机器有 128 G内存，则至少需要 32 台参数服务器。因此如果能够大幅降低内存，则对硬件资源的需求也能够下降。

2. 考虑词频统计，在数十亿网页文件中：

   • 在删除停用词之后，几乎所有单词的词频不超过 32 位无符号整数的上限。因此主题-单词 矩阵的元素采用 32 位无符号整数存放。
   • 大多数单词出现的次数少于 $ T $ 次， $ T $ 为主题数量（论文中为一百万）。这意味着主题-单词 矩阵中，大多数单词列是稀疏的，如果采用稀疏表示( 如hash 映射) 将显著减少内存需求。

3. 采用稀疏表示存在一个问题：其随机访问性能很差，这会损害MCMC 采样的速度。为了保持高采样性能、低内存需求，LightLDA 提出了混合数据结构：

   • 对于词频较高的单词，其对应的主题计数列是不做修改的、方便随机访问的 dense 表示。这部分单词占据词表的 10% ，几乎覆盖了语料库中 95% 的位置。
   • 对于词频较低的长尾单词，其对应的主题计数列经过 hash 映射的 sparse 表示，使得内存需求大幅降低。这部分单词占据词表的 90%，仅仅覆盖了语料库中 5% 的位置。

   这就使得：

   • 在MCMC 采样中，对大多数主题-单词 列的访问都是 dense 表示，这使得采样的吞吐量很高。
   • 在存储方面，大多数主题-单词列的存储是sparse 表示，这使得内存需求较低。

4.3.4 系统实现

1. LightLDA 使用开源的分布式机器学习系统 Petuum 来实现，特别使用其参数服务器来进行有界异步数据并行。

2. 参数服务器用于存放 LDA 的两类模型参数：主题-单词 矩阵 $ \mathbf W $ ，主题频次向量 $ \mathbf{\vec w} = (n^v_1,n^v_2,\cdots,n^v_T) $ ，其中 $ n^v_t $ 为主题 $ t $ 生成的单词的总数（它也等于 $ \mathbf W $ 第 $ t $ 行的求和）。

3. 因为语料库的规模远大于模型的大小，所以在网络中交换文档的代价对网络压力非常大。因此LightLDA 并不是交换数据，而是交换模型：先将语料库随机分配到各个worker 的磁盘上，然后在整个算法期间每个 worker 仅仅访问本地磁盘上的部分语料库。

   交换数据的做法是：每轮迭代时，将语料库分发到不同 worker，每个 worker 在不同迭代步处理的数据会有所不同。

4. LightLDA 整体架构如下图所示：

   • 各参数的意义位（这里采用论文中的符号表示）：

     • $ n_d $ ：文档 $ d $ 的长度； $ D_n $ ：数据分片中包含的文档数量。 $ z_{di} $ ：文档 $ d $ 的第 $ i $ 个词汇的主题。
     • $ n_{kv} $ ：语料库中主题 $ k $ 生成的单词 $ v $ 的数量，即 $ W[k,v] $ 。 $ n_k $ ：语料库中主题 $ k $ 的频次，即 $ \mathbf W $ 第 $ t $ 行的求和。 $ n_{k,d} $ ：文档 $ d $ 的主题 $ k $ 的频次。
     • $ \{w_{d_i},z_{d_i}\}_{d=1,i=1}^{D_n,n_d} $ ：数据分片。 $ \{n_{k,v}\}_{k=1,v=1}^{K,V_S} $ ：模型分片。 $ \{n_k\}_{k=1}^K $ ：主题频次向量。

   • 数据分片从 worker 的磁盘加载到 worker 的内存，模型分片由 worker 从参数服务器进行获取。

   • 考虑到每个数据分片可能仍然非常巨大，无法一次性加载进worker 内存。因此 LightLDA 将每个数据分片继续划分成数据块 Data Block ，并将这些数据块依次加载进内存处理。

   

5. 为了加速并行处理，LightLDA 进行了如下优化：

   • 通过流水线来消除IO的延迟：在采样的同时可以加载数据块、拉取下一个模型分片、更新上一个模型分片。

     这需要根据采样器的吞吐量、数据块大小、模型切片大小仔细安排参数。

   • 为防止模型切片之间的数据不均衡（热门词和冷门词），需要对词汇表按照词频进行排序，然后对单词进行混洗来生成模型切片。

   • 在生成数据块时，将文档中的单词按照它们在词表中的顺序进行排序，从而确保同一个模型切片的所有单词在数据块中是连续的。这个操作只需要执行一次，与 LDA 整体消耗时间相比该操作非常快。

   • 使用有界异步数据并行来消除在相邻迭代边界处发生的网络等待时间。

6. LightLDA 在每个 worker 内部开启多线程来进一步加速算法：

   • 每个数据块在内存中被划分为不相交的区域，每个区域由不同的线程进行采样。
   • 所有线程之间共享模型切片，且采样期间模型切片不变。在将模型切片更新到参数服务器之前，对各线程的更新结果进行聚合。

   通过保持模型切片不变，这避免了竞争条件和加锁/解锁等并发问题。虽然这种延迟更新方式需要更多的迭代步才能收敛，但是由于这种方式消除了并发问题，提高了采样器吞吐率，使得每个迭代步的速度快得多，因此整体上仍然可以加速收敛速度。