論文の概要: Equivalence of Dataflow Graphs via Rewrite Rules Using a
Graph-to-Sequence Neural Model
- arxiv url: http://arxiv.org/abs/2002.06799v2
- Date: Thu, 3 Jun 2021 21:40:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 12:25:31.924322
- Title: Equivalence of Dataflow Graphs via Rewrite Rules Using a
Graph-to-Sequence Neural Model
- Title（参考訳）: Graph-to-Sequence Neural Modelを用いたリライトルールによるデータフローグラフの等価性
- Authors: Steve Kommrusch, Th\'eo Barollet, Louis-No\"el Pouchet
- Abstract要約: 本研究では,2つのプログラム間の等価性の問題を,セマンティクスに則った書き直し規則の集合を一方から他方へ保存する問題として定式化する。
そこで我々は,プログラム等価性のための最初のグラフからシーケンスまでのニューラルネットワークシステムを開発した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we target the problem of provably computing the equivalence
between two programs represented as dataflow graphs. To this end, we formalize
the problem of equivalence between two programs as finding a set of
semantics-preserving rewrite rules from one into the other, such that after the
rewrite the two programs are structurally identical, and therefore trivially
equivalent. We then develop the first graph-to-sequence neural network system
for program equivalence, trained to produce such rewrite sequences from a
carefully crafted automatic example generation algorithm. We extensively
evaluate our system on a rich multi-type linear algebra expression language,
using arbitrary combinations of 100+ graph-rewriting axioms of equivalence. Our
system outputs via inference a correct rewrite sequence for 96% of the 10,000
program pairs isolated for testing, using 30-term programs. And in all cases,
the validity of the sequence produced and therefore the provable assertion of
program equivalence is computable, in negligible time.
- Abstract（参考訳）: 本研究では,データフローグラフとして表される2つのプログラム間の等価性を確実に計算する問題を対象としている。
この目的のために、我々は2つのプログラム間の等価性の問題を、セマンティクスを保存した書き直し規則の集合を1つずつ探すこととして定式化し、その2つのプログラムは構造的に同一であり、従って自明に等価である。
次に,プログラム等価性のための最初のグラフ・ツー・シーケンスニューラルネットワークシステムを開発し,注意深い自動サンプル生成アルゴリズムからそのような書き換えシーケンスを生成するように訓練した。
我々は,100以上のグラフ書き換え公理の任意の組み合わせを用いて,リッチな多型線形代数表現言語上でのシステムを広範囲に評価した。
テスト用に分離された1万個のプログラムペアのうち、96%が30日間のプログラムを使用して正しい書き直しシーケンスを推論して出力する。
いずれの場合も、生成されたシーケンスの妥当性と、プログラム等価性の証明可能なアサーションは、無視可能な時間で計算可能である。
関連論文リスト
- An Expressive Trace Logic for Recursive Programs [0.36832029288386137]
本稿では, 2進状態述語, チョップ, 最小不動点に基づく, トレース式上の表現論理について述べる。
プログラムとトレース公式の両方に、直接的なスタイル、完全な構成的、意味論的意味論が備わっている。
我々の結果は、プログラミング構造と論理連結体との対応に光を当てた。
論文 参考訳（メタデータ） (2024-11-20T08:35:29Z) - Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
本研究では、動的プログラミング(DP)にインスパイアされた最大独立集合(MIS)問題を解決するグラフニューラルネットワーク(GNN)フレームワークを提案する。
GNNをベースとしたDPライクな再帰アルゴリズムを提案し、まず2つの小さなサブグラフを構築し、より大きなMISを持つサブグラフを予測し、次に再帰呼び出しを行う。
MISサイズに関する異なるグラフの比較を注釈付けすると、自己学習プロセスが発生し、比較をより正確に自己アノテーションし、その逆も引き起こされる。
論文 参考訳（メタデータ） (2023-10-28T10:58:25Z) - Hierarchical Phrase-based Sequence-to-Sequence Learning [94.10257313923478]
本稿では、学習中の帰納バイアスの源として階層的フレーズを取り入れ、推論中の明示的な制約として、標準的なシーケンス・ツー・シーケンス(seq2seq)モデルの柔軟性を維持するニューラルトランスデューサについて述べる。
本手法では,木が原文と対象句を階層的に整列するブラケット文法に基づく識別的導出法と,整列した句を1対1で翻訳するニューラルネットワークセク2セックモデルという2つのモデルを訓練する。
論文 参考訳（メタデータ） (2022-11-15T05:22:40Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - Binary Diffing as a Network Alignment Problem via Belief Propagation [0.0]
本稿では,プログラムのコールグラフ上でのグラフ編集問題の特別な事例として,この問題の新しい定式化を導入する。
この定式化はネットワークアライメント問題と等価であることを示す。
我々は,QBinDiffと呼ばれる手法のプロトタイプを実装し,この手法がアートディファリングツールの状況より優れていることを示す広範囲な評価手法を提案する。
論文 参考訳（メタデータ） (2021-12-31T07:54:11Z) - Self-Supervised Learning to Prove Equivalence Between Straight-Line
Programs via Rewrite Rules [9.1570563482476]
2つのプログラムは、1つのプログラムをもう1つのプログラムに書き換える、書き換え規則の一連の適用が存在する場合と同値である。
本稿では,プログラムペア間の等価性の証明を生成するために,トランスフォーマーモデルに基づくニューラルネットワークアーキテクチャを提案する。
我々のシステムであるS4Eqは、1万対の等価プログラムをキュレートしたデータセット上で97%の証明成功を達成した。
論文 参考訳（メタデータ） (2021-09-22T01:37:08Z) - Enforcing Consistency in Weakly Supervised Semantic Parsing [68.2211621631765]
本稿では,関連する入力に対する出力プログラム間の整合性を利用して,スプリアスプログラムの影響を低減することを提案する。
より一貫性のあるフォーマリズムは、一貫性に基づくトレーニングを必要とせずに、モデルパフォーマンスを改善することにつながります。
論文 参考訳（メタデータ） (2021-07-13T03:48:04Z) - Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of
Greedy Algorithm [20.582965700659788]
我々は、最も単純なアルゴリズムであるGREEDYの競合比を、関連する離散過程を連続的に近似することによって推定する。
驚くべきことに、GREEDYは、オンラインマッチングのためのもう1つの有名なアルゴリズムであるRANKINGよりも優れたパフォーマンスを保証することができる。
論文 参考訳（メタデータ） (2021-07-02T12:18:19Z) - Structured Reordering for Modeling Latent Alignments in Sequence
Transduction [86.94309120789396]
本稿では,分離可能な置換の辺りを正確に推定する効率的な動的プログラミングアルゴリズムを提案する。
結果のSeq2seqモデルは、合成問題やNLPタスクの標準モデルよりも体系的な一般化が優れている。
論文 参考訳（メタデータ） (2021-06-06T21:53:54Z) - Proving Equivalence Between Complex Expressions Using Graph-to-Sequence
Neural Models [0.0]
プログラム同値性のためのグラフ・ツー・シーケンスニューラルネットワークシステムを開発した。
我々は、リッチな多型線形代数表現言語を用いて、我々のシステムを広範囲に評価する。
我々の機械学習システムは、全ての真正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の正の
論文 参考訳（メタデータ） (2021-06-01T20:45:42Z) - Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence
Lip-Reading [96.48553941812366]
唇読解は唇運動系列から音声内容を推測することを目的としている。
seq2seqモデルの伝統的な学習プロセスには2つの問題がある。
本稿では,これら2つの問題に対処するために,PCPGに基づく新しい手法を提案する。
論文 参考訳（メタデータ） (2020-03-09T09:12:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。