任意阶隐马尔可夫模型的摊销参数推断 张思祥、蔡丽敏

《Axioms》:Amortized Parameter Inference for the Arbitrary-Order Hidden Markov Model Sixiang Zhang and Liming Cai

【字体: 大 中 小 】 时间:2026年04月16日 来源:Axioms 1.6

编辑推荐:

  摘要 任意阶隐藏马尔可夫模型(??-HMM)是标准HMM的非平凡泛化,旨在模拟随机过程中任意远处随机事件之间的高阶依赖关系。??-HMM采用了一种高效的Viterbi风格最优解码算法,使得在观测到的序列数据中发现数据对象之间的高阶依赖关系成为可能。由于??

  摘要 任意阶隐藏马尔可夫模型(??-HMM)是标准HMM的非平凡泛化,旨在模拟随机过程中任意远处随机事件之间的高阶依赖关系。??-HMM采用了一种高效的Viterbi风格最优解码算法,使得在观测到的序列数据中发现数据对象之间的高阶依赖关系成为可能。由于??-HMM的表达能力超过了标准HMM、固定阶数的HMM以及随机上下文无关文法,因此需要有效的概率参数估计方法将??-HMM的理论表达能力转化为实际应用价值。本文提出了一种基于观测数据有效估计??-HMM概率参数的原理性方法。在大规模序列数据集中,高阶依赖关系可能因实例而异,因此单一的全局参数集可能不够适用。为此,我们提出了一种分摊参数估计方法,该方法从数据中学习输入条件下的参数估计器,并用其来为解码算法的每个输入实例推断特定于该实例的参数。具体而言,神经参数估计器通过一个复合学习目标进行训练,该目标部分由最优解码算法实现。通过将??-HMM应用于生物分子结构建模和预测的实证结果,证明了所提出参数估计方法的有效性。 1. 引言隐藏马尔可夫模型(HMM)是一种适用于随机过程的概率图模型,在涉及时间序列和序列数据推理的应用中取得了广泛的成功 [1,2,3]。尽管通过线性时间的Viterbi算法可以实现高效的推理,从而从观测数据中有效地解码潜在状态序列 [4],但HMM的实际效果在很大程度上取决于可靠的参数估计方法的可用性。特别是,成熟的学习技术,如对完全观测到的训练数据使用最大似然估计,以及对具有潜在或缺失结构的数据使用基于期望最大化的Baum–Welch算法 [5,6],使得可以从数据中稳健地学习HMM参数。正是这种结合,尤其是参数估计方法的成熟,使得HMM的理论形式成为广泛采用的建模框架。虽然标准HMM在模拟局部依赖关系方面表现有效,但序列数据的应用可能需要推断超出简单随机过程的更丰富的结构信息。这样的结构可能出现在各种场景中,例如语言序列中的句法和语义依赖关系 [7,8]、决定生物分子结构和功能的生物残基相互作用 [9,10],以及时间序列数据中的潜在模式,如天气预报和市场预测 [11,12,13,14]。尽管已经通过扩展标准HMM对随机事件之间的高阶依赖关系进行了建模 [15,16],但它们很少能达到与标准HMM相同的实际效果。由于模型复杂性的增加,参数估计比在标准HMM中困难得多;更丰富的结构依赖关系显著增加了参数的数量并使潜在推断变得复杂。特别是,在??阶HMM中的学习面临着参数指数级增长和数据稀疏性问题 [17,18],而随机上下文无关文法(SCFG)[19] 的训练在计算上是昂贵的且在统计上效率低下 [20,21]。最近,任意阶隐藏马尔可夫模型(??-HMM)[22] 被引入,作为标准HMM的泛化,其表达能力克服了之前对HMM的扩展(例如??阶HMM和SCFG)的不足。??-HMM具备了一种机制,可以表达数据中任意距离事件之间的依赖关系,并且对生成数据的观测序列和隐藏事件具有明确定义的联合概率分布。这些依赖关系可能是嵌套的、平行的和交叉的模式,其中一些超出了SCFG的表征能力。与标准HMM一样,??-HMM的一个重要用途是通过解码揭示潜在事件之间的高阶依赖关系。尽管使用??-HMM的全部能力进行解码在计算上可能是不可行的,但已经证明可以在O(?(n^3)的时间复杂度内高效地预测由互补隐藏事件对诱导的最优依赖关系集合 [22]。为了将??-HMM的理论潜力转化为实际应用价值,必须将其解码算法与有效的概率参数估计方法相结合。然而,由于??-HMM的表达能力严格超过了??阶HMM和随机上下文无关文法,为这些模型开发的参数估计方法已不再适用。此外,在大规模数据集中,高阶依赖结构可能因实例而大相径庭,单一的全局参数集是不够的。为了解决这些挑战,我们提出了一种分摊学习方法 [23,24],该方法能够实现可扩展的、特定于实例的参数推断,并充分利用??-HMM的建模能力。我们不是估计所有序列共用的单一全局参数集,而是从数据中学习输入条件下的参数估计器,为每个需要预测依赖结构的数据输入序列生成特定的??-HMM参数。具体来说,分摊参数估计器通过优化一个综合目标进行训练,该目标结合了对潜在事件序列的全局和局部结构约束。第一个术语鼓励参考隐藏事件路径在推断出的参数下获得高分。第二个术语对参考隐藏状态序列施加监督,有助于稳定局部一致的状态转换行为。第三个术语引入了一个结构化边际,将参考路径与在相同参数下由Viterbi风格解码产生的竞争路径分开。第四个特定于任务的术语进一步引导模型朝向期望的结构化输出。通过在生物分子结构建模和预测中的应用实证结果,证明了所提出的参数估计方法的有效性。 2. 基础知识在本节中,我们回顾了隐藏马尔可夫模型(HMM)和一些机器学习的基础知识,这些知识对于进一步阅读??-HMM的解码算法以及后续部分将介绍的参数估计方法是必要的。更多详细信息,请参考 [2,25]。 2.1. 隐藏马尔可夫模型随机过程是一组随机变量 {???? :?? ∈?},其中 ? 是自然数集,随机变量 ???? 定义在相同的概率空间上。定义1. 离散隐藏马尔可夫模型(HMM)[5] 是一个双变量随机过程 {(????,????) :?? ∈?},其中 ???? 从有限的状态集 S 中抽取值,???? 从有限的符号集 Σ 中抽取值,使得对于每个有限的 ?? ≥1,联合概率 ???({(????,????) :?? ≤??}) 定义为 ???({(????,????):??≤??})=???(??1)???∏??=1???(????|????)????1∏??=1???(????+1|????) (1) 注意方程(1)是基于局部马尔可夫性质以及概率论的链式法则推导出来的。图形上,HMM表示为一个概率有限状态机(??,Σ,??,??),其中每个状态 ?? ∈?? 可以以概率 ?????(??) 发射符号 ?? ∈Σ,其分布满足 ∑??∈Σ?????(??) =1。每个状态 r 可以以概率 ?????(??) 转移到另一个状态 s,其分布满足 ∑??∈???????(??) =1。具体来说,对于任何符号 ?? ∈Σ 和任何状态 ?? ∈??,条件概率 ???(???? =??|???? =??) 在(1)中定义为 ?????(??),条件概率 ???(????+1 =??|???? =??) 对于任何状态 ?? ∈?? 定义为 ?????(??)。分布 ?? 和 ?? 是完全确定HMM模型的参数。与HMM相关的一个典型任务是从观测到的有限符号序列 {???? :?? ≤??} 解码隐藏状态 {????? :?? ≤??},优化问题为 {?????:??≤??}=arg?max{????:??≤??}????({????:??≤??}|{????:??≤??}) ,这可以通过利用方程(1)中的概率分解,使用???(??)-时间动态规划Viterbi算法计算得出。为了将解码算法应用于实际应用,需要知道HMM模型的参数 ?? =(??,??)。虽然参数的准确值可能并不总是已知的,但可以从训练数据中估计出参数值。根据数据的可用性,通常有两种不同的HMM参数估计方法。当训练数据同时包含观测到的符号序列和生成它们的隐藏状态时,可以通过计数训练数据中标记的所有发射和转换来使用最大似然方法计算分布 ?? 和 ??,并将频率分配给概率参数。当发射可观测符号的状态未知或未包含在训练数据中时,会出现困难情况。为了处理这种缺失数据的情况,通常使用期望最大化(EM)方法来计算事件发生的预期频率。技术上,EM 是一个迭代过程,包括交替计算期望和最大化期望的步骤。给定当前参数 ??(??),计算并最大化所有可能隐藏变量值(从训练数据中抽取)下 ?? 的预期对数似然 ???(??,??|??),即 ??(??+1)=arg?max???????~???(·|??,??(??))?[log????(??,??|??)] =arg?max???∑??log????(??,??|??)??(??|??,???(??))。对于HMM,迭代过程通过Baum–Welch算法 [6] 高效实现,该算法协调两个方向的计算,计算总概率 ∑?????(??,??)。 2.2. 深度学习基础深度学习是一种通过神经网络近似输入和输出之间复杂关系函数的先进技术 [26]。神经网络由堆叠的计算单元层组成,每个单元计算其输入的加权和,然后进行非线性转换。实际上,较低的层通常捕获抽象的简单或局部模式,而较深的层将它们组合起来以编码更全局和结构化的信息。通过在可用数据上训练来学习神经网络,通过最小化与网络计算单元相关的参数来确定这些参数。这些参数是通过最小化一个经验目标函数来确定的,该函数量化了网络预测输出与观测数据之间的差异。由于优化问题通常是非凸的且维度高,因此使用基于梯度的迭代方法(如反向传播)来计算网络参数是相当高效的 [25]。以下是一些也将在我们第4节介绍的??-HMM神经参数估计器中使用的基本函数。单元级函数sigmoid:sigmoid函数将实数(例如,神经门的输出)转换为区间(0,1)内的概率,对于每个 ?? ∈?,???(??)=1/(1+exp?(???))。softplus:softplus函数将实数映射到非负值,对于每个 ?? ∈?,softplus?(??)=log?(1+exp?(??))∈?≥0。层级函数MLP [27]:MLP是一种多层感知器,定义了从输入层到输出层的映射:??? →???,中间有一个或多个隐藏层,其中连续两层中的神经元完全连接。softmax:softmax函数将向量 ?? ∈??? 映射到概率向量 ?? ∈[0,1]??,使得对于 ?? =1,…,??,????=softmax?(????)=exp?(????)∑????=1exp?(????),满足 ∑????=1。它通常用作归一化操作符,仅应用于输出层。序列上的函数Transformer编码器 [28]:Transformer编码器是一种映射函数:???? :???×?? →???×??,将输入长度为L的向量序列映射到相同长度的上下文化表示序列。每个输入向量(包含d个条目)是相应输入位置的嵌入(语义),而每个输出向量是所有输入位置的加权组合(使用自注意力计算)。注意力池化:注意力池化函数 ???×?? →???,计算向量序列的加权汇总,其中权重用于强调对任务最相关的元素。 3. 任意阶隐藏马尔可夫模型 3.1. ??-HMMHMM被扩展为涵盖模型更高阶依赖关系的框架,这些依赖关系超出了随机过程中连续事件之间的线性关系。从技术上讲,两个状态之间的依赖关系可以通过这两个状态的数据发射联合概率分布来指定[22]。定义2:一个影响是一个有序的状态对???,???,其中??,?? ∈??,且具有概率分布??????,??,使得对于每一个固定的?? ∈Σ,都有∑??∈Σ??????,???(??)=1(2)。设{(????,????|??∈?)}是一个随机过程,其中????和????(??
5.2. ??1-HMM估计器的RNA特定参数化
为了使用??1-HMM解码输入RNA序列?? =??1…????(长度为n)的隐藏状态,转移、发射和影响参数(??,??,??)由学习到的参数估计器????预测,即?????(??)=(??,??,??)。从图3中,我们定义了以下矩阵:
??=?? ? ? ? ? ? ? ??1?ΔΔ00??leave01???leave0??leave001???leave????01???????? ? ? ? ? ? ? ??, ??=(????????????????), ??=?? ? ? ? ? ? ? ???????????????????????????????????????????????????????3????3??????2??????2??????2?????????2?????????????3??????3??????3??????3???????? ? ? ? ? ? ? ? ?。 (7)
这里,??是在状态??,??,??,??之间的转移概率矩阵。特别地,?????(??) =Δ且?????(??) =1 ?Δ,而??的R行由??,?? ≥0参数化,其中?? +?? ≤1。在本工作中使用的RNA实现中,我们进一步引入了两个离开概率??leave和??leave,分别控制从状态P和Q的转移。

使用????对每个输入RNA序列??的??1-HMM估计(??,??,??)需要五个标量(Δ,??,??,??leave,??leave)、四个logits(??)和4 ×4 =16个logits(??),总共25个序列特定参数。解码过程中使用的其他量,如起始分布和几个状态依赖的成本,是跨序列共享的全局可训练参数。

为了推断这25个参数,我们首先将RNA序列通过一个神经编码器,它将每个核苷酸(A, C, G, U)映射到一个可学习的640维嵌入向量。然后,得到的嵌入序列通过一个三层Transformer编码器进行处理,该编码器具有旋转位置编码、640的隐藏维度、10个注意力头、2 ×640 =1280的前馈维度以及GELU激活函数和0.05的丢弃率。每个序列位置的上下文化表征随后通过一个 token-level trunk 处理,包括从640维到320维的线性投影、一个GELU激活函数、一个层归一化层以及一个隐藏维度为320且丢弃率为0.05的残差前馈块。这些token特征随后通过一个注意力池化层聚合,得到一个序列级表征,该表征通过一个层归一化层后接着是一个线性投影映射到25个序列特定参数。对于tRNA实验,我们使用了模型的简化版本,其中只有Δ, ??, 和??被预测为序列特定的转移参数,而??leave和??leave不进行推断,而是固定为零。因此,tRNA变体预测了3 +4 +16 =23个序列特定参数,而不是25个。tRNA编码器的规模也较小,使用了一个具有128隐藏维度的两层Transformer、192的前馈维度、4个注意力头、学习到的绝对位置嵌入以及0.1的丢弃率。在这两种模型变体中,三种影响作用通过一个共享的4 ×4核苷酸对矩阵??参数化。

5.3. RNA二级结构预测的训练目标
我们使用AdamW [32]进行模型训练,学习率为10?4,权重衰减为10?2。根据第4节介绍的一般损失公式,我们将RNA二级结构目标定义为?=exp?(???path) ?path+??path+exp?(???state) ?state+??state +exp?(???adv) ?adv+??adv+exp?(???task) ?task+??task,其中??path、??state、??adv和??task是可学习的标量权重。
设??表示输入的RNA序列,??表示参考的隐藏状态序列,??表示参考的点括号二级结构。设?????(??,??,??)表示在由?????(??)预测的序列特定参数下的参考状态路径的得分。那么路径级别的损失定义为?path=softplus?(??path??????(??,??,??)),这鼓励参考路径获得足够高的得分。
结构化对抗损失定义为?adv=1??3??∑??=1softplus?(?????(??,??′??,??′??)??????(??,??,??)+??adv),其中{(??′??,??′??)}????=1是解码出的硬负候选项,??path,??adv ≥0是边际常数。
状态序列损失定义为在预测的起始和转移分布下参考隐藏状态链的负对数似然:?state=?log??????(??1)????1∑??=1log??????(????+1∣????)。在RNA二级结构设置中,任务特定的项?task被实现为成对碱基对监督损失:?task=1|??+|?∑(??,??)∈??+softplus?(??????(??,??))+1|???|?∑(??,??)∈???softplus?(?????(??,??)),其中?? +和?? ?分别表示正的和抽取的负的碱基对候选项。
在我们的实现中,解码是离散的且不可微的。特别是,Viterbi风格的动态规划仅用于生成?adv的硬负候选项,梯度不会通过离散的回溯步骤传播。因此,训练不依赖于REINFORCE风格的梯度估计;相反,通过上述可微的替代损失来优化摊销估计器。

5.4. 数据集和评估设置
我们在四种互补的设置下评估??1-HMM在RNA二级结构预测上的性能,这些设置旨在评估tRNA家族内的性能、在训练分布内的时间保留tRNA序列上的性能、在更广泛的RNA家族上的性能,以及超出领域范围的RNA家族上的性能。
首先,我们在策划的T-psi-C数据集[33]上评估模型,该数据集包含注释的tRNA序列。在这个数据集上,我们进行了两项评估:(i) 使用2024年之前发布的tRNA序列进行10折交叉验证的领域内评估;(ii) 在2024年之前发布的所有序列上训练模型,并在2024年发布的14个tRNA序列上进行评估的时间保留评估。
其次,为了评估超出相对tRNA家族的泛化能力,我们在RNAStralign上训练更广泛的家族模型,并在领域内测试分割和领域外的ArchiveII基准上进行评估。RNAStralign是一个广泛使用的RNA二级结构数据集,包含来自八个RNA家族的37,149个序列:16S rRNA、tRNA、5S rRNA、group I内含子(grp1)、SRP、tmRNA和端粒酶RNA。ArchiveII包含来自十个RNA家族的3975个序列,其中包括两个额外的家族:23S rRNAs和group II内含子(grp2),这些家族不在RNAStralign中表示。
在更广泛的家族实验中,我们遵循基于学习的RNA二级结构预测基准采用的一般数据处理协议,并排除伪结结构和长度超过600个核苷酸的序列,因为这些超出了本文的范围。预处理后,得到的数据集大小分别为:训练13,950个序列,验证2073个序列,领域内RNAStralign测试分割1439个序列,领域外ArchiveII测试集1119个序列。

5.5. 基线和评估协议
我们将我们的方法与CONTRAfold [34]、ViennaRNA(RNAfold MFE和centroid)[35]、LinearFold [36]、SPOT-RNA [37]、RNA-FM [38]、E2Efold [39]、MXfold2 [40]和KnotFold [41]进行比较。
对于2024年之前的T-psi-C基准,所有方法都在相同的10折交叉验证协议下进行评估,我们报告了各折叠的平均值±标准差(表1)。对于更广泛的家族评估,我们还在ArchiveII上报告了结果(表2)。
表1. 在tRNA基准上的方法性能比较。报告了在2024年之前的T-psi-C数据集上10折平均值的成对精度(P)、召回率(R)和F1分数。

5.6. tRNA基准测试的结果
如表1所总结的,我们的神经??1-HMM在tRNA上实现了强大的成对精度,尤其在精度和F1分数上与这里考虑的基线方法相比具有优势。这些结果表明,所提出的摊销参数推理框架在均匀的tRNA设置中非常有效。
为了阻止记忆常见的tRNA二级结构模式,我们构建了两个负面集:(i) 随机负面样本,其中对于每个tRNA长度L,我们通过从{??,??,??,??}中均匀采样每个核苷酸来生成一个序列;(ii) 混合负面样本,其中每个tRNA序列被随机打乱,保留了单核苷酸组成但破坏了生物结构。这些负面样本仅用于评估。我们的方法在混合负面样本上的成对核苷酸比率(PNRs)为0.223 ±0.005,在随机负面样本上为0.219 ±0.006,表明模型并不是简单地在任意序列上预测高配对率。
为了评估时间泛化能力,我们在2024年发布的14个tRNA序列上评估了模型,所有这些序列都未被用于训练和验证。??1-HMM在这个保留的集合上实现了精度=1.000、召回率=1.000和F1=1.000。尽管这个结果令人鼓舞,但应该谨慎解释,因为时间测试集较小且来自结构均匀的RNA家族。我们在图4中可视化了一个这样的预测,显示了与几个基线方法相比的高质量结构恢复。图4. 同一序列上的RNA二级结构预测的定性比较。(A) 真实值(GT)。(B) 我们的预测,它是唯一与GT相同的。(C) CONTRAfold。(D) RNAfold(ViennaRNA)。(E) ViennaRNA。(F)E2Efold。(G) KnotFold。(H) RNA-FM。(I) SPOT-RNA。(J) MXfold2。所有二级结构可视化都是使用R2DT [42]生成的。该序列来自T-Psi-C数据库2.0(条目tdbR00000239),这是时间测试集的一部分。

5.7. 在更广泛的RNA家族上的结果
我们使用更广泛的RNAStralign和ArchiveII基准进一步评估了所提出的方法。在领域内的RNAStralign测试分割上,我们的方法实现了精度=0.9820、召回率=0.9759和F1=0.9789。在领域外的ArchiveII基准上,表2显示我们的方法在F1分数上最強,同时保持了非常高的精度。这些结果共同表明,所提出的摊销??1-HMM框架不仅在更广泛的训练分布内具有竞争力,而且在结构多样化的RNA家族上也同样具有竞争力。图5展示了一个长16S rRNA示例(484 nt)的高碱基对精度(F1=0.9682),表明我们的模型能够捕捉长距离的碱基对相互作用。

5.6. 结论
我们提出了一种新颖的摊销推理流程,用于序列建模,该流程基于度为1的任意阶隐藏马尔可夫模型(??1-HMM)。通过神经估计器学习输入条件参数,我们的方法能够在单次前向传递中实现特定实例的概率建模,避免了昂贵的逐序列迭代参数估计,同时保持了结构化潜变量模型的可解释性。在RNA二级结构预测的背景下,我们的框架即使在具有挑战性的负面控制条件下也展示了高精度和鲁棒性,并提供了可解释的预测。尽管当前模型仅捕获了一阶影响(??1),未来的工作可以探索更高阶的依赖性(????,对于?? >1)来建模更丰富的长距离相互作用。重要的是,摊销推理通过提供高效的实例条件参数化使这样的扩展成为可能;补充的方向包括受限或近似的解码策略,以进一步提高超出??2(??3)最坏情况复杂性的可扩展性。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号