期望最大化（EM）算法在混合多项式模型（Mixture of Multinomials）中的参数估计过程
字数 4393 2025-12-12 11:54:00

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

我们先从一个实际问题开始。假设您有一大堆短文本（比如推文标题），每个标题由一些词组成。您想把这些文本自动分成K个主题（例如体育、科技、娱乐），但您不知道每条文本属于哪个主题，也不知道每个主题下词汇的分布规律。混合多项式模型非常适合用在这种“离散特征”数据的聚类场景，而EM算法可以帮助我们在“主题未知”的情况下，估计出模型参数。下面，我将为您一步步拆解。

第一步：理解问题与模型设定

  1. 场景：我们有N个观测到的文本（样本），每个文本表示为一个“词袋”，即忽略词序，只关心每个词出现的次数。假设整个词典一共有V个不同的词。
  2. 目标：我们假设这些文本来自K个不同的“主题”（或“类别”）。我们的目标是：
    • 软聚类：为每个文本i，计算它属于每个主题k的概率。
    • 模型参数：估计出每个主题k下，各个词v出现的概率分布。
  3. 模型：混合多项式模型
    • 混合系数（Mix Proportion）：π = [π₁, π₂, …, π_K]，π_k 表示一个随机文本属于主题k的先验概率。满足 π_k > 0 且 ∑_{k=1}^K π_k = 1。
    • 每个主题的词分布：对于主题k，有一个多项式分布参数向量 φ_k = [φ_{k1}, φ_{k2}, …, φ_{kV}]。φ_{kv} 表示在主题k下，出现词v的概率。满足 φ_{kv} > 0 且 ∑_{v=1}^V φ_{kv} = 1。
    • 隐变量（Latent Variable）：对于第i个文本，其真实的主题标签 z_i 是我们观察不到的。z_i 是一个K维的one-hot向量，例如，如果它属于主题2，则 z_i = (0, 1, 0, …, 0)。
    • 观测数据：第i个文本，我们观察到的是一个V维的计数向量 x_i = [n_{i1}, n_{i2}, …, n_{iV}]，其中 n_{iv} 是词v在该文本中出现的次数。记该文本的总词数为 L_i = ∑_v n_{iv}。

第二步：建立完整数据似然函数与Q函数

EM算法的核心是处理缺失数据（这里是隐变量z）。我们先写出“如果隐变量z也能被观测到”时的完整数据似然函数。

  1. 单个样本 (x_i, z_i) 的概率：

    • 首先，这个样本的主题 z_i 来自一个类别分布：P(z_i) = ∏_{k=1}^K (π_k)^{z_{ik}}。z_{ik}=1 时表示选中k。
    • 然后，给定主题k，观测到文本计数向量 x_i 的概率是一个多项式分布：P(x_i | z_{ik}=1) = (L_i)! / (∏_{v=1}^V n_{iv}!) * ∏_{v=1}^V (φ_{kv})^{n_{iv}}。（组合数项与参数φ无关，在优化中可视为常数）。
    • 因此，完整数据的联合概率为：
      P(x_i, z_i) = P(z_i) * P(x_i | z_i) = [∏_{k=1}^K (π_k)^{z_{ik}}] * [∏_{k=1}^K (∏_{v=1}^V (φ_{kv})^{n_{iv}})^{z_{ik}}]。

  2. 所有样本的完整数据对数似然函数（对数和，忽略与参数无关的常数项）：
    log P(X, Z) = ∑_{i=1}^N ∑_{k=1}^K z_{ik} [ log π_k + ∑_{v=1}^V n_{iv} log φ_{kv} ]。

  3. 构建Q函数：在E步，我们需要计算完整数据对数似然函数关于隐变量后验分布 P(Z|X, θ⁰) 的期望，其中θ⁰是当前参数的估计值（π⁰, φ⁰）。这个期望就是Q函数。

    • Q(θ, θ⁰) = E_{Z|X, θ⁰} [ log P(X, Z | θ) ]。
    • 代入上面的对数似然，期望只作用在 z_{ik} 上。因此，关键是计算隐变量的后验期望 E[z_{ik} | x_i, θ⁰]。
    • E[z_{ik} | x_i, θ⁰] = P(z_{ik}=1 | x_i, θ⁰)。根据贝叶斯定理：
      γ_{ik} ≜ P(z_{ik}=1 | x_i, θ⁰) = [ π_k⁰ * P(x_i | φ_k⁰) ] / [ ∑_{j=1}^K π_j⁰ * P(x_i | φ_j⁰) ]。
      其中，P(x_i | φ_k⁰) = ∏_{v=1}^V (φ_{kv}⁰)^{n_{iv}}（忽略多项式系数）。
    • γ_{ik} 有一个非常直观的意义：在现有参数下，第i个文本属于主题k的“责任”或“响应度”（responsibility）。它是一个介于0和1之间的软分配值。
    • 于是，Q函数可以明确写出：
      Q(θ, θ⁰) = ∑_{i=1}^N ∑_{k=1}^K γ_{ik} [ log π_k + ∑_{v=1}^V n_{iv} log φ_{kv} ]。

第三步：M步 - 最大化Q函数以更新参数

在M步，我们要找到一组新的参数θ = (π, φ) 来最大化Q函数，同时满足各自的概率和为1的约束。这需要用拉格朗日乘子法。

  1. 更新混合系数 π_k：

    • 需要最大化 ∑_{i=1}^N ∑_{k=1}^K γ_{ik} log π_k，约束是 ∑_k π_k = 1。
    • 构建拉格朗日函数：L_π = ∑_i ∑_k γ_{ik} log π_k + λ (∑_k π_k - 1)。
    • 对 π_k 求导并令为0：∂L_π/∂π_k = (1/π_k) ∑_i γ_{ik} + λ = 0 => ∑_i γ_{ik} = -λ π_k。
    • 对k求和：∑_k ∑_i γ_{ik} = -λ ∑_k π_k。注意到 ∑_k γ_{ik} = 1（对于一个文本i，属于所有主题的概率和为1），所以左边等于N。右边 ∑_k π_k = 1，所以 N = -λ，即 λ = -N。
    • 代回：∑_i γ_{ik} = N π_k。因此，更新公式为：
      π_k^{(new)} = (1/N) ∑_{i=1}^N γ_{ik}。
    • 直观解释：新的主题k的先验概率，等于所有文本被赋予主题k的“责任”的平均值。

  2. 更新主题词分布参数 φ_{kv}：

    • 需要最大化 ∑_{i=1}^N ∑_{k=1}^K γ_{ik} ∑_{v=1}^V n_{iv} log φ_{kv}，对每个k，约束是 ∑_v φ_{kv} = 1。
    • 对每个主题k分别构建拉格朗日函数：L_{φ_k} = ∑_i γ_{ik} ∑_v n_{iv} log φ_{kv} + μ_k (∑_v φ_{kv} - 1)。
    • 对 φ_{kv} 求导并令为0：∂L_{φ_k}/∂φ_{kv} = (1/φ_{kv}) ∑_i γ_{ik} n_{iv} + μ_k = 0。
    • 所以 φ_{kv} ∝ ∑_i γ_{ik} n_{iv}。
    • 利用约束 ∑_v φ_{kv} = 1 进行归一化，得到更新公式：
      φ_{kv}^{(new)} = [∑_{i=1}^N γ_{ik} n_{iv}] / [∑_{i=1}^N γ_{ik} ∑_{u=1}^V n_{iu}]。
    • 注意分母中 ∑_u n_{iu} = L_i 是第i个文本的总词数。所以公式可以写为：
      φ_{kv}^{(new)} = [∑_{i=1}^N γ_{ik} n_{iv}] / [∑_{i=1}^N γ_{ik} L_i]。
    • 直观解释：
      • 分子：在整个语料库中，所有文本里词v出现的次数，按照文本属于主题k的“责任”γ_{ik} 进行加权求和。可以理解为估计出的、属于主题k的所有文本中，词v出现的总期望次数。
      • 分母：所有文本的总词数，按照文本属于主题k的“责任”γ_{ik} 进行加权求和。可以理解为估计出的、属于主题k的所有文本的总期望词数。
      • 因此，φ_{kv} 就是词v在主题k中的期望相对频率。

第四步：整合EM算法步骤与收敛

  1. 初始化：随机或启发式地初始化参数 π^0 和 φ^0。确保它们满足概率分布的性质（和为1，元素为正）。
  2. E步（期望步）：使用当前参数 π^{old}, φ^{old}，对每个样本i和每个主题k，计算责任 γ_{ik}。
    γ_{ik} = [ π_k^{old} * ∏_{v=1}^V (φ_{kv}^{old})^{n_{iv}} ] / [ ∑_{j=1}^K π_j^{old} * ∏_{v=1}^V (φ_{jv}^{old})^{n_{iv}} ]。
    在实际计算中，通常先计算对数概率避免数值下溢：log P(x_i|φ_k) = ∑_v n_{iv} log φ_{kv}，然后通过指数归一化（softmax）计算 γ_{ik}。
  3. M步（最大化步）：使用计算出的 γ_{ik} 作为固定权重，更新参数。
    • 更新混合系数：π_k^{new} = (1/N) ∑_i γ_{ik}。
    • 更新主题词分布：φ_{kv}^{new} = [∑_i γ_{ik} n_{iv}] / [∑_i γ_{ik} L_i]。
  4. 收敛判断：计算观测数据的对数似然 log P(X|θ) = ∑_i log [ ∑_k π_k * ∏_v (φ_{kv})^{n_{iv}} ]。检查这次迭代的对数似然相比上次的增加量是否小于一个预设的阈值。如果是，则停止；否则，用新的参数 (π^{new}, φ^{new}) 替换旧的，回到第2步（E步）。

总结与核心思想

  • E步本质是“软分配”：在现有模型下，为每个数据点计算一个到各个组份（主题）的归属概率（责任γ_{ik}），而不是非此即彼的硬性划分。这使得模型能处理重叠的、模糊的类别。
  • M步本质是“加权估计”：当有了数据的“软分配”后，更新每个组份的参数，就像为每个主题k单独估算一个多项式模型一样，只不过每个数据点x_i 都以其责任γ_{ik} 为权重参与了主题k的参数估计。这确保了与一个主题更相关的数据点对该主题的参数更新贡献更大。
  • 最终输出：算法收敛后，我们不仅得到了每个主题的词分布φ_k（可以查看每个主题下概率最高的词来解读主题含义），还得到了每个文本的主题后验概率γ_i，实现了软聚类。这个模型实质上是概率潜在语义分析（PLSA） 的核心，也是更复杂的主题模型（如LDA）的基础。
期望最大化（EM）算法在混合多项式模型（Mixture of Multinomials）中的参数估计过程 我们先从一个实际问题开始。假设您有一大堆短文本（比如推文标题），每个标题由一些词组成。您想把这些文本自动分成K个主题（例如体育、科技、娱乐），但您不知道每条文本属于哪个主题，也不知道每个主题下词汇的分布规律。混合多项式模型非常适合用在这种“离散特征”数据的聚类场景，而EM算法可以帮助我们在“主题未知”的情况下，估计出模型参数。下面，我将为您一步步拆解。 第一步：理解问题与模型设定 场景 ：我们有N个观测到的文本（样本），每个文本表示为一个“词袋”，即忽略词序，只关心每个词出现的次数。假设整个词典一共有V个不同的词。 目标 ：我们假设这些文本来自K个不同的“主题”（或“类别”）。我们的目标是： 软聚类 ：为每个文本i，计算它属于每个主题k的概率。 模型参数 ：估计出每个主题k下，各个词v出现的概率分布。 模型 ：混合多项式模型 混合系数（Mix Proportion） ： π = [π₁, π₂, …, π_K] ， π_k 表示一个随机文本属于主题k的先验概率。满足 π_k > 0 且 ∑_{k=1}^K π_k = 1 。 每个主题的词分布 ：对于主题k，有一个多项式分布参数向量 φ_k = [φ_{k1}, φ_{k2}, …, φ_{kV}] 。 φ_{kv} 表示在主题k下，出现词v的概率。满足 φ_{kv} > 0 且 ∑_{v=1}^V φ_{kv} = 1 。 隐变量（Latent Variable） ：对于第i个文本，其真实的主题标签 z_i 是我们观察不到的。 z_i 是一个K维的one-hot向量，例如，如果它属于主题2，则 z_i = (0, 1, 0, …, 0) 。 观测数据 ：第i个文本，我们观察到的是一个V维的计数向量 x_i = [n_{i1}, n_{i2}, …, n_{iV}] ，其中 n_{iv} 是词v在该文本中出现的次数。记该文本的总词数为 L_i = ∑_v n_{iv} 。 第二步：建立完整数据似然函数与Q函数 EM算法的核心是处理缺失数据（这里是隐变量z）。我们先写出“如果隐变量z也能被观测到”时的 完整数据似然函数 。 单个样本 (x_ i, z_ i) 的概率 ： 首先，这个样本的主题 z_i 来自一个类别分布： P(z_i) = ∏_{k=1}^K (π_k)^{z_{ik}} 。 z_{ik}=1 时表示选中k。 然后，给定主题k，观测到文本计数向量 x_i 的概率是一个多项式分布： P(x_i | z_{ik}=1) = (L_i)! / (∏_{v=1}^V n_{iv}!) * ∏_{v=1}^V (φ_{kv})^{n_{iv}} 。（组合数项与参数φ无关，在优化中可视为常数）。 因此，完整数据的联合概率为： P(x_i, z_i) = P(z_i) * P(x_i | z_i) = [∏_{k=1}^K (π_k)^{z_{ik}}] * [∏_{k=1}^K (∏_{v=1}^V (φ_{kv})^{n_{iv}})^{z_{ik}}] 。 所有样本的完整数据对数似然函数 （对数和，忽略与参数无关的常数项）： log P(X, Z) = ∑_{i=1}^N ∑_{k=1}^K z_{ik} [ log π_k + ∑_{v=1}^V n_{iv} log φ_{kv} ] 。 构建Q函数 ：在E步，我们需要计算完整数据对数似然函数关于 隐变量后验分布 P(Z|X, θ⁰) 的期望，其中θ⁰是当前参数的估计值（ π⁰, φ⁰ ）。这个期望就是Q函数。 Q(θ, θ⁰) = E_ {Z|X, θ⁰} [ log P(X, Z | θ) ]。 代入上面的对数似然，期望只作用在 z_{ik} 上。因此，关键是计算隐变量的 后验期望 E[z_{ik} | x_i, θ⁰] 。 E[z_{ik} | x_i, θ⁰] = P(z_{ik}=1 | x_i, θ⁰) 。根据贝叶斯定理： γ_{ik} ≜ P(z_{ik}=1 | x_i, θ⁰) = [ π_k⁰ * P(x_i | φ_k⁰) ] / [ ∑_{j=1}^K π_j⁰ * P(x_i | φ_j⁰) ] 。 其中， P(x_i | φ_k⁰) = ∏_{v=1}^V (φ_{kv}⁰)^{n_{iv}} （忽略多项式系数）。 γ_{ik} 有一个非常直观的意义：在现有参数下， 第i个文本属于主题k的“责任”或“响应度”（responsibility） 。它是一个介于0和1之间的软分配值。 于是，Q函数可以明确写出： Q(θ, θ⁰) = ∑_{i=1}^N ∑_{k=1}^K γ_{ik} [ log π_k + ∑_{v=1}^V n_{iv} log φ_{kv} ] 。 第三步：M步 - 最大化Q函数以更新参数 在M步，我们要找到一组新的参数θ = ( π , φ ) 来最大化Q函数，同时满足各自的概率和为1的约束。这需要用拉格朗日乘子法。 更新混合系数 π_ k ： 需要最大化 ∑_{i=1}^N ∑_{k=1}^K γ_{ik} log π_k ，约束是 ∑_k π_k = 1 。 构建拉格朗日函数： L_π = ∑_i ∑_k γ_{ik} log π_k + λ (∑_k π_k - 1) 。 对 π_k 求导并令为0： ∂L_π/∂π_k = (1/π_k) ∑_i γ_{ik} + λ = 0 => ∑_i γ_{ik} = -λ π_k 。 对k求和： ∑_k ∑_i γ_{ik} = -λ ∑_k π_k 。注意到 ∑_k γ_{ik} = 1 （对于一个文本i，属于所有主题的概率和为1），所以左边等于N。右边 ∑_k π_k = 1 ，所以 N = -λ ，即 λ = -N 。 代回： ∑_i γ_{ik} = N π_k 。因此， 更新公式 为： π_k^{(new)} = (1/N) ∑_{i=1}^N γ_{ik} 。 直观解释 ：新的主题k的先验概率，等于所有文本被赋予主题k的“责任”的平均值。 更新主题词分布参数 φ_ {kv} ： 需要最大化 ∑_{i=1}^N ∑_{k=1}^K γ_{ik} ∑_{v=1}^V n_{iv} log φ_{kv} ，对每个k，约束是 ∑_v φ_{kv} = 1 。 对每个主题k分别构建拉格朗日函数： L_{φ_k} = ∑_i γ_{ik} ∑_v n_{iv} log φ_{kv} + μ_k (∑_v φ_{kv} - 1) 。 对 φ_{kv} 求导并令为0： ∂L_{φ_k}/∂φ_{kv} = (1/φ_{kv}) ∑_i γ_{ik} n_{iv} + μ_k = 0 。 所以 φ_{kv} ∝ ∑_i γ_{ik} n_{iv} 。 利用约束 ∑_v φ_{kv} = 1 进行归一化，得到 更新公式 ： φ_{kv}^{(new)} = [∑_{i=1}^N γ_{ik} n_{iv}] / [∑_{i=1}^N γ_{ik} ∑_{u=1}^V n_{iu}] 。 注意分母中 ∑_u n_{iu} = L_i 是第i个文本的总词数。所以公式可以写为： φ_{kv}^{(new)} = [∑_{i=1}^N γ_{ik} n_{iv}] / [∑_{i=1}^N γ_{ik} L_i] 。 直观解释 ： 分子：在整个语料库中，所有文本里词v出现的次数，按照文本属于主题k的“责任” γ_{ik} 进行加权求和。可以理解为 估计出的、属于主题k的所有文本中，词v出现的总期望次数 。 分母：所有文本的总词数，按照文本属于主题k的“责任” γ_{ik} 进行加权求和。可以理解为 估计出的、属于主题k的所有文本的总期望词数 。 因此， φ_{kv} 就是词v在主题k中的期望相对频率。 第四步：整合EM算法步骤与收敛 初始化 ：随机或启发式地初始化参数 π^0 和 φ^0 。确保它们满足概率分布的性质（和为1，元素为正）。 E步（期望步） ：使用当前参数 π^{old} , φ^{old} ，对每个样本i和每个主题k，计算责任 γ_{ik} 。 γ_{ik} = [ π_k^{old} * ∏_{v=1}^V (φ_{kv}^{old})^{n_{iv}} ] / [ ∑_{j=1}^K π_j^{old} * ∏_{v=1}^V (φ_{jv}^{old})^{n_{iv}} ] 。 在实际计算中，通常先计算对数概率避免数值下溢： log P(x_i|φ_k) = ∑_v n_{iv} log φ_{kv} ，然后通过指数归一化（ softmax ）计算 γ_{ik} 。 M步（最大化步） ：使用计算出的 γ_{ik} 作为固定权重，更新参数。 更新混合系数： π_k^{new} = (1/N) ∑_i γ_{ik} 。 更新主题词分布： φ_{kv}^{new} = [∑_i γ_{ik} n_{iv}] / [∑_i γ_{ik} L_i] 。 收敛判断 ：计算观测数据的 对数似然 log P(X|θ) = ∑_i log [ ∑_k π_k * ∏_v (φ_{kv})^{n_{iv}} ] 。检查这次迭代的对数似然相比上次的增加量是否小于一个预设的阈值。如果是，则停止；否则，用新的参数 ( π^{new} , φ^{new} ) 替换旧的，回到第2步（E步）。 总结与核心思想 E步本质是“软分配” ：在现有模型下，为每个数据点计算一个到各个组份（主题）的归属概率（责任 γ_{ik} ），而不是非此即彼的硬性划分。这使得模型能处理重叠的、模糊的类别。 M步本质是“加权估计” ：当有了数据的“软分配”后，更新每个组份的参数，就像为每个主题k单独估算一个多项式模型一样，只不过每个数据点 x_i 都以其责任 γ_{ik} 为权重参与了主题k的参数估计。这确保了与一个主题更相关的数据点对该主题的参数更新贡献更大。 最终输出 ：算法收敛后，我们不仅得到了每个主题的词分布 φ_k （可以查看每个主题下概率最高的词来解读主题含义），还得到了每个文本的主题后验概率 γ_i ，实现了 软聚类 。这个模型实质上是 概率潜在语义分析（PLSA） 的核心，也是更复杂的主题模型（如LDA）的基础。