専門家の問題解決は、強力な思考様式言語、すなわち問題とその解決策を考えるための言語システムに依存しています。専門知識を獲得することは、これらの言語を学ぶこと、つまり概念体系とそれらを使用するスキルを学ぶことを意味します。私たちは、プログラムを記述することで問題を解決する学習システムであるDreamCoderを提案します。これは、ドメイン概念を表現するためのプログラミング言語を作成し、ニューラルネットワークがこれらの言語でプログラムを探索するプロセスをガイドすることで、専門知識を段階的に構築します。「覚醒-睡眠」（wake-sleep）学習アルゴリズムは、言語を交互に拡張し、新しい記号的抽象化を追加し、想像上の問題と再生された問題でニューラルネットワークを訓練します。DreamCoderは、古典的な帰納的プログラミングタスクを解決できるだけでなく、画像の描画やシーンの構築といった創造的なタスクも実行できます。それは、現代の関数型プログラミング、ベクトル代数、およびニュートンの法則やクーロンの法則を含む古典物理学の基本原則を再発見しました。概念は以前に学んだ内容から構成的に構築され、多層的で解釈可能な記号表現を形成し、これらの表現は新しいタスクに転移できると同時に、経験の増加に伴って柔軟かつ効率的に拡張されます。
人工知能（AI）の長年の夢は、子供のように学習する機械（1）を構築することでした。すなわち、ごくわずかな知識から出発し、人間の大人が持つすべての知識へと徐々に成長していくことです。しかし、この目標はまだ遠い道のりです。なぜなら、人間の知能は人工システムがまだ習得していない多くの学習能力に依存しているからです。現在の機械は通常、単一のタスクカテゴリ向けに設計されていますが、人間は料理から微積分、グラフィックデザインまで、多種多様な問題を解決する方法を学びます。さらに、機械学習は通常大量のデータを必要とし、汎化能力が弱い一方で、人間はごくわずかな経験から強力な汎化を実現することがよくあります。おそらく最も顕著な違いは、人間が専門知識を構築するということです。私たちは、コミュニケーションし、拡張できる知識を獲得し、既存の概念の上に新しい概念を継続的に生成することで、あるドメインを習得すると、より良く、より速く学ぶことができるようになります。
本稿では、DreamCoderを紹介します。これは、人間の能力により近づくことを目指して設計された機械学習システムであり、広範なドメインにおいて、解釈可能で再利用可能、かつ汎化可能な知識を効率的に発見することができます。DreamCoderは、私たちが「覚醒-睡眠ベイズプログラム誘導」（wake-sleep Bayesian program induction）と呼ぶアプローチを具現化しています。本節の残りの部分では、その背後にある核心的なアイデアを説明します。学習をプログラム誘導と見なすことが何を意味するのか、プログラム誘導をベイズモデルにおける推論と見なすことがなぜ価値があるのか、そして「覚醒-睡眠」アルゴリズムがどのようにして経験とともにモデルを成長させ、より効率的に学習できるようにし、このアプローチを実用的かつスケーラブルにするのかについて説明します。
学習をプログラム誘導として定式化する私たちの方法は、AIの発展の初期段階（2）にまで遡ります。私たちは新しいタスクの学習を、そのタスクを解決する、または期待される振る舞いをするプログラムをプログラム空間で探索することと見なします。図1は、DreamCoderが適用された8つの異なるドメインにおけるプログラム誘導タスクの例（図1A）と、古典的なリスト処理ドメインにおけるタスクの詳細な説明を示しています。少数の入出力例が与えられただけで、数字のリストをソートするプログラムを学習します（図1B）。純粋な統計的手法と比較して、学習をプログラム誘導として見なすことは、いくつかの利点をもたらします。
記号化されたプログラムは強力な汎化能力を示します。直感的には、単なる内挿ではなく外挿する傾向があります。これにより、学習プロセスも非常にサンプル効率が良くなります。通常、学習すべき特定の関数を指定するのに数個の例で十分です。設計上、プログラムは非常に人間が解釈可能です。それらは私たちの科学や工学における標準的なモデリング言語を包含し、ますます複雑なタスクを解決するために再利用および結合できる知識を明らかにします。最後に、プログラムは普遍的です。原則として、任意のチューリング完全な言語は、知能が解決できるすべての計算問題を表現できます。
これらの利点と、複数のドメインでの成功した適用（3-9）にもかかわらず、プログラム誘導のAI分野における影響力はまだ限られています。ベイズフレームワークは、これらの課題を明確化すると同時に、それらに対処するための道筋も示しています。私たちが探索に使用するプログラミング言語は、学習の仮説空間と事前確率を定義します。その言語で短いプログラムほど、事前確率が高くなります。どの汎用プログラミング言語もプログラム誘導をサポートしますが、これまでのシステムは、強力な、手作業で調整された帰納的バイアスや事前知識を提供する、慎重に設計されたドメイン固有言語（DSL）から開始する必要があることを発見しました。DSLがない場合、発見されるプログラムは長すぎ（事前確率が低い）、そのため合理的な時間内に探索することが困難になります。慎重に設計された事前知識があったとしても、探索空間の組み合わせ的性質のため、最適なプログラムを見つける探索は、汎用アルゴリズムにとってほぼ常に手に負えません。したがって、ほとんどの実際のプログラム誘導アプリケーションでは、手作業で設計されたDSLだけでなく、そのDSLを活用して高速推論を実現するための、専門的に設計された探索アルゴリズムも必要とされます。これら2つの要件は、プログラム誘導のスケーラビリティと幅広い適用性を制限します。
DreamCoderは、与えられたドメインにおいてプログラムをコンパクトに表現し、効率的に帰納することで、これら2つのボトルネックを解決します。このシステムは、「学習する方法を学習する」——より良いプログラムを書き、それらのプログラムをより効率的に探索する——ことを実現します。これは、2種類の異なるドメイン専門知識を共同で構築することによって実現されます。(1) 明示的な宣言的知識。これは、タスク間で共通する概念的抽象化を捉える学習済みのドメイン固有言語として現れます。(2) 暗黙的な手続き的知識。これは、学習済みの言語を使用して新しいタスクを解決する方法をガイドするニューラルネットワークとして現れ、学習済みのドメイン固有探索戦略を具体化します。ベイズの観点から見ると、このシステムは、プログラムの事前分布と、観測されたタスクデータが与えられたプログラムの事後分布を効率的に近似するためのニューラルネットワークによってパラメータ化された推論アルゴリズムを同時に学習します。
DreamCoderは、これらの両面を自己教師あり、自己誘導的な方法で学習し、一連の訓練タスクに何度も直面する過程で両者を段階的に構築します。これにより、新しいドメインでの学習を拡張でき、十分に多様な訓練タスクが与えられれば、あるドメイン内で学習を拡張することもできます。通常、新しいドメインで学習プロセスを開始するには、中程度の数のタスクで十分です。例えば、図1Bに示されているリストソート関数は、システムがループ処理した109個のタスクの1つであり、システムは学習過程で数字リストを処理するための約20の基本操作を含むライブラリを段階的に構築しました。これらの操作は、将来遭遇する新しいタスクを解決するための基礎的な構成要素となりました。
DreamCoderが学習する言語形式は、多層の抽象階層構造をなしています（図1Bおよび図7A、B）。これらの階層構造は、ディープニューラルネットワークの内部表現に似ていますが、ここでは各層が以前のコード層で定義された記号コードに基づいて構築されており、これらの表現は自然に人間が解釈可能で説明可能になります。抽象ネットワークは時間とともに徐々に成長し、各層の概念は以前に獲得した概念の上に構築されます。これは、人間が概念体系を構築する方法にインスピレーションを得ています。私たちは微積分を学ぶ前に代数を学び、代数を学ぶ前に算数を学びます。複雑なパターンを描くことを学ぶ前に、簡単な形状を描くことを学びます。例えば、リスト処理の例（図1B）では、私たちのモデルは4層の深いライブラリコンポーネントである「n番目に大きい要素を取得する」を呼び出すことで数字シーケンスのソートを実装し、このコンポーネントはさらに低レベルの学習済み概念である最大値（maximum）とフィルタリング（filter）を呼び出します。理論的には、同等のプログラムは初期言語でも記述できますが、最終的に学習された言語で生成されたプログラムは、より理解しやすく、より簡潔です。初期のプリミティブのみで表現すると、これらのプログラムはあまりにも複雑で、学習者が合理的な時間内にそれらを見つけることができません。ドメイン固有の専門知識を獲得して初めて、ほとんどの問題が実践的に解決可能になります。
DreamCoderという名前は、「覚醒-睡眠」サイクルによってドメイン知識を反復的に増やしていくことから来ており、このメカニズムは、睡眠の異なる段階で起こる記憶固定化のプロセスに大まかに触発されています（10, 11）。一般に、「覚醒-睡眠」ベイズ学習（12）は、学習者の事前分布を定義する概観生成モデルと、新しいデータが与えられた場合にこの生成モデルを反転させる方法を学習するニューラル認識モデルの訓練を交互に行います。「覚醒」フェーズでは、生成モデルが新しいデータを解釈するために使用され、認識モデルによってガイドされます。一方、「睡眠」フェーズでは、認識モデルは、生成モデルからサンプリングされた架空のデータセット（「夢」または「幻想」と呼ばれる）を使用してオフラインで訓練されます。
DreamCoderは、プログラム学習のための「覚醒-睡眠」アプローチを発展させました。その学習された言語は、プログラムとタスクをカバーする生成モデルを定義し、各プログラムは特定の仮説的タスクを解決します。そのニューラルネットワークは、タスク間のパターンを認識し、特定の新しいタスクを解決する可能性のあるプログラムコンポーネントを最もよく予測するように学習します。「覚醒」フェーズでは、システムは複数のタスクのデータを受け取り、それらのタスクを解決できるプログラムを合成しようとします。同時に、ニューラル認識モデルを利用して候補プログラムを提案します。学習は、2つの異なるが交互に行われる「睡眠」フェーズで発生します。1つは、「覚醒」フェーズで見つかったプログラム内の新しい抽象化を統合することで、学習済み言語（つまり生成モデル）を拡張することです。もう1つは、生成モデルからサンプリングされた「幻想」プログラムを訓練することで、ニューラルネットワーク（つまり認識モデル）を最適化することです。
この「覚醒-睡眠」アーキテクチャは、既存の2つのアイデアを基盤としており、それらをさらに統合しています。ベイズ多重タスクプログラム学習（5, 13, 14）と、ニューラルガイドによるプログラム合成（15, 16）です。これら2つの方向性は、最近の文献でそれぞれ重要な影響力を持っていますが、私たちの研究で初めて統合されました。これはEC2アルゴリズム（17）に始まり、現在ではDreamCoderでより大規模に拡張されています（先行研究に関するさらなる議論についてはS3節を参照）。
その結果として生まれたシステムは、幅広い応用可能性を秘めています。私たちはその8つのドメインでの応用を説明します（図1A）。古典的なプログラム合成の課題、より創造的な視覚的描画および構築問題、そして最終的には再帰プログラミング、ベクトル代数、および基本的な物理言語を捕捉するライブラリ学習です。私たちのすべてのタスクは、新しい概念または関数の5〜10個の例、あるいは新しいオブジェクトを描写する画像やシーンなど、ごく少量のデータからプログラムを帰納することを含みます。学習された言語は、決定論的プログラムと確率的プログラムの両方をカバーしており、生成的に（例：画像や計画を生成する）も条件的に（例：入力を出力にマッピングする）も実行できるプログラムが含まれます。
要約すると、これらの応用例が、人工知能システムにおいて解釈可能で再利用可能な知識を構築するための実用的、汎用的、かつデータ効率の高い方法としてのプログラム帰納の可能性を説明することを願っています。
覚醒/睡眠プログラム学習
ここでDreamCoderにおける学習の具体的な詳細について説明します。まずアルゴリズムとその数学的定式化を概説し、次にその3つのフェーズの詳細について深く掘り下げます。学習プロセスは反復的に行われ、各反復（式1、図2）は「覚醒」フェーズと2つの「睡眠」フェーズのサイクルを経ます。「覚醒」フェーズではタスクの解決を試み、その後に続く2つの「睡眠」フェーズで新しいタスクを解決する方法を学習します。
覚醒フェーズ（図2上部）では、システムはトレーニングセットからタスクをランダムなミニバッチでサンプリングし（またはドメインのサイズと複雑さによっては、トレーニングセット全体を使用する可能性もあります）、それらのタスクを解決できるプログラムを検索します。ニューラル認識モデルは、各タスクで観測されたデータに基づいて候補プログラムをランク付けし、検索プロセス全体をガイドします。候補プログラムは2つの基準で評価されます。1つは現在のタスクをどれだけ解決できるか、もう1つは学習済みのプログラム生成モデルに基づいて、そのプログラムが事前確率的に合理的であるかです。
最初の「睡眠」フェーズは抽象化フェーズ（図2左側）と呼ばれ、これは「覚醒」フェーズで見つかった経験をリプレイすることで、タスクの解決策から共通のプログラム断片を抽出し、これらの断片を新しいコード基本単位として抽象化し、プログラミングプリミティブライブラリ（すなわち生成モデル）を拡張します。このメカニズムは、学習者の宣言的知識の広さと深さを増加させます。学習されたライブラリをネットワークとして見なすと、図1Bや図7に示すようになります。
2つ目の「睡眠」フェーズは、夢フェーズ（図2右側）と呼んでいます。これは、プログラム探索を補助するために使用されるニューラルネットワークを訓練することで、学習者がコードを書く際のプロシージャルスキル（つまり操作スキル）を向上させます。
神経認識モデルは、リプレイされた経験だけでなく、「幻想」（fantasies）データでも訓練されます。「幻想」とは、学習済みのライブラリからランダムにサンプリングされたプログラムであり、生成モデルとして機能します。これらのランダムプログラムは、システムが夢フェーズで解決する必要があるタスクを定義し、ニューラルネットワークは、想像上の各タスクの観測データに基づいて、見つかった解決策を予測するように訓練されます。
確率的推論の観点から見ると、DreamCoderはタスクの訓練セットXを観測し、2つの内容を推論します。1つは各タスクx ∈ Xの解法プログラムρx、もう1つは当該ドメインでタスクを解決する可能性のあるプログラムの事前分布（図2中央）。この事前分布はライブラリLによって符号化されており、プログラムの生成モデルP[ρ|L]を定義します（詳細はS4.3節）。ニューラルネットワークは、タスクの観測例を条件として、そのタスクを解決する可能性のあるプログラムの近似事後分布を予測することで、問題解決プログラムの探索を助けます。したがって、このネットワークは認識モデルとして、Helmholtzマシン（12）から着想を得た方法で生成モデルと共同で訓練されます。Q(ρ|x)は認識モデルが予測する近似事後分布を表します。
高レベルでは、「覚醒-睡眠」サイクルは図2に示す一連の更新操作に対応しています。これらの更新は、タスク集合Xが与えられたライブラリLに関する事後分布の下限を最大化することを目的としています（付録S4.1を参照）。
ここで、P[L]はライブラリの記述長事前分布（付録S4.5参照）、P[x|ρ]はプログラムρが与えられた場合のタスクx ∈ Xの尤度です。例えば、タスクxが入出力によって指定される場合、この尤度は0または1になります。一方、確率的プログラムを学習する場合、この尤度は、そのプログラムが観測されたタスクを生成する確率です。
この3段階の推論プロセスは、2つの異なる形式の「自己誘導」（bootstrapping）メカニズムによって実現されます。各睡眠サイクルにおいて、次のバージョンのライブラリは、以前のサイクルで学習された概念に基づいて構築されるため、学習されたライブラリはますます深く、豊かになります。同時に、生成モデルと認識モデルも相互にガイドし合っています。より専門的なライブラリは、認識モデルにより豊富な「夢」を提供して学習させることができ、より正確な認識モデルは、覚醒フェーズでより多くのタスクを解決でき、これらのタスクは次のバージョンのライブラリにフィードバックされます。
これら2つの「睡眠」フェーズは、プログラム合成に伴う組み合わせ爆発問題の緩和にも共同で貢献します。より高レベルのライブラリルーチンは、より少ない関数呼び出しで問題を解決することを可能にし、探索の深さを効果的に減少させます。一方、ニューラル認識モデルは、プログラム空間であまり可能性のない経路の重みを下げ、探索の広さを効果的に減少させます。
覚醒フェーズ
覚醒フェーズのタスクは、後方確率が高い特定タスクプログラム、すなわち高い尤度（タスクを解決できるため）と高い事前確率（現在の言語での記述長が短いため）を兼ね備えたプログラムを見つけることです。各覚醒ループでは、トレーニングセットのランダムなミニバッチからタスクをサンプリングし（またはドメインのサイズと複雑さによっては、トレーニングセット全体を使用することもあります）、認識モデルQ(ρ|x)の下で確率の降順でプログラムを列挙することで、各タスクを解決できるプログラムを検索し、プログラムρがそのタスクの解決に正の確率（P[x|ρ] > 0）を割り当てているかどうかを確認します。
モデルは特定のタスクを解決できる多くのプログラムを見つける可能性があるため、最も高い事後確率P[ρ|x, L]を持つプログラムの小さなサブセット（ビーム探索ではk = 5）のみを保持し、式1の睡眠更新でこの候補プログラムの集合を周辺化します。
私たちはプログラムを多態型付けされたラムダ計算式（polymorphically typed λ-calculus expressions）として表現します。これは、条件文、変数、高階関数、および新しい関数を定義する能力を含む、表現能力の非常に高い形式システムです。
抽象化フェーズ
抽象化睡眠フェーズでは、モデルは概念ライブラリを拡張して自身の知識体系を成長させます。その目標は、現在のタスクの解をより簡単に表現できるような、特化した抽象構造を発見することです。「表現の簡便性」は、覚醒フェーズで見つかったプログラムを最もよく圧縮できるライブラリを優先するというライブラリへの選好に変換されます。抽象化睡眠の目標（式1）は、ライブラリの記述長（−log P[D]）と、覚醒フェーズで見つかったプログラムを再構築した後の記述長の合計を最小化することに相当します。
直感的には、「再利用されるコードを圧縮する」ことでベイズ規準を最大化します。しかし、繰り返される構文構造を圧縮するのとは異なり、プログラムを再構築することで、そこに繰り返し現れる意味的パターンを明らかにします。
コードは無限の多様な方法で再構築できるため、プログラムとその再構築の間のλ計算評価ステップ数を制限し、有限だが通常は非常に膨大な再構築集合を得ます。図3は例を示しています。モデルは、汎用プリミティブ（Yコンビネータを介した再帰を含む）の集合から出発し、現代の関数型プログラミングにおける最も基本的な構成要素の1つである高階関数mapを段階的に発見しました。この例では、可能な再構築の方法は約10¹⁴通りあります。この数はプログラムのサイズと許容される最大評価ステップ数とともに指数関数的に増加します。
この指数関数的な爆発問題を解決するために、私たちはこれらの再構築集合を表現および操作するための新しいデータ構造を導入しました。これは、バージョン空間代数（version space algebras）と等価グラフ（equivalence graphs）のアイデアを組み合わせたもので、その構築のための動的計画法アルゴリズムを導出しました（付録S4.5を参照）。このデータ構造の成長速度は、共有サブツリーの因数分解表現のおかげで、プログラムのサイズに対して多項式関係にありますが、最大評価ステップ数の上限に対しては依然として指数関数的です。私たちは、小さい上限（例えば3に設定）を設定することで、パフォーマンスに影響を与えることなく、この指数項の規模を制御できます。その結果、顕著な効率向上をもたらしました。10⁶個のノードを含むバージョン空間は数分で計算でき、図3で本来なら明示的に列挙・探索するのに数世紀かかる10¹⁴通りの再構築を表すことができます。
夢フェーズ
夢睡眠フェーズでは、システムは認識モデルを訓練し、その後の覚醒フェーズにおける問題解決プロセスでのプログラム探索を加速させます。私たちは認識モデルをニューラルネットワークとして実装し、ネットワーク構造を通じてドメイン知識を注入します。例えば、画像からグラフィックプログラムを帰納する場合、畳み込みネットワークを使用することで、有用な画像特徴を学習する傾向を持たせます。
私たちは認識ネットワークを、覚醒フェーズで見つかったプログラムのリプレイデータと、ライブラリLからランダムにサンプリングされた「幻想」データという2種類の自己教師ありデータソースで訓練します。リプレイデータは、認識モデルが実際に解決する必要のあるタスクで訓練されることを保証し、それらの解決方法を忘れないようにします。一方、「幻想」は、データ効率にとって極めて重要である、大量かつ非常に多様な訓練データを提供します。あるドメインの専門家になることは、少数サンプル学習問題でも、ビッグデータ問題でもありません。私たちは通常、DreamCoderを100〜200のタスクで訓練しますが、これは大容量のニューラルネットワークにとってはサンプル数が少なすぎます。しかし、モデルがカスタマイズされたドメインライブラリを学習すれば、そこから無限に「夢」をサンプリングまたは生成して、認識ネットワークを訓練することができます。
私たちの夢フェーズは、従来の「覚醒-睡眠」（wake-sleep）方式における夢フェーズとは異なります。古典的な「覚醒-睡眠」方式は、生成モデルからランダムなプログラムをサンプリングし、そのプログラムを実行してタスクを生成し、そのタスクからサンプリングされたプログラムを予測するように認識ネットワークを訓練します。一方、私たちは「夢を見る」ことを、一連のランダムな問題を生成するプロセスと見なし、睡眠中に能動的な方法で、覚醒フェーズと同じプログラム探索プロセスを使用してこれらの問題を解決します。そして、これらの問題に基づいて、見つかった解決策を予測できるように認識ネットワークを訓練します。
具体的には、私たちは以下の期待値を最大化することで、認識モデルQを訓練し、最大事後（MAP）推論を実行させます。
ここで期待値はすべてのタスクについて取られています。この期待値がタスクの経験分布に関して計算される場合、訓練データはリプレイデータになります。もし生成モデルからのサンプリングに関して計算される場合、訓練データは幻想データになります。私たちはリプレイデータと幻想データを50/50の混合比率で訓練に使用します。入力を出力にマッピングする幻想タスクの場合、訓練タスクから入力をサンプリングします。理論的にはQを完全な事後推論を実行するように訓練することも可能ですが、私たちのMAP目標には利点があります。それは、認識ネットワークに各問題に対して最も単純で標準的な解決策を見つけることを教えることです。より技術的に言えば、私たちのMAP目標は、ネットワークにすべての確率質量を、意味的には等価だが構文的には異なる表現の集合の中で唯一のメンバーに集中させることで、プログラム空間における構文的対称性を破ります。手作業で書かれた対称性破りメカニズムは、多くのプログラム合成器にとって不可欠であることが証明されています（22, 23）。DreamCoderが学習した対称性破りメカニズムに関する理論的および経験的分析については、付録S4.6を参照してください。
結果
まず、DreamCoderを2つの古典的なベンチマーク領域で実験的に研究しました。リスト処理とテキスト編集です。どちらの場合も、タスクは条件付きマッピング（すなわち入出力例）によって定義され、map、fold、cons、car、cdrなどの基本ルーチンを含む汎用関数型プログラミングの基礎から訓練を開始しました。
当社のリスト処理タスクは、（17）の218問からなり、テストセットとトレーニングセットに50/50で分割され、各タスクには15の入出力例が提供されました。これらの問題を解決する過程で、DreamCoderは約20の新しいライブラリルーチンを合成し（付録S1.1参照）、filterなどの高階関数を再発見しました。各抽象化ループは、以前の睡眠サイクルで発見された概念に基づいて構築されました。例えば、モデルは最初にfilterを学習し、それを使用してリストから最大要素を抽出する方法を学習し、次にこのルーチンを使用してリストからn番目に大きい要素を抽出する新しいライブラリルーチンを学習し、最終的にこの新しいルーチンを使用して数字リストのソートを実現しました（図1B参照）。
テキストを編集できるプログラムの合成は、プログラミング言語と人工知能の文献における古典的な問題であり（18）、テキスト編集プログラムを合成するためのアルゴリズムはMicrosoft Excel（7）に適用されています。例えば、このようなシステムは「Alan Turing」→「A.T.」のようなマッピング関係を観測し、「Grace Hopper」を「G.H.」に変換するプログラムを推論することができます。従来のテキスト編集プログラムシンセサイザーは、手作業で設計された基本操作ライブラリと手作業で設計された探索戦略に依存していました。ここでは、私たちはこれら2つの要素を共同で学習し、現在の最先端の汎用ドメインプログラムシンセサイザーに匹敵するパフォーマンスを達成しました。
私たちは128個の自動生成されたテキスト編集タスクでシステムを訓練し、2017年のSyGuS（24）プログラム合成コンペティションの108個のテキスト編集問題でテストしました。学習前、DreamCoderは10分以内に3.7%の問題を解決し、平均探索時間は235秒でした。学習後、79.6%の問題を解決し、はるかに高速に、平均解決時間はわずか40秒でした。このコンペティションで最も優れた性能を示したシンセサイザーCVC4は82.4%の問題を解決しましたが、コンペティションの条件は各問題に1時間と8つのCPUコアが割り当てられていました。このようなより緩やかな計算リソース条件下では、私たちは84.3%の問題を解決しました。
さらに、SyGuSでは各テキスト編集問題にそれぞれ異なる手作業で設計された基本操作ライブラリが付属していました。一方、私たちはすべての編集タスクに適用可能な統一されたテキスト編集概念ライブラリのみを学習しましたが、これは実際のアプリケーションにおいて必要な前提条件です。
次に、より創造的なタスク、すなわち画像、計画、テキストの生成を検討します。プログラム的または生成的な視覚概念（Bongard問題（25）、手書き文字（5, 26）、Raven推理行列（27）など）は、低レベルの知覚と高レベルの推論を結びつけるため、人工知能と認知科学で広く研究されています。
ここでは、LOGOタートルグラフィックス（Turtle graphics）（28）に触発され、モデルに「ペン」を制御させ、命令的なフロー制御能力と角度および距離に関する算術演算能力を持たせました。タスクは、160枚の画像からなるコーパスを描画することです（テストセットとトレーニングセットに50/50で分割。図4A参照）。DreamCoderを20回の「覚醒-睡眠」サイクルで訓練した後、学習されたライブラリ（付録S1.1参照）を調べたところ、訓練データ内の視覚オブジェクトのカテゴリ（多角形、円、らせんなど）に対応する解釈可能なパラメータ化された描画ルーチンを発見しました（図4B）。システムは教師なしで、その視覚世界の基本オブジェクトタイプを学習したのです。
さらに、半径対称性（radial symmetry）のようなより抽象的な視覚関係も学習し、それを新しい高階関数としてライブラリに追加しました（図4C）。
システムが学習プロセス中に見た「夢」を可視化することで、生成モデルが認識モデルの訓練をどのようにガイドしているかを明らかにすることができます。ライブラリが成長し、現在のドメインにますます適応するにつれて、ニューラルネットワークが受け取る訓練データもより豊かで多様になります。学習の初期段階では、ライブラリを用いて書かれたランダムなプログラムは単純で構造が緩いものであり（図4D）、認識モデルの訓練価値は限られていました。しかし、学習後には、システムの「夢」は豊かな構造を持つようになり（図4E）、訓練データから得られた潜在的な構成要素やパターンを創造的な方法で組み合わせます。これらの方法は、その覚醒経験には決して存在しませんでしたが、広範な汎化能力を持つ認識モデルを訓練するのに非常に適しています（29）。
古典的な人工知能の「コピーデモ」タスク（エージェントがブロックで構築された塔を観察し、それを再構築しようとするタスク（30））に触発され、次にDreamCoderに107個の「コピー塔」タスク（テストセットとトレーニングセットに50/50で分割、図5A参照）を与えました。このタスクでは、システムは塔の画像とその各ブロックの位置を同時に観察し、シミュレートされた機械腕がその塔をどのように構築するかを計画するプログラムを記述する必要があります。システムが使用する制御フロープリミティブはLOGOグラフィックスと同じでした。学習されたライブラリには、アーチ、階段、橋などの概念を含む、ブロック塔を構築するためのパラメータ化された「オプション」（31）が発見され、これらの概念はモデルの夢の中にも現れました（図5C-D）。
次に、少数の例から確率的生成概念を学習する能力を検討します。これは人間が自然に持つ能力であり、例えば、自然言語における新しいルールを学習したり（32）、記号や記号の一般的なパターンを学習したり（5）、単語を生成するための新しい運動プログラムを学習したり（33）します。まず、DreamCoderに少数の文字列から確率的正規表現（Regex、図1Aの例を参照）を推論させました。これらの文字列は、ウェブページからスクレイピングされた256のCSV列（データソース：（34）、タスクはテストセットとトレーニングセットに50/50で分割され、各概念には5つの文字列例が提供されました）に由来します。システムは、電話番号、日付、時刻、金額など、典型的なテキスト概念構造を記述する正規表現を学習しました（図S5参照）。これにより、多くの現実世界のテキストパターンを解釈し、それを確率的生成モデルとして解釈することで、これらの概念の新しいインスタンスを想像することができます。
例えば、DreamCoderはドル金額の概念を理解していませんが、$5.70、$2.80、$7.60などの例からその背後にある抽象的なパターンを推論し、$2.40や$3.30といった他の例を生成できます。-4.26、-1.69、-1.622、...、-1のような例外を伴うパターンについては、-9.9のような文字列を通常生成し、時折-2のような異常も生成する確率モデルを推論します。また、人間には馴染みのない、しかし数例で素早く学習し一般化できるような、よりニッチな概念も学習できます。例えば、-00:16:05.9、-00:19:52.9、-00:33:24.7などの例が与えられた後、-00:93:53.2、さらには-00:23=43.3のような妥当な近似結果を生成できる生成概念を推論します。
最後に、滑らかな軌跡を生成する実数値パラメータ方程式を推論することを考えます（付録S2.1.6および図1A、「記号回帰」を参照）。各タスクの目標は、特定の曲線によって生成されたデータに適合することです。その曲線は有理関数であるか、最高4次の多項式であるかのいずれかです。DreamCoderには加算、乗算、除算操作、および重要な任意の実数値パラメータを初期化し、これらパラメータを内部ループ勾配降下法によって最適化しました。私たちは各パラメータ化されたプログラムを、曲線集合を確率的に生成するものとしてモデル化し、ベイズ情報量規準（BIC）（35）を用いてこれらの連続パラメータの使用をペナルティしました。私たちのベイズメカニズムは、データを説明でき、かつ冗長な連続パラメータの使用を可能な限り避けるプログラムに焦点を当てることを学習しました。例えば、1.7x² − 2.1x + 1.8の実数値データが与えられた場合、3つの連続パラメータを含むプログラムを推論し、x−2.2/3.8のデータが与えられた場合、2つの連続パラメータのみを含むプログラムを推論しました。
DreamCoderのドメイン横断的な定量的分析
DreamCoderがどのように学習するかをよりよく理解するために、完全なシステムと、神経認識モデル（すなわち「夢」睡眠フェーズ）または新しいライブラリルーチンを形成する能力（すなわち「抽象化」睡眠フェーズ）といった重要なコンポーネントが欠落しているいくつかのバリアントとを比較実験しました。また、以下のいくつかのベースライン方法とも比較しました。
- 探索-圧縮（Exploration-Compression）（13）：プログラムを交互に探索し、再利用されるコンポーネントを圧縮して学習済みのライブラリを形成しますが、当社の再構築アルゴリズムは使用しません。
- ニューラルプログラム合成（Neural Program Synthesis）：初期ライブラリのサンプル上でRobustFill（16）モデルを訓練します。
- 列挙法（Enumeration）：各タスクについて24時間の型指向列挙（23）を実行し、最大4億のプログラムを生成およびテストします。
良好なライブラリ学習における圧縮メカニズムの役割を分離するために、2つの「記憶」（Memorize）ベースラインも構築しました。これらのバリアントは、タスクソリューション全体を新しい基本操作としてライブラリに組み込むことでライブラリを拡張します。これらは圧縮を試みず、覚醒フェーズで見つかったソリューションを単純に記憶し、新しい問題で再利用します（(36)参照）。私たちは神経認識モデルありと無しでの「記憶」バリアントを評価しました。
複数のドメインにおいて、私たちのモデルは一貫して最も多くの保留テストタスクを解決し（図6A。記憶ベースラインについては図S13参照）、通常は最短時間で完了しました（平均54.1秒、中央値15.0秒、図S11）。これらの結果は、DreamCoderの核となるコンポーネント、すなわち「睡眠-抽象化」フェーズにおける再構築と圧縮によるライブラリ学習、および「睡眠-夢」フェーズにおける認識モデル学習が、その全体的なパフォーマンスに実質的な貢献をしていることを示しています。
これらのコンポーネント間の相乗効果は、LOGOグラフィックスやタワー構築のような、より創造的で生成的な構造構築ドメインにおいて特に顕著です。これらのドメインでは、他のどの代替モデルも保留タスクの60%以上を解決できませんでしたが、DreamCoderはほぼ100%のタスクを解決することを学習しました。図6Aに示すDreamCoderが収束するために必要な時間はドメインによって異なりますが、適度な計算リソース（20〜100CPU）では通常約1日で完了します。
学習されたライブラリが時間とともにどのように成長するかを観察することによって（学習された認識モデルを含むかどうかにかかわらず）、その深さと規模における機能的な有意差を発見しました。各ドメインにおいて、より深いライブラリはより高いタスク解決率と密接に関連しており（相関係数r = 0.79）、学習された認識モデルを備えたシステムはすべての深さでより優れたパフォーマンスを示しました。さらに、認識モデルは最終的に学習されたライブラリがより深い階層を持つことを促進し、より高い漸近性能レベルを達成しました（図6B、図S1）。学習されたライブラリのサイズとパフォーマンスの間にも同様だが弱い関係が存在しました。したがって、認識モデルは、「より良い」ライブラリの学習を導いているように見えます。ここで「より良い」とは、学習された記号表現の深さと広さの両方に関連しています。
DreamCoderの認識モデルがライブラリ学習をどのように導くかという観点から、これらの表現が解決すべき問題の類似性構造をどのように共同で埋め込んでいるかを分析しました。DreamCoderはまず、認識ネットワークの活性化においてタスクを符号化し、次にそのタスクを解決できる記号プログラムで再表現します。学習プロセスが進むにつれて、これらの暗黙的な初期表現は、最終的なプログラムソリューションの明示的な構造に徐々に一致するようになります。これは、認識ネットワークの活性化空間における問題の類似性と、問題を解決するために使用されるコードコンポーネントの類似性との間の相関関係の継続的な強化として現れます（図S4を参照。χ²検定を使用し、学習前後でp < 10⁻⁴）。これらの学習されたタスクの類似性をt-SNE埋め込みで可視化したところ、モデルがより豊かな概念的語彙を獲得するにつれて、その表現はより高い抽象的な共通性を持つタスクをグループ化するようになることがわかりました（図S3）。これは、人間のドメインエキスパートが表面的な類似性ではなく、問題の背後にある原理に基づいて分類する方法と類似している可能性があります（37、38）。
学習ライブラリから学習言語へ
これまでの私たちの実験では、DreamCoderがどのように「初心者」の状態から成長していくかを研究しました。初期には、最も単純な問題だけが簡潔で直接的な解決策を持つような、基本的なドメイン固有のプロセスが与えられていました。そして、システムが徐々に「専門家」の状態へと成長するにつれて、様々な概念を習得し、最も難しい問題でさえも簡潔で意味のあるプログラムで解決できるようになりました。ここで私たちは疑問を投げかけます。より簡素な出発点から学習を開始することは可能でしょうか、あるいは最初から基礎的なドメイン知識をまったく持たずに学習することは可能でしょうか？DreamCoderは、高度に汎用的なプログラミングおよび算術プリミティブのみから出発して、基礎的かつ高度なドメイン概念の両方を含むドメイン固有言語を段階的に開発し、それによってそのドメインのすべての問題を解決できるようになるのでしょうか？
古典物理学における実験データから物理法則を推論する研究（39-41）に触発され、私たちはまずDreamCoderに、APおよびMCAT物理試験の「チートシート」から得られた60種類の異なる物理法則および数学的恒等式を学習させました。各公式に対応する数値的な例データに基づいて学習させます。完全なデータセットには、力学と電磁気学における多くのよく知られた法則が含まれており、これらはベクトル、力、比率などの概念を用いて自然に表現されます。しかし、これらの数学的抽象化を直接提供するのではなく、DreamCoderには、少数の再帰シーケンス操作プリミティブ（mapやfoldなど）と基本的な算術操作といった、より汎用的な基盤のみを初期化し、物理学に適用できる数学的言語を自ら学習できるかどうかをテストしました。
実際、8回の「覚醒-睡眠」サイクルを経た後、DreamCoderはデータセット中の法則と恒等式の93%を学習することに成功しました。まず、内積、ベクトル和、ノルムなど、ベクトル代数の基本的な構成要素を学習しました（図7A）。次に、この数学的語彙を利用して、複数の物理法則の背後にある概念、例えば「逆二乗の法則」のパターンを構築し、ニュートンの万有引力の法則やクーロンの静電気力の法則を学習できるようにしました。これにより、当初の再帰シーケンス処理言語から、物理学のような言語への「基底変換」を効果的に完了しました。
では、DreamCoderは再帰シーケンス処理言語自体も学習できるのでしょうか？私たちはシステムを1959年のLispの最小限のプリミティブセット（car, cdr, cons, ...）のみで初期化し、20の基本的なプログラミングタスクを解決するよう求めました。これらのタスクは、コンピュータサイエンス入門コースでよくある練習問題に似ています。重要な点は、初期言語には原始的な再帰メカニズム（Yコンビネータ）が含まれており、理論上、学習者が任意の再帰関数を表現できるものの、それ以外に既成の再帰関数は提供されていなかったことです。これまでの設定では、再帰は高階関数（map, foldなど）にカプセル化され、プリミティブとして学習者に提供されていました。十分な計算時間（約64のCPUで5日間稼働）を費やすことで、DreamCoderは20の問題すべてを解決することを学習し、その過程で、map, fold, zip, length、そして区間内の自然数リストを生成するような算術操作を含む、現代の関数型プログラミングの慣用法に相当するライブラリを構築しました（図7B参照）。
これらすべてのライブラリ関数は、高階関数foldとその双対であるunfoldを用いて表現できます。これら2つの操作は、形式的には再帰データ型における最も基本的な2つの操作であり、この発見は「折り紙プログラミング」（origami programming）（42）として知られています。DreamCoderはこの発見のプロセスを再現しました。まずfoldを再発明し、次にunfoldを、そして他のすべての再帰関数をfoldとunfoldの組み合わせとして定義しました。
議論
私たちの研究は、汎用的なプログラム誘導システムを構築することが可能であり、実現可能であることを示しています。このシステムは、性質の異なる多くの領域における新しい学習タスクを表現し、解決するために必要な専門知識を学習し、経験の蓄積とともに専門能力を継続的に向上させることができます。DreamCoderにおける最適な専門知識は、明示的な宣言的知識と暗黙的な手続き的スキルの共同学習に依存しています。
より広範な観点から見ると、DreamCoderがドメインの概念構造の深層的な明示的表現を学習できることは、記号主義、確率論的方法、そしてニューラルネットワーク学習を組み合わせた強力な能力を示しています。階層的表現学習アルゴリズムは、従来のディープニューラルネットワークとは異なり、人間が理解できる知識を創造できます。また、それが生み出す記号的な専門知識表現は柔軟性があり、経験とともに適応し拡張できる点で、従来のAIエキスパートシステムとは異なります。
私たちがここで焦点を当てている問題では、解空間は明確な記号形式で正確に捉えることができます。これは、画像ピクセル入力、生成されたテキストパターンにおける例外や不規則な状況、または記号回帰の例で使用した連続パラメータなど、他の複雑性を含む領域でも同様です。しかし、現実世界の大量のデータは、これらよりもはるかに混沌としています。将来のプログラム誘導が直面する重要な課題は、遍在するノイズと不確実性をより良く処理する方法であり、これには確率的およびニューラルネットワークの人工知能手法にさらに依存する必要があります（5, 43, 44）。
最近の研究では、様々な混合型ニューラル・シンボリック表現のプログラム帰納方法が探求されています（45-49）。これらの方法とDreamCoderのライブラリ学習および自己誘導能力を組み合わせることは、今後の重要な発展方向となる可能性があります。
プログラム帰納をAI全域に拡張すること、例えば常識推論、自然言語理解、因果推論などには、まだ多大な革新が必要ですが、そこには計り知れない可能性が秘められています。学習媒体としてのプログラムの独特な利点は、普遍的な表現力、データ効率の良い汎化能力、そして解釈可能で組み合わせ可能な再利用の可能性を兼ね備えている点にあります。
今日、私たちは単一のプログラムだけでなく、ドメイン全体に特化した言語を学習できるようになりました。これにより、プログラムのもう一つの特性が特に重要になります。それは、プログラムが人間と機械の両方が理解できる方法で知識を表現するということです。
すべてのAIシステムは本質的に人間知能と機械知能の共同産物であると認識し、ここで示されたツールが、真に人間と機械が共同で参加するAI開発の道筋を構築するための基盤を築くと考えます。
以下の議論では、より良い人間学習モデルの構築、およびより人間らしい機械学習形式に対する私たちの研究の広範な意味合いについてさらに深く掘り下げます。
生物学的学習とのインターフェース
DreamCoderの「覚醒-睡眠」メカニズムは、ヘルムホルツ機械に触発されており、ヘルムホルツ機械自体もまた、人間の睡眠中に起こる学習プロセスから大まかに着想を得ています。DreamCoderは、交互に行われる一対の「睡眠」サイクル概念を導入しており、興味深いことに、生物学的な意味での睡眠もまた複数の段階に分かれています。急速眼球運動（REM）睡眠、すなわち「夢」睡眠は、暗黙的な手続き的スキルを生み出す学習プロセスに関連しており（11）、エピソードの再生や夢を含み、これは私たちのモデルにおける「夢」睡眠フェーズに類似しています。
一方、徐波睡眠は、新しい宣言的抽象化の形成と固定化に関連しており（10）、私たちのモデルにおける「抽象化」睡眠フェーズに大まかに対応しています。DreamCoderもヘルムホルツ機械も、生物学的プロセスをモデル化するために設計されたわけではありませんが、私たちのアプローチは、「覚醒-睡眠」学習アルゴリズムを、人間の睡眠中に実際に起こる学習プロセスに近づける可能性があると推測しています。
DreamCoderの知識は段階的に成長し、その動的なメカニズムは、「カリキュラム学習」（curriculum learning）（50）や「小さく始める」（starting small）（51）に関する初期の発達理論に関連していますが、それらとは異なります。人間の教師がシステムのタスクの難易度順序を決め、段階的に解決させる「カリキュラム」とは異なり、DreamCoderの学習方法は自然界の教師なし探索に似ています。ランダムにサンプリングされたタスクを解決しようと試み、覚醒フェーズで自身の能力の限界を探り、その後の睡眠サイクルでその限界を拡張します。これにより、単純なタスクから学んだ概念を用いて、より複雑なタスクの解決を導きます。
しかし、人間の学習方法はより能動的です。彼らは解決すべきタスクを選択したり、より難しい問題への中間ステップとして、あるいは好奇心や美的動機から、自らタスクを生成したりすることもできます。人間のような方法で問題を自動生成できるエージェントを構築することは、将来の重要な一歩です。
ドメイン専門知識を明示的な宣言的知識と暗黙的な手続き的スキルに区分する私たちのアプローチは、認知科学における「デュアルプロセスモデル」（dual-process models）（52, 53）や人間の専門家に関する研究（37, 38）から大まかに着想を得ています。人間の専門家は、言語で表現できる宣言的ドメイン概念、例えば芸術家が弧、対称性、遠近法の原則を学ぶように、物理学者が内積、ベクトル場、逆二乗の法則を学ぶように、を学ぶだけでなく、これらの概念を新しい問題を解決するために迅速に適用する手続き的（そして通常は暗黙的な）スキルも習得します。
これら2種類の知識は、専門家が問題解決策の「深層構造」に基づいてより正確に問題を分類し（37, 38）、解決策を探し始める前から、どの概念が有用かを直感的に判断できるようになるため、共同で機能します。私たちは、これら2種類の専門知識が、生物学的および人工的学習システムの両方にとって不可欠な構成要素であり、ニューラルネットワークと記号的方法がここで補完的な役割を果たすと考えています。
何が組み込まれるべきか、何が学習によって獲得されるべきか
人間のように学習すること、特に子供のように学習することという目標は、研究者によって「ゼロから」学習することという目標と同一視されることがよくあります。彼らは、チューリングが提案したように、子供は「文房具店で買ったノートのように、ごくわずかな仕組みとたくさんの白紙」という「白紙」の状態から始まるものと仮定しています（1）。
プログラム帰納は、汎用人工知能へのアプローチとして、このビジョンに根ざしており、最小限のチューリング完全言語があれば、原理的には計算可能なあらゆる問題を解決できるプログラムを帰納できることを示した初期の研究成果に後押しされています（2、54-56）。DreamCoderが最も基礎的なところから出発し、関数型プログラミング、ベクトル代数、物理学の基本的な語彙を発見できることは、この目標へのもう一歩と見なすことができます。
では、この方法はさらに拡張できるでしょうか。一度に一つの領域を学習するだけでなく、ごくわずかな基盤から出発して、同時に複数の異なる種類の問題の専門知識を開発することは可能でしょうか。このような進歩は、領域横断的なメタ学習、すなわち、人間が生物学的・文化的進化を通じて集合的に構築してきたような、領域横断的なライブラリ、あるいは「思考の言語」（language of thought）（57, 58）を構築することに依存するかもしれません。そして、それは無限の種類の新しい問題領域の表現に分化していくことができます。
これらの方向性は魅力的ですが、そのような微小な基盤から多くのことを学習することは、私たちの人工知能への最良の道筋であるとは限りません。特に、今日、私たちは多くの巨人の肩の上に立つことができるからです。「ゼロから」が理論的に可能であったとしても、このような方法は、通常、よく知られているデータ不足問題（ニューラルネットワークなど）に直面するか、データに依存しない場合、膨大な計算資源を必要とします。DreamCoderは、「折り紙スタイル」の関数型プログラミング能力を構築するためだけに、約1CPU年を消費しました。
これに対し、私たちは「プログラムスケッチ」（sketching）のプログラム合成手法（22）から着想を得ています。スケッチング手法は通常、個々の合成問題を独立して扱い、人間のエンジニアが解の骨格を概説することを期待します。同様に、私たちはシステムに、複数の異なるドメインで問題を解決するために不可欠であると考える基本的な要素、すなわち、比較的簡潔でありながら汎用的に強力な制御フロー演算子、高階関数、および型システムをあらかじめ組み込みました。そして、これらの基礎の上に専門的な言語を構築するために学習メカニズムを利用します。
プログラム合成における学習の未来は、シミュレーションエンジンや現代のプログラミング言語の標準ライブラリが体現するような、より豊富でありながら広範に適用可能なリソースで初期化されたシステムにあるかもしれません。
このビジョンは、プログラム帰納が人間らしいAIを構築する上でどのように貢献すべきかという私たちの見方も形作っています。それは、「白紙」学習を追求するのではなく、既存の豊かな組み込み知識に基づいて学習することです。私たちがここで議論する様々な領域を学習する前に、人間の子供は生まれつき「核心知識」（core knowledge）を備えています。これは、物体、エージェント、空間、その他の常識的な概念を表現し、推論するための概念システムです（59-61）。
私たちは、人間がすでに持っている概念資源から出発し、人間が理解できる知識体系を構築する人工知能アプローチを強く支持します。これが、人間の世界の中に存在し、人間知能と共生する人工知能システムへの最良の道筋かもしれません。
原文リンク: https://arxiv.org/pdf/2006.08381