Байесовская теория поиска - Bayesian search theory

Байесовская теория поиска это применение Байесовская статистика к поиску потерянных предметов. Его несколько раз использовали для поиска потерянных морских судов, например USS Скорпион, и сыграл ключевую роль в восстановлении бортовых самописцев в Рейс 447 авиакомпании Air France катастрофа 2009 года. Он также использовался в попытках найти останки Рейс 370 Malaysia Airlines.^[1][2][3]

Процедура

Обычная процедура выглядит следующим образом:

1. Сформулируйте как можно больше разумных гипотез о том, что могло случиться с объектом.
2. Для каждой гипотезы построить функция плотности вероятности за расположение объекта.
3. Создайте функцию, дающую вероятность фактического нахождения объекта в местоположении X при поиске там, если он действительно находится в местоположении X. При поиске в океане это обычно является функцией глубины воды - на мелководье шансы найти объект хорошие, если поиск в нужном месте. В глубокой воде шансы уменьшаются.
4. Последовательно объедините приведенную выше информацию, чтобы создать общую карту плотности вероятности. (Обычно это просто означает умножение двух функций вместе.) Это дает вероятность найти объект, глядя в местоположение X, для всех возможных местоположений X. (Это можно визуализировать как контурная карта вероятности.)
5. Постройте путь поиска, который начинается в точке с наибольшей вероятностью и «просматривает» области с высокой вероятностью, затем промежуточные вероятности и, наконец, области с низкой вероятностью.
6. Постоянно проверяйте все вероятности во время поиска. Например, если гипотезы для местоположения X предполагают вероятное разрушение объекта и поиск в местоположении X не дал никаких фрагментов, то вероятность того, что объект находится где-то поблизости, значительно снижается (хотя обычно не до нуля), в то время как вероятности его нахождения в других местах соответственно увеличивается. Процесс доработки осуществляется путем применения Теорема Байеса.

Другими словами, сначала ищите там, где он, скорее всего, будет найден, затем ищите там, где его нахождение менее вероятно, затем ищите там, где вероятность еще меньше (но все же возможна из-за ограничений по топливу, дальности, водным потокам и т. Д.), пока остается недостаточная надежда найти объект по приемлемой стоимости.

Преимущества байесовского метода заключаются в том, что вся доступная информация используется согласованно (т. Е. "Защищенным от утечек" способом), и метод автоматически производит оценки стоимости для заданной вероятности успеха. То есть, даже до начала поиска, можно гипотетически сказать, что «существует 65% -ный шанс найти его за 5-дневный поиск. Эта вероятность возрастет до 90% после 10-дневного поиска и 97% после 15 дней »или аналогичное заявление. Таким образом, можно оценить экономическую жизнеспособность поиска до выделения ресурсов на поиск.

Отдельно от USS Скорпион, другие суда, обнаруженные с помощью теории байесовского поиска, включают MVДербишир, крупнейшее британское судно, когда-либо потерянное в море, и SSЦентральная Америка. Он также оказался успешным в поисках потерянного водородная бомба после 1966 Крушение Palomares B-52 в Испании, а также восстановление в Атлантическом океане потерпевшего крушение Рейс 447 авиакомпании Air France.

Теория байесовского поиска включена в программу планирования миссии CASP (Computer Assisted Search Program), используемую Береговая охрана США за поиск и спасение. Позже эта программа была адаптирована для поиска на суше путем добавления факторов местности и почвенного покрова для использования ВВС США и Гражданский воздушный патруль.

Математика

Предположим, что квадрат сетки имеет вероятность п содержания обломков и что вероятность успешного обнаружения обломков, если они есть, q. Если в квадрате обыскивают и не обнаруживают обломков, то, согласно теореме Байеса, пересмотренная вероятность того, что затонувший корабль находится в квадрате, определяется как

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

Для любого другого квадрата сетки, если его априорная вероятность равна р, его апостериорная вероятность дается выражением

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

USS Скорпион

В мае 1968 г. ВМС США с атомная подводная лодка USS Скорпион (SSN-589) не прибыла, как ожидалось, в порт приписки Норфолк, Вирджиния. Командующие ВМС США были почти уверены, что судно потерялось у берегов. Восточное побережье, но тщательные поиски не позволили обнаружить останки Скорпион.

Затем, глубоководный эксперт ВМФ, Джон П. Крейвен, Предполагается, что Скорпион затонул в другом месте. Крейвен организовал поиски к юго-западу от Азорские острова на основе противоречивой приблизительной триангуляции гидрофоны. Ему выделили только один корабль, Мицар, и он воспользовался советом фирмы математиков-консультантов, чтобы максимально использовать свои ресурсы. Была принята байесовская методология поиска. Были опрошены опытные командиры подводных лодок, чтобы сформулировать гипотезы о том, что могло вызвать потерю подводных лодок. Скорпион.

Район моря был разделен на квадраты сетки, и каждому квадрату была присвоена вероятность согласно каждой из гипотез, чтобы получить ряд сеток вероятностей, по одной для каждой гипотезы. Затем они были сложены вместе, чтобы получить общую сетку вероятностей. Вероятность, привязанная к каждому квадрату, тогда была вероятностью того, что обломок находится в этом квадрате. Вторая сетка была построена с вероятностями, которые представляли вероятность успешного обнаружения обломков, если бы этот квадрат был обыскан и обломки действительно были бы там. Это была известная функция глубины воды. Результатом объединения этой сетки с предыдущей сеткой является сетка, которая дает вероятность найти затонувший корабль в каждом квадрате сетки моря, если его нужно будет обыскать.

В конце октября 1968 года океанографический исследовательский корабль ВМФ, Мицар, расположенные секции корпуса Скорпион на морском дне, примерно в 740 км (400 морских миль; 460 миль) к юго-западу от Азорские острова,^[4] на глубине более 3000 м (9800 футов). Это было после того, как военно-морской флот выпустил аудиозаписи из подводного мира "СОСУС "подслушивающая система, содержащая звуки разрушения Скорпион. Впоследствии следственный суд был вновь созван, и другие суда, в том числе батискаф Триест II, были отправлены на место происшествия, собрав множество фотографий и других данных.

Хотя Крейвен получил большое признание за обнаружение обломков Скорпион, Гордон Гамильтон, эксперт по акустике, который первым применил гидроакустика для точного определения мест приводнения ракеты Polaris сыграло важную роль в определении компактного "окна поиска", в котором в конечном итоге было найдено обломки. Гамильтон установил на Канарских островах станцию ​​прослушивания, которая получала четкий сигнал того, что, по мнению некоторых ученых, было шумом взрыва прочного корпуса судна, когда оно проходило мимо. глубина дробления. А Лаборатория военно-морских исследований ученый по имени Честер «Бак» Бьюкенен, используя на борту буксируемые снегоходы собственной конструкции Мицар, наконец найденный Скорпион.^[4] Буксируемые салазки для фотоаппаратов, изготовленные Дж. Л. «Жаком» Хаммом из отдела инженерных услуг лаборатории военно-морских исследований, размещены в Национальный музей ВМС США. Бьюкенен обнаружил разбитый корпус Thresher в 1964 г. по этой методике.

Оптимальное распределение поисковых усилий

Классическая книга на эту тему Теория оптимального поиска (Общество исследования операций Америки, 1975) по Лоуренс Д. Стоун выиграл 1975 Приз Ланчестера Американским обществом исследования операций.

Поиск в ящиках

Предположим, что неподвижный объект скрыт в одном из n ящиков (локаций). Для каждого места ${\displaystyle i}$ известны три параметра: стоимость ${\displaystyle c_{i}}$ одиночного поиска вероятность ${\displaystyle a_{i}}$ найти объект за один поиск, если объект есть, и вероятность ${\displaystyle p_{i}}$ что объект есть. Искатель ищет объект. Они знают априорные вероятности в начале и обновляют их по закону Байеса после каждой (неудачной) попытки. Проблема нахождения объекта с минимальной ожидаемой стоимостью - классическая проблема, решаемая Дэвид Блэквелл.^[5] Удивительно, но оптимальную политику легко описать: на каждом этапе ищите то место, которое максимально${\displaystyle {\frac {p_{i}a_{i}}{c_{i}}}}$. На самом деле это частный случай Индекс Гиттинса.

Смотрите также

• Байесовский вывод
• Искать игры

Рекомендации

1. Ангус Уитли1, Ангус Уитли. "Как статистик восемнадцатого века помогает найти MH370". Bloomberg.com. Получено 2016-03-07.
2. «Поиск MH370 сузился до« горячей точки », поскольку анализ показывает, что самолет не совершил контролируемую посадку». Telegraph.co.uk. Получено 2016-03-07.
3. Ангус Уитли1, Ангус Уитли. «Охотники за MH370 выясняют наиболее вероятное место крушения». Bloomberg.com. Получено 2016-03-07.
4. «Странные устройства, обнаружившие затонувшего подводного скорпиона». Популярная наука, Апрель 1969 г., стр. 66–71.
5. Ассаф, Давид; Замир, Шмуэль (1985). «Оптимальный последовательный поиск: байесовский подход». Анналы статистики. 13 (3): 1213–1221. Дои:10.1214 / aos / 1176349665. ISSN  0090-5364. JSTOR  2241134.

• Стоун, Лоуренс Д., Теория оптимального поиска, опубликованный Общество исследования операций Америки, 1975
• Стоун, Лоуренс Д., В поисках рейса 447 авиакомпании Air France. Институт исследований операций и управленческих наук, 2011 г. https://www.informs.org/ORMS-Today/Public-Articles/August-Volume-38-Number-4/In-Search-of-Air-France-Flight-447
• Иида, Коджи., Исследования по оптимальному плану поиска, Vol. 70, Конспект лекций по статистике, Springer-Verlag, 1992.
• Де Гроот, Моррис Х., Оптимальные статистические решения, Библиотека Wiley Classics, 2004.
• Ричардсон, Генри Р.; и Стоун, Лоуренс Д. Анализ операций во время подводных поисков Скорпион. Ежеквартально по логистике военно-морских исследований, Июнь 1971 г., т. 18, номер 2. Управление военно-морских исследований.
• Стоун, Лоуренс Д. Поиски СС Центральная Америка: Математический поиск сокровищ. Технический отчет, Metron Inc. Рестон, Вирджиния.
• Купман, Б. Поиск и проверка, Отчет 56 Группы оценки операционных исследований, Центр военно-морского анализа, Александрия, Вирджиния. 1946 г.
• Ричардсон, Генри Р.; и Discenza, J.H. Компьютерная система планирования поиска береговой охраны США (CASP). Ежеквартально по логистике военно-морских исследований. Vol. 27 номер 4. С. 659–680. 1980 г.
• Росс, Шелдон М., Введение в стохастическое динамическое программирование, Academic Press. 1983 г.