Comment choisir un article dans une liste en fonction d'une probabilité spécifique?

Question

Supposons que nous avons une liste comme celle ci-dessous:

list = [[A,10,3],[B,5,2],[C,8,1]] 

Pour chaque élément dans la liste il y a une probabilité d'être choisie qui pourrait être calculé par softmax. par exemple pour le premier élément (A), nous avons:

from math import exp 

A_probability = exp(list[0][2]/list[0][1]/
        (exp(list[0][2]/list[0][1]) + 
         exp(list[1][2]/list[1][1]) + 
         exp(list[2][2]/list[2][1]))) 

Comment puis-je choisir les éléments de la liste au hasard, selon la probabilite calculée pour chacun d'eux?

Answer 1

Je suppose que vous avez une liste de probabilités pré-calculée (disons probs) pour chacun des index de la liste (disons data) que vous voulez choisir.

En outre, probs et data doit évidemment avoir la même longueur et les entrées de probs doivent être des nombres non négatifs Rajouté à 1.

Il est une technique simple mais propre à choisir au hasard les index dans data selon la répartition en probs qui est connu comme la roue de la roulette . En Python, je crois, il devrait ressembler en quelque sorte comme celui-ci

import random 

data = ['A', 'B', 'C', 'D'] 

probs = [0.2, 0.4, 0.3, 0.1] 

def roulette_wheel(probs): 
    rand = random.random() 
    for slot, prob in enumerate(probs): 
     rand -= prob 
     if rand < 0.0: 
      return slot 

Notez que cela peut être généralisé à une liste de poids non négatifs (qui ne doit pas ajouter jusqu'à 1) en multipliant rand par le terme sum(weights). Je crois, j'ai d'abord vu cette idée mignonne dans un livre au sujet de la programmation de Pascal il y a quelques années.

Modifier:

Comme MadPhysicist suggéré dans un comment cela peut être beaucoup plus efficace si l'on a besoin de tirer à plusieurs reprises à partir des mêmes données. Dans ce cas, on peut pré-calculer la fonction de distribution cumulative, puis faire une recherche binaire pour l'index tel que cumulative prob. <= rand ~ U(0, 1). En Python, cela pourrait par exemple regarder en quelque sorte comme ce qui suit

from random import random 
from bisect import bisect_right 


def cdf(probs): 
    cdf = [] 
    total = 0.0 
    for p in probs: 
     total += p 
     cdf.append(total) 
    return cdf 


def roulette_wheel_bisect(cdf): 
    return bisect_right(cdf, random()) 

# compute cdf 
cumsum = cdf(probs) 

# randomly draw 10 indexes 
for i in range(0, 10): 
    print(roulette_wheel_bisect(cumsum)) 

Disclaimer: Je ne suis pas un programmeur Python par le commerce, de sorte que le code ci-dessus ne doit illustrer l'idée générale. Il peut ne pas être très robuste pour des utilisations pratiques. Vous devriez toujours utiliser une bibliothèque standard bien testée, numpy par exemple, si vous le pouvez.

Edit2:

Je viens d'apprendre que numpy a numpy.random.choice qui fait exactement ce dont vous avez besoin. Exemple:

from numpy import random 

data = ['A', 'B', 'C', 'D'] 
probs = [0.2, 0.4, 0.3, 0.1] 

# randomly draw 10 list elements with replacement 
for i in range(0, 10): 
    print(random.choice(data, p=probs))