البرمجة الاستقرائية

الموسوعة الحرة

البرمجة الاستقرائية ( IP ) هي مجال خاص من البرمجة الآلية ، تغطي الأبحاث من الذكاء الاصطناعي والبرمجة ، والتي تتناول تعلم البرامج التصريحية ( المنطقية أو الوظيفية ) والتكرارية في كثير من الأحيان من مواصفات غير مكتملة، مثل أمثلة الإدخال/الإخراج أو القيود.

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

تعريف

يشمل البرمجة الاستقرائية جميع المناهج التي تُعنى بتعلم البرامج أو الخوارزميات من مواصفات غير مكتملة ( رسمية ). وتشمل المدخلات المحتملة في نظام البرمجة الاستقرائية مجموعة من مدخلات التدريب ومخرجاتها المقابلة، أو دالة تقييم المخرجات التي تصف السلوك المطلوب للبرنامج المقصود، أو مسارات أو تسلسلات الإجراءات التي تصف عملية حساب مخرجات محددة، أو قيودًا على البرنامج المراد استنتاجها فيما يتعلق بكفاءته الزمنية أو تعقيده، أو أنواعًا مختلفة من المعرفة الأساسية مثل أنواع البيانات القياسية ، والوظائف المُعرَّفة مسبقًا والمُراد استخدامها، ومخططات أو قوالب البرامج التي تصف تدفق البيانات للبرنامج المقصود، والأساليب الاستدلالية لتوجيه البحث عن حل، أو غيرها من التحيزات.

إن مخرجات نظام IP هي برنامج بلغة برمجة عشوائية تحتوي على عبارات شرطية وحلقات أو هياكل تحكم تكرارية، أو أي نوع آخر من لغات التمثيل الكاملة تورينج .

في العديد من التطبيقات، يجب أن يكون برنامج الإخراج صحيحًا فيما يتعلق بالأمثلة والمواصفات الجزئية، وهذا يؤدي إلى اعتبار البرمجة الاستقرائية مجالًا خاصًا داخل البرمجة التلقائية أو توليف البرامج ، [ 1 ] [ 2 ] وعادة ما يتم معارضتها لتوليف البرامج "الاستنتاجي"، [ 3 ] [ 4 ] [ 5 ] حيث تكون المواصفات عادةً كاملة.

In other cases, inductive programming is seen as a more general area where any declarative programming or representation language can be used and we may even have some degree of error in the examples, as in general machine learning, the more specific area of structure mining or the area of symbolic artificial intelligence. A distinctive feature is the number of examples or partial specification needed. Typically, inductive programming techniques can learn from just a few examples.

The diversity of inductive programming usually comes from the applications and the languages that are used: apart from logic programming and functional programming, other programming paradigms and representation languages have been used or suggested in inductive programming, such as functional logic programming, constraint programming, probabilistic programming, abductive logic programming, modal logic, action languages, agent languages and many types of imperative languages.

History

The early works of Plotkin,[6][7] and his "relative least general generalization (rlgg)", had an enormous impact in inductive logic programming. There were some encouraging results on learning recursive Prolog programs such as quicksort from examples together with suitable background knowledge, for example with GOLEM.[8] However, after initial success, the community got disappointed by limited progress about the induction of recursive programs[9][10][11] with ILP less and less focusing on recursive programs and leaning more and more towards a machine learning setting with applications in relational data mining and knowledge discovery.[12]

In parallel to work in ILP, Koza[13] proposed genetic programming in the early 1990s as a generate-and-test based approach to learning programs. The idea of genetic programming was further developed into the inductive programming system ADATE[14] and the systematic-search-based system MagicHaskeller.[15] Here again, functional programs are learned from sets of positive examples together with an output evaluation (fitness) function which specifies the desired input/output behavior of the program to be learned.

ترتبط الأعمال المبكرة في استقراء القواعد النحوية (المعروف أيضًا بالاستدلال النحوي) بالبرمجة الاستقرائية، حيث يمكن استخدام أنظمة إعادة الكتابة أو البرامج المنطقية لتمثيل قواعد الإنتاج. في الواقع، اعتبرت الأعمال المبكرة في الاستدلال الاستقرائي استقراء القواعد النحوية واستدلال برامج لغة ليسب مشكلة واحدة أساسًا. [ 16 ] ارتبطت النتائج المتعلقة بقابلية التعلم بمفاهيم كلاسيكية، مثل التحديد في النهاية، كما ورد في العمل الرائد لجولد. [ 17 ] في الآونة الأخيرة، تناول مجتمع البرمجة الاستقرائية مشكلة تعلم اللغة. [ 18 ] [ 19 ]

في السنوات الأخيرة، تمّ استئناف المناهج الكلاسيكية وتطويرها بنجاح كبير. ولذلك، أُعيدت صياغة مشكلة التركيب على خلفية أنظمة إعادة كتابة المصطلحات القائمة على المُنشئات، مع مراعاة التقنيات الحديثة للبرمجة الوظيفية، بالإضافة إلى الاستخدام المعتدل لاستراتيجيات البحث، والاستفادة من المعرفة الأساسية، فضلاً عن الابتكار التلقائي للبرامج الفرعية. وقد ظهرت مؤخراً العديد من التطبيقات الجديدة والناجحة خارج نطاق تركيب البرامج، لا سيما في مجال معالجة البيانات، والبرمجة بالأمثلة، والنمذجة المعرفية (انظر أدناه).

تم استكشاف أفكار أخرى تشترك في استخدام لغات وصفية لتمثيل الفرضيات. على سبيل المثال، تم الترويج لاستخدام خصائص أو مخططات أو مسافات مُهيكلة من الرتبة العليا لتحسين التعامل مع أنواع البيانات والهياكل المتكررة ؛ [ 20 ] [ 21 ] [ 22 ] كما تم استكشاف التجريد كنهج أكثر فعالية للتعلم التراكمي وابتكار الدوال. [ 23 ] [ 24 ]

يُعدّ البرمجة الاحتمالية (والنماذج ذات الصلة، مثل برامج المنطق العشوائي وبرمجة المنطق البايزي) نموذجًا قويًا استُخدم مؤخرًا لتمثيل الفرضيات في البرمجة الاستقرائية (عادةً في شكل نماذج توليدية ). [ 25 ] [ 26 ] [ 24 ] [ 27 ]

مجالات التطبيق

حددت ورشة العمل الأولى حول مناهج وتطبيقات البرمجة الاستقرائية (AAIP)، المؤرشفة بتاريخ 3 مارس 2016 على موقع Wayback Machine ، والتي عُقدت بالتزامن مع المؤتمر الدولي للتعلم الآلي (ICML) لعام 2005، جميع التطبيقات التي تتطلب "تعلم البرامج أو القواعد التكرارية، [...] أولاً في مجال هندسة البرمجيات حيث يمكن للتعلم الهيكلي، ومساعدي البرمجيات، ووكلاء البرمجيات أن تُخفف عن المبرمجين المهام الروتينية، وتُقدم دعمًا برمجيًا للمستخدمين النهائيين، أو دعمًا للمبرمجين المبتدئين وأنظمة تعليم البرمجة. وتشمل مجالات التطبيق الأخرى تعلم اللغات، وتعلم قواعد التحكم التكرارية لتخطيط الذكاء الاصطناعي، وتعلم المفاهيم التكرارية في استخراج البيانات من الويب أو لتحويل تنسيقات البيانات".

منذ ذلك الحين، أثبتت هذه المجالات والعديد من المجالات الأخرى أنها مجالات تطبيق ناجحة للبرمجة الاستقرائية، مثل برمجة المستخدم النهائي ، [ 28 ] والمجالات ذات الصلة بالبرمجة عن طريق المثال [ 29 ] والبرمجة عن طريق العرض التوضيحي ، [ 30 ] وأنظمة التدريس الذكية .

تشمل المجالات الأخرى التي طُبِّق فيها الاستدلال الاستقرائي مؤخرًا اكتساب المعرفة ، [ 31 ] والذكاء الاصطناعي العام ، [ 32 ] والتعلم المعزز وتقييم النظريات، [ 33 ] [ 34 ] والعلوم المعرفية بشكل عام. [ 35 ] [ 27 ] وقد تكون هناك تطبيقات مستقبلية في الوكلاء الأذكياء، والألعاب، والروبوتات، والتخصيص، والذكاء المحيطي، وواجهات المستخدم.

انظر أيضاً

مراجع

  1. ↑ بيرمان، أ. و. (1992). شابيرو، س. س. (محرر). "البرمجة الآلية". موسوعة الذكاء الاصطناعي : 18-35 .
  2. ↑ ريتش، سي.؛ ووترز، آر سي (1993). يوفيتس، إم سي (محرر). مناهج البرمجة الآلية (ملف PDF) . التقدم في الحوسبة. المجلد 37. الصفحات 1-57 . doi : 10.1016/S0065-2458(08)60402-7 . ISBN   9780120121373.
  3. ↑ لوري، إم إل؛ مكارثي، آر دي، محرران. (1991). تصميم البرمجيات الآلي .
  4. ^ مناع، ز. والدينجر، ر. (1992). “أساسيات توليف البرنامج الاستنتاجي”. IEEE Trans Softw Eng . 18 (8): 674-704 . سايتسيركس 10.1.1.51.817 . دوى : 10.1109/32.153379 . 
  5. ↑ فلينر، ب. (2002). "إنجازات وآفاق توليف البرامج". في: كاكاس، أ.؛ صدري، ف. (محرران). المنطق الحسابي: البرمجة المنطقية وما بعدها؛ مقالات تكريمًا لروبرت أ. كوالسكي . سلسلة محاضرات في علوم الحاسوب. المجلد LNAI 2407. الصفحات 310-346 . doi : 10.1007/3-540-45628-7_13 . ISBN   978-3-540-43959-2.
  6. ↑ بلوتكين، جوردون د. (1970). ميلتزر، ب.؛ ميتشي، د. (محرران). "ملاحظة حول التعميم الاستقرائي" (ملف PDF) . الذكاء الآلي . 5 : 153-163 .
  7. ↑ بلوتكين، جوردون د. (1971). ميلتزر، ب.؛ ميتشي، د. (محرران). "ملاحظة إضافية حول التعميم الاستقرائي". ذكاء الآلة . 6 : 101-124 .
  8. ↑ موغلتون، إس إتش؛ فينغ، سي. (1990). "الاستقراء الفعال للبرامج المنطقية". وقائع ورشة عمل نظرية التعلم الخوارزمي . 6 : 368-381 . S2CID 14992676 . 
  9. ↑ كوينلان، جيه آر؛ كاميرون-جونز، آر إم (1993). "تجنب المزالق عند تعلم النظريات التكرارية". المؤتمر الدولي المشترك للذكاء الاصطناعي : 1050-1057 . S2CID 11138624 . 
  10. ↑ كوينلان، جيه آر؛ كاميرون-جونز، آر إم (1995). "استقراء البرامج المنطقية: FOIL والأنظمة ذات الصلة" (ملف PDF) . 13 ( 3-4 ). سبرينغر: 287-312 . مؤرشف من الأصل (ملف PDF) بتاريخ 2017-09-07 . تم الاسترجاع بتاريخ 2017-09-07 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
  11. ↑ فلينر، ب.؛ يلماز، س. (1999). "التوليف الاستقرائي لبرامج المنطق التكراري: الإنجازات والآفاق" . مجلة برمجة المنطق . 41 (2): 141-195 . doi : 10.1016/s0743-1066(99)00028-x .
  12. ↑ دزيروسكي، ساشو (1996)، "البرمجة المنطقية الاستقرائية واكتشاف المعرفة في قواعد البيانات"، في فياض، يو إم؛ بياتيتسكي-شابيرو، جي؛ سميث، بي؛ أوثوروسامي، آر (محررون)، التطورات في اكتشاف المعرفة واستخراج البيانات ، مطبعة معهد ماساتشوستس للتكنولوجيا ، ص 117-152 
  13. ↑ كوزا، جيه آر (1992). البرمجة الجينية: المجلد 1، حول برمجة الحواسيب عن طريق الانتقاء الطبيعي . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 9780262111706.
  14. ↑ أولسون، جيه آر (1995). "البرمجة الوظيفية الاستقرائية باستخدام تحويل البرنامج التزايدي" . الذكاء الاصطناعي . 74 (1): 55-83 . doi : 10.1016/0004-3702(94)00042-y .
  15. ↑ كاتاياما، سوسومو (2008). "التوليد الشامل الفعال للبرامج الوظيفية باستخدام بحث مونت كارلو مع التعميق التكراري" (ملف PDF) . مؤتمر PRICAI 2008: اتجاهات في الذكاء الاصطناعي . سلسلة محاضرات في علوم الحاسوب. المجلد 5351. الصفحات 199-210 . CiteSeerX 10.1.1.606.1447 . doi : 10.1007/978-3-540-89197-0_21 . ISBN    978-3-540-89196-3.
  16. ↑ أنجلوين، د.؛ سميث، سي إتش (1983). "الاستدلال الاستقرائي: النظرية والأساليب". مجلة ACM Computing Surveys . 15 (3): 237-269 . doi : 10.1145/356914.356918 . S2CID 3209224 . 
  17. ↑ غولد، إي إم (1967). "تحديد اللغة في الحد" . المعلومات والتحكم . 10 (5): 447-474 . doi : 10.1016/s0019-9958(67)91165-5 .
  18. ↑ موغلتون، ستيفن (1999). "البرمجة المنطقية الاستقرائية: قضايا ونتائج وتحدي تعلم اللغة في المنطق" . الذكاء الاصطناعي . 114 ( 1-2 ): 283-296 . doi : 10.1016/s0004-3702(99)00067-3 .هنا: القسم 2.1
  19. ↑ أولسون، جيه آر؛ باورز، دي إم دبليو (2003). "التعلم الآلي للغة البشرية من خلال البرمجة التلقائية". وقائع المؤتمر الدولي للعلوم المعرفية : 507-512 .
  20. ↑ لويد، جيه دبليو (2001). "تمثيل المعرفة، والحساب، والتعلم في منطق الرتبة العليا" (PDF) .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
  21. ↑Lloyd, J.W. (2003). Logic for learning: learning comprehensible theories from structured data. Springer. ISBN 9783662084069.
  22. ↑Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, M.J. (2014). "Bridging the gap between distance and generalization". Computational Intelligence. 30 (3): 473–513. doi:10.1111/coin.12004. hdl:10251/34946. S2CID 7255690.
  23. ↑Henderson, R.J.; Muggleton, S.H. (2012). "Automatic invention of functional abstractions"(PDF). Advances in Inductive Logic Programming.
  24. 12Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). "Inducing probabilistic programs by Bayesian program merging". arXiv:1110.5667 [cs.AI].
  25. ↑Muggleton, S. (2000). "Learning stochastic logic programs"(PDF). Electron. Trans. Artif. Intell. 4(B): 141–153. Archived from the original(PDF) on 2017-09-07. Retrieved 2017-09-07.
  26. ↑De Raedt, L.; Kersting, K. (2008). Probabilistic inductive logic programming. Springer.
  27. 12Stuhlmuller, A.; Goodman, N.D. (2012). "Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs". Cognitive Systems Research. 28: 80–99. doi:10.1016/j.cogsys.2013.07.003. S2CID 7602205.
  28. ↑Lieberman, H.; Paternò, F.; Wulf, V. (2006). End user development. Springer.
  29. ↑Lieberman, H. (2001). Your wish is my command: Programming by example. Morgan Kaufmann. ISBN 9781558606883.
  30. ↑Cypher, E.; Halbert, D.C. (1993). Watch what I do: programming by demonstration. MIT Press. ISBN 9780262032131.
  31. ↑Schmid, U.; Hofmann, M.; Kitzelmann, E. (2009). "Analytical inductive programming as a cognitive rule acquisition devise"(PDF). Proceedings of the Second Conference on Artificial General Intelligence: 162–167.
  32. ↑ كروسلي، ن.؛ كيتزلمان، إ.؛ هوفمان، م.؛ شميد، يو. (2009). "الجمع بين البرمجة الاستقرائية التحليلية والتطورية" (ملف PDF) . وقائع المؤتمر الثاني حول الذكاء الاصطناعي العام : 19-24 .
  33. ↑ هيرنانديز-أورالو، ج. (2000). "التعلم المعزز البنّاء". المجلة الدولية للأنظمة الذكية . 15 (3): 241-264 . CiteSeerX 10.1.1.34.8877 . doi : 10.1002/(sici)1098-111x(200003)15:3 < 241::aid-int6 > 3.0.co ; 2-z . S2CID 123390956 .  
  34. ↑ كيمب، سي.؛ غودمان، ن.؛ تيننباوم، جيه بي (2007). "تعلم واستخدام النظريات العلائقية" (ملف PDF) . التطورات في أنظمة معالجة المعلومات العصبية : 753-760 .
  35. ↑ شميد، يو .؛ كيتزلمان، إي. (2011). "التعلم الاستقرائي للقواعد على مستوى المعرفة". بحوث الأنظمة المعرفية . 12 (3): 237-248 . doi : 10.1016/j.cogsys.2010.12.002 . S2CID 18613664 . 

للمزيد من القراءة