論文の概要: Optimal Program Synthesis Over Noisy Data
- arxiv url: http://arxiv.org/abs/2103.05030v1
- Date: Mon, 8 Mar 2021 19:39:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-10 14:46:11.030199
- Title: Optimal Program Synthesis Over Noisy Data
- Title（参考訳）: 雑音データによる最適プログラム合成
- Authors: Shivam Handa and Martin Rinard
- Abstract要約: 我々は,ノイズデータ上でプログラムを合成するタスクを探索し,定式化する。
ノイズ源,入力源,プログラム上の事前分布の概念を定式化することにより,ノイズの多いデータセットを構成する確率過程を定式化する。
- 参考スコア（独自算出の注目度）: 6.807275190841031
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explore and formalize the task of synthesizing programs over noisy data,
i.e., data that may contain corrupted input-output examples. By formalizing the
concept of a Noise Source, an Input Source, and a prior distribution over
programs, we formalize the probabilistic process which constructs a noisy
dataset. This formalism allows us to define the correctness of a synthesis
algorithm, in terms of its ability to synthesize the hidden underlying program.
The probability of a synthesis algorithm being correct depends upon the match
between the Noise Source and the Loss Function used in the synthesis
algorithm's optimization process. We formalize the concept of an optimal Loss
Function given prior information about the Noise Source. We provide a technique
to design optimal Loss Functions given perfect and imperfect information about
the Noise Sources. We also formalize the concept and conditions required for
convergence, i.e., conditions under which the probability that the synthesis
algorithm produces a correct program increases as the size of the noisy data
set increases. This paper presents the first formalization of the concept of
optimal Loss Functions, the first closed form definition of optimal Loss
Functions, and the first conditions that ensure that a noisy synthesis
algorithm will have convergence guarantees.
- Abstract（参考訳）: ノイズの多いデータ、すなわち破損した入出力サンプルを含む可能性のあるデータに対してプログラムを合成するタスクを探索し、定式化する。
ノイズ源,入力源,プログラム上の事前分布の概念を定式化することにより,ノイズの多いデータセットを構成する確率過程を定式化する。
この形式化により、隠れたプログラムを合成する能力の観点から、合成アルゴリズムの正確性を定義することができる。
合成アルゴリズムが正しい確率は、合成アルゴリズムの最適化プロセスで使用されるノイズ源と損失関数のマッチングに依存する。
ノイズ源に関する事前情報を与えられた最適損失関数の概念を定式化する。
ノイズ源に関する完全かつ不完全な情報を与える最適損失関数を設計する手法を提案する。
また、収束に必要な概念や条件、すなわち合成アルゴリズムが正しいプログラムを生成する確率が、ノイズの多いデータセットのサイズが大きくなるにつれて増加する条件を定式化する。
本稿では、最適損失関数の概念の最初の形式化、最適損失関数の最初の閉形式定義、およびノイズの多い合成アルゴリズムが収束を保証することを保証する最初の条件について述べる。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Optimal adaptation of surface-code decoders to local noise [0.0]
量子デバイスのノイズ特性は、量子エラー訂正符号の性能向上に利用することができる。
本稿では,表面符号デコーダの雑音特性への適応が性能改善につながる範囲を最大化する手法を提案する。
論文 参考訳（メタデータ） (2024-03-13T17:12:33Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。
本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
論文 参考訳（メタデータ） (2023-06-13T01:18:16Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Probabilistic unitary synthesis with optimal accuracy [1.0923877073891446]
ユニタリ合成は、ターゲットのユニタリ変換を最適に近似するゲートシーケンスを見つけることである。
本稿では,現在の確率論的合成アルゴリズムの最適性について述べる。
単一量子ユニタリに対する効率的な確率的合成アルゴリズムを構築し、その時間的複雑性を厳密に推定し、決定論的アルゴリズムと比較して近似誤差を2次的に減少させることを示す。
論文 参考訳（メタデータ） (2023-01-16T08:37:34Z) - PriorGrad: Improving Conditional Denoising Diffusion Models with
Data-Driven Adaptive Prior [103.00403682863427]
条件拡散モデルの効率を改善するために, PreGrad を提案する。
PriorGradはデータとパラメータの効率を向上し、品質を向上する。
論文 参考訳（メタデータ） (2021-06-11T14:04:03Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Matrix completion based on Gaussian belief propagation [5.685589351789462]
行列ファクタリゼーションに基づく雑音マトリクス補完問題に対するメッセージパッシングアルゴリズムの開発を行う。
近似メッセージパッシングの文献によく用いられる摂動処理を適用することにより,提案アルゴリズムのメモリフレンドリーなバージョンを導出する。
合成データセットの実験により, 提案アルゴリズムは, 先行アルゴリズムが最適となる条件下では, ほぼ同じ性能を示すが, 非ガウス雑音により観測されたデータセットが破損した場合に有利であることがわかった。
論文 参考訳（メタデータ） (2021-05-01T12:16:49Z) - Inductive Program Synthesis over Noisy Datasets using Abstraction
Refinement Based Optimization [6.807275190841031]
ノイズの多いデータセット上でのプログラム合成を解くための新しい合成アルゴリズムを提案する。
本アルゴリズムはプログラムの合成に抽象的洗練度に基づく最適化プロセスを用いる。
sygus 2018ベンチマークスイートを用いて,現在のノイズの多いプログラム合成システムと比較した。
論文 参考訳（メタデータ） (2021-04-27T16:45:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。