論文の概要: Inductive Program Synthesis over Noisy Datasets using Abstraction Refinement Based Optimization

• arxiv url: http://arxiv.org/abs/2104.13315v1
• Date: Tue, 27 Apr 2021 16:45:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-28 13:16:36.949891
• Title: Inductive Program Synthesis over Noisy Datasets using Abstraction Refinement Based Optimization
• Title（参考訳）: 抽象洗練に基づく最適化によるノイズデータセット上の帰納的プログラム合成
• Authors: Shivam Handa and Martin Rinard
• Abstract要約: ノイズの多いデータセット上でのプログラム合成を解くための新しい合成アルゴリズムを提案する。 本アルゴリズムはプログラムの合成に抽象的洗練度に基づく最適化プロセスを用いる。 sygus 2018ベンチマークスイートを用いて,現在のノイズの多いプログラム合成システムと比較した。
• 参考スコア（独自算出の注目度）: 6.807275190841031
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a new synthesis algorithm to solve program synthesis over noisy datasets, i.e., data that may contain incorrect/corrupted input-output examples. Our algorithm uses an abstraction refinement based optimization process to synthesize programs which optimize the tradeoff between the loss over the noisy dataset and the complexity of the synthesized program. The algorithm uses abstractions to divide the search space of programs into subspaces by computing an abstract value that represents outputs for all programs in a subspace. The abstract value allows our algorithm to compute, for each subspace, a sound approximate lower bound of the loss over all programs in the subspace. It iteratively refines these abstractions to further subdivide the space into smaller subspaces, prune subspaces that do not contain an optimal program, and eventually synthesize an optimal program. We implemented this algorithm in a tool called Rose. We compare Rose to a current state-of-the-art noisy program synthesis system using the SyGuS 2018 benchmark suite. Our evaluation demonstrates that Rose significantly outperforms this previous system: on two noisy benchmark program synthesis problems sets drawn from the SyGus 2018 benchmark suite, Rose delivers speedups of up to 1587 and 81.7, with median speedups of 20.5 and 81.7. Rose also terminates on 20 (out of 54) and 4 (out of 11) more benchmark problems than the previous system. Both Rose and the previous system synthesize programs that are optimal over the provided noisy data sets. For the majority of the problems in the benchmark sets ($272$ out of $286$), the synthesized programs also produce correct outputs for all inputs in the original (unseen) noise-free data set. These results highlight the benefits that Rose can deliver for effective noisy program synthesis.
• Abstract（参考訳）: ノイズの多いデータセット、すなわち不正/誤入力出力例を含む可能性のあるデータに対して、プログラム合成を解くための新しい合成アルゴリズムを提案する。 本アルゴリズムでは, ノイズデータセット上の損失と合成プログラムの複雑さとのトレードオフを最適化するプログラムを, 抽象化による最適化プロセスを用いて合成する。 このアルゴリズムは、サブスペース内の全てのプログラムの出力を表す抽象値を計算することで、プログラムの検索空間をサブスペースに分割するために抽象化を使用する。 抽象的な値は,各部分空間に対して,その部分空間内の全てのプログラムに対する損失の音の近似下界を計算できる。 反復的にこれらの抽象化を洗練し、空間をより小さな部分空間、最適なプログラムを含まないプルーン部分空間に分割し、最終的に最適なプログラムを合成する。 我々はこのアルゴリズムをRoseというツールで実装した。 sygus 2018ベンチマークスイートを用いて,現在のノイズの多いプログラム合成システムと比較した。 SyGus 2018ベンチマークスイートから引き出された2つのノイズの多いベンチマークプログラム合成問題において、Roseは最大1587と81.7のスピードアップを提供し、中央値は20.5と81.7である。 Roseはまた、以前のシステムよりも20(54点中)と4(11点中)のベンチマーク問題を終了する。 roseと以前のシステムは、提供された騒がしいデータセットよりも最適なプログラムを合成する。 ベンチマークセットのほとんどの問題(286ドルのうち272ドル)に対して、合成プログラムは元の(目に見えない)ノイズフリーデータセットのすべての入力に対して正しい出力を生成する。 これらの結果は、Roseが効果的なノイズの多いプログラム合成にもたらすメリットを強調している。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Amortizing Pragmatic Program Synthesis with Rankings [17.775664476910247]
  合理的音声法(RSA)フレームワークの使用は、プログラムシンセサイザーの構築に成功している。 遅くて正確なRSAシンセサイザーを再生する一般的な方法を提案する。
  論文  参考訳（メタデータ） (2024-06-01T22:55:33Z)
• Iterative Genetic Improvement: Scaling Stochastic Program Synthesis [11.195558777385259]
  プログラム合成は、与えられた仕様を満たす基礎となるプログラミング言語からプログラムを自動的に見つけることを目的としている。 既存のプログラム合成技術はこの期待を十分に満たさず、スケーラビリティの問題に悩まされている。 本稿では、この問題を解決するために反復的遺伝的改善と呼ばれるプログラム合成の新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2022-02-26T02:00:35Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Synthesizing Optimal Parallelism Placement and Reduction Strategies on Hierarchical Systems for Deep Learning [0.3345437353879254]
  本稿では,複数並列化形式を階層型加速器系にマッピングする手法を提案する。 我々は、これらのマッピングが全再現性能(最大448倍)に与える影響を実験的に検証した。 我々は1つ以上の並列化軸を集合列に分解できる新しい構文誘導型プログラム合成フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-10-20T13:05:49Z)
• Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages [97.58968222942173]
  入力出力の例からCプログラムを合成する第一歩を踏み出す。 特に,部分生成プログラムの実行を近似するために潜在表現を学習するLa Synthを提案する。 これらのプログラムのトレーニングにより,Karel と C のプログラム合成における予測性能がさらに向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T02:21:32Z)
• Optimal Program Synthesis Over Noisy Data [6.807275190841031]
  我々は,ノイズデータ上でプログラムを合成するタスクを探索し,定式化する。 ノイズ源,入力源,プログラム上の事前分布の概念を定式化することにより,ノイズの多いデータセットを構成する確率過程を定式化する。
  論文  参考訳（メタデータ） (2021-03-08T19:39:13Z)
• Optimal Neural Program Synthesis from Multimodal Specifications [45.35689345004124]
  マルチモーダルプログラム合成は、プログラム合成を挑戦的な設定に拡張する魅力的な方法である。 本稿では,ユーザが提供する制約を満たすプログラムを見つけることを目的とした,最適なニューラルシンセサイザー手法を提案する。
  論文  参考訳（メタデータ） (2020-10-04T20:51:21Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  プログラムのボトムアップ検索に学習を活用する新しい合成手法を提案する。 特に、入力出力例のセットに基づいて、探索条件中の中間値の合成を優先順位付けするようにモデルを訓練する。 単純な教師付き学習アプローチであっても,学習とボトムアップ検索の組み合わせは極めて効果的であることを示す。
  論文  参考訳（メタデータ） (2020-07-28T17:46:18Z)
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis [81.54148730967394]
  本稿では,合成,実行,デバッグの段階を組み込んだニューラルネットワーク生成フレームワークであるSEDを提案する。 SEDはまず、神経プログラムシンセサイザーコンポーネントを使用して初期プログラムを生成し、その後、神経プログラムデバッガを使用して生成されたプログラムを反復的に修復する。 挑戦的な入出力プログラム合成ベンチマークであるKarelでは、SEDはニューラルプログラムシンセサイザー自体のエラー率をかなりのマージンで削減し、デコードのための標準ビームサーチより優れている。
  論文  参考訳（メタデータ） (2020-07-16T04:15:47Z)

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

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