Decoding Strategies | greedy approach, beam search, random sampling

· Decoding strategies
· Greedy Approach
· Beam Search
· Random sampling
　· random sampling with temperature
· Top-k random sampling
· Top-p random samplilng (= Nucleus sampling)

Decoding strategies

$$ P(x_i|x_{1:i-1}) = \sum_jexp(u_i)/exp(u_j) $$

($x$: 타임 스텝 $i$의 토큰, $u$: vocabulary에 있는 모든 토큰을 나타내는 벡터)

디코딩 하는 동안 각 타임 스텝에서 representation vector에 softmax 함수를 적용하여 각 단어에 대한 확률 배열로 변환한다. 이때 ‘토큰을 어떤 방식으로 선택할 것인가’에 대한 대표적인 방법론들에 대해 정리해 보았다.

 

Greedy Approach

• greedy approach란, 각 타임 스텝마다 가장 확률이 높은 토큰을 선택하는 단순한 방법

Context: Try this cake. I baked it myself.
Optimal Response : This cake tastes great.
Generated Response: This is okay.

• 생성된 문장이 매우 일반적 문장일 수 있음 = 최적의 문장이 아닐 수 있음
  → 해당 타임 스텝 당시엔 가장 높은 확률이었지만 최종 누적 확률은 가장 높지 않을 수 있음
• 이러한 문제점을 해결하기 위해 Exhaustive search 제안됨
• Exhaustive search란, 모든 타임 스텝마다의 확률 누적 곱을 전부 구한 후 최종적으로 가장 높은 확률의 문장을 생성하는 방법
  → 시간 복잡도가 너무 높은 단점
  ⇒ 이를 보완하기 위해 Beam search가 제안되었음

Beam Search

• Beam search란, 누적 확률을 고려하되 beam size만큼만 계산하는 방법
• 1️⃣ <SOS> token이 입력되면 모든 토큰에 대한 확률을 구한 후 확률이 높은 상위 k개 선택
  이때 beam size를 k라고 하고, K개의 노드는 각각 하나의 빔이라고 한다.
• 2️⃣ k개의 빔에서 각각 다음 토큰에 대한 확률을 구하고 상위 k개를 선택
• 3️⃣ 총 $k^2$개의 노드 중 누적 확률 순으로 상위 k개를 선택 → 상위 k개가 각각 하나의 빔이 됨
• 4️⃣ <EOS> token을 만난 빔이 K개가 될 때까지 2️⃣, 3️⃣ 반복

Context: Try this cake. I baked it myself.
Response A: That cake tastes great.
Response B: Thank you.

• beam search를 사용하게 되면 greedy search의 단점을 보완할 수 있지만, “i don’t know”나 “thank you” 같은 틀리진 않았지만 지루한 문장만을 반복 생성하게 될 수 있음
• length penalty (확률/length penalty or 확률/길이) - 추후 수정

Random sampling

• generic sentence만 생성하는 것을 막기 위해 stochastic approaches, 확률적 방법론이 제안됨
• random sampling은 말 그대로 확률에 따라 랜덤하게 선택됨
• 예를 들어, 0.8% 확률의 “i”와 0.01% 확률 “nice”가 있을 때,
  ‘i’가 선택될 확률이 높지만 ‘nice’가 선택이 절대 되지 않는 것이 아님 → 다양성 증가

Random Sampling with Temperature

$$ P(x_i|x_{1:i-1}) = \sum_jexp(u_i/t)/exp(u_j/t) $$

• temperature는 random sampling에서 확률이 높은 것은 더 높게 하고, 낮은 것은 더 낮게 하는 데에 사용됨
• 일반적으로, 0 < temperature ≤ 1 → temperature = 1이면 기본 random sampling과 똑같음

Top-K Random sampling

• 확률이 높은 상위 k개의 토큰들만을 사용해서 random sampling
  • 상위 k개의 토큰들에 대해서 renoramlization을 수행한 다음 random sampling
  • 나머지 토큰들이 확률은 0이 됨 → 선택되지 않음
• 위의 random sampling의 경우, 0.001% 같은 낮은 확률의 토큰들도 선택될 가능성은 존재했지만 Top-K random sampling의 경우 상위 k개를 제외한 나머지 토큰들은 선택되지 않음
• k 선택에 따른 문제점이 존재
  • 예시 ① k = 3일 때, (0.27, 0.25, 0.25, 0.23, …) 확률로 n개의 토큰이 존재하는 경우
    • 0.23의 확률을 가지는 토큰은 다른 토큰들과 비슷한 확률임에도 배제됨
  • 예시 ② k = 100일 때, (0.8, 0.19, 0.001, …) 확률로 n개의 토큰이 존재하는 경우
    • 매우 낮은 확률로, 사실상 선택되지 않았어야 할 토큰도 선택될 수 있음

Nucleus sampling (= Top-P Random sampling)

• Top-p sampling이란, 토큰들 확률의 합이 p 이상인 상위 토큰들에 대해서 random sampling
  • 상위 토큰들부터 시작해서 누적 확률 합이 p 이상인 토큰들에 대해서 renormalization을 수행한 다음 random sampling
  • 나머지 토큰들의 확률은 0이 됨 → 선택되지 않음
• 모델이 certain할 경우 = 소수의 토큰들이 높은 확률을 가짐 → 소수의 토큰들의 확률 합이 p을 넘기에 충분
• 모델이 uncertain할 경우 = 많은 토큰들의 확률이 높지 않음 → 확률 합이 p을 넘기 위해 많은 토큰들이 필요함
• 모델에 따라, 유동적으로 토큰들의 수를 달리할 수 있음

 

 

본 포스팅은 아래를 참고하여 작성되었습니다.

• Decoding Strategies that You Need to Know for Response Generation
• [Sooftware 머신러닝] Beam Search (빔서치)