論文の概要: A Divide-Align-Conquer Strategy for Program Synthesis

• arxiv url: http://arxiv.org/abs/2301.03094v1
• Date: Sun, 8 Jan 2023 19:10:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-10 16:52:42.222876
• Title: A Divide-Align-Conquer Strategy for Program Synthesis
• Title（参考訳）: プログラム合成のための分割結合戦略
• Authors: Jonas Witt, Stef Rasing, Sebastijan Duman\v{c}i\'c, Tias Guns and Claus-Christian Carbon
• Abstract要約: 本稿では,大規模プログラムの探索を複数の小さなプログラム合成問題に分割する例によって,構成セグメント化がプログラミングに応用可能であることを示す。 入力と出力における構成部品の構造的アライメントは、プログラム探索を導くのに使用されるペアワイズ対応に繋がる。
• 参考スコア（独自算出の注目度）: 8.595181704811889
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major bottleneck in search-based program synthesis is the exponentially growing search space which makes learning large programs intractable. Humans mitigate this problem by leveraging the compositional nature of the real world: In structured domains, a logical specification can often be decomposed into smaller, complementary solution programs. We show that compositional segmentation can be applied in the programming by examples setting to divide the search for large programs across multiple smaller program synthesis problems. For each example, we search for a decomposition into smaller units which maximizes the reconstruction accuracy in the output under a latent task program. A structural alignment of the constituent parts in the input and output leads to pairwise correspondences used to guide the program synthesis search. In order to align the input/output structures, we make use of the Structure-Mapping Theory (SMT), a formal model of human analogical reasoning which originated in the cognitive sciences. We show that decomposition-driven program synthesis with structural alignment outperforms Inductive Logic Programming (ILP) baselines on string transformation tasks even with minimal knowledge priors. Unlike existing methods, the predictive accuracy of our agent monotonically increases for additional examples and achieves an average time complexity of $\mathcal{O}(m)$ in the number $m$ of partial programs for highly structured domains such as strings. We extend this method to the complex setting of visual reasoning in the Abstraction and Reasoning Corpus (ARC) for which ILP methods were previously infeasible.
• Abstract（参考訳）: 検索ベースのプログラム合成における大きなボトルネックは、大規模プログラムの学習を難なくする指数関数的に増加する検索空間である。 構造化されたドメインでは、論理的仕様はより小さく、補完的なソリューションプログラムに分解されることが多い。 大規模プログラムの探索を複数の小さなプログラム合成問題に分割する例によって,構成セグメント化がプログラミングに応用可能であることを示す。 各例について,潜在タスクプログラム下での出力の再現精度を最大化する,より小さな単位への分解を探索する。 入力と出力における構成部品の構造的アライメントは、プログラム合成探索のガイドに使用されるペアワイズ対応をもたらす。 インプット/アウトプット構造を整合させるために、認知科学に起源を持つ人間の類推的推論の形式モデルであるStructure-Mapping Theory(SMT)を利用する。 構造的アライメントによる分解駆動型プログラム合成は,最小限の知識先でも文字列変換タスクの帰納的論理プログラミング(ilp)ベースラインよりも優れていることを示す。 既存の手法とは異なり、エージェントの予測精度は追加例に対して単調に増加し、文字列のような高度に構造化されたドメインに対する部分プログラムの数$m$で$\mathcal{O}(m)$の平均時間複雑性を達成する。 この手法を抽象推論コーパス (arc) における視覚推論の複雑な設定に拡張し, 従来 ilp メソッドは実現不可能であった。

関連論文リスト

• Origami: (un)folding the abstraction of recursion schemes for program synthesis [0.0]
  遺伝的プログラミングは入力仕様を満たす正しいプログラムを探索する。 特定の課題はループと再帰を扱う方法であり、終わらないプログラムを避けることである。 再帰スキーマは、データ生産と消費の組み合わせを一般化する。
  論文  参考訳（メタデータ） (2024-02-21T14:17:45Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  プログラム合成において望ましいいくつかの異なる構成一般化形式を特徴付ける。 本稿では,ExeDecを提案する。ExeDecは,実行サブゴールを予測し,各ステップでプログラム実行によって段階的に通知される問題を解くための,新しい分解ベースの戦略である。
  論文  参考訳（メタデータ） (2023-07-26T01:07:52Z)
• Hierarchical Neural Program Synthesis [19.94176152035497]
  プログラム合成は、与えられたタスク仕様を満たす人間可読プログラムを自動構築することを目的としている。 プログラムを階層的に構成することでプログラムを合成するスケーラブルなプログラム合成フレームワークを提案する。 入力/出力ペアを持つ文字列変換領域において,提案するフレームワークを広範囲に評価する。
  論文  参考訳（メタデータ） (2023-03-09T18:20:07Z)
• Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages [97.58968222942173]
  入力出力の例からCプログラムを合成する第一歩を踏み出す。 特に,部分生成プログラムの実行を近似するために潜在表現を学習するLa Synthを提案する。 これらのプログラムのトレーニングにより,Karel と C のプログラム合成における予測性能がさらに向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T02:21:32Z)
• Differentiable Inductive Logic Programming for Structured Examples [6.8774606688738995]
  雑音や構造化例から論理プログラムを学ぶための新しいフレームワークを提案する。 我々の新しいフレームワークは、シーケンスやツリーなど、ノイズや構造化された例から論理プログラムを学習できることを示します。 我々のフレームワークは、関数記号を持つ複数の節からなる複雑なプログラムを扱うためにスケールできる。
  論文  参考訳（メタデータ） (2021-03-02T13:47:33Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  プログラム合成エンジンにおける部分的なプログラム表現手法について紹介する。 モジュラーニューラルネットワークとして実装された近似実行モデルを学ぶ。 これらのハイブリッドニューロシンボリック表現は、実行誘導型シンセサイザーがより強力な言語構成を使うことができることを示す。
  論文  参考訳（メタデータ） (2020-12-23T20:40:18Z)
• Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
  プログラム合成や文書要約などの多くのシーケンス学習タスクにおいて、重要な問題は出力シーケンスの広い空間を探索することである。 本稿では,検索対象とする出力の表現を学習することを提案する。 本稿では,まず入力/出力サンプルから離散潜在コードを予測するプログラム合成手法であるemphLatent Programmerを紹介し,そのプログラムを対象言語で生成する。
  論文  参考訳（メタデータ） (2020-12-01T10:11:35Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  プログラムのボトムアップ検索に学習を活用する新しい合成手法を提案する。 特に、入力出力例のセットに基づいて、探索条件中の中間値の合成を優先順位付けするようにモデルを訓練する。 単純な教師付き学習アプローチであっても,学習とボトムアップ検索の組み合わせは極めて効果的であることを示す。
  論文  参考訳（メタデータ） (2020-07-28T17:46:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。