arXiv：cs.LG· Markel Zubia, Nils Jansen·· 4 小时前AI 评分31
HMM 可识别性判定问题的计算复杂度研究
On the Computational Complexity of Hidden Markov Model Identification
AI 导读
研究隐马尔可夫模型（HMM）可识别性判定问题的计算复杂度，涵盖确定性、泛型、全局、局部、状态置换不变及有限字母表等多种可识别性定义。结果表明这些问题均可在 PSPACE 内判定，方法是通过归约到不同量词交替层级的实数理论。确定性变体在简单参数化族上已是 coETR-hard，因而也是 coNP-hard。
正文
Abstract:Identification is the task of recovering the parameters of an unknown ground-truth model from sampled data. When parameters other than the ground truth induce the same output distribution, data alone does not provide enough information to recover the ground truth, and the model is thus called unidentifiable. We study the identifiability problem for hidden Markov models (HMMs): given an HMM, is it identifiable? Existing work on HMM identification establishes conditions under which the ground-truth HMM can be identified. However, most of these conditions are sufficient but not necessary, meaning that, when a model does not satisfy them, its identifiability remains inconclusive. We instead take a computational perspective: is there a sound and complete algorithm that decides whether a given HMM is identifiable, and if so, what is the complexity of this decision problem? We consider the decision problems arising from the various notions of identifiability in the literature, including deterministic, generic, global, local, state-permutation- invariant, and finite-alphabet identifiability. We show that all of these problems are decidable in PSPACE, via reductions to the theory of the reals at various levels of its quantifier-alternation hierarchy. We further show that the deterministic variants are already coETR-hard (and hence coNP-hard) for simply parameterized families.
| Subjects: | Computational Complexity (cs.CC); Machine Learning (cs.LG); Statistics Theory (math.ST) |
| Cite as: | arXiv:2610.09104 [cs.CC] |
| (or arXiv:2610.09104v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09104 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Markel Zubia [view email]
[v1]
Tue, 6 Oct 2026 20:54:08 UTC (49 KB)
来源：arXiv：cs.LG · arxiv.org