शोधकर्ताओं ने ऑनलाइन एल्गोरिदम के बारे में व्यापक विश्वास का खंडन किया | क्वांटा पत्रिका

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

शोधकर्ता इन समस्याओं से निपटने के लिए नए तरीकों की जांच करने के लिए उनके सामान्यीकृत संस्करणों का अध्ययन करते हैं। सबसे प्रसिद्ध में से एक है "k-सर्वर समस्या,'' जो एक-एक करके आने वाले अनुरोधों को पूरा करने के लिए एजेंटों के बेड़े को भेजने के कठिन कार्य का वर्णन करती है। वे मरम्मत तकनीशियन या अग्निशामक या यहां तक ​​कि घूमने वाले आइसक्रीम विक्रेता भी हो सकते हैं।

"इस समस्या को परिभाषित करना वास्तव में सरल है," ने कहा मार्सिन बीनकोव्स्की, पोलैंड में व्रोकला विश्वविद्यालय में एक एल्गोरिदम शोधकर्ता। लेकिन यह "विचित्र रूप से कठिन साबित होता है।" जब से शोधकर्ताओं ने हमला करना शुरू किया k-1980 के दशक के उत्तरार्ध में सर्वर समस्या के कारण, उन्होंने सोचा कि ऑनलाइन एल्गोरिदम कितनी अच्छी तरह कार्य को संभाल सकते हैं।

दशकों से, शोधकर्ताओं ने यह मानना ​​शुरू कर दिया है कि एल्गोरिथम प्रदर्शन का एक निश्चित स्तर है जिसे आप हमेशा प्राप्त कर सकते हैं k-सर्वर समस्या. तो इससे कोई फर्क नहीं पड़ता कि आप समस्या के किस संस्करण से निपट रहे हैं, एक एल्गोरिदम होगा जो इस लक्ष्य तक पहुंचता है। लेकिन पिछले नवंबर में पहली बार ऑनलाइन प्रकाशित एक पेपर में, तीन कंप्यूटर वैज्ञानिक पता चला यह हमेशा प्राप्त करने योग्य नहीं है। कुछ मामलों में, प्रत्येक एल्गोरिदम छोटा पड़ जाता है।

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

कंप्यूटर वैज्ञानिक पहले इस समस्या को रेखांकित किया 1988 में। इसे समझने के लिए, आइए एक ऐसी कंपनी की कल्पना करें जो प्लंबरों को रोजगार देती है। जैसे ही कॉल आती हैं, कंपनी को यह तय करना होता है कि कौन सा प्लंबर किस स्थान पर जाएगा। कंपनी का लक्ष्य - और इसके लिए एल्गोरिदम का लक्ष्य k-सर्वर समस्या - सभी प्लंबरों द्वारा तय की गई कुल दूरी को कम करना है।

मुश्किल बात यह है कि कंपनी को पहले से पता नहीं होता कि कॉल कहां से आएंगी। यदि ऐसा हुआ, तो यह भविष्य जानने वाले "ऑफ़लाइन एल्गोरिदम" पर भरोसा कर सकता है। विशेष रूप से, यह एक आदर्श प्रेषण रणनीति का उपयोग कर सकता है जो कॉल की किसी भी श्रृंखला के लिए कम से कम कुल यात्रा के साथ समाधान ढूंढता है। कोई भी ऑनलाइन एल्गोरिदम इसे हरा नहीं सकता, या यहां तक ​​कि विश्वसनीय रूप से इसकी बराबरी भी नहीं कर सकता।

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

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

फिर भी, बीनकोव्स्की ने कहा, लालची एल्गोरिदम से बेहतर करना संभव है। “दोहरा कवरेजएल्गोरिदम दोनों प्लंबरों को उनके बीच आने वाली किसी भी कॉल की ओर एक ही गति से ले जाता है, जब तक कि उनमें से एक उस तक नहीं पहुंच जाता। यह विधि लालची एल्गोरिदम की तुलना में कम प्रतिस्पर्धी अनुपात प्राप्त करती है।

हालाँकि यह अमूर्त समस्या वास्तविक प्लंबिंग कंपनियों के लिए प्रासंगिक नहीं है, “द k-ऑनलाइन कंप्यूटिंग में सर्वर समस्या ही वास्तव में निर्णायक प्रश्न है।'' युवल रबानीजेरूसलम के हिब्रू विश्वविद्यालय के एक कंप्यूटर वैज्ञानिक, जिन्होंने हालिया पेपर का सह-लेखन किया। आंशिक रूप से, ऐसा इसलिए है क्योंकि काम के दौरान उपकरण और तकनीकें विकसित हुईं k-सर्वर समस्या का अनुप्रयोग अक्सर ऑनलाइन एल्गोरिदम के अध्ययन में कहीं और पाया जाता है, और यहां तक ​​कि इसके बाहर भी।

"यह एल्गोरिदम पर काम करने के जादू का हिस्सा है," उन्होंने कहा।

जब वे इन समस्याओं का अध्ययन करते हैं, तो वैज्ञानिक उन्हें एक प्रतिद्वंद्वी के खिलाफ खेल के रूप में देखना पसंद करते हैं। प्रतिद्वंद्वी अपने ऑफ़लाइन समकक्ष की तुलना में ऑनलाइन एल्गोरिदम को यथासंभव खराब प्रदर्शन करने के लिए अनुरोधों का एक शैतानी क्रम चुनता है। प्रतिद्वंद्वी से उसकी कुछ शक्ति छीनने के लिए, शोधकर्ता एल्गोरिदम का उपयोग करते हैं जिनमें शामिल हैं यादृच्छिक निर्णय.

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

अधिकांश शोधकर्ताओं की तरह, रबानी और उनके सह-लेखक - सेबास्टियन ब्यूबेक माइक्रोसॉफ्ट रिसर्च के और क्रिश्चियन कोस्टर ऑक्सफ़ोर्ड विश्वविद्यालय के - अनुमान सच था। कोएस्टर ने कहा, "मेरे पास इस पर संदेह करने का कोई कारण नहीं था।"

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

रबानी ने कहा कि यह कोएस्टर ही थे जिन्होंने सबसे पहले यादृच्छिकता का सुझाव दिया था k-सर्वर अनुमान गलत हो सकता है. "जैसे ही उसने यह कहा, सब कुछ समझ में आ गया।"

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

विकल्पों ने रबानी को रॉबर्ट फ्रॉस्ट की कविता की याद दिला दी "अलग रास्ता,जिसमें एक यात्री एक पीली लकड़ी के माध्यम से दो संभावित रास्तों पर विचार करता है। उन्होंने मजाक में कहा, "हम सिर्फ कविता को पुनरावर्ती रूप से लागू करते हैं।" "और फिर चीजें वास्तव में खराब हो जाती हैं।"

लेखकों ने दिखाया कि, उनके द्वारा बनाए गए स्थानों में, एक यादृच्छिक एल्गोरिदम कभी भी (लॉग) से बेहतर प्रतिस्पर्धी अनुपात प्राप्त नहीं कर सकता है k)², लॉग के एक सार्वभौमिक लक्ष्य को आगे बढ़ाना k हमेशा के लिए पहुंच से बाहर. उन्होंने अनुमान का खंडन किया था.

यह काम, जिसने जीता बेस्ट पेपर अवार्ड पर कंप्यूटिंग के सिद्धांत पर 2023 संगोष्ठीगुप्ता ने कहा, यह एक “ठोस सैद्धांतिक” मील का पत्थर है। इस प्रकार के परिणाम यह इंगित करने में मदद करते हैं कि हम अपने एल्गोरिदम से किस प्रकार के प्रदर्शन की उम्मीद कर सकते हैं। हालाँकि, व्यवहार में, एल्गोरिथम डिज़ाइनर अक्सर सर्वशक्तिमान प्रतिद्वंद्वी और भविष्य की पूरी अज्ञानता के साथ सबसे खराब स्थिति के आसपास योजना नहीं बनाते हैं। जब एल्गोरिदम वास्तविक दुनिया की समस्याओं पर लागू होते हैं, तो वे अक्सर सैद्धांतिक अपेक्षाओं से अधिक होते हैं।

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

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

क्वांटा अपने दर्शकों को बेहतर सेवा देने के लिए सर्वेक्षणों की एक श्रृंखला आयोजित कर रहा है। हमारा ले कंप्यूटर विज्ञान पाठक सर्वेक्षण और आपको निःशुल्क जीतने के लिए प्रवेश दिया जाएगा क्वांटा माल।