有放回和无放回的加权随机选择

2025-01-21 09:01:00
admin
原创
72
摘要:问题描述:最近我需要对列表中的元素进行加权随机选择,既有放回法也有放回法。虽然有一些众所周知的优秀非加权选择算法,还有一些无放回加权选择算法(例如对存储算法的修改),但我找不到任何有放回加权选择的好算法。我还想避免使用存储方法,因为我选择的只是列表中的很大一部分,这些部分足够小,可以保存在内存中。有人对这种情...

问题描述:

最近我需要对列表中的元素进行加权随机选择,既有放回法也有放回法。虽然有一些众所周知的优秀非加权选择算法,还有一些无放回加权选择算法(例如对存储算法的修改),但我找不到任何有放回加权选择的好算法。我还想避免使用存储方法,因为我选择的只是列表中的很大一部分,这些部分足够小,可以保存在内存中。

有人对这种情况下的最佳方法有什么建议吗?我有自己的解决方案,但我希望找到更高效、更简单或两者兼而有之的方法。


解决方案 1:

用不变列表中的替换样本制作多个样本的最快方法之一是别名方法。核心直觉是,我们可以为加权列表创建一组大小相等的容器,这些容器可以通过位运算非常有效地索引,从而避免二分搜索。事实证明,如果操作正确,我们只需要在每个容器中存储原始列表中的两个项目,因此可以用一个百分比来表示分割。

让我们以五个同等权重的选择为例,(a:1, b:1, c:1, d:1, e:1)

要创建别名查找:

  1. 将权重标准化,使得它们的总和为1.0(a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) 这是选择每个权重的概率。

  2. 找到大于或等于变量数的最小 2 的幂,并创建此数量的分区。|p|每个分区代表一个概率质量1/|p|。在这种情况下,我们创建8分区,每个分区都可以包含0.125

  3. 取剩余重量最少的变量,并将其质量尽可能多地放在空分区中。在这个例子中,我们看到填充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)`

  4. 如果分区未填满,则取权重最大的变量,并用该变量填充分区。

重复步骤 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)待分配

在运行时:

  1. 获取U(0,1)随机数,比如二进制0.001100000

  2. 对其进行位移lg2(p),找到索引分区。因此,我们将其移动3,得到001.1,或位置 1,从而得到分区 2。

  3. 如果分区被拆分,则使用移位后的随机数的小数部分来决定拆分。在本例中,值为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)时间内的有放回和无放回两种情况。

它包括实现一个二叉搜索树,按要选择的元素排序,其中树的每个节点包含:

  1. 元素本身(元素

  2. 元素的非规范化权重 ( elementweight ),以及

  3. 左子节点及其所有子节点的所有未规范化权重的总和 ( leftbranchweight )。

  4. 右子节点及其所有子节点的所有未规范化权重的总和 ( rightbranchweight )。

然后,我们通过沿树向下随机选择一个元素,从 BST 中随机选择一个元素。算法的粗略描述如下。算法给出树的一个节点。然后将节点的leftbranchweightrightbranchweightelementweight的值相加,并将权重除以该和,分别得到leftbranchprobability
rightbranchprobabilityelementprobability的值。然后获得一个介于 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

您应该知道,这些原始概率对于无放回选择来说是不可能实现23

但我们希望初始概率是利润分配概率。否则,它会使小型候选池更有利可图。因此,我们意识到替换随机选择将对我们有所帮助——随机选择>KN存储每个验证者的权重以进行奖励分配:

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
相关推荐
  政府信创国产化的10大政策解读一、信创国产化的背景与意义信创国产化,即信息技术应用创新国产化,是当前中国信息技术领域的一个重要发展方向。其核心在于通过自主研发和创新,实现信息技术应用的自主可控,减少对外部技术的依赖,并规避潜在的技术制裁和风险。随着全球信息技术竞争的加剧,以及某些国家对中国在科技领域的打压,信创国产化显...
工程项目管理   1590  
  为什么项目管理通常仍然耗时且低效?您是否还在反复更新电子表格、淹没在便利贴中并参加每周更新会议?这确实是耗费时间和精力。借助软件工具的帮助,您可以一目了然地全面了解您的项目。如今,国内外有足够多优秀的项目管理软件可以帮助您掌控每个项目。什么是项目管理软件?项目管理软件是广泛行业用于项目规划、资源分配和调度的软件。它使项...
项目管理软件   1361  
  信创产品在政府采购中的占比分析随着信息技术的飞速发展以及国家对信息安全重视程度的不断提高,信创产业应运而生并迅速崛起。信创,即信息技术应用创新,旨在实现信息技术领域的自主可控,减少对国外技术的依赖,保障国家信息安全。政府采购作为推动信创产业发展的重要力量,其对信创产品的采购占比情况备受关注。这不仅关系到信创产业的发展前...
信创和国产化的区别   18  
  信创,即信息技术应用创新产业,旨在实现信息技术领域的自主可控,摆脱对国外技术的依赖。近年来,国货国用信创发展势头迅猛,在诸多领域取得了显著成果。这一发展趋势对科技创新产生了深远的推动作用,不仅提升了我国在信息技术领域的自主创新能力,还为经济社会的数字化转型提供了坚实支撑。信创推动核心技术突破信创产业的发展促使企业和科研...
信创工作   18  
  信创技术,即信息技术应用创新产业,旨在实现信息技术领域的自主可控与安全可靠。近年来,信创技术发展迅猛,对中小企业产生了深远的影响,带来了诸多不可忽视的价值。在数字化转型的浪潮中,中小企业面临着激烈的市场竞争和复杂多变的环境,信创技术的出现为它们提供了新的发展机遇和支撑。信创技术对中小企业的影响技术架构变革信创技术促使中...
信创国产化   19  
热门文章
项目管理软件有哪些?
云禅道AD
禅道项目管理软件

云端的项目管理软件

尊享禅道项目软件收费版功能

无需维护,随时随地协同办公

内置subversion和git源码管理

每天备份,随时转为私有部署

免费试用