algoritmo efficiente per selezionare casualmente oggetti con frequenza

Question

Dato un array di n coppie word frequenza:

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

dove wi è una parola, fi è un frequencey intero, e la somma delle frequenze ∑fi = m,

Desidero utilizzare un generatore di numeri pseudo casuali (pRNG) per selezionare p parole wj0, wj1, ..., wjp-1 tali che la probabilità di selezionare qualsiasi parola sia proporzionale alla sua frequenza:

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

(nota, questa è la selezione con sostituzione, per cui la stessa parola potrebbe essere scelto ogni volta).

mi è venuta in mente tre algoritmi finora:

1. creare un array di dimensioni m, e popolare così le prime voci sono f0w0, i prossimi f1 voci sono w1, e così via , quindi le ultime voci fp-1 sono wp-1.

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

   Quindi utilizzare il pRNG per selezionare gli indici p nell'intervallo 0...m-1 e segnalare le parole memorizzate in tali indici.
   Questo richiede lavoro O(n + m + p), che non è eccezionale, dal momento che m può essere molto più grande di n.

2. ciclo attraverso l'array di input volta, calcolando

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

   e dopo aver calcolato mi, utilizzare il PRNG per generare un numero xk nell'intervallo 0...mi-1 per ogni k in 0...p-1 e selezionare wi per wjk (eventualmente sostituendo il valore corrente di wjk) se xk < fi.
   Ciò richiede il lavoro O(n + np).

3. Compute mi come nell'algoritmo 2, e generare il seguente matrice su n word-frequenza parziale somma triplica:

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

   e quindi, per ogni k in 0...p-1, utilizzare il PRNG per generare un numero xk nell'intervallo 0...m-1 quindi fai una ricerca binaria sulla serie di triple per trovare il i st mi-fi ≤ xk < mi e selezionare wi per wjk.
   Ciò richiede il lavoro O(n + p log n).

La mia domanda è: Esiste un algoritmo più efficiente posso usare per questo, o sono questi Qualcosa è cambiato?

Answer 1

Ok, ho trovato un altro algoritmo: the alias method (menzionato anche in this answer). In sostanza si crea una partizione dello spazio di probabilità in modo tale che:

• ci sono n partizioni, tutte della stessa larghezza r S.T. nr = m.
• ogni partizione contiene due parole in un rapporto (che viene memorizzato con la partizione).
• per ogni parola wi, fi = ∑partitions t s.t wi ∈ t r × ratio(t,wi)

Poiché tutte le partizioni sono della stessa dimensione, selezionare quale partizione può essere realizzata in opera costante (scegliere un indice da 0...n-1 a caso), e il rapporto della partizione può quindi essere utilizzato per selezionare quale parola viene utilizzata in costante lavoro (confrontare un numero pRNGed con il rapporto tra le due parole). Quindi questo significa che le selezioni p possono essere eseguite nel lavoro , data tale partizione.

Il motivo per cui tale partizionamento esiste è che esiste una parola wi s.t. fi < r, se e solo se esiste una parola wi' s.t. fi' > r, poiché r è la media delle frequenze.

Dato un tale coppia wi e wi' possiamo sostituirli con uno pseudo-word w'i di frequenza f'i = r (che rappresenta wi con probabilità fi/r e wi' con probabilità 1 - fi/r) e una nuova parola w'i' di frequenza impostata f'i' = fi' - (r - fi) rispettivamente. La frequenza media di tutte le parole sarà ancora r, e la regola del paragrafo precedente si applica ancora. Poiché la pseudo-parola ha frequenza r ed è composta da due parole con frequenza ≠ r, sappiamo che se iteriamo questo processo, non creeremo mai una pseudo-parola da una pseudo-parola, e tale iterazione deve terminare con un sequenza di n pseudo parole che sono la partizione desiderata.

Per costruire questa partizione in O(n) tempo,

• passare attraverso la lista delle parole, una volta, la costruzione di due liste:
  • una delle parole con una frequenza ≤ r
  • una delle parole con le frequenza > r
• quindi tirare una parola dal primo t
  • se la sua frequenza = r, allora farne una partizione un elemento
  • altrimenti, tirare una parola dall'altro elenco, e utilizzarlo per compilare una partizione di due parole. Quindi rimetti la seconda parola nella prima o nella seconda lista in base alla frequenza regolata.

Questo in realtà funziona ancora, se il numero di partizioni q > n (dovete solo per dimostrare in modo diverso). Se vuoi assicurarti che r sia integrale, non puoi trovare facilmente un fattore q di m s.t. q > n, è possibile eseguire il rilievo di tutte le frequenze per un fattore di n, quindi f'i = nfi, che aggiorna m' = mn e imposta r' = m quando q = n.

In ogni caso, questo algoritmo richiede solo il lavoro O(n + p), che devo pensare sia ottimale.

In 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

Questo suona come selezione roulette, utilizzato principalmente per il processo di selezione in algoritmi genetici/evolutivo.

Osservare Roulette Selection in Genetic Algorithms

Answer 3

Si potrebbe creare la matrice di destinazione, quindi scorrere le parole che determinano la probabilità che esso debba essere raccolto, e sostituire le parole nella matrice secondo un numero casuale.

Per la prima parola della probabilità sarebbe f/m (dove m _n = f 0 + .. + f _n), cioè il 100%, in modo tutte le posizioni la matrice di destinazione verrebbe riempita con w .

Per le seguenti parole, la probabilità diminuisce e quando si raggiunge l'ultima parola, l'array di destinazione viene riempito con parole selezionate casualmente che si accodono alla frequenza.

Esempio di codice in 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; 
     } 
    } 
}