베이즈 탐색 이론

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 절차
3. 수학적 모델
4. 응용 사례
5. 최적 탐색 노력 분배
참조

1. 개요

베이즈 탐색 이론은 물체의 위치를 탐색하는 데 사용되는 확률적 접근 방식이다. 이 이론은 가능한 가설을 설정하고, 각 가설에 따라 물체의 위치에 대한 확률 밀도 함수를 구성하며, 탐색 성공 확률을 고려하여 전체 확률 밀도 맵을 생성한다. 탐색 경로는 확률이 높은 지점에서 시작하여 지속적으로 확률을 수정하며 진행된다. 베이즈 탐색 이론은 스콜피온 잠수함 탐색, 팔로마레스 B-52 폭격기 추락 사고 수소폭탄 수색, 에어 프랑스 447편 추락 사고 잔해 수색 등 다양한 실제 사례에 적용되었다. 미국 해안 경비대의 수색 구조 소프트웨어 CASP에 통합되어 있으며, 한국의 해양 사고 대응에도 활용될 수 있다.

더 읽어볼만한 페이지

운용 과학 - 계획
계획은 목표 달성을 위한 방법과 절차를 결정하는 과정으로, 개인적 목록 작성부터 국가적 자원 사용, 토지 이용 규제 등 다양한 형태로 나타나며, 상위-하향식, 하위-상향식, PDCA 사이클 등의 방법론을 활용하여 명확한 목표 설정, 효율적인 자원 관리, 위험 관리, 유연성을 필요로 한다.
운용 과학 - 알고리즘 설계
알고리즘 설계는 문제 해결을 위한 효율적인 절차나 방법을 구체화하는 과정으로, 문제 정의부터 문서화까지의 개발 단계를 거치며 분할 정복, 동적 계획법 등의 다양한 설계 기법들이 활용된다.
베이즈 통계학 - 주관주의
주관주의는 현실이 인식에 의존한다는 철학적 입장으로, 형이상학에서는 궁극적 실재가 인식에 달려있다고 보며, 윤리학에서는 윤리적 판단이 개인의 태도에 따라 달라진다고 보고, 확률론에서는 확률을 개인의 신념으로 해석한다.
베이즈 통계학 - 사후 확률
사후 확률은 베이즈 통계학에서 증거가 주어졌을 때 모수의 확률을 나타내며, 베이즈 정리를 통해 계산하고, 사전 확률을 갱신하여 사후 확률 분포를 얻는 데 활용된다.
검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.

베이즈 탐색 이론
개요
유형	탐색 이론
분야	베이즈 통계학
목적	분실된 물체나 정보를 찾기 위한 최적의 전략 개발
주요 개념
사전 확률	탐색 대상이 특정 위치에 존재할 확률
탐색 효율	특정 위치를 탐색했을 때 대상을 발견할 확률
사후 확률	탐색 후 갱신된 대상의 위치 확률
적용 분야
탐색 및 구조	조난자, 실종자 탐색
해양 탐사	MH370편 잔해 탐색
데이터 분석	데이터베이스에서 특정 정보 검색
소프트웨어 개발	버그 추적 및 해결
군사 작전	적군 탐색
인공지능	로봇 공학에서의 탐색 전략
경제학	투자 전략 개발
특징
장점	탐색 자원 효율적 배분, 불확실성 하에서 최적 탐색 경로 제시
고려 사항	정확한 사전 확률 설정, 탐색 효율 추정, 환경 변화 반영
역사적 배경
기원	제2차 세계 대전 중 잠수함 탐색 연구에서 유래
발전	18세기 통계학자 토머스 베이즈의 이론에 기반하여 발전
참고 자료
참고 문헌	Bloomberg.com, "How an Eighteenth-Century Statistician Is Helping to Find MH370" Bloomberg.com 기사 Telegraph.co.uk, "MH370 search narrowed to 'hot-spot' as analysis finds plane did not conduct controlled landing" Telegraph.co.uk 기사 Bloomberg.com, "MH370 Hunters Narrow Down Most Likely Site of Wreckage" Bloomberg.com 기사

2. 절차

베이즈 탐색 이론은 잃어버린 물체를 찾기 위한 통계적 방법으로, 다음과 같은 단계를 거친다.^[10]^[11]

1. 가설 수립: 물체에 발생 가능한 모든 합리적인 시나리오를 만든다.

2. 확률 밀도 함수 구성: 각 가설에 대해 물체의 위치에 대한 확률 밀도 함수를 구성한다.

3. 탐색 성공 확률 함수 구성: 특정 위치를 탐색했을 때 물체를 발견할 확률 함수를 구성한다.

4. 확률 밀도 맵 생성: 위 함수들을 곱하여 모든 위치에 대한 탐색 성공 확률 지도를 만든다.

5. 탐색 경로 설정: 확률이 높은 곳부터 낮은 곳 순으로 탐색 경로를 구성한다.

6. 확률 업데이트: 탐색 중 얻는 정보로 확률을 계속 수정하고 베이즈 정리를 적용한다.

이러한 단계를 통해, 사용 가능한 모든 정보를 활용하고, 성공 확률에 대한 비용 추정치를 자동 생성하여 효율적인 탐색을 수행할 수 있다.

2. 1. 가설 수립

찾고자 하는 대상에 대해 발생 가능한 모든 합리적인 시나리오를 구성한다. 일반적인 절차는 다음과 같다.^[10]^[11]

# 해당 물체에 무슨 일이 일어났는지에 대해, 합리적인 가설을 최대한 많이 정식화한다.

2. 2. 확률 밀도 함수 구성

각 가설에 대해, 대상의 위치에 대한 확률 밀도 함수를 구성한다. 해상 수색의 경우, 일반적으로 수심을 사용한 함수가 된다. 수심이 얕은 경우, 장소만 맞으면 발견에 성공할 가능성이 높다. 반대로 수심이 깊으면, 놓칠 가능성이 높아진다.^[10]

2. 3. 탐색 성공 확률 함수 구성

특정 위치 X를 탐색했을 때, 그곳에 실제로 물체가 있다면 물체를 발견할 확률을 나타내는 함수를 구성한다. 해양 탐색의 경우, 이 함수는 일반적으로 수심의 함수가 된다. 수심이 얕은 곳에서는 탐색이 올바른 위치에서 이루어진다면 물체를 찾을 가능성이 높다. 반면, 수심이 깊은 곳에서는 물체를 찾을 가능성이 낮아진다.^[10]

2. 4. 확률 밀도 맵 생성

앞서 만든 두 함수를 곱하여, 모든 위치에 대한 탐색 성공 확률을 나타내는 지도를 만든다. 일반적인 절차는 다음과 같다.^[10]^[11]

위의 정보를 일관성 있게 조합하여, 최종적인 확률 밀도 맵을 작성한다. (일반적으로, 두 개의 함수를 단순하게 곱한다.)
이를 통해, 지점 X의 수색에서 물체가 발견될 확률을, 각각 모든 지점 X에 대해 얻을 수 있다.
이는 확률에 관한 등치선으로 도식화할 수 있다.

2. 5. 탐색 경로 설정

확률이 가장 높은 지점에서 시작하여 확률이 높은 영역, 중간 확률, 낮은 확률 영역을 순서대로 '스캔'하는 탐색 경로를 구성한다.^[10] 탐색 중에는 모든 확률을 지속적으로 수정한다. 예를 들어, 특정 위치 X에 대한 가설이 물체의 붕괴 가능성을 암시하고, 위치 X에서의 탐색에서 잔해가 나오지 않으면, 물체가 그 주변 어딘가에 있을 확률은 크게 감소한다 (보통 0은 아니지만). 그에 따라 다른 위치에 있을 확률은 증가한다. 이러한 수정 과정은 베이즈 정리를 적용하여 수행된다.^[10]

다시 말해, 먼저 가장 찾을 가능성이 높은 곳을 수색한 다음, 찾는 것이 덜 확률적인 곳을 수색하고, 그 다음 확률이 훨씬 낮지만 (연료, 범위, 해류 등의 제한으로 인해) 여전히 가능한 곳을 수색하여, 허용 가능한 비용으로 물체를 찾을 희망이 충분하지 않을 때까지 수색을 계속한다.^[10]

베이즈 방법의 장점은 사용 가능한 모든 정보가 일관되게 사용되고, 주어진 성공 확률에 대한 비용 추정치를 자동으로 생성한다는 것이다. 즉, 수색을 시작하기 전에 "5일 수색에서 그것을 찾을 확률은 65%입니다. 그 확률은 10일 수색 후에 90%로, 15일 수색 후에 97%로 상승할 것입니다"와 같은 진술을 할 수 있다. 따라서 수색에 자원을 투입하기 전에 수색의 경제적 생존 가능성을 추정할 수 있다.^[10]

2. 6. 확률 업데이트

탐색 과정에서 얻는 새로운 정보를 바탕으로 확률 값을 지속적으로 수정하고, 이를 탐색 경로에 반영한다. 예를 들어, 특정 위치 X에서 물체를 찾지 못하면, 그 위치에 물체가 있을 확률은 감소한다. 반면 다른 위치에 물체가 있을 확률은 상대적으로 증가한다. 이러한 수정 과정은 베이즈 정리를 적용하여 수행된다.^[10]

3. 수학적 모델

베이즈 탐색 이론은 어떤 물체를 찾는 확률을 수학적으로 나타낸다. 특정 격자(칸)에 난파선이 있을 확률과, 그 난파선을 실제로 찾을 수 있는 확률을 가정하고, 수색 결과를 바탕으로 확률을 갱신한다.

수색 결과에 따라 특정 격자의 확률은 감소하고, 다른 격자들의 확률은 상대적으로 증가한다. 이는 베이즈 정리를 통해 계산된다.

3. 1. 기본 원리

탐색 영역을 격자(grid) 형태로 나누고, 각 격자에 대상이 존재할 확률 ''p''와 그 대상을 탐지할 확률 ''q''를 가정한다. 어떤 격자를 수색했지만 대상을 찾지 못한 경우, 베이즈 정리에 의해 해당 격자에 대상이 존재할 확률은 다음과 같이 갱신된다.

:

p' = \frac{p(1-q)}{(1-p)+p(1-q)} = p \frac{1-q}{1-pq} < p.

이는 처음 확률 ''p''보다 낮은 값이다.

다른 격자의 경우, 처음 확률이 ''r''이었다면, 수색 후 갱신된 확률은 다음과 같다.

:

r' = r \frac{1}{1- pq} > r.

이는 처음 확률 ''r''보다 높은 값이다.

3. 2. 공식

격자 한 칸에 난파선이 있을 확률이 ''p''이고, 난파선이 있을 경우 이를 성공적으로 감지할 확률이 ''q''라고 가정해 보자. 격자를 수색했으나 난파선을 찾지 못한 경우, 베이즈 정리에 의해 해당 격자에 난파선이 있을 수정된 확률은 다음과 같다.

:

p' = \frac{p(1-q)}{(1-p)+p(1-q)} = p \frac{1-q}{1-pq} < p.

다른 모든 격자의 경우, 사전 확률이 ''r''이면, 사후 확률은 다음과 같다.

:

r' = r \frac{1}{1- pq} > r.

지도상의 각 격자에 대해, 찾고 있는 잔해가 그곳에 있을 확률 ''p''와 잔해가 거기에 있었다고 가정할 때 실제로 발견할 수 있는 확률 ''q''를 가정한다. 어떤 격자를 수색하여 잔해를 찾지 못했다면, 베이즈 정리에 의해 그 격자에 잔해가 있을 확률은 위와 같이 갱신된다.

3. 3. 최적 탐색

데이비드 블랙웰은 최소 비용으로 물체를 찾는 최적의 탐색 정책은 각 단계에서

\frac{p_i a_i}{c_i}

를 최대화하는 위치를 탐색하는 것임을 증명했다.^[6] 여기서

p_i

는 물체가 위치

i

에 있을 확률,

a_i

는 물체가 위치

i

에 있을 때 한 번의 수색으로 이를 발견할 수 있는 확률,

c_i

는 위치

i

를 한 번 수색하는 데 드는 비용이다. 이는 기팅스 지수의 특별한 경우에 해당한다.

4. 응용 사례

베이즈 탐색 이론은 USS 스콜피온 외에도 다양한 사례에 적용되어 성공적인 결과를 얻었다. 바다에서 사라진 영국 선박 중 가장 큰 MV 더비셔와 SS 센트럴 아메리카를 발견하는 데 사용되었으며, 1966년 팔로마레스 B-52 추락 사고 이후 분실된 수소 폭탄 수색과 대서양에서 추락한 에어 프랑스 447편 회수에도 성공적이었다.

미국 해안 경비대는 수색 및 구조 임무 계획 소프트웨어(CASP)에 베이즈 탐색 이론을 통합하여 활용하고 있다. CASP는 해상 수색뿐만 아니라, 지형 및 지면 피복 요소를 추가하여 내륙 수색에도 적용되어 미국 공군과 민간 항공 순찰대에서도 사용되고 있다.

4. 1. USS 스콜피온 탐색 (1968)

1968년 5월, 미국 해군의 원자력 잠수함 스콜피온이 버지니아주 노퍽의 모항에 도착 예정이었으나, 예정대로 도착하지 못했다. 해군 지휘관들은 스콜피온이 동부 해안에서 손실되었다고 생각했지만, 광범위한 수색에도 불구하고 잔해를 발견하지 못했다.

이에 해군의 심해 전문가 존 P. 크레이븐은 스콜피온이 다른 곳에서 침몰했다고 주장하고, 아조레스 제도 남서쪽에서의 수색을 조직했다. 그는 수중 음파 청음기를 이용한 삼각 측량을 바탕으로 수색을 진행했다. 그는 단 하나의 함선인 미자르만 배정받았으며, 자원을 극대화하기 위해 컨설턴트 수학자 회사인 Metron Inc.의 조언을 구했다. 그 결과 베이즈 탐색 방법론이 채택되었고, 숙련된 잠수함 함장들과의 인터뷰를 통해 스콜피온의 손실을 야기할 수 있는 가설을 세웠다.

수색 해역은 격자형 사각형으로 나뉘었고, 각 가설에 따라 각 사각형에 확률이 할당되어, 각 가설마다 하나의 확률 격자가 생성되었다. 그런 다음 이들을 모두 합쳐 전체 확률 격자를 생성했다. 각 사각형에 할당된 확률은 난파선이 해당 사각형에 있을 확률이었다. 두 번째 격자는 해당 사각형을 수색했을 때 난파선을 성공적으로 찾을 확률을 나타내는 확률로 구성되었으며, 난파선이 실제로 그곳에 있었다. 이것은 수심의 알려진 함수였다. 이 격자를 이전 격자와 결합한 결과는 해당 사각형을 수색했을 경우 바다의 각 격자 사각형에서 난파선을 찾을 확률을 제공하는 격자가 되었다.

1968년 10월 말, 해군의 해양 연구선 미자르는 아조레스 제도에서 남서쪽으로 약 740km 떨어진 해저, 3000m 이상의 수심에서 스콜피온 선체의 일부를 발견했다.^[5] 이는 해군이 수중 "SOSUS" 청취 시스템에서 음향 테이프를 공개한 후의 일로, 여기에는 스콜피온의 파괴 소리가 담겨 있었다. 이후 조사 위원회가 다시 소집되었고, 심해 잠수정 트리예스테 II를 포함한 다른 선박들이 현장으로 파견되어 많은 사진과 기타 데이터를 수집했다.

크레이븐이 스콜피온 잔해 위치를 찾은 데 큰 공을 세웠지만, 수중 음향을 사용하여 폴라리스 미사일의 낙하 지점을 정확히 찾아내는 데 선구적인 역할을 한 음향 전문가 고든 해밀턴이 난파선이 최종적으로 발견된 좁은 "수색 구역"을 정의하는 데 중요한 역할을 했다. 해밀턴은 카나리아 제도에 청취 기지를 설치하여 일부 과학자들이 선체의 파괴 소리로 추정하는 명확한 신호를 얻었다. 미 해군 연구소의 과학자 체스터 "벅" 부캐넌은 미자르에 자체 설계한 견인식 카메라 썰매를 사용하여 마침내 스콜피온을 발견했다.^[5] 해군 연구소의 엔지니어링 서비스 부서의 J. L. "잭" 햄이 제작한 견인식 카메라 썰매는 미국 해군 국립 박물관에 보관되어 있다. 부캐넌은 1964년에 이 기술을 사용하여 스레셔의 난파된 선체를 발견했다.

4. 2. 기타 주요 사례

베이즈 탐색 이론은 다음과 같은 주요 사례에서 그 유용성이 입증되었다.

팔로마레스 B-52 추락 사고에서 행방불명된 수소 폭탄 수색^[10]
더비셔호 탐색
센트럴 아메리카호 탐색
에어 프랑스 447편 추락 사고 실종자 및 잔해 수색^[11]

이 이론은 미국 해안 경비대의 수색 구조 임무 계획 소프트웨어 CASP에 통합되었으며, 이후 미국 공군과 민간 항공 초계대가 내륙 수색에도 활용하고 있다.

4. 3. 미국 해안경비대 CASP

미국 해안경비대는 수색 및 구조 임무 계획 소프트웨어(CASP)에 베이즈 탐색 이론을 통합하여 활용하고 있다.^[11] CASP는 해상 수색뿐만 아니라, 지형 및 지면 피복 요소를 추가하여 내륙 수색에도 적용되어 미국 공군과 민간 항공 초계대에서도 사용되고 있다.

5. 최적 탐색 노력 분배

이 문제에 관한 교과서적인 문헌으로는 메트론사(Metron)의 로렌스 D. 스톤이 저술하여 1975년 미국 운영 연구 학회가 간행한 『최적 탐색 이론』(The Theory of Optimal Search)이 있으며, 이는 같은 해에 학회의 란체스터 상을 수상했다.^[1]

n개의 사각형 구역 중 한 곳에 정지해 있는 물체가 숨겨져 있다고 가정한다. 각 구역 $i$ 에 대해 세 가지 알려진 변수가 있다. $c_i$ 는 한 번의 수색에 드는 비용, $a_i$ 는 물체가 그곳에 있었을 때 한 번의 수색으로 이를 발견할 수 있는 확률, $p_i$ 는 물체가 그곳에 있을 확률이다. 수색자는 시작 시점의 사전 확률을 알고 있으며, 발견에 실패할 때마다 베이즈 정리에 따라 이를 갱신해 나간다.

물체를 발견하기 위해 예상되는 비용을 어떻게 최소화할 것인가 하는 것은 고전적인 문제이며, 이는 데이비드 블랙웰이 해결했다. 의외로, 이 최적화 방법은 " $\frac{p_i a_i}{c_i}$ 가 최대가 되는 곳을 순서대로 수색해 나간다"는 형태로 쉽게 표현할 수 있다. 사실, 이것은 기팅스 지수의 특수한 경우에 해당한다.^[1]

참조

_[1] 웹사이트 How an Eighteenth-Century Statistician Is Helping to Find MH370 https://www.bloomber[...] 2016-03-07
_[2] 웹사이트 MH370 search narrowed to 'hot-spot' as analysis finds plane did not conduct controlled landing https://www.telegrap[...] 2016-03-07
_[3] 웹사이트 MH370 Hunters Narrow Down Most Likely Site of Wreckage https://www.bloomber[...] 2016-03-07
_[4] 서적 The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines & Emerged Triumphant from Two Centuries of Controversy Yale University Press 2011
_[5] 간행물 Strange Devices That Found the Sunken Sub Scorpion. https://books.google[...] Popular Science 1969-04
_[6] 논문 Optimal Sequential Search: A Bayesian Approach 1985
_[7] 웹사이트 How an Eighteenth-Century Statistician Is Helping to Find MH370 https://www.bloomber[...] 2016-03-07
_[8] 웹사이트 MH370 search narrowed to 'hot-spot' as analysis finds plane did not conduct controlled landing https://www.telegrap[...] 2016-03-07
_[9] 웹사이트 MH370 Hunters Narrow Down Most Likely Site of Wreckage https://www.bloomber[...] 2016-03-07
_[10] 서적 The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines & Emerged Triumphant from Two Centuries of Controversy Yale University Press 2011
_[11] 문서 Computer Assisted Search Program、コンピュータ支援された捜索プログラム
_[12] 논문 Strange Devices That Found the Sunken Sub Scorpion https://books.google[...] 2022-02-01
_[13] 논문 Optimal Sequential Search: A Bayesian Approach 1985

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com