ایده ی monte carlo: یک مجموعه تصادفی از فضا را انتخاب می کند و یک الگوریتم قطعی روی آن انجام می دهد. این کار را تکرار می کند.
این کار معادل این است که یک random walk روی فضای مساله بزنیم تا به جواب برسیم.
در تحلیل این روش احتمال انتخاب جواب نسبت تعداد جوابها به کل فضا است.
(almost uniform sampler: نمونه گیری که در آن احتمال یکنواخت بودن از یک اپسیلون کمتر باشد.)
برای بهبود آن نمونه گیری را در دو مرحله انجام می دهیم:
-فضای نمونه را به زیر مجموعه هایی افراز می کنیم که احتمال انتخاب هر کدام یکسان باشد و یکی را با احتمال متناسب با تعداد اعضایش انتخاب می کنیم.
-احتمال انتخاب یک عضو از زیر مجموعه هم یکسان باشد و یکی از آنها را یکنواخت انتخاب می کنیم.
با این کار احتمال انتخاب شدن هر عضو یکنواخت است. (مثل قبل)
می توانیم این کار را با تعداد بیشتری مرحله انجام بدهیم، یعنی در هر مرحله ی الگوریتم از جواب قبلی استفاده کنیم و از روی آن جواب جدید را بسازیم.
مثلا در روشهای افزایشی، هر بار از جواب قبلی استفاده کنیم و دو حالت داریم: یا این عضو جدید در جواب تاثیر دارد یا نه. با حساب کردن احتمال تغییر جواب می توانیم احتمال رسیدن به جواب نهایی را به دست بیاوریم.
این کار معادل markov chain روی فضای مساله است، چون دیگر احتمال رسیدن به هر وضعیت یکسان نیست. (متناسب با اعضای آن مجموعه است.)
برای اینکه این روش جواب بدهد باید دو شرط همگرایی markov chain برقرار باشند: همبند بودن و ب.م.م طول دورهای گراف=1 باشد.
برای برقرار شدن شرط اول که کاری نمیشه کرد؛ ولی برای برقرار شدن ب.م.م طول دورها = 1 می توانیم طوقه (دور با طول 1 یال: از هر راس به خودش) اضافه کنیم که اگر به اندازه ی n-d(u) باشه احتمال یکنواخت هم میشه و تبدیل به random walk میشه.
الآن بار اول است که بعد از اینکه random walk یاد گرفتم و الآن می بینم که اون الگوریتمی که یک عمر نمی فهمیدم چرا درست کار می کنه این بوده.
خب اگر تصادفی حرکت کنه، در زمان بینهایت کل فضا را طی می کنه و مزیتش اینه که حافظه نیاز نداره.
گرافش هم فکر کنم حتی ساخته نمیشه و چون ربات در هر جهتی حرکت می کنه فقط از این استفاده میشه که احتمال اینکه به هر جهتی حرکت کنه مساویه.
صرفا از نظر شباهت گفتم فکر کنم چیزهای دیگه ای هم داشت.
http://www.madalgo.au.dk/img/SS2010/Course%20Material/Orthogonal%20Range%20Queries%20Basic%20Methods.pdf
سوال 1- سوال 1 پست قبلی (خوشه بندی که شکل دارد و DBSCAN هم دارد)
سوال 2- روشهای تشخیص outlier را توضیح دهید.
سوال 3- آیا با شبکه عصبی که از تابع سیگموئید استفاده می کند می توان نمونه های زیر را جدا کرد؟ (نمونه های (0,0) (0,1) (1,1) مربوط به یک کلاس و (1,0) مربوط به کلاس دیگر)
سوال 4- در یک شبکه بیز، کدام متغیرها از هم مستقلند و کدام متغیرها وابسته؟ تابع احتمال توام آنها را بنویسید و برای (یک مقدار داده شده در مساله) حساب کنید.
الآن دیدم سوالهای میان ترم از اینجا بوده:
http://www.it.uu.se/edu/course/homepage/infoutv2/vt13/Exam-DUT-070816-ans.pdf
http://www.it.uu.se/edu/course/homepage/infoutv2/vt13/Exam-DM2-110527.pdf