what is beam search?

https://machinelearningmastery.com/beam-search-decoder-natural-language-processing/

How to Implement a Beam Search Decoder for Natural Language Processing

빔 서치를 찾아보면서 위 링크를 통해 이해한 바를 정리한다.

 

단어를 맞추는 모델이 존재한다. 

주어진 입력으로 부터

우리고 가지고 있는 단어의 묶음 (이게 vocab?) 중

어떤 단어일 확률이 가장 높은지 알려주는 모델이다.

 

이 모델로 부터 문장을 만들어 낸다고 생각해 보자.

 

모델은 매 순간 순간 가장 큰 확률을 갖는 단어를 내뱉는다.

그러고 나서 그 단어들을 보았더니 전혀 말이 되지 않는 문장이다.

흐음,, 무엇이 문제일까? 

모델은 순간 순간 최선을 다했다. 

하지만 우리는 말을 할때 순간 순간 생각난 단어를 내뱉지 않는다.

앞 뒤 문맥이라는 것을 고려한다. 

 

따라서 단어들 간에는 서로 연관성이 존재 하며 

이를 통해, 단어 간의 확률을 모델링하고 문장을 완성시킨다고 볼 수 있다.

 

이때 단어간의 확률을 모델링 하는 방법중 하나가 빔 서취라고 이해했다.

그리디의 경우 매순간 가장 높은 확률을 가지는 녀석 하나를 고려하는 반면

빔서치의 경우 주어진 사이즈 만큼 조사를 한다. 

스텝이 진행될수록 계산량은 지수적으로 늘어난다. 

사이즈가 커질 수록 올바른 문장을 만들어낼 확률이 커지겠지만,

계산량이 증가하여 속도가 떨어지는 트레이드 오프 관계를 가진다.