Beam search

A.1) 배경

seq2seq 의 decoder 에서 output 을 결정하는 방식은 Recurrent Neural Network 처럼 확률 분포에 기반한 random sampling 을 따를 경우, 결과가 좋지 않을 수 있다. 그래서 일반적으로 매 output 을 정할때 마다 가장 확률값이 높은 output 을 택하는 greedy search 방식을 취하는데, 이는 전체 sequence 로 보았을 때 적절하지 않다.

예를 들어, Jane is visiting Africa in September 라는 output 을 원하는데 Jane is 까지 왔다고 가정해보자. 여기서 visiting 을 선택하는게 가장 좋겠지만, Jane is 라는 것만 봐서는 going 이라는 단어가 확률이 가장 높아서 선택을 할 수 있다: Jane is going to be visiting Africa in September.

빔 서치는 “한 번에 한 단어씩만 보지 말고, 여러 개의 유망한 후보 문장을 동시에 고려하며 가장 좋은 문장을 찾자” 는 아이디어입니다. 너비가 k인 빔(beam)으로 빛을 비추듯, 매 단계에서 가장 확률 높은 k개의 후보 문장(가설, Hypothesis)만을 남기고 탐색을 이어나갑니다.

여기서 가장 중요한 개념은 빔 너비(Beam Width, k) 입니다. k가 1이면 매 순간 가장 좋은 하나만 선택하는 그리디 서치(Greedy Search)와 동일합니다.

B) 빔 서치 계산 과정 (예시: $k=2$)

상황: 모델이 “나는 오늘”이라는 문장을 입력받았고, 다음 단어부터 문장을 완성해야 합니다. k=2, 즉, 매 단계마다 가장 유망한 후보 2개를 유지합니다.

B.1) Step 1: 첫 번째 단어 예측

1. 모델은 “나는 오늘” 다음에 올 단어의 확률을 계산합니다.

   • 학교에: 0.5

   • 공원에: 0.3

   • 영화를: 0.1

   • 집에서: 0.05

   • … (기타 등등)

2. 이 중에서 확률이 가장 높은 k=2개의 단어를 선택하여 첫 번째 후보군(빔)을 구성합니다.

   • 후보 1: 나는 오늘 학교에 (점수: 0.5)

   • 후보 2: 나는 오늘 공원에 (점수: 0.3)

---

B.2) Step 2: 각 후보 확장 및 점수 계산

이제 각 후보 문장에 대해, 그 다음 단어를 예측하고 누적 점수를 계산합니다.

※ 핵심 계산: 왜 로그 확률(Log Probability)을 사용할까? 문장의 확률은 각 단어의 조건부 확률을 계속 곱해서 구합니다 (P(A,B) = P(A) * P(B|A)). 확률은 0과 1 사이의 값이므로, 계속 곱하면 값이 너무 작아져 컴퓨터가 제대로 계산하지 못하는 언더플로우(underflow) 문제가 발생합니다. 이를 해결하기 위해 확률에 로그(log)를 씌워 덧셈으로 계산합니다. log(A*B) = log(A) + log(B). 로그 확률은 음수이며, 0에 가까울수록 확률이 높은 것입니다.

1. 후보 1 (나는 오늘 학교에) 확장:

   • 다음에 올 단어 예측: 간다(log P: -0.7), 갔다(log P: -1.2)

   • 새로운 후보 문장 및 누적 점수 계산:

     • 나는 오늘 학교에 간다: log(0.5) + log(P(간다|…학교에)) = -0.69 + (-0.7) = -1.39

     • 나는 오늘 학교에 갔다: log(0.5) + log(P(갔다|…학교에)) = -0.69 + (-1.2) = -1.89

2. 후보 2 (나는 오늘 공원에) 확장:

   • 다음에 올 단어 예측: 갔다(log P: -0.9), 산책하러(log P: -1.5)

   • 새로운 후보 문장 및 누적 점수 계산:

     • 나는 오늘 공원에 갔다: log(0.3) + log(P(갔다|…공원에)) = -1.20 + (-0.9) = -2.10

     • 나는 오늘 공원에 산책하러: log(0.3) + log(P(산책하러|…공원에)) = -1.20 + (-1.5) = -2.70

---

B.2.1.1) Step 3: 전체 후보군에서 상위 K개 선택 (가지치기, Pruning)

이제 Step 2에서 생성된 모든 새로운 후보 문장들을 하나의 리스트에 모아 점수(누적 로그 확률) 순으로 정렬합니다.

1. 나는 오늘 학교에 간다 (점수: -1.39) <— 가장 유망 (점수가 가장 높음)

2. 나는 오늘 학교에 갔다 (점수: -1.89) <— 두 번째로 유망

3. 나는 오늘 공원에 갔다 (점수: -2.10)

4. 나는 오늘 공원에 산책하러 (점수: -2.70)

이 중에서 가장 점수가 높은 k=2개만 남기고 나머지는 버립니다. 이것이 빔 서치의 핵심인 가지치기(Pruning) 과정입니다.

• 새로운 빔 (다음 단계의 후보군):

  • 후보 1: 나는 오늘 학교에 간다 (점수: -1.39)

  • 후보 2: 나는 오늘 학교에 갔다 (점수: -1.89)

중요 포인트: 나는 오늘 공원에에서 파생된 문장들은 모두 탈락했습니다. 이처럼 빔 서치는 각 단계에서 가장 유망한 전체 경로를 유지하며 탐색을 최적화합니다.

---

B.2.1.2) Step 4: 반복 및 종료

이후 Step 2와 Step 3을 계속 반복합니다.

• 종료 조건:
  1. 모든 후보 문장이 문장의 끝을 의미하는 <EOS>(End-of-Sentence) 토큰에 도달했을 때
  2. 미리 정해둔 최대 문장 길이에 도달했을 때
• 최종 결과: 종료 시점에서 가장 높은 누적 점수를 가진 후보 문장을 최종 결과로 선택합니다.

B.2.2) 면접 대비 요약

단계	계산 내용	핵심 개념
1. 시작	첫 단어 예측 후, 확률이 가장 높은 k개의 단어로 초기 후보군(빔)을 만듭니다.	빔 너비(k)
2. 확장	현재 k개의 각 후보 문장에 대해 다음 단어를 예측하여 새로운 후보 문장들을 생성합니다.	후보 확장
3. 점수 계산	**로그 확률(Log Probability)**을 사용하여 각 신규 후보 문장의 누적 점수를 덧셈으로 계산합니다.	언더플로우 방지
4. 가지치기	모든 신규 후보 문장을 점수 순으로 정렬하고, 가장 점수가 높은 k개만 남기고 나머지는 버립니다.	Pruning (가지치기)
5. 반복/종료	종료 조건(최대 길이,  토큰)이 될 때까지 2~4단계를 반복하고, 마지막에 가장 점수가 높은 문장을 선택합니다.	최적 경로 탐색

빔 서치는 매 단계에서 k개의 가장 유망한 후보를 유지하고, 로그 확률을 더해나가며 누적 점수를 계산합니다. 이 과정에서 점수가 낮은 후보는 가지치기하여 계산 효율성을 높이면서도, 그리디 서치보다 더 최적의 문장을 탐색하는 방식입니다.

B.3) 정의

Beam search 는 seq2seq 의 output 을 결정할 때, greedy 알고리즘보다 좀 더 다양한 경우를 고려하는 방식이다.

Parameter $B$ 를 입력받아서, top-$B$ 개의 높은 확률을 가진 word 를 선택한다 ($B=1$ 은 greedy algorithm). 즉, 매 $T_y$ step 마다 총 $V$ 개의 단어들 중, $B$ 개의 높은 확률을 가진 단어를 선택한다는 의미가 된다

$$\underset{y}{\mathrm{argmax}}P\left({\hat{y}}^{(1)},{\hat{y}}^{(2)},,\cdots ,{\hat{y}}^{(Ty)}\mid x\right)$$

C) 예시

예시 ($B=3$)

step 1 에서는 in, jane, september 이렇게 3 개를 선택

$$P\left(y^{<1>}\mid x\right)$$

• step 2 에서는 step 1 에서 선택한 단어를 입력으로 하고, 가장 높은 확률을 가지는 출력을 선택 : $P\left(y^{<1>},y^{<2>}\mid x\right)=P\left(y^{<1>}\mid x\right)P\left(y^{<2>}\mid x,y^{<1>}\right)$

D) Related

E) References