帰納プログラミング

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

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

定義

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

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

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

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

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

歴史

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

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

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

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

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

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

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

応用領域

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

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

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

脚注

参考文献

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.