언어모델은 컨텍스트(=토큰시퀀스)를 입력받아, 다음 토큰이 나타날 확률을 출력으로 반환한다. 즉 모델의 출력 확률 분포로부터 다음 토큰을 반복해서 선택하는 과정이 바로 문장생성 태스크다. 문제는 특정 컨텍스트 다음에 올 토큰으로 무수히 많은 경우의 수가 존재한다. 이론적으로는 다음 단어를 하나 선택해야 할 때 어휘 집합 크기만큼의 경우의 수가 생길 ㅅ수 있다. 이렇게 반복적으로 다음 토큰을 생성할 경우 무수히 많은 가짓수가 파생되며 모든 경우의 수를 계산해 보는것는것은 사실상 불가능 하다.
Greedy search model.generate파라미터의 do_sample=False를 주므로써 확률값이 높은 단어를 다음 단어로 결정되도록하면 그리디서치를 수행하게 된다. 그리디서치는 매 단계에서 가장 높은 확률을 갖는 단어를 선택하는 방식이다. 즉 현재 시점에서 가장 확률이 높은 단어를 선택하고, 그 다음에도 계속해서 가장 확률이 높은 단어를 차례로 선택하는 방식이다. 그렇기 때문에 매 단계마다 전체 어휘 집합에 대한 확률 계싼을 해야 하므로 계산비용이 매우 크고 속도가 느려질수 있다.
그래서 전체 어휘 집합 대신 beam search 나 top-k등의 기법을 사용하여 후보집합을 제한해 계산량을 크게 줄일 수 있다.
빔서치도 그리디서치도 모두 매 단계에서 확률 계산을 해야 한다. 하지만 동작방식에는 아래와 같은 차이점이 있다.
그리디는 매 단계에서 가장 높은 확률의 단어 하나만 선택한다. 그리디서치는 매 스텝에서 전체 어휘 집합에 대한 확률 계산을 해야 한다. 예를 들어 어휘크기가 5만개라면, 매 스텝마다 5만개의 확률을 모두 계산해야 한다. 반면 빔서치는 beam sizeK만큼의 확률만 계산하면 된다. 보통 K=5,10정도의 작은 값을 사용한다. 그래서 매 스탭에서 K개의 확률만 계산하면 되므로 그리디서치보다 계산량이 크게 줄어든다. 그리고 빔 서치는 K개의 경로를 동시에 탐색하므로 그리디서치보다 다양한 해를 얻을 수 있는 장점이 있다. 그래서 넓은 탐색이 가능하여 성능이 좋다.
예를 들어, top : eat, go, buy라면 그리디서치는 I want to eat을 출력한다.
빔서치는 I want to eat, I want to go, I want to buy가 상위3개 확률이라 3개의 경로를 유지한다.
- "I want to eat" -> "pizza", "an apple", "breakfast"
- "I want to go" -> "home", "to the park", "shopping"
- "I want to buy" -> "a car", "some food", "a gift"
그 다음단계에서 빔서치는 이 3개의 경로에 대해 각각의 상위 3개 확률을 계산하고 유지한다. 이렇게 경로를 유지하며 점수가 가장 높은 K개의 완성된 문장을 출력한다.
그리디는 한번 선택하면 되돌릴수 없지만, 빔서치는 매 단계에서 k개의 가능성을 탐색하므로 greediness를 피할 수 있다. 하지만 K가 커질수록 계산 비용도 증가한다.
빔서치에서 topK샘플링 옵션에 따라 상위K개의 확률만 계산하게 된다.
- 현재까지의 시퀀스에 대해 전체 어휘 집합의 확률 분포를 계산
- 이 확률 분포에서 상위 k개의 확률을 가진 단어와 그 확률값만 추출
- 이렇게 top-k 후보들 중에서 빔 서치 알고리즘에 따라 유지할 시퀀스들을 결정
- 선택된 시퀀스들에 대해서만 다음 스텝의 확률 분포를 계산
- 2~4 과정을 목표 시퀀스 길이에 도달할 때까지 반복
따라서 topK샘플링은 빔서치에서 계산비용을 크게 줄이기 위해 사용된다. 전체 어휘대신 topK후보들만 고려하므로 계산량이 현저히 줄어든다. (보통 topK를 전체 어휘크기 만큼 주진 않으니까ㅎ)
예를 들어 어휘 크기가 50,000개라면:
- 그리디 서치: 매 스텝에서 50,000개 전체 확률 계산
- 빔 서치(top_k=50,000): 매 스텝에서 50,000개 전체 확률 계산