algoritmo eficiente para seleccionar aleatoriamente elementos con frecuencia

Question

Dada una matriz de n pares de palabras de frecuencia:

[ (w0, f0), (w1, f1), ..., (wn-1, fn-1) ]

donde wi es una palabra, fi es un frequencey número entero, y la suma de las frecuencias ∑fi = m,

Quiero usar un generador de números pseudoaleatorios (pRNG) para seleccionar p palabras de modo que la probabilidad de seleccionar cualquier palabra sea proporcional a su frecuencia:

P(wi = wjk) = P(i = jk) = fi/m

(Nota: esto es la selección con el reemplazo, por lo que la misma palabra podría ser elegido cada vez).

Yo he llegado con tres algoritmos hasta ahora:

1. crear una matriz de tamaño m, y rellenarla por lo que las primeras entradas son f0w0, los próximos f1 entradas son w1, etc. , por lo que las últimas entradas fp-1 son wp-1.

   [ w0, ..., w0, w1,..., w1, ..., wp-1, ..., wp-1 ]

   Luego use el pRNG para seleccionar los índices p en el rango 0...m-1, e informe las palabras almacenadas en esos índices.
   Esto toma O(n + m + p) trabajo, que no es genial, ya que m puede ser mucho más grande que n.

2. Paso a través de la matriz de entrada una vez, el cálculo de

   mi = ∑h≤ifh = mi-1 + fi

   y después de calcular mi, utilice el PRNG para generar un número xk en el intervalo 0...mi-1 para cada k en 0...p-1 y seleccione wi para wjk (posiblemente sustituir el valor actual de wjk) si xk < fi.
   Esto requiere O(n + np) trabajo.

3. Compute mi como en el algoritmo 2, y generar la siguiente matriz en n palabra de frecuencia parcial de suma triplica:

   [ (w0, f0, m0), (w1, f1, m1), ..., (wn-1, fn-1, mn-1) ]

   y luego, para cada k en 0...p-1, utilice el PRNG para generar un número xk en el intervalo 0...m-1 luego haz una búsqueda binaria en la matriz de tripletas para encontrar el i st mi-fi ≤ xk < mi, y seleccione wi para wjk.
   Esto requiere O(n + p log n) trabajo.

Mi pregunta es: ¿Existe un algoritmo más eficiente que puedo utilizar para esto, o se trata tan bueno como se pone?

Answer 1

Ok, he encontrado otro algoritmo: the alias method (también mencionado in this answer). Básicamente se crea una partición del espacio de probabilidad tal que:

• Hay n particiones, todas de la misma anchura r S.T. nr = m.
• cada partición contiene dos palabras en alguna relación (que se almacena con la partición).
• para cada palabra wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Puesto que todas las particiones son del mismo tamaño, seleccionar qué partición se puede hacer de trabajo constante (recoger un índice de 0...n-1 al azar), y la relación de la partición puede entonces ser utilizado para seleccionar qué palabra se usa en el trabajo constante (compare un número pRNGed con la relación entre las dos palabras). Esto significa que las selecciones p se pueden realizar en el trabajo O(p), dada una partición de este tipo.

La razón por la que existe tal partición es que existe una palabra wi s.t. fi < r, si y solo si existe una palabra wi' s.t. fi' > r, ya que r es el promedio de las frecuencias.

dado un par tal wi y wi' podemos reemplazarlos con un pseudo-palabra w'i de frecuencia f'i = r (que representa wi con probabilidad fi/r y wi' con probabilidad 1 - fi/r) y una nueva palabra w'i' de frecuencia ajustada f'i' = fi' - (r - fi) respectivamente. La frecuencia promedio de todas las palabras seguirá siendo r, y la regla del párrafo anterior aún se aplica. Como la pseudopalabra tiene frecuencia ry está compuesta por dos palabras con la frecuencia ≠ r, sabemos que si repetimos este proceso, nunca haremos una pseudopalabra a partir de una pseudopalabra, y dicha iteración debe terminar con una secuencia de n pseudo palabras que son la partición deseada.

Para construir esta partición en O(n) tiempo,

• pasar por la lista de las palabras de una vez, la construcción de dos listas:
  • una de las palabras con frecuencia ≤ r
  • una de las palabras con frecuencia > r
• y luego saca una palabra de la primera lis t
  • si su frecuencia = r, a continuación, lo hacen en una partición de un elemento
  • de otra manera, tire de una palabra de la otra lista, y lo utilizan para llenar una partición de dos palabras. Luego, coloque la segunda palabra en la primera o segunda lista según su frecuencia ajustada.

realidad Esto todavía funciona si el número de particiones q > n (sólo hay que probar de otra manera). Si desea asegurarse de que r es integral, y no puede encontrar fácilmente un factor q de m s.t. q > n, puede rellenar todas las frecuencias por un factor de n, entonces f'i = nfi, que actualiza m' = mn y establece r' = m cuando q = n.

En cualquier caso, este algoritmo solo toma el trabajo O(n + p), que tengo que pensar es óptimo.

En Ruby:

def weighted_sample_with_replacement(input, p) 
    n = input.size 
    m = input.inject(0) { |sum,(word,freq)| sum + freq } 

    # find the words with frequency lesser and greater than average 
    lessers, greaters = input.map do |word,freq| 
         # pad the frequency so we can keep it integral 
         # when subdivided 
         [ word, freq*n ] 
         end.partition do |word,adj_freq| 
         adj_freq <= m 
         end 

    partitions = Array.new(n) do 
    word, adj_freq = lessers.shift 

    other_word = if adj_freq < m 
        # use part of another word's frequency to pad 
        # out the partition 
        other_word, other_adj_freq = greaters.shift 
        other_adj_freq -= (m - adj_freq) 
        (other_adj_freq <= m ? lessers : greaters) << [ other_word, other_adj_freq ] 
        other_word 
       end 

    [ word, other_word , adj_freq ] 
    end 

    (0...p).map do 
    # pick a partition at random 
    word, other_word, adj_freq = partitions[ rand(n) ] 
    # select the first word in the partition with appropriate 
    # probability 
    if rand(m) < adj_freq 
     word 
    else 
     other_word 
    end 
    end 
end 

Answer 2

Esto suena como la selección de ruleta, principalmente utilizada para el proceso de selección en algoritmos genéticos/evolutivos.

Look at Roulette Selection in Genetic Algorithms

Answer 3

podría crear la matriz de destino, a continuación, recorrer las palabras que determinan la probabilidad de que debe ser recogida, y sustituir las palabras en la matriz de acuerdo con un número aleatorio.

Para la primera palabra la probabilidad sería f/m (donde M _n = f + .. + f _n), es decir 100%, por lo todas las posiciones en el conjunto de destino se llenará con w .

Para las siguientes palabras, la probabilidad cae, y cuando llega a la última palabra, la matriz objetivo se llena con palabras escogidas al azar según la frecuencia.

código de ejemplo de C#:

public class WordFrequency { 

    public string Word { get; private set; } 
    public int Frequency { get; private set; } 

    public WordFrequency(string word, int frequency) { 
     Word = word; 
     Frequency = frequency; 
    } 

} 

WordFrequency[] words = new WordFrequency[] { 
    new WordFrequency("Hero", 80), 
    new WordFrequency("Monkey", 4), 
    new WordFrequency("Shoe", 13), 
    new WordFrequency("Highway", 3), 
}; 

int p = 7; 
string[] result = new string[p]; 
int sum = 0; 
Random rnd = new Random(); 
foreach (WordFrequency wf in words) { 
    sum += wf.Frequency; 
    for (int i = 0; i < p; i++) { 
     if (rnd.Next(sum) < wf.Frequency) { 
      result[i] = wf.Word; 
     } 
    } 
}