[NLP] Beam Search

https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture08-nmt.pdf

 

보통 NLG 같은 task에서는 자연어를 생성할 때 매 타입스텝마다 decoder를 거쳐서 나온 단어가 다음 타임스텝의 input으로 들어가게 된다. 그리고 decoder에서는 매 타임스텝마다 가장 확률이 높은 단어를 선택해서 출력을 하게 되는데 이것을 Greedy decoding이라고 한다.

 

하지만 Greedy decoding의 문제점은 매 타임스텝의 최대 확률 값만을 고려하는 것이 전체 타임스텝으로 보면 적절하지 않은 문장을 출력으로 가지게 될 수 있다는 점이다.

Greedy decoding의 문제점

 

 

그렇다면 greedy decoding에서 하는 방식인 현재 타입스텝만의 확률을 고려하는 방식이 아닌 전체 타임스텝에 대하여 확률을 고려하여 출력을 하는 방법이 있지만 그러한 방법은 계산해야 하는 경우의 수가 기하급수적으로 늘어나게 된다.

예를 들어 단어집합이 40000개 타임스텝이 10개라면 40000^10의 경우의 수를 모두 고려해야 하는 것이다.

 

그리하여 beam search의 기본 아이디어는 매 타입스텝마다 모든 가능한 경우의 수를 고려하여 계산하는 것이 아닌 K개의 가장 가능성이 있는 경우의 수만을 추적해서 가능한 출력 값으로 보관하는 것이다.

 

 

아래는 beam search 계산 예시이다.

k=2 일때의 beam search

k=2임으로 매 타임스텝마다 가장 가능성이 있는 2개의 출력 값을 추적한다.

 

Greedy decoding에서는 생성과정중에 <eos> 토큰이 출력 값으로 나오게 되면 생성을 멈추는데, beam search는 아래와 같은 조건이 충족될 때까지 계속되게 된다.

여기서 T와 n은 사용자 정의에 따라 달라질 수 있다.

그리고 최종적으로 가능성이 있는 K개의 출력값들 중에서 가장 score가 높은 값을 출력값으로 가지게 된다.

 

여기서 score를 길이로 normalize 해주는 이유는 사전에 정의해둔 T개의 타임스텝에 도달하기 이전에 <eos> 토큰을 생성하고 beam search를 종료한 문장들은 보통 더 낮은 score를 가지게 된다. 그러한 문장들을 normalize 해주지 않으면 최종 출력 값을 선정할 때 길이가 짧은 문장들이 더 좋은 score를 가지기 때문에 최종 출력 값으로 좀 더 유리한 score를 가질 수밖에 없다.

 

따라서 문장의 길이 or 타임스텝만큼 나누어 normalize를 해준 다음에 최종 score를 비교하게 된다.