Gewichtete Zufallszahlen

101

Ich versuche, gewichtete Zufallszahlen zu implementieren. Ich schlage gerade meinen Kopf gegen die Wand und kann das nicht herausfinden.

In meinem Projekt (Hold'em-Handbereiche, subjektive All-in-Equity-Analyse) verwende ich die Zufallsfunktionen von Boost. Nehmen wir also an, ich möchte eine Zufallszahl zwischen 1 und 3 auswählen (also entweder 1, 2 oder 3). Der Mersenne-Twister-Generator von Boost wirkt wie ein Zauber dafür. Ich möchte jedoch, dass die Auswahl beispielsweise wie folgt gewichtet wird:

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

Hat Boost dafür irgendeine Funktionalität?

nhaa123
quelle

Antworten:

179

Es gibt einen einfachen Algorithmus zum zufälligen Auswählen eines Artikels, bei dem Artikel individuelle Gewichte haben:

1) Berechnen Sie die Summe aller Gewichte

2) Wählen Sie eine Zufallszahl, die 0 oder größer ist und kleiner als die Summe der Gewichte ist

3) Gehen Sie die Artikel einzeln durch und subtrahieren Sie ihr Gewicht von Ihrer Zufallszahl, bis Sie den Artikel erhalten, bei dem die Zufallszahl geringer ist als das Gewicht dieses Artikels

Pseudocode zur Veranschaulichung:

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");

Dies sollte einfach an Ihre Boost-Container und dergleichen anzupassen sein.


Wenn Ihre Gewichte selten geändert werden, Sie jedoch häufig zufällig eine auswählen und Ihr Container Zeiger auf die Objekte speichert oder mehr als ein paar Dutzend Elemente lang ist (im Grunde müssen Sie ein Profil erstellen, um zu wissen, ob dies hilft oder behindert). , dann gibt es eine Optimierung:

Durch Speichern der kumulierten Gewichtssumme in jedem Artikel können Sie mithilfe einer binären Suche den Artikel auswählen, der dem Kommissioniergewicht entspricht.


Wenn Sie die Anzahl der Elemente in der Liste nicht kennen, gibt es einen sehr übersichtlichen Algorithmus namens Reservoir Sampling , der zur Gewichtung angepasst werden kann.

Wille
quelle
3
Als Optimierung können Sie kumulative Gewichte und eine binäre Suche verwenden. Aber für nur drei verschiedene Werte ist dies wahrscheinlich übertrieben.
Sellibitze
2
Ich gehe davon aus, dass Sie, wenn Sie "in Reihenfolge" sagen, absichtlich einen Vorsortierungsschritt für das Array "choice_weight" weglassen, ja?
SilentDirge
2
@Aureis, das Array muss nicht sortiert werden. Ich habe versucht, meine Sprache zu klären.
Will
1
@ Will: Ja, aber es gibt einen gleichnamigen Algorithmus. sirkan.iit.bme.hu/~szirmay/c29.pdf und en.wikipedia.org/wiki/Photon_mapping A Monte Carlo method called Russian roulette is used to choose one of these actions wird beim googeln in Eimern angezeigt. "Russischer Roulette-Algorithmus". Man könnte argumentieren, dass all diese Leute den falschen Namen haben.
v.oddou
3
Hinweis für zukünftige Leser: Der Teil, der ihr Gewicht von Ihrer Zufallszahl abzieht, ist leicht zu übersehen, aber für den Algorithmus von entscheidender Bedeutung (ich bin in ihrem Kommentar in dieselbe Falle geraten wie @kobik).
Frank Schmitt
48

Aktualisierte Antwort auf eine alte Frage. Sie können dies in C ++ 11 ganz einfach mit std :: lib tun:

#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';
}

Ausgabe auf meinem System:

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

Beachten Sie, dass der größte Teil des obigen Codes nur der Anzeige und Analyse der Ausgabe gewidmet ist. Die eigentliche Generation besteht nur aus wenigen Codezeilen. Die Ausgabe zeigt, dass die angeforderten "Wahrscheinlichkeiten" erhalten wurden. Sie müssen die angeforderte Ausgabe durch 1,5 teilen, da dies die Anforderungen sind.

Howard Hinnant
quelle
Nur eine Erinnerung zur Kompilierung dieses Beispiels: erfordert C ++ 11, dh. Verwenden Sie das Compiler-Flag -std = c ++ 0x, verfügbar ab gcc 4.6.
Pete855217
3
Möchten Sie nur die notwendigen Teile auswählen, die das Problem lösen?
Jonny
2
Dies ist die beste Antwort, aber ich denke, std::discrete_distributionstattdessen std::piecewise_constant_distributionwäre es noch besser gewesen.
Dan
1
@ Dan, ja, das wäre eine weitere hervorragende Möglichkeit, dies zu tun. Wenn Sie es codieren und damit antworten, werde ich dafür stimmen. Ich denke, der Code könnte dem, was ich oben habe, ziemlich ähnlich sein. Sie müssten lediglich eine zur generierten Ausgabe hinzufügen. Und die Eingabe in die Verteilung wäre einfacher. Ein Vergleich / Kontrast-Satz von Antworten in diesem Bereich kann für die Leser wertvoll sein.
Howard Hinnant
15

Wenn sich Ihre Gewichte langsamer ändern als gezeichnet, ist C ++ 11 discrete_distributionam einfachsten:

#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...

Beachten Sie jedoch, dass c ++ 11 discrete_distributionalle kumulierten Summen bei der Initialisierung berechnet. Normalerweise möchten Sie das, weil es die Abtastzeit für einmalige O (N) -Kosten beschleunigt. Für eine sich schnell ändernde Verteilung entstehen jedoch hohe Berechnungs- (und Speicher-) Kosten. Wenn die Gewichte beispielsweise die Anzahl der Elemente darstellen und jedes Mal, wenn Sie eines zeichnen, entfernen Sie es, möchten Sie wahrscheinlich einen benutzerdefinierten Algorithmus.

Wills Antwort https://stackoverflow.com/a/1761646/837451 vermeidet diesen Overhead, ist jedoch langsamer zu zeichnen als C ++ 11, da keine binäre Suche verwendet werden kann.

Um dies zu sehen, können Sie die relevanten Zeilen sehen ( /usr/include/c++/5/bits/random.tccauf meiner Ubuntu 16.04 + GCC 5.3-Installation):

  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
quelle
10

Was ich mache, wenn ich Zahlen gewichten muss, ist die Verwendung einer Zufallszahl für das Gewicht.

Zum Beispiel: Ich brauche das, um Zufallszahlen von 1 bis 3 mit den folgenden Gewichten zu generieren:

  • 10% einer Zufallszahl könnten 1 sein
  • 30% einer Zufallszahl könnten 2 sein
  • 60% einer Zufallszahl könnten 3 sein

Dann benutze ich:

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;
}

Damit hat es zufällig 10% der Wahrscheinlichkeiten 1, 30% 2 und 60% 3.

Sie können damit nach Ihren Wünschen spielen.

Hoffe ich konnte dir helfen, viel Glück!

Chirry
quelle
Dies schließt eine dynamische Anpassung der Verteilung aus.
Josh C
2
Hacky aber ich mag es. Schön für einen schnellen Prototyp, bei dem Sie eine grobe Gewichtung wünschen.
Zeichnen
1
Es funktioniert nur für rationale Gewichte. Sie werden es schwer haben, es mit einem 1 / pi-Gewicht zu tun;)
Joseph Budin
1
@ JosephBudin Andererseits würden Sie niemals ein irrationales Gewicht haben können. Ein ~ 4,3 Milliarden Gehäuseschalter sollte für Schwimmergewichte gut geeignet sein. : D
Jason C
1
Richtig @JasonC, das Problem ist jetzt unendlich kleiner, aber immer noch ein Problem;)
Joseph Budin
3

Erstellen Sie eine Tasche (oder std :: vector) aller Artikel, die ausgewählt werden können.
Stellen Sie sicher, dass die Anzahl der einzelnen Elemente proportional zu Ihrer Gewichtung ist.

Beispiel:

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

Haben Sie also eine Tasche mit 100 Artikeln mit 60 1er, 35 2er und 5 3er.
Sortieren Sie nun die Tasche nach dem Zufallsprinzip (std :: random_shuffle)

Nehmen Sie die Elemente nacheinander aus dem Beutel, bis er leer ist.
Sobald der Beutel leer ist, randomisieren Sie ihn erneut und beginnen Sie erneut.

Martin York
quelle
6
Wenn Sie eine Tüte mit rotem und blauem Marmor haben und einen roten Marmor daraus auswählen und diesen nicht ersetzen, ist die Wahrscheinlichkeit, einen anderen roten Marmor auszuwählen, immer noch gleich? Auf die gleiche Weise erzeugt Ihre Aussage "Elemente nacheinander aus dem Beutel auswählen, bis er leer ist" eine völlig andere Verteilung als beabsichtigt.
ldog
@ldog: Ich verstehe Ihr Argument, aber wir suchen nicht nach wahrer Zufälligkeit, sondern nach einer bestimmten Verteilung. Diese Technik garantiert die korrekte Verteilung.
Martin York
4
Mein Punkt ist genau, dass Sie nach meinem vorherigen Argument die Verteilung nicht korrekt erzeugen. Betrachten Sie das einfache Zählerbeispiel. Angenommen, Sie haben ein Array von 3 als 1,2,21 1/3 der Zeit und 2 2/3. Randomisieren Sie das Array, wählen Sie das erste aus, sagen wir eine 2, jetzt folgt das nächste Element, das Sie auswählen, der Verteilung von 1 1/2 der Zeit und 2 1/2 der Zeit. Kapieren?
ldog
0

Wählen Sie eine Zufallszahl für [0,1), die der Standardoperator () für ein Boost-RNG sein sollte. Wählen Sie den Artikel mit der kumulativen Wahrscheinlichkeitsdichtefunktion> = diese Zahl:

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
}

Wobei random01 () ein double> = 0 und <1 zurückgibt. Beachten Sie, dass für die obigen Schritte die Wahrscheinlichkeiten nicht 1 ergeben müssen. es normalisiert sie für dich.

p ist nur eine Funktion, die einem Element in der Sammlung eine Wahrscheinlichkeit zuweist [Anfang, Ende]. Sie können es weglassen (oder eine Identität verwenden), wenn Sie nur eine Folge von Wahrscheinlichkeiten haben.

Jonathan Graehl
quelle