Variational Free Energy Pivot Selection for Pivoted Cholesky

तकनीकी सारांश: पिवोटेड चोलेस्की के लिए वेरिएशनल फ्री एनर्जी पिवट चयन

समस्या विवरण
सममित धनात्मक निश्चित (SPD) मैट्रिसेस के लो-रैंक सन्निकटन (approximations) संख्यात्मक रैखिक बीजगणित में मौलिक हैं, विशेष रूप से गाऊसी प्रक्रिया (GP) रिग्रेशन में जहाँ कर्नेल मैट्रिक्स $K$ को रैंक-$r$ गुणनखंड $\tilde{K} = LL^\top$ द्वारा सन्निकट किया जाता है। शास्त्रीय विधियाँ, जैसे कि ग्रीडी (greedy) और रैंडमली पिवोटेड चोलेस्की (RPCholesky), अवशिष्ट (residual) के बीजगणितीय ट्रेस-नॉर्म त्रुटि ($\text{tr}(K - \tilde{K})$) को कम करने के लिए अनुक्रमिक रूप से पिवट चुनती हैं। हालाँकि, कई अनुप्रयोगों में, मैट्रिक्स $K$ का मूल्यांकन अकेले नहीं किया जाता है, बल्कि एक गैर-रेखीय मैट्रिक्स फंकशनल (nonlinear matrix functional) के भीतर किया जाता है। विशेष रूप से, GP रिग्रेशन में, सन्निकटन की गुणवत्ता वेरिएशनल फ्री एनर्जी (VFE) द्वारा निर्धारित होती है, जिसे $L(\tilde{K})$ द्वारा दर्शाया जाता है, जो लॉग मार्जिनल लाइकलीहुड (log marginal likelihood) पर एक निचला बाउंड (lower bound) है।

VFE फंकशनल तीन अलग-अलग पदों को संयोजित करता है: एक लॉग-डिटरमिनेंट टर्म (जटिलता), एक क्वाड्रेटिक डेटा-फिट टर्म, और एक ट्रेस पेनल्टी टर्म। मौजूदा पिवट चयन नियम, जो केवल अवशिष्ट विकर्ण परिमाणों (residual diagonal magnitudes) पर निर्भर करते हैं, केवल ट्रेस-नॉर्म त्रुटि को लक्षित करते हैं। फलस्वरूप, वे लॉग-डिटरमिनेंट और डेटा-फिट घटकों की उपेक्षा करते हैं, जिससे विशिष्ट अनुमान उद्देश्य (inference objective) के लिए व्यवस्थित रूप से उप-इष्टतम (suboptimal) सन्निकटन हो सकता है। यह शोध पत्र इस प्रश्न को संबोधित करता है: जब लक्ष्य एक शुद्ध बीजगणितीय सन्निकटन त्रुटि के बजाय एक मैट्रिक्स फंकशनल को अनुकूलित करना हो, तो पिवट चयन कैसे किया जाना चाहिए?

कार्यप्रणाली
लेखक एक नया पिवट चयन नियम प्रस्तावित करते हैं, जिसे $\Delta$-VFE पिवोटेड चोलेस्की कहा जाता है, जो चोलेस्की-संगत रैंक-1 अपडेट के तहत VFE फंकशनल में सटीक एक-चरणीय परिवर्तन (exact one-step change) को सीधे अधिकतम करता है।

1. गेन फॉर्मूला (Gain Formula) का व्युत्पन्न:
   लेखक चोलेस्की-संगत रैंक-1 अपडेट $\tilde{K}_{i+1} = \tilde{K}_i + uu^\top$ के तहत VFE $L(\tilde{K})$ में सटीक परिवर्तन $\Delta L$ के लिए एक क्लोज्ड-फॉर्म अभिव्यक्ति व्युत्पन्न करते हैं। मैट्रिक्स डिटरमिनेंट लेम्मा और शेरमैन-मोरिसन फॉर्मूला का उपयोग करते हुए, वे गेन को तीन योज्य (additive) घटकों में विभाजित करते हैं:
   $$\Delta L = -\frac{1}{2} \left( \log(1 + a) - \frac{b^2}{1 + a} - \frac{1}{\sigma^2_\varepsilon} \|u\|^2_2 \right)$$
   जहाँ:

• $a = u^\top \Sigma_i^{-1} u$ जटिलता योगदान (लॉग-डिटरमिनेंट टर्म) को दर्शाता है, जो नियमितीकृत व्युत्क्रम मेट्रिक के साथ अपडेट की अंतःक्रिया को मापता है।
• $b = u^\top \Sigma_i^{-1} y$ डेटा-फिट योगदान को दर्शाता है, जो अपडेट दिशा और वर्तमान प्रेडिक्शन रेजिडुअल के बीच संरेखण को मापता है।
• $\|u\|^2_2$ ट्रेस योगदान (अवशिष्ट विचरण कमी) को दर्शाता है, जो शास्त्रीय विधियों द्वारा उपयोग किए जाने वाले विकर्ण प्रॉक्सी के बजाय सटीक एक-चरणीय ट्रेस कमी के अनुरूप है।

2. चोलेस्की-संगत अपडेट्स:
   यह सुनिश्चित करने के लिए कि सन्निकटन एक वैध चोलेस्की गुणनखंड बना रहे, अपडेट वेक्टर $u$ को $u_p = t_p / \sqrt{(T_i)_{p,p}}$ के रूप में प्रतिबंधित किया गया है, जहाँ $t_p$ अवशिष्ट मैट्रिक्स $T_i$ का $p$-वाँ कॉलम है। यह प्रतिबंध सुनिश्चित करता है कि अवशिष्ट धनात्मक अर्ध-निश्चित (positive semi-definite) रहे और चयनित पिवट का विक럴 एंट्री शून्य हो जाए।

3. एल्गोरिदम का क्रियान्वयन:
   प्रत्येक चरण में सभी $n$ उम्मीदवारों के लिए $\Delta L$ का मूल्यांकन करना गणनात्मक रूप से अत्यधिक महंगा ($O(n^2r^2)$) होगा। दक्षता बनाए रखने के लिए, विधि एक बैच्ड सैंपलिंग रणनीति (batched sampling strategy) का उपयोग करती है:

• प्रत्येक पुनरावृत्ति (iteration) में, अप्रयुक्त इंडिसेस के सेट से $s$ उम्मीदवार पिवोट्स का एक बैच सैंपल किया जाता है।
• सैंपलिंग संभाव्यता अवशिष्ट विक럴 एंट्रीज के समानुपाती है, जो RPCholesky में उपयोग किए गए वितरण के समान है।
• नियमितीकृत व्युत्क्रम $\Sigma_i^{-1} = (\tilde{K}_i + \sigma^2_\varepsilon I)^{-1}$ को वुडबरी मैट्रिक्स आइडेंटिटी और एक सहायक मैट्रिक्स $B = (I + L^\top L / \sigma^2_\varepsilon)^{-1}$ के वृद्धिशील अपडेट का उपयोग करके कुशलतापूर्वक लागू किया जाता है।
• यह दृष्टिकोण $s$ उम्मीदवारों के लिए गेन के मूल्यांकन को कुल लागत $O(snr^2)$ के साथ संभव बनाता है, जो बैच फैक्टर $s$ तक RPCholesky की एसिम्प्टोटिक जटिलता से मेल खाता है।

प्रमुख योगदान

• उद्देश्य-जागरूक पिवट नियम: शोध पत्र पहला पिवट चयन मानदंड व्युत्पन्न करता है जो शुद्ध ट्रेस-नॉर्म त्रुटि के बजाय VFE के प्रति-चरण गेन को स्पष्ट रूप से अधिकतम करता है।
• सैद्धांतिक गारंटी: लेखक सिद्ध करते हैं कि कोई भी चोलेस्की-संगत रैंक-1 अपडेट का अनुक्रम VFE मानों का एक मोनोटोनिक रूप से गैर-घटता (non-decreasing) अनुक्रम प्रदान करता है। प्रस्तावित नियम उस पिवट को चुनता है जो प्रत्येक चरण में इस गारंटीकृत गेन को अधिकतम करता है।
• जटिलता दक्षता: विधि वुडबरी अपडेट और बैच्ड कैंडिडेट इवैल्यूएशन का लाभ उठाकर RPCholesky के समान एसिम्प्टोटिक जटिलता ($O(snr^2)$) प्राप्त करती है।
• पदानुक्रमित व्याख्या (Hierarchical Interpretation): यह कार्य पिवट नियमों के तीन-स्तरीय पदानुक्रम को स्थापित करता है:
  1. स्तर 1: शास्त्रीय ग्रीडी/RPCholesky (ट्रेस रिडक्शन के लिए विक럴 प्रॉक्सी का उपयोग करता है)।
  2. स्तर 2: सटीक ट्रेस-रिडक्शन मैक्सिमाइज़र (पूर्ण अवशिष्ट कॉलम का उपयोग करता है, डेटा/जटिलता की उपेक्षा करता है)।
  3. स्तर 3: $\Delta$-VFE (पूर्ण VFE को अनुकूलित करने के लिए पूर्ण अवशिष्ट कॉलम, डेटा वेक्टर और नियमितीकृत व्युत्क्रम का उपयोग करता है)।

परिणाम
Abalone और QM7 डेटासेट पर संख्यात्मक प्रयोग निम्नलिखित प्रदर्शित करते हैं:

• VFE अनुकूलन: $\Delta$-VFE, ग्रीडी और RPCholesky दोनों की तुलना में लगातार लॉग मार्जिनल लाइकलीहुड के लिए एक कड़ा बाउंड (छोटा सापेक्ष VFE गैप) प्राप्त करता है, विशेष रूप से कम से मध्यम रैंक ($r \le 1024$) पर।
• सन्निकटन की गुणवत्ता: विधि RPCholesky के तुलनीय ट्रेस-नॉर्म सन्निकटन गुणवत्ता बनाए रखती है। यह VFE सुधार प्राप्त करने के लिए मानक कर्नेल सन्निकटन सटीकता का त्याग नहीं करती है।
• पूर्वानुमान प्रदर्शन (Predictive Performance): GP रिग्रेशन कार्यों में, बेहतर VFE कम से मध्यम रैंक पर पूर्वानुमान त्रुटियों (RMSE और MAE) को कम करने में मदद करता है।
• बैच आकार संवेदनशीलता: बैच आकार $s$ को बढ़ाने से प्रदर्शन में घटते प्रतिफल (diminishing returns) मिलते हैं, लेकिन यह लगातार VFE गैप और पूर्वानुमान सटीकता में सुधार करता है। छोटे बैच आकार (जैसे, $s=8$ या $s=16$) भी RPCholesky की तुलना में पर्याप्त लाभ प्रदान करते हैं।

महत्व
यह शोध पत्र दावा करता है कि प्रस्तावित विधि बीजगणितीय मैट्रिक्स सन्निकटन और कार्य-विशिष्ट अनुमान उद्देश्यों के बीच के अंतर को पाटती है। VFE के लिए एक सटीक, क्लोज्ड-फॉर्म गेन व्युत्पन्न करके, लेखक एक ग्रीडी पिवट नियम प्रदान करते हैं जो स्पष्ट रूप से गाऊसी प्रक्रियाओं के संभाव्य अनुमान लक्ष्य के साथ संरेखित है। परिणाम बताते हैं कि जहाँ मैट्रिक्स फंकशनल में डेटा-फिट या जटिलता पद शामिल होते हैं, वहाँ केवल ट्रेस-नॉर्म त्रुटि को अनुकूलित करना अपर्याप्त है, और उद्देश्य-जागरूक चयन बिना किसी महत्वपूर्ण गणनात्मक ओवरहेड के बेहतर व्यावहारिक प्रदर्शन प्रदान करता है। यह विधि RPCholesky का एक सीधा सामान्यीकरण है जो अतिरिक्त सूचनाओं को शामिल करता है।