A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

कल्पना कीजिए कि आप एक रोबोट को भूलभुलैया (maze) सुलझाना सिखाने की कोशिश कर रहे हैं। कभी-कभी भूलभुलैया एक साधारण, सीधी गलियारे जैसी होती है; और कभी-कभी यह घुमावदार, मुड़ने वाली एक ऐसी भूलभुलैया होती है जिसमें डेड एंड (रास्ते बंद होना) और जाल होते हैं। कंप्यूटर विज्ञान की दुनिया में, इसे ऑप्टिमाइज़ेशन (optimisation) कहा जाता है: किसी समस्या का सबसे अच्छा संभव समाधान खोजना। लेकिन यहाँ एक पेचीदा बात है: सभी भूलभुलैया एक जैसी नहीं होतीं। कुछ भूलभुलैया रोबोट के लिए हल करना आसान होता है, जबकि कुछ इतनी जटिल होती हैं कि सबसे स्मार्ट एल्गोरिदम भी उनमें खो जाते हैं।

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

---

कोड एक क्रिस्टल बॉल की तरह

इस शोध पत्र में, मार्कस गैलघेर और कैथरीन मालन इन कठिन समस्याओं को देखने का एक नया, थोड़ा जादुई तरीका प्रस्तावित करते हैं। परिदृश्य (landscape) को मापने के लिए स्काउट भेजने के बजाय, वे सुझाव देते हैं कि हमें बस उस "रेसिपी" को पढ़ लेना चाहिए जिसका उपयोग कंप्यूटर उस समस्या को बनाने के लिए करता है।

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

लेखकों का बड़ा विचार यह है: कोड जितना अधिक अव्यवस्थित और जटिल होगा, एल्गोरिदम के लिए समस्या को हल करना उतना ही कठिन होगा।

वे इस "अव्यवस्थितता" को मापने के लिए सॉफ्टवेयर इंजीनियरिंग की दुनिया से दो उपकरणों का उपयोग करते हैं।

1. हेल्डस्टैड वॉल्यूम (Halstead Volume): कल्पना कीजिए कि आप एक पैराग्राफ में हर एक शब्द और प्रतीक को गिन रहे हैं। यदि आपके पास सरल शब्दों वाली एक छोटी कहानी है, तो गणना कम है। यदि आपके पास जटिल शब्दावली और लंबे वाक्यों वाला एक उपन्यास है, तो गणना अधिक है। यह माप कोड में "ऑपरेटरों" (जैसे गणितीय प्रतीक) और "ऑपरेंड्स" (जैसे संख्याएं और चर/variables) को गिनता है।
2. शैनन एंट्रॉपी (Shannon Entropy): यह थोड़ा 'आश्चर्य के कारक' (surprise factor) को मापने जैसा है। यदि एक पैराग्राफ बार-बार एक ही पांच शब्दों का उपयोग करता है, तो यह अनुमानित है (कम एंट्रॉपी)। यदि यह एक अनिश्चित क्रम में कई अद्वितीय शब्दों का उपयोग करता है, तो यह अप्रत्याशित है (उच्च एंट्रॉपी)।

प्रयोग: सरल वृत्तों से लेकर अराजक चोटियों तक

अपने सिद्धांत का परीक्षण करने के लिए, लेखकों ने 24 परीक्षण समस्याओं का एक प्रसिद्ध सेट लिया जिसका उपयोग दुनिया भर के वैज्ञानिक करते हैं (जिसे BBOB सूट के रूप में जाना जाता है)। ये "स्फीयर" (Sphere) फंक्शन (एक पूरी तरह से चिकना, गोल पहाड़ी जो नीचे लुढ़कने में आसान है) से लेकर "लुनासेक बी-रास्ट्रिगिन" (Lunacek bi-Rastrigin) फंक्शन (हजारों छोटी चोटियों और घाटियों वाला एक ऊबड़-खाबड़, पथरीला परिदृश्य) तक विस्तृत हैं।

उन्होंने प्रत्येक 24 समस्याओं के लिए कंप्यूटर कोड लिखा और अपने "अव्यवस्थितता" कैलकुलेटर चलाए। परिणाम बिल्कुल वैसे ही थे जैसी उन्हें उम्मीद थी:

• सरल, चिकना स्फीयर फंक्शन का जटिलता स्कोर सबसे कम था।
• ऊबड़-खाबड़, कठिन लुनासेक फंक्शन का जटिलता स्कोर सबसे अधिक था।
• वास्तव में, लुनासेक फंक्शन की कोड संरचना स्फीयर फंक्शन की तुलना में लगभग 9.3 गुना अधिक जटिल थी।

उन्होंने इसका परीक्षण एक अलग प्रकार की समस्या पर भी किया: एक न्यूरल नेटवर्क (एक प्रकार का AI मस्तिष्क) को प्रशिक्षित करना। उन्होंने पाया कि "Tanh" एक्टिवेशन फंक्शन का उपयोग करने वाले नेटवर्क का कोड "ReLU" की तुलना में थोड़ा अधिक जटिल था, और यह इस विचार से मेल खाता है कि Tanh वाला संस्करण हल करने के लिए एक थोड़ा कठिन पहेली है।

जादुई संबंध: कोड की जटिलता प्रदर्शन की भविष्यवाणी करती है

असली जादू तब होता है जब वे इन कोड स्कोर की तुलना इस बात से करते है कि विभिन्न एल्गोरिदम ने वास्तव में कैसा प्रदर्शन किया। उन्होंने इन 24 समस्याओं को हल करने की कोशिश करने वाले पांच अलग-अलग "रोबोट" एल्गोरिदम के डेटा को देखा।

उन्होंने एक स्पष्ट पैटर्न पाया: कोड जितना अधिक जटिल होगा, रोबोट का प्रदर्शन उतना ही खराब होगा।

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

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

यह क्यों मायने रखता है

इस दृष्टिकोण की सुंदरता यह है कि यह अविश्वसनीय रूप से तेज़ है और इसमें कोई अतिरिक्त काम नहीं करना पड़ता है। समस्याओं को समझने के पारंपरिक तरीकों में अक्सर यह देखने के लिए एल्गोरिदम को हजारों बार चलाना शामिल होता है कि परिदृश्य (landscape) कैसा दिखता है। यह एक मानचित्र बनाने के लिए पूरे भूलभुलैया में स्काउट भेजने जैसा है।

इसके विपरीत, लेखकों का तरीका भूलभुलैया के ब्लूप्रिंट को देखने जैसा है। आप समस्या को एक बार भी चलाए बिना, एक सेकंड के भीतर कोड की जटिलता की गणना कर सकते हैं। यह इस बात की परवाह नहीं करता कि समस्या कितनी बड़ी है या उसके कितने आयाम (dimensions) हैं; यह केवल निर्देशों की संरचना को देखता है।

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