Exploiting Non-Negativity in DAG Structure Learning

तकनीकी सारांश: DAG संरचना शिक्षण में गैर-ऋणात्मकता (Non-Negativity) का दोहन

समस्या विवरण
यह शोध पत्र एक रैखिक स्ट्रक्चरल इक्वेशन मॉडल (SEM) द्वारा उत्पन्न नोडल अवलोकनों (nodal observations) से निर्देशित अचक्रीय ग्राफ़ (Directed Acyclic Graphs - DAG) सीखने की चुनौती को संबोधित करता है। जबकि DAG लर्निंग, कारण अनुमान (causal inference) और नेटवर्क टोपोलॉजी अनुमान के लिए मौलिक है, यह गणनात्मक रूप से कठिन है क्योंकि अचक्रीयता (acyclicity) एक वैश्विक कॉम्बिनेटोरियल गुण है। मौजूदा निरंतर दृष्टिकोण, जैसे कि NOTEARS और DAGMA, विविक्त अचक्रीयता प्रतिबंध (discrete acyclicity constraint) को स्मूथ समानता प्रतिबंधों (जैसे कि मैट्रिक्स एक्सपोनेंशियल या हैडामार्ड उत्पादों के लॉग-डिटरमिनेंट पर आधारित) द्वारा प्रतिस्थापित करते हैं। हालाँकि, ये फॉर्मूलेशन गैर-उत्तल (non-convex) अनुकूलन परिदृश्य और अपभ्रष्ट प्रथम-क्रम इष्टतम स्थितियों (degenerate first-order optimality conditions) से ग्रस्त होते हैं। विशेष रूप से, मानक अचक्रीयता फलनों के ग्रेडिएंट (gradients) व्यवहार्य DAGs पर लुप्त (vanish) हो जाते हैं, जिससे KKT अपभ्रष्टता (degeneracy) उत्पन्न होती है जहाँ व्यवहार्य समाधान स्कोर फंक्शन के अनियंत्रित स्टेशनरी पॉइंट्स के समान ही प्रतीत होते हैं।

कार्यप्रणाली
लेखक गैर-ऋणात्मक एज वेट्स (non-negative edge weights) वाले DAGs पर ध्यान केंद्रित करके एक पूरक दृष्टिकोण प्रस्तावित करते हैं। यह धारणा, जो उत्तेजक (excitatory) या योगात्मक (additive) अंतःक्रियाओं वाले संदर्भों में स्वाभाविक है, मैट्रिक्स शक्तियों में संकेत निरस्तीकरण (sign cancellations) को समाप्त कर देती है, जिससे अचक्रीयता का एक सरल लक्षण वर्णन संभव होता है।

1. गैर-ऋणात्मक अचक्रीयता लक्षण वर्णन:
   हैडामार्ड उत्पादों ($W \circ W$) के बजाय, लेखक एडजेसेंसी मैट्रिक्स $W \in \mathbb{R}^{d \times d}_+$ पर सीधे अचक्रीयता प्रतिबंध को परिभाषित करते हैं। वे इस फलन का उपयोग करते हैं:
   $$h(W) = d \log(s) - \log \det(sI - W)$$
   जहाँ $s$ एक स्केलर है जो स्पेक्ट्रल रेडियस $\rho(W) < s$ सुनिश्चित करता है।

• मुख्य गुण: गैर-ऋणात्मक मैट्रिसेस के लिए, $h(W) = 0$ तभी होता है जब $W$ एक DAG का प्रतिनिधित्व करता है।
• लाभ: हैडामार्ड-आधारित प्रतिबंधों के विपरीत, ग्रेडिएंट $\nabla h(W) = (sI - W)^{-\top}$ व्यवहार्य DAGs पर लुप्त नहीं होता है। यह KKT स्थितियों की अपभ्रष्टता को रोकता है, यह सुनिश्चित करता है कि व्यवहार्य अचकलीय मैट्रिसेस केवल स्वयं के प्रतिबंध के स्टेशनरी पॉइंट न बन जाएँ।

2. अनुकूलन फॉर्मूलेशन (Optimization Formulation):
   लर्निंग समस्या को एक लॉग-डिटरमिनेंट अचक्रीयता प्रतिबंध और गैर-ऋणात्मकता प्रतिबंधों के साथ एक नियमितकृत लीस्ट-स्क्वायर्स एस्टिमेटर के रूप में तैयार किया गया है:
   $$\min_{W \ge 0} \frac{1}{2n}\|X - W^\top X\|_F^2 + \alpha_n \sum_{i \neq j} W_{ij} \quad \text{सर्त (s.t.)} \quad h(W) = 0, \rho(W) < s$$
   लेखक इसे मेथड ऑफ मल्टीप्लायर्स (Augmented Lagrangian) का उपयोग करके हल करते हैं। एल्गोरिदम प्रक्षिप्त ग्रेडिएंट डिसेंट (projected gradient descent) के माध्यम से एडजेसेंसी मैट्रिक्स को पुनरावृत्त रूप से अपडेट करता है (गैर-ऋणात्मक ऑर्थेंट पर प्रोजेक्शन के साथ) और प्रतिबंध उल्लंघन के आधार पर लैग्रेंज मल्टीप्लायर को अपडेट करता है।

मुख्य योगदान

• सरलीकृत अचक्रीयता प्रतिबंध: यह शोध पत्र प्रदर्शित करता है कि गैर-ऋणात्मकता के तहत, अचक्रीयता को एक स्मूथ फलन द्वारा लक्षित किया जा सकता है जो हैडामार्ड उत्पादों से बचता है, जिससे मौजूदा निरंतर फॉर्मूलेशन में मौजूद ग्रेडिएंट लुप्त होने की समस्या से बचा जा जा सकता है।
• एल्गोरिद्मिक प्रस्ताव: लेखक NOMAD (Non-negative Optimization via Multipliers for Acyclic Digraphs) पेश करते हैं, जो गैर-ऋणात्मक DAG लर्निंग के लिए विशेष रूप से तैयार किया गया एक ऑगमेंटेड-लैग्रेंजियन एल्गोरिदम है।
• पॉपुलेशन लैंडस्केप विश्लेषण: शोध पत्र जनसंख्या-स्तर के अनुकूलन परिदृश्य का गहन सैद्धांतिक विश्लेषण प्रदान करता है। मानक पहचान योग्यता (identifiability) धारणाओं और एक विशिष्ट मल्टीप्लायर सेटिंग ($\lambda \ge 2$) के तहत, वे सिद्ध करते हैं कि:
  1. वास्तविक DAG, जनसंख्या ऑगमेंटेड लैग्रेंजियन का एकमात्र वैश्विक मिनिमाइज़र (global minimizer) है।
  2. कोई स्प्यूरियस इंटीरियर स्टेशनरी पॉइंट्स (spurious interior stationary points) नहीं हैं (यदि $\lambda > 2$, कोई स्टेशनरी पॉइंट मौजूद नहीं है; यदि $\lambda = 2$, एकमात्र स्टेशनरी पॉइंट वास्तविक DAG है)।
  3. एकमात्र अचकलीय KKT पॉइंट वास्तविक DAG ही है।
• अनुभवजन्य सत्यापन (Empirical Validation): सिंथेटिक डेटा और वास्तविक दुनिया के 'सैक्स प्रोटीन-सिग्नलिंग' बेंचमार्क पर व्यापक संख्यात्मक प्रयोगों से पता चलता है कि प्रस्तावित विधि de facto भारित अनुमान त्रुटि (weighted estimation error) और स्ट्रक्चरल रिकवरी (SHD) दोनों में अत्याधुनिक निरंतर बेसलाइनों (NOTEARS, DAGMA, CoLiDE) से बेहतर प्रदर्शन करती है, विशेष रूपकर जैसे-जैसे नमूना आकार बढ़ता है।

परिणाम और महत्व
शोध पत्र का दावा है कि गैर-ऋणात्मकता का उपयोग करना DAG लर्निंग को एक "काफी बेहतर-कंडीशन्ड ऑप्टिमाइज़ेशन समस्या" में बदल देता है। सैद्धांतिक परिणाम संकेत देते हैं कि प्रस्तावित फॉर्मूलेशन उन स्थानीय मिनिमा और अपभ्रष्ट स्टेशनरी पॉइंट्स से बचता है जो मौजूदा विधियों को प्रभावित करते हैं। जनसंख्या शासन (population regime) में, परिदृश्य "सौम्य" (benign) है, जहाँ वास्तविक DAG एकमात्र समाधान है।

परिमित-नमूना (finite-sample) शासन में, संख्यात्मक परिणाम दर्शाते हैं कि प्रस्तावित विधि की अनुमान त्रुटि अवलोकनों की संख्या बढ़ने के साथ लगातार घटती है, जबकि कुछ बेसलाइन संतृप्ति (saturation) प्रदर्शित करती हैं। सैक्स प्रोटीन-सिग्नलिंग बेंचमार्क पर, विधि ने सबसे कम स्ट्रक्चरल हैमिंग डिस्टेंस (SHD) और फॉल्स डिस्कवरी रेट (FDR) प्राप्त किया, जो बिना किसी गलत किनारे (false edges) को जोड़े जैविक ज्ञान के अनुरूप एक स्पार्स ग्राफ को सफलतापूर्वक रिकवर करती है।

इस कार्य का महत्व इस बात में निहित है कि यह दिखाना है कि सार्थक संकेत जानकारी (गैर-ऋणात्मकता) को शामिल करना केवल एक मॉडलिंग पूर्वधारणा (modeling prior) नहीं है, बल्कि एक संरचनात्मक सक्षमकर्ता (structural enabler) है जो अचक्रीयता प्रतिबंध को सरल बनाता है, अनुकूलन परिदृश्य में सुधार करता है, और उन अनुप्रयोगों में अधिक मजबूत और सटीक कारण खोज (causal discovery) की ओर ले जाता है जहाँ अंतःक्रियाएं ज्ञात रूप से गैर-निरोधात्मक (non-inhibitory) होती हैं।