Complexité de l'échantillonnage à partir du modèle de mélange

Question

J'ai un modèle où l'état j parmi les M états est choisi avec la probabilité p_j. La probabilité pourrait être n'importe quel nombre réel. Ceci spécifie un modèle de mélange sur les états M. Je peux accéder à p_j pour tout j en temps constant. Je veux faire un grand nombre (N) d'échantillons aléatoires. L'algorithme le plus évident est

1) Calculer la distribution de probabilité cumulative P_j = p_1 + p_2 + ... p_j. O (M)

2) Pour chaque échantillon, choisissez float aléatoire x dans [0,1]. O (N)

3) Pour chaque échantillon, choisir j tel que min (0, P_j-1) < x < = max (1, P_j). O (Nlog (M))

Donc la complexité asymptotique est O (Nlog (M)). Le facteur de N est évidemment inévitable, mais je m'interroge sur log (M). Est-il possible de battre ce facteur dans une mise en œuvre réaliste?

Answer 1

Je pense que vous pouvez faire mieux utiliser quelque chose comme l'algorithme suivant, ou tout autre sampler de distribution multinomiale raisonnable,

// Normalize p_j 
for j = 1 to M 
    p_hat[j] = p[j]/P_j 

// Place the draws from the mixture model in this array 
draws = []; 

// Sample until we have N iid samples 
cdf = 1.0; 
for (j = 1, remaining = N; j <= M && remaining > 0; j++) 
{ 
    // p_hat[j] is the probability of sampling item j and there 
    // are (N - count) items remaining to sample. This is just 
    // (N - count) Bernoulli trials, so draw from a 
    // Binomial(N - count, p_hat[j]/cdf) distribution to get the 
    // number of items  
    // 
    // Adjusting the probability by 1 - CDF ensures that *something* 
    // is sampled because p_hat[M]/cdf = p_hat[M]/p_hat[M] = 1.0 
    items = Binomial.sample(remaining, p_hat[j]/cdf); 
    remaining -= items; 
    cdf -= p_hat[j]; 

    for (k = 0; k < items; k++) 
     draws.push(sample_from_mixture_component(j))   
} 

Cela devrait prendre près de O (N) du temps, mais cela dépend de la façon efficace votre La distribution binomiale et les échantillonneurs de composants du modèle de mélange sont.