Algoritmo eficiente para seleccionar al azar los elementos con frecuencia

Question

Dado un array de n palabra-frecuencia de pares:

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

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

Quiero usar un pseudo-generador de números aleatorios (pRNG) para seleccionar p palabras wj0, wj1, ..., wjp-1 tal que la probabilidad de seleccionar cualquier palabra es proporcional a su frecuencia:

P(wyo = wjk) = P(i = jk) = fyo / m

(Nota: esta es la selección de 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 llenar así la primera f0 las entradas son w0, el siguiente f1 las entradas son w1, y así sucesivamente, por lo que el último fp-1 las entradas son wp-1.

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

   A continuación, utilice el pRNG para seleccionar p los índices en el rango 0...m-1, y el informe de las palabras almacenadas en los índices.
   Esto se lleva a O(n + m + p) el trabajo, que no es muy grande, ya que m puede ser mucho mayor que n.

2. El paso a través de la matriz de entrada una vez, la informática, la

   myo = ∑h≤ifh = mi-1 + fyo

   y después de la computación myo, utilice el pRNG para generar un número xk en el rango de 0...myo-1 para cada k en 0...p-1 y seleccione wyo para wjk (posiblemente sustituyendo el valor actual de wjk) si xk < fyo.
   Esto requiere O(n + np) trabajo.

3. Calcular myo como en el algoritmo 2, y generar la siguiente matriz en la palabra n-frecuencia-parcial-de la suma triples:

   [ (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 rango de 0...m-1 a continuación, hacer una búsqueda binaria en el conjunto de tripletas para encontrar la i s.t. myo-fyo ≤ xk < myo, y seleccione wyo para wjk.
   Esto requiere O(n + p log n) trabajo.

Mi pregunta es:Hay un algoritmo más eficiente que puedo utilizar para esto, o son estos tan bueno como se pone?

Answer 1

Ok, he encontrado otro algoritmo: el método alias (también mencionado en esta respuesta).Básicamente, se crea una partición de la probabilidad del espacio tales que:

• Hay n particiones, todas de la misma anchura r s.t. nr = m.
• cada partición contiene dos palabras en algunos ratio (que se almacena con la partición).
• para cada palabra wyo, fyo = ∑particiones t s.t wyo ∈ t r × ratio(t,wyo)

Desde todas las particiones del mismo tamaño, la selección de la partición puede hacerse en constante trabajo (elegir un índice de 0...n-1 al azar), y la partición de la relación puede entonces ser utilizado para seleccionar la palabra que se utiliza en el trabajo constante (comparar un pRNGed número con la relación entre las dos palabras).Por lo que esto significa p las selecciones se pueden hacer en O(p) el trabajo, por ejemplo una partición.

La razón por la que tal partición existe es que no existe una palabra wyo s.t. fyo < r, si y sólo si existe una palabra wyo s.t. fyo > r, puesto que r es el promedio de las frecuencias.

Dado un par de wyo y wyo podemos sustituirlos con un pseudo-palabra w'yo de frecuencia f'yo = r (que representa wyo con una probabilidad de fyo/r y wyo con una probabilidad de 1 - fyo/r) y una nueva palabra w'yo de frecuencia ajustado f'yo = fyo - (r - fyo) respectivamente.La frecuencia media de todas las palabras todavía será r, y la regla del párrafo anterior, se aplica todavía.Desde el pseudo-palabra ha de frecuencia r y se compone de dos palabras con frecuencia ≠ r, sabemos que si repetimos este proceso, nunca vamos a hacer una pseudo-palabra de un pseudo-palabra, y tal iteración debe terminar con una secuencia de n pseudo-palabras que son la partición deseada.

Para la construcción de esta partición en O(n) tiempo,

• ir a través de la lista de palabras una vez, la construcción de dos listas:
  • una de las palabras con frecuencia ≤ r
  • una de las palabras con frecuencia > r
• a continuación, tire de una de las palabras de la primera lista
  • si su frecuencia = r, entonces la convierten en un elemento de la partición
  • de lo contrario, sacar una palabra de la otra lista, y usar para llenar una de dos palabras de la partición.A continuación, poner la segunda palabra de nuevo en el primer o el segundo de la lista de acuerdo a su frecuencia ajustado.

En realidad, esto todavía funciona si el número de particiones q > n (sólo tienes que demostrarlo de otra forma).Si desea asegurarse de que r es integral, y no puede encontrar fácilmente un factor de q de m s.t. q > n, puede almohadilla de todas las frecuencias por un factor de n, por lo que f'yo = nfyo, que las actualizaciones de m' = mn y establece r' = m cuando q = n.

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

En rubí:

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 la rueda de ruleta, utilizado principalmente para el proceso de selección en algoritmos genéticos / evolutivas.

Selección ruleta en Algoritmos Genéticos

Answer 3

Se puede 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.

En la primera palabra la probabilidad habría f ₀ / m ₀ (donde m _n = f ₀ + .. + f _n ), es decir 100%, por lo que todas las posiciones en la matriz de destino estaría lleno de w ₀ .

Para las siguientes palabras la probabilidad de caídas, y al llegar a la última palabra de la matriz de destino está lleno de palabras escogidas al azar accoding a la frecuencia.

Ejemplo de código en 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;
        }
    }
}