帰納プログラミングは、人工知能の一分野であり、不完全な仕様からコンピュータプログラムを自動的に合成することに関係している。人間が明示的な命令を書く従来のプログラミングとは異なり、帰納プログラミングは、望ましい動作の例、論理的性質、またはその他の部分的な制約からプログラムを推論する。「帰納的」という用語は、特定の事例から一般的な規則へと一般化するプロセスを反映しており、これは人間の学習と自動プログラム合成の両方において中心的な推論形式である。
この分野は、機械学習、自動推論、プログラミング言語理論からのアイデアを活用している。1970年代から1980年代の初期の研究は、入力と出力のペアから小さな再帰関数を合成することに焦点を当てており、しばしば可能なプログラムの空間上の探索を用いていた。時が経つにつれて、その範囲はより複雑なデータ構造、高階関数、そして現代の学習パラダイムとの統合へと拡大した。帰納プログラミングは、形式的な論理仕様からプログラムを導出する演繹的プログラム合成とは異なるが、実際にはこの2つのアプローチはしばしば相互に補完し合う。
歴史的基礎
帰納プログラミングは、人工知能の初期の時代にルーツを持つ。1970年代、ゼロックス・パルクや他の機関の研究者たちは、例からLispプログラムを学習できるシステムを探求した。注目すべきマイルストーンは、1975年に開発されたTHESYSシステムであり、これは入力と出力のペアから再帰的なLisp関数を合成した。この研究は、単純な探索ベースの手法が、リスト反転や算術演算などのタスクのプログラムを発見できることを実証した。
1980年代には、論理プログラミングの台頭とともにこの分野は勢いを増した。MIS（モデル推論システム）などのシステムや後のアプローチは、帰納論理プログラミング（ILP）を用いて、正例と負例からProlog節を推論した。ILPは独立した研究領域となり、バイオインフォマティクスや自然言語処理への応用が進んだ。1990年代までに、カーネギーメロン大学やMIT CSAILの研究者たちは、プログラム探索の複雑さや背景知識の役割を含む理論的基礎の多くを形式化した。
2010年代の深層学習の出現は、帰納プログラミングに新しいツールをもたらした。特に系列変換モデルなどのニューラルネットワークがプログラム合成タスクに適用され、プログラム生成を翻訳問題として扱った。このハイブリッドアプローチは、しばしばニューラルプログラム合成と呼ばれ、機械学習のパターン認識の強みと従来の探索の形式的保証を組み合わせた。
中核技術
帰納プログラミングの手法は、大まかに探索ベースと学習ベースのアプローチに分類できる。探索ベースの手法は、与えられた例に各候補がどれだけ適合するかを測定するスコアリング関数に導かれ、構造化された空間内の候補プログラムを列挙する。この空間は、しばしば文法やプログラムテンプレートのセットによって定義される。列挙探索、遺伝的プログラミング、制約解決などの技法がこのカテゴリに該当する。例えば、2011年にマイクロソフトリサーチで開発されたFlashFillシステムは、文字列変換と探索の組み合わせを用いて、ユーザーが提供した例からスプレッドシートの数式を合成した。
学習ベースの手法は、統計モデルを用いてプログラム構造を直接予測する。一般的なアーキテクチャはエンコーダ・デコーダモデルであり、エンコーダが入力と出力の例を処理し、デコーダがプログラムをトークンごとに生成する。これらのモデルは通常、プログラムと例のペアの大規模データセットで訓練され、損失関数としてクロスエントロピーを用いる。2017年に導入されたトランスフォーマーアーキテクチャは、長距離依存関係を処理できるため、そのようなシステムの標準的なバックボーンとなっている。しかし、純粋にニューラルなアプローチは正確な正しさに苦労することが多いため、しばしば探索と組み合わせられる。モデルが候補プログラムを提案し、検証器がそれらを例に対してチェックする。
もう一つの重要な技法はカリキュラム学習の使用であり、モデルは一般化を改善するために徐々に難しい例で訓練される。さらに、データ拡張は合成トレーニングデータを生成するために使用され、プログラムパターンのカバレッジを拡大する。これらの手法は、文字列操作からデータベースクエリ、さらには大規模言語モデル支援のコード生成に至るまでの領域に適用されている。
応用
帰納プログラミングは、いくつかの領域で実用的な応用を見出している。顕著な用途の一つはエンドユーザープログラミングであり、非専門家のユーザーが例を通じて望ましい動作を指定できる。マイクロソフトのFlashFillはExcelに統合されており、広く展開された例である。ユーザーは望ましい変換の例をいくつか入力し、システムが列の残りの部分の数式を合成する。このアプローチは、手動のデータクリーニングの膨大な時間を節約してきた。
ソフトウェア工学では、帰納プログラミングは自動バグ修正とテスト生成を支援する。失敗するテストケースが与えられると、合成システムはテストを通過させるパッチを推論でき、しばしばプログラム編集の探索を用いる。この技法は学術ツールや商用製品で探求されてきたが、意味的正しさを保証することの難しさから、依然として活発な研究領域である。
生成AIの台頭も帰納プログラミングに影響を与えている。OpenAIやAnthropicによって開発されたような現代の大規模言語モデルは、自然言語の記述からコードを生成でき、これは仕様がテキストプロンプトである帰納プログラミングの一形態と見なすことができる。これらのモデルはしばしばコードコーパスで微調整され、幅広いタスクに対して機能的なプログラムを生成できる。しかし、形式的保証が欠けており、その出力は通常、テストや人間のレビューを通じて検証される。
課題と限界
帰納プログラミングにおける中心的な課題は、探索空間の爆発である。可能なプログラムの数はプログラムの長さに応じて指数関数的に増加し、最も単純なタスクを除いて全数探索は実行不可能になる。型指向探索やビーム探索などのヒューリスティックは空間を剪定するのに役立つが、有効なプログラムを見逃す可能性がある。この完全性と効率性のトレードオフは、根本的な未解決問題である。
もう一つの問題は、仕様の曖昧さである。有限の例のセットが与えられた場合、それらに適合するプログラムは無限に存在し、そのほとんどは未見の入力に対して意味的に正しくない。したがって、帰納システムは、より短いプログラムや特定の構造的特性を持つものを好むなどの帰納バイアスを組み込む必要がある。このバイアスはしばしば探索文法やトレーニングデータにエンコードされるが、タスクによっては過学習または過小学習につながる可能性がある。
ニューラルアプローチは、大量のトレーニングデータの必要性や、構文的および意味的妥当性の保証の難しさなど、追加の課題に直面している。トランスフォーマーはベンチマークタスクで印象的な結果を示しているが、構文的に無効なコードやエッジケースで失敗するプログラムを生成する可能性がある。予測と正しさの間のギャップを埋めるために、検証と修復のメカニズムがしばしば必要である。
将来の方向性
この分野は、ニューラルモデルと記号的推論の強みを組み合わせたハイブリッドシステムへと進化している。例えば、最近のいくつかの研究では、大規模言語モデルを使用して候補プログラムを生成し、その後剪定された探索や形式的検証器を使用して出力を洗練する。このアプローチは、事前訓練モデルの広範な知識を活用しながら、正しさの保証を維持する。
もう一つの方向性は、対話型帰納プログラミングであり、システムは合成中にユーザーに追加の例や明確化を求める。これにより曖昧さが軽減され、意図したプログラムを生成する可能性が向上する。人間参加型システムの研究は、学術的および産業的設定の両方で有望な結果を示している。
最後に、帰納プログラミングと機械学習パイプラインとの統合は成長する可能性が高い。深層学習モデルがより能力を高めるにつれて、それらはプログラム仮説のソースとその動作の検証器の両方として機能できる。最終的な目標は、自然言語、例、フィードバックからプログラミングを学習できるシステムを作成し、人間のプログラマーの柔軟性に近づくことである。