Сложность отбора проб из модели смеси - PullRequest
Новая
       29

Сложность отбора проб из модели смеси

1 голос
/ 11 октября 2010

У меня есть модель, в которой состояние j среди M состояний выбирается с вероятностью p_j. Вероятность может быть любым действительным числом. Это определяет модель смеси по M состояниям. Я могу получить доступ к p_j для всех j в постоянное время. Я хочу сделать большое количество (N) случайных выборок. Наиболее очевидный алгоритм -

1) Рассчитать совокупное распределение вероятностей P_j = p_1 + p_2 + ... p_j. O (M)

2) Для каждого образца выберите случайное число с плавающей точкой x в [0,1]. O (N)

3) Для каждой выборки выберите j так, чтобы min (0, P_j-1)

Таким образом, асимптотическая сложность равна O (Nlog (M)). Фактор N, очевидно, неизбежен, но меня интересует log (M). Можно ли превзойти этот фактор в реалистичной реализации?

1 Ответ

1 голос
/ 26 октября 2010

Я думаю, что вы можете добиться большего успеха, используя что-то вроде следующего алгоритма или любого другого разумного сэмплера для многочленного распределения, 

// 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 ))         
}

Это должно занять время, близкое к O (N), но оно зависит от того, насколько эффективны ваши пробоотборники для биномиального распределения и составной модели компонентов.

...