有放回和无放回的加权随机选择
- 2025-01-21 09:01:00
- admin 原创
- 71
问题描述：
最近我需要对列表中的元素进行加权随机选择，既有放回法也有放回法。虽然有一些众所周知的优秀非加权选择算法，还有一些无放回加权选择算法（例如对存储算法的修改），但我找不到任何有放回加权选择的好算法。我还想避免使用存储方法，因为我选择的只是列表中的很大一部分，这些部分足够小，可以保存在内存中。
有人对这种情况下的最佳方法有什么建议吗？我有自己的解决方案，但我希望找到更高效、更简单或两者兼而有之的方法。
解决方案 1：
用不变列表中的替换样本制作多个样本的最快方法之一是别名方法。核心直觉是，我们可以为加权列表创建一组大小相等的容器，这些容器可以通过位运算非常有效地索引，从而避免二分搜索。事实证明，如果操作正确，我们只需要在每个容器中存储原始列表中的两个项目，因此可以用一个百分比来表示分割。
让我们以五个同等权重的选择为例，(a:1, b:1, c:1, d:1, e:1)
要创建别名查找：
将权重标准化，使得它们的总和为
1.0。(a:0.2 b:0.2 c:0.2 d:0.2 e:0.2)这是选择每个权重的概率。找到大于或等于变量数的最小 2 的幂，并创建此数量的分区。
|p|每个分区代表一个概率质量1/|p|。在这种情况下，我们创建8分区，每个分区都可以包含0.125。取剩余重量最少的变量，并将其质量尽可能多地放在空分区中。在这个例子中，我们看到填充
a了第一个分区。(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8)`(a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)`如果分区未填满，则取权重最大的变量，并用该变量填充分区。
重复步骤 3 和 4，直到原始分区中的任何权重都不需要分配给列表。
例如，如果我们再进行一次 3 和 4 的迭代，我们会看到
(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)剩下(a:0, b:0.15 c:0.2 d:0.2 e:0.2)待分配
在运行时：
获取
U(0,1)随机数，比如二进制0.001100000对其进行位移
lg2(p)，找到索引分区。因此，我们将其移动3，得到001.1，或位置 1，从而得到分区 2。如果分区被拆分，则使用移位后的随机数的小数部分来决定拆分。在本例中，值为
0.5，且0.5 < 0.6，因此返回a。
这里有一些代码和另一种解释，但不幸的是它没有使用位移技术，我也没有真正验证过它。
解决方案 2：
这里没有提到的一种简单方法是Efraimidis 和 Spirakis提出的一种方法。在 Python 中，您可以从 n >= m 个加权项目中选择 m 个项目，这些项目的权重严格为正，存储在权重中，并返回选定的索引，方法是：
import heapq
import math
import random
def WeightedSelectionWithoutReplacement(weights, m):
elt = [(math.log(random.random()) / weights[i], i) for i in range(len(weights))]
return [x[1] for x in heapq.nlargest(m, elt)]
这与 Nick Johnson 提出的第一种方法在结构上非常相似。不幸的是，该方法在选择元素时存在偏差（请参阅方法评论）。Efraimidis 和 Spirakis 在链接的论文中证明了他们的方法相当于无放回随机抽样。
解决方案 3：
以下是我针对无替换加权选择得出的结论：
def WeightedSelectionWithoutReplacement(l, n):
"""Selects without replacement n random elements from a list of (weight, item) tuples."""
l = sorted((random.random() * x[0], x[1]) for x in l)
return l[-n:]
列表中要选择的项目数为 O(m log m)。我相当肯定这会正确地加权项目，尽管我还没有以任何正式的方式验证过。
以下是我针对替换加权选择得出的结论：
def WeightedSelectionWithReplacement(l, n):
"""Selects with replacement n random elements from a list of (weight, item) tuples."""
cuml = []
total_weight = 0.0
for weight, item in l:
total_weight += weight
cuml.append((total_weight, item))
return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]
这是 O(m + n log m)，其中 m 是输入列表中的项目数，n 是要选择的项目数。
解决方案 4：
我建议您先查看 Donald Knuth 的《半数值算法》第 3.4.2 节。
如果您的数组很大，John Dagpunar 的《随机变量生成原理》第 3 章中有更高效的算法。如果您的数组不是很大，或者您不关心尽可能提高效率，那么 Knuth 中更简单的算法可能就足够了。
解决方案 5：
在首先在 O(N) 时间内创建一个额外的 O(N) 大小的数据结构之后，可以在 O(1) 时间内进行带替换的加权随机选择。该算法基于Walker 和 Vose 开发的Alias 方法，此处对此进行了详细描述。
基本思想是，直方图中的每个 bin 都由均匀 RNG 以 1/N 的概率选择。因此，我们将逐步介绍它，对于任何可能收到多余命中的填充不足的 bin，将多余部分分配给填充过多的 bin。对于每个 bin，我们存储属于它的命中百分比，以及多余部分的配对 bin。此版本会就地跟踪小 bin 和大 bin，无需额外的堆栈。它使用配对的索引（存储在中bucket[1]）作为它们已被处理的指示。
这是一个最小的 Python 实现，基于此处的 C 实现
def prep(weights):
data_sz = len(weights)
factor = data_sz/float(sum(weights))
data = [[w*factor, i] for i,w in enumerate(weights)]
big=0
while big<data_sz and data[big][0]<=1.0: big+=1
for small,bucket in enumerate(data):
if bucket[1] is not small: continue
excess = 1.0 - bucket[0]
while excess > 0:
if big==data_sz: break
bucket[1] = big
bucket = data[big]
bucket[0] -= excess
excess = 1.0 - bucket[0]
if (excess >= 0):
big+=1
while big<data_sz and data[big][0]<=1: big+=1
return data
def sample(data):
r=random.random()*len(data)
idx = int(r)
return data[idx][1] if r-idx > data[idx][0] else idx
使用示例：
TRIALS=1000
weights = [20,1.5,9.8,10,15,10,15.5,10,8,.2];
samples = [0]*len(weights)
data = prep(weights)
for _ in range(int(sum(weights)*TRIALS)):
samples[sample(data)]+=1
result = [float(s)/TRIALS for s in samples]
err = [a-b for a,b in zip(result,weights)]
print(result)
print([round(e,5) for e in err])
print(sum([e*e for e in err]))
解决方案 6：
以下是对集合（或多重集，如果允许重复）元素的随机加权选择的描述，包括 O（n）空间和 O（log n）时间内的有放回和无放回两种情况。
它包括实现一个二叉搜索树，按要选择的元素排序，其中树的每个节点包含：
元素本身（元素）
元素的非规范化权重 ( elementweight )，以及
左子节点及其所有子节点的所有未规范化权重的总和 ( leftbranchweight )。
右子节点及其所有子节点的所有未规范化权重的总和 ( rightbranchweight )。
然后，我们通过沿树向下随机选择一个元素，从 BST 中随机选择一个元素。算法的粗略描述如下。算法给出树的一个节点。然后将节点的leftbranchweight、rightbranchweight和elementweight的值相加，并将权重除以该和，分别得到leftbranchprobability、
rightbranchprobability和elementprobability的值。然后获得一个介于 0 和 1 之间的随机数（randomnumber ）。
如果数字小于elementprobability，
+ 像平常一样从 BST 中删除元素，更新所有必要节点的*左分支权重*
和*右分支权重，并返回该元素。*否则，如果数字小于（elementprobability + leftbranchweight）
+ *在左孩子*上递归（使用*左孩子*作为*节点*运行算法）别的
+ *右子*节点递归
当我们最终使用这些权重找到要返回的元素时，我们要么简单地返回它（替换），要么删除它并更新树中的相关权重（不替换）。
免责声明：该算法比较粗糙，这里不试图论述 BST 的正确实现；相反，希望这个答案能够帮助那些真正需要快速加权选择而不进行替换的人（就像我一样）。
解决方案 7：
这是一个老问题，numpy 现在提供了一个简单的解决方案，所以我想提一下。numpy 的当前版本是 1.2，numpy.random.choice允许使用给定权重进行有放回或无放回的采样。
解决方案 8：
假设你想从列表 ['white','blue','black','yellow','green'] 中不重复地抽取 3 个元素，概率分布为 [0.1, 0.2, 0.4, 0.1, 0.2]。使用 numpy.random 模块非常简单：
import numpy.random as rnd
sampling_size = 3
domain = ['white','blue','black','yellow','green']
probs = [.1, .2, .4, .1, .2]
sample = rnd.choice(domain, size=sampling_size, replace=False, p=probs)
# in short: rnd.choice(domain, sampling_size, False, probs)
print(sample)
# Possible output: ['white' 'black' 'blue']
将replace标志设置为True，您就有一个可替换的抽样。
更多信息请访问：
http: //docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice
解决方案 9：
我们面临的问题是，每个时期根据候选人K的质押比例随机选择一次候选人验证者N。但这给我们带来了以下问题：
想象一下每个候选人的概率：
0.1
0.1
0.8
经过 1,000,000 次不重复2选择后，每个候选人的概率变为：3
0.254315
0.256755
0.488930
您应该知道，这些原始概率对于无放回选择来说是不可能实现2的3。
但我们希望初始概率是利润分配概率。否则，它会使小型候选池更有利可图。因此，我们意识到替换随机选择将对我们有所帮助——随机选择>K并N存储每个验证者的权重以进行奖励分配：
std::vector<int> validators;
std::vector<int> weights(n);
int totalWeights = 0;
for (int j = 0; validators.size() < m; j++) {
int value = rand() % likehoodsSum;
for (int i = 0; i < n; i++) {
if (value < likehoods[i]) {
if (weights[i] == 0) {
validators.push_back(i);
}
weights[i]++;
totalWeights++;
break;
}
value -= likehoods[i];
}
}
它对数百万个样本给出了几乎原始的奖励分布：
0.101230
0.099113
0.799657
