روش نمونه‌برداری بازپس‌زننده

در تجزیه و تحلیل عددی و آمار محاسباتی، روش نمونه‌برداری بازپس‌زننده یک تکنیک اساسی است که برای تولید مشاهدات از یک توزیع استفاده می شود.

معرفی

در آنالیز عددی و محاسبات آماری، نمونه‌برداری بازپس‌زننده (به انگلیسی: rejection sampling) روش پایه‌ای برای تولید نمونه از یک توزیع احتمالی است که در آن به جای نمونه‌برداری مستقیم از توزیع $P(x)$

که دشوار است، از توزیع پیشنهادی

Q(x)

که نمونه‌برداری از آن ساده است استفاده می‌شود. اما توزیع پیشنهادی

Q(x)

باید به‌گونه‌ای انتخاب شود که حداقل یک مقدار

k

وجود داشته باشد به‌طوریکه

kQ(x)\geq {\tilde {P}}(x)

. با استفاده از توزیع

Q(x)

نمونه

x^{*}

را بدست می‌آوریم اما این نمونه با احتمال

{\frac {{\tilde {P}}(x^{*})}{kQ(x^{*})}}

پذیرفته می‌شود. دلیل استفاده از

{\tilde {P}}(x)

بجای

P(x)

این است که با توجه به رابطه

P(x)={\frac {{\tilde {P}}(x)}{Z}}

نمونه‌برداری از

{\tilde {P}}(x)

ساده‌تر از

P(x)

است.

روش نمونه‌برداری بازپس زننده

احتمال تولید شدن و پذیرفتن یک نمونه

در این روش احتمال تولید شدن یک نمونه دقبقا برابر با $P(x)$

است.

${\cfrac {{\cfrac {{\tilde {P}}(x)}{kQ(x)}}Q(x)}{\int {\cfrac {{\tilde {P}}(x)}{kQ(x)}}Q(x)\,dx}}={\cfrac {{\tilde {P}}(x)}{\int {\tilde {P}}(x)\,dx}}=P(x)$

همچنین احتمال پذیرش هر نمونه برابر است با:

$P(accept)=\int {\cfrac {{\tilde {P}}(x)}{kQ(x)}}Q(x)\,dx={\frac {\int {\tilde {P}}(x)\,dx}{k}}$

به عبارت دیگر با افزایش مقدار $k$

احتمال پذیرش نمونه‌ها کاهش می‌یابد.

روش نمونه‌برداری بازپس‌زننده تطبیقی

چالش اصلی در روش نمونه‌برداری بازپس‌زننده تعیین توزیع پیشنهادی مناسب $Q(x)$

است. بطوریکه مقدار

k

بگونه‌ای انتخاب شود که احتمال پذیرفته نشدن نمونه‌ها کاهش چشمگیری نداشته باشد. به عبارت دیگر

kQ(x)

در قسمت بالای منحنی

P(x)

قرار بگیرد و همچنین فاصله زیادی از آن نداشته باشد. در صورتیکه

P(x)

لگاریتم-مقعر باشد (به انگلیسی: log-concave) باشد با استفاده از روش نمونه‌برداری بازپس‌زننده تطبیقی (به انگلیسی: Adaptive rejection sampling) می‌توان توزیع پیشنهادی

Q(x)

مناسب را بدست آورد.

فرآیند اجرا

ابتدا با استفاده از توزیع یکنواخت تعدادی نمونه تولید می‌کنیم و برحسب احتمال گفته شده نمونه‌ها را پذیرش و یا رد می‌کنیم. در صورت پذیرفته نشدن هر نمونه یک خط مماس بر توزیع اصلی در آن نقطه رسم می‌کنیم. درنتیجه از تقاطع حاصل از این خطوط یک توزیع حاصل می‌شود. با نمونه برداری از این توزیع و پذیرفتن نمونه‌ها برحسب نسبت گفته شده، درصورت پذیرفته نشدن هر نمونه یک خط مماس جدید بر توزیع بدست آمده رسم می‌کنیم و فرآیند به همین ترتیب ادامه می‌یابد. با افزایش تعداد خطوط مماس، توزیع پیشنهادی بدست آمده پیچیده‌تر می‌شود. اما باید توجه داشت که این خطوط در مقیاس لگاریتم رسم می‌شوند. در واقع با اجرای این فرآیند توزیعی بدست خواهد آمد که در مقیاس معمولی تکه‌ای نمایی (به انگلیسی: piecewise exponential) است، که نمونه‌برداری از آن کار دشواری نیست.

روش نمونه برداری بازپس زننده تطبیقی

عملکرد نمونه‌برداری بازپس‌زننده در ابعاد بالا

در روش نمونه برداری بازپس‌زننده با افزایش تعداد ابعاد توزیع موردنظر احتمال پذیرفته‌شدن نمونه‌ها بصورت نمایی کاهش می‌یابد. به عنوان مثال اگر $P(x)$

دارای توزیع نرمال

N(\mu ;\sigma _{p}^{2})

و

Q(x)

دارای توزیع نرمال

N(\mu ;\sigma _{q}^{2})

باشند بطوریکه

\sigma _{p}^{2}

و

\sigma _{q}^{2}

تفاوت بسیار ناچیزی داشته باشند و تعداد ابعاد هر کدام از این دو توزیع برابر

d

باشند، در اینصورت می‌توان متغیر تصادفی

X

را بصورت

(X_{1},X_{2},...,X_{d})^{T}

نمایش داد.

$X\sim N_{d}(\mu ,\Sigma )$

که در آن

\mu

بردار میانگین با اندازه

d

بعد است،

\mu =E[X]=[E[X_{1}],E[X_{2}],...,E[X_{d}]]^{T}

و

\Sigma

ماتریس کواریانس با ابعاد

d\times d

است.

$\Sigma _{i,j}=\operatorname {E} [(X_{i}-\mu _{i})(X_{j}-\mu _{j})]=\operatorname {Cov} [X_{i},X_{j}]$

رابطه تابع چگالی احتمال برای توزیع نرمال چندمتغیره بصورت $f_{\mathbf {X} }(x_{1},\ldots ,x_{d})={\frac {\exp \left(-{\frac {1}{2}}({\mathbf {x} }-{\boldsymbol {\mu }})^{\mathrm {T} }{\boldsymbol {\Sigma }}^{-1}({\mathbf {x} }-{\boldsymbol {\mu }})\right)}{\sqrt {(2\pi )^{d}|{\boldsymbol {\Sigma }}|}}}$

که در آن

\Sigma

دترمینان ماتریس کواریانس است. ماتریس کواریانس یک ماتریس قطری است و می‌دانیم که دترمینان ماتریس قطری برابر است با حاصل‌ضرب عناصر موجود در قطر اصلی، به عبارت دیگر

\Sigma

برابر است با

\sigma _{1}^{2}\times \sigma _{2}^{2}....\times \sigma _{d}^{2}

. از طرفی دیگر واریانس ابعاد مختلف یکسان است، بنابراین

|{\boldsymbol {\Sigma }}|=(\sigma ^{2})^{d}

.

درنهایت با توجه به رابطه‌ $kQ(X)\geq P(X)$

می‌توان به این نتیجه رسید که

k=({\frac {\sigma _{q}}{\sigma _{p}}})^{d}

.

بنابراین حتی اگر $P(x)$

فاصله بسیار کمی با

Q(x)

داشته باشد، در ابعاد بالا

k

عدد بسیار بزرگی خواهد بود و در نتیجه احتمال پذیرش نمونه‌ها کاهش می‌یابد و به همین دلیل روش نمونه‌برداری بازپس‌زننده در ابعاد بالا کاربردی نخواهد داشت و در این موارد از روشهایی از جمله گیبز و متروپلیس هستینگز استفاده می‌شود.

جستارهای وابسته

روش تبدیل معکوس

منابع

↑ http://www.cs.cmu.edu/~epxing/Class/10708/lectures/lecture16-MC.pdf
↑ "View source for Multivariate normal distribution". Wikipedia (به انگلیسی).

Robert, C.P. and Casella, G. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
J. von Neumann, "Various techniques used in connection with random digits. Monte Carlo methods", Nat. Bureau Standards, 12 (1951), pp. 36–38.

[:0-1] ttp://www.cs.cmu.edu/~epxing/Class/10708/lectures/lecture16-MC.pdf

[2] "View source for Multivariate normal distribution". Wikipedia (به انگلیسی).