موضوع مقاله: فیلتر ذره‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فیلتر ذره‌ای | مقدمه: اساس این روش برپایه به‌کارگیری از ذراتی است که در طی روندی الگوریتمی، برآوردی از توزیع پسین بدست داده، به کمک این برآورد می‌توان دست به تخمین پارامتر موردنظر زد. | ## بخش 1: فیلتر ذره‌ای | از آنجا که برآورد براساس توزیع پسین انجام می‌گیرد، فیلتر ذره ای از روش‌های بیزی شمرده می‌شود. برآورد برپایه نمونه‌برداری Monte-Carlo فرض کنید یک آزمایش تصادفی را به صورت مستقل از هم بار انجام دهیم و پیشامد را در طول این آزمایش مدنظر قرار دهیم. این رابطه بیان می‌کند که چنانچه آزمایش را با تعداد دفعات نامحدود و به صورت کاملاً مستقل از هم انجام دهیم، آنگاه می‌توان احتمال رخداد پیشامدی مانند را با شمردن تعداد رویداد آن پیشامد و تقسیم کردن بر تعداد دفعات کل بدست آورد. اما در جهان واقع به دلیل اینکه تعداد دفعات آزمایش محدود است و وابستگی‌هایی بین آزمایش‌ها وجود دارد می‌توان احتمال رخداد پیشامد را به‌صورت زیر تقریب زد. اینک با توجه به اینکه تعداد رویدادهای پیشامد مورد نظر برای ‌های محدود یک متغیر تصادفی است، تقریب احتمال رخداد پیشامد (رابطه بالا) نیز یک متغیر تصادفی خواهد بود. اما برای آنکه برآورد به روش مونت‌کارلو کیفیت مناسبی داشته باشد باید دارای ویژگی‌های زیر باشد: ویژگی اول: برآورد برپایه مونت‌کارلو باید نااریب باشد، یعنی اگر با انجام آزمایش‌های متعدد مقدارهای برآورد متفاوتی بدست‌آوردیم باید میانگین این مقادیر دقیقاً برابر با مقدار مورد برآورد باشد؛ یعنی اگر به دفعات با به‌کارگیری از روش مونت کارلو، احتمال رخداد پیشامد را برآورد کردیم و مجموعه‌ای از برآوردها (تخمین‌ها) بدست آوردیم، میانگین این برآوردها باید برابر با مقدار واقعی احتمال رخداد باشد. ویژگی دوم: برآورد برپایه مونت‌کارلو باید سازگار (Consistent) باشد، یعنی واریانس مقادیر مختلف از مجموعه برآوردها بر پایه روش مونت‌کارلو با افزایش تعداد دفعات آزمایش به سمت صفر بگراید. در نتیجه خطای برآورد نااریب و سازگار دارای میانگین آماری صفر بوده و واریانس آن با افزایش تعداد تکرر آزمایش به سمت صفر می‌گراید. به عنوان یک مثال کاربردی از روش برآورد مونت‌کارلو می‌توان به برآورد مساحت اشاره‌کرد. فرض کنید برآورد مساحت یک ناحیه برای ما مطلوب است و این ناحیه مورد برآورد در یک ناحیه مشخص دیگری پَروسته (محصور) شده باشد که مساحت آن دانسته‌است؛ بنابراین بر طبق روش مونت‌کارلو یک آزمایش تصادفی که جزئیات آن بیان می‌شود را انجام می‌دهیم؛ ریختن ذره‌هایی به صورت کاملاً مستقل و تصادفی همگی در درون ناحیه‌ای که مساحت آن را می‌دانیم؛ بنابراین آزمایش انجام شد. اینک پیشامد برآورد شده را به‌صورت تعداد ذره‌های که در درون ناحیه‌ای که می‌خواستیم تخمین بزنیم می‌افتند تعریف می‌کنیم. اکنون تعداد ذره‌هایی را که در درون ناحیه با مساحت نامعلوم می‌افتد با و تعداد ذره‌هایی را که در درون ناحیه با مساحت معلوم می‌افتد با نشان می‌دهیم. شکل زیر یک مثال از ناحیه‌ای که مساحتش را می‌خواهیم برآورد کنیم و ناحیه با مساحت معلوم را نشان می‌دهد. برای اینکه برآورد به صورت نااریب باشد لازم است ذره‌هایی که در درون ناحیه با مساحت معلوم قرار می‌گیرند دارای توزیع یکنواخت روی آن ناحیه باشند. اما روش مونت‌کارلو به اینجا محدود نمی‌شود، فرض کنید ذره‌های به یک طریقی و به‌طور مستقل از هم و تصادفی از توزیع احتمال بیرون کشیده شده باشند. اینک برپایه روش مونت‌کارلو تابع توزیع به کمک ذره‌های بیرون کشیده شده به صورت زیر تقریب زده می‌شود. رابطه اخیر بیان می‌دارد که برای محاسبه امید ریاضی هر تابع دلخواه کافیست ذره از تابع توزیع نمونه داشت و مقدار آنها تحت تابعیت را محاسبه کرد. در صورتی‌که وجود داشته باشد بر طبق قانون ضعیف اعداد بزرگ برای هر کمیت کوچک اپسیلون رابطه زیر را می‌توان نوشتZ. بر طبق این رابطه هرچه بزرگتر شود احتمال اینکه برآورد متوسط تابع از مقدر واقعی آن یعنی دور شود کمتر است. از طرف دیگر این برآورد یک برآورد نااریب است چراکه داریم: همچنین این برآورد یک برآورد سازگار است، برای فهم آن نیز داریم: که در بدست آوردن رابطه اخیر، معادله زیر و با توجه به i.i.d. اینک با توجه به اینکه بسیاری از کمیت‌ها و پارامترهایی را که می‌خواهیم برآورد کنیم می‌توان به صورت امید ریاضی نوشت و امید ریاضی را نیز می‌توان به کمک روش بیان شده مونت‌کارلو برآورد کرد، گستره کاربرد روش مونت‌کارلو روشن می‌شود. برای مثال فرض کنید بخواهیم کمیت را برپایه تخمین MMSE و با در نظر گرفتن کمیت مشاهده شده تخمین بزنیم. بدین منظور کافیست ذره‌های مستقل و تصادفی را از توزیع بیرون کشیده و طبق برآورد مونت‌کارلو در رابطه زیر قرار دهیم. در ادامه پیرامون نمونه‌برداری بااهمیت به عنوان شاخه‌ای از برآورد مونت‌کارلو بحث می‌کنیم. اینکه در این روش به‌جای نمونه‌برداری از همه نواحی توزیع احتمال تنها از نواحی پراهمیت یا مدنظر، نمونه‌برداری انجام می‌گیرد به دلیل کاهش حجم محاسبات یا سهولت در نمونه‌برداری می‌تواند باشد. این روش به‌ویژه برای فضاهایی با بعد بالا که معمولاً هم داده‌ها تنک بوده و ناحیه مطلوب کوچکتر از کل فضای داده‌است بسیار کاراست. ایده روش نمونه‌برداری بااهمیت، گزینش یک توزیع پیشنهادی به‌جای استفاده از توزیع احتمال اصلی است. همانگونه که گفته شد دلیل این جایگزینی به دلیل عدم لزوم یا سختی در نمونه‌برداری از توزیع احتمال است. در نتیجه نمونه‌برداری بااهمیت مونت‌کارلو به استفاده از ذره مستقل و تصادفی بیرون کشیده شده از تلقی می‌شود تا مقدار متوسط تابع را بگونه زیر تخمین بزند. | ## بخش 2: فیلتر ذره‌ای | درحقیقت دلیل تقریب زدن متوسط تابع بر طبق روابط بالا در این است که توزیع (و نه ) را برپایه تخمین مونت‌کارلو به گونه زیر می‌توان تقریب زد. که این‌بار ذره‌های به‌طور مستقل از هم و تصادفی از توزیع چگالی احتمال بیرون کشیده شده‌اند. با مقایسه تخمین مونت‌کارلو از رابطه و تخمین با نمونه‌های با اهمیت از رابطه فهمیده می‌شود که تخمین برپایه نمونه‌برداری بااهمیت مونت کارلو به کمک ذره‌های بیرون کشیده شده از توزیع دست یافتنی و نیز وزن‌های بااهمیت مرتبط با آن انجام می‌گیرد؛ بنابراین به طریقی نمونه‌برداری از توزیع با نمونه‌برداری از توزیع قابل حصول جایگزین شده‌است. با توجه به رابطه [?] به راحتی می‌توان فهمید که این تخمین‌گر نیز نااریب است چراکه داریم: واریانس این تخمین نیز به کمک روابط زیر محاسبه می‌شود [?]. بودن ذره‌های بیرون کشیده شده از توزیع استفاده شد، یعنی: با توجه به رابطه [?] مشخص می‌شود که واریانس این تخمین متفاوت از رابطه [?] مربوط به تخمین مونت‌کارلو بدست می‌آید، اما این واریانس در صورت برقراری یکی از دو شرط زیر می‌تواند کوچک شود [?]. اگر متناسب با برگزیده شود به نحوی که واریانس توزیع اصلی را نیز بر طبق رابطه بالا کمتر کند. بنابراین نمونه‌برداری با اهمیت از دو جهت می‌تواند حائز اهمیت باشد، یکی اینکه نمونه‌برداری از توزیع می‌تواند به مراتب راحت‌تر و کم محاسبه‌تر از نمونه‌برداری از توزیع باشد و دیگر اینکه این نوع نمونه‌برداری می‌تواند حتی واریانس تخمین را کمتر از واریانس تخمین مونت‌کارلو کند. اما گزینش توزیع خود یک مسئله بسیار حیاتی در این مقوله است، انتخاب نادرست این توزیع موجب افزایش واریانس تخمین‌گر شده باعث می‌شود هزینه زیادی در قبال راحت‌تر بودن نمونه‌برداری از آن در قبال توزیع بپردازیم. در حقیقت اگر مناسب برگزیده نشود توزیع وزن‌ها بسیار ناهمگون و پراکنده خواهد شد و در نتیجه بسیاری از وزن‌ها به دلیل توزیع خاصشان بی‌استفاده می‌شوند. همچنین در این حالت تخمین برای فضاهای بزرگ تنها توسط تعداد کمی از ذره‌ها با وزن‌های بزرگ تعیین‌کننده می‌شود. بنابر آنچه گفته شد، گزینش توزیع پیشنهادی باید بر طبق بندهای زیر باشد [?]: توزیع باید به ازای هایی که است بزرگتر از صفر باشد، . که یک شرط دیگر باید داشته باشد، و آن اینکه باسرعت کمتری نسبت به به سمت صفر بگراید تا حساسیتی کمتر نسبت به داده‌های پرت (Outlier) داشته باشد یا به عبارتی دیگر این توزیع باید دمبی (tail) بزرگ داشته باشد، یک معیار برای سنجش میزان دمب یک توزیع، تابع رتبه (score) است که رابطه آن در زیر آمده‌است. نشان داده می‌شود که اگر شرط محدود بودن را داشته باشد آنگاه توزیع دارای دمبی بزرگ خواهد بودZ. اما محدود بودن برای تابع مزبور بدین معنی است که به ازای هر حقیقی‌ای وجود داشته باشد کمیت‌های حقیقی و که داشته باشیم: نمونه‌برداری بااهمیت تناوبی همانگونه که در بخش پیشین بحث شد، گزینش توزیع پیشنهادی در بازدهی و کارایی تخمین برپایه نمونه‌برداری بااهمیت بسیار مهم و حیاتی است؛ بنابراین شیوه گزینش یک توزیع مناسب کلید بهره‌بری از یک تخمین‌گر موفق شمرده می‌شود. با این حال در اغلب موارد یافتن یک توزیع متناسب به‌ویژه در مواردی که با فضاهایی با بعد بالا سروکار داریم کار سختی است [?]. برای این منظور بایسته‌است که توزیع پیشنهادی به نحوی برگزیده شود تا خاصیت زیر را داشته باشد [?]. نیز برای توزیع پیشنهادی طبق خاصیتی که برای آن مقرر شد داریم: در نتیجه وزن‌های بااهمیت را می‌توان به صورت زیر بازنویسی کرد. از جمله مزیت‌های این روش در این است که این وزن‌ها در طول زمان به‌صورت تناوبی محاسبه می‌شوند و بازدهی آن در حین الگوریتم افزوده می‌شود، اما عیب مهم آن در این است که واریانس وزن‌ها ممکن است بزرگ باشد که موجب کاهش دقت در تخمین می‌شوند. به عبارت دیگر در مرجع [?] نشان داده شده‌است که واریانس وزن‌های بااهمیت در طول زمان افزوده شده و پس از چند تکرر (iteration) از الگوریتم تعداد بسیاری از وزن‌ها مقداری نزدیک به صفر و تنها اندکی از وزن‌ها ناصفر خواهند بود. راه حل مقابله با این مشکل استفاده از متدهای بازنمونه‌برداری است؛ بنابراین بازنمونه‌برداری به عنوان یکی از گام‌های اصلی در الگوریتم SIS شمرده می‌شود که هدف از آن حذف ذره‌هایی با وزن‌های کوچک و تقویت ذره‌های با وزن بزرگ است. یا به عبارت دیگر این فرایند موجب تشدید ذره‌های با احتمال بالا و تضعیف ذره‌های با احتمال کوچک می‌شود. در این شکل تشدید ذره‌ها با وزن‌های بالا و تضعیف ذره‌ها با وزن‌های کم توسط فرایند بازنمونه‌برداری به خوبی نشان داده شده‌است؛ بنابراین بر طبق مطالب گفته شده الگوریتم SIR را می‌توان به صورت زیر خلاصه کرد[?]. بنابراین این گام نقشی اساسی در الگوریتم نمونه‌برداری بااهمیت ایفا می‌کند [?] چراکه از طرفی با پدیده پراکندگی ناموزون وزن‌ها که موجب اتلاف محاسباتی می‌شود مقابله کرده و از تباهیدگی وزن‌ها جلوگیری می‌کند و از طرف دیگر هنگامیکه وزن‌ها مورب (Skewed) باشند موجب گزینش وزن‌های بااهمیت‌تر می‌شود. برای همین چه بسا این گام خود موجب تغییراتی در واریانس نمونه‌ها شده و لزوماً تخمین را بهبود ندهد. برای همین این گام با ملاحظاتی انجام می‌شود که خود موجب پیدایش الگوریتم‌های مختلف برای بازنمونه‌برداری شده‌است. نکته قابل تأمل در میان این الگوریتم‌ها در این است که اگر معیار، واریانس ذره‌های تولیدی باشد روش بازنمونه‌برداری‌ای که به روش سیستماتیک (systematic) موسوم است، واریانس کمتری را ایجاد کرده و از این لحاظ ارجح است [?]. اینک به ازای هر ذره نخست متغیر به‌صورت یکنواخت در بازه [۰٬۱] تولید شده و به کمک آن متغیر به صورت روبرو ایجاد می‌شود. برای درک بهتر نحوه عملکرد فرایند بازنمونه‌برداری سیستماتیک خواننده را به مرجع [?] ارجاع می‌دهیم. الگوریتم فیلتر ذره‌ای تا اینجا با اساس و پیشنیازهای لازم برای بیان جزئیات الگوریتم فیلتر ذره‌ای آشنا شدیم و نیز ذکر شد که این فیلتر براساس الگوریتم SIR استوار است. | ## بخش 3: فیلتر ذره‌ای | شاید ذکر این نکته نیز برای شروع معرفی فیلتر ذره‌ای مناسب باشد که این فیلتر با تقریب زدن چگالی پسین به‌صورت تناوبی و براساس تخمین بیزین عمل می‌کند [?]. در حقیقت چون نمونه‌برداری مستقیم از چگالی پسین عملی نیست باید به دنبال راهکاری بود که این چگالی را تخمین زد، فیلتر ذره‌ای گزیری برای رفع این مشکل است. اینک توضیح این فیلتر را با تخمین چگالی پسین به کمک ذره‌های بیرون کشیده شده از آن آغاز می‌کنیم [?]. همانگونه که بیان شد بر طبق تخمین مونت‌کارلو چگالی پسین را برپایه ذره بیرون کشیده شده از آن به‌صورت زیر می‌توان تقریب زد. که در آن ذره‌های مستقل از هم و به‌صورت تصادفی بیرون کشیده شده از چگالی پسین است. با این حال نمونه‌برداری از چگالی مزبور تنها حالتی خاص و غیرپیچیده در تخمین مونت‌کارلو است، در حالت کلی چگالی پسین دیگری در استخراج فیلتر ذره‌ای بکارگرفته می‌شود که چگالی کامل‌تری در روش فیلترکردن بیزین محسوب شده، به دلیل استفاده از اطلاعات افزون‌تر عملکرد بهتری خواهد داشت. اما به دلیل اینکه نمونه‌برداری مستقیم از این چگالی قابل عملی نیست بر طبق روش نمونه‌برداری بااهمیت از یک توزیع پیشنهادی بهره گرفته می‌شود؛ بنابراین تخمین تابع دلخواه با این توزیع پیشنهادی به صورت زیر بدست می‌آید. اینک چون مخرج رابطه اخیر مقداری ثابت است آن را می‌توان به داخل اپراتور متوسط‌گیری صورت برد، در نتیجه می‌توان نوشت: همان‌طور که پیشتر گفته شد، کمیت ، وزن بااهمیت نامیده شده بر طبق رابطه زیر بدست می‌آید. همچنین کمیت نرمالیزه شده وزن‌های بااهمیت با نشان داده شد که از رابطه زیر بدست می‌آید. پس به عبارتی چگالی پسین بر پایه تخمین نمونه‌برداری بااهمیت مونت‌کارلو از رابطه زیر تخمین زده می‌شود. که در آن ذره‌های به‌جای آنکه از چگالی نامعلوم و غیرقابل عملی نمونه‌برداری شده باشند از تویع پیشنهادی بیرون کشیده شده‌اند. پیرامون شرایط حیاتی انتخاب توزیع پیشنهادی در بخش [?] بحث شد، یکی از این شروط این بود که آن را بتوان به صورت زیر تجزیه کرد. در نتیجه با کمک گرفتن از این تجزیه و با درنظر گرفتن دو شرط اساسی \eqref{ASUM1} و \eqref{ASUM2} وزن‌های با اهمیت را به صورت تناوبی می‌توان محاسبه کرد، برای نشان دادن این مطلب توجه کنید که: اینک با درنظر داشتن این نکته که با داشتن بردار حالت در لحظه و پیش از آن اطلاعات افزون‌تری در احتمال رخداد بدست نمی‌دهند، داریم: از طرف دیگر به دلیل علیت می‌دانیم بردار حالت در زمان تأثیری در احتمال رخداد بردار مشاهده در لحظه ندارد. پس می‌توان نوشت: بنابراین در مجموع رابطه زیر را به‌صورتی که درپی می‌آید می‌توان ادامه داد. بنابراین وزن‌های متناظر با ذره‌های نمونه‌برداری شده از توزیع پیشنهادی به صورت تناوبی زیر قابل دستیابی هستند. که در آن مجموعه ذره‌های نمونه برداری شده از آغاز تا لحظه حاضر است، یعنی: بنابراین فیلتر ذره‌ای برپایه نمونه‌برداری تناوبی مونت‌کارلو عمل کرده و به کمک ذره‌های بیرون کشیده شده از توزیع پیشنهادی و وزن‌های متناظر با آن که به صورت تناوبی از وزن‌های ماقبل خود بدست می‌آیند تخمینی از بردار حالت ارائه می‌دهد. شاید تکرار این نکته مفید باشد که طبق رابطه SIS وزن‌های بااهمیت در هر لحظه به کمک ذره‌های نمونه برداشته شده از توزیع پیشنهادی و ارزیابی احتمال درستنمایی و چگالی گذار که بر طبق فضای حالت دانسته هستند بدست می‌آیند؛ بنابراین تخمین MMSE به کمک این ذره‌ها و وزن‌های متناظر با آن به طریق زیر محاسبه می‌شوند. در نهایت یادآوری این نکته حائز اهمیت است که واریانس وزن‌ها در طول الگوریتم رو به فزونی می‌گذارد، بگونه‌ای که مقدار بیشتر وزن‌ها به سمت صفر گراییده، مقدار تعداد اندکی از آنها بزرگ می‌شود، و درنهایت موجب تباه شدن وزن‌ها می‌شود که لازم می‌دارد از متدهای بازنمونه‌برداری که در بخش [?] پیرامون آن بحث شد استفاده شود. در این لحظه ذره‌ها از روی چگالی نمونه‌برداری می‌شوند که این چگالی احتمال با در نظر گرفتن تحرک جسم در لحظه اولیه تقریب زده می‌شود. تا اینجا درمورد نحوه انتخاب توزیع پیشنهادی نکاتی بیان شد، اما گزینه‌هایی مطرح نشد. بر طبق مرجع [?] انتخابی بهینه از دید کمینه شدن واریانس وزن‌های بااهمیت طبق گزینه زیر است. اما همان‌طور هم که در مرجع [?] مذکور بیان شده‌است نمونه‌برداری از این توزیع غیرعملی است. انتخاب برای توزیع می‌بایست حول احتمال رخداد بردار حالت در لحظه به شرط در اختیار داشتن کل مجموعه بردارهای مشاهدات تا لحظه و کل مجموعه بردارهای حالت تا لحظه باشد. به عبارت دیگر باید دید چنانچه بردار مشاهدات و بردار حالت بترتیب تا لحظه و در دسترس باشند، بردار حالت در لحظه چه توزیعی خواهد داشت آن توزیع را برای توزیع پیشنهادی برگزید. بنابر آنچه گفته شد می‌توان این توزیع را جداگانه به کمک فیلتر کالمن و با فرض گاوسی بودن این توزیع بدست آورد [?]. که در آن همان‌طور که گفته شد ماتریس کواریانس نویز پروسس بوده از رابطه زیر حساب می‌شود. سرانجام میانگین و ماتریس کواریانس توزیع پیشنهادی بترتیب به کمک ماتریس MMSE و فرایند تصحیح فیلتر کالمن طبق روابط زیر تعیین می‌شوند. | ## جمع‌بندی | به عبارت دیگر انتخاب توزیع پیشنهادی به صورت زیر خواهد بود، که در آن میانگین این توزیع برابر بردار حالت اصلاح شده بوده و ماتریس کواریانس آن همان ماتریس MMSE است.