Convergence of Alternating Gradient Descent to Nuclear-Norm Minimizing Factorizations

मशीन लर्निंग और डेटा साइंस की दुनिया में, एक मौलिक कार्य है जो मूवी रिकमेंडेशन से लेकर इमेज कंप्रेशन तक हर चीज़ में दिखाई देता है: संख्याओं की एक बड़ी, जटिल तालिका को दो छोटी, सरल तालिकाओं में तोड़ना, जो आपस में गुणा होने पर मूल संख्या को फिर से बना सकें। इस प्रक्रिया को मैट्रिक्स फैक्टराइजेशन (matrix factorization) के रूप में जाना जाता है। कल्पना कीजिए कि दो सरल रेखाचित्रों को खोजकर एक विशाल, जटिल पेंटिंग का वर्णन करने का प्रयास करना, जिन्हें एक साथ रखने पर वही छवि उत्पन्न होती है। चुनौती यह है कि इन दो रेखाचित्रों को चुनने के अनगिनत तरीके हो सकते हैं। कुछ संयोजन गणितीय रूप से अव्यवस्थित होते हैं, जबकि अन्य उल्लेखनीय रूप से स्वच्छ और संतुलित होते हैं। वर्षों से, शोधकर्ताओं ने देखा है कि जब वे इन रेखाचित्रों को खोजने के लिए एक विशिष्ट, सरल विधि का उपयोग करते हैं, तो कंप्यूटर लगभग हमेशा सबसे स्वच्छ, सबसे संतुलित संस्करण चुनता है, भले ही उस विधि को स्पष्ट रूप से संतुलन की तलाश करने के लिए प्रोग्राम न किया गया हो। यह घटना, जहाँ एल्गोरिदम में सरलता के लिए एक छिपी हुई प्राथमिकता प्रतीत होती है, 'इम्प्लिसिट रेगुलराइजेशन' (implicit regularization) कहलाती है, और यह समझना कि वास्तव में ऐसा क्यों होता है, एक प्रमुख पहेली रही है।

भारतीय प्रौद्योगिकी संस्थान गुवाहाटी की अंजलि जायसवाल का एक नया अध्ययन इस पहेली का एक निश्चित उत्तर प्रदान करता है, जो एक विशिष्ट और व्यापक रूप से उपयोग की जाने वाली विधि, जिसे 'अल्टरनेटिंग ग्रेडिएंट डिसेंट' (alternating gradient descent) कहा जाता है, के लिए है। यह शोध एक ऐसी स्थिति पर केंद्रित है जहाँ डेटा पूरी तरह से दृश्यमान है और लक्ष्य संख्याओं का सबसे सरल संभव विभाजन खोजना है। लेखक सिद्ध करते हैं कि जब यह एल्गोरिदम एक बहुत ही छोटे, यादृच्छिक अनुमान (random guess) के साथ शुरू होता है, तो यह केवल कोई भी समाधान नहीं खोजता; बल्कि यह गणितीय निश्चितता के साथ उस एकमात्र, अद्वितीय समाधान की ओर अग्रसर होता है जो दोनों कारक तालिकाओं (factor tables) के कुल "आकार" को न्यूनतम करता है। क्षेत्र की भाषा में, इसका अर्थ है कि एल्गोरिदम स्वाभाविक रूप से उस गुणनखंड (factorization) का चयन करता है जो 'न्यूक्लियर नॉर्म' (nuclear norm) को न्यूनतम करता है, जो जटिलता का एक माप है और डेटा के सबसे संतुलित और कुशल प्रतिनिधित्व के अनुरूप है। अध्ययन इस बात की पुष्टि करता है कि यह व्यवहार एक भाग्यशाली दुर्घटना या प्रमाण की त्रुटि नहीं है, बल्कि छोटे और यादृच्छिक शुरुआती बिंदु के साथ एल्गोरिदम की कार्यप्रणाली का एक गारंटीकृत परिणाम है।

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

इस निष्कर्ष तक पहुँचने के लिए, लेखक ने एक कठोर गणितीय तर्क विकसित किया है जो एल्गोरिदम के व्यवहार को चरण-दरчаव ट्रैक करता है। यह प्रमाण दो मुख्य उपकरणों पर निर्भर करता है। पहला, एक "ल्यपुनोव फंक्शन" (Lyapunov function) एक वैश्विक ऊर्जा मीटर के रूप में कार्य करता है, जो यह दर्शाता है कि एल्गोरिदम द्वारा उठाए गए प्रत्येक कदम के साथ सिस्टम की समग्र त्रुटि लगातार कम होती है। दूसरा, और अधिक महत्वपूर्ण रूप से, लेखक एक "बैलेंस फंक्शन" (balance function) पेश करते हैं जो दो कारक तालिकाओं के आकार के बीच के अंतर को मापता है। विश्लेषण से पता चलता है कि एल्गोरिदम के तालिकाओं को अपडेट करने का विशिष्ट तरीका—एक के बाद एक, न कि एक साथ—एक अनूठा प्रभाव पैदा करता है। यह वैकल्पिक लय (alternating rhythm) तालिकाओं के आकार के बीच के अंतर को तेजी से कम करती है, जिससे वे पूर्ण समानता की ओर बढ़ती हैं। शोध दिखाता है कि यह संतुलन कार्य एक अनुमानित, रैखिक गति (linear speed) से होता है, जिसका अर्थ है कि सिस्टम प्रत्येक पुनरावृत्ति (iteration) के साथ एक निश्चित प्रतिशत से आदर्श समाधान के करीब पहुँच जाता है।

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

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

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