Muestreo de depósito
# Muestreo de depósito

El muestreo de depósito es una familia de algoritmos aleatorios para elegir una muestra aleatoria simple, sin reemplazo, de k elementos de una población de tamaño no conocido n en un solo paso por los elementos. El algoritmo no conoce el tamaño de la población n y, por lo general, es demasiado grande para muestrearla en su totalidad y que todos los n 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 n y podemos acceder a los elementos arbitrariamente; por lo tanto, la solución es fácil: se seleccionan 10 índices distintos i entre 1 y n con la misma probabilidad y se conservan los i -ésimos elementos. El problema es que no siempre conocemos el n exacto de antemano.

## Simple: algoritmo R

Jeffrey Vitter creó un algoritmo simple y popular pero lento, el algoritmo R.

   Inicialice una matriz $R$ indexada de $1$ a $k$, que contenga los primeros k elementos de la entrada $x_{1},...,x_{k}$ . Este es el depósito .
   Por cada nueva entrada $x_{i}$, genere un número aleatorio j uniformemente en $\{1,...,i\}$ . Si $j\in \{1,...,k\}$, haga que $R[j]:=x_{i}$, de lo contrario, descarte $x_{i}$ .
   Devuelva $R$ una vez procesadas todas las entradas.

Este algoritmo funciona por inducción en $i\geq k$ .

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 $x_{i+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 $x_r$ ∈ ${x_1,…,$ $x_i}$ 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 $x_{i+1}$ (es decir, de que $x_r$ no sea sustituida por $x_{i+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 $x_r$ en particular sea sustituido por $x_{i+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 $O(n)$. 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 *)

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$ números al azar $u_{1},...,u_{n}\sim U[0,1]$ independientemente, los índices de los $k$ más pequeños es una muestra uniforme de los subconjuntos de k de $\{1,...,n\}$ .

El proceso se puede hacer sin conocer $n$:

   Conserve los $k$ más pequeños de $u_{1},...,u_{i}$ vistos hasta ahora, así como $w_{i}$, el índice de los más grandes entre ellos. Para cada $u_{i+1}$ nuevo compare con $u_{w_{i}}$. Si $u_{i+1}<u_{w_{i}}$, descarte $u_{w_{i}}$, almacene $u_{i+1}$ y establezca $w_{i+1}$ como el índice del mayor entre ellos. De lo contrario, descarte $u_{i+1}$ y haga $w_{i+1}=w_{i}$ .

Ahora combine esto con el flujo de entradas $x_{1},...,x_{n}$ . Cada vez que alguna $u_{i}$ se acepta, guarde el $x_{i}$ correspondiente. Cada vez que alguna $u_{i}$ se descarta, descarte el $x_{i}$ correspondiente.

Este algoritmo todavía necesita $O(n)$ números aleatorios y toma un tiempo de $O(n)$. Pero se puede simplificar.

Primera simplificación: no es necesario probar $u_{i+1},u_{i+2},...$ nuevos uno por uno, ya que la probabilidad de que la siguiente aceptación suceda en $u_{i+l}$ es $(1-u_{w_{i}})^{l-1}-(1-u_{w_{i}})^{l}$, es decir, el intervalo $l$ de aceptación sigue una distribución geométrica.

Segunda simplificación: no es necesario recordar todo el arreglo de los $k$ más pequeños de $u_{1},...,u_{i}$ que se ha visto hasta ahora, sino simplemente $w$, el mayor de ellos. Esto se basa en tres observaciones:

* Cada vez que un $x_{i+1}$ nuevo se selecciona para ir al depósito, se descarta una entrada uniformemente aleatoria en el almacenamiento.
* $u_{i+1}\sim U[0,w]$
* $w_{i+1}$ tiene la misma distribución que $\max\{u_{1},...,u_{k}\}$, donde todos $u_{1},...,u_{k}\sim U[0,w]$ de modo independiente. Esto puede ser muestreado con la primera toma de $u\sim U[0,1]$muestras y tomando $w\cdot u^{\frac {1}{k}}$ .

Este es el algoritmo L, que se implementa así:

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 $O(k(1+\log(n/k)))$, 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 k 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 k elementos con los valores asociados más grandes en el momento en una cola de prioridad .

El tiempo de ejecución esperado de este algoritmo es $O(n+k\log k\log(n/k))$ 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 i $w_{i}$ y la suma de todos los pesos sea W, 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 X es la muestra actual, la probabilidad de un elemento $i\notin X$ de ser seleccionado en esa ronda es $\textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})$ .
* La probabilidad de que cada elemento sea incluido en la muestra aleatoria es proporcional a su peso relativo, es decir, $w_{i}/W$. Tenga en cuenta que esta interpretación podría no ser posible en algunos casos, por ejemplo cuando$k=n$.

### Algoritmo A-Res

El siguiente algoritmo fue desarrollado por Efraimidis y Spirakis que usan la interpretación 1:

Este 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 $r^{1/w_{i}}$ donde r es el número aleatorio y se seleccionan los k 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 $-\ln(r)/w_{i}$ y selecciona los elementos k 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:

Este algoritmo sigue las mismas propiedades matemáticas que se utilizan en A-Res, pero en vez de calcular la clave para cada elemento y verificar si ese elemento debe insertarse, calcula un salto exponencial al siguiente elemento que se insertará. Esto evita tener que crear variantes aleatorias para cada elemento, lo que puede resultar costoso. El número de variables aleatorias requeridas se reduce de $O(n)$ a $O(k\log(n/k))$, donde $k$ es el tamaño del depósito y $n$ es el número de elementos en la secuencia.

### Algoritmo A-Chao

El siguiente algoritmo fue desarrollado por MT Chao quien utiliza la interpretación 2:

Para cada elemento, se calcula el peso relativo y se usa para decidir aleatoriamente si el elemento se agregará al depósito. Si se selecciona el elemento, uno de los elementos existentes en el depósito se selecciona uniformemente y se reemplaza con el elemento nuevo. La clave aquí es que, si las probabilidades de todos los elementos en el depósito ya son proporcionales a sus pesos, al seleccionar uniformemente qué elemento reemplazar, las probabilidades de todos los elementos siguen siendo proporcionales a su peso después del reemplazo.

Tenga en cuenta que Chao no especifica cómo muestrear los primeros k elementos. Simplemente asume que tenemos alguna otra forma de recogerlos en proporción a su peso. Chao: «Supongamos que tenemos un plan de muestreo de tamaño fijo con respecto a S_k en el momento A ; tal que su probabilidad de inclusión de primer orden de X_t es π(k; i) ».

**Algoritmo A-Chao con saltos**

De modo similar a los otros algoritmos, se puede calcular un peso aleatorio j y restar los valores de masa de probabilidad de los elementos, haciéndolos a un lado; mientras que j > 0, reduciendo la cantidad de números aleatorios que deben generarse.

## Relación con el algoritmo de Fisher-Yates

Supongamos que se quiere tomar k cartas al azar de una baraja. Un método natural sería barajar las cartas y luego tomar las k cartas superiores. En el caso general, el barajado también debe funcionar incluso si el número de cartas no se conoce de antemano, una condición que se cumple con la versión de adentro hacia afuera del algoritmo Fisher-Yates :

Tenga en cuenta que aunque el resto de las cartas se barajan, solo las primeras k importan en el contexto presente. Por lo tanto, el arreglo R solo necesita rastrear las cartas en las primeras k posiciones mientras realiza el barajado, lo que reduce la cantidad de memoria necesaria. Truncando R a la longitud k, el algoritmo se modifica en consecuencia:

Dado que el orden de las primeras k cartas no importa, el primer bucle se puede eliminar y R se puede inicializar para ser los primeros k elementos de la entrada. Esto produce el algoritmo R.

## Propiedades estadísticas

La probabilidad de selección de los métodos de depósito se analiza en Chao (1982) y Tillé (2006). Mientras que la probabilidad de selección de primer orden es igual a $k/n$ (o, en el caso del procedimiento de Chao, a un conjunto arbitrario de probabilidades desiguales), las probabilidades de selección de segundo orden dependen del orden en que se clasifican los registros en el depósito original. El problema se resuelve con el método de muestreo de cubos de Deville y Tillé (2004).

## Limitaciones

El muestreo de depósito supone que la muestra deseada cabe en la memoria principal, lo que a menudo implica que k es una constante independiente de n. En las aplicaciones en las que nos gustaría seleccionar un gran subconjunto de la lista de entrada (digamos un tercero, es decir, $k=n/3$ ), es necesario adoptar otros métodos. Se han propuesto algunas implementaciones distribuidas para resolver este problema.

