番外篇：LDA 与 SparseLDA
主题定义
LDA（Latent Dirichlet Allocation，潜在狄利克雷分配）是一种经典的概率主题模型，用来发现文档集合中的潜在主题结构。它假设每篇文档由多个主题混合而成，而每个主题都是词汇表上的一个概率分布。
LDA 的生成过程：
- 主题—词语分布：对每个主题 \(t\)，从狄利克雷先验中采样词语分布 \(\phi_t \sim \operatorname{Dirichlet}(\beta)\)
- 文档分布：对每篇文档 \(m\)，从狄利克雷先验中采样主题分布 \(\theta_m \sim \operatorname{Dirichlet}(\alpha)\)
- 生成词语：对文档中的每个位置 \(n\)
- 根据 \(\theta_m\) 采样主题 \(z_{m,n}\)
- 根据该主题的词语分布 \(\phi_{z_{m,n}}\) 采样词语 \(w_{m,n}\)
这里的 \(\theta_m\) 和 \(\phi_t\) 都是隐变量，不是人工预设的固定分布。训练 LDA 的过程，就是根据观察到的词语反推这些隐变量。
到底主题是什么
实际上，主题就是词汇表上的概率分布。每个主题代表一个语义相关的词语集合。
示例主题：
主题 0（科技）：
P(w|z=0) = {
"手机": 0.12, "苹果": 0.08, "电脑": 0.10,
"软件": 0.07, "网络": 0.09, "数据": 0.06,
"算法": 0.05, "程序": 0.04, "系统": 0.03,
"应用": 0.04, "技术": 0.05, ...
}
主题 1（体育）：
P(w|z=1) = {
"足球": 0.15, "比赛": 0.12, "球员": 0.10,
"进球": 0.08, "教练": 0.07, "联赛": 0.09,
"冠军": 0.06, "球队": 0.11, "场地": 0.04,
"训练": 0.05, "战术": 0.03, ...
}
主题 2（美食）：
P(w|z=2) = {
"苹果": 0.06, "牛肉": 0.09, "餐厅": 0.08,
"味道": 0.10, "烹饪": 0.07, "食材": 0.11,
"美味": 0.09, "菜谱": 0.05, "香甜": 0.04,
"新鲜": 0.06, "营养": 0.05, ...
}
举个生成的例子
假设有这么一个文档，其主题分布为：
P(z|文档) = {主题0: 0.6, 主题1: 0.1, 主题2: 0.3}
过程演示：
假设有这么一个文档：
最新的手机配备了先进的苹果芯片，其内置软件能够高效处理海量数据。
通过智能算法和网络连接，这个程序运行流畅。
今天的比赛很精彩，现场还有美味的苹果和各种食物，味道很棒。
该文档包含的关键词是：["手机", "苹果", "软件", "数据", "算法", "网络", "程序", "比赛", "美味", "味道"]
那么这些关键词的生成过程大概是这样：
- 第0个词：采样主题 → 主题0（科技），采样词语 → “手机”
- 第1个词：采样主题 → 主题0（科技），采样词语 → “苹果”（指苹果公司/芯片）
- 第2个词：采样主题 → 主题0（科技），采样词语 → “软件”
- 第3个词：采样主题 → 主题0（科技），采样词语 → “数据”
- 第4个词：采样主题 → 主题0（科技），采样词语 → “算法”
- 第5个词：采样主题 → 主题0（科技），采样词语 → “网络”
- 第6个词：采样主题 → 主题0（科技），采样词语 → “程序”
- 第7个词：采样主题 → 主题1（体育），采样词语 → “比赛”
- 第8个词：采样主题 → 主题2（美食），采样词语 → “美味”
- 第9个词：采样主题 → 主题2（美食），采样词语 → “味道”
这个例子展示的是词语及其主题的生成关系，而不是一段有顺序的文本。LDA 是词袋模型，只建模词语在文档中的共现，不建模局部词序，因此不能像自回归语言模型一样生成连贯句子。
注意到，“苹果”可以同时出现在多个主题中。LDA 会利用整篇文档中的词语共现，为“苹果”的每一次出现推断一个主题，因此能够在一定程度上反映多义性。不过，LDA 是词袋模型，不使用局部词序，也不能保证完成严格的词义消歧。
关键公式
LDA 模型可以通过 Gibbs 采样来推断每个词语的主题分配。关键的采样公式为：
$$ P(z_{m,n}=t \mid \mathbf{z}{-m,n}, \mathbf{w}) \propto \frac{(\alpha + n{t|m}^{-m,n})(\beta + n_{w|t}^{-m,n})} {\sum_v(\beta + n_{v|t}^{-m,n})} $$
该公式表示：对于文档 m 中第 n 个词语，其主题分配为 t 的概率正比于右侧的表达式。
完整的文档—主题因子还包含分母 \(n_{\cdot|m}^{-m,n}+K\alpha\)。对同一个词语枚举候选主题 \(t\) 时，这个分母保持不变，因此可以在未归一化的 Gibbs 采样权重中省略。词语—主题因子的分母则随 \(t\) 变化，不能省略。
分项解释：
-
第一部分 \((\alpha + n_{t|m}^{-m,n})\)：文档-主题倾向
- 表示去除当前词语后，文档 m 中分配给主题 t 的词语数量
- \(\alpha\) 是平滑参数，避免零概率
-
第二部分 \((\beta + n_{w|t}^{-m,n})\)：词语-主题倾向
- 表示去除当前词语后，全部语料中词语 w 被分配给主题 t 的次数
- \(\beta\) 是平滑参数
-
分母部分 \(\sum_v(\beta + n_{v|t}^{-m,n})\)：归一化项
- 表示主题 t 的总词语数量，用于归一化
直观理解： 假设当前词语是“苹果“，候选主题是“科技“：
- 如果当前文档中已有很多词语被分配给“科技“主题（第一部分）
- 且“苹果“在“科技“主题中出现概率高（第二部分）
- 那么“苹果“被分配给“科技“主题的概率就很高
SparseLDA
标准 LDA 每次采样需要遍历全部主题，时间复杂度为 \(O(K)\)，其中 \(K\) 是主题数。当主题数很大时，这会成为性能瓶颈。SparseLDA 通过将采样概率分解为三个“桶”来减少实际需要遍历的主题。
数学推导
由标准的 LDA 采样公式开始：
$$ P(z_{m,n}=t) \propto \frac{(\alpha+n_{t|m}^{-m,n})(\beta+n_{w|t}^{-m,n})} {\beta V+n_{\cdot|t}^{-m,n}} $$
对记号简化，定义：
- \(n_{t|m}\) ：文档 m 中分配给主题 t 的词数
- \(n_{w|t}\) ：词语 w 被分配给主题 t 的次数
- \(n_{·|t}\) ：主题 t 的总词数
第一步：展开分子
把分子展开： $$ (\alpha+n_{t|m})(\beta+n_{w|t}) = \alpha\beta + \alpha n_{w|t} + n_{t|m}\beta + n_{t|m}n_{w|t} $$
第二步：组织成三个部分
把展开式重新组织： $$ \frac{\alpha\beta + \alpha n_{w|t} + n_{t|m}\beta + n_{t|m}n_{w|t}} {\beta V + n_{\cdot|t}} $$
$$ \frac{\alpha\beta}{\beta V + n_{\cdot|t}} {}+ \frac{n_{t|m}\beta}{\beta V + n_{\cdot|t}} {}+ \left( \frac{\alpha n_{w|t}}{\beta V + n_{\cdot|t}} {}+ \frac{n_{t|m}n_{w|t}}{\beta V + n_{\cdot|t}} \right) $$
第三步：得到三个桶
桶 s （平滑项）： $$ s_t = \frac{\alpha\beta}{\beta V + n_{\cdot|t}} $$
桶 r （文档项）： $$ r_t = \frac{n_{t|m}\beta}{\beta V + n_{\cdot|t}} $$
桶 q （词语项）： $$ q_t = \frac{\alpha n_{w|t}}{\beta V + n_{\cdot|t}} {}+ \frac{n_{t|m}n_{w|t}}{\beta V + n_{\cdot|t}} = \frac{(\alpha + n_{t|m})n_{w|t}}{\beta V + n_{\cdot|t}} $$
平滑桶 \(s\) 仍然包含全部 \(K\) 个主题；文档桶 \(r\) 只包含当前文档中出现过的主题；词语桶 \(q\) 只包含当前词语被分配过的主题。后两个集合通常远小于 \(K\)。平滑桶的总质量可以维护起来，并且采样通常只需遍历实际落入的那个桶，因此平均开销会明显低于每次完整遍历全部主题。
具体算法
采样步骤：
-
计算桶的总质量： $$ S = \sum_t s_t {}+ \sum_{t:n_{t|m}>0} r_t {}+ \sum_{t:n_{w|t}>0} q_t $$
-
按比例选择桶：
- 随机数生成 \(u \sim \text{Uniform}(0,S)\)
- 若 \(u < S_s\), 选择桶 s
- 若 \(S_s \leq u < S_s + S_r\)，选择桶 r
- 否则选择桶 q
-
桶内采样：
- 根据选中的桶，对应的候选主题中概率采样
平滑桶的总质量
\(S_s=\sum_t s_t=\sum_t\frac{\alpha\beta}{\beta V+n_{\cdot|t}}\)
需要缓存，否则每个词语都重新求和仍要遍历全部主题。理论上，每次主题移动只改变旧、新两个主题的总计数，可以用 \(O(1)\) 增量精确更新；Semat 当前实现选择在每轮迭代开始时通过 UpdateCache 重新计算一次，轮内使用该缓存值，因此这里采用的是近似更新。
多线程
仅仅降低单次采样的时间复杂度还不够，还可以进一步利用多线程。观察 SparseLDA 的采样公式可以发现：合理划分文档和词汇块，能够消除大部分文档—主题计数与词语—主题计数的写冲突，但全局主题计数仍然需要单独处理。
回顾下采样公式： \(P(z_{m,n}=t) \propto \frac{(\alpha+n_{t|m})(\beta+n_{w|t})}{\beta V + n_{·|t}}\)
计数依赖分析：
- 更新文档 m 中词语 w的主题时，会影响：
- \(n_{t|m}\) : 文档m的主题计数
- \(n_{w|t}\) : 词语w的主题计数
- \(n_{·|t}\) : 主题的总计数
竞争条件问题： 若多个线程同时操作，会造成这些数据出现不一致：
- 同一文档的不同词语：会竞争修改 \(n_{*|m}\)
- 不同文档的相同词语：会竞争修改 \(n_{w|*}\)
- 任意词语：都会竞争修改 \(n_{·|*}\) (这个竞争无法避免)
一种直接做法是为共享计数加锁，但锁竞争可能抵消并行带来的收益。
N-Queen 方案 类似于 N 皇后问题中皇后之间不能相互攻击的约束，让不同线程操作的文档块和词汇块互不相交，可以避免这两类局部计数之间的竞争。
核心思想：
- 把文档和词汇表都分块
- 不同线程负责不同的文档-词汇块组合
- 通过巧妙的调度避免竞争
局部计数无冲突条件： 线程 i 处理文档块 \(D_i\) 和词汇块 \(V_i\)，线程 j 处理文档块 \(D_j\) 和词汇块 \(V_j\)。满足以下条件时，文档—主题计数和词语—主题计数不会发生写冲突：
- \(D_i \cap D_j = \varnothing\)（文档块不相交）
- \(V_i \cap V_j = \varnothing\)（词汇块不相交）
这并不意味着整个算法已经完全无锁。Semat 的分块保证同一轮中的线程不会同时修改同一文档的 nm[m]，也不会同时修改同一词语的 nv[w]；但所有线程仍会修改共享的 nvsum[t]。当前代码没有为这些读写使用原子操作或锁，在 C++ 内存模型中属于数据竞争，而不仅是统计意义上的“陈旧计数”。若要得到定义明确的并行实现，应将 nvsum 改为原子计数，或者累计线程局部增量并在每轮调度后合并。
分块策略示例（4线程，8文档，8词汇）：
第1轮：
词0-1 词2-3 词4-5 词6-7
文档0-1 [T0] × × ×
文档2-3 × [T1] × ×
文档4-5 × × [T2] ×
文档6-7 × × × [T3]
第2轮（列循环右移）：
词0-1 词2-3 词4-5 词6-7
文档0-1 × × × [T0]
文档2-3 [T1] × × ×
文档4-5 × [T2] × ×
文档6-7 × × [T3] ×
第3轮（继续右移）：
词0-1 词2-3 词4-5 词6-7
文档0-1 × × [T0] ×
文档2-3 × × × [T1]
文档4-5 [T2] × × ×
文档6-7 × [T3] × ×
第4轮（完成覆盖）：
词0-1 词2-3 词4-5 词6-7
文档0-1 × [T0] × ×
文档2-3 × × [T1] ×
文档4-5 × × × [T2]
文档6-7 [T3] × × ×
Perplexity
困惑度（Perplexity）用于衡量模型对未见文档的预测能力。标准评估应在留出的验证集或测试集上进行，而不是直接复用训练语料及其当前主题分配。
基本思想： LDA假设每个词语的生成分为两步：
- 根据文档的主题分布选择一个主题 t
- 根据主题 t 的词语分布选择一个词语 w
主题是隐变量，因此计算词语的边缘概率时，不能只使用当前分配到的一个主题，而要对全部主题求和。对于文档 \(m\) 中位置 \(i\) 的词语：
$$ P(w_{m,i}\mid m) = \sum_{t=1}^{K}P(t\mid m)P(w_{m,i}\mid t) $$
其中：
- \(P(t|m) = \frac{n_{t|m}+\alpha}{n_m + K\alpha}\) : 文档 m 中主题 t 的概率
- \(P(w|t) = \frac{n_{w|t}+\beta}{n_t + V\beta}\) : 主题 t 中词语 w 的概率
对数似然函数：
$$ \log P(\text{全部词语}) = \sum_{m=1}^{M}\sum_{i=1}^{N_m} \log\left( \sum_{t=1}^{K}P(t\mid m)P(w_{m,i}\mid t) \right) $$
困惑度（Perplexity） 定义：
$$ \text{Perplexity} = \exp\left( {}-\frac{\log P(\text{全部词语})}{\text{总词数}} \right) $$
其中总词数为测试集中所有文档的词语数量。困惑度可以直观理解为模型在每个位置面对的平均有效候选数；在相同数据集和评估方法下，数值越低，表示模型的预测能力越好。实际评估时，还需要为测试文档推断文档—主题分布，并避免使用待评估词语本身的信息。
训练过程中的近似指标
标准困惑度需要在测试文档上推断主题分布，并对全部主题求和，计算成本较高。训练过程中为了快速观察模型变化，也可以利用每个词语当前的主题分配，计算一个近似得分：
$$ \log P(z_{m,i}\mid m)+\log P(w_{m,i}\mid z_{m,i}) $$
将所有词语的得分相加，再按词数取负平均并求指数，就能得到一个随训练过程变化的指标。它利用的是训练语料及其当前主题分配，适合观察同一次训练是否趋于稳定；但它没有对隐含主题进行边缘化，也没有评估未见文档，因此不能代替前面定义的标准困惑度。
配套实现：Ismantic/Semat