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

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

सिंटेक्स

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

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

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

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

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

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

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

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

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

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

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

उदाहरण 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.

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

false if it rained and the sun was shining.

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

उदाहरण 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.

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

 false if John is a resident of the USA.

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

एक अधिक जटिल उदाहरण जो 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