은닉 마르코프 모델 식별의 계산 복잡도에 관하여
On the Computational Complexity of Hidden Markov Model Identification
한국어 초록
식별(Identification)은 샘플링된 데이터로부터 미지의 참(ground-truth) 모델의 매개변수를 복원하는 작업입니다. 참 모델이 아닌 다른 매개변수들이 동일한 출력 분포를 유도할 때, 데이터만으로는 참 모델을 복원하기에 충분한 정보를 제공하지 못하며, 이러한 모델을 식별 불가능(unidentifiable)하다고 부릅니다. 본 연구에서는 은닉 마르코프 모델(HMM)의 식별 가능성 문제를 다룹니다: 주어진 HMM은 식별 가능할까요? HMM 식별에 관한 기존 연구는 참 HMM이 식별될 수 있는 조건들을 제시합니다. 그러나 이러한 조건들 대부분은 필요조건이 아닌 충분조건이므로, 모델이 해당 조건을 만족하지 못할 경우 식별 가능성을 단정할 수 없습니다. 대신 우리는 계산적 관점을 취합니다: 주어진 HMM이 식별 가능한지 판별하는 건전하고 완전한(sound and complete) 알고리즘이 존재하는가, 존재한다면 이 결정 문제의 복잡도는 무엇인가? 우리는 문헌에 등장하는 결정적(deterministic), 제네릭(generic), 전역적(global), 국소적(local), 상태 순열 불변(state-permutation-invariant), 유한 알파벳(finite-alphabet) 식별 가능성을 포함한 다양한 식별 가능성 개념에서 발생하는 결정 문제들을 고려합니다. 우리는 한정 기호 교차(quantifier alternation) 계층 구조의 다양한 수준에서 실수 이론(theory of the reals)으로의 환원을 통해, 이 모든 문제들이 PSPACE 내에서 결정 가능함을 보입니다. 나아가 단순 매개변수화된 패밀리에 대해서도 결정적 변형 문제들이 이미 coETR-난해(따라서 coNP-난해)임을 보입니다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.