TriSearch: Learning to Optimize Triangulations via Bistellar Flips

तकनीकी सारांश: TriSearch

समस्या का निरूपण (Problem Formulation)

यह शोध पत्र एक $d$-आयामी पॉलीटोप $P$ के त्रिकोणीकरण (triangulations) के अनुकूलन (optimization) को संबोधित करता है। एक त्रिकोणीकरण $P$ को $d$-सिम्प्लेक्स में विभाजित करता है जो केवल साझा फलकों (shared faces) पर मिलते हैं। सभी त्रिकोणीकरणों का स्थान, $\mathcal{T}(P)$, चरघातांकी (exponentially) रूप से विशाल है, जो $2^{O(|V(P)|\lceil d/2 \rceil)}$ के रूप में बढ़ता है। इस स्थान पर कई स्वाभाविक उद्देश्य, जैसे कि सिम्प्लेक्स की संख्या को कम करना या कुल किनारे की लंबाई को कम करना, $d \geq 2$ के लिए NP-hard हैं।

खोज स्थान (search space) एक फ्लिप ग्राफ $\mathcal{G}(P)$ के रूप में संरचित है, जहाँ नोड्स त्रिकोणीकरण हैं और किनारे बिस्टेलर फ्लिप्स (bistellar flips) के अनुरूप हैं। एक बिस्टेलर फ्लिप एक स्थानीय चाल (local move) है जो एक सर्किट (शीर्षों का एक न्यूनतम रैखिक रूप से आश्रित सेट) द्वारा समर्थित एक वास्तविक स्थानीय उप-त्रिकोणीकरण (local subtriangulation) को उसी शीर्ष सेट के वैकल्पिक त्रिकोणीकरण के साथ बदल देता है। चुनौती इस ग्राफ में नेविगेट करने में निहित है: व्यवहार्य क्रियाओं (flippable circuits) का सेट स्थिति-निर्भर है और प्रत्येक चाल के बाद बदल जाता है, जिससे मानक न्यूरल कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन कठिन हो जाता है क्योंकि एक्शन स्पेस स्थिर नहीं है।

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

लेखक TriSearch प्रस्तावित करते हैं, जो एक सुदृढीकरण शिक्षण (reinforcement learning - RL) ढांचा है जो त्रिकोणीकरण अनुकूलन को एक अंतर्निहित (implicit) फ्लिप ग्राफ पर खोज के रूप में मानता है।

1. समस्या का पुनर्रूपण (Problem Reformulation)

समस्या को एक मार्कोव निर्णय प्रक्रिया (MDP) के रूप में मॉडल किया गया है:

• अवस्था (State): एक पूर्ण त्रिकोणीकरण $\Delta$।
• क्रिया (Action): एक वर्तमान में व्यवहार्य बिस्टेलर फ्लिप $Z \in \mathcal{F}(\Delta)$।
• पुरस्कार (Reward): फ्लिप द्वारा प्रेरित उद्देश्य फलन $f$ में सुधार ($R = f(\Delta) - f(\text{Flip}(\Delta; Z))$)।
• क्षितिज (Horizon): प्रति एपिसोड फ्लिप्स की एक निश्चित संख्या।

महत्वपूर्ण रूप से, यह ढांचा नीति (policy) से ज्यामितीय वैधता सीखने के लिए नहीं कहता है। इसके बजाय, एक ज्यामितीय रूटीन (TOPCOM पर आधारित) सभी वैध स्थानीय चालों (flippable circuits) को सूचीबद्ध करता है। सीखी गई नीति की भूमिका इन वैध चालों को रैंक करना है ताकि यह पहचान की जा सके कि कौन सी चाल दीर्घकालिक अनुकूलन की ओर ले जाती है।

2. सर्किट-समर्थित क्रिया प्रतिनिधित्व (Circuit-Supported Action Representation)

परिवर्तनीय और स्थिति-निर्भर एक्शन स्पेस को संभालने के लिए, TriSearch एक नवीन क्रिया प्रतिनिधित्व पेश करता है। प्रत्येक व्यवहार्य क्रिया को निम्नलिखित द्वारा एनकोड किया जाता है:

1. समर्थित सर्किट $Z$।
2. वर्तमान त्रिकोणीकरण में निहित वास्तविक स्थानीय उप-त्रिकोणीकरण $\Delta^+(Z)$।

यह प्रतिनिधित्व प्रमाणिकता के प्रमाण (certificate of admissibility) और विशिष्ट स्थानीय ज्यामिति दोनों को एनकोड करता है जिसे बदला जा रहा है। क्योंकि सर्किट आंतरिक रूप से परिभाषित होते हैं, यह प्रतिनिधित्व आयाम-अज्ञेय (dimension-agnostic) है और विभिन्न फ्लिप अरिटी (flip arities) का समर्थन करता है।

3. न्यूरल आर्किटेक्चर

नीति एक दो-चरणीय आर्किटेक्चर का उपयोग करती है (चित्र 2):

• ग्लोबल एनकोडर: एक इक्विवेरिएंट ग्राफ न्यूरल नेटवर्क (EGNN) त्रिकोणीकरण ग्राफ $G(\Delta)$ के 1-कंकाल (1-skeleton) को प्रोसेस करता है। यह वर्टेक्स-स्तरीय एम्बेडिंग $h^*$ उत्पन्न करता है जो कठोर गति समरूपताओं (rigid motion symmetries) का सम्मान करते हुए वैश्विक ज्यामितीय संदर्भ को कैप्चर करता है।
• एक्टर (एक्शन स्कोरर): एक्टर वर्टेक्स एम्बेडिंग को मैक्सिमल $d$-सिम्प्लेक्स के स्तर तक ले जाता है। यह त्रिकोणीकरण के ड्यूल ग्राफ (जहाँ नोड्स सिम्प्लेक्स हैं) पर सिम्पलिसियल न्यूरल नेटवर्क (SNN) परतों का उपयोग करके कार्य करता है। प्रत्येक व्यवहार्य सर्किट $Z$ के लिए, एक्टर वास्तविक स्थानीय उप-त्रिकोणीकरण $\Delta^+(Z)$ पर रिफाइंड सिम्प्लेक्स फीचर्स को पूल करता है और उन्हें एक स्केलर स्कोर में प्रोजेक्ट करता है।
• वैल्यू हेड: एक हल्का MLP, पुल किए गए वर्टेक्स एम्बेडिंग का उपयोग करके स्टेट वैल्यू $V(\Delta)$ का अनुमान लगाता है, जिसका उपयोग पॉलिसी ग्रेडिएंट ट्रेनिंग के लिए किया जाता है।

4. प्रशिक्षण रणनीति (Training Strategy)

नीति को जेनेरालाइज्ड एडवांटेज एस्टीमेशन (GAE) के साथ प्रॉक्सिमल पॉलिसी ऑप्टिमाइज़ेशन (PPO) का उपयोग करके प्रशिक्षित किया जाता है।

• सामान्यीकरण (Generalization): मॉडल को छोटे पॉलीटोप्स के वितरण पर प्रशिक्षित किया जाता है और बड़े, अनदेखे पॉलीटोप्स पर मूल्यांकन किया जाता है।
• अन्वेषण (Exploration): उप-इष्टतम प्रक्षेप पथों (suboptimal trajectories) में फंसने से बचने के लिए, इसमें एक काउंट-आधारित एक्सपेंशन बोनस $b_t = \beta N(\Delta_{t+1})^{-1/2}$ शामिल है, जो एजेंट को अंतर्निहित ग्राफ में नए राज्यों (states) पर जाने के लिए प्रोत्साहित करता है।
• प्रारंभिक अवस्था नमूनाकरण (Initial State Sampling): प्रारंभिक अवस्थाओं को $N(\Delta_0)^{-1/2}$ के अनुपात में भार के साथ सैंपल किया जाता है ताकि कम-अन्वेषित क्षेत्रों को प्राथमिकता दी जा सके।

मुख्य योगदान

1. त्रिकोणीकरण के लिए RL फॉर्मूलेशन: यह शोध पत्र त्रिकोणीकरण अनुकूलन को एक अंतर्निहित फ्लिप ग्राफ पर RL के रूप में पहचानता है, जिसमें वैधता के लिए ज्यामितीय रूटीन और चाल चयन के लिए एक सीखी गई नीति का उपयोग किया गया है।
2. सर्किट-समर्थित क्रिया प्रतिनिधित्व: एक आयाम-अज्ञेय इंटरफ़ेस जो क्रियाओं को उनके समर्थित सर्किट और स्थानीय उप-त्रिकोणीकरण के माध्यम से एनकोड करता है, जिससे नीति को स्थानीय ज्यामितीय और कॉम्बिनेटोरियल विशेषताओं के आधार पर चालों को रैंक करने में सक्षम बनाया जाता है।
3. जीरो-शॉट सामान्यीकरण (Zero-Shot Generalization): फ्रेमवर्क छोटे प्रशिक्षण उदाहरणों से बड़े पॉलीटोप्स (जिनके खोज स्थान चरघातांकी रूप से बड़े हैं) तक मजबूत सामान्यीकरण प्रदर्शित करता है।
4. कैलि-याउ सैंपलिंग के लिए अनुप्रयोग: फ्रेमवर्क को 4D रिफ्लेक्सिव पॉलीटोप्स (जो कैलि-याउ थ्रीफोल्ड्स को पैरामीटराइज़ करते हैं) के फाइन, रेगुलर, स्टार (FRST) त्रिकोणीकरण के लिए एक सैंपलर के रूप में अनुकूलित किया गया है।

प्रयोगात्मक परिणाम

3D और 4D में तीन उद्देश्यों के तहत प्रयोग किए गए: मिन सिम्प्लेक्स (Min Simplices), मिन डायमीटर (Min Diameter), और मिन वेट (Min Weight)।

• अनुकूलन प्रदर्शन (Optimization Performance):

  • 3D में, TriSearch सटीक इष्टतम (जो सटीक TOPCOM गणना द्वारा पाया गया है) के विरुद्ध औसतन 0.16% का सापेक्ष अंतर (relative gap) प्राप्त करता है, जो NLS (8.97%), GREEDY, और सिम्युलेटेड एनीलिंग जैसे बेसलाइन्स से काफी बेहतर है।
  • 4D में, जहाँ सटीक गणना असंभव है, TriSearch 'मिन सिम्प्लेक्स' और 'मिन वेट' पर $10^9$-स्टेप TOPCOM गणना बेसलाइन को पछाड़ देता है। यह औसतन 1.43% का सापेक्ष अंतर प्राप्त करता है, जबकि अगले सर्वश्रेष्ठ बेसलाइन (NLS) के लिए यह 9.09% है।
  • एब्लेशन (Ablation): सिम्पलिसियल जानकारी (केवल EGNN का उपयोग करके) या उप-त्रिकोणीकरण संरचना (साधारण पूलिंग का उपयोग करके) को हटाने से सापेक्ष अंतर काफी बढ़ जाता है, जो सर्किट-समर्थित प्रतिनिधित्व की आवश्यकता की पुष्टि करता है।

• कैलि-याउ थ्रीफोल्ड सैंपलिंग:

  • 4D रिफ्लेक्सिव पॉलीटोप्स (क्रुज़र-स्कारके लिस्ट) के लिए अलग-अलग FRSTs की खोज करने के कार्य में, TriSearch मौजूदा CYTOOLS सैंपलर्स (FRST फास्ट सैंपलर और MCMC) से बेहतर प्रदर्शन करता है।
  • एक निश्चित बजट के तहत, TriSearch अधिक विशिष्ट कैलि-याउ थ्रीफोल्ड क्लास की खोज करता है, विशेष रूप से उच्च हॉज नंबरों ($h^{1,1} = 12, 16$) के लिए, जहाँ अन्य विधियाँ कम सैंपलिंग दक्षता या सफलता दर में तेजी से गिरावट का सामना करती हैं।

महत्व और सीमाएं

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

लेखक सीमाओं को स्वीकार करते हैं:

• वर्तमान में विधि एक ज्यामितीय रूटीन (TOPCOM) पर निर्भर करती है जो वैध फ्लिप्स को सूचीबद्ध करती है, जिसे समानांतर (parallelize) करना कठिन है।
• यह वर्तमान में उन मामलों को संबोधित नहीं करता है जहाँ फ्लिप ग्राफ विच्छेदित (disconnected) होता है (जो $d \geq 6$ में ज्ञात है)।
• CY सैंपलिंग में, प्रारंभिक त्रिकोणीकरण को समान रूप से (uniformly) सैंपल किया जाता है; भविष्य के कार्य रणनीतिक सैंपलिंग के लिए हाइट स्पेस में FRSTs के वितरण को सीख सकते हैं।

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