Muestreo de embalses

El muestreo de reservorio es una familia de algoritmos aleatorios para seleccionar una muestra aleatoria simple , sin reemplazo, de k elementos de una población de tamaño desconocido n en una sola pasada. El tamaño de la población n es desconocido para el algoritmo y suele ser demasiado grande para que todos los n elementos quepan en la memoria principal . La población se revela al algoritmo con el tiempo, y este no puede consultar 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.

Supongamos que vemos una secuencia de elementos, uno a la vez. Queremos almacenar 10 elementos en memoria y seleccionarlos aleatoriamente de la secuencia. Si conocemos el número total de elementos n y podemos acceder a ellos arbitrariamente, la solución es sencilla: seleccionar 10 índices distintos i entre 1 y n con igual probabilidad y conservar el i -ésimo elemento. El problema es que no siempre conocemos el valor exacto de n de antemano.

Jeffrey Vitter creó un algoritmo sencillo y popular, pero lento, llamado Algoritmo R. ^{[ 1 ]}

Inicializar un array${\displaystyle R}$indexado desde${\displaystyle 1}$a${\displaystyle k}$, que contiene los primeros k elementos de la entrada${\displaystyle x_{1},...,x_{k}}$Este es el embalse .

Para cada nueva entrada${\displaystyle x_{i}}$, generar un número aleatorio j uniformemente en${\displaystyle \{1,...,i\}}$. Si${\displaystyle j\in \{1,...,k\}}$, luego establece${\displaystyle R[j]:=x_{i}.}$De lo contrario, deséchelo.${\displaystyle x_{i}}$.

Devolver${\displaystyle R}$una vez que se hayan procesado todas las entradas.

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

Aunque conceptualmente simple y fácil 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${\displaystyle O(n)}$Generar esta cantidad de aleatoriedad y el tiempo de ejecución lineal hace que el algoritmo sea innecesariamente lento si la población de entrada es grande.

Este es el algoritmo R, implementado de la siguiente manera:

(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // llena el array del reservorio para i := 1 a k R [ i ] := S [ i ] fin// Reemplazar elementos con probabilidad decreciente gradualmente para i := k + 1 hasta n (* randomInteger(a, b) genera un entero uniforme del rango inclusivo {a, ..., b} *) j := randomInteger ( 1 , i ) si j <= k R [ j ] := S [ i ] fin fin fin

Si generamos${\displaystyle n}$números aleatorios${\displaystyle u_{1},...,u_{n}\sim U[0,1]}$independientemente, entonces los índices del más pequeño${\displaystyle k}$de ellos es una muestra uniforme de la${\displaystyle k}$-subconjuntos de${\displaystyle \{1,...,n\}}$.

El proceso se puede realizar sin saberlo${\displaystyle n}$:

Conserva el más pequeño${\displaystyle k}$de${\displaystyle u_{1},...,u_{i}}$que se ha visto hasta ahora, así como${\displaystyle w_{i}}$, el índice del mayor entre ellos. Para cada nuevo${\displaystyle u_{i+1}}$, compáralo con${\displaystyle u_{w_{i}}}$. Si${\ Displaystyle u_ {i+1} <u_ {w_ {i}}}$luego deséchelo${\displaystyle u_{w_{i}}}$, almacenar${\displaystyle u_{i+1}}$y establecer${\displaystyle w_{i+1}}$ser el índice del mayor entre ellos. De lo contrario, descartar${\displaystyle u_{i+1}}$y establecer${\displaystyle w_{i+1}=w_{i}}$.

Ahora combine esto con el flujo de entradas${\displaystyle x_{1},...,x_{n}}$Cada vez que alguien${\displaystyle u_{i}}$Si se acepta, almacene el correspondiente${\displaystyle x_{i}}$Cada vez que alguien${\displaystyle u_{i}}$se descarta, deseche el correspondiente${\displaystyle x_{i}}$.

Este algoritmo aún necesita${\displaystyle O(n)}$números aleatorios, tomando así${\displaystyle O(n)}$tiempo. Pero se puede simplificar.

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

Segunda simplificación: no es necesario recordar toda la matriz de los más pequeños.${\displaystyle k}$de${\displaystyle u_{1},...,u_{i}}$eso es lo que se ha visto hasta ahora, pero simplemente${\displaystyle w}$, la más grande de ellas. Esto se basa en tres observaciones:

• Cada vez que hay algo nuevo${\displaystyle x_{i+1}}$Si se selecciona una entrada para ser almacenada, se descarta una entrada aleatoria uniforme en el almacenamiento.
• ${\displaystyle u_{i+1}\sim U[0,w]}$
• ${\displaystyle w_{i+1}}$tiene la misma distribución que${\displaystyle \max\{u_{1},...,u_{k}\}}$donde todos${\displaystyle u_{1},...,u_{k}\sim U[0,w]}$de forma independiente. Esto se puede muestrear primero mediante muestreo.${\displaystyle u\sim U[0,1]}$, luego tomando${\displaystyle w\cdot u^{\frac {1}{k}}}$.

Este es el algoritmo L , ^{[ 2 ]} que se implementa de la siguiente manera:

(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) // llena el array del reservorio para i = 1 a k R [ i ] := S [ i ] fin(* random() genera un número aleatorio uniforme (0,1) *) W := exp ( log ( random ()) / k )mientras i <= n i := i + floor ( log ( random ()) / log ( 1 - W )) + 1 si i <= n (* reemplazar un elemento aleatorio del depósito con el elemento i *) R [ randomInteger ( 1 , k )] := S [ i ] // índice aleatorio entre 1 y k, inclusive W := W * exp ( log ( random ()) / k ) fin fin fin

Este algoritmo calcula tres números aleatorios para cada elemento que pasa a formar parte del reservorio y no dedica tiempo a los elementos que no lo hacen. Por lo tanto, su tiempo de ejecución esperado es:${\displaystyle O(k(1+\log(n/k)))}$, ^{[ 2 ]} que es óptimo. ^{[ 1 ]} Al mismo tiempo, es sencillo de implementar de manera eficiente y no depende de desviaciones aleatorias de distribuciones exóticas o difíciles de calcular.

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. ^{[ 3 ]} Un muestreo de reservorio simple mantiene así los k elementos con los valores asociados más grandes actualmente en una cola de prioridad .

(*  S es un flujo de elementos para muestrear  S.Current devuelve el elemento actual en el flujo  S.Next avanza el flujo a la siguiente posición  min-priority-queue admite:  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 la clave mínima  Insert(key, Item) -> Agrega el elemento con la clave especificada *) ReservoirSample ( S [ 1 .. ? ]) H := nueva min - priority - queue mientras S tenga datos r := random () // aleatorio uniforme entre 0 y 1, exclusivo si H . Count < k H . Insert ( r , S . Current ) else // conserva k elementos con las claves asociadas más grandes si r > H . Minimum H . Extract - Min () H . Insert ( r , S . Current ) end S . Next end devuelve los elementos en H end

El tiempo de ejecución previsto de este algoritmo es${\displaystyle O(n+k\log k\log(n/k))}$Y es relevante principalmente porque se puede extender fácilmente a artículos con peso.

Los métodos presentados en las secciones anteriores no permiten obtener probabilidades de inclusión fijas a priori. Algunas aplicaciones requieren que las probabilidades de muestreo de los elementos se ajusten a los pesos asociados a cada elemento. Por ejemplo, podría ser necesario muestrear consultas en un motor de búsqueda con un peso igual al número de veces que se realizaron, de modo que la muestra pueda analizarse para determinar su impacto general en la experiencia del usuario. Sea el peso del elemento i .${\displaystyle w_{i}}$y la suma de todos los pesos sea W. Hay dos maneras de interpretar los pesos asignados a cada elemento del conjunto: ^{[ 4 ]}

1. En cada ronda, la probabilidad de que cada elemento no seleccionado sea seleccionado en esa ronda es proporcional a su peso en relación con los pesos de todos los elementos no seleccionados. Si X es la muestra actual, entonces la probabilidad de que un elemento sea seleccionado es proporcional a su peso en relación con los pesos de todos los elementos no seleccionados.${\displaystyle i\notin X}$ser seleccionado en la ronda actual es${\displaystyle \textstyle w_{i}/(W-\sum _{j\in X}{w_{j}})}$.
2. La probabilidad de que cada elemento se incluya en la muestra aleatoria es proporcional a su peso relativo, es decir,${\displaystyle w_{i}/W}$No es posible lograrlo cuando${\displaystyle k=n}$, puesto que cada elemento se incluye entonces con una probabilidad de 1.

El siguiente algoritmo fue proporcionado por Efraimidis y Spirakis que utiliza la interpretación 1: ^{[ 5 ]}

(*  S es un flujo de elementos para muestrear  S.Current devuelve el elemento actual en el flujo  S.Weight devuelve el peso del elemento actual en el flujo  S.Next avanza el flujo a la siguiente posición  El operador de potencia está representado por ^  min-priority-queue admite:  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 la clave mínima  Insert(key, Item) -> Agrega el elemento con la clave especificada *) ReservoirSample ( S [ 1 .. ? ]) H := nueva min - priority - queue mientras S tiene datos r := random () ^ ( 1 / S . Weight ) // random() produce un número aleatorio uniforme en (0,1) si H . Count < k H . Insert ( r , S . Current ) else // conserva k elementos con las claves asociadas más grandes si r > H . Minimum H . Extract - Min () H . Insert ( r , S . Current ) end end S . A continuación , devuelva los artículos al final H.

Este algoritmo es idéntico al algoritmo presentado en Reservoir Sampling with Random Sort, excepto por la generación de las claves de los elementos. El algoritmo es equivalente a asignar una clave a cada elemento.${\displaystyle r^{1/w_{i}}}$donde r es el número aleatorio y luego seleccionando los k elementos con las claves más grandes. De forma equivalente, una formulación numéricamente más estable de este algoritmo calcula las claves como${\displaystyle -\ln(r)/w_{i}}$y seleccionar los k elementos con las claves más pequeñas . ^{[ 6 ]}

El siguiente algoritmo es una versión más eficiente de A-Res , también proporcionada por Efraimidis y Spirakis: ^{[ 5 ]}

(*  S es un flujo de elementos para muestrear  S.Current devuelve el elemento actual en el flujo  S.Weight devuelve el peso del elemento actual en el flujo  S.Next avanza el flujo a la siguiente posición  El operador de potencia está representado por ^  min-priority-queue admite:  Count -> número de elementos en la cola de prioridad  Minimum -> clave mínima de cualquier elemento en la cola de prioridad  Extract-Min() -> Elimina el elemento con la clave mínima  Insert(Key, Item) -> Agrega el elemento con la clave especificada *) ReservoirSampleWithJumps ( S [ 1 .. ? ]) H := nueva min - priority - queue mientras S tiene datos y H . Count < k r := random () ^ ( 1 / S . Weight ) // random() produce un número aleatorio uniforme en (0,1) H . Insert ( r , S . Current ) S . Siguiente fin X := log ( aleatorio ()) / log ( H . Mínimo ) // esta es la cantidad de peso que se debe saltar mientras S tiene datos X := X - S . Peso si X <= 0 t := H . Mínimo ^ S . Peso r := aleatorio ( t , 1 ) ^ ( 1 / S . Peso ) // aleatorio(x, y) produce un número aleatorio uniforme en (x, y) H . Extraer - Mínimo () H . Insertar ( r , S . Actual )X := log ( aleatorio ()) / log ( H . Mínimo ) fin S . Siguiente fin devolver elementos en H fin

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

Advertencia: la siguiente descripción es incorrecta; consulte el artículo original de Chao y la discusión aquí .

El siguiente algoritmo fue dado por MT Chao usa la interpretación 2: ^{[ 7 ]} y Tillé (2006). ^{[ 8 ]}

(*  S tiene elementos para muestrear, R contendrá el resultado  S[i].Weight contiene el peso para cada elemento *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum := 0 // llenar el array del reservorio para i := 1 a k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Weight fin para i := k + 1 a n WSum := WSum + S [ i ] . Weight p := S [ i ] . Weight / WSum // probabilidad para este elemento j := random () ; // aleatorio uniforme entre 0 y 1 si j <= p // seleccionar elemento según la probabilidad R [ randomInteger ( 1 , k )] := S [ i ] // selección uniforme en el reservorio para reemplazo fin fin fin

Para cada elemento, se calcula su peso relativo y se utiliza para decidir aleatoriamente si se añadirá al depósito. Si se selecciona el elemento, se elige uniformemente uno de los elementos existentes en el depósito y se reemplaza por el nuevo. La clave está en 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.

Nótese que Chao no especifica cómo muestrear los primeros k elementos. Simplemente asume que tenemos alguna otra forma de seleccionarlos 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 instante A ; tal que su probabilidad de inclusión de primer orden de X_t es π(k; i) ".

De forma similar a otros algoritmos, es posible calcular un peso aleatorio jy restar los valores de masa de probabilidad de los elementos, omitiéndolos mientras j > 0, reduciendo así la cantidad de números aleatorios que deben generarse. ^{[ 4 ]}

(*  S tiene elementos para muestrear, R contendrá el resultado  S[i].Weight contiene el peso para cada elemento *) WeightedReservoir - Chao ( S [ 1 .. n ] , R [ 1 .. k ]) WSum := 0 // llenar el arreglo del reservorio para i := 1 a k R [ i ] := S [ i ] WSum := WSum + S [ i ] . Weight end j := random () // uniformemente aleatorio entre 0 y 1 pNone := 1 // probabilidad de que no se haya seleccionado ningún elemento hasta ahora (en este salto) para i := k + 1 a n WSum := WSum + S [ i ] . Weight p := S [ i ] . Peso / WSum // probabilidad para este elemento j -= p * pNone pNone := pNone * ( 1 - p ) si j <= 0 R [ randomInteger ( 1 , k )] := S [ i ] //selección uniforme en el reservorio para reemplazo j = random () pNone := 1 fin fin fin

En las aplicaciones de aprendizaje automático , la equidad es un factor crítico, especialmente en escenarios donde los flujos de datos presentan desequilibrio de clases. Para abordar este problema, Nikoloutsopoulos, Titsias y Koutsopoulos propusieron el algoritmo de muestreo de reservorio de Kullback-Leibler (KLRS) como solución a los desafíos del aprendizaje continuo, donde los modelos deben aprender de forma incremental a partir de un flujo de datos continuo.

El algoritmo KLRS se diseñó para crear una política flexible que ajuste los porcentajes de clase en el búfer a una distribución objetivo, empleando técnicas de muestreo de reservorio. Esto se logra minimizando la divergencia de Kullback-Leibler (KL) entre la distribución actual del búfer y la distribución objetivo deseada.

KLRS generaliza métodos anteriores como el muestreo de embalses y el muestreo de embalses con equilibrio de clases, como lo verifican los experimentos que utilizan intervalos de confianza, lo que demuestra su mayor aplicabilidad y su rendimiento mejorado.

El algoritmo KLRS funciona manteniendo un búfer de tamaño y actualizando su contenido a medida que llegan nuevos puntos de datos en un flujo. A continuación se muestra el pseudocódigo del algoritmo KLRS:

KLRS ( Flujo , Tamaño del búfer M , Distribución objetivo ) Entrada : * Flujo ( puntos de datos ( x , y ) que llegan secuencialmente ) * Tamaño del búfer M * Distribución objetivo ( distribución de clase deseada en el búfer )Salida : Búfer actualizado manteniendo la distribución objetivo .Inicializa el búfer M con los primeros M puntos de datos del flujo . Para t = M + 1 a ∞ : - Actualiza los contadores del flujo para calcular n_ {t+1} . - Calcula la distribución objetivo p_ {t+1} . - Para cada clase k en el búfer : - Simula la eliminación de una instancia de la clase k y la adición de ( x_t , y_t ) . - Calcula la divergencia KL v_k entre p_ {t+1} y la distribución del búfer modificada . - Selecciona la clase k * con el mínimo v_k . - Si k * = y_t : - Genera un número aleatorio r en [ 1 , n_ {t+1} , y_t ] . - Si r ≤ m_ {t, y_t} , - reemplaza una instancia aleatoria de la clase y_t en el búfer con ( x_t , y_t ) . - De lo contrario , reemplace una instancia aleatoria de la clase seleccionada k * en el búfer con ( x_t , y_t ) . - Actualice los contadores del búfer m_ {t+1}].  - Actualice el conjunto de clases C_{t+1} := unique ( C_t ∪ {y_t} ) .

Supongamos que se quisiera extraer k cartas al azar de una baraja. Un enfoque natural sería barajar la baraja y luego tomar las k primeras cartas. En el caso general, la barajada también debe funcionar incluso si no se conoce de antemano el número de cartas en la baraja, una condición que cumple la versión de adentro hacia afuera de la barajada de Fisher-Yates : ^{[ 9 ]}

(* S contiene la entrada, R contendrá la permutación de salida *) Barajar ( S [ 1 .. n ] , R [ 1 .. n ]) R [ 1 ] := S [ 1 ] para i desde 2 hasta n hacer j := randomInteger ( 1 , i ) // rango inclusivo R [ i ] := R [ j ] R [ j ] := S [ i ] fin fin

Nótese que, si bien el resto de las cartas se barajan, solo las primeras k son importantes en este contexto. Por lo tanto, el arreglo R solo necesita registrar las cartas en las primeras k posiciones durante el barajado, lo que reduce la cantidad de memoria necesaria. Al truncar R a una longitud k , el algoritmo se modifica en consecuencia:

(* S tiene elementos para muestrear, R contendrá el resultado *) ReservoirSample ( S [ 1 .. n ] , R [ 1 .. k ]) R [ 1 ] := S [ 1 ] para i desde 2 hasta k hacer j := randomInteger ( 1 , i ) // rango inclusivo R [ i ] := R [ j ] R [ j ] := S [ i ] fin para i desde k + 1 hasta n hacer j := randomInteger ( 1 , i ) // rango inclusivo si ( j <= k ) R [ j ] := S [ i ] fin fin fin

Dado que el orden de las primeras k cartas es irrelevante, se puede eliminar el primer bucle y R puede inicializarse con los primeros k elementos de la entrada. Esto da como resultado el algoritmo R.

El muestreo de reservorio parte del supuesto de que la muestra deseada cabe en la memoria principal , lo que a menudo implica que k es una constante independiente de n . En aplicaciones donde nos gustaría seleccionar un subconjunto grande de la lista de entrada (por ejemplo, un tercio, es decir)${\displaystyle k=n/3}$), es necesario adoptar otros métodos. Se han propuesto implementaciones distribuidas para este problema. ^{[ 10 ]}