빔 탐색

너비 3인 빔 탐색 (애니메이션)

컴퓨터 과학에서 빔 탐색(beam search)은 제한된 세트에서 가장 유망한 노드를 확장하여 그래프를 탐색하는 휴리스틱 탐색 알고리즘이다. 빔 탐색은 최상 우선 탐색을 수정하여 메모리 요구 사항을 줄인다. 최상 우선 탐색은 어떤 휴리스틱에 따라 모든 부분 해(상태)를 정렬하는 그래프 탐색이다. 그러나 빔 탐색에서는 미리 정해진 수의 최상의 부분 해만 후보로 유지된다. 따라서 탐욕 알고리즘이다.

상세

빔 탐색은 너비 우선 탐색을 사용하여 탐색 트리를 구축한다. 트리의 각 수준에서 현재 수준의 상태에 대한 모든 후속 항목을 생성하고 휴리스틱 비용의 오름차순으로 정렬한다. 그러나 각 수준에서 미리 정해진 수인 $\beta$개의 최상의 상태(빔 너비라고 함)만 저장한다. 이 상태들만 다음으로 확장된다. 빔 너비가 클수록 가지치기되는 상태가 적어진다. 무한한 빔 너비에서는 어떤 상태도 가지치기되지 않으며 빔 탐색은 최상 우선 탐색과 동일하다. 반대로 빔 너비가 1인 경우는 힐 클라이밍 알고리즘에 해당한다. 빔 너비는 탐색을 수행하는 데 필요한 메모리를 제한한다. 목표 상태가 가지치기될 수 있으므로 빔 탐색은 완전성(알고리즘이 해가 존재할 경우 해를 가지고 종료한다는 보장)을 희생한다. 빔 탐색은 최적(즉, 최상의 해를 찾는다는 보장이 없음)이 아니다.

사용

빔 탐색은 전체 탐색 트리를 저장할 메모리가 부족한 대규모 시스템에서 추적 가능성을 유지하기 위해 가장 자주 사용된다. 예를 들어, 많은 기계 번역 시스템에서 사용되었다. (현재는 주로 신경망 기계 번역 기반 방법, 특히 대규모 언어 모델을 사용한다.) 최상의 번역을 선택하기 위해 각 부분이 처리되고 단어를 번역하는 여러 가지 다른 방법이 나타난다. 문장 구조에 따라 상위 최상의 번역만 유지되고 나머지는 버려진다. 그런 다음 번역기는 주어진 기준에 따라 번역을 평가하여 목표를 가장 잘 유지하는 번역을 선택한다.

역사

하피 음성 인식 시스템(1976년 박사 학위 논문에서 소개됨)은 빔 탐색으로 알려지게 될 것의 첫 번째 사용이었다. 이 절차는 원래 "탐색의 궤적 모델"이라고 불렸지만, "빔 탐색"이라는 용어는 이미 1977년에 사용되었다.

변형

빔 탐색은 깊이 우선 탐색과 결합하여 완전해졌으며, 그 결과 빔 스택 탐색 및 깊이 우선 빔 탐색, 그리고 제한된 불일치 탐색과 결합하여 제한된 불일치 역추적을 사용하는 빔 탐색(BULB)이 탄생했다. 결과적인 탐색 알고리즘은 빔 탐색처럼 좋지만 최적이 아닐 가능성이 있는 해를 빠르게 찾은 다음 역추적하고 최적 해로 수렴할 때까지 개선된 해를 계속 찾는 언제나 알고리즘이다.

지역 탐색의 맥락에서 지역 빔 탐색은 무작위로 생성된 $\beta$개의 상태를 선택한 다음, 탐색 트리의 각 수준에서 목표에 도달할 때까지 현재 상태의 모든 가능한 후속 상태 중에서 항상 $\beta$개의 새로운 상태를 고려하는 특정 알고리즘을 의미한다.

지역 빔 탐색은 종종 지역 최댓값에서 끝나기 때문에 일반적인 해결책은 상태의 휴리스틱 평가에 따라 확률적으로 다음 $\beta$개의 상태를 무작위로 선택하는 것이다. 이러한 종류의 탐색을 확률적 빔 탐색이라고 한다.

다른 변형으로는 유연 빔 탐색(flexible beam search)과 복구 빔 탐색(recovery beam search)이 있다.