본문으로 이동

빔 탐색

한울위키, 우리 모두의 백과사전.
파일:Beam search.gif
너비 3인 빔 탐색 (애니메이션)

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

상세

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

사용

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

역사

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

변형

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

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

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

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

각주

  1. ↑ “beam search”. 《Free On-line Dictionary of Computing》. 2024년 3월 27일에 확인함. 
  2. ↑ “BRITISH MUSEUM SEARCH”. 《bradley.bradley.edu》. 2016년 4월 11일에 확인함. 
  3. ↑ 가 나 Norvig, Peter (1992). 《Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP》. Morgan Kaufmann. 196쪽. ISBN 9781558601918. 
  4. ↑ 가 나 다 라 Furcy, D.; Koenig, S. (2005). 〈Limited discrepancy beam search〉. 《Proceedings of the 19th international joint conference on Artificial intelligence》. Morgan Kaufmann. 125–131쪽. 
  5. ↑ Tillmann, C.; Ney, H. (2003). 《Word reordering and a dynamic programming beam search algorithm for statistical machine translation》. 《Computational Linguistics》 29. 97–133쪽. doi:10.1162/089120103321337458. S2CID 7829066. 
  6. ↑ Lowerre, Bruce T. (1976). 《The Harpy Speech Recognition System》 (PDF) (PhD). Carnegie Mellon University. 
  7. ↑ Ow, Peng Si; Morton, Thomas E. (1988). 《Filtered beam search in scheduling†》 (영어). 《International Journal of Production Research》 26. 35–62쪽. doi:10.1080/00207548808947840. ISSN 0020-7543. 
  8. ↑ Defense Technical Information Center (1977년 8월 1일). 《DTIC ADA049288: Speech Understanding Systems. Summary of Results of the Five-Year Research Effort at Carnegie-Mellon University》 (영어). 6쪽. 
  9. ↑ Zhou, Rong; Hansen, Eric (2005). 〈Beam-Stack Search: Integrating Backtracking with Beam Search〉. 《ICAPS》. 90–98쪽. 2021년 4월 20일에 원본 문서에서 보존된 문서. 2011년 4월 9일에 확인함. 
  10. ↑ Svetlana Lazebnik. “Local search algorithms” (PDF). University of North Carolina at Chapel Hill, Department of Computer Science. 15쪽. 2011년 7월 5일에 원본 문서 (PDF)에서 보존된 문서. 
  11. ↑ 가 나 Pushpak Bhattacharyya. “Beam Search”. Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE). 39–40쪽. 2018년 11월 21일에 원본 문서에서 보존된 문서. 
  12. ↑ James Parker (2017년 9월 28일). “Local Search” (PDF). University of Minnesota. 17쪽. 2017년 10월 13일에 원본 문서 (PDF)에서 보존된 문서. 2018년 11월 21일에 확인함. 
원본 주소 "https://www.hanul.wiki/w/index.php?title=빔_탐색&oldid=1924693"