python - color - plotly layout

Selección aleatoria ponderada con y sin reemplazo

Question

Recientemente necesité hacer una selección aleatoria ponderada de elementos de una lista, tanto con como sin reemplazo. Si bien existen algoritmos bien conocidos y buenos para la selección no ponderada, y algunos para la selección ponderada sin reemplazo (como las modificaciones del algoritmo del repositorio), no pude encontrar ningún algoritmo bueno para la selección ponderada con reemplazo. También quería evitar el método de depósito, ya que estaba seleccionando una fracción significativa de la lista, que es lo suficientemente pequeña como para mantenerla en la memoria.

¿Alguien tiene alguna sugerencia sobre el mejor enfoque en esta situación? Tengo mis propias soluciones, pero espero encontrar algo más eficiente, más simple o ambas cosas.

Answer 1

Es posible hacer una selección aleatoria ponderada con reemplazo en el tiempo O (1), después de crear primero una estructura de datos de tamaño O (N) adicional en el tiempo O (N). El algoritmo se basa en el Método Alias desarrollado por Walker y Vose, que está bien descrito here .

La idea esencial es que cada bin en un histograma sería elegido con probabilidad 1 / N por un RNG uniforme. Así que lo revisaremos, y para cualquier contenedor poco poblado que reciba un exceso de visitas, asigne el exceso a un contenedor superpoblado. Para cada contenedor, almacenamos el porcentaje de visitas que le pertenecen y el contenedor asociado para el exceso. Esta versión rastrea contenedores pequeños y grandes en su lugar, eliminando la necesidad de una pila adicional. Utiliza el índice del socio (almacenado en el bucket[1] ) como indicador de que ya se han procesado.

Aquí hay una implementación mínima de python, basada en la implementación de C aquí

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

Ejemplo de uso:

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 2

Esto es lo que se me ocurrió para la selección ponderada sin reemplazo:

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:]

Esto es O (m log m) en la cantidad de elementos de la lista para seleccionar. Estoy bastante seguro de que esto pesará los elementos correctamente, aunque no lo he verificado en ningún sentido formal.

Esto es lo que se me ocurrió para la selección ponderada con reemplazo:

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)]

Esto es O (m + n log m), donde m es el número de elementos en la lista de entrada, y n es el número de elementos que se seleccionarán.

Answer 3

La siguiente es una descripción de la selección ponderada aleatoria de un elemento de un conjunto (o multiset, si se permiten repeticiones), tanto con y sin reemplazo en el espacio O (n) como en el tiempo O (log n).

Consiste en implementar un árbol de búsqueda binaria, ordenado por los elementos a seleccionar, donde cada nodo del árbol contiene:

1. el elemento en sí mismo ( elemento )
2. el peso no normalizado del elemento (elemento de peso ), y
3. la suma de todos los pesos no normalizados del nodo secundario izquierdo y todos sus hijos ( leftbranchweight ).
4. la suma de todos los pesos no normalizados del nodo derecho-hijo y todos sus hijos (derecha- divisor ).

Luego seleccionamos aleatoriamente un elemento del BST descendiendo por el árbol. Una descripción aproximada del algoritmo sigue. El algoritmo recibe un nodo del árbol. Luego se suman los valores de leftbranchweight , rightbranchweight y elementweight of node , y los pesos se dividen por esta suma, lo que da como resultado los valores leftbranchprobability , rightbranchprobability y elementprobability , respectivamente. Luego se obtiene un número aleatorio entre 0 y 1 (número aleatorio ).

• si el número es menor que la probabilidad de elemento ,
  • elimine el elemento de la BST de forma normal, actualizando leftbranchweight y rightbranchweight de todos los nodos necesarios, y devuelva el elemento.
• de lo contrario, si el número es menor que ( elementprobability + leftbranchweight )
  • recurse en leftchild (ejecuta el algoritmo usando leftchild como nodo )
• más
  • recurse en rightchild

Cuando finalmente encontramos, usando estos pesos, qué elemento debe devolverse, simplemente lo devolvemos (con reemplazo) o lo eliminamos y actualizamos los pesos relevantes en el árbol (sin reemplazo).

DESCARGO DE RESPONSABILIDAD: El algoritmo es difícil, y aquí no se intenta un tratado sobre la implementación adecuada de una BST; más bien, se espera que esta respuesta ayude a aquellos que realmente necesitan una selección ponderada rápida sin reemplazo (como yo).

Answer 4

Supongamos que desea muestrear 3 elementos sin reemplazo de la lista [''blanco'', ''azul'', ''negro'', ''amarillo'', ''verde''] con un problema. distribución [0.1, 0.2, 0.4, 0.1, 0.2]. Usar el módulo numpy.random es tan fácil como esto:

    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'']

Al establecer el indicador de replace en True , tiene un muestreo con reemplazo.

Más información aquí: http://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html#numpy.random.choice

Answer 5

Te recomiendo que comiences mirando la sección 3.4.2 de los algoritmos de Seminumerical de Donald Knuth.

Si sus matrices son grandes, hay algoritmos más eficientes en el capítulo 3 de Principios de la generación aleatoria de varianzas de John Dagpunar. Si sus matrices no son terriblemente grandes o no le preocupa exprimir la mayor eficiencia posible, los algoritmos más sencillos de Knuth probablemente estén bien.

Answer 6

Un enfoque simple que no se ha mencionado aquí es uno propuesto en Efraimidis y Spirakis . En python, puede seleccionar m elementos de n> = m elementos ponderados con pesos estrictamente positivos almacenados en pesos, que devuelven los índices seleccionados, con:

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)]

Esto es muy similar en estructura al primer enfoque propuesto por Nick Johnson. Desafortunadamente, ese enfoque es parcial en la selección de los elementos (ver los comentarios sobre el método). Efraimidis y Spirakis demostraron que su enfoque es equivalente al muestreo aleatorio sin reemplazo en el documento vinculado.

Answer 7

Una de las formas más rápidas de hacer muchas con muestras de reemplazo de una lista inmutable es el método de alias. La intuición central es que podemos crear un conjunto de contenedores de igual tamaño para la lista ponderada que se puede indexar de manera muy eficiente a través de operaciones de bits, para evitar una búsqueda binaria. Resultará que, hecho correctamente, solo necesitaremos almacenar dos elementos de la lista original por contenedor, y así podemos representar la división con un solo porcentaje.

Tomemos el ejemplo de cinco elecciones igualmente ponderadas, (a:1, b:1, c:1, d:1, e:1)

Para crear la búsqueda de alias:

1. Normalice los pesos de modo que sumen a 1.0 . (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) Esta es la probabilidad de elegir cada peso.

2. Encuentre la potencia más pequeña de 2 mayor o igual que la cantidad de variables, y cree este número de particiones, |p| . Cada partición representa una masa de probabilidad de 1/|p| . En este caso, creamos 8 particiones, cada una capaz de contener 0.125 .

3. Tome la variable con el menor peso restante y coloque la mayor cantidad de masa posible en una partición vacía. En este ejemplo, vemos que a llena la primera partición. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) con (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

4. Si la partición no está llena, tome la variable con más peso y llene la partición con esa variable.

Repita los pasos 3 y 4, hasta que no se asigne ninguna parte del peso de la partición original a la lista.

Por ejemplo, si ejecutamos otra iteración de 3 y 4, vemos

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) con (a:0, b:0.15 c:0.2 d:0.2 e:0.2) dejó de ser asignado

En tiempo de ejecución:

1. Obtenga un número aleatorio U(0,1) , por ejemplo, 0.001100000 binario

2. Bitshift it lg2(p) , encontrando la partición de índice. Por lo tanto, lo cambiamos por 3 , produciendo 001.1 , o la posición 1, y por lo tanto la partición 2.

3. Si la partición está dividida, use la parte decimal del número aleatorio desplazado para decidir la división. En este caso, el valor es 0.5 y 0.5 < 0.6 , entonces devuelve a .

Aquí hay un código y otra explicación , pero desafortunadamente no usa la técnica de cambio de bits, ni la he verificado.