Взвешенный случайный выбор с заменой и без

Question

Недавно мне нужно было сделать взвешенный случайный выбор элементов из списка, как с заменой, так и без нее. Несмотря на то, что существуют хорошо известные и хорошие алгоритмы для взвешенного выбора и некоторые для взвешенного выбора без замены (например, модификации алгоритма повторного поиска), я не смог найти хороших алгоритмов для взвешенного выбора с заменой. Я также хотел избежать метода пересмотра, так как я выбирал значительную часть списка, который достаточно мал для хранения в памяти.

Есть ли у кого-нибудь предложения по лучшему подходу в этой ситуации? У меня есть свои собственные решения, но я надеюсь найти что-то более эффективное, более простое или оба.

Answer 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,

Вот некоторый код и другое объяснение, но, к сожалению, он не использует технику битового сдвига, и я на самом деле не проверял ее.

Answer 2

Простой подход, который не был упомянут здесь, - это предложенный в Efraimidis и Spirakis. В python вы можете выбрать m элементов из n >= 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)]

По структуре это очень похоже на первый подход, предложенный Ником Джонсоном. К сожалению, этот подход смещен в выборе элементов (см. Комментарии к методу). Эфраимидис и Спиракис доказали, что их подход эквивалентен случайной выборке без замены в связанной статье.

Answer 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 - количество элементов, которые нужно выбрать.

Answer 4

Я бы порекомендовал вам начать с изучения раздела 3.4.2 Полуразрядных алгоритмов Дональда Кнута.

Если ваши массивы большие, в главе 3 Принципов генерации случайных вариаций Джона Дагпунара есть более эффективные алгоритмы. Если ваши массивы не очень велики или вы не заинтересованы в том, чтобы выжать как можно больше эффективности, более простые алгоритмы в Knuth, вероятно, подойдут.

Answer 5

Взвешенный случайный выбор можно выполнить с заменой за время O(1) после первого создания дополнительной структуры данных размера O(N) за время O(N). Алгоритм основан на методе псевдонимов, разработанном Уокером и Возе, который хорошо описан здесь.

Основная идея заключается в том, что каждый бин в гистограмме будет выбираться с вероятностью 1/N однородным ГСЧ. Таким образом, мы пройдемся по нему, и для любого малонаселенного мусорного ведра, которое получило бы избыточные попадания, назначьте избыток перенаселенному мусорному ведру. Для каждого бина мы храним процент попаданий, которые ему принадлежат, и партнерское бин для превышения. Эта версия отслеживает маленькие и большие корзины на месте, устраняя необходимость в дополнительном стеке. Используется индекс партнера (хранится в 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]))

Answer 6

Ниже приведено описание случайного взвешенного выбора элемента набора (или мультимножества, если разрешены повторы), как с заменой, так и без замены в пространстве O(n) и времени O(log n).

Он состоит из реализации двоичного дерева поиска, отсортированного по выбранным элементам, где каждый узел дерева содержит:

1. сам элемент (элемент)
2. ненормализованный вес элемента (elementweight), и
3. сумма всех ненормализованных весов левого дочернего узла и всех его дочерних элементов (левый ответный вес).
4. сумма всех ненормализованных весов правого дочернего узла и всех его детей (правосторонний вес).

Затем мы случайным образом выбираем элемент из BST, спускаясь по дереву. Грубое описание алгоритма приведено ниже. Алгоритм задается узлом дерева. Затем значения левого и правого ветвей и веса элементов для узла суммируются, и веса делятся на эту сумму, в результате чего значения правостороннего правопреемства, правостороннего правдоподобия и правдоподобия элементов соответственно. Затем получается случайное число от 0 до 1 (randomnumber).

• если число меньше вероятности элемента,
  • удалите элемент из BST как обычно, обновив левый и правый вес всех необходимых узлов и верните элемент.
• иначе, если число меньше чем (elementprobability + leftbranchweight)
  • рекурсировать на левом шилде (запустить алгоритм, используя левого ребенка в качестве узла)
• еще
  • рекурсировать по праву

Когда мы, наконец, с помощью этих весов выясняем, какой элемент должен быть возвращен, мы либо просто возвращаем его (с заменой), либо удаляем его и обновляем соответствующие веса в дереве (без замены).

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Алгоритм является грубым, и трактат о правильной реализации BST здесь не предпринимается; скорее, мы надеемся, что этот ответ поможет тем, кто действительно нуждается в быстром взвешенном отборе без замены (как я).

Answer 7

Это старый вопрос, для которого numpy теперь предлагает простое решение, поэтому я подумал, что упомяну его. Текущая версия numpy - версия 1.2 и numpy.random.choiceпозволяет проводить отбор проб с заменой или без нее и с заданным весом.

Answer 8

Предположим, что вы хотите выбрать 3 элемента без замены из списка ['white','blue','black','yellow','green'] с пробой. распределение [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

Answer 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