تحقیق الگوریتم 23 ص

دسته بندي : دانش آموزی و دانشجویی » دانلود تحقیق
لینک دانلود و خرید پایین توضیحات
دسته بندی : وورد
نوع فایل :  word (..doc) ( قابل ويرايش و آماده پرينت )
تعداد صفحه : 22 صفحه

 قسمتی از متن word (..doc) : 
 

‏مقدمه
‏در سالهاي اخير آمارشناسان به طور زياد روش‌هاي الگوريتم مونت كارلوي زنجير ماركوفي (MCMC‏) را رسم كرده‌اند. الگوريتم نمونه‌گيري گيبر يكي از بهترين روش‌هاي شناخته شده است براي آشنايي با شرايط مسأله فرض كنيد در بردار تصادفي (‏) براي محاسبه چگالي كناري x‏ ، با مشكل روبرو هستيم اما چگالي‌هاي شرطي ‏ و ‏ و …‏ در دسترس مي‌باشند. در روش نمونه‌گيري گيبس مشاهداتي به صورت غيرمستقيم ازx‏ توليد مي‌شود و به كمك آنها چگالي كناري x‏ را بررسي مي‌كنيم.
‏ح‏الا توجه قابل ملاحظه‌اي به الگوريتم متروپوليس- هستينگس‏ Metropolis-Hastings
‏ تخصيص داده شده است كه توسط متروپوليس و روسنبلوس‏ Rosenbluth
‏، تلر‏ Teller
‏ (1953) گسترش و بعداً توسط هستينگس (1970) نظم داده شده است. الگوريتم M-H‏ به طور زياد در فيزيك كاربرد دارد و هنوز با وجود مقاله‌اي كه توسط هستينگس ارائه شده است، به طور خيلي كم براي آمارشناسان شناخته شده است.
‏به دليل سودمندي الگوريتم M-H‏ ، كاربردهاي آن به طور مداوم ظاهر مي‌شود. براي مثال‌هاي جديد مولرMuller
‏ (1993)، چيب وگريبزگ‏ chib and Greenberg
‏ ‏ ‏(1994) و فيليپس و اسميت‏ Smith
‏ (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) ‏