Кіріспе
Орташа шешім құны кез келген әдіспен бірдей. Есептеудің математикалық талдауы. Есептеу күрделілігі және оңтайландыру салаларында "тегін түскі асқа" қатысты теорема – математикалық мәселелердің белгілі бір түрлері үшін шешім табудың есептік құны, осы сыныптағы барлық мәселелер бойынша орташа алғанда, кез келген шешім әдісі үшін бірдей болады деген тұжырым. Бұл атау "тегін түскі ас деген жоқ" деген мақалға сілтеме жасайды, яғни ешбір әдіс "қысқа жол" ұсынбайды. Бұл, іздеу кеңістігі ықтималдық тығыздық функциясы ретінде қарастырылған жағдайда ғана дұрыс. Егер іздеу кеңістігінде жасырын құрылым болса (мысалы, дифференциалдауға болатын функция болса), оны кездейсоқ іздеуден тиімдірек пайдалануға болады (мысалы, оңтайландырудағы Ньютон әдісі) немесе тіпті іздеусіз анықталатын жабық формадағы шешімдер (мысалы, квадраттық полиномның экстремалды мәндері) болса, онда бұл теорема қолданылмайды. Мұндай ықтималдық болжамдарда, белгілі бір типтегі мәселені шешуге арналған барлық процедуралардың нәтижелері статистикалық тұрғыдан бірдей болады. Дэвид Уолперт пен Уильям Г. Макредидің іздеу және оңтайландыру мәселелерімен байланысты енгізген түрлі-түсті сипаттамасы бойынша, мұндай жағдайды "тегін түскі ас жоқ" деп айтуға болады. Уолперт бұрын машиналық оқыту (статистикалық қорытынды) үшін "тегін түскі ас" теоремаларын жасаған. Уолперттің мақаласы жарияланбастан бұрын Каллен Шаффер осы теоремалардың бірінің шектеулі нұсқасын тәуелсіз түрде дәлелдеп, индукция мәселесі бойынша машиналық оқыту зерттеулерінің қазіргі жай-күйін сынау үшін пайдаланған. "Тегін түскі ас жоқ" метафорасында әр "ресторанның" (мәселе шешу процедурасы) әр "тағамға" (мәселе) "баға" (мәселені шешудегі процедураның тиімділігі) сәйкес келетін "менюі" болады. Ресторандардың мәзірлері бір-біріне ұқсас, бірақ бағалар бір рестораннан екіншісіне ауысады. Барлық тағамдарды тең мүмкіндікпен таңдайтын адам үшін түскі ас құнының орташа көрсеткіші ресторан таңдауына байланысты емес. Алайда, ет жеушімен бірге үнемі тамақтанатын вегетариан түскі асқа орташа бағаны жоғары төлеуі мүмкін. Орташа құнды әдістемелік тұрғыдан төмендету үшін, алдын ала білу қажет: а) қандай тағамды таңдайтынымызды және б) әртүрлі ресторандарда оның құны қандай болатынын. Яғни, мәселелерді шешудегі тиімділікті арттыру үшін, алдын ала ақпаратты пайдаланып, процедураларды мәселелерге сәйкестендіру керек. Бұл шарт іс жүзінде толыққанды орындалмайды.
mathematical analysis of computing
In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. The name alludes to the saying "no such thing as a free lunch", that is, no method offers a "short cut". This is under the assumption that the search space is a probability density function. It does not apply to the case where the search space has underlying structure (e. g., is a differentiable function) that can be exploited more efficiently (e. g., Newton's method in optimization) than random search or even has closed form solutions (e. g., the extrema of a quadratic polynomial) that can be determined without search at all. For such probabilistic assumptions, the outputs of all procedures solving a particular type of problem are statistically identical. A colourful way of describing such a circumstance, introduced by David Wolpert and William G. Macready in connection with the problems of search and optimization,
is to say that there is no free lunch. Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). Before Wolpert's article was published, Cullen Schaffer independently proved a restricted version of one of Wolpert's theorems and used it to critique the current state of machine learning research on the problem of induction. In the "no free lunch" metaphor, each "restaurant" (problem solving procedure) has a "menu" associating each "lunch plate" (problem) with a "price" (the performance of the procedure in solving the problem). The menus of restaurants are identical except in one regard – the prices are shuffled from one restaurant to the next. For an omnivore who is as likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But a vegan who goes to lunch regularly with a carnivore who seeks economy might pay a high average cost for lunch. To methodically reduce the average cost, one must use advance knowledge of a) what one will order and b) what the order will cost at various restaurants. That is, improvement of performance in problem solving hinges on using prior information to match procedures to problems. This condition does not hold precisely in practice,
Шолу
Кейбір есептеу проблемалары кандидат шешімдер кеңістігінде жақсы шешімдерді іздеу арқылы шешіледі. Бағалау үшін үміткер шешімдерді қайта-қайта таңдаудың сипаттамасы іздеу алгоритмі деп аталады. Белгілі бір мәселеде әртүрлі іздеу алгоритмдері әртүрлі нәтижелер бере алады, бірақ барлық проблемалар бойынша олар ешбір айырмашылықты көрсетпейді. Осыдан келіп, егер алгоритм кейбір проблемаларда жақсы нәтижелерге жетсе, онда ол басқа проблемаларда нашар нәтижелерге ұшырауы керек. Осы тұрғыдан алғанда, іздеуде тегін нәрсе жоқ. "Тегін түскі ас жоқ" деген нәтижелер алгоритмдерді проблемаларға сәйкестендірудің орташа өнімділігі, барлық проблемаларға бірдей алгоритмді қолданудан жоғары екенін көрсетеді. Игель мен Туссент.
Вольперт және Макриди алгоритм кандидат шешімді ешқашан қайта бағаламайды және алгоритмнің өнімділігі нәтижелер бойынша өлшенеді деп есептейді. Мысалы, егер әрбір кандидат шешімі 300 0 және 1 сандарының тізбегімен кодталған болса, ал жақсылық көрсеткіштері 0 және 1 болса, онда көптеген объективті функциялардың Колмогоров күрделілігі кем дегенде 2300 биттей болады, ал бұл Ллойдтың 1090 ≈ 2299 бит шегінен артық. Осыдан, бастапқы "тегін түскі ас жоқ" теоремасы физикалық компьютерде сақталатын мәліметтерге қолданылмайды; оның орнына, "нақтыланған" тегін түскі асқа қатысты теоремалар қолданылуы керек. Сондай-ақ, NFL нәтижелері есептеуге келмейтін функцияларға да қатысты екені дәлелденді.
Ресми қысқаша мазмұны
барлық объективті функциялардың жиыны f:X→Y, мұндағы X – шекті шешім кеңістігі және Y – шекті позит. X-тің барлық пермутацияларының жиыны J болып табылады. F кездейсоқ айнымалысы J жиынындағы барлық j үшін , F o j кездейсоқ айнымалысымен үлестіріледі, және барлық f үшін P(F o j = f) = P(F = f o j−1). a(f) іздеу алгоритмінің a кіріс f бойынша шығарылымын білдірсін. Егер барлық іздеу алгоритмдері a және b үшін a(F) және b(F) бірдей үлестірілген болса, онда F NFL үлестіріміне ие. Бұл шарт тек қана егер F және F o j барлық j үшін бірдей үлестірілген болса ғана орындалады. Жақында жиындық-теориялық NFL теоремалары кез келген кардиналдық X және Y үшін жалпыландырылды.
Let a(f) denote the output of search algorithm a on input f. If a(F) and b(F) are identically distributed for all search algorithms a and b, then F has an NFL distribution. This condition holds if and only if F and F o j are identically distributed for all j in J. Set theoretic NFL theorems have recently been generalized to arbitrary cardinality and .
Шығу тегі
Вулперт пен Макриди екі негізгі НФЛ теоремасын келтіреді, біріншісі іздеу барысында өзгермейтін мақсатты функцияларға, ал екіншісі өзгеруі мүмкін мақсатты функцияларға қатысты. Бірнеше ескерту бар:
Теориялық тұрғыдан, жалпы мақсаттағы, дерлік әмбебап оптимизатор бар. Кез келген іздеу алгоритмі дерлік барлық мақсатты функцияларда жақсы өнім көрсетеді.
Бірлескен даму
Вольперт пен МакКреди эволюциялық оптимизациядағы «тегін мүмкіндіктер» бар екенін дәлелдеді. Олардың талдауы «өздік ойын» мәселелерін қамтиды. Мұндай мәселелерде ойыншылар жиыны чемпионды шығару үшін бірлесіп жұмыс істейді, ал ол кейін көп ойыншылы ойында бір немесе бірнеше қарсыласпен күреседі. Яғни, мақсат – жақсы ойыншыны алу, бірақ мақсатты функциясыз. Әр ойыншының (күдікті шешімнің) сапасы оның басқалармен қаншалықты жақсы ойнайтынына қарай бағаланады. Алгоритм жақсырақ ойыншыларды алу үшін ойыншыларды және олардың ойын сапасын пайдалануға тырысады. Алгоритм ең жақсы деп таныған ойыншы чемпион атанды. Вольперт пен МакКреди кейбір коэволюциялық алгоритмдердің чемпиондардың сапасы тұрғысынан басқа алгоритмдерден артық екенін көрсетті. Өздік ойын арқылы чемпионды жасау эволюциялық есептеу және ойын теориясы үшін қызығушылық тудырады. Бұл нәтижелер биологиялық түрлердің коэволюциясына қатысты емес, себебі ол чемпиондарды шығармайды.