🤖 AI

Diversity of Extensions in Abstract Argumentation

यह शोधपत्र सिमेट्रिक डिफरेंस (symmetric difference) पर आधारित एब्स्ट्रैक्ट आर्गुमेंटेशन फ्रेमवर्क्स में एक्सटेंशन डाइवर्सिटी (extension diversity) की एक मात्रात्मक अवधारणा प्रस्तुत करता है, संबंधित निर्णय और अनुकूलन समस्याओं के लिए एक व्यवस्थित जटिलता वर्गीकरण प्रदान करता है, और डाइवर्सिटी स्तरों की गणना करने के लिए एक प्रोटोटाइप मूल्यांकन प्रस्तुत करता है।

मूल लेखक: Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang

प्रकाशित 2026-05-14

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

CC BY 4.0

मूल लेखक: Johannes K. Fichte, Markus Hecher, Yasir Mahmood, Zhengjun Wang

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

कल्पना कीजिए कि आप एक जटिल पहेली को हल करने की कोशिश कर रहे हैं, जैसे कि किसी चिकित्सा उपचार पर निर्णय लेना या किसी शहर के लिए नीति चुनना। आर्टिफिशियल इंटेलिजेंस की दुनिया में, इसे अक्सर एब्स्ट्रैक्ट आर्गुमेंटेशन (Abstract Argumentation) का उपयोग करके मॉडल किया जाता है। इसे विचारों (तर्कों) के एक विशाल मानचित्र के रूप में समझें जहाँ कुछ विचार दूसरों पर हमला करते हैं या विरोध करते हैं।

आमतौर पर, जब कंप्यूटर इन पहेलियों को हल करते हैं, तो वे एक या अधिक समाधान (जिन्हें एक्सटेंशन/extensions कहा जाता है) खोज लेते हैं। प्रत्येक समाधान विचारों का एक सुसंगत सेट है जो आपस में बिना लड़े एक साथ रह सकते हैं। यदि कई समाधान हैं, तो इसका अर्थ है कि एक ही स्थिति को देखने के कई वैध तरीके मौजूद हैं।

समस्या: "ये समाधान कितने अलग हैं?"
अब तक, यदि किसी कंप्यूटर को तीन अलग-अलग समाधान मिलते थे, तो वह आपको यह तो बता सकता था कि वे क्या थे, लेकिन वह आसानी से यह नहीं बता पाता था कि वे एक-दूसरे से कितने दूर हैं।

क्या समाधान A और समाधान B थोड़े अलग हैं (जैसे लाल शर्ट बनाम नीली शर्ट चुनना)?
या क्या वे पूरी तरह से असंगत हैं (जैसे बर्गर खाने का निर्णय लेना बनाम भूखा रहने का निर्णय लेना)?

मौजूदा तरीके इस "दूरी" को प्रभावी ढंग से नहीं माप सके।

नया विचार: "विविधता" को मापना
यह शोध पत्र पेश करता है कि ये समाधान एक-दूसरे से वास्तव में कितने भिन्न हैं। लेखक इसके लिए सिमेट्रिक डिफरेंस (Symmetric Difference) नामक एक गणितीय अवधारणा का उपयोग करते हैं।

रचनात्मक उपमा: "स्वैप" (बदलने) की गिनती
कल्पना कीजिए कि आपके पास किराने के सामान की दो सूचियाँ हैं:

सूची A: दूध, अंडे, ब्रेड, सेब।
सूची B: दूध, अंडे, ब्रेड, केले।

इन दोनों के बीच "विविधता" खोजने के लिए, आप देखते हैं कि कौन सी चीज़ एक सूची में है लेकिन दूसरी में नहीं है।

सूची A में सेब है (सूची B में नहीं)।
सूची B में केले हैं (सूची A में नहीं)।
वे दूध, अंडे और ब्रेड साझा करते हैं।

यहाँ "विविधता स्कोर" 2 है (सेब और केले)। यदि सूचियाँ बिल्कुल समान होतीं, तो स्कोर 0 होता। यदि उनमें कुछ भी साझा नहीं होता, तो स्कोर कुल वस्तुओं की संख्या के बराबर होता।

लेखक इस पद्धति को अपने तर्क मानचित्रों पर लागू करते हैं। वे पूछते हैं: "यदि हम दो अलग-अलग वैध दृष्टिकोणों को लें, तो एक को दूसरे में बदलने के लिए हमें कितने तर्कों को बदलना (swap) पड़ेगा?"

कम विविधता (Low Diversity): दृष्टिकोण बहुत समान हैं; वे ज्यादातर सहमत हैं, बस मामूली बदलाव हैं।
उच्च विविधता (High Diversity): दृष्टिकोण मौलिक रूप से भिन्न हैं; वे पूरी तरह से अलग तर्क पर आधारित हैं।

यह क्यों मायने रखता है?
यह शोध पत्र एक चिकित्सा निर्णय के उदाहरण का उपयोग करता है (टेक्स्ट में चित्र 1)।

विकल्प X: तुरंत उपचार X शुरू करें।
विकल्प Y: तुरंत उपचार Y शुरू करें।
विकल्प W: अधिक डेटा के लिए प्रतीक्षा करें।

लेखकों ने पाया कि विकल्प X और विकल्प Y बहुत विविध थे (उनके बीच लगभग कोई साझा तर्क नहीं था)। हालांकि, विकल्प X और विकल्प W कम विविध थे (उनके बीच कुछ साझा तर्क थे)।
यह निर्णय लेने वालों को वास्तविक समझौतों (trade-offs) को समझने में मदद करता है। यदि आप केवल एक समाधान देखते हैं, तो आप इस तथ्य को मिस कर सकते हैं कि अन्य विकल्प मौलिक रूप से अलग हैं। उच्च विविधता का अर्थ है गहरा मतभेद; कम विविधता का अर्थ है लगभग सहमति।

उन्होंने वास्तव में क्या किया?

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

उन्होंने क्या दावा नहीं किया

उन्होंने यह दावा नहीं किया कि यह तुरंत बीमारियों को ठीक करेगा या राजनीतिक संकटों को हल करेगा।
उन्होंने यह दावा नहीं किया कि यह ब्रह्मांड के हर एकल तर्क समस्या के लिए काम करता है (उन्होंने "stable," "admissible," और "complete" जैसे विशिष्ट "semantics" पर ध्यान केंद्रित किया)।
उन्होंने सबसे कठिन मामलों के लिए कोई अंतिम, पूर्ण एल्गोरिदम प्रदान नहीं किया; उन्होंने केवल यह पहचाना कि कठिनाई कहाँ है और भविष्य के शोध के लिए कुछ "खुले मामले" (open cases) छोड़ दिए।

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

तकनीकी सारांश: एब्स्ट्रैक्ट आर्गुमेंटेशन में एक्सटेंशन की विविधता (Diversity of Extensions in Abstract Argumentation)

समस्या की परिभाषा

एब्स्ट्रैक्ट आर्गुमेंटेशन मॉडल, आर्गुमेंटेशन फ्रेमवर्क्स (AFs) के माध्यम से तर्क प्रक्रिया (reasoning) को दर्शाते हैं, जिन्हें निर्देशित ग्राफ (directed graphs) के रूप में प्रस्तुत किया जाता है जहाँ नोड्स तर्कों (arguments) का प्रतिनिधित्व करते हैं और किनारे (edges) हमलों (attacks) का प्रतिनिधित्व करते हैं। AF के सिमेंटिक्स (semantics) "एक्सटेंशन" (extensions) को परिभाषित करते हैं—जो कि तर्कों के ऐसे सेट होते हैं जो विशिष्ट सामंजस्य स्थितियों (जैसे, संघर्ष-मुक्तता, ग्राह्यता, स्थिरता) को पूरा करते हैं। जबकि मानक तर्क कार्य एक्सटेंशन के अस्तित्व या व्यक्तिगत तर्कों की स्वीकृति स्थिति (क्रेडुलस या स्केप्टिकल) को निर्धारित करते हैं, वे अक्सर एक्सटेंशन के बीच संरचनात्मक दूरी को मापने में विफल रहते हैं। बातचीत (negotiation) या निर्णय लेने वाले परिदृश्यों में, यह समझना महत्वपूर्ण है कि क्या वैकल्पिक दृष्टिकोण (extensions) मामूली रूप से भिन्न हैं या मौलिक रूप से असंगत हैं। मौजूदा अवधारणाएं, जैसे प्रतिनिधि दृष्टिकोणों का चयन करना या एक्सटेंशन की गिनती करना, पूरे एक्सटेंशन के बीच "विविधता" या असमानता को स्पष्ट रूप से नहीं मापती हैं।

यह शोध पत्र सिमेट्रिक डिफरेंस ( $A \triangle B = (A \cup B) \setminus (A \cap B)$ ) पर आधारित एक्सटेंशन विविधता (extension diversity) की एक मात्रात्मक धारणा पेश करके इस अंतर को संबोधित करता है। मुख्य समस्या यह निर्धारित करना है कि क्या एक AF दो ऐसे एक्सटेंशन को स्वीकार करता है जो ठीक $k$ तर्कों से भिन्न हैं, कम से कम $k$ तर्कों से भिन्न हैं, या अधिकतम $k$ तर्कों से भिन्न हैं, और दिए गए फ्रेमवर्क के लिए अधिकतम संभव विविधता ( $k_{max}$ ) की गणना करना है।

कार्यप्रणाली (Methodology)

लेखक इस समस्या को तीन मुख्य स्तंभों के माध्यम से देखते हैं: औपचारिक परिभाषा, कम्प्यूटेशनल जटिलता विश्लेषण, और प्रयोगात्मक मूल्यांकन।

1. औपचारिक परिभाषाएँ (Formal Definitions)

दो एक्सटेंशन $S$ और $T$ के बीच विविधता को $d(S, T) = |S \triangle T|$ के रूप में परिभाषित किया गया है। शोध पत्र कई निर्णय और अनुकूलन समस्याओं को परिभाषित करता है:

$k$ -Div-Arg $_\sigma$ : दिए गए तर्क $a, b$ , क्या दो $\sigma$ -एक्सटेंशन $S, T$ मौजूद हैं ताकि $a \in S, b \in T$ , और $d(S, T) = k$ ?
$k$ -Div-Ext $_\sigma$ : क्या AF $k$ की दूरी वाले दो $\sigma$ -एक्सटेंशन को स्वीकार करता है?
विविधता के प्रकार (Variants): ये समस्याएँ विविधता $\ge k$ और $\le k$ के लिए भी परिभाषित की गई हैं, साथ ही अधिकतम $k$ ($max$- $k$ -Div) खोजने के लिए अनुकूलन समस्याएँ भी दी गई हैं।

2. जटिलता विश्लेषण (Complexity Analysis)

शोध पत्र विभिन्न सिमेंटिक्स के तहत इन समस्याओं के लिए कम्प्यूटेशनल जटिलता का एक व्यवस्थित वर्गीकरण प्रदान करता है:

कॉन्फ्लिक्ट-फ्री (Conflict-free) और नैइव (Naive) सिमेंटिक्स: समस्याएँ आम तौर पर NP-complete हैं। विशेष रूप से, जबकि मानक तर्क (जैसे, एक्सटेंशन अस्तित्व) संघर्ष-मुक्त सिमेंटिक्स के लिए बहुपद समय (polynomial time) में होता है, विविधता निर्धारित करना NP-hard है।
एडमिसेबल (Admissible), कम्प्लीट (Complete), और स्टेबल (Stable) सिमेंटिक्स: जटिलता क्रेडुलस स्वीकृति (credulous acceptance) के अनुरूप है, जो NP-complete बनी रहती है।
सेमी-स्टेबल (Semi-stable), स्टेज (Stage), और प्रेफर्ड (Preferred) सिमेंटिक्स: ये उच्च-स्तरीय सिमेंटिक्स विशिष्ट तर्कों और एक्सटेंशन से जुड़ी निर्णय समस्याओं के लिए जटिलता को बढ़ाकर $\Sigma_2^P$ -complete कर देते हैं।
अधिकतम विविधता (Maximal Diversity): निचले स्तर के सिमेंटिक्स के लिए सटीक अधिकतम विविधता थ्रेशोल्ड निर्धारित करना DP-complete और सेमी-स्टेबल एवं स्टेज सिमेंटिक्स के लिए DP $_2$ -complete दिखाया गया है। इसमें $k$ विविधता वाले समाधान की उपस्थिति और $k$ से अधिक विविधता वाले समाधानों की अनुपस्थिति दोनों की जांच शामिल है।

लेखक इन हार्डनेस परिणामों को स्थापित करने के लिए मानक जटिलता समस्याओं (3SAT, डोमिनेटिंग सेट, SAT-UNSAT, और क्वांटिफाइड बुलियन फॉर्मूला) से रिडक्शन (reductions) का उपयोग करते हैं।

3. प्रयोगात्मक मूल्यांकन (Experimental Evaluation)

एक प्रोटोटाइप कार्यान्वयन एन्सर सेट प्रोग्रामिंग (ASP) और सॉल्वर ASPARTIX का उपयोग करके विकसित किया गया। यह प्रणाली AFs के लिए न्यूनतम और अधिकतम विविधता मानों की गणना करती है। प्रयोग ICCMA 2025 बेंचमार्क सुइट (जो $\le 1000$ तर्कों वाले फ्रेमवर्क तक सीमित है) से 270 इंस्टेंस पर एडमिसेबल, कम्प्लीट और स्टेबल सिमेंटिक्स के तहत आयोजित किए गए थे।

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

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

परिणाम (Results)

जटिलता: अध्ययन से पता चलता है कि विविधता तर्क समान रूप से आसान नहीं है। कॉन्फ्लिक्ट-फ्री सिमेंटिक्स के लिए, यह NP-complete है, जो मानक एक्सटेंशन अस्तित्व की बहुपद-समय समाधान क्षमता के विपरीत है। सेमी-स्टेबल और स्टेज सिमेंट्स के लिए, समस्या पॉलीनोमियल हाइरार्की के दूसरे स्तर ( $\Sigma_2^P$ ) पर पहुँच जाती है।
प्रयोगात्मक निष्कर्ष: प्रयोग संकेत देते हैं कि विविधता मान इंस्टेंस के आधार पर काफी भिन्न होते हैं। जबकि कई फ्रेमवर्क के ऐसे एक्सटेंशन होते हैं जो संरचनात्मक रूप से करीब होते हैं (कम विविधता), एक उपसमूह ऐसे एक्सटेंशन को स्वीकार करता है जो मौलिक रूप से भिन्न होते हैं (उच्च विविधता)। परीक्षण किए गए इंस्टेंस के लिए अधिकतम विविधता की गणना करने का औसत रनटाइम आमतौर पर 2 सेकंड से कम था, जो मध्यम-स्तर की समस्याओं के लिए व्यावहारिक व्यवहार्यता का सुझाव देता है।
गैर-मोनोटोनिसिटी (Non-Monotonicity): लेखक नोट करते हैं कि विविधता न तो मोनोटोनिक है और न ही एंटी-मोनोटोनिक, जिसका अर्थ है कि फ्रेमवर्क में तर्क जोड़ने से अधिकतम विविधता का पूर्वानुमानित रूप से बढ़ना या घटना तय नहीं है।

महत्व और दावे (Significance and Claims)

शोध पत्र का दावा है कि इसका प्राथमिक योगदान यह स्पष्ट करना है कि AF में वैकल्पिक, आंतरिक रूप से सुसंगत दृष्टिकोण कितनी मजबूती से भिन्न होते हैं। केवल स्वीकृति या गिनती से आगे बढ़कर, यह मात्रात्मक माप तर्कसंगत स्थितियों के सूक्ष्म विश्लेषण के लिए एक बेहतर विश्लेषण प्रदान करता है।

लेखक इस कार्य को निम्नलिखित के लिए एक उपकरण के रूप में देखते हैं:

बातचीत और निर्णय लेना (Negotiation and Decision Making): यह पहचानना कि क्या असहमति सतही (कम विविधता) है या मौलिक (उच्च विविधता) है।
मजबूती विश्लेषण (Robustness Analysis): उच्च विविधता कम मजबूती का संकेत देती है, क्योंकि फ्रेमवर्क रेडिकल रूप से अलग स्थितियों का समर्थन करता है।
भावी दिशाएँ: लेखक विनम्रतापूर्वक सुझाव देते हैं कि इस धारणा को लॉजिक-आधारित आर्गुमेंटेशन में विस्तारित किया जा सकता है और नॉलेज बेस में सुसंगत क्वेरी अनswering के लिए लागू किया जा सकता है, लेकिन वे यह दावा नहीं करते हैं कि ये अनुप्रयोग वर्तमान में साकार हैं। वे ओपन कॉम्प्लेक्सिटी केस (जैसे, मिनिमल विविधता) और पैरामीटराइज्ड कॉम्प्लेक्सिटी दृष्टिकोणों के लिए संभावित भविष्य के कार्य के रूप में भी पहचान करते हैं।

शोध पत्र निष्कर्ष निकालता है कि हालांकि कुछ सिमेंटिक्स के लिए कम्प्यूटेशनल लागत अधिक हो सकती है, लेकिन दृष्टिकोणों के बीच "दूरी" को मापने की क्षमता एब्स्ट्रक्ट आर्गुमेंटेशन के विश्लेषण के लिए एक मूल्यवान नया आयाम प्रदान करती है।