El muestreo de depósito es una familia de algoritmos aleatorios para elegir una muestra aleatoria simple, sin reemplazo, de elementos de una población de tamaño no conocido en un solo paso por los elementos. El algoritmo no conoce el tamaño de la población y, por lo general, es demasiado grande para muestrearla en su totalidad y que todos los elementos quepan en la memoria principal. La población se revela al algoritmo a lo largo del tiempo y el algoritmo no puede mirar atrás a elementos anteriores. En cualquier momento, el estado actual del algoritmo debe permitir la extracción de una muestra aleatoria simple sin reemplazo de tamaño k sobre la parte de la población vista hasta el momento.
Motivación Supongamos que vemos una secuencia de elementos, uno a la vez. Queremos mantener diez de estos en la memoria y que se seleccionen al azar en la secuencia. Si conocemos el número total de elementos y podemos acceder a los elementos arbitrariamente; por lo tanto, la solución es fácil: se seleccionan 10 índices distintos entre 1 y con la misma probabilidad y se conservan los -ésimos elementos. El problema es que no siempre conocemos el exacto de antemano.
Simple: algoritmo R Jeffrey Vitter creó un algoritmo simple y popular pero lento, el algoritmo R.Inicialice una matriz indexada de a , que contenga los primeros elementos de la entrada . Este es el depósito .
Por cada nueva entrada , genere un número aleatorio uniformemente en . Si , haga que , de lo contrario, descarte .
Devuelva una vez procesadas todas las entradas.Este algoritmo funciona por inducción en .
PruebaCuando i = k el algoritmo R devuelve todas las entradas, proporcionando la base para una demostración por inducción matemática.
Aquí, la hipótesis de inducción es que la probabilidad de que una determinada entrada esté incluida en el depósito justo antes de que se procese la (i + 1)-ésima entrada es k / i y debemos demostrar que la probabilidad de que una entrada determinada esté incluida en el depósito es k / (i + 1) justo después de que se procese la (i + 1)-ésima entrada. Aplique el algoritmo R a la (i + 1)-ésima entrada. La entrada xi+1 se incluye con probabilidad k / (i + 1) por definición del algoritmo. Para cualquier otra j ∈ {k + 1,…, i + 1}, por la hipótesis de inducción, la probabilidad de que la entrada xr ∈ {x1,…, xi} se incluya en el depósito justo antes de que se procese la (i + 1)-ésima entrada, es k / i.
La probabilidad de que siga incluida en el depósito después de procesar xi+1 (es decir, de que xr no sea sustituida por xi+1) es (k / i)(1 – 1 / (i + 1)). Este último resultado se desprende de la suposición de que el número entero j j se genera uniformemente al azar; una vez que queda claro que de hecho se producirá una sustitución, la probabilidad de que xr en particular sea sustituido por xi+1 es (k / (i + 1))(1 / k) = 1 / (i + 1).
Hemos demostrado que la probabilidad de que una entrada nueva entre en el depósito es igual a la probabilidad de que una entrada existente se mantenga en el depósito. Por lo tanto, concluimos por el principio de inducción matemática que el algoritmo R produce efectivamente una muestra aleatoria de las entradas.
Aunque es conceptualmente simple y sencillo de entender, este algoritmo necesita generar un número aleatorio para cada elemento de la entrada, incluidos los elementos que se descartan. Por lo tanto, el tiempo de ejecución asintótico del algoritmo es . Generar esta cantidad de aleatoriedad y el tiempo de ejecución lineal hace que el algoritmo sea innecesariamente lento cuando la población de entrada es grande.
Este es el Algoritmo R, implementado del siguiente modo:(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample(S[1..n], R[1..k]) // llenar el conjunto de depósitos for i := 1 to k R[i] := S[i]
// sustituir elementos con probabilidad gradualmente decreciente for i := k+1 to n (* randomInteger(a, b) genera un entero uniforme del intervalo inclusivo {a, ..., b} *) j := randomInteger(1, i) if j <= k R[j] := S[i](* S tiene elementos para muestrear, R contendrá el resultado *)
MuestraDeDeposito(S[1..n], R[1..k])
// llenar el arreglo del depósito
for i := 1 to k
R[i] := S[i]
// sustituir elementos con probabilidad gradualmente decreciente
for i := k+1 to n
(* randomInteger(a, b) genera un entero uniforme del intervalo inclusivo {a, ..., b} *)
j := randomInteger(1, i)
if j <= k
R[j] := S[i]
Óptimo: algoritmo L Si generamos números al azar independientemente, los índices de los más pequeños es una muestra uniforme de los subconjuntos de k de .
El proceso se puede hacer sin conocer :Conserve los más pequeños de vistos hasta ahora, así como , el índice de los más grandes entre ellos. Para cada nuevo compare con . Si , descarte , almacene y establezca como el índice del mayor entre ellos. De lo contrario, descarte y haga .Ahora combine esto con el flujo de entradas . Cada vez que alguna se acepta, guarde el correspondiente. Cada vez que alguna se descarta, descarte el correspondiente.
Este algoritmo todavía necesita números aleatorios y toma un tiempo de . Pero se puede simplificar.
Primera simplificación: no es necesario probar nuevos uno por uno, ya que la probabilidad de que la siguiente aceptación suceda en es , es decir, el intervalo de aceptación sigue una distribución geométrica.
Segunda simplificación: no es necesario recordar todo el arreglo de los más pequeños de que se ha visto hasta ahora, sino simplemente , el mayor de ellos. Esto se basa en tres observaciones:
Cada vez que un nuevo se selecciona para ir al depósito, se descarta una entrada uniformemente aleatoria en el almacenamiento.
tiene la misma distribución que , donde todos de modo independiente. Esto puede ser muestreado con la primera toma de muestras y tomando .
Este es el algoritmo L, que se implementa así:(* S tiene elementos para muestrear, R contendrá el resultado *) MuestraDeDeposito(S[1..n], R[1..k]) // llenar el arreglo del depósito for i = 1 to k R[i] := S[i]
(* random() genera un número (0,1) aleatorio uniforme *) W := exp(log(random())/k)
while i <= n i := i + floor(log(random())/log(1-W)) + 1 if i <= n (* sustituir un elemento aleatorio del depósito por el elemento i *) R[randomInteger(1,k)] := S[i] // índice aleatorio comprendido entre 1 y k, ambos inclusive W := W * exp(log(random())/k)Este algoritmo calcula tres números aleatorios para cada elemento que entra a formar parte del depósito y no dedica tiempo a los elementos que no lo hacen. Así que el tiempo de ejecución esperado es , que es óptimo. Al mismo tiempo, es fácil de implementar de manera eficiente y no depende de desviaciones aleatorias de distribuciones exóticas o difíciles de calcular.
Con clasificación aleatoria Si asociamos a cada elemento de la entrada un número aleatorio generado uniformemente, los elementos con los valores asociados más grandes (o, equivalentemente, más pequeños) forman una muestra aleatoria simple. Por lo tanto, un muestreo de depósito simple mantiene los elementos con los valores asociados más grandes en el momento en una cola de prioridad .(* S es un flujo de elementos para muestrear S.Current devuelve el elemento actual del flujo S.Next avanza el flujo a la siguiente posición min-priority-queue permite: Count -> número de elementos en la cola de prioridad Mínimo -> devuelve el valor de clave mínimo de todos los elementos Extract-Min() -> Elimina el elemento con clave mínima Insert(key, Item) -> Añade el elemento con la clave especificada *) ReservoirSample(S[1..?]) H := new min-priority-queue while S has data r := random() // aleatorio uniforme entre 0 y 1, exclusivo if H.Count < k H.Insert(r, S.Current) else // conservar k elementos con las mayores claves asociadas if r > H.Minimum H.Extract-Min() H.Insert(r, S.Current) S.Next return items in HEl tiempo de ejecución esperado de este algoritmo es y es relevante en particular porque puede extenderse fácilmente a elementos ponderados.
Muestreo aleatorio ponderado Este método, también conocido como muestreo secuencial, es incorrecto en el sentido de que no permite obtener probabilidades de inclusión fijadas con anterioridad. Algunas aplicaciones requieren que las probabilidades de muestreo de los elementos estén de acuerdo con los pesos asociados con cada elemento. Por ejemplo, es posible que sea necesario muestrear consultas en un motor de búsqueda, con peso, según la cantidad de veces que se realizaron para que la muestra pueda analizarse con respecto al impacto general en la experiencia del usuario. Sean el peso del elemento y la suma de todos los pesos sea , hay dos maneras de interpretar los pesos asignados a cada elemento del conjunto:
En cada ronda, la probabilidad de que cada elemento no seleccionado sea seleccionado en esa ronda sea proporcional a su peso en relación con los pesos de todos los elementos no seleccionados. Si es la muestra actual, la probabilidad de un elemento de ser seleccionado en esa ronda es . La probabilidad de que cada elemento sea incluido en la muestra aleatoria es proporcional a su peso relativo, es decir, . Tenga en cuenta que esta interpretación podría no ser posible en algunos casos, por ejemplo cuando.
Algoritmo A-Res El siguiente algoritmo fue desarrollado por Efraimidis y Spirakis que usan la interpretación 1:(* S es un flujo de elementos a muestrear S.Actual devuelve el elemento actual del flujo S.Peso devuelve el peso del elemento actual del flujo S.Next avanza el flujo a la siguiente posición El operador de potencia se representa mediante ^ min-priority-queue permite: Count -> número de elementos en la cola de prioridad Minimum() -> devuelve el valor de clave mínimo de todos los elementos Extract-Min() -> Elimina el elemento con clave mínima Insert(key, Item) -> Añade el elemento con la clave especificada *) ReservoirSample(S[1..?]) H := new min-priority-queue while S has data r := random() ^ (1/S.Weight) // random() produce un número aleatorio uniforme en (0,1) if H.Count < k H.Insert(r, S.Current) else // conservar los k elementos con las claves asociadas más grandes if r > H.Minimum H.Extract-Min() H.Insert(r, S.Current) S.Next return items in HEste algoritmo es idéntico al algoritmo dado en <i>Reservoir Sampling with Random Sort</i> salvo en la generación de las claves de los elementos. El algoritmo equivale a asignar a cada elemento una clave donde es el número aleatorio y se seleccionan los elementos con las claves más grandes. De manera equivalente, una formulación más estable numéricamente de este algoritmo calcula las claves como y selecciona los elementos con las claves más pequeñas.
Algoritmo A-ExpJ El siguiente algoritmo es una versión más eficiente de A-Res, también proporcionado por Efraimidis y Spirakis:(* S es un flujo de elementos a muestrear S.Actual devuelve el elemento actual del flujo S.Peso devuelve el peso del elemento actual del flujo S.Next avanza el flujo a la siguiente posición El operador de potencia se representa mediante ^ min-priority-queue permite: Count -> número de elementos en la cola de prioridad Mínimo -> clave mínima de cualquier elemento de la cola de prioridad Extract-Min() -> Elimina el elemento con clave mínima Insert(Key, Item) -> Añade el elemento con la clave especificada *) ReservoirSampleWithJumps(S[1..?]) H := new min-priority-queue while S has data and H.Count < k r := random() ^ (1/S.Weight) // random() produce un número aleatorio uniforme en (0,1) H.Insert(r, S.Current) S.Next X := log(random()) / log(H.Minimum) // esta es la cantidad de peso que hay que saltar while S has data X := X - S.Weight if X <= 0 t := H.Minimum ^ S.Weight r := random(t, 1) ^ (1/S.Weight) // random(x, y) produce un número aleatorio uniforme en (x, y)
H.Extract-Min() H.Insert(r, S.Current)
X := log(random()) / log(H.Minimum) S.Next