빔 탐색

1 개요

beam search

beam 探索

빔 탐색

• 몇 개의 최상 선택을 동시에 탐색하는 휴리스틱 탐색 기법
• 그래프 구조에서 최적의 해결책을 찾기 위해 사용되는 휴리스틱 탐색 알고리즘
• 제한된 집합에서 가장 유망한 노드를 확장하여 그래프를 탐색하는 휴리스틱 탐색 알고리즘
• 효율적인 탐색을 위해 가장 유망한 후보들만을 선택하여 탐색의 범위를 제한하는 탐색 알고리즘
• 메모리 요구사항을 줄이는 최상 우선 탐색을 최적화한 것
• 최상 우선 탐색은 선택한 휴리스틱에 따라 모든 부분 솔루션(상태)의 순서를 지정하는 그래프 검색이다. 그러나 빔 탐색에서는 미리 정해진 개수의 최적 부분해만 후보로 유지된다. 즉, 탐욕 알고리즘이다. 무제한의 후보 집합으로 구현된 빔 검색은 역추적 알고리즘이 된다 .
• 완전 탐색과 그리디 탐색의 중간 형태로 볼 수 있다.
• 주요 응용 분야: 자연어 처리(기계 번역, 텍스트 요약, 음성 인식), 비전, 머신러닝(시퀀스 예측, 신경망의 효율적인 학습)
• "빔 탐색"이라는 용어는 1977년 카네기 멜론 대학교의 Raj Reddy가 만들었다.

2 작동 원리

빔 탐색은 탐색 과정에서 발생할 수 있는 모든 가능성 중 일부만을 고려하여 계산의 효율성을 높인다. 이 알고리즘은 '빔'이라는 고정된 크기의 집합을 사용하여 각 단계에서 가능한 최고의 후보들만을 유지한다.

• 초기화: 탐색을 시작할 노드를 선택한다.
• 확장: 현재 노드에서 이동할 수 있는 모든 후속 노드들을 생성한다.
• 평가: 후속 노드들을 특정 기준(예: 확률, 비용)에 따라 평가한다.
• 선택: 가장 좋은 평가를 받은 상위 N개의 노드를 선택한다. 여기서 N이 빔의 크기이다.
• 반복: 새로운 노드들에서 다시 확장, 평가, 선택 과정을 반복한다.
• 종료 조건: 특정 조건(예: 목표 노드 도달, 최대 깊이 도달)이 만족될 때까지 이 과정을 반복한다.

3 장단점

3.1 장점

• 완전 탐색에 비해 계산 효율이 높다.
• 큰 탐색 공간에서도 상대적으로 빠른 해결책을 제공한다.

3.2 단점

• 최적의 해결책을 항상 보장하지는 않는다.
• 빔의 크기가 결과에 큰 영향을 미친다.

4 같이 보기

• 빔(beam)
• 탐색
• 최선 우선 검색

5 참고

• 위키백과 "빔 탐색"
• 위키낱말사전 "빔 탐색"
• 다음사전 "빔 탐색"
• 다음백과 "빔 탐색"
• 네이버사전 "빔 탐색"
• 네이버백과 "빔 탐색"
• 나무위키 "빔 탐색"
• 리브레 위키 "빔 탐색"