तरंग फ़ंक्शन पतन एल्गोरिथम की एक सुलभ व्याख्या

वेवफंक्शन संक्षिप्त एल्गोरिथ्म एक कंप्यूटर को सुधारना सिखाता है। इनपुट पर, यह चापलूसी डेटा प्राप्त करता है और मूल रूप से प्रक्रियात्मक रूप से उत्पन्न डेटा बनाता है।


( स्रोत )

अधिकतर इसका उपयोग चित्र बनाने के लिए किया जाता है, लेकिन यह शहरों , स्केटपार्क का निर्माण भी कर सकता है और भयानक कविताएँ लिख सकता है।


( स्रोत )

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

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

कहानी से शुरू करते हैं।

शादी

कल्पना कीजिए कि आप अपनी शादी की योजना बना रहे हैं। गहने और संगीत के चयन के अलावा, आपको रात के खाने के लिए मेहमानों के लिए बैठने की योजना बनाने की आवश्यकता है। आपका परिवार बहस करना और शरारती होना पसंद करता है, इसलिए यह मुश्किल हो सकता है। एक पिता अपनी मां से दो तालिकाओं के करीब नहीं बैठ सकता है। एक चचेरा भाई अकेला हो जाता है अगर वह दूसरे चचेरे भाई के साथ नहीं बैठता है। और अपने साथी के परिवार के पर्यावरण के अनुकूल सदस्यों के बगल में अंकल रॉय को रोपण नहीं करना बेहतर है। यह भोजन के आगमन से केवल 5 घंटे पहले रहता है, इसलिए आप लहर कार्य पतन एल्गोरिथ्म का उपयोग करके इस जिद्दी कार्य पर हमला करने का निर्णय लेते हैं।

आप नियमों की एक लंबी सूची और खाली बैठने की योजना के साथ शुरू करते हैं।


आप योजना की मूल तरंग फ़ंक्शन बनाते हैं। वह प्रत्येक कुर्सी को उन लोगों की सूची में बाँधता है जो उस पर बैठ सकते हैं। जबकि कोई भी व्यक्ति किसी भी कुर्सी पर बैठ सकता है। मेहमानों के बैठने की लहर समारोह प्रत्येक संभावित योजना के पूर्ण सुपरपोजिशन (क्वांटम भौतिकी से उधार लिया गया है) से शुरू होता है।


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

हम एक कुर्सी के लिए तरंग फ़ंक्शन के पतन का प्रदर्शन करके ऐसा करना शुरू करते हैं। हम एक कुर्सी का चयन करते हैं, उन लोगों की सूची को देखते हैं जो उस पर बैठ सकते हैं, और उनमें से एक को यादृच्छिक रूप से असाइन कर सकते हैं। इस स्थिति में, स्टूल की तरंग फ़ंक्शन ढह जाती है।


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


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

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

यदि आप एक विरोधाभास पर पहुंच गए हैं, तो सबसे आसान तरीका शुरू करना है। सभी पिछले काम को छोड़ दें, एक नई खाली योजना ढूंढें और एल्गोरिथ्म को फिर से शुरू करें, एक और यादृच्छिक कुर्सी के लिए लहर फ़ंक्शन के पतन को पूरा करें। आप एक बैकट्रैकिंग सिस्टम भी लागू कर सकते हैं जो आपको एक विशेष विकल्प को रद्द करने की अनुमति देता है, बजाय तुरंत सब कुछ त्यागने के लिए ("क्या होगा यदि शीला को कुर्सी 54 पर स्थानांतरित किया गया है?")।

कुछ झूठी शुरुआत के बाद, आप अंत में पूरी तरह से ढह गई स्थिति में पहुंच जाएंगे जिसमें प्रत्येक कुर्सी को एक व्यक्ति को सौंपा गया है और सभी नियमों का पालन किया जाता है। हो गया!

शादी से लेकर बिटमैप तक

यह कोई सैद्धांतिक उदाहरण नहीं है। आप वास्तव में लहर फ़ंक्शन के पतन के एक संस्करण का एहसास कर सकते हैं, जो शादी के लिए मेहमानों के लिए बैठने की योजना बनाएगा। हालांकि, अधिक परंपरागत वेवफंक्शन पतन में, हम आमतौर पर शादी में लोगों को सीट नहीं देने की कोशिश करते हैं, लेकिन आउटपुट छवि में पिक्सेल की व्यवस्था करते हैं। हालांकि, प्रक्रिया बहुत समान होगी। हम एल्गोरिथ्म को नियमों का एक सेट सिखाते हैं जो आउटपुट को संतुष्ट करना चाहिए। हम तरंग फ़ंक्शन को प्रारंभ करते हैं। हम एक तत्व का पतन करते हैं और परिणाम को तरंग फ़ंक्शन के बाकी हिस्सों तक बढ़ाते हैं। और हम ऐसा करना जारी रखते हैं, या तो जब तक कि तरंग फ़ंक्शन पूरी तरह से ढह नहीं जाता, या जब तक हम एक विरोधाभास तक नहीं पहुंचते।

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

आइए एक साधारण विशेष मामले को देखते हुए एक लहर फ़ंक्शन के वास्तविक पतन का शोध करना शुरू करें, जिसे ExUtumno (एल्गोरिथ्म का निर्माता) सरल टाइल वाले मॉडल कहते हैं ।

साधारण टाइल वाला मॉडल

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


सिंपल टाइलेड मॉडल इसकी टाइल्स की समरूपता और घुमाव को ध्यान में रखता है। उदाहरण के लिए, भूमि तट के पास हो सकती है, लेकिन केवल सही अभिविन्यास में।


यह समरूपता प्रसंस्करण बेहतर आउटपुट चित्र प्रदान करता है, लेकिन कोड को जटिल बनाता है। चीजों को सरल रखने के लिए, आइए लहर फ़ंक्शन के पतन के एक और भी सरल दृश्य को देखें, जिसे मैंने सम सरल टाइल वाला मॉडल कहा था।

यहां तक ​​कि सरल टाइल वाले मॉडल

यहां तक ​​कि सरल टाइल वाले मॉडल ("एक भी सरल टाइल मॉडल") साधारण टाइल वाले मॉडल के समान है, लेकिन इसकी टाइलों में समरूपता गुण नहीं हैं। प्रत्येक टाइल एक ही रंग का एक पिक्सेल है, अर्थात, हम किसी भी तरह से उनके किनारों को भ्रमित करने में सक्षम नहीं होंगे।


यहां तक ​​कि सरल टाइल वाले मॉडल नियम यह निर्धारित करते हैं कि कौन सी टाइलें एक दूसरे के बगल में और किस अभिविन्यास में रखी जा सकती हैं। प्रत्येक नियम तीन तत्वों (3-ट्यूपल) का एक टपल है: दो टाइलें और एक दिशा। उदाहरण के लिए, (SEA, COAST, LEFT) अर्थ है कि SEA टाइल (समुद्र) COAST टाइल (तट) से हो सकती है। यह नियम किसी अन्य नियम के साथ होना चाहिए जो COAST - (COAST, SEA, RIGHT) संदर्भ में स्थिति का वर्णन करता है।


यदि आप चाहते हैं कि SEA टाइल्स न केवल , बल्कि COAST टाइल्स से पर भी स्थित हों। तब उन्हें अतिरिक्त नियमों की आवश्यकता होती है: (SEA, COAST, RIGHT) और (COAST, SEA, LEFT) ।

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


ऊपर दिखाए गए उदाहरण की छवि की जांच की, यहां तक ​​कि सरल टाइल वाले मॉडल ने यह नोटिस किया कि समुद्री टाइलें केवल तट टाइलों के नीचे या कहीं भी हो सकती हैं, या अन्य समुद्री टाइलों के पास कहीं भी। वह यह भी नोट करती है कि तट टाइलें भूमि, समुद्र या अन्य तट टाइलों के बगल में स्थित हो सकती हैं, लेकिन केवल समुद्र की टाइलों के ऊपर और जमीन की टाइलों के नीचे। वह किसी भी अधिक जटिल नियमों को प्राप्त करने की कोशिश नहीं करती है, उदाहरण के लिए, "समुद्री टाइलें कम से कम एक समुद्री टाइल के पास होनी चाहिए" या "प्रत्येक द्वीप में कम से कम एक लैंड टाइल होना चाहिए।" टाइलों में से कोई भी इस तथ्य को प्रभावित नहीं कर सकता है कि कुछ प्रकार की टाइलें उनसे दो या अधिक वर्ग स्थित हो सकती हैं या नहीं। यह एक विवाह योजना मॉडल के समान है जिसमें एकमात्र नियम है: "X, Y के बगल में बैठ सकता है"।

आने वाली छवि का विश्लेषण करते समय, हमें उस आवृत्ति को भी रिकॉर्ड करना होगा जिसके साथ प्रत्येक टाइल मिलती है। बाद में, हम इन संख्याओं को भार के रूप में उपयोग करते हैं, जब स्क्वायर की लहर फ़ंक्शन का चयन करते हैं, जिसके पतन का प्रदर्शन किया जाना चाहिए, साथ ही जब यह ढह जाता है तो स्क्वायर को सौंपी गई टाइल को चुनते समय।

आउटपुट इमेज का पालन करने वाले नियमों को जानने के बाद, हम आउटपुट इमेज के वेव फंक्शन के पतन के लिए तैयार हैं।

गिरावट

जैसा कि शादी के उदाहरण में, हम एक लहर फ़ंक्शन के साथ पतन की प्रक्रिया शुरू करते हैं जिसमें आउटपुट छवि का प्रत्येक वर्ग प्रत्येक प्रकार के टाइल के एक सुपरपोजिशन में होता है।


हम एक वर्ग का चयन करके शुरू करते हैं, जिसकी लहर फ़ंक्शन ढह जाएगी। शादी के उदाहरण में, यह विकल्प संयोग से बनाया गया था। हालाँकि, जैसा कि ExUtumno ने उल्लेख किया है, लोग आमतौर पर इन कार्यों को अलग तरीके से करते हैं। इसके बजाय, वे सबसे कम एन्ट्रापी वाले वर्गों की तलाश करते हैं। एन्ट्रॉपी अनिश्चितता और विकार का एक उपाय है। सामान्य तौर पर, उच्च एन्ट्रॉपी वाला एक वर्ग एक ऐसा वर्ग होता है, जिसमें कई लहरें होती हैं, जो इसकी तरंग क्रिया में शेष होती हैं। यह अभी भी स्पष्ट नहीं है कि वह किस टाइल से टकराता है। एक कम एन्ट्रापी वर्ग तरंग फ़ंक्शन में सबसे कम संभव टाइलों वाला एक वर्ग है। टाइल्स का सेट, जिसमें से एक के परिणामस्वरूप वह गिरता है, पहले से ही बहुत सीमित है।

उदाहरण के लिए, सम सरल टाइल मॉडल में, आसपास के चौकों के बारे में जानकारी के बिना एक वर्ग असीमित है और कोई भी टाइल बन सकता है। इसलिए, इसमें बहुत अधिक एन्ट्रापी है। लेकिन एक वर्ग जिसके आस-पास कई वर्ग पहले ही ढह चुके हैं, केवल 2 टाइलों का विकल्प हो सकता है।


ऊपर की आकृति में केंद्रीय वर्ग की तरंग फ़ंक्शन पूरी तरह से नहीं गिरती है, लेकिन हम पहले से ही जानते हैं कि यह एक भूमि टाइल नहीं हो सकती है। हालांकि, यह पहले से ही सीमित है, जिसका अर्थ है कि यह ऊपरी दाएं वर्ग की तुलना में एक एंट्रोपी कम है, जो अभी भी भूमि, समुद्र या तट हो सकता है।

यह कम एन्ट्रॉपी वाली ऐसी सीमित टाइलें हैं जिन पर लोग आमतौर पर ध्यान देते हैं जब वे ऐसी समस्याओं को मैन्युअल रूप से हल करते हैं। यहां तक ​​कि अगर आप शादी में मेहमानों को समायोजित करने के लिए एक योजना बनाने के लिए लहर समारोह के पतन का उपयोग नहीं करते हैं और इसे अपने दम पर आकर्षित करेंगे, फिर भी योजना के उन क्षेत्रों पर ध्यान केंद्रित करें जिनके पास पहले से ही सबसे अधिक प्रतिबंध हैं। आप ड्वेन को टेबल 1 पर नहीं रखेंगे, और फिर केटी को टेबल 7 (जो अब तक खाली है) पाने के लिए बेतरतीब ढंग से कूदेंगे। आप पहले ड्वेन को लगाते हैं, फिर आप यह पता लगाएंगे कि कौन उसके बगल में बैठ सकता है, फिर कौन इस व्यक्ति के बगल में बैठ सकता है, इत्यादि। मैंने अभी तक इसके लिए तर्क नहीं देखा है, लेकिन मेरा अंतर्ज्ञान कहता है कि न्यूनतम एन्ट्रॉपी के इस अनुमान का उपयोग करने से कम विरोधाभास पैदा होने की संभावना कम होती है , यदि आप बेतरतीब ढंग से पतन के लिए वर्गों का चयन करते हैं।

शैनन फार्मूला का उपयोग तरंग फ़ंक्शन पतन एल्गोरिथम में एन्ट्रापी फॉर्मूला के रूप में किया जाता है। यह उन टाइलों के वजन का उपयोग करता है जिन्हें हमने पिछले चरण में आने वाली छवि से पार्स किया था:

 # Sums are over the weights of each remaining # allowed tile type for the square whose # entropy we are calculating. shannon_entropy_for_square = log(sum(weight)) - (sum(weight * log(weight)) / sum(weight)) 

सबसे छोटी एन्ट्रॉपी के साथ तरंग फ़ंक्शन के वर्ग की गणना करने के बाद, हम इसकी तरंग फ़ंक्शन को ध्वस्त करते हैं। हम बेतरतीब ढंग से उन टाइलों में से एक का चयन करके करते हैं जो अभी भी वर्ग के लिए उपलब्ध हैं, टाइलों के वजन से भारित होता है जिसे हमने आने वाली छवि से पार्स किया था। वज़न का उपयोग किया जाता है क्योंकि यह अधिक यथार्थवादी आउटपुट छवि प्रदान करता है। मान लीजिए कि एक चौकोर रिपोर्ट का काम यह है कि यह भूमि या तट हो सकता है। हमें हमेशा 50% की संभावना वाले विकल्पों में से एक को चुनना नहीं पड़ता है। यदि इनपुट छवि में तट की तुलना में अधिक भूमि टाइल है, तो हमें आउटपुट छवि में इस लाभ को प्रतिबिंबित करना चाहिए। यह सरल वैश्विक भार का उपयोग करके महसूस किया जाता है। यदि उदाहरण छवि में 20 भूमि टाइलें और 10 तट टाइलें हैं, तो वर्ग 2/3 संभावना के साथ भूमि में और 1/3 की शेष संभावना के साथ तट में ढह जाता है।

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

परिणामस्वरूप, हमने एक दुनिया (या गलती) बनाई।

आगे कहाँ जाना है

इवन सिंपल टाइल्ड मॉडल से निपटने के बाद, आप एल्गोरिथ्म की शक्ति और जटिलता की सीढ़ी पर चढ़ने के लिए तैयार हैं। सरल टाइल वाले मॉडल से शुरू करें जो हमने इस पोस्ट की शुरुआत में उल्लेख किया था, फिर पूर्ण ओवरलैपिंग मॉडल पर जाएं। ओवरलैपिंग मॉडल में, टाइल या पिक्सेल एक दूसरे को दूर से प्रभावित करते हैं। यदि आप ऐसी चीजों को समझते हैं, तो ExUtumno नोटिस करता है कि सिंपल ExUtumno मॉडल ऑर्डर -1 के मार्कोव चेन के समान है, और अधिक जटिल मॉडल एक बड़े ऑर्डर की चेन से मिलते जुलते हैं।

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

लहर फ़ंक्शन का पतन एक सुंदर और शक्तिशाली उपकरण है जो मास्टरिंग के लायक है। अगली बार जब आप शादी की योजना बनाते हैं या एक प्रक्रियात्मक दुनिया उत्पन्न करते हैं, तो इसके बारे में सोचें।