فیلتر ذره‌ای
فریافت نمونه‌برداری بااهمیت

نمونه‌برداری بااهمیت (Importance Sampling) به عنوان شاخه‌ای از تخمین برپایه مونت‌کارلو اولین بار توسط مارشال معرفی شد. ایده اصلی آن بر پایه نمونه‌برداری از توزیع احتمال تنها در نواحی پراهمیت است. اینکه در این روش به‌جای نمونه‌برداری از همه نواحی توزیع احتمال تنها از نواحی پراهمیت یا مدنظر، نمونه‌برداری انجام می‌گیرد به دلیل کاهش حجم محاسبات یا سهولت در نمونه‌برداری می‌تواند باشد. این روش به‌ویژه برای فضاهایی با بعد بالا که معمولاً هم داده‌ها تنک بوده و ناحیه مطلوب کوچکتر از کل فضای داده‌است بسیار کاراست.
ایده روش نمونه‌برداری بااهمیت، گزینش یک توزیع پیشنهادی   q(x) به‌جای استفاده از توزیع احتمال اصلی  P(x) است. همانگونه که گفته شد دلیل این جایگزینی به دلیل عدم لزوم یا سختی در نمونه‌برداری از توزیع احتمال  P(x) است.
\int f(x)P(x)dx=\int f(x){\frac {P(x)}{q(x)}}q(x)dx
در نتیجه نمونه‌برداری بااهمیت مونت‌کارلو به استفاده از  N ذره مستقل و تصادفی بیرون کشیده شده از  q(x) تلقی می‌شود تا مقدار متوسط تابع  f(x) را بگونه زیر تخمین بزند.
{\hat {\mathbb {E} }}(f(x))={\frac {1}{N}}\sum _{i=1}^{N}{w(x^{(i)})f(x^{(i)})}
که در آن  w(x) وزن بااهمیت (Importance Weight) گفته شده و به گونه زیر بدست می‌آید.
w(x^{(i)})={\frac {P(x^{(i)})}{q(x^{(i)})}}
درحقیقت دلیل تقریب زدن متوسط تابع  f(x) بر طبق روابط بالا در این است که توزیع  q(x) (و نه  P(x)) را برپایه تخمین مونت‌کارلو به گونه زیر می‌توان تقریب زد.
q(x)\approx {\frac {1}{N}}\sum _{i=1}^{N}\delta (x-x^{(i)})
که این‌بار ذره‌های  \{x^{(i)}\}_{i=1}^{N}  به‌طور مستقل از هم و تصادفی از توزیع چگالی احتمال  q(x) بیرون کشیده شده‌اند. سپس بر طبق رابطه [?] تخمین متوسط  f(x) بگونه زیر بدست می‌آید.
با مقایسه تخمین مونت‌کارلو از رابطه A1 و تخمین با نمونه‌های با اهمیت از رابطه B1 فهمیده می‌شود که تخمین برپایه نمونه‌برداری بااهمیت مونت کارلو به کمک ذره‌های بیرون کشیده شده از توزیع دست یافتنی  q(x) و نیز وزن‌های بااهمیت مرتبط با آن  w(x^{(i)}) انجام می‌گیرد؛ بنابراین به طریقی نمونه‌برداری از توزیع  P(x) با نمونه‌برداری از توزیع قابل حصول  q(x) جایگزین شده‌است.
در استفاده‌های عملی از این روش مانند فیلتر ذره‌ای که پیرامون آن در همین فصل توضیح داده می‌شود از وزن‌های نرمالیزه (Normalized importance weights) شده استفاده می‌شود. تعریف وزن‌های بااهمیت نرمالیزه از رابطه زیر بدست می‌آید.
{\tilde {w}}(x^{(i)})={\frac {w(x^{(i)})}{\sum _{j=1}^{N}{w(x^{(j)})}}}
در این صورت تخمین متوسط تابع  f(x) را به گونه زیر می‌توان نوشت [?].
{\hat {f}}_{N}={\frac {{\frac {1}{N}}\sum _{j=1}^{N}{w(x^{(j)})f(x^{(j)})}}{\sum _{j=1}^{N}{w(x^{(j)})}}}=\sum _{j=1}^{N}{{\tilde {w}}(x^{(j)})f(x^{(j)})}
با توجه به رابطه [?] به راحتی می‌توان فهمید که این تخمین‌گر نیز نااریب است چراکه داریم:
{\begin{aligned}\mathbb {E} _{q(x)}({\hat {f}}_{N})&=\mathbb {E} _{q(x)}({\frac {1}{N}}\sum _{i=1}^{N}{{\frac {P(x^{(i)})}{q(x^{(i)})}}f(x^{(i)})})={\frac {1}{N}}\sum _{i=1}^{N}{\mathbb {E} _{q(x)}({\frac {P(x)}{q(x)}}f(x))}\\&={\frac {1}{N}}\sum _{i=1}^{N}{\mathbb {E} _{P(x)}(f(x))}=\mathbb {E} (f(x))\end{aligned}}
واریانس این تخمین نیز به کمک روابط زیر محاسبه می‌شود [?].
{\begin{aligned}{\mbox{Var}}_{q(x)}({\hat {f}}_{N})&=\mathbb {E} _{q(x)}(({\frac {1}{N}}\sum _{i=1}^{N}{w(x^{(i)})f(x^{(i)})}-\mathbb {E} _{q(x)}({\frac {P(x)}{q(x)}}f(x)))^{2})\\&={\frac {1}{N^{2}}}\mathbb {E} _{q(x)}(\sum _{i,j}^{N}{{\frac {P(x^{(i)})P(x^{(j)})}{q(x^{(i)})q(x^{(j)})}}f(x^{(i)})f(x^{(j)})})-\mathbb {E} _{q(x)}(({\frac {P(x)}{q(x)}}f(x))^{2})\\&={\frac {1}{N^{2}}}((N^{2}-N)\mathbb {E} _{q(x)}({\frac {P(x)}{q(x)}}f(x))^{2}+N\mathbb {E} _{q(x)}(({\frac {P(x)}{q(x)}}f(x))^{2}))-\mathbb {E} _{q(x)}({\frac {P(x)}{q(x)}}f(x))^{2}\\&={\frac {1}{N}}\int {\frac {(f(x)P(x))^{2}}{q(x)}}dx-{\frac {\mathbb {E} _{P(x)}(f(x))^{2}}{N}}\end{aligned}}
در بدست آوردن رابطه اخیر از i.i.d. بودن ذره‌های بیرون کشیده شده از توزیع   q(x) استفاده شد، یعنی:
\mathbb {E} ({\frac {P(x^{(i)})P(x^{(j)})}{q(x^{(i)})q(x^{(j)})}}f(x^{(i)})f(x^{(j)}))={\begin{cases}\mathbb {E} (({\frac {P(x)}{q(x)}}f(x))^{2})&i=j,\\\mathbb {E} ({\frac {P(x)}{q(x)}}f(x))^{2}&i\neq j\end{cases}}
با توجه به رابطه [?] مشخص می‌شود که واریانس این تخمین متفاوت از رابطه [?] مربوط به تخمین مونت‌کارلو بدست می‌آید، اما این واریانس در صورت برقراری یکی از دو شرط زیر می‌تواند کوچک شود [?].
اگر  q(x) متناسب با  P(x) برگزیده شود به نحوی که تقریبی از واریانس توزیع اصلی را بدست دهد.
اگر  q(x) متناسب با   |f(x)|P(x) برگزیده شود به نحوی که واریانس توزیع اصلی را نیز بر طبق رابطه بالا کمتر کند.
بنابراین نمونه‌برداری با اهمیت از دو جهت می‌تواند حائز اهمیت باشد، یکی اینکه نمونه‌برداری از توزیع   q(x) می‌تواند به مراتب راحت‌تر و کم محاسبه‌تر از نمونه‌برداری از توزیع  P(x) باشد و دیگر اینکه این نوع نمونه‌برداری می‌تواند حتی واریانس تخمین را کمتر از واریانس تخمین مونت‌کارلو کند.
اما گزینش توزیع  q(x) خود یک مسئله بسیار حیاتی در این مقوله است، انتخاب نادرست این توزیع موجب افزایش واریانس تخمین‌گر شده باعث می‌شود هزینه زیادی در قبال راحت‌تر بودن نمونه‌برداری از آن در قبال توزیع  P(x) بپردازیم. در حقیقت اگر  q(x) مناسب برگزیده نشود توزیع وزن‌ها بسیار ناهمگون و پراکنده خواهد شد و در نتیجه بسیاری از وزن‌ها به دلیل توزیع خاصشان بی‌استفاده می‌شوند. همچنین در این حالت تخمین برای فضاهای بزرگ تنها توسط تعداد کمی از ذره‌ها با وزن‌های بزرگ تعیین‌کننده می‌شود.
بنابر آنچه گفته شد، گزینش توزیع پیشنهادی  q(x) باید بر طبق بندهای زیر باشد [?]:
توزیع  q(x) باید به ازای  xهایی که  P(x)\neq 0 است بزرگتر از صفر باشد،  q(x)\geq 0.
توزیع  q(x) باید در نواحی مورد محاسبه متناسب با   |f(x)|P(x) ویا متناسب با  P(x) باشد.
نمونه‌برداری کردن از  q(x) راحت باشد.
محاسبه  q(x) برای هر ذره  x^{(i)} ساده باشد.
با این همه در برخی تجربه‌های عملی نشان داده شده‌است که  q(x) یک شرط دیگر باید داشته باشد، و آن اینکه باسرعت کمتری نسبت به  P(x) به سمت صفر بگراید تا حساسیتی کمتر نسبت به داده‌های پرت (Outlier) داشته باشد یا به عبارتی دیگر این توزیع باید دمبی (tail) بزرگ داشته باشد، یک معیار برای سنجش میزان دمب یک توزیع، تابع رتبه (score) است که رابطه آن در زیر آمده‌است.
\phi (x)={\frac {-d~log(P(x))}{dx}}
نشان داده می‌شود که اگر  \phi (x) شرط محدود بودن را داشته باشد آنگاه توزیع  P(x) دارای دمبی بزرگ خواهد بود، در غیر این صورت خیر. اما محدود بودن برای تابع مزبور بدین معنی است که به ازای هر  x حقیقی‌ای وجود داشته باشد کمیت‌های حقیقی  L و  U که داشته باشیم:
\forall x\in \mathbb {R} :~L\leq \phi (x)\leq U