Beam Search

자연어 생성에서의 Beam search와 Greedy search의 차이 

준비물: 학습된 자연어 생성 모델

목표: 학습된 자연어 생성 모델을 갖고 자연어를 생성(예측) 

기본적인 방법: 예측된 확률 분포에 따라 가능한 모든 아웃풋 시퀀스의 조합을 탐색. 

그러나 이는 계산 비용이 크다. 따라서 이를 해결하는 방법 두 가지를 소개한다. 

 

1. Greedy search

• 기본적인  Seq2Seq 모델에서 채택하는 방식.
• 현 시점에서 가장 확률이 높은 단어를 다음 시점의 인풋으로 넣어 아웃풋을 도출한다. 
• 시간복잡도 측면 good, 최종 정확도 측면 bad.
• 각 시점마다 확률이 좀 낮아도 최종 정확도는 높아질 수 있기 때문. 

2. Beam search 

• Greedy search의 단점을 보완하여 등장.
• 현 시점에서 확률 분포가 상위 k개(빔의 개수)인 것을 골라 아웃풋을 도출한 후, 자식 노드가 k보다 크면, 누적 확률이 가장 큰 k개를 남기고 버림. 
• 어떠한 자식 노드들이 서로 같은 확률을 가지더라도, 어떤 가지에서 어떤 순서로 뻗어나왔냐에 따라 누적 확률이 달라짐. 
• 최종적으로 마지막 토큰 <eos>를 출력한 자식노드가 k개가 되면 예측을 멈춘다. 
• 최종 k개의 후보 중에서 가장 높은 누적 확률을 가진 빔을 선택한다. 
• 빔의 길이가 길어질수록 최종 누적 확률 계산 시 값이 작아지는 불공평성을 해결하기 윟새 length penalty 적용.

 

출처: https://blog.naver.com/PostView.nhn?blogId=sooftware&logNo=221809101199&from=search&redirect=Log&widgetTypeCall=true&directAccess=false 

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