Muestreo determinístico de distribución discreta

Question

Estoy trabajando en una generalización de la Min-Hash algoritmo para permitir la comparación significativa de los valores ordenados tales como los números enteros. El núcleo truco es usar determinista de la aleatoriedad como un reemplazo para los hash funciones.

Sin embargo, para obtener esta cosa para trabajar necesito una manera determinista de la muestra de una distribución discreta. I. e. si en repetidas ocasiones que la extracción de muestras de una distribución discreta necesito para obtener el mismo conjunto de valores para cada llamada.

Las funciones de la biblioteca como sample de la lenguaR uso estándar algoritmos de toma de muestras que suelen utilizar el uniforme de muestreo, a partir de la distribución acumulativa. Por lo tanto, necesitan algún tipo de números pseudo-aleatorios. Por la siembra y el restablecimiento de este generador de números aleatorios antes de cada llamada, es posible cortar la aleatoriedad y hacer las cosas determinista. sample a continuación, se comporta como una función matemática.

Considere el siguiente ejemplo:

value:    a       b      c     d    e     f     g      h     i    j
prob:    0.070 0.0774 0.083 0.090 0.096 0.103 0.109 0.116 0.122 0.129

setSeed(1)
sample(value,5, prob, replace = TRUE)
>>> a, c, e, j, a
setSeed(1)
sample(value,5, prob, replace = TRUE)
>>> a, c, e, j, a

Sin embargo, en el caso de la distribución cambia un poco (he.e otro valor k se inserta) los valores devueltos de estas estándar algoritmos de toma de muestras a cambiar drásticamente.

setSeed(1)
sample(value, 5, prob, replace = TRUE)
>>> a, c, e, j, a
insert('k')
>>> value:    a     b     c     d    e     f     g      h     i     j    k
>>> prob:  0.062 0.068 0.073 0.079 0.085 0.090 0.096 0.102 0.107 0.113 0.119
setSeed(1)
sample(value,5, prob, replace = TRUE)
>>> b, d, f, k, b

Así, a pesar de la distribución cambia sólo ligeramente, el dibujado de la muestra cambiado ampliamente. Sin embargo, me gustaría ver un cambio menor, algo así como

>>> a, c, e, j, a   <-- initial sample from initial density
>>> a, c, k, j, a   <-- desired sample after small density change
>>> b, d, f, k, b   <-- actual sample after small density change

Una lenta pero trabajando algoritmo sería para 'simular' este muestreo mediante el uso de 10.000 contenedores. Cada bandeja contiene un único "valor". El número de contenedores de un cierto valor corresponde a la probabilidad de que el valor en la distribución. Dibujo a partir de esta simulación, a continuación, obras de dibujo enteros i de 1 a 10.000 y devolver el valor de la bandeja con número i. Si los contenedores se sustituye con otro valor, el de la muestra cambia sólo ligeramente, debido a que en cada llamada de la misma contenedores de ser seleccionado.

Así que los problemas con algoritmos estándar, es decir, que por lo general de ordenación reorganizar estos contenedores para obtener la aceleración. Sin embargo, eso no es posible en ese caso.

Es allí una manera de ejemplo de la distribución de la densidad de sí mismo mientras se asegura de que el cambio en el dibujado de la muestra es similar al cambio de la distribución?

Answer 1

De una manera general para generar secuencias similares para las distribuciones con probabilidades similares es la siguiente. Supongamos $A$ es un orden de alfabeto finito $(a,b,c,\ldots)$, con una distribución de probabilidad $p_A$. Para dibujar un valor al azar de $A$, generar un vector de independiente uniforme varia $\mathbf{U}=(U_a, U_b, U_c, \ldots)$. Si $U_a \le p_A(a)$, elija $a$. De lo contrario, de forma recursiva dibujar un valor en el resto de las letras $A^\prime = A-\{a\} = (b,c,\ldots)$ utilizando el vector $\mathbf{U}^\prime=(U_b, U_c, \ldots)$ y las probabilidades de $$p_{A^\prime}(b) = \frac{p_A(b)}{1-p_A(a)},\ p_{A^\prime}(c) = \frac{p_A(c)}{1-p_A(a)},$$ etc.

You can re-use the same vector $\mathbf{U}$ for any other distribution on $A$.

Using this method, the expected frequency with which the same letter would be drawn from distributions $p_A$ and $q_A$ is the frequency with which $a$ would be drawn from both distributions, equal to the smaller of $p_A(a)$ and $q_A(a)$, plus the expected frequency with which the same letter would be drawn from $(b,c,\ldots)$, conditional on $a$ not being drawn from either distribution.

This method is the best you can do by assigning each letter to its own connected interval. With additional work it's possible to make the two sequences agree even more frequently, but you would have to assign the extra letter "k" to a complicated subset of $(0,1]$.

---

Aquí es R código para generar n símbolos de un alfabeto con probabilidad de vectores prob.

s <- function(n, prob) {
  k <- length(prob)
  q <- prob / rev(cumsum(rev(prob)))
  u <- matrix(runif(n*k), nrow=k, byrow=TRUE) < q
  apply(u, 2, function(x) match(TRUE, x))
}

Vamos a generar muestras de tamaño 10,000 a partir de las distribuciones, como los de la pregunta. La salida muestra los primeros 60 extrae de cada uno, usando la misma a partir de la semilla. Ellos son muy similares.

prob <- c(75, 77, 83, 90, 96, 103, 109, 116, 122, 129, rep(0, 16))
prob.k <- prob
prob.k[11] <- 0.119/(1-0.119)*sum(prob)

seed <- 17
N <- 1e4
set.seed(seed); x <- letters[s(N, prob)]
set.seed(seed); x.k <- letters[s(N, prob.k)]

rbind(First=paste0(head(x, 60), collapse=""),
      Second=paste0(head(x.k, 60), collapse=""))

Aquí está:

First  "geifgefhiifafbhfhijgfcdiebjfjegajgggidghchhjjfgdjheicbhbjica"
Second "geifgefhiikafbhgiikifcdiibjfkjkakiggkdghchijjfgdkhhkkbhbkkcj"

Usted puede comprobar que las frecuencias reales están cerca de la intención de:

rbind(First=c(table(x), k=0), Second=table(x.k))

Esta salida es

         a   b   c   d   e    f    g    h    i    j    k
First  755 775 808 842 995 1068 1111 1184 1206 1256    0
Second 657 666 693 739 872  955  973 1056 1074 1144 1171

El grado de similitud (es decir, la proporción de tiempo en las dos secuencias se espera que de acuerdo) es fácilmente calculada de forma recursiva.

similarity <- function(x, y) {
  if (min(length(x), length(y)) == 0) return (0)
  a <- min(x[1], y[1])
  x.s <- sum(x[-1])
  y.s <- sum(y[-1])
  if (x.s > 0 & y.s > 0) {
    b <- max(x[1], y[1])
    x <- x[-1]/sum(x[-1])
    y <- y[-1]/sum(y[-1])
    b <- (1-b) * similarity(x, y)
  } else {
    b <- 0
  }
  return (a + b)
}
similarity(prob/sum(prob), prob.k/sum(prob.k))

La salida es

0.7568941

De hecho, en esta simulación, la frecuencia observada fue de cerca de que:

mean(x.k == x)

[1] 0.754