빔 탐색(beam search)은 컴퓨터 과학에서 제한된 집합 내에서 가장 유망한 노드를 확장하여 그래프를 탐색하는 데 사용되는 휴리스틱 탐색 알고리즘이다. 이는 최상 우선 탐색(best-first search)을 수정한 것으로, 후보로 유지할 최상의 부분 해결책의 수를 미리 정해진 수로만 유지하여 메모리 요구량을 줄인 탐욕 알고리즘이다. 이 알고리즘은 기계 번역 및 음성 인식과 같은 시퀀스 디코딩 작업에 널리 적용되며, 출력 품질과 계산 가능성 사이의 균형을 맞춘다.
빔 탐색의 핵심 아이디어는 빔(beam)이라고 불리는 가장 유망한 부분 해결책들의 집합을 유지하고, 각 단계에서 해당 집합만 확장하는 것이다. 이 접근 방식은 모든 가능한 경로를 고려하는 완전 탐색 방법과 대조되며, 이러한 완전 탐색은 탐색 공간이 큰 경우 계산적으로 불가능할 수 있다. 덜 유망한 후보를 가지치기함으로써 빔 탐색은 완전성과 최적성의 보장을 희생하면서 효율성을 달성한다.
알고리즘 세부 사항
빔 탐색은 너비 우선 탐색 전략을 사용하여 탐색 트리를 구축한다. 트리의 각 수준에서 현재 수준의 상태에 대한 모든 후속 상태를 생성하고 휴리스틱 비용의 증가 순서로 정렬한다. 그러나 각 수준에서 미리 정해진 수(β, 빔 폭)의 최상의 상태만 저장한다. 해당 상태만 다음에 확장되고 나머지는 폐기된다.
빔 폭 β는 탐색 품질과 리소스 사용 간의 균형을 제어하는 중요한 매개변수이다. 더 넓은 빔 폭은 더 많은 상태를 유지하여 가지치기되는 후보의 수를 줄이고 잠재적으로 솔루션 품질을 향상시키지만, 메모리 및 계산 요구 사항도 증가시킨다. 무한한 빔 폭에서는 상태가 가지치기되지 않으며 빔 탐색은 최상 우선 탐색과 동일해진다. 반대로 빔 폭이 1이면 언덕 오르기 알고리즘에 해당하며, 단일 최상 경로만 탐욕적으로 따른다.
빔 폭은 탐색을 수행하는 데 필요한 메모리를 제한하므로 메모리가 제한된 대규모 시스템에 적합하다. 그러나 목표 상태가 가지치기될 수 있기 때문에 빔 탐색은 완전성 - 솔루션이 존재하는 경우 알고리즘이 솔루션으로 종료된다는 보장 - 을 희생한다. 또한 빔 탐색은 최적이 아니므로 최상의 가능한 솔루션을 찾을 것이라는 보장이 없다.
역사적 발전
빔 탐색으로 알려지게 된 것의 첫 사용은 1976년 논문에서 소개된 Harpy 음성 인식 시스템이었다. 이 절차는 원래 "탐색의 궤적 모델"로 불렸지만, "빔 탐색"이라는 용어는 1977년에 이미 사용되고 있었다. Harpy는 카네기 멜론 대학교에서 개발되었으며 음성 인식 기술의 중요한 발전을 나타내며 실세계 응용에서 휴리스틱 탐색의 실용적 유용성을 입증했다.
빔 탐색의 개발은 인공 지능 시스템을 위한 효율적인 탐색 알고리즘을 향한 1970년대의 더 넓은 추세의 일부였다. 연구자들은 완전 탐색 방법이 복잡한 문제에 종종 비실용적이라는 것을 인식했으며, 이는 좋은 솔루션을 빠르게 찾을 수 있는 휴리스틱 접근 방식의 개발로 이어졌다. Harpy 시스템의 성공은 빔 탐색을 해당 분야의 기본 기술로 확립하는 데 도움이 되었다.
기계 번역에서의 응용
빔 탐색은 기계 번역 시스템에서 가장 두드러지게 사용되며, 많은 가능한 후보 중에서 최상의 번역을 선택하는 데 도움이 된다. 전통적인 통계적 기계 번역에서는 문장의 각 부분이 처리되고 단어를 번역하는 많은 다른 방법이 생성된다. 빔 탐색은 문장 구조에 따라 최상의 번역을 유지하고 나머지를 폐기한 다음, 주어진 기준에 따라 나머지 번역을 평가하여 목표를 가장 잘 충족하는 번역을 선택한다.
주로 대규모 언어 모델과 트랜스포머 아키텍처를 사용하는 현대 신경망 기계 번역에서 빔 탐색은 여전히 핵심 디코딩 전략이다. 생성 중에 모델은 각 단계에서 가능한 다음 토큰에 대한 확률 분포를 생성한다. 빔 탐색은 여러 부분 시퀀스를 유지하고 누적 확률에 따라 가장 유망한 시퀀스를 확장한다. 이 접근 방식은 각 단계에서 가장 가능성 있는 단일 토큰만 선택하는 탐욕 디코딩보다 더 높은 품질의 번역을 생성한다.
기계 번역에서 빔 탐색의 응용은 광범위하게 연구되었으며, 연구자들은 성능을 향상시키기 위한 다양한 수정을 탐구했다. 예를 들어, 길이 정규화는 더 짧은 시퀀스로 편향되는 것을 피하기 위해 종종 적용되며, 다양한 빔 탐색 기술은 후보 시퀀스 간의 다양성을 장려하기 위해 개발되었다.
변형 및 확장
빔 탐색의 한계, 특히 완전성과 최적성의 부족을 해결하기 위해 여러 변형이 개발되었다. 한 접근 방식은 빔 탐색을 깊이 우선 탐색과 결합하여 빔 스택 탐색과 깊이 우선 빔 탐색을 생성한다. 이러한 알고리즘은 빔 탐색처럼 좋지만 아마도 차선의 솔루션을 빠르게 찾은 다음 역추적하여 최적 솔루션으로 수렴할 때까지 개선된 솔루션을 계속 찾는 언제든지 알고리즘이다.
또 다른 변형인 제한된 불일치 역추적을 사용한 빔 탐색(BULB)은 빔 탐색을 제한된 불일치 탐색과 결합한다. 이 접근 방식은 시간이 지남에 따라 솔루션을 개선할 수 있는 언제든지 알고리즘도 생성한다. 지역 탐색의 맥락에서 지역 빔 탐색은 β개의 무작위로 생성된 상태를 선택하여 시작하고, 탐색 트리의 각 수준에 대해 목표에 도달할 때까지 현재 상태의 모든 가능한 후속 상태 중에서 β개의 새 상태를 고려하는 특정 알고리즘이다.
지역 빔 탐색은 종종 지역 최대값에 빠지기 때문에, 일반적인 해결책은 상태의 휴리스틱 평가에 의존하는 확률로 다음 β 상태를 무작위 방식으로 선택하는 것이다. 이러한 종류의 탐색을 확률적 빔 탐색이라고 한다. 다른 변형에는 유연한 빔 탐색과 복구 빔 탐색이 포함되며, 이는 빔 폭을 동적으로 조정하거나 잘못된 가지치기 결정에서 복구할 수 있게 한다.
현대 AI 시스템에서의 역할
빔 탐색은 특히 생성형 AI 응용에서 현대 인공 지능 시스템에서 중요한 역할을 한다. 딥 러닝 모델, 특히 트랜스포머 아키텍처 기반 모델에서 빔 탐색은 추론 중에 텍스트, 코드 또는 음성과 같은 시퀀스를 생성하는 데 사용된다. OpenAI, Anthropic 및 Google DeepMind와 같은 회사는 언어 모델에서 빔 탐색을 사용하여 일관되고 맥락에 맞는 출력을 생성한다.
이 기술은 이미지 캡셔닝, 음성 인식 및 단백질 구조 예측과 같은 다른 시퀀스 생성 작업에도 사용된다. 이러한 응용에서 빔 탐색은 생성된 출력의 품질과 필요한 계산 리소스 간의 균형을 맞추는 데 도움이 된다. 빔 폭은 작업의 특정 요구 사항에 따라 조정될 수 있으며, 더 넓은 폭은 더 나은 품질을 제공하지만 계산 비용이 증가한다.
이론적 속성
빔 탐색의 이론적 속성은 휴리스틱 탐색의 맥락에서 분석되었다. 탐욕 알고리즘으로서 각 단계에서 지역적으로 최적의 선택을 하며, 이는 전역적으로 차선의 솔루션으로 이어질 수 있다. 알고리즘의 성능은 상태를 평가하는 데 사용되는 휴리스틱 함수의 품질에 크게 의존한다. 잘 설계된 휴리스틱은 탐색을 좋은 솔루션으로 안내할 수 있는 반면, 나쁜 휴리스틱은 알고리즘이 최적 경로를 놓치게 할 수 있다.
빔 폭과 솔루션 품질 간의 균형은 실용적 응용에서 핵심 고려 사항이다. 연구에 따르면 빔 폭을 늘리면 일반적으로 솔루션 품질이 향상되지만 수익은 감소한다. 어떤 경우에는 너무 큰 빔 폭이 과도한 생성과 계산 비용 증가를 초래할 수 있으며 품질 향상은 크지 않다. 반대로 너무 작은 빔 폭은 과도한 가지치기로 인해 좋지 않은 솔루션을 초래할 수 있다.
계산 고려 사항
빔 탐색의 계산 복잡성은 주로 빔 폭과 탐색 공간의 분기 계수에 의해 결정된다. 각 수준에서 알고리즘은 빔의 모든 상태에 대한 후속 상태를 생성하며, 이는 β × b 연산이 필요하며, 여기서 b는 분기 계수이다. 이러한 후속 상태의 정렬은 수준당 log(β × b)의 추가 요소를 추가한다. 따라서 총 복잡성은 O(β × b × L × log(β × b))이며, 여기서 L은 탐색의 최대 깊이이다.
메모리 사용은 빔 폭에 의해 제한되며, 각 수준에서 β개의 상태만 저장된다. 이는 빔 탐색을 임베디드 시스템이나 실시간 처리와 같은 메모리가 제한된 응용에 특히 매력적으로 만든다. 메모리 사용과 솔루션 품질 간의 균형을 맞추는 알고리즘의 능력은 학술 연구와 산업 응용 모두에서 지속적인 인기에 기여했다.
다른 탐색 방법과의 비교
빔 탐색은 종종 탐욕 탐색, 최상 우선 탐색 및 기계 학습 기반 디코딩 방법과 같은 다른 탐색 알고리즘과 비교된다. 빔 폭이 1인 빔 탐색에 해당하는 탐욕 탐색은 계산적으로 효율적이지만 종종 더 낮은 품질의 결과를 생성한다. 모든 부분 솔루션을 고려하는 최상 우선 탐색은 최적 솔루션을 찾을 수 있지만 전체 탐색 공간에 비례하는 메모리가 필요하다.
신경망 시퀀스 생성의 맥락에서 빔 탐색은 확률 분포에 따라 토큰을 무작위로 선택하는 샘플링 기반 방법과 대조되기도 한다. 샘플링은 더 다양한 출력을 생성할 수 있지만 일관성을 희생할 수 있는 반면, 빔 탐색은 더 결정적이고 더 높은 품질의 결과를 생성하는 경향이 있다. 최근 연구는 품질과 다양성 간의 균형을 달성하기 위해 빔 탐색과 샘플링을 결합한 하이브리드 접근 방식을 탐구했다.
미래 방향
2020년대 초반 현재 빔 탐색은 특히 대규모 언어 모델의 맥락에서 여전히 활발한 연구 영역이다. 연구자들은 모델 예측의 신뢰도에 따라 조정되는 적응형 빔 폭 전략과 빔 탐색 과정에 외부 제약을 통합하는 방법을 탐구하고 있다. NVIDIA 및 AMD와 같은 회사의 전문 AI 가속기와 같은 더 효율적인 하드웨어의 개발은 실시간 응용에서 더 넓은 빔 폭과 더 복잡한 탐색 전략을 가능하게 했다.
빔 탐색과 강화 학습 및 신경망과 같은 다른 AI 기술의 통합도 지속적인 조사 영역이다. 이러한 노력은 자연어 처리에서 과학적 발견에 이르기까지 다양한 응용에서 시퀀스 생성의 효율성과 효과를 향상시키는 것을 목표로 한다.