Байєсівський пошук: простий метод пошуку речей, які ви загубили

Знайдіть свій гаманець чи ключі, або ж атомний підводний човен.

Основні тези

Кожен із нас час від часу щось губить: чи то телефон, гаманець, чи комплект ключів.

Коли губиться щось надзвичайно цінне, наприклад, атомний підводний човен, то часто використовуються математичні методи його пошуку.

Суть цього методу досить проста, щоб зрозуміти та застосувати його у повсякденному житті.

Якщо ви губите телефон, гаманець або ключі, то можете вдатися до кількох хитрощів, аби визначити їх місцезнаходження. Можливо, ви повторите всі свої кроки. Можливо, обнишпорите кожне місце, на якому зазвичай залишаєте речі. Або ви спробуєте пригадати кожне незвичне місце, у якому перебували останнім часом. І кожен із цих варіантів має логіку.

Коли суб’єкт, який має величезні ресурси, втрачає щось надзвичайно цінне (як згаданий нами раніше атомний підводний човен), задля його пошуку звертаються до байєсівської теорії. На щастя для всіх нас, базові концепції досить прості, аби ми могли розібратися та знайти повсякденні речі. Навіть якщо ваш зниклий предмет коштує лише сотню доларів, цей математичний процес може оптимізувати логічний ланцюжок вашого пошуку, заощадивши ваш час та гроші.

Чувак, куди поділася моя тачка?

Імовірність того, що загублений предмет знайдеться в одному місці, а не в іншому, – це інтуїтивна концепція, яку можна перетворити на математичний об’єкт. Беремо звичайну карту, поділену на сітку, і кожному розділу призначаємо ймовірність знаходження там елементу, що є формою функції щільності ймовірності. Уявімо, що ви залишили машину на парковці, розрахованій на 100 місць, а тепер забули, де припаркувалися. Найпростіша функція щільності ймовірності паркування дорівнює одній обмеженій території для кожного місця, кожна з імовірністю 1/100 (або 0,01).

Також припустимо, що ви не інвалід, а є десять місць для людей з обмеженими можливостями. Тепер функція щільності ймовірності виглядає більше як 0,011 у 90 проміжках і 0,001 у кожному неактивному місці. (Ми також припускаємо 10% імовірність того, що ви зробили помилку при паркуванні.)

Давайте наведемо ще деякі дані. Десять найдальших від магазину паркомісць – порожні. Тобто шанси, що ваша машина там опиниться, дорівнюють нулю. Тепер ваша функція щільності виглядає як 80 квадратів з імовірністю ~0,0125. Якщо ви зазвичай об’їжджаєте ділянку, аби знайти вільну територію найближче до дверей, тоді ймовірність того, що це місце ближче до магазину, буде дещо вищою, а те, що далі, – меншою.

Справа в тому, що кожного разу, коли ви отримуєте більше інформації, функція щільності ймовірності змінюється. Отже, таким способом ви можете звузити і пришвидшити пошук, починаючи з місць із найвищою імовірністю, де може знаходитися ваш автомобіль, і просуваючись вниз по списку ймовірностей, перевіряючи місця з найменшою вірогідністю (як крайній варіант).

Пес з'їв моє домашнє завдання?

Перша карта, звісно, хороша, але друга ще краща. Ця карта містить для кожної області пошуку ймовірність того, що ви дійсно знайдете предмет, якщо він знаходиться у цьому місці.

Щоб продемонструвати це, давайте використаємо трохи іншу метафору. Якщо ваше домашнє завдання зникло, його буде легше або ж важче знайти в тих місцях, де ви можете його шукати. Якщо домашнє завдання лежить на порожньому столі, ви обов’язково побачите його там. Якщо ви залишили його на захаращеному столі, заваленому різними паперами, відповідно, ваші шанси зменшуються. Якщо воно могло вилетіти з вікна, то ймовірність того, що воно все ще лежить у дворі, значно менша (це зумовлено поривами вітру). Якщо його з’їв собака, ваша ймовірність знайти його зводиться до нуля.

Тепер візьміть ці дві карти розподілу ймовірностей і перемножте їх разом. Будь-яка область пошуку, яка, напевно, містить предмет і має високу ймовірність того, що ви його там знайдете, якщо він там, звісно, є, буде представлена відносно великим числом. Це хороші місця для початку пошуку. Місця, де предмет, імовірно, важко помітити, відмічені меншим числом. Це нижчий пріоритет пошуку. Місця, де мала ймовірність і ви не можете відразу помітити його - на думку моментально спадає пес, - відносяться до крайнього варіанту.

Знайти втікача / злочинця

Якщо ви обшукуєте області з найбільшою сумарною імовірністю, вам слід переглянути свої припущення та оновити свою карту ймовірностей.

Використаємо третю метафору. Тепер ви шукаєте втікача. Ваша зграя гончих собак може відчути, де він нещодавно був. Біля в'язниці дорога, що веде до автобусної зупинки. Ймовірність того, що він побіжить по дорозі, щоб встигнути на автобус, є відносно високою, і ваші шанси помітити його, якщо він знаходиться поблизу відкритої дороги (на відміну, скажімо, від лісу) також високі. Зупинка зі скляними стінами, на якій автобуси з’являються періодично, має таку ж високу сукупну ймовірність.

Якщо ви обстежуєте дорогу, а гончаки не вловлюють запаху, тоді ймовірність того, що він знаходиться десь дорогою далі, значно зменшується. Автобусна зупинка також є малоймовірним місцем. З іншого боку, якщо ж собаки щось відчувають, шанси того, що він на автобусній зупинці – зростають.

Якщо все це звучить відносно просто, то лише тому, що так воно і є. Хитрість методу полягає в тому, щоб використовувати розумові здібності при розподілі ймовірностей, враховуючи те, як вони можуть змінюватися по ходу. Серйозного розгляду потребує функція щільності ймовірності того, де може бути розташований об’єкт. Найкращий спосіб сформувати таку функцію — не вгадувати чи користуватися методом тику, а розробити низку гіпотез про те, чому вона зникла, і визначити, де вона, найімовірніше, опиниться в результаті. По всій області пошуку призначте ймовірність кожному квадрату для кожної гіпотези, а потім перемножте ці ймовірності разом.

Байєсівський пошук = розсудливість + математика

У випадку згаданого нами зниклого корабля можна побудувати кілька полів імовірностей, починаючи з гіпотези та дотримуючись її можливих результатів. Імовірно, перша гіпотеза може полягати в тому, що найбільш вірогідне розташування корабля знаходиться поблизу місця, де було встановлено останній радіозв’язок, і ця імовірність буде зменшуватися у разі віддалення від цього місця. Інша гіпотеза може заключатися в тому, що якщо цією територією пройшов ураган, найвірогіднішим місцем затоплення корабля буде найбільш небезпечна і руйнівна частина шторму. Якщо знайдено уламок, який плаває в певній області, то ймовірність того, що залишки корабля лежать десь поблизу, зростає, і разом з цим зменшується імовірність того, що вони знаходиться на великій відстані. Якщо через територію, де були знайдені уламками, протікає сильна течія, то шлях вгору за течією набуває більшої вірогідності, простягаючись на стільки, скільки він протікав після втрати корабля. Області нижче за течією, відповідно, зменшують імовірність.

Байєсівський пошук — це перегонка здорового глузду, формалізованого та ретельнішого за допомогою відносно простих математичних понять. Якщо ви шукаєте втрачений скарб цінністю з мільярд доларів, ви можете сісти за комп’ютер, намалювати численні розподіли ймовірностей і математично їх об’єднати. Якщо ви цілу годину шукаєте свій гаманець, швидке розумове впровадження байєсівського методу пошуку допоможе заощадити ваш час і збільшити ваші шанси на успіх.

Стаття вперше була опублікована англійською мовою під назвою «Bayesian search: A simple rule to find stuff you’ve lost» в журналі «Bigthink» 3 грудня 2022 року.

Переклала Валерія Горцевич