빔 서치 (Beam Search)
쉽게 풀면
매 단계마다 다음에 올 수 있는 단어 후보가 수만 개씩 있다고 생각해봅시다. 이 모든 조합을 다 따져보는 것은 사실상 불가능합니다. 그렇다고 매 단계마다 "가장 확률 높은 단어 딱 하나"만 고르면(그리디 방식) 당장은 그럴듯해 보여도 나중에 가서 전체 문장이 어색해지는 경우가 많습니다. Beam Search는 그 중간 지점을 택합니다. 매 단계마다 확률이 높은 후보를 예를 들어 5개(빔 너비 5)만 남겨두고, 그다음 단계에서 이 5개 각각에 이어질 수 있는 단어들을 다시 확률순으로 추려 상위 5개만 유지하는 식으로 진행합니다. 이렇게 하면 모든 경우를 다 보지 않고도, 한 가지만 고집하는 것보다 훨씬 자연스러운 문장을 찾아낼 확률이 높아집니다.
왜 중요한가
텍스트 생성, 번역, 음성 인식처럼 결과물을 한 토큰씩 순차적으로 만들어내는 모델은 학습이 끝난 뒤에도 "어떤 방식으로 출력을 뽑아낼 것인가"라는 디코딩 문제가 따로 남습니다. Beam Search는 이 디코딩 단계에서 속도와 출력 품질 사이의 균형을 맞추는 실용적인 방법이라 자연어 생성 계열 논문 대부분에서 실험 설정의 기본값으로 언급됩니다. 또한 같은 모델이라도 디코딩 전략을 어떻게 바꾸느냐에 따라 평가 지표가 달라지므로, 새로운 모델을 제안하는 논문은 비교 실험에서 빔 서치를 기준선(baseline) 삼아 다른 디코딩 방법과 성능을 나란히 비교하는 경우가 많습니다.
논문에서는 이렇게 쓰입니다
이 문장은 기계번역 모델이 출력 문장을 만들 때, 매 단계 최선의 단어 하나만 고르는 그리디 방식 대신 여러 후보를 동시에 유지하는 빔 서치 방식을 사용했더니 번역 품질 평가 지표가 더 좋아졌다는 실험 결과를 보여줍니다. 자연어 생성, 기계번역, 음성 인식 등 순차적으로 출력을 만드는 모델의 디코딩 단계에서 자주 사용됩니다.
음성 인식 분야의 예문입니다. 음향 모델이 각 시점마다 내놓는 후보 문자·단어 확률을 그대로 그리디하게 이어붙이면 문법적으로 어색한 결과가 나오기 쉬운데, 빔 서치로 여러 후보 문장을 동시에 유지하면서 별도의 언어 모델 점수까지 함께 반영하면 전체적으로 더 자연스러운 문장을 고를 수 있다는 내용입니다.
텍스트 요약 분야의 예문으로, 빔 서치를 그대로 키운다고 결과가 무조건 좋아지는 것은 아니며 오히려 같은 표현이 반복되는 부작용이 나타날 수 있다는 점, 그리고 이를 보완하기 위해 길이 페널티 등의 추가 장치를 함께 쓰는 경우가 많다는 실무적 맥락을 보여줍니다.
조금 더 깊게 보면
실제 구현에서는 각 후보 시퀀스의 확률을 그대로 곱하지 않고 로그 확률의 합으로 계산하는데, 문장이 길어질수록 로그 확률의 합이 계속 작아져 짧은 문장이 유리해지는 경향이 있습니다. 이를 보정하기 위해 길이에 따라 점수를 나누거나 가중치를 주는 길이 정규화(length normalization) 기법이 흔히 함께 쓰입니다. 또한 빔 서치는 매 단계 지역적으로 우수한 후보들만 남기는 근사적 탐색이므로 전역적으로 최적인 문장을 찾는다는 보장은 없으며, 같은 표현이 반복되는 문제를 막기 위한 반복 억제(repetition penalty)나 n-그램 중복 방지 규칙이 함께 적용되는 경우도 많습니다. 논문을 읽을 때는 빔 너비, 길이 정규화 방식, 반복 방지 여부 같은 디코딩 세부 설정이 실험 재현성에 큰 영향을 준다는 점을 함께 살펴보는 것이 좋습니다.
주의할 점
빔 너비를 1로 설정하면 탐욕 알고리즘과 같아지고, 빔 너비를 무한히 크게 하면 모든 경우의 수를 다 따지는 완전 탐색에 가까워집니다. 즉 Beam Search는 이 둘 사이에서 속도와 정확도의 균형을 조절하는 방법이며, 빔 너비를 무조건 크게 한다고 결과가 항상 더 좋아지는 것은 아니라는 점에 유의해야 합니다.