디코딩 전략: Greedy, Beam Search, Random, Temperature, Top-K, Nucleus

들어가며

• 자연어생성 (NLG) 태스크에서, 딥러닝 언어 모델은 일반적으로 한 번에 토큰(예: 단어) 하나를 생성하며 문장을 만듦
• 어떤 생성 (디코딩) 전략을 선택하느냐에 따라 생성된 답변이 참신할 수도 있고, 정확할 수도 있고, 혹은 지루하거나 너무 일반적일 수 있음

Greedy

• greedy란 욕심많은 이라는 뜻
• 이름에서도 볼 수 있듯이 가장 욕심많은, 즉 다음 토큰이 될 확률이 가장 높은 토큰을 선택하는 방법
• 간단하지만 최적의 방법은 아닌데, 그 이유는 학습 데이터에 많이 포함된 형식의 아주 일반적이고 무난한 토큰을 선택하는 경향이 있기 때문

문맥: 이 케이크 먹어봐. 내가 직접 만들었어.
최적 답변: 이 케이크 진짜 맛있다.
생성 답변: 이거 괜찮다.
(학습 데이터에 많이 포함된 일반적인 형식이 답변으로 등장. 무난하지만 재미는 없는 답변)

Beam Search

• Greedy Search의 단점을 보완하기 위해, Exhaustive search는 모든 토큰의 조합을 고려
  • 예를 들어 10,000개의 단어사전(=즉, 선택될 수 있는 토큰의 후보군)이 있고 총 10개의 토큰으로 이루어진 문장을 생성하고자 한다면, (10,000의 10제곱)의 경우의 수를 모두 고려
  • 하지만 숫자의 규모로도 느낄 수 있듯이, 이런 방법은 엄청난 계산량을 야기해 비효율적
• Beam Search는 모든 단어사전의 조합을 계산하지 않고, Beam Width로 설정된 n개의 후보군에 대해서만 연산을 진행
• 각 단계마다 모든 단어사전 목록 중에서 가장 가능성이 높은 n 개의 후보군을 선택
• n개의 후보들은 다음 단계로 이동하며 다시 모든 단어사전 목록과의 조합을 통해 가장 가능성이 높은 n개가 계속해서 살아남음
• 즉, Beam Search의 space는 (10,000*n), 이를 통해 꽤 괜찮은 문장을 생성할 수 있음
• 하지만 답변이 안전지향형인지라 계속해서 "고마워", "잘 모르겠어"와 같은 문장을 생성할 여지가 있음

문맥: 이 케이크 먹어봐. 내가 직접 만들었어.
최적 답변: 이 케이크 진짜 맛있다.
생성 답변: 고마워.

추가 설명

• Beam Search = 3, 단어사전 = 10,000
• Step 1에서 [I, My, We] 라는 3개의 단어를 선택했다고 가정
• 첫 번째 단어 다음으로 올 두 번째 단어를 고를 때 조건부 확률과 Softmax Function을 활용
  • 예를 들어 I라는 단어 뒤에 올 두 번째 단어를 구할 때, (I, 두 번째 단어)의 쌍의 확률을 조건부확률을 이용해서 구함
  • 두 번째 단어의 후보군은 단어사전 내의 10,000개의 단어이고 첫 번째 단어는 I, My, We 총 3개이므로, 3 * 10,000 = 30,000개의 조합에 대해 조건부확률을 비교
  • 이 중 확률이 가장 높은 3개의 쌍(pair)를 선택하고 이를 다음 단계에서 사용
  • 글(link2)에서는 [I am, I will, My parents]를 예시로 듦

간단 요약

• 각 단계마다 beam width=n개의 후보군만이 살아남음
• 각 단계에서 pair의 확률을 구할 때 이전에 선택된 단어들을 기반으로 한 조건부확률을 사용

Random Sampling

• 랜덤 샘플링은 토큰이 갖는 확률에 따라 토큰을 선택
  • 예를 들어서 '나', '응', '좋은', '한다', '잘'과 같은 토큰들이 들어있는 단어사전 목록
  • 각 토큰이 다음에 올 확률을 구한다고 했을 때, '나'가 0.2, '잘'이 0.0001이었다고 가정
  • greedy search였다면 확률이 가장 높은 '나'를 선택했을 테지만, random sampling에서는 '나'가 나올 확률은 0.2, '잘'이 나올 확률은 0.0001
  • 확률이 적은 토큰이라도 다음 토큰으로 선택될 가능성이 존재

Random Sampling with Temperature

• Temperature는 가능성이 높은 토큰의 확률은 높여주고, 가능성이 낮은 토큰의 확률은 낮춰주는 역할
• OpenAI (link)
  • 낮은 값의 temperature는 더욱 일관된 답변을 생성 (예: 0.2)
  • 높은 값의 temperature는 더욱 다양하고 창의적인 답변을 생성 (예: 1.0)
  • temperature 범위는 0에서 2로 제공
• HuggingFace (link)
  • temperature가 0으로 갈수록 greedy decoding과 유사

Top-K Sampling

• 가능성이 적은 토큰들이 선택될 여지는 제거
• 오직 상위 K개의 토큰들만 고려
• Top-K Sampling도 마찬가지로 Temperature와 함께 사용 가능
• 최근 많은 생성 태스크에 적용
• 한 가지 제약사항은 시작할 때 미리 몇 개의 토큰을 선택할 것인지 정해야 함 (K를 결정)

Nucleus Sampling

• Nucleus Sampling은 Top-K Sampling과 유사
• 상위 K개의 단어에 집중하는 대신 확률의 합이 p 이상인 가장 작은 Top-V 단어들의 세트를 찾는 것에 초점
• 다시 말해, 토큰들의 집합이 두 가지 조건을 만족해야 함
  • 가능한 모든 경우의 수 중 집합에 포함된 토큰들의 수가 가장 적어야 함
  • 토큰들의 확률의 합이 p 이상이 되어야 함
• 이렇게 V를 찾고 나면 V에 속하지 않는 토큰들의 확률은 0으로 변경, V에 속하는 토큰들의 합이 1이 되도록 확률을 재조정
• 이러한 샘플링 기법은 모델이 몇몇 토큰들에 대해 굉장히 확신(certain)할 때, 가능한 후보 토큰들의 개수가 작을 거라는 intuition에 기반

Summary

• Greedy: 한 번에 가장 가능성이 높은 토큰 하나를 선택
• Beam Search: 가장 가능성이 높은 답변을 선택
• Random Sampling: 확률에 기반해 랜덤으로 추출 (확률이 아주 작더라도 토큰이 선택될 가능성 존재)
• Temperature: 확률을 줄이거나 늘림
• Top-K Sampling: 가능성이 높은 상위 K개의 토큰을 선택
• Nucleus Sampling: 합이 일정 확률을 만족하는 가장 적은 수의 토큰들을 선택

관련 링크 (link1, link2)