帰納的プログラミング

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

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

帰納的プログラミングには、不完全な (形式的な) 仕様からプログラムやアルゴリズムを学習することに関係するすべてのアプローチが組み込まれています。IP システムで可能な入力は、トレーニング入力とそれに対応する出力のセット、または対象プログラムの望ましい動作を記述する出力評価関数、特定の出力を計算するプロセスを記述するトレースまたはアクション シーケンス、時間効率や複雑さに関して誘導されるプログラムの制約、標準データ型などのさまざまな種類の背景知識、使用する定義済み関数、対象プログラムのデータ フローを記述するプログラム スキームまたはテンプレート、ソリューションの検索をガイドするヒューリスティック、またはその他のバイアスです。

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

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

他のケースでは、帰納的プログラミングは、一般的な機械学習、より具体的な構造マイニングの領域、またはシンボリック人工知能の領域のように、宣言型プログラミング言語または表現言語を使用でき、例に多少のエラーがあってもよい、より一般的な領域と見なされます。際立った特徴は、必要な例または部分的な仕様の数です。通常、帰納的プログラミング手法は、ほんの数例から学習できます。

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

再帰的関数プログラムの帰納的合成に関する研究は1970年代初頭に始まり、サマーズの独創的なTHESISシステム^{[6]とビアマンの研究[7]}によって確固たる理論的基礎が築かれました。 これらのアプローチは2つの段階に分かれています。第1段階では、入出力例を少数の基本演算子を使用して非再帰プログラム（トレース）に変換します。第2段階では、トレースの規則性を検索し、それを再帰プログラムに折り込みます。1980年代半ばまでの主な結果はスミスによって概説されています。^[8]合成可能なプログラムの範囲に関する進歩が限られていたため、研究活動は次の10年間で大幅に減少しました。

1980年代初頭、論理プログラミングの出現は新たな活力と新たな方向性をもたらしました。特に、シャピロのMISシステム^{[9]が、最終的に帰納的論理プログラミング（ILP） [10]}という新しい分野を生み出しました。プロトキン^{[11] [12]}の初期の研究と彼の「相対最小一般化（rlgg）」は、帰納的論理プログラミングに多大な影響を与えました。ILPの研究のほとんどは、再帰的論理プログラムだけでなく、論理的表現からの記号仮説の機械学習にも焦点が当てられているため、より広範な問題に取り組んでいます。ただし、GOLEMなどの適切な背景知識と組み合わせた例からクイックソートなどの再帰的Prologプログラムを学習することに関する有望な結果もありました。^[13]しかし、初期の成功の後、コミュニティは再帰プログラムの誘導に関する進歩が限られていることに失望しました。 ^{[14] [15] [16] ILPは再帰プログラムにますます重点を置かなくなり、}リレーショナルデータマイニングや知識発見への応用を伴う機械学習の設定にますます傾倒していきました。^[17]

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

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

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

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

帰納的プログラミング（一般的には生成モデルの形式）における仮説の表現に最近使用されている強力なパラダイムの1つは、確率的プログラミング（および確率的論理プログラムやベイズ論理プログラミングなどの関連パラダイム）です。^{[30] [31] [29] [32]}

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

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

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

• 進化的プログラミング
• 帰納的推論
• テスト駆動開発

• バンベルク大学が主催する帰納的プログラミング コミュニティ ページ。