17. Markov and hidden Markov models

17.1. Introduction

이 장에서는 임의 길이의 이산적으로 연속된 관찰 X_{1}, \cdots, X_{T}에 대한 확률적 모델을 다룬다.

17.2. Markov models

마르코프 연쇄의 기본 발상은 X_{t}가 미래를 예측하는 데 있어 충족 통계량이란 것이다. 이산적 시간 단계를 가정한다면 결합분포를 다음과 같이 쓸 수 있다:

p(X_{1:T}) = p(X_{1}) \prod_{t=2}^{T} p(X_{t} | X_{t-1})

이를 마르코프 연쇄 또는 마르코프 모델이라 한다.

전이 함수 p(X_{t} | X_{t-1})이 시간에 독립적이라 가정한다면 이 연쇄는 상동성, 정지, 시간 불변이라 불리며 이는 매개변수 공유의 예이다. 이 가정은 임의의 갯수만큼의 변수를 고정된 크기의 매개변수만으로 모델링할 수 있게 해 준다. 이런 모델을 추계적 과정이라 한다.

관찰된 변수가 이산적이라면 이를 이산 상태 또는 유한 상태 마르코프 연쇄라 한다. 이 절에서는 이를 가정한다.

17.2.1. Transition matrix

X_{t}가 이산적이면 p(X_{t} | X_{t-1})K \times K의 크기를 가지며 원소가 A_{ij} = p(X_{t} = j | X_{t-1} = i)이 되는 전이 행렬 \mathbf{A}로 나타내어질 수 있다. 이 때 행렬의 각 행은 원소들의 합이 1이 되므로 이를 추계적 행렬이라 부른다.

고정된, 유한 상태 마르코프 연쇄는 추계 오토마톤과 같으며 노드가 상태를, 화살표가 영이 아닌 전이를 나타내는 방향그래프로 시각화할 수 있다. 이를 상태 전이 도형이라 하며 그래프 내 노드에 연관된 가중치는 해당 상태 전이의 확률이 된다. 전이 행렬이 상삼각행렬일 경우 (즉, 되돌아가는 상태가 없는 경우)를 좌-우 전이 행렬이라 한다.

n단계 전이 행렬 \mathbf{A}(n)A_{ij}(n) = p(X_{t+n} = j | X_{t} = i)로 정의되며, 채프먼-콜모고르프 식에 의해 A_{ij}(m + n) = \sum_{k=1}^{K} A_{ik}(m) A_{kj}(n)이 성립한다. 이는 행렬곱 \mathbf{A}(m+n) = \mathbf{A}(m) \mathbf{A}(n)로 볼 수 있으며, 그러므로 \mathbf{A}(n) = \mathbf{A}^{n}이다.

17.2.2. Application: Language modeling

마르코프 모델의 중요한 응용은 단어의 나열에 대한 확률분포인 통계적 언어 모델이다. 주변확률 p(X_{t} = k)유니그램 통계량으로 불린다. 1차 마르코프 모델에서 p(X_{t} = k | X_{t-1} = j)바이그램 모델이 된다. 2차 마르코프 모델에서 p(X_{t} = k | X_{t-1} = j, X_{t-2} = i)트리그램 모델이다. 일반적으로는 n-그램 모델이라 불린다. 언어 모델은 다음과 같은 용례가 있다.

  • 문장 완성 : 문장의 앞 단어들에 기반해 다음 단어를 예측
  • 데이터 압축 : 문자열을 짧은 코드워드로 압축
  • 텍스트 분류 : 텍스트를 분류. 0-그램 모델은 나이브 베이즈 분류기가 된다.
  • 자동 수필 쓰기 : 모델로부터 추출된 인공적인 텍스트 생성
<종의 기원>에 대한 유니그램-바이그램 모델.

17.2.2.1 MLE for Markov language models

학습 데이터에서 전이 행렬을 추적하는 방법을 알아보자. 임의의 길이 T의 확률은 p(x_{1:T} | \mathbf{\theta}) = \pi(x_{1}) A(x_{1}, x_{2}) \cdots A(x_{T-1}, x_{T}) = \prod_{j=1}^{K} (\pi_{j})^{\mathbf{1}_{x_{1} = j}} \prod_{t=2}^{T} \prod_{j=1}^{K} \prod_{k=1}^{K} (A_{jk})^{\mathbf{1}_{x_{t} = k, x_{t-1} = j}}이 된다.

따라서 각각의 길이 T_{i}의 문장 \mathbf{x}_{i} = (x_{i1}, \cdots, x_{i, T_{i}})이 모인 학습 데이터셋 \mathcal{D} = (\mathbf{x}_{1}, \cdots, \mathbf{x}_{N})에 대한 로그가능도는 N_{j}^{1} = \sum_{i=1}^{N}, \mathbf{1}_{x_{i1} = j}, N_{jk} = \sum_{i=1}^{N} \sum_{t=1}^{T_{i} - 1} \mathbf{1}_{x_{i, t} = j, x_{i, t + 1} = k}으로 둘 때 p(\mathcal{D} | \mathbf{\theta}) = \sum_{i=1}^{N} \log p(\mathbf{x}_{i} | \mathbf{\theta}) = \sum_{j} N_{j}^{1} \log \pi_{j} + \sum_{j} \sum_{k} N_{jk} \log A_{jk}으로 주어진다.

따라서 표준화된 계수에 대한 최대가능도추정은 \hat{\pi}_{j} = \frac{N_{j}^{1}}{\sum_{j^{\prime}} N_{j^{\prime}}^{1}}, \hat{A}_{jk} = \frac{N_{jk}}{\sum_{k^{\prime}} N_{jk^{\prime}}}이다.

위의 결과는 고차 마르코프 모델에 대해 쉽게 확장될 수 있으나 상태의 수와 상태의 길이가 많아질 수록 0 카운트 문제가 커진다는 문제가 있다. 쉬운 해결책은 1 더하기 다듬질을 하는 것이지만 이는 모든 n-그램의 확률이 같다는 비현실적 가정이 들어간다. 그냥 데이터를 많이 모으는 것도 방법이기는 하지만, 아래에서는 조금 더 복잡한 베이지안적 접근법을 다룬다.

17.2.2.2. Empirical Bayes version of deleted interpolation

데이터 희소 문제를 푸는 널리 알려진 휴리스틱은 삭제 보간법이다. 이는 전이 행렬을 바이그램 f_{jk} = \frac{N_{jk}}{N_{j}}과 유니그램 f_{k} = \frac{N_{k}}{N}의 볼록결합 A_{jk} = (1- \lambda)f_{jk} + \lambda f_{k}으로 나타내는 것이며 \lambda는 교차검증으로 세팅된다. 이는 백오프 다듬질이라는 또 다른 테크닉과도 관련이 있다. 이는 f_{jk}가 지나치게 작을 경우 f_{k}라는 추정으로 후퇴하는 발상에 근거한다.

이제 간단한 계층적 베이지안 모델을 통한 삭제 보간법 휴리스틱이 왜 예측값에 대한 근사가 되는지 알아보자. 먼저 전이 행렬의 각 행에 대해 독립적인 디리클레 사전분포 \mathbf{A}_{j} \sim \mathrm{Dir}(\alpha_{0} m_{1}, \cdots, \alpha_{0} m_{K}) = \mathrm{Dir}(\alpha_{0} \mathbf{m}) = \mathrm{Dir}(\mathbf{\alpha})을 정의한다. (\mathbf{A}_{j}는 전이 행렬의 j번째 행, \mathbf{m}은 사전평균으로 \sum_{k} m_{k} = 1을 만족, \alpha_{0}은 사전분포의 세기)

이때 사후분포는 \mathbf{N}_{j} = (N_{j1}, \cdots, N_{jK})이 상태 j로부터 다른 상태로 변환된 횟수라고 할 때 \mathbf{A}_{j} \sim \mathrm{Dir}(\mathbf{\alpha} + \mathbf{N}_{j})이 된다. 사후예측분포는 \bar{A}_{jk} = \mathbb{E}[A_{jk} | \mathcal{D}, \mathbf{\alpha}]이고 \lambda_{j} = \frac{\alpha_{j}}{N_{j} + \alpha_{0}}일 때 p(X_{t+1} = k | X_{t} = j, \mathcal{D}) = \bar{A}_{jk} = (1 - \lambda)f_{jk} + \lambda_{j} m_{k}이 된다.

이는 위의 식과 비슷하지만 같지는 않다. 주변빈도 f_{k} 대신 사전평균 m_{k}와 실측 빈도 f_{jk}를 고정된 가중치 \lambda가 아닌 컨텍스트 의존 가중치 \lambda_{j}로 결합하기 때문이다. 이를 적응적 삭제 보간법이라 한다.

남은 질문은 \alpha\mathbf{m}에 대해 어떤 값을 써야하는가이다. 이에 대해서는 실측 베이스를 써 보자. 전이 행렬의 각 행이 독립이라고 가정했으므로, 마르코프 모델에 대한 주변가능도는 p(\mathcal{D} | \mathbf{\alpha}) = \prod_{j} \frac{B(\mathbf{N}_{j} + \mathbf{\alpha})}{B(\mathbf{\alpha})}가 된다. 이를 이용해서 직접적으로 모델을 피팅할 수도 있고, m_{k} \propto \lvert \{j : N_{jk} > 0\}\rvert의 근사를 이용할 수도 있다. 이는 단어 k의 사전확률은 그 단어가 등장하는 횟수 자체보다는 단어가 몇 개의 서로 다른 컨텍스트에 등장하는지에 따른다는 것을 나타낸다.

실제로는 이보다 보간 네세르-네이 모델이 좋다. 하지만 그를 뛰어넘는 비매개변수 베이지안 모델도 존재한다.

17.2.2.3. Handling out-of-vocabulary words

위의 다듬질 방법은 완전히 새로운 단어가 테스트 셋에 등장하는 경우 (고유명사 등)에 대처하지 못한다. 또한, 어휘의 풀이 고정되어 있고 알려져 있음을 가정하고 있다. 이에 대처하는 휴리스틱은 새로운 단어를 특수 심볼 미지(unk)에 대응시키는 것이다. 또는 새로운 단어가 충분히 많이 등장하면 데이터 공간을 확장하는 디리클레 과정을 쓸 수도 있다.

17.2.3. Stationary distribution of a Markov chain

마르코프 모델은 연속된 관찰에 대한 결합확률분포로 볼 수도 있지만 추계쩍 동역학계로 볼 수도 있다. 이 경우 장기적 관점에서의 상태 분포, 즉 연쇄의 정지 분포가 많은 탐구 대상이 된다.

17.2.3.1. What is a stationary distribution?

A_{ij} = p(X_{t} = j | X_{t-1} = i)이 1단계 전이 행렬이라 하고 \pi_{t}(j) = p(X_{t} = j)가 시각 t에서 상태 j일 확률이라 하자. \mathbf{\pi}는 행벡터라 가정하자. 초기 상태 분포 \mathbf{\pi}_{0}에 대해 시각 1에서는 \mathbf{\pi}_{1} = \mathbf{\pi}_{0} \mathbf{A}이 된다. 이를 반복해 언젠가 \mathbf{\pi} = \mathbf{\pi}\mathbf{A}이 된다면 정지 분포(불변 분포, 평형 분포)에 도달했다고 한다. 위의 식을 풀면 \pi_{i} \sum_{j \neq i} A_{ij} = \sum_{j \neq i} \pi_{j} A_{ji}이 된다. 즉, 상태 i에 있을 확률에 상태 i에서 변화하는 확률을 곱하면 상태 i에 있지 않을 확률과 상태 i로 변화하는 확률을 곱한 것과 같아야 한다. 이를 전역 평균식이라 하며 이 방정식은 \sum_{j} \pi_{j} = 1 조건에 대해 풀 수 있다.

17.2.3.2. Computing the stationary distribution

정지 분포를 찾기 위해서는 고유벡터 \mathbf{A}^{T} \mathbf{v} = \mathbf{v}을 푼 뒤에 \mathbf{\pi} = \mathbf{v}^{T}로 놓는다. (이런 고유벡터는 \mathbf{A}가 행-추계 행렬이기 때문에 존재성이 보장된다) 다만 이런 고유벡터가 실벡터이기 위해서는 0 < A_{ij} < 1이어야 한다는 조건이 있다. 이를 풀기 위해선, \mathbf{\pi} (\mathbf{I} - \mathbf{A}) = \mathbf{0}, \mathbf{\pi} \mathbf{1} = 0이라는 식을 풀면 된다. 미지수가 K개에 조건식이 K+1개이므로 \mathbf{I} - \mathbf{A}의 한 열을 \mathbf{1}로 교체한 뒤 이를 풀면 된다. 안타깝게도, 모든 연쇄에 대해 정지 분포가 존재하는 것은 아니다.

17.2.3.3. When does a stationary distribution exist?

정지 분포는 언제 존재하는가? 흡수 상태 (항상 되풀이되는 상태)가 있는지 직접 시험해 볼 수도 있지만, 우선 유일한 정지 분포가 존재하기 위한 최소한의 필요 조건은 상태 전이 도형이 단일 연결 컴포넌트임을 이용하면 좋다. 이런 연쇄는 기약이라 한다.

다음을 정의하자: \pi_{j} = \lim_{n \to \infty} A_{ij}^{n}이 모든 j에 대해 i와 독립적으로 존재한다면 연쇄가 극한 분포를 갖고 있다고 한다. 이것이 성립한다면 상태에 대한 장기적 분포는 시작 상태에 독립적이 되어 t \to \inftyP(X_{t} = j) = \sum_{i} P(X_{0} = i) A_{ij}(t) \to \pi_{j}가 된다.

그래서 이 극한 분포는 언제 존재하는가? 상태 i의 주기d(i) = \mathrm{gcd}\{t : A_{ii}(t) > 0 \} (gcd는 최대공약수)라 하고 주기가 1일 때를 비주기적이라 하자. 모든 상태가 비주기적이면 연쇄를 비주기적이라 하자. 이 때 다음이 성립한다:

Theorem. 모든 기약 (단일 연결), 비주기적 유한 상태 마르코프 연쇄는 극한 분포가 존재하며, 이것은 그의 유일한 정지 분포 \mathbf{\pi}와 같다.

임의의 상태에서 다른 상태로 n번 안에 갈 수 있는 상한 n이 존재하는 연쇄를 정칙 연쇄라 하는데, 모든 정칙 상태 연쇄는 유일한 정지 분포를 갖는다. 정칙 연쇄이기 위한 충분조건으로 연쇄가 기약이고 모든 상태가 같은 상태로 되돌아오는 것이 가능함이 있다.

상태 공간이 유한이 아닌 마르코프 체인에 대해서는 정의를 보다 확장해야 하는데, 각 상태가 재귀적일 것까지 요구한다. 재귀적이지 않은 상태라면, 즉 단기적이라면 그 상태로 돌아갈 방법이 없으므로 정지 분포가 존재하지 않는 것이 당연하다. 유한 상태 가역 연쇄는 당연히 재귀적이다. 또한 재귀적인 것만으로는 불충분한데, 상태에서 되돌아오는 기대 시간이 유한인 널이 아닌 재귀적 상태임을 요구한다. 비주기적이고, 널이 아닌 재귀적인 연쇄를 에르고딕이라 하자. 그러면 다음이 성립한다.

Theorem. 모든 기약 에르고딕 마르코프 연쇄는 극한 분포가 존재하며, 이는 그의 유일한 정지 분포 \mathbf{\pi}과 같다.

이는 아까 나온 정리의 일반화이다.

17.2.3.4. Detailed balance

에르고딕성을 보이는 것은 어려우므로 더 쉽게 증명할 수 있는 다른 조건을 찾아보도록 하자.

마르코프 연쇄 \mathbf{A}에 대해 상세 균형식 \pi_{i} A_{ij} = \pi_{j} A_{ji}을 만족하는 분포 \mathbf{\pi}가 있으면 이를 시간 가역적이라 한다. 이는 상태 i에서 j로의 흐름이 가중치 보정을 할 경우 상태 j에서 i로의 흐름과 동치임을 의미한다. 여기서 다음 결과를 얻는다.

Theorem. 전이 행렬 \mathbf{A}를 가진 마르코프 연쇄가 정칙이고 분포 \mathbf{\pi}에 대해 상태 균형식을 만족한다면, \mathbf{\pi}는 연쇄의 정지 분포이다.

이는 충분조건이지 필요조건은 아니다. 전이 행렬은 전이 커널로도 불린다.

17.2.4. Application: Google’s PageRank algorithm for web page ranking

구글의 페이지랭크 알고리즘은 정지 분포 이론의 중요한 용례이다. 기본 아이디어는, 웹을 거대한 방향그래프로 보고 웹 크롤링을 하는 것이다. 이후 웹 페이지 내 모든 단어는 뒤집힌 인덱스라는 자료구조에 넣어진다. 즉, 모든 단어에 대해 이 단어가 등장하는 문서의 리스트를 저장하고 문서를 연관성/점수가 감소하는 순서대로 순위를 매긴다. 단어의 등장 빈도 뿐만 아니라 페이지의 권위 (링크된 수)도 저장하는데, 링크 파밍을 막기 위해 가중치를 둔다.

PageRank 알고리즘을 수행한 예제. 히스토그램/웹 그래프/페이지랭크 벡터.

17.2.4.1. Efficiently computing the PageRank vector

페이지간 전이에 대해 n을 페이지 수, \delta = \frac{1 - p}{n}을 한 페이지에서 다른 페이지로 링크 없이 점프할 확률, c_{j} = \sum_{i} G_{ij}를 페이지 j의 외차수라 할 때 다음의 전이 행렬이 정의된다:

c_{ij} > 0이면 M_{ij} = p \frac{G_{ij}}{c_{j}} + \delta, c_{ij} = 0이면 M_{ij} = \frac{1}{n}

이 때 \mathbf{M}은 열-추계 행렬이 되며 대각 행렬 \mathbf{D} = \mathrm{diag}(\frac{1}{c_{j}})z_{j} = \mathbf{1}_{c_{j} \neq 0}\delta + \mathbf{1}_{c_{j} = 0}\frac{1}{n}로 정의되는 벡터 \mathbf{z}에 대해 \mathbf{M} = p\mathbf{G}\mathbf{D} + \mathbf{1} \mathbf{z}^{T}이 성립한다. 이 행렬은 희소행렬이 아닌 대신 희소행렬의 랭크 1 업데이트이며 이 업데이트는 대부분 작은 상수 \delta에 의해 이루어진다.

우리의 목표는 \mathbf{v} = \mathbf{\pi}^{T}일 때 \mathbf{v} = \mathbf{M}\mathbf{v}을 푸는 것인데 이는 제곱법으로 푼다.

17.2.4.2. Web spam

페이지랭크 알고리즘은 완벽하지 않으며 검색 엔진 최적화 또는 웹 스팸에 당하기도 한다. 이는 인위적으로 가중치를 낮추는 방식으로 대응하지만, 자동적으로 감지할 수도 있다. 그 방법은 이 책범위를 넘어선다.

17.3. Hidden Markov models

은닉 마르코프 모델(HMM)은 은닉 상태 z_{t} \in \{1, \cdots, K \}과 그에 대한 관찰 p(\mathbf{x}_{t} | z_{t})로 이루어진 이산 시간의 이산 상태 마르코프 연쇄이다. 그에 해당하는 결합분포는 p(\mathbf{z}_{1 : T} | \mathbf{x}_{1:T}) = p(\mathbf{z}_{1:T}) p(\mathbf{x}_{1:T} | \mathbf{z}_{1: T}) = [p(z_{1}) \prod_{t=2}^{T} p(z_{t} | z_{t-1})] [\prod_{t=1}^{T} p(\mathbf{x}_{t} | z_{t})]의 형태가 된다.

은닉 마르코프 모델의 은닉 상태는 이산적이지만 그에 대한 관찰은 이산적일 수도 있고 연속적일 수도 있다. 이산적인 경우에는 관찰 모델을 관찰 행렬 p(\mathbf{x}_{t} = l | z_{t} = k, \mathbf{\theta}) = B_{kl}로 잡는다. 연속적인 경우에는 관찰 모델을 조건부 가우시안 p(\mathbf{x}_{t} | z_{t} = k, \mathbf{\theta}) = \mathcal{N}(\mathbf{x}_{t} | \mathbf{\mu}_{k}, \mathbf{\Sigma}_{k})로 잡는다. 이는 가우시안 혼합 모델과 비슷하지만 클러스터가 마르코프 역학계를 따른다는 것이 다르다. 그래서 이는 마르코프 치환 모델이라고도 불린다.

3상태 은닉 마르코프 모델에서의 샘플링 / 은닉 상태 서열.

17.3.1. Applications of HMMs

은닉 마르코프 모델은 연속된 확률변수에 대한 블랙박스 밀도 모델로 쓰인다. 이들은 일반 마르코프 모델에 비해 잠재 변수에 의해 은닉되는 장기적 관점에서의 관찰 간 의존성을 표현할 수 있다는 이점이 있다. 또한, 관찰 자체에 대해서는 마르코프 특성을 필요로 하지 않는다. 생성적 분류기에 대한 클래스 조건부 분포를 정의할 수도 있고, 관찰로부터 은닉 상태를 추정할 수도 있다. 이 때 온라인 학습에서는 p(z_{t} | \mathbf{x}_{1:t})를, 오프라인 학습에서는 p(z_{t} | \mathbf{x}_{1:T})를 쓴다. 용례들은 다음과 같다.

  • 자동 발화 감지. \mathbf{x}_{t}은 발화 신호로부터 추출되는 특성들을, z_{t}은 말해진 단어들을 나타낸다. 전이 모델 p(z_{t} | z_{t-1})은 언어 모델을, 관찰 모델 p(\mathbf{x}_{t} | z_{t})은 청각 모델을 나타낸다.
  • 활동 감지. \mathbf{x}_{t}은 비디오 프레임에서 추출된 특성들을, z_{t}은 해당하는 사람의 활동을 나타낸다.
  • 발화 부분 태깅. x_{t}는 단어를, z_{t}는 그 단어의 발화 내 부분 (명사, 동사, 목적어 등)을 나타낸다.
  • 유전자 찾기. x_{t}는 DNA 염기를, z_{t}는 유전자 암호화 지역 여부를 나타낸다.
  • 단백질 서열 배치. x_{t}는 아미노산을, z_{t}는 이 아미노산이 이 영역에서 잠재 컨센선스 서열에 들어맞는지를 나타낸다. 이는 프로파일링 은닉 마르코프 모델이라고도 한다.

위 용례 중 일부에서는 은닉 마르코프 모델의 구별적 버전인 조건부 무작위 장이 더 적절할 수도 있다.

17.4. Inference in HMMs

매개변수를 알 때 은닉 마르코프 모델의 은닉 상태는 어떻게 추론할 수 있을까? 이에 대한 방법들은 다른 연쇄 구조 그래프 모델에 대해서도 쓸 수 있으며, 임의의 그래프 모델에 대해서도 일반화할 수 있다.

17.4.1. Types of inference problems for temporal models

은닉 마르코프 모델의 은닉 상태 추론에는 여러 예가 있는데 그 중 하나는 가끔 부정직한 카지노 문제이다. 이 모델에서 모델은 심볼의 서열을 생성하지만 분포의 통계량은 항상 바뀐다. 이에 대한 여러 타입의 추론이 있다.

  • 필터링 : 데이터가 스트리밍됨에 따라 믿음 상태 p(z_{t} | \mathbf{x}_{1:t})을 온라인으로 또는 재귀적으로 계산하는 것이다. 이는 단순히 현재 상태만으로 은닉 상태를 추정하는 것보다 노이즈를 줄이기 때문에 필터링로 불린다. 베이즈 룰을 연속적으로 적용해서 수행할 수 있다.
  • 다듬질 : p(z_{t} | \mathbf{x}_{1:T})을 오프라인으로 계산하는 것이며, 과거와 미래 데이터 전부에 대해 컨디셔닝하는 것이기 때문에 불확실성은 눈에 띄게 감소한다. (깨달음)
  • 고정 지연 다듬질 : 오프라인과 온라인 접근의 결합으로, 지연 l > 0에 대해 p(z_{t-l} | \mathbf{x}_{1 : t})을 계산하는 것이다. 필터링보다 정확도가 높지만 시간 지연이 된다는 단점이 있다. l의 값을 적절히 선택해 정확도-지연간 트레이드오프를 조정할 수 있다.
  • 예측 : 고정 지연 다듬질에서는 미래 정보를 통해 과거를 예측했지만 여기서는 반대로 지평선 h > 0에 대해 p(z_{t+h} | \mathbf{x}_{1:t})를 계산해 과거 정보를 통해 미래를 예측한다. 이것이 계산된다면 사후예측분포 p(\mathbf{x}_{t+h} | \mathbf{x}_{1:t}) = \sum_{z_{t+h}} p(\mathbf{x}_{t+h} | z_{t+h}) p(z_{t+h} | \mathbf{x}_{1:t})을 이용해 미래 관찰에 대한 예측도 할 수 있다.
  • 최대사후확률 추정 : \mathrm{argmax}_{\mathbf{z}_{1:T}} p(\mathbf{z}_{1:T} | \mathbf{x}_{1:T})을 계산하며, 이는 비터비 복호화로 알려져 있다. 이는 다듬질에 비해 오차율이 높은데, 오차율에 대한 최적화를 하려면 사후주변분포에 관계해야 하기 때문이다.
  • 사후표본 : 사후분포 p(\mathbf{z}_{1:T} | \mathbf{x}_{1:T})로부터 샘플링한다. 이는 다듬질로 얻은 주변분포의 서열보다 많은 정보를 갖고 있다.
  • 증거확률 : 모든 은닉 경로에 대한 확률을 p(\mathbf{x}_{1:T}) = \sum_{\mathbf{z}_{1:T}} p(\mathbf{z}_{1:T}, \mathbf{x}_{1:T})로 합해서 증거확률을 구할 수 있다. 이는 이상치 감지나 모델 기반 클러스터링 등에 쓰인다.

17.4.2. The forwards algorithm

은닉 마르코프 모델에서 필터링된 주변분포 p(z_{t} | \mathbf{x}_{1:t})을 재귀적으로 계산하려면 어떻게 할까?

두 단계로 진행하는데 첫 번째인 예측 단계에서는 한 단계 뒤 예측 밀도 p(z_{t} = j | \mathbf{x}_{1:t-1}) = \sum_{i} p(z_{t} = j | z_{t-1} = i)p(z_{t-1} = i | \mathbf{x}_{1:t-1})을 계산한다. 두 번째인 업데이트 단계에서는 베이즈 룰을 적용해 Z_{t} = p(\mathbf{x}_{t} | \mathbf{x}_{1:t-1}) = \sum_{j} p(z_{t} = j | \mathbf{x}_{1:t-1}) p(\mathbf{x}_{t} | z_{t} = j)에 대해 \alpha_{t}(j) = \frac{1}{Z_{t}} p(\mathbf{x}_{t} | z_{t} = j) p(z_{t} = j | \mathbf{x}_{1:t-1})을 계산한다. 이를 예측-업데이트 순환이라 한다. 분포 p(z_{t} | \mathbf{x}_{1:t}) = \mathbf{\alpha}_{t}은 시점 t에서의 필터링된 믿음 상태라고 한다. \odot하다마드 곱일 때위의 식은 \mathbf{\alpha}_{t} \propto \mathbf{\psi}_{t} \odot (\mathbf{\Psi}^{T} \mathbf{\alpha}_{t-1})로 나타낼 수 있다. 추가로 이 알고리즘을 통해 증거로그확률을 구할 수도 있다: \log p(\mathbf{x}_{1:T} | \mathbf{\theta}) = \sum_{t=1}^{T} \log Z_{t}.

17.4.3. The forwards-backwards algorithm

위에서는 온라인 추론을 통해 필터링된 주변분포 p(z_{t} = j | \mathbf{x}_{1:t})를 계산하였다. 여기서는 오프라인 추론을 통해 다듬질된 주변분포 p(z_{t} = j | \mathbf{x}_{1:T})을 계산한다.

17.4.3.1. Basic idea

기본 아이디어는 연쇄를 과거/미래 두 부분으로 나누는 것이다.

p(z_{t} = j | \mathbf{x}_{1:T}) \propto p(z_{t} = j, \mathbf{x}_{t+1:T} | \mathbf{x}_{1:T}) \propto p(z_{t} = j | \mathbf{x}_{1:t}) p(\mathbf{x}_{t+1 : T} | z_{t} = j)

이 때 \alpha_{t}(j) = p(z_{t} = j | \mathbf{x}_{1:t})를 필터링된 믿음 상태, \beta_{t}(j) = p(\mathbf{x}_{t+1:T} | z_{t} = j)을 은닉 상태에 대해 조건을 건 미래 증거 조건 가능도, \gamma_{t}(j) = p(z_{t} = j | \mathbf{x}_{1:T})을 다듬질된 사후주변분포라 하자. 그러면 \gamma_{t}(j) \propto \alpha_{t}(j) \beta_{t}(j)이 성립한다.

위에서 \mathbf{\alpha}_{t}를 재귀적으로 구했듯이 \mathbf{\beta}_{t}도 재귀적으로 구할 수 있는데 \mathbf{\beta}_{t-1} = \mathbf{\Psi}(\mathbf{\psi}_{t} \odot \mathbf{\beta}_{t})이 된다. 기본 케이스는 \beta_{T}(i) = 1로, 이벤트가 발생하지 않았을 때의 확률이다. 전방-후방 메시지를 계산한 뒤에는 \gamma_{t}(j) \propto \alpha_{t}(j) \beta_{t}(j)로 사후주변분포를 계산할 수 있는데, 이를 전방-후방 알고리즘이라 한다.

17.4.3.2. Two-slice smoothed marginals

기대값 최대화 확률로 전이 행렬의 매개변수를 추정할 때는 상태간 전이의 기대 횟수를 다음과 같이 계산한다:

N_{ij} = \sum_{t=1}^{T-1} \mathbb{E}[\mathbf{1}_{z_{t} = i, z_{t+1} = j} | \mathbf{x}_{1:T}] = \sum_{t=1}^{T-1} p(z_{t} = i, z_{t+1} = j | \mathbf{x}_{1:T})

p(z_{t} = i, z_{t+1} = j | \mathbf{x}_{1:T})이중 슬라이스 주변분포\mathbf{\xi}_{t, t+1} \propto \mathbf{\Psi} \odot (\mathbf{\alpha}_{t} (\mathbf{\phi}_{t+1} \odot \mathbf{\beta}_{t+1})^{T})이 된다.

17.4.3.3. Time and space complexity

전방-후방 알고리즘의 직접 구현은 O(K^{2}T) 시간복잡도가 든다. 전이 행렬이 희소하면 상삼각행렬일 경우 O(TK) 시간으로 줄일 수 있다. 전이 행렬이 희소하지 않아도 \psi(i, j) \propto e^{-\sigma^{2} \lvert \mathbf{z}_{i} - \mathbf{z}_{j} \rvert}의 형태일 때 O(TK \log K) 시간으로 줄일 수 있다.

어떤 때에는 시간이 아니라 공간 복잡도가 병목이 될 수도 있다. 메모리는 보통 O(KT)를 차지하는데 분할 정복 알고리즘을 사용해서 O(K \log T)로 줄일 수도 있지만 이 경우에는 시간 복잡도가 O(K^{2} T \log T)로 늘어난다.

17.4.4. The Viterbi algorithm

비터비 알고리즘은 연쇄 구조 그래프 모델에서 가장 확률이 높은 서열을 계산한다. 즉, \mathbf{z}^{\ast} = \mathrm{argmax}_{\mathbf{z}_{1:T}} p(\mathbf{z}_{1:T} | \mathbf{x}_{1:T})을 계산한다. 이는 트렐리스 다이어그램의 최단거리를 계산하는 것과 같은데, 이 다이어그램에서는 각 시각에서의 상태가 노드이고 경로의 가중치는 로그 확률 \log \pi_{1}(z_{1}) + \log \phi_{1}(z_{1}) + \sum_{t=2}^{T} [\log \phi(z_{t-1}, z_{t}) + \log \phi_{t}(z_{t})]로 정의된다.

17.4.4.1. MAP vs MPE

짚고 넘어가야 할 사실은 가장 결합 확률이 높은 서열은 가장 주변 확률이 높은 서열과 꼭 같지는 않다는 점이다. 비터비 알고리즘은 전자를 계산하고, 후자는 사후주변분포 최대화자(MPM) \hat{\mathbf{z}} = (\mathrm{argmax}_{z_{1}} p(z_{1} | \mathbf{x}_{1:T}), \cdots, \mathrm{argmax}_{z_{T}} p(z_{T} | \mathbf{x}_{1:T}))이 된다.

전자인 결합사후확률분포추정의 장점은 전역적으로 일관적이 있다는 점이다. 후자인 사후주변분포 최대화자 추정은 더 강건하다. 왜냐하면 비터비 알고리즘에서는 z_{t}를 추정할 때 다른 변수들에 대해 최대값을 구해 \mathrm{z}_{t}^{\ast} = \mathrm{argmax}_{z_{t}} \max_{\mathbf{z}_{1 : t-1}, \mathbf{z}_{t+1 : T}} p(\mathbf{z}_{1 : t-1}, z_{t}, \mathbf{z}_{t+1 : T} | \mathbf{x}_{1:T})을 계산하지만, 후자인 사후주변분포 계산을 전방-후방 알고리즘으로 계산할 때에는 다른 변수들을 합하는 식으로 p(z_{t} | \mathbf{x}_{1:T}) = \sum_{\mathbf{z}_{1 : t-1}, \mathbf{z}_{t+ 1 : T}} p(\mathbf{z}_{1 : t-1}, z_{t}, \mathbf{z}_{t+1, T} | \mathbf{x}_{1 : T})을 계산하기 때문이다. 각 노드를 그 근방에 대해 평균을 내서 추정하므로, 근방의 특정한 값에 조건을 거는 것에 비해 강건하다고 볼 수 있다.

17.4.4.2. Details of the algorithm

비터비 알고리즘을 전방-후방 알고리즘(합 곱)의 합 부분을 최대화로 (최대화 곱) 단순히 바꾸면 된다고 생각할지 모르나, 결합분포의 최빈값이 여러 개이면 이것은 틀린 결과를 낸다. 전방 알고리즘은 합 부분을 최대화로 바꾸기만 하면 되지만, 후방 알고리즘은 역추적 과정으로 가장 확률이 높은 경로를 계산해야 한다.

\delta_{j} = \max_{z_{1}, \cdots, z_{t-1}} p(\mathbf{z}_{1 : t-1}, z_{t} = j | \mathbf{x}_{1:t})를 가장 가능성 높은 경로를 탔을 때 시간 t에서 상태 j에 도달할 확률이라 하자. 이는 시간 t-1에서 상태 i에 도달할 확률에 상태 i에서 상태 j로 전이할 확률을 곱한 것이므로 \delta_{t}(j) = \max{i} \delta_{t-1}(i) \phi(i, j) \phi_{t}(j)이 된다. 가장 확률이 높은 직전 상태 a_{t}(j) = \mathrm{argmax}_{i} \delta_{t-1}(i) \psi(i, j) \phi_{t}(j)도 저장해 놓아야 한다. 초기값은 \delta_{1}(j) = \pi_{j} \phi_{1}(j)로 선택하고 최종 상태는 z_{T}^{\ast} = \mathrm{argmax}_{i} \delta_{T}(i)이 된다. 이 후에 역추적으로 z_{t}^{\ast} = a_{t+1}(z_{t+1}^{\ast})을 통해 계산해 나가면 된다.

언더플로우도 고려의 대상인데 \log \max = \max \log이므로 전방-후방 알고리즘과는 달리 로그를 취해서 해결할 수 있다. 이는 학습 속도도 상당히 높이는데 이것이 기대값 최대화의 E 단계에서 비터비 알고리즘이 많이 쓰이는 이유이다.

17.4.4.3. Example

비터비 알고리즘의 간단한 용례를 확인할 수 있다.

17.4.4.4. Time and space complexity

시간 복잡도는 O(K^{2}T), 공간 복잡도는 O(KT)로 전방-후방 알고리즘과 같다. 전이 행렬이 \psi(i, j) \propto e^{-\sigma^{2} \lVert \mathbf{z}_{i} - \mathbf{z}_{j} \rVert^{2}}의 꼴이라면 시간 복잡도는 O(TK)가 된다.

17.4.4.5. N-best list

비터비 알고리즘을 확장해서 N개의 최고 경로를 반환하도록 하는 N-최고 리스트를 만들 수 있다. 문제점은 N개의 최고 경로가 서로 비슷하다는 점인데 이를 해결하는 방법으로 사후분포에서 경로를 추출하는 방법이 있다.

17.4.5. Forwards filtering, backwards sampling

종종 사후분포에서 경로를 \mathbf{z}_{1:T}^{s} \sim p(\mathbf{z}_{1:T} | \mathbf{x}_{1:T})로 추출하는 것이 유용하기도 하다. 이는 전방-후방 알고리즘으로 이중 슬라이스 다듬질 사후분포 p(z_{t-1, t} | \mathbf{x}_{1:T})을 계산하고 이를 표준화해 조건분포 p(z_{t} | z_{t-1}, \mathbf{x}_{1:T})을 계산하고 (초기값은 z_{1,2}^{\ast} \sim p(z_{1, 2} | \mathbf{x}_{1: T})) 마지막으로 재귀적으로 z_{t}^{\ast} \sim p(z_{t} | z_{t-1}^{\ast}, \mathbf{x}_{1:T})의 과정을 통해 표본을 추출한다.

위의 방법은 전방-후방 알고리즘을 돌린 뒤에 전방 표본 추출 알고리즘을 추가로 돌려야 한다는 단점이 있다. 대안은 전방 알고리즘을 돌린 뒤 후방 알고리즘에서는 샘플링을 하는 것이다. 이렇게 할 수 있는 이유는 p(\mathbf{z}_{1:T} | \mathbf{x}_{1 : T}) = p(z_{T} | \mathbf{x}_{1:T}) \prod_{t = T-1}^{1} p(z_{t} | z_{t+1}, \mathbf{x}_{1:T})이므로 z_{t}^{s} \sim p(z_{t} | z_{t+1}^{s}, \mathbf{x}_{1:t})로 후방 샘플링을 할 수 있다는 것이다. 이 때 샘플링 분포는 p(z_{t} = i | z_{t+1} = j, \mathbf{x}_{1:t}) = \frac{\phi_{t+1}(j) \psi(i, j) \alpha_{t}(i)}{\alpha_{t+1}(j)}이 되고 기본 케이스는 z_{T}^{s} \sim p(z_{T} = i | \mathbf{x}_{1:T}) = \alpha_{T}(i)이다. 이는 매개변수 추론에 쓰이는 블록 깁스 샘플링에 기반한다.

17.5. Learning for HMMs

\mathbf{\pi}가 초기 상태 분포, \mathbf{A}가 전이 행렬, \mathbf{B}가 클래스 조건분포 매개변수일 때 \mathbf{\theta} = (\mathbf{\pi}, \mathbf{A}, \mathbf{B})을 추정해보자. 먼저 쉬운 경우인 \mathbf{z}_{1:T}이 학습 데이터셋에서 관찰가능한 경우를 보고, 그 다음 \mathbf{z}_{1:T}이 숨겨진 경우를 알아보자.

17.5.1. Training with fully observed data

은닉 상태 서열을 관찰할 수 있다면 \mathbf{A}\mathbf{\pi}의 최대가능도추정을 정확히 계산할 수 있다. 켤레사전분포를 쓰면 사후분포도 계산할 수 있을 것이다. \mathbf{B}를 추정하는 것은 관찰 모델의 형태에 달렸다. 예를 들어 각 상태가 다항 베르누이 분포를 따르고 B_{jl} = p(X_{t} = l | z_{t} = j)이라면 최대가능도추정은 N_{jl}^{X} = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \mathbf{1}_{z_{i, t} = j, x_{i, t} = l}일 때 \hat{B}_{jl} = \frac{N_{jl}^{X}}{N_{j}}이 된다. 비슷하게, 각 상태가 가우시안 분포를 따른다면 \bar{\mathbf{x}}_{k} = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \mathbf{1}_{z_{i, t} = k} \mathbf{x}_{i, t}, (\bar{\mathbf{xx}})_{k}^{T} = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \mathbf{1}_{z_{i, t} = k} \mathbf{x}_{i, t} \mathbf{x}_{i, t}^{T}일 때 \hat{\mathbf{\mu}}_{k} = \frac{\bar{\mathbf{x}}}{N_{k}}, \hat{\mathbf{\Sigma}}_{k} = \frac{(\bar{\mathbf{xx}})_{k}^{T} - N_{k} \hat{\mathbf{\mu}}_{k}\hat{\mathbf{\mu}}_{k}^{T}}{N_{k}}이 된다. 다른 분포에 대해서도 계산할 수도 있으며 최대사후확률추정으로 어렵지 않게 확장할 수 있다.

17.5.2. EM for HMMs (the Baum-Welch algorithm)

z_{t}가 관측되지 않을 경우에는 혼합 모델을 피팅하는 것과 같은 접근법을 쓴다. 가장 흔한 방법은 기대값 최대화 알고리즘으로 최대가능도추정이나 최대사후확률추정 매개변수를 구하는 것이다. 경사 하강법도 물론 쓸 수 있다. 여기서 기대값 최대화 알고리즘을 쓸 때 이를 바움-웰치 알고리즘이라 한다.

17.5.2.1. E step

기대완전데이터 로그가능도는 다음과 같다:

Q(\mathbf{\theta}, \mathbf{\theta}_{\mathrm{old}}) = \sum_{k=1}^{K} \mathbb{E}[N_{k}^{1}] \log \pi_{k} + \sum_{j=1}^{K} \sum_{k=1}^{K} \mathbb{E}[N_{jk}] \log A_{jk} + \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \sum_{k=1}^{K} p(z_{t} = k | \mathbf{x}_{i}, \mathbf{\theta}^{\mathrm{old}}) \log p(\mathbf{x}_{i, t} | \mathbf{\phi}_{k})

\mathbb{E}[N_{k}^{1}] = \sum_{i=1}^{N} p(z_{i1} = k | \mathbf{x}_{i}, \mathbf{\theta}^{\mathrm{old}})

\mathbb{E}[N_{jk}] = \sum_{i=1}^{N} \sum_{t=2}^{T_{i}} p(z_{i, t - 1} = j, z_{i, t} = k | \mathbf{x}_{i}, \mathbf{\theta}^{\mathrm{old}})

\mathbb{E}[N_{j}] = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} p(z_{i, t} = j | \mathbf{x}_{i}, \mathbf{\theta}^{\mathrm{old}})

이 충족 통계량은 전방-후방 앍리즘을 통해 \gamma_{i, t}(j) = p(z_{t} = j | \mathbf{x}_{i, 1 : T_{i}}, \mathbf{\theta}), \xi_{i, t}(j, k) = p(z_{t-1} = j, z_{t} = k | \mathbf{x}_{i, 1 : T_{i}}, \mathbf{\theta})를 계산함으로써 계산할 수 있다.

17.5.2.2. M step

\mathbf{A}\mathbf{\pi}의 M 단계는 기대 등장빈도 \hat{A}_{jk} = \frac{\mathbb{E}[N_{jk}]}{\sum_{k^{\prime}} \mathbb{E} [N_{jk^{\prime}}]}, \hat{\pi}_{k} = \frac{\mathbb{E}[N_{k}^{1}]}{N}이다. 이는 직관적으로 상태 j에서 k로 전이되는 횟수의 기대값을 더한 뒤 상태 j에서 다른 상태로 전이되는 횟수로 나눈 것과 같다.

다항 베르누이 관찰 분포에서는 \mathbb{E}[M_{jl}] = \sum_{i=1}^{N} \sum_{t : x_{i, t} = l} \gamma_{i, t}(j)일 때 \hat{B}_{jl} = \frac{\mathbb{E}[M_{jl}]}{\mathbb{E}[N_{j}]}가 된다. 이는 직관적으로 상태 j에서 심볼 l을 보는 횟수의 기대값에서 상태 j에 있는 횟수로 나눈 것과 같다.

가우시안 관찰 분포에서는 \mathbb{E}[\bar{\mathbf{x}}_{k}] = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \gamma_{i, t}(k) \mathbf{x}_{i, t}, \mathbb{E}[(\bar{\mathbf{xx}})_{k}^{T}] = \sum_{i=1}^{N} \sum_{t=1}^{T_{i}} \gamma_{i, t}(k) \mathbf{x}_{i, t} \mathbf{x}_{i, t}^{T}일 때 \hat{\mathbf{\mu}}_{k} = \frac{\mathbb{E}[\bar{\mathbf{x}}_{k}]}{\mathbb{E}[N_{k}]}, \hat{\mathbf{\Sigma}}_{k} = \frac{\mathbb{E}[(\bar{\mathbf{xx}})_{k}^{T}] - \mathbb{E}[N_{k}] \hat{\mathbf{\mu}}_{k}\hat{\mathbf{\mu}}_{k}^{T}}{\mathbb{E}[N_{k}]}이 된다.

정규화는 일반화된 선형 모델에서 정규화하듯이 똑같이 하면 된다.

17.5.2.3. Initialization

기대값 최대화 알고리즘이 항상 그렇듯이, 안 좋은 국소적 최적해에 갇히는 일이 없게 하기 위해 매개변수를 주의 깊게 초기화해야 한다. 몇 가지 방법은

  • 매개변수를 초기화할 때 완전히 라벨링된 일부 데이터를 사용한다.
  • 초기에는 마르코프 의존성을 무시하고, 관찰 매개변수를 일반적인 혼합 모델 추정법 (K-평균이나 기대값 최대화 등)을 적용한다.
  • 매개변수를 무작위로 초기화하고 여러 번 재시작한 뒤에 최고의 해를 고른다.

결정론적 담금질 등의 테크닉은 국소적 최적해의 효과를 완화시킨다. 또한 은닉 마르코프 모델의 기대값 최대화 초기화를 비터비 학습으로 할 수도 있다. 즉, 경로에서의 사후분포를 가장 확률 높은 한 가지의 경로로 근사하는 것이다. 초기 매개변수 추정은 나쁜 값일 가능성이 많으므로 그다지 좋은 방법은 아니다. 더 안전한 방법은 전방-후방 알고리즘으로 시작한 뒤 수렴 직전에 비터비로 전환하는 것이다.

17.5.3. Bayesian methods for “fitting” HMMs

기대값 최대화 알고리즘은 매개변수의 최대사후확률추정을 반환한다. 은닉 마르코프 모델에서 베이지안 매개변수 추정을 하는 방법도 있다.

하나의 접근법은 변량 베이지안 기대값 최대화(VBEM)을 쓰는 것이다. 기본 발상은 E 단계에서 전방-후방 알고리즘을 돌릴 때 최대사후확률추정 대신 사후평균 매개변수를 대입하는 것이다. M 단계에서는 매개변수를 직접 업데이트하는 대신에 켤레사후분포의 매개변수를 업데이트한다.

변량 베이지안 기대값 최대화의 대안은 마르코프 연쇄 몬테 카를로법을 이용한다. 이에는 블록 깁스 샘플링 등이 있다. 기본 발상은 \mathbf{z}_{1: T}를 전방 필터링, 후방 샘플링으로 샘플링하고, 이로 샘플된 잠재변수 경로에 조건을 건 사후분포에서 매개변수를 추출하는 것이다. 구현하기는 쉽지만 혼합 모델들처럼 매개변수 특정이 불가능하다는 단점이 존재한다.

17.5.4. Discriminative training

종종 은닉 마르코프 모델은 생성적 분류기 내에서 클래스 조건분포로 쓰이기도 한다. 이 경우 p(\mathbf{x} | y = c, \mathbf{\theta})은 전방 알고리즘으로 계산될 수 있다. 이 때 결합가능도 \prod_{i=1}^{N} p(\mathbf{x}_{i}, y_{i} | \mathbf{\theta})는 기대값 최대화로 피팅해서 각 클래스 조건분포에 대한 은닉 마르코프 모델을 독립적으로 피팅할 수 있다.

조건부 가능도 \prod_{i=1}^{N} p(y_{i} | \mathbf{x}_{i}, \mathbf{\theta}) = \prod_{i} \frac{p(y_{i} | \mathbf{\theta}) p(\mathbf{x}_{i} | y_{i}, \mathbf{\theta})}{\sum_{c} p(y_{i} = c | \mathbf{\theta}) p(\mathbf{x}_{i} | y_{i} = c, \mathbf{\theta})}을 최대화하는 매개변수를 찾기를 원할 수도 있다. 이는 결합 가능도를 최대화하는 것보다 연산량이 많은데, 분모 때문이다. 또한, 기대값 최대화 알고리즘을 쓸 수 없고 경사 하강법에 의존해야 한다. 그렇지만 이 경우 정확도가 더 개선된 경우가 많다. 음성 인식에서 표준 접근은 생성적 분류기를 기대값 최대화로 초기에 독립적으로 학습시킨 뒤 구별적으로 미세 조정을 하는 것이다.

17.5.5. Model selection

은닉 마르코프 모델에서 모델 선택 관련 두 가지의 이슈는 상태의 개수를 결정하는 것과 상태 전이 도형의 형태를 결정하는 것이다.

17.5.1. Choosing the number of hidden states

은닉 마르코프 모델에서 상태의 개수를 결정하는 것은 혼합 모델에서 혼합 컴포넌트의 수를 결정하는 것과 비슷하다. 다음의 해법이 있다:

  • K의 범위에 대해 격자 탐색을 한다. 이 때 목적 함수는 교차검증가능도, BIC 점수, 로그-주변 가능도에 대한 변량 하한 등을 사용한다.
  • 가역 점프 마르코프 연쇄 몬테 카를로를 사용한다. 이는 매우 느리다.
  • 변량 베이즈를 통해 필요 없는 컴포넌트를 삭제한다.
  • 무한 은닉 마르코프 모델을 사용한다. 이는 계층적 디리클레 과정에 기반한다.

17.5.5.2. Structure learning

은닉 마르코프 모델에서의 구조 학습은 희소한 전이 행렬을 학습하는 것이다. (그래프 모델의 구조를 학습하는 것이 아니다) 많은 휴리스틱이 있지만 분할 병합 방법 등이 있다. 다른 방법으론, 이 문제를 최소 엔트로피 사전분포 p(\mathbf{A}_{i, :}) \propto e^{-\mathbb{H}(\mathbf{A}_{i, :})}를 이용한 최대사후확률추정 문제로 볼 수 있다. 이 사전분포는 결정론적에 가까워서 엔트로피가 낮은 분포를 선호하게 된다. 대응하는 M 단계는 닫힌 형태로 풀릴 수 없지만 수치적 근사는 가능하다. 문제점은 모든 들어오는 상전이를 쳐내게 될 가능성이 있다는 점인데, 무한 은닉 마르코프 모델이 흥미로운 대안이 될 수 있다.

17.6. Generalizations of HMMs

은닉 마르코프 모델에 대한 많은 변형들이 제안되었다.

17.6.1. Variable duration (semi-Markov) HMMs

일반 은닉 마르코프 모델에서 d 단계에서 상태 i에 있을 확률은 p(t_{i} = d) \propto e^{d \log A_{ii}}이다. 이를 기하 분포라 하는데, d에 대해 지수적으로 감소하는 함수이므로 때때로는 비현실적이다. 조금 더 일반화된 지속 시간을 허용하기 위해서는 반-마르코프 모델을 사용한다. 이는 다음 상태를 예측할 때 과거 상태뿐만 아니라 그 상태에 얼마나 있었는지도 같이 사용한다. 상태 공간이 직접적으로 관측되지 않으면 이는 은닉 반-마르코프 모델(HSMM), 가변 지속 은닉 마르코프 모델, 명시적 지속 은닉 마르코프 모델이라 한다. 이는 유전자 탐색에 많이 쓰인다.

은닉 반-마르코프 모델은 각 상태에서의 대기 시간을 더 정확하게 모델링할 수 있다는 장점 외에도 관찰의 전체 배치에 대한 분포를 한 번에 모델링하는 것에도 장점이 있다. 즉, p(\mathbf{x}_{t : t + l} | z_{t} = k, d_{t} = l) 형태의 가능도를 쓰는 것이다. 이는 데이터가 구간적으로 선형일 때 유용하다.

17.6.1.1. HSMM as augmented HMMs

은닉 반-마르코프 모델을 묘사하는 하나의 방법은 그래프 모델을 쓰는 것이다. D_{t} \in \{0, 1, \cdots, D\}은 상태 지속 시간 카운터이다. 상태 j에 돌입했을 때는 D_{t} \sim p_{j}(\cdot)로 지속 시간 분포에서 지속 시간을 샘플링한다. 이후 D_{t} = 0이 될 때까지 카운트다운을 수행한다. D_{t} > 0인 동안에는 상태 z_{t}를 변경하지 않고, D_{t} = 0인 경우에는 새 상태로의 추계적 전이를 수행한다.

즉, 조건부 분포는 다음과 같다:

p(D_{t} = d^{\prime} | D_{t-1} = d, z_{t} = j) = p_{j}(d^{\prime}) if d = 0, 1 if $d^{\prime} = d – 1$ and d \geq 1, 0 otherwise

p(z_{t} = k | z_{t-1} = j, D_{t-1} = d) = 1 if d> 0 and j = k, A_{jk} if d = 0, 0 otherwise

이 때 p_{j}(d)를 테이블이나 매개변수 분포로 표현할 수 있음을 눈여겨보라. p_{j}(d)가 지수 분포가 되면 표준 은닉 마르코프 모델이 된다.

메가 변수 Y_{t} = (D_{t}, z_{t})를 정의함으로써 이 모델에서 추론을 할 수 있지만, D_{t}가 결정론적이므로 이는 효율적이지 못하다. D_{t}를 적분해 빼낸 뒤 추론 과정을 유도할 수 있다. 안타깝게도 모두 O(TK^{2} D) 시간복잡도가 걸린다.

17.6.1.2. Approximations to semi-Markov models

기하 분포가 아닌 대기 시간을 갖는 모델을 모델링하는 더 효율적인 (그러나 덜 유연한) 방법은 각 상태를 n개의 새로운 상태로 치환하고 해당 새로운 상태들은 기존 상태와 동일한 방출 확률을 갖도록 하는 것이다. p_{j}(d)를 근사하기 위해 각 상태에 필요한 확장의 수를 E라 하면 전방-후방 알고리즘은 O(T(KE)F_{in}) 시간이 든다. (F_{in}은 이전 상태의 평균수) 반면 은닉 반-마르코프 모델은 O(TK(F_{in} + D)) 시간이 든다. 보통 F_{in} + DE F_{in}보다 훨씬 크므로 이러한 상태 확장 모델은 은닉-반 마르코프 모델보다 훨씬 빠르다.

17.6.2. Hierarchical HMMs

계층적 은닉 마르코프 모델(HHMM)은 계층적 구조를 갖는 모델에 대한 은닉 마르코프 모델의 확장이다. 이는 여러 곳에서 쓰이며 추계적 컨텍스트 프리 문법(SCFG)에 비하면 표현력이 적지만 (계층의 깊이에 상한이 존재하기 때문에), 더 효율적인 추론이 가능하다. 추론 시간복잡도가 O(T)로 추계적 컨텍스트 프리 문법은 O(T^{3})이 걸리기 때문이다.

계층적 은닉 마르코프 모델은 방향그래프모델로 볼 수 있다. 계층 l에서의 상태 전이는 아래 계층에서의 연쇄가 끝난 경우에만 허용된다. 이 메커니즘은 높은 계층에서의 연쇄가 낮은 계층에서의 연쇄보다 더 늦게 변함을 보장한다.

가변 지속 은닉 마르코프 모델은 계층적 은닉 마르코프 모델의 특수한 경우로 볼 수 있다. 이 경우 위층을 결정론적 카운터, 아래층을 일반 은닉 마르코프 모델로 본다.

17.6.3. Input-output HMMs

은닉 마르코프 모델은 입력을 다루도록 확장할 수 있다. 이는 p(\mathbf{y}_{1:T}, \mathbf{z}_{1:T} | \mathbf{u}_{1:T}, \mathbf{\theta}) 꼴의 서열에 대한 조건밀도함수 모델을 정의한다. (\mathbf{u}_{t}는 입력) 만약 입력과 출력이 연속적이라면, 가능한 매개화는 p(z_{t} | \mathbf{x}_{t}, z_{t-1} = i, \mathbf{\theta}) = \mathrm{Cat}(z_{t} | \mathcal{S}(\mathbf{W}_{i} \mathbf{u}_{t})), p(\mathbf{y}_{t} | \mathbf{x}_{t}, z_{t} = j, \mathbf{\theta}) = \mathcal{N}(\mathbf{y}_{t} | \mathbf{V}_{j} \mathbf{u}_{t}, \mathbf{\Sigma}_{j})이 될 것이다.

즉, 전이 행렬은 매개변수가 이전 상태에 의존하는 로지스틱 회귀 모델이다. 관측 모델은 현재 상태에 의존하는 가우시안이다. 전체 모델은 최대 엔트로피 마르코프 모델의 은닉 버전으로 생각될 수 있다.

입력 \mathbf{u}_{1:T}\mathbf{\theta}에 조건을 걸면 전방-후방 알고리즘으로 은닉 상태를 추정할 수 있다. 기대값 최대화 알고리즘으로 매개변수를 추정하는 것도 가능하다.

17.6.4. Auto-regressive and buried HMMs

표준 은닉 마르코프 모델은 주어진 은닉 상태에 대해 관찰들이 조건부 독립임을 가정하나, 이는 종종 잘 들어맞지 않는다. 그래서 \mathbf{x}_{t-1}에서 \mathbf{x}_{t}로 가는 간선을 추가하기도 한다. 이를 자동 회귀 은닉 마르코프 모델, 또는 제도 변환 마르코프 모델이라 한다. 연속적 데이터에 대해서는 관측 모델은 p(\mathbf{x}_{t} | \mathbf{x}_{t-1}, z_{t} = j, \mathbf{\theta}) = \mathcal{N}(\mathbf{x}_{t} | \mathbf{W}_{j} \mathbf{x}_{t-1} + \mathbf{\mu}_{j}, \mathbf{\Sigma}_{j})이 된다. 이는 현재 은닉 상태에 매개변수가 의존하는 선형 회귀 모델이다.

마지막 L개의 관찰에 현재 상태가 의존하도록 확장하는 것도 가능하다:

p(\mathbf{x}_{t} | \mathbf{x}_{t - L:t-1}, z_{t} = j, \mathbf{\theta}) = \mathcal{N}(\mathbf{x}_{t} | \sum_{l=1}^{L} \mathbf{W}_{j, l} \mathbf{x}_{t - l} + \mathbf{\mu}_{j}, \mathbf{\Sigma}_{j})

자동 회귀 은닉 마르코프 모델은 두 개의 마르코프 연쇄를 결합한 것이다. 하나는 장기적 의존성을 은닉 변수에 담고, 하나는 단기적 의존성을 관측 변수에 담는다. X개의 노드가 관측되어 있으므로, 해당 노드간 연결은 국소적인 증거도에 대한 계산만 바꿀 뿐이고 여전히 일반적 전방-후방 알고리즘을 사용해 추론을 할 수 있다. 기대값 최대화를 사용한 매개변수 추정은 역시 쉽다: E 단계와 M 단계는 변하지 않는다. 관찰 값을 스칼라로 가정하면 M 단계는 \sum_{t} \mathbb{E}[\frac{1}{\sigma^{2} (s_{t})} (y_{t} - \mathbf{y}_{t - L:t-1}^{T} \mathbf{w}(s_{t})^{2} + \log \sigma^{2} (s_{t}))]을 최소화하는 것을 포함한다. \mathbf{w} 항에 집중하면, 이것은 K개의 가중치 최소 제곱 문제 J(\mathbf{w}_{1 : K}) = \sum_{j} \sum_{t} \frac{\gamma_{t}(j)}{\sigma^{2} (j)} (y_{t} - \mathbf{y}_{t - L: t - 1}^{T} \mathbf{w}_{j})^{2}을 푸는 것과 같다. (\gamma_{t}(j) = p(z_{t} = k | \mathbf{x}_{1:T})은 다듬질된 사후주변분포) 이 부분 문제는 레빈슨-더빈 법으로 풀릴 수 있다.

매몰 마르코프 모델은 자동 회귀 마르코프 모델의 일반화로, 관측 노드들 간의 의존성이 은닉 상태에도 의존성을 갖도록 허용한다. 이는 여러 다른 네트워크의 혼합이므로, 동적 베이지안 다중 넷이라고도 한다. 선형-가우시안 세팅에서는 \mathbf{x}_{t-1} \to \mathbf{x}_{t} 호의 구조를 희소 회귀 행렬 \mathbf{W}_{j}로 변경할 수 있고, \mathbf{x}_{t}의 컴포넌트간 연결의 구조는 희소 가우시안 그래프 모델을 이용해 변경할 수 있다.

17.6.5. Factorial HMM

은닉 마르코프 모델은 하나의 이산확률변수 z_{t} \in \{1, \cdots, K\}을 이용해 상태를 표현한다. 10비트를 표현하기 위해서는 1024 상태가 필요할 것이다. 반면에 분산 표현, 즉 z_{c, t} \in \{0, 1\}이 t번째 은닉 상태의 c번째 비트를 나타낸다고 하자. 그러면 10비트를 10개의 이진 변수만으로 나타낼 수 있게 된다. 이를 인자 은닉 마르코프 모델이라 한다. 이는 신호의 여러 다른 특성을 저장할 수 있다는 장점이 있다. 단점은 \mathbf{x}_{t} 조건 하에서는 모든 은닉 변수가 상호 연관된다는 것인데, 이는 정확한 상태 추정을 불가능하게 한다. 하지만 효율적인 근사는 가능하다.

17.6.6. Coupled HMM and the influence model

상호 연관된 데이터 스트림이 여러 개 있으면 짝지어진 은닉 마르코프 모델을 쓸 수 있다. 이것은 상태 전이가 이웃한 연쇄의 상태에 의존하는 은닉 마르코프 모델의 시리즈이다. 즉, 결합조건분포가 p(\mathbf{z}_{t} | \mathbf{z}_{t-1}) = \prod_{c} p(z_{ct} | \mathbf{z}_{t-1}), p(z_{ct} | \mathbf{z}_{t-1}) = p(z_{ct} | z_{c, t-1}, z_{c-1, t-1}, z_{c+1, t-1})이 된다. 이는 음성-시각 발화 감지 등에 쓰인다. 이 모델의 문제점은 매개변수의 수가 O(CK^{4}) 개가 된다는 점인데, 이와 밀접한 관계가 있으면서 매개변수를 더 적게 사용하는 영향력 모델이 있다. 이는 p(z_{ct} | \mathbf{z}_{t-1}) = \sum_{c^{\prime} = 1}^{C} \alpha_{c, c^{\prime}} p(z_{ct} | z_{c^{\prime}, t-1})의 결합확률분포를 사용한다. (\sum_{c^{\prime}} \alpha_{c, c^{\prime}} = 1을 만족) 즉, 쌍별 전이 행렬에 대해 볼록 결합을 사용한다. 이는 O(C^{2} + CK^{2}) 개의 매개변수를 사용한다. 또한, 이는 각각의 연쇄가 이웃한 연쇄들 뿐만 아니라 다른 연쇄들에 대해서도 영향을 받을수 있도록 해준다. 안타깝게도, 이 모델 모두 추론에 O(T (K^{C})^{2}) 시간이 걸린다. 여러 근사 방법이 존재한다.

17.6.7. Dynamic Bayesian networks (DBNs)

동적 베이지안 망은 방향그래프 모델을 이용해 추계적 과정을 나타내는 방법이다. 이 때 네트워크는 동적이지 않다 (구조와 매개변수가 고정되어 있으니까), 다만 네트워크가 표현하는 역학계가 동적일 뿐이다. 지금까지 본 모든 은닉 마르코프 연쇄 변형은 동적 베이지안 망으로 볼 수 있다.

동적 베이지안 망을 정의하는 것은 1차 슬라이스와 2차 슬라이스의 구조를 특정하고, 조건부 확률분포의 형태를 특정하면 된다. 학습도 쉽다. 다만 연산량이 많다는 단점이 있는데, 모든 은닉 변수가 시간에 따라 상호 연관되게 되기 때문이다 (이를 꼬임이라 한다). 따라서 희소 그래프가 꼭 추적 가능한 정확한 추론을 낳는 것은 아니다. 여러 효율적인 근사적 추론법이 존재한다.

요점 정리

  • 연속된 관찰의 서열에 대한 확률적 모델을 정의할 수 있음.
  • 마르코프 모델 : 현재 상태가 이전 상태에만 의존하는 형태의 연쇄 모델.
  • 은닉 마르코프 모델 : 은닉 상태는 마르코프 연쇄를 쓰고, 이에 대한 관측이 존재하는 모델.
  • 은닉 마르코프 모델의 추론 : 전방-후방 알고리즘, 비터비 알고리즘 등을 씀.
  • 은닉 마르코프 모델의 학습 : 기대값 최대화 알고리즘을 씀.
  • 은닉 마르코프 모델의 일반화 : 가변 지속 은닉 마르코프 모델, 계층 은닉 마르코프 모델 등 여러 변형이 존재.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중