시퀀스 모델을 위한 정확한 제약 디코딩: 제어기 증강 은닉 마르코프 모델과 그 너머
Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond
한국어 초록
은닉 마르코프 모델은 순차 추론의 기반이 되지만, 선행 요건, 방문 횟수, 단조적 상태 진행과 같은 경로 단위 제약을 조건으로 부여하면 동적 계획법에 추가 메모리를 요구하는 장거리 의존성이 생길 수 있다. 이를 해결하기 위해 각 제약을 충분한 유한 이력을 추적하는 유한 상태 제어기로 컴파일하는 프레임워크인 제어기 증강 은닉 마르코프 모델(Controller-Augmented Hidden Markov Models, CHMM)을 제시한다. 이후 증강된 연쇄에 표준 순방향-역방향 및 비터비 재귀를 적용하면 이산 시간에서는 정확한 제약 사후 확률과 최대 사후 확률 경로를, 균등화(uniformization)를 통해 연속 시간에서는 관측 시점의 최대 사후 확률 증강 상태 시퀀스를 계산한다. 여러 이론적 보장을 확립하는 한편, 11개 제약 계열에 대한 제어기 인코딩 목록으로 프레임워크를 구체화한다. 실험에서는 \emph{Drosophila melanogaster}의 유전자 구조 디코딩, CASAS 스마트 홈의 자유 생활 활동 인식, 웨어러블 센서 기반의 프로토콜 정의 활동 인식이라는 3개의 실제 시퀀스 레이블링 과제에서 제어기 증강 유무에 따른 고전적 및 신경망 디코더를 평가한다. 이론과 실험을 종합하여 정확한 제어기 증강이 유용한 경우와 더 단순한 접근으로 충분한 경우를 규명한다.
원문 초록
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.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.13850v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.