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

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

सिंटेक्स

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

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

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

 false:- A1,...,An, not B1, ..., not Bm.

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

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

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

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

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

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

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

उदाहरण 1

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

 Grass is wet if it rained.

 Grass is wet if the sprinkler was on.

 The sun was shining.

$A$ में योगोत्पादी विधेय "it rained" और "the sprinkler was on" और ${\mathit {IC}}$ में एकमात्र अखंडता बाधा है:

false if it rained and the sun was shining.

अवलोकन कि घास नम है, के दो संभावित स्पष्टीकरण हैं, "it rained" और "the sprinkler was on", जो अवलोकन को आवश्यक बनाता है। यद्यपि, मात्र दूसरा संभावित स्पष्टीकरण, "the sprinkler was on", अखंडता की कमी को पूरा करते है।

उदाहरण 2

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

 X is a citizen if X is born in the USA.

 X is a citizen if X is born outside the USA and X is a resident of the USA and X is naturalized.

 X is a citizen if X is born outside the USA and Y is the mother of X and Y is a citizen and X is registered.

 Mary is the mother of John.

 Mary is a citizen.

साथ में पाँच अपहृत विधेय के साथ, "is born in the USA", "is born outside the USA", "is a resident of the USA", "is naturalized" और "is registered" और अखंडता बाधा है:

 false if John is a resident of the USA.

लक्ष्य "John is citizen" के दो योगोत्पादीात्मक हल हैं, जिनमें से एक "John is born in the USA", जिसमें से दूसरा "John is born outside the USA" और "John is registered"। निवास और प्राकृतिककरण द्वारा नागरिक बनने का संभावित हल विफल हो जाता है क्योंकि यह अखंडता की बाधा का उल्लंघन करते है।

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

उदाहरण 3

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

डोमेन ज्ञान (P)

   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.

योगोत्पादी योग्य (A)

   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$ है जैसे कि:

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

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

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

कार्यान्वयन और प्रणाली

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

यह भी देखें

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

संदर्भ

• 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.

बाहरी संबंध

• एसीएलपी
• ACL
• Sसीआईएफएफ
• Asystem