Взвешенные случайные числа

104

Я пытаюсь реализовать взвешенные случайные числа. Я сейчас просто бьюсь головой об стену и не могу понять этого.

В своем проекте (диапазоны рук в холдеме, субъективный анализ эквити олл-ин) я использую случайные функции Boost. Итак, допустим, я хочу выбрать случайное число от 1 до 3 (то есть 1, 2 или 3). Генератор mersenne twister от Boost отлично справляется с этой задачей. Однако я хочу, чтобы выбор был взвешен, например, следующим образом:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Есть ли у Boost какие-то функции для этого?

nhaa123
источник

Ответы:

181

Существует простой алгоритм случайного выбора предмета, при котором предметы имеют индивидуальный вес:

1) посчитайте сумму всех весов

2) выберите случайное число, которое равно 0 или больше и меньше суммы весов

3) просматривайте элементы по одному, вычитая их вес из случайного числа, пока не получите элемент, случайное число которого меньше веса этого элемента.

Псевдокод, иллюстрирующий это:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

Это должно быть легко адаптировать к вашим буст-контейнерам и тому подобному.


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

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


Если вы не знаете количество элементов в списке, тогда существует очень удобный алгоритм, называемый отбором проб резервуара, который можно адаптировать для взвешивания.

Будет
источник
3
В качестве оптимизации вы можете использовать кумулятивные веса и бинарный поиск. Но всего для трех разных значений это, вероятно, перебор.
sellibitze
2
Я предполагаю, что когда вы говорите «по порядку», вы намеренно пропускаете этап предварительной сортировки в массиве choice_weight, да?
SilentDirge
2
@Aureis, сортировка массива не требуется. Я попытался пояснить свой язык.
Уилл
1
@Will: Да, но есть алгоритм с таким же названием. sirkan.iit.bme.hu/~szirmay/c29.pdf и en.wikipedia.org/wiki/Photon_mapping, когда A Monte Carlo method called Russian roulette is used to choose one of these actions он ищет его в Google, он всплывает группами . «Алгоритм русской рулетки». Вы можете возразить, что у всех этих людей неправильное имя.
v.oddou
3
Примечание для будущих читателей: часть вычитания их веса из вашего случайного числа легко упустить из виду, но она имеет решающее значение для алгоритма (я попал в ту же ловушку, что и @kobik в их комментарии).
Фрэнк Шмитт
48

Обновленный ответ на старый вопрос. Вы можете легко сделать это в C ++ 11 с помощью только std :: lib:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Вывод в моей системе:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Обратите внимание, что большая часть приведенного выше кода посвящена просто отображению и анализу вывода. Фактическая генерация - это всего лишь несколько строк кода. Выходные данные показывают, что запрошенные «вероятности» были получены. Вы должны разделить запрошенный вывод на 1,5, так как это то, к чему складываются запросы.

Говард Хиннант
источник
Просто напоминание о компиляции этого примера: требуется C ++ 11, т.е. используйте флаг компилятора -std = c ++ 0x, доступный начиная с gcc 4.6.
Pete855217
3
Хотите просто выбрать необходимые детали, которые решат проблему?
Джонни
2
Это лучший ответ, но я думаю , что std::discrete_distributionвместо того , std::piecewise_constant_distributionбыло бы еще лучше.
Дэн
1
@Dan, да, это был бы еще один отличный способ сделать это. Если вы его закодируете и ответите, я проголосую за это. Я думаю, что код может быть очень похож на тот, что у меня выше. Вам просто нужно добавить один к сгенерированному выводу. И ввод в раздачу был бы проще. Набор сравнений / противопоставлений ответов в этой области может быть ценным для читателей.
Ховард Хиннант
15

Если ваши веса изменяются медленнее, чем они нарисованы, C ++ 11 discrete_distributionбудет самым простым:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Однако обратите внимание, что c ++ 11 discrete_distributionвычисляет все совокупные суммы при инициализации. Обычно вам это нужно, потому что это ускоряет время выборки за разовую стоимость O (N). Но для быстро меняющегося дистрибутива это потребует больших затрат на вычисления (и память). Например, если веса представляют количество элементов, и каждый раз, когда вы рисуете один и удаляете его, вам, вероятно, понадобится собственный алгоритм.

Ответ Уилла https://stackoverflow.com/a/1761646/837451 позволяет избежать этих накладных расходов, но будет работать медленнее, чем C ++ 11, потому что он не может использовать двоичный поиск.

Чтобы убедиться в этом, вы можете увидеть соответствующие строки ( /usr/include/c++/5/bits/random.tccв моей установке Ubuntu 16.04 + GCC 5.3):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }
mmdanziger
источник
10

Когда мне нужно взвесить числа, я использую случайное число для веса.

Например: мне нужно, чтобы сгенерировали случайные числа от 1 до 3 со следующими весами:

  • 10% случайного числа может быть 1
  • 30% случайного числа может быть 2
  • 60% случайного числа может быть 3

Тогда использую:

weight = rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

При этом случайным образом у 10% вероятностей будет 1, 30% - 2 и 60% - 3.

Вы можете играть с ним по своему усмотрению.

Надеюсь, я смогу вам помочь, удачи!

Чирри
источник
Это исключает динамическую корректировку распределения.
Джош К.
2
Хаки, но мне это нравится. Подходит для быстрого прототипа, где нужно немного взвесить.
нарисовал
1
Это работает только для рациональных весов. Вам будет сложно делать это с весом 1 / пи;)
Джозеф Будин
1
@JosephBudin Опять же, вы никогда не сможете иметь иррациональный вес. Переключатель на ~ 4,3 миллиарда корпусов отлично подойдет для плавающих весов. : D
Jason C
1
Право, @JasonC, проблема теперь бесконечно меньше, но все еще остается проблемой;)
Джозеф Будин
3

Создайте сумку (или std :: vector) из всех предметов, которые можно выбрать.
Убедитесь, что количество каждого элемента пропорционально вашему весу.

Пример:

  • 1 60%
  • 2 35%
  • 3 5%

Так что имейте мешок со 100 предметами с 60 единицами, 35 двойками и 5 тройками.
Теперь случайным образом отсортируйте сумку (std :: random_shuffle)

Выбирайте элементы из пакета последовательно, пока он не опустеет.
После того, как мешок опустеет, перемешайте его заново и начните заново.

Мартин Йорк
источник
6
если у вас есть мешок с красными и синими шариками, и вы выбираете из него красный шарик и не заменяете его, остается ли вероятность выбора другого красного шарика такой же? Точно так же ваше утверждение «Выбирайте элементы из пакета последовательно, пока он не станет пустым» производит совершенно иное распределение, чем предполагалось.
ldog
@ldog: Я понимаю ваш аргумент, но мы не ищем истинной случайности, мы ищем конкретное распределение. Этот метод гарантирует правильное распределение.
Мартин Йорк,
4
Я имею в виду именно то, что вы неправильно производите распространение согласно моему предыдущему аргументу. рассмотрим простой пример счетчика, допустим, у вас есть массив из 3, который 1,2,2производит 1 1/3 времени и 2 2/3. Произведите случайный выбор массива, выберите первый, скажем, 2, теперь следующий выбранный элемент следует распределению 1 1/2 времени и 2 1/2 времени. Сообразительный?
ldog
0

Выберите случайное число на [0,1), которое должно быть оператором по умолчанию () для повышения ГСЧ. Выберите элемент с кумулятивной функцией плотности вероятности> = это число:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Где random01 () возвращает двойное значение> = 0 и <1. Обратите внимание, что приведенное выше не требует суммирования вероятностей до 1; это нормализует их для вас.

p - это просто функция, присваивающая вероятность элементу в коллекции [начало, конец). Вы можете опустить его (или использовать идентификатор), если у вас есть просто последовательность вероятностей.

Джонатан Грель
источник