Kontentke ótiw

Induktiv programmalastırıw

Wikipedia — erkin enciklopediya

Induktiv programmalastırıw (IP) — bul jasalma intellekt hám programmalastırıwdan alınǵan izertlewlerdi qamtıytuǵın avtomat programmalastırıwdıń arnawlı bir tarawı bolıp, ol ádette deklarativ (logikalıq yamasa funkcional) hám kóbinese rekursiv programmalardı kirgiziw/shıǵarıw mısalları yamasa sheklewler sıyaqlı tolıq emes specifikaciyalardan úyreniwdi qarastıradı.

Qollanılatuǵın programmalastırıw tiline baylanıslı, induktiv programmalastırıwdıń bir neshe túri bar. Lisp yamasa Haskell sıyaqlı funkcional programmalastırıw tillerin qollanatuǵın induktiv funkcional programmalastırıw, hám eń áhmiyetlisi Prolog sıyaqlı logikalıq programmalastırıw tillerin hám deskripciya logikaları sıyaqlı basqa logikalıq kórinislerdi paydalanatuǵın induktiv logikalıq programmalastırıw kóbirek kózge túsken, biraq sheklewli programmalastırıw yamasa itimallıq programmalastırıw sıyaqlı basqa (programmalastırıw) til paradigmaları da qollanılǵan.

Anıqlaması

Induktiv programmalastırıw tolıq emes (formal) specifikaciyalardan programmalar yamasa algoritmlerdi úyreniwge baylanıslı barlıq usıllardı óz ishine aladı. IP sistemasındaǵı múmkin bolǵan kirgiziwler — bul oqıtıw kirgiziwleri hám sáykes shıǵarıwlar toplamı yamasa shıǵarıw bahalaw funkciyası, olar jobalanǵan programmanıń qálegen háreketin táriyipleydi, belgili bir shıǵarıwlardı esaplaw processin táriyipleytuǵın izlewler yamasa háreketler izbe-izligi, payda etiliwi kerek bolǵan programmanıń waqıt nátiyjeliligi yamasa onıń quramalılıǵı menen baylanıslı sheklewler, standart maǵlıwmat túrleri sıyaqlı hár túrli fon bilimi, paydalanılıwı kerek bolǵan aldınnan anıqlanǵan funkciyalar, jobalanǵan programmanıń maǵlıwmat aǵımın táriyipleytuǵın programma sxemaları yamasa shablonları, sheshim izlewdi basqarıw ushın evristikalar yamasa basqa da qálewler.

IP sistemasınıń shıǵıwı — bul qanday da bir qálegen programmalastırıw tilindegi, shártler hám cikl yamasa rekursiv basqarıw strukturaların óz ishine alǵan programma, yamasa basqa da hár qanday Tyuring-tolıq kórinis tili.

Kóp qosımshalarda shıǵıw programması mısallarǵa hám bóleklik specifikaciyaǵa sáykes durıs bolıwı kerek, hám bul induktiv programmalastırıwdı avtomat programmalastırıw yamasa programma sintezi ishinde arnawlı bir taraw retinde qarastırıwǵa alıp keledi,[1][2] bul ádette specifikaciya tolıq bolatuǵın 'deduktiv' programma sintezine[3][4][5] qarama-qarsı.

Basqa jaǵdaylarda, induktiv programmalastırıw qálegen deklarativ programmalastırıw yamasa kórinis tili paydalanılıwı múmkin bolǵan anaǵurlım ulıwma taraw retinde qaraladı hám bizde ulıwma mashinalıq oqıtıw, anaǵurlım anıq struktura qazıp alıw tarawı yamasa simvollı jasalma intellekt tarawındaǵı sıyaqlı mısallarda belgili bir dárejede qáte bolıwı múmkin. Ayrıqsha ózgeshelik — kerek bolǵan mısallar sanı yamasa bóleklik specifikaciya. Ádette, induktiv programmalastırıw usılları tek bir neshe mısaldan úyrene aladı.

Induktiv programmalastırıwdıń hár túrliligi ádette qosımshalardan hám paydalanılatuǵın tillerden kelip shıǵadı: logikalıq programmalastırıw hám funkcional programmalastırıwdan tısqarı, induktiv programmalastırıwda funkcional logikalıq programmalastırıw, sheklewli programmalastırıw, itimallıq programmalastırıw, abduktiv logikalıq programmalastırıw, modal logika, háreket tilleri, agent tilleri hám kóp túrli imperativ tiller sıyaqlı basqa programmalastırıw paradigmaları hám kórinis tilleri de paydalanılǵan yamasa usınılǵan.

Tariyxı

Rekursiv funkcional programmalardı induktiv sintezlew boyınsha izertlewler 1970-jıllardıń basında baslandı hám Summers-tiń tiykar salıwshı THESIS sisteması[6] hám Biermannnıń jumısı[7]. menen bekkem teoriyalıq tiykarlarǵa iye boldı. Bul usıllar eki fazaǵa bólindi: birinshiden, kirgiziw-shıǵarıw mısalları tiykarǵı operatorlardıń kishi toplamın paydalanıp rekursiv emes programmalarǵa (izlewlerge) túrlendiriledi; ekinshiden, izlewlerdegi nızamlılıqlar izlenedi hám olardı rekursiv programmaǵa jıynaw ushın paydalanıladı. 1980-jıllardıń ortasına shekemgi tiykarǵı nátiyjeler Smit tárepinen qarap shıǵılǵan[8]. Sintezleniw múmkin bolǵan programmalar diapazonı boyınsha sheklengen alǵa ilgerlew sebepli, kelesi on jıllıqta izertlew iskerligi ádewir azaydı.

Logikalıq programmalastırıwdıń payda bolıwı 1980-jıllardıń basında jańa ilham, biraq sonıń menen birge jańa baǵdar alıp keldi, ásirese Shapironıń MIS sisteması[9] sebepli, usınıń aqıbetinde induktiv logikalıq programmalastırıw (ILP) jańa tarawınıń payda bolıwına sebep boldı. Plotkinniń dáslepki jumısları hám onıń «salıstırmalı eń kishi ulıwma ulıwmalastırıwı (rlgg)» induktiv logikalıq programmalastırıwǵa úlken tásir etti. Kópshilik ILP jumısı máselelerdiń keńirek klasın qarastıradı, sebebi itibar tek rekursiv logikalıq programmalarǵa emes, al logikalıq kórinislerden simvollı gipotezalardı mashinalıq oqıtıwǵa qaratılǵan. Degen menen, mısallardan hám sáykes fon biliminen tez sortlaw sıyaqlı rekursiv Prolog programmaların úyreniw boyınsha ayırım xoshametleytuǵın nátiyjeler boldı, mısalı, GOLEM menen. Biraq jáne de, dáslepki tabıstan keyin, birlespe rekursiv programmalar indukciyası boyınsha sheklengen alǵa ilgerlewden kewli qaldı, ILP rekursiv programmalarǵa barǵan sayın az itibar berip, relyaciyalıq maǵlıwmatlardı qazıp alıw hám bilimlerdi ashıwdaǵı qosımshaları bar mashinalıq oqıtıw ortalıǵına barǵan sayın kóbirek beyimlese basladı[10].

ILPdaǵı jumıslar menen parallel túrde, Koza[11] 1990-jıllardıń basında programmalardı úyreniw ushın generaciyalaw-hám-testlewge tiykarlanǵan usıl retinde genetikalıq programmalastırıwdı usındı. Genetikalıq programmalastırıw ideyası keyinirek ADATE[12] induktiv programmalastırıw sistemasına hám MagicHaskeller[13] sistematikalıq izlew tiykarındaǵı sistemasına rawajlandırıldı. Bul jerde de, funkcional programmalar úyreniliwi kerek bolǵan programmanıń qálegen kirgiziw/shıǵarıw háreketin anıqlaytuǵın shıǵarıw bahalaw (jaramlılıq) funkciyası menen birge oń mısallar toplamınan úyreniledi.

Grammatika indukciyası (grammatikalıq juwmaq shıǵarıw dep te ataladı) boyınsha dáslepki jumıslar induktiv programmalastırıw menen baylanıslı, sebebi qayta jazıw sistemaları yamasa logikalıq programmalar óndiris qaǵıydaların kórsetiw ushın paydalanılıwı múmkin. Shınında da, induktiv juwmaq shıǵarıw boyınsha dáslepki jumıslar grammatika indukciyasın hám Lisp programmasın juwmaq shıǵarıwdı negizinde birdey másele retinde qarastırdı[14]. Úyreniw múmkinshiligi boyınsha nátiyjeler Goldtıń tiykar salıwshı jumısında[15] kirgizilgen shegarada-identifikaciyalaw sıyaqlı klassikalıq túsinikler menen baylanıslı edi. Jaqın arada til úyreniw máselesin induktiv programmalastırıw birlespesi qarap shıqtı[16][17].

Sońǵı jıllarda klassikalıq usıllar úlken tabıs penen qayta tiklendi hám rawajlandırıldı. Sonlıqtan, sintez máselesi funkcional programmalastırıwdıń zamanagóy usılların esapqa alıp, sonday-aq izlew tiykarındaǵı strategiyalardı hám fon bilimlerin shekli paydalanıw, sonday-aq kishi programmalardı avtomat túrde oylap tabıw menen birge, konstruktor tiykarındaǵı term qayta jazıw sistemaları fonında qayta formulirovka etildi. Jaqında programma sintezinen tıs kóp jańa hám tabıslı qosımshalar payda boldı, eń áhmiyetlisi maǵlıwmatlardı manipulyaciyalaw, mısal menen programmalastırıw hám kognitiv modellestiriw tarawlarında (tómenge qarań).

Basqa da ideyalar, gipotezalardı kórsetiw ushın deklarativ tillerdi paydalanıw ulıwma ózgesheligi menen izertlendi. Mısalı, joqarı dárejeli ózgesheliklerdi, sxemalardı yamasa strukturalıq aralıqlardı paydalanıw rekursiv maǵlıwmat túrlerin hám strukturaların jaqsıraq qayta islew ushın usınıldı;[18][19][20] abstrakciya sonıń menen birge jıynaqlı úyreniw hám funkciya oylap tabıw ushın kúshlirek usıl retinde de izertlendi[21].

Jaqında induktiv programmalastırıwda gipotezalardı kórsetiw ushın qollanılǵan (ulıwma generativ modeller formasında) kúshli bir paradigma — bul itimallıq programmalastırıw (hám baylanıslı paradigmalar, mısalı, stoxastikalıq logikalıq programmalar hám Bayes logikalıq programmalastırıw)[22][23][24].

Qollanıw tarawları

ICML 2005 penen birge ótkerilgen Induktiv Programmalastırıwdıń Usılları hám Qollanılıwları (AAIP) boyınsha birinshi seminar programmalar yamasa rekursiv qaǵıydalardı úyreniw talap etiletuǵın barlıq qosımshalardı anıqladı, [...] birinshiden programmalıq támiynat injenerligi tarawında, bunda strukturalıq úyreniw, programmalıq támiynat járdemshileri hám programmalıq támiynat agentleri baǵdarlamashılardı ádettegi wazıypalardan azat etiwge, aqırǵı paydalanıwshılar ushın programmalastırıw qollap-quwatlawın beriwge yamasa jańa baslawshı baǵdarlamashılar menen programmalastırıw repetitor sistemaların qollap-quwatlawǵa járdem bere aladı. Qosımsha qollanıw tarawları — til úyreniw, jasalma intellekt jobalastırıw ushın rekursiv basqarıw qaǵıydaların úyreniw, veb-qazıp alıwda yamasa maǵlıwmat formatın túrlendiriw ushın rekursiv túsiniklerdi úyreniw».

Sonnan berli, bul hám basqa da kóp tarawlar induktiv programmalastırıw ushın tabıslı qollanıw tarawları ekenin kórsetti, mısalı, aqırǵı paydalanıwshı programmalastırıwı,[25] oǵan baylanıslı mısal menen programmalastırıw[26] hám kórsetiw menen programmalastırıw[27] tarawları, hám intellektual repetitorlıq sistemalar.

Induktiv juwmaq shıǵarıw jaqında qollanılǵan basqa tarawlar — bilimlerdi alıw,[28] ulıwma jasalma intellekt,[29] bekkemlewshi oqıtıw hám teoriyanı bahalaw,[30][31] hám ulıwma alǵanda kognitiv ilim[32]. Sonıń menen birge intellektual agentler, oyınlar, robototexnika, jekelestiriw, qorshaǵan ortalıq intellekti hám adam interfeyslerinde de perspektivalı qollanıwları bolıwı múmkin.

Derekler

  1. ↑ Biermann, A.W. (1992). Shapiro, S.C.. ed. Automatic programming. pp. 18–35.
  2. ↑ Rich, C.; Waters, R.C.. Approaches to automatic programming, Advances in Computers, 1993 — 1–57 bet. DOI:10.1016/S0065-2458(08)60402-7. ISBN 9780120121373. 
  3. ↑ Automatic software design, 1991. 
  4. ↑ Manna, Z.; Waldinger, R. (1992). Fundamentals of deductive program synthesis. 18. pp. 674–704. doi:10.1109/32.153379.
  5. ↑ Flener, P.. Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski, Lecture Notes in Computer Science, 2002 — 310–346 bet. DOI:10.1007/3-540-45628-7_13. ISBN 978-3-540-43959-2. 
  6. ↑ Summers, P.D. (1977). "A methodology for LISP program construction from examples". J ACM 24 (1): 161–175. doi:10.1145/321992.322002.
  7. ↑ Biermann, A.W. (1978). "The inference of regular LISP programs from examples". IEEE Trans Syst Man Cybern 8 (8): 585–600. doi:10.1109/tsmc.1978.4310035.
  8. ↑ Smith, D.R. (1984). "The synthesis of LISP programs from examples: a survey". Automatic Program Construction Techniques: 307–324.
  9. ↑ Shapiro, E.Y.. Algorithmic program debugging. The MIT Press, 1983. 
  10. ↑ Džeroski, Sašo (1996), „Inductive Logic Programming and Knowledge Discovery in Databases“, in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (red.), Advances in Knowledge Discovery and Data Mining, 117–152-bet {{citation}}: Unknown parameter |publisher= ignored (járdem)
  11. ↑ Koza, J.R.. Genetic Programming: vol. 1, On the programming of computers by means of natural selection. MIT Press, 1992. ISBN 9780262111706. 
  12. ↑ Olsson, J.R. (1995). Inductive functional programming using incremental program transformation.
  13. ↑ Katayama, Susumu. PRICAI 2008: Trends in Artificial Intelligence, 2008. ISBN 978-3-540-89196-3. 
  14. ↑ Angluin, D.; C.H., Smith (1983). "Inductive inference: Theory and methods". ACM Computing Surveys 15 (3): 237–269. doi:10.1145/356914.356918.
  15. ↑ Gold, E.M. (1967). "Language identification in the limit". Information and Control 10 (5): 447–474. doi:10.1016/s0019-9958(67)91165-5.
  16. ↑ 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
  17. ↑ Olsson, J.R.; Powers, D.M.W. (2003). "Machine learning of human language through automatic programming". Proceedings of the International Conference on Cognitive Science: 507–512.
  18. ↑ Lloyd, J.W. (2001). Knowledge Representation, Computation, and Learning in Higher-order Logic.
  19. ↑ Lloyd, J.W.. Logic for learning: learning comprehensible theories from structured data, 2003. 
  20. ↑ Estruch, V.; Ferri, C. (2014). "Bridging the gap between distance and generalization". Computational Intelligence 30 (3): 473–513. doi:10.1111/coin.12004.
  21. ↑ Henderson, R.J.; Muggleton, S.H. (2012). "Automatic invention of functional abstractions". Advances in Inductive Logic Programming.
  22. ↑ Muggleton, S. (2000). Learning stochastic logic programs. https://ocs.aaai.org/Papers/Workshops/2000/WS-00-06/WS00-06-006.pdf.
  23. ↑ De Raedt, L.. Probabilistic inductive logic programming. Springer, 2008. 
  24. ↑ Stuhlmuller, A. (2012). Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs.
  25. ↑ Lieberman, H.; Paternò, F.. End user development, 2006. 
  26. ↑ Lieberman, H.. Your wish is my command: Programming by example, 2001. 
  27. ↑ Cypher, E.; Halbert, D.C.. Watch what I do: programming by demonstration, 1993. 
  28. ↑ Schmid, U.; Hofmann, M. (2009). "Analytical inductive programming as a cognitive rule acquisition devise". Proceedings of the Second Conference on Artificial General Intelligence: 162–167.
  29. ↑ Crossley, N.; Kitzelmann, E. (2009). "Combining analytical and evolutionary inductive programming". Proceedings of the Second Conference on Artificial General Intelligence: 19–24.
  30. ↑ Hernandez-Orallo, J. (2000). "Constructive reinforcement learning". International Journal of Intelligent Systems 15 (3): 241–264. doi:10.1002/(sici)1098-111x(200003)15:3<241::aid-int6>3.0.co;2-z.
  31. ↑ Kemp, C.; Goodman, N. (2007). "Learning and using relational theories". Advances in Neural Information Processing Systems: 753–760.
  32. ↑ Schmid, U.; Kitzelmann, E. (2011). "Inductive rule learning on the knowledge level". Cognitive Systems Research 12 (3): 237–248. doi:10.1016/j.cogsys.2010.12.002.
«https://kaa.wikipedia.org/w/index.php?title=Induktiv_programmalastırıw&oldid=168803» saytınan alınǵan