نمونه گیری تصادفی و رند کردن تصادفی LPها (فصل 5 WS)

تضمین عملکرد الگوریتم تقریبی که انتخاب تصادفی می کند، امیدریاضی (expected value) جواب به دست آمده نسبت به {بر حسب} جواب بهینه است، وقتی روی همه ی انتخاب های تصادفی حساب شود.

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

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

همچنین گاهی می توانیم با احتمال بالا تضمین عملکرد الگوریتم تقریبی تصادفی را بدهیم. یعنی احتمال اینکه تضمین عملکرد نادرست باشد یک بر چندجمله ای بر حسب اندازه ورودی است. معمولا می توانیم این چندجمله ای را هرقدر می خواهیم بزرگ کنیم (و در نتیجه هر چقدر می خواهیم احتمال را کم کنیم) که تضمین عملکرد را با یک ضریب ثابت بدتر می کند. اینجا غیرتصادفی کردن کمتر لازم است، هر چند گاهی با روشهای پیچیده تری امکان پذیر است.
دو الگوریتم تصادفی برای مسائل maximum satisfiability و maximum cut می دهیم. نشان می دهیم که جوابی که به صورت تصادفی یکنواخت از مجموعه جوابها انتخاب شده باشد، یک الگوریتم تقریبی تصادفی خوب می دهد. برای مساله تصدیق بیشینه می توانیم از این هم جلوتر برویم و نشان دهیم انتخاب غیریکنواخت (بایاس شده) به تضمین عملکرد بهتری می رسد.

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

---------------------

یک الگوریتم ساده برای تصدیق بیشینه (MAX SAT) و برش بیشینه (MAX CUT)

برای هر کدام از این دو مساله یک الگوریتم تصادفی 1/2-تقریبی می دهیم.

در مساله MAX SAT، ورودی شامل n متغیر x_1 و ... و x_n است که true یا false هستند؛ m عبارت C_1 و ... و C_m که یای منطقی متغیرها و نقیض آنها هستند؛ وزن های نامنفی w_j برای C_j. هدف مساله پیدا کردن تخصیصی از true/false به x_i ها است که وزن عبارتهای صادق را بیشینه کند. یک عبارت صادق است، اگر یکی از متغیرهای نقیض نشده ی آن true شود، یا یکی از متغیرهای نقیض شده آن false شود.

تعاریف:

literal: به x_i و نقیض آن x'_i می گویند.

positive literal: خود x_i

negative literal: نقیض متغیر = x'_i

اندازه یا طول: تعداد literal های یک عبارت: L_j برای C_j

عبارت یکه: عبارت با طول 1

بدون از دست رفتن عمومیت مساله فرض کنید هیچ literal ای در یک عبارت تکرار نشده باشد. فرض کنید هر دوی x_i و x'_i هم در یک عبارت نباشند. فرض کنید عبارتها متمایز هستند (چون اگر مشابه باشند یکی از آنها را نگه می داریم و وزن مجموع آنها را به آن اختصاص می دهیم.).

الگوریتم تصادفی:

با احتمال 1/2 هر متغیر x_i را true می گذاریم. دید دیگر به این حل برای مساله انتخاب تصادفی یکنواخت مقادیر متغیرها از بین همه ی حالتها است. این الگوریتم تقریب خوبی از مساله به ما می دهد.

قضیه: ثابت کنید ضریب تقریب الگوریتم بالا 1/2 است.

اثبات: متناظر هر عبارت یک متغیر Y_j در نظر بگیرید که اگر آن عبارت صادق باشد 1 و در غیر این صورت 0 باشد. در این صورت مجموع وزن عبارتهای صادق به صورت زیر است:

w = sum_j_1_m (Y_j*w_j)

فرض کنید OPT جواب بهینه برای این نمونه از مساله MAX SAT باشد. طبق خطی بودن امید ریاضی داریم:

E(w) = sum_j_1_m (w_j*E(Y_j)) = sum_j_1_m (w_j*pr(C_j=true))

برای هر عبارت C_j که j =1...m، احتمال صادق نبودن آن احتمال این است که هیچ کدام از متغیرهای درون آن درست نباشند (نقیض آنها نادرست). پس چون احتمال درست/نادرست بودن 1/2 است:

pr(C_j = true) = (1-1/2^L_j) >= 1/2

که این نامساوی به دلیل L_j >=1 بودن درست است. پس:

E(w) <= sum_j_1_m(w_j*1/2) = 1/2 sum_j_1_m(w_j) >= 1/2 OPT

این نامساوی آخر از این به دست آمده که جمع وزنها برای جواب بهینه کران بالا است. (چون وزنها نامنفی هستند.)

(پایان اثبات)

دقت کنید که اگر L_j >= k باشد (برای همه عبارتها)، آنگاه الگوریتم ما 

1-1/2^k

تقریبی است. پس عملکرد آن روی MAS SAT ای که عبارتهای طولانی داشته باشد بهتر است.

مثال tight: حالتی که L_j = 3 باشد را MAX E3SAT می نامند. تقریب آن با این روش 7/8 به دست می آید که در صورتی که P=NP نباشد جواب بهتری برای آن نیست.

(اثبات: فصل 16.3 کتاب!)

------------------------------------

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

الگوریتم با ضریب تقریب 1/2 و تصادفی:

هر راس را با احتمال 1/2 در یکی از مجموعه ها می گذاریم. (مشابه سوال قبلی). این کار در واقع نمونه گیری یک جواب به صورت یکنواخت از فضای همه ی جوابها (حالتهای مساله) است.

اثبات ضریب تقریب: متغیر X_ij را 1 بگیرید اگر یال (i,j) در برش بود و 0 در غیر این صورت. Z را متغیر تصادفی بگیرید که جمع وزن یالهای برش است. پس:

Z = sum_(i,j) (w_ij*X_ij)

E(Z) = sum_(i_j) (w_ij*E(X_ij)) = sum_(i,j) (w_ij*pr( (i,j) in cut) )

OPT را هم جواب بهینه این مساله بگیرید. (برای این ورودی).

احتمال حضور یال (i,j) در برش به اندازه ی احتمال حضور هر سر آن در هر کدام از این مجموعه هاست که 2/4=1/2 است، پس:

E(Z) = 1/2 sum_(i,j) (w_ij) >= 1/2 OPT

چون وزنها نامنفی هستند، جواب بهینه کمتر مساوی جمع وزن ها است.

------------------------------------------------------------------------------------------

غیر تصادفی کردن

هدف: به دست آوردن الگوریتم قطعی با جوابی به خوبی امیدریاضی جواب الگوریتم تصادفی

برای مساله تصدیق بیشینه (MAX SAT)، به جای انتخاب تصادفی مقدار درست یا نادرست برای متغیر، یک روش دیگر به کار می بریم که همان مقدار امیدریاضی آن را بدهد. مقادیر متغیرهای یکی بعد از دیگری تعیین می شود.

اول فرض کنید ما فقط مقدار x_1 را قطعی تعیین می کنیم و بقیه با همان احتمال 1/2 تعیین می شوند. پس بهترین راه مقداردهی آن این است که امیدریاضی جواب را بیشینه کنیم. یعنی امیدریاضی w (وزن عبارتهای درست) را به شرط درست بودن x_1 و امیدریاضی w را به شرط نادرست بودن x_1 به دست بیاوریم و هر کدام مقدار x_1 را بیشتر کرد، آن را به عنوان مقدار x_1 در نظر می گیریم. این از نظر شهودی منطقی است، چون ماکسیمم از میانگین بیشتر است و امید ریاضی W میانگین آن روی دو مقدار ممکن x_1 است. در این حالت، یک نسخه ی الگوریتمی از امید ریاضی که حداقل نصف بهینه است به دست می آوریم که تعداد متغیرهای تصادفی را کمتر می کند.

به صورت ریاضی:

if E(W|x_1=true) >= E(W|x_1=false) ==> x_1 = true, else x_1 = false

(conditional probability) ==>

E(W) = E(W|x_1=true)Pr(x_1=true)+E(W|x_1=false)Pr(x_1=false) = 1/2 (E(W|x_1=true)+E(W|x_1=false)

b1=arg max( E(W|x_1=b1) ) ==> E(W|x_1=b1) > E(W)

یعنی انتخاب قطعی مقدار x_1 تضمین مقداری بزرگتر مساوی امیدریاضی الگوریتم کاملا تصادفی می دهد.

با استقرا برای حالتی که مقدار متغیرهای قبلی مشخص شده باشد برای متغیر x_i به همین صورت مقدار انتخاب می کنیم. بعد از تعیین آخرین متغیر، وزن به دست آمده از الگوریتم ما بیشتر مساوی مقدار به دست آمده از الگوریتم تصادفی است که آن هم از نصف بهینه بیشتر است. پس الگوریتم 1/2-تقریبی است.

برای اینکه بتوانیم این الگوریتم را اجرا کنیم باید بتوانیم این احتمالهای شرطی را محاسبه کنیم.

(پایان اثبات)

تکنیک غیرتصادفی کردن برای انواع زیادی از الگوریتم های تصادفی کار می کند که در آنها متغیرها به صورت مستقل مقداردهی می شوند و احتمالات شرطی در زمان چندجمله ای قابل محاسبه هستند. این کار گاهی روش امیدریاضی شرطی (method of conditional expectation) هم نامیده می شود، چون از امید ریاضی شرطی استفاده می کند. برای برش بیشینه هم با استدلالی دقیقا مثل سوال قبل می توان به نسخه ی غیرتصادفی 1/2-تقریبی برای آن رسید.

----------------------------------------------------------------

پرتاب سکه نامتقارن

چطور می توانیم الگوریتم تصادفی تصدیق بیشینه (MAX SAT) را بهبود دهیم؟ نشان می دهیم که با نامتقارن کردن احتمال مقادیر x_i یعنی با احتمالی به غیر از 1/2 می توانیم آن را بهبود دهیم. برای این کار ساده تر است MAX SAT هایی را در نظر بگیریم که هیچ عبارت یکه (با یک متغیر) x'_i ندارند، یعنی هیچ پرانتری ندارند که درون آن فقط نقیض یک متغیر باشد). بعدا نشان می دهیم که می توانیم این فرض را حذف کنیم. فرض کنید مقدار x_i را با احتمال p>1/2 درست (true) بگذاریم. مشابه قبل باید احتمال صادق بودن هر عبارت را به دست بیاوریم.

لم: با فرض درست بودن مقدار x_i با احتمال p>1/2 به صورت مستقل، احتمال اینکه هر عبارتی صادق باشد حداقل به اندازه ی مینیمم p و 1-p^2 است.

اثبات: اگر فقط یک متغیر داشته باشد احتمال p است. اگر عبارت طول حداقل 2 داشته باشد، احتمال درست بودن آن 

1-p^a*(1-p)^b

که در آن a تعداد متغیرهای نقیض شده و b تعداد متغیرهای معمولی در این عبارت است که a+b=L_j>=2 است. داریم:

1-p < 1/2 < p ==> pr( clause = true ) >= 1-p^(a+b) = 1-p^L_j >= 1-p^2

(پایان اثبات).

بهترین تضمین جواب را وقتی به دست می آوریم که p=1-p^2 باشد که نتیجه می دهد: p=1/2(sqrt(5)-1)=0.618

از این لم قضیه زیر نتیجه می شود:

قضیه: با کاری که گفته شد به الگوریتم تصادفی min(p,1-p^2)-تقریبی می رسیم، برای مساله تصدیق بیشینه که پرانتر فقط دارای یک متغیر نقیض شده نداشته باشد.

اثبات:

E(W) = sum_j_1_m (w_j*Pr(C_j=true) ) >= min(p,1-p^2)*sum_j_1_m( w_j ) >= min(p,1-p^2)*OPT

(پایان اثبات).

می خواهیم این را به تصدیق بیشینه تعمیم بدهیم، پس از کرانی بهتر از جمع وزن عبارتها استفاده می کنیم. فرض کنید برای هر i وزن عبارت فقط شامل این متغیر حداقل به اندازه وزن عبارت شامل فقط نقیض آن باشد؛ این بدون از دست رفتن عمومیت مساله برقرار است، چون در غیر این صورت تغییر متغیر می دهیم و نقیض آن را به عنوان متغیر می گیریم. v_i را وزن پرانتز شامل فقط نقیض x_i بگیرید و اگر وجود نداشت آن را 0 بگذارید.

لم: جواب بهینه کمتر مساوی مجموع وزن عبارتها منهای مجموع وزن پرانتزهای شامل فقط نقیض متغیرها است.

اثبات:

برای هر i جواب بهینه یا x_i را درست می گذارد یا نقیض آن را. پس وزن جواب بهینه نمی تواند شامل هر دوی عبارت های تک متغیری خود متغیر و نقیض آن باشد و وزن نقیض هر متغیر را کمتر از خودش گرفتیم پس لم درست است.

قضیه: می توانیم الگوریتم تقریبی تصادفی با ضریب 1/2(sqrt(5)-1) به دست بیاوریم. (برای مساله تصدیق بیشینه).

اثبات: عبارتهای شامل فقط نقیض متغیرها را در نظر نمی گیریم (طبق لم). از قبل هم احتمال درست بودن هر عبارت را به دست آوردیم از این دو با هم حکم نتیجه می شود.

این الگوریتم می تواند با روشی که گفته شد غیرتصادفی شود.