비터비 알고리즘
14 Nov 2017 | Viterbi Dynanmic programming
이번 글에서는 비터비 알고리즘(Viterbi Algorithm)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
비터비 알고리즘이란 히든 스테이트의 최적 시퀀스(the most likely sequence of hidden states)를 찾기 위한 다이내믹 프로그래밍(dynamic programming) 기법의 일종입니다. 여기서 히든 스테이트란 은닉마코프모델 등의 추정 대상인 품사, 개체명 등을 가리킵니다. 은닉마코프모델에 적용된 비터비 알고리즘을 파이썬 코드로 구현한 내용은 이곳을 참고하시면 좋을 것 같습니다.
어쨌든 비터비 알고리즘을 이해하기 위해서는 은닉마코프모델 등의 아키텍처뿐 아니라 다이내믹 프로그래밍 개념(반복되는 계산 결과를 저장해 두었다가 풀기)을 익히고 있어야 하는데요. 이 글에서는 다이내믹 프로그래밍의 대표적 예시 가운데 하나이자 비터비 알고리즘과 유사한 기법인 Assembly-Line Scheduling을 중심으로 살펴 보겠습니다.
Assembly-Line Scheduling
Assembly-Line Scheduling 문제는 2개(혹은 그 이상)의 조립라인 사이에서 생산비용을 최소화하는 최적 경로(path)를 찾는 문제입니다. 다음 그림과 같습니다.
위 그림에서 동그라미는 비용(cost)을 나타냅니다. 제품은 1번 내지 2번 라인을 자유롭게 오갈 수 있습니다. 제품이 첫번째 공정에서 1번 라인에 보내진다면 그 비용은 2+7, 즉 9가 됩니다. 제품이 첫번째 공정에서 2번 라인에 보내진다면 비용은 4+8, 즉 12가 됩니다. 이를 식으로 쓰면 다음과 같습니다.
- $f_1[1]=2+7=9$
- $f_1[2]=4+8=12$
그러면 두번째 공정에서 제품이 1번 라인에 있다면 그 최소 비용(=$f_2[1]$)은 얼마일까요? 두 가지 경우의 수를 생각해 볼 수 있습니다. 첫번째 공정에서 1번 라인, 두번째 공정도 1번 라인인 case입니다. 또 첫번째 공정에서 2번 라인, 두번째 공정은 1번 라인인 case입니다. 두 경우 중 작은 값을 취해 구합니다.
\[\begin{align*}
{ f }_{ 2 }\left[ 1 \right] &=\min { \left( 2+7+9,4+8+2+9 \right) } \\ &=\min { \left( { f }_{ 1 }\left[ 1 \right] +9,{ f }_{ 1 }\left[ 2 \right] +2+9 \right) } \\ &=\min { \left( 18,23 \right) } =18
\end{align*}\]
그렇다면 두번째 공정의 1번 라인을 기준으로 보면, 1번 라인을 유지하는게 나을까요, 아니면 1번에서 2번으로 라인을 바꾸는 것이 좋을까요? 각각의 비용은 18, 23이므로 유지하는 것이 좋습니다. 제품이 두번째 공정에서 1번 라인에 있다면 생산비용을 줄이기 위한 제품의 최적 경로는 1번 라인(직전 공정) → 1번 라인(현재 공정)입니다.
이를 식으로 나타내면 다음과 같습니다.
- $l_2[1]=1$
같은 방식으로 $f_2[2]$와 $l_2[2]$를 구하면 각각 다음과 같습니다. 다시 말해 제품이 두번째 공정에서 2번 라인에 있다면 제품의 최적 경로는 1번 라인 → 2번 라인입니다.
- $f_2[2]=min(4+8+5,2+7+2+5)\=min(f_1[2]+5,f_1[1]+2+5)=min(17,16)=16$
- $l_2[2]=1$
그런데 구하는 과정을 자세히 보면 처음에 구한 $f_1[1]$과 $f_1[2]$을 다음 공정에 소요되는 최소 비용을 구할 때 재활용한다는 사실을 알 수 있습니다. 이처럼 계산과정이 반복될 때 중간 계산과정을 저장해 두었다가 해당 계산결과가 필요할 때 다시 써먹는 기법을 다이내믹 프로그래밍이라고 합니다.
위와 같은 과정을 반복해 각 단계별 최소 생산비용을 구한 표는 다음과 같습니다.
$j$
1
2
3
4
5
6
$f_j[1]$
9
18
20
24
32
35
$f_j[2]$
12
16
22
25
30
37
각 단계별 최적 경로는 다음과 같습니다.
$j$
2
3
4
5
6
$l_j[1]$
1
2
1
1
2
$l_j[2]$
1
2
1
2
2
자, 이제는 제품이 라인을 빠져나가는 경우를 생각해 봅시다. 제품이 여섯번째 공정까지 왔고 1번 라인에 있는 경우의 최소 소요비용($f_6[1]$)은 35입니다. 1번 라인에서 출하하는 데 드는 비용은 위의 그림을 보니 3입니다. 둘을 더한 38이 총 생산비용이 됩니다. 마찬가지로 2번 라인에 대해 총 생산비용을 구하면 37+2로 39가 됩니다. 따라서 총 생산비용을 최소화하는 제품 생산 경로는 마지막 여섯번째 공정 때 1번 라인에 있어야 합니다.
각 단계별로 backtrace를 한 결과는 다음과 같습니다.
- 총 생산비용을 최소화하려면, 제품은 다섯번째 공정에서 2번 라인에 있어야 한다. (∵ $l_6[1]=2$)
- 제품은 네번째 공정에서 2번 라인에 있어야 한다. (∵ $l_5[2]=2$)
- 제품은 세번째 공정에서 1번 라인에 있어야 한다. (∵ $l_4[2]=1$)
- 제품은 두번째 공정에서 2번 라인에 있어야 한다. (∵ $l_3[1]=2$)
- 제품은 첫번째 공정에서 1번 라인에 있어야 한다. (∵ $l_2[2]=1$)
이를 그림으로 나타내면 다음과 같습니다. 처음에 소개한 그림과 동일합니다.
Viterbi Algorithm
비터비 알고리즘을 애니메이션으로 만든 그림은 다음과 같습니다(출처). 현재 스테이트로 전이할 확률이 가장 큰 직전 스테이트를 모든 시점, 모든 스테이트에 대해 구합니다.
모든 시점, 모든 스테이트에 대해 구한 결과는 다음과 같습니다. (원래는 그물망처럼 촘촘하게 되어 있으나 경로가 끊어지지 않고 처음부터 끝까지 연결되어 있는 경로가 유효할 것이므로 그래프를 그린 사람이 이해를 돕기 위해 이들만 남겨 놓은 것 같습니다)
위 패스에서 만약 최대 확률을 내는 $k+2$번째 시점의 상태가 $θ_0$라면 backtrace 방식으로 구한 최적 상태열은 다음과 같습니다.
- $[θ_0, θ_2, θ_2, θ_1, θ_0, θ_1]$
이번 글에서는 비터비 알고리즘(Viterbi Algorithm)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
비터비 알고리즘이란 히든 스테이트의 최적 시퀀스(the most likely sequence of hidden states)를 찾기 위한 다이내믹 프로그래밍(dynamic programming) 기법의 일종입니다. 여기서 히든 스테이트란 은닉마코프모델 등의 추정 대상인 품사, 개체명 등을 가리킵니다. 은닉마코프모델에 적용된 비터비 알고리즘을 파이썬 코드로 구현한 내용은 이곳을 참고하시면 좋을 것 같습니다.
어쨌든 비터비 알고리즘을 이해하기 위해서는 은닉마코프모델 등의 아키텍처뿐 아니라 다이내믹 프로그래밍 개념(반복되는 계산 결과를 저장해 두었다가 풀기)을 익히고 있어야 하는데요. 이 글에서는 다이내믹 프로그래밍의 대표적 예시 가운데 하나이자 비터비 알고리즘과 유사한 기법인 Assembly-Line Scheduling을 중심으로 살펴 보겠습니다.
Assembly-Line Scheduling
Assembly-Line Scheduling 문제는 2개(혹은 그 이상)의 조립라인 사이에서 생산비용을 최소화하는 최적 경로(path)를 찾는 문제입니다. 다음 그림과 같습니다.
위 그림에서 동그라미는 비용(cost)을 나타냅니다. 제품은 1번 내지 2번 라인을 자유롭게 오갈 수 있습니다. 제품이 첫번째 공정에서 1번 라인에 보내진다면 그 비용은 2+7, 즉 9가 됩니다. 제품이 첫번째 공정에서 2번 라인에 보내진다면 비용은 4+8, 즉 12가 됩니다. 이를 식으로 쓰면 다음과 같습니다.
- $f_1[1]=2+7=9$
- $f_1[2]=4+8=12$
그러면 두번째 공정에서 제품이 1번 라인에 있다면 그 최소 비용(=$f_2[1]$)은 얼마일까요? 두 가지 경우의 수를 생각해 볼 수 있습니다. 첫번째 공정에서 1번 라인, 두번째 공정도 1번 라인인 case입니다. 또 첫번째 공정에서 2번 라인, 두번째 공정은 1번 라인인 case입니다. 두 경우 중 작은 값을 취해 구합니다.
\[\begin{align*} { f }_{ 2 }\left[ 1 \right] &=\min { \left( 2+7+9,4+8+2+9 \right) } \\ &=\min { \left( { f }_{ 1 }\left[ 1 \right] +9,{ f }_{ 1 }\left[ 2 \right] +2+9 \right) } \\ &=\min { \left( 18,23 \right) } =18 \end{align*}\]그렇다면 두번째 공정의 1번 라인을 기준으로 보면, 1번 라인을 유지하는게 나을까요, 아니면 1번에서 2번으로 라인을 바꾸는 것이 좋을까요? 각각의 비용은 18, 23이므로 유지하는 것이 좋습니다. 제품이 두번째 공정에서 1번 라인에 있다면 생산비용을 줄이기 위한 제품의 최적 경로는 1번 라인(직전 공정) → 1번 라인(현재 공정)입니다.
이를 식으로 나타내면 다음과 같습니다.
- $l_2[1]=1$
같은 방식으로 $f_2[2]$와 $l_2[2]$를 구하면 각각 다음과 같습니다. 다시 말해 제품이 두번째 공정에서 2번 라인에 있다면 제품의 최적 경로는 1번 라인 → 2번 라인입니다.
- $f_2[2]=min(4+8+5,2+7+2+5)\=min(f_1[2]+5,f_1[1]+2+5)=min(17,16)=16$
- $l_2[2]=1$
그런데 구하는 과정을 자세히 보면 처음에 구한 $f_1[1]$과 $f_1[2]$을 다음 공정에 소요되는 최소 비용을 구할 때 재활용한다는 사실을 알 수 있습니다. 이처럼 계산과정이 반복될 때 중간 계산과정을 저장해 두었다가 해당 계산결과가 필요할 때 다시 써먹는 기법을 다이내믹 프로그래밍이라고 합니다.
위와 같은 과정을 반복해 각 단계별 최소 생산비용을 구한 표는 다음과 같습니다.
| $j$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| $f_j[1]$ | 9 | 18 | 20 | 24 | 32 | 35 |
| $f_j[2]$ | 12 | 16 | 22 | 25 | 30 | 37 |
각 단계별 최적 경로는 다음과 같습니다.
| $j$ | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| $l_j[1]$ | 1 | 2 | 1 | 1 | 2 |
| $l_j[2]$ | 1 | 2 | 1 | 2 | 2 |
자, 이제는 제품이 라인을 빠져나가는 경우를 생각해 봅시다. 제품이 여섯번째 공정까지 왔고 1번 라인에 있는 경우의 최소 소요비용($f_6[1]$)은 35입니다. 1번 라인에서 출하하는 데 드는 비용은 위의 그림을 보니 3입니다. 둘을 더한 38이 총 생산비용이 됩니다. 마찬가지로 2번 라인에 대해 총 생산비용을 구하면 37+2로 39가 됩니다. 따라서 총 생산비용을 최소화하는 제품 생산 경로는 마지막 여섯번째 공정 때 1번 라인에 있어야 합니다.
각 단계별로 backtrace를 한 결과는 다음과 같습니다.
- 총 생산비용을 최소화하려면, 제품은 다섯번째 공정에서 2번 라인에 있어야 한다. (∵ $l_6[1]=2$)
- 제품은 네번째 공정에서 2번 라인에 있어야 한다. (∵ $l_5[2]=2$)
- 제품은 세번째 공정에서 1번 라인에 있어야 한다. (∵ $l_4[2]=1$)
- 제품은 두번째 공정에서 2번 라인에 있어야 한다. (∵ $l_3[1]=2$)
- 제품은 첫번째 공정에서 1번 라인에 있어야 한다. (∵ $l_2[2]=1$)
이를 그림으로 나타내면 다음과 같습니다. 처음에 소개한 그림과 동일합니다.
Viterbi Algorithm
비터비 알고리즘을 애니메이션으로 만든 그림은 다음과 같습니다(출처). 현재 스테이트로 전이할 확률이 가장 큰 직전 스테이트를 모든 시점, 모든 스테이트에 대해 구합니다.
모든 시점, 모든 스테이트에 대해 구한 결과는 다음과 같습니다. (원래는 그물망처럼 촘촘하게 되어 있으나 경로가 끊어지지 않고 처음부터 끝까지 연결되어 있는 경로가 유효할 것이므로 그래프를 그린 사람이 이해를 돕기 위해 이들만 남겨 놓은 것 같습니다)
위 패스에서 만약 최대 확률을 내는 $k+2$번째 시점의 상태가 $θ_0$라면 backtrace 방식으로 구한 최적 상태열은 다음과 같습니다.
- $[θ_0, θ_2, θ_2, θ_1, θ_0, θ_1]$
Comments