Исследователи на один шаг ближе подошли к добавлению вероятностных процессов к детерминистским машинам



Давняя проблема компьютеров – симуляция броска шулерского кубика

Вот вам обманчиво простое упражнение: придумайте случайный номер телефона. Семь цифр подряд, выбранных так, чтобы каждая из них была одинаково вероятной, и так, чтобы ваш выбор очередной цифры не влиял на выбор следующей. Скорее всего, у вас этого не выйдет. Можете не верить мне на слово – исследования, проводимые ещё с 1950-х годов, показывают, насколько мы неслучайны с математической точки зрения, даже не осознавая этого.

Не расстраивайтесь. Компьютеры тоже не генерируют случайных чисел. Они и не должны – программы и аппаратура компьютеров работают на булевой логике, а не на вероятностях. «Компьютерная культура зиждется на детерминизме, — сказал Викаш Мансинхка, руководящий проектом вероятностных вычислений в Массачусетском технологическом институте, — и это проявляется практически на всех уровнях».

Однако программисты хотят создавать программы, работающие со случайностью – иногда того требуют задачи. За все эти годы были разработаны хитроумные алгоритмы, которые, хотя и не генерируют случайных чисел, предлагают хитрые и эффективные способы использования и манипулирования случайностью. Одну из самых новых попыток предприняла группа Мансинхки в MIT, которая собирается представлять свой алгоритм Fast Loaded Dice Roller [быстрый бросок шулерских кубиков], или FLDR, на международной конференции по ИИ и статистике в августе.

Проще говоря, FLDR использует случайную последовательность для идеальной симуляции броска шулерского кубика (или монеты с нарушенной развесовкой, или краплёных карт). «Он показывает, как превратить идеально случайный бросок монеты в искажённый», — сказал математик Питер Бирхорст из Ново-орлеанского университета. Бирхорст не участвовал в этом исследовании, однако считает предпосылки, лежащие в основе FLDR, «убедительными».

FLDR не даст вам преимуществ при игре в «Монополию» или на столах для игры в крэпс в Лас-Вегасе. Однако его создатели говорят, что он позволяет интегрировать случайные числа в изначально детерминистское ПО или железо. Включение подобных неопределённостей поможет машинам делать предсказания, больше похожие на человеческие, и лучше симулировать явления, основанные на случайности – климат или финансовые рынки.

Случайность – концепция более сложная, чем кажется. У каждой цифры в последовательности случайных цифр, где нет никакой различимой закономерности, вероятность появления одна и та же. К примеру, число π не является случайным, однако считается, что по этому определению его цифры случайные (математики называют это «нормальным»): каждая цифра от 0 до 9 появляется примерно одно и то же количество раз.

И хотя в Google можно найти «генераторы случайных чисел», чистой случайности там не будет. Сегодняшние процессоры, поисковые системы и генераторы паролей используют «псевдослучайный» метод, который «достаточно хорошо» подходит для большинства задач. Числа генерируются по сложным формулам – однако, в теории, если знать формулу, то можно будет предсказать последовательность.

Учёные пытались встроить в машины реальную случайность не менее 80 лет. А до тех пор случайные номера брали у старых и надёжных помощников – кидали кости, вынимали шары с номерами из хорошо перемешанного мешка, или использовали другие механические устройства. В 1927 году один статистик сделал выборку из данных по переписи населения, составив табличку из 40 000 случайных чисел.


Викаш Мансинхка, руководящий проектом вероятностных вычислений в Массачусетском технологическом институте

Ранними источниками случайных чисел были физические машины. Первый генератор случайных чисел изобрели британские статистики Морис Джордж Кендол и Бернард Бабингтон Смит, описавшие его в 1938 году. Машину ставили в тёмную комнату, и там она крутила диск, поделённый на 10 секторов, пронумерованных от 0 до 9. Когда кто-нибудь жал на кнопку через неравные промежутки времени, краткие вспышки неона или искры освещали диск, выхватывая из темноты его, казалось, застывшее изображение, где было видно только одну цифру. Бол��е поздняя машина, «Эрни», использовала шум в неоновых трубках. С 1957 года она выбирала выигрышные номера в британской лотерее.

Позднее в поисках истинно случайных последовательностей специалистам по информатике, по словам Бирхорст, пришлось обращаться к таким природным явлениям, как реликтовое излучение или непредсказуемые квантовые системы. «В природе существуют истинно непредсказуемые случайные процессы, которыми можно воспользоваться, — сказал он. – Электрон, отражающийся влево или вправо, заранее не может сказать, что он сделает».

Однако на одной случайности далеко не уедешь. К концу 1940-х физики начали генерировать случайные числа, укладывающиеся в заданное распределение вероятности. Такие инструменты – теоретические версии ШУ кубиков –точнее работали в реальных ситуациях, типа загруженности дорог или химических реакций. К 1976 году пионеры информатики Дональд Кнут и Эндрю Яо представили алгоритм, способный на основе последовательности случайных чисел выдавать случайные выборки любого массива взвешенных результатов. «Это наиболее эффективный по времени алгоритм из всех, что можно придумать», — сказал Фера Саад, аспирант из лаборатории Мансинхка, руководивший работой над FLDR.

К сожалению, как говорит Саад, алгоритм идёт на компромисс, известный среди специалистов по информатике: многие быстро работающие приложения используют большое количество памяти, а приложения, использующие немного памяти, могут работать очень долго. Алгоритм Кнута и Яо попадает в первую категорию, что делает его элегантным, но слишком требовательным к памяти для практического применения.

Однако прошлой весной Саад придумал хитрый ход. Он понял, что если сумма весов цифр кубика равна какой-нибудь степени 2, алгоритм получается эффективным и по памяти, и по времени. Представим, что для кубика с шестью гранями к вероятностям выкинуть цифры от 1 до 6 добавили веса 1, 2, 3, 4, 5 и 1. То есть, вероятность выкинуть 1 составляет 1/16, а 2 – 2/16. В итоге сумма весов составляет 16 – или 24 — и алгоритм получается эффективным и по памяти, и по времени.


Фера Саад, аспирант из MIT

Но допустим, веса будут равняться 1, 2, 3, 2, 4, 2, что в сумме даст 14. Поскольку 14 – это не степень 2, алгоритму Кнута-Яо потребуется значительно больше памяти. Саад понял, что можно добавить дополнительный вес так, чтобы веса всегда давали в сумме степень 2. В данном случае можно добавить вымышленную грань с весом 2, и тогда веса в сумме дадут 16. Если алгоритм выбирает реальную грань, это значение записывается. Если вымышленную – значение отбрасывается, и алгоритм запускается снова.

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

FLDR делает алгоритм Кнута-Яо эффективным и предоставляет возможность расширить его область применения. Симуляции изменения климата, предсказания урожаев, симуляции поведения частиц, модели финансовых рынков и обнаружение подземных ядерных взрывов – всё это зависит от случайных чисел, распределённых со взвешенной вероятностью. Также случайные числа лежат в основе криптографических схем, защищающих данные, передаваемые по интернету.

Мансинхка говорит, что FLDR может помочь исследователям находить способы интегрировать вероятность в компьютерные процессоры – этим занимается его лаборатория в MIT. Алгоритм может помочь улучшить программные библиотеки и новую архитектуру процессоров, которые смогут генерировать случайные числа и эффективно их использовать. Это значительно изменило бы ситуацию по сравнению с теми детерминистскими булевыми машинами, к которым мы привыкли.

«У нас, возможно, есть хороший шанс интегрировать случайность в строительные блоки программ и железа», — сказал он.

См. также: