跳到正文
返回论文列表
stat.ME提交于 已译

序列模型的精确约束解码:控制器增强隐马尔可夫模型及扩展

Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond

Lekha Patel · Luis Damiano

中文摘要

隐马尔可夫模型是序列推断的基础,但以路径约束(如优先级要求、访问基数或单调状态推进)为条件会引入长程依赖,需要额外内存进行动态规划。为此,提出控制器增强隐马尔可夫模型(CHMMs),将每个约束编译为跟踪充分有限历史的有限状态控制器,随后在增强链上使用标准前向-后向和 Viterbi 递归,在离散时间中计算精确约束后验和最大后验路径,并通过均匀化在连续时间中计算观测时刻的最大后验增强状态序列。建立若干理论保证的同时,11 个约束族的控制器编码目录使框架可操作。在 3 个真实序列标注任务上评估经典和神经解码器(有无控制器增强):黑腹果蝇基因结构解码、CASAS 智能家居自由生活活动识别、可穿戴传感器协议定义活动识别。理论与实验共同刻画了精确控制器增强何时有用、何时更简单方法已足够。

关键要点

  1. 01路径约束引入长程依赖,标准动态规划需额外内存,是精确约束解码的核心难点。
  2. 02将约束编译为有限状态控制器,在增强链上复用前向-后向与 Viterbi 递归实现精确解码。
  3. 03给出 11 个约束族的控制器编码目录,并建立若干理论保证。
  4. 04在果蝇基因结构、CASAS 智能家居、可穿戴传感器三个真实任务上验证有效性。
  5. 05理论与实验共同界定控制器增强的适用边界,简单方法在部分场景已足够。

解读

尚无解读。

原始英文摘要

arXiv:2606.13850v2 Announce Type: replace-cross Abstract: Hidden Markov models are foundational for sequential inference, yet conditioning on pathwise constraints such as precedence requirements, visitation cardinalities, or monotonic state progression can introduce long-range dependencies that require additional memory for dynamic programming. To deal with this, we present Controller-Augmented Hidden Markov Models (CHMMs), a framework that compiles each constraint into a finite-state controller tracking a sufficient finite history, after which standard forward--backward and Viterbi recursions on the augmented chain compute exact constrained posteriors and maximum a posteriori paths in discrete time and, through uniformization, maximum a posteriori augmented-state sequences at observation times in continuous time. While we establish several theoretical guarantees, a catalog of controller encodings for 11 constraint families operationalizes our framework. Empirically, we evaluate classical and neural decoders with and without controller augmentation on 3 real-world sequence-labeling tasks: gene-structure decoding in \emph{Drosophila melanogaster}, free-living activity recognition in CASAS smart homes, and protocol-defined activity recognition from wearable sensors. Together, theory and experiment characterize when exact controller augmentation is useful and when simpler approaches suffice.

同方向论文 · stat.ME

查看全部 →