[Data Mining] Markov Chain and Hidden Markov Model

이번 포스팅에서는 Markov Chain과 Hidden Markov Model에 대해서 이야기해보도록 하자. 우선 Markov Chain이다. Markov Chain은 일종의 Automata의 확장이라고 보면 된다. Automata의 확장인데 하나의 state에서 그 다음 state으로 갈 때 확률이 이용되는 automata라고 보면 될 것 같다. 이거는 예제로 보면 금방 이해가 갈 것이다.

우선 위의 그림과 함께 Markov Chain의 component를 설명해보자.

Q : component of Markov model e.g. q0, q1, ... qN

위의 그림에서의 동그라미 하나하나가 state이다. HOT 동그라미는 q1 state이고 COLD 동그라미는 q2 state이고 WARM 동그라미는 q3 state이다.

aij : state i에서 state j로 가는 확률이다. 예를 들어, HOT 다음에 또 HOT일 확률은 a11이고, HOT 다음에 WARM일 확률은 a13이다. 

q0, qF :  q0는 state 0, 즉 시작하는 start state을 의미하며, qF는 Final state, 즉 종료하는 final state을 의미한다.

위의 Markov Chain에서 두가지 가정이 있다. 첫번째 가정은 하나의 state에서 다음 state로 가는 probability는 오로지 이전의 상태에 의해서 결정된다는 것이다. 즉 a13은 HOT에서 WARM으로 가는 확률인데 이 확률은 오로지 state1과 state3 사이에서만 결정되지 state1이 어떤 probability로 state1이 되었는지는 중요하지 않다는 이야기이다.

두번째 가정은 하나의 state에서 다음 state로 뻗어나가는 probability의 합은 1이라는 것이다. 당연한 이야기이다. 한 state에서 무조건 다음 state로 어떻게든 어디로든 갈 것이기 때문에 당연히 probability의 합은 1이다.

Markov Chain은 별로 안어렵다. 그래서 예제 하나만 더 보고 끝내도록 하자. 위의 그림에서 HOT HOT HOT WARM이 input으로 왔을 때 그 probability는 어떻게 구하는가? 아주 쉽다.

a01 a11 a11 a13을 전부 곱한 값이 될 것이다. 아주 쉽다.

자 두번째 공부할 것은 Hidden Markov Model이다. 우리가 살면서 주어진 input을 통해 output을 예측해야 되는 경우는 굉장히 많다. 사람들이 밖에 돌아다니는 빈도를 보고 비오는 날씨인지 날씨가 좋은지를 예측할 수도 있고, 사람들이 어떤 물건을 많이 사는지 적게 사는지를 관찰하여 그 물건의 품질을 결정할 수도 있고, 어떤 사람이 말을 얼마나 많이 하느냐에 따라 그 사람의 기분을 측정할 수도 있다. 이런식으로 우리가 관찰한 것들을 기반으로 우리가 볼 수 없는 무언가를 찾아내는 것, 숨겨진 그것을 찾아내는 것(hidden)을 model로 만들어 둔 것이 Hidden Markov Model(HMM)이다. 따라서 HMM에는 한 가지의 component가 더 들어간다. 

Q, A, q0, qF까지는 Markov Chain과 같고, 여기에 O(e.g. o1, o2, o3, ..., oT) observatoin 순서가(sequence of observation) 들어간다. sequence of observation 즉, 첫번째 날 두번째 날 세번째 날에 각각 사람을 10명 1명 4명 봤을 때, 첫번째 두번째 세번째 날의 날씨는?? 여기서 o1 o2 o3는 각각 10명 1명 4명이고, 이것을 가지고 예측된 날씨는 가령, Sunny Rainy Windy 등등이 되겠지. 즉 10명 1명 4명이라는 input sequence를 가지고 Sunny State인지 Rainy State인지 Windy State인지를 예측하는 것이 되겠다.

그 다음에 또 하나 언급할 component는 observation probability이다. 특정 state i에서 각각의 o1, o2, o3, ..., oT가 관측될 probability를 의미한다. 가령, Sunny state에서(Sunny한 날씨에) 밖에 사람이 10명이 관측될 확률, 1명이 관측될 확률, 4명이 관측될 확률을 의미한다. i state에 ot가 관측될 probability를 의미할 경우 기호로는 bi(ot)로 쓴다.

이것을 통해서 우리가 할 수 있는 것은 무엇일까? 보통 HMM을 통해서 우리는 다음의 세 가지 문제를 풀려고 한다.

Problem 1 : 주어진 input sequence으로 가능한 모든 output sequence 각각의 probability는?

Problem 2 : 주어진 ipnut sequence에 대해서 가장 그럴듯한 (highest probability) output sequence는?

Problem 3 : Learning!! 즉, Observation에 대한 probability(B)와 transition probability의 확률(A)를 learning하는 것!!

이 문제를 푸는 algorithm이 있는데, 각각의 문제가 아래의 algorithm을 통해 풀 수 있다.

Forward algorithm → Problem 1

Viterbi algorithm → Problem 2

Forward-Backward algorithm (Baum-Welch Algorithm) → Problem 3

다음 포스팅에는 Forward algorithm과 Viterbi algorithm을 같이 설명해보자. 둘다 비슷한 점이 있기 때문이다. 흠 그런데 Forward-Backward algorithm.. 요거 요거 이해가 어렵다. 당분간 skip 하도록 하자.