در جستجو و بهینه سازی از ناهار مجانی خبری نیست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
شرح گرافیکی نتایج براهین NFL برای الگوریتم های هیوریستیک: تمام هیوریستیک ها میانگین هزینه اجرای یکسانی دارند. یک هیوریستیک ممکن است از یک هیوریستیک دیگر در حل مسئله یا دامنه ای از مسائل بهتر عمل کند، اما در دامنه دیگری از مسائل بدتر باشد. علاوه بر این، هر چقدر در دامنه خودش بهتر باشد در باقی دامنه ها بدتر خواهد بود.

در علوم کامپیوتر مواقعی پیش می آید که خروجی تمام روندهایی که مشغول حل یک نوع مسئله خاص هستند از لحاظ آماری مشابه هم می باشند. دیوید ولپرت و ویلیام مک ردی بیان زیبایی را برای چنین وضعیتی در مسائل جستجو[۱] و بهینه سازی [۲] ارائه داده‌اند، و آن هم این بود که از "ناهار مجانی خبری نیست". ولپرت قبلاً براهین "هیچ ناهار مجانی" را برای یادگیری ماشین(استنتاج آماری)[۳] به دست آورده بود. قبل از اینکه مقاله ولپرت منتشر شود، کالن شفر خلاصه ای از کار منتشر نشده ولپرت را با اصطلاحات متفاوت به جامعه علمی عرضه کرد.[۴]

در اصطلاح "هیچ ناهار مجانی"، هر رستوران(رویه حل مسئله) یک لیست غذا دارد که هر پرس غذا(مسئله) با یک قیمت(اجرای رویه برای حل مسئله) نسبت معینی دارد. لیست های غذای رستوران ها به جز در یک مورد خاص مشابه هم هستند، آن هم این است که ترتیب قیمت ها در یک رستوران نسبت به رستوران بعد به هم ریخته می شود. برای یک همه چیزخوار که احتمال انتخاب غذاها برای او یکسان است، هزینه میانگین به رستورانی که انتخاب می کند بستگی نخواهد داشت. اما برای یک گیاهخوار که به طور منظم با دوست گوشتخوارش که به دنبال هزینه کمتر است به رستوران می رود، برای هر پرس غذا میانگین هزینه بالایی را پرداخت می کند. برای اینکه هزینه میانگین را کاهش دهیم باید اطلاعات مناسبی در رابطه با الف) هر کس چه چیزی سفارش می دهد ، ب) آن سفارش در رستوران های مختلف قیمتش چقدر می شود، داشته باشیم. در واقع برای حل این نوع مسائل نیاز به اطلاعات پیش زمینه ای در رابطه با رویه داریم تا بتوانیم اجرا را بهینه تر کنیم.[۲][۴]

به بیان دیگر، زمانی که توزیع احتمالی روی نمونه های مسئله، نتایج توزیع شده مشابهی داشته باشند، دیگر خبری از ناهار مجانی نیست. در مورد جستجو، مسئله مورد نظر یک تابع عینی است، و نتیجه رشته ای از مقادیر است که از بررسی پاسخ های کاندید در دامنه تابع به دست می آیند. برای توصیف نوعی از نتایج، بهینه سازی رویه، همان جستجو است. در جستجو هیچ ناهاری مجانی نیست اگر و فقط اگر توزیع روی توابع عینی تحت جابجایی فضای پاسخ های کاندید، ثابت باشد.[۵][۶][۷] این حالت دقیقاً در عمل وجود ندارد[۶]، اما برهان "(تقریباً) هیچ ناهار مجانی" نشان می دهد که تقریباً وجود دارد. [۸]

خلاصه[ویرایش]

بعضی مسائل محاسباتی با جستجو در راه حل های مناسب در یک فضا از پاسخ های کاندید حل می شوند. انتخاب مکرر پاسخ های کاندید برای بررسی را الگوریتم جستجو می نامند. در مسائل متفاوت این الگوریتم نتایج متفاوتی خواهد داشت، اما روی تمام مسائل، غیر قابل تشخیص اند. از این نتیجه می گیریم که اگر یک الگوریتم روی یک سری از مسائل نتایج خوبی بدست آورد، باید به مسائل دیگر اهمیت کمتری بدهد. در این حالت هیچ ناهار مجانی در جستجو نداریم[۱]. به طور مشابه، همانطور که شفر گفته بود[۴]، هزینه اجرا ذخیره شده است. جستجو معمولاً با عنوان بهینه سازی شناخته می شود، پس می توان گفت که در بهینه سازی ناهار مجانی وجود ندارد.[۲]

"نظریه "هیچ ناهار مجانی" ولپرت و مک ردی"، آن طور که خودشان به زبان ساده بیان کرده‌اند به این صورت است، "هر دو الگوریتم دلخواهی برابرند زمانی که هزینه اجرایشان روی تمام مسائل ممکن میانگین گرفته شود.[۹] نتیجه "هیچ ناهار مجانی" نشان می دهد که اختصاص هر مسئله به یک الگوریتم خاص هزینه اجرا را نسبت به استفاده از یک الگوریتم ثابت کمتر می کند. ایجل، توسینت[۶]، و انگلیش[۷] شرط عمومی را برقرار کردند که تحت آن هیچ ناهار مجانی نخواهد بود. در حالی که به لحاظ فیزیکی ممکن است، اما دقیقاً قابل اجرا نیست.[۶][۸] دراست، جنسن، و وگنر برهانی را اثبات کردند که آن طور که خودشان می گفتند در عمل نشان می دهد که "تقریباً" هیچ ناهار مجانی نیست.[۸]

برای اینکه بتوانیم بستر نظری مناسب تری فراهم کنیم، فردی را در نظر بگیرید که می خواهد یک مسئله را بهینه سازی کند. با در نظر داشتن این که چرا این مسئله به وجود آمده، آن فرد می تواند آز آن دانش پیش زمینه برای انتخاب الگوریتم مناسب برای حل مسئله استفاده کند. اگر آن فرد نداند که چطور از دانش پیش زمنیه خود استفاده کند، یا اگر دانش پیش زمینه ای نداشته باشد، آنگاه با این مسئله مواجه می شود که آیا بعضی الگوریتم ها در دنیای واقعی بهتر از دیگر الگوریتم ها عمل می کنند یا نه. نویسندگان برهان "(تقریباً) هیچ ناهار مجانی نیست" پاسخ این مسئله را منفی می دانند، اما فکر می کنند امکان کاربردی کردن الگوریتم وجود دارد.[۸]

هیچ ناهاری مجانی نیست(NFL)[ویرایش]

یک "مسئله"، یک تابع عینی است که پاسخ های کاندید را با مقادیر خوبی نسبت می دهد. یک الگوریتم جستجو یک تابع عینی را به عنوان ورودی می گیرد و پاسخ های کاندید را تک به تک ارزشیابی می کند. خروجی الگوریتم رشته مقادیر خوبی مشاهده شده است.[۱۰][۱۱]

ولپرت و مک ردی تصریح می کنند که یک الگوریتم هیچ گاه یک پاسخ کاندید را دوباره ارزشیابی نمی‌کند، و هزینه اجرا الگوریتم روی خروجی ها محاسبه می شود[۲]. برای آسانی کار، هیچ عمل تصادفی در الگوریتم های قائل نمی‌شویم. تحت این شرایط، وقتی یک الگوریتم جستجو روی تمام ورودی های ممکن اجرا می شود، هر پاسخ خروجی را دقیقاً یک بار تولید می کند[۷]. چون که هزینه اجرا روی خروجی ها محاسبه می شود، الگوریتم ها از این نظر که در چه بازه زمانی سطح خاصی از اجرا را بدست می آورند غیر قابل تشخیص اند.

بعضی از ارزشیابی های هزینه اجرا نشان می دهد که الگوریتم های جستجو در بهینه سازی تابع عینی، خیلی خوب عمل می کنند. در واقع، به نظر می رسد که هیچ برنامه جالبی از الگوریتم های جستجو وجود ندارد که بهینه سازی نکند. یکی از روش های ارزشیابی اجرا به کارگیری کمترین شاخص از کمترین مقدار در رشته خروجی است. این تعداد ارزشیابی های لازم برای کمینه کردن تابع عینی است. برای بعضی از الگوریتم ها، زمان لازم برای یافتن کمینه به تعداد ارزشیابی ها بستگی دارد.[۷]

براهین اصلی هیچ ناهار مجانی نیست(NFL) فرض می کنند که تمام توابع عینی به طور مساوی احتمال ورودی گرفتن الگوریتم جستجو را دارند[۲]. بنابراین گفته می شود یک NFL وجود دارد اگر و فقط اگر به هم ریختن توابع عینی روی احتمال آن ها هیچ تاثیری نداشته باشد[۶][۷]. با اینکه این شرط NFL از لحاظ فیزیکی ممکن است، اما در عمل به کار نمی‌آید.[۶]

تفسیر واضح نقیض NFL قاعدتاً "ناهار مجانی وجود دارد" است. اما این گمراه کننده است. NFL یک درجه است نه یک گزاره صفر و یک منطقی. اگر شرایط NFL دقیقاً برقرار باشد آنگاه تمام الگوریتم ها برای تمام توابع عینی تقریباً نتایج یکسانی خواهند داشت.[۷] باید توجه داشت که نقیض NFL نشان می دهد که تنها آن الگوریتم ها روی هم رفته با اندازه گیری هزینه اجرا با هم برابر نیستند. برای اندازه گیری سود اجرا، الگوریتم ها ممکن است کاملاً یا تقریباً برابر بمانند.[۷]

در حالت نظری، تمام الگوریتم ها همیشه در بهینه سازی خیلی خوب اجرا می شوند. این یعنی اینکه یک الگوریتم با تعداد نسبتاً کمی از ارزشیابی ها، پاسخ های خوبی برای تقریباً تمام توابع عینی بدست می آورد[۱۱]. دلیلش این است که تقریباً تمام توابع عینی درجه بالایی از کلماگوراف از خود بروز می دهند. این نشان دهنده یک بی نظمی و غیرقابل پیش بینی بودن شدید است. تمام سطوح خوبی ها به طور مساوی به تمام پاسخ های کاندید ارائه می شوند، و پاسخ های خوب در تمام فضای کاندیدها پراکنده می شوند. الگوریتم جستجو ندرتاً بیشتر از بخش کوچکی از کاندیدها را برای محل یابی یک پاسخ خیلی خوب ارزشیابی می کند.[۱۱]

در عمل تمام توابع عینی و الگوریتم ها از چنان پیچیدگی کولماگورافی برخوردارند که هیچ گاه بر انگیخته نمی‌شوند[۵][۷][۱۱] . در توابع عینی نمونه یا الگوریتم، اطلاعات بیشتری از آنچه ست لوید تخمین زده بود که جهان قابلیت نگهداری آن را دارد وجود دارد. به طور مثال، اگر هر پاسخ کاندید به شکل رشته ای از 300 0 و 1 کد شود، و مقادیر ارزش خوبی 0 و 1 باشند، آنگاه اکثر توابع عینی پیچیدگی کولماگوراف با اندازه حداقل 2300 دارند[۱۲]، و این بزرگتر از مرز 2299 لوید است. نتیجه می گیریم تمام برهان "هیچ ناهار مجانی" در دنیای فیزیکی صدق نمی‌کند. در حالت عملی، الگوریتم هایی که آنقدر کوچک هستند که در نرم‌افزارها به کار آیند در مقابل آن های که بزرگترند، اجرای بهتری دارند.

بیان ریاضی NFL[ویرایش]

Y^X مجموعه ای از تمام توابع عینی f:XY است، که X فضایی محدود از پاسخ هاست و Y مجموعه جزئاً مرتب و متناهی. مجموعه تمام جایگشت های X از J است. یک متغیر تصادفی مانند F روی Y^X توزیع شده است. برای تمام jهای در J، هر F o j متغیری تصادفی است که روی Y^X توزیع شده است، با احتمال P(F o j = f) = P(F = f o j–1 برای تمام f در Y^X.

فرض کنید (a(f خروجی الگوریتم جستجوی a برای ورودی f باشد. اگر (a(F و (b(F به طور یکسان برای تمام الگوریتم های جستجو a و b توزیع شده باشند، آنگاه F یک توزیع NFL دارد. این شرط این امر را در نظر دارد که اگر و فقط اگر F و F o j به طور مشابه روی j برای تمام J ها توزیع شده باشند[۶][۷]. به بیان دیگر، هیچ ناهار مجانی برای الگوریتم های جستجو نخواهد بود اگر و فقط اگر توزیع توابع عینی تحت جایگشت فضای پاسخ ها ثابت باشد. قسمت "فقط اگر" اولین بار توسط شوماخر در پایان نامه دکترایش با عنوان "جستجوی جعبه سیاه – چارچوب ها و روش ها" منتشر شد.(دانشگاه تنسی) براهین NFL اخیراً به شمارش های دلخواه X و Y عمومی سازی شده‌اند.

براهین اصلی NFL[ویرایش]

ولپرت و مک‌ردی دو برهان اصلی NFL ارائه دادند، اولی مربوط به توابع هدفی است که هنگام اجرای رویه تغییر نمی‌کنند، و دومی مربوط به آنهایی است که تغییر می‌کنند.[۲]

برهان 1: برای هر جفت الگوریتم a1 و a2 داریم:

\sum_f P(h_m^y | f, m, a_1) = \sum_f P(h_m^y | f, m, a_2).

در واقع این تساوی می‌گوید اگر تمام توابع f دارای احتمال یکسان باشند، احتمال مشاهده‌ی رشته‌ای دلخواه از m مقدار در هنگام جستجو به الگوریتم جستجو بستگی ندارد. برهان 2 بیان دقیق‌تری از نتایج NFL را برای توابع عینی متغیر با زمان ارائه می‌کند.

بررسی نتایج NFL[ویرایش]

یکی از تفاسیر قراردادی اما نه چندان دقیق از نتایج NFL این است که " یک استراتژی بهینه سازی همه کاره جهانی از لحاظ نظری غیرممکن است، و تنها راهی که یک الگوریتم در اجرای یک عمل می تواند از الگوریتم ها دیگر بهتر عمل کند این است که برای آن عمل خاص طراحی شده باشد"[۱۳]

یک استراتژی بهینه سازی تقریباً همه کاره جهانی به لحاظ نظری وجود دارد. هر الگوریتم جستجو رو تمام توابع عینی تقریباً خوب عمل می کند.[۱۱]
یک الگوریتم ممکن است در حل یک مسئله از الگوریتم دیگر بهتر عمل کند اگر هیچ کدام برای حل آن مسئله خاص طراحی نشده باشند. ممکن است هر دو از بدترین الگوریتم ها برای حل آن مسئله باشند. ولپرت و مک ردی یک درجه اندازه گیری برای "تطابق" بین یک مسئله و الگوریتم بدست آورده‌اند[۲]. اینکه بگوییم یک الگوریتم با یک مسئله بهتر از دیگری تطابق دارد بدین معنا نیست که بگوییم که یک از آنها برای حل مسئله طراحی شده است.
در عمل، بعضی الگوریتم ها، پاسخ های کاندید را دوباره ارزشیابی می کنند. برتری الگوریتمی که هیچ گاه کاندیدها رو دوباره ارزشیابی نمی‌کند به آن که این کار را می کند هیچ ربطی به اینکه یکی از آنها برای حل آن مسئله طراجی شده باشند را ندارد.
تقریباً برای تمام توابع عینی، طراحی مخصوص تقریباً تصادفی است. اگر یک تابع عینی تجزیه ناپذیر را به ما داده باشند، هیچ دلیلی ندارد که آن را بر الگوریتم دیگری ترجیح دهیم. اگر الگوریتم انتخاب شده بهتر از بقیه عمل کند، نتیجه یک روی داد شانسی است.

در عمل، فقط توابع عینی تجزیه پذیر قابلیت ذخیره سازی در حافظه کامپیوترها را دارند، و چنین نیست که یک الگوریتم رو تمام توابع عینی تجزیه پذیر به خوبی عمل کند. عموماً به لحاظ هزینه اجرا بهتر است دانش پیش زمینه ای در رابطه با مسئله داشته باشیم.[۱۱]

در عمل انسان ها دانش های پیش زمنیه کمی در اختیار دارند. در بعضی حالات هم دانش پیش زمینه کمک شایان توجهی در کاهش هزینه اجرا ندارد. باید در نظر داشت که زمان انسان نسبت به زمان کامپیوتر خیلی با ارزش تر است. مواقع زیادی پیش می آید که یک شرکت ترجیح می دهد یک تابع را با یک برنامه کامپیوتری دستکاری نشده با سرعت کمی بهینه کند تا اینکه آن را به یک برنامه دستکاری شده توسط انسان و با سرعت بالا انجام دهد. نتایج NFL نمی‌گویند که به مسائل بدون الگوریتم به طور تصادفی الگوریتم ندهیم. هیچ کس تا به حال تعداد مسائل عملی که یک الگوریتم در آن سریعاً به جواب خوب می رسد را مشخص نکرده است. و یک ناهار مجانی عملاً وجود دارد که اصلاً هم با مبانی نظری آن در تضاد نیست. اجرا پیاده سازی یک الگوریتم در کامپیوتر در مقابل ارزش زمان انسان و سود یک جواب مناسب هزینه بسیار کمی دارد. اگر یک الگوریتم موفق به پیدا کردن راه حلی مناسب برای یک مسئله در زمانی مناسب باشد آنگاه با هزینه ای کم به سودی زیاد رسیده‌ایم، وگرنه چیزی از دست نداده ایم.

ناهار مجانی هم تکاملی[ویرایش]

ولپرت و مک ردی اثبات کردند که در بهینه سازی هم تکاملی ها ناهار مجانی وجود دارد[۹]. تحلیل آنها مسائل خود-بازی را پوشش می دهد که در آن مجموعه ای از بازیکنان با هم فعالیت می کنند تا یک قهرمان بدست آید، که بعداً یک یا چند رقیب را در بازی های بعد به کار می گیرد[۹]. این بدان معناست که، هدف این است که بازیکن خوبی بدست آوریم، اما بدون یک تابع عینی. خوبی هر بازیکن(پاسخ کاندید) با مشاهده نحوه رقابتش با دیگران ارزیابی می شود. الگوریتم بازیکن ها و کیفیت بازی آن ها را می گیرد تا بازیکنان بهتری انتخاب کند. بازیکنی که الگوریتم اول قرار دهد قهرمان می شود. ولپرت و مک ردی نشان دادند که بعضی از الگوریتم های هم تکاملی در انتخاب قهرمان نسبت به الگوریتم های دیگر بهتر عمل می کنند. تولید یک قهرمان از طریق خود-بازی یکی از مباحث مهم در محاسبات تکاملی و نظریه بازی هاست. نتایج روی هم تکاملی گونه های زیستی قابل اجرا نیست زیرا در این حالات قهرمانی وجود ندارد.

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).
  2. ۲٫۰ ۲٫۱ ۲٫۲ ۲٫۳ ۲٫۴ ۲٫۵ ۲٫۶ Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization," IEEE Transactions on Evolutionary Computation 1, 67. http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf
  3. Wolpert, David (1996), "“The Lack of A Priori Distinctions between Learning Algorithms," Neural Computation, pp. 1341-1390.
  4. ۴٫۰ ۴٫۱ ۴٫۲ Schaffer, Cullen (1994), "A conservation law for generalization performance," International Conference on Machine Learning, H. Willian and W. Cohen, Editors. San Francisco: Morgan Kaufmann, pp.295-265.
  5. ۵٫۰ ۵٫۱ Streeter, M. (2003) "Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold," Genetic and Evolutionary Computation—GECCO 2003, pp. 1418–1430.
  6. ۶٫۰ ۶٫۱ ۶٫۲ ۶٫۳ ۶٫۴ ۶٫۵ ۶٫۶ Igel, C., and Toussaint, M. (2004) "A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions," Journal of Mathematical Modelling and Algorithms 3, pp. 313–322.
  7. ۷٫۰ ۷٫۱ ۷٫۲ ۷٫۳ ۷٫۴ ۷٫۵ ۷٫۶ ۷٫۷ ۷٫۸ English, T. (2004) No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227-234. http://BoundedTheoretics.com/CEC04.pdf
  8. ۸٫۰ ۸٫۱ ۸٫۲ ۸٫۳ S. Droste, T. Jansen, and I. Wegener. 2002. "Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions," Theoretical Computer Science, vol. 287, no. 1, pp. 131-144.
  9. ۹٫۰ ۹٫۱ ۹٫۲ Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches," IEEE Transactions on Evolutionary Computation, 9(6): 721-735
  10. A search algorithm also outputs the sequence of candidate solutions evaluated, but that output is unused in this article.
  11. ۱۱٫۰ ۱۱٫۱ ۱۱٫۲ ۱۱٫۳ ۱۱٫۴ ۱۱٫۵ English, T. M. 2000. "Optimization Is Easy and Learning Is Hard in the Typical Function," Proceedings of the 2000 Congress on Evolutionary Computation: CEC00, pp. 924-931. http://www.BoundedTheoretics.com/cec2000.pdf
  12. Li, M., and Vitányi, P. (1997) An Introduction to Kolmogorov Complexity and Its Applications (2nd ed.), New York: Springer.
  13. Ho, Y.C., Pepyne, D.L. (2002), "Simple Explanation of the No-Free-Lunch Theorem and Its Implications," Journal of Optimization Theory and Applications 115, 549.

جستارهای وابسته[ویرایش]

پیوند به بیرون[ویرایش]