Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models

Alexandre Mösching

doi:10.1080/10618600.2025.2572328

2025-12-01

PRE

Alexandre Mösching

Housen Li *

Axel Munk

DOI：10.1080/10618600.2025.2572328

原文链接

原文求助

摘要

En 中文

隐马尔可夫模型（HMMs）的特征是一个不可观测的马尔可夫链和一个可观测过程——隐藏链的噪声版本。从噪声观测中解码原始信号是几乎所有基于HMM的数据分析的主要目标之一。现有的解码算法，如Viterbi算法和逐点最大后验概率（PMAP）算法，其计算复杂度最多与观测序列的长度呈线性关系，与隐藏链的状态空间大小呈次二次关系。我们提出了一种名为Quick Adaptive Ternary Segmentation（QATS）的分治法，其计算复杂度与序列长度呈多项式对数关系，与状态空间大小呈立方关系，因此特别适用于具有相对较少状态的大规模HMM。它还提出了一种有效的数据存储方式，即特定的累积和。本质上，估计的状态序列依次在所有最多三个区间的局部路径中最大化局部似然得分，并且同时是可接受的。这种最大化仅通过自适应搜索过程近似完成。我们的模拟实验展示了QATS相较于Viterbi和PMAP提供的加速效果，并进行了精度分析。QATS的一个实现可在GitHub上的R软件包QATS中找到。本文的补充材料可在网上获取。

Keyword:

Hidden states

Local search

Massive data

Polylogarithmic runtime

Segmentation