確率的計算

確率的計算は、連続した値をランダム ビットのストリームで表現する一連の手法です。複雑な計算は、ストリームに対する単純なビット単位の演算によって実行できます。確率的計算は、ランダム化アルゴリズムの研究とは異なります。

が与えられていて、 を計算したいとします。確率的計算では、算術ではなく確率を使用してこの操作を実行します。 ${\displaystyle p,q\in [0,1]}$${\displaystyle p\times q}$

具体的には、確率数（ベルヌーイ過程）と呼ばれる 2 つのランダムで独立したビット ストリームがあり、最初のストリームで 1 になる確率が、2 番目のストリームで 1 になる確率が であるとします。2つのストリームの 論理積を取ることができます。${\displaystyle p}$${\displaystyle q}$

出力ストリーム内の 1 の確率は です。十分な出力ビットを観察し、1 の頻度を測定することで、任意の精度で推定することができます。 ${\displaystyle pq}$${\displaystyle pq}$

上記の演算は、かなり複雑な計算（との乗算）を、ランダム ビットに対する一連の非常に単純な演算（ の評価）に変換します。 別の観点から見ると、AND ゲートの真理値表を想定しています。 従来の解釈では、入力 A と B が真の場合にのみ出力が真になります。 ただし、表を垂直に解釈すると、(0011) AND (0101) は (0001)、つまり 1/2 x 1/2 = 1/4 となり、これはまさに算術乗算です。 情報は確率分布で表されているため、確率乗算は文字通り AND 演算です。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle a_{i}\land b_{i}}$

より一般的に言えば、確率的計算は、数値をランダムビットのストリームとして表現し、頻度を計算することによって数値を再構築します。計算はストリームに対して実行され、ストリーム表現に対する複雑な操作を単純な操作に変換します。(再構築の方法のため、これらの操作を実行するデバイスは、確率的平均化プロセッサと呼ばれることがあります。) 現代の用語では、確率的計算は、計算を確率的に解釈し、ギブスサンプラーで評価するものと見なすことができます。また、ハイブリッドアナログ/デジタルコンピューター と解釈することもできます。${\displaystyle p}$${\displaystyle q}$

確率的計算は、1953年にジョン・フォン・ノイマンの先駆的な論文で初めて紹介されました。^[1]しかし、理論が完全に発展したのは1960年代の計算技術の進歩によるものでした。^{[2] [3]主に米国[4]} と英国^[5] での一連の同時並行的な取り組みを通じてでした。 1960年代後半には、確率的計算を実行するための専用ハードウェアの設計に注目が集まりました。これらのマシンのホスト^[6]は 1969年から1974年の間に構築されました。 この記事には RASCEL ^{[7]の写真が掲載されています。}

1960年代と1970年代に強い関心が寄せられたにもかかわらず、確率的計算は最終的に、以下に概説する理由により、より伝統的なデジタルロジックと競争することができませんでした。確率的計算に関する最初の（そして最後の）国際シンポジウム^[8]は 1978年に開催されましたが、その後数年間でこの分野での活発な研究は減少しました。

確率的計算は一般的な計算方法としては衰退しましたが、いくつかのアプリケーションでは有望であることが示されています。研究は伝統的に機械学習と制御の特定のタスクに焦点を当ててきました。^{[9] [10]} 最近では、確率的計算をエラー訂正コードのデコードに適用する確率的デコードに関心が向けられています。^{[11]さらに最近では、確率的回路は}エッジ検出^[12]や画像しきい値処理などの画像処理タスクで効果的に使用されています。^[13]確率的回路の最近の進歩は、エッジコンピューティングでの人工知能 (AI) ハードウェアアクセラレーションにおける有望な速度とエネルギー効率の利点も示しています。

確率的コンピューティングは歴史的には失敗でしたが、特定の問題を解決する上では依然として意味があるかもしれません。それがいつ意味を持ち続けるかを理解するには、確率的コンピューティングと従来のデジタル コンピューティングの方法を比較すると役立ちます。

ビット精度の 2 つの数値を乗算するとします。一般的な長整数乗算法を使用して、演算を実行する必要があります 。確率的計算では、任意の数のビットを AND で結合でき、期待値は常に正確になります。(ただし、サンプル数が少ないと、分散によって実際の結果が非常に不正確になります)。 ${\displaystyle n}$${\displaystyle n^{2}}$

さらに、デジタル乗算器の基本的な演算は 全加算器であるのに対し、確率的コンピュータではAND ゲートのみが必要である。さらに、デジタル乗算器は単純に入力線を必要とするが、確率的乗算器では 2 つの入力線のみが必要である^[要出典]。(ただし、デジタル乗算器が出力をシリアル化する場合、必要な入力線も 2 つだけである。) ${\displaystyle 2n}$

さらに、確率的コンピューティングはノイズに対して堅牢であり、ストリーム内のいくつかのビットが反転したとしても、それらのエラーはソリューションに大きな影響を与えません。

さらに、確率的計算要素は入力の到着時間のずれを許容することができる。入力が時間的にずれていても回路は正常に動作する。その結果、確率的システムは、グローバルクロックと高価なクロック分配ネットワークを使用する代わりに、安価なローカル生成クロックで動作するように設計することができる。^[14]

最後に、確率的計算は、ビットストリームを拡張するにつれて精度が増す解の推定値を提供します。特に、大まかな推定値が非常に迅速に提供されます。この特性は通常、漸進的精度と呼ばれ、確率的数（ビットストリーム）の精度は計算が進むにつれて増加することを示しています。 ^[15] これは、数の最上位ビットが最下位ビットよりも先に到達するかのようであり、最上位ビットが通常最後に到着する従来の算術回路とは異なります。一部の反復システムでは、漸進的精度を通じて取得された部分解は、従来の計算方法よりも高速なフィードバックを提供できるため、収束が速くなります。

確率的計算は、その性質上、ランダムです。ランダムなビット ストリームを調べて、基になる値を再構築しようとする場合、有効な精度はサンプルの分散によって測定できます。上記の例では、デジタル乗算器はビットの精度で数値を計算するため、精度は です。ランダム ビット ストリームを使用して数値を推定し、解の推定値の標準偏差を少なくとも にしたい場合は、サンプルが必要になります。これは、作業が指数関数的に増加することを意味します。ただし、特定のアプリケーションでは、確率的計算の漸進的精度特性を利用して、この指数関数的な損失を補うことができます。 ${\displaystyle 2n}$${\displaystyle 2^{-2n}}$${\displaystyle 2^{-2n}}$${\displaystyle O(2^{4n})}$

第二に、確率的計算には、ランダムなバイアスビットストリームを生成する方法が必要です。実際には、これらのストリームは 疑似乱数ジェネレータで生成されます。残念ながら、（疑似）ランダムビットの生成には、（たとえば全加算器の費用と比較して）かなりのコストがかかります。そのため、確率的計算のゲートレベルの利点は通常失われます。

第三に、確率的計算の分析では、ビットストリームが独立している（相関がない）と仮定しています。この仮定が成り立たない場合、確率的計算は大幅に失敗する可能性があります。たとえば、のビットストリームを それ自体で乗算して計算しようとすると、プロセスは失敗します。 であるため、確率的計算では が生成されますが、これは一般には当てはまりません（0 または 1 でない限り）。フィードバックのあるシステムでは、無相関の問題がより複雑な形で現れることがあります。確率的プロセッサのシステムは 、異なるコンポーネント間のフィードバックによってデッドロック状態になる可能性があるラッチングになりがちです。 ^[16] ラッチングを修正するには、システムの無相関化に多大な労力を費やす必要があります。 ${\displaystyle p^{2}}$${\displaystyle p}$${\displaystyle a_{i}\land a_{i}=a_{i}}$${\displaystyle p\times p=p}$${\displaystyle p=}$

4 番目に、一部のデジタル関数には非常に単純な確率的対応物 (乗算と AND ゲート間の変換など) がありますが、多くの関数にはそのような関数はありません。これらの関数を確率的に表現しようとすると、さまざまな問題が発生する可能性があります。たとえば、確率的デコードには関数 の計算が必要です。この関数を計算できる単一ビット操作はありません。通常の解決策では相関出力ビットを生成しますが、これは上で説明したように、さまざまな問題を引き起こす可能性があります。 ${\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}$

その他の関数 (平均化演算子など) では、ストリームのデシメーションまたはインフレーションのいずれかが必要です。精度とメモリのトレードオフは難しい場合があります。 ${\displaystyle f(p,q)\rightarrow (p+q)/2}$

確率的計算は、一般的な計算方法として考えると多くの欠点がありますが、その長所を際立たせる特定のアプリケーションもあります。注目すべきケースの 1 つは、特定のエラー訂正コードのデコードです。

確率的計算とは関係のない開発では、ビリーフプロパゲーションアルゴリズムを使用してLDPC コードをデコードする非常に効果的な方法が開発されました。このコンテキストでのビリーフ プロパゲーションでは、2 つの基本的な操作 (基本的には確率的 XOR 操作と平均化操作) を使用して、特定のパラメーターを繰り返し再推定します。

2003年、研究者たちは、これら2つの操作を確率的計算で非常に簡単にモデル化できることに気付きました。^{[17]さらに、ビリーフプロパゲーションアルゴリズムは反復的であるため、確率的計算は部分的なソリューションを提供し、より速い収束につながる可能性があります。確率的デコーダのハードウェア実装は}FPGA 上に構築されています。 ^[18] これらの方法の支持者は、確率的デコードのパフォーマンスはデジタルの代替手段と競争力があると主張しています。

SCの決定論的手法は、SC回路で完全に正確な計算を実行するために開発されました。^[19]これらの手法の基本的な原理は、1つのビットストリームのすべてのビットが他のビットストリームのすべてのビットと正確に1回相互作用することです。これらの手法で完全に正確な結果を生成するには、入力ビットストリームの長さの積に対して操作を実行する必要があります。決定論的手法は、単項ビットストリーム、^{[20] [21]}疑似ランダムビットストリーム、^[22]および低差異ビットストリームに基づいて開発されています。^[23]

基本的な確率的計算パラダイムには、さまざまなバリエーションがあります。詳細については、Mars と Poppelbaum の参考文献を参照してください。

バンドル処理では、ストリームの代わりに固定数のビットを送信します。このアプローチの利点の 1 つは、精度が向上することです。理由を確認するために、ビットを送信するとします 。通常の確率的計算では、推定値の分散のため、ほぼ異なる値の精度を表すことができます。バンドル処理では、 の精度を表すことができます。ただし、バンドル処理では、通常の確率的処理と同じエラーに対する堅牢性が保持されます。 ${\displaystyle s}$${\displaystyle O(1/{\sqrt {s}})}$${\displaystyle 1/s}$

エルゴード処理では、バンドルのストリームを送信し、通常の確率的処理とバンドル処理の利点を活用します。

バースト処理は、数値を上位の基数の増加ストリームでエンコードします。たとえば、4.3を10進数の10桁でエンコードすると、

4444444555

前のストリームの平均値は 4.3 であるためです。この表現にはさまざまな利点があります。数字は昇順に表示されるためランダム化がなく、PRNG の問題を回避できますが、確率的計算の利点の多く (ソリューションの部分的な推定など) が保持されます。さらに、バンドル処理とエルゴード処理の線形精度も保持されます。

• 従来とは異なるコンピューティング

• Gaines, Brian R. (1967)。「確率的コンピュータによる識別技術」(PDF)。「自動制御システムにおける識別の問題」に関する IFAC シンポジウム議事録、第 6 章 特殊識別装置、プラハ、1967 年 6 月 12 ～ 19 日。2013年 11 月 11 日閲覧。
• Alaghi, Armin; Hayes, John P. (2013). 「確率的コンピューティングの調査」(PDF) . ACM Transactions on Embedded Computing Systems . 12 (2s): 1–19. CiteSeerX  10.1.1.296.4448 . doi :10.1145/2465787.2465794. S2CID  4689958 . 2013-11-11に取得。