은닉 마르코프 모델 예시로 쉽게 이해, HMM(Hidden Markov Model)

 

마르코프 체인 (Markov Chain)

 N개의 상태(State)가 있고 각 상태에서 다른 상태로 이동할 때의 전이 확률(transition probability)이 함께 정의되어 있는 그래프를 마르코프 체인 그래프이다. 마르코프 체인의 특성은, 이전 상태로부터 영향을 받지 않고 현재의 상태에서만 다음 상태로 넘어갈 때의 확률에 영향을 준다는 것이다. 즉 이전에 얼마나 복잡한 상태를 거쳐 현재 상태를 왔는지는 다음 상태로 넘어가는 데 있어 영향을 주지 않는다. 또한 현재 상태에서 다음 상태로 갈 수 있는 여러 확률들의 합은 1로 정의된다. 

A Markov Chain with 5 states

 마르코프 체인은 아래와 같이 전이 확률에 대해 행렬(matrix)로 표현할 수 있다. 예시에서 상태 1은 비, 상태 2는 구름, 상태 3은 맑음으로 나타낸 경우, ‘맑음 다음, 비’ $P(S_1|S_3)$의 확률은 행렬에서 3행 1열인 0.1 임을 확인할 수 있다.

 

 

은닉 마르코프 모델 (Hidden Markov Model)

 은닉 마르코프 모델은 다음 항아리(urn) 예시로 쉽게 이해할 수 있다.

 

N개의 항아리가 있으며, "어떤 확률분포에 따라 첫 항아리를 선택($\pi$)"한다.

해당 항아리에서 "어떤 확률 분포에 따라 항아리 속 색깔 구슬을 선택하여 기록(B)"한다.

"어떤 확률분호에 따라 다음 차례의 항아리를 선택(A)"한다.

선택된 항아리에서 구슬을 기록하고, 다음 차례 항아리를 고르는 것을 반복한다.

 

Urn example

 

 은닉 마르코프 모델의 파라미터는 다음과 같이 구성되어 있다.

 

$ \lambda = (A, B, \pi)$

$ A = transition probability distribution$

$ B = observation symbol probability distribution$

$ \pi = initial state distribution$

 

 은닉 마르코프 모델은 단지 일련의 구슬 색깔이 기록된 관찰 데이터 (O)만을 가지고, $A, B, \pi$ 모두 맞추는 것을 목표로 하는 모델이다. 때문에 각 파라미터, A state의 개수 등을 모두 모른 채 가정하여 맞춰야 한다.

 

 

은닉 마르코프 모델 이해를 위한 The dishonest casino 예시

 카지노 딜러와 주사위 게임을 해서 높은 숫자의 주사위가 나오는 사람이 이기는 게임을 하고자 한다. 다만, 딜러는 게임도중 몰래 6이 많이 나오는 조작된 주사위로 바꾸어 본인의 승률을 높이고, 들키기 전에 공정한 주사위로 돌아간다.

 

공정한 주사위 (Fair die): P(1)= P(2)= P(3)= P(4)= P(5)= P(6)=1/6

조작된 주사위 (Loaded die): P(1)= P(2)= P(3)= P(4)= P(5)=1/10, P(6)=1/2

The dishonest casino Markov Chain

 

 우리는 딜러의 주사위 값에 대한 아래와 같은 sequence만 볼 수 있고, 최종적으로는 위와 같은 마르코프 모델을 알아내고자 한다. 이를 단계적으로 풀기 위해 3가지 문제를 차례로 해결해나가며 최종적으로 마르코프 모델을 구하는 방법을 살펴본다.

The dishonest casino sequence

 

 

은닉 마르코프 모델 문제 1 (Evaluation)

 관찰된 시퀀스(observation sequence) $O$ 와 마르코프 모델 $\lambda$이 주어졌을 때 해당 시퀀스가 나타날 확률을 구하는 것을 목적으로 한다.

 카지노 예시에서 무식한 방법으로 시퀀스가 나올 확률을 구한다면, 각 주사위 눈이 나올 수 있는 모든 state의 확률을 구해서 더하면 된다. 공정한 주사위, 조작된 주사위 모두 1~6 값이 나올 수 있기 때문에 해당 시퀀스가 나올 수 있는 state 가지 수는 state 개수(주사위 개수) N, sequence 길이 T라고 하면 $N^T$가 된다

 다만 이는 매우 비효율적이기 때문에 마르코프 모델을 사용한다. 마르코프 모델의 특징은 현재 state로 도달할 확률을 알면 그 이전 state의 확률들은 고려하지 않아도 된다는 점이다. 때문에 현재 state에서 다음 state로 도달할 때의 확률 만을 구해주면 $O(T)$만큼의 computation이 소요된다. 이는 backward 로도 동일하게 구할 수 있다.

 

은닉 마르코프 모델 문제 2 (Decode)

 관찰된 시퀀스(observation sequence) $O$와 마르코프 모델 $\lambda$이 주어졌을 때 각 관찰 값들이 각각 어느 state에서 나온 것인지 구하는 것을 목적으로 한다.

 Dynamic programming을 사용하는 Viterbi Algorithm을 사용해서 구한다.

 Sequence T에서의 특정 시간을 t라고 하자. 문제 1에서 설명된 방법대로 forward로 각 state의 확률을 모두 구하고 backward로 각 state의 확률을 모두 구해주면 특정 t에서의 state별 확률을 구할 수 있다. State의 확률 중 가장 responsibility가 높은 state를 선택하면 문제에 대한 답이 된다.

 

은닉 마르코프 모델 문제 3 (Learning)

 관찰된 시퀀스(observation sequence) $O$가 나타날 확률이 가장 높은 마르코프 모델 $\lambda$를 구하는 것을 목적으로 한다. 즉, 관찰 시퀀스를 만들어 낸 마르코프 모델을 추정하는 것을 목적으로 한다.

 이 문제는 EM(Expectation maximization)을 사용해서 푼다. $\lambda = (A, B, \pi)$ 에 처음 랜덤 한 값을 부여하여 초기화하고, E-step에서는 문제 2의 풀이 방법과 같이 responsibility를 계산한 뒤 M-step에서 $A, B$를 update 하는 작업을 반복하여 정답을 구한다.

 

EM 알고리즘 예시로 쉽게 이해하기 (Expectation maximization, EM algorithm)

 

 

---

참고자료:

- a tutorial on hidden markov models and selected applications in speech recognition

web.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf

- Hidden Markov Models

www.slideserve.com/gayora/hidden-markov-models-powerpoint-ppt-presentation

www.cs.cmu.edu/~aarti/Class/10601/slides/HMM_11_1_2011.pdf