論文の概要: SAT-DIFF: A Tree Diffing Framework Using SAT Solving
- arxiv url: http://arxiv.org/abs/2404.04731v1
- Date: Sat, 6 Apr 2024 21:22:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-09 19:50:28.748797
- Title: SAT-DIFF: A Tree Diffing Framework Using SAT Solving
- Title（参考訳）: SAT-DIFF:SATソルビングを用いたツリーディフティングフレームワーク
- Authors: Chuqin Geng, Haolin Ye, Yihan Zhang, Brigitte Pientka, Xujie Si,
- Abstract要約: そこで我々は,構造微分問題をMaxSAT問題に再構成する,SatDiffと呼ばれる新しい木回折手法を提案する。
ソースツリーからターゲットツリーへの変換をエンコードすることで、SatDiffは正式な保証付きで正しい、最小限の、タイプセーフな低レベルの編集スクリプトを生成する。
実験の結果、SatDiffは、合理的なランタイムを維持しながら、簡潔さの点で、既存のアプローチよりも優れていることが示されています。
- 参考スコア（独自算出の注目度）: 10.986558595502725
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computing differences between tree-structured data is a critical but challenging problem in software analysis. In this paper, we propose a novel tree diffing approach called SatDiff, which reformulates the structural diffing problem into a MaxSAT problem. By encoding the necessary transformations from the source tree to the target tree, SatDiff generates correct, minimal, and type safe low-level edit scripts with formal guarantees. We then synthesize concise high-level edit scripts by effectively merging low-level edits in the appropriate topological order. Our empirical results demonstrate that SatDiff outperforms existing heuristic-based approaches by a significant margin in terms of conciseness while maintaining a reasonable runtime.
- Abstract（参考訳）: 木構造データ間のコンピューティングの違いは、ソフトウェア分析において重要な問題であるが難しい問題である。
本稿では,構造微分問題をMaxSAT問題に再構成する,SatDiffと呼ばれる新しい木回折手法を提案する。
ソースツリーからターゲットツリーへの変換をエンコードすることで、SatDiffは正式な保証付きで正しい、最小限の、タイプセーフな低レベルの編集スクリプトを生成する。
次に、適切なトポロジ的順序で効果的に低レベル編集をマージすることで、簡潔な高レベル編集スクリプトを合成する。
実験の結果、SatDiffは、合理的なランタイムを維持しながら簡潔さの点で、既存のヒューリスティックなアプローチよりも優れていることが示された。
関連論文リスト
- Parse Trees Guided LLM Prompt Compression [20.61121589698341]
本稿では、PartPromptと呼ばれる新しい選択的圧縮手法を提案する。
まず、言語規則に基づいて各文のパースツリーを取得し、パースツリーの各ノードのローカル情報エントロピーを算出する。
実験によると、PartPromptはさまざまなデータセットで最先端のパフォーマンスを受信している。
論文 参考訳（メタデータ） (2024-09-23T06:21:40Z) - Tree Prompting: Efficient Task Adaptation without Fine-Tuning [112.71020326388029]
Tree Promptingはプロンプトの決定ツリーを構築し、複数のLMコールをリンクしてタスクを解決する。
分類データセットの実験により、Tree Promptingは競合するメソッドよりも精度が向上し、微調整と競合することが示された。
論文 参考訳（メタデータ） (2023-10-21T15:18:22Z) - Structured Dialogue Discourse Parsing [79.37200787463917]
談話解析は、多人数会話の内部構造を明らかにすることを目的としている。
本稿では,符号化と復号化という2つの観点から,従来の作業を改善する原理的手法を提案する。
実験の結果,本手法は,STACでは2.3,Mollweniでは1.5,先行モデルでは2.3を上回った。
論文 参考訳（メタデータ） (2023-06-26T22:51:01Z) - Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
従来,数式表現の2次木構造を考慮に入れたモデルでは,性能が向上した。
本稿では、出力構造を統一するために、任意のM枝(M-tree)を持つ木を適用した構造統一M-Tree符号化(S-UMCr)を提案する。
広く使われているMAWPSとMath23Kデータセットの実験結果は、SUMC-rが複数の最先端モデルを上回るだけでなく、低リソース条件下でもはるかに優れた性能を発揮することを示した。
論文 参考訳（メタデータ） (2022-10-22T12:20:36Z) - FastKASSIM: A Fast Tree Kernel-Based Syntactic Similarity Metric [48.66580267438049]
我々は,発話レベルと文書レベルの構文的類似性の指標であるFastKASSIMを提案する。
ツリーカーネルに基づいたドキュメントのペア間で、最も類似した依存関係解析ツリーをペア化し、平均化する。
r/ChangeMyViewコーパス内のドキュメントのベースラインメソッドよりも最大5.2倍高速に動作します。
論文 参考訳（メタデータ） (2022-03-15T22:33:26Z) - Fast-R2D2: A Pretrained Recursive Neural Network based on Pruned CKY for
Grammar Induction and Text Representation [41.51966652141165]
推論中に並列符号化が可能なモデルベースプルーニング法を提案する。
実験により,我々のFast-R2D2は,下流分類タスクにおける文法誘導および競合結果において,性能を著しく向上することが示された。
論文 参考訳（メタデータ） (2022-03-01T07:54:44Z) - Incorporating Constituent Syntax for Coreference Resolution [50.71868417008133]
本稿では,構成構文構造をグラフベースで組み込む手法を提案する。
また、高次近傍情報を利用して構成木に富んだ構造をエンコードすることも検討する。
on the English and Chinese parts of OntoNotes 5.0 benchmark shows that our proposed model beats a strong baseline or a new-of-the-art performance。
論文 参考訳（メタデータ） (2022-02-22T07:40:42Z) - Structural Optimization Makes Graph Classification Simpler and Better [5.770986723520119]
モデル学習プロセスを簡素化しつつ,グラフ分類性能の向上の可能性を検討する。
構造情報アセスメントの進歩に触発されて、グラフから木をコードするデータサンプルを最適化する。
本稿では,木カーネルと畳み込みネットワークにこのスキームを実装し,グラフ分類を行う。
論文 参考訳（メタデータ） (2021-09-05T08:54:38Z) - Recursive Tree Grammar Autoencoders [3.791857415239352]
本稿では,木をボトムアップ文法で符号化し,木を木文法で復号する,新しいオートエンコーダ手法を提案する。
提案手法は, 4つのベンチマークデータセットにおいて, 自動符号化誤差, トレーニング時間, 最適化スコアを改善することを実験的に示す。
論文 参考訳（メタデータ） (2020-12-03T17:37:25Z) - Tree-structured Attention with Hierarchical Accumulation [103.47584968330325]
階層的累積」は解析木構造を一定時間複雑度で自己注意に符号化する。
提案手法は,4つの IWSLT 翻訳タスクと WMT'14 翻訳タスクにおいて,SOTA 法より優れている。
論文 参考訳（メタデータ） (2020-02-19T08:17:00Z) - The Tree Ensemble Layer: Differentiability meets Conditional Computation [8.40843862024745]
我々は、異なる決定木(ソフトツリー)のアンサンブルからなるニューラルネットワークのための新しいレイヤを導入する。
異なる木は文学において有望な結果を示すが、典型的には条件計算をサポートしないため、訓練と推論が遅い。
我々は、空間性を利用する特殊前方及び後方伝播アルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-02-18T18:05:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。