Revisiting column subset selection through the lens of submodularity
यह शोध पत्र स्थापित करता है कि कॉलम वॉल्यूम के लघुगणक (logarithm) को अधिकतम करना एक उप-मॉड्यूलर (submodular) समस्या है, जिससे यह स्पष्ट होता है कि पारंपरिक कॉलम पिवोटिंग वाला बुसिंगर-गोलब (Businger-Golub) क्यूआर, गु-आइजनस्टैट (Gu-Eisenstat) स्ट्रॉन्ग रैंक-रिवीलिंग क्यूआर की तुलना में एक बेहतर सापेक्ष त्रुटि सीमा (relative error bound) वाला एक ग्रीडी एल्गोरिदम है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक जासूस हैं जो एक विशाल पहेली को सुलझाने की कोशिश कर रहे हैं, लेकिन आपके पास केवल एक छोटी सी नोटबुक है। आप अपराध स्थल से हर एक सुराग अपनी नोटबुक में नहीं लिख सकते क्योंकि आपकी नोटबुक बहुत छोटी है। इसलिए, आपको उन कुछ बेहतरीन सुरागों को चुनना होगा जो पूरी तस्वीर को फिर से बनाने में आपकी मदद कर सकें। यह एक ऐसी समस्या है जो विज्ञान और तकनीक में हर जगह दिखाई देती है, जैसे कि स्मार्ट कंप्यूटरों को प्रशिक्षित करने से लेकर यह तय करने तक कि सेल फोन टावर कहाँ लगाए जाएं। चुनौती यह है कि उन कुछ सुरागों को चुनने के लाखों तरीके हो सकते हैं, और हर एक संयोजन की जांच करने में ब्रह्मांड के अस्तित्व से भी अधिक समय लग जाएगा।
इसे प्रबंधनीय बनाने के लिए, गणितज्ञ "सबमॉड्यूलरिटी" (submodularity) नामक एक विशेष प्रकार के तर्क का उपयोग करते हैं। इसे "घटते प्रतिफल" (diminishing-returns) के नियम के रूप में सोचें: आपके द्वारा प्राप्त किया गया पहला सूचना का टुकड़ा आमतौर पर सबसे मूल्यवान होता है। दूसरा टुकड़ा अभी भी मददगार है, लेकिन शायद पहले की तुलना में उतना नहीं है, क्योंकि आपके पास पहले से ही तस्वीर का कुछ हिस्सा है। तीसरा टुकड़ा और भी कम मदद करता है, और इसी तरह। यदि कोई समस्या इस नियम का पालन करती है, तो आपको हर संभावना की जांच करने की आवश्यकता नहीं है; आप बस प्रत्येक चरण में उपलब्ध "सबसे अच्छे" चीज़ को लालची होकर (greedily) चुन सकते हैं, और आप बिना सारा कठिन काम किए एक बहुत अच्छा परिणाम प्राप्त कर लेंगे।
अब, इल्से इप्सन और अरविंद साइबाबा के एक नए शोध पत्र की ओर बढ़ें। वे एक विशिष्ट प्रकार की पहेली की ओर देख रहे हैं: एक विशाल संख्या ग्रिड (मैट्रिक्स) से सबसे अच्छे कॉलम चुनना ताकि पूरे ग्रिड का सटीक प्रतिनिधित्व किया जा सके। उन्होंने "सटीकता" को मापने के लिए "वॉल्यूम" (आयतन) नामक चीज़ का उपयोग करने का निर्णय लिया। कल्पना कीजिए कि आपके ग्रिड के कॉलम फर्श से खड़े हुए डंडे हैं। यदि आप कुछ डंडे चुनते हैं, तो वे एक आकार बनाते हैं। "वॉल्यूम" वह स्थान है जिसे वह आकार भरता है। वॉल्यूम जितना अधिक होगा, वे डंडे उतने ही अद्वितीय और सूचनात्मक होंगे। लेखकों ने सिद्ध किया कि इस वॉल्यूम का "लॉगारिदम" (विशाल संख्याओं को प्रबंधनीय आकार में सिकोड़ने का एक गणितीय तरीका) उस "घटते प्रतिफल" के नियम का पूरी तरह से पालन करता है। इसका मतलब है कि सबसे अच्छे कॉलम चुनने की समस्या वास्तव में एक सबमॉड्यूलर समस्या है, जो सरल, तेज़ रणनीतियों का उपयोग करके शानदार समाधान खोजने का मार्ग खोलती है।
इसके बाद, शोध पत्र दो प्रसिद्ध कंप्यूटर एल्गोरिदम का परीक्षण करता है यह देखने के लिए कि कौन सा कॉलम चुनने में बेहतर है। पहला "बसिंगर-गोलब" (Businger-Golub) तरीका है, जो एक लालची पदयात्री (greedy hiker) की तरह है जो हमेशा अगला कदम चुनता है जो अभी सबसे तीव्र और सबसे आशाजनक दिखता है। दूसरा "गु-आइजनस्टैट" (Gu-Eisenstat) तरीका है, जो एक ऐसे पदयात्री की तरह है जो एक रास्ता चुनता है, थोड़ा चलता है, और फिर पीछे मुड़कर देखता है कि क्या पहले लिए गए किसी कदम को बदलने से पूरी यात्रा बेहतर हो सकती है।
शोधकर्ताओं ने एक आश्चर्यजनक बात पाई जो यह बताती है कि सरल तरीका वास्तविक दुनिया में अक्सर बेहतर क्यों काम करता है। जब डेटा को इस तरह से स्केल किया जाता है कि इसके सबसे छोटे सिंगुलर मान (singular values) कम से कम 1 हों (एक ऐसी स्थिति जिसे मैट्रिक्स को एक स्थिरांक से गुणा करके प्राप्त किया जा सकता है), तो लालची बसिंगर-गोलब पदयात्री को इस विशिष्ट मीट्रिक के तहत सर्वोत्तम संभव वॉल्यूम के 37% के भीतर रहने की गारंटी है। अधिक जटिल गु-आइजनस्टैट पदयात्री, जो पथ को सुधारने के लिए कदमों को बदलने की कोशिश करता है, को इसी मीट्रिक के तहत सर्वोत्तम के 50% के भीतर रहने की गारंटी है। दूसरे शब्दों में, पूर्ण-रैंक या उचित रूप से स्केल किए गए मैट्रिक्स के लिए, सरल, लालची दृष्टिकोण वास्तव में इस विशिष्ट माप के अनुसार जटिल रणनीति की तुलना में अधिक सटीक है!
हालाँकि, यह पत्र इस बात के लिए भी चेतावनी देता है कि यह हर स्थिति के लिए जादुई समाधान नहीं है। यदि डेटा अव्यवस्थित है या "रैंक-डेफिशिएंट" (rank-deficient) है (अर्थात कुछ कॉलम एक-दूसरे की प्रतियां हैं), तो "वॉल्यूम" का नियम टूट सकता है और अजीब तरह से व्यवहार करना शुरू कर सकता है। ऐसे पेचीदा मामलों में, लेखक "ट्रेस" (trace) नामक एक अलग माप देखने का सुझाव देते हैं, जो केवल एक विशिष्ट गणितीय विभाजन में विकर्ण संख्याओं का योग है। इस नए माप के साथ भी, लालची बसिंगर-गोलब विधि बढ़त बनाए रखती है, जो 37% त्रुटि मार्जिन के भीतर रहती है, जबकि बदलने वाली (swapping) विधि 50% पर रहती है।
लेखकों ने इन निष्कर्षों को एक विशेष प्रकार के ग्रिड तक विस्तारित किया जिसे "सिमेट्रिक पॉजिटिव-डेफिनिट" (symmetric positive-definite) मैट्रिक्स कहा जाता है, जो मौसम के पैटर्न की भविष्यवाणी करने या सेंसर डेटा का विश्लेषण करने जैसी चीजों में दिखाई देता है। उन्होंने दिखाया कि "चोलेस्की फैक्टराइजेशन" (Cholesky factorization) का उपयोग करने वाला एक समान "लालची" दृष्टिकोण सामान्य ग्रिड के लिए कॉलम-चुनने के तरीकों की तरह ही अच्छा काम करता है।
अंततः, यह शोध पत्र कोई नया एल्गोरिदम आविष्कार नहीं करता है; इसके बजाय, यह इस बात पर प्रकाश डालता है कि दशकों से उपयोग किए जा रहे हमारे पुराने, सरल एल्गोरिदम इतने प्रभावी क्यों हैं। यह सिद्ध करके कि समस्या "सबमॉड्यूलर" सांचे में फिट बैठती है (विशेष रूप से जब डेटा को उचित रूप से स्केल किया जाता है), लेखकों ने हमें उस लालची दृष्टिकोण पर भरोसा करने का एक गणितीय कारण दिया है। उन्होंने दिखाया कि कभी-कभी, "अभी सबसे अच्छी चीज़ चुनें" वाली सरल रणनीति न केवल तेज़ है, बल्कि वास्तव में उस जटिल रणनीति की तुलना में अधिक विश्वसनीय है जो खुद पर संदेह करने की कोशिश करती है। यह एक याद दिलाता है कि बिग डेटा की दुनिया में, सीधा रास्ता अक्सर सबसे सटीक मंजिल की ओर ले जाता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।