जटिल जानकारी को छांटने के लिए एक सार्वभौमिक विधि की खोज की गई थी

अपना कैफे खोलते हुए, आप निम्नलिखित प्रश्न का उत्तर जानना चाहेंगे: "अन्य कैफे इस बिंदु के सबसे करीब कहाँ है?" यह जानकारी आपको अपने प्रतियोगियों को बेहतर ढंग से समझने में मदद करेगी।

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

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

और अब, कंप्यूटर वैज्ञानिकों की एक टीम ने निकटतम पड़ोसी को खोजने की समस्या को हल करने के लिए पूरी तरह से नया तरीका निकाला है। कागजात की एक जोड़ी में , पांच वैज्ञानिकों ने जटिल डेटा के लिए निकटतम पड़ोसी को खोजने की समस्या को हल करने के लिए पहले सामान्यीकृत विधि का विस्तार से वर्णन किया।

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

दूरी का अंतर

हम दूरी को निर्धारित करने के एकमात्र तरीके से इतने जुड़े हुए हैं कि अन्य तरीकों की संभावना से दृष्टि खोना आसान है। आमतौर पर हम यूक्लिडियन के रूप में दूरी को मापते हैं - दो बिंदुओं के बीच एक सीधी रेखा के रूप में। हालांकि, ऐसी परिस्थितियां हैं जिनमें अन्य परिभाषाएं अधिक मायने रखती हैं। उदाहरण के लिए, मैनहट्टन की दूरी आपको 90 डिग्री तक मोड़ देती है, जैसे कि सड़कों के आयताकार नेटवर्क के साथ चलती है। ऐसी दूरी को मापने के लिए जो एक सीधी रेखा में 5 किलोमीटर हो सकती है, आपको शहर को एक दिशा में 3 किमी पार करने की आवश्यकता हो सकती है और फिर दूसरी में 4 और।

भौगोलिक दृष्टि से नहीं दूरी के बारे में बात करना भी संभव है। एक सामाजिक नेटवर्क में दो लोगों के बीच की दूरी, या दो फिल्में या दो जीनोम क्या हैं? इन उदाहरणों में, दूरी समानता की डिग्री को इंगित करती है।

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

एडिटिंग डिस्टेंस और यूक्लिडियन डिस्टेंस डिस्टेंस की दो अलग-अलग अवधारणाएं हैं, और एक को कम करना असंभव है। यह असंगति दूरी जोड़े के कई जोड़े के लिए मौजूद है, और कंप्यूटर वैज्ञानिकों के लिए एक बाधा है जो निकटतम पड़ोसी को खोजने के लिए एल्गोरिदम विकसित करने की कोशिश कर रहा है। इसका मतलब यह है कि एक एल्गोरिथ्म जो एक प्रकार की दूरी के लिए काम करता है, दूसरे के लिए काम नहीं करेगा - अधिक सटीक रूप से, यह अब तक था, जब तक कि एक नई तरह की खोज प्रकट नहीं हुई।


अलेक्जेंडर एंडोनी

वृत्त वर्ग

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

फिर प्रक्रिया को दोहराएं। मंडलियों को उप-वर्ग में विभाजित करें, इन कोशिकाओं को आगे विभाजित करें, और इसी तरह। नतीजतन, केवल दो बिंदुओं वाला एक सेल है: मौजूदा और नया। यह मौजूदा बिंदु आपका निकटतम पड़ोसी होगा।


ऊपर कोशिकाओं में डेटा का विभाजन है। नीचे विस्तार ग्राफ का उपयोग किया गया है।

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

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

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

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

“आप कुछ विशिष्ट मामलों के लिए यूक्लिडियन या मैनहट्टन दूरी के लिए एक बहुत प्रभावी एल्गोरिदम के साथ आ सकते हैं। लेकिन हमारे पास एक एल्गोरिथ्म नहीं था जो एक बड़े वर्ग के लिए काम करता था। ”

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


इलिया रज़नेशिन

अप्रत्याशित परिणाम

एक नए काम में, वैज्ञानिकों ने विशेष एल्गोरिदम की खोज को छोड़ दिया। इसके बजाय, उन्होंने एक व्यापक सवाल पूछा: एक निश्चित दूरी मीट्रिक पर एल्गोरिथ्म के विकास को क्या रोकता है?

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

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

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

"दो हिस्सों में विस्तारक को काटने के लिए किसी भी तरह से कई पसलियों को काटने की आवश्यकता होती है, जो कई करीबी रूप से लंबित हिस्सों को विभाजित करता है," वेइंगटन, काम के सह-लेखक ने कहा।

2016 की गर्मियों तक, एंडोनी, न्योकोलोव, रासेनस्टीन और वनगार्टन जानते थे कि विस्तारकों के लिए निकटतम पड़ोसी को खोजने के लिए एक अच्छा एल्गोरिथ्म नहीं आ सकता है। लेकिन वे यह साबित करना चाहते थे कि कई अन्य दूरी के मेट्रिक्स - मेट्रिक्स के लिए ऐसे एल्गोरिदम का निर्माण करना असंभव है, जब अच्छे एल्गोरिदम की खोज की जाए जिसके लिए कंप्यूटर वैज्ञानिक एक ठहराव में आए हैं।

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


एरिक वेनगार्टन

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

"हमने असफ को इस बयान के साथ मदद करने के लिए कहा, और उन्होंने इसके विपरीत साबित किया," एंडोनी ने कहा।

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

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

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

नतीजतन, नए काम पहली बार बहुआयामी डेटा में निकटतम पड़ोसी की खोज को सामान्य करते हैं। विशिष्ट मैट्रिक्स के लिए विशेष एल्गोरिदम विकसित करने के बजाय, प्रोग्रामर के पास एल्गोरिदम खोजने के लिए एक सार्वभौमिक दृष्टिकोण है।

"विन्गार्टन ने कहा," किसी भी दूरी के मैट्रिक्स में निकटतम पड़ोसी को खोजने के लिए एल्गोरिदम विकसित करने के लिए यह एक व्यवस्थित तरीका है। "