विवेचनात्मक तर्क प्रोग्रामिंग (इंडक्टिव लॉजिक प्रोग्रामिंग)

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

• स्कीमा: सकारात्मक उदाहरण + नकारात्मक उदाहरण + पृष्ठभूमि ज्ञान ⇒ परिकल्पना

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

औपचारिक परिभाषा

पृष्ठभूमि ज्ञान तर्क सिद्धांत के रूप में दिया जाता है B, आमतौर पर लॉजिक प्रोग्रामिंग में उपयोग किए जाने वाले हॉर्न क्लॉज के रूप में। सकारात्मक और नकारात्मक उदाहरण संयोजन के रूप में दिए गए हैं $E^{+}$ और $E^{-}$ अप्रतिबंधित और नकारात्मक जमीनी अभिव्यक्ति की क्रमशः शाब्दिक (गणितीय तर्क)। एक सही परिकल्पना h तार्किक प्रस्ताव है जो निम्नलिखित आवश्यकताओं को पूरा करता है।

एंटेलमेंट#सिमेंटिक परिणाम|

${\begin{array}{llll}{\text{Necessity:}}&B&\not \models &E^{+}\\{\text{Sufficiency:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Weak consistency:}}&B\land h&\not \models &{\textit {false}}\\{\text{Strong consistency:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}$आवश्यकता किसी पर प्रतिबंध नहीं लगाती h, लेकिन परिकल्पना के किसी भी निर्माण को तब तक प्रतिबंधित करता है जब तक कि इसके बिना सकारात्मक तथ्यों की व्याख्या की जा सकती है।

पर्याप्तता के लिए किसी उत्पन्न परिकल्पना की आवश्यकता होती है h सभी सकारात्मक उदाहरणों की व्याख्या करने के लिए $E^{+}$.
कमजोर स्थिरता किसी भी परिकल्पना के निर्माण को मना करती है h जो पृष्ठभूमि ज्ञान के विपरीत है B.
मजबूत स्थिरता भी किसी भी परिकल्पना के निर्माण को मना करती है h जो नकारात्मक उदाहरणों के साथ असंगत है $E^{-}$, पृष्ठभूमि ज्ञान दिया B; इसका अर्थ है कमजोर संगति; यदि कोई नकारात्मक उदाहरण नहीं दिया जाता है, तो दोनों आवश्यकताएँ मेल खाती हैं। जेरोस्की  केवल पर्याप्तता (वहां पूर्णता कहा जाता है) और मजबूत स्थिरता की आवश्यकता होती है।

उदाहरण

अनुभाग उदाहरण में अनुमानित पारिवारिक संबंध

पारिवारिक संबंधों की परिभाषाएँ सीखने के बारे में निम्नलिखित सुप्रसिद्ध उदाहरण संक्षिप्त रूपों का उपयोग करता है

par: parent, fem: female, dau: daughter, g: George, h: Helen, m: Mary, t: Tom, n: Nancy, और e: Eve.

यह पृष्ठभूमि ज्ञान से शुरू होता है (cf. चित्र)

${\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)$,

सकारात्मक उदाहरण

${\textit {dau}}(m,h)\land {\textit {dau}}(e,t)$,

और तुच्छ प्रस्ताव true नकारात्मक उदाहरणों की अनुपस्थिति को निरूपित करने के लिए।

प्लॉटकिन का प्रारंभिक तर्क प्रोग्रामिंग के सापेक्ष कम से कम सामान्यीकरण (आरएलजीजी) दृष्टिकोण का उपयोग बेटी संबंध को औपचारिक रूप से परिभाषित करने के तरीके के बारे में सुझाव प्राप्त करने के लिए किया जाएगा। dau.

यह दृष्टिकोण निम्न चरणों का उपयोग करता है।

• पूर्ण पृष्ठभूमि ज्ञान के साथ शाब्दिक रूप से प्रत्येक सकारात्मक उदाहरण को सापेक्ष करें:

  ${\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}$,

• खंड सामान्य रूप में परिवर्तित करें:

  ${\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}$,

• एंटी-यूनिफिकेशन (कंप्यूटर साइंस) | एंटी-यूनिफाई प्रत्येक संगत जोड़ा शाब्दिक का:
  • ${\textit {dau}}(x_{me},x_{ht})$ से ${\textit {dau}}(m,h)$ और ${\textit {dau}}(e,t)$,
  • $\lnot {\textit {par}}(x_{ht},x_{me})$ से $\lnot {\textit {par}}(h,m)$ और $\lnot {\textit {par}}(t,e)$,
  • $\lnot {\textit {fem}}(x_{me})$ से $\lnot {\textit {fem}}(m)$ और $\lnot {\textit {fem}}(e)$,
  • $\lnot {\textit {par}}(g,m)$ से $\lnot {\textit {par}}(g,m)$ और $\lnot {\textit {par}}(g,m)$, अन्य सभी पृष्ठभूमि-ज्ञान शाब्दिकों के समान
  • $\lnot {\textit {par}}(x_{gt},x_{me})$ से $\lnot {\textit {par}}(g,m)$ और $\lnot {\textit {par}}(t,e)$, और कई अन्य नकारात्मक अक्षर
• सकारात्मक शाब्दिक में नहीं होने वाले चर वाले सभी अस्वीकृत शाब्दिक हटाएं:
  • की तुलना में अन्य चर वाले सभी अस्वीकृत शाब्दिकों को हटाने के बाद $x_{me},x_{ht}$, केवल ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ पृष्ठभूमि ज्ञान से सभी जमीनी शाब्दिकों के साथ रहता है
• क्लॉज को वापस हॉर्न फॉर्म में बदलें:
  • ${\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})$

परिणामी हॉर्न खंड परिकल्पना है h आरएलजीजी दृष्टिकोण द्वारा प्राप्त किया गया। पृष्ठभूमि ज्ञान तथ्यों की उपेक्षा करते हुए, खंड अनौपचारिक रूप से पढ़ता है$x_{me}$ की पुत्री कहलाती है $x_{ht}$ अगर $x_{ht}$ का जनक है $x_{me}$ और $x_{me}$ महिला है, जो सामान्य रूप से स्वीकृत परिभाषा है।

1. औपचारिक परिभाषा आवश्यकताओं के संबंध में, आवश्यकता विधेय के कारण संतुष्ट थी dau पृष्ठभूमि ज्ञान में प्रकट नहीं होता है, इसलिए इस विधेय वाली किसी भी संपत्ति को लागू नहीं किया जा सकता है, जैसे कि सकारात्मक उदाहरण हैं।

परिकलित परिकल्पना से पर्याप्तता संतुष्ट होती है h, इसके बाद से, साथ में ${\textit {par}}(h,m)\land {\textit {fem}}(m)$ पृष्ठभूमि ज्ञान से, पहला सकारात्मक उदाहरण निकलता है ${\textit {dau}}(m,h)$, और इसी तरह  h और ${\textit {par}}(t,e)\land {\textit {fem}}(e)$ पृष्ठभूमि ज्ञान से दूसरे सकारात्मक उदाहरण का तात्पर्य है ${\textit {dau}}(e,t)$. कमजोर संगति से संतुष्ट होता है h, तब से h पृष्ठभूमि ज्ञान द्वारा वर्णित (परिमित) हरब्रांड संरचना में है; मजबूत स्थिरता के लिए समान।

दादी के संबंध की सामान्य परिभाषा, अर्थात। ${\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)$, उपरोक्त दृष्टिकोण का उपयोग करके नहीं सीखा जा सकता है, क्योंकि चर y क्लॉज बॉडी में ही होता है; संबंधित शाब्दिक दृष्टिकोण के चौथे चरण में हटा दिए गए होंगे। इस दोष को दूर करने के लिए, उस कदम को इस तरह संशोधित करना होगा कि इसे अलग-अलग शाब्दिक पोस्ट-चयन हेरिस्टिक्स के साथ पैरामीट्रिज किया जा सके। ऐतिहासिक रूप से, गोलेम कार्यान्वयन आरएलजीजी दृष्टिकोण पर आधारित है।

इंडक्टिव लॉजिक प्रोग्रामिंग सिस्टम

इंडक्टिव लॉजिक प्रोग्रामिंग सिस्टम प्रोग्राम है जो इनपुट लॉजिक सिद्धांतों के रूप में लेता है $B,E^{+},E^{-}$ और सही परिकल्पना का उत्पादन करता है H wrt सिद्धांत $B,E^{+},E^{-}$ ILP प्रणाली के एल्गोरिथ्म में दो भाग होते हैं: परिकल्पना खोज और परिकल्पना चयन। पहले आगमनात्मक तर्क प्रोग्रामिंग प्रक्रिया के साथ परिकल्पना की खोज की जाती है, फिर मिली परिकल्पनाओं का सबसेट (अधिकांश प्रणालियों में परिकल्पना) चयन एल्गोरिथ्म द्वारा चुना जाता है। चयन एल्गोरिथम प्रत्येक पाई गई परिकल्पना को स्कोर करता है और उच्चतम स्कोर वाले को लौटाता है। स्कोर फ़ंक्शन के उदाहरण में न्यूनतम संपीड़न लंबाई शामिल है जहां सबसे कम कोलमोगोरोव जटिलता वाली परिकल्पना में उच्चतम स्कोर होता है और वापस आ जाता है। किसी भी इनपुट लॉजिक सिद्धांतों के लिए ILP सिस्टम पूर्ण है $B,E^{+},E^{-}$ कोई सही परिकल्पना H इन इनपुट सिद्धांतों के संबंध में इसकी परिकल्पना खोज प्रक्रिया के साथ पाया जा सकता है।

परिकल्पना खोज

प्रोगोल जैसे आधुनिक ILP सिस्टम,जयकार करना और मैं सीखता हूँ परिकल्पना खोजें H उलटा प्रवेश के सिद्धांत का उपयोग करनासिद्धांतों के लिए B, E, H: $B\land H\models E\iff B\land \neg E\models \neg H$. पहले वे मध्यवर्ती सिद्धांत का निर्माण करते हैं F शर्तों को संतुष्ट करने वाला ब्रिज थ्योरी कहलाता है $B\land \neg E\models F$ और $F\models \neg H$. फिर ऐसे $H\models \neg F$, वे सेतु सिद्धांत के निषेध का सामान्यीकरण करते हैं F विरोधी प्रवेश के साथ। हालांकि, अत्यधिक गैर-नियतात्मक होने के बाद से एंटी-एंटेलमेंट का संचालन कम्प्यूटेशनल रूप से अधिक महंगा है। इसलिए, वैकल्पिक परिकल्पना खोज को इसके बजाय व्युत्क्रम सबसम्प्शन (एंटी-सबजम्पशन) के संचालन का उपयोग करके आयोजित किया जा सकता है, जो एंटी-एंटेलमेंट की तुलना में कम गैर-नियतात्मक है।

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

कार्यान्वयन

• 1BC और 1BC2: प्रथम क्रम के भोले बायेसियन क्लासिफायर:
• ACE (एक संयुक्त इंजन)
• Aleph
• एटम Archived 2014-03-26 at the Wayback Machine
• क्लॉडियन
• डीएल-लर्नर
• डीमैक्स
• FastLAS (उत्तर सेट से तेजी से सीखना)
• फर्स्ट ऑर्डर इंडक्टिव लर्नर | एफओआईएल (फर्स्ट ऑर्डर इंडक्टिव लर्नर)
• गोलेम (ILP)
• ILASP (उत्तर सेट कार्यक्रमों की आगमनात्मक शिक्षा)
• इम्पारो* Inthelex (उदाहरणों से इंक्रीमेंटल थ्योरी लर्नर) Archived 2011-11-28 at the Wayback Machine
• लाइम
• मेटागोल
• Mio
• एमआईएस (मॉडल अनुमान प्रणाली) एहुद शापिरो द्वारा
• प्रोगोल
• आरएसडी
• वार्मर (अब एसीई में शामिल)
• ProGolem

यह भी देखें

• सामान्य ज्ञान तर्क
• औपचारिक अवधारणा विश्लेषण
• विवेचनात्मक तार्किकता
• आगमनात्मक प्रोग्रामिंग
• आगमनात्मक संभावना
• सांख्यिकीय संबंधपरक शिक्षा
• वर्जन स्पेस लर्निंग

अग्रिम पठन

• Muggleton, S.; De Raedt, L. (1994). "Inductive Logic Programming: Theory and methods". The Journal of Logic Programming. 19–20: 629–679. doi:10.1016/0743-1066(94)90035-3.
• Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 978-0-13-457870-5. Archived from the original on 2004-09-06. Retrieved 2004-09-22.
• Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html Archived 2014-03-26 at the Wayback Machine