コンテンツにスキップ

帰納プログラミング

出典: フリー百科事典『ウィキペディア（Wikipedia）』

帰納プログラミング (Inductive Programming, IP) は人工知能とプログラミングの研究分野をまたぐ自動プログラミングの特殊分野である．通常，入出力例や制約などの不完全な仕様からの，宣言型（論理型または関数型）言語のプログラムの学習を扱う．学習されるプログラムはしばしば再帰的である．

使用するプログラミング言語によって，いくつかの種類の帰納プログラミングが存在する．LispやHaskellなどの関数型言語を用いる帰納関数プログラミング，そして特に，Prologのような論理型言語や記述論理（英語版）のようなその他の論理的表現を用いる帰納論理プログラミング（英語版）がこれまでよく知られていたが，制約プログラミングや確率プログラミングのようなその他のプログラミング言語も用いられている．

定義

[編集]

帰納プログラミングは，不完全な形式的仕様からのプログラムやアルゴリズムの学習に関する全てのアプローチを含んでいる．帰納プログラミングシステムへの可能な入力形態としては，訓練入力と対応する出力の組の集合や出力評価関数，意図したプログラムの望ましい挙動の記述，トレースすなわち特定の出力を計算する過程を記述した行動系列，得られるプログラムの計算量を考慮した制約，種々の背景知識が挙げられる．背景知識としては，標準的なデータ型，使用する定義済み関数，データの流れや意図したプログラムを記述するプログラムの概形あるいはテンプレート，解の探索を誘導するヒューリスティクスやその他のバイアスが挙げられる．

帰納プログラミングシステムの出力は，条件分岐やループや再帰構造を含む様々なプログラミング言語や，その他のチューリング完全な表現言語の形態を取り得る．

多くの応用において，出力プログラムは例や不完全な仕様と合致することが要求される．このため，通常完全な仕様を用いる演繹的プログラム合成[1][2][3]と対比されて，帰納プログラミングは自動プログラミングやプログラム合成[4][5]の分野内において特殊な分野と考えられている．

場合によっては，帰納プログラミングは，宣言型プログラミングや表現言語を用いることができる，より一般的な領域と考えられることもある．一般の機械学習や，構造マイニング（英語版）の特定領域や，記号人工知能の領域に見られるように，例の中にある程度の誤りを認めることもある．これらの他分野との明らかな違いの1つは，必要とされる例や不完全仕様の数である．一般に，帰納プログラミング手法は少ない例から学習することができる．

帰納プログラミングの多様性は，適用先や使用言語の多様性から来ていることが多い．論理プログラミングや関数プログラミングの他にも，関数論理プログラミング（英語版），制約プログラミング，確率プログラミング，abductive logic programming（英語版）, 様相論理，action language（英語版）, agent languageや多くの種類の命令型言語など，多くのプログラミング言語や表現言語が，使用され，または使用することが提案されている．

歴史

[編集]

再帰的関数プログラムの帰納的合成の研究は1970年代初期に始まり，かのSummersのTHESISシステム[6]とBiermannの研究[7] を理論的基盤に据えていた． これらのアプローチは2段階に分かれていた． つまり，第1段階として，入出力例は少数の基本演算集合を用いた非再帰的プログラム（トレース）に変換され， 第2段階として，トレース中の規則性を探索して，それらを用いて再帰的プログラムに畳み込むというものである． 1980年代半ばまでの主な結果は，Smithによってサーベイされている．[8] 合成できるプログラムの範囲についてあまり進展が見られなかったため，研究活動は次の10年間で著しく減退することとなった．

1980年代初期には，論理プログラミングの到来によって新しい活気や方向性が生まれた．特に，ShapiroのMISシステム[9]によって，最終的には帰納論理プログラミングという新しい分野が誕生することとなった． Plotkinの初期の研究[10][11]と相対的最小汎化 (relative least general generalization, rlgg)は，帰納論理プログラミングに多大な衝撃を与えた． ほとんどの帰納論理プログラミングの研究は，再帰的論理プログラムのみならず論理的表現からの記号論的仮説の機械学習一般に焦点を当てているため， より広いクラスの問題を扱う．しかし，GOLEM[12]の例のように，例とともに適切な背景知識を与えることによるquicksortのような再帰的Prologプログラムの学習を行うような，希望に満ちた結果もあった．しかし再び，最初の成功の後，帰納論理プログラミングによる再帰的プログラムの合成の進展の遅さに人々は失望した．[13][14][15] 再帰的プログラムの合成への注目は日増しに減っていき，代わりに関係データマイニングや知識発見といった応用のある機械学習に傾倒していった． [16]

帰納論理プログラミングの研究とは独立に，生成テスト法に基づいたプログラム学習法として，Koza[17] は1990年代初頭に遺伝的プログラミングを提案した．遺伝的プログラミングの考え方はさらに進んで，帰納プログラミングシステムADATE[18] および系統的探索に基づいたシステムMagicHaskeller[19]につながっていった．ここで再び，再帰的関数プログラムの学習が，学習するプログラムの望ましい入出力挙動を規定する正例集合と出力評価関数（適応度関数）(ADATEの場合)に基づいて行われることとなる．

文法推論（英語版） (あるいはgrammatical inference)の初期の研究は，書き換えシステムや論理プログラムを用いてプロダクションルールを表現できるため，帰納プログラミングに関連している．実際，帰納推論の初期の研究は，grammar inductionとLispプログラム推論を基本的に同じ問題とみなしていた．[20] 学習可能性の観点からの結果は，Goldの有名な研究において導入された極限での同一性(identification-in-the-limit)のような古典的な概念に関連している．[21] より最近において，言語学習問題は帰納プログラミングコミュニティにおいて扱われている． [22][23]

近年，古典的アプローチの延長上にある研究も再開し，多大な進展がみられる．プログラム合成問題は，最近の関数プログラミングの技術，適度に探索を用いた戦略，背景知識，部分解の自動合成を考慮したコンストラクタ項書換え系の背景のもとで再構築されている．特に，データ処理，例示プログラミング，認知モデリングといった，プログラム合成を超えた多くの分野への応用がなされている．（下記参照）

仮説表現に宣言型言語を用いていることによる特徴を生かしたその他のアイデアも研究されている．たとえば，再帰的データ型や構造をうまく扱う上で，高階の構造を扱うことが提案されている．[24][25][26] 抽象化についても，cumulative learningやfunction inventionへのより強力なアプローチとして研究されている． [27][28]

帰納プログラミングにおける仮説表現において最近用いられている強力なパラダイムの1つは確率プログラミング（及び確率的論理プログラムやベイジアン論理プログラミングといった関連パラダイム）である． [29][30][28][31]

応用領域

[編集]

最初の帰納プログラミングのアプローチと応用に関するワークショップ(Approaches and Applications of Inductive Programming, AAIP) はICML（英語版） 2005のもとで開催され，プログラムや再帰的ルールの学習が求められるあらゆる応用が考えられた．まずは，ソフトウェアエンジニアリングの領域において，構造の学習，ソフトウェアによる補助，およびソフトウェアエージェントがプログラマを反復仕事から解放する手伝いをしたり，一般ユーザにプログラミング補助をしたり，あるいは初心プログラマやプログラミング教育システムの補助を行うといったことが考えられた． さらなる応用領域は，言語の学習，AIプランニングにおける再帰的制御則の学習，ウェブマイニングにおける再帰的な概念の学習，あるいはデータ形式の変換とされた．

それ以降，これら及びその他の多くの領域，たとえば一般ユーザのプログラミング[32] ，例示プログラミング（英語版）[33]や演示プログラミング（英語版）[34]の関連領域，及び知的教育システムにおいて，帰納プログラミングがうまく行く事がわかってきた．加えて，自動データ処理は，Microsoft ExcelにおけるFlash Fillのような帰納プログラミングのキラーアプリとして話題に登ってくる． [35][36]

最近帰納推論が応用された他の領域としては，知識獲得[37]，強いAI[38]，強化学習と理論評価[39][40] ，及び認知科学全般がある．[41][31] また，知的エージェント，ゲーム，ロボット工学，パーソナリゼーション， などの応用も考えられる．

脚注

[編集]
  1. ^ Lowry, M.L.; McCarthy, R.D., eds (1991). Automatic software design 
  2. ^ Manna, Z.; Waldinger, R. (1992). “Fundamentals of deductive program synthesis”. IEEE Trans Softw Eng 18(8): 674–704. 
  3. ^ Flener, P. (2002). Kakas, A.; Sadri, F.. eds. “Achievements and prospects of program synthesis”. Computational logic: logic programming and beyond; essays in honour of Robert A. Kowalski (Springer) LNAI 2407: 310–346. 
  4. ^ Biermann, A.W. (1992). Shapiro, S.C.. ed. “Automatic programming”. Encyclopedia of artificial intelligence (Wiley): 18–35. 
  5. ^ Rich, C.; Waters, R.C. (1993). Yovits, M.C.. ed. “Approaches to automatic programming”. Advances in computers (Academic Press) 37. 
  6. ^ Summers, P.D. (1977). “A methodology for LISP program construction from examples”. J ACM 24(1): 161–175. 
  7. ^ Biermann, A.W. (1978). “The inference of regular LISP programs from examples”. IEEE Trans Syst Man Cybern 8(8): 585–600. 
  8. ^ Smith, D.R. (1984). Biermann, A.W.; Guiho, G.. eds. “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. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D.. eds. “A Note on Inductive Generalization”. Machine Intelligence (Edinburgh University Press) 5: 153–163. 
  11. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D.. eds. “A Further Note on Inductive Generalization”. Machine Intelligence (Edinburgh University Press) 6: 101–124. 
  12. ^ 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. 
  13. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1993). “Avoiding Pitfalls When Learning Recursive Theories”. IJCAI: 1050–1057. 
  14. ^ Quinlan, J.R.; Cameron-Jones, R.M. (1995). Induction of logic programs: FOIL and related systems. 13(3-4). Springer. pp. 287–312. 
  15. ^ Flener, P.; Yilmaz, S. (1999). “Inductive synthesis of recursive logic programs: Achievements and prospects”. The Journal of Logic Programming 41(2): 141–195. 
  16. ^ Džeroski, Sašo (1996), “Inductive Logic Programming and Knowledge Discovery in Databases”, in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P. et al., Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 117–152 
  17. ^ Koza, J.R. (1992). Genetic Programming: vol. 1, On the programming of computers by means of natural selection. MIT Press 
  18. ^ Olsson, J.R. (1995). “Inductive functional programming using incremental program transformation”. Artificial Intelligence (Elsevier) 74(1): 55–83. 
  19. ^ Katayama, Susumu (2008). “Efficient exhaustive generation of functional programs using Monte-Carlo search with iterative deepening”. PRICAI 2008: Trends in Artificial Intelligence: 199–210. 
  20. ^ Angluin, D.; C.H., Smith (1983). “Inductive inference: Theory and methods”. ACM Computing Surveys (ACM) 15: 237–269. 
  21. ^ Gold, E.M. (1967). “Language identification in the limit”. Information and Control (Elsevier) 10 (5): 447–474. オリジナルの2009-01-25時点におけるアーカイブ。. https://web.archive.org/web/20090125120159/http://www.isrl.uiuc.edu/~amag/langev/paper/gold67limit.html. 
  22. ^ Muggleton, Stephen (1999). “Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic”. Artificial Intelligence 114: 283–296. ; here: Sect.2.1
  23. ^ 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. 
  24. ^ Lloyd, J.W. (2001). Knowledge Representation, Computation, and Learning in Higher-order Logic. 
  25. ^ Lloyd, J.W. (2003). Logic for learning: learning comprehensible theories from structured data. Springer 
  26. ^ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, M.J. (2014). “Bridging the gap between distance and generalization”. Computational Intelligence (Wiley). 
  27. ^ Henderson, R.J.; Muggleton, S.H. (2012). “Automatic invention of functional abstractions”. Advances in Inductive Logic Programming (Imperial College Press). 
  28. ^ a b Irvin, H.; Stuhlmuller, A.; Goodman, N.D. (2011). “Inducing probabilistic programs by Bayesian program merging”. arXiv preprint arXiv:1110.5667 (Elsevier). 
  29. ^ Muggleton, S. (2000). “Learning stochastic logic programs”. Electron. Trans. Artif. Intell. 4(B): 141-153. 
  30. ^ De Raedt, L.; Kersting, K. (2008). Probabilistic inductive logic programming. Springer 
  31. ^ 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). 
  32. ^ Lieberman, H.; Paternò, F.; Wulf, V. (2006). End user development. Springer 
  33. ^ Lieberman, H. (2001). Your wish is my command: Programming by example. Morgan Kaufmann 
  34. ^ Cypher, E.; Halbert, D.C.. Watch what I do: programming by demonstration publisher=. 
  35. ^ Gulwani, S.; Harris, W.R.; Singh, R. (2012). “Spreadsheet data manipulation using examples”. Communications of the ACM (ACM) 55(8): 97–105. 
  36. ^ Harris, Steven (1 October 2013). “Excel 2013 - Flash Fill”. Experts-Exchange.com. Experts Exchange. 23 November 2013閲覧。
  37. ^ 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. 
  38. ^ 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. 
  39. ^ Hernandez-Orallo, J. (2000). “Constructive reinforcement learning”. International Journal of Intelligent Systems 15(3): 241–264. 
  40. ^ Kemp, C.; Goodman, N.; Tenenbaum, J.B. (2007). “Learning and using relational theories”. 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. 

参考文献

[編集]
  • Flener, P.; Schmid, U. (2008). “An introduction to inductive programming”. Artificial Intelligence Review (Springer) 29(1): 45–62. 
  • Kitzelmann, E. (2010). “Inductive programming: A survey of program synthesis techniques”. Approaches and Applications of Inductive Programming (Springer): 50–73. 
  • Partridge, D. (1997). “The case for inductive programming”. Computer (IEEE) 30(1): 36–41. 
  • Flener, P.; Partridge, D. (2001). “Inductive Programming”. Automated Software Engineering (Springer) 8(2): 131–137. 
  • Hofmann, M.; Kitzelmann, E. (2009). “A unifying framework for analysis and evaluation of inductive programming systems”. Proceedings of the Second Conference on Artificial General Intelligence: 55–60. 
  • Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 0-13-457870-8. http://www-ai.ijs.si/SasoDzeroski/ILPBook/ 
  • Muggleton, S.; De Raedt, Luc.; Poole, D.; Bratko, I.; Flach, P.; Inoue, K.; Srinivasan, A. (2012). “ILP turns 20”. Machine Learning (Springer) 86(1): 3–23. 

関連項目

[編集]

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=帰納プログラミング&oldid=89938922」から取得