🤖 machine learning

Learning Lookahead Lemmas for Neural Network Verification

यह शोध पत्र न्यूरल नेटवर्क सत्यापन के लिए एक इनप्रोसेसिंग फ्रेमवर्क पेश करता है जो अस्थिर ReLUs पर लेमा (lemmas) प्राप्त करने के लिए लुकअहेड प्रक्रियाओं का उपयोग करता है, जिनका उपयोग फिर खोज स्थान को कम करने और Marabou तथा $\alpha$ - $\beta$ -CROWN जैसे अत्याधुनिक सत्यापनकर्ताओं के प्रदर्शन में सुधार करने के लिए किया जाता है, जिससे 34% तक अधिक इंस्टेंस को असंतोषजनक (unsatisfiable) सिद्ध किया जा सकता है।

मूल लेखक: Liam Davis, Haoze Wu

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

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

CC BY 4.0

मूल लेखक: Liam Davis, Haoze Wu

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

कल्पना कीजिए कि आप एक रोबोट को सुरक्षित रूप से कार चलाना सिखाने की कोशिश कर रहे हैं। आप 100% सुनिश्चित होना चाहते हैं कि वह कभी भी रेड लाइट न तोड़े या पैदल यात्री से न टकराए, चाहे मौसम कैसा भी हो या ड्राइवर का व्यवहार कैसा भी हो। यह न्यूरल नेटवर्क वेरिफिकेशन (neural network verification) की दुनिया है। न्यूरल नेटवर्क आधुनिक AI के पीछे के "मस्तिष्क" हैं, लेकिन वे अक्सर एक 'ब्लैक बॉक्स' की तरह होते हैं: हम जानते हैं कि क्या अंदर जा रहा है और क्या बाहर आ रहा है, लेकिन उनके भीतर की उलझी हुई गणितीय प्रक्रिया को समझना कठिन है। क्योंकि इन प्रणालियों का उपयोग सुरक्षा-महत्वपूर्ण (safety-critical) कार्यों में किया जाता है, हम केवल अनुमान नहीं लगा सकते कि वे सुरक्षित हैं; हमें इसे सिद्ध करने की आवश्यकता है।

इसे करने के लिए, गणितज्ञ ब्रांच-एंड-बाउंड (Branch-and-Bound) नामक रणनीति का उपयोग करते हैं। इसे एक ऐसे जासूस की तरह सोचें जो हर संभावित संदिग्ध की जांच करके एक रहस्य को सुलझाने की कोशिश कर रहा है। जासूस मामले को छोटे-छोटे हिस्सों में विभाजित करता है (ब्रांचिंग) और यह सिद्ध करने की कोशिश करता है कि कुछ परिदृश्य असंभव हैं (बाउंडिंग)। यदि वे सिद्ध कर सकते हैं कि कोई परिदृश्य असंभव है, तो वे उसे हटा देते हैं और उस पर समय बर्बाद करना बंद कर देते हैं। हालाँकि, यह प्रक्रिया अविश्वसनीय रूप से धीमी हो सकती है क्योंकि जांचने के लिए बहुत सारे संभावित परिदृश्य मौजूद हैं। बड़ा सवाल यह है कि हम जासूस को स्मार्ट कैसे बना सकते हैं ताकि उन्हें हर एक गलत रास्ते (dead end) की जांच न करनी पड़े?

यह शोध पत्र एक चतुर नई तकनीक पेश करता है जिसे लर्निंग लुकअहेड लेम्माज़ (Learning Lookahead Lemmas) कहा जाता है। केवल यह पता लगाने के बाद कि कोई रास्ता खराब था, रुकने के बजाय, लेखक वर्िफायर (verifier) को काम शुरू करने से पहले ही "सड़क के नियम" देखने और सीखने के लिए प्रशिक्षित करते हैं। उन्होंने पाया कि कुछ कदम आगे का पूर्वावलोकन (simulating) करके, सिस्टम AI के मस्तिष्क के विभिन्न हिस्सों के बीच तार्किक संबंधों की खोज कर सकता है। उन्होंने एक ऐसा ढांचा बनाया जो इन कनेक्शनों का उपयोग करके खोज क्षेत्र (search space) के विशाल हिस्सों को तुरंत काट देता है। जब उन्होंने इस नई पद्धति का परीक्षण दुनिया के दो सबसे तेज़ वेरिफिकेशन टूल्स, मारबौ (Marabou) और α-β-क्राउन (α-β-CROWN) पर किया, तो यह जादू की तरह काम कर गया। इन टूल्स ने 34% अधिक मामलों को सुरक्षित (या गणितीय शब्दों में "अनसैटिस्फिएबल/unsatisfiable") सिद्ध किया और ऐसा उन्होंने बहुत तेज़ी से किया, बिना एक ही समस्या पर बार-बार अटकें।

जासूस की नई महाशक्ति

कल्पische कि आप एक भूलभुलैया (maze) सुलझाने की कोशिश कर रहे एक जासूस हैं। आमतौर पर, आप एक रास्ते पर चलते हैं, दीवार से टकराते हैं, वापस मुड़ते हैं, और दूसरा रास्ता आज़माते हैं। वर्तमान AI वर्िफायर इसी तरह काम करते हैं: वे एक समस्या को दो संभावनाओं में विभाजित करते हैं (जैसे "क्या यह लाइट चालू है या बंद?"), जांचते हैं कि क्या यह काम करता है, और यदि यह विफल हो जाता है, तो वे आगे बढ़ जाते हैं। लेकिन यह धीमा है।

लेखकों ने पूछा: क्या होगा यदि जासूस कदम उठाने से पहले ही कोने के पार झाँक सके?

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

इम्पलीकेशन ग्राफ: सुरागों का जाल

लेखकों ने इन सभी छोटे नियमों को एक विशाल जाल में एकत्र किया जिसे इम्पलीकेशन ग्राफ (Implication Graph) कहा जाता है। इस ग्राफ को तर्क के एक विशाल फ्लोचार्ट के रूप में सोचें।

नोड्स (Nodes) AI के "फेजेस" (phases) हैं (जैसे एक न्यूरॉन का सक्रिय या निष्क्रिय होना)।
एरो (Arrows) कारण और प्रभाव को दर्शाते हैं। यदि नोड A होता है, तो नोड B का होना अनिवार्य है।

यह ग्राफ केवल एक स्थिर सूची नहीं है; यह एक जीवित उपकरण है जिसका उपयोग जासूस तीन शक्तिशाली तरीकों से करता है:

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

परिणाम: तेज़ और स्मार्ट

लेखकों ने केवल इसकी कल्पना नहीं की; उन्होंने इसे दो वास्तविक दुनिया के सुपर-सॉल्वर में शामिल किया: मारबौ (Marabou) और α-β-क्राउन (α-β-CROWN)। उन्होंने विमान की टक्करों से बचने (ACAS Xu), हस्तलिखित संख्याओं को पहचानने (MNIST), और छवियों को वर्गीकृत करने (CIFAR और TinyImageNet) के लिए उपयोग किए जाने वाले मानक बेंचमार्क पर इनका परीक्षण किया।

परिणाम प्रभावशाली थे। इस "लुकअहेड" ढांचे का उपयोग करके:

सॉल्वर्स ने अपने पिछले संस्करणों की तुलना में 34% अधिक उदाहरणों को सुरक्षित (UNSAT) सिद्ध किया।
उन्होंने इन समस्याओं को तेज़ी से हल किया, जिसमें "झाँकने" (peeking) वाले हिस्से ने कुल समय का बहुत कम हिस्सा (कुछ परीक्षणों में अक्सर 2.6% से भी कम) लिया।
MNIST बेंचमार्क पर, नए तरीके ने पुराने तरीके की तुलना में 35 अधिक अनसैटिस्फिएबल (unsatisfiable) उदाहरणों को हल किया।

यह शोध पत्र दिखाता है कि यह दृष्टिकोण एक वास्तविक सुधार है, न कि केवल एक सैद्धांतिक विचार। यह सत्यापन प्रक्रिया को एक धीमी, चरण-दर-चरण चाल से बदलकर एक स्मार्ट, रणनीतिक खेल में बदलकर काम करता है जहाँ जासूस हर बार झाँकने से सीखता है, और असंभव रास्तों को शुरू होने से पहले ही काट देता है। लेखक सुझाव देते हैं कि यह AI को महत्वपूर्ण कार्यों के लिए सुरक्षित बनाने की दिशा में एक बड़ा कदम हो सकता है, हालांकि वे यह भी नोट करते हैं कि भविष्य में "झाँकने" (peeking) को और भी स्मार्ट बनाने की गुंजाइश अभी भी है।

तकनीकी सारांश: न्यूरल नेटवर्क सत्यापन के लिए लर्निंग लुकअहेड लेम्मास (Learning Lookahead Lemmas)

समस्या विवरण
स्टेट-ऑफ-द-आर्ट न्यूरल नेटवर्क वेरीफायर (verifiers) ब्रांच-एंड-बाउंड (BaB) प्रक्रिया पर निर्भर करते हैं, जो नॉन-लीनियर एक्टिवेशन फंक्शन्स (विशेष रूप से ReLUs) को विश्लेषित करने के लिए रिकर्सिवली (recursively) विभाजित करते हैं। जबकि हालिया प्रगति ने ब्रांचिंग ह्यूरिस्टिक्स (branching heuristics) को बेहतर बनाया है और असंभव सबप्रॉब्लम्स (infeasible subproblems) से व्युत्पन्न किए गए बूलियन कट्स (boolean cuts) में सुधार किया है, ये दृष्टिकोण काफी हद तक रिएक्टिव (reactive) हैं। वे उस जानकारी का उपयोग करते हैं जिसे खोज (search) पहले ही प्राप्त कर चुकी है। आधुनिक SAT सॉल्वर्स के विपरीत, जो इनप्रोसेसिंग (inprocessing) का उपयोग करते हैं—जो सूचना प्राप्त करने के लिए खोज को रुक-रुक कर सक्रिय रूप से नई जानकारी व्युत्पन्न करने के लिए रोकते हैं—न्यूरल नेटवर्क वेरिफिकेशन में एक समान तंत्र का अभाव है। यह शोध पत्र BaB सॉल्विंग लूप में प्रोएक्टिव (proactive) सूचना व्युत्पन्न करने के एकीकरण के अंतर को दूर करता है।

कार्यप्रणाली (Methodology)
लेखक एक इनप्रोसेसिंग फ्रेमवर्क पेश करते हैं जो लुकअहेड प्रक्रिया (lookahead procedure) के एक रूपांतर द्वारा संचालित है। लुकअहेड का उपयोग केवल अगले ब्रांचिंग वेरिएबल को चुनने के लिए करने के बजाय, यह फ्रेमवर्क अस्थिर ReLUs के चरणों (सक्रिय या निष्क्रिय) के संबंध में नए तार्किक लेम्मा (logical lemmas) व्युत्पन्न करने के लिए इसका उपयोग करता है।

मुख्य कार्यप्रणाली में तीन घटक शामिल हैं:

इम्प्लिकेशन ग्राफ निर्माण (Implication Graph Construction):
फ्रेमवर्क एक निर्देशित इम्प्लिकेशन ग्राफ $G = (V, E)$ का निर्माण करता है जहाँ नोड्स अस्थिर ReLUs के फेज फिक्सेस ( $r_i$ सक्रिय के लिए, $\neg r_i$ निष्क्रिय के लिए) का प्रतिनिधित्व करते हैं।

लुकअहेड प्रोब (Lookahead Probe): प्रत्येक अस्थिर ReLU के लिए, प्रक्रिया उसे दोनों सक्रिय और निष्क्रिय चरणों में फिक्स करने का अनुकरण (simulate) करती है। एक प्रतिबंधित, बजटेड बाउंड प्रोपेगेशन (Marabou के लिए DeepPoly या $\alpha$ - $\beta$ -CROWN के लिए एक एकल $\alpha$ -CROWN पास का उपयोग करके) किया जाता है।
लेम्मा व्युत्पत्ति (Lemma Derivation): यदि एक फेज फिक्स असंभवता (infeasibility) की ओर ले जाता है, तो उसके पूरक को एक यूनिट लेम्मा (unit lemma) के रूप में रिकॉर्ड किया जाता है। यदि एक फेज फिक्स किसी अन्य अस्थिर ReLU को एक विशिष्ट चरण की ओर मजबूर करता है, तो एक बाइनरी इम्प्लिकेशन ( $r_i \to r_j$ ) रिकॉर्ड किया जाता है।
**हल बाउंड्स (Hull Bounds):ism यह प्रक्रिया दोनों फेज सिमुलेशन से प्राप्त बाउंड्स के हल (hull) को लेकर अधिक सटीक बाउंड्स भी कंप्यूट करती है।

SAT क्लोजर के माध्यम से सर्च स्पेस प्रूनिंग (Search Space Pruning via SAT Closure):
इम्प्लिकेशन ग्राफ को एक प्रपोजिशनल फॉर्मूला $\Sigma$ के रूप में माना जाता है। किसी भी BaB नोड पर, सॉल्वर $\Sigma \cup R$ की संतुष्टि (satisfiability) की जाँच करता है, जहाँ $R$ वर्तमान खोज पथ के साथ प्रतिबद्ध (committed) किए गए फेज फिक्स का प्रतिनिधित्व करता है। यदि यह यूनियन असंतोषजनक (unsatisfiable) है, तो सबप्रॉब्लम को आगे के बाउंड प्रोपेगेशन या विभाजन के बिना तुरंत हटा (prune) दिया जाता है।
डायनेमिक अपडेट्स और कट विविफिकेशन (Dynamic Updates and Cut Vivification):

रीप्रोबिंग (Reprobing): जैसे-जैसे खोज आगे बढ़ती है और अधिक ReLUs फिक्स होते हैं, सर्च स्पेस संकुचित होता जाता है। फ्रेमवर्क विशिष्ट अंतरालों पर (जब कोई नया ब्रांचिंग निर्णय लागू नहीं होता और स्थापित चरणों का सेट बढ़ जाता है) रीप्रोबिंग को ट्रिगर करता है ताकि प्रतिबंधित क्वेरी पर लुकअहेड प्रक्रिया को फिर से चलाया जा सके। यह इम्प्लिकेशन ग्राफ को उन नए तथ्यों के साथ अपडेट करता है जो रूट (root) पर सिद्ध करने योग्य नहीं थे।
कट विविफिकेशन (Cut Vivification): जब एक सबप्रॉब्लम UNSAT सिद्ध हो जाता है, तो मानक वेरीफायर बूलियन कट्स (जैसे BICCOS या PICID) को माइन करते हैं। फ्रेमवर्क इम्प्लिकेशन ग्राफ का उपयोग करके इन कट्स को विविफाई (vivify) करता है। यह इम्प्लिकेशन को ट्रेस करके कट से अनावश्यक फेज फिक्सेस की पहचान करता है और उन्हें हटा देता है। यदि कोई कट ग्राफ के क्लोजर के विरुद्ध असंतोषजनक पाया जाता है, तो फ्रेमवर्क एक अनसैटिस्फिएबल कोर (unsatisfiable core) निकालता है (अक्सर कट को आकार 2 या एक सिंगल यूनिट लेम्मा तक कम कर देता है)। इस छोटे किए गए कट को फिर से ग्लोबल समस्या और इम्प्लिकेशन ग्राफ में जोड़ा जाता है, जिससे भविष्य की प्रूनिंग मजबूत होती है।

प्रमुख योगदान (Key Contributions)

इनप्रोसेसिंग फ्रेमवर्क: यह पेपर न्यूरल नेटवर्क वेरिफिकेशन के लिए पहला पूर्ण इनप्रोसेसिंग फ्रेमवर्क प्रस्तावित करता है, जो सूचना के रिएक्टिव दोहन से प्रोएक्टिव व्युत्पन्न करने की ओर शिफ्ट करता है।
लुकअहेड-व्युत्पन्न लेम्मास: यह केवल एक ब्रांचिंग ह्यूरिस्टिक के रूप में उपयोग करने के बजाय, ReLU फेज संबंधों के एक डायनेमिक इम्प्लिकेशन ग्राफ को उत्पन्न करने के लिए लुकअहेड प्रक्रिया को अनुकूलित करता है।
मौजूदा वेरीफर्स के साथ एकीकरण: इस फ्रेमवर्क को दो अलग-अलग स्टेट-ऑफ-द-आर्ट वेरीफर्स में स्थापित किया गया है: Marabou (SMT-आधारित, CPU) और $\alpha$ - $\beta$ -CROWN ( $\alpha$ - $\beta$ -CROWN आधारित, GPU)।
कट सुदृढ़ीकरण (Cut Strengthening): यह इम्प्लिकेशन ग्राफ का उपयोग करके बूलियन कट्स को विविफाई करने के लिए एक तंत्र पेश करता है, जो प्रभावी रूप से कट्स को उनके आवश्यक असंभव कोर तक छोटा करता है।

प्रायोगिक परिणाम (Experimental Results)
फ्रेमवर्क का मूल्यांकन मानक बेंचमार्क (Marabou के लिए ACASXu, MNIST, SafeNLP; $\alpha$ - $\beta$ -CROWN के लिए CIFAR और TinyImageNet) पर किया गया।

प्रदर्शन लाभ: फ्रेमवर्क ने दोनों वेरीफर्स के प्रदर्शन में सुधार किया। विशेष रूप से, इसने बेसलाइन वेरीफर्स की तुलना में 34% अधिक इंस्टेंस UNSAT सिद्ध किए।
दक्षता: लुकअहेड प्रोबिंग और रीप्रोबिंग चरणों का ओवरहेड न्यूनतम था। उदाहरण के लिए, SafeNLP पर, प्रोबिंग ने वॉल-क्लॉक टाइम का 0.1% से भी कम हिस्सा लिया; यहाँ तक कि MNIST पर भी, जहाँ यह 19.2% तक पहुँचा, शुद्ध लाभ (35 अतिरिक्त UNSAT इंस्टेंस) लागत से कहीं अधिक था।
मजबूती (Robustness): इस दृष्टिकोण ने सभी परीक्षण किए गए बेंचमार्क में टाइमआउट और औसत खोज अवस्थाओं (average search states) को कम किया।

महत्व और दावे (Significance and Claims)
यह पेपर एक प्रोएक्टिव सूचना व्युत्पन्न तंत्र पेश करके न्यूरल नेटवर्क वेरिफिकेशन में एक महत्वपूर्ण अंतर को भरने का दावा करता है जो SAT सॉल्विंग में इनप्रोसेसिंग के समान है। लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण सूचना के नए व्युत्पन्न को ब्रांचिंग ह्यूरिस्टिक्स के बायप्रोडक्ट (byproduct) के बजाय समाधान प्रक्रिया के एक अभिन्न अंग के रूप में मानता है।

परिणामों से पता चलता है कि इम्प्लिकेशन ग्राफ बनाने के लिए लुकअहेड का लाभ उठाना वेरीफायर को सर्च स्पेस को अधिक प्रभावी ढंग से प्रून करने और बूलियन कट्स को मजबूत करने की अनुमति देता है। लेखक नोट करते हैं कि हालांकि वर्तमान कार्यान्वयन बाइनरी इम्प्लिकेशन और यूनिट लेम्मा पर केंद्रित है, भविष्य के कार्य प्रोपेगेशन-रेडंडेंट क्लॉज (propagation-redundant clauses) व्युत्पन्न करने या रीजनिंग को लीनियर कंस्ट्रेंट्स तक उठाने की खोज कर सकते हैं। वे यह भी सुझाव देते हैं कि क्वेरीज़ के बीच ग्राफ को ले जाने से इंक्रीमेंटल वेरिफिकेशन (incremental verification) में सुधार हो सकता है, हालांकि यह भविष्य के अनुसंधान के लिए एक दिशा बनी हुई है।

जासूस की नई महाशक्ति

इम्पलीकेशन ग्राफ: सुरागों का जाल

परिणाम: तेज़ और स्मार्ट

इसी तरह के और पेपर