جواب تمرین الگوریتم تصادفی

جواب تمرین های الگوریتم تصادفی

سوال 4 این سوال 1 تمرینه: (موش و گربه)

http://www.eecs.berkeley.edu/~vkanade/cs174/HW/HW9_sol.pdf

من از استادمون پرسیدم که این راهی که من رفتم راه اصلیه گفت آره اما خب این راه دیگه ای رفته.

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

من گفتم که این معادل یک random walk روی یک گراف دیگه است که هر راسش جای موش و گربه است.

ظاهر این دو تا حل مثل همه (یعنی این قسمتی که من گفتم) ولی بقیه اش خیلی فرق داره.

جزوه الگوریتم تصادفی

دریافت
حجم: 2.12 مگابایت

مال دانشگاه خودمون نیست ولی خیلی خوب و کامل توضیح داده.

استفاده از مشخصات مساله

به جای اینکه مساله را مستقیما حل کنیم می توانیم مشخصاتی از آن را در نظر بگیریم و این مشخصات را با هم مقایسه کنیم. (چون چک کردن تساوی آنها به طور مستقیم زمانبر است.)

در این صورت می توانیم با چک کردن تصادفی این مشخصات مسائلی که یکسان بودن دو چیز را بررسی می کنند حل کنیم.

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

تحلیل: دو حالت وجود دارد: واقعا مساوی بودن (A) و واقعا نامساوی بودن (A'). پیشامد B را هم تشخیص درست در نظر می گیریم. طبق احتمال شرطی داریم:

pr(B) = Pr(B|A)Pr(A)+Pr(B|A')Pr(A')

با استفاده از pr<=1 و محاسبه ی احتمالهایی مثل محاسبه ی احتمالهای دیگر برای آن کران پیدا کرد.

markov chain با توزیع دلخواه

می خواهیم با اضافه کردن طوقه به گراف فعلی، کاری کنیم که markov chain ما به یک توزیع دلخواه همگرا شود.

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

توزیع یکنواخت:

x = (x1,...,xn)

xi*pij=xj*pji

اگر x برداری باشد که به آن همگرا می شویم و pij احتمال رفتن از i به j باشد؛ در صورتی که شرط بالا برقرار باشد به توزیع دلخواه x می رسیم.

در حالت خاص تقارن (pij=pji) به توزیع یکنواخت می رسیم. (معادل گراف بدون جهت)

برای برقرار شدن شرط بالا باید به شکل زیر احتمالها را به روز کنیم:

different i,j

pij = min(1,xi/xj) if xi is a neighbor of xj

pij = 0 otherwise

else

pii = 1-sum(pij) (different i,j)

یعنی برای به روز کردن احتمالها به جای اینکه چندین طوقه اضافه کنیم، یک طوقه اضافه می کنیم اما وزن یالها را طوری تغییر می دهیم که به توزیع مورد نظرمان برسیم (pij=xi/xj) و بقیه احتمال را به طوقه می دهیم (pii).

نمونه گیری تصادفی

ایده ی monte carlo: یک مجموعه تصادفی از فضا را انتخاب می کند و یک الگوریتم قطعی روی آن انجام می دهد. این کار را تکرار می کند.

این کار معادل این است که یک random walk روی فضای مساله بزنیم تا به جواب برسیم.

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

(almost uniform sampler: نمونه گیری که در آن احتمال یکنواخت بودن از یک اپسیلون کمتر باشد.)

برای بهبود آن نمونه گیری را در دو مرحله انجام می دهیم:

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

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

با این کار احتمال انتخاب شدن هر عضو یکنواخت است. (مثل قبل)

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

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

این کار معادل markov chain روی فضای مساله است، چون دیگر احتمال رسیدن به هر وضعیت یکسان نیست. (متناسب با اعضای آن مجموعه است.)

برای اینکه این روش جواب بدهد باید دو شرط همگرایی markov chain برقرار باشند: همبند بودن و ب.م.م طول دورهای گراف=1 باشد.

برای برقرار شدن شرط اول که کاری نمیشه کرد؛ ولی برای برقرار شدن ب.م.م طول دورها = 1 می توانیم طوقه (دور با طول 1 یال: از هر راس به خودش) اضافه کنیم که اگر به اندازه ی n-d(u) باشه احتمال یکنواخت هم میشه و تبدیل به random walk میشه.

الگوریتم روبات رومبا

الآن بار اول است که بعد از اینکه random walk یاد گرفتم و الآن می بینم که اون الگوریتمی که یک عمر نمی فهمیدم چرا درست کار می کنه این بوده.

خب اگر تصادفی حرکت کنه، در زمان بینهایت کل فضا را طی می کنه و مزیتش اینه که حافظه نیاز نداره.

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

صرفا از نظر شباهت گفتم فکر کنم چیزهای دیگه ای هم داشت.

ارائه ها

به دلیل نامعلومی تصمیم گرفتم ارائه هام رو آپلود کنم.

دریافت
عنوان: fault tolerant clustering

دریافت
عنوان: P3C clustering algorithm
توضیحات: projected + subspace

دریافت
عنوان: online unit clustering
توضیحات: randomized clustering

آنتروپی و تولید عدد رندم

می خوایم یک عدد تصادفی یکنواخت بسازیم ولی فقط عدد تصادفی سازی داریم که توی کامپیوتر هست. (یک عدد رندم بین 0 و 1 تولید می کنه.)

معمولی که عدد تولید می کنیم خودمون توی برنامه ها (در یک عدد ضرب می کنیم) رندم یکنواخت نیست! :دی دلیل:

خب وقتی یک عدد تصادفی می سازیم احتمال اینکه یه عدد بزرگ ( با تعداد بیت زیاد) درست بشه بیشتر از اینه که عددهای با بیت کمتر ساخته بشن چون تعداد عددهای بزرگ بیشتره.

حالا حالتی رو در نظر بگیرید که بیت بسازیم تا عدد بشه. (حالت مطلوب!) اگر یک سری عدد 0 تا m داشته باشیم که احتمالشون مساوی باشه، باید چطوری بیتها رو رندم انتخاب کنیم؟ دو تا چیز هست که میشه اینجا تغییر داد یکی تعداد بیتهاست اون یکی احتمال 0 و 1 بودنشون.

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

احتمال ساخته شدن یک عدد k بیتی چقدره؟

(2^k)/m

امید ریاضی تعداد بیتها رو حساب می کنیم:

E(#bits) = sum_k_1_lg(m) (k* (2^k)/m)

ثابت می کنیم تعداد بیتهای عددی که با این روش جدید از روی قبلی می سازیم کمتر از log 1/q میشه که q احتمال رخ دادن اون عدده. می دونیم مجموع احتمالها یک میشه، پس 

?????

میان ترم الگوریتم تصادفی شریف - واقعی!

کیفیتش هم داغونه اصلا خونده نمیشه!