Induktivno programiranje

S Vikipedije, slobodne enciklopedije
Paradigme programiranja

Induktivno programiranje (IP)je posebna oblast automatskog programiranja, koja pokriva istraživanje iz veštačke inteligencije i programiranja, koji se bavi učenju običnih deklarativnih (logički ili funkcionalni) i često rekurzivnih programa iz nepotpunih specifikacija, kao što je ulaz/izlaz primeri ili ograničenja.

U zavisnosti od programskog jezika koji se koristi, postoji nekoliko vrsta induktivnog programiranja. Induktivno funkcionalno programiranje, koje koristi funkcionalne programske jezike kao što su Lisp ili Haskell, a većina posebno induktivno logičko programiranje, koje koristi logičke programske jezike kao što su Prolog i druge logičke reprezentacije kao što je opis logike, su izraženi, ali i druge (programiranje) jezičke paradigme se takođe koriste, kao što je ograničenje programanja ili verovatnoća programiranja.

Definicija[uredi | uredi izvor]

Induktivno programiranje uključuje sve pristupe koji su uključeni sa programima za učenje ili algoritama iz nepotpunih (formalnih) specifikacija. Mogući ulazi u IP sistem su skup u obuku ulaza i odgovarajućeg izlaza ili funkcija izlaznih evaluacija, opisujući željeno ponašanje koje je namenjeno programima, tragovi ili akcione scene koje opisuju proces obračuna posebnih izlaza, ograničenja za program koja indukuju o njegovom vremenu efikasnosti ili kompleksnosti, razne vrste predznanja kao što su standardni tipovi podataka, definisane funkcije koje se koriste, programske šeme ili šabloni opisuju protok podataka namenjenih programima, heuristika za vođenje potrage za rešenjem ili još predrasuda.

Izlaz na IP sistem je program u nekom proizvoljnom programskom jeziku koji sadrži uređaj i petlje ili rekurzivne kontrolne strukture, ili bilo koju drugu vrstu Tjuringove potpunosti reprezentacije jezika.

U mnogim aplikacijama izlazni program mora biti tačan u vezi sa primerima i delimičnim specifikacijama, i to dovodi do razmatranja induktivnog programiranja kao posebna oblast unutar automatskog programiranja ili program sinteza,[1][2] obično razlika od "deduktivne' program sinteze,[3][4][5] gde je specifikacija obično potpuna.

U drugim slučajevima, induktivno programiranje se posmatra kao još šire područje gde se neko deklarativno programiranje ili zastupljenost jezika može koristi i čak može imati neki stepen greške u primerima, kao kod opšteg mašinskog učenja, viša specifična oblast strukture rudarstva i područje simboličke veštačke inteligencije. Specifičnost je broj primera ili delimična specifikacija koja je potrebna. Tipično, induktivne tehnike programiranja mogu da se nauče u samo nekoliko primera.

Raznolikost induktivnog programiranja obično dolazi od aplikacija i jezika koji se koriste: osim logičkog programiranja i funkcionalnog programiranja, ostale programske paradigme i zastupanje jezika se koristi ili su predložene u induktivnom programiranju, kao što su funkcionalno logičko programiranje, ograničenje programiranja, verovatnoća programiranja, abduktiv logika programiranja, modalna logika, akcioni jezici, agent jezici i mnoge vrste imperativnih jezika.

Istorija[uredi | uredi izvor]

Istraživanje o induktivnim sintezama rekurzivnih funkcionalnih programa počela je u ranim 1970-im i dovedena je na čvrste teorijske osnove sa prvobitnom tezom sistema Summers-a[6] i rada Biermann-a.[7] Ovi pristupi su podeljeni u dve faze: prva, ulazno-izlazni primeri su pretvoreni u ne-rekurzivne programe (tragova) koristeći mali skup osnovnih operatora; Drugo, pravilnosti u tragovima su tražili da polovina odustane u rekurzivnom programu. Glavni rezultati do sredine 1980-ih je anketirani Smit.[8] Zbog ograničenog napretka u pogledu opsega programa koji se može sintetizirati, istraživačke aktivnosti se značajno smanjuju u narednoj deceniji.

Pojava logičkog programiranja donelo je novi elan, ali i novi pravac u ranim 1980-im, posebno zbog MIS sistema Shapiro[9] koji na kraju formira novu oblast induktivnog logikog programiranja (ILP).[10] Rani radovi Plotkin-a,[11][12] i njegov "rođak najmanje opšte generalizacije (rnog)", ima ogroman uticaj na induktivno logičko programiranje.  Većina ILP radova bavi se širokom klasom problema, kao što fokus nije samo rekurzivan logički program, ali je na mašini učenja simboličkih hipoteza iz logičkih reprezentacija. Međutim, bilo je nekih ohrabrujućih rezultata na učenje rekurzivnih Prolog programa kao što su quicksor od primera, zajedno sa odgovarajućim znanjem, na primer, sa GOLEM-om.[13] Ali opet, posle početnog uspeha, zajednica dobija razočarano ograničenje napretka indukcije rekurzivnih programa[14][15][16] sa ILP manjim i manje se fokusira na rekurzivne programe i naginje sve više i više ka mašinskom učenju podešavanje sa primenama u relacionim podacima rudarstva i otkrivanju znanja.[17]

U paralelnom poslu u ILP-u, Koza[18] je predložio genetičko programiranje u ranim 1990-im kao generisanje-i-test zasnovan pristup programima za učenje. Ideja genetskog programiranja je dalje razvijanje u induktivnom programiranju sistema ADATE[19] i sistematska-pretraga baze sistema MagicHaskeller-a.[20] Evo opet, funkcionalni programi se nauče iz kompleta pozitivnih primera, zajedno sa izlazom evaluacija (fitnes) funkcija koje određuju željeni ulaz/izlaz ponašanja programa za učenje.

Rani rad u osnovnoj indukciji (takođe poznat kao gramatičko zaključivanje) odnosi se na induktivno programiranje, kao prepisivanje sistema i logički programi mogu se koristiti za predstavljanje pravila proizvodnje. U stvari, na početku radova u induktivnom zaključivanju smatra osnovnu indukciju i Lisp program u osnovi kao istim problemom.[21] Rezultati u smislu lakoća učenja su se odnosili na klasične koncepte, kao što je identifikacija u-limitu, kao uvođenje u prvobitnom radu Gold-a.[22] U skorije vreme, problem učenje jezika se obratio zajednici induktivnog programiranja.[23][24]

U poslednjih nekoliko godina, klasični pristupi su nastavljeni i napredovali sa velikim uspehom. Dakle, problem sinteza je preformulisan na pozadinu konstruktora na bazi termina korekcija sistema uzimajući u obzir moderne tehnike funkcionalnog programiranja, kao i umereno korišćenje pretraživača na bazi strategije i korišćenja pozadinskog predznanja, kao i automatski pronalazak potprograma. Mnoge nove i uspešne primene nedavno su se pojavile iznad programa sintrza, većina naročito u oblasti manipulacije podacima, programiranje primera i kognitivnog modeliranja (vidi dole).

Druge ideje su istražene sa zajedničkim karakteristikama korišćenja deklarativnog jezika za predstavljanje hipoteza. Na primer, upotreba višeg reda karakteristika, šema ili strukturiranih razdaljina se zagovara za bolje rukovanje rekurzivnih tipova podataka i objekata;[25][26][27] apstrakcija je i istražena kao snažniji pristup kumulativnom učenju i funkciji pronalaska.[28][29]

Jedna moćna paradigma koja je nedavno korišćena za predstavljanje hipoteza u induktivnom programiranju (uglavnom u obliku generativnih modela) je probabilističko programiranje (i srodne paradigme, kao što su stohastički logički programi i Bajesovo logičko programiranje).[30][31][32][33]

Oblast primene[uredi | uredi izvor]

Prva radionica o pristupima i primenama induktivnog programiranja (PPIP) održana u vezi sa ICML 2005 identifikovala je sve aplikacije gde je "učenje programa ili rekurzivnih pravila pozvano, [...] najpre u domenu softverskog inženjerstva gde je struktura učenja, softverski asistenti i softverski agenti mogu pomoći da se oslobode programeri iz rutinskih zadataka, dati programsku podršku za krajnje korisnike, odnosno podršku početnim programerima i programiranje tutor sistema. Ostala područja primene su učenje jezika, učenje rekurzivnih pravila kontrole za AI-planiranje, učenje rekurzivnih koncepata u veb-rudarstvu ili podatak-format transformacije ".

Od tada, ove i mnoge druge oblasti su pokazale da mogu da budu uspešne aplikacije za induktivno programiranje, kao što je krajnje-korisničko razvijanje,[34] srodne oblasti su programiranje primerima[35] i programiranja od strane demonstracije,,[36]i inteligentni tutorski sistemi. Automatska manipulacija podacima je takođe bilo predmet nekih "ubica aplikacija" za induktivno programiranje, kao što je 'Flash Fill' alat[37][38] u Majkrosoft Ekselu.

Druge oblasti u kojima induktivno zaključivanje je nedavno primenjeno su sticanje znanja,[39] veštačka inteligencija,[40] pojačavanje učenja i ocenjivanje teorije,[41][42] i kognitivne nauke uopšte.[43][33] Takođe mogu biti potencijalne aplikacije u inteligentnim agenatima, igre, robotika, personalizacija, ambijentalna inteligencija i ljudski interfejs.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ Biermann, A.W. (1992). Shapiro, S.C., ur. „Automatic programming”. Encyclopedia of artificial intelligence. Wiley: 18—35. 
  2. ^ Rich, C.; Waters, R.C. (1993). Yovits, M.C., ur. „Approaches to automatic programming”. Advances in computers. Academic Press. 37. 
  3. ^ Lowry, M.L.; McCarthy, R.D., ur. (1991). Automatic software design. 
  4. ^ Manna, Z.; Waldinger, R. (1992). „Fundamentals of deductive program synthesis”. IEEE Trans Softw Eng. 18 (8): 674—704. doi:10.1109/32.153379. 
  5. ^ Flener, P. (2002). Kakas, A.; Sadri, F., ur. „Achievements and prospects of program synthesis”. Computational logic: logic programming and beyond; essays in honour of Robert A. Kowalski. Springer. LNAI 2407: 310—346. doi:10.1007/3-540-45628-7_13. 
  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). Biermann, A.W.; Guiho, G., ur. „The synthesis of LISP programs from examples: a survey”. Automatic program construction techniques. Macmillan: 307—324. 
  9. ^ Shapiro, E.Y. (1983). Algorithmic program debugging. The MIT Press. 
  10. ^ Muggleton, S. (1991). „Inductive logic programming”. New Generation Computing. 8 (4): 295—318. doi:10.1007/BF03037089. 
  11. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., ur. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163. 
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ur. „A Further Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 6: 101—124. 
  13. ^ Muggleton, S.H.; Feng, C. (1990). „Efficient induction of logic programs”. Proceedings of the Workshop on Algorithmic Learning Theory. the Japanese Society for AI. 6: 368—381. 
  14. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1993). „Avoiding Pitfalls When Learning Recursive Theories”. IJCAI: 1050—1057. 
  15. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1995). „Induction of logic programs: FOIL and related systems”. 13(3-4). Springer: 287—312. 
  16. ^ Flener, P.; Yilmaz, S. (1999). „Inductive synthesis of recursive logic programs: Achievements and prospects”. The Journal of Logic Programming. 41 (2): 141—195. doi:10.1016/s0743-1066(99)00028-x. 
  17. ^ Džeroski, Sašo (1996), „Inductive Logic Programming and Knowledge Discovery in Databases”, Ur.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, str. 117—152 
  18. ^ Koza, J.R. (1992). Genetic Programming: vol. 1, On the programming of computers by means of natural selection. MIT Press. 
  19. ^ Olsson, J.R. (1995). „Inductive functional programming using incremental program transformation”. Artificial Intelligence. Elsevier. 74 (1): 55—83. doi:10.1016/0004-3702(94)00042-y. 
  20. ^ Katayama, Susumu (2008). „Efficient exhaustive generation of functional programs using Monte-Carlo search with iterative deepening”. PRICAI 2008: Trends in Artificial Intelligence: 199—210. 
  21. ^ Angluin, D.; C.H., Smith (1983). „Inductive inference: Theory and methods”. ACM Computing Surveys. ACM. 15: 237—269. doi:10.1145/356914.356918. 
  22. ^ Gold, E.M. (1967). „Language identification in the limit”. Information and Control. Elsevier. 10 (5): 447—474. doi:10.1016/s0019-9958(67)91165-5. Arhivirano iz originala 25. 01. 2009. g. Pristupljeno 13. 01. 2016. 
  23. ^ Muggleton, Stephen (1999). „Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence. 114: 283—296. doi:10.1016/s0004-3702(99)00067-3. ; here: Sect.2.1
  24. ^ Olsson, J.R.; Powers, D.M.W. (2003). „Machine learning of human language through automatic programming”. Proceedings of the International Conference on Cognitive Science. University of New South Wales: 507—512. 
  25. ^ Lloyd, J.W. (2001). „Knowledge Representation, Computation, and Learning in Higher-order Logic”. 
  26. ^ Lloyd, J.W. (2003). Logic for learning: learning comprehensible theories from structured data. Springer. 
  27. ^ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, M.J. (2014). „Bridging the gap between distance and generalization”. Computational Intelligence. Wiley. 
  28. ^ Henderson, R.J.; Muggleton, S.H. (2012). „Automatic invention of functional abstractions”. Advances in Inductive Logic Programming. Imperial College Press. 
  29. ^ Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). „Inducing probabilistic programs by Bayesian program merging”. arXiv. Elsevier. arXiv:1110.5667 Slobodan pristup. 
  30. ^ Muggleton, S. (2000). „Learning stochastic logic programs”. Electron. Trans. Artif. Intell. 4(B): 141—153. 
  31. ^ De Raedt, L.; Kersting, K. (2008). Probabilistic inductive logic programming. Springer. 
  32. ^ Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). „Inducing probabilistic programs by Bayesian program merging”. arXiv preprint arXiv:1110.5667. Elsevier. 
  33. ^ a b Stuhlmuller, A.; Goodman, N.D. (2012). „Reasoning about reasoning by nested conditioning: Modeling theory of mind with probabilistic programs”. Cognitive Systems Research. Elsevier. 
  34. ^ Lieberman, H.; Paternò, F.; Wulf, V. (2006). End user development. Springer. 
  35. ^ Lieberman, H. (2001). Your wish is my command: Programming by example. Morgan Kaufmann. 
  36. ^ Watch what I do : programming by demonstration. Allen Cypher, Daniel Conrad Halbert. Cambridge, Mass.: MIT Press. 1993. ISBN 0-262-03213-9. OCLC 27431647. 
  37. ^ Gulwani, S.; Harris, W.R.; Singh, R. (2012). „Spreadsheet data manipulation using examples”. Communications of the ACM. ACM. 55 (8): 97—105. doi:10.1145/2240236.2240260. 
  38. ^ Harris, Steven (1. 10. 2013). „Excel 2013 - Flash Fill”. Experts-Exchange.com. Experts Exchange. Pristupljeno 23. 11. 2013. 
  39. ^ Schmid, U.; Hofmann, M.; Kitzelmann, E. (2009). „Analytical inductive programming as a cognitive rule acquisition devise”. Proceedings of the Second Conference on Artificial General Intelligence: 162—167. 
  40. ^ Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). „Combining analytical and evolutionary inductive programming”. Proceedings of the Second Conference on Artificial General Intelligence: 19—24. 
  41. ^ 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. 
  42. ^ Kemp, C.; Goodman, N.; Tenenbaum, J.B. (2007). „Learning and using relational theories”. Advances in neural information processing systems: 753—760. 
  43. ^ 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. 

Literatura[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Индуктивно_програмирање&oldid=27673135”