重み付きランダム選択で置換と非置換をいつ使用するか?

重み付きランダム選択: 置換 vs. 非置換

重み付きランダム選択は、さまざまなアプリケーションで使用される基本的な手法です。これには、指定された重みによって決定される確率分布を使用して、指定されたリストから要素をサンプリングすることが含まれます。置換を伴う要素を選択する場合、各項目を複数回選択できるため、より重みの高い項目が選択される可能性が高くなります。対照的に、置換なしの選択では、一度選択された項目の選択が制限されます。

重み付けされたランダム選択、特に置換を伴う効率的なアルゴリズムを見つけるのは困難な場合があります。修正されたリザーバー アルゴリズムを含む既存の方法は、小さなリスト サイズからの有意な分数の選択には適していないことがわかります。

効率的なアプローチ: Alias メソッド

このシナリオで優れた 1 つのアプローチエイリアスメソッドです。この手法では、それぞれが加重リストの一部を表す構造化されたビンのセットを作成します。ビット操作を利用することで、バイナリ検索を回避してビンに効率的にインデックスを付けることができます。各ビンには元のリストの 2 つの要素が含まれており、分布を効率的に表現できます。

たとえば、均等に重み付けされた 5 つの選択肢のリストを考えてみましょう: (a:1、b:1、c:1、d: 1、e:1)。エイリアス メソッドは、それぞれの確率質量が 0.125 の 8 つのビンのセットを作成します。

1. 正規化: 合計が 1.0 になるように重みを調整します。この場合、(a:0.2 b:0.2 c:0.2 d:0.2 e:0.2).
2. Partition: 分割確率 (0.125) よりも低い重みでビンを割り当てます。最も軽い重量で。ここでは、(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8).
3. Filling: パーティション内の残りのスペースを最高の値で埋めます。重量変数。たとえば、(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8).

ランタイム選択:

実行時に乱数を生成し、ビット演算を使用して確率分布に対応するビンを効率的に決定します。ビンが分割されている場合、乱数の小数部分を使用してビン内の 2 つの要素の間で選択します。

要約すると、エイリアス法は、置換による重み付きランダム選択の効率的な手法を提供します。ビット操作を利用してビンのインデックスを高速化し、重みを管理可能なビンに慎重に分割することで正確な確率分布を実現します。

以上が重み付きランダム選択で置換と非置換をいつ使用するか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。