帰納的プログラミング

帰納的プログラミング( IP ) は自動プログラミングの特殊な領域であり、人工知能とプログラミングの研究をカバーし、入出力例や制約などの不完全な仕様から、 通常は宣言型(論理型または関数型) で多くの場合再帰的なプログラムを学習することを扱います。

使用されるプログラミング言語に応じて、帰納的プログラミングにはいくつかの種類があります。LispやHaskellなどの関数型プログラミング言語を使用する帰納的関数型プログラミング、そして特にPrologなどの論理型プログラミング言語と記述論理などの他の論理表現を使用する帰納的論理型プログラミングが最も普及していますが、制約プログラミングや確率プログラミングなどの他の（プログラミング）言語パラダイムも使用されてきました。

意味

帰納的プログラミングは、不完全な（形式的な）仕様からプログラムやアルゴリズムを学習するあらゆるアプローチを包含します。IPシステムへの入力としては、訓練入力とそれに対応する出力のセット、あるいは対象プログラムの望ましい動作を記述する出力評価関数、特定の出力を計算するプロセスを記述するトレースまたはアクションシーケンス、時間効率や複雑さに関するプログラムの制約、標準データ型などの様々な背景知識、使用する定義済み関数、対象プログラムのデータフローを記述するプログラムスキームまたはテンプレート、解決策やその他のバイアスの探索を導くヒューリスティックなどが挙げられます。

IP システムの出力は、条件文とループまたは再帰制御構造を含む任意のプログラミング言語、またはその他の種類のチューリング完全な表現言語 のプログラムです。

多くのアプリケーションでは、出力プログラムは例と部分的な仕様に関して正確でなければならないため、自動プログラミングまたはプログラム合成内の特別な領域として帰納的プログラミングが考慮されることになります。[ 1 ] [ 2 ]通常は「演繹的」プログラム合成とは対照的です。 [ 3 ] [ 4 ] [ 5 ]通常は仕様が完全です。

一方、帰納的プログラミングは、より一般的な機械学習、より具体的な構造マイニング、あるいはシンボリック人工知能の分野のように、宣言型プログラミング言語や表現言語を自由に使用でき、例に多少の誤りがあっても許容される、より一般的な分野とみなされる場合もあります。その際立った特徴は、必要な例の数、あるいは部分的な仕様の数です。通常、帰納的プログラミング手法は、ほんの数例から学習することができます。

帰納的プログラミングの多様性は、通常、使用されるアプリケーションと言語に由来します。論理プログラミングと関数型プログラミングの他に、関数型論理プログラミング、制約プログラミング、確率プログラミング、アブダクション論理プログラミング、様相論理、アクション言語、エージェント言語、および多くの種類の命令型言語など、他のプログラミングパラダイムと表現言語が帰納的プログラミングで使用または提案されてきました。

歴史

Plotkinの初期の研究[ 6 ] [ 7 ]と彼の「相対最小一般化（rlgg） 」は、帰納的論理プログラミングに大きな影響を与えました。適切な背景知識、例えばGOLEMを用いて、クイックソートなどの再帰Prologプログラムを例から学習することに関して、いくつかの有望な結果が得られました。[ 8 ]しかし、初期の成功の後、コミュニティは再帰プログラムの帰納に関する進歩が限られていることに失望しました。[ 9 ] [ 10 ] [ 11 ] ILPは再帰プログラムにますます重点を置くのではなく、リレーショナルデータマイニングや知識発見への応用を伴う機械学習の設定にますます傾倒していきました。[ 12 ]

ILPの研究と並行して、Koza [ 13 ]は1990年代初頭に、生成とテストに基づくプログラム学習アプローチとして遺伝的プログラミングを提案しました。遺伝的プログラミングの概念は、帰納的プログラミングシステムADATE [ 14 ]と体系的探索に基づくシステムMagicHaskeller [ 15 ]へと発展しました。ここでも、関数型プログラムは、学習対象プログラムの望ましい入出力動作を指定する出力評価（適応度）関数と、正例集合から学習されます。

文法帰納法（文法推論とも呼ばれる）の初期の研究は、帰納的プログラミングと関連している。これは、書き換えシステムや論理プログラムを用いて生成規則を表現できるためである。実際、帰納的推論の初期の研究は、文法帰納法とLispプログラム推論を基本的に同じ問題として扱っていた。[ 16 ]学習可能性に関する結果は、ゴールドの画期的な研究で導入された極限における識別といった古典的な概念に関連していた。[ 17 ]近年では、言語学習の問題は帰納的プログラミングコミュニティによって取り組まれている。[ 18 ] [ 19 ]

近年、古典的なアプローチが再開され、大きな成功を収めて発展してきました。そのため、合成問題は、関数型プログラミングの最新技術、探索ベースの戦略の適度な活用、背景知識の活用、そしてサブプログラムの自動生成を考慮したコンストラクタベースの項書き換えシステムを背景に、再定式化されてきました。プログラム合成以外にも、データ操作、例によるプログラミング、認知モデリング（下記参照）といった分野で、近年、多くの新しく成功した応用が登場しています。

仮説の表現に宣言型言語を用いるという共通の特徴を持つ他のアイデアも検討されてきた。例えば、高階特徴、スキーム、構造化距離の使用は、再帰的なデータ型や構造をより適切に処理するために提唱されてきた。[ 20 ] [ 21 ] [ 22 ]抽象化もまた、累積学習や関数の発明に対するより強力なアプローチとして検討されてきた。[ 23 ] [ 24 ]

帰納的計画法（一般的には生成モデルの形で）における仮説の表現に最近使用されている強力なパラダイムの1つは、確率的計画法（および確率的論理プログラムやベイズ論理プログラミングなどの関連パラダイム）である。[ 25 ] [ 26 ] [ 24 ] [ 27 ]

応用分野

ICML 2005と併せて開催された、帰納的プログラミングのアプローチとアプリケーション (AAIP) に関する最初のワークショップ ( Wayback Machineに 2016-03-03がアーカイブされています) では、「プログラムまたは再帰ルールの学習が求められるすべてのアプリケーションを特定しました。[...] まず、構造学習、ソフトウェア アシスタント、ソフトウェア エージェントが、プログラマーの日常的なタスクの負担を軽減し、エンド ユーザーへのプログラミング サポート、初心者プログラマーやプログラミング チューター システムのサポートに役立つソフトウェア エンジニアリングの領域です。その他のアプリケーション領域としては、言語学習、AI プランニングのための再帰制御ルールの学習、Web マイニングやデータ形式変換のための再帰概念の学習などがあります。」

それ以来、エンドユーザープログラミング[ 28 ] 、関連分野である例によるプログラミング[ 29 ]、デモンストレーションによるプログラミング[ 30 ] 、インテリジェントな指導システムなど、これらや他の多くの分野が帰納的プログラミングの成功した応用分野であることが示されてきました。

帰納的推論が最近応用されている他の分野としては、知識獲得、[ 31 ]、汎用人工知能、[ 32 ] 、強化学習と理論評価、[ 33 ]、[ 34 ]、一般的な認知科学[ 35 ]、[ 27 ]などがある。また、インテリジェントエージェント、ゲーム、ロボット工学、パーソナライゼーション、アンビエントインテリジェンス、ヒューマンインターフェースなどにも応用が期待される。

参照

参考文献

  1. ^ Biermann, AW (1992). Shapiro, SC (編). 「自動プログラミング」.人工知能百科事典: 18–35 .
  2. ^ Rich, C.; Waters, RC (1993). Yovits, MC (編).自動プログラミングへのアプローチ(PDF) . Advances in Computers. Vol. 37. pp.  1– 57. doi : 10.1016/S0065-2458(08)60402-7 . ISBN 9780120121373。
  3. ^ Lowry, ML; McCarthy, RD 編 (1991).自動ソフトウェア設計.
  4. ^マナ、Z。 Waldinger、R. (1992)。 「演繹的プログラム合成の基礎」。IEEE トランス ソフトウェアエンジニアリング18 (8): 674–704。CiteSeerX 10.1.1.51.817。土井: 10.1109/32.153379。 
  5. ^ Flener, P. (2002). 「プログラム合成の成果と展望」. Kakas, A.; Sadri, F. (編).計算論理：論理プログラミングとその先へ；Robert A. Kowalski記念エッセイ集. コンピュータサイエンス講義ノート. Vol. LNAI 2407. pp.  310– 346. doi : 10.1007/3-540-45628-7_13 . ISBN 978-3-540-43959-2。
  6. ^ Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D. (編). 「帰納的一般化に関するノート」(PDF) .機械知能. 5 : 153–163 .
  7. ^ Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D. (編). 「帰納的一般化に関する更なる考察」.機械知能. 6 : 101–124 .
  8. ^ Muggleton, SH; Feng, C. (1990). 「論理プログラムの効率的な帰納法」.アルゴリズム学習理論ワークショップ論文集. 6 : 368–381 . S2CID 14992676 . 
  9. ^ Quinlan, JR; Cameron-Jones, RM (1993). 「再帰理論を学ぶ際の落とし穴を避ける」IJCAI : 1050–1057 . S2CID 11138624 . 
  10. ^ Quinlan, JR; Cameron-Jones, RM (1995). 「論理プログラムの誘導：FOILと関連システム」（PDF） . 13 ( 3– 4). Springer: 287– 312. 2017年9月7日時点のオリジナル（PDF）からアーカイブ。 2017年9月7日閲覧。{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  11. ^ Flener, P.; Yilmaz, S. (1999). 「再帰論理プログラムの帰納的合成：成果と展望」 . The Journal of Logic Programming . 41 (2): 141– 195. doi : 10.1016/s0743-1066(99)00028-x .
  12. ^ Džeroski, Sašo (1996)、「Inductive Logic Programming and Knowledge Discovery in Databases」、Fayyad, UM; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R. (eds.)、Advances in Knowledge Discovery and Data Mining、MIT Press、pp.  117– 152
  13. ^ Koza, JR (1992).遺伝的プログラミング: 第1巻, 自然選択によるコンピュータプログラミングについて. MIT Press. ISBN 9780262111706。
  14. ^ Olsson, JR (1995). 「増分プログラム変換を用いた帰納的関数型プログラミング」人工知能. 74 (1): 55– 83. doi : 10.1016/0004-3702(94)00042-y .
  15. ^片山 進 (2008). 「反復深化を用いたモンテカルロ探索による関数型プログラムの効率的な網羅的生成」(PDF) . PRICAI 2008: 人工知能の動向. コンピュータサイエンス講義ノート. 第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。
  16. ^ Angluin, D.; CH, Smith (1983). 「帰納的推論：理論と方法」. ACM Computing Surveys . 15 (3): 237– 269. doi : 10.1145/356914.356918 . S2CID 3209224 . 
  17. ^ Gold, EM (1967). 「限界における言語識別」情報と制御10 (5): 447–474 . doi : 10.1016/s0019-9958(67)91165-5 .
  18. ^マグルトン、スティーブン (1999). 「帰納的論理プログラミング：論理言語学習における課題、結果、そして挑戦」人工知能. 114 ( 1–2 ): 283–296 . doi : 10.1016/s0004-3702(99)00067-3 .; ここ: セクション2.1
  19. ^ Olsson, JR; Powers, DMW (2003). 「自動プログラミングによる人間の言語の機械学習」.国際認知科学会議論文集: 507–512 .
  20. ^ Lloyd, JW (2001). 「高階論理における知識表現、計算、学習」(PDF) .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  21. ^ロイド、JW (2003). 『学習のための論理：構造化データから理解可能な理論を学ぶ』 シュプリンガー. ISBN 9783662084069。
  22. ^ Estruch, V.; Ferri, C.; Hernandez-Orallo, J.; Ramirez-Quintana, MJ (2014). 「距離と一般化のギャップを埋める」 .計算知能. 30 (3): 473– 513. doi : 10.1111/coin.12004 . hdl : 10251/34946 . S2CID 7255690 . 
  23. ^ Henderson, RJ; Muggleton, SH (2012). 「関数型抽象の自動発明」(PDF) .帰納的論理プログラミングの進歩.
  24. ^ a b Irvin, H.; Stuhlmuller, A.; Goodman, ND (2011). 「ベイズプログラムマージによる確率的プログラムの誘導」arXiv : 1110.5667 [ cs.AI ].
  25. ^ Muggleton, S. (2000). 「確率的論理プログラムの学習」(PDF) . Electron. Trans. Artif. Intell . 4(B) : 141– 153. 2017年9月7日時点のオリジナル(PDF)からアーカイブ。 2017年9月7日閲覧。
  26. ^ De Raedt, L.; Kersting, K. (2008).確率的帰納的論理プログラミング. Springer.
  27. ^ a b Stuhlmuller, A.; Goodman, ND (2012). 「ネストされた条件付けによる推論についての推論：確率的プログラムによる心の理論のモデリング」認知システム研究. 28 : 80–99 . doi : 10.1016/j.cogsys.2013.07.003 . S2CID 7602205 . 
  28. ^ Lieberman, H.; Paternò, F.; Wulf, V. (2006).エンドユーザー開発. Springer.
  29. ^リーバーマン、H. (2001). 「あなたの願いは私の命令：例によるプログラミング」 モーガン・カウフマン. ISBN 9781558606883。
  30. ^ Cypher, E.; Halbert, DC (1993). Watch what I do: programming by demonstration . MIT Press. ISBN 9780262032131。
  31. ^ Schmid, U. ; Hofmann, M. ; Kitzelmann, E. (2009). 「認知ルール獲得装置としての解析的帰納的プログラミング」(PDF) .第2回汎用人工知能会議議事録: 162–167 .
  32. ^ Crossley, N.; Kitzelmann, E.; Hofmann, M.; Schmid, U. (2009). 「分析的帰納的プログラミングと進化的帰納的プログラミングの融合」(PDF) .第2回汎用人工知能会議議事録: 19–24 .
  33. ^ Hernandez-Orallo, J. (2000). 「構成的強化学習」. 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 . S2CID 123390956 .  
  34. ^ Kemp, C.; Goodman, N.; Tenenbaum, JB (2007). 「関係理論の学習と利用」(PDF) . 『神経情報処理システムの進歩』753–760 .
  35. ^ Schmid, U. ; Kitzelmann, E. (2011). 「知識レベルでの帰納的ルール学習」.認知システム研究. 12 (3): 237– 248. doi : 10.1016/j.cogsys.2010.12.002 . S2CID 18613664 . 

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Inductive_programming&oldid=1325138944」より取得