1

M状態の中から状態jが確率p_jで選択されるモデルがあります。確率は任意の実数である可能性があります。これは、M 状態の混合モデルを指定します。すべての j の p_j に一定時間でアクセスできます。多数 (N) のランダム サンプルを作成したいと考えています。最も明白なアルゴリズムは

1) 累積確率分布 P_j = p_1+p_2+...p_j を計算します。O(M)

2) 各サンプルに対して、[0,1] のランダムな float x を選択します。オン）

3) 各サンプルについて、min(0,P_j-1) < x <= max(1,P_j) となるように j を選択します。O(ログ(M))

したがって、漸近的な複雑さは O(Nlog(M)) です。N の係数は明らかにやむを得ないのですが、log(M) について疑問に思っています。現実的な実装でこの要因を打ち負かすことは可能ですか?

4

1 に答える 1

1

次のアルゴリズムのようなもの、または他の合理的な多項分布サンプラーを使用すると、より良い結果が得られると思います。

// 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) 時間近くかかるはずですが、二項分布と混合モデル コンポーネント サンプラーの効率性に依存します。

于 2010-10-25T20:19:00.433 に答える