研究者は、決定論的マシンに確率論的プロセスを追加することに一歩近づいています
長期
的なコンピューティングの問題-ダイスロールのシミュレーションこれは一見単純な演習です。ランダムな電話番号を考え出します。それぞれが同じ確率であり、次の番号の選択が次の番号の選択に影響を与えないように選択された、連続した7つの番号。ほとんどの場合、これは機能しません。私の言葉を信じることはできません。1950年代以降に行われた調査では、数学的な観点から、気づかないうちにランダムではないことが示されています。
動揺しないでください。コンピュータもランダムな数字を生成しません。コンピュータのプログラムとハードウェアは、確率ではなくブール論理で実行されるべきではありません。 「コンピューター文化は決定論に基づいています」とVikashMansinhka氏は述べています。MITで確率的コンピューティングプロジェクトを実行している人-そしてそれはほぼすべてのレベルで現れます。」
ただし、プログラマーはランダムに実行されるプログラムを作成したいと考えています。タスクで必要になる場合もあります。何年にもわたって、ランダムな数値を生成しない一方で、ランダム性を使用および操作するための巧妙で効率的な方法を提供する独創的なアルゴリズムが開発されてきました。最近の試みの1つは、MITのMansinkheeのグループによって行われ、8月の国際AIおよび統計会議でFast Loaded Dice Roller（FLDR）を発表しようとしています。
簡単に言うと、FLDRはランダムなシーケンスを使用して、不正行為を行うダイ（または、重みの悪いコインやマークされたカード）を完全にシミュレートします。 「彼は完全にランダムなコイントスを歪んだものに変える方法を示しています」と数学者は言いましたニューオーリンズ大学のピーター・バーホルスト。 Birhorstはこの研究には関与していませんが、FLDRの基礎となる前提は「説得力がある」と考えています。
FLDRは、モノポリーをプレイしたり、ラスベガスのがらくたテーブルでプレイしたりするときに、アドバンテージを与えません。ただし、その作成者は、ランダムな数値をネイティブに決定論的なソフトウェアまたはハードウェアに統合できると述べています。このような不確実性を組み込むことで、マシンは予測をより人間らしいものにし、偶然に基づいてイベントをより適切にシミュレートするのに役立ちます-気候または金融市場。
ランダム性は、思ったよりも複雑な概念です。識別可能なパターンがないランダムな数字のシーケンスの各数字は、発生の確率が同じです。たとえば、数πはランダムではありませんが、この定義により、その数はランダムであると考えられています（数学者はそれを「通常」と呼びます）。0から9までの各桁はほぼ同じ回数出現します。
また、Googleで「ランダム数ジェネレーター」を見つけることはできますが、純粋なチャンスはありません。今日のプロセッサ、検索エンジン、およびパスワードジェネレータは、ほとんどのタスクに「十分」な「疑似ランダム」方式を使用しています。数値は複雑な式から生成されますが、理論的には、式を知っているとシーケンスを予測できます。
科学者たちは、少なくとも80年間、真のランダム性をマシンに組み込むことを試みてきました。それまでは、古くて信頼できるアシスタントからランダムな番号が取られていました。彼らはダイスを投げたり、よく混ぜられたバッグから番号の付いたボールを取り出したり、他の機械装置を使用したりしていました。 1927年、統計学者が国勢調査データをサンプリングし、40,000のランダムな数値の表を作成しました。
MITの確率的コンピューティングプロジェクトマネージャー、Vikash Mansinkhka
ランダム番号の最も初期のソースは物理的なマシンでした。最初のランダム数ジェネレーターは、1938年にそれを説明した英国の統計学者Maurice GeorgeKendallとBernardBabingtonSmithによって発明されました。車は暗い部屋に置かれ、そこで0から9までの番号が付けられた10のセクターに分割されたディスクを回転させました。誰かが不規則な間隔でボタンを押すと、ネオンまたは火花の短い閃光がディスクを照らし、暗闇からそれを奪ったように見えました。 1つの番号しか表示されていないフリーズされた画像。後のマシン、アーニーはネオン管でノイズを使用しました。 1957年以来、彼女は英国の宝くじで当選番号を選んでいます。
その後、真にランダムなシーケンスを求めて、Birhorstによると、コンピューター科学者は、遺物の放射や予測不可能な量子システムなどの自然現象に目を向けなければなりませんでした。 「実際には、悪用される可能性のある、本当に予測不可能なランダムプロセスがあります」と彼は言いました。 「左または右に反射する電子は、それが何をするかを前もって知ることはできません。」
しかし、チャンスだけでは遠くまで行くことはできません。 1940年代後半までに、物理学者は与えられた確率分布に適合するランダムな数を生成し始めました。このようなツール（NOSキューブの理論バージョン）は、交通渋滞や化学反応などの実際の状況でより正確に機能しました。 1976年までに、コンピューターサイエンスのパイオニアであるDonaldKnuthとAndrewYaoランダム番号のシーケンスに基づいて、重み付けされた結果の任意の配列のランダムサンプルを生成できるアルゴリズムを提示しました。 「これはあなたが考えることができる最も時間効率の良いアルゴリズムです」とFLDRを率いたMansinkhkeの研究室の大学院生であるFeraSaadは言いました。
残念ながら、Saad氏によると、このアルゴリズムはコンピューター科学者の間で妥協点を知らせます。高速で実行されるアプリケーションの多くは大量のメモリを使用し、メモリをほとんど使用しないアプリケーションは非常に長く実行される可能性があります。 KnuthとYaoのアルゴリズムは最初のカテゴリに分類されます。これにより、エレガントになりますが、実際に使用するにはメモリを大量に消費します。
しかし、Saadは昨年の春に巧妙な動きを思いついた。彼は、立方体の桁の重みの合計が2の累乗に等しい場合、アルゴリズムはメモリと時間の両方で効率的であることが判明したことに気付きました。 6面キューブの場合、1から6までの数値をロールアウトする確率に重み1、2、3、4、5、および1が追加されると想像してください。つまり、1をロールアウトする確率は1 / 16、2は2/16です。その結果、重みの合計は16（または2 4）になり、アルゴリズムはメモリと時間の両方で効率的であることがわかります。
MITの博士課程の学生であるFeraSaad
ただし、重みが1、2、3、2、4、2で、合計が14になるとします。14は2の累乗ではないため、Knut-Yaoアルゴリズムはかなり多くのメモリを必要とします。 Saadは、重みが常に2の累乗になるように、余分な重みを追加できることに気付きました。この場合、重みが2の架空の顔を追加し、次に重みを合計16にすることができます。アルゴリズムが実際の顔を選択した場合、この値が記録されます。架空の場合、値は破棄され、アルゴリズムが再開されます。
これがFLDRの有効性の鍵であり、強力なシミュレーションツールになっています。余分なスローのための余分なメモリの量は、アルゴリズムの元のバージョンで必要とされる大量と比較してごくわずかです。
FLDRは、Knuth-Yaoアルゴリズムを効率的にし、その範囲を拡大する機会を提供します。気候変動シミュレーション、作物予測、粒子シミュレーション、金融市場モデル、地下核爆発はすべて、加重確率で分布するランダム数に依存しています。また、ランダム番号は、インターネットを介して送信されるデータを保護する暗号化スキームの中心です。
Mansinkhkaは、FLDRは、研究者が確率をコンピュータープロセッサに統合する方法を見つけるのに役立つと述べています。MITの彼の研究室はこれを行っています。このアルゴリズムは、ランダムな数値を生成して効率的に使用できるソフトウェアライブラリと新しいプロセッサアーキテクチャの改善に役立ちます。これは、私たちが慣れている決定論的なブールマシンからの重要な変更になります。
「ソフトウェアとハードウェアの構成要素にランダム性を統合する可能性が高いかもしれません」と彼は言いました。
参照：