베이즈 탐색 이론

**베이즈 탐색 이론**(Bayesian search theory)은 잃어버린 물건을 찾는 데 베이즈 통계를 적용한 것이다. 이는 USS 스콜피온(USS Scorpion)과 같은 잃어버린 해상 선박을 찾는 데 여러 번 사용되었으며 2009년 에어프랑스 447편 추락 사고에서 비행 기록 장치를 복구하는 데 핵심적인 역할을 했다. 또한 말레이시아 항공 370편의 잔해의 위치를 찾는 시도에도 사용되었다.

## 절차
일반적인 절차는 다음과 같다.
# 물체에 무슨 일이 일어났을지에 대해 가능한 한 많은 합리적인 가설을 세운다.
# 각 가설에 대해 물체의 위치에 대한 확률 밀도 함수를 구성한다.
# 실제로 위치 X에 있는 경우 그곳을 탐색할 때 위치 X에서 실제로 개체를 찾을 확률을 제공하는 함수를 구성한다. 해양 탐색에서 이는 일반적으로 수심의 함수이다. 얕은 물에서는 개체를 찾을 가능성이 높다. 탐색이 올바른 위치에 있는 경우. 깊은 물에서는 확률이 감소한다.
# 위의 정보를 일관되게 결합하여 전체 확률 밀도 맵을 생성한다. (보통 이는 단순히 두 함수를 곱하는 것을 의미한다.) 이는 모든 가능한 위치 X에 대해 위치 X를 보고 객체를 찾을 확률을 제공한다. (이는 확률의 등고선 지도로 시각화될 수 있다.)
# 확률이 가장 높은 지점에서 시작하여 확률이 높은 영역, 중간 확률, 확률이 낮은 영역을 '스캔'하는 탐색 경로를 구성한다.
# 탐색하는 동안 모든 확률을 지속적으로 수정한다. 예를 들어, 위치 X에 대한 가설이 물체의 붕괴 가능성을 암시하고 위치 X에서의 탐색에서 조각이 나오지 않으면 물체가 그 주변 어딘가에 있을 확률은 크게 감소하지만(보통 0은 아니지만) 확률은 그에 따라 다른 위치에 있는 것도 증가한다. 수정 과정은 베이즈 정리를 적용하여 수행된다.

다시 말해, 먼저 가장 찾을 확률이 높은 곳을 수색하고, 그 다음으로 찾을 확률이 낮은 곳을 수색하며, 연료, 항속 거리, 해류 등의 제약으로 인해 확률이 더 낮지만 여전히 가능성이 있는 곳을 수색한다. 이는 허용 가능한 비용으로 물체를 찾을 희망이 거의 없을 때까지 계속된다.

베이즈 방법의 장점은 사용 가능한 모든 정보가 일관되게 (즉, "누수 방지" 방식으로) 사용되며, 이 방법이 주어진 성공 확률에 대한 비용 추정치를 자동으로 생성한다는 것이다. 즉, 수색을 시작하기 전에도 가설적으로 "5일간의 수색으로 찾을 확률이 65%이다. 이 확률은 10일 후 90%로, 15일 후 97%로 증가할 것이다"와 유사한 진술을 할 수 있다. 따라서 수색에 자원을 투입하기 전에 수색의 경제적 타당성을 추정할 수 있다.

USS 스콜피온 (SSN-589) 외에도 베이즈 탐색 이론으로 위치가 확인된 다른 선박으로는 해상에서 사라진 가장 큰 영국 선박인 MV 데르비셔와 SS 센트럴 아메리카가 있다. 또한 스페인 1966년 팔로마레스 B-52 추락 사고 이후 실종된 수소폭탄 수색과 에어프랑스 447편 추락 사고의 대서양 회수에도 성공적으로 활용되었다.

베이즈 탐색 이론은 미국 해안경비대가 탐색 구조에 사용하는 CASP (Computer Assisted Search Program) 임무 계획 소프트웨어에 통합되어 있다. 이 프로그램은 나중에 미국 공군과 민간 항공 순찰대가 사용하도록 지형 및 지표면 요소를 추가하여 내륙 수색에 맞게 조정되었다.

## 수학

격자 칸에 잔해가 있을 확률이 p이고, 잔해가 있을 경우 성공적으로 잔해를 탐지할 확률이 q라고 가정하자. 만약 그 칸을 수색했지만 잔해가 발견되지 않았다면, 베이즈 정리에 의해 그 칸에 잔해가 있을 수정된 확률은 다음과 같다.

:   p' = \frac{p(1-q)}{(1-p)+p(1-q)} = p \frac{1-q}{1-pq} 
다른 모든 격자 칸의 경우, 사전 확률이 r이라면 사후 확률은 다음과 같다.

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

### USS 스콜피온

1968년 5월, 미국 해군의 원자력 잠수함 USS 스콜피온 (SSN-589)은 예상대로 모항인 노퍽 (버지니아주)에 도착하지 못했다. 미국 해군 지휘관들은 이 함정이 미국 동해안에서 실종된 것이 거의 확실하다고 판단했지만, 광범위한 수색에도 불구하고 스콜피온의 잔해를 발견하지 못했다.

이후 해군 심해 전문가인 존 크레이븐은 스콜피온이 다른 곳에서 침몰했을 것이라고 제안했다. 크레이븐은 수중청음기를 이용한 논란의 여지가 있는 대략적인 삼각 측량에 기반하여 아소르스 제도 남서쪽에서 수색을 조직했다. 그는 USNS 미자르 (AGOR-11)라는 단 한 척의 배만 배정받았고, 자원을 최대한 활용하기 위해 컨설팅 수학 회사인 Metron Inc.의 조언을 구했다. 베이즈 탐색 방법론이 채택되었다. 숙련된 잠수함 지휘관들을 인터뷰하여 스콜피온의 손실 원인에 대한 가설들을 구성했다.

해역은 격자 칸으로 나뉘었고, 각 가설 아래 각 칸에 확률이 할당되어 각 가설에 대한 여러 확률 격자를 생성했다. 그런 다음 이들을 합산하여 전체 확률 격자를 만들었다. 각 칸에 할당된 확률은 잔해가 그 칸에 있을 확률이었다. 두 번째 격자는 그 칸을 수색하고 잔해가 실제로 그곳에 있을 경우 잔해를 성공적으로 찾을 확률을 나타내는 확률로 구성되었다. 이는 수심의 알려진 함수였다. 이 격자와 이전 격자를 결합한 결과는 수색할 경우 각 해역 격자 칸에서 잔해를 찾을 확률을 제공하는 격자이다.

1968년 10월 말, 해군 해양 연구선 는 아소르스 제도 남서쪽 약  지점의 해저에서 스콜피온 선체의 일부를 발견했으며, 수심은  이상이었다. 이는 해군이 스콜피온의 파괴음을 담고 있는 수중 "SOSUS" 청취 시스템의 음향 테이프를 공개한 이후였다. 이후 조사 위원회가 재소집되었고, 바티스카프 트리에스테 II를 포함한 다른 선박들이 현장에 파견되어 많은 사진과 기타 데이터를 수집했다.

크레이븐은 스콜피온의 잔해를 찾는 데 큰 공로를 인정받았지만, 폴라리스 미사일 낙하 지점을 정확히 찾아내기 위해 수중음향학 사용을 개척한 음향 전문가 고든 해밀턴은 잔해가 최종적으로 발견된 압축된 "수색 상자"를 정의하는 데 중요한 역할을 했다. 해밀턴은 카나리아 제도에 청취 스테이션을 설치하여, 일부 과학자들이 함정이 파괴 수심을 지날 때 선체 압력 선체가 폭발하는 소리라고 믿는 신호를 명확하게 얻었다. 해군 연구소 과학자 체스터 "벅" 부캐넌은 미자르호에 자신이 설계한 견인식 카메라 썰매를 사용하여 마침내 스콜피온을 발견했다. 해군 연구소 공학 서비스 부서의 J. L. "잭" 햄이 제작한 이 견인식 카메라 썰매는 미국 해군 박물관에 소장되어 있다. 부캐넌은 이 기술을 사용하여 1964년에 USS 스레셔 (SSN-593)의 난파된 선체를 발견한 바 있다.

## 최적 탐색 노력 분배

이 주제에 대한 고전적인 책인 Metron Inc.의 로렌스 D. 스톤이 쓴 "The Theory of Optimal Search (미국 운영 연구 학회, 1975)"는 1975년 미국 운영 연구 학회의 란체스터 상을 수상했다.

## 상자 안에서 탐색

정지된 물체가 n개의 상자(위치) 중 하나에 숨겨져 있다고 가정하자. 각 위치 i에는 세 가지 알려진 매개변수가 있다: 단일 탐색 비용 c_i, 물체가 그곳에 있을 경우 단일 탐색으로 물체를 찾을 확률 a_i, 그리고 물체가 그곳에 있을 확률 p_i. 탐색자는 물체를 찾는다. 그들은 초기에 사전 확률을 알고 각 (실패한) 시도 후에 베이즈 정리에 따라 확률을 갱신한다.

최소 기대 비용으로 물체를 찾는 문제는 데이비드 블랙웰이 해결한 고전적인 문제이다. 이후 데이비드 아사프는 블랙웰의 결과를 두 개 이상의 물체로 확장했다. 최적의 정책은 각 단계에서 \frac{p_i a_i}{c_i}를 최대화하는 위치를 살펴보는 것이다. 이것은 기틴스 지수의 특별한 경우이다.

## 같이 보기
* 베이즈 추론
* 탐색 게임

## 각주

## 출처
* Stone, Lawrence D., *The Theory of Optimal Search*, published by the Operations Research Society of America, 1975
* Stone, Lawrence D., *In Search of Air France Flight 447.* Institute of Operations Research and the Management Sciences, 2011. https://www.informs.org/ORMS-Today/Public-Articles/August-Volume-38-Number-4/In-Search-of-Air-France-Flight-447
* Iida, Koji., * Studies on the Optimal Search Plan*, Vol.&nbsp;70, Lecture Notes in Statistics, Springer-Verlag, 1992.
* De Groot, Morris H., *Optimal Statistical Decisions*, Wiley Classics Library, 2004.
* Richardson, Henry R; and Stone, Lawrence D. Operations Analysis during the underwater search for *Scorpion*. *Naval Research Logistics Quarterly*, June&nbsp;1971, Vol.&nbsp;18, Number&nbsp;2. Office of Naval Research.
* Stone, Lawrence D. Search for the SS *Central America*: Mathematical Treasure Hunting. Technical Report, Metron Inc. Reston, Virginia.
* Koopman, B.O. *Search and Screening*, Operations Research Evaluation Group Report 56, Center for Naval Analyses, Alexandria, Virginia. 1946.
* Richardson, Henry R; and Discenza, J.H. The United States Coast Guard computer-assisted search planning system (CASP). *Naval Research Logistics Quarterly*. Vol.&nbsp;27 number&nbsp;4. pp.&nbsp;659–680. 1980.
* Ross, Sheldon M., *An Introduction to Stochastic Dynamic Programming*, Academic Press. 1983.

분류:베이즈 통계학
분류:검색 알고리즘
분류:운용 과학