#6 Viterbi-Search

* 8주차 강의 내용입니다.

 

가장 최적의 path를 찾아가는 search - 딥러닝 문제 해결

1) 품사 분석기(Part of Speech Tagging)

 Viterbi-Search는 머신러닝 분야에서 최종적으로 의사 결정(Descision Making)을 할 때 최적의 path를 찾아 나가는 탐색 알고리즘이다. 이 알고리즘을 이해하기 위해 사용되는 가장 대표적인 예시는 품사 분석기(Part of Speech Tagging)인데, 용어 그대로 주어진 문장에서 요소들을 추출하고 품사를 결정하는 문제를 말한다.

 

 squence of word가 들어왔을 때 각 word를 w1, w2, ... wk라고 했을 때 각 word는 특정 태그를 가질 수 있을 것이며 이는 squence를 가진다. 즉, sequence of tagging의 path를 찾는 문제라는 것(높은 확률을 지닌)

 

 이 때 각 스코어는 확률로써 나타날 것이며 확률 모델은 HMM(Hidden Markov Model)을 사용한다.

 

HMM(Hidden Markov Model)

 Viterbi-Search와 거의 한 세트로 나오는 개념이다. squence of event가 주어졌고, 우리가 관심있는 이벤트를 ek라고 했을 때 ek에 영향을 주는 것은 아마 ek 이전에 일어난 모든 이벤트 즉, 과거일 것이다(P(ek | PAST)). 하지만 이를 구하기 위해 모든 과거에 대해 정의하고 확률을 따지기란 쉽지 않은 일이다.

 

 이러한 복잡한 모델링 상황에서 아주 단순하게 바로 전의 이벤트들의 확률을 정의할 수 있도록 대단히 강한 조건을 걸자라는 것이 기본 아이디어이다. 

 

 바로 전 이벤트에서 다음 이벤트로 transition되는 확률로만 모델링할 수 있다고 가정한다. 아주 강한 제약이지만, 어찌보면 현실성 있는 제약이다. 이게 너무하다 싶으면 과거 이벤트 갯수를 늘릴 수 있다. 갯수에 따라 first order, second order property라고 불린다. 이렇게 하는 것이 일단은 Markov Model이다.

 

 HMM은 Hidden이라는 개념이 매우 중요하게 작용한다. 이 Hidden Variable 이라는건 DNN에서 설명한 Hidden과 같다. 어떤 값이던 될 수 있으며 관측이 불가능하고 셀 수 없는 즉, 우리 상상속에만 존재하는 variable 이다. Markov Model에 Hidden을 적용한 것이 HMM이다.

 

--

 

 다시 PoS로 돌아와서, 위 수식을 한번 보자. 1부터 n까지 가장 확률이 높은 태그들의 조합(squence of tagging)을 위와 같이 표시하겠다는 뜻이다. 하지만 저것을 그대로 계산하지 않을 것이다. 비용이 매우 많이 들기 때문이다. 우리는 HMM을 적용하여 위의 수학적 모델을 단순화 시킬 것이다.

 

 

 우선 조건부 확률의 성질을 이용하면 위와 같이 바꿀 수 있다. 여기서 분모 즉 P(w1~n)를 보면 단어의 나열을 뜻한다. 헌데 단어의 나열은 이미 벌어진 사건이며 tagging을 하는데는 굳이 필요가 없는 element이기 때문에 위 수식에서는 거의 상수에 가깝다. 어차피 공통적인 요소이기 때문에 상대적인 우위를 비교할 때 무시(drop)할 수 있다는 것이다.

 

 

 분모를 제거한 뒤의 수식이다. 이 때 보면 P(w|t)라고 되어있는데 이는 처음과는 순서가(t|w) 바뀌어 있다. 여기까지는 단순히 확률에 기반한 drop이였지만 HMM을 적용하여 생각해보자.

 

 

--

 

Viterbi Algorithm

 가령 back이라는 word에 도달했을 때 우리가 생각할 것은 back 까지 오는데 가장 높은 스코어를 기록하면서 오는 path는 무엇인가? 이다. 즉, 문제를 단순화 하자는 것이다. back이면서 VB일 확률과 과거의 최고의 path 확률 값을 곱한 값이 back의 확률 값이 된다는 것이다. 즉, observation과 trasition 확률을 곱해서 Vt로 바꾸고 업데이트 하자는 것

 

 

 조금 더 부연 설명해서 우리가 time t에 있다고 해보자. 적어도 t-1까지 갈 확률이 이미 계산되어 있는데 이것이 vt-1(i)이다. 즉, 과거의 일은 신경 쓰지 말고 observation을 구하고 과거 최고의 스코어를 곱하면 된다.