MITの研究者、高速でメモリ効率が高い乱数生成アルゴリズム「FLDR」を開発：重み付け乱数を効率良く生成

MITの研究者チームは、少なくとも特定のタスクについては、速度と精度、低いメモリ要件を最適な組み合わせで満たしながら乱数を生成するアルゴリズム「Fast Loaded Dice Roller」（FLDR）を開発した。

[＠IT]

　マサチューセッツ工科大学（MIT）の研究者チームは、2020年5月28日（米国時間）、乱数を生成する優れたアルゴリズム「Fast Loaded Dice Roller」（FLDR）を開発したと発表した。

　乱数を生成するときに求められる3種類の要件、すなわち速度と精度、メモリをあまり使わないことについて、現時点における最適な組み合わせで実行できるという。乱数生成はさまざまなシミュレーションで多用されているため、効率の良い手法に対するニーズは高い。

　FLDRを開発したのは、MITの大学院生フェラス・サード氏、リサーチサイエンティストのキャメロン・フリーア氏、マーティン・リナード教授、プリンシパルリサーチサイエンティストのビカシュ・マンシンカ氏。「AISTATS 2020 : The 23rd International Conference on Artificial Intelligence and Statistics」（AISTATS第23回人工知能と統計学に関する国際会議、2020年6月3〜5日に開催）で、FLDRに関するプレゼンテーションを行う予定だ。

　簡単に言えば、FLDRは、さいころの回転をシミュレートして整数の乱数を生成するコンピュータプログラムだ。さいころは任意の数の面を持ち、事前に重み付けすることで、特定の面が他の面よりも高い確率で出るようになる。

　重み付けされたさいころ（原文では「loaded dice」とあり、「いかさまさいころ」という意味がある）は、乱数を生成できる。どの面が出るか前もって予想できないためだ。その一方でランダム性を、あらかじめ設定した確率分布を満たすように制約できる。例えば、重み付けされたさいころを使って、野球の試合結果をシミュレートできるかもしれない。

　FLDRでは、さいころは“完全に”重み付けされている。これは、指定された通りの確率を実現できることを意味する。4面のさいころを例に説明すると、「1」「2」「3」「4」の各目を25％ずつではなく、例えば23％、34％、17％、26％の確率で出るように設定できる。

　多数の面を持ち、重み付けされたさいころの回転をシミュレートするために、MITの研究チームはまず、ランダム性を生み出す簡単な源を利用しなければならなかった。それは、0または1をそれぞれ50％の確率で生成する、コイントスのコンピュータ化されたバージョンだった。乱数生成方法の効率は、各さいころの回転をシミュレートするために、こうしたランダム源を利用する必要がある回数（“コイントス”の回数）に依存する。こうした効率が、乱数生成方法の重要な設計基準となる。

既に知られている効率の良い手法には問題があった

　1976年にコンピュータサイエンティストのドナルド・クヌース氏とアンドルー・ヤオ氏が発表した、重み付けされたさいころの回転をシミュレートする画期的なアルゴリズムは、理論上最大の効率を備えている。

　これについてサード氏は、「彼らのアルゴリズムは時間に関しては効率が最大化されていたが、空間に関しては効率が悪かった。必要とされるメモリの量がさいころの面の数や他の要因に応じて、指数関数的に増加するからだ。彼らのアルゴリズムは理論的に重要だが、特別な場合を除けば、実用的ではない」と指摘する。

　FLDRは、高い利便性の提供を目指して設計された。「FLDRは、クヌース氏とヤオ氏のアルゴリズムに近い時間効率を発揮する一方、メモリ効率は格段に優れている」（サード氏）。FLDRは両氏のアルゴリズムと比べて、使用するメモリ容量は最大1万分の1にすぎず、演算当たりの所要時間は1.5倍にとどまる。

　FLDRの現在の主な競合相手は、数十年にわたってこの分野の主流だったエイリアス法だ。フリーア氏によると、理論的な分析の結果、FLDRには、エイリアス法に対する明確な優位点がある。それは、ランダムソースをより効率的に利用することだ。さらに、特定のケースでは、FLDRの方がエイリアス法よりも、重み付けされたさいころの回転をより高速に生成する。

　FLDRはまだ新しく、広く使われていない。だが、FLDRを開発した研究者は、ソフトウェアとハードウェアエンジニアリングによって、FLDRの効果を高める方法を考えている。さらに、一般的な乱数生成ニーズへの対応以外にも、FLDRの具体的な用途を想定している。マンシンカ氏は、FLDRは、いわゆるモンテカルロシミュレーションやモンテカルロ推論の効率を高める点で、最も役に立つだろうと述べている。