Fldr

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

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

Вот вам обманчиво простое упражнение: придумайте случайный номер телефона. Семь цифр подряд, выбранных так, чтобы каждая из них была одинаково вероятной, и так, чтобы ваш выбор очередной цифры не влиял на выбор следующей. Скорее всего, у вас этого не выйдет. Можете не верить мне на слово исследования, проводимые ещё с 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 или 2⁴ и алгоритм получается эффективным и по памяти, и по времени.


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

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

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

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

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

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