Greedy Decoding vs. Beam Search vs. Exhaustive Search: 텍스트 생성 알고리즘 비교

안녕하세요, 제이덥입니다! 기술 면접을 준비하면서 기초 개념들을 하나씩 정리해보고 있는데요. 오늘은 Text Generation모델의 텍스트 생성 알고리즘에 대해서 다뤄보려고 합니다. 대표적인 텍스트 알고리즘 중 가장 대표적이며 학습자/실무자 쉽게 접할 수 있는 Greedy Decoding, Exhaustive Search, Beam Search 3가지 알고리즘의 정의/장점/한계에 대해 정리하여 포스팅합니다. 

 

0️⃣ 문장을 생성할 때 학습만 하면 다 된 것 아니야?

Sequence to Sequence Model with Attention(이하, Seq2Seq 모델), 즉 자연어 생성모델에서 디코더는 다음 토큰에 대한 확률 값을 계산하여 문장을 출력합니다. 하지만, 매 타임 스텝마다 다음 단어 중 가장 높은 확률을 선택하는 것이 늘 항상 좋은 결과를 가지는 것이 아닙니다. 이럴 경우 전체 문장 맥락과 어긋난 문장을 출력할 수 있어 저품질의 문장을 생성할 수 있습니다. 또 오로지 높은 성능만 추구할 경우(Exhaustive Search) 연산 속도가 커지고 생성 속도가 느려져 실제 서비스 상황에서는 응답 지연이 발생할 수 있습니다. 결국 속도와 성능을 고려해야 하기에, 이번 글에서는 Greedy Decoding, Exhaustive Search, Beam Search를 이러한 관점에서 살펴볼 것입니다. 

1️⃣ Greedy Decoding

자연어 생성 모델은 주어진 맥락에서 다음 단어 만을 예측하는 작업을 수행합니다. Greedy Decoding은 매 타임 스텝마다 가장 높은 확률을 가진 단어 하나를 선택하는 작업을 순차적으로 진행해 문장 생성을 진행합니다. 따라서 매 타인스텝마다 가장 높은 확률을 가진 다음 단어만을 고려하기에 생성하기에 속도는 빠르지만, 전체 Sequence 즉 문장을 고려하지 못하며, 이미 선택된 단어는 되돌릴 수 없어 결과적으로 부정확한 문장을 생성할 위험이 있습니다. 예컨대 “I participate in the Geultto community”라는 문장을 학습했더라도, 만약 ‘participate’ 뒤에 올 단어로 ‘a’가 최대 확률로 잘못 산정된다면 실제 출력은 “I participate in a…”가 되어 맥락상 어색한 문장이 될 수 있습니다.

2️⃣ Exhaustive Search

Exhaustive Search는 Joint Probability를 이용하여 단어가 생성될 때마다 전체 문장의 확률을 고려하는 기법입니다. 아래 식을 보겠습니다. 전체 문장을 $y$라고 생각하고 각 단어를 $y_1, y_2, ..., y_n$ 이라고 했을 때, $y_2$는 $P(y_2 | y_1, x)$와 같이 $y_1$까지 고려하여 생성합니다. 이후 생성되는 단어들도 마찬가지로 $y_3$는 $y_2, y_1$을 그리고 $y_4$는 $y_3,y_2,y_1$을 참조하여 생성합니다. 즉, 모델은 n번째 단어는 n-1부터 첫번째 단어까지 고려하여 생성하게 되는 것이죠. 이렇게 되면 단일 단어의 확률 값이 조금은 낮더라도 전체적으로 확률이 높은 문장을 찾을 수 있어 결과 품질이 좋아집니다. 다만, 타임 스텝을 t, 단어를 V라고 가정하면 $O(V^t)$의 매우 큰 시간 복잡도를 가지게 되어 실제 서비스 환경에서 응답 속도가 극단적으로 느려질 수 있다는 문제점을 가지고 있습니다. 

 

$$
P(y|x) = P(y_1 | x) \cdot P(y_2 | y_1, x) \cdot P(y_3 | y_2, y_1, x) \dots P(y_T | y_1, \dots, y_{T-1}, x)
$$

$$
= \prod_{t=1}^{T} P(y_t | y_1, \dots, y_{t-1}, x)
$$

3️⃣ Beam Search

Beam Search는 Greedy Search와 Exhaustive Search의 단점을 보완한 방식으로, 각 타임 스텝에서 확률이 높은 상위 k개의 후보만 유지하며 문장을 생성해나가는 기법입니다. 예를 들어 아래의 다이어그램과 같이 k=2인 Beam Search를 하는 상황을 가정해 봅시다. <START> 토큰이 시작되고 가장 확률이 높은 두 단어인 he, hit을 선택합니다. 이후, 이 두 단어를 이용해 두 번째 타임스텝에서는 [he hit, he struck, I was, I got]와 같이 이어질 수 있는 후보군을 생성한 뒤, 이 중 가장 높은 확률을 가진 he hit, I was만 남겨서 다음 단어를 생성합니다. 이와 같이 매 타임 스템마다 제일 높은 확률을 가진 k개의 후보를 유지하며 문장을 생성합니다. 이러한 과정이 <EOS> 토큰이 등장할 때까지 반복하고, 만일 특정 경우만 <EOS> 나온다면 해당 경우만 중지하고, 나머지는 다시 <EOS > 토큰이 나올 때까지 진행하여 모든 가설에 <EOS>가 나오면 탐색을 끝냅니다. (혹은, T라는 타임스텝 파라미터를 지정하여 T타임 스템이 지나면 끝나도록 구현할 수도 있습니다.) 이후 탐색이 종료되고 남은 문장들 중 확률이 가장 높은 문장을 선택합니다. 다만,  동시사건확률을 고려하여 계산하기 때문에 문장이 짧을수록 더 높은 확률을 가진다는 단점이 있습니다. 그래서 이를 보정하고자 타임스텝 개수(t)로 최종 스코어를 나눠서 평균 확률값을 최종 스코어로 사용합니다. 

 

그림 출처 : CS224n

 

 

4️⃣ 글을 맺으며,,,

이처럼 문장을 학습한 뒤에도 디코더 레벨에서 문장을 생성할 때는 다양한 알고리즘을 적용할 수 있습니다. 실제 서비스 상황에서는 생성 속도와 정확도를 균형 있게 고려해야 하며, 세 가지 알고리즘 중에서는 Beam Search가 가장 널리 활용됩니다. 특히 Beam Search는 Greedy나 Exhaustive Search에 비해 속도와 품질의 절충안을 제공하므로, 생성 속도와 정확도를 모두 충족하기 위해 적절한 k 값을 선택하는 것이 핵심입니다.

출처 :

• 부스트코스 강의 : 자연어 처리의 모든 것 - Beam Search
• StanFord CS224n 강의 노트