[IR] Beam Search

Beam Search

 

 

자연어 생성은, 단어들의 시퀀스를 아웃풋으로 예측해내는 태스크이다. 

Generation Model은 각각 decoding time step에서 

전체  Vocabulary에 대한 각 확률 분포를 예측하고, 확률이 높은 것을 다음 예측 단어로 선택한다. 

 

그러므로 모델의 예측 확률 분포를 이용해서, 각 타임 스텝의 단어로 변환하는 과정이 필요하다. 

 

모델이 예측한 확률 분포에 따라

가능한 아웃풋 시퀀스 조합을 찾기 위해 탐색(Search) 작업이 필요한데, 

Vocabulary는 수 만개의 토큰을 가지고 있으므로

모든 경우의 수에 따른 전체 공간을 탐색하는 것은 불가능하다. 

그래서 휴리스틱한 방법을 사용해 이것을 진행하며, 여기엔 Greedy Search 와 Beam Search 가 있다. 

 

이미지 출처: https://littlefoxdiary.tistory.com/4

 

 

 

정의

optimization algorithm으로, 특히 자연어 처리 및 음성 인식작업과 같은 seq2seq 모델의 context에서 사용된다. 

search strategy의 한 유형으로,

입력 시퀀스가 주어졌을 때

가장 유망한(promising) partial solution을 반복적으로 확장하여 

가장 가능성이 높은 아웃풋(the most likely output) sequence을 찾는 것을 목표로 한다. 

 

 

설명

 

greedy에서는 항상 그 상황에서의 제일 좋은 선택을 해 나가는 거지만

Beam search에서는 그 상황에서의 제일 좋은 k개를 선택하여 계속 추적해 나간다. 

그러다가 특정 경로가 <eos>를 만나면 해당경로를 candidate에 넣고

k+1번째를 추가하여 k개를 충족한 후 계속 추적해 나간다. 

candidate가 k개가 될 때까지 반복적으로 경로들을 추적해 나간다.

 

최종 candidate k 개 중에서, 가장 높은 누적 확률을 가진 candidate을 선택한다.

여기서 candidate를 beam이라고 부름. 

 

이 확률을 계산할 때는, Length panalty를 추가로 적용하여 계산한다. 

누적확률은 계속 곱하게 되어, 곱할 수록 숫자가 줄어들기 때문에 (확률이란 0<=p<=1 이므로)

beam의 길이가 길어질 수록 누적확률의 숫자가 줄어드는 것을 방지하기 위한 것이다.

 

 

 

 

---

참고한 자료

ChatGPT

https://velog.io/@nawnoes/%EC%9E%90%EC%97%B0%EC%96%B4%EC%B2%98%EB%A6%AC-Beam-Search

 

https://littlefoxdiary.tistory.com/4

 

https://networkx.org/documentation/stable/auto_examples/algorithms/plot_beam_search.html

 

https://blog.naver.com/PostView.naver?blogId=sooftware&logNo=221809101199 

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