| 0 |
|
На этой неделе исследователи из Массачусетского технологического института (MIT) представят на 23-й международной конференции по искусственному интеллекту и статистике разработанный ими компьютерный алгоритм Fast Loaded Dice Roller (FLDR), который, по крайней мере для некоторых задач, может генерировать случайные числа с наилучшим на сегодняшний день сочетанием скорости, точности и занимаемой памяти.
Для получения случайных целых чисел FLDR имитирует бросок костей. Кости могут иметь любое количество сторон, которые могут быть «утяжелены» так, чтобы сделать выпадание некоторых сторон более вероятным, чем других. При этом FDLR позволяет задавать точную вероятность получения каждого результата при большом количестве бросков.
В далёком 1976 году Дональд Кнут (Donald Knuth) и Эндрю Яо (Andrew Yao) представили идеальный алгоритм симуляции броска кубиков с утяжелёнными гранями, обеспечивающий наивысшую теоретически возможную эффективность. Однако, объем требуемой им памяти растет в геометрической прогрессии, в зависимости от количества сторон на кости и других факторов. Это делает самый быстрый в мире метод непрактичным для большинства сценариев использования.
FLDR отстаёт в быстродействии от алгоритма Кнута-Яо не более чем в полтора раза, но при этом может использовать в 10 тысяч раз меньше памяти. Его непосредственным конкурентом является доминирующий в данной области уже пару десятилетий алгоритм Alias, от которого FLDR выгодно отличается более эффективным использованием исходного двоичного источника случайных чисел. Кроме того, в ряде случаях FLDR быстрее, чем Alias моделирует выбрасывание костей.
Помимо общей, постоянно существующей потребности в случайных числах, FLDR способен улучшить эффективность так называемых методов Монте-Карло. Подобно тому, как FLDR использует двоичный рандомный генератор для имитации более сложного броска утяжелённых, многогранных костей, симуляции методом Монте-Карло используют бросок костей для порождения более сложных комбинаций случайных чисел.
К примеру, эксперты ООН используют метод Монте-Карло для выполнения рандомных симуляций, которыми пытаются воспроизвести реальные сейсмические данные. Таким образом можно установить координаты эпицентров землетрясений или испытаний ядерного оружия, однако это требует в сотни или тысячи раз больше случайных чисел, чем простая симуляция.
«Это одно большое узкое место, где FLDR действительно может помочь. Алгоритмы моделирования и логического вывода Монте-Карло также играют центральную роль в вероятностном программировании, новой области ИИ с обширными перспективами применения», — говорит ведущий научный сотрудник MIT, Викаш Мансингка (Vikash Mansinghka).
Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365
| 0 |
|
