당신이 일련의 단서들을 바탕으로 비밀스러운 이야기를 추측하려고 한다고 상상해 보십시오. 당신에게는 가능한 캐릭터(상태)들의 지도와 그들이 한 곳에서 다른 곳으로 이동할 수 있는 규칙들이 주어져 있습니다. 이것이 바로 음성 인식부터 생물학에 이르기까지 모든 분야에서 사용되는 고전적인 도구인 **은닉 마르코프 모델(Hidden Markov Model, HMM)**의 역할입니다.

하지만 표준 HMM에는 사각지대가 있습니다. 이들은 오직 바로 다음 단계만을 바라봅니다. 전체 여정을 기억하지 못합니다. 이로 인해 다음과 같은 엄격한 "줄거리 규칙"이 있는 경우 문제가 발생합니다:

"대장간을 먼저 방문하기 전에는 성에 들어갈 수 없다." (선행 조건)
"시장을 정확히 세 번 방문해야 하며, 그 이상도 그 이하도 안 된다." (횟수 계산)
"주방을 떠나면 10분 동안 다시 돌아올 수 없다." (쿨다운/재사용 대기시간)

만약 이 규칙들을 표준 HMM에 강제로 적용하려 한다면, 모델이 규칙 위반 여부를 확인하는 데 필요한 이력을 기억하지 못하기 때문에 수학적 구조가 무너집니다.

해결책: "컨트롤러" 배낭

이 논문의 저자들은 **컨트롤러 증강 은닉 마르코프 모델(Controller-Augmented Hidden Markov Models, CHMM)**이라는 새로운 프레임워크를 소개합니다.

표준 HMM을 현재 위치의 지도만 가진 여행자라고 생각해 보십시오. 그들은 다음 단계를 추측하는 데는 뛰어나지만, 복잡한 규칙을 따르는 데는 서툽니다.

CHMM은 이 여행자에게 **배낭(컨트롤러)**을 쥐여줍니다.

배낭은 이력을 추적합니다: 당신이 특정 장소를 몇 번 방문했는지 세고, 특정 인물을 만났는지 기억하며, 쿨다운 기간을 위한 타이머를 작동시킵니다.
배낭은 똑똑합니다: 규칙을 확인하는 데 필요한 최소한의 정보만을 운반합니다. 우주의 모든 역사를 다 들고 다니는 것이 아니라, 제약 조건과 관련된 특정 "할 일 목록" 아이템들만 챙깁니다.
배낭은 문지기 역할을 합니다: 여행자가 발걸음을 옮기기 전, 배낭은 확인합니다: "지금까지 해온 일들을 고려했을 때, 이 움직임이 허용되는가?" 만약 그 움직임이 규칙을 어긴다면(예: 대장간을 가기 전에 성에 들어가는 것), 배방은 문을 쾅 닫아버립니다. 움직임이 안전하다면, 문을 열어줍니다.

이 배낭을 추가함으로써, 저자들은 이 복잡하고 규칙을 어기기 쉬운 문제를 표준적이고 해결하기 쉬운 수학 문제로 변모시켰습니다. 그들은 우리가 이미 사용하는 동일하고 효율적인 알고리즘(예: "전방-후방(Forward-Backward)" 및 "비테르비(Viterbi)" 방법)을 여전히 사용할 수 있음을 증명했습니다. 다만, 단순히 '여행자'가 아닌 '여행자 + 배낭' 조합에 대해 실행할 뿐입니다.

"국소적 vs 누적적" 발견

이 논문은 이 배방이 실제로 언제 필요한지에 대한 흥미로운 발견을 제시합니다. 저자들은 세 가지 매우 다른 실제 작업에서 여섯 가지의 다른 일반적인 해결 방식(단순 필터나 빔 서치 등)과 이 방법을 테스트했습니다.

초파리 유전자 디코딩 ("누적적" 사례):
- 과업: 초파리 유전자의 구조를 해독하는 것.
- 규칙: 유전자 부위들은 엄격한 순서(시작 -> 코딩 -> 종료)로 나타나야 하며, 각 부위는 정확히 한 번씩 나타나야 합니다.
- 결과: 다른 방법들은 처참하게 실패했습니다. 그들은 전체 시퀀스를 기억하지 못했기 때문에 "종료" 부분이 두 번 나타나거나 잘못된 순서로 나타났다고 계속 추측했습니다. CHMM(배낭을 가진 모델)은 시퀀스를 100% 완벽하게 유효하게 만들어낸 유일한 방법이었습니다.
- 비유: 이는 모든 조각을 정확히 한 번씩 사용해야 하는 퍼즐을 푸는 것과 같습니다. 만약 사용한 조각의 목록을 가지고 있지 않다면, 실수를 하게 될 것입니다.
스마트 홈 활동 ("국소적" 사례):
- 과업: 센서 데이터를 기반으로 스마트 홈 내의 사람(요리 중, 수면 중 등)이 무엇을 하고 있는지 추측하는 것.
- 규칙: 주로 "잠을 자는 상태에서 '깨어남' 단계를 거치지 않고 바로 '달리기'로 갈 수 없다"와 같은 단순한 규칙들입니다.
- 결과: 여기서 CHMM은 더 단순한 "배낭 없는" 방법들과 대등한 성능을 보였습니다. 규칙이 단순하여 다른 방법들도 바로 다음 단계만을 봄으로써 처리할 수 있었기 때문입니다.
- 비유: 규칙이 단순히 "절벽에서 뛰어내리지 마라"는 것이라면, 당신의 인생 전체를 기억할 배낭은 필요 없습니다. 그저 발 앞의 지면만 보면 됩니다.
웨어러블 활동 인식 ("하이브리드" 사례):
- 과업: 스마트 워치를 통해 인간의 움직임(접기, 쓸기, 걷기 등)을 식별하는 것.
- 규칙: 순서와 "중복 금지" 규칙이 혼합되어 있습니다.
- 결과: CHMM은 다른 방법들이 실패한 지점에서 다시 한번 성공하며, 규칙이 복잡해질 때 배낭이 필수적임을 입증했습니다.

이것이 왜 중요한가

논문은 세 가지 주요 사항을 주장합니다:

정확성: CHMM은 추측하거나 근사치를 구하지 않습니다. 그것이 내놓는 답이 모든 규칙을 따른다는 것을 수학적으로 보장합니다.
효율성: 배낭이 있음에도 불구하고 수학적 계산이 너무 무겁지 않습니다. 선형적으로 확장되므로, 즉 현실 세계에서 사용하기에 충분히 빠릅니다.
학습: 모델은 데이터로부터 학습하는 동안 새로운 규칙을 배울 수 있습니다. 만약 당신이 모델에게 "시장을 반드시 방문해야 한다"라고 알려준다면, 모델은 그 규칙을 준수하면서 동시에 이야기의 확률을 학습하며, 이는 규칙을 무시했을 때보다 더 나은 추측을 이끌어냅니다.

결론

저자들은 표준적이고 강력한 AI 도구들이 복잡하고 장기적인 규칙을 깨뜨리지 않고 따를 수 있게 해주는 보편적인 "어댑터(컨트롤러)"를 구축했습니다. 그들은 단순한 국소적 규칙에는 이 어댑터가 필요하지 않지만, 생물학적 서열이나 엄격한 프로토콜과 같이 복잡하고 누적적인 규칙의 경우에는 이것이 올바르고 유효한 답을 얻기 위한 유일한 방법임을 보여주었습니다. 이는 규칙을 잊어버려 길을 잃는 여행자와, 똑똑한 배낭을 메고 절대 실수하지 않는 여행자의 차이와 같습니다.

기술 요약: 컨트롤러 증강 은닉 마르코프 모델 (Controller-Augmented Hidden Markov Models)

문제 정의

은닉 마르코프 모델(HMM)은 확률적 순차 모델링의 기초로서, 마르코프 가정을 통해 수학적 추적 가능성(tractability)을 제공한다. 그러나 이 가정은 순차적 프로세스가 메모리리스(memoryless) 특성과 호환되지 않는 장거리 의존성을 유발하는 **전역적 경로 제약(global pathwise constraints)**에 의해 지배될 때 근본적인 한계가 된다. 이러한 제약은 다음과 같은 다양한 도메인에서 빈번하게 나타난다:

시간 및 지속 시간 요구사항: 최소 관측 기간, 쿨다운(cool-down) 기간, 명시적 지속 시간 모델링.
선후 관계 및 순서: 로보틱스, 조립 계획, 임상 중재에서의 작업 시퀀싱.
안전 및 상호 배제: 자율 시스템 및 안전한 강화 학습에서의 제약 조건.
논리 및 카운팅 속성: $k$ -세그먼트 제약, 단조성 요구사항, 생물학적 서열의 구조적 제약.

기존의 제약된 추론 방식은 내재적인 한계를 겪는다: 사후 필터링(post-hoc filtering)은 실행 불가능한 궤적에 자원을 낭비하며, 모델 수정(예: 세미-마르코프 모델)은 일반적인 논리적 제약을 처리하는 데 실패하는 경우가 많고, 근사 방법(입자 필터, 빔 서치)은 정확성 보장을 희생하며, 판별 모델(CRF)은 로컬 클리크 특징에 의존하기 때문에 누적된 경로 속성을 표현하는 데 어려움을 겪는다. 결과적으로, 임의의 유한 메모리 경로 제약 하에서 정확한 확률적 추론과 파라미터 학습을 수행할 수 있는 통합된 프레임워크가 부재한 실정이다.

방법론: 컨트롤러 증강 은닉 마르코프 모델 (CHMMs)

본 논문은 **컨트롤러 증강 은닉 마르코프 모델(CHMM)**을 소개하며, 이는 제약이 있는 비-마르코프 문제를 증강된 상태 공간 상의 제약 없는 마르코프 문제로 변환하는 프레임워크이다.

핵심 구성

이 프레임워크는 결정적 유한 상태 컨트롤러를 설계하기 위해 **감독 제어 이론(supervisory control theory)**에 의존하며, 이 컨트롤러는 제약 만족을 검증하는 데 필요한 최소한의 충분한 이력(minimal sufficient history)을 추적한다.

컨트롤러 사양: 튜플 $(C, c_0, \tau, F, F_T)$ $(C, c_{0}, τ, F, F_{T})$ 는 다음을 정의한다:
- $C$ : 유한 컨트롤러 상태 공간.
- $c_0$ : 초기 은닉 상태를 컨트롤러 상태로 매핑하는 초기화 함수.
- $\tau$ : 결정적 업데이트 규칙 $C_{t+1} = \tau(C_t, X_t, X_{t+1}, t)$ .
- $F$ : 현재 컨트롤러 상태에서 로컬 제약을 위반하는 전이를 차단하는 게이팅(gating) 함수.
- $F_T$ : 궤적의 끝에서 누적 제약이 충족되었는지 확인하는 터미널 수용 집합.
증강 상태 공간: 은닉 상태는 $\tilde{X} = X \times C$ 로 증강된다. 시스템은 제약을 위반하는 전이가 흡수적인 데드 상태( $\perp$ )로 이어지는 "킬드(killed)" 마르코프 체인으로서 진화한다.
마르코프화(Markovianization): 정리 2.3은 이 구성이 증강된 공간에서 마르코프 성질을 보존하면서 제약을 정확하게 강제함을 증명한다. 제약된 사후 확률은 궤적이 데드 상태에 진입하지 않고 수용되는 컨트롤러 상태에서 종료된다는 사건에 조건부로 계산된다.

알고리즘 프레임워크

추론: 표준 동적 계획법 알고리즘(Forward-Backward 및 Viterbi)이 증강 커널 $\tilde{P}$ $\tilde{P}$ 에 직접 적용된다.
- 이산 시간: 재귀는 $\tilde{P}$ 상에서 작동하며, 터미널 합은 수용 집합 $F_T$ 로 제한된다.
- 연속 시간: 이 프레임워크는 킬드 생성자(killed generator) $\bar{Q}$ 의 **유니포미제이션(uniformization)**을 통해 연속 시간 HMM(CT-HMM)으로 확장된다.
파라미터 학습: 제약된 기대-최대화(EM) 알고리즘이 유도된다.
- E-단계: 증강된 체인 상에서 평활화된 한계값(smoothed marginals)을 계산한다.
- M-단계: 컨트롤러 차원을 주변화하여 기본 파라미터( $\nu, P, B$ 또는 $Q$ )를 업데이트한다. 게이팅 함수는 업데이트의 서포트(support)를 자연스럽게 제한하여, 패널티 항을 통한 방식이 아닌 구조적 설계를 통해 제약이 강제되도록 보장한다.
- 수렴: 정리 3.2는 제약된 EM 절차가 제약된 한계 로그 가능도(marginal log-likelihood)를 단조 증가시킨다는 것을 확립한다.

제약 카탈로그

본 논문은 다음을 포함한 11가지 제약 패밀리에 대한 컨트롤러 인코딩의 체계적인 카탈로그를 제공한다:

순서(Ordering): 선후 관계( $a \prec b$ ), 단계적 단조성.
방문(Visitation): 특정 집합에 대한 최소/최대/정확히- $K$ 번의 방문.
경로(Path): $K$ -전이 제한, 모든 요소가 서로 다른(all-different) 제약.
시간(Temporal): 체류 금지(no-dwell), 재진입 금지(no-reentry), 쿨다운 기간.
실제적인 제약의 경우 추론 복잡도는 컨트롤러 카디널리티 $|C|$ 에 선형적으로 비례하며, 이는 대부분의 실제적인 제약(예: 방문 횟수 $O(K)$ )에 대해 완만한 수준이다.

주요 기여

정확성에 대한 이론적 보장: 컨트롤러 증강이 마르코프 성질을 보존하면서 동시에 유한 메모리 경로 제약을 강제한다는 것을 증명하여, 표준 알고리즘을 통한 정확한 추론을 가능하게 한다.
체계적 인코딩 방법론: 다양한 응용 도메인을 위해 즉시 사용 가능한 컨트롤러 인코딩을 포함한 11가지 제약 패밀리의 카탈로그를 제공하여 프레임워크를 구체화한다.
알고리즘적 완전성: 정확성, 단조 증가 수렴성 및 다항 시간 복잡도 경계에 대한 증명을 동반하여, 이산 및 연속 시간 모두에 대한 forward-backward, Viterbi 및 제약된 EM 절차를 개발하였다.
강건성 분석: 제약 미스스펙으로 인한 제약된 사후 확률에 대한 총 변동(total-variation) 상한을 설정하여, 지정된 제약 집합과 실제 제약 집합 사이의 편차를 정량화한다.
경험적 이분법: "로컬 대 누적(local-versus-cumulative)" 이분법을 식별하여, 컨트롤러 증강이 누적 제약 체제(예: 선후 관계 체인, 정확한 카디널리티)에는 독보적으로 필요하지만, 로컬이 지배적인 체제에서는 더 단순한 로컬 프루닝 디코더로도 충분함을 입증한다.

실험 결과

프레임워크는 합성 데이터와 세 가지 실제 시퀀스 레이블링 태스크에 대해 평가되었다:

합성 데이터: 제약 완결성, 미스스펙 상한, 파라미터 회복에 관한 이론적 주장을 검증하였다. 제약된 EM은 제약 위반 경로로 인한 로컬 옵티마 문제를 피함으로써 unconstrained Baum-Welch보다 우수한 파라미터 회복과 빠른 수렴을 보여주었다.
초파리 유전자 구조 디코딩 (누적 체제):
- 태스크: 엄격한 선후 관계 및 정확히 하나만 진입해야 하는 카디널리티 제약이 있는 유전자 구조(UTR5, START, CDS, STOP, UTR3) 디코딩.
- 결과: CHMM은 **100% 시퀀스 수준 궤적 유효성(TVRseq)**을 달성한 반면, 모든 베이스라인(재입력을 포함한 빔 서치 및 CRF 포함)은 전역 제약을 만족하는 데 실패했다(CRF/BSR의 TVRseq = 0). CHMM은 가장 강력한 확률적 베이스라인보다 정확도에서 7.7%, segment-F1에서 11.5% 더 높은 성능을 보였다.
CASAS 스마트 홈 활동 인식 (로컬 체제):
- 태스크: 주로 로컬 엣지 허용 가능성과 제한된 히스토리를 가진 재진입 금지에 의해 제어되는 활동 디코딩.
- 결과: CHMM은 TVRseq = 1을 달 달성했으나, 정확도와 macro-F1 측면에서는 재입력 포함 빔 서치(BSR)와 대등한 성능을 보였다. 이는 로컬 제약의 경우, 정확한 증강을 위한 계산 오버헤드가 성능을 위해 반드시 필수적인 것은 아니지만, 유효성을 보장한다는 점을 확인시켜 준다.
인간 활동 인식 (HAR) (중간 체제):
- 태스크: 순서 및 재진입 금지 제약이 있는 프로토콜 정의 활동 체인.
- 결과: CHMM은 유일하게 TVRseq = 1을 달성했으며, segment-F1 점수가 베이스라인보다 거의 3배 높았다. 제약된 EM 학습은 제약 위반을 명시적으로 처벌하지 않는 지표로 평가하더라도 unconstrained EM보다 훨씬 높은 디코딩 정확도를 얻었다.

의의 및 주장

본 논문은 임의의 유한 메모리 경로 제약 하에서의 HMM 추론에 대한 최초의 통합적 취급을 제공한다고 주장한다. 이 연구의 의의는 다음과 같다:

간극 해소: 이전에 근사치나 사후 필터링으로만 처리되었던 제약들에 대해 정확한 추론과 파라미터 학습을 통합한다.
원칙적인 트레이드오프 제시: 정확한 컨트롤러 증강이 필요한 시점(누적 제약)과 더 단순한 접근법이 충분한 시점(로컬 제약)을 명확히 구분하여 계산적, 경험적 트레이드오프를 규명한다.
구조적 충실도: 제약 조건을 소프트 패널티를 통해 적용하는 대신 구조적으로 강제함으로써, 디코딩된 궤적이 전역적으로 실행 가능하다는 것을 보장한다. 이는 안전이 중요하거나 과학적으로 엄밀함이 요구되는 응용 분야에서 필수적이다.
확장성: 컨트롤러 크기에 따라 다항식으로 스케일링되는 복잡도를 보장함으로써, 복잡한 도메인 지식을 가진 실제 문제에도 적용 가능하도록 하여 제약된 추론이 계산적으로 실행 가능함을 보장한다.

저자들은 CHMM을 기존의 모든 방법을 대체하는 것이 아니라, 전역적 경로 속성의 정확한 강제가 필요한 특정 영역을 위한 원칙적인 솔루션으로 제안하며, 휴리스틱이나 근사 전략에 대한 엄격한 대안을 제시한다.

Controller-Augmented Hidden Markov Models: A Computational Framework for Constrained Sequential Inference