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

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

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

Процедура

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

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

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

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

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

Байесовская теория поиска включена в программное обеспечение для планирования миссий 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 «Скорпион» (SSN-589) не смогла, как ожидалось, прибыть в порт приписки Норфолк, штат Вирджиния . Командование ВМС США было почти уверено, что судно потерялось у восточного побережья , но обширные поиски там не смогли обнаружить останки "Скорпиона" .

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

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

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

Хотя Крэйвен получил большую заслугу в обнаружении обломков «Скорпиона» , Гордон Гамильтон, эксперт по акустике, который первым применил гидроакустику для определения мест приводнения ракет «Поларис», сыграл важную роль в определении компактного «поискового поля», в котором в конечном итоге было обнаружено обломки. Гамильтон установил на Канарских островах станцию ​​прослушивания, которая получила четкий сигнал о том, что, по мнению некоторых ученых, было шумом взрыва прочного корпуса судна, когда оно проходило глубину раздавливания . Ученый из военно-морской исследовательской лаборатории по имени Честер «Бак» Бьюкенен, используя буксируемую салазку с камерой собственной конструкции на борту «Мицар» , наконец обнаружил Скорпиона . ^[5] Буксируемая салазка для камеры, изготовленная Дж. Л. «Джеком» Хэммом из отдела инженерных служб Военно-морской исследовательской лаборатории, хранится в Национальном музее ВМС США . Используя этот метод, Бьюкенен обнаружил разбитый корпус «Трешера» в 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 . Проверено 7 марта 2016 г.
2. «Поиск MH370 сузился до «горячей точки», поскольку анализ показал, что самолет не совершил контролируемую посадку» . Телеграф.co.uk . Проверено 7 марта 2016 г.
3. Уитли, Ангус. «Охотники за MH370 определили наиболее вероятное место крушения» . Bloomberg.com . Проверено 7 марта 2016 г.
4. МакГрейн, Шэрон Берч (2011). Теория, которая не умрет: как правило Байеса взломало код-загадку, выследило российские подводные лодки и одержало победу в двухвековых спорах . Издательство Йельского университета. стр. 92–. ISBN 978-0-300-18822-6.
5. «Странные устройства, которые нашли затонувший подводный скорпион». Popular Science , апрель 1969 г., стр. 66–71.
6. Ассаф, Дэвид; Замир, Шмуэль (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/В поисках воздуха-Франция-Рейс-447
• Иида, Кодзи., Исследования по оптимальному плану поиска , Vol. 70, Конспект лекций по статистике, Springer-Verlag, 1992.
• Де Гроот, Моррис Х., Оптимальные статистические решения , Библиотека классической литературы Wiley, 2004.
• Ричардсон, Генри Р.; и Стоун, Лоуренс Д. Анализ операций во время подводных поисков Скорпиона . Ежеквартальный журнал военно-морских исследований , июнь 1971 г., Vol. 18, номер 2. Управление военно-морских исследований.
• Стоун, Лоуренс Д. Поиски СС в Центральной Америке : математический поиск сокровищ. Технический отчет, Metron Inc. Рестон, Вирджиния.
• Купман, Б.О. Поиск и проверка , Отчет 56 группы по исследованию операций, Центр военно-морского анализа, Александрия, Вирджиния. 1946 год.
• Ричардсон, Генри Р.; и Дисенца, Дж. Х. Компьютерная система планирования поиска береговой охраны США (CASP). Ежеквартальный журнал военно-морских исследований по логистике . Том. 27 № 4. С. 659–680. 1980.
• Росс, Шелдон М., Введение в стохастическое динамическое программирование , Academic Press. 1983.