Тегін түскілік жоқ: Оптимизация алгоритмдерінің шектеулері
No free lunch theorem
Жоқ нәрседен тамақ іздеу мүмкін емес: Математикадағы «тегін тамақ жоқ» теоремасы – алгоритмдердің тиімділігі мәселелерге байланысты екенін көрсетеді. Оптимизация, машиналық оқыту.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Егер алгоритм кейбір мәселелерде жақсы жұмыс істесе, онда ол басқа мәселелерде осыған төлейді.
Математикалық фольклор
If an algorithm does well on some problems, then it pays for that on other problems
mathematical folklore
Математикалық фольклорда Дэвид Уолперт пен Уильям Макредидің «тегін түскі ас жоқ» (NFL) теоремасы (кейде көпше түрінде) «тегін түскі ас деген нәрсе жоқ» деген мақалға сілтеме жасайды, яғни табысқа жетудің оңай жолдары жоқ. Бұл 1997 жылы «Оптимизация үшін тегін түскі ас теоремалары жоқ» деген мақалада пайда болды. Уолперт бұрыннан-ақ машиналық оқыту (статистикалық қорытынды) үшін тегін түскі ас теоремаларын шығарған болатын. 2005 жылы Уолперт пен Макреди өздерінің мақаласындағы алғашқы теоремасы «кез келген екі оптимизация алгоритмі барлық мүмкін мәселелер бойынша орташа есептелгенде тең болады» дейтінін атап көрсетті. «Тегін түскі ас жоқ» (NFL) теоремасы – Уолперт пен Макреди нақты дәлелдейтін теоремалардың оңай түсіндірілетін және оңай айтылатын салдары. Бұл дәлелденген теоремаларға қарағанда әлсіз, сондықтан оларды толығымен қамтымайды. Әртүрлі зерттеушілер Уолперт пен Макредидің жұмысын маңызды түрде кеңейтті. NFL теоремасы зерттеу саласының контекстінде қалай қолданылатынына қатысты айтатын болсақ, іздеу және оптимизациядағы тегін түскі ас жоқ – бұл статистикалық сәйкестікті, әсіресе іздеу және оптимизация үшін деректерді математикалық талдау мақсатындағы сала. Кейбір ғалымдар NFL маңызды түсінік береді деп санайды, ал басқалары NFL машиналық оқыту зерттеулеріне аса қатысы жоқ деп есептейді.
In mathematical folklore, the "no free lunch" (NFL) theorem (sometimes pluralized) of David Wolpert and William Macready, alludes to the saying "no such thing as a free lunch", that is, there are no easy shortcuts to success. It appeared in the 1997 "No Free Lunch Theorems for Optimization". Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state[s] that any two optimization algorithms are equivalent when their performance is averaged across all possible problems". The "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them. Various investigators have extended the work of Wolpert and Macready substantively. In terms of how the NFL theorem is used in the context of the research area, the no free lunch in search and optimization is a field that is dedicated for purposes of mathematically analyzing data for statistical identity, particularly search and optimization. While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.
Шығу тегі
Вулперт пен Макреди фольклорлық теоремамен тығыз байланысты екі НФЛ теоремасын келтіреді. Олар өз мақаласында былай деп жазады:
Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state:
blockquote|Біз осы нәтижелерді НФЛ теоремалары деп атадық, себебі олар алгоритмнің белгілі бір проблемалар класында жақсы өнім көрсетсе, қалған барлық проблемалар жиынтығында өнімнің нашарлауымен сөзсіз төлейтінін көрсетеді.
blockquote|We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.