योगोत्पादी तर्क प्रोग्रामन (एबडक्टिव लॉजिक प्रोग्रामिंग)

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

सिंटेक्स

अपहरणात्मक तर्क कार्यक्रमों के तीन घटक होते हैं, $\langle P,A,IC\rangle ,$ कहाँ:

• P ठीक उसी रूप का एक लॉजिक प्रोग्राम है जैसा लॉजिक प्रोग्रामिंग में होता है
• A विधेय नामों का एक समूह है, जिसे अपवर्तक विधेय कहा जाता है
• आईसी प्रथम क्रम शास्त्रीय सूत्रों का एक सेट है।

आम तौर पर, तर्क कार्यक्रम पी में कोई खंड नहीं होता है जिसका सिर (या निष्कर्ष) एक अपवर्तक विधेय को संदर्भित करता है। (यह प्रतिबंध व्यापकता के नुकसान के बिना बनाया जा सकता है।) साथ ही व्यवहार में, कई बार, आईसी में अखंडता की कमी अक्सर इनकार के रूप तक ही सीमित होती है, यानी प्रपत्र के खंड:

   असत्य:- A1,...,An, B1 नहीं, ..., Bm नहीं।

इस तरह की बाधा का अर्थ है कि यह संभव नहीं है कि सभी A1,...,An सत्य हों और साथ ही सभी B1,...,Bm असत्य हों।

अनौपचारिक अर्थ और समस्या समाधान

पी में खंड गैर-अपहरण योग्य विधेय के एक सेट को परिभाषित करते हैं और इसके माध्यम से वे समस्या डोमेन का विवरण (या मॉडल) प्रदान करते हैं। आईसी में अखंडता बाधाएं समस्या डोमेन के सामान्य गुणों को निर्दिष्ट करती हैं जिन्हें किसी समस्या के किसी भी समाधान में सम्मानित करने की आवश्यकता होती है।

एक समस्या, जी, जो या तो एक अवलोकन व्यक्त करती है जिसे समझाया जाना चाहिए या वांछित लक्ष्य, सकारात्मक और नकारात्मक (एनएएफ) अक्षर के संयोजन द्वारा दर्शाया जाता है। इस तरह की समस्याओं को जी के अपवर्तक स्पष्टीकरण की गणना करके हल किया जाता है।

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

एएलपी में संगणना सामान्य तर्क प्रोग्रामिंग (समस्याओं को उप-समस्याओं में कम करने के लिए) के पिछड़े तर्क को एक तरह की अखंडता जांच के साथ जोड़ती है ताकि यह दिखाया जा सके कि अपहरण की व्याख्याएं अखंडता की कमी को पूरा करती हैं।

निम्नलिखित दो उदाहरण, एएलपी के सख्त वाक्य-विन्यास के बजाय सरल संरचित अंग्रेजी में लिखे गए हैं, एएलपी में अपहरणात्मक स्पष्टीकरण की धारणा और समस्या समाधान के संबंध में इसका वर्णन करते हैं।

उदाहरण 1

अपहरण तर्क कार्यक्रम, $\langle P,A,{\mathit {IC}}\rangle$, में है $P$ निम्नलिखित वाक्य:

  बारिश हुई तो घास भीगी है।

  अगर स्प्रिंकलर चालू है तो घास गीली है।

  सूर्य चमक रहा था।

abducible में भविष्यवाणी करता है $A$ क्या बारिश हो रही है और स्प्रिंकलर चालू है और एकमात्र अखंडता बाधा है ${\mathit {IC}}$ है:

  झूठा अगर बारिश हुई और सूरज चमक रहा था।

अवलोकन कि घास गीली है, के दो संभावित स्पष्टीकरण हैं, बारिश हुई और स्प्रिंकलर चालू था, जो अवलोकन को आवश्यक बनाता है। हालाँकि, केवल दूसरा संभावित स्पष्टीकरण, स्प्रिंकलर चालू था, अखंडता की कमी को पूरा करता है।

उदाहरण 2

निम्नलिखित (सरलीकृत) खंडों से मिलकर अपहृत तर्क कार्यक्रम पर विचार करें:

  यदि X अमेरिका में पैदा हुआ है तो X एक नागरिक है।

  X एक नागरिक है यदि X संयुक्त राज्य अमेरिका के बाहर पैदा हुआ है और X संयुक्त राज्य अमेरिका का निवासी है और X देशीयकृत है।

  X एक नागरिक है यदि X का जन्म संयुक्त राज्य अमेरिका के बाहर हुआ है और Y, X की माँ है और Y एक नागरिक है और X पंजीकृत है।

  मैरी जॉन की मां है।

  मैरी एक नागरिक है।

संयुक्त राज्य अमेरिका में पैदा हुआ है, संयुक्त राज्य अमेरिका के बाहर पैदा हुआ है, संयुक्त राज्य अमेरिका का निवासी है, देशीयकृत है और पंजीकृत है और अखंडता बाधा है:

  झूठा अगर जॉन यूएसए का निवासी है।

जॉन के नागरिक होने के लक्ष्य के दो अपहरणात्मक समाधान हैं, जिनमें से एक जॉन यूएसए में पैदा हुआ है, जिसमें से दूसरा जॉन यूएसए के बाहर पैदा हुआ है और जॉन पंजीकृत है। निवास और प्राकृतिककरण द्वारा नागरिक बनने का संभावित समाधान विफल हो जाता है क्योंकि यह अखंडता की बाधा का उल्लंघन करता है।

एक अधिक जटिल उदाहरण जो ALP के अधिक औपचारिक सिंटैक्स में भी लिखा गया है, वह निम्नलिखित है।

उदाहरण 3

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

डोमेन ज्ञान (पी)

   feed(lactose) :- make(permease), make(galactosidase).
   make(Enzyme) :- code(Gene, Enzyme), express(Gene).
   express(lac(X)) :- amount(glucose, low), amount(lactose, hi).
   express(lac(X)) :- amount(glucose, medium), amount(lactose, medium).
   code(lac(y), permease).
   code(lac(z), galactosidase).
   temperature(low) :- amount(glucose, low).

अखंडता की कमी (आईसी)

   false :- amount(S, V1), amount(S, V2), V1 ≠ V2.

अपहरण योग्य (ए)

   abducible_predicate(amount).

समस्या लक्ष्य है $G={\text{feed(lactose)}}$. यह या तो व्याख्या किए जाने वाले अवलोकन के रूप में उत्पन्न हो सकता है या किसी योजना की खोज करके प्राप्त की जाने वाली स्थिति के रूप में हो सकता है। इस लक्ष्य की दो अपहरणात्मक व्याख्याएँ हैं:

${\begin{cases}\Delta _{1}=\{{\text{amount(lactose, hi), amount(glucose, low)}}\}\\\Delta _{2}=\{{\text{amount(lactose, medium), amount(glucose, medium)}}\}\end{cases}}$

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

एक बार स्पष्टीकरण का चयन हो जाने के बाद, यह सिद्धांत का हिस्सा बन जाता है, जिसका उपयोग नए निष्कर्ष निकालने के लिए किया जा सकता है। स्पष्टीकरण और आम तौर पर ये नए निष्कर्ष समस्या का समाधान बनाते हैं।

औपचारिक शब्दार्थ

एएलपी में अपहरणात्मक स्पष्टीकरण की केंद्रीय धारणा के औपचारिक शब्दों को निम्नलिखित तरीके से परिभाषित किया जा सकता है।

एक अपहरणात्मक तर्क कार्यक्रम को देखते हुए, $\langle P,A,{\mathit {IC}}\rangle$, एक समस्या के लिए एक अपहरणात्मक स्पष्टीकरण $G$ एक सेट है $\Delta$ abducible विधेय पर जमीन के परमाणुओं की संख्या जैसे कि:

• $P\cup \Delta \models G$
• $P\cup \Delta \models IC$
• $P\cup \Delta$ संगत है

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

उपरोक्त परिभाषा अखंडता बाधाओं की भूमिका की औपचारिकता पर एक विशेष दृष्टिकोण लेती है ${\mathit {IC}}$ संभावित अपहरण समाधान पर प्रतिबंध के रूप में। इसके लिए आवश्यक है कि ये एक अपहरणात्मक समाधान के साथ विस्तारित तर्क कार्यक्रम द्वारा उलझाए गए हैं, इस प्रकार इसका अर्थ है कि विस्तारित तर्क कार्यक्रम के किसी भी मॉडल में (जिसे कोई आने वाली दुनिया के रूप में सोच सकता है) $\Delta$) अखंडता बाधाओं की आवश्यकताओं को पूरा किया जाता है। कुछ मामलों में यह अनावश्यक रूप से मजबूत हो सकता है और निरंतरता की कमजोर आवश्यकता, अर्थात् $P\cup {\mathit {IC}}\cup \Delta$ सुसंगत है, पर्याप्त हो सकता है, जिसका अर्थ है कि विस्तारित कार्यक्रम का कम से कम एक मॉडल (संभावित आगामी दुनिया) मौजूद है जहां अखंडता की कमी है। व्यवहार में, कई मामलों में अखंडता की भूमिका को औपचारिक रूप देने के ये दो तरीके तर्क कार्यक्रम के रूप में मेल खाते हैं और इसके विस्तार में हमेशा एक अनूठा मॉडल होता है। कई ALP प्रणालियाँ अखंडता बाधाओं के प्रवेश दृश्य का उपयोग करती हैं क्योंकि इसे अखंडता बाधाओं की संतुष्टि के लिए किसी अतिरिक्त विशेष प्रक्रियाओं की आवश्यकता के बिना आसानी से लागू किया जा सकता है क्योंकि यह दृष्टिकोण समस्या लक्ष्य के समान ही बाधाओं का इलाज करता है। कई व्यावहारिक मामलों में एएलपी में एक अपहरणात्मक स्पष्टीकरण की इस औपचारिक परिभाषा में तीसरी शर्त या तो तुच्छ रूप से संतुष्ट है या यह दूसरी स्थिति में विशिष्ट अखंडता बाधाओं के उपयोग के माध्यम से निहित है जो स्थिरता को पकड़ती है।

कार्यान्वयन और सिस्टम

एएलपी के अधिकांश कार्यान्वयन तर्क प्रोग्रामिंग के एसएलडी संकल्प-आधारित कम्प्यूटेशनल मॉडल का विस्तार करते हैं। एएलपी को उत्तर सेट प्रोग्रामिंग (एएसपी) के साथ इसके लिंक के माध्यम से भी लागू किया जा सकता है, जहां एएसपी सिस्टम को नियोजित किया जा सकता है। पूर्व दृष्टिकोण के सिस्टम के उदाहरण ACLP, A- सिस्टम, CIFF, SCIFF, ABDUAL और ProLogICA हैं।

यह भी देखें

• आगमनात्मक तर्क प्रोग्रामिंग

संदर्भ

• Poole, D.; Goebel, R.; Aleliunas, R. (1987). "Theorist: a logical reasoning system for defaults and diagnosis". In Cercone, Nick; McCalla, Gordon (eds.). The Knowledge Frontier: Essays in the Representation of Knowledge. Springer. pp. 331–352. ISBN 978-0-387-96557-4.
• Kakas, A.C.; Mancarella, P. (1990). "Generalised Stable Models: A Semantics for Abduction". In Aiello, L.C. (ed.). ECAI 90: proceedings of the 9th European Conference on Artificial Intelligence. Pitman. pp. 385–391. ISBN 978-0273088226.
• Console, L.; Dupre, D.T.; Torasso, P. (1991). "On the Relationship between Abduction and Deduction". Journal of Logic and Computation. 1 (5): 661–690. CiteSeerX 10.1.1.31.9982. doi:10.1093/logcom/1.5.661.
• Kakas, A.C.; Kowalski, R.A.; Toni, F. (1993). "Abductive Logic Programming". Journal of Logic and Computation. 2 (6): 719–770. CiteSeerX 10.1.1.37.3655. doi:10.1093/logcom/2.6.719.
• Denecker, Marc; De Schreye, Danny (February 1998). "SLDNFA: An Abductive Procedure for Abductive Logic Programs". Journal of Logic Programming. 34 (2): 111–167. CiteSeerX 10.1.1.21.6503. doi:10.1016/S0743-1066(97)00074-5.
• Denecker, M.; Kakas, A.C. (July 2000). "Special issue: abductive logic programming". Journal of Logic Programming. 44 (1–3): 1–4. doi:10.1016/S0743-1066(99)00078-3.
• Denecker, M.; Kakas, A.C. (2002). "Abduction in Logic Programming". In Kakas, A.C.; Sadri, F. (eds.). Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski. Lecture Notes in Computer Science. Vol. 2407. Springer. pp. 402–437. ISBN 978-3-540-43959-2.
• Poole, D. (1993). "Probabilistic Horn abduction and Bayesian networks" (PDF). Artificial Intelligence. 64 (1): 81–129. doi:10.1016/0004-3702(93)90061-F.
• Esposito, F.; Ferilli, S.; Basile, T.M.A.; Di Mauro, N. (February 2007). "Inference of abduction theories for handling incompleteness in first-order learning" (PDF). Knowl. Inf. Syst. 11 (2): 217–242. doi:10.1007/s10115-006-0019-5. S2CID 10699982. Archived from the original (PDF) on 2011-07-17.

बाहरी संबंध

• ACLP
• ACL
• SCIFF
• Asystem