🤖 machine learning

Transformer Circuits Can Realize Clustering Algorithms

यह शोध पत्र यह प्रदर्शित करता है कि एक ट्रांसफॉर्मर आर्किटेक्चर, जिसे $k$ -means ट्रांसफॉर्मर कहा गया है, मानक सर्किट तंत्रों का उपयोग करके $k$ -means क्लस्टरिंग के लिए लॉयड के एल्गोरिदम (Lloyd's algorithm) को सैद्धांतिक और अनुभवजन्य रूप से लागू कर सकता है, और साथ ही पारंपरिक एल्गोरिदम के प्रदर्शन से आगे बढ़ने और वास्तुशिल्प संशोधनों के माध्यम से विविध क्लस्टरिंग वेरिएंट्स में स्वाभाविक रूप से सामान्यीकरण करने में भी सक्षम है।

मूल लेखक: Kenneth L. Clarkson, Lior Horesh, Takuya Ito, Charlotte Park, Parikshit Ram

प्रकाशित 2026-08-11

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Kenneth L. Clarkson, Lior Horesh, Takuya Ito, Charlotte Park, Parikshit Ram

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

जिस शोध पत्र का आप अन्वेषण करने जा रहे हैं, वह इस रहस्य की गहराई में उतरता है और k-means क्लस्टरिंग नामक एक क्लासिक समस्या को हल करता है। इसे कंचों को छाँटने के खेल के रूप में सोचें। कल्पना कीजिए कि आपके पास अलग-अलग रंगों और आकारों के कंचों का एक विशाल थैला है, जो सब आपस में मिले हुए हैं। आपका लक्ष्य उन्हें $k$ समूहों (मान लीजिए 5 समूह) में छाँटना है ताकि एक ही समूह के कंचे आपस में यथासंभव समान दिखें। दशकों से, इसे करने का मानक तरीका लॉयड एल्गोरिदम (Lloyd's algorithm) नामक एक एल्गोरिदम रहा है। यह एक बहुत ही विशिष्ट, कठोर रेसिपी है: 5 यादृच्छिक (रैंडम) स्थान चुनें जो "केंद्र" होंगे, फिर हर कंचे को निकटतम केंद्र की ओर ले जाएं, फिर केंद्रों को उनके नए कंचों के औसत स्थान पर ले जाएं, और तब तक दोहराते रहें जब तक कि समूह बदलना बंद न हो जाए। यह एक सटीक, गणितीय नृत्य है, लेकिन एक सीखने वाली मशीन को इसे बिल्कुल सटीक रूप से करना सिखाना कठिन है क्योंकि मशीन आमतौर पर सख्त नियमों का पालन करने के बजाय "अनुमान" लगाना पसंद करती है।

इस शोध पत्र के शोधकर्ताओं ने, जो IBM रिसर्च और MIT में कार्यरत हैं, एक साहसी प्रश्न पूछा: क्या हम एक ऐसा ट्रांसफॉर्मर बना सकते हैं जो केवल कंचों को छाँटने का अनुमान न लगाए, बल्कि वास्तव में लॉयड एल्गोरिदम के सटीक चरणों का पालन करे? और इससे भी अधिक रोमांचक बात यह है कि क्या हम इसे मूल रेसिपी से भी बेहतर करने के लिए प्रशिक्षित कर सकते हैं?

उन्होंने एक विशेष प्रकार का ट्रांसफॉर्मर बनाया जिसे वे "k-means ट्रांसफॉर्मर" कहते हैं। मशीन को परीक्षण और त्रुटि (ट्रायल एंड एरर) के माध्यम से छाँटना सीखने देने के बजाय, उन्होंने मशीन के आंतरिक पुर्जों (इसके अटेंशन मैकेनिज्म और कनेक्शन) को लॉयड एल्गोरिदम के गणित की भौतिक रूप से नकल करने के लिए डिज़ाइन किया। उन्होंने गणितीय रूप से सिद्ध किया कि यदि आप इस मशीन के वेट्स (weights) को सही ढंग से सेट करते हैं, तो इस ट्रांसफॉर्मर का एक लेयर (परत) छाँटने के नृत्य का ठीक एक चरण पूरा करता है। यदि आप दस लेयर्स को एक के ऊपर एक रखते हैं, तो यह क्लासिक एल्गोरिदम की सटीक नकल करते हुए दस चरण पूरे करता है। यह एक ऐसे रोबोट को बनाने जैसा है जो केवल चलना नहीं सीखता; बल्कि आप इसे ऐसे पैरों के साथ बनाते हैं जो मानव के ठीक समान कदम उठाने के लिए यांत्रिक रूप से लॉक हैं।

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

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

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

तकनीकी सारांश: ट्रांसफॉर्मर सर्किट क्लस्टरिंग एल्गोरिदम को साकार कर सकते हैं

समस्या विवरण

क्लस्टरिंग, विशेष रूप से $k$ -means क्लस्टरिंग, कंप्यूटर विज्ञान में एक मौलिक कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्या है, फिर भी यह ज्ञात है कि यह NP-hard है। जबकि डीप लर्निंग आर्किटेक्चर, विशेष रूप से ट्रांसफॉर्मर, कच्चे डेटा से पदानुक्रमित (hierarchical) विशेषताओं को सीखने में उत्कृष्ट हैं, यह स्पष्ट नहीं है कि वे सटीक, असतत (discrete) एल्गोरिदम गणनाओं को किस हद तक लागू कर सकते हैं। यह शोध पत्र शास्त्रीय असतत क्लस्टरिंग एल्गोरिदम और आधुनिक न्यूरल आर्किटेक्चर के बीच के अंतर को संबोधित करता है, जिसमें यह जांचा गया है कि क्या ट्रांसफॉर्मर सर्किट तंत्र $k$ -means क्लस्टरिंग के लिए लॉयड के एल्गोरिदम (Lloyd's algorithm) के पुनरावृत्ति चरणों को सटीक रूप से स्थापित कर सकते हैं।

कार्यप्रणाली

$k$ -means ट्रांसफॉर्मर आर्किटेक्चर

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

इनपुट एम्बेडिंग्स (Input Embeddings):
- एनकोडर: $n$ डेटा बिंदुओं $X \in \mathbb{R}^{d \times n}$ के सेट को प्रोसेस करता है। प्रत्येक बिंदु $x_i$ को $(d+k)$ -आयामी वेक्टर $[x_i^\top, y_i^\top]^\top$ में एम्बेड किया जाता है, जहाँ $y_i \in \{0,1\}^k$ एक वन-हॉट क्लस्टर असाइनमेंट (प्रारंभिक रूप से शून्य) को दर्शाता है।
- डिकोडर: $k$ क्लस्टर सेंटर्स $C \in \mathbb{R}^{d \times k}$ को प्रोसेस करता है। प्रत्येक सेंटर $c_j$ को $(d+k)$ -आयामी वेक्टर $[c_j^\top, e_j^\top]^\top$ में एम्बेड किया जाता है, जहाँ $e_j$ $j$ -वाँ विशेषता वेक्टर (वन-हॉट इंडेक्स) है।
अटेंशन मैकेनिज्म (Attention Mechanisms):
- यूक्लिडियन अटेंशन (Euclidean Attention): एनकोडर (पॉइंट असाइनमेंट) अपडेट के लिए, पेपर नकारात्मक वर्ग यूक्लिडियन दूरी (negative squared Euclidean distances) पर आधारित एक लिमिटिंग सॉफ्ट-मैक्स अटेंशन का उपयोग करता है: $A_{ji} = -\|Kz_j - Qx_i\|^2$ । जैसे-जैसे तापमान पैरामीटर $\gamma \to \infty$ होता है, यह एक arg-max ऑपरेशन का अनुमान लगाता है, जिससे पॉइंट्स को निकटतम सेंटर को असाइन किया जाता है।
- डॉट-प्रोडक्ट अटेंशन (Dot-Product Attention): डिकोडर (सेंटर अपडेट) चरणों के लिए, असाइन किए गए पॉइंट्स के माध्य (mean) की गणना करने के लिए मानक डॉट-प्रोडक्ट अटेंशन का उपयोग किया जाता है।
- रेसिडुअल कनेक्शंस (Residual Connections): क्रॉस-अटेंशन अपडेट से पहले वर्तमान असाइनमेंट या सेंटर्स को शून्य पर रीसेट करने के लिए उपयोग किया जाता है, जो प्रभावी रूप से लॉयड के एल्गोरिदम के "असाइनमेंट" और "अपडेट" चरणों को एक सिंगल फॉरवर्ड पास में लागू करता है।
सैद्धांतिक निर्माण (Theoretical Construction):
- थ्योरम 2.1: यह सिद्ध करता है कि विशिष्ट निश्चित वेट्स (इक्वेशन 5 में परिभाषित) और लिमिटिंग सॉफ्ट-मैक्स अटेंशन ( $\gamma \to \infty$ ) के साथ एक $T$ -लेयर ट्रांसफॉर्मर सटीक रूप से लॉयड के एल्गोरिदम के $T$ इटरेशन को निष्पादित करता है। मॉडल का आकार $O(d+k)$ है, जो इनपुट आकार $O(d(n+k))$ से छोटा है।
- थ्योरम 2.2: यह प्रदर्शित करता है कि एक मानक डॉट-प्रोडक्ट अटेंशन ट्रांसफॉर्मर भी लॉयड के एल्गोरिदम को सटीक रूप से निष्पादित कर सकता है यदि टोकन एम्बेडिंग्स को स्क्वेर्ड नॉर्म्स के साथ ऑगमेंट किया जाए और सेंटर्स को अपडेट करने के लिए एक फीड-फॉरवर्ड नेटवर्क (FFN) जिसमें रेक्टिफाइड क्वाड्रेटिक एक्टिवेशन हो, का उपयोग किया जाए।

लर्निंग एक्सपेमेंट्स (Learning Experiments)

लेखक एक सिंगल-लेयर ट्रांसफॉर्मर को क्लस्टरिंग कार्यों के वितरण (गाऊसी मिश्रण से नमूने) पर प्रशिक्षित करते हैं, जो $k$ -means ऑब्जेक्टिव के स्मूद्थ ऊपरी बाउंड (smoothed upper bound) को कम करता है। प्रशिक्षण में सैद्धांतिक लिमिटिंग केस के बजाय मानक सॉफ्ट-मैक्स ( $\gamma=1$ ) का उपयोग किया जाता है। de प्रशिक्षित मॉडल का मूल्यांकन अनदेखे कार्यों पर किया जाता है, जिसमें सैंपल साइज, डाइमेंशनलिटी और इनिशियलाइजेशन रणनीतियों (रैंडम बनाम $k$ -means++) को बदला जाता है।

मुख्य योगदान

लॉयड के एल्गोरिदम का सटीक कार्यान्वयन: पेपर एक सैद्धांतिक प्रमाण और अनुभवजन्य सत्यापन प्रदान करता है कि एक विशिष्ट पैरामीटर चयन वाला ट्रांसफॉर्मर आर्किटेक्चर $k$ -means क्लस्टरिंग के लिए लॉयड के एल्गोरिदम को सटीक रूप से लागू करता है। यह असतत एल्गोरिदम चरणों और निरंतर न्यूरल सर्किट तंत्रों के बीच के अंतर को पाटता है।
लर्नेबल क्लस्टरिंग एल्गोरिदम: क्लस्टरिंग कार्यों के वितरण पर प्रशिक्षित होने पर, ट्रांसफॉर्मर आर्किटेक्चर एक सामान्यीकरण योग्य (generalizable) क्लस्टरिंग एल्गोरिदम सीखता है जो मानक सॉफ्ट-मैक्स अटेंशन ( $\gamma=1$ ) का उपयोग करने के बावजूद, क्लस्टरिंग गुणवत्ता (कम $k$ -means ऑब्जेक्टिव) के मामले में मानक लॉयड एल्गोरिदम से बेहतर प्रदर्शन करता है।
विविध एल्गोरिदम के लिए आर्किटेक्चरल वेरिएंट्स: विशिष्ट ट्रांसफॉर्मर सर्किट तंत्रों (जैसे अटेंशन प्रकार, नॉर्मलाइजेशन, एक्टिवेशन फंक्शन) को संशोधित करके, लेखक विभिन्न मौजूदा और नवीन क्लस्टरिंग एल्गोरिदम को स्थापित करना दिखाते हैं:
- सॉफ्ट $k$ -मीन्स (Soft $k$ -means): लिमिटिंग सॉफ्ट-मैक्स को मानक सॉफ्ट-मैक्स और लीनियर अटेंशन के साथ बदलकर प्राप्त किया गया।
- स्फेरिकल $k$ -मीन्स (Spherical $k$ -means): डॉट-प्रोडक्ट अटेंशन और टोकन-वाइज नॉर्मलाइजेशन (जैसे RMSNorm) का उपयोग करके प्राप्त किया गया।
- ट्रिम्ड $k$ -मीन्स (Trimmed $k$ -means): सॉफ्ट-मैक्स को नॉर्म-मैक्स अटेंशन (रेगुलराइज्ड arg-max) से बदलकर प्राप्त किया गया।
- रोबस्ट $k$ -मीन्स (Robust $k$ -means): स्पार्स सॉफ्ट-मैक्स अटेंशन का उपयोग करके प्राप्त किया गया।
- रैंडमाइज्ड $k$ -मेडॉइड्स (Randomized $k$ -medoids): वास्तविक डेटा पॉइंट्स को सेंटर्स के रूप में चुनने के लिए गम्बल-सॉफ्टमैक्स (Gumbel-softmax) अटेंशन का उपयोग करके प्राप्त किया गया।

परिणाम

सैद्धांतिक समानता: संख्यात्मक सत्यापन पुष्टि करता है कि एक बड़े लेकिन परिमित तापमान ( $\gamma = 10^4$ ) के साथ, ट्रांसफॉर्मर का क्लस्टर सेंटर्स और फाइनल असाइनमेंट का प्रक्षेपवक्र (trajectory) 10 इटरेशन में लॉयड के एल्गोरिदम से सटीक रूप से मेल खाता है।
प्रदर्शन श्रेष्ठता: लर्निंग एक्सपेमेंट्स में, प्रशिक्षित ट्रांसफॉर्मर औसत लॉग- $k$ -मीन्स ऑब्जेक्टिव $\sim 5.0$ तक अभिसरण (converge) करता है, जो समान कार्यों पर लॉयड के एल्गोरिदम ( $\sim 5.25$ ) से बेहतर प्रदर्शन करता है। यह सुधार तब भी बना रहता है जब ट्रांसफॉर्मर का परीक्षण अलग-अलग सैंपल साइज और इनिशियलाइजेशन स्कीम्स (जैसे $k$ -means++) के साथ किया जाता है, जबकि इसे केवल रैंडम इनिशियलाइजेशन पर प्रशिक्षित किया गया था।
एम्बेडिंग डाइमेंशनलिटी: एब्लेशन स्टडीज दिखाती हैं कि टोकन एम्बेडिंग्स में अतिरिक्त $k$ डाइमेंशन्स (कुल $d+k$ ) महत्वपूर्ण हैं। केवल $d$ डाइमेंशन वाला मॉडल लॉयड के प्रदर्शन से मेल खाने में विफल रहता है, और उच्च ऑब्जेक्टिव ( $\sim 5.35$ ) पर अभिसरण करता है।
वेट एनालिसिस: सीखे गए वेट्स सैद्धांतिक निर्माणों के साथ संरचनात्मक समानताएं प्रदर्शित करते हैं (जैसे $Q^\top K$ मैट्रिसेस में डोमिनेंट डायगोनल फॉर्म्स) लेकिन वे विशिष्ट अंतर भी दिखाते हैं, जो यह सुझाव देते हैं कि सीखा गया एल्गोरिदम मानक लॉयड से कुछ विशिष्ट तरीकों में (जैसे सेंटर्स अपडेट करने के तरीके में) भिन्न है।

महत्व और दावे

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

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

लेखक सीमाओं का उल्लेख करते हैं, विशेष रूप से उनके सैद्धांतिक परिणाम लिमिटिंग सॉफ्ट-मैक्स अटेंशन पर निर्भर करते हैं जो बैकप्रोपैगेट करने में कठिन है, हालांकि वे दिखाते हैं कि मॉडल मानक सॉफ्ट-मैक्स के साथ भी काम करता है। वे यह भी कहते हैं कि जबकि उनका मॉडल बड़े $n$ (पॉइंट्स की संख्या) के लिए सामान्यीकरण (generalize) करता है, यह वर्तमान में बड़े $k$ (क्लस्टर्स की संख्या) के लिए सामान्यीकरण का समर्थन नहीं करता है यदि इसे एक निश्चित $k$ के लिए प्रशिक्षित किया गया हो। यह कार्य शास्त्रीय विधियों के न्यूरल कार्यान्वयन के लिए आगे के अन्वेषण के आधार के रूप में खुद को स्थापित करता है।