期望最大化（EM）算法在多项式分布混合模型（Mixture of Multinomials）中的参数估计过程

字数 4838 2025-12-07 00:38:49

期望最大化（EM）算法在多项式分布混合模型（Mixture of Multinomials）中的参数估计过程

题目描述

假设我们有一组文档，每个文档由词袋（bag-of-words）表示，即每个文档表示为一个词频向量。我们假设这些文档来自K个不同的主题（主题即为多项式分布）。每个主题k对应一个多项式分布，参数为\(\phi_k\)，表示在给定该主题时每个词出现的概率。同时，每个文档d属于某个主题的概率由混合权重\(\pi_k\)决定。给定观测到的文档词频数据，目标是使用期望最大化（EM）算法估计所有主题的多项式分布参数\(\phi_k\)以及混合权重\(\pi_k\)。这是一个多项式分布混合模型（Mixture of Multinomials）的参数估计问题。

解题过程

1. 模型建立

假设有K个主题，每个主题k对应一个多项式分布，其参数为\(\phi_k = [\phi_{k1}, \phi_{k2}, ..., \phi_{kV}]\)，其中V是词汇表大小，\(\phi_{kv}\)表示在主题k下生成词v的概率，满足\(\sum_{v=1}^V \phi_{kv} = 1\)。
混合权重\(\pi = [\pi_1, \pi_2, ..., \pi_K]\)，满足\(\sum_{k=1}^K \pi_k = 1\)，表示随机选择一个文档时，其主题为k的先验概率。
对于文档d（d=1,...,D），其观测数据为词频向量\(x_d = [x_{d1}, x_{d2}, ..., x_{dV}]\)，其中\(x_{dv}\)表示词v在文档d中出现的次数，文档总词数为\(N_d = \sum_{v} x_{dv}\)。
隐变量为文档d的主题标签\(z_d \in \{1,2,...,K\}\)，表示文档d的真实主题。

生成过程：

为文档d采样主题：\(z_d \sim \text{Categorical}(\pi)\)。
在给定主题\(z_d = k\)下，文档d的词频向量服从多项式分布：\(x_d | z_d = k \sim \text{Multinomial}(N_d, \phi_k)\)。

2. 完全数据似然

若隐变量\(z_d\)已知，则完全数据（观测数据+隐变量）的似然为：

\[p(X, Z | \pi, \Phi) = \prod_{d=1}^D p(z_d | \pi) p(x_d | z_d, \Phi) = \prod_{d=1}^D \pi_{z_d} \cdot \prod_{v=1}^V \phi_{z_d, v}^{x_{dv}} \]

其中，\(\Phi = \{\phi_1, ..., \phi_K\}\)。取对数得完全数据对数似然：

\[\log p(X, Z | \pi, \Phi) = \sum_{d=1}^D \left[ \log \pi_{z_d} + \sum_{v=1}^V x_{dv} \log \phi_{z_d, v} \right] \]

3. E步：计算隐变量的后验分布

在E步，我们基于当前参数估计（\(\pi^{(t)}, \Phi^{(t)}\)）计算隐变量\(z_d\)的后验概率：

\[\gamma_{dk}^{(t)} = p(z_d = k | x_d, \pi^{(t)}, \Phi^{(t)}) = \frac{\pi_k^{(t)} \cdot p(x_d | z_d=k, \phi_k^{(t)})}{\sum_{j=1}^K \pi_j^{(t)} \cdot p(x_d | z_d=j, \phi_j^{(t)})} \]

其中，\(p(x_d | z_d=k, \phi_k^{(t)}) = \frac{N_d!}{\prod_v x_{dv}!} \prod_{v=1}^V (\phi_{kv}^{(t)})^{x_{dv}}\)，但常数项在计算\(\gamma_{dk}\)时会约去，因此实际计算时使用：

\[p(x_d | z_d=k, \phi_k^{(t)}) \propto \prod_{v=1}^V (\phi_{kv}^{(t)})^{x_{dv}} \]

代入得：

\[\gamma_{dk}^{(t)} = \frac{\pi_k^{(t)} \prod_{v=1}^V (\phi_{kv}^{(t)})^{x_{dv}}}{\sum_{j=1}^K \pi_j^{(t)} \prod_{v=1}^V (\phi_{jv}^{(t)})^{x_{dv}}} \]

\(\gamma_{dk}^{(t)}\)表示文档d属于主题k的“责任”（responsibility），满足\(\sum_{k=1}^K \gamma_{dk}^{(t)} = 1\)。

4. M步：最大化期望完全数据对数似然

M步中，我们最大化期望完全数据对数似然：

\[Q(\pi, \Phi) = \mathbb{E}_{Z|X, \pi^{(t)}, \Phi^{(t)}} [\log p(X, Z | \pi, \Phi)] = \sum_{d=1}^D \sum_{k=1}^K \gamma_{dk}^{(t)} \left[ \log \pi_k + \sum_{v=1}^V x_{dv} \log \phi_{kv} \right] \]

需在约束\(\sum_k \pi_k = 1\)和\(\sum_v \phi_{kv} = 1\)下最大化\(Q\)。

更新混合权重\(\pi_k\)：
引入拉格朗日乘子\(\lambda\)，构造拉格朗日函数：

\[ L_\pi = \sum_{d=1}^D \sum_{k=1}^K \gamma_{dk}^{(t)} \log \pi_k + \lambda \left( \sum_{k=1}^K \pi_k - 1 \right) \]

对\(\pi_k\)求导并令导数为0：

\[ \frac{\partial L_\pi}{\partial \pi_k} = \frac{\sum_{d=1}^D \gamma_{dk}^{(t)}}{\pi_k} + \lambda = 0 \quad \Rightarrow \quad \pi_k = -\frac{\sum_{d=1}^D \gamma_{dk}^{(t)}}{\lambda} \]

利用约束\(\sum_k \pi_k = 1\)，可得\(\lambda = -\sum_{d=1}^D \sum_{k=1}^K \gamma_{dk}^{(t)} = -D\)，因为\(\sum_k \gamma_{dk}^{(t)} = 1\)，所以\(\sum_{d,k} \gamma_{dk}^{(t)} = D\)。因此：

\[ \pi_k^{(t+1)} = \frac{\sum_{d=1}^D \gamma_{dk}^{(t)}}{D} \]

即\(\pi_k\)更新为所有文档属于主题k的平均责任。

更新主题参数\(\phi_{kv}\)：
对每个主题k，我们需要最大化\(Q\)中与\(\phi_k\)相关的部分：

\[ \sum_{d=1}^D \gamma_{dk}^{(t)} \sum_{v=1}^V x_{dv} \log \phi_{kv} = \sum_{v=1}^V \left( \sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv} \right) \log \phi_{kv} \]

引入拉格朗日乘子\(\lambda_k\)，构造拉格朗日函数：

\[ L_{\phi_k} = \sum_{v=1}^V \left( \sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv} \right) \log \phi_{kv} + \lambda_k \left( \sum_{v=1}^V \phi_{kv} - 1 \right) \]

对\(\phi_{kv}\)求导并令导数为0：

\[ \frac{\partial L_{\phi_k}}{\partial \phi_{kv}} = \frac{\sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv}}{\phi_{kv}} + \lambda_k = 0 \quad \Rightarrow \quad \phi_{kv} = -\frac{\sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv}}{\lambda_k} \]

利用约束\(\sum_v \phi_{kv} = 1\)，可得：

\[ \sum_{v=1}^V \phi_{kv} = -\frac{\sum_{v=1}^V \sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv}}{\lambda_k} = 1 \quad \Rightarrow \quad \lambda_k = -\sum_{v=1}^V \sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv} \]

注意\(\sum_v x_{dv} = N_d\)，因此：

\[ \sum_{v=1}^V \sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv} = \sum_{d=1}^D \gamma_{dk}^{(t)} N_d \]

所以更新公式为：

\[ \phi_{kv}^{(t+1)} = \frac{\sum_{d=1}^D \gamma_{dk}^{(t)} x_{dv}}{\sum_{d=1}^D \gamma_{dk}^{(t)} N_d} \]

直观解释：\(\phi_{kv}\)更新为所有文档中词v的出现次数加权和（权重为文档属于主题k的责任），除以所有文档的总词数加权和。

5. EM算法迭代

初始化：随机或启发式初始化参数\(\pi^{(0)}\)和\(\Phi^{(0)}\)，确保满足概率约束。
E步：基于当前参数计算责任\(\gamma_{dk}^{(t)}\)。
M步：使用上面推导的公式更新\(\pi^{(t+1)}\)和\(\Phi^{(t+1)}\)。
检查收敛：计算对数似然\(\log p(X | \pi, \Phi) = \sum_{d=1}^D \log \sum_{k=1}^K \pi_k p(x_d | \phi_k)\)，若变化小于阈值则停止，否则返回E步。

6. 算法输出

参数估计：混合权重\(\pi_k\)、每个主题的多项式分布参数\(\phi_k\)。
文档主题软分配：责任\(\gamma_{dk}\)可作为文档d属于主题k的概率。

小结

EM算法用于多项式分布混合模型的参数估计，通过迭代E步（计算文档的主题责任）和M步（最大化期望完全数据似然更新参数），最终得到主题分布和文档-主题关联。此模型是文本聚类和主题建模的基础模型，但其假设每个文档仅来自一个主题（混合模型），不同于LDA（每个文档是多个主题的混合）。

期望最大化（EM）算法在多项式分布混合模型（Mixture of Multinomials）中的参数估计过程题目描述假设我们有一组文档，每个文档由词袋（bag-of-words）表示，即每个文档表示为一个词频向量。我们假设这些文档来自K个不同的主题（主题即为多项式分布）。每个主题k对应一个多项式分布，参数为\(\phi_ k\)，表示在给定该主题时每个词出现的概率。同时，每个文档d属于某个主题的概率由混合权重\(\pi_ k\)决定。给定观测到的文档词频数据，目标是使用期望最大化（EM）算法估计所有主题的多项式分布参数\(\phi_ k\)以及混合权重\(\pi_ k\)。这是一个多项式分布混合模型（Mixture of Multinomials）的参数估计问题。解题过程 1. 模型建立假设有K个主题，每个主题k对应一个多项式分布，其参数为\(\phi_ k = [ \phi_ {k1}, \phi_ {k2}, ..., \phi_ {kV}]\)，其中V是词汇表大小，\(\phi_ {kv}\)表示在主题k下生成词v的概率，满足\(\sum_ {v=1}^V \phi_ {kv} = 1\)。混合权重\(\pi = [ \pi_ 1, \pi_ 2, ..., \pi_ K]\)，满足\(\sum_ {k=1}^K \pi_ k = 1\)，表示随机选择一个文档时，其主题为k的先验概率。对于文档d（d=1,...,D），其观测数据为词频向量\(x_ d = [ x_ {d1}, x_ {d2}, ..., x_ {dV}]\)，其中\(x_ {dv}\)表示词v在文档d中出现的次数，文档总词数为\(N_ d = \sum_ {v} x_ {dv}\)。隐变量为文档d的主题标签\(z_ d \in \{1,2,...,K\}\)，表示文档d的真实主题。生成过程：为文档d采样主题：\(z_ d \sim \text{Categorical}(\pi)\)。在给定主题\(z_ d = k\)下，文档d的词频向量服从多项式分布：\(x_ d | z_ d = k \sim \text{Multinomial}(N_ d, \phi_ k)\)。 2. 完全数据似然若隐变量\(z_ d\)已知，则完全数据（观测数据+隐变量）的似然为： \[ p(X, Z | \pi, \Phi) = \prod_ {d=1}^D p(z_ d | \pi) p(x_ d | z_ d, \Phi) = \prod_ {d=1}^D \pi_ {z_ d} \cdot \prod_ {v=1}^V \phi_ {z_ d, v}^{x_ {dv}} \] 其中，\(\Phi = \{\phi_ 1, ..., \phi_ K\}\)。取对数得完全数据对数似然： \[ \log p(X, Z | \pi, \Phi) = \sum_ {d=1}^D \left[ \log \pi_ {z_ d} + \sum_ {v=1}^V x_ {dv} \log \phi_ {z_ d, v} \right ] \] 3. E步：计算隐变量的后验分布在E步，我们基于当前参数估计（\(\pi^{(t)}, \Phi^{(t)}\)）计算隐变量\(z_ d\)的后验概率： \[ \gamma_ {dk}^{(t)} = p(z_ d = k | x_ d, \pi^{(t)}, \Phi^{(t)}) = \frac{\pi_ k^{(t)} \cdot p(x_ d | z_ d=k, \phi_ k^{(t)})}{\sum_ {j=1}^K \pi_ j^{(t)} \cdot p(x_ d | z_ d=j, \phi_ j^{(t)})} \] 其中，\(p(x_ d | z_ d=k, \phi_ k^{(t)}) = \frac{N_ d!}{\prod_ v x_ {dv}!} \prod_ {v=1}^V (\phi_ {kv}^{(t)})^{x_ {dv}}\)，但常数项在计算\(\gamma_ {dk}\)时会约去，因此实际计算时使用： \[ p(x_ d | z_ d=k, \phi_ k^{(t)}) \propto \prod_ {v=1}^V (\phi_ {kv}^{(t)})^{x_ {dv}} \] 代入得： \[ \gamma_ {dk}^{(t)} = \frac{\pi_ k^{(t)} \prod_ {v=1}^V (\phi_ {kv}^{(t)})^{x_ {dv}}}{\sum_ {j=1}^K \pi_ j^{(t)} \prod_ {v=1}^V (\phi_ {jv}^{(t)})^{x_ {dv}}} \] \(\gamma_ {dk}^{(t)}\)表示文档d属于主题k的“责任”（responsibility），满足\(\sum_ {k=1}^K \gamma_ {dk}^{(t)} = 1\)。 4. M步：最大化期望完全数据对数似然 M步中，我们最大化期望完全数据对数似然： \[ Q(\pi, \Phi) = \mathbb{E} {Z|X, \pi^{(t)}, \Phi^{(t)}} [ \log p(X, Z | \pi, \Phi)] = \sum {d=1}^D \sum_ {k=1}^K \gamma_ {dk}^{(t)} \left[ \log \pi_ k + \sum_ {v=1}^V x_ {dv} \log \phi_ {kv} \right ] \] 需在约束\(\sum_ k \pi_ k = 1\)和\(\sum_ v \phi_ {kv} = 1\)下最大化\(Q\)。更新混合权重\(\pi_ k\) ：引入拉格朗日乘子\(\lambda\)，构造拉格朗日函数： \[ L_ \pi = \sum_ {d=1}^D \sum_ {k=1}^K \gamma_ {dk}^{(t)} \log \pi_ k + \lambda \left( \sum_ {k=1}^K \pi_ k - 1 \right) \] 对\(\pi_ k\)求导并令导数为0： \[ \frac{\partial L_ \pi}{\partial \pi_ k} = \frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)}}{\pi_ k} + \lambda = 0 \quad \Rightarrow \quad \pi_ k = -\frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)}}{\lambda} \] 利用约束\(\sum_ k \pi_ k = 1\)，可得\(\lambda = -\sum_ {d=1}^D \sum_ {k=1}^K \gamma_ {dk}^{(t)} = -D\)，因为\(\sum_ k \gamma_ {dk}^{(t)} = 1\)，所以\(\sum_ {d,k} \gamma_ {dk}^{(t)} = D\)。因此： \[ \pi_ k^{(t+1)} = \frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)}}{D} \] 即\(\pi_ k\)更新为所有文档属于主题k的平均责任。更新主题参数\(\phi_ {kv}\) ：对每个主题k，我们需要最大化\(Q\)中与\(\phi_ k\)相关的部分： \[ \sum_ {d=1}^D \gamma_ {dk}^{(t)} \sum_ {v=1}^V x_ {dv} \log \phi_ {kv} = \sum_ {v=1}^V \left( \sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv} \right) \log \phi_ {kv} \] 引入拉格朗日乘子\(\lambda_ k\)，构造拉格朗日函数： \[ L_ {\phi_ k} = \sum_ {v=1}^V \left( \sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv} \right) \log \phi_ {kv} + \lambda_ k \left( \sum_ {v=1}^V \phi_ {kv} - 1 \right) \] 对\(\phi_ {kv}\)求导并令导数为0： \[ \frac{\partial L_ {\phi_ k}}{\partial \phi_ {kv}} = \frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv}}{\phi_ {kv}} + \lambda_ k = 0 \quad \Rightarrow \quad \phi_ {kv} = -\frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv}}{\lambda_ k} \] 利用约束\(\sum_ v \phi_ {kv} = 1\)，可得： \[ \sum_ {v=1}^V \phi_ {kv} = -\frac{\sum_ {v=1}^V \sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv}}{\lambda_ k} = 1 \quad \Rightarrow \quad \lambda_ k = -\sum_ {v=1}^V \sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv} \] 注意\(\sum_ v x_ {dv} = N_ d\)，因此： \[ \sum_ {v=1}^V \sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv} = \sum_ {d=1}^D \gamma_ {dk}^{(t)} N_ d \] 所以更新公式为： \[ \phi_ {kv}^{(t+1)} = \frac{\sum_ {d=1}^D \gamma_ {dk}^{(t)} x_ {dv}}{\sum_ {d=1}^D \gamma_ {dk}^{(t)} N_ d} \] 直观解释：\(\phi_ {kv}\)更新为所有文档中词v的出现次数加权和（权重为文档属于主题k的责任），除以所有文档的总词数加权和。 5. EM算法迭代初始化：随机或启发式初始化参数\(\pi^{(0)}\)和\(\Phi^{(0)}\)，确保满足概率约束。 E步：基于当前参数计算责任\(\gamma_ {dk}^{(t)}\)。 M步：使用上面推导的公式更新\(\pi^{(t+1)}\)和\(\Phi^{(t+1)}\)。检查收敛：计算对数似然\(\log p(X | \pi, \Phi) = \sum_ {d=1}^D \log \sum_ {k=1}^K \pi_ k p(x_ d | \phi_ k)\)，若变化小于阈值则停止，否则返回E步。 6. 算法输出参数估计：混合权重\(\pi_ k\)、每个主题的多项式分布参数\(\phi_ k\)。文档主题软分配：责任\(\gamma_ {dk}\)可作为文档d属于主题k的概率。小结 EM算法用于多项式分布混合模型的参数估计，通过迭代E步（计算文档的主题责任）和M步（最大化期望完全数据似然更新参数），最终得到主题分布和文档-主题关联。此模型是文本聚类和主题建模的基础模型，但其假设每个文档仅来自一个主题（混合模型），不同于LDA（每个文档是多个主题的混合）。