유도 프로그래밍

Inductive programming
프로그래밍 패러다임

귀납 프로그래밍(IP)은 인공지능과 프로그래밍의 연구를 다루는 자동 프로그래밍의 특수한 영역으로, 전형적으로 선언적(논리적 또는 기능적)의 학습을 다루며 입출력 예나 제약과 같은 불완전한 사양에서 재귀적 프로그램을 자주 다룬다.

사용되는 프로그래밍 언어에 따라 몇 가지 종류의 귀납 프로그래밍이 있다. Lisp나 Haskell과 같은 기능 프로그래밍 언어를 사용하는 유도 기능 프로그래밍과, 특히 Prolog와 같은 논리 프로그래밍 언어와 설명 로직과 같은 다른 논리 표현을 사용하는 유도 논리 프로그래밍은 더욱 두드러져 왔으나, 다른 (프로그래밍) 언어 패러다임 또한 b를 가지고 있다.사용된 een(예: 제약 조건 프로그래밍 또는 확률론적 프로그래밍)

정의

유도 프로그래밍은 불완전한 (공식) 규격에서 학습 프로그램 또는 알고리즘과 관련된 모든 접근방식을 포함한다. IP 시스템에서 가능한 입력은 훈련 입력물 및 해당 출력물 또는 출력 평가 함수로, 특정 출력물의 계산 과정, 시간 효율성 또는 그 계산과 관련하여 유도되는 프로그램에 대한 제약조건, 추적 또는 조치 시퀀스 등의 원하는 동작을 기술한다.어휘성, 표준 데이터 유형과 같은 다양한 종류의 배경 지식, 사용할 미리 정의된 기능, 의도된 프로그램의 데이터 흐름을 설명하는 프로그램 구성이나 템플릿, 솔루션 또는 기타 편견을 찾기 위한 경험적 접근성.

IP 시스템의 출력은 조건 및 루프 또는 반복 제어 구조 또는 다른 종류의 튜링 완료 표현 언어를 포함하는 임의 프로그래밍 언어의 프로그램이다.

많은 응용 분야에는 출력 프로그램 보기와 부분적인 명세와 관련하여, 이 유도 프로그래밍의 자동 프로그래밍, 프로그램 synthesis,[1][2]보통 규격은 보통 complet'deductive'프로그램 synthesis,[3][4][5]에 반대하는 안에 특별한 지역으로 고려로 이어진다 정확해야 한다.e

다른 경우에서, 귀납 프로그래밍은 선언적 프로그래밍이나 표현 언어를 사용할 수 있는 보다 일반적인 영역으로 보이며, 일반적인 기계학습에서와 같이, 구조 채굴의 보다 구체적인 영역이나 상징적인 인공지능의 영역과 같이 우리는 그 예에서 어느 정도의 오차가 있을 수도 있다. 독특한 특징은 필요한 예시 수나 부분 명세서다. 전형적으로, 귀납 프로그래밍 기법은 단지 몇 가지 예에서 배울 수 있다.

유도 프로그래밍의 다양성은 일반적으로 사용되는 응용 프로그램과 언어에서 온다: 논리 프로그래밍과 기능 프로그래밍과는 별도로, 다른 프로그래밍 패러다임과 표현 언어가 사용되거나 제안되었다(예: 기능적 논리 프로그래밍, 제약조건 프로그래밍, 확률론).c 프로그래밍, 납치 논리 프로그래밍, 모달 논리, 액션 언어, 에이전트 언어 및 많은 유형의 명령어.

역사

재귀적 기능 프로그램의 귀납적 합성에 관한 연구는 1970년대 초에 시작되었고 서머스의[6] 정론적 논문 체계와 비어만의 연구로 확고한 이론적 토대를 마련하였다.[7] 이러한 접근방식은 두 단계로 나뉘었다. 첫째, 입력-출력 예는 작은 기본 연산자 세트를 사용하여 비복구 프로그램(트레이스)으로 변환된다. 둘째, 추적의 정규성을 검색하여 재귀 프로그램으로 접기 위해 사용한다. 1980년대 중반까지의 주요 결과는 스미스에 의해 조사되었다.[8] 합성할 수 있는 프로그램의 범위에 관한 제한적인 진보로 인해, 향후 10년 동안 연구 활동은 현저하게 감소하였다.

로직 프로그래밍의 등장은 새로운 엘란(elan)을 가져왔으나 또한 1980년대 초반에 새로운 방향을 제시했는데, 특히 샤피로의[9] MIS 시스템 때문에 결국 새로운 유도 논리 프로그래밍(ILP)의 분야가 생겨났다.[10] 플롯킨의 초기 작품들과 [11][12]그의 "상대적 최소 일반화(rlgg)"는 유도 논리 프로그래밍에 엄청난 영향을 미쳤다. 대부분의 ILP 작업은 반복적인 논리 프로그램뿐만 아니라 논리적인 표현으로부터 상징적인 가설을 기계적으로 학습하는 것에 초점을 맞추고 있기 때문에 더 광범위한 문제를 다룬다. 그러나, 예를 들어 골렘과 같은 적절한 배경지식과 함께 예시로부터의 퀵 서트와 같은 재귀적 프롤로그 프로그램에 대한 몇몇 고무적인 결과가 있었다.[13] 그러나 다시 한번, 초기 성공 이후, 지역사회는 ILP를 통한 재귀 프로그램[14][15][16] 도입이 점점 더 반복적인 프로그램에 초점을 맞추고 관계형 데이터 마이닝과 지식 발견에 응용하는 기계 학습 환경에 점점 더 기울어짐에 대한 제한적인 진전에 실망했다.[17]

ILP에서의 작업과 병행하여, 코자는[18] 1990년대 초 학습 프로그램에 대한 생성 및 테스트 기반 접근법으로 유전자 프로그래밍을 제안했다. 유전자 프로그래밍의 아이디어는 유도 프로그래밍 시스템 ADATE와[19] 체계적 탐색 기반 시스템 MagicHaskeller로 더욱 발전되었다.[20] 여기서도 기능 프로그램은 학습할 프로그램의 원하는 입출력 동작을 지정하는 출력 평가(피트니스) 기능과 함께 긍정적인 예시 집합으로부터 학습된다.

문법 유도의 초기 작품(문법적 추론이라고도 한다)은, 재쓰기 시스템이나 논리 프로그램을 생산 규칙을 나타내기 위해 사용할 수 있기 때문에 귀납 프로그래밍과 관련이 있다. 사실, 귀납 추론에서의 초기 작품들은 문법 유도와 리스프 프로그램 추론을 기본적으로 같은 문제로 간주했다.[21] 학습성 측면에서의 결과는 골드(Gold)의 정석적인 작품에서 소개된 대로, 제한적으로 식별하는 것과 같은 고전적 개념과 관련이 있었다.[22] 더 최근에, 언어 학습 문제는 귀납 프로그래밍 커뮤니티에 의해 다루어졌다.[23][24]

최근 몇 년 동안 고전적인 접근법이 재개되어 큰 성공을 거두며 발전해 왔다. 따라서, 종합 문제는 현대적인 기능 프로그래밍 기법을 고려한 시공자 기반 용어 재작성 시스템의 배경과 더불어, 하위 프로그램의 자동 발명뿐만 아니라, 검색 기반 전략과 배경 지식의 사용의 중간적인 이용에 의해 재구성되었다. 많은 새롭고 성공적인 애플리케이션들이 최근 프로그램 합성을 넘어 나타났으며, 특히 데이터 조작, 예시별 프로그래밍 및 인지 모델링(아래 참조) 분야에서 특히 그러하다.

다른 생각들도 가설을 표현하기 위해 선언적 언어를 사용하는 공통적인 특성을 가지고 탐구되었다. 예를 들어, 재귀적 데이터 유형과 구조의 더 나은 처리를 위해 고차원의 특징, 체계 또는 구조화된 거리의 사용은 주장되어 왔다.[25][26][27] 추상화는 또한 누적 학습과 기능 발명에 대한 더 강력한 접근법으로서 탐구되었다.[28][29]

귀납적 프로그래밍(일반적으로 생성적 모델의 형태로)에서 가설의 표현에 최근 사용되어 온 강력한 패러다임 중 하나는 확률적 논리 프로그램 및 베이시안 논리 프로그래밍과 같은 확률론적 프로그래밍이다.[30][31][32][33]

응용 영역

ICML 2005와 함께 열린 첫 번째 유도 프로그래밍의 접근법과 응용에 관한 워크숍에서는 "프로그램이나 재귀적 규칙의 학습이 요구되고, 구조 학습, 소프트웨어 보조자 및 소프트웨어 에이전트가 프로그(Proggue)를 완화시키는 데 도움을 줄 수 있는 소프트웨어 엔지니어링 영역에서 먼저 [...]가 필요한 모든 응용프로그램을 확인했다.일상적인 작업에서 나오는 래머, 최종 사용자를 위한 프로그래밍 지원 또는 초보 프로그래머와 프로그래밍 튜터 시스템의 지원을 제공한다. 그 외에도 언어 학습, AI 계획 수립을 위한 학습 재귀 제어 규칙, 웹 마이닝 또는 데이터 형식 변환을 위한 학습 재귀 개념 등이 적용 대상이다.

그 이후로, 이러한 영역과 많은 다른 영역들은 최종 사용자 프로그래밍,[34] 예시별[35] 프로그래밍과 데모별 프로그래밍의 관련 영역,[36] 지능형 튜터링 시스템과 같은 유도 프로그래밍에 대한 성공적인 응용 틈새로 나타났다.

그 밖에 최근 귀납 추론이 적용된 분야로는 지식 습득,[37] 인공지능,[38] 강화학습 및 이론 평가,[39][40] 인지과학 등이 있다.[41][33] 지능 에이전트, 게임, 로봇공학, 개인화, 주변 지능 및 휴먼 인터페이스에도 잠재적인 응용 프로그램이 있을 수 있다.

참고 항목

참조

  1. ^ Biermann, A.W. (1992). Shapiro, S.C. (ed.). "Automatic programming". Encyclopedia of Artificial Intelligence: 18–35.
  2. ^ Rich, C.; Waters, R.C. (1993). Yovits, M.C. (ed.). Approaches to automatic programming (PDF). Advances in Computers. Vol. 37. pp. 1–57. doi:10.1016/S0065-2458(08)60402-7. ISBN 9780120121373.
  3. ^ Lowry, M.L.; McCarthy, R.D., eds. (1991). Automatic software design.
  4. ^ Manna, Z.; Waldinger, R. (1992). "Fundamentals of deductive program synthesis". IEEE Trans Softw Eng. 18 (8): 674–704. CiteSeerX 10.1.1.51.817. doi:10.1109/32.153379.
  5. ^ Flener, P. (2002). "Achievements and prospects of program synthesis". In Kakas, A.; Sadri, F. (eds.). Computational Logic: Logic Programming and Beyond. Computational Logic: Logic Programming and Beyond; Essays in Honour of Robert A. Kowalski. Lecture Notes in Computer Science. Vol. LNAI 2407. pp. 310–346. 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. S2CID 7474210.
  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. S2CID 15277948.
  8. ^ Smith, D.R. (1984). Biermann, A.W.; Guiho, G. (eds.). "The synthesis of LISP programs from examples: a survey". Automatic Program Construction Techniques: 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. CiteSeerX 10.1.1.329.5312. doi:10.1007/BF03037089. S2CID 5462416.
  11. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (eds.). "A Note on Inductive Generalization" (PDF). Machine Intelligence. 5: 153–163.
  12. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (eds.). "A Further Note on Inductive Generalization". Machine Intelligence. 6: 101–124.
  13. ^ Muggleton, S.H.; Feng, C. (1990). "Efficient induction of logic programs". Proceedings of the Workshop on Algorithmic Learning Theory. 6: 368–381. S2CID 14992676.
  14. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1993). "Avoiding Pitfalls When Learning Recursive Theories". IJCAI: 1050–1057. S2CID 11138624.
  15. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1995). "Induction of logic programs: FOIL and related systems" (PDF). 13 (3–4). Springer: 287–312. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  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", in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.), Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 117–152
  18. ^ Koza, J.R. (1992). Genetic Programming: vol. 1, On the programming of computers by means of natural selection. MIT Press. ISBN 9780262111706.
  19. ^ Olsson, J.R. (1995). "Inductive functional programming using incremental program transformation". Artificial Intelligence. 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" (PDF). PRICAI 2008: Trends in Artificial Intelligence. Lecture Notes in Computer Science. Vol. 5351. pp. 199–210. CiteSeerX 10.1.1.606.1447. doi:10.1007/978-3-540-89197-0_21. ISBN 978-3-540-89196-3. {{cite book}}: 누락 또는 비어 있음 title= (도움말)
  21. ^ Angluin, D.; C.H., Smith (1983). "Inductive inference: Theory and methods". ACM Computing Surveys. 15 (3): 237–269. doi:10.1145/356914.356918. S2CID 3209224.
  22. ^ Gold, E.M. (1967). "Language identification in the limit". Information and Control. 10 (5): 447–474. doi:10.1016/s0019-9958(67)91165-5.
  23. ^ 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.; 여기: 제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: 507–512.
  25. ^ Lloyd, J.W. (2001). "Knowledge Representation, Computation, and Learning in Higher-order Logic" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  26. ^ Lloyd, J.W. (2003). Logic for learning: learning comprehensible theories from structured data. Springer. ISBN 9783662084069.
  27. ^ 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. S2CID 7255690.
  28. ^ Henderson, R.J.; Muggleton, S.H. (2012). "Automatic invention of functional abstractions" (PDF). Advances in Inductive Logic Programming.
  29. ^ Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). "Inducing probabilistic programs by Bayesian program merging". arXiv:1110.5667 [cs.AI].
  30. ^ Muggleton, S. (2000). "Learning stochastic logic programs" (PDF). 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:1110.5667 [cs.AI].
  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. 28: 80–99. doi:10.1016/j.cogsys.2013.07.003. S2CID 7602205.
  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. ISBN 9781558606883.
  36. ^ Cypher, E.; Halbert, D.C. (1993). Watch what I do: programming by demonstration. ISBN 9780262032131.
  37. ^ 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.
  38. ^ Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). "Combining analytical and evolutionary inductive programming" (PDF). Proceedings of the Second Conference on Artificial General Intelligence: 19–24.
  39. ^ Hernandez-Orallo, J. (2000). "Constructive reinforcement learning". International Journal of Intelligent Systems. 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.
  40. ^ Kemp, C.; Goodman, N.; Tenenbaum, J.B. (2007). "Learning and using relational theories" (PDF). Advances in Neural Information Processing Systems: 753–760.
  41. ^ 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. S2CID 18613664.

추가 읽기

외부 링크