跳转至

Advanced Posterior Analyses of Hidden Markov Models: Finite Markov Chain Imbedding and Hybrid Decoding

作者: Zenia Elise Damgaard Bæk, Moisès Coll Macià, Laurits Skov, Asger Hobolth
来源: Scandinavian Journal of Statistics
主题: 统计计算 / 算法
相关性: 5/10
机构绿灯: University of Copenhagen(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文所处的子方向是隐马尔可夫模型(HMM)的后验推断,具体解决两类问题:(i) 给定观测序列后,计算隐状态序列的汇总统计量(如状态访问次数、总停留时间、最长游程等)的精确后验分布;(ii) 在全局最优(Viterbi)与逐点最优(Posterior decoding)之间寻找折中的解码路径。该方向在计算生物学(基因预测)、群体遗传学(古人类基因渗入检测)、地震学等领域有直接应用。方法学上,该方向已相当成熟——HMM 的前向-后向算法与 Viterbi 算法自 1970 年代以来就是标准工具,但对"后验分布中非逐点、非全局的汇总统计量"的精确计算以及解码路径的折中策略仍有发展空间。

发展脉络

  • 奠基工作:HMM 的基本推断框架由 Baum 等人(前向-后向算法)与 Viterbi(全局最优解码)在 1960-70 年代建立,经典教材见 [Zucchini et al., 2016]。Burge & Karlin (1997) 将 HMM 引入基因结构预测(GENSCAN),是计算生物学中最具影响力的应用之一,确立了 HMM 作为序列分析核心工具的地位。
  • 主要进展(FMCI 线索):Fu & Koutras (1994) 提出有限马尔可夫链嵌入(FMCI)方法,用于计算 Bernoulli 试验中游程与模式(patterns)的精确分布。Aston & Martin (2007) 将 FMCI 推广到 HMM 框架,在给定观测序列的条件下,通过构造辅助马尔可夫链计算隐状态序列中各类模式的精确后验分布。这是本文方法学的直接基础。
  • 主要进展(解码线索):Lember & Koloydenko (2014) 提出广义风险框架,将 Viterbi 与 Posterior decoding 统一为风险最小化问题,并给出混合解码(hybrid decoding)的动态规划算法。Kuljus & Lember (2023) 将这一框架推广到成对马尔可夫模型(PMM),并系统研究了混合解码的性质。
  • 当前 frontier:在群体遗传学中,Skov et al. (2018) 开发了 hmmix 软件,用 HMM 检测现代人类基因组中的尼安德特人与丹尼索瓦人基因渗入片段。Coll Macià et al. (2025)(本文的姊妹篇)将 FMCI 应用于全基因组规模的基因渗入分析,这是本文方法在大规模数据上的直接推动力。
  • 本文的位置:本文处于上述两条线索的交汇点——一方面将 FMCI 系统化地应用于 HMM 后验汇总统计量的精确计算(含模拟采样作为辅助工具),另一方面对混合解码给出新的推导(加权几何平均视角)并提出基于 Artemis plot 的调参流程。本文是方法综述+应用演示性质的工作,而非全新的理论突破。

子线索聚类

  1. FMCI 与模式分布计算:Fu & Koutras (1994) → Aston & Martin (2007) → Martin (2020) → 本文第 3 节。这条线索的核心问题是:给定一个随机序列(或条件随机序列),如何精确计算"游程长度、访问次数、最长游程"等组合统计量的分布。方法本质是将原始过程嵌入一个状态空间更大的马尔可夫链,使目标统计量成为该链某个状态的吸收概率或首达概率。
  2. 解码策略与风险框架:Viterbi (全局) vs Posterior (逐点) → Lember & Koloydenko (2014) → Kuljus & Lember (2023) → 本文第 4 节。这条线索的核心问题是:解码的损失函数如何定义?逐点准确率与序列级概率不可兼得,如何折中?
  3. 应用驱动:Burge & Karlin (1997) 基因预测 → Skov et al. (2018) 基因渗入检测 → Coll Macià et al. (2025) 全基因组 FMCI。这条线索为方法学提供了具体的性能指标(如解码准确率、渗入片段长度分布)和计算规模约束。

这个方向在追问的核心问题

  1. 精确后验分布的计算可行性:给定观测序列后,隐状态序列的汇总统计量(如最长游程、总访问次数)的精确后验分布能否在多项式时间内计算?FMCI 的状态空间大小如何随原 HMM 的状态数和目标统计量的复杂度增长?
  2. 解码的损失函数选择:逐点准确率(Posterior decoding)与序列级概率(Viterbi)之间的折中如何量化?是否存在系统性的调参方法?
  3. 大规模应用的数值稳定性:全基因组数据(长度 n ~ 10^6-10^7)下,FMCI 的转移矩阵乘法如何避免数值下溢?如何选择截断参数 ℓ(最大游程长度)以平衡精度与计算量?

⚠️ 作者的 framing(这是作者的说法)

作者将本文定位为"对 HMM 后验分析的两种互补工具的完整描述":FMCI 用于"超越点估计的精确后验汇总",混合解码用于"在两种经典解码之间架桥"。作者强调其贡献在于:(a) 将 Aston-Martin 框架从理论文献转化为可直接应用的算法描述(含转移矩阵的显式构造);(b) 对混合解码给出加权几何平均的新推导,使调参过程有直观解释;(c) 提出 Artemis plot 作为选择 α 的实用工具。作者淡化了以下竞争路线:贝叶斯采样方法(如 MCMC 或粒子滤波)虽可近似任意后验汇总统计量,但缺乏精确性保证;而本文的 FMCI 提供的是精确计算。作者也回避了 FMCI 在状态数较多时的计算复杂度问题(转移矩阵维度随 ℓ 线性增长,但随原状态数平方增长)。

值得注意的张力:作者声称 Artemis plot 的"弓形"曲线在"所有模拟中"都出现,但并未给出理论证明——这是一个经验观察而非定理。此外,作者建议的"45 度角"调参规则缺乏决策理论依据(为什么是 45 度而非其他角度?),这更像启发式而非最优准则。

张力

未见被引工作之间存在明显对立结论。但有一个微妙差异:Aston & Martin (2007) 的 FMCI 框架强调"精确计算",而 Lember & Koloydenko (2014) 的混合解码框架强调"风险最小化"——两者对"什么是好的后验分析"的隐含标准不同(前者追求分布精确性,后者追求决策最优性)。本文试图调和两者,但并未在理论上证明二者的一致性。

二、最核心、最简单的例子 / 数学问题

第一步:符号、模型、可观测数据

HMM 设定: - 隐状态序列:\(y = (y_1, \ldots, y_n)\),其中 \(y_t \in \{1, \ldots, m\}\)(\(m\) 个离散状态)。这是潜在(不可观测)的随机变量。 - 观测序列:\(x = (x_1, \ldots, x_n)\),其中 \(x_t\) 可以是离散或连续。这是可观测的数据。 - 模型参数: - \(\pi = (\pi_1, \ldots, \pi_m)\):初始状态分布,\(\pi_i = P(y_1 = i)\)。这是参数(已知或已估计)。 - \(\Gamma = (\Gamma_{ij})_{m \times m}\):转移概率矩阵,\(\Gamma_{ij} = P(y_t = j \mid y_{t-1} = i)\)。这是参数。 - \(\Phi\):发射分布族,\(\Phi(x_t \mid y_t)\) 表示在状态 \(y_t\) 下观测到 \(x_t\) 的概率(密度)。这是参数。 - 数据生成机制:\(y_1 \sim \pi\),\(y_t \mid y_{t-1} \sim \Gamma_{y_{t-1}, \cdot}\),\(x_t \mid y_t \sim \Phi(\cdot \mid y_t)\)。隐状态 \(y\) 是马尔可夫链,观测 \(x\) 在给定隐状态下条件独立。

后验对象: - 前向概率:\(\alpha_t(j) = P(y_t = j, x_1, \ldots, x_t)\)(联合概率,可递归计算)。 - 后向概率:\(\beta_t(j) = P(x_{t+1}, \ldots, x_n \mid y_t = j)\)(条件概率,可递归计算)。 - 逐点后验:\(P(y_t = j \mid x) = \alpha_t(j)\beta_t(j) / P(x)\),其中 \(P(x) = \sum_j \alpha_n(j)\) 是似然(边际概率)。 - 关键定理(本文 Theorem 1):给定观测 \(x\),隐状态序列 \(y\) 的条件分布是一个非齐次马尔可夫链,转移概率为

\[P(y_t \mid y_{t-1}, x) = \frac{\beta_t(y_t) \Gamma_{y_{t-1}, y_t} \Phi(x_t \mid y_t)}{\beta_{t-1}(y_{t-1})}, \quad t = 2, \ldots, n.\]
初始分布为 \(P(y_1 = i \mid x) = \beta_1(i)\pi_i\Phi(x_1 \mid i) / P(x)\)。这个定理是整个 FMCI 方法的基础——它告诉我们,后验隐状态序列仍然是一个马尔可夫链(只是转移概率随时间变化),因此可以应用马尔可夫链的嵌入技术。

目标量(estimand): - 汇总统计量 \(T(y)\),例如: - \(J\) = 从状态 1 到状态 2 的转移次数(跳跃次数); - \(N\) = 在状态 2 中停留的总时间(位置数); - \(E_k\) = 状态 2 中长度为 \(k\) 的精确游程(run)的个数; - \(L\) = 状态 2 中的最长游程长度。 - 我们想要计算 \(P(T(y) = t \mid x)\),即给定观测后,这些统计量的精确后验分布。

第二步:最小内核

核心思想:虽然隐状态序列 \(y\) 有 \(m^n\) 种可能(指数级),但如果我们只关心某个汇总统计量 \(T(y)\),可以通过构造一个嵌入马尔可夫链(imbedded Markov chain),将 \(T(y)\) 的值编码为嵌入链的状态,从而在多项式时间内精确计算 \(T(y)\) 的分布。

最简特例:\(m = 2\) 个状态(状态 1 和状态 2),观测长度 \(n\),我们关心从状态 1 到状态 2 的跳跃次数 \(J\)。

  • 嵌入链的状态:\((j, c)\),其中 \(j \in \{0, 1, \ldots, \ell\}\) 是到目前为止的跳跃次数,\(c \in \{1, 2\}\) 是当前隐状态。
  • 初始分布:\(\eta_{(j,c)} = P(y_1 = c \mid x) \cdot \mathbb{I}(j = 0)\)(初始跳跃次数为 0)。
  • 转移概率:从 \((j, c)\) 到 \((j', c')\) 的概率为
  • 若 \(c = c'\)(不跳跃):\(j' = j\),概率为 \(P(y_t = c' \mid y_{t-1} = c, x)\);
  • 若 \(c = 1, c' = 2\)(跳跃):\(j' = j + 1\),概率为 \(P(y_t = 2 \mid y_{t-1} = 1, x)\);
  • 若 \(c = 2, c' = 1\)(跳跃但方向相反,不计入 \(J\)):\(j' = j\),概率为 \(P(y_t = 1 \mid y_{t-1} = 2, x)\)。
  • 经过 \(n\) 步后,嵌入链的状态分布给出了 \(J\) 的后验分布:$P(J = j \mid x) = \sum_c \text{(第 \(n\) 步处于状态 \((j,c)\) 的概率)}$。

为什么这个例子是"最小内核":它展示了 FMCI 的三个关键要素: 1. 状态扩增:将原始隐状态 \(c\) 扩增为 \((j, c)\),其中 \(j\) 编码目标统计量的累积值; 2. 转移矩阵的稀疏性:嵌入链的转移矩阵是稀疏的(每个原始转移只对应少数几个 \(j\) 的变化),因此矩阵乘法是高效的; 3. 精确性:嵌入链的构造是精确的(没有近似),因此得到的分布是精确的后验分布。

一般化:对于更复杂的统计量(总停留时间 \(N\)、精确游程 \(E_k\)、最长游程 \(L\)),只需改变嵌入链的状态编码方式: - \(N\):状态 \((n, c)\),其中 \(n\) 是累计在状态 2 的时间; - \(E_k\):状态 \((r, c, s)\),其中 \(r\) 是已完成的长度为 \(k\) 的游程数,\(s\) 是当前游程的长度(\(0 \le s \le k\)); - \(L\):状态 \((l, c, s)\),其中 \(l\) 是迄今为止的最长游程,\(s\) 是当前游程长度。

计算复杂度:嵌入链的状态数约为 \(O(\ell \cdot m)\)(\(\ell\) 是统计量的最大可能值),转移矩阵乘法的时间复杂度为 \(O(n \cdot \ell \cdot m^2)\)。对于全基因组数据(\(n \sim 10^7\)),这需要精心实现(利用稀疏矩阵乘法),但仍然是多项式时间的。

混合解码的最小内核:在解码问题中,核心数学对象是混合风险

\[R_\alpha(u|x) = (1-\alpha) \left[-\frac{1}{n}\sum_{t=1}^n \log P(y_t = u_t | x)\right] + \alpha \left[-\frac{1}{n} \log P(y = u | x)\right],\]
其中 \(\alpha \in [0,1]\) 是权重。当 \(\alpha=0\) 时退化为 Posterior decoding(逐点最优),当 \(\alpha=1\) 时退化为 Viterbi(全局最优)。Theorem 2 给出了计算混合路径的动态规划递归:
\[\delta_t(j) = \max_i \left\{ \delta_{t-1}(i) + \alpha \log P(y_t = j, x_t | y_{t-1} = i) \right\} + (1-\alpha) \log P(y_t = j | x),\]
其计算复杂度与 Viterbi 相同(\(O(n \cdot m^2)\)),但每一步额外加上逐点后验的对数项。

三、这篇论文做了什么

三句话

  1. 研究了什么问题:给定 HMM 的观测序列,如何精确计算隐状态序列的汇总统计量(跳跃次数、总停留时间、精确游程数、最长游程)的后验分布,以及如何在 Viterbi 与 Posterior decoding 之间进行系统性的折中解码。
  2. 核心工具/方法:有限马尔可夫链嵌入(FMCI)——将原始隐状态序列扩增为包含统计量累积值的嵌入马尔可夫链,通过稀疏矩阵乘法精确计算统计量的后验分布;混合解码——通过加权几何平均统一 Viterbi 与 Posterior decoding 的损失函数,并用 Artemis plot 选择权重 \(\alpha\)。
  3. 主要结论:FMCI 能精确计算四类汇总统计量的后验分布,且计算复杂度可控(转移矩阵具有块稀疏结构);混合解码在中间块大小上优于两种经典解码方法;Artemis plot 的"弓形"曲线提供了选择 \(\alpha\) 的实用依据。

关键设定与假设

  • HMM 基本假设:隐状态序列是一阶齐次马尔可夫链(转移矩阵 \(\Gamma\) 不随时间变化),观测在给定隐状态下条件独立(发射分布 \(\Phi\))。这是标准 HMM 假设,本文未放宽。
  • 参数已知:本文假设 HMM 的参数 \((\pi, \Gamma, \Phi)\) 已通过 Baum-Welch 或直接数值最大化估计完毕,后验分析是在参数已知的条件下进行的。这是一个重要简化——实际应用中参数估计的不确定性未被纳入。
  • Theorem 1 的假设:后验隐状态序列是非齐次马尔可夫链。这一结论对任何 HMM 都成立(只要发射分布满足基本的正则条件),无需额外假设。
  • FMCI 的截断假设:对于最长游程 \(L\),需要设定一个最大长度 \(\ell\)(超过 \(\ell\) 的游程归入"\(\ge \ell\)"类)。这是一个计算上的截断,不是模型假设——\(\ell\) 的选择会影响计算精度与速度的权衡。
  • 混合解码的假设:损失函数为逐点 \(L_1\) 与全局 \(L_\infty\) 的加权组合(式 11)。这一假设排除了其他可能的损失函数(如块状损失),但覆盖了两种经典解码作为特例。

主要结果

FMCI 部分(第 3 节):

  1. Theorem 1:后验隐状态序列 \(y \mid x\) 是非齐次马尔可夫链,转移概率由前向-后向算法给出。这是 FMCI 的理论基础。
  2. 四类统计量的嵌入构造:
  3. 跳跃次数 \(J\):嵌入状态 \((j, c)\),转移矩阵为块对角加次对角结构(图 6);
  4. 总停留时间 \(N\):嵌入状态 \((n, c)\),转移矩阵为块上三角结构(图 7);
  5. 精确游程 \(E_k\):嵌入状态 \((r, c, s)\),需要跟踪当前游程长度 \(s\);
  6. 最长游程 \(L\):嵌入状态 \((l, c, s)\),需要同时跟踪当前游程和最大值。
  7. 块稀疏结构:所有四类嵌入链的转移矩阵都具有块稀疏结构(每个时间步的转移只涉及少数状态),这使得计算复杂度从朴素的 \(O(n \cdot \ell^2 \cdot m^2)\) 降至 \(O(n \cdot \ell \cdot m^2)\)。
  8. 胎儿运动数据演示:对经典的胎儿羊羔运动数据(\(n = 225\)),FMCI 精确计算了跳跃次数、总停留时间、精确游程数和最长游程的后验分布,与 1000 次模拟采样的经验分布高度一致(图 2)。

混合解码部分(第 4 节):

  1. 加权几何平均推导:作者证明混合风险(式 11)等价于最大化加权几何平均
    \[H_\alpha(u) = \left( \prod_{t=1}^n P(y_t = u_t | x) \right)^{\frac{1-\alpha}{n}} \cdot P(y = u | x)^{\alpha},\]
    这为 \(\alpha\) 提供了直观解释:\(\alpha\) 控制"逐点准确率"与"序列级概率"之间的权衡。
  2. Theorem 2:混合路径可通过动态规划递归计算,复杂度与 Viterbi 相同(\(O(n \cdot m^2)\))。
  3. Artemis plot:以点准确率(x 轴)和对数联合概率(y 轴)为坐标,绘制 \(\alpha\) 从 0 到 1 变化的轨迹。作者观察到该轨迹呈"弓形"(图 4),并建议选择 45 度切线对应的 \(\alpha\) 作为平衡点。
  4. 模拟研究:在 9 种不同的 HMM 设定下(3 种转移概率 × 3 种发射分布),混合解码在块大小 ≥ 2 时优于 Posterior decoding 和 Viterbi(图 13-14)。具体地,混合解码的块准确率在中间块大小(2-5)时最高,而 Viterbi 在大块(≥ 6)时最优。

真实例子: - 胎儿运动数据(\(n = 225\)):FMCI 精确计算了四类统计量的后验分布,展示了方法的实用性。 - 地震数据(\(n = 107\)):混合解码在 1918 和 1973 年给出了不同于 Viterbi 和 Posterior decoding 的状态估计,且这些估计在生物学上更合理。 - 全基因组应用(姊妹篇 Coll Macià et al. 2025):FMCI 被应用于人类基因组中古人类基因渗入片段的检测,这是本文方法在大规模数据上的验证。

🔎 结论是否比证明窄

  • Artemis plot 的"弓形"性质:作者在多个模拟中观察到弓形曲线,但没有给出理论证明。文中说"in all of our simulations we have seen this bow-shaped curve"(第 4.2 节),这是一个经验观察而非定理。对于某些 HMM 参数,曲线可能不是严格弓形(例如当 Viterbi 与 Posterior decoding 差异极小时)。
  • 45 度角规则的合理性:作者建议选择 45 度切线对应的 \(\alpha\),但没有证明这是最优选择。这一规则基于"准确率与概率同等重要"的主观判断,而非决策理论推导。文中承认"we suggest to choose the tuning parameter α by shooting out an arrow at a 45 degree angle"(第 4.2 节),语气是建议而非断言。
  • FMCI 的扩展性:作者在讨论中承认,FMCI 的转移矩阵维度随原 HMM 状态数 \(m\) 的平方增长,对于 \(m\) 较大的 HMM(如 \(m > 10\)),计算可能变得昂贵。文中提到"a number of adaptations are required for long sequences"(第 5 节),但未给出具体的复杂度分析。
  • 参数不确定性的忽略:全文假设 HMM 参数已知,未讨论参数估计误差对后验分布的影响。这是一个重要的局限性——在实际应用中,参数估计的不确定性可能主导后验分布的不确定性。

四、开放问题

  1. Artemis plot 的理论性质:弓形曲线是否对所有 HMM 成立?能否给出 \(\alpha\) 与(点准确率,联合概率)之间关系的解析刻画?45 度角规则是否有决策理论依据?(扎根于第 4.2 节的经验观察与建议性调参规则)

  2. FMCI 的复杂度优化:对于状态数 \(m\) 较大或序列长度 \(n\) 极长(如全基因组 \(n \sim 10^7\))的 HMM,FMCI 的转移矩阵乘法如何优化?能否利用稀疏矩阵结构或低秩近似降低计算成本?(扎根于第 5 节的讨论:"a number of adaptations are required for long sequences")

  3. 参数不确定性的传播:当 HMM 参数 \((\pi, \Gamma, \Phi)\) 是估计值时,FMCI 计算的后验分布如何反映参数估计的不确定性?能否构建参数不确定性的置信带?(扎根于全文"参数已知"的设定)

  4. 混合解码的损失函数推广:本文使用逐点 \(L_1\) 与全局 \(L_\infty\) 的加权组合。能否考虑其他损失函数(如块状损失、加权逐点损失)?混合解码框架能否推广到更一般的成对马尔可夫模型之外的设定?(扎根于第 4.1 节与 [Kuljus & Lember, 2023] 的讨论)

  5. FMCI 与贝叶斯方法的比较:FMCI 提供精确后验分布,但计算成本可能高于 MCMC 或粒子滤波的近似方法。在什么条件下 FMCI 的计算成本是可接受的?能否给出精确方法与近似方法之间的误差界?(扎根于第 5 节对计算复杂度的讨论)


给研究者的提示:若要确认上述某条是否是真 gap,建议去读以下近期文献的引言部分:(1) HMM 解码方向的近期工作(如 [Kuljus & Lember, 2023] 及其后续);(2) FMCI 在群体遗传学中的应用(如 [Coll Macià et al., 2025] 及其引用);(3) 计算生物学中 HMM 后验不确定性的量化方法。若这些文献的引言都指向同一问题,则大概率是共识性 gap;若互相矛盾,则可能是机会。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论