برمجة منطقية استقرائية

برمجة منطقية استقرائية هي مجال فرعي لذكاء الاصطناعي الرمزي الذي يستخدم البرمجة المنطقية كتمثيل موحد للمعرفة الخلفية والفرضية. اعطاء تشفير لمعرفة خلفية معروفة ومجموعة من الأمثلة تمثل قاعدة بيانات منطقية للحقائق، نظام البرمجة المنطقي الاستقرائي سيشتق برنامج منطقي افتراضي الذي يتتبع جميع الأمثلة الصحيحة وغير الصحيحة.

مخطط:أمثلة صحيحة + امثلة خاطئة"+ معرفة خلفية← "فرضية".

تفيد البرمجة المنطقية الاستقرائية خصوصا في مجال المعلوماتية الحيوية ومعالجة اللغات الطبيعية.

جوردون بلوتيكن وايهود شابيرو وضعوا الأساس الاولي النظري لتعلم الآلة الاستقرائي في إطار المنطق.^[1]^[2]^[3] Shapiro built their first implementation (Model Inference System) in 1981:^[4] برنامج برولوغ يستنتج برنامج منطقي بشكل استقرائي من الأمثلة صحيحة والخاطئة. مصطلح البرمجة المنطقية الاستقرائية كان أول ظهور له في الصحف ^[5] من قبل ستيفن موغليتون في ١٩٩١ ^[6]

كما اسس موغليتون المؤتمر الدولي السنوي حول البرمجة المنطقية الاستقرائية، وقدم الافكار النظرية للابتكار، والحلول العكسية^[7]، التضمين العكسية ^[8] أول مرة في نظام بروغول.

مصطلح استقرائي يشير هنا إلى الفلسفة (اقتراح فرضية لتفسير حقائق مرصودة).

تعريف رسمي[عدل]

تعطى المعرفة الخلفية كنظرية منطقية B، تكون بالعادة على شكل عبارات هورن التي تستخدم في البرمجة المنطقية. تعطى الامثلة الصحيحة والخاطئة كعامل $E^{+}$ and $E^{-}$ لغير المنفي والمنفي من لاتريل على التوالي. الفرضية الصحيحة h هي قضايا منطقية تحقق المتطلبات التالية:^[9]

${\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}}$ «ضرورة»(Necessity)ليس مفترض تقييدها ب h، لكن يمنع تشكيل أي فرضية طالما الحقائق الصحيحة يمكن شرحها بدونها. «كافية»(sufficiency)يتطلب تشكيل أي فرضية h لشرح كل الامثلة الصحيحة. «تناسب ضعيف»(weak consistency)يمنع تشكيل أي فرضية h تتناقض مع المعرفة الخلفية B. «تناسب قوي»(strong consistency)أيضًا يمنع تشكيل أي نظرية h تكون متعارضة مع الامثلة الخاطئة.

الخلفية المعرفية B تدل على «تناسب ضعيف»، إذا لم يعطى أي أمثلة خاطئة، كلا المتطلبان يجب ان يتزامنا. ديروسكي يتطلب فقط «كافية» (تسمى هنا «الاكتمال») و «تناسب قوي».

نظام برمجي منطقي استقرائي[عدل]

النظام البرمجي المنطقي الاستقرائي هو برنامج يأخذ كمدخلات منطقية نظرية المعرفة الخلفية والامثلة الصحيحة إضافة إلى الامثلة الخاطئة وكمخرجات فرضيات صحيحة H، خوارزمية النظام البرمجي المنطقي الاستقرائي يتكون من جزئيين هما: البحث عن الفرضية واختيار الفرضية. في البداية يتم البحث عن الفرضيات عن طريق اسلوب البرمجة المنطقية الاستقرائية، ومن ثم تشكيل مجموعة فرعية من الفرضيات (في اغلب الحالات تكون واحدة فقط) يُختر واحدة منهم عن طريق خوارزمية الاختيار. تعطي خوارزمية الاختيار نقاط للفرضيات ومن ثم ترجع الفرضية صاحبة اعلى نقاط. يشتمل أحد الأمثلة على دالة النتيجة على الحد الأدنى لطول الضغط حيث تكون الفرضية ذات تعقيد كولمغروف الأقل لها أعلى درجة ويتم إرجاعها. يكتمل نظام البرمجة المنطقي الاستقرائي إذا كان لكل إدخال نظري منطقي $B,E^{+},E^{-}$ أي فرضية صحيحة H، يمكن إيجاد هذه الفرضيات من خلال إجراء بحث الفرضية.

إيجاد الفرضيات[عدل]

تجد أنظمة البرمجة المنطقية الاستقرائية الحديثة مثل برولوغ ^[6] وهايل ^[10] وإمبارو ^[11] الفرضيات 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$ ، يعممون النظرية المنفية للنظرية الجسر مع المضاد الاستلزام. ^[12] ومع ذلك، فإن تشغيل مضاد الاستلزام نظرًا لكونه غير حتمي بدرجة كبيرة يكون أكثر تكلفة من الناحية الحسابية. لذلك، يمكن إجراء بحث عن فرضية بديلة باستخدام عملية تضمين العكسي (مضاد التضمين) بدلاً من ذلك والتي تكون أقل حتمية من عدم الاستلزام. تنشأ أسئلة حول اكتمال إجراء بحث عن فرضية لنظام معين من البرمجة المنطقية الاستقرائية على سبيل المثال، إجراء البحث عن فرضية برولوغ ب استنادًا إلى قاعدة التضمين المعكوس غير مكتمل بمثال Yamamoto. من ناحية أخرى، يكتمل إمبارو من خلال كل من إجراءات عدم الاستلزام ^[13] وإجراء التضمين العكسي الموسع.^[14]

اقرأ ايضًا[عدل]

التعلم الإحصائي العلائقي

مصادر[عدل]

^ Plotkin G.D. Automatic Methods of Inductive Inference, PhD thesis, University of Edinburgh, 1970. نسخة محفوظة 2017-12-22 على موقع واي باك مشين.
^ Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, pp. 199–254. نسخة محفوظة 2021-08-21 على موقع واي باك مشين.
^ Shapiro, Ehud Y. (1983). Algorithmic program debugging. Cambridge, Mass: MIT Press. (ردمك 0-262-19218-7)
^ شابيرو صمم تطبيقهم الأول(نظام الاستدلال النموذجي) في ١٩٨١<ref>Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981. نسخة محفوظة 2023-04-06 على موقع واي باك مشين.
^ Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. سايتسيركس: 10.1.1.56.1790 "نسخة مؤرشفة". مؤرشف من الأصل في 2012-10-15. اطلع عليه بتاريخ 2021-10-10.{{استشهاد ويب}}: صيانة الاستشهاد: BOT: original URL status unknown (link)
^ ^أ ^ب Muggleton، S.H. (1991). "Inductive logic programming". New Generation Computing. ج. 8 ع. 4: 295–318. CiteSeerX:10.1.1.329.5312. DOI:10.1007/BF03037089.
^ Muggleton S.H. and Buntine W. "Machine invention of first-order predicate by inverting resolution","Proceedings of the 5th International Conference on Machine Learning, 1988. نسخة محفوظة 2021-04-14 على موقع واي باك مشين.
^ Muggleton، S.H. (1995). "Inverting entailment and Progol". New Generation Computing. ج. 13 ع. 3–4: 245–286. CiteSeerX:10.1.1.31.1630. DOI:10.1007/bf03037227.
^ Muggleton، Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. ج. 114 ع. 1–2: 283–296. DOI:10.1016/s0004-3702(99)00067-3.; here: Sect.2.1
^ Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning^{[وصلة مكسورة]}. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer. نسخة محفوظة 2022-04-08 على موقع واي باك مشين.
^ Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer. نسخة محفوظة 2021-10-15 على موقع واي باك مشين.
^ Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. Inverse subsumption for complete explanatory induction. Machine learning, 86(1):115–139, 2012. نسخة محفوظة 2021-09-28 على موقع واي باك مشين.
^ Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012. نسخة محفوظة 2020-07-11 على موقع واي باك مشين.
^ David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836

برمجة منطقية استقرائية في المشاريع الشقيقة:

[1] Plotkin G.D. Automatic Methods of Inductive Inference, PhD thesis, University of Edinburgh, 1970. نسخة محفوظة 2017-12-22 على موقع واي باك مشين.

[2] Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, pp. 199–254. نسخة محفوظة 2021-08-21 على موقع واي باك مشين.

[3] Shapiro, Ehud Y. (1983). Algorithmic program debugging. Cambridge, Mass: MIT Press. (ردمك 0-262-19218-7)

[4] شابيرو صمم تطبيقهم الأول(نظام الاستدلال النموذجي) في ١٩٨١<ref>Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981. نسخة محفوظة 2023-04-06 على موقع واي باك مشين.

[5] Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. سايتسيركس: 10.1.1.56.1790 "نسخة مؤرشفة". مؤرشف من الأصل في 2012-10-15. اطلع عليه بتاريخ 2021-10-10.{{استشهاد ويب}}: صيانة الاستشهاد: BOT: original URL status unknown (link)

[muggleton1995inverse-6] أ ^ب Muggleton، S.H. (1991). "Inductive logic programming". New Generation Computing. ج. 8 ع. 4: 295–318. CiteSeerX:10.1.1.329.5312. DOI:10.1007/BF03037089.

[7] Muggleton S.H. and Buntine W. "Machine invention of first-order predicate by inverting resolution","Proceedings of the 5th International Conference on Machine Learning, 1988. نسخة محفوظة 2021-04-14 على موقع واي باك مشين.

[8] Muggleton، S.H. (1995). "Inverting entailment and Progol". New Generation Computing. ج. 13 ع. 3–4: 245–286. CiteSeerX:10.1.1.31.1630. DOI:10.1007/bf03037227.

[9] Muggleton، Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence. ج. 114 ع. 1–2: 283–296. DOI:10.1016/s0004-3702(99)00067-3.; here: Sect.2.1

[10] Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning^{[وصلة مكسورة]}. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer. نسخة محفوظة 2022-04-08 على موقع واي باك مشين.

[11] Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer. نسخة محفوظة 2021-10-15 على موقع واي باك مشين.

[12] Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. Inverse subsumption for complete explanatory induction. Machine learning, 86(1):115–139, 2012. نسخة محفوظة 2021-09-28 على موقع واي باك مشين.

[kimber2009induction-13] Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012. نسخة محفوظة 2020-07-11 على موقع واي باك مشين.

[14] David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

وصلة مكسورة