Beam Search

(Beam Search의 본질적인 개념보단, Seq2Seq with attention 모델에서의 Beam Search가 어떤식으로 작동하는지에 대해 작성하였습니다.)

 

Beam Search는 Seq2seq with attention 등 자연어의 생성 모델에서, 최종적으로 생성된 결과값의 퀄리티를 높이기 위한 전략입니다.

 

BFS와 유사한 방식으로 동작하지만, 모든 가능성을 탐색(완전탐색)하지않고, 가장 가능성이 높은 후보들만 유지하여 효율적으로 탐색합니다.

 

---

 

Seq2Seq의 Decoder 에서의 Beam Search

Seq2seq과같은 자연어 생성 모델은 다음 단어를 예측할 때 Greedy decoding방식(가장 확률이 높은 단어 하나)을 기반으로 학습되고, Task를 처리합니다. (시간복잡도 O(t), t는 타임스텝 길이)

 

다만, 이렇게 하면 아쉬운 지점이 있는데, 각 타임스텝마다 했던 최선의 선택이 전체로 봤을 때 최선의 결과가 아닐수도 있다는 점입니다.

 

예를 들어, "나는 밥을 먹고나서 커피를 먹었다" 라는 문장을 영어로 번역하는 작업을 예시로 생각해보면, 이에 대한 올바른 출력값은 "I had coffee after meal" 일 것입니다.

 

그러나 예를 들어, I 다음에 had를 빼먹고 coffee를 예측했다고 하면(이유가 뭐가 됐든), 그 이후의 단어를 예측하는 방향이 점점 이상해질것입니다.

 

해결 방안

두 가지 방식을 생각해볼 수 있습니다.

 

1. Exhaustive Search, 완전 탐색 - 매 타임스텝마다 Vocab에 있는 모든 단어들에 대한 확률값을 싹 다 확인해보는 방법

2. Beam Search - Greedy Decoding방식과 Exhaustive Search방식의 타협점이 되는 방식으로, 매 타임스텝마다 상위 k개(Beam Size)의 경우의 수만 고려하여 답변을 생성하는 알고리즘을 사용하는 방법.

 

1번 방식은 할 수만 있다면 항상 최선의 답변을 보장받을 수 있겠지만, 현실적으로 불가능한 방법입니다. 가령 Vocab의 사이즈를 V라고 하고, 타임스텝을 t라고 하면, V^t 개의 가지수를 고려해야한다는 뜻이기 때문입니다.

 

반면, Beam Search(2번 방식)의 경우 생성 속도와 성능의 Trade Off에 대한 타협점입니다. 최선의 답변을 보장하는 방식은 아니지만, 그래도 Greedy한 방식보단 더 최선의 답변을 뱉어낼 가능성이 높은 방식이라고 볼 수 있습니다. 시간 복잡도 또한 O(k*V*t)로, 완전 탐색보다 계산량을 훨씬 줄일 수 있습니다. (k는 Beam Size)

 

다만, 로그 확률의 합산 방식으로 인해, 출력하는 전체 시퀀스의 길이가 길어질수록 이전에 생성했던 시퀀스에 대한 스코어들이 누적되어 일반적으로 시퀀스가 긴 출력문장은 짧은 시퀀스보다 불리합니다. 따라서 이에 대한 정규화를 위해 문장의 시퀀스 길이로 나누어줍니다.

 

무조건 좋은건 아니다

시간 복잡도를 다시 비교해보면, 아래와 같습니다.
Greedy Decoding: O(t)

Beam Search: O(k*V*t)

Exhaustive Search: O(V^t)

 

그리디 방식 말고 아래 두 방식은 V가 포함되어있는데, 이는 결국 Beam Search도 전체 Vocab에 대한 확률 분포를 계산해야한다는 것입니다. 따라서 이에 대한 계산량을 또 다시 줄이기 위한 기법으로, Top-k Sampling(매 타임스텝마다 확률이 높은 k개의 단어만을 선택하고, 그 후보들만 고려하는 기법), Top-p Sampling(누적 확률이 p이상인 단어들만 선택하여 후보를 추적하는 기법)과 같은 기법들이 사용되기도 합니다.

---

 

Ref : https://blog.naver.com/sooftware/221809101199

[Sooftware 머신러닝] Beam Search (빔서치)

https://littlefoxdiary.tistory.com/4

자연어 생성에서의 Beam Search / 파이썬으로 Beam Search 구현하기

https://www.boostcourse.org/ai330/lecture/1455757?isDesc=false

자연어 처리의 모든 것

https://huggingface.co/blog/how-to-generate?fbclid=IwAR19kbEiW_sF19TeSr4BE4jQZSIqz0GzOFD2013fIGEH32DReW9pAFq6vDM

How to generate text: using different decoding methods for language generation with Transformers