खोज और अनुकूलन में कोई निःशुल्क लंच नहीं: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 22: Line 22:
वोल्पर्ट और मैकरेडी पूर्व से ही निर्धारित करते हैं कि एल्गोरिदम कभी भी प्रत्याशी समाधान का पुनर्मूल्यांकन नहीं करता है, और एल्गोरिदम का प्रदर्शन आउटपुट पर मापा जाता है।<ref name="WM97" />  सरलता के लिए, हम एल्गोरिदम में यादृच्छिकता की अनुमति नहीं देते हैं। इन नियमों के अनुसार, जब शोध एल्गोरिदम प्रत्येक संभावित इनपुट पर चलाया जाता है, तो यह प्रत्येक संभावित आउटपुट को उत्पन्न करता है।<ref name="English2004" />क्योंकि प्रदर्शन को आउटपुट पर मापा जाता है, एल्गोरिदम इस बात में अप्रभेद्य हैं कि वे कितनी बार प्रदर्शन के विशेष स्तर को प्राप्त करते हैं।
वोल्पर्ट और मैकरेडी पूर्व से ही निर्धारित करते हैं कि एल्गोरिदम कभी भी प्रत्याशी समाधान का पुनर्मूल्यांकन नहीं करता है, और एल्गोरिदम का प्रदर्शन आउटपुट पर मापा जाता है।<ref name="WM97" />  सरलता के लिए, हम एल्गोरिदम में यादृच्छिकता की अनुमति नहीं देते हैं। इन नियमों के अनुसार, जब शोध एल्गोरिदम प्रत्येक संभावित इनपुट पर चलाया जाता है, तो यह प्रत्येक संभावित आउटपुट को उत्पन्न करता है।<ref name="English2004" />क्योंकि प्रदर्शन को आउटपुट पर मापा जाता है, एल्गोरिदम इस बात में अप्रभेद्य हैं कि वे कितनी बार प्रदर्शन के विशेष स्तर को प्राप्त करते हैं।


प्रदर्शन के कुछ उपाय दर्शाते हैं कि उद्देश्य फलन के अनुकूलन (गणित) में शोध एल्गोरिदम कितना उत्तम प्रदर्शन करते हैं। वास्तव में, विचाराधीन वर्ग में अनुकूलन समस्याओं के अतिरिक्त शोध एल्गोरिदम का कोई लोकप्रिय अनुप्रयोग नहीं दिखता है। सामान्य प्रदर्शन माप आउटपुट अनुक्रम में सबसे कम मूल्य का सबसे छोटा सूचकांक है। यह वस्तुनिष्ठ कार्य को न्यूनतम करने के लिए आवश्यक मूल्यांकनों की संख्या है। कुछ एल्गोरिदम के लिए, न्यूनतम परिक्षण करने के लिए आवश्यक समय मूल्यांकन की संख्या के समानुपाती होता है।<ref name="English2004" />
प्रदर्शन के कुछ उपाय दर्शाते हैं कि उद्देश्य फलन के अनुकूलन (गणित) में शोध एल्गोरिदम कितना उत्तम प्रदर्शन करते हैं। वास्तव में, विचाराधीन वर्ग में अनुकूलन समस्याओं के अतिरिक्त शोध एल्गोरिदम का कोई लोकप्रिय अनुप्रयोग नहीं दिखता है। सामान्य प्रदर्शन माप आउटपुट अनुक्रम में सबसे कम मूल्य का सबसे छोटा सूचकांक है। यह वस्तुनिष्ठ फलन को न्यूनतम करने के लिए आवश्यक मूल्यांकनों की संख्या है। कुछ एल्गोरिदम के लिए, न्यूनतम परिक्षण करने के लिए आवश्यक समय मूल्यांकन की संख्या के समानुपाती होता है।<ref name="English2004" />


मूल नो फ्री लंच (एनएफएल) प्रमेय मानता है कि सभी वस्तुनिष्ठ कार्यों के शोध एल्गोरिदम में इनपुट होने की समान संभावना है।<ref name="WM97" />तब से यह स्थापित हो गया है कि एनएफएल तभी है जब, शिथिल रूप से कहें तो, वस्तुनिष्ठ कार्यों में परिवर्तन का संभावनाओं पर कोई प्रभाव नहीं पड़ता है।<ref name="Igel" /><ref name="English2004" />यद्यपि एनएफएल के लिए यह स्थिति भौतिक रूप से संभव है, यह तर्क दिया गया है कि यह निश्चित रूप से त्रुटिहीन रूप से प्रारम्भ नहीं होती है।<ref name="Igel" />
मूल नो फ्री लंच (एनएफएल) प्रमेय मानता है कि सभी वस्तुनिष्ठ फलनों के शोध एल्गोरिदम में इनपुट होने की समान संभावना है।<ref name="WM97" />तब से यह स्थापित हो गया है कि एनएफएल तभी है जब, शिथिल रूप से कहें तो, वस्तुनिष्ठ फलनों में परिवर्तन का संभावनाओं पर कोई प्रभाव नहीं पड़ता है।<ref name="Igel" /><ref name="English2004" />यद्यपि एनएफएल के लिए यह स्थिति भौतिक रूप से संभव है, यह तर्क दिया गया है कि यह निश्चित रूप से त्रुटिहीनता से प्रारम्भ नहीं होती है।<ref name="Igel" />


एनएफएल की स्पष्ट व्याख्या फ्री दोपहर का भोजन है, किंतु यह भ्रामक है। एनएफएल डिग्री की स्तिथि है, सब कुछ या कुछ नहीं का प्रस्ताव नहीं है। यदि एनएफएल के लिए नियम लगभग प्रारम्भ होती है, तो सभी एल्गोरिदम सभी उद्देश्य कार्यों पर लगभग समान परिणाम देते हैं।<ref name="English2004" />एनएफएल का तात्पर्य केवल यह नहीं है कि प्रदर्शन के कुछ मापों के आधार पर एल्गोरिदम समग्र रूप से असमान हैं। रुचि के प्रदर्शन माप के लिए, एल्गोरिदम समतुल्य, या लगभग इतना ही रह सकता है।<ref name="English2004" />
एनएफएल की स्पष्ट व्याख्या फ्री दोपहर का भोजन है, किंतु यह भ्रामक है। एनएफएल डिग्री की स्तिथि है, सब कुछ या कुछ नहीं का प्रस्ताव नहीं है। यदि एनएफएल के लिए नियम लगभग प्रारम्भ होता है, तो सभी एल्गोरिदम सभी उद्देश्य फलनों पर लगभग समान परिणाम देते हैं।<ref name="English2004" />एनएफएल का तात्पर्य केवल यह नहीं है कि प्रदर्शन के कुछ मापों के आधार पर एल्गोरिदम समग्र रूप से असमान हैं। रुचि के प्रदर्शन माप के लिए, एल्गोरिदम समतुल्य, या लगभग इतना ही रह सकता है।<ref name="English2004" />


'''कोलमोगोरोव यादृच्छिकता'''
'''कोलमोगोरोव यादृच्छिकता'''


सभी संभावित फलन के समुच्चय के लगभग सभी तत्व (फलन के समुच्चय-सैद्धांतिक अर्थ में) कोलमोगोरोव यादृच्छिकता हैं, और इसलिए एनएफएल प्रमेय फलन के समुच्चय पर प्रारम्भ होते हैं जिनमें से लगभग सभी को लुकअप तालिका की तुलना में अधिक कॉम्पैक्ट रूप से व्यक्त नहीं किया जा सकता है शोध स्थान में प्रत्येक बिंदु के लिए भिन्न (और यादृच्छिक) प्रविष्टि सम्मिलित है। वे फलन जिन्हें अधिक संक्षिप्त रूप से व्यक्त किया जा सकता है (उदाहरण के लिए, उचित आकार की गणितीय अभिव्यक्ति द्वारा) परिभाषा के अनुसार कोलमोगोरोव यादृच्छिक नहीं हैं।
सभी संभावित फलन के समुच्चय लगभग सभी तत्व (फलन के समुच्चय-सैद्धांतिक अर्थ में) कोलमोगोरोव यादृच्छिकता हैं, और इसलिए एनएफएल प्रमेय फलन के समुच्चय पर प्रारम्भ होते हैं जिनमें से लगभग सभी को लुकअप तालिका की तुलना में अधिक कॉम्पैक्ट रूप से व्यक्त नहीं किया जा सकता है शोध स्थान में प्रत्येक बिंदु के लिए भिन्न (और यादृच्छिक) प्रविष्टि सम्मिलित है। वे फलन जिन्हें अधिक संक्षिप्त रूप से व्यक्त किया जा सकता है (उदाहरण के लिए, उचित आकार की गणितीय अभिव्यक्ति द्वारा) परिभाषा के अनुसार कोलमोगोरोव यादृच्छिक नहीं हैं।


इसके अतिरिक्त, सभी संभावित वस्तुनिष्ठ कार्यों के समुच्चय के भीतर, प्रत्याशी समाधानों के मध्य उत्तम के स्तर को समान रूप से दर्शाया जाता है, इसलिए उत्तम समाधान प्रत्याशी के पूर्ण स्थान पर विस्तारित हैं। तदनुसार, शोध एल्गोरिदम अधिक उत्तम समाधान परिक्षण करने से पूर्व संभवतः ही कभी प्रत्याशी के छोटे भाग से अधिक का मूल्यांकन करेगा।<ref name=English2000/>
इसके अतिरिक्त, सभी संभावित वस्तुनिष्ठ फलनों के समुच्चय के भीतर, प्रत्याशी समाधानों के मध्य उत्तम के स्तर को समान रूप से दर्शाया जाता है, इसलिए उत्तम समाधान प्रत्याशी के पूर्ण स्थान पर विस्तारित हैं। तदनुसार, शोध एल्गोरिदम अधिक उत्तम समाधान परिक्षण करने से पूर्व संभवतः ही कभी प्रत्याशी के छोटे भाग से अधिक का मूल्यांकन करेगा।<ref name=English2000/>


लगभग सभी वस्तुनिष्ठ कार्य इतनी उच्च [[कोलमोगोरोव जटिलता|कोलमोगोरोव समिष्टता]] के हैं कि उन्हें किसी विशेष कंप्यूटर में संग्रहीत नहीं किया जा सकता है।<ref name=Streeter/><ref name=English2004/><ref name=English2000/>अधिक त्रुटिहीन रूप से, यदि हम किसी दिए गए भौतिक कंप्यूटर को आधुनिक कंप्यूटर की मेमोरी के क्रम में दिए गए आकार की मेमोरी के साथ रजिस्टर मशीन के रूप में मॉडल करते हैं, तो अधिकांश उद्देश्य कार्यों को उनकी मेमोरी में संग्रहीत नहीं किया जा सकता है। विशिष्ट वस्तुनिष्ठ फलन या एल्गोरिदम में [[सेठ लॉयड]] के अनुमान से अधिक जानकारी है कि अवलोकन योग्य ब्रह्मांड पंजीकरण करने में सक्षम है।<ref name=Lloyd2002>{{cite journal |last=Lloyd |first=S. |year=2002 |title=ब्रह्मांड की कम्प्यूटेशनल क्षमता|journal=Physical Review Letters |volume=88 |issue=23 |pages=237901–237904 |doi=10.1103/PhysRevLett.88.237901 |pmid=12059399 |arxiv=quant-ph/0110141 |bibcode=2002PhRvL..88w7901L |s2cid=6341263 }}</ref> उदाहरण के लिए, यदि प्रत्येक प्रत्याशी समाधान को 300 0 और 1 के अनुक्रम के रूप में एन्कोड किया गया है, और उत्तम मान 0 और 1 हैं, तो अधिकांश उद्देश्य कार्यों में कोलमोगोरोव समिष्टता कम से कम 2<sup>300</sup>बिट्स है,<ref name=LV>{{cite book |last1=Li |first1=M. |last2=Vitányi |first2=P. |year=1997 |title=कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का एक परिचय|edition=2nd |location=New York |publisher=Springer |isbn=0-387-94868-6 }}</ref> और यह लॉयड की 10<sup>90</sup> ≈ 2<sup>299</sup> बिट्स की सीमा से अधिक है इसका तात्पर्य यह है कि मूल नो फ्री लंच प्रमेय उस चीज़ पर प्रारम्भ नहीं होता है जिसे भौतिक कंप्यूटर में संग्रहीत किया जा सकता है; इसके अतिरिक्त तथाकथित समिष्ट नो फ्री लंच प्रमेय को प्रारम्भ करने की आवश्यकता है। यह भी दिखाया गया है कि एनएफएल परिणाम अतुलनीय कार्यों पर प्रारम्भ होते हैं।<ref>{{cite book |last=Woodward |first=John R. |chapter-url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.7782&rep=rep1&type=pdf |chapter=Computable and incomputable functions and search algorithms |title=IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009 |volume=1 |pages=871–875 |year=2009 |publisher=IEEE |citeseerx=10.1.1.158.7782 }}</ref>
लगभग सभी वस्तुनिष्ठ फलन इतनी उच्च [[कोलमोगोरोव जटिलता|कोलमोगोरोव समिष्टता]] के हैं कि उन्हें किसी विशेष कंप्यूटर में संग्रहीत नहीं किया जा सकता है।<ref name=Streeter/><ref name=English2004/><ref name=English2000/>अधिक त्रुटिहीन रूप से, यदि हम किसी दिए गए भौतिक कंप्यूटर को आधुनिक कंप्यूटर की मेमोरी के क्रम में दिए गए आकार की मेमोरी के साथ रजिस्टर मशीन के रूप में मॉडल करते हैं, तो अधिकांश उद्देश्य फलनों को उनकी मेमोरी में संग्रहीत नहीं किया जा सकता है। विशिष्ट वस्तुनिष्ठ फलन या एल्गोरिदम में [[सेठ लॉयड]] के अनुमान से अधिक जानकारी है कि अवलोकन योग्य ब्रह्मांड पंजीकरण करने में सक्षम है।<ref name=Lloyd2002>{{cite journal |last=Lloyd |first=S. |year=2002 |title=ब्रह्मांड की कम्प्यूटेशनल क्षमता|journal=Physical Review Letters |volume=88 |issue=23 |pages=237901–237904 |doi=10.1103/PhysRevLett.88.237901 |pmid=12059399 |arxiv=quant-ph/0110141 |bibcode=2002PhRvL..88w7901L |s2cid=6341263 }}</ref> उदाहरण के लिए, यदि प्रत्येक प्रत्याशी समाधान को 300 0 और 1 के अनुक्रम के रूप में एन्कोड किया गया है, और उत्तम मान 0 और 1 हैं, तो अधिकांश उद्देश्य फलनों में कोलमोगोरोव समिष्टता कम से कम 2<sup>300</sup> बिट्स है,<ref name=LV>{{cite book |last1=Li |first1=M. |last2=Vitányi |first2=P. |year=1997 |title=कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का एक परिचय|edition=2nd |location=New York |publisher=Springer |isbn=0-387-94868-6 }}</ref> और यह लॉयड की 10<sup>90</sup> ≈ 2<sup>299</sup> बिट्स की सीमा से अधिक है इसका तात्पर्य यह है कि मूल नो फ्री लंच प्रमेय उस चीज़ पर प्रारम्भ नहीं होता है जिसे भौतिक कंप्यूटर में संग्रहीत किया जा सकता है; इसके अतिरिक्त तथाकथित समिष्ट नो फ्री लंच प्रमेय को प्रारम्भ करने की आवश्यकता है। यह भी दिखाया गया है कि एनएफएल परिणाम अतुलनीय कार्यों पर प्रारम्भ होते हैं।<ref>{{cite book |last=Woodward |first=John R. |chapter-url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.7782&rep=rep1&type=pdf |chapter=Computable and incomputable functions and search algorithms |title=IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009 |volume=1 |pages=871–875 |year=2009 |publisher=IEEE |citeseerx=10.1.1.158.7782 }}</ref>


== औपचारिक सारांश ==
== औपचारिक सारांश ==
<math>Y^X</math> सभी वस्तुनिष्ठ फलनों का समुच्चय f:X→Y है, जहाँ <math>X</math> परिमित [[समाधान स्थान|समाधान समिष्ट]] है और <math>Y</math> परिमित स्थिति है, X के सभी क्रम परिवर्तनों का समुच्चय J है। यादृच्छिक चर F वितरित किया गया है <math>Y^X</math>, J में सभी J के लिए, ''F'' o ''j'' यादृच्छिक चर वितरित किया गया है <math>Y^X</math>, सभी f के लिए P(F o j = f) = P(F = f o j<sup>−1</sup>) सभी <math>Y^X</math> है।
<math>Y^X</math> सभी वस्तुनिष्ठ फलनों का समुच्चय f:X→Y है, जहाँ <math>X</math> परिमित [[समाधान स्थान|समाधान समिष्ट]] है और <math>Y</math> परिमित स्थिति है, X के सभी क्रम परिवर्तनों का समुच्चय J है। यादृच्छिक चर F वितरित किया गया है <math>Y^X</math>, J में सभी J के लिए, ''F'' o ''j'' यादृच्छिक चर वितरित किया गया है <math>Y^X</math>, सभी f के लिए P(F o j = f) = P(F = f o j<sup>−1</sup>) औए <math>Y^X</math> है।


मान लीजिए a(f) इनपुट f पर शोध एल्गोरिदम a के आउटपुट को दर्शाता है। यदि a(F) और b(F) को सभी शोध एल्गोरिदम a और b के लिए समान रूप से वितरित किया जाता है, तो F के पास एनएफएल वितरण है। यह नियम तभी प्रारम्भ होता है जब F और ''F'' o ''j'' को J में सभी J के लिए समान रूप से वितरित किया जाता है।<ref name=Igel/><ref name=English2004/>दूसरे शब्दों में, शोध एल्गोरिदम के लिए कोई फ्री लंच नहीं है यदि केवल समाधान स्थान के क्रम परिवर्तन के अनुसार उद्देश्य फलनो का वितरण अपरिवर्तनीय है।<ref>The "only if" part was first published by {{cite thesis |first=C. W. |last=Schumacher |type=PhD dissertation |title=Black Box Search : Framework and Methods |publisher=The University of Tennessee, Knoxville |year=2000 |id={{ProQuest|304620040}} }}</ref> समुच्चय-सैद्धांतिक एनएफएल प्रमेयों को वर्तमान में कार्डिनैलिटी के लिए <math>X</math> और <math>Y</math> में सामान्यीकृत किया गया है।<ref name=Rowe>{{cite journal |last1=Rowe |last2=Vose |last3=Wright |url=https://scholarworks.umt.edu/cgi/viewcontent.cgi?article=1008&context=cs_pubs |title=निःशुल्क दोपहर का भोजन नहीं की पुनर्व्याख्या|journal=Evolutionary Computation |year=2009 |volume=17 |issue=1 |pages=117–129 |doi=10.1162/evco.2009.17.1.117 |pmid=19207090 |s2cid=6251842 }}</ref>
मान लीजिए a(f) इनपुट f पर शोध एल्गोरिदम a के आउटपुट को दर्शाता है। यदि a(F) और b(F) को सभी शोध एल्गोरिदम a और b के लिए समान रूप से वितरित किया जाता है, तो F के पास एनएफएल वितरण है। यह नियम तभी प्रारम्भ होता है जब F और ''F'' o ''j'' को J में सभी J के लिए समान रूप से वितरित किया जाता है।<ref name=Igel/><ref name=English2004/>दूसरे शब्दों में, शोध एल्गोरिदम के लिए कोई फ्री लंच नहीं है यदि केवल समाधान स्थान के क्रम परिवर्तन के अनुसार उद्देश्य फलनो का वितरण अपरिवर्तनीय है।<ref>The "only if" part was first published by {{cite thesis |first=C. W. |last=Schumacher |type=PhD dissertation |title=Black Box Search : Framework and Methods |publisher=The University of Tennessee, Knoxville |year=2000 |id={{ProQuest|304620040}} }}</ref> समुच्चय-सैद्धांतिक एनएफएल प्रमेयों को वर्तमान में कार्डिनैलिटी के लिए <math>X</math> और <math>Y</math> में सामान्यीकृत किया गया है।<ref name=Rowe>{{cite journal |last1=Rowe |last2=Vose |last3=Wright |url=https://scholarworks.umt.edu/cgi/viewcontent.cgi?article=1008&context=cs_pubs |title=निःशुल्क दोपहर का भोजन नहीं की पुनर्व्याख्या|journal=Evolutionary Computation |year=2009 |volume=17 |issue=1 |pages=117–129 |doi=10.1162/evco.2009.17.1.117 |pmid=19207090 |s2cid=6251842 }}</ref>
Line 43: Line 43:
== उत्पत्ति ==
== उत्पत्ति ==
वोल्पर्ट और मैकरेडी दो प्रमुख एनएफएल प्रमेय देते हैं, प्रथम वस्तुनिष्ठ फलनो के बारे में जो शोध प्रारंभ रहने के समय नहीं परिवर्तित होते हैं, और दूसरा वस्तुनिष्ठ फलनो के बारे में जो परिवर्तित हो सकते हैं।<ref name=WM97/>  
वोल्पर्ट और मैकरेडी दो प्रमुख एनएफएल प्रमेय देते हैं, प्रथम वस्तुनिष्ठ फलनो के बारे में जो शोध प्रारंभ रहने के समय नहीं परिवर्तित होते हैं, और दूसरा वस्तुनिष्ठ फलनो के बारे में जो परिवर्तित हो सकते हैं।<ref name=WM97/>  
:प्रमेय 1: एल्गोरिदम की किसी भी जोड़ी के a<sub>1</sub> और a<sub>2</sub>
:प्रमेय 1: एल्गोरिदम की जोड़ी के लिए a<sub>1</sub> और a<sub>2</sub>
::<math>\sum_f P(d_m^y | f, m, a_1) = \sum_f P(d_m^y | f, m, a_2),</math> जहाँ <math>d_m^y</math> आकार के क्रमबद्ध समुच्चय को दर्शाता है <math>m</math> व्यय मानों का <math>y \in Y</math> इनपुट मानों से संबद्ध <math>x \in X</math>, <math>f:X \rightarrow Y </math> क्या फलन को अनुकूलित किया जा रहा है और <math>P(d_m^y | f, m, a)</math> एल्गोरिथम से व्यय मानों के दिए गए अनुक्रम को प्राप्त करने की सशर्त संभावना है <math>a</math> और <math>m</math> फलन में कई बार <math>f</math> उपस्थित है।
::<math>\sum_f P(d_m^y | f, m, a_1) = \sum_f P(d_m^y | f, m, a_2),</math> जहाँ <math>d_m^y</math> आकार के क्रमबद्ध समुच्चय को दर्शाता है <math>m</math> व्यय मानों का <math>y \in Y</math> इनपुट मानों से संबद्ध <math>x \in X</math>, <math>f:X \rightarrow Y </math> क्या फलन को अनुकूलित किया जा रहा है और <math>P(d_m^y | f, m, a)</math> एल्गोरिथम से व्यय मानों के दिए गए अनुक्रम को प्राप्त करने की सशर्त संभावना है <math>a</math> और <math>m</math> फलन में कई बार <math>f</math> उपस्थित है।


Line 53: Line 53:
एनएफएल परिणामों की पारंपरिक, किंतु पूर्ण रूप से त्रुटिहीन नहीं, व्याख्या यह है कि सामान्य-उद्देश्य वाली सार्वभौमिक अनुकूलन रणनीति सैद्धांतिक रूप से असंभव है, और रणनीति दूसरे से उत्तम प्रदर्शन तभी कर सकती है जब वह विचाराधीन विशिष्ट समस्या के लिए विशिष्ट हो।<ref>{{cite journal |last1=Ho |first1=Y. C. |last2=Pepyne |first2=D. L. |year=2002 |title=नो-फ्री-लंच प्रमेय और इसके निहितार्थ की सरल व्याख्या|journal=Journal of Optimization Theory and Applications |volume=115 |issue=3 |pages=549–570 |doi=10.1023/A:1021251113462 |s2cid=123041865 }}</ref> कई टिप्पणियाँ क्रम में हैं:
एनएफएल परिणामों की पारंपरिक, किंतु पूर्ण रूप से त्रुटिहीन नहीं, व्याख्या यह है कि सामान्य-उद्देश्य वाली सार्वभौमिक अनुकूलन रणनीति सैद्धांतिक रूप से असंभव है, और रणनीति दूसरे से उत्तम प्रदर्शन तभी कर सकती है जब वह विचाराधीन विशिष्ट समस्या के लिए विशिष्ट हो।<ref>{{cite journal |last1=Ho |first1=Y. C. |last2=Pepyne |first2=D. L. |year=2002 |title=नो-फ्री-लंच प्रमेय और इसके निहितार्थ की सरल व्याख्या|journal=Journal of Optimization Theory and Applications |volume=115 |issue=3 |pages=549–570 |doi=10.1023/A:1021251113462 |s2cid=123041865 }}</ref> कई टिप्पणियाँ क्रम में हैं:


*सैद्धांतिक रूप से सामान्य-उद्देश्य वाला लगभग-सार्वभौमिक अनुकूलक उपस्तिथ है। प्रत्येक शोध एल्गोरिदम लगभग सभी वस्तुनिष्ठ फलनो पर उत्तं प्रदर्शन करता है।<ref name=English2000/>इसलिए यदि कोई शोध एल्गोरिदम के मध्य अपेक्षाकृत छोटे अंतरों से चिंतित नहीं है, उदाहरण के लिए, क्योंकि कंप्यूटर का समय मूल्यहीन है, तो आपको फ्री दोपहर के भोजन के बारे में ध्यान नहीं देना चाहिए।
*सैद्धांतिक रूप से सामान्य-उद्देश्य वाला लगभग-सार्वभौमिक अनुकूलक उपस्तिथ है। प्रत्येक शोध एल्गोरिदम लगभग सभी वस्तुनिष्ठ फलनो पर उत्तम प्रदर्शन करता है।<ref name=English2000/>इसलिए यदि कोई शोध एल्गोरिदम के मध्य अपेक्षाकृत छोटे अंतरों से चिंतित नहीं है, उदाहरण के लिए, क्योंकि कंप्यूटर का समय मूल्यहीन है, तो आपको फ्री दोपहर के भोजन के बारे में ध्यान नहीं देना चाहिए।


*एल्गोरिथ्म किसी समस्या पर दूसरे से उत्तम प्रदर्शन कर सकता है जब दोनों में से कोई भी समस्या के लिए विशेषज्ञ न हो। वास्तव में, ऐसा हो सकता है कि दोनों एल्गोरिदम समस्या के लिए सबसे व्यर्थ हों। अधिक सामान्यतः, वोल्पर्ट और मैकरेडी ने एल्गोरिदम और समस्याओं पर वितरण (कठिनता से कहें तो, आंतरिक उत्पाद) के मध्य संरेखण की डिग्री का माप विकसित किया है।<ref name=WM97/>यह कहने का तात्पर्य यह नहीं है कि ल्गोरिदम किसी वितरण से दूसरे से उत्तम युग्मित होता है, इसका तात्पर्य यह नहीं है कि उनमें से किसी को निश्चयपूर्वक वितरण के लिए विशेषीकृत किया गया है; किसी एल्गोरिथम में केवल भाग्य से उत्तम संरेखण हो सकता है।
*एल्गोरिथ्म किसी समस्या पर दूसरे से उत्तम प्रदर्शन कर सकता है जब दोनों में से कोई भी समस्या के लिए विशेषज्ञ न हो। वास्तव में, ऐसा हो सकता है कि दोनों एल्गोरिदम समस्या के लिए सबसे व्यर्थ हों। अधिक सामान्यतः, वोल्पर्ट और मैकरेडी ने एल्गोरिदम और समस्याओं पर वितरण (कठिनता से कहें तो, आंतरिक उत्पाद) के मध्य संरेखण की डिग्री का माप विकसित किया है।<ref name=WM97/>यह कहने का तात्पर्य यह नहीं है कि एल्गोरिदम किसी वितरण से दूसरे से उत्तम युग्मित होता है, इसका तात्पर्य यह नहीं है कि उनमें से किसी को निश्चयपूर्वक वितरण के लिए विशेषीकृत किया गया है; किसी एल्गोरिथम में केवल भाग्य से उत्तम संरेखण हो सकता है।


*व्यवहार में, कुछ एल्गोरिदम प्रत्याशी समाधानों का पुनर्मूल्यांकन करते हैं। केवल पूर्व कभी मूल्यांकन न किए गए प्रत्याशी के प्रदर्शन पर विचार करने का कारण यह सुनिश्चित करना है कि एल्गोरिदम की तुलना करते समय एप्पल की तुलना एप्पल से की जा रही है। इसके अतिरिक्त, किसी एल्गोरिदम की श्रेष्ठता जो कभी भी किसी अन्य एल्गोरिदम पर प्रत्याशी का पुनर्मूल्यांकन नहीं करती है जो किसी विशेष समस्या पर करता है, उसका समस्या की विशेषज्ञता से कोई सम्बन्ध नहीं हो सकता है।
*व्यवहार में, कुछ एल्गोरिदम प्रत्याशी समाधानों का पुनर्मूल्यांकन करते हैं। केवल पूर्व कभी मूल्यांकन न किए गए प्रत्याशी के प्रदर्शन पर विचार करने का कारण यह सुनिश्चित करना है कि एल्गोरिदम की तुलना करते समय एप्पल की तुलना एप्पल से की जा रही है। इसके अतिरिक्त, किसी एल्गोरिदम की श्रेष्ठता जो कभी भी किसी अन्य एल्गोरिदम पर प्रत्याशी का पुनर्मूल्यांकन नहीं करती है जो किसी विशेष समस्या पर करता है, उसका समस्या की विशेषज्ञता से कोई सम्बन्ध नहीं हो सकता है।
Line 63: Line 63:
व्यवहार में, केवल अत्यधिक संपीड़ित (यादृच्छिक से दूर) उद्देश्य फलन कंप्यूटर के भंडारण में फिट होते हैं, और ऐसा नहीं है कि प्रत्येक एल्गोरिदम लगभग सभी संपीड़ित फलनो पर उत्तम प्रदर्शन करता है। एल्गोरिथम में समस्या के पूर्व ज्ञान को सम्मिलित करने में सामान्यतः प्रदर्शन लाभ होता है। जबकि एनएफएल परिणाम, कठिन अर्थ में, अनुकूलन व्यवसायी के लिए [[पूर्ण रोजगार प्रमेय]] का गठन करते हैं, बड़े संदर्भ को ध्यान में रखना महत्वपूर्ण है। विचार के लिए, मनुष्यों के पास प्रायः कार्य करने के लिए अधिक कम पूर्व ज्ञान होता है। दूसरे के लिए, पूर्व ज्ञान को सम्मिलित करने से कुछ समस्याओं पर अधिक प्रदर्शन लाभ नहीं मिलता है। अंततः, कंप्यूटर समय की तुलना में मानव का समय अधिक मूल्यवान है। ऐसे कई स्तिथि हैं जिनमें कोई कंपनी मानव-संशोधित प्रोग्राम के अतिरिक्त तीव्रता से अनमॉडिफाइड कंप्यूटर प्रोग्राम के साथ किसी फलन को धीरे-धीरे अनुकूलित करने में रूचि रखती है।
व्यवहार में, केवल अत्यधिक संपीड़ित (यादृच्छिक से दूर) उद्देश्य फलन कंप्यूटर के भंडारण में फिट होते हैं, और ऐसा नहीं है कि प्रत्येक एल्गोरिदम लगभग सभी संपीड़ित फलनो पर उत्तम प्रदर्शन करता है। एल्गोरिथम में समस्या के पूर्व ज्ञान को सम्मिलित करने में सामान्यतः प्रदर्शन लाभ होता है। जबकि एनएफएल परिणाम, कठिन अर्थ में, अनुकूलन व्यवसायी के लिए [[पूर्ण रोजगार प्रमेय]] का गठन करते हैं, बड़े संदर्भ को ध्यान में रखना महत्वपूर्ण है। विचार के लिए, मनुष्यों के पास प्रायः कार्य करने के लिए अधिक कम पूर्व ज्ञान होता है। दूसरे के लिए, पूर्व ज्ञान को सम्मिलित करने से कुछ समस्याओं पर अधिक प्रदर्शन लाभ नहीं मिलता है। अंततः, कंप्यूटर समय की तुलना में मानव का समय अधिक मूल्यवान है। ऐसे कई स्तिथि हैं जिनमें कोई कंपनी मानव-संशोधित प्रोग्राम के अतिरिक्त तीव्रता से अनमॉडिफाइड कंप्यूटर प्रोग्राम के साथ किसी फलन को धीरे-धीरे अनुकूलित करने में रूचि रखती है।


एनएफएल परिणाम यह संकेत नहीं देते हैं कि गैर-विशिष्ट एल्गोरिदम के साथ समस्याओं पर पॉट शॉट लेना व्यर्थ है। किसी ने भी उन व्यावहारिक समस्याओं का अंश निर्धारित नहीं किया है जिनके लिए एल्गोरिदम तीव्रता से उत्तम परिणाम देता है। और वहाँ व्यावहारिक फ्री दोपहर का भोजन है, सिद्धांत के साथ भी विरोधाभास नहीं है। कंप्यूटर पर एल्गोरिदम के कार्यान्वयन को चलाने में मानव समय का व्यय और उत्तम समाधान के लाभ के सापेक्ष अधिक कम व्यय आता है। यदि कोई एल्गोरिदम स्वीकार्य समय में संतोषजनक समाधान परिक्षण करने में सफल होता है, तो छोटे से निवेश से बड़ा लाभ मिलता है। यदि एल्गोरिथम विफल हो जाता है, तो अधिक कम हानि होती है।
एनएफएल परिणाम यह संकेत नहीं देते हैं कि गैर-विशिष्ट एल्गोरिदम के साथ समस्याओं पर पॉट शॉट लेना व्यर्थ है। किसी ने भी उन व्यावहारिक समस्याओं का भाग निर्धारित नहीं किया है जिनके लिए एल्गोरिदम तीव्रता से उत्तम परिणाम देता है। और वहाँ व्यावहारिक फ्री दोपहर का भोजन है, सिद्धांत के साथ भी विरोधाभास नहीं है। कंप्यूटर पर एल्गोरिदम के कार्यान्वयन को चलाने में मानव समय का व्यय और उत्तम समाधान के लाभ के सापेक्ष अधिक कम व्यय आता है। यदि कोई एल्गोरिदम स्वीकार्य समय में संतोषजनक समाधान परिक्षण करने में सफल होता है, तो छोटे से निवेश से बड़ा लाभ मिलता है। यदि एल्गोरिथम विफल हो जाता है, तो अधिक कम हानि होती है।


==[[सहविकास]]==
==[[सहविकास]]==
Line 71: Line 71:
== यह भी देखें ==
== यह भी देखें ==
* [[विकासवादी सूचना विज्ञान]]
* [[विकासवादी सूचना विज्ञान]]
* [[आगमनात्मक पूर्वाग्रह]]
* [[आगमनात्मक पूर्वाग्रह|इंडक्टिव बायस]]
*ओकार्य का उस्तरा
*ओकम रेजर  
*[[सादगी|सिम्प्लिसिटी]]
*[[सादगी|सिम्प्लिसिटी]]
* [[बदसूरत बत्तख का बच्चा प्रमेय|अग्ली डकलिंग प्रमेय]]
* [[बदसूरत बत्तख का बच्चा प्रमेय|अग्ली डकलिंग प्रमेय]]

Revision as of 16:01, 23 July 2023

This article is about कंप्यूटिंग का गणितीय विश्लेषण. For संबंधित लोककथाएँ और प्रमेय के व्यापक निहितार्थ, see कोई मुफ़्त लंच प्रमेय नहीं.
समस्या तीव्रता से प्रत्याशी ए, बी, और सी के मध्य समाधान परिक्षण करना है जो किसी भी अन्य के समान उत्तम हो, जहां उत्तम या तो 0 या 1 है। समस्या के आठ उदाहरण (लंच प्लेट) हैं, जहां x, y, और z क्रमशः a, b, और c की उत्तमता को दर्शाते हैं। प्रक्रिया (रेस्तरां) a प्रत्याशी का मूल्यांकन a, b, c क्रम में करता है और b उस क्रम के विपरीत प्रत्याशी का मूल्यांकन करता है, किंतु प्रत्येक 5 स्तिथि में 1 मूल्यांकन, 2 स्तिथि में 2 मूल्यांकन और 1 स्तिथि में 3 मूल्यांकन का शुल्क लेता है।

कम्प्यूटेशनल समिष्टता सिद्धांत और अनुकूलन (गणित) में नो फ्री लंच प्रमेय परिणाम है जो बताता है कि कुछ प्रकार की गणितीय समस्याओं के लिए, समाधान परिक्षण का कम्प्यूटेशनल व्यय, कक्षा में सभी समस्याओं पर औसत, किसी भी समाधान विधि के लिए समान है यह नाम इस कथन की ओर संकेत करता है कि फ्री लंच जैसी कोई चीज़ नहीं होती, अर्थात कोई भी विधि लघु विधि प्रदान नहीं करती। यह इस धारणा के अनुसार है कि शोध स्थान संभाव्यता घनत्व फलन है। यह उस स्तिथि पर प्रारम्भ नहीं होती है जहां शोध स्थान में अंतर्निहित संरचना होती है (उदाहरण के लिए, भिन्न फलन है) जिसे यादृच्छिक परिक्षण की तुलना में अधिक कुशलता से उपयोग किया जा सकता है (उदाहरण के लिए, अनुकूलन में न्यूटन की विधि) या यहां तक ​​कि विवृत-रूप समाधान भी हैं (उदाहरण के लिए, द्विघात बहुपद का शीर्ष) जिसे बिना किसी परिक्षण के निर्धारित किया जा सकता है। ऐसी संभाव्य धारणाओं के लिए, किसी विशेष प्रकार की समस्या को समाधान करने वाली सभी प्रक्रियाओं के आउटपुट सांख्यिकीय रूप से समान होते हैं। ऐसी परिस्थिति का वर्णन करने की रंगीन विधि, परिक्षण की समस्याओं के संबंध में डेविड वोल्पर्ट और विलियम जी. मैकरेडी द्वारा प्रस्तुत किया गया[1]यह कहना है कि कोई [2]फ्री दोपहर का भोजन नहीं है।[3] वोल्पर्ट ने पूर्व मशीन लर्निंग (सांख्यिकीय अनुमान) के लिए कोई निःशुल्क लंच प्रमेय नहीं निकाला था।[4]वोल्पर्ट का लेख प्रकाशित होने से पूर्व, कुलेन शेफ़र ने स्वतंत्र रूप से वोल्पर्ट के प्रमेयों में से प्रतिबंधित संस्करण सिद्ध किया और इसका उपयोग प्रेरण की समस्या पर मशीन लर्निंग अनुसंधान की वर्तमान स्थिति की आलोचना करने के लिए किया।

फ्री लंच नहीं के रूपक में, रेस्तरां (समस्या-समाधान प्रक्रिया) में प्रत्येक लंच प्लेट (समस्या) के मान (समस्या का समाधान करने में प्रक्रिया का प्रदर्शन) के साथ जोड़ने वाला मेनू होता है। रेस्तरां के मेनू स्तिथि को छोड़कर समान हैं- व्यय एक रेस्तरां से दूसरे रेस्तरां में परिवर्तित होती रहती हैं। सर्वाहारी के लिए जो किसी अन्य के जैसे प्रत्येक प्लेट का ऑर्डर देने की संभावना रखता है, दोपहर के भोजन की औसत व्यय रेस्तरां की रूचि पर निर्भर नहीं करती है। किंतु शाकाहारी जो अल्पव्ययता चाहने वाले मांसाहारी के साथ नियमित रूप से दोपहर के भोजन के लिए किया जाता है, उसे दोपहर के भोजन के लिए उच्च औसत व्यय का भुगतान करना पड़ सकता है। औसत व्यय को व्यवस्थित रूप से कम करने के लिए, किसी को पूर्व से ज्ञात होना चाहिए कि (ए) वह क्या ऑर्डर करेगा और (बी) विभिन्न रेस्तरां में ऑर्डर की व्यय क्या होगी। अर्थात्, समस्या-समाधान के प्रदर्शन में सुधार प्रक्रियाओं को समस्याओं से मिलाने के लिए पूर्व सूचना का उपयोग करने पर निर्भर करता है।[2][4]

औपचारिक शब्दों में, कोई फ्री लंच नहीं होता है जब समस्या के उदाहरणों पर संभाव्यता वितरण ऐसा होता है कि सभी समस्या समाधानकर्ताओं के परिणाम समान रूप से वितरित होते हैं। शोध एल्गोरिदम की स्तिथि में, इस संदर्भ में समस्या उदाहरण विशेष उद्देश्य फलन है, और परिणाम फलन के फलन डोमेन में प्रत्याशी समाधानों के मूल्यांकन में प्राप्त मानों का अनुक्रम है। परिणामों की विशिष्ट व्याख्याओं के लिए, शोध अनुकूलन (गणित) प्रक्रिया है। शोध में कोई निःशुल्क लंच नहीं है यदि केवल प्रत्याशी समाधानों के स्थान के क्रम परिवर्तन के अनुसार वस्तुनिष्ठ कार्यों पर वितरण अपरिवर्तनीय (गणित) है।[5][6][7] यह स्थिति व्यवहार में त्रुटिहीन रूप से प्रारम्भ नहीं होती,[6]किंतु (लगभग) कोई निःशुल्क लंच प्रमेय यह विचार नहीं प्रदान करता कि यह लगभग सही है।[8]

अवलोकन

कुछ कम्प्यूटेशनल समस्याओं को प्रत्याशी समाधानों के क्षेत्र में उत्तम समाधानों का शोध करके समाधान किया जाता है। मूल्यांकन के लिए प्रत्याशी समाधानों को बार-बार कैसे चयन किया जाए, इसका विवरण शोध एल्गोरिदम कहलाता है। किसी विशेष समस्या पर, भिन्न-भिन्न शोध एल्गोरिदम भिन्न-भिन्न परिणाम प्राप्त कर सकते हैं, किंतु सभी समस्याओं पर, वे अप्रभेद्य हैं। इसका तात्पर्य यह है कि यदि कोई एल्गोरिदम कुछ समस्याओं पर उत्तम परिणाम प्राप्त करता है, तो उसे अन्य समस्याओं पर हीनता के साथ भुगतान करना होगा। इस अर्थ में शोध में कोई निःशुल्क दोपहर का भोजन नहीं है।[1]वैकल्पिक रूप से, शेफ़र का अनुसरण करते हुए,[4]शोध प्रदर्शन संरक्षण नियम (भौतिकी) है। सामान्यतः शोध की व्याख्या अनुकूलन (गणित) के रूप में की जाती है, और इससे यह निष्कर्ष निकलता है कि अनुकूलन में कोई फ्री लंच नहीं है।[2]

वोलपर्ट और मैकरेडी का 'नो फ्री लंच' प्रमेय, जैसा कि वोलपर्ट और मैकरेडी ने स्पष्ट भाषा में यह कहा है, कि कोई भी दो एल्गोरिदम समतुल्य होते हैं जब उनका प्रदर्शन सभी संभावित समस्याओं के मध्य औसत होता है।[9] निःशुल्क दोपहर के भोजन के न होने के परिणाम दर्शाते हैं कि समस्याओं के लिए एल्गोरिदम का संघ सभी के लिए निश्चित एल्गोरिदम प्रारम्भ करने की तुलना में अधिक औसत प्रदर्शन देता है। इगेल, टूसेंट[6]और अंग्रेजी[7] सामान्य नियम स्थापित किया है जिसके अनुसार फ्री दोपहर का भोजन नहीं है। चूँकि यह शारीरिक रूप से संभव है, यह त्रुटिहीन रूप से प्रारम्भ नहीं होता है।[6]ड्रोस्टे, जेन्सन और वेगनर ने प्रमेय में सिद्ध किया है जिसकी व्याख्या वे इस प्रकार करते हैं कि व्यवहार में (लगभग) कोई फ्री दोपहर का भोजन नहीं है।[8]

स्तिथि को अधिक ठोस बनाने के लिए, किसी समस्या का सामना करने वाले अनुकूलन व्यवसायी पर विचार करें। समस्या कैसे उत्पन्न हुई, इसके बारे में कुछ ज्ञान होने पर, अभ्यासकर्ता एल्गोरिदम के चयन में उस ज्ञान का उपयोग करने में सक्षम हो सकता है जो समस्या का समाधान करने में उत्तम प्रदर्शन करेगा। यदि अभ्यासकर्ता यह नहीं समझता है कि ज्ञान का दोहन कैसे किया जाए, या उसके पास कोई ज्ञान नहीं है, तो उसे इस सवाल का सामना करना पड़ता है कि क्या कुछ एल्गोरिदम सामान्यतः वास्तविक संसार की समस्याओं पर दूसरों से उत्तम प्रदर्शन करते हैं। (लगभग) नो फ्री लंच प्रमेय के लेखकों का कहना है कि उत्तर अनिवार्य रूप से नहीं है, किंतु इस बारे में कुछ आपत्तियां स्वीकार करते हैं कि क्या प्रमेय अभ्यास को संबोधित करता है।[8]

प्रमेय

समस्या, अधिक औपचारिक रूप से, उद्देश्यपूर्ण फलन है जो प्रत्याशी समाधानों को उत्तम मानों के साथ जोड़ता है। शोध एल्गोरिदम वस्तुनिष्ठ फलन को इनपुट के रूप में लेता है और प्रत्याशी समाधानों का मूल्यांकन करता है। एल्गोरिथम का आउटपुट प्रेक्षित उत्तम मानों का अनुक्रम है।[10][11]

वोल्पर्ट और मैकरेडी पूर्व से ही निर्धारित करते हैं कि एल्गोरिदम कभी भी प्रत्याशी समाधान का पुनर्मूल्यांकन नहीं करता है, और एल्गोरिदम का प्रदर्शन आउटपुट पर मापा जाता है।[2] सरलता के लिए, हम एल्गोरिदम में यादृच्छिकता की अनुमति नहीं देते हैं। इन नियमों के अनुसार, जब शोध एल्गोरिदम प्रत्येक संभावित इनपुट पर चलाया जाता है, तो यह प्रत्येक संभावित आउटपुट को उत्पन्न करता है।[7]क्योंकि प्रदर्शन को आउटपुट पर मापा जाता है, एल्गोरिदम इस बात में अप्रभेद्य हैं कि वे कितनी बार प्रदर्शन के विशेष स्तर को प्राप्त करते हैं।

प्रदर्शन के कुछ उपाय दर्शाते हैं कि उद्देश्य फलन के अनुकूलन (गणित) में शोध एल्गोरिदम कितना उत्तम प्रदर्शन करते हैं। वास्तव में, विचाराधीन वर्ग में अनुकूलन समस्याओं के अतिरिक्त शोध एल्गोरिदम का कोई लोकप्रिय अनुप्रयोग नहीं दिखता है। सामान्य प्रदर्शन माप आउटपुट अनुक्रम में सबसे कम मूल्य का सबसे छोटा सूचकांक है। यह वस्तुनिष्ठ फलन को न्यूनतम करने के लिए आवश्यक मूल्यांकनों की संख्या है। कुछ एल्गोरिदम के लिए, न्यूनतम परिक्षण करने के लिए आवश्यक समय मूल्यांकन की संख्या के समानुपाती होता है।[7]

मूल नो फ्री लंच (एनएफएल) प्रमेय मानता है कि सभी वस्तुनिष्ठ फलनों के शोध एल्गोरिदम में इनपुट होने की समान संभावना है।[2]तब से यह स्थापित हो गया है कि एनएफएल तभी है जब, शिथिल रूप से कहें तो, वस्तुनिष्ठ फलनों में परिवर्तन का संभावनाओं पर कोई प्रभाव नहीं पड़ता है।[6][7]यद्यपि एनएफएल के लिए यह स्थिति भौतिक रूप से संभव है, यह तर्क दिया गया है कि यह निश्चित रूप से त्रुटिहीनता से प्रारम्भ नहीं होती है।[6]

एनएफएल की स्पष्ट व्याख्या फ्री दोपहर का भोजन है, किंतु यह भ्रामक है। एनएफएल डिग्री की स्तिथि है, सब कुछ या कुछ नहीं का प्रस्ताव नहीं है। यदि एनएफएल के लिए नियम लगभग प्रारम्भ होता है, तो सभी एल्गोरिदम सभी उद्देश्य फलनों पर लगभग समान परिणाम देते हैं।[7]एनएफएल का तात्पर्य केवल यह नहीं है कि प्रदर्शन के कुछ मापों के आधार पर एल्गोरिदम समग्र रूप से असमान हैं। रुचि के प्रदर्शन माप के लिए, एल्गोरिदम समतुल्य, या लगभग इतना ही रह सकता है।[7]

कोलमोगोरोव यादृच्छिकता

सभी संभावित फलन के समुच्चय लगभग सभी तत्व (फलन के समुच्चय-सैद्धांतिक अर्थ में) कोलमोगोरोव यादृच्छिकता हैं, और इसलिए एनएफएल प्रमेय फलन के समुच्चय पर प्रारम्भ होते हैं जिनमें से लगभग सभी को लुकअप तालिका की तुलना में अधिक कॉम्पैक्ट रूप से व्यक्त नहीं किया जा सकता है शोध स्थान में प्रत्येक बिंदु के लिए भिन्न (और यादृच्छिक) प्रविष्टि सम्मिलित है। वे फलन जिन्हें अधिक संक्षिप्त रूप से व्यक्त किया जा सकता है (उदाहरण के लिए, उचित आकार की गणितीय अभिव्यक्ति द्वारा) परिभाषा के अनुसार कोलमोगोरोव यादृच्छिक नहीं हैं।

इसके अतिरिक्त, सभी संभावित वस्तुनिष्ठ फलनों के समुच्चय के भीतर, प्रत्याशी समाधानों के मध्य उत्तम के स्तर को समान रूप से दर्शाया जाता है, इसलिए उत्तम समाधान प्रत्याशी के पूर्ण स्थान पर विस्तारित हैं। तदनुसार, शोध एल्गोरिदम अधिक उत्तम समाधान परिक्षण करने से पूर्व संभवतः ही कभी प्रत्याशी के छोटे भाग से अधिक का मूल्यांकन करेगा।[11]

लगभग सभी वस्तुनिष्ठ फलन इतनी उच्च कोलमोगोरोव समिष्टता के हैं कि उन्हें किसी विशेष कंप्यूटर में संग्रहीत नहीं किया जा सकता है।[5][7][11]अधिक त्रुटिहीन रूप से, यदि हम किसी दिए गए भौतिक कंप्यूटर को आधुनिक कंप्यूटर की मेमोरी के क्रम में दिए गए आकार की मेमोरी के साथ रजिस्टर मशीन के रूप में मॉडल करते हैं, तो अधिकांश उद्देश्य फलनों को उनकी मेमोरी में संग्रहीत नहीं किया जा सकता है। विशिष्ट वस्तुनिष्ठ फलन या एल्गोरिदम में सेठ लॉयड के अनुमान से अधिक जानकारी है कि अवलोकन योग्य ब्रह्मांड पंजीकरण करने में सक्षम है।[12] उदाहरण के लिए, यदि प्रत्येक प्रत्याशी समाधान को 300 0 और 1 के अनुक्रम के रूप में एन्कोड किया गया है, और उत्तम मान 0 और 1 हैं, तो अधिकांश उद्देश्य फलनों में कोलमोगोरोव समिष्टता कम से कम 2300 बिट्स है,[13] और यह लॉयड की 1090 ≈ 2299 बिट्स की सीमा से अधिक है इसका तात्पर्य यह है कि मूल नो फ्री लंच प्रमेय उस चीज़ पर प्रारम्भ नहीं होता है जिसे भौतिक कंप्यूटर में संग्रहीत किया जा सकता है; इसके अतिरिक्त तथाकथित समिष्ट नो फ्री लंच प्रमेय को प्रारम्भ करने की आवश्यकता है। यह भी दिखाया गया है कि एनएफएल परिणाम अतुलनीय कार्यों पर प्रारम्भ होते हैं।[14]

औपचारिक सारांश

सभी वस्तुनिष्ठ फलनों का समुच्चय f:X→Y है, जहाँ परिमित समाधान समिष्ट है और परिमित स्थिति है, X के सभी क्रम परिवर्तनों का समुच्चय J है। यादृच्छिक चर F वितरित किया गया है , J में सभी J के लिए, F o j यादृच्छिक चर वितरित किया गया है , सभी f के लिए P(F o j = f) = P(F = f o j−1) औए है।

मान लीजिए a(f) इनपुट f पर शोध एल्गोरिदम a के आउटपुट को दर्शाता है। यदि a(F) और b(F) को सभी शोध एल्गोरिदम a और b के लिए समान रूप से वितरित किया जाता है, तो F के पास एनएफएल वितरण है। यह नियम तभी प्रारम्भ होता है जब F और F o j को J में सभी J के लिए समान रूप से वितरित किया जाता है।[6][7]दूसरे शब्दों में, शोध एल्गोरिदम के लिए कोई फ्री लंच नहीं है यदि केवल समाधान स्थान के क्रम परिवर्तन के अनुसार उद्देश्य फलनो का वितरण अपरिवर्तनीय है।[15] समुच्चय-सैद्धांतिक एनएफएल प्रमेयों को वर्तमान में कार्डिनैलिटी के लिए और में सामान्यीकृत किया गया है।[16]

उत्पत्ति

वोल्पर्ट और मैकरेडी दो प्रमुख एनएफएल प्रमेय देते हैं, प्रथम वस्तुनिष्ठ फलनो के बारे में जो शोध प्रारंभ रहने के समय नहीं परिवर्तित होते हैं, और दूसरा वस्तुनिष्ठ फलनो के बारे में जो परिवर्तित हो सकते हैं।[2]

प्रमेय 1: एल्गोरिदम की जोड़ी के लिए a1 और a2
जहाँ आकार के क्रमबद्ध समुच्चय को दर्शाता है व्यय मानों का इनपुट मानों से संबद्ध , क्या फलन को अनुकूलित किया जा रहा है और एल्गोरिथम से व्यय मानों के दिए गए अनुक्रम को प्राप्त करने की सशर्त संभावना है और फलन में कई बार उपस्थित है।

संक्षेप में, यह कहता है कि जब सभी फलन f समान रूप से संभावित होते हैं, तो शोध के समय m मानों के अनुक्रम को देखने की संभावना शोध एल्गोरिदम पर निर्भर नहीं होती है।

दूसरा प्रमेय समय-भिन्न उद्देश्य फलनो के लिए अधिक सूक्ष्म एनएफएल परिणाम स्थापित करता है।[2]

परिणामों की व्याख्या

एनएफएल परिणामों की पारंपरिक, किंतु पूर्ण रूप से त्रुटिहीन नहीं, व्याख्या यह है कि सामान्य-उद्देश्य वाली सार्वभौमिक अनुकूलन रणनीति सैद्धांतिक रूप से असंभव है, और रणनीति दूसरे से उत्तम प्रदर्शन तभी कर सकती है जब वह विचाराधीन विशिष्ट समस्या के लिए विशिष्ट हो।[17] कई टिप्पणियाँ क्रम में हैं:

  • सैद्धांतिक रूप से सामान्य-उद्देश्य वाला लगभग-सार्वभौमिक अनुकूलक उपस्तिथ है। प्रत्येक शोध एल्गोरिदम लगभग सभी वस्तुनिष्ठ फलनो पर उत्तम प्रदर्शन करता है।[11]इसलिए यदि कोई शोध एल्गोरिदम के मध्य अपेक्षाकृत छोटे अंतरों से चिंतित नहीं है, उदाहरण के लिए, क्योंकि कंप्यूटर का समय मूल्यहीन है, तो आपको फ्री दोपहर के भोजन के बारे में ध्यान नहीं देना चाहिए।
  • एल्गोरिथ्म किसी समस्या पर दूसरे से उत्तम प्रदर्शन कर सकता है जब दोनों में से कोई भी समस्या के लिए विशेषज्ञ न हो। वास्तव में, ऐसा हो सकता है कि दोनों एल्गोरिदम समस्या के लिए सबसे व्यर्थ हों। अधिक सामान्यतः, वोल्पर्ट और मैकरेडी ने एल्गोरिदम और समस्याओं पर वितरण (कठिनता से कहें तो, आंतरिक उत्पाद) के मध्य संरेखण की डिग्री का माप विकसित किया है।[2]यह कहने का तात्पर्य यह नहीं है कि एल्गोरिदम किसी वितरण से दूसरे से उत्तम युग्मित होता है, इसका तात्पर्य यह नहीं है कि उनमें से किसी को निश्चयपूर्वक वितरण के लिए विशेषीकृत किया गया है; किसी एल्गोरिथम में केवल भाग्य से उत्तम संरेखण हो सकता है।
  • व्यवहार में, कुछ एल्गोरिदम प्रत्याशी समाधानों का पुनर्मूल्यांकन करते हैं। केवल पूर्व कभी मूल्यांकन न किए गए प्रत्याशी के प्रदर्शन पर विचार करने का कारण यह सुनिश्चित करना है कि एल्गोरिदम की तुलना करते समय एप्पल की तुलना एप्पल से की जा रही है। इसके अतिरिक्त, किसी एल्गोरिदम की श्रेष्ठता जो कभी भी किसी अन्य एल्गोरिदम पर प्रत्याशी का पुनर्मूल्यांकन नहीं करती है जो किसी विशेष समस्या पर करता है, उसका समस्या की विशेषज्ञता से कोई सम्बन्ध नहीं हो सकता है।
  • लगभग सभी वस्तुनिष्ठ फलनो के लिए, विशेषज्ञता अनिवार्य रूप से अकारण है। जहाँ तक कोलमोगोरोव यादृच्छिकता को परिभाषित करने के लिए उपयोग की जाने वाली सार्वभौमिक ट्यूरिंग मशीनिंग का संबंध है, असम्पीडित, या कोलमोगोरोव यादृच्छिकता, उद्देश्य फलनो में एल्गोरिथ्म के शोषण के लिए कोई नियमितता नहीं है। तो मान लीजिए कि सार्वभौमिक ट्यूरिंग मशीन का, स्पष्ट रूप से उत्तम विकल्प है। फिर ऑब्जेक्टिव फलन दिया गया है जो उस ट्यूरिंग मशीन के लिए असम्पीडित है, दो एल्गोरिदम के मध्य चयन करने का कोई आधार नहीं है यदि दोनों संपीड़ित हैं, जैसा कि उस ट्यूरिंग मशीन का उपयोग करके मापा जाता है। यदि कोई चयन किया गया एल्गोरिदम अधिकांश से उत्तम प्रदर्शन करता है, तो परिणाम घटित होता है।[11]कोलमोगोरोव यादृच्छिक फलन का लुकअप तालिका से छोटा कोई प्रतिनिधित्व नहीं होता है जिसमें शोध स्थान में प्रत्येक बिंदु के अनुरूप (यादृच्छिक) मान होता है; कोई भी फलन जिसे अधिक संक्षिप्त रूप से व्यक्त किया जा सकता है, परिभाषा के अनुसार, कोलमोगोरोव यादृच्छिक नहीं है।

व्यवहार में, केवल अत्यधिक संपीड़ित (यादृच्छिक से दूर) उद्देश्य फलन कंप्यूटर के भंडारण में फिट होते हैं, और ऐसा नहीं है कि प्रत्येक एल्गोरिदम लगभग सभी संपीड़ित फलनो पर उत्तम प्रदर्शन करता है। एल्गोरिथम में समस्या के पूर्व ज्ञान को सम्मिलित करने में सामान्यतः प्रदर्शन लाभ होता है। जबकि एनएफएल परिणाम, कठिन अर्थ में, अनुकूलन व्यवसायी के लिए पूर्ण रोजगार प्रमेय का गठन करते हैं, बड़े संदर्भ को ध्यान में रखना महत्वपूर्ण है। विचार के लिए, मनुष्यों के पास प्रायः कार्य करने के लिए अधिक कम पूर्व ज्ञान होता है। दूसरे के लिए, पूर्व ज्ञान को सम्मिलित करने से कुछ समस्याओं पर अधिक प्रदर्शन लाभ नहीं मिलता है। अंततः, कंप्यूटर समय की तुलना में मानव का समय अधिक मूल्यवान है। ऐसे कई स्तिथि हैं जिनमें कोई कंपनी मानव-संशोधित प्रोग्राम के अतिरिक्त तीव्रता से अनमॉडिफाइड कंप्यूटर प्रोग्राम के साथ किसी फलन को धीरे-धीरे अनुकूलित करने में रूचि रखती है।

एनएफएल परिणाम यह संकेत नहीं देते हैं कि गैर-विशिष्ट एल्गोरिदम के साथ समस्याओं पर पॉट शॉट लेना व्यर्थ है। किसी ने भी उन व्यावहारिक समस्याओं का भाग निर्धारित नहीं किया है जिनके लिए एल्गोरिदम तीव्रता से उत्तम परिणाम देता है। और वहाँ व्यावहारिक फ्री दोपहर का भोजन है, सिद्धांत के साथ भी विरोधाभास नहीं है। कंप्यूटर पर एल्गोरिदम के कार्यान्वयन को चलाने में मानव समय का व्यय और उत्तम समाधान के लाभ के सापेक्ष अधिक कम व्यय आता है। यदि कोई एल्गोरिदम स्वीकार्य समय में संतोषजनक समाधान परिक्षण करने में सफल होता है, तो छोटे से निवेश से बड़ा लाभ मिलता है। यदि एल्गोरिथम विफल हो जाता है, तो अधिक कम हानि होती है।

सहविकास

वोल्पर्ट और मैकरेडी ने सिद्ध कर दिया है कि सहविकासवादी अनुकूलन में फ्री लंच हैं।[9] उनके विश्लेषण में 'स्वयं-खेल' समस्याओं को सम्मिलित किया गया है। इन समस्याओं में, खिलाड़ियों का समूह चैंपियन तैयार करने के लिए मिलकर कार्य करता है, जो पश्चात के मल्टीप्लेयर गेम में या अधिक विरोधियों को सम्मिलित करता है।[9]अर्थात्, उद्देश्य उत्तम खिलाड़ी प्राप्त करना है, किंतु बिना किसी वस्तुनिष्ठ कार्य के प्रत्येक खिलाड़ी (प्रत्याशीसमाधान) का उत्तम आकलन यह देखकर किया जाता है कि वह दूसरों के विपरीत कितना अच्छा खेलता है। एल्गोरिदम उत्तम खिलाड़ी प्राप्त करने के लिए खिलाड़ियों और उनके खेल की गुणवत्ता का उपयोग करने का प्रयास करता है। एल्गोरिथम द्वारा सबसे उतम समझा जाने वाला खिलाड़ी चैंपियन होता है। वोल्पर्ट और मैकरेडी ने पूर्व में ही प्रदर्शित कर दिया है कि कुछ सह-विकासवादी एल्गोरिदम सामान्यतः प्राप्त चैंपियनों की गुणवत्ता में अन्य एल्गोरिदम से उत्तम होते हैं। स्व-खेल के माध्यम से चैंपियन उत्पन्न करना विकासवादी गणना और गेम सिद्धांत में रुचि रखता है। परिणाम जैविक प्रजातियों के सह-विकास पर प्रारम्भ नहीं होते हैं, जिससे चैंपियन नहीं मिलते हैं।[9]

यह भी देखें

टिप्पणियाँ

  1. ↑ 1.0 1.1 Wolpert, D. H.; Macready, W. G. (1995). "खोज के लिए कोई फ्री लंच थ्योरम नहीं" (PDF). Technical Report SFI-TR-95-02-010. Santa Fe Institute. S2CID 12890367.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Wolpert, D. H.; Macready, W. G. (1997). "अनुकूलन के लिए कोई निःशुल्क लंच प्रमेय नहीं". IEEE Transactions on Evolutionary Computation. 1: 67–82. doi:10.1109/4235.585893. S2CID 5553697.
  3. ↑ Wolpert, David (1996). "The Lack of A Priori Distinctions between Learning Algorithms" (PDF). तंत्रिका संगणना. Vol. 8. pp. 1341–1390. doi:10.1162/neco.1996.8.7.1341. S2CID 207609360.
  4. ↑ 4.0 4.1 4.2 Schaffer, Cullen (1994). "A conservation law for generalization performance" (PDF). In Willian, H.; Cohen, W. (eds.). मशीन लर्निंग पर अंतर्राष्ट्रीय सम्मेलन. San Francisco: Morgan Kaufmann. pp. 259–265.
  5. ↑ 5.0 5.1 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. ↑ 6.0 6.1 6.2 6.3 6.4 6.5 6.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. ↑ 7.0 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 English, T. (2004) No More Lunch: Analysis of Sequential Search, Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pp. 227–234.
  8. ↑ 8.0 8.1 8.2 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. ↑ 9.0 9.1 9.2 9.3 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. ↑ 11.0 11.1 11.2 11.3 11.4 English, T. M. (2000). "अनुकूलन आसान है और विशिष्ट कार्य में सीखना कठिन है". Proceedings of the 2000 Congress on Evolutionary Computation: CEC00. 2: 924–931. doi:10.1109/CEC.2000.870741. ISBN 0-7803-6375-2. S2CID 11295575.
  12. ↑ Lloyd, S. (2002). "ब्रह्मांड की कम्प्यूटेशनल क्षमता". Physical Review Letters. 88 (23): 237901–237904. arXiv:quant-ph/0110141. Bibcode:2002PhRvL..88w7901L. doi:10.1103/PhysRevLett.88.237901. PMID 12059399. S2CID 6341263.
  13. ↑ Li, M.; Vitányi, P. (1997). कोलमोगोरोव जटिलता और उसके अनुप्रयोगों का एक परिचय (2nd ed.). New York: Springer. ISBN 0-387-94868-6.
  14. ↑ Woodward, John R. (2009). "Computable and incomputable functions and search algorithms". IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009. Vol. 1. IEEE. pp. 871–875. CiteSeerX 10.1.1.158.7782.
  15. ↑ The "only if" part was first published by Schumacher, C. W. (2000). Black Box Search : Framework and Methods (PhD dissertation). The University of Tennessee, Knoxville. ProQuest 304620040.
  16. ↑ Rowe; Vose; Wright (2009). "निःशुल्क दोपहर का भोजन नहीं की पुनर्व्याख्या". Evolutionary Computation. 17 (1): 117–129. doi:10.1162/evco.2009.17.1.117. PMID 19207090. S2CID 6251842.
  17. ↑ Ho, Y. C.; Pepyne, D. L. (2002). "नो-फ्री-लंच प्रमेय और इसके निहितार्थ की सरल व्याख्या". Journal of Optimization Theory and Applications. 115 (3): 549–570. doi:10.1023/A:1021251113462. S2CID 123041865.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=खोज_और_अनुकूलन_में_कोई_निःशुल्क_लंच_नहीं&oldid=227487’