HMM과 비터비 알고리즘(Viterbi Algorithm)

이전 글에서는 은닉 마르코프 모델(Hidden Markov Model, HMM)에 대해 알아보았다. HMM에서 가장 확률이 높은 조합을 알아내기 위해서 모든 경우의 수를 일일이 계산해야 했다. 오늘 글에서 다룰 비터비 알고리즘(Viterbi Algorithm)은 ‘가장 확률이 높은 조합’을 찾을 때 사용하는 알고리즘이다. 참고: 자연어처리에서는 이를 ‘디코딩(Decoding)’한다고 한다.

■ 최적 경로를 찾는 네비게이션 – 비터비 알고리즘

지난 글에서 다룬 예제 문제를 그대로 가져와서 다시 한 번 살펴보자. 각각의 전이 확률(Transition Probability)과 출력 확률(Emission Probability)은 다음과 같고, 사전 확률(Prior Probability) 역시 동일하게 A = 2/3, B = 1/3 이다.

■ 예제로 알아보는 비터비 알고리즘

홍길동이란 고객의 구매 데이터는 다음과 같다.

A – A – B – B – B – A

A 브랜드를 구입한 횟수도 3번, B 브랜드를 구입한 횟수도 3번이다. 이 때 홍길동의 브랜드 선호도는 어떻고, 그에 대한 변화가 있을까?

브랜드는 여전히 A, B로 2개의 선택지만이 있지만, 구매 데이터가 3개에서 6개로 늘어나는 경우이다. 이 때 총 경우의 수는 2⁶ 이다(2개의 선택지가 6번 있으므로). 하나씩 계산하기에 너무 많으니 비터비 알고리즘을 사용해서 문제를 풀어본다.

먼저 첫 번째 구매 기록부터 살펴보자. 이 때 홍길동은 브랜드 A를 선호하여 구매까지 이어졌을 수도 있고, 브랜드 B를 선호하지만 A를 구매했을 수도 있다.

A = \frac{2}{3} * 0.8 = 0.533

B =  \frac{1}{3} * 0.4 = 0.133

A 브랜드 선호의 사전 확률은 2/3이고, A 브랜드를 선호하는 사람이 A를 구매할 출력 확률이 0.8이므로 계산하면 0.533이다. 마찬가지로 B 브랜드 선호의 사전 확률은 1/3이고, B 브랜드를 선호하는 사람이 A를 구매할 출력 확률이 0.4이므로 확률을 계산하면 0.133이다.

두 번째 구매부터 조금 더 신경써서 살펴봐야한다.

먼저 두 번째 구매에서 브랜드 A를 선호할 경우(a – 그림에서 파란색 하트의 확률)와
브랜드 B를 선호할 경우(b – 그림에서 빨간색 하트의 확률)로 나뉜다.

각각의 하트는 다시 두 가지 경우의 수로 나뉘는데 먼저 a 파란색 하트를 살펴보자.
첫 번째 구매 시 브랜드 A를 선호하고 두 번째 구매에서도 브랜드 A를 선호할 경우 (1)와
첫 번째 구매 시 브랜드 B를 선호하였지만 두 번째 구매에서는 브랜드 A를 선호할 경우 (2)로 나눠진다.

(1)의 경우에는 브랜드 A를 선호하는 확률 0.533 * 브랜드 A에서 다시 브랜드 A를 선호할 전이 확률 0.8 * 브랜드 A를 선호하는 사람이 브랜드 A를 구매할 출력 확률 0.8을 곱해서 구한다.

(2)의 경우에는 브랜드 B를 선호하는 확률 0.133 * 브랜드 B에서 브랜드 A를 선호할 전이 확률 0.4 * 브랜드 A를 선호하는 사람이 브랜드 A를 구매할 출력 확률 0.8을 곱해서 구한다.

이 과정을 좀 더 수식으로 간략화하면 출력 확률을 동일하므로 괄호 밖으로 빼서 묶고, 최대 값을 뽑는 맥스(Max) 함수를 써서 Max(0.533*0.8, 0.133*0.4) * 0.8 = 0.341 을 얻는다. 빨간색 하트 b의 확률도 이와 동일하게 구하면 된다.

그리고 이 과정을 반복해서 3번째 구매, 4번째 구매, …. n번째 구매까지 반복하면 된다.

이전 확률을 가져와서 동일한 전이 확률을 곱하는 과정이 반복됨을 눈치챌 수 있다.

모든 단계에 대한 선호도 확률을 구하고 나면 가장 마지막 단계부터 선호도 확률이 높은 순서를 타고 올라가면 된다(그림에서 우측에서부터 좌측으로 따라가면 된다). 즉, A-A-B-B-B-A를 구매한 고객의 브랜드 선호도는 A-A-A-B-B-A 라고 추론할 수 있게 되었다. A 회사의 마케터라면 세 번째 구매에서 A를 선호하지만 B를 구매한 이유를 탐색해보고 대응 방안을 준비할 수 있다.

■ 히든 마르코프 모델(HMM)의 단점

1) 파라미터가 너무 많다.

비터비 알고리즘이 계산을 좀 더 용이하게 해주지만, 기본적으로 HMM 방법은 파라미터가 많다는 단점이 있다. 우리의 경우 2가지 브랜드로 한정해서 예제를 풀어봤지만, 현실에서 소비자가 선택하는 브랜드의 가지수는 N만큼 많으며, 구매 기록 역시 M만큼 많다. 이를 HMM으로 해결하려면 M*N + N² + N 파라미터가 필요하다.

2) 생성 모델(Generative Model)이다.

HMM은 p(X, Y)를 모델링한다. 예측에 필요한 것은 p(Y|X) 뿐인데 말이다.

3) 이진 변수/숫자형 변수를 다루지 못한다.

HMM은 오직 다항 관측치(multinomial observables)에서 관찰된 다항 레이블(multinomial labels)만을 예측한다. binary, numeric feature에 대해서는 다루지 못한다는 한계점이 있다.

이런 한계를 극복하기 위해 도입되는 기법이 바로 CRF(Conditional Random Fields)이다. 이 부분은 우리가 지금 본 관점보다는 자연어처리에서 더 많이 다뤄지기 때문에 자연어처리를 정리할 때 다시 다뤄보겠다.