У математичком фолклору, теорема „нема бесплатног ручка” (НФЛ) (понекад у множини) Давида Волперта и Вилијама Макредија, алудира на изреку „бесплатан ручак не постоји”. У овом случају намеравано значење је да не постоје лаке пречице за дизајнирање алгоритама оптимизације. Појавила се у раду из 1997. године „Теореме нема бесплатног ручка за оптимизацију” (енгл. No Free Lunch Theorems for Optimization). Волперт је претходно извео теореме „нема бесплатног ручка” за машинско учење.

Године 2005, Волперт и Макреди су изјавили да прва теорема у њиховом раду значи да су „било која два алгоритма за оптимизацију еквивалентна када се њихове перформансе усредсреди преко свих могућих проблема”.

Теорема „нема бесплатног ручка” (НФЛ) је лако изрецива и лако разумљива последица теорема које су Волперт и Макреди заправо доказали. Она је објективно слабија од доказаних теорема и стога их не обухвата. Разни истраживачи су суштински проширили рад Волперта и Макредија. У смислу тога како се НФЛ теорема користи у контексту истраживачке области, нема бесплатног ручка у претрази и оптимизацији је поље посвећено сврхама математичке анализе података за статистички идентитет, посебно претраге и оптимизације.

Док неки научници тврде да НФЛ преноси важан увид, други тврде да је НФЛ од малог значаја за истраживање машинског учења.

Пример Претпоставимо једноставан модел универзума који постоји тачно два дана и сваки дан има једно стање: сунчано или облачно. Овај универзум има тачно четири могуће историје: (сунчано, облачно): универзум је сунчан 1. дана, а облачан 2. дана (сунчано, сунчано) (облачно, облачно) (облачно, сунчано)

Свака стратегија предвиђања која успева за историју бр. 2, предвиђајући да ће бити сунчано 2. дана ако је сунчано 1. дана, пропашће за историју бр. 1, и обрнуто. Ако су све историје једнако вероватне, онда ће свака стратегија предвиђања имати исти резултат, са истом стопом тачности од 0,5.

Порекло Волперт и Макреди дају две НФЛ теореме које су уско повезане са фолклорном теоремом. У свом раду они наводе:

Прва теорема поставља хипотезу о функцијама циља које се не мењају док је оптимизација у току, а друга претпоставља функције циља које се могу мењати.

Теорема се може еквивалентно формулисати на следећи начин:

Овде, слепа претрага значи да се у сваком кораку алгоритма, елемент бира насумично са униформном расподелом вероватноће од елемената из који претходно нису били изабрани.

У суштини, ово говори да када су све функције f једнако вероватне, вероватноћа уочавања произвољног низа од m вредности током оптимизације не зависи од алгоритма. У аналитичком оквиру Волперта и Макредија, перформанса је функција низа посматраних вредности (а не нпр. у реалном времену извршавања), па лако следи да сви алгоритми имају идентично распоређене перформансе када су функције циља равномерно насумично извучене, као и да сви алгоритми имају идентичне средње перформансе. Али идентичне средње перформансе свих алгоритама не имплицирају Теорему 1, и стога фолклорна теорема није еквивалентна оригиналној теореми.

Теорема 2 успоставља сличан, али „суптилнији”, НФЛ резултат за временски променљиве функције циља.

Мотивација НФЛ теореме изричито нису биле мотивисане питањем шта се може закључити (у случају НФЛ-а за машинско учење) или пронаћи (у случају НФЛ-а за претрагу) када је „окружење униформно насумично”. Уместо тога, униформна насумичност је коришћена као алат за поређење броја окружења за која алгоритам А надмашује алгоритам Б са бројем окружења у којима Б надмашује А. НФЛ нам говори да (прикладно пондерисано) има исто толико окружења у оба ова скупа.

Ово важи за многе дефиниције тога шта је тачно „окружење”. Конкретно, постоји једнако толико априорних расподела (прикладно пондерисаних) у којима алгоритам учења А побеђује Б (у просеку) и обрнуто. Ова изјава о скуповима априорних расподела (енгл. sets of priors) је оно што је најважније у вези са НФЛ-ом, а не чињеница да било која два алгоритма раде подједнако за једну, специфичну априорну расподелу која додељује једнаку вероватноћу свим окружењима.

Иако је НФЛ важан за разумевање фундаменталног ограничења за скуп проблема, он не говори ништа о свакој појединачној инстанци проблема која се може појавити у пракси. То јест, НФЛ наводи оно што је садржано у његовим математичким исказима и ништа више од тога. На пример, примењује се на ситуације у којима је алгоритам фиксан априори, а проблем најгорег случаја за фиксни алгоритам се бира апостериори. Стога, ако имамо „добар” проблем у пракси или ако можемо да изаберемо „добар” алгоритам учења за дату конкретну инстанцу проблема, онда НФЛ не спомиње никаква ограничења у вези са овом конкретном инстанцом проблема. Иако се НФЛ може чинити контрадикторним резултатима из других радова који сугеришу генерализацију алгоритама учења или хеуристике претраживања, важно је разумети разлику између тачне математичке логике НФЛ-а и њене интуитивне интерпретације.

Импликације

Да би се илустровала једна од контраинтуитивних импликација НФЛ-а, претпоставимо да фиксирамо два алгоритма надгледаног учења, Ц и Д. Затим узоркујемо циљну функцију f да бисмо произвели скуп улазно-излазних парова, d. Питање је како да изаберемо да ли да тренирамо Ц или Д на d, како бисмо направили предвиђања о томе који би излаз био повезан са тачком која лежи изван d.

У скоро целој науци и статистици је уобичајено да се на ово питање одговори – да се бира између Ц и Д – покретањем унакрсне валидације на d са та два алгоритма. Другим речима, да бисмо одлучили да ли да генерализујемо из d са Ц или Д, гледамо који од њих има боље перформансе ван узорка када се тестира унутар d.

Пошто су Ц и Д фиксни, ова употреба унакрсне валидације за одабир између њих је сама по себи алгоритам, тј. начин генерализације из произвољног скупа података. Назовимо овај алгоритам А. (Може се рећи да је А поједностављен модел самог научног метода.)

Могли бисмо такође да употребимо анти-унакрсну валидацију да бисмо направили наш избор. Другим речима, могли бисмо да бирамо између Ц и Д на основу тога који има лошије перформансе ван узорка унутар d. Опет, пошто су Ц и Д фиксни, ова употреба анти-унакрсне валидације је сама по себи алгоритам. Назовимо тај алгоритам Б.

НФЛ нам говори (уопштено говорећи) да Б мора да победи А на исто толико циљних функција (и повезаних скупова података d) колико А победи Б. У овом веома специфичном смислу, научни метод ће изгубити од „анти-научног” метода једнако лако као што ће и победити.

НФЛ се примењује само ако је циљна функција изабрана из униформне расподеле свих могућих функција. Ако то није случај, а одређене циљне функције имају већу вероватноћу да буду изабране од других, онда А може радити боље од Б у целини. Допринос НФЛ-а је у томе што нам говори да одабир одговарајућег алгоритма захтева доношење претпоставки о врстама циљних функција за које се алгоритам користи. Без претпоставки, ниједан „мета-алгоритам”, као што је научни метод, не ради боље од случајног избора.

Док неки научници тврде да НФЛ преноси важан увид, други тврде да је НФЛ од малог значаја за истраживање машинског учења. Ако је Окамова бритва тачна, на пример ако су секвенце ниже Колмогоровљеве сложености вероватније од секвенци веће сложености, онда (као што се примећује у стварном животу) неки алгоритми, као што је унакрсна валидација, у просеку имају боље перформансе на практичним проблемима (у поређењу са случајним избором или са анти-унакрсном валидацијом).

Међутим, постоје велики формални изазови у коришћењу аргумената заснованих на Колмогоровљевој сложености за успостављање својстава стварног света, пошто је она неизрачунљива и недефинисана до произвољне адитивне константе. Делом у знак признања ових изазова, недавно се тврдило да постоје начини да се заобиђу теореме „нема бесплатног ручка” без позивања на Тјурингове машине, коришћењем „мета-индукције”. Штавише, Колмогоровљева сложеност модела машинског учења може бити горње ограничена компресијама њиховог означавања података, и могуће је произвести нетривијалне границе генерализације међу доменима путем Колмогоровљеве сложености.

Види још Нема бесплатног ручка у претрази и оптимизацији

Референце

Спољашње везе Теореме нема бесплатног ручка Графика која илуструје теорему

Категорија:Научни фолклор Категорија:Филозофија математике Категорија:Математичке теореме