دانلود تحقیق الگوریتم

در سالهای اخیر آمارشناسان به طور زیاد روش‌های الگوریتم مونت کارلوی زنجیر مارکوفی (MCMC) را رسم کرده‌اند.

الگوریتم نمونه‌گیری گیبر یکی از بهترین روش‌های شناخته شده است برای آشنایی با شرایط مسأله فرض کنید در بردار تصادفی ( ) برای محاسبه چگالی کناری x ، با مشکل روبرو هستیم اما چگالی‌های شرطی و و … در دسترس می‌باشند.

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

حالا توجه قابل ملاحظه‌ای به الگوریتم متروپولیس- هستینگس تخصیص داده شده است که توسط متروپولیس و روسنبلوس ، تلر (1953) گسترش و بعداً توسط هستینگس (1970) نظم داده شده است.

الگوریتم M-H به طور زیاد در فیزیک کاربرد دارد و هنوز با وجود مقاله‌ای که توسط هستینگس ارائه شده است، به طور خیلی کم برای آمارشناسان شناخته شده است.

به دلیل سودمندی الگوریتم M-H ، کاربردهای آن به طور مداوم ظاهر می‌شود.

برای مثال‌های جدید مولر (1993)، چیب وگریبزگ (1994) و فیلیپس و اسمیت (1994) را ببینید.

ما مقدمه‌ای را از این الگوریتم تهیه کرده‌ایم که از اصول اولیه آن مشتق شده است این مقاله به تنهایی مربوط به تئوری زنجیر مارکوف است.

مطالب مربوط به این مقاله چنان که در پایین می‌آید به بحث گذاشته می‌شود.

در بخش 2،‌ ما به طور خلاصه مشابه روش‌پذیرش- رد کردنی را مرور می‌کنیم.

اگر چه MCMC نیست ولی بعضی از تفسیرهایی که در الگوریتم متروپولیس- هستینگس ظاهر می‌شود را به کار می‌برد و این مقدمه ای خوب برای این موضوع است.

بخش 3 ارتباط تئوری زنجیر مارکوف به فضای وضعیت دائم را معرفی می‌کند که با فلسفه کلی که در پشت روش MCMC است همراه می‌شود.

در بخش 4 الگوریتم M-H را نتیجه می‌گیریم و بخش 5 شامل مقالاتی می‌شود که با انتخاب چگالی کاندیدی- تولیدی در ارتباط هستند.

2- نمونه‌گیری پذیرش- رد کردنی
بر خلاف روش‌های MCMC که در پایین توضیح داده شده تکنیک‌های مشابه قدیمی که نمونه‌های مارکوفی را تولید نمی‌کند وجود دارد.

روش مهم این دسته روش A-R است که به این صورت است.

روش A-R : روش A-R به طور علمی نمونه‌هایی را تولید می‌کند که از چگالی معین می‌آید که یک چگالی غیرنرمالی و k یک ثابت نرمالیز است که ناشناخته است.

فرض کنید که h(x) یک چگالی باشد که با روش‌هایی معین می‌تواند شبیه‌سازی شود و فرض کنید که یک ثابت شناخته شده C باشد طوری که برای تمام x ها باشد.

*یک مقدار Z از h(.) و یک مقدار U از (1/0)U (توزیع یکنواخت روی (اره)) بگیرید.

اگر آنگاه z=y و به * برگردید،‌در غیر این صورت باز هم به * برگردید.

به آسانی نشان داده می‌شود که این y یک متغیر تصادفی از است.

برای اینکه این روش مفید و سودمند باشدC باید با دقت انتخاب شود.

نظر به تولید چگالی همچنین در الگوریتم M-H ظاهر می‌شود، اما قبل از در نظر گرفتن تفاوت‌ها و مشابهت‌ها، ما به منطق و فکری که در پشت روش MCMC است توجه می‌کنیم.

3- شبیه‌سازی مونت کارلوی زنجیر مارکوفی روش معمول تئوری زنجیر مارکوفی روی فضای وضعیت این است که با یک انتقال کرنل برای و ، جایی که B بورل سیگا میدان روی است شروع می‌شود.

انتقال کرنل امکان حرکت از x تا یک نقطه‌ای در دستگاه A را نمایش می‌دهد و انتقال از x تا x که با نمایش می‌دهیم به طور فرضی صفر نیست.

توجه اصلی روی تئوری زنجیر مارکوفی این است که یک توزیع هدف وجود دارد که تحت شرایطی معین انتقال کرنل به آن توزیع هدف همگرا می‌شود.

(1) تکرار n ام به وسیله جایی که داده می‌شود.

تحت شرایطی که در پایین بحث می‌شود نشان داده می‌شود که تکرار n ام به سمت توزیع هدف همگرا می‌شود.

وقتی که n به سمت بینهایت میل می‌کند.

در واقع چگالی هدف همان است که شناخته شده است و نمونه‌ها به سمت آن میل می‌کنند و انتقال کرنل ناشناخته است.

برای اینکه نمونه‌هایی از تولید شود باید یک انتقال کرنل مناسب پیدا کرد که در تکرار n ام وقتی که n بزرگ می‌شود به سمت همگرا شود.

این فرآیند در یک x قراردادی آغاز شده و در مدت زمان زیادی تکرار می‌شود، بعد از این تعداد زیاد، توزیع مشاهدات که از شبیه‌سازی تولید می‌شود تقریباً توزیع معینی است.

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

فرض کنید انتقال کرنل به صورت زیر باشد: (2) که و از اینکه واضح است که الزاماً یک نیست.

حالا اگر مورد استفاده در (2) به صورتی باشد که رابطه زیر برقرار باشد.

(3) آنگاه چگالی هدف همان است (تیرنی 1994).

برای اینکه تحقیق کنیم،‌ طرف راست (1) را ارزیابی می‌کنیم.

(4) طرف چپ رابطه (3) حرکت از x تا y است جایی که x از تولید می‌شود و طرف راست حرکت از x تا y است جاییکه y همچنین از تولید می‌شود.

در واقع نتیجه نشان می‌دهد که توزیع ثابتی است برای .

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

4- الگوریتم متروپولیس- هستینگس همان‌طور که در روش A-R، ما فرض می‌کنیم که یک چگالی داریم که کاندیدها را می‌تواند تولید کند در اینجا هم یک چگالی داریم که کاندیدها را از آن تولید می‌کنیم و اگر این اتفاق بیفتد که خودش وضعیت برگشت‌پذیری (3) را برای تمام xها و y ها فراهم کند تحقیق ما خاتمه می‌یابد.

اما بیشترین احتمال این است که آن اتفاق نمی‌افتد و ممکن است که برای مثال برای بعضی از xها و y ها داشته باشیم.

(5) در این حالت فرآیند از x تا y بیشتر دقت‌ها و از y تا x خیلی به ندرت حرکت می‌کند.

راه راحتی که این وضعیت را تصحیح می‌کند این است که شماره حرکات از x تا y را به وسیله معرفی احتمال کاهش دهیم.

ما از ‌به عنوان احتمال حرکت رجوع می‌کنیم.

اگر حرکت ساخته نشده باشد فرآیند دوباره به x ‌بر می‌گردد.

در الگوریتم M-H داریم: دوباره در نظر بگیرید نابرابری (5).

این نابرابری به ما می‌گوید که حرکت از y تا x اغلب به طور کافی ساخته نمی‌‌شود، بنابر این ما باید را که تا حد ممکن بزرگ باشد تعریف کنیم که حد بالای آن یک است.

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

بنابر این (6) ما حالا می‌بینیم که ،‌ البته اگر نابرابری در (5) برعکس شود ما قرار می‌دهیم و همان‌طور که در بالاست را نتیجه می‌گیریم.

احتمالات و سپس معرفی می‌شوند تا مطمئن شویم که دو طرف (5) در تعادل هستند یا به عبارت دیگر برگشت‌پذیری را فراهم می‌کند.

اگر و گرنه 1 برای اینکه تعریف انتقال کرنل برای زنجیر متروپولیس- هستینگس را کامل کنیم ما باید احتمال غیرصفری را در نظر بگیریم که این فرآیند درx باقی می‌ماند.

همان‌طور که در بالا تعریف کردیم.

در نتیجه انتقال کرنل زنجیر M-H، به وسیله مشخص می‌شود.

Markov chain monte carlo (MCMC) روش مونتوکارلو در واقع بر گرفته از قانون اعداد بزرگ برای برآورد یک احتمال مرکزی یا امید ریاضی است.

فرض کنید می‌خواهیم امید (EY)Y‌را برآورد کنیم و یک الگوریتم برای تولید یک نمونه‌ی تصادفی (Y1,Y2,Y3,…)iid داریم که دارای توزیع یکسان Y با میانگین نمونه‌ای می‌باشند که برای اندازه‌ی نمونه‌ی بزرگ یک برآوردگر خوب برای EY می‌باشد.

در مسائل ساده معمولاً اینچنین متغیرهای تصادفی را از متغیرهای تصادفی تولید می‌کنیم ولی در مسائل پیچیده‌تر به این راحتی نیست.

MCMC یک تکنیک خوب بر پایه اعداد بزرگ برای زنجیره‌های مارکوف است، به این صورت که: می‌خواهیم امید Y را تقریب بزنیم.

فرض کنید الگوریتمی داریم که X1,X2,… را از زنجیره‌ی مارکوف تولید می‌کند و روی فضای نمونه‌ای X با تابع توزیع ثابت ‌و یک تابع حقیقی مقدار و میانگین نمونه‌ای که می‌تواند برای برآورد EY استفاده شود.

MCMC از این جهت مفید است که کار کردن با یک زنجیره‌ی مارکوف با تابع توزیع ثابت مشخص شده آسانتر از تابع توزیع اصلی است.

الگوریتم METROPOLIS : یکی از کاربردهای انتگرال مونت کارلو در بدست آوردن نمونه هایی از بعضی توزیع های احتمال پیچیده ی است.

تلاش برای بدست آوردن این نمونه ها اساس روشهای MCMC است و یکی از این روشها متروپولیس- هستینگ است.

فرض کنید که هدف ما استخراج نمونه هایی از توزیع است که در حالی که ثابت مالیزه است و مجهول و محاسبه آن مشکل می باشد.

الگوریتم (Metropolis & Ulam 1949, Metropolis et al.1953) Metropolis یک دنباله از استخراج ها را از این توزیع تولید می کند , به صورت زیر : با هر مقدار اولیه که شروع کنید.

برای مقدار کنونی x یک نقطه ی پیشنهادی را از توزیع از طریق نمونه گیری انتخاب کنید.

تنها محدودیت روی این چگالی در الگوریتم Metropolis متقارن بودن آن است: نسبت چگالی نقطه ی پیشنهادی و مقادیر کنونی را محاسبه کنید: توجه کنید که در این گام چون نسبت را تحت دو مقدار مختلف درس نظر گرفته ایم ثابت نرمالیز حذف می شود.

اگر (پرش چگالی را افزایش دهد) نقطه ی پیشنهادی را می پذیریم و قرار می دهیم و به گام 2 باز می گردیم.

اگر (پرش چگالی را کاهش دهد) با احتمال نقطه ی پیشنهادی را می پذیریم و به گام 2 باز می گردیم.

به بیان دیگر: را محاسبه کرده و سپس مقدار پیشنهادی را با احتمال (احتمال انتقال) می پذیریم.

این کار یک زنجیره ی مارکوف را تولید می کند که احتمالات انتقال از به فقط به (و نه به ) بستگی دارد.

هستینگس (1970) , الگوریتم متروپولیس را با استفاده از تابع احتمالات انتقال اختیاری تعمیم داد و احتمال پذیرش برای یک مقدار پیشنهادی به صورت زیر است: این الگوریتم (MH) Metropolis – Hastings است.

اگر فرض متقارن بودن توزیع پیشنهادی را نیز اضافه کنیم الگوریتم اولیه ی Metropolis بهبود می یابد.

به صورت خلاصه الگوریتم متروپولیس- هستینگس از این قرار است: با شروع کنید برای ...

, 2 , 1= i : مقدار را پیشنهاد کنید.

را تولید کنید.

اگر را بپذیرید و قرار دهید در غیر اینصورت را رد کنید قرار دهید.

الگوریتم متروپولیس با هر توزیع متقارنی کار می کند در حالی که الگوریتم متروپولیس- هستینگس خیلی کلی تر است.

مثال 1: تابع چگالی زیر را در نظر بگیرید: فرض کنید که علاقه مند به شبیه سازی مقادیری از این توزیع با 5=n درجه آزادی هستیم و 4=a.

فرض کنید که توزیع مولد پیشنهادی را توزیع یکنواخت روی (100,0) در نظر گرفته ایم (توجه کنید که این مثال ساختگی است) حال الگوریتم را اجرا می کنیم: 1= را به عنوان مقدار اولیه قرار داده و فرض می کنیم که توزیع یکنواخت یک مقدار پیشنهادی 82/39= را نتیجه می دهد.

در این حال و با احتمال 0007/0 پذیرفته می شود، بنابر این به صورت تصادفی u را از (1,0)Uniform (یکنواخت روی (1,0) ) به صورت تصادفی انتخاب می کنیم و سپس پذیرفته می شود اگر .

در این مثال مقدار پیشنهادی رد شده و مقدار دیگری را از توزیع پیشنهادی انتخاب می کنیم و ادامه می دهیم.

انتخاب توزیع پیشنهادی (0)q: در این قسمت می خواهیم بررسی کنیم که بهترین انتخاب ها برای توزیع پیشنهادی چیست؟

دو روش کلی برای انتخاب داریم: گام زدن تصادفی زنجیره ی نمونه گیری مستقل گام زدن تصادفی: تحت یک نمونه گیری که توزیع پیشنهادی مورد استفاده بر پایه زنجیره ی قدم تصادفی است، مقدار جدید را برابر با مقدار فعلی به اضافه ی متغیر تصادفی می گیریم: در این حالت چگالی به متغیر تصادفی وابسته است.

اگر ، به عبارت دیگر، چگالی متغیر تصادفی متقارن است.

(در توزیع نرمال یا نرمال چند متغیره با میانگین صفر یا یکنواخت مرکزی اطراف صفر) سپس می توان نمونه گیری Metropolis را استفاده کرد: واریانس توزیع پیشنهادی می تواند به عنوان یک هماهنگ کننده ی پارامتر در نظر گرفته شود که می توانیم آنرا برای داشتن پراکندگی بهتر تعدیل کنیم.

به صورت خلاصه: توزیع هدف: توزیع پیشنهادی: مثال: نرمال پارامتر تنظیم کننده: زنجیره ی نمونه گیری مستقل: تحت یک نمونه گیری که توزیع پیشنهادی مورد استفاده بر پایه ی زنجیره ی نمونه گیری مستقل است احتمال پرش نقطه ی از مقدار فعلی در زنجیره ی نمونه گیری مستقل است یعنی بنابر این مقدار پیشنهادی از یک توزیع مورد علاقه که مستقل از مقدار کنونی است نتیجه می شود.

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

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

همانطور که اشاره شد ما می توانیم توزیع پیشنهادی را برای تعدیل کردن پیچیدگی و به ویژه احتمال پذیرش زنجیره هماهنگ کنیم.

این کار معمولا توسط تنظیم کردن انحراف استاندارد از توزیع پیشنهادی انجام می شود.

برای مثال، تنظیم واریانس (یا مقادیر ویژه از ماتریس کوواریانس) برای یک توزیع نرمال (یا نرمال چند متغیره) افزایش یا کاهش بازه ی اگر توزیع یکنواخت استفاده شده (واریانس با افزایش افزایش می یابد.) دراپر 2000 برای افزایش احتمال پذیرش SD توزیع پیشنهادی را کاهش داد.

همچنین اگر SD خیلی بزرگ باشد، تغییرها بزرگ هستند (که خوب است.) اما معمولا پذیرفته نیستند.

این ها را به خود همبستگی زیاد و پیچیدگی خیلی ناچیز راهنمایی می کند که زنجیره های خیلی بزرگتر را نیاز دارد.

اگر SD پیشنهادی خیلی کوچک است، تغییرها معمولا پذیرفته اند (احتمال پذیرش زیاد است) مثال: فرض کنید می خواهیم یک توزیع را به عنوان چگالی انتخابی خود استفاده کنیم در حالی که به سادگی توزیع مستقل از موقعیت فعلی باشد.

برای که بنابر این توجه کنید که متقارن نیست بنابر این از نمونه گیری متروپولیس- هستینگس استفاده می کنیم، با احتمال پذیرش با استفاده از توزیع اولیه یکسان با مثال 1 و ، احتمال رد آن می شود: ترکیب استراتژی ها: راه دیگر برای بدست آوردن بهترین (0)q ترکیب استراتژی های قبل است: فرض کنید توزیع اولیه مان است و دو توزیع پیشنهادی را داریم ، و به 3 روش زیر دو توزیع پیشنهادی را ترکیب می کنیم: روش اول: توجه کنید که این روش نسبت پذیرش بالایی می دهد.