Пређи на садржај

Индуктивно програмирање

С Википедије, слободне енциклопедије
Парадигме програмирања

Индуктивно програмирање (ИП)је посебна област аутоматског програмирања, која покрива истраживање из вештачке интелигенције и програмирања, који се бави учењу обичних декларативних (логички или функционални) и често рекурзивних програма из непотпуних спецификација, као што је улаз/излаз примери или ограничења.

У зависности од програмског језика који се користи, постоји неколико врста индуктивног програмирања. Индуктивно функционално програмирање, које користи функционалне програмске језике као што су Lisp или Haskell, а већина посебно индуктивно логичко програмирање, које користи логичке програмске језике као што су Prolog и друге логичке репрезентације као што је опис логике, су изражени, али и друге (програмирање) језичке парадигме се такође користе, као што је ограничење програмања или вероватноћа програмирања.

Дефиниција

[уреди | уреди извор]

Индуктивно програмирање укључује све приступе који су укључени са програмима за учење или алгоритама из непотпуних (формалних) спецификација. Могући улази у IP систем су скуп у обуку улаза и одговарајућег излаза или функција излазних евалуација, описујући жељено понашање које је намењено програмима, трагови или акционе сцене које описују процес обрачуна посебних излаза, ограничења за програм која индукују о његовом времену ефикасности или комплексности, разне врсте предзнања као што су стандардни типови података, дефинисане функције које се користе, програмске шеме или шаблони описују проток података намењених програмима, хеуристика за вођење потраге за решењем или још предрасуда.

Излаз на IP систем је програм у неком произвољном програмском језику који садржи уређај и петље или рекурзивне контролне структуре, или било коју другу врсту Тјурингове потпуности репрезентације језика.

У многим апликацијама излазни програм мора бити тачан у вези са примерима и делимичним спецификацијама, и то доводи до разматрања индуктивног програмирања као посебна област унутар аутоматског програмирања или програм синтеза,[1][2] обично разлика од "дедуктивне' програм синтезе,[3][4][5] где је спецификација обично потпуна.

У другим случајевима, индуктивно програмирање се посматра као још шире подручје где се неко декларативно програмирање или заступљеност језика може користи и чак може имати неки степен грешке у примерима, као код општег машинског учења, виша специфична област структуре рударства и подручје симболичке вештачке интелигенције. Специфичност је број примера или делимична спецификација која је потребна. Типично, индуктивне технике програмирања могу да се науче у само неколико примера.

Разноликост индуктивног програмирања обично долази од апликација и језика који се користе: осим логичког програмирања и функционалног програмирања, остале програмске парадигме и заступање језика се користи или су предложене у индуктивном програмирању, као што су функционално логичко програмирање, ограничење програмирања, вероватноћа програмирања, абдуктив логика програмирања, модална логика, акциони језици, агент језици и многе врсте императивних језика.

Историја

[уреди | уреди извор]

Истраживање о индуктивним синтезама рекурзивних функционалних програма почела је у раним 1970-им и доведена је на чврсте теоријске основе са првобитном тезом система Summers-а[6] и рада Biermann-а.[7] Ови приступи су подељени у две фазе: прва, улазно-излазни примери су претворени у не-рекурзивне програме (трагова) користећи мали скуп основних оператора; Друго, правилности у траговима су тражили да половина одустане у рекурзивном програму. Главни резултати до средине 1980-их је анкетирани Смит.[8] Због ограниченог напретка у погледу опсега програма који се може синтетизирати, истраживачке активности се значајно смањују у наредној деценији.

Појава логичког програмирања донело је нови елан, али и нови правац у раним 1980-им, посебно због MIS система Shapiro[9] који на крају формира нову област индуктивног логиког програмирања (ИЛП).[10] Рани радови Plotkin-а,[11][12] и његов "рођак најмање опште генерализације (рног)", има огроман утицај на индуктивно логичко програмирање.  Већина ILP радова бави се широком класом проблема, као што фокус није само рекурзиван логички програм, али је на машини учења симболичких хипотеза из логичких репрезентација. Међутим, било је неких охрабрујућих резултата на учење рекурзивних Prolog програма као што су quicksor од примера, заједно са одговарајућим знањем, на пример, са GOLEM-ом.[13] Али опет, после почетног успеха, заједница добија разочарано ограничење напретка индукције рекурзивних програма[14][15][16] са ILP мањим и мање се фокусира на рекурзивне програме и нагиње све више и више ка машинском учењу подешавање са применама у релационим подацима рударства и откривању знања.[17]

У паралелном послу у ILP-у, Koza[18] је предложио генетичко програмирање у раним 1990-им као генерисање-и-тест заснован приступ програмима за учење. Идеја генетског програмирања је даље развијање у индуктивном програмирању система ADATE[19] и систематска-претрага базе система MagicHaskeller-а.[20] Ево опет, функционални програми се науче из комплета позитивних примера, заједно са излазом евалуација (фитнес) функција које одређују жељени улаз/излаз понашања програма за учење.

Рани рад у основној индукцији (такође познат као граматичко закључивање) односи се на индуктивно програмирање, као преписивање система и логички програми могу се користити за представљање правила производње. У ствари, на почетку радова у индуктивном закључивању сматра основну индукцију и Lisp програм у основи као истим проблемом.[21] Резултати у смислу лакоћа учења су се односили на класичне концепте, као што је идентификација у-лимиту, као увођење у првобитном раду Gold-а.[22] У скорије време, проблем учење језика се обратио заједници индуктивног програмирања.[23][24]

У последњих неколико година, класични приступи су настављени и напредовали са великим успехом. Дакле, проблем синтеза је преформулисан на позадину конструктора на бази термина корекција система узимајући у обзир модерне технике функционалног програмирања, као и умерено коришћење претраживача на бази стратегије и коришћења позадинског предзнања, као и аутоматски проналазак потпрограма. Многе нове и успешне примене недавно су се појавиле изнад програма синтрза, већина нарочито у области манипулације подацима, програмирање примера и когнитивног моделирања (види доле).

Друге идеје су истражене са заједничким карактеристикама коришћења декларативног језика за представљање хипотеза. На пример, употреба вишег реда карактеристика, шема или структурираних раздаљина се заговара за боље руковање рекурзивних типова података и објеката;[25][26][27] апстракција је и истражена као снажнији приступ кумулативном учењу и функцији проналаска.[28][29]

Једна моћна парадигма која је недавно коришћена за представљање хипотеза у индуктивном програмирању (углавном у облику генеративних модела) је пробабилистичко програмирање (и сродне парадигме, као што су стохастички логички програми и Бајесово логичко програмирање).[30][31][32][33]

Област примене

[уреди | уреди извор]

Прва радионица о приступима и применама индуктивног програмирања (ППИП) одржана у вези са ICML 2005 идентификовала је све апликације где је "учење програма или рекурзивних правила позвано, [...] најпре у домену софтверског инжењерства где је структура учења, софтверски асистенти и софтверски агенти могу помоћи да се ослободе програмери из рутинских задатака, дати програмску подршку за крајње кориснике, односно подршку почетним програмерима и програмирање тутор система. Остала подручја примене су учење језика, учење рекурзивних правила контроле за AI-планирање, учење рекурзивних концепата у веб-рударству или податак-формат трансформације ".

Од тада, ове и многе друге области су показале да могу да буду успешне апликације за индуктивно програмирање, као што је крајње-корисничко развијање,[34] сродне области су програмирање примерима[35] и програмирања од стране демонстрације,,[36]и интелигентни туторски системи. Аутоматска манипулација подацима је такође било предмет неких "убица апликација" за индуктивно програмирање, као што је 'Flash Fill' алат[37][38] у Мајкрософт Екселу.

Друге области у којима индуктивно закључивање је недавно примењено су стицање знања,[39] вештачка интелигенција,[40] појачавање учења и оцењивање теорије,[41][42] и когнитивне науке уопште.[43][33] Такође могу бити потенцијалне апликације у интелигентним агенатима, игре, роботика, персонализација, амбијентална интелигенција и људски интерфејс.

Види још

[уреди | уреди извор]

Референце

[уреди | уреди извор]
  1. ^ Biermann, A.W. (1992). Shapiro, S.C., ур. „Automatic programming”. Encyclopedia of artificial intelligence. Wiley: 18—35. 
  2. ^ Rich, C.; Waters, R.C. (1993). Yovits, M.C., ур. „Approaches to automatic programming”. Advances in computers. Academic Press. 37. 
  3. ^ Lowry, M.L.; McCarthy, R.D., ур. (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., ур. „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., ур. „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., ур. „A Note on Inductive Generalization”. Machine Intelligence. Edinburgh University Press. 5: 153—163. 
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., ур. „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”, Ур.: Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, стр. 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. Архивирано из оригинала 25. 01. 2009. г. Приступљено 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 Слободан приступ. 
  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. ^ а б 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. Приступљено 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. 

Литература

[уреди | уреди извор]

Спољашње везе

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