帰納的プログラミング

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

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

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

IPシステムの出力は、条件分岐やループ、再帰制御構造を含む任意のプログラミング言語で記述されたプログラム、あるいはその他のチューリング完全な表現言語である。

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

場合によっては、帰納的プログラミングは、宣言型プログラミングや表現言語であればどれでも使用できる、より一般的な分野と見なされます。一般的な機械学習、より具体的な構造マイニング、あるいは記号的人工知能の分野のように、例に多少の誤差があっても構いません。特徴的なのは、必要な例の数や部分的な仕様です。通常、帰納的プログラミング手法は、ほんの数個の例から学習できます。

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

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

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

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

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

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

帰納的プログラミングにおける仮説の表現に最近用いられている強力なパラダイムの一つは、確率的プログラミング（および確率的論理プログラムやベイズ論理プログラミングなどの関連パラダイム）である。 ^{[ 25 ] [ 26 ] [ 24 ] [ 27 ]}

ICML 2005と併催された、帰納的プログラミングのアプローチと応用に関する最初のワークショップ（AAIP、アーカイブは2016年3月3日にWayback Machineに保存）では、「プログラムや再帰ルールの学習が求められるすべてのアプリケーション」が特定されました。[...] まず、ソフトウェアエンジニアリングの分野では、構造学習、ソフトウェアアシスタント、ソフトウェアエージェントがプログラマーのルーチン作業の軽減、エンドユーザーへのプログラミングサポート、初心者プログラマーやプログラミングチューターシステムのサポートに役立ちます。その他の応用分野としては、言語学習、AIプランニングのための再帰制御ルールの学習、Webマイニングやデータ形式変換における再帰概念の学習などがあります。

それ以来、これらの分野やその他多くの分野が、帰納的プログラミングの成功した応用分野であることが示されており、例えばエンドユーザープログラミング^{[ 28 ]}、例によるプログラミング^{[ 29 ]}やデモンストレーションによるプログラミング^{[ 30 ]}といった関連分野、そしてインテリジェントチュータリングシステムなどが挙げられる。

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

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

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