Байесовская теория поиска

Метод поиска потерянных предметов

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

Процедура

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

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

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

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

Помимо USS Scorpion , другие суда, обнаруженные с помощью байесовской теории поиска, включают MV  Derbyshire , крупнейшее британское судно, когда-либо потерянное в море, и SS  Central America . Он также оказался успешным в поиске потерянной водородной бомбы после крушения B-52 в Паломаресе в 1966 году в Испании, ^[4] и подъеме в Атлантическом океане разбившегося рейса Air France 447 .

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

Математика

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

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

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

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

УСССкорпион

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

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

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

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

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

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

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

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

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

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

• Байесовский вывод  – Метод статистического вывода
• Поисковая игра  – Игра для двух человек с нулевой суммой

Ссылки

1. Уитли, Ангус. «Как статистик восемнадцатого века помогает найти MH370». Bloomberg.com . Получено 07.03.2016 .
2. "Поиск MH370 сужен до "горячей точки", поскольку анализ показал, что самолет не совершил контролируемую посадку". Telegraph.co.uk . Получено 07.03.2016 .
3. Уитли, Ангус. «Охотники за MH370 сузили круг наиболее вероятных мест крушения». Bloomberg.com . Получено 07.03.2016 .
4. Макгрейн, Шарон Берч (2011). Теория, которая не умрет: как правило Байеса взломало код «Энигмы», выследило русские подлодки и вышло победителем из двух столетий споров . Издательство Йельского университета. С. 92–. ISBN 978-0-300-18822-6.
5. «Странные устройства, которые нашли затонувший Sub Scorpion». Popular Science , апрель 1969 г., стр. 66–71.
6. Ассаф, Дэвид; Замир, Шмуэль (1985). «Оптимальный последовательный поиск: байесовский подход». Анналы статистики . 13 (3): 1213–1221. doi : 10.1214/aos/1176349665 . ISSN  0090-5364. JSTOR  2241134.

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