परिचय
गणितज्ञ एक अच्छी पहेली को पसंद करते हैं। जब आप इसे करने का सबसे कुशल तरीका खोजने की कोशिश करते हैं, तो मैट्रिक्स (संख्याओं की द्वि-आयामी तालिका) को गुणा करने के रूप में अमूर्त के रूप में कुछ भी एक खेल की तरह महसूस कर सकता है। यह रूबिक क्यूब को यथासंभव कुछ चालों में हल करने की कोशिश करने जैसा है - चुनौतीपूर्ण, लेकिन आकर्षक। रूबिक क्यूब को छोड़कर, प्रत्येक चरण में संभावित चालों की संख्या 18 है; मैट्रिक्स गुणा के लिए, अपेक्षाकृत सरल मामलों में भी, प्रत्येक चरण 10 से अधिक प्रस्तुत कर सकता है12 विकल्प.
पिछले 50 वर्षों में, शोधकर्ताओं ने कई तरह से इस समस्या का सामना किया है, सभी मानव अंतर्ज्ञान द्वारा सहायता प्राप्त कंप्यूटर खोजों पर आधारित हैं। पिछले महीने, आर्टिफिशियल इंटेलिजेंस कंपनी डीपमाइंड की एक टीम ने दिखाया कि समस्या को एक नई दिशा से कैसे निपटा जाए, एक में रिपोर्टिंग काग़ज़ in प्रकृति कि उन्होंने मैट्रिक्स गुणन के लिए नए तेज़ एल्गोरिदम खोजने के लिए एक न्यूरल नेटवर्क को सफलतापूर्वक प्रशिक्षित किया था। यह ऐसा था जैसे एआई को एक राक्षसी रूप से जटिल रूबिक क्यूब को हल करने के लिए एक अज्ञात रणनीति मिल गई हो।
"यह एक बहुत साफ परिणाम है," कहा जोश अलमन, कोलंबिया विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक। लेकिन उन्होंने और अन्य मैट्रिक्स गुणन विशेषज्ञों ने इस बात पर भी जोर दिया कि इस तरह की एआई सहायता मौजूदा तरीकों को बदलने के बजाय पूरक होगी - कम से कम निकट अवधि में। "यह किसी चीज़ के लिए अवधारणा के प्रमाण की तरह है जो एक सफलता बन सकती है," अलमन ने कहा। परिणाम शोधकर्ताओं को उनकी खोज में आसानी से मदद करेगा।
मानो बात को साबित करने के लिए, तीन दिन बाद प्रकृति पेपर निकला, ऑस्ट्रियाई शोधकर्ताओं की एक जोड़ी ने उदाहरण दिया कि कैसे नए और पुराने तरीके एक दूसरे के पूरक हो सकते हैं। उन्होंने एक पारंपरिक कंप्यूटर एडेड सर्च का इस्तेमाल किया आगे का सुधार तंत्रिका नेटवर्क द्वारा खोजे गए एल्गोरिदम में से एक।
परिणाम बताते हैं कि रूबिक क्यूब को हल करने की प्रक्रिया की तरह, बेहतर एल्गोरिदम का मार्ग ट्विस्ट और टर्न से भरा होगा।
मैट्रिसेस का गुणन
मैट्रिक्स गुणन सभी गणित में सबसे मौलिक और सर्वव्यापी संक्रियाओं में से एक है। के एक जोड़े को गुणा करना n-द्वारा-n मेट्रिसेस, प्रत्येक के साथ n2 तत्वों, आप गुणा करते हैं और इन तत्वों को विशेष संयोजनों में एक साथ जोड़कर उत्पाद बनाते हैं, एक तिहाई n-द्वारा-n आव्यूह। दो को गुणा करने का मानक नुस्खा n-द्वारा-n मैट्रिसेस की आवश्यकता है n3 गुणा संचालन, इसलिए 2-बाय -2 मैट्रिक्स, उदाहरण के लिए, आठ गुणा की आवश्यकता होती है।
हजारों पंक्तियों और स्तंभों वाले बड़े मैट्रिसेस के लिए, यह प्रक्रिया जल्दी ही बोझिल हो जाती है। लेकिन 1969 में, गणितज्ञ वोल्कर स्ट्रैसन एक प्रक्रिया की खोज की अधिक अतिरिक्त चरणों को शुरू करने की कीमत पर, आठ गुणन चरणों के बजाय सात का उपयोग करके 2-बाय -2 मैट्रिक्स की एक जोड़ी को गुणा करने के लिए।
यदि आप केवल 2-बाय -2 मैट्रिसेस की एक जोड़ी को गुणा करना चाहते हैं, तो स्ट्रैसेन का एल्गोरिथ्म अनावश्यक रूप से जटिल है। लेकिन उन्होंने महसूस किया कि यह बड़े मेट्रिसेस के लिए भी काम करेगा। ऐसा इसलिए है क्योंकि मैट्रिक्स के तत्व स्वयं मैट्रिसेस हो सकते हैं। उदाहरण के लिए, 20,000 पंक्तियों और 20,000 कॉलम वाले मैट्रिक्स को 2-बाय-2 मैट्रिक्स के रूप में पुन: कल्पना की जा सकती है, जिनके चार तत्व प्रत्येक 10,000-बाय-10,000 मैट्रिक्स हैं। इनमें से प्रत्येक मेट्रिसेस को चार 5,000-बाई-5,000 ब्लॉकों में विभाजित किया जा सकता है, और इसी तरह। स्ट्रैसन इस नेस्टेड पदानुक्रम के प्रत्येक स्तर पर 2-बाय -2 मैट्रिसेस को गुणा करने के लिए अपनी विधि लागू कर सकता है। जैसे-जैसे मैट्रिक्स का आकार बढ़ता है, कम गुणन से बचत बढ़ती है।
स्ट्रैसन की खोज ने मैट्रिक्स गुणा के लिए कुशल एल्गोरिदम की खोज की, जिसके बाद से दो अलग-अलग उपक्षेत्रों को प्रेरित किया गया। एक सिद्धांत के प्रश्न पर ध्यान केंद्रित करता है: यदि आप दो को गुणा करने की कल्पना करते हैं n-द्वारा-n मैट्रिसेस और चलो n अनंत की ओर दौड़ें, सबसे तेज़ संभव एल्गोरिथम पैमाने में गुणन चरणों की संख्या कैसे होती है n? वर्तमान रिकॉर्ड सर्वोत्तम स्केलिंग के लिए, n2.3728596, अलमन के अंतर्गत आता है और वर्जीनिया वासिलेवस्का विलियम्स, मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी में एक कंप्यूटर वैज्ञानिक। (हाल ही में अप्रकाशित प्रीप्रिंट एक नई तकनीक का उपयोग करते हुए एक छोटे से सुधार की सूचना दी।) लेकिन ये एल्गोरिदम विशुद्ध रूप से सैद्धांतिक रुचि के हैं, स्ट्रैसेन जैसे तरीकों पर केवल बेतुके बड़े मेट्रिसेस के लिए जीत हासिल करते हैं।
दूसरा उपक्षेत्र छोटे पैमाने पर सोचता है। स्ट्रैसन के काम के तुरंत बाद, इजरायली अमेरिकी कंप्यूटर वैज्ञानिक शमूएल विनोग्राद पता चला कि स्ट्रैसन एक सैद्धांतिक सीमा तक पहुँच गया था: सात से कम गुणन चरणों के साथ 2-बाय-2 मैट्रिक्स को गुणा करना संभव नहीं है। लेकिन अन्य सभी मैट्रिक्स आकारों के लिए, आवश्यक गुणन की न्यूनतम संख्या एक खुला प्रश्न है। और छोटे मेट्रिसेस के लिए तेज़ एल्गोरिदम का प्रभाव बहुत अधिक हो सकता है, क्योंकि इस तरह के एल्गोरिथ्म के बार-बार पुनरावृत्तियों से स्ट्रैसेन के एल्गोरिथ्म को हराया जा सकता है जब यथोचित आकार के मेट्रिसेस को गुणा किया जा रहा हो।
दुर्भाग्य से, संभावनाओं की सरासर संख्या बहुत बड़ी है। यहां तक कि 3-बाय -3 मैट्रिक्स के लिए, "संभावित एल्गोरिदम की संख्या ब्रह्मांड में परमाणुओं की संख्या से अधिक है," कहा अलहुसैन फावजी, एक डीपमाइंड शोधकर्ता और नए काम के नेताओं में से एक।
विकल्पों के इस चक्करदार मेनू का सामना करते हुए, शोधकर्ताओं ने मैट्रिक्स गुणा को पूरी तरह से अलग गणित समस्या की तरह दिखने में प्रगति की है - जो कि कंप्यूटर को संभालने में आसान है। एक विशिष्ट प्रकार की गणितीय वस्तु के रूप में दो आव्यूहों को गुणा करने के अमूर्त कार्य का प्रतिनिधित्व करना संभव है: संख्याओं की एक त्रि-आयामी सरणी जिसे टेन्सर कहा जाता है। इसके बाद शोधकर्ता इस टेंसर को "रैंक-1" टेंसर कहे जाने वाले प्रारंभिक घटकों के योग में विभाजित कर सकते हैं; इनमें से प्रत्येक संबंधित मैट्रिक्स गुणन एल्गोरिथ्म में एक अलग चरण का प्रतिनिधित्व करेगा। इसका मतलब है कि एक कुशल गुणन एल्गोरिथ्म की खोज एक टेंसर अपघटन में शब्दों की संख्या को कम करने के लिए होती है - जितनी कम शर्तें, उतने ही कम चरण शामिल होते हैं।
इस तरह शोधकर्ताओं ने नई खोज की है एल्गोरिदम कि गुणा करें n-द्वारा-n मैट्रिसेस मानक से कम का उपयोग कर रहे हैं n3 कई छोटे मैट्रिक्स आकारों के लिए गुणन चरण। लेकिन एल्गोरिदम जो न केवल मानक से बेहतर प्रदर्शन करते हैं, बल्कि छोटे मेट्रिसेस के लिए स्ट्रैसेन के एल्गोरिदम भी अब तक पहुंच से बाहर हैं।
खेल शुरू
डीपमाइंड टीम ने टेंसर अपघटन को एकल-खिलाड़ी खेल में बदलकर समस्या का समाधान किया। उन्होंने एक गहन शिक्षण एल्गोरिथम के साथ शुरुआत की, जो 2016 में अल्फागो - एक और डीपमाइंड एआई से उतरा बोर्ड गेम गो खेलना सीखा शीर्ष मानव खिलाड़ियों को हराने के लिए पर्याप्त है।
सभी गहरे शिक्षण एल्गोरिदम तंत्रिका नेटवर्क के आसपास बनाए गए हैं: कृत्रिम न्यूरॉन्स के जाल परतों में क्रमबद्ध होते हैं, कनेक्शन के साथ जो ताकत में भिन्न हो सकते हैं यह दर्शाता है कि प्रत्येक न्यूरॉन अगली परत में उन पर कितना प्रभाव डालता है। इन कनेक्शनों की ताकत को एक प्रशिक्षण प्रक्रिया के कई पुनरावृत्तियों में बदल दिया जाता है, जिसके दौरान तंत्रिका नेटवर्क प्राप्त होने वाले प्रत्येक इनपुट को एक आउटपुट में बदलना सीखता है जो एल्गोरिथ्म को अपने समग्र लक्ष्य को पूरा करने में मदद करता है।
डीपमाइंड के नए एल्गोरिदम में, जिसे अल्फाटेन्सर करार दिया गया है, इनपुट एक वैध मैट्रिक्स गुणन योजना के रास्ते में कदमों का प्रतिनिधित्व करते हैं। तंत्रिका नेटवर्क का पहला इनपुट मूल मैट्रिक्स गुणन टेंसर है, और इसका आउटपुट रैंक -1 टेंसर है जिसे अल्फाटेन्सर ने अपनी पहली चाल के लिए चुना है। एल्गोरिथ्म इस रैंक -1 टेंसर को प्रारंभिक इनपुट से घटाता है, एक अपडेटेड टेंसर प्रदान करता है जिसे नए इनपुट के रूप में नेटवर्क में वापस फीड किया जाता है। प्रक्रिया तब तक दोहराती है जब तक कि शुरुआती टेन्सर में प्रत्येक तत्व को शून्य तक कम नहीं कर दिया जाता है, जिसका अर्थ है कि बाहर निकालने के लिए रैंक-1 टेंसर नहीं हैं।
उस बिंदु पर, तंत्रिका नेटवर्क ने एक वैध टेन्सर अपघटन की खोज की है, क्योंकि यह गणितीय रूप से गारंटी है कि सभी रैंक-1 टेंसरों का योग शुरुआती टेन्सर के बराबर है। और वहां पहुंचने के लिए उठाए गए कदमों को संबंधित मैट्रिक्स गुणा एल्गोरिदम के चरणों में वापस अनुवादित किया जा सकता है।
यहाँ खेल है: AlphaTensor रैंक -1 घटकों के एक सेट के लिए बार-बार एक टेंसर को विघटित करता है। हर बार, AlphaTensor को पुरस्कृत किया जाता है यदि वह चरणों की संख्या को कम करने का तरीका ढूंढता है। लेकिन जीत के लिए शॉर्टकट बिल्कुल भी सहज नहीं हैं, जैसे कि कभी-कभी आपको पूरी तरह से हल करने से पहले रुबिक के घन पर एक पूरी तरह से आदेशित चेहरे को खंगालना पड़ता है।
टीम के पास अब एक एल्गोरिदम था जो सैद्धांतिक रूप से उनकी समस्या का समाधान कर सकता था। उन्हें बस इसे पहले प्रशिक्षित करना था।
नए रास्ते
सभी तंत्रिका नेटवर्क की तरह, अल्फाटेन्सर को प्रशिक्षित करने के लिए बहुत अधिक डेटा की आवश्यकता होती है, लेकिन टेंसर अपघटन एक कुख्यात कठिन समस्या है। कुशल अपघटन के कुछ उदाहरण थे जो शोधकर्ता नेटवर्क को खिला सकते थे। इसके बजाय, उन्होंने एल्गोरिथ्म को बहुत आसान उलटा समस्या पर प्रशिक्षण देकर आरंभ करने में मदद की: बेतरतीब ढंग से उत्पन्न रैंक -1 टेंसरों का एक गुच्छा जोड़ना।
"वे कठिन समस्या के लिए अधिक डेटा का उत्पादन करने के लिए आसान समस्या का उपयोग कर रहे हैं," कहा माइकल लिटमैन, ब्राउन यूनिवर्सिटी में एक कंप्यूटर वैज्ञानिक। इस पिछड़े प्रशिक्षण प्रक्रिया को सुदृढीकरण सीखने के साथ जोड़कर, जिसमें अल्फाटेन्सर ने अपने स्वयं के प्रशिक्षण डेटा को उत्पन्न किया क्योंकि यह कुशल अपघटन की तलाश में भूल गया था, अपने आप में प्रशिक्षण पद्धति की तुलना में बहुत बेहतर काम किया।
डीपमाइंड टीम ने 12-बाय -12 तक मेट्रिसेस के गुणन का प्रतिनिधित्व करने वाले टेन्सर को विघटित करने के लिए अल्फाटेन्सर को प्रशिक्षित किया। इसने साधारण वास्तविक संख्याओं के मैट्रिक्स को गुणा करने के लिए तेज़ एल्गोरिदम की मांग की और मॉड्यूलो 2 अंकगणितीय के रूप में जाने वाली अधिक विवश सेटिंग के लिए विशिष्ट एल्गोरिदम भी। (यह केवल दो संख्याओं पर आधारित गणित है, इसलिए मैट्रिक्स तत्व केवल 0 या 1, और 1 + 1 = 0 हो सकते हैं।) शोधकर्ता अक्सर इस अधिक प्रतिबंधित लेकिन फिर भी विशाल स्थान से शुरू करते हैं, इस उम्मीद में कि यहां खोजे गए एल्गोरिदम को अनुकूलित किया जा सकता है वास्तविक संख्याओं के मैट्रिक्स पर काम करें।
प्रशिक्षण के बाद, अल्फाटेंसर ने मिनटों के भीतर स्ट्रैसेन के एल्गोरिथ्म को फिर से खोज लिया। इसके बाद इसने प्रत्येक मैट्रिक्स आकार के लिए हजारों नए तेज एल्गोरिदम की खोज की। ये सबसे प्रसिद्ध एल्गोरिदम से अलग थे लेकिन इनमें गुणन चरणों की संख्या समान थी।
कुछ मामलों में, AlphaTensor ने मौजूदा रिकॉर्ड को भी तोड़ दिया। इसकी सबसे आश्चर्यजनक खोज मॉडुलो 2 अंकगणित में हुई, जहां इसने 4 गुणन चरणों में 4-बाय -47 मैट्रिसेस को गुणा करने के लिए एक नया एल्गोरिथ्म पाया, स्ट्रैसेन के एल्गोरिथ्म के दो पुनरावृत्तियों के लिए आवश्यक 49 चरणों में सुधार। इसने 5-बाय-5 मॉड्यूलो 2 मैट्रिसेस के लिए सबसे प्रसिद्ध एल्गोरिदम को भी हरा दिया, 98 से 96 के पिछले रिकॉर्ड से आवश्यक गुणन की संख्या को कम कर दिया। (लेकिन यह नया रिकॉर्ड अभी भी उन 91 चरणों से पीछे है जिन्हें हराने की आवश्यकता होगी स्ट्रैसेन का एल्गोरिदम 5-बाय -5 मैट्रिसेस का उपयोग करता है।)
नए हाई-प्रोफाइल परिणाम ने बहुत उत्साह पैदा किया कुछ शोधकर्ताओं यथास्थिति पर एआई-आधारित सुधार पर ढेर सारी प्रशंसा। लेकिन मैट्रिक्स गुणन समुदाय में हर कोई इतना प्रभावित नहीं था। वासिलेव्स्का विलियम्स ने कहा, "मुझे ऐसा लगा जैसे यह थोड़ा अधिक हो गया था।" "यह एक और उपकरण है। ऐसा नहीं है, 'ओह, कंप्यूटर इंसानों को हरा देते हैं,' आप जानते हैं?
शोधकर्ताओं ने इस बात पर भी जोर दिया कि रिकॉर्ड-ब्रेकिंग 4-बाय-4 एल्गोरिथम के तत्काल अनुप्रयोग सीमित होंगे: यह न केवल मॉडुलो 2 अंकगणित में मान्य है, बल्कि वास्तविक जीवन में गति के अलावा महत्वपूर्ण विचार भी हैं।
फावजी ने माना कि वास्तव में, यह तो बस शुरुआत है। "सुधार और अनुसंधान के लिए बहुत जगह है, और यह एक अच्छी बात है," उन्होंने कहा।
एक फाइनल ट्विस्ट
अच्छी तरह से स्थापित कंप्यूटर खोज विधियों की तुलना में AlphaTensor की सबसे बड़ी ताकत भी इसकी सबसे बड़ी कमजोरी है: यह मानव अंतर्ज्ञान द्वारा बाधित नहीं है कि अच्छे एल्गोरिदम कैसा दिखते हैं, इसलिए यह अपने विकल्पों की व्याख्या नहीं कर सकता है। इससे शोधकर्ताओं के लिए इसकी उपलब्धियों से सीखना मुश्किल हो जाता है।
लेकिन यह उतना बड़ा नुकसान नहीं हो सकता जितना लगता है। AlphaTensor परिणाम के कुछ दिनों बाद, गणितज्ञ मैनुअल कौएर्स और उनके स्नातक छात्र जैकब मूसबाउर, ऑस्ट्रिया में जोहान्स केपलर यूनिवर्सिटी लिंज़ दोनों ने एक और कदम आगे बढ़ने की सूचना दी।
परिचय
जब डीपमाइंड पेपर सामने आया, कौएर्स और मूसबाउर एक पारंपरिक कंप्यूटर-एडेड खोज का उपयोग करके नए गुणन एल्गोरिदम की खोज करने की प्रक्रिया में थे। लेकिन ऐसी अधिकांश खोजों के विपरीत, जो एक नए मार्गदर्शक सिद्धांत के साथ नए सिरे से शुरू होती हैं, उनकी विधि मौजूदा एल्गोरिथ्म को बार-बार ट्वीक करके काम करती है, इससे अधिक गुणन बचत को निचोड़ने की उम्मीद में। शुरुआती बिंदु के रूप में 5-बाय-5 मॉड्यूलो 2 मैट्रिसेस के लिए अल्फाटेन्सर के एल्गोरिथ्म को लेते हुए, उन्हें यह जानकर आश्चर्य हुआ कि उनकी विधि ने गणना के कुछ ही सेकंड के बाद गुणन चरणों की संख्या को 96 से घटाकर 95 कर दिया।
AlphaTensor ने उन्हें अप्रत्यक्ष रूप से एक और सुधार करने में भी मदद की। इससे पहले, काउर्स और मूसबाउर ने 4-बाई-4 मैट्रिसेस के स्थान का पता लगाने की जहमत नहीं उठाई थी, यह मानते हुए कि स्ट्रैसन के एल्गोरिथ्म के दो पुनरावृत्तियों को हरा पाना संभव नहीं होगा। AlphaTensor परिणाम ने उन्हें पुनर्विचार करने के लिए प्रेरित किया, और स्क्रैच से शुरू होने वाले गणना समय के एक सप्ताह के बाद, उनकी विधि ने एक और 47-चरणीय एल्गोरिथम बदल दिया, जो कि AlphaTensor द्वारा खोजे गए एक से संबंधित नहीं था। "अगर किसी ने हमें बताया था कि 4-बाय -4 के लिए कुछ खोजने के लिए है, तो हम पहले ऐसा कर सकते थे," कौएर्स ने कहा। "लेकिन ठीक है, ठीक है, यह इस तरह काम करता है।"
लिटमैन इस तरह के और अधिक आश्चर्य की अपेक्षा करता है, स्थिति की तुलना पहली बार एक धावक ने चार मिनट के भीतर एक मील की दूरी पर पूरी की, एक ऐसा कारनामा जिसे व्यापक रूप से असंभव माना जाता था। "लोग ऐसे थे, 'ओह, रुको, हम यह कर सकते हैं,' और अब बहुत से लोग इसे कर सकते हैं," उन्होंने कहा।
भविष्य की ओर देखते हुए, फावजी को गणितीय और कम्प्यूटेशनल कार्यों की एक विस्तृत श्रृंखला से निपटने के लिए अल्फाटेंसर को सामान्य बनाने की उम्मीद है, जैसे कि इसके पूर्वज अल्फा गो ने अंततः अन्य खेलों में प्रवेश किया।
काउर्स इसे नए एल्गोरिदम की खोज के लिए मशीन लर्निंग के अनुप्रयोग के लिए सही लिटमस टेस्ट के रूप में देखते हैं। वह बताते हैं कि तेजी से मैट्रिक्स गुणन एल्गोरिदम की खोज एक मिश्रित समस्या है, जिसके लिए मानव सहायता के साथ या उसके बिना कंप्यूटर की खोज अच्छी तरह से अनुकूल है। लेकिन सभी गणितीय समस्याओं को ठीक करना इतना आसान नहीं है। यदि मशीन लर्निंग गुणात्मक रूप से नए एल्गोरिथम विचार की खोज कर सकता है, तो उन्होंने कहा, "यह गेम चेंजर होगा।"
