[Data Mining] Forward-Backward algorithm

이번 포스팅은 내가 이전에 공부하다가 몰라서 잠깐 미뤄뒀던 Forward-Backward algorithm이다. 알고 보면 그렇게 어려운 내용은 아니었던 것 같은데 왜 이렇게 오래걸렸을까? 아무래도 여러가지 probability를 표현하는 기호에 익숙하지 않았던 것, 그리고 Forward-Backward algorithm에 나오는 기본 전제를 간과해서. 아무래도 후자가 조금 큰 것 같다. 아무튼 Forward-Backward algorithm 설명해보도록 하자.

Forward-Backward algorithm를 구하기 위해서 필요한 data는 observation sequence와 initial transition probability matrix, initial emission probability matrix이다. initial transition probability matrix와 initial emission probability matrix는 기본적으로 HMM의 parameter에 해당한다. 왜 initial이라는 단어를 붙였냐면, 기본적으로 Forward-Backward algorithm는 HMM의 parameter를 training하기 위한 algorithm이기 때문이다. 자, observation sequence도 분명 필요한 data라는 것을 다시 한번 되세기자.

이전에 포스팅했던 Forward algorithm과 Viterbi algorithm에서 사용했던 예제를 다시 사용하여 이야기해보면,

# Observation sequence : 10 - 1 - 4

# HMM parameter

이렇게 두 개가 주어진 상태에서, Forward-Backward algorithm를 돌리는 것이다. Forward-Backward algorithm의 최종 목적은 HMM parameter를 training하는 것이다. 편의상 transition probability matrix를 A로 놓고 emission probability matrix는 B로 놓자.

Transition probability matrix = A

Emission probability matrix = B

그러면 우선 probability 수학식보다는 머리 속으로 직관적으로 말해보자.

우선 A에서 분자 부분을(expected number of transition from state i to state j) 먼저 설명해보자. 기호 말고 예시로 생각을 해보자.

위와 같이 observation sequence가 time 1, 2, 3에 각각 10 1 4로 주어졌고, state의 가능한 값들은 sunny, rainy라고 해보자. 우리가 구하고자 하는 Aij는 가령, sunny에서 rainy로 넘어가는 확률이다. 이것을 어떻게 구할까? 

time 1 → time 2만 놓고 생각해보자. sunny → rainy가 될 확률은

sunny → rainy로 기대되는 횟수를 sunny → rainy와 sunny → sunny로 기대되는 횟수로 나누는 것이다. 그러면 time 1 → time 2에 sunny → rainy로 넘어가는 확률은 어떻게 구할까?

여기서 forward probability와 backward probability를 사용한다. 

forward probability : start state(time 0)에서 time 1까지 observation sequence가 10일 확률

backward probability : time 2에서 final state(time 3)까지 observation sequence가 1 - 4일 확률

forward probability는 이전 포스팅에서 자세하게 설명했으므로 여기서는 생략하자. backward probability 어떻게 구하는지는 마지막에 살짝 link만 남겨놓겠다. 여기서는 우선 무시하고 backward probability가 의미하는 확률을 제대로 정의하고만 넘어가자.

time = 2에서 rainy일 backward probability를 구한다고 하면,

backward probability는 start state와 time = 1은 고려하지 않고(가정하고), time = 2부터만 고려한 probability가 된다. 따라서 time = 1까지의 확률은 1이라고 가정하고 time = 2부터의 확률을 계산하는 것이다. time = 2부터 observation sequence가 1 - 4로 주어질 확률이 backward probability이다.

여기서 잠깐, 왜 backward이냐? 이건 아래에 backward probability를 구하는 링크를 따라가서 공부해보면 알 수 있다. 젤 뒤에 final state부터 차례차례 거슬러올라가는 식으로 계산이 되기 때문이다. forward algorithm을 뒤집어 놓은 거라고 생각하면 된다. 그래서 backward이다.

자 그럼 다시 time 1 → time 2에 sunny → rainy로 넘어가는 확률에 대해서 생각해보자. 

즉 time 1 → time 2에 sunny → rainy로 넘어가는 확률은 위의 그림에서 forward probability, backward probability 그리고 p(sunny→rainy) * p(1|sunny)를 모두 곱한 확률이 되겠다. 우리는 이 확률을 간단하게 기호를 사용해서 나타내려고 한다.

A에서 분자 부분은(expected number of transition from state i to state j) 위의 확률이 모든 time에 대하여 나타날 확률을 모두 더한 것이다. 따라서

이렇게 된다. A에서 분모부분은 어떻게 될까? state i에서의 모든 transition을 모든 t에 대하여 해주면 되는 부분이므로 최종적으로 우리가 원하는 식은 아래와 같게 된다.

자, 지금까지 절반했다. 나머지 절반은 emission probability를 구하는 식이다. 

위의 두번째 b가 emission probability를 구하는 식이다. 위의 식에서 분모부분은 어떻게 구할까? 특정 time t에 state j에 있을 확률을 구한 후 그것을 모든 t에 대하여 더해주면 되겠다. 가령 time = 2에 sunny에 있을 확률을 그림으로 나타내면 아래와 같다.

즉 time = 2에 sunny에 있을 확률은

이렇게 되고 이것을 state j, time t에 대하여 일반화시키면 아래와 같이 된다.

이것을 모든 t에 대하여 sum을 한 것이 우리가 원하는 emission probability의 분모부분이다.

그러면 분자부분은 무엇인가? 분자 부분은 state j에 있고 Vk를 관찰할 확률이므로, 단순히 observation probability matrix를 확인해서 곱해주면 될 것 같다.(이상하게 이부분은 책에 명시되어 있지 않아서 내가 스스로 생각한 부분이다.) 이것을 수식으로 나타내면 아래와 같다.

내 블로그에 예시가 없으면 섭하다. 그런데 이번에는 적당한 예시를 못 찾았다.ㅠㅠ 예시를 만들수는 있으나 그래도 검토까지 해서 맞는지 전부 확인하고 올리는 것이 기본인데, 아직 적당한 예시를 못 찾았다. 그래서 일단 예시는 skip하고 여기서 포스팅 마무리하려고 한다. 

다음에 적절한 예시를 찾으면 수정하는 것으로 하자.