🤖 AI

Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

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

मूल लेखक: Meghyn Bienvenu, Camille Bourgaux, Robin Jean

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

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

CC BY 4.0

मूल लेखक: Meghyn Bienvenu, Camille Bourgaux, Robin Jean

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

पूर्ण तर्क की अस्त-व्यस्त वास्तविकता

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

आमतौर पर, इन पहेलियों को पूर्ण बनाने के लिए डिज़ाइन किया जाता है। यदि नियम और तथ्य आपस में नहीं टकराते हैं, तो कंप्यूटर आसानी से आपके द्वारा पूछे गए किसी भी प्रश्न का उत्तर दे सकता है। लेकिन वास्तविक दुनिया में, डेटा अस्त-व्यस्त होता है। कभी-कभी तथ्य नियमों के साथ विरोधाभास करते हैं, या दो तथ्य एक-दूसरे से लड़ते हैं। पुराने तरीके में, यदि कंप्यूटर को एक भी छोटा सा विरोधाभास मिलता था, तो वह अपने डिजिटल हाथ ऊपर उठा देता था और कहता था, "मैं हार मानता हूँ! चूंकि सब कुछ टूट गया है, इसलिए कुछ भी सच हो सकता है।" यह एक समस्या है क्योंकि इसका मतलब है कि कंप्यूटर आपको उपयोगी उत्तर देना बंद कर देता है।

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

टूटी हुई पहेलियों के लिए 'प्राइस टैग' दृष्टिकोण

इस शोध पत्र में, लेखक इन अस्त-व्यस्त, असंगत नॉलेज बेसों के लिए प्रश्न पूछने का एक चतुर नया तरीका पेश करते हैं। पहेली को पूर्ण बनाने की कोशिश करने के बजाय, वे इसे एक खेल की तरह मानते हैं जहाँ आप नियमों को तोड़ सकते हैं, लेकिन हर बार जब आप ऐसा करते हैं, तो आपको जुर्माना भरना पड़ता है।

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

कंप्यूटर फिर डेटा की व्याख्या करने के सभी संभावित तरीकों को देखता है। कुछ व्याख्याओं में कुछ नरम नियमों को तोड़ना पड़ सकता है, जिससे थोड़ी लागत आएगी। अन्य में कई नियमों को तोड़ना पड़ सकता है, जिससे भारी खर्च होगा। कंप्यूटर प्रत्येक संभावित परिदृश्य के लिए "कुल लागत" की गणना करता है।

लेखक इस लागत के आधार पर उत्तर खोजने के दो मुख्य तरीके परिभाषित करते हैं:

"बेस्ट डील" (सबसे अच्छी डील) दृष्टिकोण: कंप्यूटर केवल उन परिदृश्यों को देखता है जिनमें पैसे की बिल्कुल न्यूनतम लागत आती है। यह पूछता है, "इस अव्यवस्था को समझने का सबसे सस्ता और सबसे कुशल तरीका क्या है?"
"बजट" दृष्टिकोण: कंप्यूटर एक खर्च की सीमा (बजट) निर्धारित करता है। यह पूछता है, "उस किसी भी परिदृश्य में क्या सच है जो इस बजट के भीतर रहता है?" यह तब उपयोगी होता है जब आप जानना चाहते हैं कि कौन से उत्तर "मजबूत" (robust) हैं—अर्थात, वे सच रहते हैं भले ही आप डेटा को ठीक करने के लिए थोड़ा अतिरिक्त भुगतान करने को तैयार हों।

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

उनके निष्कर्ष अच्छे समाचार और "यह निर्भर करता है" का मिश्रण हैं। उन्होंने सिद्ध किया कि सबसे जटिल प्रकार के तर्क के लिए, उत्तर निकालना कंप्यूटर के लिए अविश्वसनीय रूप से कठिन है—यह समस्याओं के एक ऐसे वर्ग में है जिसे हल करने में डेटा बढ़ने के साथ घातांकीय (exponential) समय लग सकता है। हालांकि, कई वास्तविक दुनिया के अनुप्रयोगों में उपयोग किए जाने वाले सरल, अधिक सामान्य प्रकार के तर्क के लिए, समस्या प्रबंधनीय है, हालांकि अभी भी कठिन है। उन्होंने यह भी खोजा कि आप "लागत" को कैसे लिखते हैं (चाहे आप एक साधारण गिनती का उपयोग करें या एक बड़ी संख्या का) यह समस्या को कंप्यूटर के लिए कितना कठिन बनाता है।

महत्वपूर्ण रूप से, लेखक दिखाते हैं कि यह नया तरीका केवल एक अनुमान नहीं है; यह एक गणितीय रूप से प्रमाणित ढांचा है। उन्होंने प्रदर्शित किया कि यदि आपका डेटा संयोग से पूर्ण है (कोई विरोधाभास नहीं है), तो उनकी विधि आपको पारंपरिक, पूर्ण विधियों के समान ही उत्तर देगी। लेकिन जब डेटा टूटा हुआ होता है, तो उनकी विधि उत्तरों की एक रैंक सूची देती है: कुछ "निश्चित" हैं (जो सबसे सस्ते, सर्वोत्तम परिदृश्यों में दिखाई देते हैं) और कुछ "संभावित" हैं (जो कम से कम एक सस्ते परिदृश्य में दिखाई देते हैं)।

संक्षेप में, यह शोध पत्र कंप्यूटरों को यह कहने के लिए एक गणितीय टूलकिट प्रदान करता है कि, "ठीक है, डेटा अस्त-व्यस्त है, लेकिन यदि हम कम महत्वपूर्ण गलतियों को अनदेखा कर दें, तो सबसे अधिक संभावना वाला सच यह है।" यह एक "सिस्टम क्रैश" को एक "मोलभाव" (negotiation) में बदल देता है, जिससे हम उपयोगी उत्तर प्राप्त कर सकते हैं भले ही हमारे पास मौजूद जानकारी कितनी भी अपूर्ण क्यों न हो।

तकनीकी सारांश: असंगत भारित ज्ञान आधारों (Weighted Knowledge Bases) के लिए लागत-आधारित अर्थविज्ञान (Cost-Based Semantics)

समस्या विवरण
ऑन्टोलॉजी-मध्यस्थता वाले क्वेरी उत्तर (OMQA) डिस्क्रिप्शन लॉजिक (DL) ज्ञान आधारों (KBs) पर निर्भर करते हैं, जो एक TBox (ऑन्टोलॉजी) और एक ABox (डेटा) से मिलकर बने होते हैं। शास्त्रीय OMQA अर्थविज्ञान, जो फर्स्ट-ऑर्डर लॉजिक पर आधारित है, असंगत ज्ञान आधारों के मामले में सूचनात्मक उत्तर प्रदान करने में विफल रहता है, क्योंकि एक विरोधाभास से सब कुछ सिद्ध (entailed) हो जाता है। जबकि मौजूदा दृष्टिकोण मरम्मत (repairs) (जैसे, AR और ब्रेव सेमेंटिक्स) के माध्यम से असंगति को संभालते हैं, वे आमतौर पर यह मान लेते हैं कि TBox विश्वसनीय है और केवल ABox में संशोधन करते हैं। इसके अतिरिक्त, मानक मरम्मत अर्थविज्ञान अक्सर सभी कथनों को समान रूप से विश्वसनीय मानते हैं या कार्डिनैलिटी-आधारित अधिकतमता (maximality) पर निर्भर करते हैं, जिसमें विश्वास के विभिन्न स्तरों के आधार पर संघर्षपूर्ण जानकारी को प्राथमिकता देने का सूक्ष्म तरीका नहीं होता है।

यह शोध पत्र एक मात्रात्मक ढांचे (quantitative framework) को पेश करके असंगत DL KBs को क्वेरी करने की चुनौती को संबोधित करता है। मुख्य समस्या यह परिभाषित करना है कि सार्थक निश्चित (certain) और संभावित (possible) उत्तर क्या हैं, जब TBox एक्सिओम्स और ABox कथनों दोनों का उल्लंघन किया जा सकता है, जहाँ उल्लंघनों को निर्धारित भार (weights) के अनुसार दंडित किया जाता है।

कार्यप्रणाली और ढांचा
लेखक एक भारित ज्ञान आधार (Weighted Knowledge Base - WKB) ढांचे का प्रस्ताव करते हैं, जिसे $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$ द्वारा दर्शाया गया है।

भार (Weights): एक लागत फलन (cost function) $\omega$ , $\mathcal{T}$ के प्रत्येक एक्सिओम और $\mathcal{A}$ के प्रत्येक कथन को $\mathbb{N}_{>0} \cup \{+\infty\}$ में एक मान निर्दिष्ट करता है। अनंत भार "कठोर" बाधाओं (hard constraints) का प्रतिनिधित्व करते जिन्हें संतुष्ट किया जाना चाहिए, जबकि परिमित भार "कोमल" बाधाओं (soft constraints) का प्रतिनिधित्व करते हैं जहाँ उच्च मान अधिक विश्वसनीयता का संकेत देते हैं।
व्याख्या (Interpretation) की लागत: एक व्याख्या $I$ की लागत, उल्लंघन किए गए सभी एक्सिओम्स और कथनों के भार के योग के रूप में परिभाषित है। विशेष रूप से, एक कॉन्सेप्ट इंक्लूजन $\tau$ के लिए, लागत $\omega_\tau \times |vio_\tau(I)|$ शामिल है, जहाँ $vio_\tau(I)$ डोमेन तत्वों का वह सेट है जो समावेश का उल्लंघन करता है। कथनों का उल्लंघन अधिकतम एक बार ही किया जा सकता है।
अर्थविज्ञान (Semantics): शोध पत्र लागत के आधार पर चार क्वेरी एंटेलमेंट अर्थविज्ञान को परिभाषित करता है:
1. $k$ -cost-bounded certain ( $K_\omega \models^k_c q$ ): $q$ उन सभी व्याख्याओं में सत्य है जिनका लागत $\le k$ है।
2. $k$ -cost-bounded possible ( $K_\omega \models^k_p q$ ): $q$ कम से कम एक ऐसी व्याख्या में सत्य है जिसकी लागत $\le k$ है।
3. Opt-cost certain ( $K_\omega \models^{opt}_c q$ ): $q$ न्यूनतम लागत ( $optc(K_\omega)$ ) वाली सभी व्याख्याओं में सत्य है।
4. Opt-cost possible ( $K_\omega \models^{opt}_p q$ ): $q$ कम से कम एक ऐसी व्याख्या में सत्य है जिसकी लागत न्यूनतम है।

यह ढांचा मौजूदा मरम्मत अर्थविज्ञान का सामान्यीकरण करता है। विशेष रूप से, जब TBox एक्सिओम्स के भार अनंत होते हैं, तो opt-cost certain अर्थविज्ञान $\le_\omega$ -AR सेमिantics (Bienvenu, Bourgaux, own and Goasdoué 2014) के साथ मेल खाता है, जो उन मरम्मतों का चयन करता है जो बरकरार रखे गए कथनों के भार के योग को अधिकतम करते हैं।

मुख्य योगदान
प्राथमिक योगदान इस सेटिंग में मुख्य निर्णय समस्याओं की संयुक्त और डेटा जटिलता (combined and data complexity) का एक व्यापक विश्लेषण है:

बाउंडेड कॉस्ट सैटिस्फिएबिलिटी (BCS): यह निर्धारित करना कि क्या लागत $\le k$ वाली कोई व्याख्या मौजूद है।
निश्चित और संभावित उत्तर पहचान (Certain and Possible Answer Recognition): परिभाषित किए गए चार अर्थविज्ञान के तहत एंटेलमेंट को तय करना।

अध्ययन $\mathcal{EL}^\bot$ से लेकर अभिव्यंजक $\mathcal{ALCO}$ (और ऊपरी सीमा प्रमाणों के लिए $\mathcal{ALCO}^\mathcal{Q}$ तक) के डिस्क्रिप्शन लॉजिक की एक श्रृंखला को कवर करता है, जो इंस्टेंस क्वेरीज (IQs) और कंजंक्टिव क्वेरीज (CQs) दोनों को संभालता है।

जटिलता परिणाम
शोध पत्र कड़े जटिलता बाउंड स्थापित करता है, जो इस प्रकार है:

संयुक्त जटिलता (Combined Complexity):
- अधिकांश समस्याएं EXPTIME-complete हैं।
- CQs के लिए निश्चित उत्तर पहचान (दोनों bounded और opt-cost) 2EXPTIME-complete है। यह उच्च जटिलता एक विशिष्ट लागत के सभी मॉडलों में एंटेलमेंट को सत्यापित करने की आवश्यकता से उत्पन्न होती है, जो सर्कमस्क्राइब्ड (circumscribed) KBs से संबंधित है।
- ये बाउंड तब भी लागू होते हैं जब भार और लागत सीमा $k$ को बाइनरी में एनकोड किया जाता है।
डेटा जटिलता (Data Complexity):
- बाउंडेड कॉस्ट सैटिस्फिएबिलिटी (BCS): NP-complete।
- बाउंडेड कॉस्ट अनसरिंग (IQs/CQs): NP-complete (संभावित) और coNP-complete (निश्चित)।
- इष्टतम लागत अनसरिंग (Optimal Cost Answering): जटिलता भार के एनकोडिंग पर बहुत अधिक निर्भर करती है:
  - यदि भार unary में एनकोड किए गए हैं या ABox के आकार से स्वतंत्र रूप से सीमित हैं, तो समस्याएं $\Theta^p_2$ -complete हैं (एक NP ऑरेकल के लॉगरिदमिक कॉल्स के साथ बहुपद समय में हल करने योग्य)।
  - यदि भार binary में एनकोड किए गए हैं और ABox के आकार के सापेक्ष घातीय (exponential) हो सकते हैं, तो समस्याएं $\Delta^p_2$ -complete हो जाती हैं (एक NP ऑरेकल तक पहुंच के साथ बहुपद समय में हल करने योग्य)।
- शोध पत्र नोट करता है कि बाइनरी भारों के साथ opt-cost certain अर्थविज्ञान के लिए, ऊपरी सीमा खुली है, हालांकि निचले बाउंड $\Delta^p_2$ -hard हैं।

महत्व और दावे
लेखक दावा करते हैं कि वे लागत-आधारित अर्थविज्ञान के तहत असंगत KBs के लिए क्वेरी करने के जटिलता परिदृश्य की एक "लगभग पूर्ण तस्वीर" प्रदान करते हैं। इस कार्य का महत्व निम्नलिखित में निहित है:

मात्रात्मक लचीलापन (Quantitative Flexibility): बाइनरी निरंतरता से आगे बढ़कर एक श्रेणीबद्ध दृष्टिकोण अपनाना, जहाँ उत्तरों को उनकी "मजबूती" (अर्थात, क्या वे इष्टतम लागत के करीब की व्याख्याओं में सत्य हैं) के आधार पर रैंक या फ़िल्टर किया जा सकता है।
सामान्यीकरण (Generalization): डेटाबेस में सॉफ्ट कंस्ट्रेंट्स (Carmeli et al. 2021) और ऑन्टोलॉजी में भारित मरम्मत की अवधारणाओं को एकीकृत करना, यह दिखाना कि इष्टतम-लागत अर्थविज्ञान पसंदीदा मरम्मत अर्थविज्ञान का स्वाभाविक रूप से सामान्यीकरण करता है।
तकनीकी गहराई (Technical Depth): जटिलता प्रमाण DL रीजनिंग की उन्नत तकनीकों का लाभ उठाते हैं और उन्हें अनुकूलित करते हैं, जिनमें शामिल हैं:
- ऊपरी सीमा स्थापित करने के लिए फिल्ट्रेशन (Filtration) और बाउंड मॉडल गुण।
- निचले बाउंड स्थापित करने के लिए कार्डिनैलिटी क्वेरी अनसरिंग और सर्कमस्क्राइब्ड KBs से रिडक्शन।
- भारित उल्लंघनों के विशिष्ट बाधाओं को संभालने के लिए काउंटिंग क्वेरी साहित्य (Manière 2022) से "इंटरलेसिंग" और "क्वोटिएंट" निर्माणों का अनुकूलन।

शोध पत्र भविष्य की दिशाओं को पहचानते हुए समाप्त होता है, विशेष रूप से इनवर्स रोल्स, रोल इंक्लूजन और फंक्शनल रोल्स (जैसे, DL-Lite परिवार) वाले DLs के लिए इन परिणामों के विस्तार को, यह नोट करते हुए कि ऊपरी सीमाओं के लिए वर्तमान तकनीकें इन कंस्ट्रक्ट्स में आसानी से स्थानांतरित नहीं होती हैं। यह व्यावहारिक कार्यान्वयन के लिए व्यावहारिक एल्गोरिदम विकसित करने की चुनौती को भी रेखांकित करता है।

पूर्ण तर्क की अस्त-व्यस्त वास्तविकता

टूटी हुई पहेलियों के लिए 'प्राइस टैग' दृष्टिकोण

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