이번 포스팅에서는 Forward algorithm과 Viterbi algorithm을 공부할 차례다. 우선 Forward algorithm을 공부하고 Viterbi algorithm을 공부할 예정이다. 이 두 algorithm은 굉장히 비슷하므로 Forward algorithm 설명마친 후에는 거의 Viterbi algorithm은 설명할 것이 별로 없을 것이다. 아무튼 Forward algorithm 설명해보자.
Forward algorithm는 HMM에서 주어진 input sequence에 대한 probability를 구하는 것이다. 가령, 첫째 둘째 셋째날 외출한 사람의 수가 각각 10명 1명 4명일 경우의 확률은 아래의 확률을 모두 더한 것과 같을 것이다.
Possible output : Sunny, Rainy
우선 Forward algorithm를 사용하지 않고 일일이 한번 구하려면 어떻게 구해야되는지 알아보자. 지금부터는 그냥 단순 고등학교 수학문제가 되겠다. 우리가 필요한 확률들은 아래와 같이 정의되어 있다고 하자.
우선, output sequence가 sunny, rainy, sunny라고 가정하고 (probability = 1) 부분적으로 계산을 해보자.
여기서 sunny rainy sunny일 확률을 계산해서 곱해주자.
이와 같은 일을 우리는 각각의 possible output sequence에 대하여 해줘야 된다. 즉 위의 계산을 7번 더해줘야 된다.
여기서는 output으로 가능한 경우의 수가 sunny 또는 rainy밖에 없고 input sequence 길이 역시 3밖에 안되기 때문에 8번 하는 것 정도는 금방 끝낼 수 있다. 그런데 실제로 실생활에서 사용될 때는 output 개수도 많을 것이고 input sequence는 더더욱 많을 것이다. 이는 N^V와 같은 형태로 계산 수가 늘어나기 때문에 효율상 상당히 안 좋다. 그러면 위와 같은 일을 우리는 어떻게 간단하게 해결할 수 있을까. Trellis를 이용하여 간단하게 만들면 된다. Trellis는 아래와 같은 모형을 Trellis라고 한다.
계산 결과는 결국 같다.(휴 다행이다. 한번에 끝내서) 어떤 사람들은 위의 두 풀이과정을 보고, 이거 뭐 딱히 다를게 있어? 라고 이야기 할 수도 있다. 그런데 컴퓨터 입장에서는 확실히 다르다. Forward algorithm을 사용할 경우에는 이전에 사용했었던 계산값을 다시 사용할 수가 있다. 그런데 일일이 같은 계산 8번 해줄 때는 그런 이득을 취할 수가 없다. 이런 것을 dynamic programming이라고 하나보다. 이것에 대한 정확한 개념은 독자들에게...
여기까지가 Forward algorithm이다. Viterbi algorithm은 간단하게 이야기만 하고 끝내려고 한다. Viterbi algorithm의 목적은 most likely possible output sequence를 구하는 것이다. Forward algorithm에서 다른 것은 각각의 state에서 합을 하지 말고 maximum을 취해서 가장 큰 값들만 다음 state로 넘어갈 수 있도록 하는 것이다.
o2 = 1일 때 보면, sunny일 확률도 o1=10 & sunny로부터 왔고 rainy일 확률도 o1=10 & sunny로부터 왔다. 따라서 o1까지는 sunny일 확률이 제일 높다.
o3 = 4일 때 보면, sunny일 확률도 o2=1 & rainy로부터 왔고, rainy일 확률도 o2=1 & rainy로부터 왔다. 따라서 o2까지는 sunny → rainy일 확률이 제일 높다.
마지막으로 final state에서 보면 rainy일 확률(0.020412)가 sunny일 확률(0.01134)보다 크다. 따라서 o3까지를 모두 종합해보면, observation sequence가 10, 1, 4일 경우에는 sunny → rainy → rainy 가 가장 높은 확률을 나타내게 된다.
후, 요즘 12시 넘겨서 자는 경우 거의 없는데 오늘 12시 넘긴다. 12시 16분이다. 빨리 자야겠다. 다음 포스팅은 forward-backward algorithm이면 좋겠으나 아닐 수도 있다.
forward-backward algorithm 공부해보고 싶으신 분은 이거 한번 찾아보세요!! 저는 조금 쉬었다가 다음에 보려고요
'Data Mining' 카테고리의 다른 글
| [Data Mining] Confidence level (2) | 2016.04.02 |
|---|---|
| [Data Mining] Ensemble : Bagging, Random Forest and Boosting (1) | 2016.04.01 |
| [Data Mining] Markov Chain and Hidden Markov Model (2) | 2016.03.30 |
| [Data Mining] Smoothing Techniques (0) | 2016.03.24 |
| [Data Mining] Preprocessing in NLP (0) | 2016.03.24 |
