基于期望最大化（Expectation-Maximization, EM）算法的隐马尔可夫模型（HMM）无监督训练算法详解
字数 3811 2025-12-20 15:53:24

基于期望最大化（Expectation-Maximization, EM）算法的隐马尔可夫模型（HMM）无监督训练算法详解

算法题目描述

在自然语言处理中，隐马尔可夫模型（HMM）是一种经典的概率图模型，广泛应用于词性标注、语音识别、命名实体识别等序列标注任务。HMM的核心假设是：一个可观测的序列（如单词序列）是由一个隐藏的、不可观测的状态序列（如词性序列）按照一定的概率规则生成的。HMM由三个基本要素构成：初始状态概率分布、状态转移概率矩阵和观测概率矩阵。

通常情况下，如果训练数据是有标注的（即每个观测值对应的隐藏状态已知），我们可以通过简单的统计计数来直接估计HMM的参数。然而，在很多实际场景中，我们往往只有大量的无标注观测序列（例如，只有大量的原始文本，没有对应的词性标注）。基于期望最大化（EM）算法的HMM无监督训练，就是在只有观测序列、没有状态标签的情况下，自动学习HMM模型参数（即初始概率、转移概率、发射概率）的经典算法。这个算法有时也被称为Baum-Welch算法，它是EM算法在HMM上的具体实现。

简单来说，这个算法要解决的问题是：“给定一组观测序列，如何找到一个最能解释这些观测数据的HMM模型参数？”

解题过程详解

为了让你彻底明白，我们循序渐进地讲解，从基础概念到算法核心，最后到具体计算步骤。

第一步：回顾隐马尔可夫模型（HMM）的基本要素

一个HMM模型由以下五元组定义：

  1. 状态集合 (Q)：所有可能的隐藏状态。例如，在词性标注中，Q = {名词，动词，形容词…}。
  2. 观测集合 (V)：所有可能的观测值。例如，词汇表 {“今天”, “是”, “晴天”…}。
  3. 初始状态概率分布 (π)：πᵢ = P(第一个状态是i)。向量π描述了序列开始时处于各个状态的概率。
  4. 状态转移概率矩阵 (A)：Aᵢⱼ = P(下一个状态是j | 当前状态是i)。矩阵A描述了隐藏状态之间的转移规律。
  5. 观测概率矩阵 (B)：Bᵢ(k) = P(观测到符号vₖ | 当前状态是i)。矩阵B描述了从某个状态生成某个观测值的概率。

我们的目标：在只知道观测序列O = (o₁, o₂, …, o_T)的情况下，学习出模型参数 λ = (π, A, B)。

第二步：理解核心挑战与EM算法思想

为什么这个问题很难？
因为状态序列是“隐藏”的，我们不知道每个观测值o_t对应的是哪个状态q_t。如果知道，直接统计“状态i出现了多少次”、“从i跳转到j多少次”、“从i生成观测k多少次”，就能轻松得到参数。但现在我们只有观测值，不知道状态，这就是一个典型的“含有隐变量”的参数估计问题。

EM算法框架：
EM算法是解决此类问题的利器。它是一种迭代优化算法，每次迭代包含两个步骤：

  1. E步 (Expectation, 期望步)：基于当前的模型参数λ^(old)，计算隐变量的后验概率分布，或者说，计算“在现有模型下，隐变量的期望统计量”。
  2. M步 (Maximization, 最大化步)：将E步计算得到的期望统计量，当作是“完整数据”（即观测和状态都已知的数据）的统计量，然后重新估计（更新）模型参数λ^(new)，使得在“完整数据”上的对数似然函数的期望最大化。

然后，用λ^(new)替换λ^(old)，重复E步和M步，直到模型参数收敛（变化非常小）。

第三步：EM算法在HMM中的具体实现——Baum-Welch算法

在HMM的语境下，EM算法的具体形式就是Baum-Welch算法。我们需要在E步计算一些关键的期望统计量。

首先，定义两个贯穿始终的重要概率，它们可以通过前向-后向算法高效计算：

  • 前向概率 α_t(i)：给定模型λ，在时刻t观测到序列o₁, o₂, …, o_t，并且t时刻状态为q_i的概率。即 α_t(i) = P(o₁, o₂, …, o_t, q_t = i | λ)。
  • 后向概率 β_t(i)：给定模型λ，并且在时刻t状态为q_i的条件下，从t+1到T观测到序列o_{t+1}, …, o_T的概率。即 β_t(i) = P(o_{t+1}, …, o_T | q_t = i, λ)。

有了α和β，我们就可以计算E步所需的核心期望统计量：

  1. 时刻t处于状态i的概率 (γ_t(i))：
    这是给定整个观测序列O和模型λ，在时刻t状态为q_i的概率。
    γ_t(i) = P(q_t = i | O, λ) = α_t(i)β_t(i) / P(O|λ)
    其中，P(O|λ)是观测序列的似然，可以通过前向算法的最后一步对所有状态求和得到：P(O|λ) = Σ_i α_T(i)。

  2. 时刻t处于状态i且时刻t+1处于状态j的概率 (ξ_t(i, j))：
    这是给定整个观测序列O和模型λ，在时刻t状态为q_i且在时刻t+1状态为q_j的概率。
    ξ_t(i, j) = P(q_t = i, q_{t+1} = j | O, λ) = [α_t(i) * Aᵢⱼ * Bⱼ(o_{t+1}) * β_{t+1}(j)] / P(O|λ)

直观理解：

  • γ_t(i) 可以看作是“状态i”在时刻t所承担的“责任”或“权重”。
  • ξ_t(i, j) 可以看作是“从状态i转移到状态j”这个事件在时刻t所承担的“责任”或“权重”。

第四步：算法步骤拆解

现在，我们将Baum-Welch算法的迭代过程一步步拆解：

输入：观测序列集合 {O^(1), O^(2), …, O^(K)}，状态数N，观测符号数M。
输出：HMM模型参数 λ = (π, A, B)。

步骤0：初始化参数λ^(0)
随机初始化或根据先验知识初始化 π, A, B。例如，可以均匀初始化，或者用有标签的小部分数据初始化。这是迭代的起点。

步骤1：E步 (计算期望统计量)
对于每一个观测序列O（假设长度为T）：

  1. 运行前向算法，计算所有时刻t和所有状态i的 α_t(i)。
  2. 运行后向算法，计算所有时刻t和所有状态i的 β_t(i)。
  3. 计算序列的似然 P(O|λ)。
  4. 利用α, β, P(O|λ) 和当前模型参数 λ^(old)，计算该序列对应的：
    • γ_t(i) for t=1 to T, i=1 to N
    • ξ_t(i, j) for t=1 to T-1, i=1 to N, j=1 to N

对所有K个观测序列，分别计算并保存这些概率。

步骤2：M步 (重新估计参数)
利用E步计算出的期望统计量（对所有序列求和），像处理“完整数据”一样，重新估计模型参数。

  1. 更新初始状态概率 π：
    π_i^(new) = （在所有序列的第一个时刻，状态i的期望次数） / （序列总数K的变体）
    更精确地说，对于单序列，π_i = γ_1(i)。对于多个序列，可以求平均：
    π_i^(new) = (1/K) * Σ_{k=1}^K γ_1^{(k)}(i)
    （其中 γ_1^{(k)}(i) 是第k个序列的 γ_1(i)）。

  2. 更新状态转移概率 A：
    A_{ij}^(new) = （从状态i转移到状态j的期望总次数） / （从状态i转移出去的期望总次数）
    A_{ij}^(new) = Σ_{k=1}^K Σ_{t=1}^{T_k-1} ξ_t^{(k)}(i, j) / Σ_{k=1}^K Σ_{t=1}^{T_k-1} γ_t^{(k)}(i)
    分子是所有序列中所有时刻从i到j转移的期望次数之和，分母是所有序列中所有时刻处于状态i的期望次数之和。

  3. 更新观测概率 B：
    B_i(v)^(new) = （在状态i下观测到符号v的期望总次数） / （处于状态i的期望总次数）
    B_i(v)^(new) = Σ_{k=1}^K Σ_{t=1}^{T_k} (γ_t^{(k)}(i) * I[o_t^{(k)} == v]) / Σ_{k=1}^K Σ_{t=1}^{T_k} γ_t^{(k)}(i)
    其中 I[条件] 是指示函数，当观测值o_t等于符号v时为1，否则为0。分子是“在状态i下观测到v”的加权计数，分母是“处于状态i”的总权重。

步骤3：检查收敛性
计算在新参数 λ^(new) 下，所有观测序列的总对数似然 L(λ) = Σ_k log P(O^(k) | λ^(new))。
比较新的总对数似然与旧的是否足够接近（例如，差值小于一个预设的极小阈值ε）。如果已收敛，则算法终止，λ^(new) 即为学习到的模型。否则，令 λ^(old) = λ^(new)，返回步骤1继续迭代。

总结

基于EM的HMM无监督训练（Baum-Welch算法） 巧妙地解决了“数据不完整”下的模型学习问题。其核心在于：

  • E步：通过前向-后向算法，计算出“如果数据完整，各种状态和转移应该出现的概率（期望）”。
  • M步：将这些概率当作真实发生的次数，用最大似然估计的公式去更新模型参数。

这个算法保证了每一次迭代，模型在训练数据上的对数似然都不会下降，最终会收敛到一个局部最优解。它是HMM在无监督场景下应用的基石，也深刻体现了EM算法处理隐变量问题的强大威力。

基于期望最大化（Expectation-Maximization, EM）算法的隐马尔可夫模型（HMM）无监督训练算法详解 算法题目描述 在自然语言处理中，隐马尔可夫模型（HMM）是一种经典的概率图模型，广泛应用于词性标注、语音识别、命名实体识别等序列标注任务。HMM的核心假设是：一个可观测的序列（如单词序列）是由一个隐藏的、不可观测的状态序列（如词性序列）按照一定的概率规则生成的。HMM由三个基本要素构成：初始状态概率分布、状态转移概率矩阵和观测概率矩阵。 通常情况下，如果训练数据是 有标注的 （即每个观测值对应的隐藏状态已知），我们可以通过简单的统计计数来直接估计HMM的参数。然而，在很多实际场景中，我们往往只有大量的 无标注观测序列 （例如，只有大量的原始文本，没有对应的词性标注）。 基于期望最大化（EM）算法的HMM无监督训练 ，就是在只有观测序列、没有状态标签的情况下，自动学习HMM模型参数（即初始概率、转移概率、发射概率）的经典算法。这个算法有时也被称为 Baum-Welch算法 ，它是EM算法在HMM上的具体实现。 简单来说，这个算法要解决的问题是： “给定一组观测序列，如何找到一个最能解释这些观测数据的HMM模型参数？” 解题过程详解 为了让你彻底明白，我们循序渐进地讲解，从基础概念到算法核心，最后到具体计算步骤。 第一步：回顾隐马尔可夫模型（HMM）的基本要素 一个HMM模型由以下五元组定义： 状态集合 (Q) ：所有可能的隐藏状态。例如，在词性标注中，Q = {名词，动词，形容词…}。 观测集合 (V) ：所有可能的观测值。例如，词汇表 {“今天”, “是”, “晴天”…}。 初始状态概率分布 (π) ：πᵢ = P(第一个状态是i)。向量π描述了序列开始时处于各个状态的概率。 状态转移概率矩阵 (A) ：Aᵢⱼ = P(下一个状态是j | 当前状态是i)。矩阵A描述了隐藏状态之间的转移规律。 观测概率矩阵 (B) ：Bᵢ(k) = P(观测到符号vₖ | 当前状态是i)。矩阵B描述了从某个状态生成某个观测值的概率。 我们的目标 ：在只知道观测序列O = (o₁, o₂, …, o_ T)的情况下，学习出模型参数 λ = (π, A, B)。 第二步：理解核心挑战与EM算法思想 为什么这个问题很难？ 因为状态序列是“隐藏”的，我们不知道每个观测值o_ t对应的是哪个状态q_ t。如果知道，直接统计“状态i出现了多少次”、“从i跳转到j多少次”、“从i生成观测k多少次”，就能轻松得到参数。但现在我们只有观测值，不知道状态，这就是一个典型的“含有隐变量”的参数估计问题。 EM算法框架 ： EM算法是解决此类问题的利器。它是一种迭代优化算法，每次迭代包含两个步骤： E步 (Expectation, 期望步) ：基于当前的模型参数λ^(old)，计算隐变量的 后验概率分布 ，或者说，计算“在现有模型下，隐变量的期望统计量”。 M步 (Maximization, 最大化步) ：将E步计算得到的期望统计量，当作是“完整数据”（即观测和状态都已知的数据）的统计量，然后重新估计（更新）模型参数λ^(new)，使得在“完整数据”上的对数似然函数的期望最大化。 然后，用λ^(new)替换λ^(old)，重复E步和M步，直到模型参数收敛（变化非常小）。 第三步：EM算法在HMM中的具体实现——Baum-Welch算法 在HMM的语境下，EM算法的具体形式就是Baum-Welch算法。我们需要在E步计算一些关键的期望统计量。 首先，定义两个贯穿始终的重要概率，它们可以通过 前向-后向算法 高效计算： 前向概率 α_ t(i) ：给定模型λ，在时刻t观测到序列o₁, o₂, …, o_ t，并且t时刻状态为q_ i的概率。即 α_ t(i) = P(o₁, o₂, …, o_ t, q_ t = i | λ)。 后向概率 β_ t(i) ：给定模型λ，并且在时刻t状态为q_ i的条件下，从t+1到T观测到序列o_ {t+1}, …, o_ T的概率。即 β_ t(i) = P(o_ {t+1}, …, o_ T | q_ t = i, λ)。 有了α和β，我们就可以计算E步所需的核心期望统计量： 时刻t处于状态i的概率 (γ_ t(i)) ： 这是给定整个观测序列O和模型λ，在时刻t状态为q_ i的概率。 γ_t(i) = P(q_t = i | O, λ) = α_t(i)β_t(i) / P(O|λ) 其中，P(O|λ)是观测序列的似然，可以通过前向算法的最后一步对所有状态求和得到：P(O|λ) = Σ_ i α_ T(i)。 时刻t处于状态i且时刻t+1处于状态j的概率 (ξ_ t(i, j)) ： 这是给定整个观测序列O和模型λ，在时刻t状态为q_ i且在时刻t+1状态为q_ j的概率。 ξ_t(i, j) = P(q_t = i, q_{t+1} = j | O, λ) = [α_t(i) * Aᵢⱼ * Bⱼ(o_{t+1}) * β_{t+1}(j)] / P(O|λ) 直观理解 ： γ_ t(i) 可以看作是“状态i”在时刻t所承担的“责任”或“权重”。 ξ_ t(i, j) 可以看作是“从状态i转移到状态j”这个事件在时刻t所承担的“责任”或“权重”。 第四步：算法步骤拆解 现在，我们将Baum-Welch算法的迭代过程一步步拆解： 输入 ：观测序列集合 {O^(1), O^(2), …, O^(K)}，状态数N，观测符号数M。 输出 ：HMM模型参数 λ = (π, A, B)。 步骤0：初始化参数λ^(0) 随机初始化或根据先验知识初始化 π, A, B。例如，可以均匀初始化，或者用有标签的小部分数据初始化。这是迭代的起点。 步骤1：E步 (计算期望统计量) 对于 每一个 观测序列O（假设长度为T）： 运行 前向算法 ，计算所有时刻t和所有状态i的 α_ t(i)。 运行 后向算法 ，计算所有时刻t和所有状态i的 β_ t(i)。 计算序列的似然 P(O|λ)。 利用α, β, P(O|λ) 和当前模型参数 λ^(old)，计算该序列对应的： γ_ t(i) for t=1 to T, i=1 to N ξ_ t(i, j) for t=1 to T-1, i=1 to N, j=1 to N 对所有K个观测序列，分别计算并保存这些概率。 步骤2：M步 (重新估计参数) 利用E步计算出的期望统计量（对所有序列求和），像处理“完整数据”一样，重新估计模型参数。 更新初始状态概率 π ： π_i^(new) = （在所有序列的第一个时刻，状态i的期望次数） / （序列总数K的变体） 更精确地说，对于单序列， π_i = γ_1(i) 。对于多个序列，可以求平均： π_i^(new) = (1/K) * Σ_{k=1}^K γ_1^{(k)}(i) （其中 γ_ 1^{(k)}(i) 是第k个序列的 γ_ 1(i)）。 更新状态转移概率 A ： A_{ij}^(new) = （从状态i转移到状态j的期望总次数） / （从状态i转移出去的期望总次数） A_{ij}^(new) = Σ_{k=1}^K Σ_{t=1}^{T_k-1} ξ_t^{(k)}(i, j) / Σ_{k=1}^K Σ_{t=1}^{T_k-1} γ_t^{(k)}(i) 分子是所有序列中所有时刻从i到j转移的期望次数之和，分母是所有序列中所有时刻处于状态i的期望次数之和。 更新观测概率 B ： B_i(v)^(new) = （在状态i下观测到符号v的期望总次数） / （处于状态i的期望总次数） B_i(v)^(new) = Σ_{k=1}^K Σ_{t=1}^{T_k} (γ_t^{(k)}(i) * I[o_t^{(k)} == v]) / Σ_{k=1}^K Σ_{t=1}^{T_k} γ_t^{(k)}(i) 其中 I[条件] 是指示函数，当观测值o_ t等于符号v时为1，否则为0。分子是“在状态i下观测到v”的加权计数，分母是“处于状态i”的总权重。 步骤3：检查收敛性 计算在新参数 λ^(new) 下，所有观测序列的总对数似然 L(λ) = Σ_k log P(O^(k) | λ^(new)) 。 比较新的总对数似然与旧的是否足够接近（例如，差值小于一个预设的极小阈值ε）。如果已收敛，则算法终止，λ^(new) 即为学习到的模型。否则，令 λ^(old) = λ^(new)，返回 步骤1 继续迭代。 总结 基于EM的HMM无监督训练（Baum-Welch算法） 巧妙地解决了“数据不完整”下的模型学习问题。其核心在于： E步 ：通过前向-后向算法，计算出“如果数据完整，各种状态和转移应该出现的概率（期望）”。 M步 ：将这些概率当作真实发生的次数，用最大似然估计的公式去更新模型参数。 这个算法保证了每一次迭代，模型在训练数据上的对数似然都不会下降，最终会收敛到一个局部最优解。它是HMM在无监督场景下应用的基石，也深刻体现了EM算法处理隐变量问题的强大威力。