[HMM] Forward algorithm

HMM 포스팅에서 제기된 3가지 문제 중 첫번 째 문제 해결하는 방법에 대해 알아보겠습니다.

문제는 다음과 같습니다

HMM의 인자 및 특정 출력이 주어졌을 때, 주어진 출력이 도출될 확률을 계산

Forward 알고리즘에 대해 설명하기 전, 먼저 예제를 통해 이 알고리즘의 필요성에 대해 살펴보겠습니다.

예제를 다시 한번 사용하겠습니다.

어떠한 지역은 통계적으로 다음과 같이 날씨가 변하는 지역에 살고 있다. 

초기 날씨 확률 : 맑음 0.2 / 흐림 0.5 / 비 0.3

또한, 이 지역에 거주하는 A는 날씨에 따라 아이스크림을 하루에 [표 2]와 같이 확률적으로 소비한다. 

Q. 아이스크림 소비가 (1,3,3,2)와 같이 나타났을 때, 이러한 소비 결과가 도출될 확률을 계산해라

우선 Forward 알고리즘 없이 고등학교 수준의 확률을 이용해서 계산해보겠습니다.

일단 첫번째 날부터 마지막 날까지의 날씨는 "흐림 - 흐림 - 맑음 - 비" 라고 가정하겠습니다.

우선 아이스크림 소비가 (1,3,3,2)로 진행될 확률을 계산하겠습니다.

P( 1 || 흐림 ) = 0.2

P( 3 || 흐림 ) = 0.3

P( 3 || 맑음 ) = 0.7

P( 2 || 비 ) = 0.1

따라서 P( 1 || 흐림 )  * P( 3 || 흐림 ) * P( 3 || 맑음 ) * P( 2 || 비 ) = 0.0042

다음으로 날씨가  "흐림 - 흐림 - 맑음 - 비" 으로 진행될 확률을 계산하겠습니다.

P(첫날 흐릴 확률(초기확률)) = 0.5

P(흐림 -> 흐림) = 0.3

P(흐림 -> 맑음) = 0.2

P(맑음 -> 비) =  0.2

따라서 P(첫날 흐릴 확률(초기확률))  * P(흐림 -> 흐림) * P(흐림 -> 맑음) * P(맑음 -> 비) =  0.006

마지막으로 이 두 확률을 곱하면

0.0042 * 0.006 = 0.0000252

이와 같이 구할 수 있습니다.

그러나 이 결과는 제가 가정한 날씨가  "흐림 - 흐림 - 맑음 - 비" 으로 진행되었을 때를 말합니다.

이 경우를 제외하고도 여러 경우의 수가 생길 것이고 만약 '안개' , '황사' 와 같은 변수가 추가된다면 이와 같은 방법으로 계산하기는 너무 복잡하고 귀찮을 것 같습니다.

이를 해결하기 위해 나온 알고리즘이 바로 Forward 알고리즘입니다!

이해를 돕기 위해 그림으로 설명하겠습니다.

위 그림은 시작부터 마지막날까지 날씨의 흐름도를 나타낸 것입니다.

모든 선분에 확률을 적으면 그림이 너무 복잡해질 것 같아 초기확률과 오늘과 내일이 같은 날씨인 경우만 표시했습니다.

표시하지 않은 선분의 확률은 [표 1]을 참고하시면 됩니다. 예를들어 맑음 -> 흐림으로 가는 선분의 확률은 0.3 입니다.

여기에 관측열로 첫째날부터 마지막날까지의 아이스크림 소비량을 적고 확률을 계산해보겠습니다. 

위 그림 역시 두번째 날까지의 특정 경우에만 확률을 표시했습니다 (모두 적기는 너무 힘들것 같습니다..ㅠ)

이해가 되시나요??

이렇게 첫번째 날에 나온 결과를 이용하여 두번째, 세번째 날 ... 마지막 날까지의 확률을 순차적으로 구할 수 있습니다.

맨처음에 사용했던 방법과 어떤점이 다를까요??

차이점은 이전에 계산했던 결과를 이용하여 같은 연산을 반복하는 과정을 생략하는 것입니다!

다이나믹 프로그래밍을 이용했다고 할 수 있습니다. 이것이 바로 Forward algorithm입니다.

이로써 인자와 특정 출력이 주어졌을 때, 주어진 출력이 나올 확률을 계산하는 방법에 대해 알아보았습니다. 

그리 어렵지 않을 것이라 생각하지만, 처음 접하시는 분들 입장에선 그림이 잘 이해가 안되실 수 있습니다. 

이해가 안되시면 어느 부분이 안되는지 댓글 달아주시고, 그림이 조금 더 디테일이 필요하면 수정하겠습니다.

다음 포스팅엔 HMM의 두번째 문제를 해결하는 방법에 대해 알아보겠습니다!