Рандомізація в математиці і в житті
Стаття написана Павлом Чайкою, головним редактором журналу «Пізнавайка». З 2013 року з моменту заснування журналу Павло Чайка присвятив себе популяризації науки в Україні та світі. Основна мета як журналу, так і цієї статті – пояснити складні наукові теми простою та доступною мовою.
Рандомізація (від англійського random — випадковий) означає свідоме внесення випадкового елемента в якийсь процес. Колись люди, що вирішували, як їм бути, підкиданням монети або витягуванням сірників, вважалися несерйозними. Але тепер пора зайнятися їх реабілітацією: строго доведено, що багато важливих завдань вимагають для вирішення кидати жереб. Відвернімося поки від спортивних пристрастей далекого минулого і послухаємо вчених.
Теорія ігор
У 1921 році французький математик Еміль Борель опублікував статтю, яка в той час нікого не зацікавила. Навіть Йоганна фон Неймана, в майбутньому знаменитого, а тоді ще невідомого німецького юнака, який п’ятьма роками пізніше виступив на ту ж тему перед зборами Геттінгенського математичного товариства. А в 1943 році той же фон Нейман, який став на той час з Йоганна Джоном, разом з іншим американським вченим, О. Моргенштерном, опублікував книгу «Теорія ігор та економічна поведінка». Один приклад з неї вартий того, щоб його привести тут. Він відноситься до зіткнення між Шерлоком Холмсом та професором Моріарті.
Нагадаємо, що Шерлоку Холмсу довелося тікати з Лондона від свого невблаганного ворога в Дувр і далі до Франції. Але успіх втечі з самого початку виявився під питанням: від’їжджаючи, на пероні в Лондоні Холмс побачив Моріарті, і йому стало ясно, що неминуча гонитва на спеціальному поїзді. У Холмса були дві можливості: їхати все ж до Дувра або висадитися в Кентенберрі, єдиному проміжному пункті, де поїзд робив зупинку. Ті ж дві можливості були і у його переслідувача. Яке рішення повинні прийняти обидва учасники конфлікту?
Перш за все, потрібна якась кількісна міра того, що відбувається, яку Нейман і Моргенштерн пропонують встановити так. Якщо Холмс висадиться в Кентенберрі і Моріарті, то це буде для Моріарті стовідсоткова вдача, як і випадок, якщо обидва потраплять в Дувр. Якщо Холмс прибуде в Кентенберрі, а Моріарті в Дувр, то це буде нічия (тобто виграш Моріарті складе 0 відсотків), бо і мета Холмса – потрапити до Франції – не буде досягнута. Нарешті, якщо Моріарті висадиться в Кентенберрі, а Холмс доїде до Дувра і сховається, то злочинець буде осоромлений, що автори оцінили в половину вартості життя Холмса (вартості для Моріарті), тобто у вигляді виграшу в 50 відсотків. Приймемо зазначені числа як непорушні і задамося питанням: як повинен поступати мудрий, але, на жаль, не всесильний Холмс, щоб його шанси залишитися в живих були максимальними? І як діяти Моріарті, щоб домогтися успіху?
За Нейманом і Моргенштерном, вирішення задачі таке: обом учасникам конфлікту слід рандомізувати свою поведінку. Моріарті повинен з ймовірністю 3/5 опинитися в Дуврі, а з ймовірністю 2/5 в Кентенберрі. Холмс, навпаки, з ймовірністю 3/5 в Кентенберрі і 2/5 – в Дуврі. Але як практично реалізувати цю рекомендацію?
Зрозуміло, що якщо б гонитва відбувалася 100 разів, то Холмсу треба було висаджуватися в Кентенберрі 60 разів, але так, щоб Моріарті кожен раз був у невіданні щодо його планів. Однак навіть великі сищики володіють тільки одним життям. І як діяти Моріарті, щоб реалізувати свої шанси? Наприклад, ось як. Він може взяти круглу паличку і вистругати на ній п’ять однакових граней (навряд чи злодій виходить з дому без ножа). Три з граней Моріарті повинен позначити хрестиками і кинути паличку на перон. Якщо паличка впаде на позначену межу, то Моріарті повинен їхати до Дувра, а якщо на чисту — до Кентенберрі. У свою чергу Холмс повинен позначити тільки дві грані, а в іншому чинити так само.
Щаслива заміна одного найкращого рішення багатьма, які слід застосовувати з оптимальними частотами,— це, на наш погляд, одне з головних досягнень математики в наш час. І найдивовижніше, якщо одна зі сторін ухилиться від такого образу дій, то вона дасть противнику додаткові шанси на успіх. Це зуміли показати Борель та інші, і тут сильна сторона їх підходу. А слабкі сторони? Вони є? На жаль, так.
Почнемо з того, що вагомі міркування про числа, які Нейман і Моргенштерн взяли рівними 100, 0 і 50, починаються зазвичай з соромливого «припустимо». Дійсно, і в ситуації з розповіддю, і в численних економічних і військових припущеннях теорії ігор дослідники неминуче наштовхувалися на відсутність необхідних кількісних характеристик.
Теорія ігор розвивалася інтенсивно. Вона вміє вже описувати випадки, коли учасників конфлікту не два, а скільки завгодно. Навіть коли їх нескінченно багато. Більш того, учасники конфлікту можуть вступати в коаліції один з одним так, щоб їх інтереси в чомусь збігалися. Але завжди залишається справедливим такий висновок: якщо гра не містить ніякої невизначеності, якщо це гра з повною інформацією, то найкраще рішення у кожній ситуації строго певне, таке, що не потребує рандомізації. І навпаки, якщо в грі є елемент невизначеності (наприклад, яка вноситься противником), то найкраще рішення носить в загальному випадку випадковий, рандомізований характер.
Ми обговорили слідом за Нейманом і Моргенштерном випадок, коли вибір носив дискретний характер — Кентенберрі або Дувр. Але ніщо не заважає тепер включити в розгляд будь-який ярд дороги Лондон — Дувр. Якщо Холмс легко гнув залізну кочергу, то і стрибок з поїзда був йому, ймовірно, по плечах (або по ногах). Але тоді цей шанс довелося б залишити і за підступним Моріарті. В такому випадку ми отримуємо завдання не дискретних, а «диференціальних ігор». Цей термін ввів американський вчений Р. Айзеке, причому основну увагу він приділив саме завданням переслідування. Хто тільки за ким не ганяється в книзі Р. Айзекса «Диференціальні ігри»!
Шофер за пішоходом, катер за кораблем, футбольний захисник за нападником, снаряди за літаками і навіть… чудовисько за принцесою! Цікаве формулювання останнього завдання. Чудовисько шукає принцесу в абсолютно темному приміщенні. Відлов відбувається тоді, коли відстань між ними стане менше заданого. Відома максимальна швидкість чудовиська, а швидкість принцеси може бути будь-якою. Якими повинні бути стратегії бідолахи та її мучителя? Р. Айзеке зізнається, що рішення завдання йому невідоме, але він вважає, що воно повинно бути рандомізованим. Дійсно, для принцеси обидві крайності — стояти на місці або рухатися з величезною швидкістю — явно не обіцяють нічого хорошого. Незважаючи на крижаний душ умови завдання, доля нещасної поки не посунула жодного вченого на її вирішення.
Поступово виявилося, що рандомізація має сенс і тоді, коли, по ідеї, вся інформація є. Класичним прикладом можуть служити шахи. Положення всіх фігур на шахівниці відоме обом противникам. І значить, в кожній позиції можна (в принципі можна!) вказати хід, який призводить до виграшу за мінімальне число ходів (або, скажімо, до програшу за максимальне, якщо позиція гірше). Але те, що можливо в принципі, аж ніяк не завжди здійснено технічно. Абсолютно немислима кількість позицій, які можуть виникнути в шаховій партії, роблять абсурдом спробу розглянути їх всі повністю. І в основу шахових програм часто закладають метод випадкового пошуку – рандомізований метод відшукання оптимального рішення. Пояснимо сутність цього методу на прикладі.
Випадковий пошук
Припустимо, ми хочемо підібрати параметри електродвигуна, які роблять його найбільш економічним при всіх режимах роботи. Залежності, що зв’язують ці параметри зі змінними, що характеризують умови роботи електродвигуна, нам відомі. Однак вони занадто складні, щоб безпосередньо судити, якими вибрати оптимальні параметри. Можна призначити навмання кілька тисяч наборів і вибрати з них найкращий — це так званий сліпий випадковий пошук. І здоровий глузд, і обчислювальна практика кажуть, що така стратегія не веде до успіху. Необхідно ввести елементи самонавчання, щоб комп’ютер в процесі пошуку враховував накопичений досвід. Наприклад, таким шляхом – вести пошук серіями.
Перша серія випробувань можливих параметрів проводиться описаним чином. У другій серії частіше випробовуються ті точки, які здалися найбільш економічними після першої серії випробувань. Швидше за все, це дозволить знайти ще кращий набір параметрів. Тоді на наступній серії випробувань перевіряються точки, що лягають ще кучніше по відношенню до нових оптимальних – ознака того, що отриманій інформації про найкращі значення параметрів можна довіряти. І навпаки, якщо чергова серія випробувань не дала поліпшення, то розкид досліджуваних точок навколо оптимальних значень можна збільшити — невдалий результат серії призводить до зниження нашої довіри до отриманої інформації. І так до тих пір, поки досліджувані точки не стануть зливатися в одну. Це ознака того, що пошук можна зупинити.
А ось інший спосіб самонавчання. Вловлюють тенденцію в зміні параметрів двигуна, при якій підвищується його економічність, а потім з’ясовують, до яких пір ця тенденція зберігається. Діставшись до цього місця, знову виявляють тенденцію і так далі. Але як вибрати сприятливу тенденцію зміни? А все так само, перебираючи можливі випадковим чином.
Існує багато різноманітних ідей самонавчання методом випадкового пошуку, але суть всіх цих методів одна і та ж: вони ставлять за мету подолати брак інформації про поведінку досліджуваного об’єкта. І якщо вважати, що об’єкт намагається приховати від нас свої таємниці і свідомо заважає знайти найкращі параметри, то такий шлях з точки зору теорії ігор є виправданим.
«Але дозвольте,— заперечать тут багато читачів,— адже тут мова йде не про хитромудрого Моріарті, а всього лише про електродвигун, який навряд чи ворожий нам і аж ніяк не намагається перешкодити виявленню своїх оптимальних параметрів». І дійсно, оптимізація електродвигуна — це зовсім не конфліктна ситуація з неповною інформацією. Однак з’ясовується, що електродвигун зручно наділити властивостями мислячого противника, щоб побудувати ефективний (хоча і не оптимальний) алгоритм пошуку оптимальних параметрів. Втім, на цей рахунок ще ведуться суперечки.
Планування експериментів
Один з розділів науки, в яких необхідність рандомізації визнається всіма фахівцями,— планування експериментів. Припустимо, ми шукаємо найкращий сорт пшениці для даного району. Для цього протягом декількох років в різні терміни засівається кілька ділянок. Якщо призначати ділянки під пшеницю, керуючись якимись раціональними правилами, то де гарантія, що ми не «підіграємо» тому сорту, якому симпатизуємо, призначивши йому кращу ділянку? Або не приречемо на провал інший сорт тільки тому, що нам чому-небудь не сподобалася його назва? Ви скажете, що постараєтеся бути об’єктивним,— марні старання! Намагаючись чинити всупереч своїм бажанням, ви впадаєте лише в протилежну крайність, і результати ваших експериментів все одно не будуть об’єктивними.
Тільки рандомізація здатна забезпечити об’єктивність експерименту. На жаль, відомо чимало випадків, коли експериментатор був впевнений у своїй об’єктивності і не помічав, що вносить у підготовку експерименту умови, що спотворюють його результат.
Класичний приклад такої помилки — передбачення результатів виборів президента США в 1936 році, коли ним став Ф. Д. Рузвельт. Експериментатор опитував виборців по телефону і не врахував, що в той час власники телефонів відображали думку лише найбільш забезпечених громадян. Більшість власників телефонів дійсно голосувало проти Рузвельта, в той час як більшість населення — за нього. Правильний експеримент полягав би у випадковому виборі кандидатур для опитування з повного списку виборців.
На перший погляд мотиви, які спонукають до рандомізації в теорії рішень і плануванні експериментів, істотно різняться. Але насправді ці відмінності не настільки вже й значні. Бо витоки рандомізації ті самі – брак інформації. Якби ми були впевнені, що володіємо точними фізичними законами і точно проводимо вимірювання, то для визначення оптимальних параметрів знадобилося б не більше експериментів, ніж цих параметрів. Зокрема, якби виборці діяли як одна людина, то достатньо було б опитати лише одного американця (будь-кого!). Безглуздість такого підходу абсолютно очевидна.
Статистичне моделювання
Ми торкнулися ролі рандомізації в експериментах над деякими фізичними, біологічними або соціальними об’єктами. Але експеримент може проводитися і з математичною моделлю об’єкта. Як поведе себе телефонна станція, якщо розмови абонентів будуть переважно короткими і частими? Як, якщо рідкісними, але довгими? На всі ці питання неважко відповісти за допомогою експериментів над діючою телефонною станцією. А що робити, якщо ця станція тільки проектується? Тут приходить на допомогу статистичне моделювання.
У математичну модель станції посилаються випадкові “дзвінки” і знаходиться її реакція. Статистична модель станції — це всього лише програма для комп’ютера, коштує вона незмірно менше цієї станції — семиповерхового будинку, набитого всіляким обладнанням. І, тим не менш, така модель здатна дати відповідь на питання, що чекає клієнта, якому терміново знадобиться швидка допомога або балаканина приятеля. Чи з’єднається він з бажаним об’єктом за хвилину? А за дві? І ці відповіді можна отримати не за рік експлуатації станції, а всього лише за кілька хвилин: адже комп’ютер дозволяє стискати час. Набір номера, який навіть натренована рука проводить за двадцять секунд, комп’ютер генерує за десятитисячну частку секунди.
І тут теж використання рандомізованої інформації на вході неминуче: немає строгих законів, які регламентували б наше бажання комусь зателефонувати. А спираючись на якісь детерміновані припущення, ми неминуче спотворимо результати дослідження.
Щасливий випадок
Звернення до випадку стало щасливою знахідкою для багатьох дослідників. Епідемія рандомізації охоплює все нові розділи техніки, економіки, соціології. Вчених привертає майже нічим не обмежена свобода творчості, відсутність строгих канонів, що часом ускладнюють уяву в інших підходах. Іноді, завдяки цій свободі, справа доходить до більш-менш повного абсурду. Наприклад, один австралійський дослідник запропонував випадковим чином вводити армування в залізобетонних конструкціях. Мовляв, все одно нам не відомі в точності закони, що зв’язують міцність з армуванням, як невідомий і критерій якості залізобетонної конструкції. Його колега, їдко заперечуючи проти цього підходу, зауважив, що логічним розвитком такого методу повинна бути рандомізація в медицині: оскільки невідомі причини багатьох хвороб, а діагнози далеко не завжди точні, то можна рекомендувати лікарю після огляду хворого випадковим чином брати ліки з полиці.
Але навіть якщо закрити очі на крайнощі, якими багате сучасне життя науки, то слід визнати, що не всі вчені поділяють ідеї рандомізації в теорії рішень. Багато хто заявляє, що краще вже вкладати в математичні моделі самі недосконалі, але зате детерміновані механізми, ніж покладатися на волю сліпого (або нехай навіть тільки підсліпуватого) випадку. Ці самі суперечки велися в двадцяті роки минулого століття щодо статистичних методів у фізиці. Тоді А. Ейнштейн заявляв, що він не вірить, ніби Бог, перш ніж призначити положення електрона, кидає кістки. Тим менше підстав, заявляють сучасні противники рандомізації, займатися цією мало достойною справою людині. Людина повинна намагатися осягнути закони буття, усунути білі плями, а не ховатися від них в шкаралупу рандомізації.
По обличчю цей заклик начебто хороший, а по суті не дуже. Занадто довго вважалося, що науковий підхід – це щось протилежне ненадійній грі випадку. Важко відмовитися від цього уявлення і увірувати, що сам випадок може бути вставлений в оглоблі, використаний в якості тяглової сили науки. Але поки ще Випадок нерідко брикається…
Автор: М. Висотський.